Return to global.c CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/global.c, revision 1.1.1.4

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

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