Return to local-alloc.c CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/local-alloc.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.