1/* Perform branch target register load optimizations. 2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "rtl.h" 27#include "hard-reg-set.h" 28#include "regs.h" 29#include "fibheap.h" 30#include "output.h" 31#include "target.h" 32#include "expr.h" 33#include "flags.h" 34#include "insn-attr.h" 35#include "function.h" 36#include "except.h" 37#include "tm_p.h" 38#include "toplev.h" 39#include "tree-pass.h" 40 41/* Target register optimizations - these are performed after reload. */ 42 43typedef struct btr_def_group_s 44{ 45 struct btr_def_group_s *next; 46 rtx src; 47 struct btr_def_s *members; 48} *btr_def_group; 49 50typedef struct btr_user_s 51{ 52 struct btr_user_s *next; 53 basic_block bb; 54 int luid; 55 rtx insn; 56 /* If INSN has a single use of a single branch register, then 57 USE points to it within INSN. If there is more than 58 one branch register use, or the use is in some way ambiguous, 59 then USE is NULL. */ 60 rtx use; 61 int n_reaching_defs; 62 int first_reaching_def; 63 char other_use_this_block; 64} *btr_user; 65 66/* btr_def structs appear on three lists: 67 1. A list of all btr_def structures (head is 68 ALL_BTR_DEFS, linked by the NEXT field). 69 2. A list of branch reg definitions per basic block (head is 70 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field). 71 3. A list of all branch reg definitions belonging to the same 72 group (head is in a BTR_DEF_GROUP struct, linked by 73 NEXT_THIS_GROUP field). */ 74 75typedef struct btr_def_s 76{ 77 struct btr_def_s *next_this_bb; 78 struct btr_def_s *next_this_group; 79 basic_block bb; 80 int luid; 81 rtx insn; 82 int btr; 83 int cost; 84 /* For a branch register setting insn that has a constant 85 source (i.e. a label), group links together all the 86 insns with the same source. For other branch register 87 setting insns, group is NULL. */ 88 btr_def_group group; 89 btr_user uses; 90 /* If this def has a reaching use which is not a simple use 91 in a branch instruction, then has_ambiguous_use will be true, 92 and we will not attempt to migrate this definition. */ 93 char has_ambiguous_use; 94 /* live_range is an approximation to the true live range for this 95 def/use web, because it records the set of blocks that contain 96 the live range. There could be other live ranges for the same 97 branch register in that set of blocks, either in the block 98 containing the def (before the def), or in a block containing 99 a use (after the use). If there are such other live ranges, then 100 other_btr_uses_before_def or other_btr_uses_after_use must be set true 101 as appropriate. */ 102 char other_btr_uses_before_def; 103 char other_btr_uses_after_use; 104 /* We set own_end when we have moved a definition into a dominator. 105 Thus, when a later combination removes this definition again, we know 106 to clear out trs_live_at_end again. */ 107 char own_end; 108 bitmap live_range; 109} *btr_def; 110 111static int issue_rate; 112 113static int basic_block_freq (basic_block); 114static int insn_sets_btr_p (rtx, int, int *); 115static rtx *find_btr_use (rtx); 116static int btr_referenced_p (rtx, rtx *); 117static int find_btr_reference (rtx *, void *); 118static void find_btr_def_group (btr_def_group *, btr_def); 119static btr_def add_btr_def (fibheap_t, basic_block, int, rtx, 120 unsigned int, int, btr_def_group *); 121static btr_user new_btr_user (basic_block, int, rtx); 122static void dump_hard_reg_set (HARD_REG_SET); 123static void dump_btrs_live (int); 124static void note_other_use_this_block (unsigned int, btr_user); 125static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *, 126 sbitmap *, sbitmap *, HARD_REG_SET *); 127static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *); 128static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int); 129static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int); 130static void build_btr_def_use_webs (fibheap_t); 131static int block_at_edge_of_live_range_p (int, btr_def); 132static void clear_btr_from_live_range (btr_def def); 133static void add_btr_to_live_range (btr_def, int); 134static void augment_live_range (bitmap, HARD_REG_SET *, basic_block, 135 basic_block, int); 136static int choose_btr (HARD_REG_SET); 137static void combine_btr_defs (btr_def, HARD_REG_SET *); 138static void btr_def_live_range (btr_def, HARD_REG_SET *); 139static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *); 140static int migrate_btr_def (btr_def, int); 141static void migrate_btr_defs (enum reg_class, int); 142static int can_move_up (basic_block, rtx, int); 143static void note_btr_set (rtx, rtx, void *); 144 145/* The following code performs code motion of target load instructions 146 (instructions that set branch target registers), to move them 147 forward away from the branch instructions and out of loops (or, 148 more generally, from a more frequently executed place to a less 149 frequently executed place). 150 Moving target load instructions further in front of the branch 151 instruction that uses the target register value means that the hardware 152 has a better chance of preloading the instructions at the branch 153 target by the time the branch is reached. This avoids bubbles 154 when a taken branch needs to flush out the pipeline. 155 Moving target load instructions out of loops means they are executed 156 less frequently. */ 157 158/* An obstack to hold the def-use web data structures built up for 159 migrating branch target load instructions. */ 160static struct obstack migrate_btrl_obstack; 161 162/* Array indexed by basic block number, giving the set of registers 163 live in that block. */ 164static HARD_REG_SET *btrs_live; 165 166/* Array indexed by basic block number, giving the set of registers live at 167 the end of that block, including any uses by a final jump insn, if any. */ 168static HARD_REG_SET *btrs_live_at_end; 169 170/* Set of all target registers that we are willing to allocate. */ 171static HARD_REG_SET all_btrs; 172 173/* Provide lower and upper bounds for target register numbers, so that 174 we don't need to search through all the hard registers all the time. */ 175static int first_btr, last_btr; 176 177 178 179/* Return an estimate of the frequency of execution of block bb. */ 180static int 181basic_block_freq (basic_block bb) 182{ 183 return bb->frequency; 184} 185 186static rtx *btr_reference_found; 187 188/* A subroutine of btr_referenced_p, called through for_each_rtx. 189 PREG is a pointer to an rtx that is to be excluded from the 190 traversal. If we find a reference to a target register anywhere 191 else, return 1, and put a pointer to it into btr_reference_found. */ 192static int 193find_btr_reference (rtx *px, void *preg) 194{ 195 rtx x; 196 int regno, i; 197 198 if (px == preg) 199 return -1; 200 x = *px; 201 if (!REG_P (x)) 202 return 0; 203 regno = REGNO (x); 204 for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--) 205 if (TEST_HARD_REG_BIT (all_btrs, regno+i)) 206 { 207 btr_reference_found = px; 208 return 1; 209 } 210 return -1; 211} 212 213/* Return nonzero if X references (sets or reads) any branch target register. 214 If EXCLUDEP is set, disregard any references within the rtx pointed to 215 by it. If returning nonzero, also set btr_reference_found as above. */ 216static int 217btr_referenced_p (rtx x, rtx *excludep) 218{ 219 return for_each_rtx (&x, find_btr_reference, excludep); 220} 221 222/* Return true if insn is an instruction that sets a target register. 223 if CHECK_CONST is true, only return true if the source is constant. 224 If such a set is found and REGNO is nonzero, assign the register number 225 of the destination register to *REGNO. */ 226static int 227insn_sets_btr_p (rtx insn, int check_const, int *regno) 228{ 229 rtx set; 230 231 if (NONJUMP_INSN_P (insn) 232 && (set = single_set (insn))) 233 { 234 rtx dest = SET_DEST (set); 235 rtx src = SET_SRC (set); 236 237 if (GET_CODE (dest) == SUBREG) 238 dest = XEXP (dest, 0); 239 240 if (REG_P (dest) 241 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest))) 242 { 243 gcc_assert (!btr_referenced_p (src, NULL)); 244 245 if (!check_const || CONSTANT_P (src)) 246 { 247 if (regno) 248 *regno = REGNO (dest); 249 return 1; 250 } 251 } 252 } 253 return 0; 254} 255 256/* Find and return a use of a target register within an instruction INSN. */ 257static rtx * 258find_btr_use (rtx insn) 259{ 260 return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL; 261} 262 263/* Find the group that the target register definition DEF belongs 264 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such 265 group exists, create one. Add def to the group. */ 266static void 267find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def) 268{ 269 if (insn_sets_btr_p (def->insn, 1, NULL)) 270 { 271 btr_def_group this_group; 272 rtx def_src = SET_SRC (single_set (def->insn)); 273 274 /* ?? This linear search is an efficiency concern, particularly 275 as the search will almost always fail to find a match. */ 276 for (this_group = *all_btr_def_groups; 277 this_group != NULL; 278 this_group = this_group->next) 279 if (rtx_equal_p (def_src, this_group->src)) 280 break; 281 282 if (!this_group) 283 { 284 this_group = obstack_alloc (&migrate_btrl_obstack, 285 sizeof (struct btr_def_group_s)); 286 this_group->src = def_src; 287 this_group->members = NULL; 288 this_group->next = *all_btr_def_groups; 289 *all_btr_def_groups = this_group; 290 } 291 def->group = this_group; 292 def->next_this_group = this_group->members; 293 this_group->members = def; 294 } 295 else 296 def->group = NULL; 297} 298 299/* Create a new target register definition structure, for a definition in 300 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return 301 the new definition. */ 302static btr_def 303add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn, 304 unsigned int dest_reg, int other_btr_uses_before_def, 305 btr_def_group *all_btr_def_groups) 306{ 307 btr_def this 308 = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s)); 309 this->bb = bb; 310 this->luid = insn_luid; 311 this->insn = insn; 312 this->btr = dest_reg; 313 this->cost = basic_block_freq (bb); 314 this->has_ambiguous_use = 0; 315 this->other_btr_uses_before_def = other_btr_uses_before_def; 316 this->other_btr_uses_after_use = 0; 317 this->next_this_bb = NULL; 318 this->next_this_group = NULL; 319 this->uses = NULL; 320 this->live_range = NULL; 321 find_btr_def_group (all_btr_def_groups, this); 322 323 fibheap_insert (all_btr_defs, -this->cost, this); 324 325 if (dump_file) 326 fprintf (dump_file, 327 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n", 328 dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"), 329 this->cost); 330 331 return this; 332} 333 334/* Create a new target register user structure, for a use in block BB, 335 instruction INSN. Return the new user. */ 336static btr_user 337new_btr_user (basic_block bb, int insn_luid, rtx insn) 338{ 339 /* This instruction reads target registers. We need 340 to decide whether we can replace all target register 341 uses easily. 342 */ 343 rtx *usep = find_btr_use (PATTERN (insn)); 344 rtx use; 345 btr_user user = NULL; 346 347 if (usep) 348 { 349 int unambiguous_single_use; 350 351 /* We want to ensure that USE is the only use of a target 352 register in INSN, so that we know that to rewrite INSN to use 353 a different target register, all we have to do is replace USE. */ 354 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep); 355 if (!unambiguous_single_use) 356 usep = NULL; 357 } 358 use = usep ? *usep : NULL_RTX; 359 user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s)); 360 user->bb = bb; 361 user->luid = insn_luid; 362 user->insn = insn; 363 user->use = use; 364 user->other_use_this_block = 0; 365 user->next = NULL; 366 user->n_reaching_defs = 0; 367 user->first_reaching_def = -1; 368 369 if (dump_file) 370 { 371 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }", 372 bb->index, INSN_UID (insn)); 373 374 if (user->use) 375 fprintf (dump_file, ": unambiguous use of reg %d\n", 376 REGNO (user->use)); 377 } 378 379 return user; 380} 381 382/* Write the contents of S to the dump file. */ 383static void 384dump_hard_reg_set (HARD_REG_SET s) 385{ 386 int reg; 387 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) 388 if (TEST_HARD_REG_BIT (s, reg)) 389 fprintf (dump_file, " %d", reg); 390} 391 392/* Write the set of target regs live in block BB to the dump file. */ 393static void 394dump_btrs_live (int bb) 395{ 396 fprintf (dump_file, "BB%d live:", bb); 397 dump_hard_reg_set (btrs_live[bb]); 398 fprintf (dump_file, "\n"); 399} 400 401/* REGNO is the number of a branch target register that is being used or 402 set. USERS_THIS_BB is a list of preceding branch target register users; 403 If any of them use the same register, set their other_use_this_block 404 flag. */ 405static void 406note_other_use_this_block (unsigned int regno, btr_user users_this_bb) 407{ 408 btr_user user; 409 410 for (user = users_this_bb; user != NULL; user = user->next) 411 if (user->use && REGNO (user->use) == regno) 412 user->other_use_this_block = 1; 413} 414 415typedef struct { 416 btr_user users_this_bb; 417 HARD_REG_SET btrs_written_in_block; 418 HARD_REG_SET btrs_live_in_block; 419 sbitmap bb_gen; 420 sbitmap *btr_defset; 421} defs_uses_info; 422 423/* Called via note_stores or directly to register stores into / 424 clobbers of a branch target register DEST that are not recognized as 425 straightforward definitions. DATA points to information about the 426 current basic block that needs updating. */ 427static void 428note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data) 429{ 430 defs_uses_info *info = data; 431 int regno, end_regno; 432 433 if (!REG_P (dest)) 434 return; 435 regno = REGNO (dest); 436 end_regno = regno + hard_regno_nregs[regno][GET_MODE (dest)]; 437 for (; regno < end_regno; regno++) 438 if (TEST_HARD_REG_BIT (all_btrs, regno)) 439 { 440 note_other_use_this_block (regno, info->users_this_bb); 441 SET_HARD_REG_BIT (info->btrs_written_in_block, regno); 442 SET_HARD_REG_BIT (info->btrs_live_in_block, regno); 443 sbitmap_difference (info->bb_gen, info->bb_gen, 444 info->btr_defset[regno - first_btr]); 445 } 446} 447 448static void 449compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, 450 btr_user *use_array, sbitmap *btr_defset, 451 sbitmap *bb_gen, HARD_REG_SET *btrs_written) 452{ 453 /* Scan the code building up the set of all defs and all uses. 454 For each target register, build the set of defs of that register. 455 For each block, calculate the set of target registers 456 written in that block. 457 Also calculate the set of btrs ever live in that block. 458 */ 459 int i; 460 int insn_luid = 0; 461 btr_def_group all_btr_def_groups = NULL; 462 defs_uses_info info; 463 464 sbitmap_vector_zero (bb_gen, n_basic_blocks); 465 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 466 { 467 basic_block bb = BASIC_BLOCK (i); 468 int reg; 469 btr_def defs_this_bb = NULL; 470 rtx insn; 471 rtx last; 472 int can_throw = 0; 473 474 info.users_this_bb = NULL; 475 info.bb_gen = bb_gen[i]; 476 info.btr_defset = btr_defset; 477 478 CLEAR_HARD_REG_SET (info.btrs_live_in_block); 479 CLEAR_HARD_REG_SET (info.btrs_written_in_block); 480 for (reg = first_btr; reg <= last_btr; reg++) 481 if (TEST_HARD_REG_BIT (all_btrs, reg) 482 && REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, reg)) 483 SET_HARD_REG_BIT (info.btrs_live_in_block, reg); 484 485 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); 486 insn != last; 487 insn = NEXT_INSN (insn), insn_luid++) 488 { 489 if (INSN_P (insn)) 490 { 491 int regno; 492 int insn_uid = INSN_UID (insn); 493 494 if (insn_sets_btr_p (insn, 0, ®no)) 495 { 496 btr_def def = add_btr_def ( 497 all_btr_defs, bb, insn_luid, insn, regno, 498 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno), 499 &all_btr_def_groups); 500 501 def_array[insn_uid] = def; 502 SET_HARD_REG_BIT (info.btrs_written_in_block, regno); 503 SET_HARD_REG_BIT (info.btrs_live_in_block, regno); 504 sbitmap_difference (bb_gen[i], bb_gen[i], 505 btr_defset[regno - first_btr]); 506 SET_BIT (bb_gen[i], insn_uid); 507 def->next_this_bb = defs_this_bb; 508 defs_this_bb = def; 509 SET_BIT (btr_defset[regno - first_btr], insn_uid); 510 note_other_use_this_block (regno, info.users_this_bb); 511 } 512 /* Check for the blockage emitted by expand_nl_goto_receiver. */ 513 else if (current_function_has_nonlocal_label 514 && GET_CODE (PATTERN (insn)) == ASM_INPUT) 515 { 516 btr_user user; 517 518 /* Do the equivalent of calling note_other_use_this_block 519 for every target register. */ 520 for (user = info.users_this_bb; user != NULL; 521 user = user->next) 522 if (user->use) 523 user->other_use_this_block = 1; 524 IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs); 525 IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs); 526 sbitmap_zero (info.bb_gen); 527 } 528 else 529 { 530 if (btr_referenced_p (PATTERN (insn), NULL)) 531 { 532 btr_user user = new_btr_user (bb, insn_luid, insn); 533 534 use_array[insn_uid] = user; 535 if (user->use) 536 SET_HARD_REG_BIT (info.btrs_live_in_block, 537 REGNO (user->use)); 538 else 539 { 540 int reg; 541 for (reg = first_btr; reg <= last_btr; reg++) 542 if (TEST_HARD_REG_BIT (all_btrs, reg) 543 && refers_to_regno_p (reg, reg + 1, user->insn, 544 NULL)) 545 { 546 note_other_use_this_block (reg, 547 info.users_this_bb); 548 SET_HARD_REG_BIT (info.btrs_live_in_block, reg); 549 } 550 note_stores (PATTERN (insn), note_btr_set, &info); 551 } 552 user->next = info.users_this_bb; 553 info.users_this_bb = user; 554 } 555 if (CALL_P (insn)) 556 { 557 HARD_REG_SET *clobbered = &call_used_reg_set; 558 HARD_REG_SET call_saved; 559 rtx pat = PATTERN (insn); 560 int i; 561 562 /* Check for sibcall. */ 563 if (GET_CODE (pat) == PARALLEL) 564 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--) 565 if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN) 566 { 567 COMPL_HARD_REG_SET (call_saved, 568 call_used_reg_set); 569 clobbered = &call_saved; 570 } 571 572 for (regno = first_btr; regno <= last_btr; regno++) 573 if (TEST_HARD_REG_BIT (*clobbered, regno)) 574 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info); 575 } 576 } 577 } 578 } 579 580 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block); 581 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block); 582 583 REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->il.rtl->global_live_at_end); 584 /* If this block ends in a jump insn, add any uses or even clobbers 585 of branch target registers that it might have. */ 586 for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); ) 587 insn = PREV_INSN (insn); 588 /* ??? for the fall-through edge, it would make sense to insert the 589 btr set on the edge, but that would require to split the block 590 early on so that we can distinguish between dominance from the fall 591 through edge - which can use the call-clobbered registers - from 592 dominance by the throw edge. */ 593 if (can_throw_internal (insn)) 594 { 595 HARD_REG_SET tmp; 596 597 COPY_HARD_REG_SET (tmp, call_used_reg_set); 598 AND_HARD_REG_SET (tmp, all_btrs); 599 IOR_HARD_REG_SET (btrs_live_at_end[i], tmp); 600 can_throw = 1; 601 } 602 if (can_throw || JUMP_P (insn)) 603 { 604 int regno; 605 606 for (regno = first_btr; regno <= last_btr; regno++) 607 if (refers_to_regno_p (regno, regno+1, insn, NULL)) 608 SET_HARD_REG_BIT (btrs_live_at_end[i], regno); 609 } 610 611 if (dump_file) 612 dump_btrs_live(i); 613 } 614} 615 616static void 617compute_kill (sbitmap *bb_kill, sbitmap *btr_defset, 618 HARD_REG_SET *btrs_written) 619{ 620 int i; 621 int regno; 622 623 /* For each basic block, form the set BB_KILL - the set 624 of definitions that the block kills. */ 625 sbitmap_vector_zero (bb_kill, n_basic_blocks); 626 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 627 { 628 for (regno = first_btr; regno <= last_btr; regno++) 629 if (TEST_HARD_REG_BIT (all_btrs, regno) 630 && TEST_HARD_REG_BIT (btrs_written[i], regno)) 631 sbitmap_a_or_b (bb_kill[i], bb_kill[i], 632 btr_defset[regno - first_btr]); 633 } 634} 635 636static void 637compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid) 638{ 639 /* Perform iterative dataflow: 640 Initially, for all blocks, BB_OUT = BB_GEN. 641 For each block, 642 BB_IN = union over predecessors of BB_OUT(pred) 643 BB_OUT = (BB_IN - BB_KILL) + BB_GEN 644 Iterate until the bb_out sets stop growing. */ 645 int i; 646 int changed; 647 sbitmap bb_in = sbitmap_alloc (max_uid); 648 649 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 650 sbitmap_copy (bb_out[i], bb_gen[i]); 651 652 changed = 1; 653 while (changed) 654 { 655 changed = 0; 656 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 657 { 658 sbitmap_union_of_preds (bb_in, bb_out, i); 659 changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i], 660 bb_in, bb_kill[i]); 661 } 662 } 663 sbitmap_free (bb_in); 664} 665 666static void 667link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, 668 sbitmap *btr_defset, int max_uid) 669{ 670 int i; 671 sbitmap reaching_defs = sbitmap_alloc (max_uid); 672 673 /* Link uses to the uses lists of all of their reaching defs. 674 Count up the number of reaching defs of each use. */ 675 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 676 { 677 basic_block bb = BASIC_BLOCK (i); 678 rtx insn; 679 rtx last; 680 681 sbitmap_union_of_preds (reaching_defs, bb_out, i); 682 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); 683 insn != last; 684 insn = NEXT_INSN (insn)) 685 { 686 if (INSN_P (insn)) 687 { 688 int insn_uid = INSN_UID (insn); 689 690 btr_def def = def_array[insn_uid]; 691 btr_user user = use_array[insn_uid]; 692 if (def != NULL) 693 { 694 /* Remove all reaching defs of regno except 695 for this one. */ 696 sbitmap_difference (reaching_defs, reaching_defs, 697 btr_defset[def->btr - first_btr]); 698 SET_BIT(reaching_defs, insn_uid); 699 } 700 701 if (user != NULL) 702 { 703 /* Find all the reaching defs for this use. */ 704 sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid); 705 unsigned int uid = 0; 706 sbitmap_iterator sbi; 707 708 if (user->use) 709 sbitmap_a_and_b ( 710 reaching_defs_of_reg, 711 reaching_defs, 712 btr_defset[REGNO (user->use) - first_btr]); 713 else 714 { 715 int reg; 716 717 sbitmap_zero (reaching_defs_of_reg); 718 for (reg = first_btr; reg <= last_btr; reg++) 719 if (TEST_HARD_REG_BIT (all_btrs, reg) 720 && refers_to_regno_p (reg, reg + 1, user->insn, 721 NULL)) 722 sbitmap_a_or_b_and_c (reaching_defs_of_reg, 723 reaching_defs_of_reg, 724 reaching_defs, 725 btr_defset[reg - first_btr]); 726 } 727 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, sbi) 728 { 729 btr_def def = def_array[uid]; 730 731 /* We now know that def reaches user. */ 732 733 if (dump_file) 734 fprintf (dump_file, 735 "Def in insn %d reaches use in insn %d\n", 736 uid, insn_uid); 737 738 user->n_reaching_defs++; 739 if (!user->use) 740 def->has_ambiguous_use = 1; 741 if (user->first_reaching_def != -1) 742 { /* There is more than one reaching def. This is 743 a rare case, so just give up on this def/use 744 web when it occurs. */ 745 def->has_ambiguous_use = 1; 746 def_array[user->first_reaching_def] 747 ->has_ambiguous_use = 1; 748 if (dump_file) 749 fprintf (dump_file, 750 "(use %d has multiple reaching defs)\n", 751 insn_uid); 752 } 753 else 754 user->first_reaching_def = uid; 755 if (user->other_use_this_block) 756 def->other_btr_uses_after_use = 1; 757 user->next = def->uses; 758 def->uses = user; 759 } 760 sbitmap_free (reaching_defs_of_reg); 761 } 762 763 if (CALL_P (insn)) 764 { 765 int regno; 766 767 for (regno = first_btr; regno <= last_btr; regno++) 768 if (TEST_HARD_REG_BIT (all_btrs, regno) 769 && TEST_HARD_REG_BIT (call_used_reg_set, regno)) 770 sbitmap_difference (reaching_defs, reaching_defs, 771 btr_defset[regno - first_btr]); 772 } 773 } 774 } 775 } 776 sbitmap_free (reaching_defs); 777} 778 779static void 780build_btr_def_use_webs (fibheap_t all_btr_defs) 781{ 782 const int max_uid = get_max_uid (); 783 btr_def *def_array = XCNEWVEC (btr_def, max_uid); 784 btr_user *use_array = XCNEWVEC (btr_user, max_uid); 785 sbitmap *btr_defset = sbitmap_vector_alloc ( 786 (last_btr - first_btr) + 1, max_uid); 787 sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid); 788 HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, n_basic_blocks); 789 sbitmap *bb_kill; 790 sbitmap *bb_out; 791 792 sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1); 793 794 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset, 795 bb_gen, btrs_written); 796 797 bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid); 798 compute_kill (bb_kill, btr_defset, btrs_written); 799 free (btrs_written); 800 801 bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid); 802 compute_out (bb_out, bb_gen, bb_kill, max_uid); 803 804 sbitmap_vector_free (bb_gen); 805 sbitmap_vector_free (bb_kill); 806 807 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid); 808 809 sbitmap_vector_free (bb_out); 810 sbitmap_vector_free (btr_defset); 811 free (use_array); 812 free (def_array); 813} 814 815/* Return true if basic block BB contains the start or end of the 816 live range of the definition DEF, AND there are other live 817 ranges of the same target register that include BB. */ 818static int 819block_at_edge_of_live_range_p (int bb, btr_def def) 820{ 821 if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb) 822 return 1; 823 else if (def->other_btr_uses_after_use) 824 { 825 btr_user user; 826 for (user = def->uses; user != NULL; user = user->next) 827 if (BASIC_BLOCK (bb) == user->bb) 828 return 1; 829 } 830 return 0; 831} 832 833/* We are removing the def/use web DEF. The target register 834 used in this web is therefore no longer live in the live range 835 of this web, so remove it from the live set of all basic blocks 836 in the live range of the web. 837 Blocks at the boundary of the live range may contain other live 838 ranges for the same target register, so we have to be careful 839 to remove the target register from the live set of these blocks 840 only if they do not contain other live ranges for the same register. */ 841static void 842clear_btr_from_live_range (btr_def def) 843{ 844 unsigned bb; 845 bitmap_iterator bi; 846 847 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) 848 { 849 if ((!def->other_btr_uses_before_def 850 && !def->other_btr_uses_after_use) 851 || !block_at_edge_of_live_range_p (bb, def)) 852 { 853 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr); 854 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); 855 if (dump_file) 856 dump_btrs_live (bb); 857 } 858 } 859 if (def->own_end) 860 CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); 861} 862 863 864/* We are adding the def/use web DEF. Add the target register used 865 in this web to the live set of all of the basic blocks that contain 866 the live range of the web. 867 If OWN_END is set, also show that the register is live from our 868 definitions at the end of the basic block where it is defined. */ 869static void 870add_btr_to_live_range (btr_def def, int own_end) 871{ 872 unsigned bb; 873 bitmap_iterator bi; 874 875 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) 876 { 877 SET_HARD_REG_BIT (btrs_live[bb], def->btr); 878 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); 879 if (dump_file) 880 dump_btrs_live (bb); 881 } 882 if (own_end) 883 { 884 SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); 885 def->own_end = 1; 886 } 887} 888 889/* Update a live range to contain the basic block NEW_BLOCK, and all 890 blocks on paths between the existing live range and NEW_BLOCK. 891 HEAD is a block contained in the existing live range that dominates 892 all other blocks in the existing live range. 893 Also add to the set BTRS_LIVE_IN_RANGE all target registers that 894 are live in the blocks that we add to the live range. 895 If FULL_RANGE is set, include the full live range of NEW_BB; 896 otherwise, if NEW_BB dominates HEAD_BB, only add registers that 897 are life at the end of NEW_BB for NEW_BB itself. 898 It is a precondition that either NEW_BLOCK dominates HEAD,or 899 HEAD dom NEW_BLOCK. This is used to speed up the 900 implementation of this function. */ 901static void 902augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range, 903 basic_block head_bb, basic_block new_bb, int full_range) 904{ 905 basic_block *worklist, *tos; 906 907 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); 908 909 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb)) 910 { 911 if (new_bb == head_bb) 912 { 913 if (full_range) 914 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]); 915 free (tos); 916 return; 917 } 918 *tos++ = new_bb; 919 } 920 else 921 { 922 edge e; 923 edge_iterator ei; 924 int new_block = new_bb->index; 925 926 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb)); 927 928 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]); 929 bitmap_set_bit (live_range, new_block); 930 /* A previous btr migration could have caused a register to be 931 live just at the end of new_block which we need in full, so 932 use trs_live_at_end even if full_range is set. */ 933 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]); 934 if (full_range) 935 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]); 936 if (dump_file) 937 { 938 fprintf (dump_file, 939 "Adding end of block %d and rest of %d to live range\n", 940 new_block, head_bb->index); 941 fprintf (dump_file,"Now live btrs are "); 942 dump_hard_reg_set (*btrs_live_in_range); 943 fprintf (dump_file, "\n"); 944 } 945 FOR_EACH_EDGE (e, ei, head_bb->preds) 946 *tos++ = e->src; 947 } 948 949 while (tos != worklist) 950 { 951 basic_block bb = *--tos; 952 if (!bitmap_bit_p (live_range, bb->index)) 953 { 954 edge e; 955 edge_iterator ei; 956 957 bitmap_set_bit (live_range, bb->index); 958 IOR_HARD_REG_SET (*btrs_live_in_range, 959 btrs_live[bb->index]); 960 /* A previous btr migration could have caused a register to be 961 live just at the end of a block which we need in full. */ 962 IOR_HARD_REG_SET (*btrs_live_in_range, 963 btrs_live_at_end[bb->index]); 964 if (dump_file) 965 { 966 fprintf (dump_file, 967 "Adding block %d to live range\n", bb->index); 968 fprintf (dump_file,"Now live btrs are "); 969 dump_hard_reg_set (*btrs_live_in_range); 970 fprintf (dump_file, "\n"); 971 } 972 973 FOR_EACH_EDGE (e, ei, bb->preds) 974 { 975 basic_block pred = e->src; 976 if (!bitmap_bit_p (live_range, pred->index)) 977 *tos++ = pred; 978 } 979 } 980 } 981 982 free (worklist); 983} 984 985/* Return the most desirable target register that is not in 986 the set USED_BTRS. */ 987static int 988choose_btr (HARD_REG_SET used_btrs) 989{ 990 int i; 991 GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up); 992 993 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 994 { 995#ifdef REG_ALLOC_ORDER 996 int regno = reg_alloc_order[i]; 997#else 998 int regno = i; 999#endif 1000 if (TEST_HARD_REG_BIT (all_btrs, regno) 1001 && !TEST_HARD_REG_BIT (used_btrs, regno)) 1002 return regno; 1003 } 1004give_up: 1005 return -1; 1006} 1007 1008/* Calculate the set of basic blocks that contain the live range of 1009 the def/use web DEF. 1010 Also calculate the set of target registers that are live at time 1011 in this live range, but ignore the live range represented by DEF 1012 when calculating this set. */ 1013static void 1014btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range) 1015{ 1016 if (!def->live_range) 1017 { 1018 btr_user user; 1019 1020 def->live_range = BITMAP_ALLOC (NULL); 1021 1022 bitmap_set_bit (def->live_range, def->bb->index); 1023 COPY_HARD_REG_SET (*btrs_live_in_range, 1024 (flag_btr_bb_exclusive 1025 ? btrs_live : btrs_live_at_end)[def->bb->index]); 1026 1027 for (user = def->uses; user != NULL; user = user->next) 1028 augment_live_range (def->live_range, btrs_live_in_range, 1029 def->bb, user->bb, 1030 (flag_btr_bb_exclusive 1031 || user->insn != BB_END (def->bb) 1032 || !JUMP_P (user->insn))); 1033 } 1034 else 1035 { 1036 /* def->live_range is accurate, but we need to recompute 1037 the set of target registers live over it, because migration 1038 of other PT instructions may have affected it. 1039 */ 1040 unsigned bb; 1041 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index; 1042 bitmap_iterator bi; 1043 1044 CLEAR_HARD_REG_SET (*btrs_live_in_range); 1045 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) 1046 { 1047 IOR_HARD_REG_SET (*btrs_live_in_range, 1048 (def_bb == bb 1049 ? btrs_live_at_end : btrs_live) [bb]); 1050 } 1051 } 1052 if (!def->other_btr_uses_before_def && 1053 !def->other_btr_uses_after_use) 1054 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr); 1055} 1056 1057/* Merge into the def/use web DEF any other def/use webs in the same 1058 group that are dominated by DEF, provided that there is a target 1059 register available to allocate to the merged web. */ 1060static void 1061combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) 1062{ 1063 btr_def other_def; 1064 1065 for (other_def = def->group->members; 1066 other_def != NULL; 1067 other_def = other_def->next_this_group) 1068 { 1069 if (other_def != def 1070 && other_def->uses != NULL 1071 && ! other_def->has_ambiguous_use 1072 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb)) 1073 { 1074 /* def->bb dominates the other def, so def and other_def could 1075 be combined. */ 1076 /* Merge their live ranges, and get the set of 1077 target registers live over the merged range. */ 1078 int btr; 1079 HARD_REG_SET combined_btrs_live; 1080 bitmap combined_live_range = BITMAP_ALLOC (NULL); 1081 btr_user user; 1082 1083 if (other_def->live_range == NULL) 1084 { 1085 HARD_REG_SET dummy_btrs_live_in_range; 1086 btr_def_live_range (other_def, &dummy_btrs_live_in_range); 1087 } 1088 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range); 1089 bitmap_copy (combined_live_range, def->live_range); 1090 1091 for (user = other_def->uses; user != NULL; user = user->next) 1092 augment_live_range (combined_live_range, &combined_btrs_live, 1093 def->bb, user->bb, 1094 (flag_btr_bb_exclusive 1095 || user->insn != BB_END (def->bb) 1096 || !JUMP_P (user->insn))); 1097 1098 btr = choose_btr (combined_btrs_live); 1099 if (btr != -1) 1100 { 1101 /* We can combine them. */ 1102 if (dump_file) 1103 fprintf (dump_file, 1104 "Combining def in insn %d with def in insn %d\n", 1105 INSN_UID (other_def->insn), INSN_UID (def->insn)); 1106 1107 def->btr = btr; 1108 user = other_def->uses; 1109 while (user != NULL) 1110 { 1111 btr_user next = user->next; 1112 1113 user->next = def->uses; 1114 def->uses = user; 1115 user = next; 1116 } 1117 /* Combining def/use webs can make target registers live 1118 after uses where they previously were not. This means 1119 some REG_DEAD notes may no longer be correct. We could 1120 be more precise about this if we looked at the combined 1121 live range, but here I just delete any REG_DEAD notes 1122 in case they are no longer correct. */ 1123 for (user = def->uses; user != NULL; user = user->next) 1124 remove_note (user->insn, 1125 find_regno_note (user->insn, REG_DEAD, 1126 REGNO (user->use))); 1127 clear_btr_from_live_range (other_def); 1128 other_def->uses = NULL; 1129 bitmap_copy (def->live_range, combined_live_range); 1130 if (other_def->btr == btr && other_def->other_btr_uses_after_use) 1131 def->other_btr_uses_after_use = 1; 1132 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live); 1133 1134 /* Delete the old target register initialization. */ 1135 delete_insn (other_def->insn); 1136 1137 } 1138 BITMAP_FREE (combined_live_range); 1139 } 1140 } 1141} 1142 1143/* Move the definition DEF from its current position to basic 1144 block NEW_DEF_BB, and modify it to use branch target register BTR. 1145 Delete the old defining insn, and insert a new one in NEW_DEF_BB. 1146 Update all reaching uses of DEF in the RTL to use BTR. 1147 If this new position means that other defs in the 1148 same group can be combined with DEF then combine them. */ 1149static void 1150move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, 1151 HARD_REG_SET *btrs_live_in_range) 1152{ 1153 /* We can move the instruction. 1154 Set a target register in block NEW_DEF_BB to the value 1155 needed for this target register definition. 1156 Replace all uses of the old target register definition by 1157 uses of the new definition. Delete the old definition. */ 1158 basic_block b = new_def_bb; 1159 rtx insp = BB_HEAD (b); 1160 rtx old_insn = def->insn; 1161 rtx src; 1162 rtx btr_rtx; 1163 rtx new_insn; 1164 enum machine_mode btr_mode; 1165 btr_user user; 1166 rtx set; 1167 1168 if (dump_file) 1169 fprintf(dump_file, "migrating to basic block %d, using reg %d\n", 1170 new_def_bb->index, btr); 1171 1172 clear_btr_from_live_range (def); 1173 def->btr = btr; 1174 def->bb = new_def_bb; 1175 def->luid = 0; 1176 def->cost = basic_block_freq (new_def_bb); 1177 bitmap_copy (def->live_range, live_range); 1178 combine_btr_defs (def, btrs_live_in_range); 1179 btr = def->btr; 1180 def->other_btr_uses_before_def 1181 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0; 1182 add_btr_to_live_range (def, 1); 1183 if (LABEL_P (insp)) 1184 insp = NEXT_INSN (insp); 1185 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some 1186 optimizations can result in insp being both first and last insn of 1187 its basic block. */ 1188 /* ?? some assertions to check that insp is sensible? */ 1189 1190 if (def->other_btr_uses_before_def) 1191 { 1192 insp = BB_END (b); 1193 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp)) 1194 gcc_assert (insp != BB_HEAD (b)); 1195 1196 if (JUMP_P (insp) || can_throw_internal (insp)) 1197 insp = PREV_INSN (insp); 1198 } 1199 1200 set = single_set (old_insn); 1201 src = SET_SRC (set); 1202 btr_mode = GET_MODE (SET_DEST (set)); 1203 btr_rtx = gen_rtx_REG (btr_mode, btr); 1204 1205 new_insn = gen_move_insn (btr_rtx, src); 1206 1207 /* Insert target register initialization at head of basic block. */ 1208 def->insn = emit_insn_after (new_insn, insp); 1209 1210 regs_ever_live[btr] = 1; 1211 1212 if (dump_file) 1213 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n", 1214 INSN_UID (def->insn), INSN_UID (insp)); 1215 1216 /* Delete the old target register initialization. */ 1217 delete_insn (old_insn); 1218 1219 /* Replace each use of the old target register by a use of the new target 1220 register. */ 1221 for (user = def->uses; user != NULL; user = user->next) 1222 { 1223 /* Some extra work here to ensure consistent modes, because 1224 it seems that a target register REG rtx can be given a different 1225 mode depending on the context (surely that should not be 1226 the case?). */ 1227 rtx replacement_rtx; 1228 if (GET_MODE (user->use) == GET_MODE (btr_rtx) 1229 || GET_MODE (user->use) == VOIDmode) 1230 replacement_rtx = btr_rtx; 1231 else 1232 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr); 1233 replace_rtx (user->insn, user->use, replacement_rtx); 1234 user->use = replacement_rtx; 1235 } 1236} 1237 1238/* We anticipate intra-block scheduling to be done. See if INSN could move 1239 up within BB by N_INSNS. */ 1240static int 1241can_move_up (basic_block bb, rtx insn, int n_insns) 1242{ 1243 while (insn != BB_HEAD (bb) && n_insns > 0) 1244 { 1245 insn = PREV_INSN (insn); 1246 /* ??? What if we have an anti-dependency that actually prevents the 1247 scheduler from doing the move? We'd like to re-allocate the register, 1248 but not necessarily put the load into another basic block. */ 1249 if (INSN_P (insn)) 1250 n_insns--; 1251 } 1252 return n_insns <= 0; 1253} 1254 1255/* Attempt to migrate the target register definition DEF to an 1256 earlier point in the flowgraph. 1257 1258 It is a precondition of this function that DEF is migratable: 1259 i.e. it has a constant source, and all uses are unambiguous. 1260 1261 Only migrations that reduce the cost of DEF will be made. 1262 MIN_COST is the lower bound on the cost of the DEF after migration. 1263 If we migrate DEF so that its cost falls below MIN_COST, 1264 then we do not attempt to migrate further. The idea is that 1265 we migrate definitions in a priority order based on their cost, 1266 when the cost of this definition falls below MIN_COST, then 1267 there is another definition with cost == MIN_COST which now 1268 has a higher priority than this definition. 1269 1270 Return nonzero if there may be benefit from attempting to 1271 migrate this DEF further (i.e. we have reduced the cost below 1272 MIN_COST, but we may be able to reduce it further). 1273 Return zero if no further migration is possible. */ 1274static int 1275migrate_btr_def (btr_def def, int min_cost) 1276{ 1277 bitmap live_range; 1278 HARD_REG_SET btrs_live_in_range; 1279 int btr_used_near_def = 0; 1280 int def_basic_block_freq; 1281 basic_block try; 1282 int give_up = 0; 1283 int def_moved = 0; 1284 btr_user user; 1285 int def_latency; 1286 1287 if (dump_file) 1288 fprintf (dump_file, 1289 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ", 1290 INSN_UID (def->insn), def->cost, min_cost); 1291 1292 if (!def->group || def->has_ambiguous_use) 1293 /* These defs are not migratable. */ 1294 { 1295 if (dump_file) 1296 fprintf (dump_file, "it's not migratable\n"); 1297 return 0; 1298 } 1299 1300 if (!def->uses) 1301 /* We have combined this def with another in the same group, so 1302 no need to consider it further. 1303 */ 1304 { 1305 if (dump_file) 1306 fprintf (dump_file, "it's already combined with another pt\n"); 1307 return 0; 1308 } 1309 1310 btr_def_live_range (def, &btrs_live_in_range); 1311 live_range = BITMAP_ALLOC (NULL); 1312 bitmap_copy (live_range, def->live_range); 1313 1314#ifdef INSN_SCHEDULING 1315 def_latency = insn_default_latency (def->insn) * issue_rate; 1316#else 1317 def_latency = issue_rate; 1318#endif 1319 1320 for (user = def->uses; user != NULL; user = user->next) 1321 { 1322 if (user->bb == def->bb 1323 && user->luid > def->luid 1324 && (def->luid + def_latency) > user->luid 1325 && ! can_move_up (def->bb, def->insn, 1326 (def->luid + def_latency) - user->luid)) 1327 { 1328 btr_used_near_def = 1; 1329 break; 1330 } 1331 } 1332 1333 def_basic_block_freq = basic_block_freq (def->bb); 1334 1335 for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb); 1336 !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost; 1337 try = get_immediate_dominator (CDI_DOMINATORS, try)) 1338 { 1339 /* Try to move the instruction that sets the target register into 1340 basic block TRY. */ 1341 int try_freq = basic_block_freq (try); 1342 edge_iterator ei; 1343 edge e; 1344 1345 /* If TRY has abnormal edges, skip it. */ 1346 FOR_EACH_EDGE (e, ei, try->succs) 1347 if (e->flags & EDGE_COMPLEX) 1348 break; 1349 if (e) 1350 continue; 1351 1352 if (dump_file) 1353 fprintf (dump_file, "trying block %d ...", try->index); 1354 1355 if (try_freq < def_basic_block_freq 1356 || (try_freq == def_basic_block_freq && btr_used_near_def)) 1357 { 1358 int btr; 1359 augment_live_range (live_range, &btrs_live_in_range, def->bb, try, 1360 flag_btr_bb_exclusive); 1361 if (dump_file) 1362 { 1363 fprintf (dump_file, "Now btrs live in range are: "); 1364 dump_hard_reg_set (btrs_live_in_range); 1365 fprintf (dump_file, "\n"); 1366 } 1367 btr = choose_btr (btrs_live_in_range); 1368 if (btr != -1) 1369 { 1370 move_btr_def (try, btr, def, live_range, &btrs_live_in_range); 1371 bitmap_copy(live_range, def->live_range); 1372 btr_used_near_def = 0; 1373 def_moved = 1; 1374 def_basic_block_freq = basic_block_freq (def->bb); 1375 } 1376 else 1377 { 1378 /* There are no free target registers available to move 1379 this far forward, so give up */ 1380 give_up = 1; 1381 if (dump_file) 1382 fprintf (dump_file, 1383 "giving up because there are no free target registers\n"); 1384 } 1385 1386 } 1387 } 1388 if (!def_moved) 1389 { 1390 give_up = 1; 1391 if (dump_file) 1392 fprintf (dump_file, "failed to move\n"); 1393 } 1394 BITMAP_FREE (live_range); 1395 return !give_up; 1396} 1397 1398/* Attempt to move instructions that set target registers earlier 1399 in the flowgraph, away from their corresponding uses. */ 1400static void 1401migrate_btr_defs (enum reg_class btr_class, int allow_callee_save) 1402{ 1403 fibheap_t all_btr_defs = fibheap_new (); 1404 int reg; 1405 1406 gcc_obstack_init (&migrate_btrl_obstack); 1407 if (dump_file) 1408 { 1409 int i; 1410 1411 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++) 1412 { 1413 basic_block bb = BASIC_BLOCK (i); 1414 fprintf(dump_file, 1415 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC 1416 " loop-depth = %d idom = %d\n", 1417 i, (HOST_WIDEST_INT) bb->count, bb->loop_depth, 1418 get_immediate_dominator (CDI_DOMINATORS, bb)->index); 1419 } 1420 } 1421 1422 CLEAR_HARD_REG_SET (all_btrs); 1423 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) 1424 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg) 1425 && (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg])) 1426 { 1427 SET_HARD_REG_BIT (all_btrs, reg); 1428 last_btr = reg; 1429 if (first_btr < 0) 1430 first_btr = reg; 1431 } 1432 1433 btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); 1434 btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); 1435 1436 build_btr_def_use_webs (all_btr_defs); 1437 1438 while (!fibheap_empty (all_btr_defs)) 1439 { 1440 btr_def def = fibheap_extract_min (all_btr_defs); 1441 int min_cost = -fibheap_min_key (all_btr_defs); 1442 if (migrate_btr_def (def, min_cost)) 1443 { 1444 fibheap_insert (all_btr_defs, -def->cost, (void *) def); 1445 if (dump_file) 1446 { 1447 fprintf (dump_file, 1448 "Putting insn %d back on queue with priority %d\n", 1449 INSN_UID (def->insn), def->cost); 1450 } 1451 } 1452 else 1453 BITMAP_FREE (def->live_range); 1454 } 1455 1456 free (btrs_live); 1457 free (btrs_live_at_end); 1458 obstack_free (&migrate_btrl_obstack, NULL); 1459 fibheap_delete (all_btr_defs); 1460} 1461 1462void 1463branch_target_load_optimize (bool after_prologue_epilogue_gen) 1464{ 1465 enum reg_class class = targetm.branch_target_register_class (); 1466 if (class != NO_REGS) 1467 { 1468 /* Initialize issue_rate. */ 1469 if (targetm.sched.issue_rate) 1470 issue_rate = targetm.sched.issue_rate (); 1471 else 1472 issue_rate = 1; 1473 1474 /* Build the CFG for migrate_btr_defs. */ 1475#if 1 1476 /* This may or may not be needed, depending on where we 1477 run this phase. */ 1478 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0); 1479#endif 1480 1481 life_analysis (0); 1482 1483 /* Dominator info is also needed for migrate_btr_def. */ 1484 calculate_dominance_info (CDI_DOMINATORS); 1485 migrate_btr_defs (class, 1486 (targetm.branch_target_register_callee_saved 1487 (after_prologue_epilogue_gen))); 1488 1489 free_dominance_info (CDI_DOMINATORS); 1490 1491 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 1492 PROP_DEATH_NOTES | PROP_REG_INFO); 1493 } 1494} 1495 1496static bool 1497gate_handle_branch_target_load_optimize (void) 1498{ 1499 return (optimize > 0 && flag_branch_target_load_optimize2); 1500} 1501 1502 1503static unsigned int 1504rest_of_handle_branch_target_load_optimize (void) 1505{ 1506 static int warned = 0; 1507 1508 /* Leave this a warning for now so that it is possible to experiment 1509 with running this pass twice. In 3.6, we should either make this 1510 an error, or use separate dump files. */ 1511 if (flag_branch_target_load_optimize 1512 && flag_branch_target_load_optimize2 1513 && !warned) 1514 { 1515 warning (0, "branch target register load optimization is not intended " 1516 "to be run twice"); 1517 1518 warned = 1; 1519 } 1520 1521 branch_target_load_optimize (epilogue_completed); 1522 return 0; 1523} 1524 1525struct tree_opt_pass pass_branch_target_load_optimize = 1526{ 1527 "btl", /* name */ 1528 gate_handle_branch_target_load_optimize, /* gate */ 1529 rest_of_handle_branch_target_load_optimize, /* execute */ 1530 NULL, /* sub */ 1531 NULL, /* next */ 1532 0, /* static_pass_number */ 1533 0, /* tv_id */ 1534 0, /* properties_required */ 1535 0, /* properties_provided */ 1536 0, /* properties_destroyed */ 1537 0, /* todo_flags_start */ 1538 TODO_dump_func | 1539 TODO_ggc_collect, /* todo_flags_finish */ 1540 'd' /* letter */ 1541}; 1542 1543