gcc/regrename.c

   1 /* Register renaming for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT
  13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  15    License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along 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 "tm_p.h"
  27 #include "insn-config.h"
  28 #include "regs.h"
  29 #include "addresses.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "reload.h"
  33 #include "output.h"
  34 #include "function.h"
  35 #include "recog.h"
  36 #include "flags.h"
  37 #include "toplev.h"
  38 #include "obstack.h"
  39 #include "timevar.h"
  40 #include "tree-pass.h"
  41 #include "df.h"
  42
  43 struct du_chain
  44 {
  45   struct du_chain *next_chain;
  46   struct du_chain *next_use;
  47
  48   rtx insn;
  49   rtx *loc;
  50   ENUM_BITFIELD(reg_class) cl : 16;
  51   unsigned int need_caller_save_reg:1;
  52   unsigned int earlyclobber:1;
  53 };
  54
  55 enum scan_actions
  56 {
  57   terminate_all_read,
  58   terminate_overlapping_read,
  59   terminate_write,
  60   terminate_dead,
  61   mark_read,
  62   mark_write,
  63   /* mark_access is for marking the destination regs in
  64      REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
  65      note is updated properly.  */
  66   mark_access
  67 };
  68
  69 static const char * const scan_actions_name[] =
  70 {
  71   "terminate_all_read",
  72   "terminate_overlapping_read",
  73   "terminate_write",
  74   "terminate_dead",
  75   "mark_read",
  76   "mark_write",
  77   "mark_access"
  78 };
  79
  80 static struct obstack rename_obstack;
  81
  82 static void do_replace (struct du_chain *, int);
  83 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
  84                           enum scan_actions, enum op_type, int);
  85 static void scan_rtx_address (rtx, rtx *, enum reg_class,
  86                               enum scan_actions, enum machine_mode);
  87 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
  88                       enum op_type, int);
  89 static struct du_chain *build_def_use (basic_block);
  90 static void dump_def_use_chain (struct du_chain *);
  91 static void note_sets (rtx, const_rtx, void *);
  92 static void clear_dead_regs (HARD_REG_SET *, enum reg_note, rtx);
  93 static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
  94                                     struct du_chain *);
  95
  96 /* Called through note_stores.  Find sets of registers, and
  97    record them in *DATA (which is actually a HARD_REG_SET *).  */
  98
  99 static void
 100 note_sets (rtx x, const_rtx set ATTRIBUTE_UNUSED, void *data)
 101 {
 102   HARD_REG_SET *pset = (HARD_REG_SET *) data;
 103
 104   if (GET_CODE (x) == SUBREG)
 105     x = SUBREG_REG (x);
 106   if (!REG_P (x))
 107     return;
 108   /* There must not be pseudos at this point.  */
 109   gcc_assert (HARD_REGISTER_P (x));
 110   add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
 111 }
 112
 113 /* Clear all registers from *PSET for which a note of kind KIND can be found
 114    in the list NOTES.  */
 115
 116 static void
 117 clear_dead_regs (HARD_REG_SET *pset, enum reg_note kind, rtx notes)
 118 {
 119   rtx note;
 120   for (note = notes; note; note = XEXP (note, 1))
 121     if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
 122       {
 123         rtx reg = XEXP (note, 0);
 124         /* There must not be pseudos at this point.  */
 125         gcc_assert (HARD_REGISTER_P (reg));
 126         remove_from_hard_reg_set (pset, GET_MODE (reg), REGNO (reg));
 127       }
 128 }
 129
 130 /* For a def-use chain CHAIN in basic block B, find which registers overlap
 131    its lifetime and set the corresponding bits in *PSET.  */
 132
 133 static void
 134 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
 135                         struct du_chain *chain)
 136 {
 137   struct du_chain *t = chain;
 138   rtx insn;
 139   HARD_REG_SET live;
 140   df_ref *def_rec;
 141
 142   REG_SET_TO_HARD_REG_SET (live, df_get_live_in (b));
 143   for (def_rec = df_get_artificial_defs (b->index); *def_rec; def_rec++)
 144     {
 145       df_ref def = *def_rec;
 146       if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
 147         SET_HARD_REG_BIT (live, DF_REF_REGNO (def));
 148     }
 149   insn = BB_HEAD (b);
 150   while (t)
 151     {
 152       /* Search forward until the next reference to the register to be
 153          renamed.  */
 154       while (insn != t->insn)
 155         {
 156           if (INSN_P (insn))
 157             {
 158               clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
 159               note_stores (PATTERN (insn), note_sets, (void *) &live);
 160               /* Only record currently live regs if we are inside the
 161                  reg's live range.  */
 162               if (t != chain)
 163                 IOR_HARD_REG_SET (*pset, live);
 164               clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
 165             }
 166           insn = NEXT_INSN (insn);
 167         }
 168
 169       IOR_HARD_REG_SET (*pset, live);
 170
 171       /* For the last reference, also merge in all registers set in the
 172          same insn.
 173          @@@ We only have take earlyclobbered sets into account.  */
 174       if (! t->next_use)
 175         note_stores (PATTERN (insn), note_sets, (void *) pset);
 176
 177       t = t->next_use;
 178     }
 179 }
 180
 181 /* Perform register renaming on the current function.  */
 182
 183 static unsigned int
 184 regrename_optimize (void)
 185 {
 186   int tick[FIRST_PSEUDO_REGISTER];
 187   int this_tick = 0;
 188   basic_block bb;
 189   char *first_obj;
 190
 191   df_set_flags (DF_LR_RUN_DCE);
 192   df_note_add_problem ();
 193   df_analyze ();
 194   df_set_flags (DF_DEFER_INSN_RESCAN);
 195
 196   memset (tick, 0, sizeof tick);
 197
 198   gcc_obstack_init (&rename_obstack);
 199   first_obj = XOBNEWVAR (&rename_obstack, char, 0);
 200
 201   FOR_EACH_BB (bb)
 202     {
 203       struct du_chain *all_chains = 0;
 204       HARD_REG_SET unavailable;
 205       HARD_REG_SET regs_seen;
 206
 207       CLEAR_HARD_REG_SET (unavailable);
 208
 209       if (dump_file)
 210         fprintf (dump_file, "\nBasic block %d:\n", bb->index);
 211
 212       all_chains = build_def_use (bb);
 213
 214       if (dump_file)
 215         dump_def_use_chain (all_chains);
 216
 217       CLEAR_HARD_REG_SET (unavailable);
 218       /* Don't clobber traceback for noreturn functions.  */
 219       if (frame_pointer_needed)
 220         {
 221           add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
 222 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 223           add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
 224 #endif
 225         }
 226
 227       CLEAR_HARD_REG_SET (regs_seen);
 228       while (all_chains)
 229         {
 230           int new_reg, best_new_reg;
 231           int n_uses;
 232           struct du_chain *this_du = all_chains;
 233           struct du_chain *tmp;
 234           HARD_REG_SET this_unavailable;
 235           int reg = REGNO (*this_du->loc);
 236           int i;
 237
 238           all_chains = this_du->next_chain;
 239
 240           best_new_reg = reg;
 241
 242 #if 0 /* This just disables optimization opportunities.  */
 243           /* Only rename once we've seen the reg more than once.  */
 244           if (! TEST_HARD_REG_BIT (regs_seen, reg))
 245             {
 246               SET_HARD_REG_BIT (regs_seen, reg);
 247               continue;
 248             }
 249 #endif
 250
 251           if (fixed_regs[reg] || global_regs[reg]
 252 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 253               || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
 254 #else
 255               || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
 256 #endif
 257               )
 258             continue;
 259
 260           COPY_HARD_REG_SET (this_unavailable, unavailable);
 261
 262           /* Count number of uses, and narrow the set of registers we can
 263              use for renaming.  */
 264           n_uses = 0;
 265           for (tmp = this_du; tmp; tmp = tmp->next_use)
 266             {
 267               if (DEBUG_INSN_P (tmp->insn))
 268                 continue;
 269               n_uses++;
 270               IOR_COMPL_HARD_REG_SET (this_unavailable,
 271                                       reg_class_contents[tmp->cl]);
 272             }
 273
 274           if (n_uses < 2)
 275             continue;
 276
 277           if (this_du->need_caller_save_reg)
 278             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
 279
 280           merge_overlapping_regs (bb, &this_unavailable, this_du);
 281
 282           /* Now potential_regs is a reasonable approximation, let's
 283              have a closer look at each register still in there.  */
 284           for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
 285             {
 286               int nregs = hard_regno_nregs[new_reg][GET_MODE (*this_du->loc)];
 287
 288               for (i = nregs - 1; i >= 0; --i)
 289                 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
 290                     || fixed_regs[new_reg + i]
 291                     || global_regs[new_reg + i]
 292                     /* Can't use regs which aren't saved by the prologue.  */
 293                     || (! df_regs_ever_live_p (new_reg + i)
 294                         && ! call_used_regs[new_reg + i])
 295 #ifdef LEAF_REGISTERS
 296                     /* We can't use a non-leaf register if we're in a
 297                        leaf function.  */
 298                     || (current_function_is_leaf
 299                         && !LEAF_REGISTERS[new_reg + i])
 300 #endif
 301 #ifdef HARD_REGNO_RENAME_OK
 302                     || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
 303 #endif
 304                     )
 305                   break;
 306               if (i >= 0)
 307                 continue;
 308
 309               /* See whether it accepts all modes that occur in
 310                  definition and uses.  */
 311               for (tmp = this_du; tmp; tmp = tmp->next_use)
 312                 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
 313                      && ! DEBUG_INSN_P (tmp->insn))
 314                     || (tmp->need_caller_save_reg
 315                         && ! (HARD_REGNO_CALL_PART_CLOBBERED
 316                               (reg, GET_MODE (*tmp->loc)))
 317                         && (HARD_REGNO_CALL_PART_CLOBBERED
 318                             (new_reg, GET_MODE (*tmp->loc)))))
 319                   break;
 320               if (! tmp)
 321                 {
 322                   if (tick[best_new_reg] > tick[new_reg])
 323                     best_new_reg = new_reg;
 324                 }
 325             }
 326
 327           if (dump_file)
 328             {
 329               fprintf (dump_file, "Register %s in insn %d",
 330                        reg_names[reg], INSN_UID (this_du->insn));
 331               if (this_du->need_caller_save_reg)
 332                 fprintf (dump_file, " crosses a call");
 333             }
 334
 335           if (best_new_reg == reg)
 336             {
 337               tick[reg] = ++this_tick;
 338               if (dump_file)
 339                 fprintf (dump_file, "; no available better choice\n");
 340               continue;
 341             }
 342
 343           if (dump_file)
 344             fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
 345
 346           do_replace (this_du, best_new_reg);
 347           tick[best_new_reg] = ++this_tick;
 348           df_set_regs_ever_live (best_new_reg, true);
 349         }
 350
 351       obstack_free (&rename_obstack, first_obj);
 352     }
 353
 354   obstack_free (&rename_obstack, NULL);
 355
 356   if (dump_file)
 357     fputc ('\n', dump_file);
 358
 359   return 0;
 360 }
 361
 362 static void
 363 do_replace (struct du_chain *chain, int reg)
 364 {
 365   unsigned int base_regno = REGNO (*chain->loc);
 366
 367   gcc_assert (! DEBUG_INSN_P (chain->insn));
 368
 369   while (chain)
 370     {
 371       unsigned int regno = ORIGINAL_REGNO (*chain->loc);
 372       struct reg_attrs * attr = REG_ATTRS (*chain->loc);
 373       int reg_ptr = REG_POINTER (*chain->loc);
 374
 375       if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
 376         INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
 377       else
 378         {
 379           rtx note;
 380
 381           *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
 382           if (regno >= FIRST_PSEUDO_REGISTER)
 383             ORIGINAL_REGNO (*chain->loc) = regno;
 384           REG_ATTRS (*chain->loc) = attr;
 385           REG_POINTER (*chain->loc) = reg_ptr;
 386
 387           for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
 388             {
 389               if (REG_NOTE_KIND (note) == REG_DEAD
 390                   || REG_NOTE_KIND (note) == REG_UNUSED)
 391                 {
 392                   rtx reg = XEXP (note, 0);
 393                   gcc_assert (HARD_REGISTER_P (reg));
 394
 395                   if (REGNO (reg) == base_regno)
 396                     XEXP (note, 0) = *chain->loc;
 397                 }
 398             }
 399         }
 400
 401       df_insn_rescan (chain->insn);
 402       chain = chain->next_use;
 403     }
 404 }
 405
 406
 407 static struct du_chain *open_chains;
 408 static struct du_chain *closed_chains;
 409
 410 static void
 411 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
 412               enum scan_actions action, enum op_type type, int earlyclobber)
 413 {
 414   struct du_chain **p;
 415   rtx x = *loc;
 416   enum machine_mode mode = GET_MODE (x);
 417   int this_regno = REGNO (x);
 418   int this_nregs = hard_regno_nregs[this_regno][mode];
 419
 420   if (action == mark_write)
 421     {
 422       if (type == OP_OUT)
 423         {
 424           struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
 425           this_du->next_use = 0;
 426           this_du->next_chain = open_chains;
 427           this_du->loc = loc;
 428           this_du->insn = insn;
 429           this_du->cl = cl;
 430           this_du->need_caller_save_reg = 0;
 431           this_du->earlyclobber = earlyclobber;
 432           open_chains = this_du;
 433         }
 434       return;
 435     }
 436
 437   if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
 438     return;
 439
 440   for (p = &open_chains; *p;)
 441     {
 442       struct du_chain *this_du = *p;
 443
 444       /* Check if the chain has been terminated if it has then skip to
 445          the next chain.
 446
 447          This can happen when we've already appended the location to
 448          the chain in Step 3, but are trying to hide in-out operands
 449          from terminate_write in Step 5.  */
 450
 451       if (*this_du->loc == cc0_rtx)
 452         p = &this_du->next_chain;
 453       else
 454         {
 455           int regno = REGNO (*this_du->loc);
 456           int nregs = hard_regno_nregs[regno][GET_MODE (*this_du->loc)];
 457           int exact_match = (regno == this_regno && nregs == this_nregs);
 458
 459           if (regno + nregs <= this_regno
 460               || this_regno + this_nregs <= regno)
 461             {
 462               p = &this_du->next_chain;
 463               continue;
 464             }
 465
 466           if (action == mark_read || action == mark_access)
 467             {
 468               gcc_assert (exact_match || DEBUG_INSN_P (insn));
 469
 470               /* ??? Class NO_REGS can happen if the md file makes use of
 471                  EXTRA_CONSTRAINTS to match registers.  Which is arguably
 472                  wrong, but there we are.  Since we know not what this may
 473                  be replaced with, terminate the chain.  */
 474               if (cl != NO_REGS)
 475                 {
 476                   this_du = XOBNEW (&rename_obstack, struct du_chain);
 477                   this_du->next_use = 0;
 478                   this_du->next_chain = (*p)->next_chain;
 479                   this_du->loc = loc;
 480                   this_du->insn = insn;
 481                   this_du->cl = cl;
 482                   this_du->need_caller_save_reg = 0;
 483                   while (*p)
 484                     p = &(*p)->next_use;
 485                   *p = this_du;
 486                   return;
 487                 }
 488             }
 489
 490           if (action != terminate_overlapping_read || ! exact_match)
 491             {
 492               struct du_chain *next = this_du->next_chain;
 493
 494               /* Whether the terminated chain can be used for renaming
 495                  depends on the action and this being an exact match.
 496                  In either case, we remove this element from open_chains.  */
 497
 498               if ((action == terminate_dead || action == terminate_write)
 499                   && exact_match)
 500                 {
 501                   this_du->next_chain = closed_chains;
 502                   closed_chains = this_du;
 503                   if (dump_file)
 504                     fprintf (dump_file,
 505                              "Closing chain %s at insn %d (%s)\n",
 506                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
 507                              scan_actions_name[(int) action]);
 508                 }
 509               else
 510                 {
 511                   if (dump_file)
 512                     fprintf (dump_file,
 513                              "Discarding chain %s at insn %d (%s)\n",
 514                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
 515                              scan_actions_name[(int) action]);
 516                 }
 517               *p = next;
 518             }
 519           else
 520             p = &this_du->next_chain;
 521         }
 522     }
 523 }
 524
 525 /* Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
 526    BASE_REG_CLASS depending on how the register is being considered.  */
 527
 528 static void
 529 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
 530                   enum scan_actions action, enum machine_mode mode)
 531 {
 532   rtx x = *loc;
 533   RTX_CODE code = GET_CODE (x);
 534   const char *fmt;
 535   int i, j;
 536
 537   if (action == mark_write || action == mark_access)
 538     return;
 539
 540   switch (code)
 541     {
 542     case PLUS:
 543       {
 544         rtx orig_op0 = XEXP (x, 0);
 545         rtx orig_op1 = XEXP (x, 1);
 546         RTX_CODE code0 = GET_CODE (orig_op0);
 547         RTX_CODE code1 = GET_CODE (orig_op1);
 548         rtx op0 = orig_op0;
 549         rtx op1 = orig_op1;
 550         rtx *locI = NULL;
 551         rtx *locB = NULL;
 552         enum rtx_code index_code = SCRATCH;
 553
 554         if (GET_CODE (op0) == SUBREG)
 555           {
 556             op0 = SUBREG_REG (op0);
 557             code0 = GET_CODE (op0);
 558           }
 559
 560         if (GET_CODE (op1) == SUBREG)
 561           {
 562             op1 = SUBREG_REG (op1);
 563             code1 = GET_CODE (op1);
 564           }
 565
 566         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
 567             || code0 == ZERO_EXTEND || code1 == MEM)
 568           {
 569             locI = &XEXP (x, 0);
 570             locB = &XEXP (x, 1);
 571             index_code = GET_CODE (*locI);
 572           }
 573         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
 574                  || code1 == ZERO_EXTEND || code0 == MEM)
 575           {
 576             locI = &XEXP (x, 1);
 577             locB = &XEXP (x, 0);
 578             index_code = GET_CODE (*locI);
 579           }
 580         else if (code0 == CONST_INT || code0 == CONST
 581                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
 582           {
 583             locB = &XEXP (x, 1);
 584             index_code = GET_CODE (XEXP (x, 0));
 585           }
 586         else if (code1 == CONST_INT || code1 == CONST
 587                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
 588           {
 589             locB = &XEXP (x, 0);
 590             index_code = GET_CODE (XEXP (x, 1));
 591           }
 592         else if (code0 == REG && code1 == REG)
 593           {
 594             int index_op;
 595             unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
 596
 597             if (REGNO_OK_FOR_INDEX_P (regno1)
 598                 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
 599               index_op = 1;
 600             else if (REGNO_OK_FOR_INDEX_P (regno0)
 601                      && regno_ok_for_base_p (regno1, mode, PLUS, REG))
 602               index_op = 0;
 603             else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
 604                      || REGNO_OK_FOR_INDEX_P (regno1))
 605               index_op = 1;
 606             else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
 607               index_op = 0;
 608             else
 609               index_op = 1;
 610
 611             locI = &XEXP (x, index_op);
 612             locB = &XEXP (x, !index_op);
 613             index_code = GET_CODE (*locI);
 614           }
 615         else if (code0 == REG)
 616           {
 617             locI = &XEXP (x, 0);
 618             locB = &XEXP (x, 1);
 619             index_code = GET_CODE (*locI);
 620           }
 621         else if (code1 == REG)
 622           {
 623             locI = &XEXP (x, 1);
 624             locB = &XEXP (x, 0);
 625             index_code = GET_CODE (*locI);
 626           }
 627
 628         if (locI)
 629           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
 630         if (locB)
 631           scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
 632                             action, mode);
 633
 634         return;
 635       }
 636
 637     case POST_INC:
 638     case POST_DEC:
 639     case POST_MODIFY:
 640     case PRE_INC:
 641     case PRE_DEC:
 642     case PRE_MODIFY:
 643 #ifndef AUTO_INC_DEC
 644       /* If the target doesn't claim to handle autoinc, this must be
 645          something special, like a stack push.  Kill this chain.  */
 646       action = terminate_all_read;
 647 #endif
 648       break;
 649
 650     case MEM:
 651       scan_rtx_address (insn, &XEXP (x, 0),
 652                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
 653                         GET_MODE (x));
 654       return;
 655
 656     case REG:
 657       scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
 658       return;
 659
 660     default:
 661       break;
 662     }
 663
 664   fmt = GET_RTX_FORMAT (code);
 665   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 666     {
 667       if (fmt[i] == 'e')
 668         scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
 669       else if (fmt[i] == 'E')
 670         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 671           scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
 672     }
 673 }
 674
 675 static void
 676 scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
 677           enum scan_actions action, enum op_type type, int earlyclobber)
 678 {
 679   const char *fmt;
 680   rtx x = *loc;
 681   enum rtx_code code = GET_CODE (x);
 682   int i, j;
 683
 684   code = GET_CODE (x);
 685   switch (code)
 686     {
 687     case CONST:
 688     case CONST_INT:
 689     case CONST_DOUBLE:
 690     case CONST_FIXED:
 691     case CONST_VECTOR:
 692     case SYMBOL_REF:
 693     case LABEL_REF:
 694     case CC0:
 695     case PC:
 696       return;
 697
 698     case REG:
 699       scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
 700       return;
 701
 702     case MEM:
 703       scan_rtx_address (insn, &XEXP (x, 0),
 704                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
 705                         GET_MODE (x));
 706       return;
 707
 708     case SET:
 709       scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
 710       scan_rtx (insn, &SET_DEST (x), cl, action,
 711                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
 712       return;
 713
 714     case STRICT_LOW_PART:
 715       scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
 716       return;
 717
 718     case ZERO_EXTRACT:
 719     case SIGN_EXTRACT:
 720       scan_rtx (insn, &XEXP (x, 0), cl, action,
 721                 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
 722       scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
 723       scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
 724       return;
 725
 726     case POST_INC:
 727     case PRE_INC:
 728     case POST_DEC:
 729     case PRE_DEC:
 730     case POST_MODIFY:
 731     case PRE_MODIFY:
 732       /* Should only happen inside MEM.  */
 733       gcc_unreachable ();
 734
 735     case CLOBBER:
 736       scan_rtx (insn, &SET_DEST (x), cl, action,
 737                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
 738       return;
 739
 740     case EXPR_LIST:
 741       scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
 742       if (XEXP (x, 1))
 743         scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
 744       return;
 745
 746     default:
 747       break;
 748     }
 749
 750   fmt = GET_RTX_FORMAT (code);
 751   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 752     {
 753       if (fmt[i] == 'e')
 754         scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
 755       else if (fmt[i] == 'E')
 756         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 757           scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
 758     }
 759 }
 760
 761 /* Build def/use chain.  */
 762
 763 static struct du_chain *
 764 build_def_use (basic_block bb)
 765 {
 766   rtx insn;
 767
 768   open_chains = closed_chains = NULL;
 769
 770   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
 771     {
 772       if (NONDEBUG_INSN_P (insn))
 773         {
 774           int n_ops;
 775           rtx note;
 776           rtx old_operands[MAX_RECOG_OPERANDS];
 777           rtx old_dups[MAX_DUP_OPERANDS];
 778           int i, icode;
 779           int alt;
 780           int predicated;
 781
 782           /* Process the insn, determining its effect on the def-use
 783              chains.  We perform the following steps with the register
 784              references in the insn:
 785              (1) Any read that overlaps an open chain, but doesn't exactly
 786                  match, causes that chain to be closed.  We can't deal
 787                  with overlaps yet.
 788              (2) Any read outside an operand causes any chain it overlaps
 789                  with to be closed, since we can't replace it.
 790              (3) Any read inside an operand is added if there's already
 791                  an open chain for it.
 792              (4) For any REG_DEAD note we find, close open chains that
 793                  overlap it.
 794              (5) For any write we find, close open chains that overlap it.
 795              (6) For any write we find in an operand, make a new chain.
 796              (7) For any REG_UNUSED, close any chains we just opened.  */
 797
 798           icode = recog_memoized (insn);
 799           extract_insn (insn);
 800           if (! constrain_operands (1))
 801             fatal_insn_not_found (insn);
 802           preprocess_constraints ();
 803           alt = which_alternative;
 804           n_ops = recog_data.n_operands;
 805
 806           /* Simplify the code below by rewriting things to reflect
 807              matching constraints.  Also promote OP_OUT to OP_INOUT
 808              in predicated instructions.  */
 809
 810           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 811           for (i = 0; i < n_ops; ++i)
 812             {
 813               int matches = recog_op_alt[i][alt].matches;
 814               if (matches >= 0)
 815                 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
 816               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 817                   || (predicated && recog_data.operand_type[i] == OP_OUT))
 818                 recog_data.operand_type[i] = OP_INOUT;
 819             }
 820
 821           /* Step 1: Close chains for which we have overlapping reads.  */
 822           for (i = 0; i < n_ops; i++)
 823             scan_rtx (insn, recog_data.operand_loc[i],
 824                       NO_REGS, terminate_overlapping_read,
 825                       recog_data.operand_type[i], 0);
 826
 827           /* Step 2: Close chains for which we have reads outside operands.
 828              We do this by munging all operands into CC0, and closing
 829              everything remaining.  */
 830
 831           for (i = 0; i < n_ops; i++)
 832             {
 833               old_operands[i] = recog_data.operand[i];
 834               /* Don't squash match_operator or match_parallel here, since
 835                  we don't know that all of the contained registers are
 836                  reachable by proper operands.  */
 837               if (recog_data.constraints[i][0] == '\0')
 838                 continue;
 839               *recog_data.operand_loc[i] = cc0_rtx;
 840             }
 841           for (i = 0; i < recog_data.n_dups; i++)
 842             {
 843               old_dups[i] = *recog_data.dup_loc[i];
 844               *recog_data.dup_loc[i] = cc0_rtx;
 845             }
 846
 847           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
 848                     OP_IN, 0);
 849
 850           for (i = 0; i < recog_data.n_dups; i++)
 851             *recog_data.dup_loc[i] = old_dups[i];
 852           for (i = 0; i < n_ops; i++)
 853             *recog_data.operand_loc[i] = old_operands[i];
 854           if (recog_data.n_dups)
 855             df_insn_rescan (insn);
 856
 857           /* Step 2B: Can't rename function call argument registers.  */
 858           if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
 859             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
 860                       NO_REGS, terminate_all_read, OP_IN, 0);
 861
 862           /* Step 2C: Can't rename asm operands that were originally
 863              hard registers.  */
 864           if (asm_noperands (PATTERN (insn)) > 0)
 865             for (i = 0; i < n_ops; i++)
 866               {
 867                 rtx *loc = recog_data.operand_loc[i];
 868                 rtx op = *loc;
 869
 870                 if (REG_P (op)
 871                     && REGNO (op) == ORIGINAL_REGNO (op)
 872                     && (recog_data.operand_type[i] == OP_IN
 873                         || recog_data.operand_type[i] == OP_INOUT))
 874                   scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
 875               }
 876
 877           /* Step 3: Append to chains for reads inside operands.  */
 878           for (i = 0; i < n_ops + recog_data.n_dups; i++)
 879             {
 880               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 881               rtx *loc = (i < n_ops
 882                           ? recog_data.operand_loc[opn]
 883                           : recog_data.dup_loc[i - n_ops]);
 884               enum reg_class cl = recog_op_alt[opn][alt].cl;
 885               enum op_type type = recog_data.operand_type[opn];
 886
 887               /* Don't scan match_operand here, since we've no reg class
 888                  information to pass down.  Any operands that we could
 889                  substitute in will be represented elsewhere.  */
 890               if (recog_data.constraints[opn][0] == '\0')
 891                 continue;
 892
 893               if (recog_op_alt[opn][alt].is_address)
 894                 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
 895               else
 896                 scan_rtx (insn, loc, cl, mark_read, type, 0);
 897             }
 898
 899           /* Step 3B: Record updates for regs in REG_INC notes, and
 900              source regs in REG_FRAME_RELATED_EXPR notes.  */
 901           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 902             if (REG_NOTE_KIND (note) == REG_INC
 903                 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
 904               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
 905                         OP_INOUT, 0);
 906
 907           /* Step 4: Close chains for registers that die here.  */
 908           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 909             if (REG_NOTE_KIND (note) == REG_DEAD)
 910               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 911                         OP_IN, 0);
 912
 913           /* Step 4B: If this is a call, any chain live at this point
 914              requires a caller-saved reg.  */
 915           if (CALL_P (insn))
 916             {
 917               struct du_chain *p;
 918               for (p = open_chains; p; p = p->next_chain)
 919                 p->need_caller_save_reg = 1;
 920             }
 921
 922           /* Step 5: Close open chains that overlap writes.  Similar to
 923              step 2, we hide in-out operands, since we do not want to
 924              close these chains.  */
 925
 926           for (i = 0; i < n_ops; i++)
 927             {
 928               old_operands[i] = recog_data.operand[i];
 929               if (recog_data.operand_type[i] == OP_INOUT)
 930                 *recog_data.operand_loc[i] = cc0_rtx;
 931             }
 932           for (i = 0; i < recog_data.n_dups; i++)
 933             {
 934               int opn = recog_data.dup_num[i];
 935               old_dups[i] = *recog_data.dup_loc[i];
 936               if (recog_data.operand_type[opn] == OP_INOUT)
 937                 *recog_data.dup_loc[i] = cc0_rtx;
 938             }
 939
 940           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
 941
 942           for (i = 0; i < recog_data.n_dups; i++)
 943             *recog_data.dup_loc[i] = old_dups[i];
 944           for (i = 0; i < n_ops; i++)
 945             *recog_data.operand_loc[i] = old_operands[i];
 946
 947           /* Step 6: Begin new chains for writes inside operands.  */
 948           /* ??? Many targets have output constraints on the SET_DEST
 949              of a call insn, which is stupid, since these are certainly
 950              ABI defined hard registers.  Don't change calls at all.
 951              Similarly take special care for asm statement that originally
 952              referenced hard registers.  */
 953           if (asm_noperands (PATTERN (insn)) > 0)
 954             {
 955               for (i = 0; i < n_ops; i++)
 956                 if (recog_data.operand_type[i] == OP_OUT)
 957                   {
 958                     rtx *loc = recog_data.operand_loc[i];
 959                     rtx op = *loc;
 960                     enum reg_class cl = recog_op_alt[i][alt].cl;
 961
 962                     if (REG_P (op)
 963                         && REGNO (op) == ORIGINAL_REGNO (op))
 964                       continue;
 965
 966                     scan_rtx (insn, loc, cl, mark_write, OP_OUT,
 967                               recog_op_alt[i][alt].earlyclobber);
 968                   }
 969             }
 970           else if (!CALL_P (insn))
 971             for (i = 0; i < n_ops + recog_data.n_dups; i++)
 972               {
 973                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 974                 rtx *loc = (i < n_ops
 975                             ? recog_data.operand_loc[opn]
 976                             : recog_data.dup_loc[i - n_ops]);
 977                 enum reg_class cl = recog_op_alt[opn][alt].cl;
 978
 979                 if (recog_data.operand_type[opn] == OP_OUT)
 980                   scan_rtx (insn, loc, cl, mark_write, OP_OUT,
 981                             recog_op_alt[opn][alt].earlyclobber);
 982               }
 983
 984           /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
 985              notes for update.  */
 986           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 987             if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
 988               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
 989                         OP_INOUT, 0);
 990
 991           /* Step 7: Close chains for registers that were never
 992              really used here.  */
 993           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 994             if (REG_NOTE_KIND (note) == REG_UNUSED)
 995               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 996                         OP_IN, 0);
 997         }
 998       else if (DEBUG_INSN_P (insn)
 999                && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1000         {
1001           scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1002                     ALL_REGS, mark_read, OP_IN, 0);
1003         }
1004       if (insn == BB_END (bb))
1005         break;
1006     }
1007
1008   /* Since we close every chain when we find a REG_DEAD note, anything that
1009      is still open lives past the basic block, so it can't be renamed.  */
1010   return closed_chains;
1011 }
1012
1013 /* Dump all def/use chains in CHAINS to DUMP_FILE.  They are
1014    printed in reverse order as that's how we build them.  */
1015
1016 static void
1017 dump_def_use_chain (struct du_chain *chains)
1018 {
1019   while (chains)
1020     {
1021       struct du_chain *this_du = chains;
1022       int r = REGNO (*this_du->loc);
1023       int nregs = hard_regno_nregs[r][GET_MODE (*this_du->loc)];
1024       fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs);
1025       while (this_du)
1026         {
1027           fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1028                    reg_class_names[this_du->cl]);
1029           this_du = this_du->next_use;
1030         }
1031       fprintf (dump_file, "\n");
1032       chains = chains->next_chain;
1033     }
1034 }
1035
1036 \f
1037 static bool
1038 gate_handle_regrename (void)
1039 {
1040   return (optimize > 0 && (flag_rename_registers));
1041 }
1042
1043 struct rtl_opt_pass pass_regrename =
1044 {
1045  {
1046   RTL_PASS,
1047   "rnreg",                              /* name */
1048   gate_handle_regrename,                /* gate */
1049   regrename_optimize,                   /* execute */
1050   NULL,                                 /* sub */
1051   NULL,                                 /* next */
1052   0,                                    /* static_pass_number */
1053   TV_RENAME_REGISTERS,                  /* tv_id */
1054   0,                                    /* properties_required */
1055   0,                                    /* properties_provided */
1056   0,                                    /* properties_destroyed */
1057   0,                                    /* todo_flags_start */
1058   TODO_df_finish | TODO_verify_rtl_sharing |
1059   TODO_dump_func                        /* todo_flags_finish */
1060  }
1061 };
1062