gcc/regrename.c

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