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