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 };
  61
  62 enum scan_actions
  63 {
  64   note_reference,
  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   "note_reference",
  76   "terminate_all_read",
  77   "terminate_overlapping_read",
  78   "terminate_write",
  79   "terminate_dead",
  80   "mark_read",
  81   "mark_write"
  82 };
  83
  84 static struct obstack rename_obstack;
  85
  86 static void do_replace PARAMS ((struct du_chain *, int));
  87 static void scan_rtx_reg PARAMS ((rtx, rtx *, enum reg_class,
  88                                   enum scan_actions, enum op_type));
  89 static void scan_rtx_address PARAMS ((rtx, rtx *, enum reg_class,
  90                                       enum scan_actions, enum machine_mode));
  91 static void scan_rtx PARAMS ((rtx, rtx *, enum reg_class,
  92                               enum scan_actions, enum op_type));
  93 static struct du_chain *build_def_use PARAMS ((basic_block, HARD_REG_SET *));
  94 static void dump_def_use_chain PARAMS ((struct du_chain *));
  95
  96 void
  97 regrename_optimize ()
  98 {
  99   int b;
 100   char *first_obj;
 101
 102   gcc_obstack_init (&rename_obstack);
 103   first_obj = (char *) obstack_alloc (&rename_obstack, 0);
 104
 105   for (b = 0; b < n_basic_blocks; b++)
 106     {
 107       basic_block bb = BASIC_BLOCK (b);
 108       struct du_chain *all_chains = 0;
 109       HARD_REG_SET regs_used;
 110       HARD_REG_SET unavailable;
 111       HARD_REG_SET regs_seen;
 112
 113       CLEAR_HARD_REG_SET (regs_used);
 114       CLEAR_HARD_REG_SET (unavailable);
 115
 116       if (rtl_dump_file)
 117         fprintf (rtl_dump_file, "\nBasic block %d:\n", b);
 118
 119       all_chains = build_def_use (bb, &regs_used);
 120
 121       if (rtl_dump_file)
 122         dump_def_use_chain (all_chains);
 123
 124       /* Available registers are not: used in the block, live at the start
 125          live at the end, a register we've renamed to. */
 126       REG_SET_TO_HARD_REG_SET (unavailable, bb->global_live_at_start);
 127       REG_SET_TO_HARD_REG_SET (regs_seen, bb->global_live_at_end);
 128       IOR_HARD_REG_SET (unavailable, regs_seen);
 129       IOR_HARD_REG_SET (unavailable, regs_used);
 130
 131       /* Don't clobber traceback for noreturn functions.  */
 132       if (frame_pointer_needed)
 133         {
 134           SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM);
 135 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
 136           SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM);
 137 #endif
 138         }
 139
 140       CLEAR_HARD_REG_SET (regs_seen);
 141       while (all_chains)
 142         {
 143           int n_uses;
 144           struct du_chain *this = all_chains;
 145           struct du_chain *tmp, *last;
 146           HARD_REG_SET this_unavailable;
 147           int reg = REGNO (*this->loc), treg;
 148           int nregs = HARD_REGNO_NREGS (reg, GET_MODE (*this->loc));
 149           int i;
 150
 151           all_chains = this->next_chain;
 152
 153           /* Only rename once we've seen the reg more than once.  */
 154           if (! TEST_HARD_REG_BIT (regs_seen, reg))
 155             {
 156               SET_HARD_REG_BIT (regs_seen, reg);
 157               continue;
 158             }
 159
 160           if (fixed_regs[reg] || global_regs[reg])
 161             continue;
 162
 163           COPY_HARD_REG_SET (this_unavailable, unavailable);
 164
 165           /* Find last entry on chain (which has the need_caller_save bit),
 166              count number of uses, and narrow the set of registers we can
 167              use for renaming.  */
 168           n_uses = 0;
 169           for (last = this; last->next_use; last = last->next_use)
 170             {
 171               n_uses++;
 172               IOR_COMPL_HARD_REG_SET (this_unavailable,
 173                                       reg_class_contents[last->class]);
 174             }
 175           if (n_uses < 1)
 176             continue;
 177
 178           IOR_COMPL_HARD_REG_SET (this_unavailable,
 179                                   reg_class_contents[last->class]);
 180
 181           if (last->need_caller_save_reg)
 182             IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
 183
 184           /* Now potential_regs is a reasonable approximation, let's
 185              have a closer look at each register still in there.  */
 186           for (treg = 0; treg < FIRST_PSEUDO_REGISTER; treg++)
 187             {
 188               for (i = nregs - 1; i >= 0; --i)
 189                 if (TEST_HARD_REG_BIT (this_unavailable, treg+i)
 190                     || fixed_regs[treg+i]
 191                     || global_regs[treg+i]
 192                     /* Can't use regs which aren't saved by the prologue.  */
 193                     || (! regs_ever_live[treg+i] && ! call_used_regs[treg+i])
 194 #ifdef HARD_REGNO_RENAME_OK
 195                     || ! HARD_REGNO_RENAME_OK (reg+i, treg+i)
 196 #endif
 197                     )
 198                   break;
 199               if (i >= 0)
 200                 continue;
 201
 202               /* See whether it accepts all modes that occur in
 203                  definition and uses.  */
 204               for (tmp = this; tmp; tmp = tmp->next_use)
 205                 if (! HARD_REGNO_MODE_OK (treg, GET_MODE (*tmp->loc)))
 206                   break;
 207               if (! tmp)
 208                 break;
 209             }
 210
 211           if (rtl_dump_file)
 212             {
 213               fprintf (rtl_dump_file, "Register %s in insn %d",
 214                        reg_names[reg], INSN_UID (last->insn));
 215               if (last->need_caller_save_reg)
 216                 fprintf (rtl_dump_file, " crosses a call");
 217               }
 218
 219           if (treg == FIRST_PSEUDO_REGISTER)
 220             {
 221               if (rtl_dump_file)
 222                 fprintf (rtl_dump_file, "; no available registers\n");
 223               continue;
 224             }
 225
 226
 227           for (i = nregs - 1; i >= 0; --i)
 228             SET_HARD_REG_BIT (unavailable, treg+i);
 229           do_replace (this, treg);
 230
 231           if (rtl_dump_file)
 232             fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[treg]);
 233         }
 234
 235       obstack_free (&rename_obstack, first_obj);
 236     }
 237
 238   obstack_free (&rename_obstack, NULL);
 239
 240   if (rtl_dump_file)
 241     fputc ('\n', rtl_dump_file);
 242
 243   count_or_remove_death_notes (NULL, 1);
 244   update_life_info (NULL, UPDATE_LIFE_LOCAL,
 245                     PROP_REG_INFO | PROP_DEATH_NOTES);
 246 }
 247
 248 static void
 249 do_replace (chain, reg)
 250      struct du_chain *chain;
 251      int reg;
 252 {
 253   while (chain)
 254     {
 255       *chain->loc = gen_rtx_REG (GET_MODE (*chain->loc), reg);
 256       chain = chain->next_use;
 257     }
 258 }
 259
 260
 261 static HARD_REG_SET *referenced_regs;
 262 static struct du_chain *open_chains;
 263 static struct du_chain *closed_chains;
 264
 265 static void
 266 scan_rtx_reg (insn, loc, class, action, type)
 267      rtx insn;
 268      rtx *loc;
 269      enum reg_class class;
 270      enum scan_actions action;
 271      enum op_type type;
 272 {
 273   struct du_chain **p;
 274   rtx x = *loc;
 275   enum machine_mode mode = GET_MODE (x);
 276   int this_regno = REGNO (x);
 277   int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
 278
 279   if (action == note_reference)
 280     {
 281       while (this_nregs-- > 0)
 282         SET_HARD_REG_BIT (*referenced_regs, this_regno + this_nregs);
 283       return;
 284     }
 285
 286   if (action == mark_write)
 287     {
 288       if (type == OP_OUT)
 289         {
 290           struct du_chain *this = (struct du_chain *)
 291             obstack_alloc (&rename_obstack, sizeof (struct du_chain));
 292           this->next_use = 0;
 293           this->next_chain = open_chains;
 294           this->loc = loc;
 295           this->insn = insn;
 296           this->class = class;
 297           this->need_caller_save_reg = 0;
 298           open_chains = this;
 299         }
 300       return;
 301     }
 302
 303   if ((type == OP_OUT && action != terminate_write)
 304       || (type != OP_OUT && action == terminate_write))
 305     return;
 306
 307   for (p = &open_chains; *p;)
 308     {
 309       struct du_chain *this = *p;
 310       int regno = REGNO (*this->loc);
 311       int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
 312       int exact_match = (regno == this_regno && nregs == this_nregs);
 313
 314       if (regno + nregs <= this_regno
 315           || this_regno + this_nregs <= regno)
 316         p = &this->next_chain;
 317       else if (action == mark_read)
 318         {
 319           if (! exact_match)
 320             abort ();
 321           if (class == NO_REGS)
 322             abort ();
 323
 324           this = (struct du_chain *)
 325             obstack_alloc (&rename_obstack, sizeof (struct du_chain));
 326           this->next_use = *p;
 327           this->next_chain = (*p)->next_chain;
 328           this->loc = loc;
 329           this->insn = insn;
 330           this->class = class;
 331           this->need_caller_save_reg = 0;
 332           *p = this;
 333           return;
 334         }
 335       else if (action != terminate_overlapping_read || ! exact_match)
 336         {
 337           struct du_chain *next = this->next_chain;
 338
 339           /* Whether the terminated chain can be used for renaming
 340              depends on the action and this being an exact match.
 341              In either case, we remove this element from open_chains.  */
 342
 343           if ((action == terminate_dead || action == terminate_write)
 344               && exact_match)
 345             {
 346               this->next_chain = closed_chains;
 347               closed_chains = this;
 348               if (rtl_dump_file)
 349                 fprintf (rtl_dump_file,
 350                          "Closing chain %s at insn %d (%s)\n",
 351                          reg_names[REGNO (*this->loc)], INSN_UID (insn),
 352                          scan_actions_name[(int) action]);
 353             }
 354           else
 355             {
 356               if (rtl_dump_file)
 357                 fprintf (rtl_dump_file,
 358                          "Discarding chain %s at insn %d (%s)\n",
 359                          reg_names[REGNO (*this->loc)], INSN_UID (insn),
 360                          scan_actions_name[(int) action]);
 361             }
 362           *p = next;
 363         }
 364       else
 365         p = &this->next_chain;
 366     }
 367 }
 368
 369 /* Adapted from find_reloads_address_1.  CLASS is INDEX_REG_CLASS or
 370    BASE_REG_CLASS depending on how the register is being considered.  */
 371
 372 static void
 373 scan_rtx_address (insn, loc, class, action, mode)
 374      rtx insn;
 375      rtx *loc;
 376      enum reg_class class;
 377      enum scan_actions action;
 378      enum machine_mode mode;
 379 {
 380   rtx x = *loc;
 381   RTX_CODE code = GET_CODE (x);
 382   const char *fmt;
 383   int i, j;
 384
 385   if (action == mark_write)
 386     return;
 387
 388   switch (code)
 389     {
 390     case PLUS:
 391       {
 392         rtx orig_op0 = XEXP (x, 0);
 393         rtx orig_op1 = XEXP (x, 1);
 394         RTX_CODE code0 = GET_CODE (orig_op0);
 395         RTX_CODE code1 = GET_CODE (orig_op1);
 396         rtx op0 = orig_op0;
 397         rtx op1 = orig_op1;
 398         rtx *locI = NULL;
 399         rtx *locB = NULL;
 400
 401         if (GET_CODE (op0) == SUBREG)
 402           {
 403             op0 = SUBREG_REG (op0);
 404             code0 = GET_CODE (op0);
 405           }
 406
 407         if (GET_CODE (op1) == SUBREG)
 408           {
 409             op1 = SUBREG_REG (op1);
 410             code1 = GET_CODE (op1);
 411           }
 412
 413         if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
 414             || code0 == ZERO_EXTEND || code1 == MEM)
 415           {
 416             locI = &XEXP (x, 0);
 417             locB = &XEXP (x, 1);
 418           }
 419         else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
 420                  || code1 == ZERO_EXTEND || code0 == MEM)
 421           {
 422             locI = &XEXP (x, 1);
 423             locB = &XEXP (x, 0);
 424           }
 425         else if (code0 == CONST_INT || code0 == CONST
 426                  || code0 == SYMBOL_REF || code0 == LABEL_REF)
 427           locB = &XEXP (x, 1);
 428         else if (code1 == CONST_INT || code1 == CONST
 429                  || code1 == SYMBOL_REF || code1 == LABEL_REF)
 430           locB = &XEXP (x, 0);
 431         else if (code0 == REG && code1 == REG)
 432           {
 433             int index_op;
 434
 435             if (REG_OK_FOR_INDEX_P (op0)
 436                 && REG_MODE_OK_FOR_BASE_P (op1, mode))
 437               index_op = 0;
 438             else if (REG_OK_FOR_INDEX_P (op1)
 439                      && REG_MODE_OK_FOR_BASE_P (op0, mode))
 440               index_op = 1;
 441             else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
 442               index_op = 0;
 443             else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
 444               index_op = 1;
 445             else if (REG_OK_FOR_INDEX_P (op1))
 446               index_op = 1;
 447             else
 448               index_op = 0;
 449
 450             locI = &XEXP (x, index_op);
 451             locB = &XEXP (x, !index_op);
 452           }
 453         else if (code0 == REG)
 454           {
 455             locI = &XEXP (x, 0);
 456             locB = &XEXP (x, 1);
 457           }
 458         else if (code1 == REG)
 459           {
 460             locI = &XEXP (x, 1);
 461             locB = &XEXP (x, 0);
 462           }
 463
 464         if (locI)
 465           scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
 466         if (locB)
 467           scan_rtx_address (insn, locB, BASE_REG_CLASS, action, mode);
 468         return;
 469       }
 470
 471     case POST_INC:
 472     case POST_DEC:
 473     case POST_MODIFY:
 474     case PRE_INC:
 475     case PRE_DEC:
 476     case PRE_MODIFY:
 477 #ifndef AUTO_INC_DEC
 478       class = NO_REGS;
 479 #endif
 480       break;
 481
 482     case MEM:
 483       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 484                         GET_MODE (x));
 485       return;
 486
 487     case REG:
 488       scan_rtx_reg (insn, loc, class, action, OP_IN);
 489       return;
 490
 491     default:
 492       break;
 493     }
 494
 495   fmt = GET_RTX_FORMAT (code);
 496   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 497     {
 498       if (fmt[i] == 'e')
 499         scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
 500       else if (fmt[i] == 'E')
 501         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 502           scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
 503     }
 504 }
 505
 506 static void
 507 scan_rtx (insn, loc, class, action, type)
 508      rtx insn;
 509      rtx *loc;
 510      enum reg_class class;
 511      enum scan_actions action;
 512      enum op_type type;
 513 {
 514   const char *fmt;
 515   rtx x = *loc;
 516   enum rtx_code code = GET_CODE (x);
 517   int i, j;
 518
 519   code = GET_CODE (x);
 520   switch (code)
 521     {
 522     case CONST:
 523     case CONST_INT:
 524     case CONST_DOUBLE:
 525     case SYMBOL_REF:
 526     case LABEL_REF:
 527     case CC0:
 528     case PC:
 529       return;
 530
 531     case REG:
 532       scan_rtx_reg (insn, loc, class, action, type);
 533       return;
 534
 535     case MEM:
 536       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 537                         GET_MODE (x));
 538       return;
 539
 540     case SET:
 541       scan_rtx (insn, &SET_SRC (x), class, action, OP_IN);
 542       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
 543       return;
 544
 545     case STRICT_LOW_PART:
 546       scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT);
 547       return;
 548
 549     case ZERO_EXTRACT:
 550     case SIGN_EXTRACT:
 551       scan_rtx (insn, &XEXP (x, 0), class, action,
 552                 type == OP_IN ? OP_IN : OP_INOUT);
 553       scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN);
 554       scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN);
 555       return;
 556
 557     case POST_INC:
 558     case PRE_INC:
 559     case POST_DEC:
 560     case PRE_DEC:
 561     case POST_MODIFY:
 562     case PRE_MODIFY:
 563       /* Should only happen inside MEM.  */
 564       abort ();
 565
 566     case CLOBBER:
 567       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
 568       return;
 569
 570     case EXPR_LIST:
 571       scan_rtx (insn, &XEXP (x, 0), class, action, type);
 572       if (XEXP (x, 1))
 573         scan_rtx (insn, &XEXP (x, 1), class, action, type);
 574       return;
 575
 576     default:
 577       break;
 578     }
 579
 580   fmt = GET_RTX_FORMAT (code);
 581   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 582     {
 583       if (fmt[i] == 'e')
 584         scan_rtx (insn, &XEXP (x, i), class, action, type);
 585       else if (fmt[i] == 'E')
 586         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 587           scan_rtx (insn, &XVECEXP (x, i, j), class, action, type);
 588     }
 589 }
 590
 591 /* Build def/use chain */
 592
 593 static struct du_chain *
 594 build_def_use (bb, regs_used)
 595      basic_block bb;
 596      HARD_REG_SET *regs_used;
 597 {
 598   rtx insn;
 599
 600   open_chains = closed_chains = NULL;
 601   referenced_regs = regs_used;
 602
 603   for (insn = bb->head; ; insn = NEXT_INSN (insn))
 604     {
 605       if (INSN_P (insn))
 606         {
 607           int n_ops;
 608           rtx note;
 609           rtx old_operands[MAX_RECOG_OPERANDS];
 610           rtx old_dups[MAX_DUP_OPERANDS];
 611           int i;
 612           int alt;
 613           int predicated;
 614
 615           /* Record all mentioned registers in regs_used.  */
 616           scan_rtx (insn, &PATTERN (insn), NO_REGS, note_reference, OP_IN);
 617
 618           /* Process the insn, determining its effect on the def-use
 619              chains.  We perform the following steps with the register
 620              references in the insn:
 621              (1) Any read that overlaps an open chain, but doesn't exactly
 622                  match, causes that chain to be closed.  We can't deal
 623                  with overlaps yet.
 624              (2) Any read outside an operand causes any chain it overlaps
 625                  with to be closed, since we can't replace it.
 626              (3) Any read inside an operand is added if there's already
 627                  an open chain for it.
 628              (4) For any REG_DEAD note we find, close open chains that
 629                  overlap it.
 630              (5) For any write we find, close open chains that overlap it.
 631              (6) For any write we find in an operand, make a new chain.
 632              (7) For any REG_UNUSED, close any chains we just opened.  */
 633
 634           extract_insn (insn);
 635           constrain_operands (1);
 636           preprocess_constraints ();
 637           alt = which_alternative;
 638           n_ops = recog_data.n_operands;
 639
 640           /* Simplify the code below by rewriting things to reflect
 641              matching constraints.  Also promote OP_OUT to OP_INOUT
 642              in predicated instructions.  */
 643
 644           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 645           for (i = 0; i < n_ops; ++i)
 646             {
 647               int matches = recog_op_alt[i][alt].matches;
 648               if (matches >= 0)
 649                 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
 650               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 651                   || (predicated && recog_data.operand_type[i] == OP_OUT))
 652                 recog_data.operand_type[i] = OP_INOUT;
 653             }
 654
 655           /* Step 1: Close chains for which we have overlapping reads.  */
 656           for (i = 0; i < n_ops; i++)
 657             scan_rtx (insn, recog_data.operand_loc[i],
 658                       NO_REGS, terminate_overlapping_read,
 659                       recog_data.operand_type[i]);
 660
 661           /* Step 2: Close chains for which we have reads outside operands.
 662              We do this by munging all operands into CC0, and closing
 663              everything remaining.  */
 664
 665           for (i = 0; i < n_ops; i++)
 666             {
 667               old_operands[i] = recog_data.operand[i];
 668               /* Don't squash match_operator or match_parallel here, since
 669                  we don't know that all of the contained registers are
 670                  reachable by proper operands.  */
 671               if (recog_data.constraints[i][0] == '\0')
 672                 continue;
 673               *recog_data.operand_loc[i] = cc0_rtx;
 674             }
 675           for (i = 0; i < recog_data.n_dups; i++)
 676             {
 677               old_dups[i] = *recog_data.dup_loc[i];
 678               *recog_data.dup_loc[i] = cc0_rtx;
 679             }
 680
 681           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, OP_IN);
 682
 683           for (i = 0; i < recog_data.n_dups; i++)
 684             *recog_data.dup_loc[i] = old_dups[i];
 685           for (i = 0; i < n_ops; i++)
 686             *recog_data.operand_loc[i] = old_operands[i];
 687
 688           /* Step 2B: Can't rename function call argument registers.  */
 689           if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
 690             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
 691                       NO_REGS, terminate_all_read, OP_IN);
 692
 693           /* Step 3: Append to chains for reads inside operands.  */
 694           for (i = 0; i < n_ops + recog_data.n_dups; i++)
 695             {
 696               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 697               rtx *loc = (i < n_ops
 698                           ? recog_data.operand_loc[opn]
 699                           : recog_data.dup_loc[i - n_ops]);
 700               enum reg_class class = recog_op_alt[opn][alt].class;
 701               enum op_type type = recog_data.operand_type[opn];
 702
 703               /* Don't scan match_operand here, since we've no reg class
 704                  information to pass down.  Any operands that we could
 705                  substitute in will be represented elsewhere.  */
 706               if (recog_data.constraints[opn][0] == '\0')
 707                 continue;
 708
 709               if (recog_op_alt[opn][alt].is_address)
 710                 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
 711               else
 712                 scan_rtx (insn, loc, class, mark_read, type);
 713             }
 714
 715           /* Step 4: Close chains for registers that die here.  */
 716           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 717             if (REG_NOTE_KIND (note) == REG_DEAD)
 718               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
 719
 720           /* Step 4B: If this is a call, any chain live at this point
 721              requires a caller-saved reg.  */
 722           if (GET_CODE (insn) == CALL_INSN)
 723             {
 724               struct du_chain *p;
 725               for (p = open_chains; p; p = p->next_chain)
 726                 {
 727                   struct du_chain *p2;
 728                   for (p2 = p; p2->next_use; p2 = p2->next_use)
 729                     /* nothing */;
 730                   p2->need_caller_save_reg = 1;
 731                 }
 732             }
 733
 734           /* Step 5: Close open chains that overlap writes.  Similar to
 735              step 2, we hide in-out operands, since we do not want to
 736              close these chains.  */
 737
 738           for (i = 0; i < n_ops; i++)
 739             {
 740               old_operands[i] = recog_data.operand[i];
 741               if (recog_data.operand_type[i] == OP_INOUT)
 742                 *recog_data.operand_loc[i] = cc0_rtx;
 743             }
 744           for (i = 0; i < recog_data.n_dups; i++)
 745             {
 746               int opn = recog_data.dup_num[i];
 747               old_dups[i] = *recog_data.dup_loc[i];
 748               if (recog_data.operand_type[opn] == OP_INOUT)
 749                 *recog_data.dup_loc[i] = cc0_rtx;
 750             }
 751
 752           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
 753
 754           for (i = 0; i < recog_data.n_dups; i++)
 755             *recog_data.dup_loc[i] = old_dups[i];
 756           for (i = 0; i < n_ops; i++)
 757             *recog_data.operand_loc[i] = old_operands[i];
 758
 759           /* Step 6: Begin new chains for writes inside operands.  */
 760           /* ??? Many targets have output constraints on the SET_DEST
 761              of a call insn, which is stupid, since these are certainly
 762              ABI defined hard registers.  Don't change calls at all.  */
 763           if (GET_CODE (insn) != CALL_INSN)
 764             for (i = 0; i < n_ops + recog_data.n_dups; i++)
 765               {
 766                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 767                 rtx *loc = (i < n_ops
 768                             ? recog_data.operand_loc[opn]
 769                             : recog_data.dup_loc[i - n_ops]);
 770                 enum reg_class class = recog_op_alt[opn][alt].class;
 771
 772                 if (recog_data.operand_type[opn] == OP_OUT)
 773                   scan_rtx (insn, loc, class, mark_write, OP_OUT);
 774               }
 775
 776           /* Step 7: Close chains for registers that were never
 777              really used here.  */
 778           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 779             if (REG_NOTE_KIND (note) == REG_UNUSED)
 780               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
 781         }
 782       if (insn == bb->end)
 783         break;
 784     }
 785
 786   /* Since we close every chain when we find a REG_DEAD note, anything that
 787      is still open lives past the basic block, so it can't be renamed.  */
 788   return closed_chains;
 789 }
 790
 791 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE.  They are
 792    printed in reverse order as that's how we build them.  */
 793
 794 static void
 795 dump_def_use_chain (chains)
 796      struct du_chain *chains;
 797 {
 798   while (chains)
 799     {
 800       struct du_chain *this = chains;
 801       int r = REGNO (*this->loc);
 802       int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
 803       fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
 804       while (this)
 805         {
 806           fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
 807                    reg_class_names[this->class]);
 808           this = this->next_use;
 809         }
 810       fprintf (rtl_dump_file, "\n");
 811       chains = chains->next_chain;
 812     }
 813 }