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           /* We can do the optimization.  Scan forward from INSN again,
 712              replacing regs as we go.  Set FAILED if a replacement can't
 713              be done.  In that case, we can't move the death note for SRC.
 714              This should be rare.  */
 715
 716           /* Set to stop at next insn.  */
 717           for (q = next_real_insn (insn);
 718                q != next_real_insn (p);
 719                q = next_real_insn (q))
 720             {
 721               if (reg_overlap_mentioned_p (src, PATTERN (q)))
 722                 {
 723                   /* If SRC is a hard register, we might miss some
 724                      overlapping registers with validate_replace_rtx,
 725                      so we would have to undo it.  We can't if DEST is
 726                      present in the insn, so fail in that combination
 727                      of cases.  */
 728                   if (sregno < FIRST_PSEUDO_REGISTER
 729                       && reg_mentioned_p (dest, PATTERN (q)))
 730                     failed = 1;
 731
 732                   /* Replace all uses and make sure that the register
 733                      isn't still present.  */
 734                   else if (validate_replace_rtx (src, dest, q)
 735                            && (sregno >= FIRST_PSEUDO_REGISTER
 736                                || ! reg_overlap_mentioned_p (src,
 737                                                              PATTERN (q))))
 738                     {
 739                       /* We assume that a register is used exactly once per
 740                          insn in the updates below.  If this is not correct,
 741                          no great harm is done.  */
 742                       if (sregno >= FIRST_PSEUDO_REGISTER)
 743                         reg_n_refs[sregno] -= loop_depth;
 744                       if (dregno >= FIRST_PSEUDO_REGISTER)
 745                         reg_n_refs[dregno] += loop_depth;
 746                     }
 747                   else
 748                     {
 749                       validate_replace_rtx (dest, src, q);
 750                       failed = 1;
 751                     }
 752                 }
 753
 754               /* Count the insns and CALL_INSNs passed.  If we passed the
 755                  death note of DEST, show increased live length.  */
 756               length++;
 757               if (dest_death)
 758                 d_length++;
 759
 760               if (GET_CODE (q) == CALL_INSN)
 761                 {
 762                   n_calls++;
 763                   if (dest_death)
 764                     d_n_calls++;
 765                 }
 766
 767               /* If DEST dies here, remove the death note and save it for
 768                  later.  Make sure ALL of DEST dies here; again, this is
 769                  overly conservative.  */
 770               if (dest_death == 0
 771                   && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0
 772                   && GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
 773                 remove_note (q, dest_death);
 774             }
 775
 776           if (! failed)
 777             {
 778               if (sregno >= FIRST_PSEUDO_REGISTER)
 779                 {
 780                   reg_live_length[sregno] -= length;
 781                   reg_n_calls_crossed[sregno] -= n_calls;
 782                 }
 783
 784               if (dregno >= FIRST_PSEUDO_REGISTER)
 785                 {
 786                   reg_live_length[dregno] += d_length;
 787                   reg_n_calls_crossed[dregno] += d_n_calls;
 788                 }
 789
 790               /* Move death note of SRC from P to INSN.  */
 791               remove_note (p, note);
 792               XEXP (note, 1) = REG_NOTES (insn);
 793               REG_NOTES (insn) = note;
 794             }
 795
 796           /* Put death note of DEST on P if we saw it die.  */
 797           if (dest_death)
 798             {
 799               XEXP (dest_death, 1) = REG_NOTES (p);
 800               REG_NOTES (p) = dest_death;
 801             }
 802
 803           return;
 804         }
 805
 806       /* If SRC is a hard register which is set or killed in some other
 807          way, we can't do this optimization.  */
 808       else if (sregno < FIRST_PSEUDO_REGISTER
 809                && dead_or_set_p (p, src))
 810         break;
 811     }
 812 }
 813 \f
 814 /* INSN is a copy of SRC to DEST, in which SRC dies.  See if we now have
 815    a sequence of insns that modify DEST followed by an insn that sets
 816    SRC to DEST in which DEST dies, with no prior modification of DEST.
 817    (There is no need to check if the insns in between actually modify
 818    DEST.  We should not have cases where DEST is not modified, but
 819    the optimization is safe if no such modification is detected.)
 820    In that case, we can replace all uses of DEST, starting with INSN and
 821    ending with the set of SRC to DEST, with SRC.  We do not do this
 822    optimization if a CALL_INSN is crossed unless SRC already crosses a
 823    call.
 824
 825    It is assumed that DEST and SRC are pseudos; it is too complicated to do
 826    this for hard registers since the substitutions we may make might fail.  */
 827
 828 static void
 829 optimize_reg_copy_2 (insn, dest, src)
 830      rtx insn;
 831      rtx dest;
 832      rtx src;
 833 {
 834   rtx p, q;
 835   rtx set;
 836   int sregno = REGNO (src);
 837   int dregno = REGNO (dest);
 838
 839   for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
 840     {
 841       if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
 842           || (GET_CODE (p) == NOTE
 843               && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
 844                   || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
 845         break;
 846
 847       if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
 848         continue;
 849
 850       set = single_set (p);
 851       if (set && SET_SRC (set) == dest && SET_DEST (set) == src
 852           && find_reg_note (p, REG_DEAD, dest))
 853         {
 854           /* We can do the optimization.  Scan forward from INSN again,
 855              replacing regs as we go.  */
 856
 857           /* Set to stop at next insn.  */
 858           for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q))
 859             if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
 860               {
 861                 if (reg_mentioned_p (dest, PATTERN (q)))
 862                   {
 863                     PATTERN (q) = replace_rtx (PATTERN (q), dest, src);
 864
 865                     /* We assume that a register is used exactly once per
 866                        insn in the updates below.  If this is not correct,
 867                        no great harm is done.  */
 868                     reg_n_refs[dregno] -= loop_depth;
 869                     reg_n_refs[sregno] += loop_depth;
 870                   }
 871
 872
 873               if (GET_CODE (q) == CALL_INSN)
 874                 {
 875                   reg_n_calls_crossed[dregno]--;
 876                   reg_n_calls_crossed[sregno]++;
 877                 }
 878               }
 879
 880           remove_note (p, find_reg_note (p, REG_DEAD, dest));
 881           reg_n_deaths[dregno]--;
 882           remove_note (insn, find_reg_note (insn, REG_DEAD, src));
 883           reg_n_deaths[sregno]--;
 884           return;
 885         }
 886
 887       if (reg_set_p (src, p)
 888           || (GET_CODE (p) == CALL_INSN && reg_n_calls_crossed[sregno] == 0))
 889         break;
 890     }
 891 }
 892 \f
 893 /* Find registers that are equivalent to a single value throughout the
 894    compilation (either because they can be referenced in memory or are set once
 895    from a single constant).  Lower their priority for a register.
 896
 897    If such a register is only referenced once, try substituting its value
 898    into the using insn.  If it succeeds, we can eliminate the register
 899    completely.  */
 900
 901 static void
 902 update_equiv_regs ()
 903 {
 904   rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *));
 905   rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
 906   rtx insn;
 907
 908   bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *));
 909   bzero (reg_equiv_replacement, max_regno * sizeof (rtx *));
 910
 911   init_alias_analysis ();
 912
 913   loop_depth = 1;
 914
 915   /* Scan the insns and find which registers have equivalences.  Do this
 916      in a separate scan of the insns because (due to -fcse-follow-jumps)
 917      a register can be set below its use.  */
 918   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 919     {
 920       rtx note;
 921       rtx set = single_set (insn);
 922       rtx dest;
 923       int regno;
 924
 925       if (GET_CODE (insn) == NOTE)
 926         {
 927           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
 928             loop_depth++;
 929           else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
 930             loop_depth--;
 931         }
 932
 933       /* If this insn contains more (or less) than a single SET, ignore it.  */
 934       if (set == 0)
 935         continue;
 936
 937       dest = SET_DEST (set);
 938
 939       /* If this sets a MEM to the contents of a REG that is only used
 940          in a single basic block, see if the register is always equivalent
 941          to that memory location and if moving the store from INSN to the
 942          insn that set REG is safe.  If so, put a REG_EQUIV note on the
 943          initializing insn.  */
 944
 945       if (GET_CODE (dest) == MEM && GET_CODE (SET_SRC (set)) == REG
 946           && (regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 947           && reg_basic_block[regno] >= 0
 948           && reg_equiv_init_insn[regno] != 0
 949           && validate_equiv_mem (reg_equiv_init_insn[regno], SET_SRC (set),
 950                                  dest)
 951           && ! memref_used_between_p (SET_DEST (set),
 952                                       reg_equiv_init_insn[regno], insn))
 953         REG_NOTES (reg_equiv_init_insn[regno])
 954           = gen_rtx (EXPR_LIST, REG_EQUIV, dest,
 955                      REG_NOTES (reg_equiv_init_insn[regno]));
 956
 957       /* If this is a register-register copy where SRC is not dead, see if we
 958          can optimize it.  */
 959       if (flag_expensive_optimizations && GET_CODE (dest) == REG
 960           && GET_CODE (SET_SRC (set)) == REG
 961           && ! find_reg_note (insn, REG_DEAD, SET_SRC (set)))
 962         optimize_reg_copy_1 (insn, dest, SET_SRC (set));
 963
 964       /* Similarly for a pseudo-pseudo copy when SRC is dead.  */
 965       else if (flag_expensive_optimizations && GET_CODE (dest) == REG
 966                && REGNO (dest) >= FIRST_PSEUDO_REGISTER
 967                && GET_CODE (SET_SRC (set)) == REG
 968                && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
 969                && find_reg_note (insn, REG_DEAD, SET_SRC (set)))
 970         optimize_reg_copy_2 (insn, dest, SET_SRC (set));
 971
 972       /* Otherwise, we only handle the case of a pseudo register being set
 973          once.  */
 974       if (GET_CODE (dest) != REG
 975           || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
 976           || reg_n_sets[regno] != 1)
 977         continue;
 978
 979       note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
 980
 981       /* Record this insn as initializing this register.  */
 982       reg_equiv_init_insn[regno] = insn;
 983
 984       /* If this register is known to be equal to a constant, record that
 985          it is always equivalent to the constant.  */
 986       if (note && CONSTANT_P (XEXP (note, 0)))
 987         PUT_MODE (note, (enum machine_mode) REG_EQUIV);
 988
 989       /* If this insn introduces a "constant" register, decrease the priority
 990          of that register.  Record this insn if the register is only used once
 991          more and the equivalence value is the same as our source.
 992
 993          The latter condition is checked for two reasons:  First, it is an
 994          indication that it may be more efficient to actually emit the insn
 995          as written (if no registers are available, reload will substitute
 996          the equivalence).  Secondly, it avoids problems with any registers
 997          dying in this insn whose death notes would be missed.
 998
 999          If we don't have a REG_EQUIV note, see if this insn is loading
1000          a register used only in one basic block from a MEM.  If so, and the
1001          MEM remains unchanged for the life of the register, add a REG_EQUIV
1002          note.  */
1003
1004       note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1005
1006       if (note == 0 && reg_basic_block[regno] >= 0
1007           && GET_CODE (SET_SRC (set)) == MEM
1008           && validate_equiv_mem (insn, dest, SET_SRC (set)))
1009         REG_NOTES (insn) = note = gen_rtx (EXPR_LIST, REG_EQUIV, SET_SRC (set),
1010                                            REG_NOTES (insn));
1011
1012       /* Don't mess with things live during setjmp.  */
1013       if (note && reg_live_length[regno] >= 0)
1014         {
1015           int regno = REGNO (dest);
1016
1017           /* Note that the statement below does not affect the priority
1018              in local-alloc!  */
1019           reg_live_length[regno] *= 2;
1020
1021           /* If the register is referenced exactly twice, meaning it is set
1022              once and used once, indicate that the reference may be replaced
1023              by the equivalence we computed above.  If the register is only
1024              used in one basic block, this can't succeed or combine would
1025              have done it.
1026
1027              It would be nice to use "loop_depth * 2" in the compare
1028              below.  Unfortunately, LOOP_DEPTH need not be constant within
1029              a basic block so this would be too complicated.
1030
1031              This case normally occurs when a parameter is read from memory
1032              and then used exactly once, not in a loop.  */
1033
1034           if (reg_n_refs[regno] == 2
1035               && reg_basic_block[regno] < 0
1036               && rtx_equal_p (XEXP (note, 0), SET_SRC (set)))
1037             reg_equiv_replacement[regno] = SET_SRC (set);
1038         }
1039     }
1040
1041   /* Now scan all regs killed in an insn to see if any of them are registers
1042      only used that once.  If so, see if we can replace the reference with
1043      the equivalent from.  If we can, delete the initializing reference
1044      and this register will go away.  */
1045   for (insn = next_active_insn (get_insns ());
1046        insn;
1047        insn = next_active_insn (insn))
1048     {
1049       rtx link;
1050
1051       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1052         if (REG_NOTE_KIND (link) == REG_DEAD
1053             /* Make sure this insn still refers to the register.  */
1054             && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
1055           {
1056             int regno = REGNO (XEXP (link, 0));
1057
1058             if (reg_equiv_replacement[regno]
1059                 && validate_replace_rtx (regno_reg_rtx[regno],
1060                                          reg_equiv_replacement[regno], insn))
1061               {
1062                 rtx equiv_insn = reg_equiv_init_insn[regno];
1063
1064                 remove_death (regno, insn);
1065                 reg_n_refs[regno] = 0;
1066                 PUT_CODE (equiv_insn, NOTE);
1067                 NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
1068                 NOTE_SOURCE_FILE (equiv_insn) = 0;
1069               }
1070           }
1071     }
1072 }
1073 \f
1074 /* Allocate hard regs to the pseudo regs used only within block number B.
1075    Only the pseudos that die but once can be handled.  */
1076
1077 static void
1078 block_alloc (b)
1079      int b;
1080 {
1081   register int i, q;
1082   register rtx insn;
1083   rtx note;
1084   int insn_number = 0;
1085   int insn_count = 0;
1086   int max_uid = get_max_uid ();
1087   short *qty_order;
1088   int no_conflict_combined_regno = -1;
1089
1090   /* Count the instructions in the basic block.  */
1091
1092   insn = basic_block_end[b];
1093   while (1)
1094     {
1095       if (GET_CODE (insn) != NOTE)
1096         if (++insn_count > max_uid)
1097           abort ();
1098       if (insn == basic_block_head[b])
1099         break;
1100       insn = PREV_INSN (insn);
1101     }
1102
1103   /* +2 to leave room for a post_mark_life at the last insn and for
1104      the birth of a CLOBBER in the first insn.  */
1105   regs_live_at = (HARD_REG_SET *) alloca ((2 * insn_count + 2)
1106                                           * sizeof (HARD_REG_SET));
1107   bzero (regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));
1108
1109   /* Initialize table of hardware registers currently live.  */
1110
1111 #ifdef HARD_REG_SET
1112   regs_live = *basic_block_live_at_start[b];
1113 #else
1114   COPY_HARD_REG_SET (regs_live, basic_block_live_at_start[b]);
1115 #endif
1116
1117   /* This loop scans the instructions of the basic block
1118      and assigns quantities to registers.
1119      It computes which registers to tie.  */
1120
1121   insn = basic_block_head[b];
1122   while (1)
1123     {
1124       register rtx body = PATTERN (insn);
1125
1126       if (GET_CODE (insn) != NOTE)
1127         insn_number++;
1128
1129       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1130         {
1131           register rtx link, set;
1132           register int win = 0;
1133           register rtx r0, r1;
1134           int combined_regno = -1;
1135           int i;
1136           int insn_code_number = recog_memoized (insn);
1137
1138           this_insn_number = insn_number;
1139           this_insn = insn;
1140
1141           if (insn_code_number >= 0)
1142             insn_extract (insn);
1143           which_alternative = -1;
1144
1145           /* Is this insn suitable for tying two registers?
1146              If so, try doing that.
1147              Suitable insns are those with at least two operands and where
1148              operand 0 is an output that is a register that is not
1149              earlyclobber.
1150
1151              We can tie operand 0 with some operand that dies in this insn.
1152              First look for operands that are required to be in the same
1153              register as operand 0.  If we find such, only try tying that
1154              operand or one that can be put into that operand if the
1155              operation is commutative.  If we don't find an operand
1156              that is required to be in the same register as operand 0,
1157              we can tie with any operand.
1158
1159              Subregs in place of regs are also ok.
1160
1161              If tying is done, WIN is set nonzero.  */
1162
1163           if (insn_code_number >= 0
1164 #ifdef REGISTER_CONSTRAINTS
1165               && insn_n_operands[insn_code_number] > 1
1166               && insn_operand_constraint[insn_code_number][0][0] == '='
1167               && insn_operand_constraint[insn_code_number][0][1] != '&'
1168 #else
1169               && GET_CODE (PATTERN (insn)) == SET
1170               && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0])
1171 #endif
1172               )
1173             {
1174 #ifdef REGISTER_CONSTRAINTS
1175               int must_match_0 = -1;
1176
1177
1178               for (i = 1; i < insn_n_operands[insn_code_number]; i++)
1179                 if (requires_inout_p
1180                     (insn_operand_constraint[insn_code_number][i]))
1181                   must_match_0 = i;
1182 #endif
1183
1184               r0 = recog_operand[0];
1185               for (i = 1; i < insn_n_operands[insn_code_number]; i++)
1186                 {
1187 #ifdef REGISTER_CONSTRAINTS
1188                   /* Skip this operand if we found an operand that
1189                      must match operand 0 and this operand isn't it
1190                      and can't be made to be it by commutativity.  */
1191
1192                   if (must_match_0 >= 0 && i != must_match_0
1193                       && ! (i == must_match_0 + 1
1194                             && insn_operand_constraint[insn_code_number][i-1][0] == '%')
1195                       && ! (i == must_match_0 - 1
1196                             && insn_operand_constraint[insn_code_number][i][0] == '%'))
1197                     continue;
1198 #endif
1199
1200                   r1 = recog_operand[i];
1201
1202                   /* If the operand is an address, find a register in it.
1203                      There may be more than one register, but we only try one
1204                      of them.  */
1205                   if (
1206 #ifdef REGISTER_CONSTRAINTS
1207                       insn_operand_constraint[insn_code_number][i][0] == 'p'
1208 #else
1209                       insn_operand_address_p[insn_code_number][i]
1210 #endif
1211                       )
1212                     while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
1213                       r1 = XEXP (r1, 0);
1214
1215                   if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
1216                     {
1217                       /* We have two priorities for hard register preferences.
1218                          If we have a move insn or an insn whose first input
1219                          can only be in the same register as the output, give
1220                          priority to an equivalence found from that insn.  */
1221                       int may_save_copy
1222                         = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
1223 #ifdef REGISTER_CONSTRAINTS
1224                            || (r1 == recog_operand[i] && must_match_0 >= 0)
1225 #endif
1226                            );
1227
1228                       if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1229                         win = combine_regs (r1, r0, may_save_copy,
1230                                             insn_number, insn, 0);
1231                     }
1232                 }
1233             }
1234
1235           /* Recognize an insn sequence with an ultimate result
1236              which can safely overlap one of the inputs.
1237              The sequence begins with a CLOBBER of its result,
1238              and ends with an insn that copies the result to itself
1239              and has a REG_EQUAL note for an equivalent formula.
1240              That note indicates what the inputs are.
1241              The result and the input can overlap if each insn in
1242              the sequence either doesn't mention the input
1243              or has a REG_NO_CONFLICT note to inhibit the conflict.
1244
1245              We do the combining test at the CLOBBER so that the
1246              destination register won't have had a quantity number
1247              assigned, since that would prevent combining.  */
1248
1249           if (GET_CODE (PATTERN (insn)) == CLOBBER
1250               && (r0 = XEXP (PATTERN (insn), 0),
1251                   GET_CODE (r0) == REG)
1252               && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1253               && GET_CODE (XEXP (link, 0)) == INSN
1254               && (set = single_set (XEXP (link, 0))) != 0
1255               && SET_DEST (set) == r0 && SET_SRC (set) == r0
1256               && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
1257                                         NULL_RTX)) != 0)
1258             {
1259               if (r1 = XEXP (note, 0), GET_CODE (r1) == REG
1260                   /* Check that we have such a sequence.  */
1261                   && no_conflict_p (insn, r0, r1))
1262                 win = combine_regs (r1, r0, 1, insn_number, insn, 1);
1263               else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
1264                        && (r1 = XEXP (XEXP (note, 0), 0),
1265                            GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1266                        && no_conflict_p (insn, r0, r1))
1267                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1268
1269               /* Here we care if the operation to be computed is
1270                  commutative.  */
1271               else if ((GET_CODE (XEXP (note, 0)) == EQ
1272                         || GET_CODE (XEXP (note, 0)) == NE
1273                         || GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c')
1274                        && (r1 = XEXP (XEXP (note, 0), 1),
1275                            (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
1276                        && no_conflict_p (insn, r0, r1))
1277                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1278
1279               /* If we did combine something, show the register number
1280                  in question so that we know to ignore its death.  */
1281               if (win)
1282                 no_conflict_combined_regno = REGNO (r1);
1283             }
1284
1285           /* If registers were just tied, set COMBINED_REGNO
1286              to the number of the register used in this insn
1287              that was tied to the register set in this insn.
1288              This register's qty should not be "killed".  */
1289
1290           if (win)
1291             {
1292               while (GET_CODE (r1) == SUBREG)
1293                 r1 = SUBREG_REG (r1);
1294               combined_regno = REGNO (r1);
1295             }
1296
1297           /* Mark the death of everything that dies in this instruction,
1298              except for anything that was just combined.  */
1299
1300           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1301             if (REG_NOTE_KIND (link) == REG_DEAD
1302                 && GET_CODE (XEXP (link, 0)) == REG
1303                 && combined_regno != REGNO (XEXP (link, 0))
1304                 && (no_conflict_combined_regno != REGNO (XEXP (link, 0))
1305                     || ! find_reg_note (insn, REG_NO_CONFLICT, XEXP (link, 0))))
1306               wipe_dead_reg (XEXP (link, 0), 0);
1307
1308           /* Allocate qty numbers for all registers local to this block
1309              that are born (set) in this instruction.
1310              A pseudo that already has a qty is not changed.  */
1311
1312           note_stores (PATTERN (insn), reg_is_set);
1313
1314           /* If anything is set in this insn and then unused, mark it as dying
1315              after this insn, so it will conflict with our outputs.  This
1316              can't match with something that combined, and it doesn't matter
1317              if it did.  Do this after the calls to reg_is_set since these
1318              die after, not during, the current insn.  */
1319
1320           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1321             if (REG_NOTE_KIND (link) == REG_UNUSED
1322                 && GET_CODE (XEXP (link, 0)) == REG)
1323               wipe_dead_reg (XEXP (link, 0), 1);
1324
1325 #ifndef SMALL_REGISTER_CLASSES
1326           /* Allocate quantities for any SCRATCH operands of this insn.  We
1327              don't do this for machines with small register classes because
1328              those machines can use registers explicitly mentioned in the
1329              RTL as spill registers and our usage of hard registers
1330              explicitly for SCRATCH operands will conflict.  On those machines,
1331              reload will allocate the SCRATCH.  */
1332
1333           if (insn_code_number >= 0)
1334             for (i = 0; i < insn_n_operands[insn_code_number]; i++)
1335               if (GET_CODE (recog_operand[i]) == SCRATCH)
1336                 alloc_qty_for_scratch (recog_operand[i], i, insn,
1337                                        insn_code_number, insn_number);
1338 #endif
1339
1340           /* If this is an insn that has a REG_RETVAL note pointing at a
1341              CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
1342              block, so clear any register number that combined within it.  */
1343           if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
1344               && GET_CODE (XEXP (note, 0)) == INSN
1345               && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
1346             no_conflict_combined_regno = -1;
1347         }
1348
1349       /* Set the registers live after INSN_NUMBER.  Note that we never
1350          record the registers live before the block's first insn, since no
1351          pseudos we care about are live before that insn.  */
1352
1353       IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
1354       IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
1355
1356       if (insn == basic_block_end[b])
1357         break;
1358
1359       insn = NEXT_INSN (insn);
1360     }
1361
1362   /* Now every register that is local to this basic block
1363      should have been given a quantity, or else -1 meaning ignore it.
1364      Every quantity should have a known birth and death.
1365
1366      Order the qtys so we assign them registers in order of
1367      decreasing length of life.  Normally call qsort, but if we
1368      have only a very small number of quantities, sort them ourselves.  */
1369
1370   qty_order = (short *) alloca (next_qty * sizeof (short));
1371   for (i = 0; i < next_qty; i++)
1372     qty_order[i] = i;
1373
1374 #define EXCHANGE(I1, I2)  \
1375   { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1376
1377   switch (next_qty)
1378     {
1379     case 3:
1380       /* Make qty_order[2] be the one to allocate last.  */
1381       if (qty_compare (0, 1) > 0)
1382         EXCHANGE (0, 1);
1383       if (qty_compare (1, 2) > 0)
1384         EXCHANGE (2, 1);
1385
1386       /* ... Fall through ... */
1387     case 2:
1388       /* Put the best one to allocate in qty_order[0].  */
1389       if (qty_compare (0, 1) > 0)
1390         EXCHANGE (0, 1);
1391
1392       /* ... Fall through ... */
1393
1394     case 1:
1395     case 0:
1396       /* Nothing to do here.  */
1397       break;
1398
1399     default:
1400       qsort (qty_order, next_qty, sizeof (short), qty_compare_1);
1401     }
1402
1403   /* Try to put each quantity in a suggested physical register, if it has one.
1404      This may cause registers to be allocated that otherwise wouldn't be, but
1405      this seems acceptable in local allocation (unlike global allocation).  */
1406   for (i = 0; i < next_qty; i++)
1407     {
1408       q = qty_order[i];
1409       if (qty_phys_has_sugg[q] || qty_phys_has_copy_sugg[q])
1410         qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q,
1411                                          0, 1, qty_birth[q], qty_death[q]);
1412       else
1413         qty_phys_reg[q] = -1;
1414     }
1415
1416   /* Now for each qty that is not a hardware register,
1417      look for a hardware register to put it in.
1418      First try the register class that is cheapest for this qty,
1419      if there is more than one class.  */
1420
1421   for (i = 0; i < next_qty; i++)
1422     {
1423       q = qty_order[i];
1424       if (qty_phys_reg[q] < 0)
1425         {
1426           if (N_REG_CLASSES > 1)
1427             {
1428               qty_phys_reg[q] = find_free_reg (qty_min_class[q],
1429                                                qty_mode[q], q, 0, 0,
1430                                                qty_birth[q], qty_death[q]);
1431               if (qty_phys_reg[q] >= 0)
1432                 continue;
1433             }
1434
1435           if (qty_alternate_class[q] != NO_REGS)
1436             qty_phys_reg[q] = find_free_reg (qty_alternate_class[q],
1437                                              qty_mode[q], q, 0, 0,
1438                                              qty_birth[q], qty_death[q]);
1439         }
1440     }
1441
1442   /* Now propagate the register assignments
1443      to the pseudo regs belonging to the qtys.  */
1444
1445   for (q = 0; q < next_qty; q++)
1446     if (qty_phys_reg[q] >= 0)
1447       {
1448         for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i])
1449           reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
1450         if (qty_scratch_rtx[q])
1451           {
1452             PUT_CODE (qty_scratch_rtx[q], REG);
1453             REGNO (qty_scratch_rtx[q]) = qty_phys_reg[q];
1454
1455             for (i = HARD_REGNO_NREGS (qty_phys_reg[q],
1456                                        GET_MODE (qty_scratch_rtx[q])) - 1;
1457                  i >= 0; i--)
1458               regs_ever_live[qty_phys_reg[q] + i] = 1;
1459
1460             /* Must clear the USED field, because it will have been set by
1461                copy_rtx_if_shared, but the leaf_register code expects that
1462                it is zero in all REG rtx.  copy_rtx_if_shared does not set the
1463                used bit for REGs, but does for SCRATCHes.  */
1464             qty_scratch_rtx[q]->used = 0;
1465           }
1466       }
1467 }
1468 \f
1469 /* Compare two quantities' priority for getting real registers.
1470    We give shorter-lived quantities higher priority.
1471    Quantities with more references are also preferred, as are quantities that
1472    require multiple registers.  This is the identical prioritization as
1473    done by global-alloc.
1474
1475    We used to give preference to registers with *longer* lives, but using
1476    the same algorithm in both local- and global-alloc can speed up execution
1477    of some programs by as much as a factor of three!  */
1478
1479 static int
1480 qty_compare (q1, q2)
1481      int q1, q2;
1482 {
1483   /* Note that the quotient will never be bigger than
1484      the value of floor_log2 times the maximum number of
1485      times a register can occur in one insn (surely less than 100).
1486      Multiplying this by 10000 can't overflow.  */
1487   register int pri1
1488     = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1])
1489         / ((qty_death[q1] - qty_birth[q1]) * qty_size[q1]))
1490        * 10000);
1491   register int pri2
1492     = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2])
1493         / ((qty_death[q2] - qty_birth[q2]) * qty_size[q2]))
1494        * 10000);
1495   return pri2 - pri1;
1496 }
1497
1498 static int
1499 qty_compare_1 (q1, q2)
1500      short *q1, *q2;
1501 {
1502   register int tem;
1503
1504   /* Note that the quotient will never be bigger than
1505      the value of floor_log2 times the maximum number of
1506      times a register can occur in one insn (surely less than 100).
1507      Multiplying this by 10000 can't overflow.  */
1508   register int pri1
1509     = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1])
1510         / ((qty_death[*q1] - qty_birth[*q1]) * qty_size[*q1]))
1511        * 10000);
1512   register int pri2
1513     = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2])
1514         / ((qty_death[*q2] - qty_birth[*q2]) * qty_size[*q2]))
1515        * 10000);
1516
1517   tem = pri2 - pri1;
1518   if (tem != 0) return tem;
1519   /* If qtys are equally good, sort by qty number,
1520      so that the results of qsort leave nothing to chance.  */
1521   return *q1 - *q2;
1522 }
1523 \f
1524 /* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
1525    Returns 1 if have done so, or 0 if cannot.
1526
1527    Combining registers means marking them as having the same quantity
1528    and adjusting the offsets within the quantity if either of
1529    them is a SUBREG).
1530
1531    We don't actually combine a hard reg with a pseudo; instead
1532    we just record the hard reg as the suggestion for the pseudo's quantity.
1533    If we really combined them, we could lose if the pseudo lives
1534    across an insn that clobbers the hard reg (eg, movstr).
1535
1536    ALREADY_DEAD is non-zero if USEDREG is known to be dead even though
1537    there is no REG_DEAD note on INSN.  This occurs during the processing
1538    of REG_NO_CONFLICT blocks.
1539
1540    MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to
1541    SETREG or if the input and output must share a register.
1542    In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
1543
1544    There are elaborate checks for the validity of combining.  */
1545
1546
1547 static int
1548 combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead)
1549      rtx usedreg, setreg;
1550      int may_save_copy;
1551      int insn_number;
1552      rtx insn;
1553      int already_dead;
1554 {
1555   register int ureg, sreg;
1556   register int offset = 0;
1557   int usize, ssize;
1558   register int sqty;
1559
1560   /* Determine the numbers and sizes of registers being used.  If a subreg
1561      is present that does not change the entire register, don't consider
1562      this a copy insn.  */
1563
1564   while (GET_CODE (usedreg) == SUBREG)
1565     {
1566       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD)
1567         may_save_copy = 0;
1568       offset += SUBREG_WORD (usedreg);
1569       usedreg = SUBREG_REG (usedreg);
1570     }
1571   if (GET_CODE (usedreg) != REG)
1572     return 0;
1573   ureg = REGNO (usedreg);
1574   usize = REG_SIZE (usedreg);
1575
1576   while (GET_CODE (setreg) == SUBREG)
1577     {
1578       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD)
1579         may_save_copy = 0;
1580       offset -= SUBREG_WORD (setreg);
1581       setreg = SUBREG_REG (setreg);
1582     }
1583   if (GET_CODE (setreg) != REG)
1584     return 0;
1585   sreg = REGNO (setreg);
1586   ssize = REG_SIZE (setreg);
1587
1588   /* If UREG is a pseudo-register that hasn't already been assigned a
1589      quantity number, it means that it is not local to this block or dies
1590      more than once.  In either event, we can't do anything with it.  */
1591   if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
1592       /* Do not combine registers unless one fits within the other.  */
1593       || (offset > 0 && usize + offset > ssize)
1594       || (offset < 0 && usize + offset < ssize)
1595       /* Do not combine with a smaller already-assigned object
1596          if that smaller object is already combined with something bigger. */
1597       || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
1598           && usize < qty_size[reg_qty[ureg]])
1599       /* Can't combine if SREG is not a register we can allocate.  */
1600       || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
1601       /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
1602          These have already been taken care of.  This probably wouldn't
1603          combine anyway, but don't take any chances.  */
1604       || (ureg >= FIRST_PSEUDO_REGISTER
1605           && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
1606       /* Don't tie something to itself.  In most cases it would make no
1607          difference, but it would screw up if the reg being tied to itself
1608          also dies in this insn.  */
1609       || ureg == sreg
1610       /* Don't try to connect two different hardware registers.  */
1611       || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
1612       /* Don't connect two different machine modes if they have different
1613          implications as to which registers may be used.  */
1614       || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
1615     return 0;
1616
1617   /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
1618      qty_phys_sugg for the pseudo instead of tying them.
1619
1620      Return "failure" so that the lifespan of UREG is terminated here;
1621      that way the two lifespans will be disjoint and nothing will prevent
1622      the pseudo reg from being given this hard reg.  */
1623
1624   if (ureg < FIRST_PSEUDO_REGISTER)
1625     {
1626       /* Allocate a quantity number so we have a place to put our
1627          suggestions.  */
1628       if (reg_qty[sreg] == -2)
1629         reg_is_born (setreg, 2 * insn_number);
1630
1631       if (reg_qty[sreg] >= 0)
1632         {
1633           if (may_save_copy)
1634             {
1635               SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
1636               qty_phys_has_copy_sugg[reg_qty[sreg]] = 1;
1637             }
1638           else
1639             {
1640               SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
1641               qty_phys_has_sugg[reg_qty[sreg]] = 1;
1642             }
1643         }
1644       return 0;
1645     }
1646
1647   /* Similarly for SREG a hard register and UREG a pseudo register.  */
1648
1649   if (sreg < FIRST_PSEUDO_REGISTER)
1650     {
1651       if (may_save_copy)
1652         {
1653           SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
1654           qty_phys_has_copy_sugg[reg_qty[ureg]] = 1;
1655         }
1656       else
1657         {
1658           SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
1659           qty_phys_has_sugg[reg_qty[ureg]] = 1;
1660         }
1661       return 0;
1662     }
1663
1664   /* At this point we know that SREG and UREG are both pseudos.
1665      Do nothing if SREG already has a quantity or is a register that we
1666      don't allocate.  */
1667   if (reg_qty[sreg] >= -1
1668       /* If we are not going to let any regs live across calls,
1669          don't tie a call-crossing reg to a non-call-crossing reg.  */
1670       || (current_function_has_nonlocal_label
1671           && ((reg_n_calls_crossed[ureg] > 0)
1672               != (reg_n_calls_crossed[sreg] > 0))))
1673     return 0;
1674
1675   /* We don't already know about SREG, so tie it to UREG
1676      if this is the last use of UREG, provided the classes they want
1677      are compatible.  */
1678
1679   if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
1680       && reg_meets_class_p (sreg, qty_min_class[reg_qty[ureg]]))
1681     {
1682       /* Add SREG to UREG's quantity.  */
1683       sqty = reg_qty[ureg];
1684       reg_qty[sreg] = sqty;
1685       reg_offset[sreg] = reg_offset[ureg] + offset;
1686       reg_next_in_qty[sreg] = qty_first_reg[sqty];
1687       qty_first_reg[sqty] = sreg;
1688
1689       /* If SREG's reg class is smaller, set qty_min_class[SQTY].  */
1690       update_qty_class (sqty, sreg);
1691
1692       /* Update info about quantity SQTY.  */
1693       qty_n_calls_crossed[sqty] += reg_n_calls_crossed[sreg];
1694       qty_n_refs[sqty] += reg_n_refs[sreg];
1695       if (usize < ssize)
1696         {
1697           register int i;
1698
1699           for (i = qty_first_reg[sqty]; i >= 0; i = reg_next_in_qty[i])
1700             reg_offset[i] -= offset;
1701
1702           qty_size[sqty] = ssize;
1703           qty_mode[sqty] = GET_MODE (setreg);
1704         }
1705     }
1706   else
1707     return 0;
1708
1709   return 1;
1710 }
1711 \f
1712 /* Return 1 if the preferred class of REG allows it to be tied
1713    to a quantity or register whose class is CLASS.
1714    True if REG's reg class either contains or is contained in CLASS.  */
1715
1716 static int
1717 reg_meets_class_p (reg, class)
1718      int reg;
1719      enum reg_class class;
1720 {
1721   register enum reg_class rclass = reg_preferred_class (reg);
1722   return (reg_class_subset_p (rclass, class)
1723           || reg_class_subset_p (class, rclass));
1724 }
1725
1726 /* Return 1 if the two specified classes have registers in common.
1727    If CALL_SAVED, then consider only call-saved registers.  */
1728
1729 static int
1730 reg_classes_overlap_p (c1, c2, call_saved)
1731      register enum reg_class c1;
1732      register enum reg_class c2;
1733      int call_saved;
1734 {
1735   HARD_REG_SET c;
1736   int i;
1737
1738   COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
1739   AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
1740
1741   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1742     if (TEST_HARD_REG_BIT (c, i)
1743         && (! call_saved || ! call_used_regs[i]))
1744       return 1;
1745
1746   return 0;
1747 }
1748
1749 /* Update the class of QTY assuming that REG is being tied to it.  */
1750
1751 static void
1752 update_qty_class (qty, reg)
1753      int qty;
1754      int reg;
1755 {
1756   enum reg_class rclass = reg_preferred_class (reg);
1757   if (reg_class_subset_p (rclass, qty_min_class[qty]))
1758     qty_min_class[qty] = rclass;
1759
1760   rclass = reg_alternate_class (reg);
1761   if (reg_class_subset_p (rclass, qty_alternate_class[qty]))
1762     qty_alternate_class[qty] = rclass;
1763 }
1764 \f
1765 /* Handle something which alters the value of an rtx REG.
1766
1767    REG is whatever is set or clobbered.  SETTER is the rtx that
1768    is modifying the register.
1769
1770    If it is not really a register, we do nothing.
1771    The file-global variables `this_insn' and `this_insn_number'
1772    carry info from `block_alloc'.  */
1773
1774 static void
1775 reg_is_set (reg, setter)
1776      rtx reg;
1777      rtx setter;
1778 {
1779   /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
1780      a hard register.  These may actually not exist any more.  */
1781
1782   if (GET_CODE (reg) != SUBREG
1783       && GET_CODE (reg) != REG)
1784     return;
1785
1786   /* Mark this register as being born.  If it is used in a CLOBBER, mark
1787      it as being born halfway between the previous insn and this insn so that
1788      it conflicts with our inputs but not the outputs of the previous insn.  */
1789
1790   reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
1791 }
1792 \f
1793 /* Handle beginning of the life of register REG.
1794    BIRTH is the index at which this is happening.  */
1795
1796 static void
1797 reg_is_born (reg, birth)
1798      rtx reg;
1799      int birth;
1800 {
1801   register int regno;
1802
1803   if (GET_CODE (reg) == SUBREG)
1804     regno = REGNO (SUBREG_REG (reg)) + SUBREG_WORD (reg);
1805   else
1806     regno = REGNO (reg);
1807
1808   if (regno < FIRST_PSEUDO_REGISTER)
1809     {
1810       mark_life (regno, GET_MODE (reg), 1);
1811
1812       /* If the register was to have been born earlier that the present
1813          insn, mark it as live where it is actually born.  */
1814       if (birth < 2 * this_insn_number)
1815         post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
1816     }
1817   else
1818     {
1819       if (reg_qty[regno] == -2)
1820         alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
1821
1822       /* If this register has a quantity number, show that it isn't dead.  */
1823       if (reg_qty[regno] >= 0)
1824         qty_death[reg_qty[regno]] = -1;
1825     }
1826 }
1827
1828 /* Record the death of REG in the current insn.  If OUTPUT_P is non-zero,
1829    REG is an output that is dying (i.e., it is never used), otherwise it
1830    is an input (the normal case).
1831    If OUTPUT_P is 1, then we extend the life past the end of this insn.  */
1832
1833 static void
1834 wipe_dead_reg (reg, output_p)
1835      register rtx reg;
1836      int output_p;
1837 {
1838   register int regno = REGNO (reg);
1839
1840   /* If this insn has multiple results,
1841      and the dead reg is used in one of the results,
1842      extend its life to after this insn,
1843      so it won't get allocated together with any other result of this insn.  */
1844   if (GET_CODE (PATTERN (this_insn)) == PARALLEL
1845       && !single_set (this_insn))
1846     {
1847       int i;
1848       for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
1849         {
1850           rtx set = XVECEXP (PATTERN (this_insn), 0, i);
1851           if (GET_CODE (set) == SET
1852               && GET_CODE (SET_DEST (set)) != REG
1853               && !rtx_equal_p (reg, SET_DEST (set))
1854               && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1855             output_p = 1;
1856         }
1857     }
1858
1859   if (regno < FIRST_PSEUDO_REGISTER)
1860     {
1861       mark_life (regno, GET_MODE (reg), 0);
1862
1863       /* If a hard register is dying as an output, mark it as in use at
1864          the beginning of this insn (the above statement would cause this
1865          not to happen).  */
1866       if (output_p)
1867         post_mark_life (regno, GET_MODE (reg), 1,
1868                         2 * this_insn_number, 2 * this_insn_number+ 1);
1869     }
1870
1871   else if (reg_qty[regno] >= 0)
1872     qty_death[reg_qty[regno]] = 2 * this_insn_number + output_p;
1873 }
1874 \f
1875 /* Find a block of SIZE words of hard regs in reg_class CLASS
1876    that can hold something of machine-mode MODE
1877      (but actually we test only the first of the block for holding MODE)
1878    and still free between insn BORN_INDEX and insn DEAD_INDEX,
1879    and return the number of the first of them.
1880    Return -1 if such a block cannot be found.
1881    If QTY crosses calls, insist on a register preserved by calls,
1882    unless ACCEPT_CALL_CLOBBERED is nonzero.
1883
1884    If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested
1885    register is available.  If not, return -1.  */
1886
1887 static int
1888 find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested,
1889                born_index, dead_index)
1890      enum reg_class class;
1891      enum machine_mode mode;
1892      int accept_call_clobbered;
1893      int just_try_suggested;
1894      int qty;
1895      int born_index, dead_index;
1896 {
1897   register int i, ins;
1898 #ifdef HARD_REG_SET
1899   register              /* Declare it register if it's a scalar.  */
1900 #endif
1901     HARD_REG_SET used, first_used;
1902 #ifdef ELIMINABLE_REGS
1903   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
1904 #endif
1905
1906   /* Validate our parameters.  */
1907   if (born_index < 0 || born_index > dead_index)
1908     abort ();
1909
1910   /* Don't let a pseudo live in a reg across a function call
1911      if we might get a nonlocal goto.  */
1912   if (current_function_has_nonlocal_label
1913       && qty_n_calls_crossed[qty] > 0)
1914     return -1;
1915
1916   if (accept_call_clobbered)
1917     COPY_HARD_REG_SET (used, call_fixed_reg_set);
1918   else if (qty_n_calls_crossed[qty] == 0)
1919     COPY_HARD_REG_SET (used, fixed_reg_set);
1920   else
1921     COPY_HARD_REG_SET (used, call_used_reg_set);
1922
1923   for (ins = born_index; ins < dead_index; ins++)
1924     IOR_HARD_REG_SET (used, regs_live_at[ins]);
1925
1926   IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
1927
1928   /* Don't use the frame pointer reg in local-alloc even if
1929      we may omit the frame pointer, because if we do that and then we
1930      need a frame pointer, reload won't know how to move the pseudo
1931      to another hard reg.  It can move only regs made by global-alloc.
1932
1933      This is true of any register that can be eliminated.  */
1934 #ifdef ELIMINABLE_REGS
1935   for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
1936     SET_HARD_REG_BIT (used, eliminables[i].from);
1937 #else
1938   SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
1939 #endif
1940
1941   /* Normally, the registers that can be used for the first register in
1942      a multi-register quantity are the same as those that can be used for
1943      subsequent registers.  However, if just trying suggested registers,
1944      restrict our consideration to them.  If there are copy-suggested
1945      register, try them.  Otherwise, try the arithmetic-suggested
1946      registers.  */
1947   COPY_HARD_REG_SET (first_used, used);
1948
1949   if (just_try_suggested)
1950     {
1951       if (qty_phys_has_copy_sugg[qty])
1952         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]);
1953       else
1954         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]);
1955     }
1956
1957   /* If all registers are excluded, we can't do anything.  */
1958   GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);
1959
1960   /* If at least one would be suitable, test each hard reg.  */
1961
1962   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1963     {
1964 #ifdef REG_ALLOC_ORDER
1965       int regno = reg_alloc_order[i];
1966 #else
1967       int regno = i;
1968 #endif
1969       if (! TEST_HARD_REG_BIT (first_used, regno)
1970           && HARD_REGNO_MODE_OK (regno, mode))
1971         {
1972           register int j;
1973           register int size1 = HARD_REGNO_NREGS (regno, mode);
1974           for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
1975           if (j == size1)
1976             {
1977               /* Mark that this register is in use between its birth and death
1978                  insns.  */
1979               post_mark_life (regno, mode, 1, born_index, dead_index);
1980               return regno;
1981             }
1982 #ifndef REG_ALLOC_ORDER
1983           i += j;               /* Skip starting points we know will lose */
1984 #endif
1985         }
1986     }
1987
1988  fail:
1989
1990   /* If we are just trying suggested register, we have just tried copy-
1991      suggested registers, and there are arithmetic-suggested registers,
1992      try them.  */
1993
1994   /* If it would be profitable to allocate a call-clobbered register
1995      and save and restore it around calls, do that.  */
1996   if (just_try_suggested && qty_phys_has_copy_sugg[qty]
1997       && qty_phys_has_sugg[qty])
1998     {
1999       /* Don't try the copy-suggested regs again.  */
2000       qty_phys_has_copy_sugg[qty] = 0;
2001       return find_free_reg (class, mode, qty, accept_call_clobbered, 1,
2002                             born_index, dead_index);
2003     }
2004
2005   /* We need not check to see if the current function has nonlocal
2006      labels because we don't put any pseudos that are live over calls in
2007      registers in that case.  */
2008
2009   if (! accept_call_clobbered
2010       && flag_caller_saves
2011       && ! just_try_suggested
2012       && qty_n_calls_crossed[qty] != 0
2013       && CALLER_SAVE_PROFITABLE (qty_n_refs[qty], qty_n_calls_crossed[qty]))
2014     {
2015       i = find_free_reg (class, mode, qty, 1, 0, born_index, dead_index);
2016       if (i >= 0)
2017         caller_save_needed = 1;
2018       return i;
2019     }
2020   return -1;
2021 }
2022 \f
2023 /* Mark that REGNO with machine-mode MODE is live starting from the current
2024    insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE
2025    is zero).  */
2026
2027 static void
2028 mark_life (regno, mode, life)
2029      register int regno;
2030      enum machine_mode mode;
2031      int life;
2032 {
2033   register int j = HARD_REGNO_NREGS (regno, mode);
2034   if (life)
2035     while (--j >= 0)
2036       SET_HARD_REG_BIT (regs_live, regno + j);
2037   else
2038     while (--j >= 0)
2039       CLEAR_HARD_REG_BIT (regs_live, regno + j);
2040 }
2041
2042 /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE
2043    is non-zero) or dead (if LIFE is zero) from insn number BIRTH (inclusive)
2044    to insn number DEATH (exclusive).  */
2045
2046 static void
2047 post_mark_life (regno, mode, life, birth, death)
2048      register int regno, life, birth;
2049      enum machine_mode mode;
2050      int death;
2051 {
2052   register int j = HARD_REGNO_NREGS (regno, mode);
2053 #ifdef HARD_REG_SET
2054   register              /* Declare it register if it's a scalar.  */
2055 #endif
2056     HARD_REG_SET this_reg;
2057
2058   CLEAR_HARD_REG_SET (this_reg);
2059   while (--j >= 0)
2060     SET_HARD_REG_BIT (this_reg, regno + j);
2061
2062   if (life)
2063     while (birth < death)
2064       {
2065         IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
2066         birth++;
2067       }
2068   else
2069     while (birth < death)
2070       {
2071         AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
2072         birth++;
2073       }
2074 }
2075 \f
2076 /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0
2077    is the register being clobbered, and R1 is a register being used in
2078    the equivalent expression.
2079
2080    If R1 dies in the block and has a REG_NO_CONFLICT note on every insn
2081    in which it is used, return 1.
2082
2083    Otherwise, return 0.  */
2084
2085 static int
2086 no_conflict_p (insn, r0, r1)
2087      rtx insn, r0, r1;
2088 {
2089   int ok = 0;
2090   rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
2091   rtx p, last;
2092
2093   /* If R1 is a hard register, return 0 since we handle this case
2094      when we scan the insns that actually use it.  */
2095
2096   if (note == 0
2097       || (GET_CODE (r1) == REG && REGNO (r1) < FIRST_PSEUDO_REGISTER)
2098       || (GET_CODE (r1) == SUBREG && GET_CODE (SUBREG_REG (r1)) == REG
2099           && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
2100     return 0;
2101
2102   last = XEXP (note, 0);
2103
2104   for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
2105     if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
2106       {
2107         if (find_reg_note (p, REG_DEAD, r1))
2108           ok = 1;
2109
2110         if (reg_mentioned_p (r1, PATTERN (p))
2111             && ! find_reg_note (p, REG_NO_CONFLICT, r1))
2112           return 0;
2113       }
2114
2115   return ok;
2116 }
2117 \f
2118 #ifdef REGISTER_CONSTRAINTS
2119
2120 /* Return 1 if the constraint string P indicates that the a the operand
2121    must be equal to operand 0 and that no register is acceptable.  */
2122
2123 static int
2124 requires_inout_p (p)
2125      char *p;
2126 {
2127   char c;
2128   int found_zero = 0;
2129
2130   while (c = *p++)
2131     switch (c)
2132       {
2133       case '0':
2134         found_zero = 1;
2135         break;
2136
2137       case '=':  case '+':  case '?':
2138       case '#':  case '&':  case '!':
2139       case '*':  case '%':  case ',':
2140       case '1':  case '2':  case '3':  case '4':
2141       case 'm':  case '<':  case '>':  case 'V':  case 'o':
2142       case 'E':  case 'F':  case 'G':  case 'H':
2143       case 's':  case 'i':  case 'n':
2144       case 'I':  case 'J':  case 'K':  case 'L':
2145       case 'M':  case 'N':  case 'O':  case 'P':
2146 #ifdef EXTRA_CONSTRAINT
2147       case 'Q':  case 'R':  case 'S':  case 'T':  case 'U':
2148 #endif
2149       case 'X':
2150         /* These don't say anything we care about.  */
2151         break;
2152
2153       case 'p':
2154       case 'g': case 'r':
2155       default:
2156         /* These mean a register is allowed.  Fail if so.  */
2157         return 0;
2158       }
2159
2160   return found_zero;
2161 }
2162 #endif /* REGISTER_CONSTRAINTS */
2163 \f
2164 void
2165 dump_local_alloc (file)
2166      FILE *file;
2167 {
2168   register int i;
2169   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2170     if (reg_renumber[i] != -1)
2171       fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
2172 }