gcc/regrename.c

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