Return to global-alloc.c CVS log

Up to [GCC 2.x] / gcc

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

1.1     ! root        1: /* Allocate registers for pseudo-registers that span basic blocks.
        !             2:    Copyright (C) 1987, 1988, 1991 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of GNU CC.
        !             5: 
        !             6: GNU CC is free software; you can redistribute it and/or modify
        !             7: it under the terms of the GNU General Public License as published by
        !             8: the Free Software Foundation; either version 2, or (at your option)
        !             9: any later version.
        !            10: 
        !            11: GNU CC is distributed in the hope that it will be useful,
        !            12: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            14: GNU General Public License for more details.
        !            15: 
        !            16: You should have received a copy of the GNU General Public License
        !            17: along with GNU CC; see the file COPYING.  If not, write to
        !            18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            19: 
        !            20: 
        !            21: #include <stdio.h>
        !            22: #include "config.h"
        !            23: #include "rtl.h"
        !            24: #include "flags.h"
        !            25: #include "basic-block.h"
        !            26: #include "hard-reg-set.h"
        !            27: #include "regs.h"
        !            28: #include "insn-config.h"
        !            29: #include "output.h"
        !            30: 
        !            31: /* This pass of the compiler performs global register allocation.
        !            32:    It assigns hard register numbers to all the pseudo registers
        !            33:    that were not handled in local_alloc.  Assignments are recorded
        !            34:    in the vector reg_renumber, not by changing the rtl code.
        !            35:    (Such changes are made by final).  The entry point is
        !            36:    the function global_alloc.
        !            37: 
        !            38:    After allocation is complete, the reload pass is run as a subroutine
        !            39:    of this pass, so that when a pseudo reg loses its hard reg due to
        !            40:    spilling it is possible to make a second attempt to find a hard
        !            41:    reg for it.  The reload pass is independent in other respects
        !            42:    and it is run even when stupid register allocation is in use.
        !            43: 
        !            44:    1. count the pseudo-registers still needing allocation
        !            45:    and assign allocation-numbers (allocnos) to them.
        !            46:    Set up tables reg_allocno and allocno_reg to map 
        !            47:    reg numbers to allocnos and vice versa.
        !            48:    max_allocno gets the number of allocnos in use.
        !            49: 
        !            50:    2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
        !            51:    Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
        !            52:    for conflicts between allocnos and explicit hard register use
        !            53:    (which includes use of pseudo-registers allocated by local_alloc).
        !            54: 
        !            55:    3. for each basic block
        !            56:     walk forward through the block, recording which
        !            57:     unallocated registers and which hardware registers are live.
        !            58:     Build the conflict matrix between the unallocated registers
        !            59:     and another of unallocated registers versus hardware registers.
        !            60:     Also record the preferred hardware registers
        !            61:     for each unallocated one.
        !            62: 
        !            63:    4. Sort a table of the allocnos into order of
        !            64:    desirability of the variables.
        !            65: 
        !            66:    5. Allocate the variables in that order; each if possible into
        !            67:    a preferred register, else into another register.  */
        !            68: 
        !            69: /* Number of pseudo-registers still requiring allocation
        !            70:    (not allocated by local_allocate).  */
        !            71: 
        !            72: static int max_allocno;
        !            73: 
        !            74: /* Indexed by (pseudo) reg number, gives the allocno, or -1
        !            75:    for pseudo registers already allocated by local_allocate.  */
        !            76: 
        !            77: static int *reg_allocno;
        !            78: 
        !            79: /* Indexed by allocno, gives the reg number.  */
        !            80: 
        !            81: static int *allocno_reg;
        !            82: 
        !            83: /* A vector of the integers from 0 to max_allocno-1,
        !            84:    sorted in the order of first-to-be-allocated first.  */
        !            85: 
        !            86: static int *allocno_order;
        !            87: 
        !            88: /* Indexed by an allocno, gives the number of consecutive
        !            89:    hard registers needed by that pseudo reg.  */
        !            90: 
        !            91: static int *allocno_size;
        !            92: 
        !            93: /* Indexed by (pseudo) reg number, gives the number of another
        !            94:    lower-numbered pseudo reg which can share a hard reg with this peudo
        !            95:    *even if the two pseudos would otherwise appear to conflict*.  */
        !            96: 
        !            97: static int *reg_may_share;
        !            98: 
        !            99: /* max_allocno by max_allocno array of bits,
        !           100:    recording whether two allocno's conflict (can't go in the same
        !           101:    hardware register).
        !           102: 
        !           103:    `conflicts' is not symmetric; a conflict between allocno's i and j
        !           104:    is recorded either in element i,j or in element j,i.  */
        !           105: 
        !           106: static int *conflicts;
        !           107: 
        !           108: /* Number of ints require to hold max_allocno bits.
        !           109:    This is the length of a row in `conflicts'.  */
        !           110: 
        !           111: static int allocno_row_words;
        !           112: 
        !           113: /* Two macros to test or store 1 in an element of `conflicts'.  */
        !           114: 
        !           115: #define CONFLICTP(I, J) \
        !           116:  (conflicts[(I) * allocno_row_words + (J) / INT_BITS]  \
        !           117:   & (1 << ((J) % INT_BITS)))
        !           118: 
        !           119: #define SET_CONFLICT(I, J) \
        !           120:  (conflicts[(I) * allocno_row_words + (J) / INT_BITS]  \
        !           121:   |= (1 << ((J) % INT_BITS)))
        !           122: 
        !           123: /* Set of hard regs currently live (during scan of all insns).  */
        !           124: 
        !           125: static HARD_REG_SET hard_regs_live;
        !           126: 
        !           127: /* Indexed by N, set of hard regs conflicting with allocno N.  */
        !           128: 
        !           129: static HARD_REG_SET *hard_reg_conflicts;
        !           130: 
        !           131: /* Indexed by N, set of hard regs preferred by allocno N.
        !           132:    This is used to make allocnos go into regs that are copied to or from them,
        !           133:    when possible, to reduce register shuffling.  */
        !           134: 
        !           135: static HARD_REG_SET *hard_reg_preferences;
        !           136: 
        !           137: /* Similar, but just counts register preferences made in simple copy
        !           138:    operations, rather than arithmetic.  These are given priority because
        !           139:    we can always eliminate an insn by using these, but using a register
        !           140:    in the above list won't always eliminate an insn.  */
        !           141: 
        !           142: static HARD_REG_SET *hard_reg_copy_preferences;
        !           143: 
        !           144: /* Similar to hard_reg_preferences, but includes bits for subsequent
        !           145:    registers when an allocno is multi-word.  The above variable is used for
        !           146:    allocation while this is used to build reg_someone_prefers, below.  */
        !           147: 
        !           148: static HARD_REG_SET *hard_reg_full_preferences;
        !           149: 
        !           150: /* Indexed by N, set of hard registers that some later allocno has a
        !           151:    preference for.  */
        !           152: 
        !           153: static HARD_REG_SET *regs_someone_prefers;
        !           154: 
        !           155: /* Set of registers that global-alloc isn't supposed to use.  */
        !           156: 
        !           157: static HARD_REG_SET no_global_alloc_regs;
        !           158: 
        !           159: /* Set of registers used so far.  */
        !           160: 
        !           161: static HARD_REG_SET regs_used_so_far;
        !           162: 
        !           163: /* Number of calls crossed by each allocno.  */
        !           164: 
        !           165: static int *allocno_calls_crossed;
        !           166: 
        !           167: /* Number of refs (weighted) to each allocno.  */
        !           168: 
        !           169: static int *allocno_n_refs;
        !           170: 
        !           171: /* Guess at live length of each allocno.
        !           172:    This is actually the max of the live lengths of the regs.  */
        !           173: 
        !           174: static int *allocno_live_length;
        !           175: 
        !           176: /* Number of refs (weighted) to each hard reg, as used by local alloc.
        !           177:    It is zero for a reg that contains global pseudos or is explicitly used.  */
        !           178: 
        !           179: static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
        !           180: 
        !           181: /* Guess at live length of each hard reg, as used by local alloc.
        !           182:    This is actually the sum of the live lengths of the specific regs.  */
        !           183: 
        !           184: static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
        !           185: 
        !           186: /* Test a bit in TABLE, a vector of HARD_REG_SETs,
        !           187:    for vector element I, and hard register number J.  */
        !           188: 
        !           189: #define REGBITP(TABLE, I, J)     TEST_HARD_REG_BIT (TABLE[I], J)
        !           190: 
        !           191: /* Set to 1 a bit in a vector of HARD_REG_SETs.  Works like REGBITP.  */
        !           192: 
        !           193: #define SET_REGBIT(TABLE, I, J)  SET_HARD_REG_BIT (TABLE[I], J)
        !           194: 
        !           195: /* Bit mask for allocnos live at current point in the scan.  */
        !           196: 
        !           197: static int *allocnos_live;
        !           198: 
        !           199: #define INT_BITS HOST_BITS_PER_INT
        !           200: 
        !           201: /* Test, set or clear bit number I in allocnos_live,
        !           202:    a bit vector indexed by allocno.  */
        !           203: 
        !           204: #define ALLOCNO_LIVE_P(I) \
        !           205:   (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS)))
        !           206: 
        !           207: #define SET_ALLOCNO_LIVE(I) \
        !           208:   (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
        !           209: 
        !           210: #define CLEAR_ALLOCNO_LIVE(I) \
        !           211:   (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
        !           212: 
        !           213: /* This is turned off because it doesn't work right for DImode.
        !           214:    (And it is only used for DImode, so the other cases are worthless.)
        !           215:    The problem is that it isn't true that there is NO possibility of conflict;
        !           216:    only that there is no conflict if the two pseudos get the exact same regs.
        !           217:    If they were allocated with a partial overlap, there would be a conflict.
        !           218:    We can't safely turn off the conflict unless we have another way to
        !           219:    prevent the partial overlap.
        !           220: 
        !           221:    Idea: change hard_reg_conflicts so that instead of recording which
        !           222:    hard regs the allocno may not overlap, it records where the allocno
        !           223:    may not start.  Change both where it is used and where it is updated.
        !           224:    Then there is a way to record that (reg:DI 108) may start at 10
        !           225:    but not at 9 or 11.  There is still the question of how to record
        !           226:    this semi-conflict between two pseudos.  */
        !           227: #if 0
        !           228: /* Reg pairs for which conflict after the current insn
        !           229:    is inhibited by a REG_NO_CONFLICT note.
        !           230:    If the table gets full, we ignore any other notes--that is conservative.  */
        !           231: #define NUM_NO_CONFLICT_PAIRS 4
        !           232: /* Number of pairs in use in this insn.  */
        !           233: int n_no_conflict_pairs;
        !           234: static struct { int allocno1, allocno2;}
        !           235:   no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
        !           236: #endif /* 0 */
        !           237: 
        !           238: /* Record all regs that are set in any one insn.
        !           239:    Communication from mark_reg_{store,clobber} and global_conflicts.  */
        !           240: 
        !           241: static rtx *regs_set;
        !           242: static int n_regs_set;
        !           243: 
        !           244: /* All register that can be eliminated.  */
        !           245: 
        !           246: static HARD_REG_SET eliminable_regset;
        !           247: 
        !           248: static int allocno_compare ();
        !           249: static void mark_reg_store ();
        !           250: static void mark_reg_clobber ();
        !           251: static void mark_reg_live_nc ();
        !           252: static void mark_reg_death ();
        !           253: static void dump_conflicts ();
        !           254: void dump_global_regs ();
        !           255: static void find_reg ();
        !           256: static void global_conflicts ();
        !           257: static void expand_preferences ();
        !           258: static void prune_preferences ();
        !           259: static void record_conflicts ();
        !           260: static void set_preference ();
        !           261: 
        !           262: /* Perform allocation of pseudo-registers not allocated by local_alloc.
        !           263:    FILE is a file to output debugging information on,
        !           264:    or zero if such output is not desired.  */
        !           265: 
        !           266: void
        !           267: global_alloc (file)
        !           268:      FILE *file;
        !           269: {
        !           270: #ifdef ELIMINABLE_REGS
        !           271:   static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
        !           272: #endif
        !           273:   register int i;
        !           274:   rtx x;
        !           275: 
        !           276:   max_allocno = 0;
        !           277: 
        !           278:   /* A machine may have certain hard registers that
        !           279:      are safe to use only within a basic block.  */
        !           280: 
        !           281:   CLEAR_HARD_REG_SET (no_global_alloc_regs);
        !           282: #ifdef OVERLAPPING_REGNO_P
        !           283:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           284:     if (OVERLAPPING_REGNO_P (i))
        !           285:       SET_HARD_REG_BIT (no_global_alloc_regs, i);
        !           286: #endif
        !           287: 
        !           288:   /* Build the regset of all eliminable registers and show we can't use those
        !           289:      that we already know won't be eliminated.  */
        !           290: #ifdef ELIMINABLE_REGS
        !           291:   for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
        !           292:     {
        !           293:       SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
        !           294: 
        !           295:       if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
        !           296:          || (eliminables[i].from == FRAME_POINTER_REGNUM
        !           297:              && (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)))
        !           298:        SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
        !           299:     }
        !           300: #else
        !           301:   SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
        !           302: 
        !           303:   /* If we know we will definitely not be eliminating the frame pointer,
        !           304:      don't allocate it.  */
        !           305:   if (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)
        !           306:     SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
        !           307: #endif
        !           308: 
        !           309:   /* Track which registers have already been used.  Start with registers
        !           310:      explicitly in the rtl, then registers allocated by local register
        !           311:      allocation.  */
        !           312: 
        !           313:   CLEAR_HARD_REG_SET (regs_used_so_far);
        !           314: #ifdef LEAF_REGISTERS
        !           315:   /* If we are doing the leaf function optimization, and this is a leaf
        !           316:      function, it means that the registers that take work to save are those
        !           317:      that need a register window.  So prefer the ones that can be used in
        !           318:      a leaf function.  */
        !           319:   {
        !           320:     char *cheap_regs;
        !           321:     static char leaf_regs[] = LEAF_REGISTERS;
        !           322: 
        !           323:     if (only_leaf_regs_used () && leaf_function_p ())
        !           324:       cheap_regs = leaf_regs;
        !           325:     else
        !           326:       cheap_regs = call_used_regs;
        !           327:     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           328:       if (regs_ever_live[i] || cheap_regs[i])
        !           329:        SET_HARD_REG_BIT (regs_used_so_far, i);
        !           330:   }
        !           331: #else
        !           332:   /* We consider registers that do not have to be saved over calls as if
        !           333:      they were already used since there is no cost in using them.  */
        !           334:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           335:     if (regs_ever_live[i] || call_used_regs[i])
        !           336:       SET_HARD_REG_BIT (regs_used_so_far, i);
        !           337: #endif
        !           338: 
        !           339:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           340:     if (reg_renumber[i] >= 0)
        !           341:       SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
        !           342: 
        !           343:   /* Establish mappings from register number to allocation number
        !           344:      and vice versa.  In the process, count the allocnos.  */
        !           345: 
        !           346:   reg_allocno = (int *) alloca (max_regno * sizeof (int));
        !           347: 
        !           348:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           349:     reg_allocno[i] = -1;
        !           350: 
        !           351:   /* Initialize the shared-hard-reg mapping
        !           352:      from the list of pairs that may share.  */
        !           353:   reg_may_share = (int *) alloca (max_regno * sizeof (int));
        !           354:   bzero (reg_may_share, max_regno * sizeof (int));
        !           355:   for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
        !           356:     {
        !           357:       int r1 = REGNO (XEXP (x, 0));
        !           358:       int r2 = REGNO (XEXP (XEXP (x, 1), 0));
        !           359:       if (r1 > r2)
        !           360:        reg_may_share[r1] = r2;
        !           361:       else
        !           362:        reg_may_share[r2] = r1;
        !           363:     }
        !           364: 
        !           365:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           366:     /* Note that reg_live_length[i] < 0 indicates a "constant" reg
        !           367:        that we are supposed to refrain from putting in a hard reg.
        !           368:        -2 means do make an allocno but don't allocate it.  */
        !           369:     if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
        !           370:        /* Don't allocate pseudos that cross calls,
        !           371:           if this function receives a nonlocal goto.  */
        !           372:        && (! current_function_has_nonlocal_label
        !           373:            || reg_n_calls_crossed[i] == 0))
        !           374:       {
        !           375:        if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
        !           376:          reg_allocno[i] = reg_allocno[reg_may_share[i]];
        !           377:        else
        !           378:          reg_allocno[i] = max_allocno++;
        !           379:        if (reg_live_length[i] == 0)
        !           380:          abort ();
        !           381:       }
        !           382:     else
        !           383:       reg_allocno[i] = -1;
        !           384: 
        !           385:   allocno_reg = (int *) alloca (max_allocno * sizeof (int));
        !           386:   allocno_size = (int *) alloca (max_allocno * sizeof (int));
        !           387:   allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
        !           388:   allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
        !           389:   allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
        !           390:   bzero (allocno_size, max_allocno * sizeof (int));
        !           391:   bzero (allocno_calls_crossed, max_allocno * sizeof (int));
        !           392:   bzero (allocno_n_refs, max_allocno * sizeof (int));
        !           393:   bzero (allocno_live_length, max_allocno * sizeof (int));
        !           394: 
        !           395:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           396:     if (reg_allocno[i] >= 0)
        !           397:       {
        !           398:        int allocno = reg_allocno[i];
        !           399:        allocno_reg[allocno] = i;
        !           400:        allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
        !           401:        allocno_calls_crossed[allocno] += reg_n_calls_crossed[i];
        !           402:        allocno_n_refs[allocno] += reg_n_refs[i];
        !           403:        if (allocno_live_length[allocno] < reg_live_length[i])
        !           404:          allocno_live_length[allocno] = reg_live_length[i];
        !           405:       }
        !           406: 
        !           407:   /* Calculate amount of usage of each hard reg by pseudos
        !           408:      allocated by local-alloc.  This is to see if we want to
        !           409:      override it.  */
        !           410:   bzero (local_reg_live_length, sizeof local_reg_live_length);
        !           411:   bzero (local_reg_n_refs, sizeof local_reg_n_refs);
        !           412:   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
        !           413:     if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
        !           414:       {
        !           415:        int regno = reg_renumber[i];
        !           416:        int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
        !           417:        int j;
        !           418: 
        !           419:        for (j = regno; j < endregno; j++)
        !           420:          {
        !           421:            local_reg_n_refs[j] += reg_n_refs[i];
        !           422:            local_reg_live_length[j] += reg_live_length[i];
        !           423:          }
        !           424:       }
        !           425: 
        !           426:   /* We can't override local-alloc for a reg used not just by local-alloc.  */
        !           427:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           428:     if (regs_ever_live[i])
        !           429:       local_reg_n_refs[i] = 0;
        !           430: 
        !           431:   /* Allocate the space for the conflict and preference tables and
        !           432:      initialize them.  */
        !           433: 
        !           434:   hard_reg_conflicts
        !           435:     = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
        !           436:   bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
        !           437: 
        !           438:   hard_reg_preferences
        !           439:     = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
        !           440:   bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
        !           441:   
        !           442:   hard_reg_copy_preferences
        !           443:     = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
        !           444:   bzero (hard_reg_copy_preferences, max_allocno * sizeof (HARD_REG_SET));
        !           445:   
        !           446:   hard_reg_full_preferences
        !           447:     = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
        !           448:   bzero (hard_reg_full_preferences, max_allocno * sizeof (HARD_REG_SET));
        !           449:   
        !           450:   regs_someone_prefers
        !           451:     = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
        !           452:   bzero (regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
        !           453: 
        !           454:   allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
        !           455: 
        !           456:   conflicts = (int *) alloca (max_allocno * allocno_row_words * sizeof (int));
        !           457:   bzero (conflicts, max_allocno * allocno_row_words * sizeof (int));
        !           458: 
        !           459:   allocnos_live = (int *) alloca (allocno_row_words * sizeof (int));
        !           460: 
        !           461:   /* If there is work to be done (at least one reg to allocate),
        !           462:      perform global conflict analysis and allocate the regs.  */
        !           463: 
        !           464:   if (max_allocno > 0)
        !           465:     {
        !           466:       /* Scan all the insns and compute the conflicts among allocnos
        !           467:         and between allocnos and hard regs.  */
        !           468: 
        !           469:       global_conflicts ();
        !           470: 
        !           471:       /* Eliminate conflicts between pseudos and eliminable registers.  If
        !           472:         the register is not eliminated, the pseudo won't really be able to
        !           473:         live in the eliminable register, so the conflict doesn't matter.
        !           474:         If we do eliminate the register, the conflict will no longer exist.
        !           475:         So in either case, we can ignore the conflict.  Likewise for
        !           476:         preferences.  */
        !           477: 
        !           478:       for (i = 0; i < max_allocno; i++)
        !           479:        {
        !           480:          AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
        !           481:          AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
        !           482:                                  eliminable_regset);
        !           483:          AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
        !           484:        }
        !           485: 
        !           486:       /* Try to expand the preferences by merging them between allocnos.  */
        !           487: 
        !           488:       expand_preferences ();
        !           489: 
        !           490:       /* Determine the order to allocate the remaining pseudo registers.  */
        !           491: 
        !           492:       allocno_order = (int *) alloca (max_allocno * sizeof (int));
        !           493:       for (i = 0; i < max_allocno; i++)
        !           494:        allocno_order[i] = i;
        !           495: 
        !           496:       /* Default the size to 1, since allocno_compare uses it to divide by.
        !           497:         Also convert allocno_live_length of zero to -1.  A length of zero
        !           498:         can occur when all the registers for that allocno have reg_live_length
        !           499:         equal to -2.  In this case, we want to make an allocno, but not
        !           500:         allocate it.  So avoid the divide-by-zero and set it to a low
        !           501:         priority.  */
        !           502: 
        !           503:       for (i = 0; i < max_allocno; i++)
        !           504:        {
        !           505:          if (allocno_size[i] == 0)
        !           506:            allocno_size[i] = 1;
        !           507:          if (allocno_live_length[i] == 0)
        !           508:            allocno_live_length[i] = -1;
        !           509:        }
        !           510: 
        !           511:       qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
        !           512:       
        !           513:       prune_preferences ();
        !           514: 
        !           515:       if (file)
        !           516:        dump_conflicts (file);
        !           517: 
        !           518:       /* Try allocating them, one by one, in that order,
        !           519:         except for parameters marked with reg_live_length[regno] == -2.  */
        !           520: 
        !           521:       for (i = 0; i < max_allocno; i++)
        !           522:        if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
        !           523:          {
        !           524:            /* If we have more than one register class,
        !           525:               first try allocating in the class that is cheapest
        !           526:               for this pseudo-reg.  If that fails, try any reg.  */
        !           527:            if (N_REG_CLASSES > 1)
        !           528:              {
        !           529:                find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
        !           530:                if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
        !           531:                  continue;
        !           532:              }
        !           533:            if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]]))
        !           534:              find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
        !           535:          }
        !           536:     }
        !           537: 
        !           538:   /* Do the reloads now while the allocno data still exist, so that we can
        !           539:      try to assign new hard regs to any pseudo regs that are spilled.  */
        !           540: 
        !           541: #if 0 /* We need to eliminate regs even if there is no rtl code,
        !           542:         for the sake of debugging information.  */
        !           543:   if (n_basic_blocks > 0)
        !           544: #endif
        !           545:     reload (basic_block_head[0], 1, file);
        !           546: }
        !           547: 
        !           548: /* Sort predicate for ordering the allocnos.
        !           549:    Returns -1 (1) if *v1 should be allocated before (after) *v2.  */
        !           550: 
        !           551: static int
        !           552: allocno_compare (v1, v2)
        !           553:      int *v1, *v2;
        !           554: {
        !           555:   /* Note that the quotient will never be bigger than
        !           556:      the value of floor_log2 times the maximum number of
        !           557:      times a register can occur in one insn (surely less than 100).
        !           558:      Multiplying this by 10000 can't overflow.  */
        !           559:   register int pri1
        !           560:     = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
        !           561:        / (allocno_live_length[*v1] * allocno_size[*v1]))
        !           562:        * 10000);
        !           563:   register int pri2
        !           564:     = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
        !           565:        / (allocno_live_length[*v2] * allocno_size[*v2]))
        !           566:        * 10000);
        !           567:   if (pri2 - pri1)
        !           568:     return pri2 - pri1;
        !           569: 
        !           570:   /* If regs are equally good, sort by allocno,
        !           571:      so that the results of qsort leave nothing to chance.  */
        !           572:   return *v1 - *v2;
        !           573: }
        !           574: 
        !           575: /* Scan the rtl code and record all conflicts and register preferences in the
        !           576:    conflict matrices and preference tables.  */
        !           577: 
        !           578: static void
        !           579: global_conflicts ()
        !           580: {
        !           581:   register int b, i;
        !           582:   register rtx insn;
        !           583:   short *block_start_allocnos;
        !           584: 
        !           585:   /* Make a vector that mark_reg_{store,clobber} will store in.  */
        !           586:   regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
        !           587: 
        !           588:   block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
        !           589: 
        !           590:   for (b = 0; b < n_basic_blocks; b++)
        !           591:     {
        !           592:       bzero (allocnos_live, allocno_row_words * sizeof (int));
        !           593: 
        !           594:       /* Initialize table of registers currently live
        !           595:         to the state at the beginning of this basic block.
        !           596:         This also marks the conflicts among them.
        !           597: 
        !           598:         For pseudo-regs, there is only one bit for each one
        !           599:         no matter how many hard regs it occupies.
        !           600:         This is ok; we know the size from PSEUDO_REGNO_SIZE.
        !           601:         For explicit hard regs, we cannot know the size that way
        !           602:         since one hard reg can be used with various sizes.
        !           603:         Therefore, we must require that all the hard regs
        !           604:         implicitly live as part of a multi-word hard reg
        !           605:         are explicitly marked in basic_block_live_at_start.  */
        !           606: 
        !           607:       {
        !           608:        register int offset, bit;
        !           609:        register regset old = basic_block_live_at_start[b];
        !           610:        int ax = 0;
        !           611: 
        !           612: #ifdef HARD_REG_SET
        !           613:        hard_regs_live = old[0];
        !           614: #else
        !           615:        COPY_HARD_REG_SET (hard_regs_live, old);
        !           616: #endif
        !           617:        for (offset = 0, i = 0; offset < regset_size; offset++)
        !           618:          if (old[offset] == 0)
        !           619:            i += HOST_BITS_PER_INT;
        !           620:          else
        !           621:            for (bit = 1; bit; bit <<= 1, i++)
        !           622:              {
        !           623:                if (i >= max_regno)
        !           624:                  break;
        !           625:                if (old[offset] & bit)
        !           626:                  {
        !           627:                    register int a = reg_allocno[i];
        !           628:                    if (a >= 0)
        !           629:                      {
        !           630:                        SET_ALLOCNO_LIVE (a);
        !           631:                        block_start_allocnos[ax++] = a;
        !           632:                      }
        !           633:                    else if ((a = reg_renumber[i]) >= 0)
        !           634:                      mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
        !           635:                  }
        !           636:              }
        !           637: 
        !           638:        /* Record that each allocno now live conflicts with each other
        !           639:           allocno now live, and with each hard reg now live.  */
        !           640: 
        !           641:        record_conflicts (block_start_allocnos, ax);
        !           642:       }
        !           643: 
        !           644:       insn = basic_block_head[b];
        !           645: 
        !           646:       /* Scan the code of this basic block, noting which allocnos
        !           647:         and hard regs are born or die.  When one is born,
        !           648:         record a conflict with all others currently live.  */
        !           649: 
        !           650:       while (1)
        !           651:        {
        !           652:          register RTX_CODE code = GET_CODE (insn);
        !           653:          register rtx link;
        !           654: 
        !           655:          /* Make regs_set an empty set.  */
        !           656: 
        !           657:          n_regs_set = 0;
        !           658: 
        !           659:          if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
        !           660:            {
        !           661:              int i = 0;
        !           662: 
        !           663: #if 0
        !           664:              for (link = REG_NOTES (insn);
        !           665:                   link && i < NUM_NO_CONFLICT_PAIRS;
        !           666:                   link = XEXP (link, 1))
        !           667:                if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
        !           668:                  {
        !           669:                    no_conflict_pairs[i].allocno1
        !           670:                      = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
        !           671:                    no_conflict_pairs[i].allocno2
        !           672:                      = reg_allocno[REGNO (XEXP (link, 0))];
        !           673:                    i++;
        !           674:                  }
        !           675: #endif /* 0 */
        !           676: 
        !           677:              /* Mark any registers clobbered by INSN as live,
        !           678:                 so they conflict with the inputs.  */
        !           679: 
        !           680:              note_stores (PATTERN (insn), mark_reg_clobber);
        !           681: 
        !           682:              /* Mark any registers dead after INSN as dead now.  */
        !           683: 
        !           684:              for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
        !           685:                if (REG_NOTE_KIND (link) == REG_DEAD)
        !           686:                  mark_reg_death (XEXP (link, 0));
        !           687: 
        !           688:              /* Mark any registers set in INSN as live,
        !           689:                 and mark them as conflicting with all other live regs.
        !           690:                 Clobbers are processed again, so they conflict with
        !           691:                 the registers that are set.  */
        !           692: 
        !           693:              note_stores (PATTERN (insn), mark_reg_store);
        !           694: 
        !           695: #ifdef AUTO_INC_DEC
        !           696:              for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
        !           697:                if (REG_NOTE_KIND (link) == REG_INC)
        !           698:                  mark_reg_store (XEXP (link, 0), 0);
        !           699: #endif
        !           700: 
        !           701:              /* Mark any registers set in INSN and then never used.  */
        !           702: 
        !           703:              while (n_regs_set > 0)
        !           704:                if (find_regno_note (insn, REG_UNUSED,
        !           705:                                     REGNO (regs_set[--n_regs_set])))
        !           706:                  mark_reg_death (regs_set[n_regs_set]);
        !           707:            }
        !           708: 
        !           709:          if (insn == basic_block_end[b])
        !           710:            break;
        !           711:          insn = NEXT_INSN (insn);
        !           712:        }
        !           713:     }
        !           714: }
        !           715: /* Expand the preference information by looking for cases where one allocno
        !           716:    dies in an insn that sets an allocno.  If those two allocnos don't conflict,
        !           717:    merge any preferences between those allocnos.  */
        !           718: 
        !           719: static void
        !           720: expand_preferences ()
        !           721: {
        !           722:   rtx insn;
        !           723:   rtx link;
        !           724:   rtx set;
        !           725: 
        !           726:   /* We only try to handle the most common cases here.  Most of the cases
        !           727:      where this wins are reg-reg copies.  */
        !           728: 
        !           729:   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
        !           730:     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
        !           731:        && (set = single_set (insn)) != 0
        !           732:        && GET_CODE (SET_DEST (set)) == REG
        !           733:        && reg_allocno[REGNO (SET_DEST (set))] >= 0)
        !           734:       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
        !           735:        if (REG_NOTE_KIND (link) == REG_DEAD
        !           736:            && GET_CODE (XEXP (link, 0)) == REG
        !           737:            && reg_allocno[REGNO (XEXP (link, 0))] >= 0
        !           738:            && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
        !           739:                            reg_allocno[REGNO (XEXP (link, 0))])
        !           740:            && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
        !           741:                            reg_allocno[REGNO (SET_DEST (set))]))
        !           742:          {
        !           743:            int a1 = reg_allocno[REGNO (SET_DEST (set))];
        !           744:            int a2 = reg_allocno[REGNO (XEXP (link, 0))];
        !           745: 
        !           746:            if (XEXP (link, 0) == SET_SRC (set))
        !           747:              {
        !           748:                IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
        !           749:                                  hard_reg_copy_preferences[a2]);
        !           750:                IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
        !           751:                                  hard_reg_copy_preferences[a1]);
        !           752:              }
        !           753: 
        !           754:            IOR_HARD_REG_SET (hard_reg_preferences[a1],
        !           755:                              hard_reg_preferences[a2]);
        !           756:            IOR_HARD_REG_SET (hard_reg_preferences[a2],
        !           757:                              hard_reg_preferences[a1]);
        !           758:            IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
        !           759:                              hard_reg_full_preferences[a2]);
        !           760:            IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
        !           761:                              hard_reg_full_preferences[a1]);
        !           762:          }
        !           763: }
        !           764: 
        !           765: /* Prune the preferences for global registers to exclude registers that cannot
        !           766:    be used.
        !           767:    
        !           768:    Compute `regs_someone_prefers', which is a bitmask of the hard registers
        !           769:    that are preferred by conflicting registers of lower priority.  If possible,
        !           770:    we will avoid using these registers.  */
        !           771:    
        !           772: static void
        !           773: prune_preferences ()
        !           774: {
        !           775:   int i, j;
        !           776:   int allocno;
        !           777:   
        !           778:   /* Scan least most important to most important.
        !           779:      For each allocno, remove from preferences registers that cannot be used,
        !           780:      either because of conflicts or register type.  Then compute all registers
        !           781:      prefered by each lower-priority register that conflicts.  */
        !           782: 
        !           783:   for (i = max_allocno - 1; i >= 0; i--)
        !           784:     {
        !           785:       HARD_REG_SET temp;
        !           786: 
        !           787:       allocno = allocno_order[i];
        !           788:       COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
        !           789: 
        !           790:       if (allocno_calls_crossed[allocno] == 0)
        !           791:        IOR_HARD_REG_SET (temp, fixed_reg_set);
        !           792:       else
        !           793:        IOR_HARD_REG_SET (temp, call_used_reg_set);
        !           794: 
        !           795:       IOR_COMPL_HARD_REG_SET
        !           796:        (temp,
        !           797:         reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
        !           798: 
        !           799:       AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
        !           800:       AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
        !           801:       AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
        !           802: 
        !           803:       CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
        !           804: 
        !           805:       /* Merge in the preferences of lower-priority registers (they have
        !           806:         already been pruned).  If we also prefer some of those registers,
        !           807:         don't exclude them unless we are of a smaller size (in which case
        !           808:         we want to give the lower-priority allocno the first chance for
        !           809:         these registers).  */
        !           810:       for (j = i + 1; j < max_allocno; j++)
        !           811:        if (CONFLICTP (allocno, allocno_order[j]))
        !           812:          {
        !           813:            COPY_HARD_REG_SET (temp,
        !           814:                               hard_reg_full_preferences[allocno_order[j]]);
        !           815:            if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
        !           816:              AND_COMPL_HARD_REG_SET (temp,
        !           817:                                      hard_reg_full_preferences[allocno]);
        !           818:                               
        !           819:            IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
        !           820:          }
        !           821:     }
        !           822: }
        !           823: 
        !           824: /* Assign a hard register to ALLOCNO; look for one that is the beginning
        !           825:    of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
        !           826:    The registers marked in PREFREGS are tried first.
        !           827: 
        !           828:    LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
        !           829:    be used for this allocation.
        !           830: 
        !           831:    If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
        !           832:    Otherwise ignore that preferred class.
        !           833: 
        !           834:    If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
        !           835:    will have to be saved and restored at calls.
        !           836: 
        !           837:    RETRYING is nonzero if this is called from retry_global_alloc.
        !           838: 
        !           839:    If we find one, record it in reg_renumber.
        !           840:    If not, do nothing.  */
        !           841: 
        !           842: static void
        !           843: find_reg (allocno, losers, all_regs_p, accept_call_clobbered, retrying)
        !           844:      int allocno;
        !           845:      HARD_REG_SET losers;
        !           846:      int all_regs_p;
        !           847:      int accept_call_clobbered;
        !           848:      int retrying;
        !           849: {
        !           850:   register int i, best_reg, pass;
        !           851: #ifdef HARD_REG_SET
        !           852:   register             /* Declare it register if it's a scalar.  */
        !           853: #endif
        !           854:     HARD_REG_SET used, used1, used2;
        !           855: 
        !           856:   enum reg_class class 
        !           857:     = all_regs_p ? ALL_REGS : reg_preferred_class (allocno_reg[allocno]);
        !           858:   enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
        !           859: 
        !           860:   if (accept_call_clobbered)
        !           861:     COPY_HARD_REG_SET (used1, call_fixed_reg_set);
        !           862:   else if (allocno_calls_crossed[allocno] == 0)
        !           863:     COPY_HARD_REG_SET (used1, fixed_reg_set);
        !           864:   else
        !           865:     COPY_HARD_REG_SET (used1, call_used_reg_set);
        !           866: 
        !           867:   /* Some registers should not be allocated in global-alloc.  */
        !           868:   IOR_HARD_REG_SET (used1, no_global_alloc_regs);
        !           869:   if (losers)
        !           870:     IOR_HARD_REG_SET (used1, losers);
        !           871: 
        !           872:   IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
        !           873:   COPY_HARD_REG_SET (used2, used1);
        !           874: 
        !           875:   IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
        !           876: 
        !           877:   /* Try each hard reg to see if it fits.  Do this in two passes.
        !           878:      In the first pass, skip registers that are prefered by some other pseudo
        !           879:      to give it a better chance of getting one of those registers.  Only if
        !           880:      we can't get a register when excluding those do we take one of them.
        !           881:      However, we never allocate a register for the first time in pass 0.  */
        !           882: 
        !           883:   COPY_HARD_REG_SET (used, used1);
        !           884:   IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
        !           885:   IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
        !           886:   
        !           887:   best_reg = -1;
        !           888:   for (i = FIRST_PSEUDO_REGISTER, pass = 0;
        !           889:        pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
        !           890:        pass++)
        !           891:     {
        !           892:       if (pass == 1)
        !           893:        COPY_HARD_REG_SET (used, used1);
        !           894:       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           895:        {
        !           896: #ifdef REG_ALLOC_ORDER
        !           897:          int regno = reg_alloc_order[i];
        !           898: #else
        !           899:          int regno = i;
        !           900: #endif
        !           901:          if (! TEST_HARD_REG_BIT (used, regno)
        !           902:              && HARD_REGNO_MODE_OK (regno, mode))
        !           903:            {
        !           904:              register int j;
        !           905:              register int lim = regno + HARD_REGNO_NREGS (regno, mode);
        !           906:              for (j = regno + 1;
        !           907:                   (j < lim
        !           908:                    && ! TEST_HARD_REG_BIT (used, j));
        !           909:                   j++);
        !           910:              if (j == lim)
        !           911:                {
        !           912:                  best_reg = regno;
        !           913:                  break;
        !           914:                }
        !           915: #ifndef REG_ALLOC_ORDER
        !           916:              i = j;                    /* Skip starting points we know will lose */
        !           917: #endif
        !           918:            }
        !           919:          }
        !           920:       }
        !           921: 
        !           922:   /* See if there is a preferred register with the same class as the register
        !           923:      we allocated above.  Making this restriction prevents register
        !           924:      preferencing from creating worse register allocation.
        !           925: 
        !           926:      Remove from the preferred registers and conflicting registers.  Note that
        !           927:      additional conflicts may have been added after `prune_preferences' was
        !           928:      called. 
        !           929: 
        !           930:      First do this for those register with copy preferences, then all
        !           931:      preferred registers.  */
        !           932: 
        !           933:   AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
        !           934:   GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
        !           935:                         reg_class_contents[(int) NO_REGS], no_copy_prefs);
        !           936: 
        !           937:   if (best_reg >= 0)
        !           938:     {
        !           939:       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           940:        if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
        !           941:            && HARD_REGNO_MODE_OK (i, mode)
        !           942:            && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
        !           943:                || reg_class_subset_p (REGNO_REG_CLASS (i),
        !           944:                                       REGNO_REG_CLASS (best_reg))
        !           945:                || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
        !           946:                                       REGNO_REG_CLASS (i))))
        !           947:            {
        !           948:              register int j;
        !           949:              register int lim = i + HARD_REGNO_NREGS (i, mode);
        !           950:              for (j = i + 1;
        !           951:                   (j < lim
        !           952:                    && ! TEST_HARD_REG_BIT (used, j)
        !           953:                    && (REGNO_REG_CLASS (j)
        !           954:                        == REGNO_REG_CLASS (best_reg + (j - i))
        !           955:                        || reg_class_subset_p (REGNO_REG_CLASS (j),
        !           956:                                               REGNO_REG_CLASS (best_reg + (j - i)))
        !           957:                        || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
        !           958:                                               REGNO_REG_CLASS (j))));
        !           959:                   j++);
        !           960:              if (j == lim)
        !           961:                {
        !           962:                  best_reg = i;
        !           963:                  goto no_prefs;
        !           964:                }
        !           965:            }
        !           966:     }
        !           967:  no_copy_prefs:
        !           968: 
        !           969:   AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
        !           970:   GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
        !           971:                         reg_class_contents[(int) NO_REGS], no_prefs);
        !           972: 
        !           973:   if (best_reg >= 0)
        !           974:     {
        !           975:       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !           976:        if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
        !           977:            && HARD_REGNO_MODE_OK (i, mode)
        !           978:            && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
        !           979:                || reg_class_subset_p (REGNO_REG_CLASS (i),
        !           980:                                       REGNO_REG_CLASS (best_reg))
        !           981:                || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
        !           982:                                       REGNO_REG_CLASS (i))))
        !           983:            {
        !           984:              register int j;
        !           985:              register int lim = i + HARD_REGNO_NREGS (i, mode);
        !           986:              for (j = i + 1;
        !           987:                   (j < lim
        !           988:                    && ! TEST_HARD_REG_BIT (used, j)
        !           989:                    && (REGNO_REG_CLASS (j)
        !           990:                        == REGNO_REG_CLASS (best_reg + (j - i))
        !           991:                        || reg_class_subset_p (REGNO_REG_CLASS (j),
        !           992:                                               REGNO_REG_CLASS (best_reg + (j - i)))
        !           993:                        || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
        !           994:                                               REGNO_REG_CLASS (j))));
        !           995:                   j++);
        !           996:              if (j == lim)
        !           997:                {
        !           998:                  best_reg = i;
        !           999:                  break;
        !          1000:                }
        !          1001:            }
        !          1002:     }
        !          1003:  no_prefs:
        !          1004: 
        !          1005:   /* If we haven't succeeded yet, try with caller-saves.  */
        !          1006:   if (flag_caller_saves && best_reg < 0)
        !          1007:     {
        !          1008:       /* Did not find a register.  If it would be profitable to
        !          1009:         allocate a call-clobbered register and save and restore it
        !          1010:         around calls, do that.  */
        !          1011:       if (! accept_call_clobbered
        !          1012:          && allocno_calls_crossed[allocno] != 0
        !          1013:          && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
        !          1014:                                     allocno_calls_crossed[allocno]))
        !          1015:        {
        !          1016:          find_reg (allocno, losers, all_regs_p, 1, retrying);
        !          1017:          if (reg_renumber[allocno_reg[allocno]] >= 0)
        !          1018:            {
        !          1019:              caller_save_needed = 1;
        !          1020:              return;
        !          1021:            }
        !          1022:        }
        !          1023:     }
        !          1024: 
        !          1025:   /* If we haven't succeeded yet,
        !          1026:      see if some hard reg that conflicts with us
        !          1027:      was utilized poorly by local-alloc.
        !          1028:      If so, kick out the regs that were put there by local-alloc
        !          1029:      so we can use it instead.  */
        !          1030:   if (best_reg < 0 && !retrying
        !          1031:       /* Let's not bother with multi-reg allocnos.  */
        !          1032:       && allocno_size[allocno] == 1)
        !          1033:     {
        !          1034:       /* Count from the end, to find the least-used ones first.  */
        !          1035:       for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
        !          1036:        if (local_reg_n_refs[i] != 0
        !          1037:            /* Don't use a reg no good for this pseudo.  */
        !          1038:            && ! TEST_HARD_REG_BIT (used2, i)
        !          1039:            && HARD_REGNO_MODE_OK (i, mode)
        !          1040:            && ((double) local_reg_n_refs[i] / local_reg_live_length[i]
        !          1041:                < ((double) allocno_n_refs[allocno]
        !          1042:                   / allocno_live_length[allocno])))
        !          1043:          {
        !          1044:            /* Hard reg I was used less in total by local regs
        !          1045:               than it would be used by this one allocno!  */
        !          1046:            int k;
        !          1047:            for (k = 0; k < max_regno; k++)
        !          1048:              if (reg_renumber[k] >= 0)
        !          1049:                {
        !          1050:                  int regno = reg_renumber[k];
        !          1051:                  int endregno
        !          1052:                    = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (k));
        !          1053: 
        !          1054:                  if (i >= regno && i < endregno)
        !          1055:                    reg_renumber[k] = -1;
        !          1056:                }
        !          1057: 
        !          1058:            best_reg = i;
        !          1059:            break;
        !          1060:          }
        !          1061:     }
        !          1062: 
        !          1063:   /* Did we find a register?  */
        !          1064: 
        !          1065:   if (best_reg >= 0)
        !          1066:     {
        !          1067:       register int lim, j;
        !          1068:       HARD_REG_SET this_reg;
        !          1069: 
        !          1070:       /* Yes.  Record it as the hard register of this pseudo-reg.  */
        !          1071:       reg_renumber[allocno_reg[allocno]] = best_reg;
        !          1072:       /* Also of any pseudo-regs that share with it.  */
        !          1073:       if (reg_may_share[allocno_reg[allocno]])
        !          1074:        for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
        !          1075:          if (reg_allocno[j] == allocno)
        !          1076:            reg_renumber[j] = best_reg;
        !          1077: 
        !          1078:       /* Make a set of the hard regs being allocated.  */
        !          1079:       CLEAR_HARD_REG_SET (this_reg);
        !          1080:       lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
        !          1081:       for (j = best_reg; j < lim; j++)
        !          1082:        {
        !          1083:          SET_HARD_REG_BIT (this_reg, j);
        !          1084:          SET_HARD_REG_BIT (regs_used_so_far, j);
        !          1085:          /* This is no longer a reg used just by local regs.  */
        !          1086:          local_reg_n_refs[j] = 0;
        !          1087:        }
        !          1088:       /* For each other pseudo-reg conflicting with this one,
        !          1089:         mark it as conflicting with the hard regs this one occupies.  */
        !          1090:       lim = allocno;
        !          1091:       for (j = 0; j < max_allocno; j++)
        !          1092:        if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
        !          1093:          {
        !          1094:            IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
        !          1095:          }
        !          1096:     }
        !          1097: }
        !          1098: 
        !          1099: /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
        !          1100:    Perhaps it had previously seemed not worth a hard reg,
        !          1101:    or perhaps its old hard reg has been commandeered for reloads.
        !          1102:    FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
        !          1103:    they do not appear to be allocated.
        !          1104:    If FORBIDDEN_REGS is zero, no regs are forbidden.  */
        !          1105: 
        !          1106: void
        !          1107: retry_global_alloc (regno, forbidden_regs)
        !          1108:      int regno;
        !          1109:      HARD_REG_SET forbidden_regs;
        !          1110: {
        !          1111:   int allocno = reg_allocno[regno];
        !          1112:   if (allocno >= 0)
        !          1113:     {
        !          1114:       /* If we have more than one register class,
        !          1115:         first try allocating in the class that is cheapest
        !          1116:         for this pseudo-reg.  If that fails, try any reg.  */
        !          1117:       if (N_REG_CLASSES > 1)
        !          1118:        find_reg (allocno, forbidden_regs, 0, 0, 1);
        !          1119:       if (reg_renumber[regno] < 0
        !          1120:          && !reg_preferred_or_nothing (regno))
        !          1121:        find_reg (allocno, forbidden_regs, 1, 0, 1);
        !          1122: 
        !          1123:       /* If we found a register, modify the RTL for the register to
        !          1124:         show the hard register, and mark that register live.  */
        !          1125:       if (reg_renumber[regno] >= 0)
        !          1126:        {
        !          1127:          REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
        !          1128:          mark_home_live (regno);
        !          1129:        }
        !          1130:     }
        !          1131: }
        !          1132: 
        !          1133: /* Record a conflict between register REGNO
        !          1134:    and everything currently live.
        !          1135:    REGNO must not be a pseudo reg that was allocated
        !          1136:    by local_alloc; such numbers must be translated through
        !          1137:    reg_renumber before calling here.  */
        !          1138: 
        !          1139: static void
        !          1140: record_one_conflict (regno)
        !          1141:      int regno;
        !          1142: {
        !          1143:   register int j;
        !          1144: 
        !          1145:   if (regno < FIRST_PSEUDO_REGISTER)
        !          1146:     /* When a hard register becomes live,
        !          1147:        record conflicts with live pseudo regs.  */
        !          1148:     for (j = 0; j < max_allocno; j++)
        !          1149:       {
        !          1150:        if (ALLOCNO_LIVE_P (j))
        !          1151:          SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
        !          1152:       }
        !          1153:   else
        !          1154:     /* When a pseudo-register becomes live,
        !          1155:        record conflicts first with hard regs,
        !          1156:        then with other pseudo regs.  */
        !          1157:     {
        !          1158:       register int ialloc = reg_allocno[regno];
        !          1159:       register int ialloc_prod = ialloc * allocno_row_words;
        !          1160:       IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
        !          1161:       for (j = allocno_row_words - 1; j >= 0; j--)
        !          1162:        {
        !          1163: #if 0
        !          1164:          int k;
        !          1165:          for (k = 0; k < n_no_conflict_pairs; k++)
        !          1166:            if (! ((j == no_conflict_pairs[k].allocno1
        !          1167:                    && ialloc == no_conflict_pairs[k].allocno2)
        !          1168:                   ||
        !          1169:                   (j == no_conflict_pairs[k].allocno2
        !          1170:                    && ialloc == no_conflict_pairs[k].allocno1)))
        !          1171: #endif /* 0 */
        !          1172:              conflicts[ialloc_prod + j] |= allocnos_live[j];
        !          1173:        }
        !          1174:     }
        !          1175: }
        !          1176: 
        !          1177: /* Record all allocnos currently live as conflicting
        !          1178:    with each other and with all hard regs currently live.
        !          1179:    ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
        !          1180:    are currently live.  Their bits are also flagged in allocnos_live.  */
        !          1181: 
        !          1182: static void
        !          1183: record_conflicts (allocno_vec, len)
        !          1184:      register short *allocno_vec;
        !          1185:      register int len;
        !          1186: {
        !          1187:   register int allocno;
        !          1188:   register int j;
        !          1189:   register int ialloc_prod;
        !          1190: 
        !          1191:   while (--len >= 0)
        !          1192:     {
        !          1193:       allocno = allocno_vec[len];
        !          1194:       ialloc_prod = allocno * allocno_row_words;
        !          1195:       IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
        !          1196:       for (j = allocno_row_words - 1; j >= 0; j--)
        !          1197:        conflicts[ialloc_prod + j] |= allocnos_live[j];
        !          1198:     }
        !          1199: }
        !          1200: 
        !          1201: /* Handle the case where REG is set by the insn being scanned,
        !          1202:    during the forward scan to accumulate conflicts.
        !          1203:    Store a 1 in regs_live or allocnos_live for this register, record how many
        !          1204:    consecutive hardware registers it actually needs,
        !          1205:    and record a conflict with all other registers already live.
        !          1206: 
        !          1207:    Note that even if REG does not remain alive after this insn,
        !          1208:    we must mark it here as live, to ensure a conflict between
        !          1209:    REG and any other regs set in this insn that really do live.
        !          1210:    This is because those other regs could be considered after this.
        !          1211: 
        !          1212:    REG might actually be something other than a register;
        !          1213:    if so, we do nothing.
        !          1214: 
        !          1215:    SETTER is 0 if this register was modified by an auto-increment (i.e.,
        !          1216:    a REG_INC note was found for it).
        !          1217: 
        !          1218:    CLOBBERs are processed here by calling mark_reg_clobber.  */ 
        !          1219: 
        !          1220: static void
        !          1221: mark_reg_store (orig_reg, setter)
        !          1222:      rtx orig_reg, setter;
        !          1223: {
        !          1224:   register int regno;
        !          1225:   register rtx reg = orig_reg;
        !          1226: 
        !          1227:   /* WORD is which word of a multi-register group is being stored.
        !          1228:      For the case where the store is actually into a SUBREG of REG.
        !          1229:      Except we don't use it; I believe the entire REG needs to be
        !          1230:      made live.  */
        !          1231:   int word = 0;
        !          1232: 
        !          1233:   if (GET_CODE (reg) == SUBREG)
        !          1234:     {
        !          1235:       word = SUBREG_WORD (reg);
        !          1236:       reg = SUBREG_REG (reg);
        !          1237:     }
        !          1238: 
        !          1239:   if (GET_CODE (reg) != REG)
        !          1240:     return;
        !          1241: 
        !          1242:   if (setter && GET_CODE (setter) == CLOBBER)
        !          1243:     {
        !          1244:       /* A clobber of a register should be processed here too.  */
        !          1245:       mark_reg_clobber (orig_reg, setter);
        !          1246:       return;
        !          1247:     }
        !          1248: 
        !          1249:   regs_set[n_regs_set++] = reg;
        !          1250: 
        !          1251:   if (setter)
        !          1252:     set_preference (reg, SET_SRC (setter));
        !          1253: 
        !          1254:   regno = REGNO (reg);
        !          1255: 
        !          1256:   if (reg_renumber[regno] >= 0)
        !          1257:     regno = reg_renumber[regno] /* + word */;
        !          1258: 
        !          1259:   /* Either this is one of the max_allocno pseudo regs not allocated,
        !          1260:      or it is or has a hardware reg.  First handle the pseudo-regs.  */
        !          1261:   if (regno >= FIRST_PSEUDO_REGISTER)
        !          1262:     {
        !          1263:       if (reg_allocno[regno] >= 0)
        !          1264:        {
        !          1265:          SET_ALLOCNO_LIVE (reg_allocno[regno]);
        !          1266:          record_one_conflict (regno);
        !          1267:        }
        !          1268:     }
        !          1269:   /* Handle hardware regs (and pseudos allocated to hard regs).  */
        !          1270:   else if (! fixed_regs[regno])
        !          1271:     {
        !          1272:       register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
        !          1273:       while (regno < last)
        !          1274:        {
        !          1275:          record_one_conflict (regno);
        !          1276:          SET_HARD_REG_BIT (hard_regs_live, regno);
        !          1277:          regno++;
        !          1278:        }
        !          1279:     }
        !          1280: }
        !          1281: 
        !          1282: /* Like mark_reg_set except notice just CLOBBERs; ignore SETs.  */
        !          1283: 
        !          1284: static void
        !          1285: mark_reg_clobber (reg, setter)
        !          1286:      rtx reg, setter;
        !          1287: {
        !          1288:   register int regno;
        !          1289: 
        !          1290:   /* WORD is which word of a multi-register group is being stored.
        !          1291:      For the case where the store is actually into a SUBREG of REG.
        !          1292:      Except we don't use it; I believe the entire REG needs to be
        !          1293:      made live.  */
        !          1294:   int word = 0;
        !          1295: 
        !          1296:   if (GET_CODE (setter) != CLOBBER)
        !          1297:     return;
        !          1298: 
        !          1299:   if (GET_CODE (reg) == SUBREG)
        !          1300:     {
        !          1301:       word = SUBREG_WORD (reg);
        !          1302:       reg = SUBREG_REG (reg);
        !          1303:     }
        !          1304: 
        !          1305:   if (GET_CODE (reg) != REG)
        !          1306:     return;
        !          1307: 
        !          1308:   regs_set[n_regs_set++] = reg;
        !          1309: 
        !          1310:   regno = REGNO (reg);
        !          1311: 
        !          1312:   if (reg_renumber[regno] >= 0)
        !          1313:     regno = reg_renumber[regno] /* + word */;
        !          1314: 
        !          1315:   /* Either this is one of the max_allocno pseudo regs not allocated,
        !          1316:      or it is or has a hardware reg.  First handle the pseudo-regs.  */
        !          1317:   if (regno >= FIRST_PSEUDO_REGISTER)
        !          1318:     {
        !          1319:       if (reg_allocno[regno] >= 0)
        !          1320:        {
        !          1321:          SET_ALLOCNO_LIVE (reg_allocno[regno]);
        !          1322:          record_one_conflict (regno);
        !          1323:        }
        !          1324:     }
        !          1325:   /* Handle hardware regs (and pseudos allocated to hard regs).  */
        !          1326:   else if (! fixed_regs[regno])
        !          1327:     {
        !          1328:       register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
        !          1329:       while (regno < last)
        !          1330:        {
        !          1331:          record_one_conflict (regno);
        !          1332:          SET_HARD_REG_BIT (hard_regs_live, regno);
        !          1333:          regno++;
        !          1334:        }
        !          1335:     }
        !          1336: }
        !          1337: 
        !          1338: /* Mark REG as being dead (following the insn being scanned now).
        !          1339:    Store a 0 in regs_live or allocnos_live for this register.  */
        !          1340: 
        !          1341: static void
        !          1342: mark_reg_death (reg)
        !          1343:      rtx reg;
        !          1344: {
        !          1345:   register int regno = REGNO (reg);
        !          1346: 
        !          1347:   /* For pseudo reg, see if it has been assigned a hardware reg.  */
        !          1348:   if (reg_renumber[regno] >= 0)
        !          1349:     regno = reg_renumber[regno];
        !          1350: 
        !          1351:   /* Either this is one of the max_allocno pseudo regs not allocated,
        !          1352:      or it is a hardware reg.  First handle the pseudo-regs.  */
        !          1353:   if (regno >= FIRST_PSEUDO_REGISTER)
        !          1354:     {
        !          1355:       if (reg_allocno[regno] >= 0)
        !          1356:        CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
        !          1357:     }
        !          1358:   /* Handle hardware regs (and pseudos allocated to hard regs).  */
        !          1359:   else if (! fixed_regs[regno])
        !          1360:     {
        !          1361:       /* Pseudo regs already assigned hardware regs are treated
        !          1362:         almost the same as explicit hardware regs.  */
        !          1363:       register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
        !          1364:       while (regno < last)
        !          1365:        {
        !          1366:          CLEAR_HARD_REG_BIT (hard_regs_live, regno);
        !          1367:          regno++;
        !          1368:        }
        !          1369:     }
        !          1370: }
        !          1371: 
        !          1372: /* Mark hard reg REGNO as currently live, assuming machine mode MODE
        !          1373:    for the value stored in it.  MODE determines how many consecutive
        !          1374:    registers are actually in use.  Do not record conflicts;
        !          1375:    it is assumed that the caller will do that.  */
        !          1376: 
        !          1377: static void
        !          1378: mark_reg_live_nc (regno, mode)
        !          1379:      register int regno;
        !          1380:      enum machine_mode mode;
        !          1381: {
        !          1382:   register int last = regno + HARD_REGNO_NREGS (regno, mode);
        !          1383:   while (regno < last)
        !          1384:     {
        !          1385:       SET_HARD_REG_BIT (hard_regs_live, regno);
        !          1386:       regno++;
        !          1387:     }
        !          1388: }
        !          1389: 
        !          1390: /* Try to set a preference for an allocno to a hard register.
        !          1391:    We are passed DEST and SRC which are the operands of a SET.  It is known
        !          1392:    that SRC is a register.  If SRC or the first operand of SRC is a register,
        !          1393:    try to set a preference.  If one of the two is a hard register and the other
        !          1394:    is a pseudo-register, mark the preference.
        !          1395:    
        !          1396:    Note that we are not as agressive as local-alloc in trying to tie a
        !          1397:    pseudo-register to a hard register.  */
        !          1398: 
        !          1399: static void
        !          1400: set_preference (dest, src)
        !          1401:      rtx dest, src;
        !          1402: {
        !          1403:   int src_regno, dest_regno;
        !          1404:   /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
        !          1405:      to compensate for subregs in SRC or DEST.  */
        !          1406:   int offset = 0;
        !          1407:   int i;
        !          1408:   int copy = 1;
        !          1409: 
        !          1410:   if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
        !          1411:     src = XEXP (src, 0), copy = 0;
        !          1412: 
        !          1413:   /* Get the reg number for both SRC and DEST.
        !          1414:      If neither is a reg, give up.  */
        !          1415: 
        !          1416:   if (GET_CODE (src) == REG)
        !          1417:     src_regno = REGNO (src);
        !          1418:   else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
        !          1419:     {
        !          1420:       src_regno = REGNO (SUBREG_REG (src));
        !          1421:       offset += SUBREG_WORD (src);
        !          1422:     }
        !          1423:   else
        !          1424:     return;
        !          1425: 
        !          1426:   if (GET_CODE (dest) == REG)
        !          1427:     dest_regno = REGNO (dest);
        !          1428:   else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
        !          1429:     {
        !          1430:       dest_regno = REGNO (SUBREG_REG (dest));
        !          1431:       offset -= SUBREG_WORD (dest);
        !          1432:     }
        !          1433:   else
        !          1434:     return;
        !          1435: 
        !          1436:   /* Convert either or both to hard reg numbers.  */
        !          1437: 
        !          1438:   if (reg_renumber[src_regno] >= 0)
        !          1439:     src_regno = reg_renumber[src_regno];
        !          1440: 
        !          1441:   if (reg_renumber[dest_regno] >= 0)
        !          1442:     dest_regno = reg_renumber[dest_regno];
        !          1443: 
        !          1444:   /* Now if one is a hard reg and the other is a global pseudo
        !          1445:      then give the other a preference.  */
        !          1446: 
        !          1447:   if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
        !          1448:       && reg_allocno[src_regno] >= 0)
        !          1449:     {
        !          1450:       dest_regno -= offset;
        !          1451:       if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
        !          1452:        {
        !          1453:          if (copy)
        !          1454:            SET_REGBIT (hard_reg_copy_preferences,
        !          1455:                        reg_allocno[src_regno], dest_regno);
        !          1456: 
        !          1457:          SET_REGBIT (hard_reg_preferences,
        !          1458:                      reg_allocno[src_regno], dest_regno);
        !          1459:          for (i = dest_regno;
        !          1460:               i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
        !          1461:               i++)
        !          1462:            SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
        !          1463:        }
        !          1464:     }
        !          1465: 
        !          1466:   if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
        !          1467:       && reg_allocno[dest_regno] >= 0)
        !          1468:     {
        !          1469:       src_regno += offset;
        !          1470:       if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
        !          1471:        {
        !          1472:          if (copy)
        !          1473:            SET_REGBIT (hard_reg_copy_preferences,
        !          1474:                        reg_allocno[dest_regno], src_regno);
        !          1475: 
        !          1476:          SET_REGBIT (hard_reg_preferences,
        !          1477:                      reg_allocno[dest_regno], src_regno);
        !          1478:          for (i = src_regno;
        !          1479:               i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
        !          1480:               i++)
        !          1481:            SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
        !          1482:        }
        !          1483:     }
        !          1484: }
        !          1485: 
        !          1486: /* Indicate that hard register number FROM was eliminated and replaced with
        !          1487:    an offset from hard register number TO.  The status of hard registers live
        !          1488:    at the start of a basic block is updated by replacing a use of FROM with
        !          1489:    a use of TO.  */
        !          1490: 
        !          1491: void
        !          1492: mark_elimination (from, to)
        !          1493:      int from, to;
        !          1494: {
        !          1495:   int i;
        !          1496: 
        !          1497:   for (i = 0; i < n_basic_blocks; i++)
        !          1498:     if ((basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
        !          1499:         & (1 << (from % HOST_BITS_PER_INT))) != 0)
        !          1500:       {
        !          1501:        basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
        !          1502:          &= ~ (1 << (from % HOST_BITS_PER_INT));
        !          1503:        basic_block_live_at_start[i][to / HOST_BITS_PER_INT]
        !          1504:          |= (1 << (to % HOST_BITS_PER_INT));
        !          1505:       }
        !          1506: }
        !          1507: 
        !          1508: /* Print debugging trace information if -greg switch is given,
        !          1509:    showing the information on which the allocation decisions are based.  */
        !          1510: 
        !          1511: static void
        !          1512: dump_conflicts (file)
        !          1513:      FILE *file;
        !          1514: {
        !          1515:   register int i;
        !          1516:   register int has_preferences;
        !          1517:   fprintf (file, ";; %d regs to allocate:", max_allocno);
        !          1518:   for (i = 0; i < max_allocno; i++)
        !          1519:     {
        !          1520:       int j;
        !          1521:       fprintf (file, " %d", allocno_reg[allocno_order[i]]);
        !          1522:       for (j = 0; j < max_regno; j++)
        !          1523:        if (reg_allocno[j] == allocno_order[i]
        !          1524:            && j != allocno_reg[allocno_order[i]])
        !          1525:          fprintf (file, "+%d", j);
        !          1526:       if (allocno_size[allocno_order[i]] != 1)
        !          1527:        fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
        !          1528:     }
        !          1529:   fprintf (file, "\n");
        !          1530: 
        !          1531:   for (i = 0; i < max_allocno; i++)
        !          1532:     {
        !          1533:       register int j;
        !          1534:       fprintf (file, ";; %d conflicts:", allocno_reg[i]);
        !          1535:       for (j = 0; j < max_allocno; j++)
        !          1536:        if (CONFLICTP (i, j) || CONFLICTP (j, i))
        !          1537:          fprintf (file, " %d", allocno_reg[j]);
        !          1538:       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
        !          1539:        if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
        !          1540:          fprintf (file, " %d", j);
        !          1541:       fprintf (file, "\n");
        !          1542: 
        !          1543:       has_preferences = 0;
        !          1544:       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
        !          1545:        if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
        !          1546:          has_preferences = 1;
        !          1547: 
        !          1548:       if (! has_preferences)
        !          1549:        continue;
        !          1550:       fprintf (file, ";; %d preferences:", allocno_reg[i]);
        !          1551:       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
        !          1552:        if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
        !          1553:          fprintf (file, " %d", j);
        !          1554:       fprintf (file, "\n");
        !          1555:     }
        !          1556:   fprintf (file, "\n");
        !          1557: }
        !          1558: 
        !          1559: void
        !          1560: dump_global_regs (file)
        !          1561:      FILE *file;
        !          1562: {
        !          1563:   register int i, j;
        !          1564:   
        !          1565:   fprintf (file, ";; Register dispositions:\n");
        !          1566:   for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
        !          1567:     if (reg_renumber[i] >= 0)
        !          1568:       {
        !          1569:        fprintf (file, "%d in %d  ", i, reg_renumber[i]);
        !          1570:         if (++j % 6 == 0)
        !          1571:          fprintf (file, "\n");
        !          1572:       }
        !          1573: 
        !          1574:   fprintf (file, "\n\n;; Hard regs used: ");
        !          1575:   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
        !          1576:     if (regs_ever_live[i])
        !          1577:       fprintf (file, " %d", i);
        !          1578:   fprintf (file, "\n\n");
        !          1579: }

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