gcc/local-alloc.c

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