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, *last;
 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           /* Find last entry on chain (which has the need_caller_save bit),
 263              count number of uses, and narrow the set of registers we can
 264              use for renaming.  */
 265           n_uses = 0;
 266           for (last = this_du; last->next_use; last = last->next_use)
 267             {
 268               n_uses++;
 269               IOR_COMPL_HARD_REG_SET (this_unavailable,
 270                                       reg_class_contents[last->cl]);
 271             }
 272           if (n_uses < 1)
 273             continue;
 274
 275           IOR_COMPL_HARD_REG_SET (this_unavailable,
 276                                   reg_class_contents[last->cl]);
 277
 278           if (this_du->need_caller_save_reg)
 279             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
 280
 281           merge_overlapping_regs (bb, &this_unavailable, this_du);
 282
 283           /* Now potential_regs is a reasonable approximation, let's
 284              have a closer look at each register still in there.  */
 285           for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
 286             {
 287               int nregs = hard_regno_nregs[new_reg][GET_MODE (*this_du->loc)];
 288
 289               for (i = nregs - 1; i >= 0; --i)
 290                 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
 291                     || fixed_regs[new_reg + i]
 292                     || global_regs[new_reg + i]
 293                     /* Can't use regs which aren't saved by the prologue.  */
 294                     || (! df_regs_ever_live_p (new_reg + i)
 295                         && ! call_used_regs[new_reg + i])
 296 #ifdef LEAF_REGISTERS
 297                     /* We can't use a non-leaf register if we're in a
 298                        leaf function.  */
 299                     || (current_function_is_leaf
 300                         && !LEAF_REGISTERS[new_reg + i])
 301 #endif
 302 #ifdef HARD_REGNO_RENAME_OK
 303                     || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
 304 #endif
 305                     )
 306                   break;
 307               if (i >= 0)
 308                 continue;
 309
 310               /* See whether it accepts all modes that occur in
 311                  definition and uses.  */
 312               for (tmp = this_du; tmp; tmp = tmp->next_use)
 313                 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
 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 (last->insn));
 331               if (last->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   while (chain)
 366     {
 367       unsigned int regno = ORIGINAL_REGNO (*chain->loc);
 368       struct reg_attrs * attr = REG_ATTRS (*chain->loc);
 369       int reg_ptr = REG_POINTER (*chain->loc);
 370
 371       *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
 372       if (regno >= FIRST_PSEUDO_REGISTER)
 373         ORIGINAL_REGNO (*chain->loc) = regno;
 374       REG_ATTRS (*chain->loc) = attr;
 375       REG_POINTER (*chain->loc) = reg_ptr;
 376       df_insn_rescan (chain->insn);
 377       chain = chain->next_use;
 378     }
 379 }
 380
 381
 382 static struct du_chain *open_chains;
 383 static struct du_chain *closed_chains;
 384
 385 static void
 386 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
 387               enum scan_actions action, enum op_type type, int earlyclobber)
 388 {
 389   struct du_chain **p;
 390   rtx x = *loc;
 391   enum machine_mode mode = GET_MODE (x);
 392   int this_regno = REGNO (x);
 393   int this_nregs = hard_regno_nregs[this_regno][mode];
 394
 395   if (action == mark_write)
 396     {
 397       if (type == OP_OUT)
 398         {
 399           struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
 400           this_du->next_use = 0;
 401           this_du->next_chain = open_chains;
 402           this_du->loc = loc;
 403           this_du->insn = insn;
 404           this_du->cl = cl;
 405           this_du->need_caller_save_reg = 0;
 406           this_du->earlyclobber = earlyclobber;
 407           open_chains = this_du;
 408         }
 409       return;
 410     }
 411
 412   if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
 413     return;
 414
 415   for (p = &open_chains; *p;)
 416     {
 417       struct du_chain *this_du = *p;
 418
 419       /* Check if the chain has been terminated if it has then skip to
 420          the next chain.
 421
 422          This can happen when we've already appended the location to
 423          the chain in Step 3, but are trying to hide in-out operands
 424          from terminate_write in Step 5.  */
 425
 426       if (*this_du->loc == cc0_rtx)
 427         p = &this_du->next_chain;
 428       else
 429         {
 430           int regno = REGNO (*this_du->loc);
 431           int nregs = hard_regno_nregs[regno][GET_MODE (*this_du->loc)];
 432           int exact_match = (regno == this_regno && nregs == this_nregs);
 433
 434           if (regno + nregs <= this_regno
 435               || this_regno + this_nregs <= regno)
 436             {
 437               p = &this_du->next_chain;
 438               continue;
 439             }
 440
 441           if (action == mark_read || action == mark_access)
 442             {
 443               gcc_assert (exact_match);
 444
 445               /* ??? Class NO_REGS can happen if the md file makes use of
 446                  EXTRA_CONSTRAINTS to match registers.  Which is arguably
 447                  wrong, but there we are.  Since we know not what this may
 448                  be replaced with, terminate the chain.  */
 449               if (cl != NO_REGS)
 450                 {
 451                   this_du = XOBNEW (&rename_obstack, struct du_chain);
 452                   this_du->next_use = 0;
 453                   this_du->next_chain = (*p)->next_chain;
 454                   this_du->loc = loc;
 455                   this_du->insn = insn;
 456                   this_du->cl = cl;
 457                   this_du->need_caller_save_reg = 0;
 458                   while (*p)
 459                     p = &(*p)->next_use;
 460                   *p = this_du;
 461                   return;
 462                 }
 463             }
 464
 465           if (action != terminate_overlapping_read || ! exact_match)
 466             {
 467               struct du_chain *next = this_du->next_chain;
 468
 469               /* Whether the terminated chain can be used for renaming
 470                  depends on the action and this being an exact match.
 471                  In either case, we remove this element from open_chains.  */
 472
 473               if ((action == terminate_dead || action == terminate_write)
 474                   && exact_match)
 475                 {
 476                   this_du->next_chain = closed_chains;
 477                   closed_chains = this_du;
 478                   if (dump_file)
 479                     fprintf (dump_file,
 480                              "Closing chain %s at insn %d (%s)\n",
 481                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
 482                              scan_actions_name[(int) action]);
 483                 }
 484               else
 485                 {
 486                   if (dump_file)
 487                     fprintf (dump_file,
 488                              "Discarding chain %s at insn %d (%s)\n",
 489                              reg_names[REGNO (*this_du->loc)], INSN_UID (insn),
 490                              scan_actions_name[(int) action]);
 491                 }
 492               *p = next;
 493             }
 494           else
 495             p = &this_du->next_chain;
 496         }
 497     }
 498 }
 499
 500 /* Adapted from find_reloads_address_1.  CL is INDEX_REG_CLASS or
 501    BASE_REG_CLASS depending on how the register is being considered.  */
 502
 503 static void
 504 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
 505                   enum scan_actions action, enum machine_mode mode)
 506 {
 507   rtx x = *loc;
 508   RTX_CODE code = GET_CODE (x);
 509   const char *fmt;
 510   int i, j;
 511
 512   if (action == mark_write || action == mark_access)
 513     return;
 514
 515   switch (code)
 516     {
 517     case PLUS:
 518       {
 519         rtx orig_op0 = XEXP (x, 0);
 520         rtx orig_op1 = XEXP (x, 1);
 521         RTX_CODE code0 = GET_CODE (orig_op0);
 522         RTX_CODE code1 = GET_CODE (orig_op1);
 523         rtx op0 = orig_op0;
 524         rtx op1 = orig_op1;
 525         rtx *locI = NULL;
 526         rtx *locB = NULL;
 527         enum rtx_code index_code = SCRATCH;
 528
 529         if (GET_CODE (op0) == SUBREG)
 530           {
 531             op0 = SUBREG_REG (op0);
 532             code0 = GET_CODE (op0);
 533           }
 534
 535         if (GET_CODE (op1) == SUBREG)
 536           {
 537             op1 = SUBREG_REG (op1);
 538             code1 = GET_CODE (op1);
 539           }
 540
 541         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
 542             || code0 == ZERO_EXTEND || code1 == MEM)
 543           {
 544             locI = &XEXP (x, 0);
 545             locB = &XEXP (x, 1);
 546             index_code = GET_CODE (*locI);
 547           }
 548         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
 549                  || code1 == ZERO_EXTEND || code0 == MEM)
 550           {
 551             locI = &XEXP (x, 1);
 552             locB = &XEXP (x, 0);
 553             index_code = GET_CODE (*locI);
 554           }
 555         else if (code0 == CONST_INT || code0 == CONST
 556                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
 557           {
 558             locB = &XEXP (x, 1);
 559             index_code = GET_CODE (XEXP (x, 0));
 560           }
 561         else if (code1 == CONST_INT || code1 == CONST
 562                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
 563           {
 564             locB = &XEXP (x, 0);
 565             index_code = GET_CODE (XEXP (x, 1));
 566           }
 567         else if (code0 == REG && code1 == REG)
 568           {
 569             int index_op;
 570             unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
 571
 572             if (REGNO_OK_FOR_INDEX_P (regno1)
 573                 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
 574               index_op = 1;
 575             else if (REGNO_OK_FOR_INDEX_P (regno0)
 576                      && regno_ok_for_base_p (regno1, mode, PLUS, REG))
 577               index_op = 0;
 578             else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
 579                      || REGNO_OK_FOR_INDEX_P (regno1))
 580               index_op = 1;
 581             else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
 582               index_op = 0;
 583             else
 584               index_op = 1;
 585
 586             locI = &XEXP (x, index_op);
 587             locB = &XEXP (x, !index_op);
 588             index_code = GET_CODE (*locI);
 589           }
 590         else if (code0 == REG)
 591           {
 592             locI = &XEXP (x, 0);
 593             locB = &XEXP (x, 1);
 594             index_code = GET_CODE (*locI);
 595           }
 596         else if (code1 == REG)
 597           {
 598             locI = &XEXP (x, 1);
 599             locB = &XEXP (x, 0);
 600             index_code = GET_CODE (*locI);
 601           }
 602
 603         if (locI)
 604           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
 605         if (locB)
 606           scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
 607                             action, mode);
 608
 609         return;
 610       }
 611
 612     case POST_INC:
 613     case POST_DEC:
 614     case POST_MODIFY:
 615     case PRE_INC:
 616     case PRE_DEC:
 617     case PRE_MODIFY:
 618 #ifndef AUTO_INC_DEC
 619       /* If the target doesn't claim to handle autoinc, this must be
 620          something special, like a stack push.  Kill this chain.  */
 621       action = terminate_all_read;
 622 #endif
 623       break;
 624
 625     case MEM:
 626       scan_rtx_address (insn, &XEXP (x, 0),
 627                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
 628                         GET_MODE (x));
 629       return;
 630
 631     case REG:
 632       scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
 633       return;
 634
 635     default:
 636       break;
 637     }
 638
 639   fmt = GET_RTX_FORMAT (code);
 640   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 641     {
 642       if (fmt[i] == 'e')
 643         scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
 644       else if (fmt[i] == 'E')
 645         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 646           scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
 647     }
 648 }
 649
 650 static void
 651 scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
 652           enum scan_actions action, enum op_type type, int earlyclobber)
 653 {
 654   const char *fmt;
 655   rtx x = *loc;
 656   enum rtx_code code = GET_CODE (x);
 657   int i, j;
 658
 659   code = GET_CODE (x);
 660   switch (code)
 661     {
 662     case CONST:
 663     case CONST_INT:
 664     case CONST_DOUBLE:
 665     case CONST_FIXED:
 666     case CONST_VECTOR:
 667     case SYMBOL_REF:
 668     case LABEL_REF:
 669     case CC0:
 670     case PC:
 671       return;
 672
 673     case REG:
 674       scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
 675       return;
 676
 677     case MEM:
 678       scan_rtx_address (insn, &XEXP (x, 0),
 679                         base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
 680                         GET_MODE (x));
 681       return;
 682
 683     case SET:
 684       scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
 685       scan_rtx (insn, &SET_DEST (x), cl, action,
 686                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
 687       return;
 688
 689     case STRICT_LOW_PART:
 690       scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
 691       return;
 692
 693     case ZERO_EXTRACT:
 694     case SIGN_EXTRACT:
 695       scan_rtx (insn, &XEXP (x, 0), cl, action,
 696                 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
 697       scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
 698       scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
 699       return;
 700
 701     case POST_INC:
 702     case PRE_INC:
 703     case POST_DEC:
 704     case PRE_DEC:
 705     case POST_MODIFY:
 706     case PRE_MODIFY:
 707       /* Should only happen inside MEM.  */
 708       gcc_unreachable ();
 709
 710     case CLOBBER:
 711       scan_rtx (insn, &SET_DEST (x), cl, action,
 712                 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
 713       return;
 714
 715     case EXPR_LIST:
 716       scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
 717       if (XEXP (x, 1))
 718         scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
 719       return;
 720
 721     default:
 722       break;
 723     }
 724
 725   fmt = GET_RTX_FORMAT (code);
 726   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 727     {
 728       if (fmt[i] == 'e')
 729         scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
 730       else if (fmt[i] == 'E')
 731         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 732           scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
 733     }
 734 }
 735
 736 /* Build def/use chain.  */
 737
 738 static struct du_chain *
 739 build_def_use (basic_block bb)
 740 {
 741   rtx insn;
 742
 743   open_chains = closed_chains = NULL;
 744
 745   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
 746     {
 747       if (INSN_P (insn))
 748         {
 749           int n_ops;
 750           rtx note;
 751           rtx old_operands[MAX_RECOG_OPERANDS];
 752           rtx old_dups[MAX_DUP_OPERANDS];
 753           int i, icode;
 754           int alt;
 755           int predicated;
 756
 757           /* Process the insn, determining its effect on the def-use
 758              chains.  We perform the following steps with the register
 759              references in the insn:
 760              (1) Any read that overlaps an open chain, but doesn't exactly
 761                  match, causes that chain to be closed.  We can't deal
 762                  with overlaps yet.
 763              (2) Any read outside an operand causes any chain it overlaps
 764                  with to be closed, since we can't replace it.
 765              (3) Any read inside an operand is added if there's already
 766                  an open chain for it.
 767              (4) For any REG_DEAD note we find, close open chains that
 768                  overlap it.
 769              (5) For any write we find, close open chains that overlap it.
 770              (6) For any write we find in an operand, make a new chain.
 771              (7) For any REG_UNUSED, close any chains we just opened.  */
 772
 773           icode = recog_memoized (insn);
 774           extract_insn (insn);
 775           if (! constrain_operands (1))
 776             fatal_insn_not_found (insn);
 777           preprocess_constraints ();
 778           alt = which_alternative;
 779           n_ops = recog_data.n_operands;
 780
 781           /* Simplify the code below by rewriting things to reflect
 782              matching constraints.  Also promote OP_OUT to OP_INOUT
 783              in predicated instructions.  */
 784
 785           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 786           for (i = 0; i < n_ops; ++i)
 787             {
 788               int matches = recog_op_alt[i][alt].matches;
 789               if (matches >= 0)
 790                 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
 791               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 792                   || (predicated && recog_data.operand_type[i] == OP_OUT))
 793                 recog_data.operand_type[i] = OP_INOUT;
 794             }
 795
 796           /* Step 1: Close chains for which we have overlapping reads.  */
 797           for (i = 0; i < n_ops; i++)
 798             scan_rtx (insn, recog_data.operand_loc[i],
 799                       NO_REGS, terminate_overlapping_read,
 800                       recog_data.operand_type[i], 0);
 801
 802           /* Step 2: Close chains for which we have reads outside operands.
 803              We do this by munging all operands into CC0, and closing
 804              everything remaining.  */
 805
 806           for (i = 0; i < n_ops; i++)
 807             {
 808               old_operands[i] = recog_data.operand[i];
 809               /* Don't squash match_operator or match_parallel here, since
 810                  we don't know that all of the contained registers are
 811                  reachable by proper operands.  */
 812               if (recog_data.constraints[i][0] == '\0')
 813                 continue;
 814               *recog_data.operand_loc[i] = cc0_rtx;
 815             }
 816           for (i = 0; i < recog_data.n_dups; i++)
 817             {
 818               old_dups[i] = *recog_data.dup_loc[i];
 819               *recog_data.dup_loc[i] = cc0_rtx;
 820             }
 821
 822           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
 823                     OP_IN, 0);
 824
 825           for (i = 0; i < recog_data.n_dups; i++)
 826             *recog_data.dup_loc[i] = old_dups[i];
 827           for (i = 0; i < n_ops; i++)
 828             *recog_data.operand_loc[i] = old_operands[i];
 829           if (recog_data.n_dups)
 830             df_insn_rescan (insn);
 831
 832           /* Step 2B: Can't rename function call argument registers.  */
 833           if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
 834             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
 835                       NO_REGS, terminate_all_read, OP_IN, 0);
 836
 837           /* Step 2C: Can't rename asm operands that were originally
 838              hard registers.  */
 839           if (asm_noperands (PATTERN (insn)) > 0)
 840             for (i = 0; i < n_ops; i++)
 841               {
 842                 rtx *loc = recog_data.operand_loc[i];
 843                 rtx op = *loc;
 844
 845                 if (REG_P (op)
 846                     && REGNO (op) == ORIGINAL_REGNO (op)
 847                     && (recog_data.operand_type[i] == OP_IN
 848                         || recog_data.operand_type[i] == OP_INOUT))
 849                   scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
 850               }
 851
 852           /* Step 3: Append to chains for reads inside operands.  */
 853           for (i = 0; i < n_ops + recog_data.n_dups; i++)
 854             {
 855               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 856               rtx *loc = (i < n_ops
 857                           ? recog_data.operand_loc[opn]
 858                           : recog_data.dup_loc[i - n_ops]);
 859               enum reg_class cl = recog_op_alt[opn][alt].cl;
 860               enum op_type type = recog_data.operand_type[opn];
 861
 862               /* Don't scan match_operand here, since we've no reg class
 863                  information to pass down.  Any operands that we could
 864                  substitute in will be represented elsewhere.  */
 865               if (recog_data.constraints[opn][0] == '\0')
 866                 continue;
 867
 868               if (recog_op_alt[opn][alt].is_address)
 869                 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
 870               else
 871                 scan_rtx (insn, loc, cl, mark_read, type, 0);
 872             }
 873
 874           /* Step 3B: Record updates for regs in REG_INC notes, and
 875              source regs in REG_FRAME_RELATED_EXPR notes.  */
 876           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 877             if (REG_NOTE_KIND (note) == REG_INC
 878                 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
 879               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
 880                         OP_INOUT, 0);
 881
 882           /* Step 4: Close chains for registers that die here.  */
 883           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 884             if (REG_NOTE_KIND (note) == REG_DEAD)
 885               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 886                         OP_IN, 0);
 887
 888           /* Step 4B: If this is a call, any chain live at this point
 889              requires a caller-saved reg.  */
 890           if (CALL_P (insn))
 891             {
 892               struct du_chain *p;
 893               for (p = open_chains; p; p = p->next_chain)
 894                 p->need_caller_save_reg = 1;
 895             }
 896
 897           /* Step 5: Close open chains that overlap writes.  Similar to
 898              step 2, we hide in-out operands, since we do not want to
 899              close these chains.  */
 900
 901           for (i = 0; i < n_ops; i++)
 902             {
 903               old_operands[i] = recog_data.operand[i];
 904               if (recog_data.operand_type[i] == OP_INOUT)
 905                 *recog_data.operand_loc[i] = cc0_rtx;
 906             }
 907           for (i = 0; i < recog_data.n_dups; i++)
 908             {
 909               int opn = recog_data.dup_num[i];
 910               old_dups[i] = *recog_data.dup_loc[i];
 911               if (recog_data.operand_type[opn] == OP_INOUT)
 912                 *recog_data.dup_loc[i] = cc0_rtx;
 913             }
 914
 915           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
 916
 917           for (i = 0; i < recog_data.n_dups; i++)
 918             *recog_data.dup_loc[i] = old_dups[i];
 919           for (i = 0; i < n_ops; i++)
 920             *recog_data.operand_loc[i] = old_operands[i];
 921
 922           /* Step 6: Begin new chains for writes inside operands.  */
 923           /* ??? Many targets have output constraints on the SET_DEST
 924              of a call insn, which is stupid, since these are certainly
 925              ABI defined hard registers.  Don't change calls at all.
 926              Similarly take special care for asm statement that originally
 927              referenced hard registers.  */
 928           if (asm_noperands (PATTERN (insn)) > 0)
 929             {
 930               for (i = 0; i < n_ops; i++)
 931                 if (recog_data.operand_type[i] == OP_OUT)
 932                   {
 933                     rtx *loc = recog_data.operand_loc[i];
 934                     rtx op = *loc;
 935                     enum reg_class cl = recog_op_alt[i][alt].cl;
 936
 937                     if (REG_P (op)
 938                         && REGNO (op) == ORIGINAL_REGNO (op))
 939                       continue;
 940
 941                     scan_rtx (insn, loc, cl, mark_write, OP_OUT,
 942                               recog_op_alt[i][alt].earlyclobber);
 943                   }
 944             }
 945           else if (!CALL_P (insn))
 946             for (i = 0; i < n_ops + recog_data.n_dups; i++)
 947               {
 948                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 949                 rtx *loc = (i < n_ops
 950                             ? recog_data.operand_loc[opn]
 951                             : recog_data.dup_loc[i - n_ops]);
 952                 enum reg_class cl = recog_op_alt[opn][alt].cl;
 953
 954                 if (recog_data.operand_type[opn] == OP_OUT)
 955                   scan_rtx (insn, loc, cl, mark_write, OP_OUT,
 956                             recog_op_alt[opn][alt].earlyclobber);
 957               }
 958
 959           /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
 960              notes for update.  */
 961           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 962             if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
 963               scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
 964                         OP_INOUT, 0);
 965
 966           /* Step 7: Close chains for registers that were never
 967              really used here.  */
 968           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 969             if (REG_NOTE_KIND (note) == REG_UNUSED)
 970               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 971                         OP_IN, 0);
 972         }
 973       if (insn == BB_END (bb))
 974         break;
 975     }
 976
 977   /* Since we close every chain when we find a REG_DEAD note, anything that
 978      is still open lives past the basic block, so it can't be renamed.  */
 979   return closed_chains;
 980 }
 981
 982 /* Dump all def/use chains in CHAINS to DUMP_FILE.  They are
 983    printed in reverse order as that's how we build them.  */
 984
 985 static void
 986 dump_def_use_chain (struct du_chain *chains)
 987 {
 988   while (chains)
 989     {
 990       struct du_chain *this_du = chains;
 991       int r = REGNO (*this_du->loc);
 992       int nregs = hard_regno_nregs[r][GET_MODE (*this_du->loc)];
 993       fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs);
 994       while (this_du)
 995         {
 996           fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
 997                    reg_class_names[this_du->cl]);
 998           this_du = this_du->next_use;
 999         }
1000       fprintf (dump_file, "\n");
1001       chains = chains->next_chain;
1002     }
1003 }
1004
1005 \f
1006 static bool
1007 gate_handle_regrename (void)
1008 {
1009   return (optimize > 0 && (flag_rename_registers));
1010 }
1011
1012 struct rtl_opt_pass pass_regrename =
1013 {
1014  {
1015   RTL_PASS,
1016   "rnreg",                              /* name */
1017   gate_handle_regrename,                /* gate */
1018   regrename_optimize,                   /* execute */
1019   NULL,                                 /* sub */
1020   NULL,                                 /* next */
1021   0,                                    /* static_pass_number */
1022   TV_RENAME_REGISTERS,                  /* tv_id */
1023   0,                                    /* properties_required */
1024   0,                                    /* properties_provided */
1025   0,                                    /* properties_destroyed */
1026   0,                                    /* todo_flags_start */
1027   TODO_df_finish | TODO_verify_rtl_sharing |
1028   TODO_dump_func                        /* todo_flags_finish */
1029  }
1030 };
1031