diff options
Diffstat (limited to 'gcc-1.40/global-alloc.c')
| -rw-r--r-- | gcc-1.40/global-alloc.c | 1091 |
1 files changed, 1091 insertions, 0 deletions
diff --git a/gcc-1.40/global-alloc.c b/gcc-1.40/global-alloc.c new file mode 100644 index 0000000..8c6d7a3 --- /dev/null +++ b/gcc-1.40/global-alloc.c @@ -0,0 +1,1091 @@ +/* Allocate registers for pseudo-registers that span basic blocks. + Copyright (C) 1987, 1988 Free Software Foundation, Inc. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 1, or (at your option) +any later version. + +GNU CC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +#include <stdio.h> +#include "config.h" +#include "rtl.h" +#include "flags.h" +#include "basic-block.h" +#include "hard-reg-set.h" +#include "regs.h" +#include "insn-config.h" + +/* This pass of the compiler performs global register allocation. + It assigns hard register numbers to all the pseudo registers + that were not handled in local_alloc. Assignments are recorded + in the vector reg_renumber, not by changing the rtl code. + (Such changes are made by final). The entry point is + the function global_alloc. + + After allocation is complete, the reload pass is run as a subroutine + of this pass, so that when a pseudo reg loses its hard reg due to + spilling it is possible to make a second attempt to find a hard + reg for it. The reload pass is independent in other respects + and it is run even when stupid register allocation is in use. + + 1. count the pseudo-registers still needing allocation + and assign allocation-numbers (allocnos) to them. + Set up tables reg_allocno and allocno_reg to map + reg numbers to allocnos and vice versa. + max_allocno gets the number of allocnos in use. + + 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it. + Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix + for conflicts between allocnos and explicit hard register use + (which includes use of pseudo-registers allocated by local_alloc). + + 3. for each basic block + walk forward through the block, recording which + unallocated registers and which hardware registers are live. + Build the conflict matrix between the unallocated registers + and another of unallocated registers versus hardware registers. + Also record the preferred hardware registers + for each unallocated one. + + 4. Sort a table of the allocnos into order of + desirability of the variables. + + 5. Allocate the variables in that order; each if possible into + a preferred register, else into another register. */ + +/* Number of pseudo-registers still requiring allocation + (not allocated by local_allocate). */ + +static int max_allocno; + +/* Indexed by (pseudo) reg number, gives the allocno, or -1 + for pseudo registers already allocated by local_allocate. */ + +static int *reg_allocno; + +/* Indexed by allocno, gives the reg number. */ + +static int *allocno_reg; + +/* A vector of the integers from 0 to max_allocno-1, + sorted in the order of first-to-be-allocated first. */ + +static int *allocno_order; + +/* Indexed by an allocno, gives the number of consecutive + hard registers needed by that pseudo reg. */ + +static int *allocno_size; + +/* max_allocno by max_allocno array of bits, + recording whether two allocno's conflict (can't go in the same + hardware register). + + `conflicts' is not symmetric; a conflict between allocno's i and j + is recorded either in element i,j or in element j,i. */ + +static int *conflicts; + +/* Number of ints require to hold max_allocno bits. + This is the length of a row in `conflicts'. */ + +static int allocno_row_words; + +/* Two macros to test or store 1 in an element of `conflicts'. */ + +#define CONFLICTP(I, J) \ + (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ + & (1 << ((J) % INT_BITS))) + +#define SET_CONFLICT(I, J) \ + (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \ + |= (1 << ((J) % INT_BITS))) + +/* Set of hard regs currently live (during scan of all insns). */ + +static HARD_REG_SET hard_regs_live; + +/* Indexed by N, set of hard regs conflicting with allocno N. */ + +static HARD_REG_SET *hard_reg_conflicts; + +/* Indexed by N, set of hard regs preferred by allocno N. + This is used to make allocnos go into regs that are copied to or from them, + when possible, to reduce register shuffling. */ + +static HARD_REG_SET *hard_reg_preferences; + +/* Set of registers that some allocno has a preference for. */ + +static HARD_REG_SET regs_someone_prefers; + +/* Set of registers that global-alloc isn't supposed to use. */ + +static HARD_REG_SET no_global_alloc_regs; + +/* Test a bit in TABLE, a vector of HARD_REG_SETs, + for vector element I, and hard register number J. */ + +#define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J) + +/* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */ + +#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J) + +/* Bit mask for allocnos live at current point in the scan. */ + +static int *allocnos_live; + +#define INT_BITS HOST_BITS_PER_INT + +/* Test, set or clear bit number I in allocnos_live, + a bit vector indexed by allocno. */ + +#define ALLOCNO_LIVE_P(I) \ + (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS))) + +#define SET_ALLOCNO_LIVE(I) \ + (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS))) + +#define CLEAR_ALLOCNO_LIVE(I) \ + (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS))) + +/* Record all regs that are set in any one insn. + Communication from mark_reg_{store,clobber} and global_conflicts. */ + +static rtx *regs_set; +static int n_regs_set; + +static int allocno_compare (); +static void mark_reg_store (); +static void mark_reg_clobber (); +static void mark_reg_live_nc (); +static void mark_reg_death (); +static void dump_conflicts (); +static void find_reg (); +static void global_conflicts (); +static void record_conflicts (); +static void set_preference (); + +/* Perform allocation of pseudo-registers not allocated by local_alloc. + FILE is a file to output debugging information on, + or zero if such output is not desired. */ + +void +global_alloc (file) + FILE *file; +{ + register int i; + + max_allocno = 0; + + CLEAR_HARD_REG_SET (regs_someone_prefers); + + /* A machine may have certain hard registers that + are safe to use only within a basic block. */ + + CLEAR_HARD_REG_SET (no_global_alloc_regs); +#ifdef OVERLAPPING_REGNO_P + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (OVERLAPPING_REGNO_P (i)) + SET_HARD_REG_BIT (no_global_alloc_regs, i); +#endif + + /* Establish mappings from register number to allocation number + and vice versa. In the process, count the allocnos. */ + + reg_allocno = (int *) alloca (max_regno * sizeof (int)); + + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + reg_allocno[i] = -1; + + for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) + /* Note that reg_live_length[i] < 0 indicates a "constant" reg + that we are supposed to refrain from putting in a hard reg. + -2 means do make an allocno but don't allocate it. */ + if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1) + { + reg_allocno[i] = max_allocno++; + if (reg_live_length[i] == 0) + abort (); + } + else + reg_allocno[i] = -1; + + allocno_reg = (int *) alloca (max_allocno * sizeof (int)); + allocno_size = (int *) alloca (max_allocno * sizeof (int)); + bzero (allocno_size, max_allocno * sizeof (int)); + + for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) + if (reg_allocno[i] >= 0) + { + allocno_reg[reg_allocno[i]] = i; + allocno_size[reg_allocno[i]] = PSEUDO_REGNO_SIZE (i); + } + + /* Allocate the space for the conflict tables. */ + + hard_reg_conflicts = (HARD_REG_SET *) + alloca (max_allocno * sizeof (HARD_REG_SET)); + bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET)); + + hard_reg_preferences = (HARD_REG_SET *) + alloca (max_allocno * sizeof (HARD_REG_SET)); + bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET)); + + allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS; + + conflicts = (int *) + alloca (max_allocno * allocno_row_words * sizeof (int)); + bzero (conflicts, max_allocno * allocno_row_words * sizeof (int)); + + allocnos_live = (int *) alloca (allocno_row_words * sizeof (int)); + + /* If there is work to be done (at least one reg to allocate), + perform global conflict analysis and allocate the regs. */ + + if (max_allocno > 0) + { + /* Scan all the insns and compute the conflicts among allocnos + and between allocnos and hard regs. */ + + global_conflicts (); + + /* Determine the order to allocate the remaining pseudo registers. */ + + allocno_order = (int *) alloca (max_allocno * sizeof (int)); + for (i = 0; i < max_allocno; i++) + allocno_order[i] = i; + + /* Default the size to 1, since allocno_compare uses it to divide by. */ + + for (i = 0; i < max_allocno; i++) + if (allocno_size[i] == 0) + allocno_size[i] = 1; + + qsort (allocno_order, max_allocno, sizeof (int), allocno_compare); + + if (file) + dump_conflicts (file); + + /* Try allocating them, one by one, in that order, + except for parameters marked with reg_live_length[regno] == -2. */ + + for (i = 0; i < max_allocno; i++) + if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0) + { + /* If we have more than one register class, + first try allocating in the class that is cheapest + for this pseudo-reg. If that fails, try any reg. */ + if (N_REG_CLASSES > 1) + { + find_reg (allocno_order[i], 0, 0, 0, + hard_reg_preferences[allocno_order[i]]); + if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0) + continue; + } + if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]])) + find_reg (allocno_order[i], 0, 1, 0, + hard_reg_preferences[allocno_order[i]]); + } + } + + /* Do the reloads now while the allocno data still exist, so that we can + try to assign new hard regs to any pseudo regs that are spilled. */ + + if (n_basic_blocks > 0) + reload (basic_block_head[0], 1, file); +} + +/* Sort predicate for ordering the allocnos. + Returns -1 (1) if *v1 should be allocated before (after) *v2. */ + +static int +allocno_compare (v1, v2) + int *v1, *v2; +{ + register int r1 = allocno_reg[*v1]; + register int r2 = allocno_reg[*v2]; + /* Note that the quotient will never be bigger than + the value of floor_log2 times the maximum number of + times a register can occur in one insn (surely less than 100). + Multiplying this by 10000 can't overflow. */ + register int pri1 + = (((double) (floor_log2 (reg_n_refs[r1]) * reg_n_refs[r1]) + / (reg_live_length[r1] * allocno_size[*v1])) + * 10000); + register int pri2 + = (((double) (floor_log2 (reg_n_refs[r2]) * reg_n_refs[r2]) + / (reg_live_length[r2] * allocno_size[*v2])) + * 10000); + if (pri2 - pri1) + return pri2 - pri1; + + /* If regs are equally good, sort by allocno, + so that the results of qsort leave nothing to chance. */ + return *v1 - *v2; +} + +/* Scan the rtl code and record all conflicts in the conflict matrices. */ + +static void +global_conflicts () +{ + register int b, i; + register rtx insn; + short *block_start_allocnos; + + /* Make a vector that mark_reg_{store,clobber} will store in. */ + regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2); + + block_start_allocnos = (short *) alloca (max_allocno * sizeof (short)); + + for (b = 0; b < n_basic_blocks; b++) + { + bzero (allocnos_live, allocno_row_words * sizeof (int)); + + /* Initialize table of registers currently live + to the state at the beginning of this basic block. + This also marks the conflicts among them. + + For pseudo-regs, there is only one bit for each one + no matter how many hard regs it occupies. + This is ok; we know the size from PSEUDO_REGNO_SIZE. + For explicit hard regs, we cannot know the size that way + since one hard reg can be used with various sizes. + Therefore, we must require that all the hard regs + implicitly live as part of a multi-word hard reg + are explicitly marked in basic_block_live_at_start. */ + + { + register int offset, bit; + register regset old = basic_block_live_at_start[b]; + int ax = 0; + +#ifdef HARD_REG_SET + hard_regs_live = old[0]; +#else + COPY_HARD_REG_SET (hard_regs_live, old); +#endif + for (offset = 0, i = 0; offset < regset_size; offset++) + if (old[offset] == 0) + i += HOST_BITS_PER_INT; + else + for (bit = 1; bit; bit <<= 1, i++) + { + if (i >= max_regno) + break; + if (old[offset] & bit) + { + register int a = reg_allocno[i]; + if (a >= 0) + { + SET_ALLOCNO_LIVE (a); + block_start_allocnos[ax++] = a; + } + else if ((a = reg_renumber[i]) >= 0) + mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i)); + } + } + + /* Record that each allocno now live conflicts with each other + allocno now live, and with each hard reg now live. */ + + record_conflicts (block_start_allocnos, ax); + } + + insn = basic_block_head[b]; + + /* Scan the code of this basic block, noting which allocnos + and hard regs are born or die. When one is born, + record a conflict with all others currently live. */ + + while (1) + { + register RTX_CODE code = GET_CODE (insn); + register rtx link; + + /* Make regs_set an empty set. */ + + n_regs_set = 0; + + if (code == INSN || code == CALL_INSN || code == JUMP_INSN) + { + /* Mark any registers clobbered by INSN as live, + so they conflict with the inputs. */ + + note_stores (PATTERN (insn), mark_reg_clobber); + + /* Mark any registers dead after INSN as dead now. */ + + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_DEAD) + mark_reg_death (XEXP (link, 0)); + + /* Mark any registers set in INSN as live, + and mark them as conflicting with all other live regs. + Clobbers are processed again, so they conflict with + the registers that are set. */ + + note_stores (PATTERN (insn), mark_reg_store); + + /* Mark any registers both set and dead after INSN as dead. + This is not redundant! + A register may be set and killed in the same insn. + It is necessary to mark them as live, above, to get + the right conflicts within the insn. */ + + while (n_regs_set > 0) + if (find_regno_note (insn, REG_DEAD, REGNO (regs_set[--n_regs_set]))) + mark_reg_death (regs_set[n_regs_set]); + + /*???The following seems to be incorrect. */ + /* Likewise for regs set by incrementation. */ + + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_INC + && find_regno_note (insn, REG_DEAD, REGNO (XEXP (link, 0)))) + mark_reg_death (XEXP (link, 0)); + } + + if (insn == basic_block_end[b]) + break; + insn = NEXT_INSN (insn); + } + } +} + +/* Assign a hard register to ALLOCNO; look for one that is the beginning + of a long enough stretch of hard regs none of which conflicts with ALLOCNO. + The registers marked in PREFREGS are tried first. + + If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg. + Otherwise ignore that preferred class. + + If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that + will have to be saved and restored at calls. + + If we find one, record it in reg_renumber. + If not, do nothing. */ + +static void +find_reg (allocno, losers, all_regs_p, accept_call_clobbered, prefregs) + int allocno; + register short *losers; + int all_regs_p; + int accept_call_clobbered; + HARD_REG_SET prefregs; +{ + register int i, prefreg, pass; +#ifdef HARD_REG_SET + register /* Declare it register if it's a scalar. */ +#endif + HARD_REG_SET used; + + enum reg_class class + = all_regs_p ? GENERAL_REGS : reg_preferred_class (allocno_reg[allocno]); + enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]); + + if (accept_call_clobbered) + COPY_HARD_REG_SET (used, call_fixed_reg_set); + else if (reg_n_calls_crossed[allocno_reg[allocno]] == 0) + COPY_HARD_REG_SET (used, fixed_reg_set); + else + COPY_HARD_REG_SET (used, call_used_reg_set); + + /* Some registers should not be allocated in global-alloc. */ + IOR_HARD_REG_SET (used, no_global_alloc_regs); + + IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); + IOR_HARD_REG_SET (used, hard_reg_conflicts[allocno]); + if (frame_pointer_needed) + SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); + + AND_COMPL_HARD_REG_SET (prefregs, used); + + /* Try to find a register from the preferred set first. */ + + i = -1; + for (prefreg = 0; prefreg < FIRST_PSEUDO_REGISTER; prefreg++) + if (TEST_HARD_REG_BIT (prefregs, prefreg) + && (losers == 0 || losers[prefreg] < 0) + && HARD_REGNO_MODE_OK (prefreg, mode)) + { + register int j; + register int lim = prefreg + HARD_REGNO_NREGS (prefreg, mode); + for (j = prefreg + 1; + (j < lim + && ! TEST_HARD_REG_BIT (used, j) + && (losers == 0 || losers[j] < 0)); + j++); + if (j == lim) + { + i = prefreg; + break; + } + } + +#if 0 + /* Otherwise try each hard reg to see if it fits. Do this in two passes. + In the first pass, skip registers that are prefered by some pseudo to + give it a better chance of getting one of those registers. Only if + we can't get a register when excluding those do we take one of them. */ + + /* This is turned off because it makes worse allocation on the 68020. */ + for (pass = 0; pass <= 1 && i < 0; pass++) +#endif + pass = 1; + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + { +#ifdef REG_ALLOC_ORDER + int regno = reg_alloc_order[i]; +#else + int regno = i; +#endif + if (! TEST_HARD_REG_BIT (used, regno) + && (losers == 0 || losers[regno] < 0) + && (pass == 1 || ! TEST_HARD_REG_BIT (regs_someone_prefers, regno)) + && HARD_REGNO_MODE_OK (regno, mode)) + { + register int j; + register int lim = regno + HARD_REGNO_NREGS (regno, mode); + for (j = regno + 1; + (j < lim + && ! TEST_HARD_REG_BIT (used, j) + && (losers == 0 || losers[j] < 0)); + j++); + if (j == lim) + { + i = regno; + break; + } +#ifndef REG_ALLOC_ORDER + i = j; /* Skip starting points we know will lose */ +#endif + } + } + + /* Did we find a register? */ + + if (i < FIRST_PSEUDO_REGISTER) + { + register int lim, j; + HARD_REG_SET this_reg; + + /* Yes. Record it as the hard register of this pseudo-reg. */ + reg_renumber[allocno_reg[allocno]] = i; + /* For each other pseudo-reg conflicting with this one, + mark it as conflicting with the hard regs this one occupies. */ + CLEAR_HARD_REG_SET (this_reg); + lim = i + HARD_REGNO_NREGS (i, mode); + for (j = i; j < lim; j++) + SET_HARD_REG_BIT (this_reg, j); + lim = allocno; + for (j = 0; j < max_allocno; j++) + if (CONFLICTP (lim, j) || CONFLICTP (j, lim)) + { + IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg); + } + } + else if (flag_caller_saves) + { + /* Did not find a register. If it would be profitable to + allocate a call-clobbered register and save and restore it + around calls, do that. */ + if (! accept_call_clobbered + && reg_n_calls_crossed[allocno_reg[allocno]] != 0 + && CALLER_SAVE_PROFITABLE (reg_n_refs[allocno_reg[allocno]], + reg_n_calls_crossed[allocno_reg[allocno]])) + { + find_reg (allocno, losers, all_regs_p, 1, prefregs); + if (reg_renumber[allocno_reg[allocno]] >= 0) + caller_save_needed = 1; + } + } +} + +/* Called from `reload' to look for a hard reg to put pseudo reg REGNO in. + Perhaps it had previously seemed not worth a hard reg, + or perhaps its old hard reg has been commandeered for reloads. + FORBIDDEN_REGS is a vector that indicates certain hard regs + that may not be used, even if they do not appear to be allocated. + A nonnegative element means the corresponding hard reg is forbidden. + If FORBIDDEN_REGS is zero, no regs are forbidden. */ + +void +retry_global_alloc (regno, forbidden_regs) + int regno; + short *forbidden_regs; +{ + int allocno = reg_allocno[regno]; + if (allocno >= 0) + { + /* If we have more than one register class, + first try allocating in the class that is cheapest + for this pseudo-reg. If that fails, try any reg. */ + if (N_REG_CLASSES > 1) + find_reg (allocno, forbidden_regs, 0, 0, + hard_reg_preferences[allocno]); + if (reg_renumber[regno] < 0 + && !reg_preferred_or_nothing (regno)) + find_reg (allocno, forbidden_regs, 1, 0, + hard_reg_preferences[allocno]); + } +} + +/* Called from reload pass to see if current function's pseudo regs + require a frame pointer to be allocated and set up. + + Return 1 if so, 0 otherwise. + We may alter the hard-reg allocation of the pseudo regs + in order to make the frame pointer unnecessary. + However, if the value is 1, nothing has been altered. + + Args grant access to some tables used in reload1.c. + See there for info on them. */ + +int +check_frame_pointer_required (reg_equiv_constant, reg_equiv_mem, reg_equiv_address) + rtx *reg_equiv_constant, *reg_equiv_mem, *reg_equiv_address; +{ + register int i; + HARD_REG_SET *old_hard_reg_conflicts; + short *old_reg_renumber; + char old_regs_ever_live[FIRST_PSEUDO_REGISTER]; + + /* If any pseudo reg has no hard reg and no equivalent, + we must have a frame pointer. */ + + for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) + if (reg_renumber[i] < 0 && reg_n_refs[i] > 0 + && reg_equiv_mem[i] == 0 && reg_equiv_constant[i] == 0 + && reg_equiv_address[i] == 0) + return 1; + + /* If we might not need a frame pointer, + try finding a hard reg for any pseudo that has a memory equivalent. + That is because the memory equivalent probably refers to a frame + pointer. */ + + old_reg_renumber = (short *) alloca (max_regno * sizeof (short)); + old_hard_reg_conflicts = (HARD_REG_SET *) + alloca (max_allocno * sizeof (HARD_REG_SET)); + + bcopy (reg_renumber, old_reg_renumber, max_regno * sizeof (short)); + bcopy (hard_reg_conflicts, old_hard_reg_conflicts, + max_allocno * sizeof (HARD_REG_SET)); + bcopy (regs_ever_live, old_regs_ever_live, sizeof regs_ever_live); + + for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) + if (reg_renumber[i] < 0 + && ((reg_equiv_mem[i] + && reg_mentioned_p (frame_pointer_rtx, reg_equiv_mem[i])) + || (reg_equiv_address[i] + && reg_mentioned_p (frame_pointer_rtx, reg_equiv_address[i])))) + { + retry_global_alloc (i, 0); + /* If we can't find a hard reg for ALL of them, + or if a previously unneeded hard reg is used that requires saving, + we fail: set all those pseudos back as they were. */ + if (reg_renumber[i] < 0 + || (! old_regs_ever_live[reg_renumber[i]] + && ! call_used_regs[reg_renumber[i]])) + { + bcopy (old_reg_renumber, reg_renumber, + max_regno * sizeof (short)); + bcopy (old_hard_reg_conflicts, hard_reg_conflicts, + max_allocno * sizeof (HARD_REG_SET)); + bcopy (old_regs_ever_live, regs_ever_live, sizeof regs_ever_live); + return 1; + } + mark_home_live (i); + } + + return 0; +} + +/* Record a conflict between register REGNO + and everything currently live. + REGNO must not be a pseudo reg that was allocated + by local_alloc; such numbers must be translated through + reg_renumber before calling here. */ + +static void +record_one_conflict (regno) + int regno; +{ + register int j; + + if (regno < FIRST_PSEUDO_REGISTER) + /* When a hard register becomes live, + record conflicts with live pseudo regs. */ + for (j = 0; j < max_allocno; j++) + { + if (ALLOCNO_LIVE_P (j)) + SET_HARD_REG_BIT (hard_reg_conflicts[j], regno); + } + else + /* When a pseudo-register becomes live, + record conflicts first with hard regs, + then with other pseudo regs. */ + { + register int ialloc = reg_allocno[regno]; + register int ialloc_prod = ialloc * allocno_row_words; + IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live); + for (j = allocno_row_words - 1; j >= 0; j--) + conflicts[ialloc_prod + j] |= allocnos_live[j]; + } +} + +/* Record all allocnos currently live as conflicting + with each other and with all hard regs currently live. + ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that + are currently live. Their bits are also flagged in allocnos_live. */ + +static void +record_conflicts (allocno_vec, len) + register short *allocno_vec; + register int len; +{ + register int allocno; + register int j; + register int ialloc_prod; + + while (--len >= 0) + { + allocno = allocno_vec[len]; + ialloc_prod = allocno * allocno_row_words; + IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live); + for (j = allocno_row_words - 1; j >= 0; j--) + conflicts[ialloc_prod + j] |= allocnos_live[j]; + } +} + +/* Handle the case where REG is set by the insn being scanned, + during the forward scan to accumulate conflicts. + Store a 1 in regs_live or allocnos_live for this register, record how many + consecutive hardware registers it actually needs, + and record a conflict with all other registers already live. + + Note that even if REG does not remain alive after this insn, + we must mark it here as live, to ensure a conflict between + REG and any other regs set in this insn that really do live. + This is because those other regs could be considered after this. + + REG might actually be something other than a register; + if so, we do nothing. + + CLOBBERs are processed here by calling mark_reg_clobber. */ + +static void +mark_reg_store (orig_reg, setter) + rtx orig_reg, setter; +{ + register int regno; + register rtx reg = orig_reg; + + /* WORD is which word of a multi-register group is being stored. + For the case where the store is actually into a SUBREG of REG. + Except we don't use it; I believe the entire REG needs to be + made live. */ + int word = 0; + + if (GET_CODE (reg) == SUBREG) + { + word = SUBREG_WORD (reg); + reg = SUBREG_REG (reg); + } + + if (GET_CODE (reg) != REG) + return; + + if (GET_CODE (setter) != SET) + { + /* A clobber of a register should be processed here too. */ + mark_reg_clobber (orig_reg, setter); + return; + } + + regs_set[n_regs_set++] = reg; + + set_preference (reg, SET_SRC (setter)); + + regno = REGNO (reg); + + if (reg_renumber[regno] >= 0) + regno = reg_renumber[regno] /* + word */; + + /* Either this is one of the max_allocno pseudo regs not allocated, + or it is or has a hardware reg. First handle the pseudo-regs. */ + if (regno >= FIRST_PSEUDO_REGISTER) + { + if (reg_allocno[regno] >= 0) + { + SET_ALLOCNO_LIVE (reg_allocno[regno]); + record_one_conflict (regno); + } + } + /* Handle hardware regs (and pseudos allocated to hard regs). */ + else if (! fixed_regs[regno]) + { + register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); + while (regno < last) + { + record_one_conflict (regno); + SET_HARD_REG_BIT (hard_regs_live, regno); + regno++; + } + } +} + +/* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */ + +static void +mark_reg_clobber (reg, setter) + rtx reg, setter; +{ + register int regno; + + /* WORD is which word of a multi-register group is being stored. + For the case where the store is actually into a SUBREG of REG. + Except we don't use it; I believe the entire REG needs to be + made live. */ + int word = 0; + + if (GET_CODE (setter) != CLOBBER) + return; + + if (GET_CODE (reg) == SUBREG) + { + word = SUBREG_WORD (reg); + reg = SUBREG_REG (reg); + } + + if (GET_CODE (reg) != REG) + return; + + regs_set[n_regs_set++] = reg; + + regno = REGNO (reg); + + if (reg_renumber[regno] >= 0) + regno = reg_renumber[regno] /* + word */; + + /* Either this is one of the max_allocno pseudo regs not allocated, + or it is or has a hardware reg. First handle the pseudo-regs. */ + if (regno >= FIRST_PSEUDO_REGISTER) + { + if (reg_allocno[regno] >= 0) + { + SET_ALLOCNO_LIVE (reg_allocno[regno]); + record_one_conflict (regno); + } + } + /* Handle hardware regs (and pseudos allocated to hard regs). */ + else if (! fixed_regs[regno]) + { + register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); + while (regno < last) + { + record_one_conflict (regno); + SET_HARD_REG_BIT (hard_regs_live, regno); + regno++; + } + } +} + +/* Mark REG as being dead (following the insn being scanned now). + Store a 0 in regs_live or allocnos_live for this register. */ + +static void +mark_reg_death (reg) + rtx reg; +{ + register int regno = REGNO (reg); + + /* For pseudo reg, see if it has been assigned a hardware reg. */ + if (reg_renumber[regno] >= 0) + regno = reg_renumber[regno]; + + /* Either this is one of the max_allocno pseudo regs not allocated, + or it is a hardware reg. First handle the pseudo-regs. */ + if (regno >= FIRST_PSEUDO_REGISTER) + { + if (reg_allocno[regno] >= 0) + CLEAR_ALLOCNO_LIVE (reg_allocno[regno]); + } + /* Handle hardware regs (and pseudos allocated to hard regs). */ + else if (! fixed_regs[regno]) + { + /* Pseudo regs already assigned hardware regs are treated + almost the same as explicit hardware regs. */ + register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); + while (regno < last) + { + CLEAR_HARD_REG_BIT (hard_regs_live, regno); + regno++; + } + } +} + +/* Mark hard reg REGNO as currently live, assuming machine mode MODE + for the value stored in it. MODE determines how many consecutive + registers are actually in use. Do not record conflicts; + it is assumed that the caller will do that. */ + +static void +mark_reg_live_nc (regno, mode) + register int regno; + enum machine_mode mode; +{ + register int last = regno + HARD_REGNO_NREGS (regno, mode); + while (regno < last) + { + SET_HARD_REG_BIT (hard_regs_live, regno); + regno++; + } +} + +/* Try to set a preference for an allocno to a hard register. + We are passed DEST and SRC which are the operands of a SET. It is known + that SRC is a register. If SRC or the first operand of SRC is a register, + try to set a preference. If one of the two is a hard register and the other + is a pseudo-register, mark the preference. + + Note that we are not as agressive as local-alloc in trying to tie a + pseudo-register to a hard register. */ + +static void +set_preference (dest, src) + rtx dest, src; +{ + int src_regno, dest_regno; + /* Amount to add to the hard regno for SRC, or subtract from that for DEST, + to compensate for subregs in SRC or DEST. */ + int offset = 0; + + if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e') + src = XEXP (src, 0); + + /* Get the reg number for both SRC and DEST. + If neither is a reg, give up. */ + + if (GET_CODE (src) == REG) + src_regno = REGNO (src); + else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG) + { + src_regno = REGNO (SUBREG_REG (src)); + offset += SUBREG_WORD (src); + } + else + return; + + if (GET_CODE (dest) == REG) + dest_regno = REGNO (dest); + else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG) + { + dest_regno = REGNO (SUBREG_REG (dest)); + offset -= SUBREG_WORD (dest); + } + else + return; + + /* Convert either or both to hard reg numbers. */ + + if (reg_renumber[src_regno] >= 0) + src_regno = reg_renumber[src_regno]; + + if (reg_renumber[dest_regno] >= 0) + dest_regno = reg_renumber[dest_regno]; + + /* Now if one is a hard reg and the other is a global pseudo + then give the other a preference. */ + + if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER + && reg_allocno[src_regno] >= 0) + { + dest_regno -= offset; + if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER) + { + SET_REGBIT (hard_reg_preferences, + reg_allocno[src_regno], dest_regno); + SET_HARD_REG_BIT (regs_someone_prefers, dest_regno); + } + } + + if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER + && reg_allocno[dest_regno] >= 0) + { + src_regno += offset; + if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER) + { + SET_REGBIT (hard_reg_preferences, + reg_allocno[dest_regno], src_regno); + SET_HARD_REG_BIT (regs_someone_prefers, src_regno); + } + } +} + +/* Print debugging trace information if -greg switch is given, + showing the information on which the allocation decisions are based. */ + +static void +dump_conflicts (file) + FILE *file; +{ + register int i; + fprintf (file, ";; %d regs to allocate:", max_allocno); + for (i = 0; i < max_allocno; i++) + { + fprintf (file, " %d", allocno_reg[allocno_order[i]]); + if (allocno_size[allocno_order[i]] != 1) + fprintf (file, " (%d)", allocno_size[allocno_order[i]]); + } + fprintf (file, "\n"); + + for (i = 0; i < max_allocno; i++) + { + register int j; + fprintf (file, ";; %d conflicts:", allocno_reg[i]); + for (j = 0; j < max_allocno; j++) + if (CONFLICTP (i, j) || CONFLICTP (j, i)) + fprintf (file, " %d", allocno_reg[j]); + for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) + if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j)) + fprintf (file, " %d", j); + fprintf (file, "\n"); + } + fprintf (file, "\n"); +} + +void +dump_global_regs (file) + FILE *file; +{ + register int i; + + fprintf (file, ";; Register dispositions:"); + for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) + { + if (reg_renumber[i] >= 0) + fprintf (file, " %d in %d ", i, reg_renumber[i]); + } + + fprintf (file, "\n\n;; Hard regs used: "); + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (regs_ever_live[i]) + fprintf (file, " %d", i); + fprintf (file, "\n\n"); +} |