gcc/local-alloc.c

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