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
 959           this_insn_number = insn_number;
 960           this_insn = insn;
 961
 962           extract_insn (insn);
 963           which_alternative = -1;
 964
 965           /* Is this insn suitable for tying two registers?
 966              If so, try doing that.
 967              Suitable insns are those with at least two operands and where
 968              operand 0 is an output that is a register that is not
 969              earlyclobber.
 970
 971              We can tie operand 0 with some operand that dies in this insn.
 972              First look for operands that are required to be in the same
 973              register as operand 0.  If we find such, only try tying that
 974              operand or one that can be put into that operand if the
 975              operation is commutative.  If we don't find an operand
 976              that is required to be in the same register as operand 0,
 977              we can tie with any operand.
 978
 979              Subregs in place of regs are also ok.
 980
 981              If tying is done, WIN is set nonzero.  */
 982
 983           if (1
 984 #ifdef REGISTER_CONSTRAINTS
 985               && recog_n_operands > 1
 986               && recog_constraints[0][0] == '='
 987               && recog_constraints[0][1] != '&'
 988 #else
 989               && GET_CODE (PATTERN (insn)) == SET
 990               && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0])
 991 #endif
 992               )
 993             {
 994 #ifdef REGISTER_CONSTRAINTS
 995               /* If non-negative, is an operand that must match operand 0.  */
 996               int must_match_0 = -1;
 997               /* Counts number of alternatives that require a match with
 998                  operand 0.  */
 999               int n_matching_alts = 0;
1000
1001               for (i = 1; i < recog_n_operands; i++)
1002                 {
1003                   char *p = recog_constraints[i];
1004                   int this_match = (requires_inout (p));
1005
1006                   n_matching_alts += this_match;
1007                   if (this_match == recog_n_alternatives)
1008                     must_match_0 = i;
1009                 }
1010 #endif
1011
1012               r0 = recog_operand[0];
1013               for (i = 1; i < recog_n_operands; i++)
1014                 {
1015 #ifdef REGISTER_CONSTRAINTS
1016                   /* Skip this operand if we found an operand that
1017                      must match operand 0 and this operand isn't it
1018                      and can't be made to be it by commutativity.  */
1019
1020                   if (must_match_0 >= 0 && i != must_match_0
1021                       && ! (i == must_match_0 + 1
1022                             && recog_constraints[i-1][0] == '%')
1023                       && ! (i == must_match_0 - 1
1024                             && recog_constraints[i][0] == '%'))
1025                     continue;
1026
1027                   /* Likewise if each alternative has some operand that
1028                      must match operand zero.  In that case, skip any
1029                      operand that doesn't list operand 0 since we know that
1030                      the operand always conflicts with operand 0.  We
1031                      ignore commutatity in this case to keep things simple.  */
1032                   if (n_matching_alts == recog_n_alternatives
1033                       && 0 == requires_inout (recog_constraints[i]))
1034                     continue;
1035 #endif
1036
1037                   r1 = recog_operand[i];
1038
1039                   /* If the operand is an address, find a register in it.
1040                      There may be more than one register, but we only try one
1041                      of them.  */
1042                   if (
1043 #ifdef REGISTER_CONSTRAINTS
1044                       recog_constraints[i][0] == 'p'
1045 #else
1046                       recog_operand_address_p[i]
1047 #endif
1048                       )
1049                     while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
1050                       r1 = XEXP (r1, 0);
1051
1052                   if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
1053                     {
1054                       /* We have two priorities for hard register preferences.
1055                          If we have a move insn or an insn whose first input
1056                          can only be in the same register as the output, give
1057                          priority to an equivalence found from that insn.  */
1058                       int may_save_copy
1059                         = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
1060 #ifdef REGISTER_CONSTRAINTS
1061                            || (r1 == recog_operand[i] && must_match_0 >= 0)
1062 #endif
1063                            );
1064
1065                       if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1066                         win = combine_regs (r1, r0, may_save_copy,
1067                                             insn_number, insn, 0);
1068                     }
1069                   if (win)
1070                     break;
1071                 }
1072             }
1073
1074           /* Recognize an insn sequence with an ultimate result
1075              which can safely overlap one of the inputs.
1076              The sequence begins with a CLOBBER of its result,
1077              and ends with an insn that copies the result to itself
1078              and has a REG_EQUAL note for an equivalent formula.
1079              That note indicates what the inputs are.
1080              The result and the input can overlap if each insn in
1081              the sequence either doesn't mention the input
1082              or has a REG_NO_CONFLICT note to inhibit the conflict.
1083
1084              We do the combining test at the CLOBBER so that the
1085              destination register won't have had a quantity number
1086              assigned, since that would prevent combining.  */
1087
1088           if (GET_CODE (PATTERN (insn)) == CLOBBER
1089               && (r0 = XEXP (PATTERN (insn), 0),
1090                   GET_CODE (r0) == REG)
1091               && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1092               && XEXP (link, 0) != 0
1093               && GET_CODE (XEXP (link, 0)) == INSN
1094               && (set = single_set (XEXP (link, 0))) != 0
1095               && SET_DEST (set) == r0 && SET_SRC (set) == r0
1096               && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
1097                                         NULL_RTX)) != 0)
1098             {
1099               if (r1 = XEXP (note, 0), GET_CODE (r1) == REG
1100                   /* Check that we have such a sequence.  */
1101                   && no_conflict_p (insn, r0, r1))
1102                 win = combine_regs (r1, r0, 1, insn_number, insn, 1);
1103               else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
1104                        && (r1 = XEXP (XEXP (note, 0), 0),
1105                            GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
1106                        && no_conflict_p (insn, r0, r1))
1107                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1108
1109               /* Here we care if the operation to be computed is
1110                  commutative.  */
1111               else if ((GET_CODE (XEXP (note, 0)) == EQ
1112                         || GET_CODE (XEXP (note, 0)) == NE
1113                         || GET_RTX_CLASS (GET_CODE (XEXP (note, 0))) == 'c')
1114                        && (r1 = XEXP (XEXP (note, 0), 1),
1115                            (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
1116                        && no_conflict_p (insn, r0, r1))
1117                 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1118
1119               /* If we did combine something, show the register number
1120                  in question so that we know to ignore its death.  */
1121               if (win)
1122                 no_conflict_combined_regno = REGNO (r1);
1123             }
1124
1125           /* If registers were just tied, set COMBINED_REGNO
1126              to the number of the register used in this insn
1127              that was tied to the register set in this insn.
1128              This register's qty should not be "killed".  */
1129
1130           if (win)
1131             {
1132               while (GET_CODE (r1) == SUBREG)
1133                 r1 = SUBREG_REG (r1);
1134               combined_regno = REGNO (r1);
1135             }
1136
1137           /* Mark the death of everything that dies in this instruction,
1138              except for anything that was just combined.  */
1139
1140           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1141             if (REG_NOTE_KIND (link) == REG_DEAD
1142                 && GET_CODE (XEXP (link, 0)) == REG
1143                 && combined_regno != REGNO (XEXP (link, 0))
1144                 && (no_conflict_combined_regno != REGNO (XEXP (link, 0))
1145                     || ! find_reg_note (insn, REG_NO_CONFLICT, XEXP (link, 0))))
1146               wipe_dead_reg (XEXP (link, 0), 0);
1147
1148           /* Allocate qty numbers for all registers local to this block
1149              that are born (set) in this instruction.
1150              A pseudo that already has a qty is not changed.  */
1151
1152           note_stores (PATTERN (insn), reg_is_set);
1153
1154           /* If anything is set in this insn and then unused, mark it as dying
1155              after this insn, so it will conflict with our outputs.  This
1156              can't match with something that combined, and it doesn't matter
1157              if it did.  Do this after the calls to reg_is_set since these
1158              die after, not during, the current insn.  */
1159
1160           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1161             if (REG_NOTE_KIND (link) == REG_UNUSED
1162                 && GET_CODE (XEXP (link, 0)) == REG)
1163               wipe_dead_reg (XEXP (link, 0), 1);
1164
1165           /* If this is an insn that has a REG_RETVAL note pointing at a
1166              CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
1167              block, so clear any register number that combined within it.  */
1168           if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
1169               && GET_CODE (XEXP (note, 0)) == INSN
1170               && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
1171             no_conflict_combined_regno = -1;
1172         }
1173
1174       /* Set the registers live after INSN_NUMBER.  Note that we never
1175          record the registers live before the block's first insn, since no
1176          pseudos we care about are live before that insn.  */
1177
1178       IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
1179       IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
1180
1181       if (insn == basic_block_end[b])
1182         break;
1183
1184       insn = NEXT_INSN (insn);
1185     }
1186
1187   /* Now every register that is local to this basic block
1188      should have been given a quantity, or else -1 meaning ignore it.
1189      Every quantity should have a known birth and death.
1190
1191      Order the qtys so we assign them registers in order of the
1192      number of suggested registers they need so we allocate those with
1193      the most restrictive needs first.  */
1194
1195   qty_order = (int *) alloca (next_qty * sizeof (int));
1196   for (i = 0; i < next_qty; i++)
1197     qty_order[i] = i;
1198
1199 #define EXCHANGE(I1, I2)  \
1200   { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1201
1202   switch (next_qty)
1203     {
1204     case 3:
1205       /* Make qty_order[2] be the one to allocate last.  */
1206       if (qty_sugg_compare (0, 1) > 0)
1207         EXCHANGE (0, 1);
1208       if (qty_sugg_compare (1, 2) > 0)
1209         EXCHANGE (2, 1);
1210
1211       /* ... Fall through ...  */
1212     case 2:
1213       /* Put the best one to allocate in qty_order[0].  */
1214       if (qty_sugg_compare (0, 1) > 0)
1215         EXCHANGE (0, 1);
1216
1217       /* ... Fall through ...  */
1218
1219     case 1:
1220     case 0:
1221       /* Nothing to do here.  */
1222       break;
1223
1224     default:
1225       qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
1226     }
1227
1228   /* Try to put each quantity in a suggested physical register, if it has one.
1229      This may cause registers to be allocated that otherwise wouldn't be, but
1230      this seems acceptable in local allocation (unlike global allocation).  */
1231   for (i = 0; i < next_qty; i++)
1232     {
1233       q = qty_order[i];
1234       if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
1235         qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q,
1236                                          0, 1, qty_birth[q], qty_death[q]);
1237       else
1238         qty_phys_reg[q] = -1;
1239     }
1240
1241   /* Order the qtys so we assign them registers in order of
1242      decreasing length of life.  Normally call qsort, but if we
1243      have only a very small number of quantities, sort them ourselves.  */
1244
1245   for (i = 0; i < next_qty; i++)
1246     qty_order[i] = i;
1247
1248 #define EXCHANGE(I1, I2)  \
1249   { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1250
1251   switch (next_qty)
1252     {
1253     case 3:
1254       /* Make qty_order[2] be the one to allocate last.  */
1255       if (qty_compare (0, 1) > 0)
1256         EXCHANGE (0, 1);
1257       if (qty_compare (1, 2) > 0)
1258         EXCHANGE (2, 1);
1259
1260       /* ... Fall through ...  */
1261     case 2:
1262       /* Put the best one to allocate in qty_order[0].  */
1263       if (qty_compare (0, 1) > 0)
1264         EXCHANGE (0, 1);
1265
1266       /* ... Fall through ...  */
1267
1268     case 1:
1269     case 0:
1270       /* Nothing to do here.  */
1271       break;
1272
1273     default:
1274       qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
1275     }
1276
1277   /* Now for each qty that is not a hardware register,
1278      look for a hardware register to put it in.
1279      First try the register class that is cheapest for this qty,
1280      if there is more than one class.  */
1281
1282   for (i = 0; i < next_qty; i++)
1283     {
1284       q = qty_order[i];
1285       if (qty_phys_reg[q] < 0)
1286         {
1287 #ifdef INSN_SCHEDULING
1288           /* These values represent the adjusted lifetime of a qty so
1289              that it conflicts with qtys which appear near the start/end
1290              of this qty's lifetime.
1291
1292              The purpose behind extending the lifetime of this qty is to
1293              discourage the register allocator from creating false
1294              dependencies.
1295
1296              The adjustment by the value +-3 indicates precisely that
1297              this qty conflicts with qtys in the instructions immediately
1298              before and after the lifetime of this qty.
1299
1300              Experiments have shown that higher values tend to hurt
1301              overall code performance.
1302
1303              If allocation using the extended lifetime fails we will try
1304              again with the qty's unadjusted lifetime.  */
1305           int fake_birth = MAX (0, qty_birth[q] - 3);
1306           int fake_death = MIN (insn_number * 2 + 1, qty_death[q] + 3);
1307 #endif
1308
1309           if (N_REG_CLASSES > 1)
1310             {
1311 #ifdef INSN_SCHEDULING
1312               /* We try to avoid using hard registers allocated to qtys which
1313                  are born immediately after this qty or die immediately before
1314                  this qty.
1315
1316                  This optimization is only appropriate when we will run
1317                  a scheduling pass after reload and we are not optimizing
1318                  for code size.  */
1319               if (flag_schedule_insns_after_reload
1320                   && !optimize_size
1321                   && !SMALL_REGISTER_CLASSES)
1322                 {
1323
1324                   qty_phys_reg[q] = find_free_reg (qty_min_class[q],
1325                                                    qty_mode[q], q, 0, 0,
1326                                                    fake_birth, fake_death);
1327                   if (qty_phys_reg[q] >= 0)
1328                     continue;
1329                 }
1330 #endif
1331               qty_phys_reg[q] = find_free_reg (qty_min_class[q],
1332                                                qty_mode[q], q, 0, 0,
1333                                                qty_birth[q], qty_death[q]);
1334               if (qty_phys_reg[q] >= 0)
1335                 continue;
1336             }
1337
1338 #ifdef INSN_SCHEDULING
1339           /* Similarly, avoid false dependencies.  */
1340           if (flag_schedule_insns_after_reload
1341               && !optimize_size
1342               && !SMALL_REGISTER_CLASSES
1343               && qty_alternate_class[q] != NO_REGS)
1344             qty_phys_reg[q] = find_free_reg (qty_alternate_class[q],
1345                                              qty_mode[q], q, 0, 0,
1346                                              fake_birth, fake_death);
1347 #endif
1348           if (qty_alternate_class[q] != NO_REGS)
1349             qty_phys_reg[q] = find_free_reg (qty_alternate_class[q],
1350                                              qty_mode[q], q, 0, 0,
1351                                              qty_birth[q], qty_death[q]);
1352         }
1353     }
1354
1355   /* Now propagate the register assignments
1356      to the pseudo regs belonging to the qtys.  */
1357
1358   for (q = 0; q < next_qty; q++)
1359     if (qty_phys_reg[q] >= 0)
1360       {
1361         for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i])
1362           reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
1363       }
1364 }
1365 \f
1366 /* Compare two quantities' priority for getting real registers.
1367    We give shorter-lived quantities higher priority.
1368    Quantities with more references are also preferred, as are quantities that
1369    require multiple registers.  This is the identical prioritization as
1370    done by global-alloc.
1371
1372    We used to give preference to registers with *longer* lives, but using
1373    the same algorithm in both local- and global-alloc can speed up execution
1374    of some programs by as much as a factor of three!  */
1375
1376 /* Note that the quotient will never be bigger than
1377    the value of floor_log2 times the maximum number of
1378    times a register can occur in one insn (surely less than 100).
1379    Multiplying this by 10000 can't overflow.
1380    QTY_CMP_PRI is also used by qty_sugg_compare.  */
1381
1382 #define QTY_CMP_PRI(q)          \
1383   ((int) (((double) (floor_log2 (qty_n_refs[q]) * qty_n_refs[q] * qty_size[q]) \
1384           / (qty_death[q] - qty_birth[q])) * 10000))
1385
1386 static int
1387 qty_compare (q1, q2)
1388      int q1, q2;
1389 {
1390   return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1391 }
1392
1393 static int
1394 qty_compare_1 (q1p, q2p)
1395      const GENERIC_PTR q1p;
1396      const GENERIC_PTR q2p;
1397 {
1398   register int q1 = *(int *)q1p, q2 = *(int *)q2p;
1399   register int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1400
1401   if (tem != 0)
1402     return tem;
1403
1404   /* If qtys are equally good, sort by qty number,
1405      so that the results of qsort leave nothing to chance.  */
1406   return q1 - q2;
1407 }
1408 \f
1409 /* Compare two quantities' priority for getting real registers.  This version
1410    is called for quantities that have suggested hard registers.  First priority
1411    goes to quantities that have copy preferences, then to those that have
1412    normal preferences.  Within those groups, quantities with the lower
1413    number of preferences have the highest priority.  Of those, we use the same
1414    algorithm as above.  */
1415
1416 #define QTY_CMP_SUGG(q)         \
1417   (qty_phys_num_copy_sugg[q]            \
1418     ? qty_phys_num_copy_sugg[q] \
1419     : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER)
1420
1421 static int
1422 qty_sugg_compare (q1, q2)
1423      int q1, q2;
1424 {
1425   register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1426
1427   if (tem != 0)
1428     return tem;
1429
1430   return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1431 }
1432
1433 static int
1434 qty_sugg_compare_1 (q1p, q2p)
1435      const GENERIC_PTR q1p;
1436      const GENERIC_PTR q2p;
1437 {
1438   register int q1 = *(int *)q1p, q2 = *(int *)q2p;
1439   register int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1440
1441   if (tem != 0)
1442     return tem;
1443
1444   tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1445   if (tem != 0)
1446     return tem;
1447
1448   /* If qtys are equally good, sort by qty number,
1449      so that the results of qsort leave nothing to chance.  */
1450   return q1 - q2;
1451 }
1452
1453 #undef QTY_CMP_SUGG
1454 #undef QTY_CMP_PRI
1455 \f
1456 /* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
1457    Returns 1 if have done so, or 0 if cannot.
1458
1459    Combining registers means marking them as having the same quantity
1460    and adjusting the offsets within the quantity if either of
1461    them is a SUBREG).
1462
1463    We don't actually combine a hard reg with a pseudo; instead
1464    we just record the hard reg as the suggestion for the pseudo's quantity.
1465    If we really combined them, we could lose if the pseudo lives
1466    across an insn that clobbers the hard reg (eg, movstr).
1467
1468    ALREADY_DEAD is non-zero if USEDREG is known to be dead even though
1469    there is no REG_DEAD note on INSN.  This occurs during the processing
1470    of REG_NO_CONFLICT blocks.
1471
1472    MAY_SAVE_COPYCOPY is non-zero if this insn is simply copying USEDREG to
1473    SETREG or if the input and output must share a register.
1474    In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
1475
1476    There are elaborate checks for the validity of combining.  */
1477
1478
1479 static int
1480 combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead)
1481      rtx usedreg, setreg;
1482      int may_save_copy;
1483      int insn_number;
1484      rtx insn;
1485      int already_dead;
1486 {
1487   register int ureg, sreg;
1488   register int offset = 0;
1489   int usize, ssize;
1490   register int sqty;
1491
1492   /* Determine the numbers and sizes of registers being used.  If a subreg
1493      is present that does not change the entire register, don't consider
1494      this a copy insn.  */
1495
1496   while (GET_CODE (usedreg) == SUBREG)
1497     {
1498       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (usedreg))) > UNITS_PER_WORD)
1499         may_save_copy = 0;
1500       offset += SUBREG_WORD (usedreg);
1501       usedreg = SUBREG_REG (usedreg);
1502     }
1503   if (GET_CODE (usedreg) != REG)
1504     return 0;
1505   ureg = REGNO (usedreg);
1506   usize = REG_SIZE (usedreg);
1507
1508   while (GET_CODE (setreg) == SUBREG)
1509     {
1510       if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (setreg))) > UNITS_PER_WORD)
1511         may_save_copy = 0;
1512       offset -= SUBREG_WORD (setreg);
1513       setreg = SUBREG_REG (setreg);
1514     }
1515   if (GET_CODE (setreg) != REG)
1516     return 0;
1517   sreg = REGNO (setreg);
1518   ssize = REG_SIZE (setreg);
1519
1520   /* If UREG is a pseudo-register that hasn't already been assigned a
1521      quantity number, it means that it is not local to this block or dies
1522      more than once.  In either event, we can't do anything with it.  */
1523   if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
1524       /* Do not combine registers unless one fits within the other.  */
1525       || (offset > 0 && usize + offset > ssize)
1526       || (offset < 0 && usize + offset < ssize)
1527       /* Do not combine with a smaller already-assigned object
1528          if that smaller object is already combined with something bigger.  */
1529       || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
1530           && usize < qty_size[reg_qty[ureg]])
1531       /* Can't combine if SREG is not a register we can allocate.  */
1532       || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
1533       /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
1534          These have already been taken care of.  This probably wouldn't
1535          combine anyway, but don't take any chances.  */
1536       || (ureg >= FIRST_PSEUDO_REGISTER
1537           && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
1538       /* Don't tie something to itself.  In most cases it would make no
1539          difference, but it would screw up if the reg being tied to itself
1540          also dies in this insn.  */
1541       || ureg == sreg
1542       /* Don't try to connect two different hardware registers.  */
1543       || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
1544       /* Don't connect two different machine modes if they have different
1545          implications as to which registers may be used.  */
1546       || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
1547     return 0;
1548
1549   /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
1550      qty_phys_sugg for the pseudo instead of tying them.
1551
1552      Return "failure" so that the lifespan of UREG is terminated here;
1553      that way the two lifespans will be disjoint and nothing will prevent
1554      the pseudo reg from being given this hard reg.  */
1555
1556   if (ureg < FIRST_PSEUDO_REGISTER)
1557     {
1558       /* Allocate a quantity number so we have a place to put our
1559          suggestions.  */
1560       if (reg_qty[sreg] == -2)
1561         reg_is_born (setreg, 2 * insn_number);
1562
1563       if (reg_qty[sreg] >= 0)
1564         {
1565           if (may_save_copy
1566               && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
1567             {
1568               SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
1569               qty_phys_num_copy_sugg[reg_qty[sreg]]++;
1570             }
1571           else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
1572             {
1573               SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
1574               qty_phys_num_sugg[reg_qty[sreg]]++;
1575             }
1576         }
1577       return 0;
1578     }
1579
1580   /* Similarly for SREG a hard register and UREG a pseudo register.  */
1581
1582   if (sreg < FIRST_PSEUDO_REGISTER)
1583     {
1584       if (may_save_copy
1585           && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
1586         {
1587           SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
1588           qty_phys_num_copy_sugg[reg_qty[ureg]]++;
1589         }
1590       else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
1591         {
1592           SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
1593           qty_phys_num_sugg[reg_qty[ureg]]++;
1594         }
1595       return 0;
1596     }
1597
1598   /* At this point we know that SREG and UREG are both pseudos.
1599      Do nothing if SREG already has a quantity or is a register that we
1600      don't allocate.  */
1601   if (reg_qty[sreg] >= -1
1602       /* If we are not going to let any regs live across calls,
1603          don't tie a call-crossing reg to a non-call-crossing reg.  */
1604       || (current_function_has_nonlocal_label
1605           && ((REG_N_CALLS_CROSSED (ureg) > 0)
1606               != (REG_N_CALLS_CROSSED (sreg) > 0))))
1607     return 0;
1608
1609   /* We don't already know about SREG, so tie it to UREG
1610      if this is the last use of UREG, provided the classes they want
1611      are compatible.  */
1612
1613   if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
1614       && reg_meets_class_p (sreg, qty_min_class[reg_qty[ureg]]))
1615     {
1616       /* Add SREG to UREG's quantity.  */
1617       sqty = reg_qty[ureg];
1618       reg_qty[sreg] = sqty;
1619       reg_offset[sreg] = reg_offset[ureg] + offset;
1620       reg_next_in_qty[sreg] = qty_first_reg[sqty];
1621       qty_first_reg[sqty] = sreg;
1622
1623       /* If SREG's reg class is smaller, set qty_min_class[SQTY].  */
1624       update_qty_class (sqty, sreg);
1625
1626       /* Update info about quantity SQTY.  */
1627       qty_n_calls_crossed[sqty] += REG_N_CALLS_CROSSED (sreg);
1628       qty_n_refs[sqty] += REG_N_REFS (sreg);
1629       if (usize < ssize)
1630         {
1631           register int i;
1632
1633           for (i = qty_first_reg[sqty]; i >= 0; i = reg_next_in_qty[i])
1634             reg_offset[i] -= offset;
1635
1636           qty_size[sqty] = ssize;
1637           qty_mode[sqty] = GET_MODE (setreg);
1638         }
1639     }
1640   else
1641     return 0;
1642
1643   return 1;
1644 }
1645 \f
1646 /* Return 1 if the preferred class of REG allows it to be tied
1647    to a quantity or register whose class is CLASS.
1648    True if REG's reg class either contains or is contained in CLASS.  */
1649
1650 static int
1651 reg_meets_class_p (reg, class)
1652      int reg;
1653      enum reg_class class;
1654 {
1655   register enum reg_class rclass = reg_preferred_class (reg);
1656   return (reg_class_subset_p (rclass, class)
1657           || reg_class_subset_p (class, rclass));
1658 }
1659
1660 /* Update the class of QTY assuming that REG is being tied to it.  */
1661
1662 static void
1663 update_qty_class (qty, reg)
1664      int qty;
1665      int reg;
1666 {
1667   enum reg_class rclass = reg_preferred_class (reg);
1668   if (reg_class_subset_p (rclass, qty_min_class[qty]))
1669     qty_min_class[qty] = rclass;
1670
1671   rclass = reg_alternate_class (reg);
1672   if (reg_class_subset_p (rclass, qty_alternate_class[qty]))
1673     qty_alternate_class[qty] = rclass;
1674
1675   if (REG_CHANGES_SIZE (reg))
1676     qty_changes_size[qty] = 1;
1677 }
1678 \f
1679 /* Handle something which alters the value of an rtx REG.
1680
1681    REG is whatever is set or clobbered.  SETTER is the rtx that
1682    is modifying the register.
1683
1684    If it is not really a register, we do nothing.
1685    The file-global variables `this_insn' and `this_insn_number'
1686    carry info from `block_alloc'.  */
1687
1688 static void
1689 reg_is_set (reg, setter)
1690      rtx reg;
1691      rtx setter;
1692 {
1693   /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
1694      a hard register.  These may actually not exist any more.  */
1695
1696   if (GET_CODE (reg) != SUBREG
1697       && GET_CODE (reg) != REG)
1698     return;
1699
1700   /* Mark this register as being born.  If it is used in a CLOBBER, mark
1701      it as being born halfway between the previous insn and this insn so that
1702      it conflicts with our inputs but not the outputs of the previous insn.  */
1703
1704   reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
1705 }
1706 \f
1707 /* Handle beginning of the life of register REG.
1708    BIRTH is the index at which this is happening.  */
1709
1710 static void
1711 reg_is_born (reg, birth)
1712      rtx reg;
1713      int birth;
1714 {
1715   register int regno;
1716
1717   if (GET_CODE (reg) == SUBREG)
1718     regno = REGNO (SUBREG_REG (reg)) + SUBREG_WORD (reg);
1719   else
1720     regno = REGNO (reg);
1721
1722   if (regno < FIRST_PSEUDO_REGISTER)
1723     {
1724       mark_life (regno, GET_MODE (reg), 1);
1725
1726       /* If the register was to have been born earlier that the present
1727          insn, mark it as live where it is actually born.  */
1728       if (birth < 2 * this_insn_number)
1729         post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
1730     }
1731   else
1732     {
1733       if (reg_qty[regno] == -2)
1734         alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
1735
1736       /* If this register has a quantity number, show that it isn't dead.  */
1737       if (reg_qty[regno] >= 0)
1738         qty_death[reg_qty[regno]] = -1;
1739     }
1740 }
1741
1742 /* Record the death of REG in the current insn.  If OUTPUT_P is non-zero,
1743    REG is an output that is dying (i.e., it is never used), otherwise it
1744    is an input (the normal case).
1745    If OUTPUT_P is 1, then we extend the life past the end of this insn.  */
1746
1747 static void
1748 wipe_dead_reg (reg, output_p)
1749      register rtx reg;
1750      int output_p;
1751 {
1752   register int regno = REGNO (reg);
1753
1754   /* If this insn has multiple results,
1755      and the dead reg is used in one of the results,
1756      extend its life to after this insn,
1757      so it won't get allocated together with any other result of this insn.  */
1758   if (GET_CODE (PATTERN (this_insn)) == PARALLEL
1759       && !single_set (this_insn))
1760     {
1761       int i;
1762       for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
1763         {
1764           rtx set = XVECEXP (PATTERN (this_insn), 0, i);
1765           if (GET_CODE (set) == SET
1766               && GET_CODE (SET_DEST (set)) != REG
1767               && !rtx_equal_p (reg, SET_DEST (set))
1768               && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1769             output_p = 1;
1770         }
1771     }
1772
1773   /* If this register is used in an auto-increment address, then extend its
1774      life to after this insn, so that it won't get allocated together with
1775      the result of this insn.  */
1776   if (! output_p && find_regno_note (this_insn, REG_INC, regno))
1777     output_p = 1;
1778
1779   if (regno < FIRST_PSEUDO_REGISTER)
1780     {
1781       mark_life (regno, GET_MODE (reg), 0);
1782
1783       /* If a hard register is dying as an output, mark it as in use at
1784          the beginning of this insn (the above statement would cause this
1785          not to happen).  */
1786       if (output_p)
1787         post_mark_life (regno, GET_MODE (reg), 1,
1788                         2 * this_insn_number, 2 * this_insn_number+ 1);
1789     }
1790
1791   else if (reg_qty[regno] >= 0)
1792     qty_death[reg_qty[regno]] = 2 * this_insn_number + output_p;
1793 }
1794 \f
1795 /* Find a block of SIZE words of hard regs in reg_class CLASS
1796    that can hold something of machine-mode MODE
1797      (but actually we test only the first of the block for holding MODE)
1798    and still free between insn BORN_INDEX and insn DEAD_INDEX,
1799    and return the number of the first of them.
1800    Return -1 if such a block cannot be found.
1801    If QTY crosses calls, insist on a register preserved by calls,
1802    unless ACCEPT_CALL_CLOBBERED is nonzero.
1803
1804    If JUST_TRY_SUGGESTED is non-zero, only try to see if the suggested
1805    register is available.  If not, return -1.  */
1806
1807 static int
1808 find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested,
1809                born_index, dead_index)
1810      enum reg_class class;
1811      enum machine_mode mode;
1812      int qty;
1813      int accept_call_clobbered;
1814      int just_try_suggested;
1815      int born_index, dead_index;
1816 {
1817   register int i, ins;
1818 #ifdef HARD_REG_SET
1819   register              /* Declare it register if it's a scalar.  */
1820 #endif
1821     HARD_REG_SET used, first_used;
1822 #ifdef ELIMINABLE_REGS
1823   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
1824 #endif
1825
1826   /* Validate our parameters.  */
1827   if (born_index < 0 || born_index > dead_index)
1828     abort ();
1829
1830   /* Don't let a pseudo live in a reg across a function call
1831      if we might get a nonlocal goto.  */
1832   if (current_function_has_nonlocal_label
1833       && qty_n_calls_crossed[qty] > 0)
1834     return -1;
1835
1836   if (accept_call_clobbered)
1837     COPY_HARD_REG_SET (used, call_fixed_reg_set);
1838   else if (qty_n_calls_crossed[qty] == 0)
1839     COPY_HARD_REG_SET (used, fixed_reg_set);
1840   else
1841     COPY_HARD_REG_SET (used, call_used_reg_set);
1842
1843   if (accept_call_clobbered)
1844     IOR_HARD_REG_SET (used, losing_caller_save_reg_set);
1845
1846   for (ins = born_index; ins < dead_index; ins++)
1847     IOR_HARD_REG_SET (used, regs_live_at[ins]);
1848
1849   IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
1850
1851   /* Don't use the frame pointer reg in local-alloc even if
1852      we may omit the frame pointer, because if we do that and then we
1853      need a frame pointer, reload won't know how to move the pseudo
1854      to another hard reg.  It can move only regs made by global-alloc.
1855
1856      This is true of any register that can be eliminated.  */
1857 #ifdef ELIMINABLE_REGS
1858   for (i = 0; i < (int)(sizeof eliminables / sizeof eliminables[0]); i++)
1859     SET_HARD_REG_BIT (used, eliminables[i].from);
1860 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1861   /* If FRAME_POINTER_REGNUM is not a real register, then protect the one
1862      that it might be eliminated into.  */
1863   SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
1864 #endif
1865 #else
1866   SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
1867 #endif
1868
1869 #ifdef CLASS_CANNOT_CHANGE_SIZE
1870   if (qty_changes_size[qty])
1871     IOR_HARD_REG_SET (used,
1872                       reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
1873 #endif
1874
1875   /* Normally, the registers that can be used for the first register in
1876      a multi-register quantity are the same as those that can be used for
1877      subsequent registers.  However, if just trying suggested registers,
1878      restrict our consideration to them.  If there are copy-suggested
1879      register, try them.  Otherwise, try the arithmetic-suggested
1880      registers.  */
1881   COPY_HARD_REG_SET (first_used, used);
1882
1883   if (just_try_suggested)
1884     {
1885       if (qty_phys_num_copy_sugg[qty] != 0)
1886         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]);
1887       else
1888         IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]);
1889     }
1890
1891   /* If all registers are excluded, we can't do anything.  */
1892   GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail);
1893
1894   /* If at least one would be suitable, test each hard reg.  */
1895
1896   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1897     {
1898 #ifdef REG_ALLOC_ORDER
1899       int regno = reg_alloc_order[i];
1900 #else
1901       int regno = i;
1902 #endif
1903       if (! TEST_HARD_REG_BIT (first_used, regno)
1904           && HARD_REGNO_MODE_OK (regno, mode)
1905           && (qty_n_calls_crossed[qty] == 0
1906               || accept_call_clobbered
1907               || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1908         {
1909           register int j;
1910           register int size1 = HARD_REGNO_NREGS (regno, mode);
1911           for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++);
1912           if (j == size1)
1913             {
1914               /* Mark that this register is in use between its birth and death
1915                  insns.  */
1916               post_mark_life (regno, mode, 1, born_index, dead_index);
1917               return regno;
1918             }
1919 #ifndef REG_ALLOC_ORDER
1920           i += j;               /* Skip starting points we know will lose */
1921 #endif
1922         }
1923     }
1924
1925  fail:
1926
1927   /* If we are just trying suggested register, we have just tried copy-
1928      suggested registers, and there are arithmetic-suggested registers,
1929      try them.  */
1930
1931   /* If it would be profitable to allocate a call-clobbered register
1932      and save and restore it around calls, do that.  */
1933   if (just_try_suggested && qty_phys_num_copy_sugg[qty] != 0
1934       && qty_phys_num_sugg[qty] != 0)
1935     {
1936       /* Don't try the copy-suggested regs again.  */
1937       qty_phys_num_copy_sugg[qty] = 0;
1938       return find_free_reg (class, mode, qty, accept_call_clobbered, 1,
1939                             born_index, dead_index);
1940     }
1941
1942   /* We need not check to see if the current function has nonlocal
1943      labels because we don't put any pseudos that are live over calls in
1944      registers in that case.  */
1945
1946   if (! accept_call_clobbered
1947       && flag_caller_saves
1948       && ! just_try_suggested
1949       && qty_n_calls_crossed[qty] != 0
1950       && CALLER_SAVE_PROFITABLE (qty_n_refs[qty], qty_n_calls_crossed[qty]))
1951     {
1952       i = find_free_reg (class, mode, qty, 1, 0, born_index, dead_index);
1953       if (i >= 0)
1954         caller_save_needed = 1;
1955       return i;
1956     }
1957   return -1;
1958 }
1959 \f
1960 /* Mark that REGNO with machine-mode MODE is live starting from the current
1961    insn (if LIFE is non-zero) or dead starting at the current insn (if LIFE
1962    is zero).  */
1963
1964 static void
1965 mark_life (regno, mode, life)
1966      register int regno;
1967      enum machine_mode mode;
1968      int life;
1969 {
1970   register int j = HARD_REGNO_NREGS (regno, mode);
1971   if (life)
1972     while (--j >= 0)
1973       SET_HARD_REG_BIT (regs_live, regno + j);
1974   else
1975     while (--j >= 0)
1976       CLEAR_HARD_REG_BIT (regs_live, regno + j);
1977 }
1978
1979 /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE
1980    is non-zero) or dead (if LIFE is zero) from insn number BIRTH (inclusive)
1981    to insn number DEATH (exclusive).  */
1982
1983 static void
1984 post_mark_life (regno, mode, life, birth, death)
1985      int regno;
1986      enum machine_mode mode;
1987      int life, birth, death;
1988 {
1989   register int j = HARD_REGNO_NREGS (regno, mode);
1990 #ifdef HARD_REG_SET
1991   register              /* Declare it register if it's a scalar.  */
1992 #endif
1993     HARD_REG_SET this_reg;
1994
1995   CLEAR_HARD_REG_SET (this_reg);
1996   while (--j >= 0)
1997     SET_HARD_REG_BIT (this_reg, regno + j);
1998
1999   if (life)
2000     while (birth < death)
2001       {
2002         IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
2003         birth++;
2004       }
2005   else
2006     while (birth < death)
2007       {
2008         AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
2009         birth++;
2010       }
2011 }
2012 \f
2013 /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0
2014    is the register being clobbered, and R1 is a register being used in
2015    the equivalent expression.
2016
2017    If R1 dies in the block and has a REG_NO_CONFLICT note on every insn
2018    in which it is used, return 1.
2019
2020    Otherwise, return 0.  */
2021
2022 static int
2023 no_conflict_p (insn, r0, r1)
2024      rtx insn, r0, r1;
2025 {
2026   int ok = 0;
2027   rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
2028   rtx p, last;
2029
2030   /* If R1 is a hard register, return 0 since we handle this case
2031      when we scan the insns that actually use it.  */
2032
2033   if (note == 0
2034       || (GET_CODE (r1) == REG && REGNO (r1) < FIRST_PSEUDO_REGISTER)
2035       || (GET_CODE (r1) == SUBREG && GET_CODE (SUBREG_REG (r1)) == REG
2036           && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
2037     return 0;
2038
2039   last = XEXP (note, 0);
2040
2041   for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
2042     if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
2043       {
2044         if (find_reg_note (p, REG_DEAD, r1))
2045           ok = 1;
2046
2047         /* There must be a REG_NO_CONFLICT note on every insn, otherwise
2048            some earlier optimization pass has inserted instructions into
2049            the sequence, and it is not safe to perform this optimization.
2050            Note that emit_no_conflict_block always ensures that this is
2051            true when these sequences are created.  */
2052         if (! find_reg_note (p, REG_NO_CONFLICT, r1))
2053           return 0;
2054       }
2055
2056   return ok;
2057 }
2058 \f
2059 #ifdef REGISTER_CONSTRAINTS
2060
2061 /* Return the number of alternatives for which the constraint string P
2062    indicates that the operand must be equal to operand 0 and that no register
2063    is acceptable.  */
2064
2065 static int
2066 requires_inout (p)
2067      char *p;
2068 {
2069   char c;
2070   int found_zero = 0;
2071   int reg_allowed = 0;
2072   int num_matching_alts = 0;
2073
2074   while ((c = *p++))
2075     switch (c)
2076       {
2077       case '=':  case '+':  case '?':
2078       case '#':  case '&':  case '!':
2079       case '*':  case '%':
2080       case '1':  case '2':  case '3':  case '4':
2081       case 'm':  case '<':  case '>':  case 'V':  case 'o':
2082       case 'E':  case 'F':  case 'G':  case 'H':
2083       case 's':  case 'i':  case 'n':
2084       case 'I':  case 'J':  case 'K':  case 'L':
2085       case 'M':  case 'N':  case 'O':  case 'P':
2086 #ifdef EXTRA_CONSTRAINT
2087       case 'Q':  case 'R':  case 'S':  case 'T':  case 'U':
2088 #endif
2089       case 'X':
2090         /* These don't say anything we care about.  */
2091         break;
2092
2093       case ',':
2094         if (found_zero && ! reg_allowed)
2095           num_matching_alts++;
2096
2097         found_zero = reg_allowed = 0;
2098         break;
2099
2100       case '0':
2101         found_zero = 1;
2102         break;
2103
2104       case 'p':
2105       case 'g': case 'r':
2106       default:
2107         reg_allowed = 1;
2108         break;
2109       }
2110
2111   if (found_zero && ! reg_allowed)
2112     num_matching_alts++;
2113
2114   return num_matching_alts;
2115 }
2116 #endif /* REGISTER_CONSTRAINTS */
2117 \f
2118 void
2119 dump_local_alloc (file)
2120      FILE *file;
2121 {
2122   register int i;
2123   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2124     if (reg_renumber[i] != -1)
2125       fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
2126 }