1/* Register renaming for the GNU compiler. 2 Copyright (C) 2000-2015 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14 License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "rtl-error.h" 25#include "tm_p.h" 26#include "insn-config.h" 27#include "regs.h" 28#include "addresses.h" 29#include "hard-reg-set.h" 30#include "predict.h" 31#include "vec.h" 32#include "hashtab.h" 33#include "hash-set.h" 34#include "machmode.h" 35#include "input.h" 36#include "function.h" 37#include "dominance.h" 38#include "cfg.h" 39#include "cfganal.h" 40#include "basic-block.h" 41#include "reload.h" 42#include "output.h" 43#include "recog.h" 44#include "flags.h" 45#include "obstack.h" 46#include "tree-pass.h" 47#include "df.h" 48#include "target.h" 49#include "emit-rtl.h" 50#include "regrename.h" 51 52/* This file implements the RTL register renaming pass of the compiler. It is 53 a semi-local pass whose goal is to maximize the usage of the register file 54 of the processor by substituting registers for others in the solution given 55 by the register allocator. The algorithm is as follows: 56 57 1. Local def/use chains are built: within each basic block, chains are 58 opened and closed; if a chain isn't closed at the end of the block, 59 it is dropped. We pre-open chains if we have already examined a 60 predecessor block and found chains live at the end which match 61 live registers at the start of the new block. 62 63 2. We try to combine the local chains across basic block boundaries by 64 comparing chains that were open at the start or end of a block to 65 those in successor/predecessor blocks. 66 67 3. For each chain, the set of possible renaming registers is computed. 68 This takes into account the renaming of previously processed chains. 69 Optionally, a preferred class is computed for the renaming register. 70 71 4. The best renaming register is computed for the chain in the above set, 72 using a round-robin allocation. If a preferred class exists, then the 73 round-robin allocation is done within the class first, if possible. 74 The round-robin allocation of renaming registers itself is global. 75 76 5. If a renaming register has been found, it is substituted in the chain. 77 78 Targets can parameterize the pass by specifying a preferred class for the 79 renaming register for a given (super)class of registers to be renamed. */ 80 81#if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS 82#error "Use a different bitmap implementation for untracked_operands." 83#endif 84 85enum scan_actions 86{ 87 terminate_write, 88 terminate_dead, 89 mark_all_read, 90 mark_read, 91 mark_write, 92 /* mark_access is for marking the destination regs in 93 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the 94 note is updated properly. */ 95 mark_access 96}; 97 98static const char * const scan_actions_name[] = 99{ 100 "terminate_write", 101 "terminate_dead", 102 "mark_all_read", 103 "mark_read", 104 "mark_write", 105 "mark_access" 106}; 107 108/* TICK and THIS_TICK are used to record the last time we saw each 109 register. */ 110static int tick[FIRST_PSEUDO_REGISTER]; 111static int this_tick = 0; 112 113static struct obstack rename_obstack; 114 115/* If nonnull, the code calling into the register renamer requested 116 information about insn operands, and we store it here. */ 117vec<insn_rr_info> insn_rr; 118 119static void scan_rtx (rtx_insn *, rtx *, enum reg_class, enum scan_actions, 120 enum op_type); 121static bool build_def_use (basic_block); 122 123/* The id to be given to the next opened chain. */ 124static unsigned current_id; 125 126/* A mapping of unique id numbers to chains. */ 127static vec<du_head_p> id_to_chain; 128 129/* List of currently open chains. */ 130static struct du_head *open_chains; 131 132/* Bitmap of open chains. The bits set always match the list found in 133 open_chains. */ 134static bitmap_head open_chains_set; 135 136/* Record the registers being tracked in open_chains. */ 137static HARD_REG_SET live_in_chains; 138 139/* Record the registers that are live but not tracked. The intersection 140 between this and live_in_chains is empty. */ 141static HARD_REG_SET live_hard_regs; 142 143/* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis 144 is for a caller that requires operand data. Used in 145 record_operand_use. */ 146static operand_rr_info *cur_operand; 147 148/* Return the chain corresponding to id number ID. Take into account that 149 chains may have been merged. */ 150du_head_p 151regrename_chain_from_id (unsigned int id) 152{ 153 du_head_p first_chain = id_to_chain[id]; 154 du_head_p chain = first_chain; 155 while (chain->id != id) 156 { 157 id = chain->id; 158 chain = id_to_chain[id]; 159 } 160 first_chain->id = id; 161 return chain; 162} 163 164/* Dump all def/use chains, starting at id FROM. */ 165 166static void 167dump_def_use_chain (int from) 168{ 169 du_head_p head; 170 int i; 171 FOR_EACH_VEC_ELT_FROM (id_to_chain, i, head, from) 172 { 173 struct du_chain *this_du = head->first; 174 175 fprintf (dump_file, "Register %s (%d):", 176 reg_names[head->regno], head->nregs); 177 while (this_du) 178 { 179 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn), 180 reg_class_names[this_du->cl]); 181 this_du = this_du->next_use; 182 } 183 fprintf (dump_file, "\n"); 184 head = head->next_chain; 185 } 186} 187 188static void 189free_chain_data (void) 190{ 191 int i; 192 du_head_p ptr; 193 for (i = 0; id_to_chain.iterate (i, &ptr); i++) 194 bitmap_clear (&ptr->conflicts); 195 196 id_to_chain.release (); 197} 198 199/* Walk all chains starting with CHAINS and record that they conflict with 200 another chain whose id is ID. */ 201 202static void 203mark_conflict (struct du_head *chains, unsigned id) 204{ 205 while (chains) 206 { 207 bitmap_set_bit (&chains->conflicts, id); 208 chains = chains->next_chain; 209 } 210} 211 212/* Examine cur_operand, and if it is nonnull, record information about the 213 use THIS_DU which is part of the chain HEAD. */ 214 215static void 216record_operand_use (struct du_head *head, struct du_chain *this_du) 217{ 218 if (cur_operand == NULL) 219 return; 220 gcc_assert (cur_operand->n_chains < MAX_REGS_PER_ADDRESS); 221 cur_operand->heads[cur_operand->n_chains] = head; 222 cur_operand->chains[cur_operand->n_chains++] = this_du; 223} 224 225/* Create a new chain for THIS_NREGS registers starting at THIS_REGNO, 226 and record its occurrence in *LOC, which is being written to in INSN. 227 This access requires a register of class CL. */ 228 229static du_head_p 230create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc, 231 rtx_insn *insn, enum reg_class cl) 232{ 233 struct du_head *head = XOBNEW (&rename_obstack, struct du_head); 234 struct du_chain *this_du; 235 int nregs; 236 237 head->next_chain = open_chains; 238 head->regno = this_regno; 239 head->nregs = this_nregs; 240 head->need_caller_save_reg = 0; 241 head->cannot_rename = 0; 242 243 id_to_chain.safe_push (head); 244 head->id = current_id++; 245 246 bitmap_initialize (&head->conflicts, &bitmap_default_obstack); 247 bitmap_copy (&head->conflicts, &open_chains_set); 248 mark_conflict (open_chains, head->id); 249 250 /* Since we're tracking this as a chain now, remove it from the 251 list of conflicting live hard registers and track it in 252 live_in_chains instead. */ 253 nregs = head->nregs; 254 while (nregs-- > 0) 255 { 256 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); 257 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs); 258 } 259 260 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs); 261 bitmap_set_bit (&open_chains_set, head->id); 262 263 open_chains = head; 264 265 if (dump_file) 266 { 267 fprintf (dump_file, "Creating chain %s (%d)", 268 reg_names[head->regno], head->id); 269 if (insn != NULL_RTX) 270 fprintf (dump_file, " at insn %d", INSN_UID (insn)); 271 fprintf (dump_file, "\n"); 272 } 273 274 if (insn == NULL_RTX) 275 { 276 head->first = head->last = NULL; 277 return head; 278 } 279 280 this_du = XOBNEW (&rename_obstack, struct du_chain); 281 head->first = head->last = this_du; 282 283 this_du->next_use = 0; 284 this_du->loc = loc; 285 this_du->insn = insn; 286 this_du->cl = cl; 287 record_operand_use (head, this_du); 288 return head; 289} 290 291/* For a def-use chain HEAD, find which registers overlap its lifetime and 292 set the corresponding bits in *PSET. */ 293 294static void 295merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head) 296{ 297 bitmap_iterator bi; 298 unsigned i; 299 IOR_HARD_REG_SET (*pset, head->hard_conflicts); 300 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi) 301 { 302 du_head_p other = regrename_chain_from_id (i); 303 unsigned j = other->nregs; 304 gcc_assert (other != head); 305 while (j-- > 0) 306 SET_HARD_REG_BIT (*pset, other->regno + j); 307 } 308} 309 310/* Check if NEW_REG can be the candidate register to rename for 311 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard 312 registers. */ 313 314static bool 315check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg, 316 struct du_head *this_head, HARD_REG_SET this_unavailable) 317{ 318 machine_mode mode = GET_MODE (*this_head->first->loc); 319 int nregs = hard_regno_nregs[new_reg][mode]; 320 int i; 321 struct du_chain *tmp; 322 323 for (i = nregs - 1; i >= 0; --i) 324 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) 325 || fixed_regs[new_reg + i] 326 || global_regs[new_reg + i] 327 /* Can't use regs which aren't saved by the prologue. */ 328 || (! df_regs_ever_live_p (new_reg + i) 329 && ! call_used_regs[new_reg + i]) 330#ifdef LEAF_REGISTERS 331 /* We can't use a non-leaf register if we're in a 332 leaf function. */ 333 || (crtl->is_leaf 334 && !LEAF_REGISTERS[new_reg + i]) 335#endif 336#ifdef HARD_REGNO_RENAME_OK 337 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) 338#endif 339 ) 340 return false; 341 342 /* See whether it accepts all modes that occur in 343 definition and uses. */ 344 for (tmp = this_head->first; tmp; tmp = tmp->next_use) 345 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)) 346 && ! DEBUG_INSN_P (tmp->insn)) 347 || (this_head->need_caller_save_reg 348 && ! (HARD_REGNO_CALL_PART_CLOBBERED 349 (reg, GET_MODE (*tmp->loc))) 350 && (HARD_REGNO_CALL_PART_CLOBBERED 351 (new_reg, GET_MODE (*tmp->loc))))) 352 return false; 353 354 return true; 355} 356 357/* For the chain THIS_HEAD, compute and return the best register to 358 rename to. SUPER_CLASS is the superunion of register classes in 359 the chain. UNAVAILABLE is a set of registers that cannot be used. 360 OLD_REG is the register currently used for the chain. BEST_RENAME 361 controls whether the register chosen must be better than the 362 current one or just respect the given constraint. */ 363 364int 365find_rename_reg (du_head_p this_head, enum reg_class super_class, 366 HARD_REG_SET *unavailable, int old_reg, bool best_rename) 367{ 368 bool has_preferred_class; 369 enum reg_class preferred_class; 370 int pass; 371 int best_new_reg = old_reg; 372 373 /* Further narrow the set of registers we can use for renaming. 374 If the chain needs a call-saved register, mark the call-used 375 registers as unavailable. */ 376 if (this_head->need_caller_save_reg) 377 IOR_HARD_REG_SET (*unavailable, call_used_reg_set); 378 379 /* Mark registers that overlap this chain's lifetime as unavailable. */ 380 merge_overlapping_regs (unavailable, this_head); 381 382 /* Compute preferred rename class of super union of all the classes 383 in the chain. */ 384 preferred_class 385 = (enum reg_class) targetm.preferred_rename_class (super_class); 386 387 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass 388 over registers that belong to PREFERRED_CLASS and try to find the 389 best register within the class. If that failed, we iterate in 390 the second pass over registers that don't belong to the class. 391 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in 392 ascending order without any preference. */ 393 has_preferred_class = (preferred_class != NO_REGS); 394 for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++) 395 { 396 int new_reg; 397 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) 398 { 399 if (has_preferred_class 400 && (pass == 0) 401 != TEST_HARD_REG_BIT (reg_class_contents[preferred_class], 402 new_reg)) 403 continue; 404 405 if (!check_new_reg_p (old_reg, new_reg, this_head, *unavailable)) 406 continue; 407 408 if (!best_rename) 409 return new_reg; 410 411 /* In the first pass, we force the renaming of registers that 412 don't belong to PREFERRED_CLASS to registers that do, even 413 though the latters were used not very long ago. */ 414 if ((pass == 0 415 && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class], 416 best_new_reg)) 417 || tick[best_new_reg] > tick[new_reg]) 418 best_new_reg = new_reg; 419 } 420 if (pass == 0 && best_new_reg != old_reg) 421 break; 422 } 423 return best_new_reg; 424} 425 426/* Perform register renaming on the current function. */ 427static void 428rename_chains (void) 429{ 430 HARD_REG_SET unavailable; 431 du_head_p this_head; 432 int i; 433 434 memset (tick, 0, sizeof tick); 435 436 CLEAR_HARD_REG_SET (unavailable); 437 /* Don't clobber traceback for noreturn functions. */ 438 if (frame_pointer_needed) 439 { 440 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM); 441#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 442 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM); 443#endif 444 } 445 446 FOR_EACH_VEC_ELT (id_to_chain, i, this_head) 447 { 448 int best_new_reg; 449 int n_uses; 450 struct du_chain *tmp; 451 HARD_REG_SET this_unavailable; 452 int reg = this_head->regno; 453 enum reg_class super_class = NO_REGS; 454 455 if (this_head->cannot_rename) 456 continue; 457 458 if (fixed_regs[reg] || global_regs[reg] 459#if !HARD_FRAME_POINTER_IS_FRAME_POINTER 460 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) 461#else 462 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) 463#endif 464 ) 465 continue; 466 467 COPY_HARD_REG_SET (this_unavailable, unavailable); 468 469 /* Iterate over elements in the chain in order to: 470 1. Count number of uses, and narrow the set of registers we can 471 use for renaming. 472 2. Compute the superunion of register classes in this chain. */ 473 n_uses = 0; 474 super_class = NO_REGS; 475 for (tmp = this_head->first; tmp; tmp = tmp->next_use) 476 { 477 if (DEBUG_INSN_P (tmp->insn)) 478 continue; 479 n_uses++; 480 IOR_COMPL_HARD_REG_SET (this_unavailable, 481 reg_class_contents[tmp->cl]); 482 super_class 483 = reg_class_superunion[(int) super_class][(int) tmp->cl]; 484 } 485 486 if (n_uses < 2) 487 continue; 488 489 best_new_reg = find_rename_reg (this_head, super_class, 490 &this_unavailable, reg, true); 491 492 if (dump_file) 493 { 494 fprintf (dump_file, "Register %s in insn %d", 495 reg_names[reg], INSN_UID (this_head->first->insn)); 496 if (this_head->need_caller_save_reg) 497 fprintf (dump_file, " crosses a call"); 498 } 499 500 if (best_new_reg == reg) 501 { 502 tick[reg] = ++this_tick; 503 if (dump_file) 504 fprintf (dump_file, "; no available better choice\n"); 505 continue; 506 } 507 508 if (dump_file) 509 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]); 510 511 regrename_do_replace (this_head, best_new_reg); 512 tick[best_new_reg] = ++this_tick; 513 df_set_regs_ever_live (best_new_reg, true); 514 } 515} 516 517/* A structure to record information for each hard register at the start of 518 a basic block. */ 519struct incoming_reg_info { 520 /* Holds the number of registers used in the chain that gave us information 521 about this register. Zero means no information known yet, while a 522 negative value is used for something that is part of, but not the first 523 register in a multi-register value. */ 524 int nregs; 525 /* Set to true if we have accesses that conflict in the number of registers 526 used. */ 527 bool unusable; 528}; 529 530/* A structure recording information about each basic block. It is saved 531 and restored around basic block boundaries. 532 A pointer to such a structure is stored in each basic block's aux field 533 during regrename_analyze, except for blocks we know can't be optimized 534 (such as entry and exit blocks). */ 535struct bb_rename_info 536{ 537 /* The basic block corresponding to this structure. */ 538 basic_block bb; 539 /* Copies of the global information. */ 540 bitmap_head open_chains_set; 541 bitmap_head incoming_open_chains_set; 542 struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER]; 543}; 544 545/* Initialize a rename_info structure P for basic block BB, which starts a new 546 scan. */ 547static void 548init_rename_info (struct bb_rename_info *p, basic_block bb) 549{ 550 int i; 551 df_ref def; 552 HARD_REG_SET start_chains_set; 553 554 p->bb = bb; 555 bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack); 556 bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack); 557 558 open_chains = NULL; 559 bitmap_clear (&open_chains_set); 560 561 CLEAR_HARD_REG_SET (live_in_chains); 562 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb)); 563 FOR_EACH_ARTIFICIAL_DEF (def, bb->index) 564 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) 565 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def)); 566 567 /* Open chains based on information from (at least one) predecessor 568 block. This gives us a chance later on to combine chains across 569 basic block boundaries. Inconsistencies (in access sizes) will 570 be caught normally and dealt with conservatively by disabling the 571 chain for renaming, and there is no risk of losing optimization 572 opportunities by opening chains either: if we did not open the 573 chains, we'd have to track the live register as a hard reg, and 574 we'd be unable to rename it in any case. */ 575 CLEAR_HARD_REG_SET (start_chains_set); 576 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 577 { 578 struct incoming_reg_info *iri = p->incoming + i; 579 if (iri->nregs > 0 && !iri->unusable 580 && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs)) 581 { 582 SET_HARD_REG_BIT (start_chains_set, i); 583 remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs); 584 } 585 } 586 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 587 { 588 struct incoming_reg_info *iri = p->incoming + i; 589 if (TEST_HARD_REG_BIT (start_chains_set, i)) 590 { 591 du_head_p chain; 592 if (dump_file) 593 fprintf (dump_file, "opening incoming chain\n"); 594 chain = create_new_chain (i, iri->nregs, NULL, NULL, NO_REGS); 595 bitmap_set_bit (&p->incoming_open_chains_set, chain->id); 596 } 597 } 598} 599 600/* Record in RI that the block corresponding to it has an incoming 601 live value, described by CHAIN. */ 602static void 603set_incoming_from_chain (struct bb_rename_info *ri, du_head_p chain) 604{ 605 int i; 606 int incoming_nregs = ri->incoming[chain->regno].nregs; 607 int nregs; 608 609 /* If we've recorded the same information before, everything is fine. */ 610 if (incoming_nregs == chain->nregs) 611 { 612 if (dump_file) 613 fprintf (dump_file, "reg %d/%d already recorded\n", 614 chain->regno, chain->nregs); 615 return; 616 } 617 618 /* If we have no information for any of the involved registers, update 619 the incoming array. */ 620 nregs = chain->nregs; 621 while (nregs-- > 0) 622 if (ri->incoming[chain->regno + nregs].nregs != 0 623 || ri->incoming[chain->regno + nregs].unusable) 624 break; 625 if (nregs < 0) 626 { 627 nregs = chain->nregs; 628 ri->incoming[chain->regno].nregs = nregs; 629 while (nregs-- > 1) 630 ri->incoming[chain->regno + nregs].nregs = -nregs; 631 if (dump_file) 632 fprintf (dump_file, "recorded reg %d/%d\n", 633 chain->regno, chain->nregs); 634 return; 635 } 636 637 /* There must be some kind of conflict. Prevent both the old and 638 new ranges from being used. */ 639 if (incoming_nregs < 0) 640 ri->incoming[chain->regno + incoming_nregs].unusable = true; 641 for (i = 0; i < chain->nregs; i++) 642 ri->incoming[chain->regno + i].unusable = true; 643} 644 645/* Merge the two chains C1 and C2 so that all conflict information is 646 recorded and C1, and the id of C2 is changed to that of C1. */ 647static void 648merge_chains (du_head_p c1, du_head_p c2) 649{ 650 if (c1 == c2) 651 return; 652 653 if (c2->first != NULL) 654 { 655 if (c1->first == NULL) 656 c1->first = c2->first; 657 else 658 c1->last->next_use = c2->first; 659 c1->last = c2->last; 660 } 661 662 c2->first = c2->last = NULL; 663 c2->id = c1->id; 664 665 IOR_HARD_REG_SET (c1->hard_conflicts, c2->hard_conflicts); 666 bitmap_ior_into (&c1->conflicts, &c2->conflicts); 667 668 c1->need_caller_save_reg |= c2->need_caller_save_reg; 669 c1->cannot_rename |= c2->cannot_rename; 670} 671 672/* Analyze the current function and build chains for renaming. */ 673 674void 675regrename_analyze (bitmap bb_mask) 676{ 677 struct bb_rename_info *rename_info; 678 int i; 679 basic_block bb; 680 int n_bbs; 681 int *inverse_postorder; 682 683 inverse_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); 684 n_bbs = pre_and_rev_post_order_compute (NULL, inverse_postorder, false); 685 686 /* Gather some information about the blocks in this function. */ 687 rename_info = XCNEWVEC (struct bb_rename_info, n_basic_blocks_for_fn (cfun)); 688 i = 0; 689 FOR_EACH_BB_FN (bb, cfun) 690 { 691 struct bb_rename_info *ri = rename_info + i; 692 ri->bb = bb; 693 if (bb_mask != NULL && !bitmap_bit_p (bb_mask, bb->index)) 694 bb->aux = NULL; 695 else 696 bb->aux = ri; 697 i++; 698 } 699 700 current_id = 0; 701 id_to_chain.create (0); 702 bitmap_initialize (&open_chains_set, &bitmap_default_obstack); 703 704 /* The order in which we visit blocks ensures that whenever 705 possible, we only process a block after at least one of its 706 predecessors, which provides a "seeding" effect to make the logic 707 in set_incoming_from_chain and init_rename_info useful. */ 708 709 for (i = 0; i < n_bbs; i++) 710 { 711 basic_block bb1 = BASIC_BLOCK_FOR_FN (cfun, inverse_postorder[i]); 712 struct bb_rename_info *this_info; 713 bool success; 714 edge e; 715 edge_iterator ei; 716 int old_length = id_to_chain.length (); 717 718 this_info = (struct bb_rename_info *) bb1->aux; 719 if (this_info == NULL) 720 continue; 721 722 if (dump_file) 723 fprintf (dump_file, "\nprocessing block %d:\n", bb1->index); 724 725 init_rename_info (this_info, bb1); 726 727 success = build_def_use (bb1); 728 if (!success) 729 { 730 if (dump_file) 731 fprintf (dump_file, "failed\n"); 732 bb1->aux = NULL; 733 id_to_chain.truncate (old_length); 734 current_id = old_length; 735 bitmap_clear (&this_info->incoming_open_chains_set); 736 open_chains = NULL; 737 if (insn_rr.exists ()) 738 { 739 rtx_insn *insn; 740 FOR_BB_INSNS (bb1, insn) 741 { 742 insn_rr_info *p = &insn_rr[INSN_UID (insn)]; 743 p->op_info = NULL; 744 } 745 } 746 continue; 747 } 748 749 if (dump_file) 750 dump_def_use_chain (old_length); 751 bitmap_copy (&this_info->open_chains_set, &open_chains_set); 752 753 /* Add successor blocks to the worklist if necessary, and record 754 data about our own open chains at the end of this block, which 755 will be used to pre-open chains when processing the successors. */ 756 FOR_EACH_EDGE (e, ei, bb1->succs) 757 { 758 struct bb_rename_info *dest_ri; 759 struct du_head *chain; 760 761 if (dump_file) 762 fprintf (dump_file, "successor block %d\n", e->dest->index); 763 764 if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) 765 continue; 766 dest_ri = (struct bb_rename_info *)e->dest->aux; 767 if (dest_ri == NULL) 768 continue; 769 for (chain = open_chains; chain; chain = chain->next_chain) 770 set_incoming_from_chain (dest_ri, chain); 771 } 772 } 773 774 free (inverse_postorder); 775 776 /* Now, combine the chains data we have gathered across basic block 777 boundaries. 778 779 For every basic block, there may be chains open at the start, or at the 780 end. Rather than exclude them from renaming, we look for open chains 781 with matching registers at the other side of the CFG edge. 782 783 For a given chain using register R, open at the start of block B, we 784 must find an open chain using R on the other side of every edge leading 785 to B, if the register is live across this edge. In the code below, 786 N_PREDS_USED counts the number of edges where the register is live, and 787 N_PREDS_JOINED counts those where we found an appropriate chain for 788 joining. 789 790 We perform the analysis for both incoming and outgoing edges, but we 791 only need to merge once (in the second part, after verifying outgoing 792 edges). */ 793 FOR_EACH_BB_FN (bb, cfun) 794 { 795 struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux; 796 unsigned j; 797 bitmap_iterator bi; 798 799 if (bb_ri == NULL) 800 continue; 801 802 if (dump_file) 803 fprintf (dump_file, "processing bb %d in edges\n", bb->index); 804 805 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi) 806 { 807 edge e; 808 edge_iterator ei; 809 struct du_head *chain = regrename_chain_from_id (j); 810 int n_preds_used = 0, n_preds_joined = 0; 811 812 FOR_EACH_EDGE (e, ei, bb->preds) 813 { 814 struct bb_rename_info *src_ri; 815 unsigned k; 816 bitmap_iterator bi2; 817 HARD_REG_SET live; 818 bool success = false; 819 820 REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src)); 821 if (!range_overlaps_hard_reg_set_p (live, chain->regno, 822 chain->nregs)) 823 continue; 824 n_preds_used++; 825 826 if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) 827 continue; 828 829 src_ri = (struct bb_rename_info *)e->src->aux; 830 if (src_ri == NULL) 831 continue; 832 833 EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set, 834 0, k, bi2) 835 { 836 struct du_head *outgoing_chain = regrename_chain_from_id (k); 837 838 if (outgoing_chain->regno == chain->regno 839 && outgoing_chain->nregs == chain->nregs) 840 { 841 n_preds_joined++; 842 success = true; 843 break; 844 } 845 } 846 if (!success && dump_file) 847 fprintf (dump_file, "failure to match with pred block %d\n", 848 e->src->index); 849 } 850 if (n_preds_joined < n_preds_used) 851 { 852 if (dump_file) 853 fprintf (dump_file, "cannot rename chain %d\n", j); 854 chain->cannot_rename = 1; 855 } 856 } 857 } 858 FOR_EACH_BB_FN (bb, cfun) 859 { 860 struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux; 861 unsigned j; 862 bitmap_iterator bi; 863 864 if (bb_ri == NULL) 865 continue; 866 867 if (dump_file) 868 fprintf (dump_file, "processing bb %d out edges\n", bb->index); 869 870 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi) 871 { 872 edge e; 873 edge_iterator ei; 874 struct du_head *chain = regrename_chain_from_id (j); 875 int n_succs_used = 0, n_succs_joined = 0; 876 877 FOR_EACH_EDGE (e, ei, bb->succs) 878 { 879 bool printed = false; 880 struct bb_rename_info *dest_ri; 881 unsigned k; 882 bitmap_iterator bi2; 883 HARD_REG_SET live; 884 885 REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest)); 886 if (!range_overlaps_hard_reg_set_p (live, chain->regno, 887 chain->nregs)) 888 continue; 889 890 n_succs_used++; 891 892 dest_ri = (struct bb_rename_info *)e->dest->aux; 893 if (dest_ri == NULL) 894 continue; 895 896 EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set, 897 0, k, bi2) 898 { 899 struct du_head *incoming_chain = regrename_chain_from_id (k); 900 901 if (incoming_chain->regno == chain->regno 902 && incoming_chain->nregs == chain->nregs) 903 { 904 if (dump_file) 905 { 906 if (!printed) 907 fprintf (dump_file, 908 "merging blocks for edge %d -> %d\n", 909 e->src->index, e->dest->index); 910 printed = true; 911 fprintf (dump_file, 912 " merging chains %d (->%d) and %d (->%d) [%s]\n", 913 k, incoming_chain->id, j, chain->id, 914 reg_names[incoming_chain->regno]); 915 } 916 917 merge_chains (chain, incoming_chain); 918 n_succs_joined++; 919 break; 920 } 921 } 922 } 923 if (n_succs_joined < n_succs_used) 924 { 925 if (dump_file) 926 fprintf (dump_file, "cannot rename chain %d\n", 927 j); 928 chain->cannot_rename = 1; 929 } 930 } 931 } 932 933 free (rename_info); 934 935 FOR_EACH_BB_FN (bb, cfun) 936 bb->aux = NULL; 937} 938 939void 940regrename_do_replace (struct du_head *head, int reg) 941{ 942 struct du_chain *chain; 943 unsigned int base_regno = head->regno; 944 machine_mode mode; 945 946 for (chain = head->first; chain; chain = chain->next_use) 947 { 948 unsigned int regno = ORIGINAL_REGNO (*chain->loc); 949 struct reg_attrs *attr = REG_ATTRS (*chain->loc); 950 int reg_ptr = REG_POINTER (*chain->loc); 951 952 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno) 953 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC (); 954 else 955 { 956 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); 957 if (regno >= FIRST_PSEUDO_REGISTER) 958 ORIGINAL_REGNO (*chain->loc) = regno; 959 REG_ATTRS (*chain->loc) = attr; 960 REG_POINTER (*chain->loc) = reg_ptr; 961 } 962 963 df_insn_rescan (chain->insn); 964 } 965 966 mode = GET_MODE (*head->first->loc); 967 head->regno = reg; 968 head->nregs = hard_regno_nregs[reg][mode]; 969} 970 971 972/* True if we found a register with a size mismatch, which means that we 973 can't track its lifetime accurately. If so, we abort the current block 974 without renaming. */ 975static bool fail_current_block; 976 977/* Return true if OP is a reg for which all bits are set in PSET, false 978 if all bits are clear. 979 In other cases, set fail_current_block and return false. */ 980 981static bool 982verify_reg_in_set (rtx op, HARD_REG_SET *pset) 983{ 984 unsigned regno, nregs; 985 bool all_live, all_dead; 986 if (!REG_P (op)) 987 return false; 988 989 regno = REGNO (op); 990 nregs = hard_regno_nregs[regno][GET_MODE (op)]; 991 all_live = all_dead = true; 992 while (nregs-- > 0) 993 if (TEST_HARD_REG_BIT (*pset, regno + nregs)) 994 all_dead = false; 995 else 996 all_live = false; 997 if (!all_dead && !all_live) 998 { 999 fail_current_block = true; 1000 return false; 1001 } 1002 return all_live; 1003} 1004 1005/* Return true if OP is a reg that is being tracked already in some form. 1006 May set fail_current_block if it sees an unhandled case of overlap. */ 1007 1008static bool 1009verify_reg_tracked (rtx op) 1010{ 1011 return (verify_reg_in_set (op, &live_hard_regs) 1012 || verify_reg_in_set (op, &live_in_chains)); 1013} 1014 1015/* Called through note_stores. DATA points to a rtx_code, either SET or 1016 CLOBBER, which tells us which kind of rtx to look at. If we have a 1017 match, record the set register in live_hard_regs and in the hard_conflicts 1018 bitmap of open chains. */ 1019 1020static void 1021note_sets_clobbers (rtx x, const_rtx set, void *data) 1022{ 1023 enum rtx_code code = *(enum rtx_code *)data; 1024 struct du_head *chain; 1025 1026 if (GET_CODE (x) == SUBREG) 1027 x = SUBREG_REG (x); 1028 if (!REG_P (x) || GET_CODE (set) != code) 1029 return; 1030 /* There must not be pseudos at this point. */ 1031 gcc_assert (HARD_REGISTER_P (x)); 1032 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x)); 1033 for (chain = open_chains; chain; chain = chain->next_chain) 1034 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x)); 1035} 1036 1037static void 1038scan_rtx_reg (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action, 1039 enum op_type type) 1040{ 1041 struct du_head **p; 1042 rtx x = *loc; 1043 machine_mode mode = GET_MODE (x); 1044 unsigned this_regno = REGNO (x); 1045 int this_nregs = hard_regno_nregs[this_regno][mode]; 1046 1047 if (action == mark_write) 1048 { 1049 if (type == OP_OUT) 1050 create_new_chain (this_regno, this_nregs, loc, insn, cl); 1051 return; 1052 } 1053 1054 if ((type == OP_OUT) != (action == terminate_write || action == mark_access)) 1055 return; 1056 1057 for (p = &open_chains; *p;) 1058 { 1059 struct du_head *head = *p; 1060 struct du_head *next = head->next_chain; 1061 int exact_match = (head->regno == this_regno 1062 && head->nregs == this_nregs); 1063 int superset = (this_regno <= head->regno 1064 && this_regno + this_nregs >= head->regno + head->nregs); 1065 int subset = (this_regno >= head->regno 1066 && this_regno + this_nregs <= head->regno + head->nregs); 1067 1068 if (!bitmap_bit_p (&open_chains_set, head->id) 1069 || head->regno + head->nregs <= this_regno 1070 || this_regno + this_nregs <= head->regno) 1071 { 1072 p = &head->next_chain; 1073 continue; 1074 } 1075 1076 if (action == mark_read || action == mark_access) 1077 { 1078 /* ??? Class NO_REGS can happen if the md file makes use of 1079 EXTRA_CONSTRAINTS to match registers. Which is arguably 1080 wrong, but there we are. */ 1081 1082 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn))) 1083 { 1084 if (dump_file) 1085 fprintf (dump_file, 1086 "Cannot rename chain %s (%d) at insn %d (%s)\n", 1087 reg_names[head->regno], head->id, INSN_UID (insn), 1088 scan_actions_name[(int) action]); 1089 head->cannot_rename = 1; 1090 if (superset) 1091 { 1092 unsigned nregs = this_nregs; 1093 head->regno = this_regno; 1094 head->nregs = this_nregs; 1095 while (nregs-- > 0) 1096 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); 1097 if (dump_file) 1098 fprintf (dump_file, 1099 "Widening register in chain %s (%d) at insn %d\n", 1100 reg_names[head->regno], head->id, INSN_UID (insn)); 1101 } 1102 else if (!subset) 1103 { 1104 fail_current_block = true; 1105 if (dump_file) 1106 fprintf (dump_file, 1107 "Failing basic block due to unhandled overlap\n"); 1108 } 1109 } 1110 else 1111 { 1112 struct du_chain *this_du; 1113 this_du = XOBNEW (&rename_obstack, struct du_chain); 1114 this_du->next_use = 0; 1115 this_du->loc = loc; 1116 this_du->insn = insn; 1117 this_du->cl = cl; 1118 if (head->first == NULL) 1119 head->first = this_du; 1120 else 1121 head->last->next_use = this_du; 1122 record_operand_use (head, this_du); 1123 head->last = this_du; 1124 } 1125 /* Avoid adding the same location in a DEBUG_INSN multiple times, 1126 which could happen with non-exact overlap. */ 1127 if (DEBUG_INSN_P (insn)) 1128 return; 1129 /* Otherwise, find any other chains that do not match exactly; 1130 ensure they all get marked unrenamable. */ 1131 p = &head->next_chain; 1132 continue; 1133 } 1134 1135 /* Whether the terminated chain can be used for renaming 1136 depends on the action and this being an exact match. 1137 In either case, we remove this element from open_chains. */ 1138 1139 if ((action == terminate_dead || action == terminate_write) 1140 && (superset || subset)) 1141 { 1142 unsigned nregs; 1143 1144 if (subset && !superset) 1145 head->cannot_rename = 1; 1146 bitmap_clear_bit (&open_chains_set, head->id); 1147 1148 nregs = head->nregs; 1149 while (nregs-- > 0) 1150 { 1151 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs); 1152 if (subset && !superset 1153 && (head->regno + nregs < this_regno 1154 || head->regno + nregs >= this_regno + this_nregs)) 1155 SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs); 1156 } 1157 1158 *p = next; 1159 if (dump_file) 1160 fprintf (dump_file, 1161 "Closing chain %s (%d) at insn %d (%s%s)\n", 1162 reg_names[head->regno], head->id, INSN_UID (insn), 1163 scan_actions_name[(int) action], 1164 superset ? ", superset" : subset ? ", subset" : ""); 1165 } 1166 else if (action == terminate_dead || action == terminate_write) 1167 { 1168 /* In this case, tracking liveness gets too hard. Fail the 1169 entire basic block. */ 1170 if (dump_file) 1171 fprintf (dump_file, 1172 "Failing basic block due to unhandled overlap\n"); 1173 fail_current_block = true; 1174 return; 1175 } 1176 else 1177 { 1178 head->cannot_rename = 1; 1179 if (dump_file) 1180 fprintf (dump_file, 1181 "Cannot rename chain %s (%d) at insn %d (%s)\n", 1182 reg_names[head->regno], head->id, INSN_UID (insn), 1183 scan_actions_name[(int) action]); 1184 p = &head->next_chain; 1185 } 1186 } 1187} 1188 1189/* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or 1190 BASE_REG_CLASS depending on how the register is being considered. */ 1191 1192static void 1193scan_rtx_address (rtx_insn *insn, rtx *loc, enum reg_class cl, 1194 enum scan_actions action, machine_mode mode, 1195 addr_space_t as) 1196{ 1197 rtx x = *loc; 1198 RTX_CODE code = GET_CODE (x); 1199 const char *fmt; 1200 int i, j; 1201 1202 if (action == mark_write || action == mark_access) 1203 return; 1204 1205 switch (code) 1206 { 1207 case PLUS: 1208 { 1209 rtx orig_op0 = XEXP (x, 0); 1210 rtx orig_op1 = XEXP (x, 1); 1211 RTX_CODE code0 = GET_CODE (orig_op0); 1212 RTX_CODE code1 = GET_CODE (orig_op1); 1213 rtx op0 = orig_op0; 1214 rtx op1 = orig_op1; 1215 rtx *locI = NULL; 1216 rtx *locB = NULL; 1217 enum rtx_code index_code = SCRATCH; 1218 1219 if (GET_CODE (op0) == SUBREG) 1220 { 1221 op0 = SUBREG_REG (op0); 1222 code0 = GET_CODE (op0); 1223 } 1224 1225 if (GET_CODE (op1) == SUBREG) 1226 { 1227 op1 = SUBREG_REG (op1); 1228 code1 = GET_CODE (op1); 1229 } 1230 1231 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 1232 || code0 == ZERO_EXTEND || code1 == MEM) 1233 { 1234 locI = &XEXP (x, 0); 1235 locB = &XEXP (x, 1); 1236 index_code = GET_CODE (*locI); 1237 } 1238 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 1239 || code1 == ZERO_EXTEND || code0 == MEM) 1240 { 1241 locI = &XEXP (x, 1); 1242 locB = &XEXP (x, 0); 1243 index_code = GET_CODE (*locI); 1244 } 1245 else if (code0 == CONST_INT || code0 == CONST 1246 || code0 == SYMBOL_REF || code0 == LABEL_REF) 1247 { 1248 locB = &XEXP (x, 1); 1249 index_code = GET_CODE (XEXP (x, 0)); 1250 } 1251 else if (code1 == CONST_INT || code1 == CONST 1252 || code1 == SYMBOL_REF || code1 == LABEL_REF) 1253 { 1254 locB = &XEXP (x, 0); 1255 index_code = GET_CODE (XEXP (x, 1)); 1256 } 1257 else if (code0 == REG && code1 == REG) 1258 { 1259 int index_op; 1260 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1); 1261 1262 if (REGNO_OK_FOR_INDEX_P (regno1) 1263 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG)) 1264 index_op = 1; 1265 else if (REGNO_OK_FOR_INDEX_P (regno0) 1266 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) 1267 index_op = 0; 1268 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG) 1269 || REGNO_OK_FOR_INDEX_P (regno1)) 1270 index_op = 1; 1271 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) 1272 index_op = 0; 1273 else 1274 index_op = 1; 1275 1276 locI = &XEXP (x, index_op); 1277 locB = &XEXP (x, !index_op); 1278 index_code = GET_CODE (*locI); 1279 } 1280 else if (code0 == REG) 1281 { 1282 locI = &XEXP (x, 0); 1283 locB = &XEXP (x, 1); 1284 index_code = GET_CODE (*locI); 1285 } 1286 else if (code1 == REG) 1287 { 1288 locI = &XEXP (x, 1); 1289 locB = &XEXP (x, 0); 1290 index_code = GET_CODE (*locI); 1291 } 1292 1293 if (locI) 1294 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode, as); 1295 if (locB) 1296 scan_rtx_address (insn, locB, 1297 base_reg_class (mode, as, PLUS, index_code), 1298 action, mode, as); 1299 1300 return; 1301 } 1302 1303 case POST_INC: 1304 case POST_DEC: 1305 case POST_MODIFY: 1306 case PRE_INC: 1307 case PRE_DEC: 1308 case PRE_MODIFY: 1309#ifndef AUTO_INC_DEC 1310 /* If the target doesn't claim to handle autoinc, this must be 1311 something special, like a stack push. Kill this chain. */ 1312 action = mark_all_read; 1313#endif 1314 break; 1315 1316 case MEM: 1317 scan_rtx_address (insn, &XEXP (x, 0), 1318 base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), 1319 MEM, SCRATCH), 1320 action, GET_MODE (x), MEM_ADDR_SPACE (x)); 1321 return; 1322 1323 case REG: 1324 scan_rtx_reg (insn, loc, cl, action, OP_IN); 1325 return; 1326 1327 default: 1328 break; 1329 } 1330 1331 fmt = GET_RTX_FORMAT (code); 1332 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1333 { 1334 if (fmt[i] == 'e') 1335 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode, as); 1336 else if (fmt[i] == 'E') 1337 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1338 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode, as); 1339 } 1340} 1341 1342static void 1343scan_rtx (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action, 1344 enum op_type type) 1345{ 1346 const char *fmt; 1347 rtx x = *loc; 1348 enum rtx_code code = GET_CODE (x); 1349 int i, j; 1350 1351 code = GET_CODE (x); 1352 switch (code) 1353 { 1354 case CONST: 1355 CASE_CONST_ANY: 1356 case SYMBOL_REF: 1357 case LABEL_REF: 1358 case CC0: 1359 case PC: 1360 return; 1361 1362 case REG: 1363 scan_rtx_reg (insn, loc, cl, action, type); 1364 return; 1365 1366 case MEM: 1367 scan_rtx_address (insn, &XEXP (x, 0), 1368 base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), 1369 MEM, SCRATCH), 1370 action, GET_MODE (x), MEM_ADDR_SPACE (x)); 1371 return; 1372 1373 case SET: 1374 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN); 1375 scan_rtx (insn, &SET_DEST (x), cl, action, 1376 (GET_CODE (PATTERN (insn)) == COND_EXEC 1377 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT); 1378 return; 1379 1380 case STRICT_LOW_PART: 1381 scan_rtx (insn, &XEXP (x, 0), cl, action, 1382 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT); 1383 return; 1384 1385 case ZERO_EXTRACT: 1386 case SIGN_EXTRACT: 1387 scan_rtx (insn, &XEXP (x, 0), cl, action, 1388 (type == OP_IN ? OP_IN : 1389 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT)); 1390 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN); 1391 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN); 1392 return; 1393 1394 case POST_INC: 1395 case PRE_INC: 1396 case POST_DEC: 1397 case PRE_DEC: 1398 case POST_MODIFY: 1399 case PRE_MODIFY: 1400 /* Should only happen inside MEM. */ 1401 gcc_unreachable (); 1402 1403 case CLOBBER: 1404 scan_rtx (insn, &SET_DEST (x), cl, action, 1405 (GET_CODE (PATTERN (insn)) == COND_EXEC 1406 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT); 1407 return; 1408 1409 case EXPR_LIST: 1410 scan_rtx (insn, &XEXP (x, 0), cl, action, type); 1411 if (XEXP (x, 1)) 1412 scan_rtx (insn, &XEXP (x, 1), cl, action, type); 1413 return; 1414 1415 default: 1416 break; 1417 } 1418 1419 fmt = GET_RTX_FORMAT (code); 1420 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1421 { 1422 if (fmt[i] == 'e') 1423 scan_rtx (insn, &XEXP (x, i), cl, action, type); 1424 else if (fmt[i] == 'E') 1425 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1426 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type); 1427 } 1428} 1429 1430/* Hide operands of the current insn (of which there are N_OPS) by 1431 substituting cc0 for them. 1432 Previous values are stored in the OLD_OPERANDS and OLD_DUPS. 1433 For every bit set in DO_NOT_HIDE, we leave the operand alone. 1434 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands 1435 and earlyclobbers. */ 1436 1437static void 1438hide_operands (int n_ops, rtx *old_operands, rtx *old_dups, 1439 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only) 1440{ 1441 int i; 1442 const operand_alternative *op_alt = which_op_alt (); 1443 for (i = 0; i < n_ops; i++) 1444 { 1445 old_operands[i] = recog_data.operand[i]; 1446 /* Don't squash match_operator or match_parallel here, since 1447 we don't know that all of the contained registers are 1448 reachable by proper operands. */ 1449 if (recog_data.constraints[i][0] == '\0') 1450 continue; 1451 if (do_not_hide & (1 << i)) 1452 continue; 1453 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT 1454 || op_alt[i].earlyclobber) 1455 *recog_data.operand_loc[i] = cc0_rtx; 1456 } 1457 for (i = 0; i < recog_data.n_dups; i++) 1458 { 1459 int opn = recog_data.dup_num[i]; 1460 old_dups[i] = *recog_data.dup_loc[i]; 1461 if (do_not_hide & (1 << opn)) 1462 continue; 1463 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT 1464 || op_alt[opn].earlyclobber) 1465 *recog_data.dup_loc[i] = cc0_rtx; 1466 } 1467} 1468 1469/* Undo the substitution performed by hide_operands. INSN is the insn we 1470 are processing; the arguments are the same as in hide_operands. */ 1471 1472static void 1473restore_operands (rtx_insn *insn, int n_ops, rtx *old_operands, rtx *old_dups) 1474{ 1475 int i; 1476 for (i = 0; i < recog_data.n_dups; i++) 1477 *recog_data.dup_loc[i] = old_dups[i]; 1478 for (i = 0; i < n_ops; i++) 1479 *recog_data.operand_loc[i] = old_operands[i]; 1480 if (recog_data.n_dups) 1481 df_insn_rescan (insn); 1482} 1483 1484/* For each output operand of INSN, call scan_rtx to create a new 1485 open chain. Do this only for normal or earlyclobber outputs, 1486 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to 1487 record information about the operands in the insn. */ 1488 1489static void 1490record_out_operands (rtx_insn *insn, bool earlyclobber, insn_rr_info *insn_info) 1491{ 1492 int n_ops = recog_data.n_operands; 1493 const operand_alternative *op_alt = which_op_alt (); 1494 1495 int i; 1496 1497 for (i = 0; i < n_ops + recog_data.n_dups; i++) 1498 { 1499 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 1500 rtx *loc = (i < n_ops 1501 ? recog_data.operand_loc[opn] 1502 : recog_data.dup_loc[i - n_ops]); 1503 rtx op = *loc; 1504 enum reg_class cl = alternative_class (op_alt, opn); 1505 1506 struct du_head *prev_open; 1507 1508 if (recog_data.operand_type[opn] != OP_OUT 1509 || op_alt[opn].earlyclobber != earlyclobber) 1510 continue; 1511 1512 if (insn_info) 1513 cur_operand = insn_info->op_info + i; 1514 1515 prev_open = open_chains; 1516 scan_rtx (insn, loc, cl, mark_write, OP_OUT); 1517 1518 /* ??? Many targets have output constraints on the SET_DEST 1519 of a call insn, which is stupid, since these are certainly 1520 ABI defined hard registers. For these, and for asm operands 1521 that originally referenced hard registers, we must record that 1522 the chain cannot be renamed. */ 1523 if (CALL_P (insn) 1524 || (asm_noperands (PATTERN (insn)) > 0 1525 && REG_P (op) 1526 && REGNO (op) == ORIGINAL_REGNO (op))) 1527 { 1528 if (prev_open != open_chains) 1529 open_chains->cannot_rename = 1; 1530 } 1531 } 1532 cur_operand = NULL; 1533} 1534 1535/* Build def/use chain. */ 1536 1537static bool 1538build_def_use (basic_block bb) 1539{ 1540 rtx_insn *insn; 1541 unsigned HOST_WIDE_INT untracked_operands; 1542 1543 fail_current_block = false; 1544 1545 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 1546 { 1547 if (NONDEBUG_INSN_P (insn)) 1548 { 1549 int n_ops; 1550 rtx note; 1551 rtx old_operands[MAX_RECOG_OPERANDS]; 1552 rtx old_dups[MAX_DUP_OPERANDS]; 1553 int i; 1554 int predicated; 1555 enum rtx_code set_code = SET; 1556 enum rtx_code clobber_code = CLOBBER; 1557 insn_rr_info *insn_info = NULL; 1558 1559 /* Process the insn, determining its effect on the def-use 1560 chains and live hard registers. We perform the following 1561 steps with the register references in the insn, simulating 1562 its effect: 1563 (1) Deal with earlyclobber operands and CLOBBERs of non-operands 1564 by creating chains and marking hard regs live. 1565 (2) Any read outside an operand causes any chain it overlaps 1566 with to be marked unrenamable. 1567 (3) Any read inside an operand is added if there's already 1568 an open chain for it. 1569 (4) For any REG_DEAD note we find, close open chains that 1570 overlap it. 1571 (5) For any non-earlyclobber write we find, close open chains 1572 that overlap it. 1573 (6) For any non-earlyclobber write we find in an operand, make 1574 a new chain or mark the hard register as live. 1575 (7) For any REG_UNUSED, close any chains we just opened. 1576 1577 We cannot deal with situations where we track a reg in one mode 1578 and see a reference in another mode; these will cause the chain 1579 to be marked unrenamable or even cause us to abort the entire 1580 basic block. */ 1581 1582 extract_constrain_insn (insn); 1583 preprocess_constraints (insn); 1584 const operand_alternative *op_alt = which_op_alt (); 1585 n_ops = recog_data.n_operands; 1586 untracked_operands = 0; 1587 1588 if (insn_rr.exists ()) 1589 { 1590 insn_info = &insn_rr[INSN_UID (insn)]; 1591 insn_info->op_info = XOBNEWVEC (&rename_obstack, operand_rr_info, 1592 recog_data.n_operands); 1593 memset (insn_info->op_info, 0, 1594 sizeof (operand_rr_info) * recog_data.n_operands); 1595 } 1596 1597 /* Simplify the code below by promoting OP_OUT to OP_INOUT in 1598 predicated instructions, but only for register operands 1599 that are already tracked, so that we can create a chain 1600 when the first SET makes a register live. */ 1601 1602 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 1603 for (i = 0; i < n_ops; ++i) 1604 { 1605 rtx op = recog_data.operand[i]; 1606 int matches = op_alt[i].matches; 1607 if (matches >= 0 || op_alt[i].matched >= 0 1608 || (predicated && recog_data.operand_type[i] == OP_OUT)) 1609 { 1610 recog_data.operand_type[i] = OP_INOUT; 1611 /* A special case to deal with instruction patterns that 1612 have matching operands with different modes. If we're 1613 not already tracking such a reg, we won't start here, 1614 and we must instead make sure to make the operand visible 1615 to the machinery that tracks hard registers. */ 1616 if (matches >= 0 1617 && (GET_MODE_SIZE (recog_data.operand_mode[i]) 1618 != GET_MODE_SIZE (recog_data.operand_mode[matches])) 1619 && !verify_reg_in_set (op, &live_in_chains)) 1620 { 1621 untracked_operands |= 1 << i; 1622 untracked_operands |= 1 << matches; 1623 } 1624 } 1625 /* If there's an in-out operand with a register that is not 1626 being tracked at all yet, open a chain. */ 1627 if (recog_data.operand_type[i] == OP_INOUT 1628 && !(untracked_operands & (1 << i)) 1629 && REG_P (op) 1630 && !verify_reg_tracked (op)) 1631 { 1632 machine_mode mode = GET_MODE (op); 1633 unsigned this_regno = REGNO (op); 1634 unsigned this_nregs = hard_regno_nregs[this_regno][mode]; 1635 create_new_chain (this_regno, this_nregs, NULL, NULL, 1636 NO_REGS); 1637 } 1638 } 1639 1640 if (fail_current_block) 1641 break; 1642 1643 /* Step 1a: Mark hard registers that are clobbered in this insn, 1644 outside an operand, as live. */ 1645 hide_operands (n_ops, old_operands, old_dups, untracked_operands, 1646 false); 1647 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code); 1648 restore_operands (insn, n_ops, old_operands, old_dups); 1649 1650 /* Step 1b: Begin new chains for earlyclobbered writes inside 1651 operands. */ 1652 record_out_operands (insn, true, insn_info); 1653 1654 /* Step 2: Mark chains for which we have reads outside operands 1655 as unrenamable. 1656 We do this by munging all operands into CC0, and closing 1657 everything remaining. */ 1658 1659 hide_operands (n_ops, old_operands, old_dups, untracked_operands, 1660 false); 1661 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN); 1662 restore_operands (insn, n_ops, old_operands, old_dups); 1663 1664 /* Step 2B: Can't rename function call argument registers. */ 1665 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn)) 1666 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), 1667 NO_REGS, mark_all_read, OP_IN); 1668 1669 /* Step 2C: Can't rename asm operands that were originally 1670 hard registers. */ 1671 if (asm_noperands (PATTERN (insn)) > 0) 1672 for (i = 0; i < n_ops; i++) 1673 { 1674 rtx *loc = recog_data.operand_loc[i]; 1675 rtx op = *loc; 1676 1677 if (REG_P (op) 1678 && REGNO (op) == ORIGINAL_REGNO (op) 1679 && (recog_data.operand_type[i] == OP_IN 1680 || recog_data.operand_type[i] == OP_INOUT)) 1681 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN); 1682 } 1683 1684 /* Step 3: Append to chains for reads inside operands. */ 1685 for (i = 0; i < n_ops + recog_data.n_dups; i++) 1686 { 1687 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 1688 rtx *loc = (i < n_ops 1689 ? recog_data.operand_loc[opn] 1690 : recog_data.dup_loc[i - n_ops]); 1691 enum reg_class cl = alternative_class (op_alt, opn); 1692 enum op_type type = recog_data.operand_type[opn]; 1693 1694 /* Don't scan match_operand here, since we've no reg class 1695 information to pass down. Any operands that we could 1696 substitute in will be represented elsewhere. */ 1697 if (recog_data.constraints[opn][0] == '\0' 1698 || untracked_operands & (1 << opn)) 1699 continue; 1700 1701 if (insn_info) 1702 cur_operand = i == opn ? insn_info->op_info + i : NULL; 1703 if (op_alt[opn].is_address) 1704 scan_rtx_address (insn, loc, cl, mark_read, 1705 VOIDmode, ADDR_SPACE_GENERIC); 1706 else 1707 scan_rtx (insn, loc, cl, mark_read, type); 1708 } 1709 cur_operand = NULL; 1710 1711 /* Step 3B: Record updates for regs in REG_INC notes, and 1712 source regs in REG_FRAME_RELATED_EXPR notes. */ 1713 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 1714 if (REG_NOTE_KIND (note) == REG_INC 1715 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) 1716 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, 1717 OP_INOUT); 1718 1719 /* Step 4: Close chains for registers that die here, unless 1720 the register is mentioned in a REG_UNUSED note. In that 1721 case we keep the chain open until step #7 below to ensure 1722 it conflicts with other output operands of this insn. 1723 See PR 52573. Arguably the insn should not have both 1724 notes; it has proven difficult to fix that without 1725 other undesirable side effects. */ 1726 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 1727 if (REG_NOTE_KIND (note) == REG_DEAD 1728 && !find_regno_note (insn, REG_UNUSED, REGNO (XEXP (note, 0)))) 1729 { 1730 remove_from_hard_reg_set (&live_hard_regs, 1731 GET_MODE (XEXP (note, 0)), 1732 REGNO (XEXP (note, 0))); 1733 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 1734 OP_IN); 1735 } 1736 1737 /* Step 4B: If this is a call, any chain live at this point 1738 requires a caller-saved reg. */ 1739 if (CALL_P (insn)) 1740 { 1741 struct du_head *p; 1742 for (p = open_chains; p; p = p->next_chain) 1743 p->need_caller_save_reg = 1; 1744 } 1745 1746 /* Step 5: Close open chains that overlap writes. Similar to 1747 step 2, we hide in-out operands, since we do not want to 1748 close these chains. We also hide earlyclobber operands, 1749 since we've opened chains for them in step 1, and earlier 1750 chains they would overlap with must have been closed at 1751 the previous insn at the latest, as such operands cannot 1752 possibly overlap with any input operands. */ 1753 1754 hide_operands (n_ops, old_operands, old_dups, untracked_operands, 1755 true); 1756 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN); 1757 restore_operands (insn, n_ops, old_operands, old_dups); 1758 1759 /* Step 6a: Mark hard registers that are set in this insn, 1760 outside an operand, as live. */ 1761 hide_operands (n_ops, old_operands, old_dups, untracked_operands, 1762 false); 1763 note_stores (PATTERN (insn), note_sets_clobbers, &set_code); 1764 restore_operands (insn, n_ops, old_operands, old_dups); 1765 1766 /* Step 6b: Begin new chains for writes inside operands. */ 1767 record_out_operands (insn, false, insn_info); 1768 1769 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR 1770 notes for update. */ 1771 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 1772 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) 1773 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access, 1774 OP_INOUT); 1775 1776 /* Step 7: Close chains for registers that were never 1777 really used here. */ 1778 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 1779 if (REG_NOTE_KIND (note) == REG_UNUSED) 1780 { 1781 remove_from_hard_reg_set (&live_hard_regs, 1782 GET_MODE (XEXP (note, 0)), 1783 REGNO (XEXP (note, 0))); 1784 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 1785 OP_IN); 1786 } 1787 } 1788 else if (DEBUG_INSN_P (insn) 1789 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn))) 1790 { 1791 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn), 1792 ALL_REGS, mark_read, OP_IN); 1793 } 1794 if (insn == BB_END (bb)) 1795 break; 1796 } 1797 1798 if (fail_current_block) 1799 return false; 1800 1801 return true; 1802} 1803 1804/* Initialize the register renamer. If INSN_INFO is true, ensure that 1805 insn_rr is nonnull. */ 1806void 1807regrename_init (bool insn_info) 1808{ 1809 gcc_obstack_init (&rename_obstack); 1810 insn_rr.create (0); 1811 if (insn_info) 1812 insn_rr.safe_grow_cleared (get_max_uid ()); 1813} 1814 1815/* Free all global data used by the register renamer. */ 1816void 1817regrename_finish (void) 1818{ 1819 insn_rr.release (); 1820 free_chain_data (); 1821 obstack_free (&rename_obstack, NULL); 1822} 1823 1824/* Perform register renaming on the current function. */ 1825 1826static unsigned int 1827regrename_optimize (void) 1828{ 1829 df_set_flags (DF_LR_RUN_DCE); 1830 df_note_add_problem (); 1831 df_analyze (); 1832 df_set_flags (DF_DEFER_INSN_RESCAN); 1833 1834 regrename_init (false); 1835 1836 regrename_analyze (NULL); 1837 1838 rename_chains (); 1839 1840 regrename_finish (); 1841 1842 return 0; 1843} 1844 1845namespace { 1846 1847const pass_data pass_data_regrename = 1848{ 1849 RTL_PASS, /* type */ 1850 "rnreg", /* name */ 1851 OPTGROUP_NONE, /* optinfo_flags */ 1852 TV_RENAME_REGISTERS, /* tv_id */ 1853 0, /* properties_required */ 1854 0, /* properties_provided */ 1855 0, /* properties_destroyed */ 1856 0, /* todo_flags_start */ 1857 TODO_df_finish, /* todo_flags_finish */ 1858}; 1859 1860class pass_regrename : public rtl_opt_pass 1861{ 1862public: 1863 pass_regrename (gcc::context *ctxt) 1864 : rtl_opt_pass (pass_data_regrename, ctxt) 1865 {} 1866 1867 /* opt_pass methods: */ 1868 virtual bool gate (function *) 1869 { 1870 return (optimize > 0 && (flag_rename_registers)); 1871 } 1872 1873 virtual unsigned int execute (function *) { return regrename_optimize (); } 1874 1875}; // class pass_regrename 1876 1877} // anon namespace 1878 1879rtl_opt_pass * 1880make_pass_regrename (gcc::context *ctxt) 1881{ 1882 return new pass_regrename (ctxt); 1883} 1884