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