gcc/regrename.c

   1 /* Register renaming for the GNU compiler.
   2    Copyright (C) 2000 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           SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM);
 223 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 224           SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM);
 225 #endif
 226         }
 227
 228       CLEAR_HARD_REG_SET (regs_seen);
 229       while (all_chains)
 230         {
 231           int new_reg, best_new_reg = -1;
 232           int n_uses;
 233           struct du_chain *this = all_chains;
 234           struct du_chain *tmp, *last;
 235           HARD_REG_SET this_unavailable;
 236           int reg = REGNO (*this->loc), treg;
 237           int nregs = HARD_REGNO_NREGS (reg, GET_MODE (*this->loc));
 238           int i;
 239
 240           all_chains = this->next_chain;
 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             continue;
 253
 254           COPY_HARD_REG_SET (this_unavailable, unavailable);
 255
 256           /* Find last entry on chain (which has the need_caller_save bit),
 257              count number of uses, and narrow the set of registers we can
 258              use for renaming.  */
 259           n_uses = 0;
 260           for (last = this; last->next_use; last = last->next_use)
 261             {
 262               n_uses++;
 263               IOR_COMPL_HARD_REG_SET (this_unavailable,
 264                                       reg_class_contents[last->class]);
 265             }
 266           if (n_uses < 1)
 267             continue;
 268
 269           IOR_COMPL_HARD_REG_SET (this_unavailable,
 270                                   reg_class_contents[last->class]);
 271
 272           if (this->need_caller_save_reg)
 273             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
 274
 275           merge_overlapping_regs (bb, &this_unavailable, this);
 276
 277           /* Now potential_regs is a reasonable approximation, let's
 278              have a closer look at each register still in there.  */
 279           for (treg = 0; treg < FIRST_PSEUDO_REGISTER; treg++)
 280             {
 281               new_reg = treg;
 282               for (i = nregs - 1; i >= 0; --i)
 283                 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
 284                     || fixed_regs[new_reg + i]
 285                     || global_regs[new_reg + i]
 286                     /* Can't use regs which aren't saved by the prologue.  */
 287                     || (! regs_ever_live[new_reg + i]
 288                         && ! call_used_regs[new_reg + i])
 289 #ifdef HARD_REGNO_RENAME_OK
 290                     || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
 291 #endif
 292                     )
 293                   break;
 294               if (i >= 0)
 295                 continue;
 296
 297               /* See whether it accepts all modes that occur in
 298                  definition and uses.  */
 299               for (tmp = this; tmp; tmp = tmp->next_use)
 300                 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)))
 301                   break;
 302               if (! tmp)
 303                 {
 304                   if (best_new_reg == -1
 305                       || tick[best_new_reg] > tick[new_reg])
 306                     best_new_reg = new_reg;
 307                 }
 308             }
 309
 310           if (rtl_dump_file)
 311             {
 312               fprintf (rtl_dump_file, "Register %s in insn %d",
 313                        reg_names[reg], INSN_UID (last->insn));
 314               if (last->need_caller_save_reg)
 315                 fprintf (rtl_dump_file, " crosses a call");
 316               }
 317
 318           if (best_new_reg == -1)
 319             {
 320               if (rtl_dump_file)
 321                 fprintf (rtl_dump_file, "; no available registers\n");
 322               continue;
 323             }
 324
 325           do_replace (this, best_new_reg);
 326           tick[best_new_reg] = this_tick++;
 327
 328           if (rtl_dump_file)
 329             fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
 330         }
 331
 332       obstack_free (&rename_obstack, first_obj);
 333     }
 334
 335   obstack_free (&rename_obstack, NULL);
 336
 337   if (rtl_dump_file)
 338     fputc ('\n', rtl_dump_file);
 339
 340   count_or_remove_death_notes (NULL, 1);
 341   update_life_info (NULL, UPDATE_LIFE_LOCAL,
 342                     PROP_REG_INFO | PROP_DEATH_NOTES);
 343 }
 344
 345 static void
 346 do_replace (chain, reg)
 347      struct du_chain *chain;
 348      int reg;
 349 {
 350   while (chain)
 351     {
 352       *chain->loc = gen_rtx_REG (GET_MODE (*chain->loc), reg);
 353       chain = chain->next_use;
 354     }
 355 }
 356
 357
 358 static struct du_chain *open_chains;
 359 static struct du_chain *closed_chains;
 360
 361 static void
 362 scan_rtx_reg (insn, loc, class, action, type, earlyclobber)
 363      rtx insn;
 364      rtx *loc;
 365      enum reg_class class;
 366      enum scan_actions action;
 367      enum op_type type;
 368      int earlyclobber;
 369 {
 370   struct du_chain **p;
 371   rtx x = *loc;
 372   enum machine_mode mode = GET_MODE (x);
 373   int this_regno = REGNO (x);
 374   int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
 375
 376   if (action == mark_write)
 377     {
 378       if (type == OP_OUT)
 379         {
 380           struct du_chain *this = (struct du_chain *)
 381             obstack_alloc (&rename_obstack, sizeof (struct du_chain));
 382           this->next_use = 0;
 383           this->next_chain = open_chains;
 384           this->loc = loc;
 385           this->insn = insn;
 386           this->class = class;
 387           this->need_caller_save_reg = 0;
 388           this->earlyclobber = earlyclobber;
 389           open_chains = this;
 390         }
 391       return;
 392     }
 393
 394   if ((type == OP_OUT && action != terminate_write)
 395       || (type != OP_OUT && action == terminate_write))
 396     return;
 397
 398   for (p = &open_chains; *p;)
 399     {
 400       struct du_chain *this = *p;
 401
 402       /* Check if the chain has been terminated if it has then skip to
 403          the next chain.
 404
 405          This can happen when we've already appended the location to
 406          the chain in Step 3, but are trying to hide in-out operands
 407          from terminate_write in Step 5.  */
 408
 409       if (*this->loc == cc0_rtx)
 410         p = &this->next_chain;
 411       else
 412         {
 413           int regno = REGNO (*this->loc);
 414           int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
 415           int exact_match = (regno == this_regno && nregs == this_nregs);
 416
 417           if (regno + nregs <= this_regno
 418               || this_regno + this_nregs <= regno)
 419             {
 420               p = &this->next_chain;
 421               continue;
 422             }
 423
 424           if (action == mark_read)
 425             {
 426               if (! exact_match)
 427                 abort ();
 428
 429               /* ??? Class NO_REGS can happen if the md file makes use of
 430                  EXTRA_CONSTRAINTS to match registers.  Which is arguably
 431                  wrong, but there we are.  Since we know not what this may
 432                  be replaced with, terminate the chain.  */
 433               if (class != NO_REGS)
 434                 {
 435                   this = (struct du_chain *)
 436                     obstack_alloc (&rename_obstack, sizeof (struct du_chain));
 437                   this->next_use = 0;
 438                   this->next_chain = (*p)->next_chain;
 439                   this->loc = loc;
 440                   this->insn = insn;
 441                   this->class = class;
 442                   this->need_caller_save_reg = 0;
 443                   while (*p)
 444                     p = &(*p)->next_use;
 445                   *p = this;
 446                   return;
 447                 }
 448             }
 449
 450           if (action != terminate_overlapping_read || ! exact_match)
 451             {
 452               struct du_chain *next = this->next_chain;
 453
 454               /* Whether the terminated chain can be used for renaming
 455                  depends on the action and this being an exact match.
 456                  In either case, we remove this element from open_chains.  */
 457
 458               if ((action == terminate_dead || action == terminate_write)
 459                   && exact_match)
 460                 {
 461                   this->next_chain = closed_chains;
 462                   closed_chains = this;
 463                   if (rtl_dump_file)
 464                     fprintf (rtl_dump_file,
 465                              "Closing chain %s at insn %d (%s)\n",
 466                              reg_names[REGNO (*this->loc)], INSN_UID (insn),
 467                              scan_actions_name[(int) action]);
 468                 }
 469               else
 470                 {
 471                   if (rtl_dump_file)
 472                     fprintf (rtl_dump_file,
 473                              "Discarding chain %s at insn %d (%s)\n",
 474                              reg_names[REGNO (*this->loc)], INSN_UID (insn),
 475                              scan_actions_name[(int) action]);
 476                 }
 477               *p = next;
 478             }
 479           else
 480             p = &this->next_chain;
 481         }
 482     }
 483 }
 484
 485 /* Adapted from find_reloads_address_1.  CLASS is INDEX_REG_CLASS or
 486    BASE_REG_CLASS depending on how the register is being considered.  */
 487
 488 static void
 489 scan_rtx_address (insn, loc, class, action, mode)
 490      rtx insn;
 491      rtx *loc;
 492      enum reg_class class;
 493      enum scan_actions action;
 494      enum machine_mode mode;
 495 {
 496   rtx x = *loc;
 497   RTX_CODE code = GET_CODE (x);
 498   const char *fmt;
 499   int i, j;
 500
 501   if (action == mark_write)
 502     return;
 503
 504   switch (code)
 505     {
 506     case PLUS:
 507       {
 508         rtx orig_op0 = XEXP (x, 0);
 509         rtx orig_op1 = XEXP (x, 1);
 510         RTX_CODE code0 = GET_CODE (orig_op0);
 511         RTX_CODE code1 = GET_CODE (orig_op1);
 512         rtx op0 = orig_op0;
 513         rtx op1 = orig_op1;
 514         rtx *locI = NULL;
 515         rtx *locB = NULL;
 516
 517         if (GET_CODE (op0) == SUBREG)
 518           {
 519             op0 = SUBREG_REG (op0);
 520             code0 = GET_CODE (op0);
 521           }
 522
 523         if (GET_CODE (op1) == SUBREG)
 524           {
 525             op1 = SUBREG_REG (op1);
 526             code1 = GET_CODE (op1);
 527           }
 528
 529         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
 530             || code0 == ZERO_EXTEND || code1 == MEM)
 531           {
 532             locI = &XEXP (x, 0);
 533             locB = &XEXP (x, 1);
 534           }
 535         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
 536                  || code1 == ZERO_EXTEND || code0 == MEM)
 537           {
 538             locI = &XEXP (x, 1);
 539             locB = &XEXP (x, 0);
 540           }
 541         else if (code0 == CONST_INT || code0 == CONST
 542                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
 543           locB = &XEXP (x, 1);
 544         else if (code1 == CONST_INT || code1 == CONST
 545                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
 546           locB = &XEXP (x, 0);
 547         else if (code0 == REG && code1 == REG)
 548           {
 549             int index_op;
 550
 551             if (REG_OK_FOR_INDEX_P (op0)
 552                 && REG_MODE_OK_FOR_BASE_P (op1, mode))
 553               index_op = 0;
 554             else if (REG_OK_FOR_INDEX_P (op1)
 555                      && REG_MODE_OK_FOR_BASE_P (op0, mode))
 556               index_op = 1;
 557             else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
 558               index_op = 0;
 559             else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
 560               index_op = 1;
 561             else if (REG_OK_FOR_INDEX_P (op1))
 562               index_op = 1;
 563             else
 564               index_op = 0;
 565
 566             locI = &XEXP (x, index_op);
 567             locB = &XEXP (x, !index_op);
 568           }
 569         else if (code0 == REG)
 570           {
 571             locI = &XEXP (x, 0);
 572             locB = &XEXP (x, 1);
 573           }
 574         else if (code1 == REG)
 575           {
 576             locI = &XEXP (x, 1);
 577             locB = &XEXP (x, 0);
 578           }
 579
 580         if (locI)
 581           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
 582         if (locB)
 583           scan_rtx_address (insn, locB, BASE_REG_CLASS, action, mode);
 584         return;
 585       }
 586
 587     case POST_INC:
 588     case POST_DEC:
 589     case POST_MODIFY:
 590     case PRE_INC:
 591     case PRE_DEC:
 592     case PRE_MODIFY:
 593 #ifndef AUTO_INC_DEC
 594       /* If the target doesn't claim to handle autoinc, this must be
 595          something special, like a stack push.  Kill this chain.  */
 596       action = terminate_all_read;
 597 #endif
 598       break;
 599
 600     case MEM:
 601       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 602                         GET_MODE (x));
 603       return;
 604
 605     case REG:
 606       scan_rtx_reg (insn, loc, class, action, OP_IN, 0);
 607       return;
 608
 609     default:
 610       break;
 611     }
 612
 613   fmt = GET_RTX_FORMAT (code);
 614   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 615     {
 616       if (fmt[i] == 'e')
 617         scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
 618       else if (fmt[i] == 'E')
 619         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 620           scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
 621     }
 622 }
 623
 624 static void
 625 scan_rtx (insn, loc, class, action, type, earlyclobber)
 626      rtx insn;
 627      rtx *loc;
 628      enum reg_class class;
 629      enum scan_actions action;
 630      enum op_type type;
 631      int earlyclobber;
 632 {
 633   const char *fmt;
 634   rtx x = *loc;
 635   enum rtx_code code = GET_CODE (x);
 636   int i, j;
 637
 638   code = GET_CODE (x);
 639   switch (code)
 640     {
 641     case CONST:
 642     case CONST_INT:
 643     case CONST_DOUBLE:
 644     case SYMBOL_REF:
 645     case LABEL_REF:
 646     case CC0:
 647     case PC:
 648       return;
 649
 650     case REG:
 651       scan_rtx_reg (insn, loc, class, action, type, earlyclobber);
 652       return;
 653
 654     case MEM:
 655       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 656                         GET_MODE (x));
 657       return;
 658
 659     case SET:
 660       scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0);
 661       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0);
 662       return;
 663
 664     case STRICT_LOW_PART:
 665       scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber);
 666       return;
 667
 668     case ZERO_EXTRACT:
 669     case SIGN_EXTRACT:
 670       scan_rtx (insn, &XEXP (x, 0), class, action,
 671                 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
 672       scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0);
 673       scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0);
 674       return;
 675
 676     case POST_INC:
 677     case PRE_INC:
 678     case POST_DEC:
 679     case PRE_DEC:
 680     case POST_MODIFY:
 681     case PRE_MODIFY:
 682       /* Should only happen inside MEM.  */
 683       abort ();
 684
 685     case CLOBBER:
 686       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1);
 687       return;
 688
 689     case EXPR_LIST:
 690       scan_rtx (insn, &XEXP (x, 0), class, action, type, 0);
 691       if (XEXP (x, 1))
 692         scan_rtx (insn, &XEXP (x, 1), class, action, type, 0);
 693       return;
 694
 695     default:
 696       break;
 697     }
 698
 699   fmt = GET_RTX_FORMAT (code);
 700   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 701     {
 702       if (fmt[i] == 'e')
 703         scan_rtx (insn, &XEXP (x, i), class, action, type, 0);
 704       else if (fmt[i] == 'E')
 705         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 706           scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0);
 707     }
 708 }
 709
 710 /* Build def/use chain */
 711
 712 static struct du_chain *
 713 build_def_use (bb)
 714      basic_block bb;
 715 {
 716   rtx insn;
 717
 718   open_chains = closed_chains = NULL;
 719
 720   for (insn = bb->head; ; insn = NEXT_INSN (insn))
 721     {
 722       if (INSN_P (insn))
 723         {
 724           int n_ops;
 725           rtx note;
 726           rtx old_operands[MAX_RECOG_OPERANDS];
 727           rtx old_dups[MAX_DUP_OPERANDS];
 728           int i;
 729           int alt;
 730           int predicated;
 731
 732           /* Process the insn, determining its effect on the def-use
 733              chains.  We perform the following steps with the register
 734              references in the insn:
 735              (1) Any read that overlaps an open chain, but doesn't exactly
 736                  match, causes that chain to be closed.  We can't deal
 737                  with overlaps yet.
 738              (2) Any read outside an operand causes any chain it overlaps
 739                  with to be closed, since we can't replace it.
 740              (3) Any read inside an operand is added if there's already
 741                  an open chain for it.
 742              (4) For any REG_DEAD note we find, close open chains that
 743                  overlap it.
 744              (5) For any write we find, close open chains that overlap it.
 745              (6) For any write we find in an operand, make a new chain.
 746              (7) For any REG_UNUSED, close any chains we just opened.  */
 747
 748           extract_insn (insn);
 749           constrain_operands (1);
 750           preprocess_constraints ();
 751           alt = which_alternative;
 752           n_ops = recog_data.n_operands;
 753
 754           /* Simplify the code below by rewriting things to reflect
 755              matching constraints.  Also promote OP_OUT to OP_INOUT
 756              in predicated instructions.  */
 757
 758           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 759           for (i = 0; i < n_ops; ++i)
 760             {
 761               int matches = recog_op_alt[i][alt].matches;
 762               if (matches >= 0)
 763                 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
 764               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 765                   || (predicated && recog_data.operand_type[i] == OP_OUT))
 766                 recog_data.operand_type[i] = OP_INOUT;
 767             }
 768
 769           /* Step 1: Close chains for which we have overlapping reads.  */
 770           for (i = 0; i < n_ops; i++)
 771             scan_rtx (insn, recog_data.operand_loc[i],
 772                       NO_REGS, terminate_overlapping_read,
 773                       recog_data.operand_type[i], 0);
 774
 775           /* Step 2: Close chains for which we have reads outside operands.
 776              We do this by munging all operands into CC0, and closing
 777              everything remaining.  */
 778
 779           for (i = 0; i < n_ops; i++)
 780             {
 781               old_operands[i] = recog_data.operand[i];
 782               /* Don't squash match_operator or match_parallel here, since
 783                  we don't know that all of the contained registers are
 784                  reachable by proper operands.  */
 785               if (recog_data.constraints[i][0] == '\0')
 786                 continue;
 787               *recog_data.operand_loc[i] = cc0_rtx;
 788             }
 789           for (i = 0; i < recog_data.n_dups; i++)
 790             {
 791               old_dups[i] = *recog_data.dup_loc[i];
 792               *recog_data.dup_loc[i] = cc0_rtx;
 793             }
 794
 795           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
 796                     OP_IN, 0);
 797
 798           for (i = 0; i < recog_data.n_dups; i++)
 799             *recog_data.dup_loc[i] = old_dups[i];
 800           for (i = 0; i < n_ops; i++)
 801             *recog_data.operand_loc[i] = old_operands[i];
 802
 803           /* Step 2B: Can't rename function call argument registers.  */
 804           if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
 805             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
 806                       NO_REGS, terminate_all_read, OP_IN, 0);
 807
 808           /* Step 3: Append to chains for reads inside operands.  */
 809           for (i = 0; i < n_ops + recog_data.n_dups; i++)
 810             {
 811               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 812               rtx *loc = (i < n_ops
 813                           ? recog_data.operand_loc[opn]
 814                           : recog_data.dup_loc[i - n_ops]);
 815               enum reg_class class = recog_op_alt[opn][alt].class;
 816               enum op_type type = recog_data.operand_type[opn];
 817
 818               /* Don't scan match_operand here, since we've no reg class
 819                  information to pass down.  Any operands that we could
 820                  substitute in will be represented elsewhere.  */
 821               if (recog_data.constraints[opn][0] == '\0')
 822                 continue;
 823
 824               if (recog_op_alt[opn][alt].is_address)
 825                 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
 826               else
 827                 scan_rtx (insn, loc, class, mark_read, type, 0);
 828             }
 829
 830           /* Step 4: Close chains for registers that die here.
 831              Also record updates for REG_INC notes.  */
 832           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 833             {
 834               if (REG_NOTE_KIND (note) == REG_DEAD)
 835                 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 836                           OP_IN, 0);
 837               else if (REG_NOTE_KIND (note) == REG_INC)
 838                 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
 839                           OP_INOUT, 0);
 840             }
 841
 842           /* Step 4B: If this is a call, any chain live at this point
 843              requires a caller-saved reg.  */
 844           if (GET_CODE (insn) == CALL_INSN)
 845             {
 846               struct du_chain *p;
 847               for (p = open_chains; p; p = p->next_chain)
 848                 p->need_caller_save_reg = 1;
 849             }
 850
 851           /* Step 5: Close open chains that overlap writes.  Similar to
 852              step 2, we hide in-out operands, since we do not want to
 853              close these chains.  */
 854
 855           for (i = 0; i < n_ops; i++)
 856             {
 857               old_operands[i] = recog_data.operand[i];
 858               if (recog_data.operand_type[i] == OP_INOUT)
 859                 *recog_data.operand_loc[i] = cc0_rtx;
 860             }
 861           for (i = 0; i < recog_data.n_dups; i++)
 862             {
 863               int opn = recog_data.dup_num[i];
 864               old_dups[i] = *recog_data.dup_loc[i];
 865               if (recog_data.operand_type[opn] == OP_INOUT)
 866                 *recog_data.dup_loc[i] = cc0_rtx;
 867             }
 868
 869           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
 870
 871           for (i = 0; i < recog_data.n_dups; i++)
 872             *recog_data.dup_loc[i] = old_dups[i];
 873           for (i = 0; i < n_ops; i++)
 874             *recog_data.operand_loc[i] = old_operands[i];
 875
 876           /* Step 6: Begin new chains for writes inside operands.  */
 877           /* ??? Many targets have output constraints on the SET_DEST
 878              of a call insn, which is stupid, since these are certainly
 879              ABI defined hard registers.  Don't change calls at all.  */
 880           if (GET_CODE (insn) != CALL_INSN)
 881             for (i = 0; i < n_ops + recog_data.n_dups; i++)
 882               {
 883                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 884                 rtx *loc = (i < n_ops
 885                             ? recog_data.operand_loc[opn]
 886                             : recog_data.dup_loc[i - n_ops]);
 887                 enum reg_class class = recog_op_alt[opn][alt].class;
 888
 889                 if (recog_data.operand_type[opn] == OP_OUT)
 890                   scan_rtx (insn, loc, class, mark_write, OP_OUT,
 891                             recog_op_alt[opn][alt].earlyclobber);
 892               }
 893
 894           /* Step 7: Close chains for registers that were never
 895              really used here.  */
 896           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 897             if (REG_NOTE_KIND (note) == REG_UNUSED)
 898               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
 899                         OP_IN, 0);
 900         }
 901       if (insn == bb->end)
 902         break;
 903     }
 904
 905   /* Since we close every chain when we find a REG_DEAD note, anything that
 906      is still open lives past the basic block, so it can't be renamed.  */
 907   return closed_chains;
 908 }
 909
 910 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE.  They are
 911    printed in reverse order as that's how we build them.  */
 912
 913 static void
 914 dump_def_use_chain (chains)
 915      struct du_chain *chains;
 916 {
 917   while (chains)
 918     {
 919       struct du_chain *this = chains;
 920       int r = REGNO (*this->loc);
 921       int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
 922       fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
 923       while (this)
 924         {
 925           fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
 926                    reg_class_names[this->class]);
 927           this = this->next_use;
 928         }
 929       fprintf (rtl_dump_file, "\n");
 930       chains = chains->next_chain;
 931     }
 932 }