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