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