gcc/local-alloc.c

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