X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fglobal.c;fp=gcc%2Fglobal.c;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=383f6c4943c965c459eed5ae44466a5b9d7cd990;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/gcc/global.c b/gcc/global.c deleted file mode 100644 index 383f6c49..00000000 --- a/gcc/global.c +++ /dev/null @@ -1,1990 +0,0 @@ -/* Allocate registers for pseudo-registers that span basic blocks. - Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998, - 1999, 2000, 2002 Free Software Foundation, Inc. - -This file is part of GCC. - -GCC 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 2, or (at your option) any later -version. - -GCC 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 GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ - - -#include "config.h" -#include "system.h" - -#include "machmode.h" -#include "hard-reg-set.h" -#include "rtl.h" -#include "tm_p.h" -#include "flags.h" -#include "basic-block.h" -#include "regs.h" -#include "function.h" -#include "insn-config.h" -#include "reload.h" -#include "output.h" -#include "toplev.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. Assign allocation-numbers (allocnos) to the pseudo-registers - still needing allocations and to the pseudo-registers currently - allocated by local-alloc which may be spilled by reload. - 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 - pseudo-registers and which hardware registers are live. - Build the conflict matrix between the pseudo-registers - and another of pseudo-registers versus hardware registers. - Also record the preferred hardware registers - for each pseudo-register. - - 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 which are candidates for allocation. */ - -static int max_allocno; - -/* Indexed by (pseudo) reg number, gives the allocno, or -1 - for pseudo registers which are not to be allocated. */ - -static int *reg_allocno; - -struct allocno -{ - int reg; - /* Gives the number of consecutive hard registers needed by that - pseudo reg. */ - int size; - - /* Number of calls crossed by each allocno. */ - int calls_crossed; - - /* Number of refs to each allocno. */ - int n_refs; - - /* Frequency of uses of each allocno. */ - int freq; - - /* Guess at live length of each allocno. - This is actually the max of the live lengths of the regs. */ - int live_length; - - /* Set of hard regs conflicting with allocno N. */ - - HARD_REG_SET hard_reg_conflicts; - - /* 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. */ - - HARD_REG_SET hard_reg_preferences; - - /* Similar, but just counts register preferences made in simple copy - operations, rather than arithmetic. These are given priority because - we can always eliminate an insn by using these, but using a register - in the above list won't always eliminate an insn. */ - - HARD_REG_SET hard_reg_copy_preferences; - - /* Similar to hard_reg_preferences, but includes bits for subsequent - registers when an allocno is multi-word. The above variable is used for - allocation while this is used to build reg_someone_prefers, below. */ - - HARD_REG_SET hard_reg_full_preferences; - - /* Set of hard registers that some later allocno has a preference for. */ - - HARD_REG_SET regs_someone_prefers; - -#ifdef STACK_REGS - /* Set to true if allocno can't be allocated in the stack register. */ - bool no_stack_reg; -#endif -}; - -static struct allocno *allocno; - -/* 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 (pseudo) reg number, gives the number of another - lower-numbered pseudo reg which can share a hard reg with this pseudo - *even if the two pseudos would otherwise appear to conflict*. */ - -static int *reg_may_share; - -/* Define the number of bits in each element of `conflicts' and what - type that element has. We use the largest integer format on the - host machine. */ - -#define INT_BITS HOST_BITS_PER_WIDE_INT -#define INT_TYPE HOST_WIDE_INT - -/* max_allocno by max_allocno array of bits, - recording whether two allocno's conflict (can't go in the same - hardware register). - - `conflicts' is symmetric after the call to mirror_conflicts. */ - -static INT_TYPE *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 + (unsigned) (J) / INT_BITS] \ - & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS))) - -#define SET_CONFLICT(I, J) \ - (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \ - |= ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS))) - -/* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno, - and execute CODE. */ -#define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \ -do { \ - int i_; \ - int allocno_; \ - INT_TYPE *p_ = (ALLOCNO_SET); \ - \ - for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \ - i_--, allocno_ += INT_BITS) \ - { \ - unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \ - \ - for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \ - { \ - if (word_ & 1) \ - {CODE;} \ - } \ - } \ -} while (0) - -/* This doesn't work for non-GNU C due to the way CODE is macro expanded. */ -#if 0 -/* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to - the conflicting allocno, and execute CODE. This macro assumes that - mirror_conflicts has been run. */ -#define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\ - EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\ - OUT_ALLOCNO, (CODE)) -#endif - -/* Set of hard regs currently live (during scan of all insns). */ - -static HARD_REG_SET hard_regs_live; - -/* Set of registers that global-alloc isn't supposed to use. */ - -static HARD_REG_SET no_global_alloc_regs; - -/* Set of registers used so far. */ - -static HARD_REG_SET regs_used_so_far; - -/* Number of refs to each hard reg, as used by local alloc. - It is zero for a reg that contains global pseudos or is explicitly used. */ - -static int local_reg_n_refs[FIRST_PSEUDO_REGISTER]; - -/* Frequency of uses of given hard reg. */ -static int local_reg_freq[FIRST_PSEUDO_REGISTER]; - -/* Guess at live length of each hard reg, as used by local alloc. - This is actually the sum of the live lengths of the specific regs. */ - -static int local_reg_live_length[FIRST_PSEUDO_REGISTER]; - -/* 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 (allocno[I].TABLE, 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 (allocno[I].TABLE, J) - -/* Bit mask for allocnos live at current point in the scan. */ - -static INT_TYPE *allocnos_live; - -/* Test, set or clear bit number I in allocnos_live, - a bit vector indexed by allocno. */ - -#define ALLOCNO_LIVE_P(I) \ - (allocnos_live[(unsigned) (I) / INT_BITS] \ - & ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS))) - -#define SET_ALLOCNO_LIVE(I) \ - (allocnos_live[(unsigned) (I) / INT_BITS] \ - |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS))) - -#define CLEAR_ALLOCNO_LIVE(I) \ - (allocnos_live[(unsigned) (I) / INT_BITS] \ - &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS))) - -/* This is turned off because it doesn't work right for DImode. - (And it is only used for DImode, so the other cases are worthless.) - The problem is that it isn't true that there is NO possibility of conflict; - only that there is no conflict if the two pseudos get the exact same regs. - If they were allocated with a partial overlap, there would be a conflict. - We can't safely turn off the conflict unless we have another way to - prevent the partial overlap. - - Idea: change hard_reg_conflicts so that instead of recording which - hard regs the allocno may not overlap, it records where the allocno - may not start. Change both where it is used and where it is updated. - Then there is a way to record that (reg:DI 108) may start at 10 - but not at 9 or 11. There is still the question of how to record - this semi-conflict between two pseudos. */ -#if 0 -/* Reg pairs for which conflict after the current insn - is inhibited by a REG_NO_CONFLICT note. - If the table gets full, we ignore any other notes--that is conservative. */ -#define NUM_NO_CONFLICT_PAIRS 4 -/* Number of pairs in use in this insn. */ -int n_no_conflict_pairs; -static struct { int allocno1, allocno2;} - no_conflict_pairs[NUM_NO_CONFLICT_PAIRS]; -#endif /* 0 */ - -/* 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; - -/* All registers that can be eliminated. */ - -static HARD_REG_SET eliminable_regset; - -static int allocno_compare PARAMS ((const PTR, const PTR)); -static void global_conflicts PARAMS ((void)); -static void mirror_conflicts PARAMS ((void)); -static void expand_preferences PARAMS ((void)); -static void prune_preferences PARAMS ((void)); -static void find_reg PARAMS ((int, HARD_REG_SET, int, int, int)); -static void record_one_conflict PARAMS ((int)); -static void record_conflicts PARAMS ((int *, int)); -static void mark_reg_store PARAMS ((rtx, rtx, void *)); -static void mark_reg_clobber PARAMS ((rtx, rtx, void *)); -static void mark_reg_conflicts PARAMS ((rtx)); -static void mark_reg_death PARAMS ((rtx)); -static void mark_reg_live_nc PARAMS ((int, enum machine_mode)); -static void set_preference PARAMS ((rtx, rtx)); -static void dump_conflicts PARAMS ((FILE *)); -static void reg_becomes_live PARAMS ((rtx, rtx, void *)); -static void reg_dies PARAMS ((int, enum machine_mode, - struct insn_chain *)); - -/* 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. - - Return value is nonzero if reload failed - and we must not do any more for this function. */ - -int -global_alloc (file) - FILE *file; -{ - int retval; -#ifdef ELIMINABLE_REGS - static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; -#endif - int need_fp - = (! flag_omit_frame_pointer -#ifdef EXIT_IGNORE_STACK - || (current_function_calls_alloca && EXIT_IGNORE_STACK) -#endif - || FRAME_POINTER_REQUIRED); - - size_t i; - rtx x; - - max_allocno = 0; - - /* 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); - - /* Build the regset of all eliminable registers and show we can't use those - that we already know won't be eliminated. */ -#ifdef ELIMINABLE_REGS - for (i = 0; i < ARRAY_SIZE (eliminables); i++) - { - SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from); - - if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to) - || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp)) - SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from); - } -#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM - SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM); - if (need_fp) - SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM); -#endif - -#else - SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM); - if (need_fp) - SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM); -#endif - - /* Track which registers have already been used. Start with registers - explicitly in the rtl, then registers allocated by local register - allocation. */ - - CLEAR_HARD_REG_SET (regs_used_so_far); -#ifdef LEAF_REGISTERS - /* If we are doing the leaf function optimization, and this is a leaf - function, it means that the registers that take work to save are those - that need a register window. So prefer the ones that can be used in - a leaf function. */ - { - char *cheap_regs; - char *leaf_regs = LEAF_REGISTERS; - - if (only_leaf_regs_used () && leaf_function_p ()) - cheap_regs = leaf_regs; - else - cheap_regs = call_used_regs; - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (regs_ever_live[i] || cheap_regs[i]) - SET_HARD_REG_BIT (regs_used_so_far, i); - } -#else - /* We consider registers that do not have to be saved over calls as if - they were already used since there is no cost in using them. */ - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (regs_ever_live[i] || call_used_regs[i]) - SET_HARD_REG_BIT (regs_used_so_far, i); -#endif - - for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) - if (reg_renumber[i] >= 0) - SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]); - - /* Establish mappings from register number to allocation number - and vice versa. In the process, count the allocnos. */ - - reg_allocno = (int *) xmalloc (max_regno * sizeof (int)); - - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - reg_allocno[i] = -1; - - /* Initialize the shared-hard-reg mapping - from the list of pairs that may share. */ - reg_may_share = (int *) xcalloc (max_regno, sizeof (int)); - for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1)) - { - int r1 = REGNO (XEXP (x, 0)); - int r2 = REGNO (XEXP (XEXP (x, 1), 0)); - if (r1 > r2) - reg_may_share[r1] = r2; - else - reg_may_share[r2] = r1; - } - - for (i = FIRST_PSEUDO_REGISTER; i < (size_t) 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_LIVE_LENGTH (i) != -1 - /* Don't allocate pseudos that cross calls, - if this function receives a nonlocal goto. */ - && (! current_function_has_nonlocal_label - || REG_N_CALLS_CROSSED (i) == 0)) - { - if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0) - reg_allocno[i] = reg_allocno[reg_may_share[i]]; - else - reg_allocno[i] = max_allocno++; - if (REG_LIVE_LENGTH (i) == 0) - abort (); - } - else - reg_allocno[i] = -1; - - allocno = (struct allocno *) xcalloc (max_allocno, sizeof (struct allocno)); - - for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) - if (reg_allocno[i] >= 0) - { - int num = reg_allocno[i]; - allocno[num].reg = i; - allocno[num].size = PSEUDO_REGNO_SIZE (i); - allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i); - allocno[num].n_refs += REG_N_REFS (i); - allocno[num].freq += REG_FREQ (i); - if (allocno[num].live_length < REG_LIVE_LENGTH (i)) - allocno[num].live_length = REG_LIVE_LENGTH (i); - } - - /* Calculate amount of usage of each hard reg by pseudos - allocated by local-alloc. This is to see if we want to - override it. */ - memset ((char *) local_reg_live_length, 0, sizeof local_reg_live_length); - memset ((char *) local_reg_n_refs, 0, sizeof local_reg_n_refs); - memset ((char *) local_reg_freq, 0, sizeof local_reg_freq); - for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++) - if (reg_renumber[i] >= 0) - { - int regno = reg_renumber[i]; - int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i)); - int j; - - for (j = regno; j < endregno; j++) - { - local_reg_n_refs[j] += REG_N_REFS (i); - local_reg_freq[j] += REG_FREQ (i); - local_reg_live_length[j] += REG_LIVE_LENGTH (i); - } - } - - /* We can't override local-alloc for a reg used not just by local-alloc. */ - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (regs_ever_live[i]) - local_reg_n_refs[i] = 0, local_reg_freq[i] = 0; - - allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS; - - /* We used to use alloca here, but the size of what it would try to - allocate would occasionally cause it to exceed the stack limit and - cause unpredictable core dumps. Some examples were > 2Mb in size. */ - conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words, - sizeof (INT_TYPE)); - - allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE)); - - /* 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 (); - - mirror_conflicts (); - - /* Eliminate conflicts between pseudos and eliminable registers. If - the register is not eliminated, the pseudo won't really be able to - live in the eliminable register, so the conflict doesn't matter. - If we do eliminate the register, the conflict will no longer exist. - So in either case, we can ignore the conflict. Likewise for - preferences. */ - - for (i = 0; i < (size_t) max_allocno; i++) - { - AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts, - eliminable_regset); - AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences, - eliminable_regset); - AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences, - eliminable_regset); - } - - /* Try to expand the preferences by merging them between allocnos. */ - - expand_preferences (); - - /* Determine the order to allocate the remaining pseudo registers. */ - - allocno_order = (int *) xmalloc (max_allocno * sizeof (int)); - for (i = 0; i < (size_t) max_allocno; i++) - allocno_order[i] = i; - - /* Default the size to 1, since allocno_compare uses it to divide by. - Also convert allocno_live_length of zero to -1. A length of zero - can occur when all the registers for that allocno have reg_live_length - equal to -2. In this case, we want to make an allocno, but not - allocate it. So avoid the divide-by-zero and set it to a low - priority. */ - - for (i = 0; i < (size_t) max_allocno; i++) - { - if (allocno[i].size == 0) - allocno[i].size = 1; - if (allocno[i].live_length == 0) - allocno[i].live_length = -1; - } - - qsort (allocno_order, max_allocno, sizeof (int), allocno_compare); - - prune_preferences (); - - 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 < (size_t) max_allocno; i++) - if (reg_renumber[allocno[allocno_order[i]].reg] < 0 - && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 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, 0); - if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) - continue; - } - if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS) - find_reg (allocno_order[i], 0, 1, 0, 0); - } - - free (allocno_order); - } - - /* 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 0 /* We need to eliminate regs even if there is no rtl code, - for the sake of debugging information. */ - if (n_basic_blocks > 0) -#endif - { - build_insn_chain (get_insns ()); - retval = reload (get_insns (), 1); - } - - /* Clean up. */ - free (reg_allocno); - free (reg_may_share); - free (allocno); - free (conflicts); - free (allocnos_live); - - return retval; -} - -/* Sort predicate for ordering the allocnos. - Returns -1 (1) if *v1 should be allocated before (after) *v2. */ - -static int -allocno_compare (v1p, v2p) - const PTR v1p; - const PTR v2p; -{ - int v1 = *(const int *)v1p, v2 = *(const int *)v2p; - /* 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) - weighted by the frequency (maximally REG_FREQ_MAX). - Multiplying this by 10000/REG_FREQ_MAX can't overflow. */ - int pri1 - = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq) - / allocno[v1].live_length) - * (10000 / REG_FREQ_MAX) * allocno[v1].size); - int pri2 - = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq) - / allocno[v2].live_length) - * (10000 / REG_FREQ_MAX) * allocno[v2].size); - 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 and register preferences in the - conflict matrices and preference tables. */ - -static void -global_conflicts () -{ - int b, i; - rtx insn; - int *block_start_allocnos; - - /* Make a vector that mark_reg_{store,clobber} will store in. */ - regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2); - - block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int)); - - for (b = 0; b < n_basic_blocks; b++) - { - memset ((char *) allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE)); - - /* Initialize table of registers currently live - to the state at the beginning of this basic block. - This also marks the conflicts among hard registers - and any allocnos that are live. - - 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. */ - - { - regset old = BASIC_BLOCK (b)->global_live_at_start; - int ax = 0; - - REG_SET_TO_HARD_REG_SET (hard_regs_live, old); - EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i, - { - 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 hard reg - now live. - - It is not necessary to mark any conflicts between pseudos as - this point, even for pseudos which are live at the start of - the basic block. - - Given two pseudos X and Y and any point in the CFG P. - - On any path to point P where X and Y are live one of the - following conditions must be true: - - 1. X is live at some instruction on the path that - evaluates Y. - - 2. Y is live at some instruction on the path that - evaluates X. - - 3. Either X or Y is not evaluted on the path to P - (ie it is used uninitialized) and thus the - conflict can be ignored. - - In cases #1 and #2 the conflict will be recorded when we - scan the instruction that makes either X or Y become live. */ - record_conflicts (block_start_allocnos, ax); - -#ifdef STACK_REGS - { - /* Pseudos can't go in stack regs at the start of a basic block - that is reached by an abnormal edge. */ - - edge e; - for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next) - if (e->flags & EDGE_ABNORMAL) - break; - if (e != NULL) - { - EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, ax, - { - allocno[ax].no_stack_reg = 1; - }); - for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++) - record_one_conflict (ax); - } - } -#endif - } - - insn = 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) - { - RTX_CODE code = GET_CODE (insn); - rtx link; - - /* Make regs_set an empty set. */ - - n_regs_set = 0; - - if (code == INSN || code == CALL_INSN || code == JUMP_INSN) - { - -#if 0 - int i = 0; - for (link = REG_NOTES (insn); - link && i < NUM_NO_CONFLICT_PAIRS; - link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_NO_CONFLICT) - { - no_conflict_pairs[i].allocno1 - = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))]; - no_conflict_pairs[i].allocno2 - = reg_allocno[REGNO (XEXP (link, 0))]; - i++; - } -#endif /* 0 */ - - /* Mark any registers clobbered by INSN as live, - so they conflict with the inputs. */ - - note_stores (PATTERN (insn), mark_reg_clobber, NULL); - - /* 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, NULL); - -#ifdef AUTO_INC_DEC - for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_INC) - mark_reg_store (XEXP (link, 0), NULL_RTX, NULL); -#endif - - /* If INSN has multiple outputs, then any reg that dies here - and is used inside of an output - must conflict with the other outputs. - - It is unsafe to use !single_set here since it will ignore an - unused output. Just because an output is unused does not mean - the compiler can assume the side effect will not occur. - Consider if REG appears in the address of an output and we - reload the output. If we allocate REG to the same hard - register as an unused output we could set the hard register - before the output reload insn. */ - if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn)) - for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_DEAD) - { - int used_in_output = 0; - int i; - rtx reg = XEXP (link, 0); - - for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) - { - rtx set = XVECEXP (PATTERN (insn), 0, i); - if (GET_CODE (set) == SET - && GET_CODE (SET_DEST (set)) != REG - && !rtx_equal_p (reg, SET_DEST (set)) - && reg_overlap_mentioned_p (reg, SET_DEST (set))) - used_in_output = 1; - } - if (used_in_output) - mark_reg_conflicts (reg); - } - - /* Mark any registers set in INSN and then never used. */ - - while (n_regs_set-- > 0) - { - rtx note = find_regno_note (insn, REG_UNUSED, - REGNO (regs_set[n_regs_set])); - if (note) - mark_reg_death (XEXP (note, 0)); - } - } - - if (insn == BLOCK_END (b)) - break; - insn = NEXT_INSN (insn); - } - } - - /* Clean up. */ - free (block_start_allocnos); - free (regs_set); -} -/* Expand the preference information by looking for cases where one allocno - dies in an insn that sets an allocno. If those two allocnos don't conflict, - merge any preferences between those allocnos. */ - -static void -expand_preferences () -{ - rtx insn; - rtx link; - rtx set; - - /* We only try to handle the most common cases here. Most of the cases - where this wins are reg-reg copies. */ - - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - if (INSN_P (insn) - && (set = single_set (insn)) != 0 - && GET_CODE (SET_DEST (set)) == REG - && reg_allocno[REGNO (SET_DEST (set))] >= 0) - for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_DEAD - && GET_CODE (XEXP (link, 0)) == REG - && reg_allocno[REGNO (XEXP (link, 0))] >= 0 - && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))], - reg_allocno[REGNO (XEXP (link, 0))])) - { - int a1 = reg_allocno[REGNO (SET_DEST (set))]; - int a2 = reg_allocno[REGNO (XEXP (link, 0))]; - - if (XEXP (link, 0) == SET_SRC (set)) - { - IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences, - allocno[a2].hard_reg_copy_preferences); - IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences, - allocno[a1].hard_reg_copy_preferences); - } - - IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences, - allocno[a2].hard_reg_preferences); - IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences, - allocno[a1].hard_reg_preferences); - IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences, - allocno[a2].hard_reg_full_preferences); - IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences, - allocno[a1].hard_reg_full_preferences); - } -} - -/* Prune the preferences for global registers to exclude registers that cannot - be used. - - Compute `regs_someone_prefers', which is a bitmask of the hard registers - that are preferred by conflicting registers of lower priority. If possible, - we will avoid using these registers. */ - -static void -prune_preferences () -{ - int i; - int num; - int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int)); - - /* Scan least most important to most important. - For each allocno, remove from preferences registers that cannot be used, - either because of conflicts or register type. Then compute all registers - preferred by each lower-priority register that conflicts. */ - - for (i = max_allocno - 1; i >= 0; i--) - { - HARD_REG_SET temp; - - num = allocno_order[i]; - allocno_to_order[num] = i; - COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts); - - if (allocno[num].calls_crossed == 0) - IOR_HARD_REG_SET (temp, fixed_reg_set); - else - IOR_HARD_REG_SET (temp, call_used_reg_set); - - IOR_COMPL_HARD_REG_SET - (temp, - reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]); - - AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp); - AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp); - AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp); - } - - for (i = max_allocno - 1; i >= 0; i--) - { - /* Merge in the preferences of lower-priority registers (they have - already been pruned). If we also prefer some of those registers, - don't exclude them unless we are of a smaller size (in which case - we want to give the lower-priority allocno the first chance for - these registers). */ - HARD_REG_SET temp, temp2; - int allocno2; - - num = allocno_order[i]; - - CLEAR_HARD_REG_SET (temp); - CLEAR_HARD_REG_SET (temp2); - - EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words, - allocno2, - { - if (allocno_to_order[allocno2] > i) - { - if (allocno[allocno2].size <= allocno[num].size) - IOR_HARD_REG_SET (temp, - allocno[allocno2].hard_reg_full_preferences); - else - IOR_HARD_REG_SET (temp2, - allocno[allocno2].hard_reg_full_preferences); - } - }); - - AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences); - IOR_HARD_REG_SET (temp, temp2); - COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp); - } - free (allocno_to_order); -} - -/* Assign a hard register to allocno NUM; 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. - - LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot - be used for this allocation. - - If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg. - Otherwise ignore that preferred class and use the alternate class. - - If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that - will have to be saved and restored at calls. - - RETRYING is nonzero if this is called from retry_global_alloc. - - If we find one, record it in reg_renumber. - If not, do nothing. */ - -static void -find_reg (num, losers, alt_regs_p, accept_call_clobbered, retrying) - int num; - HARD_REG_SET losers; - int alt_regs_p; - int accept_call_clobbered; - int retrying; -{ - int i, best_reg, pass; -#ifdef HARD_REG_SET - register /* Declare it register if it's a scalar. */ -#endif - HARD_REG_SET used, used1, used2; - - enum reg_class class = (alt_regs_p - ? reg_alternate_class (allocno[num].reg) - : reg_preferred_class (allocno[num].reg)); - enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg); - - if (accept_call_clobbered) - COPY_HARD_REG_SET (used1, call_fixed_reg_set); - else if (allocno[num].calls_crossed == 0) - COPY_HARD_REG_SET (used1, fixed_reg_set); - else - COPY_HARD_REG_SET (used1, call_used_reg_set); - - /* Some registers should not be allocated in global-alloc. */ - IOR_HARD_REG_SET (used1, no_global_alloc_regs); - if (losers) - IOR_HARD_REG_SET (used1, losers); - - IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]); - COPY_HARD_REG_SET (used2, used1); - - IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts); - -#ifdef CLASS_CANNOT_CHANGE_MODE - if (REG_CHANGES_MODE (allocno[num].reg)) - IOR_HARD_REG_SET (used1, - reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE]); -#endif - - /* Try each hard reg to see if it fits. Do this in two passes. - In the first pass, skip registers that are preferred by some other 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. - However, we never allocate a register for the first time in pass 0. */ - - COPY_HARD_REG_SET (used, used1); - IOR_COMPL_HARD_REG_SET (used, regs_used_so_far); - IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers); - - best_reg = -1; - for (i = FIRST_PSEUDO_REGISTER, pass = 0; - pass <= 1 && i >= FIRST_PSEUDO_REGISTER; - pass++) - { - if (pass == 1) - COPY_HARD_REG_SET (used, used1); - 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) - && HARD_REGNO_MODE_OK (regno, mode) - && (allocno[num].calls_crossed == 0 - || accept_call_clobbered - || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) - { - int j; - int lim = regno + HARD_REGNO_NREGS (regno, mode); - for (j = regno + 1; - (j < lim - && ! TEST_HARD_REG_BIT (used, j)); - j++); - if (j == lim) - { - best_reg = regno; - break; - } -#ifndef REG_ALLOC_ORDER - i = j; /* Skip starting points we know will lose */ -#endif - } - } - } - - /* See if there is a preferred register with the same class as the register - we allocated above. Making this restriction prevents register - preferencing from creating worse register allocation. - - Remove from the preferred registers and conflicting registers. Note that - additional conflicts may have been added after `prune_preferences' was - called. - - First do this for those register with copy preferences, then all - preferred registers. */ - - AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used); - GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences, - reg_class_contents[(int) NO_REGS], no_copy_prefs); - - if (best_reg >= 0) - { - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i) - && HARD_REGNO_MODE_OK (i, mode) - && (allocno[num].calls_crossed == 0 - || accept_call_clobbered - || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode)) - && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) - || reg_class_subset_p (REGNO_REG_CLASS (i), - REGNO_REG_CLASS (best_reg)) - || reg_class_subset_p (REGNO_REG_CLASS (best_reg), - REGNO_REG_CLASS (i)))) - { - int j; - int lim = i + HARD_REGNO_NREGS (i, mode); - for (j = i + 1; - (j < lim - && ! TEST_HARD_REG_BIT (used, j) - && (REGNO_REG_CLASS (j) - == REGNO_REG_CLASS (best_reg + (j - i)) - || reg_class_subset_p (REGNO_REG_CLASS (j), - REGNO_REG_CLASS (best_reg + (j - i))) - || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), - REGNO_REG_CLASS (j)))); - j++); - if (j == lim) - { - best_reg = i; - goto no_prefs; - } - } - } - no_copy_prefs: - - AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used); - GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences, - reg_class_contents[(int) NO_REGS], no_prefs); - - if (best_reg >= 0) - { - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i) - && HARD_REGNO_MODE_OK (i, mode) - && (allocno[num].calls_crossed == 0 - || accept_call_clobbered - || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode)) - && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg) - || reg_class_subset_p (REGNO_REG_CLASS (i), - REGNO_REG_CLASS (best_reg)) - || reg_class_subset_p (REGNO_REG_CLASS (best_reg), - REGNO_REG_CLASS (i)))) - { - int j; - int lim = i + HARD_REGNO_NREGS (i, mode); - for (j = i + 1; - (j < lim - && ! TEST_HARD_REG_BIT (used, j) - && (REGNO_REG_CLASS (j) - == REGNO_REG_CLASS (best_reg + (j - i)) - || reg_class_subset_p (REGNO_REG_CLASS (j), - REGNO_REG_CLASS (best_reg + (j - i))) - || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)), - REGNO_REG_CLASS (j)))); - j++); - if (j == lim) - { - best_reg = i; - break; - } - } - } - no_prefs: - - /* If we haven't succeeded yet, try with caller-saves. - We need not check to see if the current function has nonlocal - labels because we don't put any pseudos that are live over calls in - registers in that case. */ - - if (flag_caller_saves && best_reg < 0) - { - /* 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 - && allocno[num].calls_crossed != 0 - && CALLER_SAVE_PROFITABLE (allocno[num].n_refs, - allocno[num].calls_crossed)) - { - HARD_REG_SET new_losers; - if (! losers) - CLEAR_HARD_REG_SET (new_losers); - else - COPY_HARD_REG_SET (new_losers, losers); - - IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set); - find_reg (num, new_losers, alt_regs_p, 1, retrying); - if (reg_renumber[allocno[num].reg] >= 0) - { - caller_save_needed = 1; - return; - } - } - } - - /* If we haven't succeeded yet, - see if some hard reg that conflicts with us - was utilized poorly by local-alloc. - If so, kick out the regs that were put there by local-alloc - so we can use it instead. */ - if (best_reg < 0 && !retrying - /* Let's not bother with multi-reg allocnos. */ - && allocno[num].size == 1) - { - /* Count from the end, to find the least-used ones first. */ - for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--) - { -#ifdef REG_ALLOC_ORDER - int regno = reg_alloc_order[i]; -#else - int regno = i; -#endif - - if (local_reg_n_refs[regno] != 0 - /* Don't use a reg no good for this pseudo. */ - && ! TEST_HARD_REG_BIT (used2, regno) - && HARD_REGNO_MODE_OK (regno, mode) - && (allocno[num].calls_crossed == 0 - || accept_call_clobbered - || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)) -#ifdef CLASS_CANNOT_CHANGE_MODE - && ! (REG_CHANGES_MODE (allocno[num].reg) - && (TEST_HARD_REG_BIT - (reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE], - regno))) -#endif -#ifdef STACK_REGS - && (!allocno[num].no_stack_reg - || regno < FIRST_STACK_REG || regno > LAST_STACK_REG) -#endif - ) - { - /* We explicitly evaluate the divide results into temporary - variables so as to avoid excess precision problems that occur - on an i386-unknown-sysv4.2 (unixware) host. */ - - double tmp1 = ((double) local_reg_freq[regno] - / local_reg_live_length[regno]); - double tmp2 = ((double) allocno[num].freq - / allocno[num].live_length); - - if (tmp1 < tmp2) - { - /* Hard reg REGNO was used less in total by local regs - than it would be used by this one allocno! */ - int k; - for (k = 0; k < max_regno; k++) - if (reg_renumber[k] >= 0) - { - int r = reg_renumber[k]; - int endregno - = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k)); - - if (regno >= r && regno < endregno) - reg_renumber[k] = -1; - } - - best_reg = regno; - break; - } - } - } - } - - /* Did we find a register? */ - - if (best_reg >= 0) - { - int lim, j; - HARD_REG_SET this_reg; - - /* Yes. Record it as the hard register of this pseudo-reg. */ - reg_renumber[allocno[num].reg] = best_reg; - /* Also of any pseudo-regs that share with it. */ - if (reg_may_share[allocno[num].reg]) - for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++) - if (reg_allocno[j] == num) - reg_renumber[j] = best_reg; - - /* Make a set of the hard regs being allocated. */ - CLEAR_HARD_REG_SET (this_reg); - lim = best_reg + HARD_REGNO_NREGS (best_reg, mode); - for (j = best_reg; j < lim; j++) - { - SET_HARD_REG_BIT (this_reg, j); - SET_HARD_REG_BIT (regs_used_so_far, j); - /* This is no longer a reg used just by local regs. */ - local_reg_n_refs[j] = 0; - local_reg_freq[j] = 0; - } - /* For each other pseudo-reg conflicting with this one, - mark it as conflicting with the hard regs this one occupies. */ - lim = num; - EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j, - { - IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg); - }); - } -} - -/* 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 indicates certain hard regs that may not be used, even if - they do not appear to be allocated. - If FORBIDDEN_REGS is zero, no regs are forbidden. */ - -void -retry_global_alloc (regno, forbidden_regs) - int regno; - HARD_REG_SET forbidden_regs; -{ - int alloc_no = reg_allocno[regno]; - if (alloc_no >= 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 (alloc_no, forbidden_regs, 0, 0, 1); - if (reg_renumber[regno] < 0 - && reg_alternate_class (regno) != NO_REGS) - find_reg (alloc_no, forbidden_regs, 1, 0, 1); - - /* If we found a register, modify the RTL for the register to - show the hard register, and mark that register live. */ - if (reg_renumber[regno] >= 0) - { - REGNO (regno_reg_rtx[regno]) = reg_renumber[regno]; - mark_home_live (regno); - } - } -} - -/* 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; -{ - int j; - - if (regno < FIRST_PSEUDO_REGISTER) - /* When a hard register becomes live, - record conflicts with live pseudo regs. */ - EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j, - { - SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno); - }); - else - /* When a pseudo-register becomes live, - record conflicts first with hard regs, - then with other pseudo regs. */ - { - int ialloc = reg_allocno[regno]; - int ialloc_prod = ialloc * allocno_row_words; - - IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live); - for (j = allocno_row_words - 1; j >= 0; j--) - { -#if 0 - int k; - for (k = 0; k < n_no_conflict_pairs; k++) - if (! ((j == no_conflict_pairs[k].allocno1 - && ialloc == no_conflict_pairs[k].allocno2) - || - (j == no_conflict_pairs[k].allocno2 - && ialloc == no_conflict_pairs[k].allocno1))) -#endif /* 0 */ - conflicts[ialloc_prod + j] |= allocnos_live[j]; - } - } -} - -/* Record all allocnos currently live as conflicting - 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) - int *allocno_vec; - int len; -{ - int num; - int ialloc_prod; - - while (--len >= 0) - { - num = allocno_vec[len]; - ialloc_prod = num * allocno_row_words; - IOR_HARD_REG_SET (allocno[num].hard_reg_conflicts, hard_regs_live); - } -} - -/* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */ -static void -mirror_conflicts () -{ - int i, j; - int rw = allocno_row_words; - int rwb = rw * INT_BITS; - INT_TYPE *p = conflicts; - INT_TYPE *q0 = conflicts, *q1, *q2; - unsigned INT_TYPE mask; - - for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1) - { - if (! mask) - { - mask = 1; - q0++; - } - for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb) - { - unsigned INT_TYPE word; - - for (word = (unsigned INT_TYPE) *p++, q2 = q1; word; - word >>= 1, q2 += rw) - { - if (word & 1) - *q2 |= mask; - } - } - } -} - -/* 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. - - SETTER is 0 if this register was modified by an auto-increment (i.e., - a REG_INC note was found for it). */ - -static void -mark_reg_store (reg, setter, data) - rtx reg, setter; - void *data ATTRIBUTE_UNUSED; -{ - int regno; - - if (GET_CODE (reg) == SUBREG) - reg = SUBREG_REG (reg); - - if (GET_CODE (reg) != REG) - return; - - regs_set[n_regs_set++] = reg; - - if (setter && GET_CODE (setter) != CLOBBER) - set_preference (reg, SET_SRC (setter)); - - regno = REGNO (reg); - - /* 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); - } - } - - if (reg_renumber[regno] >= 0) - regno = reg_renumber[regno]; - - /* Handle hardware regs (and pseudos allocated to hard regs). */ - if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) - { - 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, data) - rtx reg, setter; - void *data ATTRIBUTE_UNUSED; -{ - if (GET_CODE (setter) == CLOBBER) - mark_reg_store (reg, setter, data); -} - -/* Record that REG has conflicts with all the regs currently live. - Do not mark REG itself as live. */ - -static void -mark_reg_conflicts (reg) - rtx reg; -{ - int regno; - - if (GET_CODE (reg) == SUBREG) - reg = SUBREG_REG (reg); - - if (GET_CODE (reg) != REG) - return; - - regno = REGNO (reg); - - /* 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) - record_one_conflict (regno); - } - - if (reg_renumber[regno] >= 0) - regno = reg_renumber[regno]; - - /* Handle hardware regs (and pseudos allocated to hard regs). */ - if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) - { - int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg)); - while (regno < last) - { - record_one_conflict (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; -{ - int regno = REGNO (reg); - - /* 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]); - } - - /* For pseudo reg, see if it has been assigned a hardware reg. */ - if (reg_renumber[regno] >= 0) - regno = reg_renumber[regno]; - - /* Handle hardware regs (and pseudos allocated to hard regs). */ - if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno]) - { - /* Pseudo regs already assigned hardware regs are treated - almost the same as explicit hardware regs. */ - 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) - int regno; - enum machine_mode mode; -{ - 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 aggressive as local-alloc in trying to tie a - pseudo-register to a hard register. */ - -static void -set_preference (dest, src) - rtx dest, src; -{ - unsigned 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; - unsigned int i; - int copy = 1; - - if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e') - src = XEXP (src, 0), copy = 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)); - - if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER) - offset += subreg_regno_offset (REGNO (SUBREG_REG (src)), - GET_MODE (SUBREG_REG (src)), - SUBREG_BYTE (src), - GET_MODE (src)); - else - offset += (SUBREG_BYTE (src) - / REGMODE_NATURAL_SIZE (GET_MODE (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)); - - if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER) - offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)), - GET_MODE (SUBREG_REG (dest)), - SUBREG_BYTE (dest), - GET_MODE (dest)); - else - offset -= (SUBREG_BYTE (dest) - / REGMODE_NATURAL_SIZE (GET_MODE (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 < FIRST_PSEUDO_REGISTER) - { - if (copy) - SET_REGBIT (hard_reg_copy_preferences, - reg_allocno[src_regno], dest_regno); - - SET_REGBIT (hard_reg_preferences, - reg_allocno[src_regno], dest_regno); - for (i = dest_regno; - i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest)); - i++) - SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i); - } - } - - if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER - && reg_allocno[dest_regno] >= 0) - { - src_regno += offset; - if (src_regno < FIRST_PSEUDO_REGISTER) - { - if (copy) - SET_REGBIT (hard_reg_copy_preferences, - reg_allocno[dest_regno], src_regno); - - SET_REGBIT (hard_reg_preferences, - reg_allocno[dest_regno], src_regno); - for (i = src_regno; - i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src)); - i++) - SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i); - } - } -} - -/* Indicate that hard register number FROM was eliminated and replaced with - an offset from hard register number TO. The status of hard registers live - at the start of a basic block is updated by replacing a use of FROM with - a use of TO. */ - -void -mark_elimination (from, to) - int from, to; -{ - int i; - - for (i = 0; i < n_basic_blocks; i++) - { - regset r = BASIC_BLOCK (i)->global_live_at_start; - if (REGNO_REG_SET_P (r, from)) - { - CLEAR_REGNO_REG_SET (r, from); - SET_REGNO_REG_SET (r, to); - } - } -} - -/* Used for communication between the following functions. Holds the - current life information. */ -static regset live_relevant_regs; - -/* Record in live_relevant_regs and REGS_SET that register REG became live. - This is called via note_stores. */ -static void -reg_becomes_live (reg, setter, regs_set) - rtx reg; - rtx setter ATTRIBUTE_UNUSED; - void *regs_set; -{ - int regno; - - if (GET_CODE (reg) == SUBREG) - reg = SUBREG_REG (reg); - - if (GET_CODE (reg) != REG) - return; - - regno = REGNO (reg); - if (regno < FIRST_PSEUDO_REGISTER) - { - int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); - while (nregs-- > 0) - { - SET_REGNO_REG_SET (live_relevant_regs, regno); - if (! fixed_regs[regno]) - SET_REGNO_REG_SET ((regset) regs_set, regno); - regno++; - } - } - else if (reg_renumber[regno] >= 0) - { - SET_REGNO_REG_SET (live_relevant_regs, regno); - SET_REGNO_REG_SET ((regset) regs_set, regno); - } -} - -/* Record in live_relevant_regs that register REGNO died. */ -static void -reg_dies (regno, mode, chain) - int regno; - enum machine_mode mode; - struct insn_chain *chain; -{ - if (regno < FIRST_PSEUDO_REGISTER) - { - int nregs = HARD_REGNO_NREGS (regno, mode); - while (nregs-- > 0) - { - CLEAR_REGNO_REG_SET (live_relevant_regs, regno); - if (! fixed_regs[regno]) - SET_REGNO_REG_SET (&chain->dead_or_set, regno); - regno++; - } - } - else - { - CLEAR_REGNO_REG_SET (live_relevant_regs, regno); - if (reg_renumber[regno] >= 0) - SET_REGNO_REG_SET (&chain->dead_or_set, regno); - } -} - -/* Walk the insns of the current function and build reload_insn_chain, - and record register life information. */ -void -build_insn_chain (first) - rtx first; -{ - struct insn_chain **p = &reload_insn_chain; - struct insn_chain *prev = 0; - int b = 0; - regset_head live_relevant_regs_head; - - live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head); - - for (; first; first = NEXT_INSN (first)) - { - struct insn_chain *c; - - if (first == BLOCK_HEAD (b)) - { - int i; - - CLEAR_REG_SET (live_relevant_regs); - - EXECUTE_IF_SET_IN_BITMAP - (BASIC_BLOCK (b)->global_live_at_start, 0, i, - { - if (i < FIRST_PSEUDO_REGISTER - ? ! TEST_HARD_REG_BIT (eliminable_regset, i) - : reg_renumber[i] >= 0) - SET_REGNO_REG_SET (live_relevant_regs, i); - }); - } - - if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER) - { - c = new_insn_chain (); - c->prev = prev; - prev = c; - *p = c; - p = &c->next; - c->insn = first; - c->block = b; - - if (INSN_P (first)) - { - rtx link; - - /* Mark the death of everything that dies in this instruction. */ - - for (link = REG_NOTES (first); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_DEAD - && GET_CODE (XEXP (link, 0)) == REG) - reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)), - c); - - COPY_REG_SET (&c->live_throughout, live_relevant_regs); - - /* Mark everything born in this instruction as live. */ - - note_stores (PATTERN (first), reg_becomes_live, - &c->dead_or_set); - } - else - COPY_REG_SET (&c->live_throughout, live_relevant_regs); - - if (INSN_P (first)) - { - rtx link; - - /* Mark anything that is set in this insn and then unused as dying. */ - - for (link = REG_NOTES (first); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == REG_UNUSED - && GET_CODE (XEXP (link, 0)) == REG) - reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)), - c); - } - } - - if (first == BLOCK_END (b)) - b++; - - /* Stop after we pass the end of the last basic block. Verify that - no real insns are after the end of the last basic block. - - We may want to reorganize the loop somewhat since this test should - always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if - the previous real insn is a JUMP_INSN. */ - if (b == n_basic_blocks) - { - for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first)) - if (INSN_P (first) - && GET_CODE (PATTERN (first)) != USE - && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC - || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC) - && prev_real_insn (first) != 0 - && GET_CODE (prev_real_insn (first)) == JUMP_INSN)) - abort (); - break; - } - } - FREE_REG_SET (live_relevant_regs); - *p = 0; -} - -/* Print debugging trace information if -dg switch is given, - showing the information on which the allocation decisions are based. */ - -static void -dump_conflicts (file) - FILE *file; -{ - int i; - int has_preferences; - int nregs; - nregs = 0; - for (i = 0; i < max_allocno; i++) - { - if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) - continue; - nregs++; - } - fprintf (file, ";; %d regs to allocate:", nregs); - for (i = 0; i < max_allocno; i++) - { - int j; - if (reg_renumber[allocno[allocno_order[i]].reg] >= 0) - continue; - fprintf (file, " %d", allocno[allocno_order[i]].reg); - for (j = 0; j < max_regno; j++) - if (reg_allocno[j] == allocno_order[i] - && j != allocno[allocno_order[i]].reg) - fprintf (file, "+%d", j); - if (allocno[allocno_order[i]].size != 1) - fprintf (file, " (%d)", allocno[allocno_order[i]].size); - } - fprintf (file, "\n"); - - for (i = 0; i < max_allocno; i++) - { - int j; - fprintf (file, ";; %d conflicts:", allocno[i].reg); - for (j = 0; j < max_allocno; j++) - if (CONFLICTP (j, i)) - fprintf (file, " %d", allocno[j].reg); - for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) - if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)) - fprintf (file, " %d", j); - fprintf (file, "\n"); - - has_preferences = 0; - for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) - if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j)) - has_preferences = 1; - - if (! has_preferences) - continue; - fprintf (file, ";; %d preferences:", allocno[i].reg); - for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) - if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j)) - fprintf (file, " %d", j); - fprintf (file, "\n"); - } - fprintf (file, "\n"); -} - -void -dump_global_regs (file) - FILE *file; -{ - int i, j; - - fprintf (file, ";; Register dispositions:\n"); - for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++) - if (reg_renumber[i] >= 0) - { - fprintf (file, "%d in %d ", i, reg_renumber[i]); - if (++j % 6 == 0) - fprintf (file, "\n"); - } - - 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"); -}