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