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