gcc/regrename.c

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