gcc/local-alloc.c

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