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