Return to local-alloc.c CVS log

Up to [Apple XNU] / GNUtools / cc

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

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