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