gcc/local-alloc.c

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