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       /* If the target doesn't claim to handle autoinc, this must be
 479          something special, like a stack push.  Kill this chain.  */
 480       action = terminate_all_read;
 481 #endif
 482       break;
 483
 484     case MEM:
 485       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 486                         GET_MODE (x));
 487       return;
 488
 489     case REG:
 490       scan_rtx_reg (insn, loc, class, action, OP_IN);
 491       return;
 492
 493     default:
 494       break;
 495     }
 496
 497   fmt = GET_RTX_FORMAT (code);
 498   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 499     {
 500       if (fmt[i] == 'e')
 501         scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
 502       else if (fmt[i] == 'E')
 503         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 504           scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
 505     }
 506 }
 507
 508 static void
 509 scan_rtx (insn, loc, class, action, type)
 510      rtx insn;
 511      rtx *loc;
 512      enum reg_class class;
 513      enum scan_actions action;
 514      enum op_type type;
 515 {
 516   const char *fmt;
 517   rtx x = *loc;
 518   enum rtx_code code = GET_CODE (x);
 519   int i, j;
 520
 521   code = GET_CODE (x);
 522   switch (code)
 523     {
 524     case CONST:
 525     case CONST_INT:
 526     case CONST_DOUBLE:
 527     case SYMBOL_REF:
 528     case LABEL_REF:
 529     case CC0:
 530     case PC:
 531       return;
 532
 533     case REG:
 534       scan_rtx_reg (insn, loc, class, action, type);
 535       return;
 536
 537     case MEM:
 538       scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
 539                         GET_MODE (x));
 540       return;
 541
 542     case SET:
 543       scan_rtx (insn, &SET_SRC (x), class, action, OP_IN);
 544       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
 545       return;
 546
 547     case STRICT_LOW_PART:
 548       scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT);
 549       return;
 550
 551     case ZERO_EXTRACT:
 552     case SIGN_EXTRACT:
 553       scan_rtx (insn, &XEXP (x, 0), class, action,
 554                 type == OP_IN ? OP_IN : OP_INOUT);
 555       scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN);
 556       scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN);
 557       return;
 558
 559     case POST_INC:
 560     case PRE_INC:
 561     case POST_DEC:
 562     case PRE_DEC:
 563     case POST_MODIFY:
 564     case PRE_MODIFY:
 565       /* Should only happen inside MEM.  */
 566       abort ();
 567
 568     case CLOBBER:
 569       scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
 570       return;
 571
 572     case EXPR_LIST:
 573       scan_rtx (insn, &XEXP (x, 0), class, action, type);
 574       if (XEXP (x, 1))
 575         scan_rtx (insn, &XEXP (x, 1), class, action, type);
 576       return;
 577
 578     default:
 579       break;
 580     }
 581
 582   fmt = GET_RTX_FORMAT (code);
 583   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 584     {
 585       if (fmt[i] == 'e')
 586         scan_rtx (insn, &XEXP (x, i), class, action, type);
 587       else if (fmt[i] == 'E')
 588         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 589           scan_rtx (insn, &XVECEXP (x, i, j), class, action, type);
 590     }
 591 }
 592
 593 /* Build def/use chain */
 594
 595 static struct du_chain *
 596 build_def_use (bb, regs_used)
 597      basic_block bb;
 598      HARD_REG_SET *regs_used;
 599 {
 600   rtx insn;
 601
 602   open_chains = closed_chains = NULL;
 603   referenced_regs = regs_used;
 604
 605   for (insn = bb->head; ; insn = NEXT_INSN (insn))
 606     {
 607       if (INSN_P (insn))
 608         {
 609           int n_ops;
 610           rtx note;
 611           rtx old_operands[MAX_RECOG_OPERANDS];
 612           rtx old_dups[MAX_DUP_OPERANDS];
 613           int i;
 614           int alt;
 615           int predicated;
 616
 617           /* Record all mentioned registers in regs_used.  */
 618           scan_rtx (insn, &PATTERN (insn), NO_REGS, note_reference, OP_IN);
 619
 620           /* Process the insn, determining its effect on the def-use
 621              chains.  We perform the following steps with the register
 622              references in the insn:
 623              (1) Any read that overlaps an open chain, but doesn't exactly
 624                  match, causes that chain to be closed.  We can't deal
 625                  with overlaps yet.
 626              (2) Any read outside an operand causes any chain it overlaps
 627                  with to be closed, since we can't replace it.
 628              (3) Any read inside an operand is added if there's already
 629                  an open chain for it.
 630              (4) For any REG_DEAD note we find, close open chains that
 631                  overlap it.
 632              (5) For any write we find, close open chains that overlap it.
 633              (6) For any write we find in an operand, make a new chain.
 634              (7) For any REG_UNUSED, close any chains we just opened.  */
 635
 636           extract_insn (insn);
 637           constrain_operands (1);
 638           preprocess_constraints ();
 639           alt = which_alternative;
 640           n_ops = recog_data.n_operands;
 641
 642           /* Simplify the code below by rewriting things to reflect
 643              matching constraints.  Also promote OP_OUT to OP_INOUT
 644              in predicated instructions.  */
 645
 646           predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
 647           for (i = 0; i < n_ops; ++i)
 648             {
 649               int matches = recog_op_alt[i][alt].matches;
 650               if (matches >= 0)
 651                 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
 652               if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
 653                   || (predicated && recog_data.operand_type[i] == OP_OUT))
 654                 recog_data.operand_type[i] = OP_INOUT;
 655             }
 656
 657           /* Step 1: Close chains for which we have overlapping reads.  */
 658           for (i = 0; i < n_ops; i++)
 659             scan_rtx (insn, recog_data.operand_loc[i],
 660                       NO_REGS, terminate_overlapping_read,
 661                       recog_data.operand_type[i]);
 662
 663           /* Step 2: Close chains for which we have reads outside operands.
 664              We do this by munging all operands into CC0, and closing
 665              everything remaining.  */
 666
 667           for (i = 0; i < n_ops; i++)
 668             {
 669               old_operands[i] = recog_data.operand[i];
 670               /* Don't squash match_operator or match_parallel here, since
 671                  we don't know that all of the contained registers are
 672                  reachable by proper operands.  */
 673               if (recog_data.constraints[i][0] == '\0')
 674                 continue;
 675               *recog_data.operand_loc[i] = cc0_rtx;
 676             }
 677           for (i = 0; i < recog_data.n_dups; i++)
 678             {
 679               old_dups[i] = *recog_data.dup_loc[i];
 680               *recog_data.dup_loc[i] = cc0_rtx;
 681             }
 682
 683           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, OP_IN);
 684
 685           for (i = 0; i < recog_data.n_dups; i++)
 686             *recog_data.dup_loc[i] = old_dups[i];
 687           for (i = 0; i < n_ops; i++)
 688             *recog_data.operand_loc[i] = old_operands[i];
 689
 690           /* Step 2B: Can't rename function call argument registers.  */
 691           if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
 692             scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
 693                       NO_REGS, terminate_all_read, OP_IN);
 694
 695           /* Step 3: Append to chains for reads inside operands.  */
 696           for (i = 0; i < n_ops + recog_data.n_dups; i++)
 697             {
 698               int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 699               rtx *loc = (i < n_ops
 700                           ? recog_data.operand_loc[opn]
 701                           : recog_data.dup_loc[i - n_ops]);
 702               enum reg_class class = recog_op_alt[opn][alt].class;
 703               enum op_type type = recog_data.operand_type[opn];
 704
 705               /* Don't scan match_operand here, since we've no reg class
 706                  information to pass down.  Any operands that we could
 707                  substitute in will be represented elsewhere.  */
 708               if (recog_data.constraints[opn][0] == '\0')
 709                 continue;
 710
 711               if (recog_op_alt[opn][alt].is_address)
 712                 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
 713               else
 714                 scan_rtx (insn, loc, class, mark_read, type);
 715             }
 716
 717           /* Step 4: Close chains for registers that die here.  */
 718           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 719             if (REG_NOTE_KIND (note) == REG_DEAD)
 720               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
 721
 722           /* Step 4B: If this is a call, any chain live at this point
 723              requires a caller-saved reg.  */
 724           if (GET_CODE (insn) == CALL_INSN)
 725             {
 726               struct du_chain *p;
 727               for (p = open_chains; p; p = p->next_chain)
 728                 {
 729                   struct du_chain *p2;
 730                   for (p2 = p; p2->next_use; p2 = p2->next_use)
 731                     /* nothing */;
 732                   p2->need_caller_save_reg = 1;
 733                 }
 734             }
 735
 736           /* Step 5: Close open chains that overlap writes.  Similar to
 737              step 2, we hide in-out operands, since we do not want to
 738              close these chains.  */
 739
 740           for (i = 0; i < n_ops; i++)
 741             {
 742               old_operands[i] = recog_data.operand[i];
 743               if (recog_data.operand_type[i] == OP_INOUT)
 744                 *recog_data.operand_loc[i] = cc0_rtx;
 745             }
 746           for (i = 0; i < recog_data.n_dups; i++)
 747             {
 748               int opn = recog_data.dup_num[i];
 749               old_dups[i] = *recog_data.dup_loc[i];
 750               if (recog_data.operand_type[opn] == OP_INOUT)
 751                 *recog_data.dup_loc[i] = cc0_rtx;
 752             }
 753
 754           scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
 755
 756           for (i = 0; i < recog_data.n_dups; i++)
 757             *recog_data.dup_loc[i] = old_dups[i];
 758           for (i = 0; i < n_ops; i++)
 759             *recog_data.operand_loc[i] = old_operands[i];
 760
 761           /* Step 6: Begin new chains for writes inside operands.  */
 762           /* ??? Many targets have output constraints on the SET_DEST
 763              of a call insn, which is stupid, since these are certainly
 764              ABI defined hard registers.  Don't change calls at all.  */
 765           if (GET_CODE (insn) != CALL_INSN)
 766             for (i = 0; i < n_ops + recog_data.n_dups; i++)
 767               {
 768                 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
 769                 rtx *loc = (i < n_ops
 770                             ? recog_data.operand_loc[opn]
 771                             : recog_data.dup_loc[i - n_ops]);
 772                 enum reg_class class = recog_op_alt[opn][alt].class;
 773
 774                 if (recog_data.operand_type[opn] == OP_OUT)
 775                   scan_rtx (insn, loc, class, mark_write, OP_OUT);
 776               }
 777
 778           /* Step 7: Close chains for registers that were never
 779              really used here.  */
 780           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 781             if (REG_NOTE_KIND (note) == REG_UNUSED)
 782               scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
 783         }
 784       if (insn == bb->end)
 785         break;
 786     }
 787
 788   /* Since we close every chain when we find a REG_DEAD note, anything that
 789      is still open lives past the basic block, so it can't be renamed.  */
 790   return closed_chains;
 791 }
 792
 793 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE.  They are
 794    printed in reverse order as that's how we build them.  */
 795
 796 static void
 797 dump_def_use_chain (chains)
 798      struct du_chain *chains;
 799 {
 800   while (chains)
 801     {
 802       struct du_chain *this = chains;
 803       int r = REGNO (*this->loc);
 804       int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
 805       fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
 806       while (this)
 807         {
 808           fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
 809                    reg_class_names[this->class]);
 810           this = this->next_use;
 811         }
 812       fprintf (rtl_dump_file, "\n");
 813       chains = chains->next_chain;
 814     }
 815 }