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