gcc/local-alloc.c

   1 /* Allocate registers within a basic block, for GNU compiler.
   2    Copyright (C) 1987, 1988, 1991, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* Allocation of hard register numbers to pseudo registers is done in
  23    two passes.  In this pass we consider only regs that are born and
  24    die once within one basic block.  We do this one basic block at a
  25    time.  Then the next pass allocates the registers that remain.
  26    Two passes are used because this pass uses methods that work only
  27    on linear code, but that do a better job than the general methods
  28    used in global_alloc, and more quickly too.
  29
  30    The assignments made are recorded in the vector reg_renumber
  31    whose space is allocated here.  The rtl code itself is not altered.
  32
  33    We assign each instruction in the basic block a number
  34    which is its order from the beginning of the block.
  35    Then we can represent the lifetime of a pseudo register with
  36    a pair of numbers, and check for conflicts easily.
  37    We can record the availability of hard registers with a
  38    HARD_REG_SET for each instruction.  The HARD_REG_SET
  39    contains 0 or 1 for each hard reg.
  40
  41    To avoid register shuffling, we tie registers together when one
  42    dies by being copied into another, or dies in an instruction that
  43    does arithmetic to produce another.  The tied registers are
  44    allocated as one.  Registers with different reg class preferences
  45    can never be tied unless the class preferred by one is a subclass
  46    of the one preferred by the other.
  47
  48    Tying is represented with "quantity numbers".
  49    A non-tied register is given a new quantity number.
  50    Tied registers have the same quantity number.
  51
  52    We have provision to exempt registers, even when they are contained
  53    within the block, that can be tied to others that are not contained in it.
  54    This is so that global_alloc could process them both and tie them then.
  55    But this is currently disabled since tying in global_alloc is not
  56    yet implemented.  */
  57
  58 /* Pseudos allocated here can be reallocated by global.c if the hard register
  59    is used as a spill register.  Currently we don't allocate such pseudos
  60    here if their preferred class is likely to be used by spills.  */
  61
  62 #include "config.h"
  63 #include "system.h"
  64 #include "rtl.h"
  65 #include "tm_p.h"
  66 #include "flags.h"
  67 #include "hard-reg-set.h"
  68 #include "basic-block.h"
  69 #include "regs.h"
  70 #include "function.h"
  71 #include "insn-config.h"
  72 #include "insn-attr.h"
  73 #include "recog.h"
  74 #include "output.h"
  75 #include "toplev.h"
  76 \f
  77 /* Next quantity number available for allocation.  */
  78
  79 static int next_qty;
  80
  81 /* Information we maitain about each quantity.  */
  82 struct qty
  83 {
  84   /* The number of refs to quantity Q.  */
  85
  86   int n_refs;
  87
  88   /* The frequency of uses of quantity Q.  */
  89
  90   int freq;
  91
  92   /* Insn number (counting from head of basic block)
  93      where quantity Q was born.  -1 if birth has not been recorded.  */
  94
  95   int birth;
  96
  97   /* Insn number (counting from head of basic block)
  98      where given quantity died.  Due to the way tying is done,
  99      and the fact that we consider in this pass only regs that die but once,
 100      a quantity can die only once.  Each quantity's life span
 101      is a set of consecutive insns.  -1 if death has not been recorded.  */
 102
 103   int death;
 104
 105   /* Number of words needed to hold the data in given quantity.
 106      This depends on its machine mode.  It is used for these purposes:
 107      1. It is used in computing the relative importances of qtys,
 108         which determines the order in which we look for regs for them.
 109      2. It is used in rules that prevent tying several registers of
 110         different sizes in a way that is geometrically impossible
 111         (see combine_regs).  */
 112
 113   int size;
 114
 115   /* Number of times a reg tied to given qty lives across a CALL_INSN.  */
 116
 117   int n_calls_crossed;
 118
 119   /* The register number of one pseudo register whose reg_qty value is Q.
 120      This register should be the head of the chain
 121      maintained in reg_next_in_qty.  */
 122
 123   int first_reg;
 124
 125   /* Reg class contained in (smaller than) the preferred classes of all
 126      the pseudo regs that are tied in given quantity.
 127      This is the preferred class for allocating that quantity.  */
 128
 129   enum reg_class min_class;
 130
 131   /* Register class within which we allocate given qty if we can't get
 132      its preferred class.  */
 133
 134   enum reg_class alternate_class;
 135
 136   /* This holds the mode of the registers that are tied to given qty,
 137      or VOIDmode if registers with differing modes are tied together.  */
 138
 139   enum machine_mode mode;
 140
 141   /* the hard reg number chosen for given quantity,
 142      or -1 if none was found.  */
 143
 144   short phys_reg;
 145
 146   /* Nonzero if this quantity has been used in a SUBREG in some
 147      way that is illegal.  */
 148
 149   char changes_mode;
 150
 151 };
 152
 153 static struct qty *qty;
 154
 155 /* These fields are kept separately to speedup their clearing.  */
 156
 157 /* We maintain two hard register sets that indicate suggested hard registers
 158    for each quantity.  The first, phys_copy_sugg, contains hard registers
 159    that are tied to the quantity by a simple copy.  The second contains all
 160    hard registers that are tied to the quantity via an arithmetic operation.
 161
 162    The former register set is given priority for allocation.  This tends to
 163    eliminate copy insns.  */
 164
 165 /* Element Q is a set of hard registers that are suggested for quantity Q by
 166    copy insns.  */
 167
 168 static HARD_REG_SET *qty_phys_copy_sugg;
 169
 170 /* Element Q is a set of hard registers that are suggested for quantity Q by
 171    arithmetic insns.  */
 172
 173 static HARD_REG_SET *qty_phys_sugg;
 174
 175 /* Element Q is the number of suggested registers in qty_phys_copy_sugg.  */
 176
 177 static short *qty_phys_num_copy_sugg;
 178
 179 /* Element Q is the number of suggested registers in qty_phys_sugg.  */
 180
 181 static short *qty_phys_num_sugg;
 182
 183 /* If (REG N) has been assigned a quantity number, is a register number
 184    of another register assigned the same quantity number, or -1 for the
 185    end of the chain.  qty->first_reg point to the head of this chain.  */
 186
 187 static int *reg_next_in_qty;
 188
 189 /* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg
 190    if it is >= 0,
 191    of -1 if this register cannot be allocated by local-alloc,
 192    or -2 if not known yet.
 193
 194    Note that if we see a use or death of pseudo register N with
 195    reg_qty[N] == -2, register N must be local to the current block.  If
 196    it were used in more than one block, we would have reg_qty[N] == -1.
 197    This relies on the fact that if reg_basic_block[N] is >= 0, register N
 198    will not appear in any other block.  We save a considerable number of
 199    tests by exploiting this.
 200
 201    If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not
 202    be referenced.  */
 203
 204 static int *reg_qty;
 205
 206 /* The offset (in words) of register N within its quantity.
 207    This can be nonzero if register N is SImode, and has been tied
 208    to a subreg of a DImode register.  */
 209
 210 static char *reg_offset;
 211
 212 /* Vector of substitutions of register numbers,
 213    used to map pseudo regs into hardware regs.
 214    This is set up as a result of register allocation.
 215    Element N is the hard reg assigned to pseudo reg N,
 216    or is -1 if no hard reg was assigned.
 217    If N is a hard reg number, element N is N.  */
 218
 219 short *reg_renumber;
 220
 221 /* Set of hard registers live at the current point in the scan
 222    of the instructions in a basic block.  */
 223
 224 static HARD_REG_SET regs_live;
 225
 226 /* Each set of hard registers indicates registers live at a particular
 227    point in the basic block.  For N even, regs_live_at[N] says which
 228    hard registers are needed *after* insn N/2 (i.e., they may not
 229    conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1.
 230
 231    If an object is to conflict with the inputs of insn J but not the
 232    outputs of insn J + 1, we say it is born at index J*2 - 1.  Similarly,
 233    if it is to conflict with the outputs of insn J but not the inputs of
 234    insn J + 1, it is said to die at index J*2 + 1.  */
 235
 236 static HARD_REG_SET *regs_live_at;
 237
 238 /* Communicate local vars `insn_number' and `insn'
 239    from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'.  */
 240 static int this_insn_number;
 241 static rtx this_insn;
 242
 243 struct equivalence
 244 {
 245   /* Set when an attempt should be made to replace a register
 246      with the associated src entry.  */
 247
 248   char replace;
 249
 250   /* Set when a REG_EQUIV note is found or created.  Use to
 251      keep track of what memory accesses might be created later,
 252      e.g. by reload.  */
 253
 254   rtx replacement;
 255
 256   rtx src;
 257
 258   /* Loop depth is used to recognize equivalences which appear
 259      to be present within the same loop (or in an inner loop).  */
 260
 261   int loop_depth;
 262
 263   /* The list of each instruction which initializes this register.  */
 264
 265   rtx init_insns;
 266 };
 267
 268 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
 269    structure for that register.  */
 270
 271 static struct equivalence *reg_equiv;
 272
 273 /* Nonzero if we recorded an equivalence for a LABEL_REF.  */
 274 static int recorded_label_ref;
 275
 276 static void alloc_qty           PARAMS ((int, enum machine_mode, int, int));
 277 static void validate_equiv_mem_from_store PARAMS ((rtx, rtx, void *));
 278 static int validate_equiv_mem   PARAMS ((rtx, rtx, rtx));
 279 static int equiv_init_varies_p  PARAMS ((rtx));
 280 static int equiv_init_movable_p PARAMS ((rtx, int));
 281 static int contains_replace_regs PARAMS ((rtx));
 282 static int memref_referenced_p  PARAMS ((rtx, rtx));
 283 static int memref_used_between_p PARAMS ((rtx, rtx, rtx));
 284 static void update_equiv_regs   PARAMS ((void));
 285 static void no_equiv            PARAMS ((rtx, rtx, void *));
 286 static void block_alloc         PARAMS ((int));
 287 static int qty_sugg_compare     PARAMS ((int, int));
 288 static int qty_sugg_compare_1   PARAMS ((const PTR, const PTR));
 289 static int qty_compare          PARAMS ((int, int));
 290 static int qty_compare_1        PARAMS ((const PTR, const PTR));
 291 static int combine_regs         PARAMS ((rtx, rtx, int, int, rtx, int));
 292 static int reg_meets_class_p    PARAMS ((int, enum reg_class));
 293 static void update_qty_class    PARAMS ((int, int));
 294 static void reg_is_set          PARAMS ((rtx, rtx, void *));
 295 static void reg_is_born         PARAMS ((rtx, int));
 296 static void wipe_dead_reg       PARAMS ((rtx, int));
 297 static int find_free_reg        PARAMS ((enum reg_class, enum machine_mode,
 298                                        int, int, int, int, int));
 299 static void mark_life           PARAMS ((int, enum machine_mode, int));
 300 static void post_mark_life      PARAMS ((int, enum machine_mode, int, int, int));
 301 static int no_conflict_p        PARAMS ((rtx, rtx, rtx));
 302 static int requires_inout       PARAMS ((const char *));
 303 \f
 304 /* Allocate a new quantity (new within current basic block)
 305    for register number REGNO which is born at index BIRTH
 306    within the block.  MODE and SIZE are info on reg REGNO.  */
 307
 308 static void
 309 alloc_qty (regno, mode, size, birth)
 310      int regno;
 311      enum machine_mode mode;
 312      int size, birth;
 313 {
 314   register int qtyno = next_qty++;
 315
 316   reg_qty[regno] = qtyno;
 317   reg_offset[regno] = 0;
 318   reg_next_in_qty[regno] = -1;
 319
 320   qty[qtyno].first_reg = regno;
 321   qty[qtyno].size = size;
 322   qty[qtyno].mode = mode;
 323   qty[qtyno].birth = birth;
 324   qty[qtyno].n_calls_crossed = REG_N_CALLS_CROSSED (regno);
 325   qty[qtyno].min_class = reg_preferred_class (regno);
 326   qty[qtyno].alternate_class = reg_alternate_class (regno);
 327   qty[qtyno].n_refs = REG_N_REFS (regno);
 328   qty[qtyno].freq = REG_FREQ (regno);
 329   qty[qtyno].changes_mode = REG_CHANGES_MODE (regno);
 330 }
 331 \f
 332 /* Main entry point of this file.  */
 333
 334 int
 335 local_alloc ()
 336 {
 337   register int b, i;
 338   int max_qty;
 339
 340   /* We need to keep track of whether or not we recorded a LABEL_REF so
 341      that we know if the jump optimizer needs to be rerun.  */
 342   recorded_label_ref = 0;
 343
 344   /* Leaf functions and non-leaf functions have different needs.
 345      If defined, let the machine say what kind of ordering we
 346      should use.  */
 347 #ifdef ORDER_REGS_FOR_LOCAL_ALLOC
 348   ORDER_REGS_FOR_LOCAL_ALLOC;
 349 #endif
 350
 351   /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected
 352      registers.  */
 353   update_equiv_regs ();
 354
 355   /* This sets the maximum number of quantities we can have.  Quantity
 356      numbers start at zero and we can have one for each pseudo.  */
 357   max_qty = (max_regno - FIRST_PSEUDO_REGISTER);
 358
 359   /* Allocate vectors of temporary data.
 360      See the declarations of these variables, above,
 361      for what they mean.  */
 362
 363   qty = (struct qty *) xmalloc (max_qty * sizeof (struct qty));
 364   qty_phys_copy_sugg
 365     = (HARD_REG_SET *) xmalloc (max_qty * sizeof (HARD_REG_SET));
 366   qty_phys_num_copy_sugg = (short *) xmalloc (max_qty * sizeof (short));
 367   qty_phys_sugg = (HARD_REG_SET *) xmalloc (max_qty * sizeof (HARD_REG_SET));
 368   qty_phys_num_sugg = (short *) xmalloc (max_qty * sizeof (short));
 369
 370   reg_qty = (int *) xmalloc (max_regno * sizeof (int));
 371   reg_offset = (char *) xmalloc (max_regno * sizeof (char));
 372   reg_next_in_qty = (int *) xmalloc (max_regno * sizeof (int));
 373
 374   /* Allocate the reg_renumber array.  */
 375   allocate_reg_info (max_regno, FALSE, TRUE);
 376
 377   /* Determine which pseudo-registers can be allocated by local-alloc.
 378      In general, these are the registers used only in a single block and
 379      which only die once.
 380
 381      We need not be concerned with which block actually uses the register
 382      since we will never see it outside that block.  */
 383
 384   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 385     {
 386       if (REG_BASIC_BLOCK (i) >= 0 && REG_N_DEATHS (i) == 1)
 387         reg_qty[i] = -2;
 388       else
 389         reg_qty[i] = -1;
 390     }
 391
 392   /* Force loop below to initialize entire quantity array.  */
 393   next_qty = max_qty;
 394
 395   /* Allocate each block's local registers, block by block.  */
 396
 397   for (b = 0; b < n_basic_blocks; b++)
 398     {
 399       /* NEXT_QTY indicates which elements of the `qty_...'
 400          vectors might need to be initialized because they were used
 401          for the previous block; it is set to the entire array before
 402          block 0.  Initialize those, with explicit loop if there are few,
 403          else with bzero and bcopy.  Do not initialize vectors that are
 404          explicit set by `alloc_qty'.  */
 405
 406       if (next_qty < 6)
 407         {
 408           for (i = 0; i < next_qty; i++)
 409             {
 410               CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
 411               qty_phys_num_copy_sugg[i] = 0;
 412               CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
 413               qty_phys_num_sugg[i] = 0;
 414             }
 415         }
 416       else
 417         {
 418 #define CLEAR(vector)  \
 419           memset ((char *) (vector), 0, (sizeof (*(vector))) * next_qty);
 420
 421           CLEAR (qty_phys_copy_sugg);
 422           CLEAR (qty_phys_num_copy_sugg);
 423           CLEAR (qty_phys_sugg);
 424           CLEAR (qty_phys_num_sugg);
 425         }
 426
 427       next_qty = 0;
 428
 429       block_alloc (b);
 430     }
 431
 432   free (qty);
 433   free (qty_phys_copy_sugg);
 434   free (qty_phys_num_copy_sugg);
 435   free (qty_phys_sugg);
 436   free (qty_phys_num_sugg);
 437
 438   free (reg_qty);
 439   free (reg_offset);
 440   free (reg_next_in_qty);
 441
 442   return recorded_label_ref;
 443 }
 444 \f
 445 /* Used for communication between the following two functions: contains
 446    a MEM that we wish to ensure remains unchanged.  */
 447 static rtx equiv_mem;
 448
 449 /* Set nonzero if EQUIV_MEM is modified.  */
 450 static int equiv_mem_modified;
 451
 452 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
 453    Called via note_stores.  */
 454
 455 static void
 456 validate_equiv_mem_from_store (dest, set, data)
 457      rtx dest;
 458      rtx set ATTRIBUTE_UNUSED;
 459      void *data ATTRIBUTE_UNUSED;
 460 {
 461   if ((GET_CODE (dest) == REG
 462        && reg_overlap_mentioned_p (dest, equiv_mem))
 463       || (GET_CODE (dest) == MEM
 464           && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
 465     equiv_mem_modified = 1;
 466 }
 467
 468 /* Verify that no store between START and the death of REG invalidates
 469    MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
 470    by storing into an overlapping memory location, or with a non-const
 471    CALL_INSN.
 472
 473    Return 1 if MEMREF remains valid.  */
 474
 475 static int
 476 validate_equiv_mem (start, reg, memref)
 477      rtx start;
 478      rtx reg;
 479      rtx memref;
 480 {
 481   rtx insn;
 482   rtx note;
 483
 484   equiv_mem = memref;
 485   equiv_mem_modified = 0;
 486
 487   /* If the memory reference has side effects or is volatile, it isn't a
 488      valid equivalence.  */
 489   if (side_effects_p (memref))
 490     return 0;
 491
 492   for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
 493     {
 494       if (! INSN_P (insn))
 495         continue;
 496
 497       if (find_reg_note (insn, REG_DEAD, reg))
 498         return 1;
 499
 500       if (GET_CODE (insn) == CALL_INSN && ! RTX_UNCHANGING_P (memref)
 501           && ! CONST_CALL_P (insn))
 502         return 0;
 503
 504       note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
 505
 506       /* If a register mentioned in MEMREF is modified via an
 507          auto-increment, we lose the equivalence.  Do the same if one
 508          dies; although we could extend the life, it doesn't seem worth
 509          the trouble.  */
 510
 511       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 512         if ((REG_NOTE_KIND (note) == REG_INC
 513              || REG_NOTE_KIND (note) == REG_DEAD)
 514             && GET_CODE (XEXP (note, 0)) == REG
 515             && reg_overlap_mentioned_p (XEXP (note, 0), memref))
 516           return 0;
 517     }
 518
 519   return 0;
 520 }
 521
 522 /* Returns zero if X is known to be invariant.  */
 523
 524 static int
 525 equiv_init_varies_p (x)
 526      rtx x;
 527 {
 528   register RTX_CODE code = GET_CODE (x);
 529   register int i;
 530   register const char *fmt;
 531
 532   switch (code)
 533     {
 534     case MEM:
 535       return ! RTX_UNCHANGING_P (x) || equiv_init_varies_p (XEXP (x, 0));
 536
 537     case QUEUED:
 538       return 1;
 539
 540     case CONST:
 541     case CONST_INT:
 542     case CONST_DOUBLE:
 543     case SYMBOL_REF:
 544     case LABEL_REF:
 545       return 0;
 546
 547     case REG:
 548       return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
 549
 550     case ASM_OPERANDS:
 551       if (MEM_VOLATILE_P (x))
 552         return 1;
 553
 554       /* FALLTHROUGH */
 555
 556     default:
 557       break;
 558     }
 559
 560   fmt = GET_RTX_FORMAT (code);
 561   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 562     if (fmt[i] == 'e')
 563       {
 564         if (equiv_init_varies_p (XEXP (x, i)))
 565           return 1;
 566       }
 567     else if (fmt[i] == 'E')
 568       {
 569         int j;
 570         for (j = 0; j < XVECLEN (x, i); j++)
 571           if (equiv_init_varies_p (XVECEXP (x, i, j)))
 572             return 1;
 573       }
 574
 575   return 0;
 576 }
 577
 578 /* Returns non-zero if X (used to initialize register REGNO) is movable.
 579    X is only movable if the registers it uses have equivalent initializations
 580    which appear to be within the same loop (or in an inner loop) and movable
 581    or if they are not candidates for local_alloc and don't vary.  */
 582
 583 static int
 584 equiv_init_movable_p (x, regno)
 585      rtx x;
 586      int regno;
 587 {
 588   int i, j;
 589   const char *fmt;
 590   enum rtx_code code = GET_CODE (x);
 591
 592   switch (code)
 593     {
 594     case SET:
 595       return equiv_init_movable_p (SET_SRC (x), regno);
 596
 597     case CC0:
 598     case CLOBBER:
 599       return 0;
 600
 601     case PRE_INC:
 602     case PRE_DEC:
 603     case POST_INC:
 604     case POST_DEC:
 605     case PRE_MODIFY:
 606     case POST_MODIFY:
 607       return 0;
 608
 609     case REG:
 610       return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
 611               && reg_equiv[REGNO (x)].replace)
 612              || (REG_BASIC_BLOCK (REGNO (x)) < 0 && ! rtx_varies_p (x, 0));
 613
 614     case UNSPEC_VOLATILE:
 615       return 0;
 616
 617     case ASM_OPERANDS:
 618       if (MEM_VOLATILE_P (x))
 619         return 0;
 620
 621       /* FALLTHROUGH */
 622
 623     default:
 624       break;
 625     }
 626
 627   fmt = GET_RTX_FORMAT (code);
 628   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 629     switch (fmt[i])
 630       {
 631       case 'e':
 632         if (! equiv_init_movable_p (XEXP (x, i), regno))
 633           return 0;
 634         break;
 635       case 'E':
 636         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 637           if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
 638             return 0;
 639         break;
 640       }
 641
 642   return 1;
 643 }
 644
 645 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true.  */
 646
 647 static int
 648 contains_replace_regs (x)
 649      rtx x;
 650 {
 651   int i, j;
 652   const char *fmt;
 653   enum rtx_code code = GET_CODE (x);
 654
 655   switch (code)
 656     {
 657     case CONST_INT:
 658     case CONST:
 659     case LABEL_REF:
 660     case SYMBOL_REF:
 661     case CONST_DOUBLE:
 662     case PC:
 663     case CC0:
 664     case HIGH:
 665     case LO_SUM:
 666       return 0;
 667
 668     case REG:
 669       return reg_equiv[REGNO (x)].replace;
 670
 671     default:
 672       break;
 673     }
 674
 675   fmt = GET_RTX_FORMAT (code);
 676   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 677     switch (fmt[i])
 678       {
 679       case 'e':
 680         if (contains_replace_regs (XEXP (x, i)))
 681           return 1;
 682         break;
 683       case 'E':
 684         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 685           if (contains_replace_regs (XVECEXP (x, i, j)))
 686             return 1;
 687         break;
 688       }
 689
 690   return 0;
 691 }
 692 \f
 693 /* TRUE if X references a memory location that would be affected by a store
 694    to MEMREF.  */
 695
 696 static int
 697 memref_referenced_p (memref, x)
 698      rtx x;
 699      rtx memref;
 700 {
 701   int i, j;
 702   const char *fmt;
 703   enum rtx_code code = GET_CODE (x);
 704
 705   switch (code)
 706     {
 707     case CONST_INT:
 708     case CONST:
 709     case LABEL_REF:
 710     case SYMBOL_REF:
 711     case CONST_DOUBLE:
 712     case PC:
 713     case CC0:
 714     case HIGH:
 715     case LO_SUM:
 716       return 0;
 717
 718     case REG:
 719       return (reg_equiv[REGNO (x)].replacement
 720               && memref_referenced_p (memref,
 721                                       reg_equiv[REGNO (x)].replacement));
 722
 723     case MEM:
 724       if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
 725         return 1;
 726       break;
 727
 728     case SET:
 729       /* If we are setting a MEM, it doesn't count (its address does), but any
 730          other SET_DEST that has a MEM in it is referencing the MEM.  */
 731       if (GET_CODE (SET_DEST (x)) == MEM)
 732         {
 733           if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
 734             return 1;
 735         }
 736       else if (memref_referenced_p (memref, SET_DEST (x)))
 737         return 1;
 738
 739       return memref_referenced_p (memref, SET_SRC (x));
 740
 741     default:
 742       break;
 743     }
 744
 745   fmt = GET_RTX_FORMAT (code);
 746   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 747     switch (fmt[i])
 748       {
 749       case 'e':
 750         if (memref_referenced_p (memref, XEXP (x, i)))
 751           return 1;
 752         break;
 753       case 'E':
 754         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 755           if (memref_referenced_p (memref, XVECEXP (x, i, j)))
 756             return 1;
 757         break;
 758       }
 759
 760   return 0;
 761 }
 762
 763 /* TRUE if some insn in the range (START, END] references a memory location
 764    that would be affected by a store to MEMREF.  */
 765
 766 static int
 767 memref_used_between_p (memref, start, end)
 768      rtx memref;
 769      rtx start;
 770      rtx end;
 771 {
 772   rtx insn;
 773
 774   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
 775        insn = NEXT_INSN (insn))
 776     if (INSN_P (insn) && memref_referenced_p (memref, PATTERN (insn)))
 777       return 1;
 778
 779   return 0;
 780 }
 781 \f
 782 /* Return nonzero if the rtx X is invariant over the current function.  */
 783 int
 784 function_invariant_p (x)
 785      rtx x;
 786 {
 787   if (CONSTANT_P (x))
 788     return 1;
 789   if (x == frame_pointer_rtx || x == arg_pointer_rtx)
 790     return 1;
 791   if (GET_CODE (x) == PLUS
 792       && (XEXP (x, 0) == frame_pointer_rtx || XEXP (x, 0) == arg_pointer_rtx)
 793       && CONSTANT_P (XEXP (x, 1)))
 794     return 1;
 795   return 0;
 796 }
 797
 798 /* Find registers that are equivalent to a single value throughout the
 799    compilation (either because they can be referenced in memory or are set once
 800    from a single constant).  Lower their priority for a register.
 801
 802    If such a register is only referenced once, try substituting its value
 803    into the using insn.  If it succeeds, we can eliminate the register
 804    completely.  */
 805
 806 static void
 807 update_equiv_regs ()
 808 {
 809   rtx insn;
 810   int block;
 811   int loop_depth;
 812   regset_head cleared_regs;
 813   int clear_regnos = 0;
 814
 815   reg_equiv = (struct equivalence *) xcalloc (max_regno, sizeof *reg_equiv);
 816   INIT_REG_SET (&cleared_regs);
 817
 818   init_alias_analysis ();
 819
 820   /* Scan the insns and find which registers have equivalences.  Do this
 821      in a separate scan of the insns because (due to -fcse-follow-jumps)
 822      a register can be set below its use.  */
 823   loop_depth = 0;
 824   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 825     {
 826       rtx note;
 827       rtx set;
 828       rtx dest, src;
 829       int regno;
 830
 831       if (GET_CODE (insn) == NOTE)
 832         {
 833           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
 834             ++loop_depth;
 835           else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
 836             {
 837               if (! loop_depth)
 838                 abort ();
 839               --loop_depth;
 840             }
 841         }
 842
 843       if (! INSN_P (insn))
 844         continue;
 845
 846       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 847         if (REG_NOTE_KIND (note) == REG_INC)
 848           no_equiv (XEXP (note, 0), note, NULL);
 849
 850       set = single_set (insn);
 851
 852       /* If this insn contains more (or less) than a single SET,
 853          only mark all destinations as having no known equivalence.  */
 854       if (set == 0)
 855         {
 856           note_stores (PATTERN (insn), no_equiv, NULL);
 857           continue;
 858         }
 859       else if (GET_CODE (PATTERN (insn)) == PARALLEL)
 860         {
 861           int i;
 862
 863           for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
 864             {
 865               rtx part = XVECEXP (PATTERN (insn), 0, i);
 866               if (part != set)
 867                 note_stores (part, no_equiv, NULL);
 868             }
 869         }
 870
 871       dest = SET_DEST (set);
 872       src = SET_SRC (set);
 873
 874       /* If this sets a MEM to the contents of a REG that is only used
 875          in a single basic block, see if the register is always equivalent
 876          to that memory location and if moving the store from INSN to the
 877          insn that set REG is safe.  If so, put a REG_EQUIV note on the
 878          initializing insn.
 879
 880          Don't add a REG_EQUIV note if the insn already has one.  The existing
 881          REG_EQUIV is likely more useful than the one we are adding.
 882
 883          If one of the regs in the address has reg_equiv[REGNO].replace set,
 884          then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
 885          optimization may move the set of this register immediately before
 886          insn, which puts it after reg_equiv[REGNO].init_insns, and hence
 887          the mention in the REG_EQUIV note would be to an uninitialized
 888          pseudo.  */
 889       /* ????? This test isn't good enough; we might see a MEM with a use of
 890          a pseudo register before we see its setting insn that will cause
 891          reg_equiv[].replace for that pseudo to be set.
 892          Equivalences to MEMs should be made in another pass, after the
 893          reg_equiv[].replace information has been gathered.  */
 894
 895       if (GET_CODE (dest) == MEM && GET_CODE (src) == REG
 896           && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
 897           && REG_BASIC_BLOCK (regno) >= 0
 898           && REG_N_SETS (regno) == 1
 899           && reg_equiv[regno].init_insns != 0
 900           && reg_equiv[regno].init_insns != const0_rtx
 901           && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
 902                               REG_EQUIV, NULL_RTX)
 903           && ! contains_replace_regs (XEXP (dest, 0)))
 904         {
 905           rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
 906           if (validate_equiv_mem (init_insn, src, dest)
 907               && ! memref_used_between_p (dest, init_insn, insn))
 908             REG_NOTES (init_insn)
 909               = gen_rtx_EXPR_LIST (REG_EQUIV, dest, REG_NOTES (init_insn));
 910         }
 911
 912       /* We only handle the case of a pseudo register being set
 913          once, or always to the same value.  */
 914       /* ??? The mn10200 port breaks if we add equivalences for
 915          values that need an ADDRESS_REGS register and set them equivalent
 916          to a MEM of a pseudo.  The actual problem is in the over-conservative
 917          handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
 918          calculate_needs, but we traditionally work around this problem
 919          here by rejecting equivalences when the destination is in a register
 920          that's likely spilled.  This is fragile, of course, since the
 921          preferred class of a pseudo depends on all instructions that set
 922          or use it.  */
 923
 924       if (GET_CODE (dest) != REG
 925           || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
 926           || reg_equiv[regno].init_insns == const0_rtx
 927           || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno))
 928               && GET_CODE (src) == MEM))
 929         {
 930           /* This might be seting a SUBREG of a pseudo, a pseudo that is
 931              also set somewhere else to a constant.  */
 932           note_stores (set, no_equiv, NULL);
 933           continue;
 934         }
 935
 936       note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
 937
 938       /* cse sometimes generates function invariants, but doesn't put a
 939          REG_EQUAL note on the insn.  Since this note would be redundant,
 940          there's no point creating it earlier than here.  */
 941       if (! note && ! rtx_varies_p (src, 0))
 942         REG_NOTES (insn)
 943           = note = gen_rtx_EXPR_LIST (REG_EQUAL, src, REG_NOTES (insn));
 944
 945       /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
 946          since it represents a function call */
 947       if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
 948         note = NULL_RTX;
 949
 950       if (REG_N_SETS (regno) != 1
 951           && (! note
 952               || rtx_varies_p (XEXP (note, 0), 0)
 953               || (reg_equiv[regno].replacement
 954                   && ! rtx_equal_p (XEXP (note, 0),
 955                                     reg_equiv[regno].replacement))))
 956         {
 957           no_equiv (dest, set, NULL);
 958           continue;
 959         }
 960       /* Record this insn as initializing this register.  */
 961       reg_equiv[regno].init_insns
 962         = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
 963
 964       /* If this register is known to be equal to a constant, record that
 965          it is always equivalent to the constant.  */
 966       if (note && ! rtx_varies_p (XEXP (note, 0), 0))
 967         PUT_MODE (note, (enum machine_mode) REG_EQUIV);
 968
 969       /* If this insn introduces a "constant" register, decrease the priority
 970          of that register.  Record this insn if the register is only used once
 971          more and the equivalence value is the same as our source.
 972
 973          The latter condition is checked for two reasons:  First, it is an
 974          indication that it may be more efficient to actually emit the insn
 975          as written (if no registers are available, reload will substitute
 976          the equivalence).  Secondly, it avoids problems with any registers
 977          dying in this insn whose death notes would be missed.
 978
 979          If we don't have a REG_EQUIV note, see if this insn is loading
 980          a register used only in one basic block from a MEM.  If so, and the
 981          MEM remains unchanged for the life of the register, add a REG_EQUIV
 982          note.  */
 983
 984       note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
 985
 986       if (note == 0 && REG_BASIC_BLOCK (regno) >= 0
 987           && GET_CODE (SET_SRC (set)) == MEM
 988           && validate_equiv_mem (insn, dest, SET_SRC (set)))
 989         REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV, SET_SRC (set),
 990                                                      REG_NOTES (insn));
 991
 992       if (note)
 993         {
 994           int regno = REGNO (dest);
 995
 996           /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
 997              We might end up substituting the LABEL_REF for uses of the
 998              pseudo here or later.  That kind of transformation may turn an
 999              indirect jump into a direct jump, in which case we must rerun the
1000              jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
1001           if (GET_CODE (XEXP (note, 0)) == LABEL_REF
1002               || (GET_CODE (XEXP (note, 0)) == CONST
1003                   && GET_CODE (XEXP (XEXP (note, 0), 0)) == PLUS
1004                   && (GET_CODE (XEXP (XEXP (XEXP (note, 0), 0), 0))
1005                       == LABEL_REF)))
1006             recorded_label_ref = 1;
1007
1008           reg_equiv[regno].replacement = XEXP (note, 0);
1009           reg_equiv[regno].src = src;
1010           reg_equiv[regno].loop_depth = loop_depth;
1011
1012           /* Don't mess with things live during setjmp.  */
1013           if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
1014             {
1015               /* Note that the statement below does not affect the priority
1016                  in local-alloc!  */
1017               REG_LIVE_LENGTH (regno) *= 2;
1018
1019
1020               /* If the register is referenced exactly twice, meaning it is
1021                  set once and used once, indicate that the reference may be
1022                  replaced by the equivalence we computed above.  Do this
1023                  even if the register is only used in one block so that
1024                  dependencies can be handled where the last register is
1025                  used in a different block (i.e. HIGH / LO_SUM sequences)
1026                  and to reduce the number of registers alive across calls.
1027
1028                  It would be nice to use "loop_depth * 2" in the compare
1029                  below.  Unfortunately, LOOP_DEPTH need not be constant within
1030                  a basic block so this would be too complicated.
1031
1032                  This case normally occurs when a parameter is read from
1033                  memory and then used exactly once, not in a loop.  */
1034
1035                 if (REG_N_REFS (regno) == 2
1036                     && (rtx_equal_p (XEXP (note, 0), src)
1037                         || ! equiv_init_varies_p (src))
1038                     && GET_CODE (insn) == INSN
1039                     && equiv_init_movable_p (PATTERN (insn), regno))
1040                   reg_equiv[regno].replace = 1;
1041             }
1042         }
1043     }
1044
1045   /* Now scan all regs killed in an insn to see if any of them are
1046      registers only used that once.  If so, see if we can replace the
1047      reference with the equivalent from.  If we can, delete the
1048      initializing reference and this register will go away.  If we
1049      can't replace the reference, and the initialzing reference is
1050      within the same loop (or in an inner loop), then move the register
1051      initialization just before the use, so that they are in the same
1052      basic block.
1053
1054      Skip this optimization if loop_depth isn't initially zero since
1055      that indicates a mismatch between loop begin and loop end notes
1056      (i.e. gcc.dg/noncompile/920721-2.c).  */
1057   block = n_basic_blocks - 1;
1058   for (insn = (loop_depth == 0) ? get_last_insn () : NULL_RTX;
1059        insn; insn = PREV_INSN (insn))
1060     {
1061       rtx link;
1062
1063       if (! INSN_P (insn))
1064         {
1065           if (GET_CODE (insn) == NOTE)
1066             {
1067               if (NOTE_INSN_BASIC_BLOCK_P (insn))
1068                 block = NOTE_BASIC_BLOCK (insn)->index - 1;
1069               else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1070                 {
1071                   if (! loop_depth)
1072                     abort ();
1073                   --loop_depth;
1074                 }
1075               else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1076                 ++loop_depth;
1077             }
1078
1079           continue;
1080         }
1081
1082       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1083         {
1084           if (REG_NOTE_KIND (link) == REG_DEAD
1085               /* Make sure this insn still refers to the register.  */
1086               && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
1087             {
1088               int regno = REGNO (XEXP (link, 0));
1089               rtx equiv_insn;
1090
1091               if (! reg_equiv[regno].replace
1092                   || reg_equiv[regno].loop_depth < loop_depth)
1093                 continue;
1094
1095               /* reg_equiv[REGNO].replace gets set only when
1096                  REG_N_REFS[REGNO] is 2, i.e. the register is set
1097                  once and used once.  (If it were only set, but not used,
1098                  flow would have deleted the setting insns.)  Hence
1099                  there can only be one insn in reg_equiv[REGNO].init_insns.  */
1100               if (reg_equiv[regno].init_insns == NULL_RTX
1101                   || XEXP (reg_equiv[regno].init_insns, 1) != NULL_RTX)
1102                 abort ();
1103               equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
1104
1105               if (asm_noperands (PATTERN (equiv_insn)) < 0
1106                   && validate_replace_rtx (regno_reg_rtx[regno],
1107                                            reg_equiv[regno].src, insn))
1108                 {
1109                   rtx equiv_link;
1110                   rtx last_link;
1111                   rtx note;
1112
1113                   /* Find the last note.  */
1114                   for (last_link = link; XEXP (last_link, 1);
1115                        last_link = XEXP (last_link, 1))
1116                     ;
1117
1118                   /* Append the REG_DEAD notes from equiv_insn.  */
1119                   equiv_link = REG_NOTES (equiv_insn);
1120                   while (equiv_link)
1121                     {
1122                       note = equiv_link;
1123                       equiv_link = XEXP (equiv_link, 1);
1124                       if (REG_NOTE_KIND (note) == REG_DEAD)
1125                         {
1126                           remove_note (equiv_insn, note);
1127                           XEXP (last_link, 1) = note;
1128                           XEXP (note, 1) = NULL_RTX;
1129                           last_link = note;
1130                         }
1131                     }
1132
1133                   remove_death (regno, insn);
1134                   REG_N_REFS (regno) = 0;
1135                   REG_FREQ (regno) = 0;
1136                   PUT_CODE (equiv_insn, NOTE);
1137                   NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
1138                   NOTE_SOURCE_FILE (equiv_insn) = 0;
1139
1140                   reg_equiv[regno].init_insns
1141                     = XEXP (reg_equiv[regno].init_insns, 1);
1142                 }
1143               /* Move the initialization of the register to just before
1144                  INSN.  Update the flow information.  */
1145               else if (PREV_INSN (insn) != equiv_insn)
1146                 {
1147                   rtx new_insn;
1148
1149                   new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
1150                   REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
1151                   REG_NOTES (equiv_insn) = 0;
1152
1153                   /* Make sure this insn is recognized before reload begins,
1154                      otherwise eliminate_regs_in_insn will abort.  */
1155                   INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
1156
1157                   PUT_CODE (equiv_insn, NOTE);
1158                   NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
1159                   NOTE_SOURCE_FILE (equiv_insn) = 0;
1160
1161                   XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
1162
1163                   REG_BASIC_BLOCK (regno) = block >= 0 ? block : 0;
1164                   REG_N_CALLS_CROSSED (regno) = 0;
1165                   REG_LIVE_LENGTH (regno) = 2;
1166
1167                   if (block >= 0 && insn == BLOCK_HEAD (block))
1168                     BLOCK_HEAD (block) = PREV_INSN (insn);
1169
1170                   /* Remember to clear REGNO from all basic block's live
1171                      info.  */
1172                   SET_REGNO_REG_SET (&cleared_regs, regno);
1173                   clear_regnos++;
1174                 }
1175             }
1176         }
1177     }
1178
1179   /* Clear all dead REGNOs from all basic block's live info.  */
1180   if (clear_regnos)
1181     {
1182       int j, l;
1183       if (clear_regnos > 8)
1184         {
1185           for (l = 0; l < n_basic_blocks; l++)
1186             {
1187               AND_COMPL_REG_SET (BASIC_BLOCK (l)->global_live_at_start,
1188                                  &cleared_regs);
1189               AND_COMPL_REG_SET (BASIC_BLOCK (l)->global_live_at_end,
1190                                  &cleared_regs);
1191             }
1192         }
1193       else
1194         EXECUTE_IF_SET_IN_REG_SET (&cleared_regs, 0, j,
1195           {
1196             for (l = 0; l < n_basic_blocks; l++)
1197               {
1198                 CLEAR_REGNO_REG_SET (BASIC_BLOCK (l)->global_live_at_start, j);
1199                 CLEAR_REGNO_REG_SET (BASIC_BLOCK (l)->global_live_at_end, j);
1200               }
1201           });
1202     }
1203
1204   /* Clean up.  */
1205   end_alias_analysis ();
1206   CLEAR_REG_SET (&cleared_regs);
1207   free (reg_equiv);
1208 }
1209
1210 /* Mark REG as having no known equivalence.
1211    Some instructions might have been proceessed before and furnished
1212    with REG_EQUIV notes for this register; these notes will have to be
1213    removed.
1214    STORE is the piece of RTL that does the non-constant / conflicting
1215    assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
1216    but needs to be there because this function is called from note_stores.  */
1217 static void
1218 no_equiv (reg, store, data)
1219      rtx reg, store ATTRIBUTE_UNUSED;
1220      void *data ATTRIBUTE_UNUSED;
1221 {
1222   int regno;
1223   rtx list;
1224
1225   if (GET_CODE (reg) != REG)
1226     return;
1227   regno = REGNO (reg);
1228   list = reg_equiv[regno].init_insns;
1229   if (list == const0_rtx)
1230     return;
1231   for (; list; list =  XEXP (list, 1))
1232     {
1233       rtx insn = XEXP (list, 0);
1234       remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
1235     }
1236   reg_equiv[regno].init_insns = const0_rtx;
1237   reg_equiv[regno].replacement = NULL_RTX;
1238 }
1239 \f
1240 /* Allocate hard regs to the pseudo regs used only within block number B.
1241    Only the pseudos that die but once can be handled.  */
1242
1243 static void
1244 block_alloc (b)
1245      int b;
1246 {
1247   register int i, q;
1248   register rtx insn;
1249   rtx note;
1250   int insn_number = 0;
1251   int insn_count = 0;
1252   int max_uid = get_max_uid ();
1253   int *qty_order;
1254   int no_conflict_combined_regno = -1;
1255
1256   /* Count the instructions in the basic block.  */
1257
1258   insn = BLOCK_END (b);
1259   while (1)
1260     {
1261       if (GET_CODE (insn) != NOTE)
1262         if (++insn_count > max_uid)
1263           abort ();
1264       if (insn == BLOCK_HEAD (b))
1265         break;
1266       insn = PREV_INSN (insn);
1267     }
1268
1269   /* +2 to leave room for a post_mark_life at the last insn and for
1270      the birth of a CLOBBER in the first insn.  */
1271   regs_live_at = (HARD_REG_SET *) xcalloc ((2 * insn_count + 2),
1272                                            sizeof (HARD_REG_SET));
1273
1274   /* Initialize table of hardware registers currently live.  */
1275
1276   REG_SET_TO_HARD_REG_SET (regs_live, BASIC_BLOCK (b)->global_live_at_start);
1277
1278   /* This loop scans the instructions of the basic block
1279      and assigns quantities to registers.
1280      It computes which registers to tie.  */
1281
1282   insn = BLOCK_HEAD (b);
1283   while (1)
1284     {
1285       if (GET_CODE (insn) != NOTE)
1286         insn_number++;
1287
1288       if (INSN_P (insn))
1289         {
1290           register rtx link, set;
1291           register int win = 0;
1292           register rtx r0, r1 = NULL_RTX;
1293           int combined_regno = -1;
1294           int i;
1295
1296           this_insn_number = insn_number;
1297           this_insn = insn;
1298
1299           extract_insn (insn);
1300           which_alternative = -1;
1301
1302           /* Is this insn suitable for tying two registers?
1303              If so, try doing that.
1304              Suitable insns are those with at least two operands and where
1305              operand 0 is an output that is a register that is not
1306              earlyclobber.
1307
1308              We can tie operand 0 with some operand that dies in this insn.
1309              First look for operands that are required to be in the same
1310              register as operand 0.  If we find such, only try tying that
1311              operand or one that can be put into that operand if the
1312              operation is commutative.  If we don't find an operand
1313              that is required to be in the same register as operand 0,
1314              we can tie with any operand.
1315
1316              Subregs in place of regs are also ok.
1317
1318              If tying is done, WIN is set nonzero.  */
1319
1320           if (optimize
1321               && recog_data.n_operands > 1
1322               && recog_data.constraints[0][0] == '='
1323               && recog_data.constraints[0][1] != '&')
1324             {
1325               /* If non-negative, is an operand that must match operand 0.  */
1326               int must_match_0 = -1;
1327               /* Counts number of alternatives that require a match with
1328                  operand 0.  */
1329               int n_matching_alts = 0;
1330
1331               for (i = 1; i < recog_data.n_operands; i++)
1332                 {
1333                   const char *p = recog_data.constraints[i];
1334                   int this_match = (requires_inout (p));
1335
1336                   n_matching_alts += this_match;
1337                   if (this_match == recog_data.n_alternatives)
1338                     must_match_0 = i;
1339                 }
1340
1341               r0 = recog_data.operand[0];
1342               for (i = 1; i < recog_data.n_operands; i++)
1343                 {
1344                   /* Skip this operand if we found an operand that
1345                      must match operand 0 and this operand isn't it
1346                      and can't be made to be it by commutativity.  */
1347
1348                   if (must_match_0 >= 0 && i != must_match_0
1349                       && ! (i == must_match_0 + 1
1350                             && recog_data.constraints[i-1][0] == '%')
1351                       && ! (i == must_match_0 - 1
1352                             && recog_data.constraints[i][0] == '%'))
1353                     continue;
1354
1355                   /* Likewise if each alternative has some operand that
1356                      must match operand zero.  In that case, skip any
1357                      operand that doesn't list operand 0 since we know that
1358                      the operand always conflicts with operand 0.  We
1359                      ignore commutatity in this case to keep things simple.  */
1360                   if (n_matching_alts == recog_data.n_alternatives
1361                       && 0 == requires_inout (recog_data.constraints[i]))
1362                     continue;
1363
1364                   r1 = recog_data.operand[i];
1365
1366                   /* If the operand is an address, find a register in it.
1367                      There may be more than one register, but we only try one
1368                      of them.  */
1369                   if (recog_data.constraints[i][0] == 'p')
1370                     while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
1371                       r1 = XEXP (r1, 0);
1372
1373                   if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
1374                     {
1375                       /* We have two priorities for hard register preferences.
1376                          If we have a move insn or an insn whose first input
1377                          can only be in the same register as the output, give
1378                          priority to an equivalence found from that insn.  */
1379                       int may_save_copy
1380                         = (r1 == recog_data.operand[i] && must_match_0 >= 0);
1381
1382                       if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1383                         win = combine_regs (r1, r0, may_save_copy,
1384                                             insn_number, insn, 0);
1385                     }
1386                   if (win)
1387                     break;
1388                 }
1389             }
1390
1391           /* Recognize an insn sequence with an ultimate result
1392              which can safely overlap one of the inputs.
1393              The sequence begins with a CLOBBER of its result,
1394              and ends with an insn that copies the result to itself
1395              and has a REG_EQUAL note for an equivalent formula.
1396              That note indicates what the inputs are.
1397              The result and the input can overlap if each insn in
1398              the sequence either doesn't mention the input
1399              or has a REG_NO_CONFLICT note to inhibit the conflict.
1400
1401              We do the combining test at the CLOBBER so that the
1402              destination register won't have had a quantity number
1403              assigned, since that would prevent combining.  */
1404
1405           if (optimize
1406               && GET_CODE (PATTERN (insn)) == CLOBBER
1407               && (r0 = XEXP (PATTERN (insn), 0),
1408                   GET_CODE (r0) == REG)
1409               && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1410               && XEXP (link, 0) != 0
1411               && GET_CODE (XEXP (link, 0)) == INSN
1412               && (set = single_set (XEXP (link, 0))) != 0
1413               && SET_DEST (set) == r0 && SET_SRC (set) == r0
1414               && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
1415                                         NULL_RTX)) != 0)
1416             {
1417               if (r1 = XEXP (note, 0), GET_CODE (r1) == REG
1418                   /* Check that we have such a sequence.  */
1419                   && no_conflict_p (insn, r0, r1))
1420                 win = combine_regs (r1, r0, 1, insn_number, insn, 1);
1421               else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
1422                        && (r1 = XEXP (XEXP (note, 0), 0),
1423                            GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1424                        && no_conflict_p (insn, r0, r1))
1425                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1426
1427               /* Here we care if the operation to be computed is
1428                  commutative.  */
1429               else if ((GET_CODE (XEXP (note, 0)) == EQ
1430                         || GET_CODE (XEXP (note, 0)) == NE
1431                         || GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c')
1432                        && (r1 = XEXP (XEXP (note, 0), 1),
1433                            (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
1434                        && no_conflict_p (insn, r0, r1))
1435                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1436
1437               /* If we did combine something, show the register number
1438                  in question so that we know to ignore its death.  */
1439               if (win)
1440                 no_conflict_combined_regno = REGNO (r1);
1441             }
1442
1443           /* If registers were just tied, set COMBINED_REGNO
1444              to the number of the register used in this insn
1445              that was tied to the register set in this insn.
1446              This register's qty should not be "killed".  */
1447
1448           if (win)
1449             {
1450               while (GET_CODE (r1) == SUBREG)
1451                 r1 = SUBREG_REG (r1);
1452               combined_regno = REGNO (r1);
1453             }
1454
1455           /* Mark the death of everything that dies in this instruction,
1456              except for anything that was just combined.  */
1457
1458           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1459             if (REG_NOTE_KIND (link) == REG_DEAD
1460                 && GET_CODE (XEXP (link, 0)) == REG
1461                 && combined_regno != (int) REGNO (XEXP (link, 0))
1462                 && (no_conflict_combined_regno != (int) REGNO (XEXP (link, 0))
1463                     || ! find_reg_note (insn, REG_NO_CONFLICT,
1464                                         XEXP (link, 0))))
1465               wipe_dead_reg (XEXP (link, 0), 0);
1466
1467           /* Allocate qty numbers for all registers local to this block
1468              that are born (set) in this instruction.
1469              A pseudo that already has a qty is not changed.  */
1470
1471           note_stores (PATTERN (insn), reg_is_set, NULL);
1472
1473           /* If anything is set in this insn and then unused, mark it as dying
1474              after this insn, so it will conflict with our outputs.  This
1475              can't match with something that combined, and it doesn't matter
1476              if it did.  Do this after the calls to reg_is_set since these
1477              die after, not during, the current insn.  */
1478
1479           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1480             if (REG_NOTE_KIND (link) == REG_UNUSED
1481                 && GET_CODE (XEXP (link, 0)) == REG)
1482               wipe_dead_reg (XEXP (link, 0), 1);
1483
1484           /* If this is an insn that has a REG_RETVAL note pointing at a
1485              CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
1486              block, so clear any register number that combined within it.  */
1487           if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
1488               && GET_CODE (XEXP (note, 0)) == INSN
1489               && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
1490             no_conflict_combined_regno = -1;
1491         }
1492
1493       /* Set the registers live after INSN_NUMBER.  Note that we never
1494          record the registers live before the block's first insn, since no
1495          pseudos we care about are live before that insn.  */
1496
1497       IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
1498       IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
1499
1500       if (insn == BLOCK_END (b))
1501         break;
1502
1503       insn = NEXT_INSN (insn);
1504     }
1505
1506   /* Now every register that is local to this basic block
1507      should have been given a quantity, or else -1 meaning ignore it.
1508      Every quantity should have a known birth and death.
1509
1510      Order the qtys so we assign them registers in order of the
1511      number of suggested registers they need so we allocate those with
1512      the most restrictive needs first.  */
1513
1514   qty_order = (int *) xmalloc (next_qty * sizeof (int));
1515   for (i = 0; i < next_qty; i++)
1516     qty_order[i] = i;
1517
1518 #define EXCHANGE(I1, I2)  \
1519   { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1520
1521   switch (next_qty)
1522     {
1523     case 3:
1524       /* Make qty_order[2] be the one to allocate last.  */
1525       if (qty_sugg_compare (0, 1) > 0)
1526         EXCHANGE (0, 1);
1527       if (qty_sugg_compare (1, 2) > 0)
1528         EXCHANGE (2, 1);
1529
1530       /* ... Fall through ...  */
1531     case 2:
1532       /* Put the best one to allocate in qty_order[0].  */
1533       if (qty_sugg_compare (0, 1) > 0)
1534         EXCHANGE (0, 1);
1535
1536       /* ... Fall through ...  */
1537
1538     case 1:
1539     case 0:
1540       /* Nothing to do here.  */
1541       break;
1542
1543     default:
1544       qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
1545     }
1546
1547   /* Try to put each quantity in a suggested physical register, if it has one.
1548      This may cause registers to be allocated that otherwise wouldn't be, but
1549      this seems acceptable in local allocation (unlike global allocation).  */
1550   for (i = 0; i < next_qty; i++)
1551     {
1552       q = qty_order[i];
1553       if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
1554         qty[q].phys_reg = find_free_reg (qty[q].min_class, qty[q].mode, q,
1555                                          0, 1, qty[q].birth, qty[q].death);
1556       else
1557         qty[q].phys_reg = -1;
1558     }
1559
1560   /* Order the qtys so we assign them registers in order of
1561      decreasing length of life.  Normally call qsort, but if we
1562      have only a very small number of quantities, sort them ourselves.  */
1563
1564   for (i = 0; i < next_qty; i++)
1565     qty_order[i] = i;
1566
1567 #define EXCHANGE(I1, I2)  \
1568   { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1569
1570   switch (next_qty)
1571     {
1572     case 3:
1573       /* Make qty_order[2] be the one to allocate last.  */
1574       if (qty_compare (0, 1) > 0)
1575         EXCHANGE (0, 1);
1576       if (qty_compare (1, 2) > 0)
1577         EXCHANGE (2, 1);
1578
1579       /* ... Fall through ...  */
1580     case 2:
1581       /* Put the best one to allocate in qty_order[0].  */
1582       if (qty_compare (0, 1) > 0)
1583         EXCHANGE (0, 1);
1584
1585       /* ... Fall through ...  */
1586
1587     case 1:
1588     case 0:
1589       /* Nothing to do here.  */
1590       break;
1591
1592     default:
1593       qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
1594     }
1595
1596   /* Now for each qty that is not a hardware register,
1597      look for a hardware register to put it in.
1598      First try the register class that is cheapest for this qty,
1599      if there is more than one class.  */
1600
1601   for (i = 0; i < next_qty; i++)
1602     {
1603       q = qty_order[i];
1604       if (qty[q].phys_reg < 0)
1605         {
1606 #ifdef INSN_SCHEDULING
1607           /* These values represent the adjusted lifetime of a qty so
1608              that it conflicts with qtys which appear near the start/end
1609              of this qty's lifetime.
1610
1611              The purpose behind extending the lifetime of this qty is to
1612              discourage the register allocator from creating false
1613              dependencies.
1614
1615              The adjustment value is choosen to indicate that this qty
1616              conflicts with all the qtys in the instructions immediately
1617              before and after the lifetime of this qty.
1618
1619              Experiments have shown that higher values tend to hurt
1620              overall code performance.
1621
1622              If allocation using the extended lifetime fails we will try
1623              again with the qty's unadjusted lifetime.  */
1624           int fake_birth = MAX (0, qty[q].birth - 2 + qty[q].birth % 2);
1625           int fake_death = MIN (insn_number * 2 + 1,
1626                                 qty[q].death + 2 - qty[q].death % 2);
1627 #endif
1628
1629           if (N_REG_CLASSES > 1)
1630             {
1631 #ifdef INSN_SCHEDULING
1632               /* We try to avoid using hard registers allocated to qtys which
1633                  are born immediately after this qty or die immediately before
1634                  this qty.
1635
1636                  This optimization is only appropriate when we will run
1637                  a scheduling pass after reload and we are not optimizing
1638                  for code size.  */
1639               if (flag_schedule_insns_after_reload
1640                   && !optimize_size
1641                   && !SMALL_REGISTER_CLASSES)
1642                 {
1643                   qty[q].phys_reg = find_free_reg (qty[q].min_class,
1644                                                    qty[q].mode, q, 0, 0,
1645                                                    fake_birth, fake_death);
1646                   if (qty[q].phys_reg >= 0)
1647                     continue;
1648                 }
1649 #endif
1650               qty[q].phys_reg = find_free_reg (qty[q].min_class,
1651                                                qty[q].mode, q, 0, 0,
1652                                                qty[q].birth, qty[q].death);
1653               if (qty[q].phys_reg >= 0)
1654                 continue;
1655             }
1656
1657 #ifdef INSN_SCHEDULING
1658           /* Similarly, avoid false dependencies.  */
1659           if (flag_schedule_insns_after_reload
1660               && !optimize_size
1661               && !SMALL_REGISTER_CLASSES
1662               && qty[q].alternate_class != NO_REGS)
1663             qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
1664                                              qty[q].mode, q, 0, 0,
1665                                              fake_birth, fake_death);
1666 #endif
1667           if (qty[q].alternate_class != NO_REGS)
1668             qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
1669                                              qty[q].mode, q, 0, 0,
1670                                              qty[q].birth, qty[q].death);
1671         }
1672     }
1673
1674   /* Now propagate the register assignments
1675      to the pseudo regs belonging to the qtys.  */
1676
1677   for (q = 0; q < next_qty; q++)
1678     if (qty[q].phys_reg >= 0)
1679       {
1680         for (i = qty[q].first_reg; i >= 0; i = reg_next_in_qty[i])
1681           reg_renumber[i] = qty[q].phys_reg + reg_offset[i];
1682       }
1683
1684   /* Clean up.  */
1685   free (regs_live_at);
1686   free (qty_order);
1687 }
1688 \f
1689 /* Compare two quantities' priority for getting real registers.
1690    We give shorter-lived quantities higher priority.
1691    Quantities with more references are also preferred, as are quantities that
1692    require multiple registers.  This is the identical prioritization as
1693    done by global-alloc.
1694
1695    We used to give preference to registers with *longer* lives, but using
1696    the same algorithm in both local- and global-alloc can speed up execution
1697    of some programs by as much as a factor of three!  */
1698
1699 /* Note that the quotient will never be bigger than
1700    the value of floor_log2 times the maximum number of
1701    times a register can occur in one insn (surely less than 100)
1702    weighted by frequency (max REG_FREQ_MAX).
1703    Multiplying this by 10000/REG_FREQ_MAX can't overflow.
1704    QTY_CMP_PRI is also used by qty_sugg_compare.  */
1705
1706 #define QTY_CMP_PRI(q)          \
1707   ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \
1708           / (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX)))
1709
1710 static int
1711 qty_compare (q1, q2)
1712      int q1, q2;
1713 {
1714   return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1715 }
1716
1717 static int
1718 qty_compare_1 (q1p, q2p)
1719      const PTR q1p;
1720      const PTR q2p;
1721 {
1722   register int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
1723   register int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1724
1725   if (tem != 0)
1726     return tem;
1727
1728   /* If qtys are equally good, sort by qty number,
1729      so that the results of qsort leave nothing to chance.  */
1730   return q1 - q2;
1731 }
1732 \f
1733 /* Compare two quantities' priority for getting real registers.  This version
1734    is called for quantities that have suggested hard registers.  First priority
1735    goes to quantities that have copy preferences, then to those that have
1736    normal preferences.  Within those groups, quantities with the lower
1737    number of preferences have the highest priority.  Of those, we use the same
1738    algorithm as above.  */
1739
1740 #define QTY_CMP_SUGG(q)         \
1741   (qty_phys_num_copy_sugg[q]            \
1742     ? qty_phys_num_copy_sugg[q] \
1743     : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER)
1744
1745 static int
1746 qty_sugg_compare (q1, q2)
1747      int q1, q2;
1748 {
1749   register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1750
1751   if (tem != 0)
1752     return tem;
1753
1754   return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1755 }
1756
1757 static int
1758 qty_sugg_compare_1 (q1p, q2p)
1759      const PTR q1p;
1760      const PTR q2p;
1761 {
1762   register int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
1763   register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1764
1765   if (tem != 0)
1766     return tem;
1767
1768   tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1769   if (tem != 0)
1770     return tem;
1771
1772   /* If qtys are equally good, sort by qty number,
1773      so that the results of qsort leave nothing to chance.  */
1774   return q1 - q2;
1775 }
1776
1777 #undef QTY_CMP_SUGG
1778 #undef QTY_CMP_PRI
1779 \f
1780 /* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
1781    Returns 1 if have done so, or 0 if cannot.
1782
1783    Combining registers means marking them as having the same quantity
1784    and adjusting the offsets within the quantity if either of
1785    them is a SUBREG).
1786
1787    We don't actually combine a hard reg with a pseudo; instead
1788    we just record the hard reg as the suggestion for the pseudo's quantity.
1789    If we really combined them, we could lose if the pseudo lives
1790    across an insn that clobbers the hard reg (eg, movstr).
1791
1792    ALREADY_DEAD is non-zero if USEDREG is known to be dead even though
1793    there is no REG_DEAD note on INSN.  This occurs during the processing
1794    of REG_NO_CONFLICT blocks.
1795
1796    MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to
1797    SETREG or if the input and output must share a register.
1798    In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
1799
1800    There are elaborate checks for the validity of combining.  */
1801
1802 static int
1803 combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead)
1804      rtx usedreg, setreg;
1805      int may_save_copy;
1806      int insn_number;
1807      rtx insn;
1808      int already_dead;
1809 {
1810   register int ureg, sreg;
1811   register int offset = 0;
1812   int usize, ssize;
1813   register int sqty;
1814
1815   /* Determine the numbers and sizes of registers being used.  If a subreg
1816      is present that does not change the entire register, don't consider
1817      this a copy insn.  */
1818
1819   while (GET_CODE (usedreg) == SUBREG)
1820     {
1821       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD)
1822         may_save_copy = 0;
1823       if (REGNO (SUBREG_REG (usedreg)) < FIRST_PSEUDO_REGISTER)
1824         offset += subreg_regno_offset (REGNO (SUBREG_REG (usedreg)),
1825                                        GET_MODE (SUBREG_REG (usedreg)),
1826                                        SUBREG_BYTE (usedreg),
1827                                        GET_MODE (usedreg));
1828       else
1829         offset += (SUBREG_BYTE (usedreg)
1830                    / REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
1831       usedreg = SUBREG_REG (usedreg);
1832     }
1833   if (GET_CODE (usedreg) != REG)
1834     return 0;
1835   ureg = REGNO (usedreg);
1836   if (ureg < FIRST_PSEUDO_REGISTER)
1837     usize = HARD_REGNO_NREGS (ureg, GET_MODE (usedreg));
1838   else
1839     usize = ((GET_MODE_SIZE (GET_MODE (usedreg))
1840               + (REGMODE_NATURAL_SIZE (GET_MODE (usedreg)) - 1))
1841              / REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
1842
1843   while (GET_CODE (setreg) == SUBREG)
1844     {
1845       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD)
1846         may_save_copy = 0;
1847       if (REGNO (SUBREG_REG (setreg)) < FIRST_PSEUDO_REGISTER)
1848         offset -= subreg_regno_offset (REGNO (SUBREG_REG (setreg)),
1849                                        GET_MODE (SUBREG_REG (setreg)),
1850                                        SUBREG_BYTE (setreg),
1851                                        GET_MODE (setreg));
1852       else
1853         offset -= (SUBREG_BYTE (setreg)
1854                    / REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
1855       setreg = SUBREG_REG (setreg);
1856     }
1857   if (GET_CODE (setreg) != REG)
1858     return 0;
1859   sreg = REGNO (setreg);
1860   if (sreg < FIRST_PSEUDO_REGISTER)
1861     ssize = HARD_REGNO_NREGS (sreg, GET_MODE (setreg));
1862   else
1863     ssize = ((GET_MODE_SIZE (GET_MODE (setreg))
1864               + (REGMODE_NATURAL_SIZE (GET_MODE (setreg)) - 1))
1865              / REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
1866
1867   /* If UREG is a pseudo-register that hasn't already been assigned a
1868      quantity number, it means that it is not local to this block or dies
1869      more than once.  In either event, we can't do anything with it.  */
1870   if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
1871       /* Do not combine registers unless one fits within the other.  */
1872       || (offset > 0 && usize + offset > ssize)
1873       || (offset < 0 && usize + offset < ssize)
1874       /* Do not combine with a smaller already-assigned object
1875          if that smaller object is already combined with something bigger.  */
1876       || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
1877           && usize < qty[reg_qty[ureg]].size)
1878       /* Can't combine if SREG is not a register we can allocate.  */
1879       || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
1880       /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
1881          These have already been taken care of.  This probably wouldn't
1882          combine anyway, but don't take any chances.  */
1883       || (ureg >= FIRST_PSEUDO_REGISTER
1884           && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
1885       /* Don't tie something to itself.  In most cases it would make no
1886          difference, but it would screw up if the reg being tied to itself
1887          also dies in this insn.  */
1888       || ureg == sreg
1889       /* Don't try to connect two different hardware registers.  */
1890       || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
1891       /* Don't connect two different machine modes if they have different
1892          implications as to which registers may be used.  */
1893       || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
1894     return 0;
1895
1896   /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
1897      qty_phys_sugg for the pseudo instead of tying them.
1898
1899      Return "failure" so that the lifespan of UREG is terminated here;
1900      that way the two lifespans will be disjoint and nothing will prevent
1901      the pseudo reg from being given this hard reg.  */
1902
1903   if (ureg < FIRST_PSEUDO_REGISTER)
1904     {
1905       /* Allocate a quantity number so we have a place to put our
1906          suggestions.  */
1907       if (reg_qty[sreg] == -2)
1908         reg_is_born (setreg, 2 * insn_number);
1909
1910       if (reg_qty[sreg] >= 0)
1911         {
1912           if (may_save_copy
1913               && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
1914             {
1915               SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
1916               qty_phys_num_copy_sugg[reg_qty[sreg]]++;
1917             }
1918           else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
1919             {
1920               SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
1921               qty_phys_num_sugg[reg_qty[sreg]]++;
1922             }
1923         }
1924       return 0;
1925     }
1926
1927   /* Similarly for SREG a hard register and UREG a pseudo register.  */
1928
1929   if (sreg < FIRST_PSEUDO_REGISTER)
1930     {
1931       if (may_save_copy
1932           && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
1933         {
1934           SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
1935           qty_phys_num_copy_sugg[reg_qty[ureg]]++;
1936         }
1937       else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
1938         {
1939           SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
1940           qty_phys_num_sugg[reg_qty[ureg]]++;
1941         }
1942       return 0;
1943     }
1944
1945   /* At this point we know that SREG and UREG are both pseudos.
1946      Do nothing if SREG already has a quantity or is a register that we
1947      don't allocate.  */
1948   if (reg_qty[sreg] >= -1
1949       /* If we are not going to let any regs live across calls,
1950          don't tie a call-crossing reg to a non-call-crossing reg.  */
1951       || (current_function_has_nonlocal_label
1952           && ((REG_N_CALLS_CROSSED (ureg) > 0)
1953               != (REG_N_CALLS_CROSSED (sreg) > 0))))
1954     return 0;
1955
1956   /* We don't already know about SREG, so tie it to UREG
1957      if this is the last use of UREG, provided the classes they want
1958      are compatible.  */
1959
1960   if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
1961       && reg_meets_class_p (sreg, qty[reg_qty[ureg]].min_class))
1962     {
1963       /* Add SREG to UREG's quantity.  */
1964       sqty = reg_qty[ureg];
1965       reg_qty[sreg] = sqty;
1966       reg_offset[sreg] = reg_offset[ureg] + offset;
1967       reg_next_in_qty[sreg] = qty[sqty].first_reg;
1968       qty[sqty].first_reg = sreg;
1969
1970       /* If SREG's reg class is smaller, set qty[SQTY].min_class.  */
1971       update_qty_class (sqty, sreg);
1972
1973       /* Update info about quantity SQTY.  */
1974       qty[sqty].n_calls_crossed += REG_N_CALLS_CROSSED (sreg);
1975       qty[sqty].n_refs += REG_N_REFS (sreg);
1976       qty[sqty].freq += REG_FREQ (sreg);
1977       if (usize < ssize)
1978         {
1979           register int i;
1980
1981           for (i = qty[sqty].first_reg; i >= 0; i = reg_next_in_qty[i])
1982             reg_offset[i] -= offset;
1983
1984           qty[sqty].size = ssize;
1985           qty[sqty].mode = GET_MODE (setreg);
1986         }
1987     }
1988   else
1989     return 0;
1990
1991   return 1;
1992 }
1993 \f
1994 /* Return 1 if the preferred class of REG allows it to be tied
1995    to a quantity or register whose class is CLASS.
1996    True if REG's reg class either contains or is contained in CLASS.  */
1997
1998 static int
1999 reg_meets_class_p (reg, class)
2000      int reg;
2001      enum reg_class class;
2002 {
2003   register enum reg_class rclass = reg_preferred_class (reg);
2004   return (reg_class_subset_p (rclass, class)
2005           || reg_class_subset_p (class, rclass));
2006 }
2007
2008 /* Update the class of QTYNO assuming that REG is being tied to it.  */
2009
2010 static void
2011 update_qty_class (qtyno, reg)
2012      int qtyno;
2013      int reg;
2014 {
2015   enum reg_class rclass = reg_preferred_class (reg);
2016   if (reg_class_subset_p (rclass, qty[qtyno].min_class))
2017     qty[qtyno].min_class = rclass;
2018
2019   rclass = reg_alternate_class (reg);
2020   if (reg_class_subset_p (rclass, qty[qtyno].alternate_class))
2021     qty[qtyno].alternate_class = rclass;
2022
2023   if (REG_CHANGES_MODE (reg))
2024     qty[qtyno].changes_mode = 1;
2025 }
2026 \f
2027 /* Handle something which alters the value of an rtx REG.
2028
2029    REG is whatever is set or clobbered.  SETTER is the rtx that
2030    is modifying the register.
2031
2032    If it is not really a register, we do nothing.
2033    The file-global variables `this_insn' and `this_insn_number'
2034    carry info from `block_alloc'.  */
2035
2036 static void
2037 reg_is_set (reg, setter, data)
2038      rtx reg;
2039      rtx setter;
2040      void *data ATTRIBUTE_UNUSED;
2041 {
2042   /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
2043      a hard register.  These may actually not exist any more.  */
2044
2045   if (GET_CODE (reg) != SUBREG
2046       && GET_CODE (reg) != REG)
2047     return;
2048
2049   /* Mark this register as being born.  If it is used in a CLOBBER, mark
2050      it as being born halfway between the previous insn and this insn so that
2051      it conflicts with our inputs but not the outputs of the previous insn.  */
2052
2053   reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
2054 }
2055 \f
2056 /* Handle beginning of the life of register REG.
2057    BIRTH is the index at which this is happening.  */
2058
2059 static void
2060 reg_is_born (reg, birth)
2061      rtx reg;
2062      int birth;
2063 {
2064   register int regno;
2065
2066   if (GET_CODE (reg) == SUBREG)
2067     {
2068       regno = REGNO (SUBREG_REG (reg));
2069       if (regno < FIRST_PSEUDO_REGISTER)
2070         regno = subreg_hard_regno (reg, 1);
2071     }
2072   else
2073     regno = REGNO (reg);
2074
2075   if (regno < FIRST_PSEUDO_REGISTER)
2076     {
2077       mark_life (regno, GET_MODE (reg), 1);
2078
2079       /* If the register was to have been born earlier that the present
2080          insn, mark it as live where it is actually born.  */
2081       if (birth < 2 * this_insn_number)
2082         post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
2083     }
2084   else
2085     {
2086       if (reg_qty[regno] == -2)
2087         alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
2088
2089       /* If this register has a quantity number, show that it isn't dead.  */
2090       if (reg_qty[regno] >= 0)
2091         qty[reg_qty[regno]].death = -1;
2092     }
2093 }
2094
2095 /* Record the death of REG in the current insn.  If OUTPUT_P is non-zero,
2096    REG is an output that is dying (i.e., it is never used), otherwise it
2097    is an input (the normal case).
2098    If OUTPUT_P is 1, then we extend the life past the end of this insn.  */
2099
2100 static void
2101 wipe_dead_reg (reg, output_p)
2102      register rtx reg;
2103      int output_p;
2104 {
2105   register int regno = REGNO (reg);
2106
2107   /* If this insn has multiple results,
2108      and the dead reg is used in one of the results,
2109      extend its life to after this insn,
2110      so it won't get allocated together with any other result of this insn.
2111
2112      It is unsafe to use !single_set here since it will ignore an unused
2113      output.  Just because an output is unused does not mean the compiler
2114      can assume the side effect will not occur.   Consider if REG appears
2115      in the address of an output and we reload the output.  If we allocate
2116      REG to the same hard register as an unused output we could set the hard
2117      register before the output reload insn.  */
2118   if (GET_CODE (PATTERN (this_insn)) == PARALLEL
2119       && multiple_sets (this_insn))
2120     {
2121       int i;
2122       for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
2123         {
2124           rtx set = XVECEXP (PATTERN (this_insn), 0, i);
2125           if (GET_CODE (set) == SET
2126               && GET_CODE (SET_DEST (set)) != REG
2127               && !rtx_equal_p (reg, SET_DEST (set))
2128               && reg_overlap_mentioned_p (reg, SET_DEST (set)))
2129             output_p = 1;
2130         }
2131     }
2132
2133   /* If this register is used in an auto-increment address, then extend its
2134      life to after this insn, so that it won't get allocated together with
2135      the result of this insn.  */
2136   if (! output_p && find_regno_note (this_insn, REG_INC, regno))
2137     output_p = 1;
2138
2139   if (regno < FIRST_PSEUDO_REGISTER)
2140     {
2141       mark_life (regno, GET_MODE (reg), 0);
2142
2143       /* If a hard register is dying as an output, mark it as in use at
2144          the beginning of this insn (the above statement would cause this
2145          not to happen).  */
2146       if (output_p)
2147         post_mark_life (regno, GET_MODE (reg), 1,
2148                         2 * this_insn_number, 2 * this_insn_number + 1);
2149     }
2150
2151   else if (reg_qty[regno] >= 0)
2152     qty[reg_qty[regno]].death = 2 * this_insn_number + output_p;
2153 }
2154 \f
2155 /* Find a block of SIZE words of hard regs in reg_class CLASS
2156    that can hold something of machine-mode MODE
2157      (but actually we test only the first of the block for holding MODE)
2158    and still free between insn BORN_INDEX and insn DEAD_INDEX,
2159    and return the number of the first of them.
2160    Return -1 if such a block cannot be found.
2161    If QTYNO crosses calls, insist on a register preserved by calls,
2162    unless ACCEPT_CALL_CLOBBERED is nonzero.
2163
2164    If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested
2165    register is available.  If not, return -1.  */
2166
2167 static int
2168 find_free_reg (class, mode, qtyno, accept_call_clobbered, just_try_suggested,
2169                born_index, dead_index)
2170      enum reg_class class;
2171      enum machine_mode mode;
2172      int qtyno;
2173      int accept_call_clobbered;
2174      int just_try_suggested;
2175      int born_index, dead_index;
2176 {
2177   register int i, ins;
2178 #ifdef HARD_REG_SET
2179   /* Declare it register if it's a scalar.  */
2180   register
2181 #endif
2182     HARD_REG_SET used, first_used;
2183 #ifdef ELIMINABLE_REGS
2184   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
2185 #endif
2186
2187   /* Validate our parameters.  */
2188   if (born_index < 0 || born_index > dead_index)
2189     abort ();
2190
2191   /* Don't let a pseudo live in a reg across a function call
2192      if we might get a nonlocal goto.  */
2193   if (current_function_has_nonlocal_label
2194       && qty[qtyno].n_calls_crossed > 0)
2195     return -1;
2196
2197   if (accept_call_clobbered)
2198     COPY_HARD_REG_SET (used, call_fixed_reg_set);
2199   else if (qty[qtyno].n_calls_crossed == 0)
2200     COPY_HARD_REG_SET (used, fixed_reg_set);
2201   else
2202     COPY_HARD_REG_SET (used, call_used_reg_set);
2203
2204   if (accept_call_clobbered)
2205     IOR_HARD_REG_SET (used, losing_caller_save_reg_set);
2206
2207   for (ins = born_index; ins < dead_index; ins++)
2208     IOR_HARD_REG_SET (used, regs_live_at[ins]);
2209
2210   IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
2211
2212   /* Don't use the frame pointer reg in local-alloc even if
2213      we may omit the frame pointer, because if we do that and then we
2214      need a frame pointer, reload won't know how to move the pseudo
2215      to another hard reg.  It can move only regs made by global-alloc.
2216
2217      This is true of any register that can be eliminated.  */
2218 #ifdef ELIMINABLE_REGS
2219   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2220     SET_HARD_REG_BIT (used, eliminables[i].from);
2221 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2222   /* If FRAME_POINTER_REGNUM is not a real register, then protect the one
2223      that it might be eliminated into.  */
2224   SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
2225 #endif
2226 #else
2227   SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
2228 #endif
2229
2230 #ifdef CLASS_CANNOT_CHANGE_MODE
2231   if (qty[qtyno].changes_mode)
2232     IOR_HARD_REG_SET (used,
2233                       reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE]);
2234 #endif
2235
2236   /* Normally, the registers that can be used for the first register in
2237      a multi-register quantity are the same as those that can be used for
2238      subsequent registers.  However, if just trying suggested registers,
2239      restrict our consideration to them.  If there are copy-suggested
2240      register, try them.  Otherwise, try the arithmetic-suggested
2241      registers.  */
2242   COPY_HARD_REG_SET (first_used, used);
2243
2244   if (just_try_suggested)
2245     {
2246       if (qty_phys_num_copy_sugg[qtyno] != 0)
2247         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qtyno]);
2248       else
2249         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qtyno]);
2250     }
2251
2252   /* If all registers are excluded, we can't do anything.  */
2253   GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);
2254
2255   /* If at least one would be suitable, test each hard reg.  */
2256
2257   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2258     {
2259 #ifdef REG_ALLOC_ORDER
2260       int regno = reg_alloc_order[i];
2261 #else
2262       int regno = i;
2263 #endif
2264       if (! TEST_HARD_REG_BIT (first_used, regno)
2265           && HARD_REGNO_MODE_OK (regno, mode)
2266           && (qty[qtyno].n_calls_crossed == 0
2267               || accept_call_clobbered
2268               || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
2269         {
2270           register int j;
2271           register int size1 = HARD_REGNO_NREGS (regno, mode);
2272           for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
2273           if (j == size1)
2274             {
2275               /* Mark that this register is in use between its birth and death
2276                  insns.  */
2277               post_mark_life (regno, mode, 1, born_index, dead_index);
2278               return regno;
2279             }
2280 #ifndef REG_ALLOC_ORDER
2281           /* Skip starting points we know will lose.  */
2282           i += j;
2283 #endif
2284         }
2285     }
2286
2287  fail:
2288   /* If we are just trying suggested register, we have just tried copy-
2289      suggested registers, and there are arithmetic-suggested registers,
2290      try them.  */
2291
2292   /* If it would be profitable to allocate a call-clobbered register
2293      and save and restore it around calls, do that.  */
2294   if (just_try_suggested && qty_phys_num_copy_sugg[qtyno] != 0
2295       && qty_phys_num_sugg[qtyno] != 0)
2296     {
2297       /* Don't try the copy-suggested regs again.  */
2298       qty_phys_num_copy_sugg[qtyno] = 0;
2299       return find_free_reg (class, mode, qtyno, accept_call_clobbered, 1,
2300                             born_index, dead_index);
2301     }
2302
2303   /* We need not check to see if the current function has nonlocal
2304      labels because we don't put any pseudos that are live over calls in
2305      registers in that case.  */
2306
2307   if (! accept_call_clobbered
2308       && flag_caller_saves
2309       && ! just_try_suggested
2310       && qty[qtyno].n_calls_crossed != 0
2311       && CALLER_SAVE_PROFITABLE (qty[qtyno].n_refs,
2312                                  qty[qtyno].n_calls_crossed))
2313     {
2314       i = find_free_reg (class, mode, qtyno, 1, 0, born_index, dead_index);
2315       if (i >= 0)
2316         caller_save_needed = 1;
2317       return i;
2318     }
2319   return -1;
2320 }
2321 \f
2322 /* Mark that REGNO with machine-mode MODE is live starting from the current
2323    insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE
2324    is zero).  */
2325
2326 static void
2327 mark_life (regno, mode, life)
2328      register int regno;
2329      enum machine_mode mode;
2330      int life;
2331 {
2332   register int j = HARD_REGNO_NREGS (regno, mode);
2333   if (life)
2334     while (--j >= 0)
2335       SET_HARD_REG_BIT (regs_live, regno + j);
2336   else
2337     while (--j >= 0)
2338       CLEAR_HARD_REG_BIT (regs_live, regno + j);
2339 }
2340
2341 /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE
2342    is non-zero) or dead (if LIFE is zero) from insn number BIRTH (inclusive)
2343    to insn number DEATH (exclusive).  */
2344
2345 static void
2346 post_mark_life (regno, mode, life, birth, death)
2347      int regno;
2348      enum machine_mode mode;
2349      int life, birth, death;
2350 {
2351   register int j = HARD_REGNO_NREGS (regno, mode);
2352 #ifdef HARD_REG_SET
2353   /* Declare it register if it's a scalar.  */
2354   register
2355 #endif
2356     HARD_REG_SET this_reg;
2357
2358   CLEAR_HARD_REG_SET (this_reg);
2359   while (--j >= 0)
2360     SET_HARD_REG_BIT (this_reg, regno + j);
2361
2362   if (life)
2363     while (birth < death)
2364       {
2365         IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
2366         birth++;
2367       }
2368   else
2369     while (birth < death)
2370       {
2371         AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
2372         birth++;
2373       }
2374 }
2375 \f
2376 /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0
2377    is the register being clobbered, and R1 is a register being used in
2378    the equivalent expression.
2379
2380    If R1 dies in the block and has a REG_NO_CONFLICT note on every insn
2381    in which it is used, return 1.
2382
2383    Otherwise, return 0.  */
2384
2385 static int
2386 no_conflict_p (insn, r0, r1)
2387      rtx insn, r0 ATTRIBUTE_UNUSED, r1;
2388 {
2389   int ok = 0;
2390   rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
2391   rtx p, last;
2392
2393   /* If R1 is a hard register, return 0 since we handle this case
2394      when we scan the insns that actually use it.  */
2395
2396   if (note == 0
2397       || (GET_CODE (r1) == REG && REGNO (r1) < FIRST_PSEUDO_REGISTER)
2398       || (GET_CODE (r1) == SUBREG && GET_CODE (SUBREG_REG (r1)) == REG
2399           && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
2400     return 0;
2401
2402   last = XEXP (note, 0);
2403
2404   for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
2405     if (INSN_P (p))
2406       {
2407         if (find_reg_note (p, REG_DEAD, r1))
2408           ok = 1;
2409
2410         /* There must be a REG_NO_CONFLICT note on every insn, otherwise
2411            some earlier optimization pass has inserted instructions into
2412            the sequence, and it is not safe to perform this optimization.
2413            Note that emit_no_conflict_block always ensures that this is
2414            true when these sequences are created.  */
2415         if (! find_reg_note (p, REG_NO_CONFLICT, r1))
2416           return 0;
2417       }
2418
2419   return ok;
2420 }
2421 \f
2422 /* Return the number of alternatives for which the constraint string P
2423    indicates that the operand must be equal to operand 0 and that no register
2424    is acceptable.  */
2425
2426 static int
2427 requires_inout (p)
2428      const char *p;
2429 {
2430   char c;
2431   int found_zero = 0;
2432   int reg_allowed = 0;
2433   int num_matching_alts = 0;
2434
2435   while ((c = *p++))
2436     switch (c)
2437       {
2438       case '=':  case '+':  case '?':
2439       case '#':  case '&':  case '!':
2440       case '*':  case '%':
2441       case '1':  case '2':  case '3':  case '4': case '5':
2442       case '6':  case '7':  case '8':  case '9':
2443       case 'm':  case '<':  case '>':  case 'V':  case 'o':
2444       case 'E':  case 'F':  case 'G':  case 'H':
2445       case 's':  case 'i':  case 'n':
2446       case 'I':  case 'J':  case 'K':  case 'L':
2447       case 'M':  case 'N':  case 'O':  case 'P':
2448       case 'X':
2449         /* These don't say anything we care about.  */
2450         break;
2451
2452       case ',':
2453         if (found_zero && ! reg_allowed)
2454           num_matching_alts++;
2455
2456         found_zero = reg_allowed = 0;
2457         break;
2458
2459       case '0':
2460         found_zero = 1;
2461         break;
2462
2463       default:
2464         if (REG_CLASS_FROM_LETTER (c) == NO_REGS)
2465           break;
2466         /* FALLTHRU */
2467       case 'p':
2468       case 'g': case 'r':
2469         reg_allowed = 1;
2470         break;
2471       }
2472
2473   if (found_zero && ! reg_allowed)
2474     num_matching_alts++;
2475
2476   return num_matching_alts;
2477 }
2478 \f
2479 void
2480 dump_local_alloc (file)
2481      FILE *file;
2482 {
2483   register int i;
2484   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2485     if (reg_renumber[i] != -1)
2486       fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
2487 }