diff options
Diffstat (limited to 'gcc/local-alloc.c')
-rw-r--r-- | gcc/local-alloc.c | 292 |
1 files changed, 204 insertions, 88 deletions
diff --git a/gcc/local-alloc.c b/gcc/local-alloc.c index e3b1667b403..f91988591ae 100644 --- a/gcc/local-alloc.c +++ b/gcc/local-alloc.c @@ -1,5 +1,5 @@ /* Allocate registers within a basic block, for GNU compiler. - Copyright (C) 1987, 88, 91, 93-97, 1998 Free Software Foundation, Inc. + Copyright (C) 1987, 88, 91, 93-98, 1999 Free Software Foundation, Inc. This file is part of GNU CC. @@ -235,6 +235,9 @@ static rtx this_insn; static rtx *reg_equiv_replacement; +/* Used for communication between update_equiv_regs and no_equiv. */ +static rtx *reg_equiv_init_insns; + static void alloc_qty PROTO((int, enum machine_mode, int, int)); static void validate_equiv_mem_from_store PROTO((rtx, rtx)); static int validate_equiv_mem PROTO((rtx, rtx, rtx)); @@ -242,6 +245,7 @@ static int contains_replace_regs PROTO((rtx, char *)); static int memref_referenced_p PROTO((rtx, rtx)); static int memref_used_between_p PROTO((rtx, rtx, rtx)); static void update_equiv_regs PROTO((void)); +static void no_equiv PROTO((rtx, rtx)); static void block_alloc PROTO((int)); static int qty_sugg_compare PROTO((int, int)); static int qty_sugg_compare_1 PROTO((const GENERIC_PTR, const GENERIC_PTR)); @@ -258,7 +262,7 @@ static int find_free_reg PROTO((enum reg_class, enum machine_mode, static void mark_life PROTO((int, enum machine_mode, int)); static void post_mark_life PROTO((int, enum machine_mode, int, int, int)); static int no_conflict_p PROTO((rtx, rtx, rtx)); -static int requires_inout PROTO((char *)); +static int requires_inout PROTO((const char *)); /* Allocate a new quantity (new within current basic block) for register number REGNO which is born at index BIRTH @@ -334,9 +338,9 @@ local_alloc () qty_n_refs = (int *) alloca (max_qty * sizeof (int)); qty_changes_size = (char *) alloca (max_qty * sizeof (char)); - reg_qty = (int *) alloca (max_regno * sizeof (int)); - reg_offset = (char *) alloca (max_regno * sizeof (char)); - reg_next_in_qty = (int *) alloca (max_regno * sizeof (int)); + reg_qty = (int *) xmalloc (max_regno * sizeof (int)); + reg_offset = (char *) xmalloc (max_regno * sizeof (char)); + reg_next_in_qty = (int *) xmalloc(max_regno * sizeof (int)); /* Allocate the reg_renumber array */ allocate_reg_info (max_regno, FALSE, TRUE); @@ -403,6 +407,10 @@ local_alloc () alloca (0); #endif } + + free (reg_qty); + free (reg_offset); + free (reg_next_in_qty); } /* Depth of loops we are in while in update_equiv_regs. */ @@ -421,7 +429,7 @@ static int equiv_mem_modified; static void validate_equiv_mem_from_store (dest, set) rtx dest; - rtx set; + rtx set ATTRIBUTE_UNUSED; { if ((GET_CODE (dest) == REG && reg_overlap_mentioned_p (dest, equiv_mem)) @@ -623,6 +631,22 @@ memref_used_between_p (memref, start, end) return 0; } +/* Return nonzero if the rtx X is invariant over the current function. */ +int +function_invariant_p (x) + rtx x; +{ + if (CONSTANT_P (x)) + return 1; + if (x == frame_pointer_rtx || x == arg_pointer_rtx) + return 1; + if (GET_CODE (x) == PLUS + && (XEXP (x, 0) == frame_pointer_rtx || XEXP (x, 0) == arg_pointer_rtx) + && CONSTANT_P (XEXP (x, 1))) + return 1; + return 0; +} + /* Find registers that are equivalent to a single value throughout the compilation (either because they can be referenced in memory or are set once from a single constant). Lower their priority for a register. @@ -634,7 +658,6 @@ memref_used_between_p (memref, start, end) static void update_equiv_regs () { - rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *)); /* Set when an attempt should be made to replace a register with the associated reg_equiv_replacement entry at the end of this function. */ char *reg_equiv_replace @@ -642,10 +665,11 @@ update_equiv_regs () rtx insn; int block, depth; - reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *)); + reg_equiv_init_insns = (rtx *) alloca (max_regno * sizeof (rtx)); + reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx)); - bzero ((char *) reg_equiv_init_insn, max_regno * sizeof (rtx *)); - bzero ((char *) reg_equiv_replacement, max_regno * sizeof (rtx *)); + bzero ((char *) reg_equiv_init_insns, max_regno * sizeof (rtx)); + bzero ((char *) reg_equiv_replacement, max_regno * sizeof (rtx)); bzero ((char *) reg_equiv_replace, max_regno * sizeof *reg_equiv_replace); init_alias_analysis (); @@ -658,7 +682,7 @@ update_equiv_regs () for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) { rtx note; - rtx set = single_set (insn); + rtx set; rtx dest, src; int regno; @@ -670,10 +694,34 @@ update_equiv_regs () loop_depth--; } - /* If this insn contains more (or less) than a single SET, ignore it. */ - if (set == 0) + if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') continue; + for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) + if (REG_NOTE_KIND (note) == REG_INC) + no_equiv (XEXP (note, 0), note); + + set = single_set (insn); + + /* If this insn contains more (or less) than a single SET, + only mark all destinations as having no known equivalence. */ + if (set == 0) + { + note_stores (PATTERN (insn), no_equiv); + continue; + } + else if (GET_CODE (PATTERN (insn)) == PARALLEL) + { + int i; + + for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) + { + rtx part = XVECEXP (PATTERN (insn), 0, i); + if (part != set) + note_stores (part, no_equiv); + } + } + dest = SET_DEST (set); src = SET_SRC (set); @@ -689,60 +737,83 @@ update_equiv_regs () If one of the regs in the address is marked as reg_equiv_replace, then we can't add this REG_EQUIV note. The reg_equiv_replace optimization may move the set of this register immediately before - insn, which puts it after reg_equiv_init_insn[regno], and hence + insn, which puts it after reg_equiv_init_insns[regno], and hence the mention in the REG_EQUIV note would be to an uninitialized pseudo. */ - - if (GET_CODE (dest) == MEM && GET_CODE (SET_SRC (set)) == REG - && (regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER + /* ????? This test isn't good enough; we might see a MEM with a use of + a pseudo register before we see its setting insn that will cause + reg_equiv_replace for that pseudo to be set. + Equivalences to MEMs should be made in another pass, after the + reg_equiv_replace information has been gathered. */ + + if (GET_CODE (dest) == MEM && GET_CODE (src) == REG + && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER && REG_BASIC_BLOCK (regno) >= 0 - && reg_equiv_init_insn[regno] != 0 + && REG_N_SETS (regno) == 1 + && reg_equiv_init_insns[regno] != 0 + && reg_equiv_init_insns[regno] != const0_rtx && ! find_reg_note (insn, REG_EQUIV, NULL_RTX) - && ! contains_replace_regs (XEXP (dest, 0), reg_equiv_replace) - && validate_equiv_mem (reg_equiv_init_insn[regno], SET_SRC (set), - dest) - && ! memref_used_between_p (SET_DEST (set), - reg_equiv_init_insn[regno], insn)) - REG_NOTES (reg_equiv_init_insn[regno]) - = gen_rtx_EXPR_LIST (REG_EQUIV, dest, - REG_NOTES (reg_equiv_init_insn[regno])); + && ! contains_replace_regs (XEXP (dest, 0), reg_equiv_replace)) + { + rtx init_insn = XEXP (reg_equiv_init_insns[regno], 0); + if (validate_equiv_mem (init_insn, src, dest) + && ! memref_used_between_p (dest, init_insn, insn)) + REG_NOTES (init_insn) + = gen_rtx_EXPR_LIST (REG_EQUIV, dest, REG_NOTES (init_insn)); + } /* We only handle the case of a pseudo register being set - once and only if neither the source nor the destination are - in a register class that's likely to be spilled. */ + once, or always to the same value. */ + /* ??? The mn10200 port breaks if we add equivalences for + values that need an ADDRESS_REGS register and set them equivalent + to a MEM of a pseudo. The actual problem is in the over-conservative + handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in + calculate_needs, but we traditionally work around this problem + here by rejecting equivalences when the destination is in a register + that's likely spilled. This is fragile, of course, since the + preferred class of a pseudo depends on all instructions that set + or use it. */ + if (GET_CODE (dest) != REG || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER - || REG_N_SETS (regno) != 1 - || CLASS_LIKELY_SPILLED_P (reg_preferred_class (REGNO (dest))) - || (GET_CODE (src) == REG - && REGNO (src) >= FIRST_PSEUDO_REGISTER - && CLASS_LIKELY_SPILLED_P (reg_preferred_class (REGNO (src))))) - continue; + || reg_equiv_init_insns[regno] == const0_rtx + || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno)) + && GET_CODE (src) == MEM)) + { + /* This might be seting a SUBREG of a pseudo, a pseudo that is + also set somewhere else to a constant. */ + note_stores (set, no_equiv); + continue; + } + /* Don't handle the equivalence if the source is in a register + class that's likely to be spilled. */ + if (GET_CODE (src) == REG + && REGNO (src) >= FIRST_PSEUDO_REGISTER + && CLASS_LIKELY_SPILLED_P (reg_preferred_class (REGNO (src)))) + { + no_equiv (dest, set); + continue; + } note = find_reg_note (insn, REG_EQUAL, NULL_RTX); -#ifdef DONT_RECORD_EQUIVALENCE - /* Allow the target to reject promotions of some REG_EQUAL notes to - REG_EQUIV notes. - - In some cases this can improve register allocation if the existence - of the REG_EQUIV note is likely to increase the lifetime of a register - that is likely to be spilled. - - It may also be necessary if the target can't handle certain constant - expressions appearing randomly in insns, but for whatever reason - those expressions must be considered legitimate constant expressions - to prevent them from being forced into memory. */ - if (note && DONT_RECORD_EQUIVALENCE (note)) - note = NULL; -#endif - + if (REG_N_SETS (regno) != 1 + && (! note + || ! function_invariant_p (XEXP (note, 0)) + || (reg_equiv_replacement[regno] + && ! rtx_equal_p (XEXP (note, 0), + reg_equiv_replacement[regno])))) + { + no_equiv (dest, set); + continue; + } /* Record this insn as initializing this register. */ - reg_equiv_init_insn[regno] = insn; + reg_equiv_init_insns[regno] + = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init_insns[regno]); /* If this register is known to be equal to a constant, record that it is always equivalent to the constant. */ - if (note && CONSTANT_P (XEXP (note, 0))) + if (note && function_invariant_p (XEXP (note, 0))) PUT_MODE (note, (enum machine_mode) REG_EQUIV); /* If this insn introduces a "constant" register, decrease the priority @@ -818,7 +889,7 @@ update_equiv_regs () /* Keep track of which basic block we are in. */ if (block + 1 < n_basic_blocks - && basic_block_head[block + 1] == insn) + && BLOCK_HEAD (block + 1) == insn) ++block; if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') @@ -850,7 +921,12 @@ update_equiv_regs () if (! reg_equiv_replace[regno]) continue; - equiv_insn = reg_equiv_init_insn[regno]; + /* reg_equiv_replace[REGNO] gets set only when + REG_N_REFS[REGNO] is 2, i.e. the register is set + once and used once. (If it were only set, but not used, + flow would have deleted the setting insns.) Hence + there can only be one insn in reg_equiv_init_insns. */ + equiv_insn = XEXP (reg_equiv_init_insns[regno], 0); if (validate_replace_rtx (regno_reg_rtx[regno], reg_equiv_replacement[regno], insn)) @@ -887,16 +963,46 @@ update_equiv_regs () REG_N_CALLS_CROSSED (regno) = 0; REG_LIVE_LENGTH (regno) = 2; - if (block >= 0 && insn == basic_block_head[block]) - basic_block_head[block] = PREV_INSN (insn); + if (block >= 0 && insn == BLOCK_HEAD (block)) + BLOCK_HEAD (block) = PREV_INSN (insn); for (l = 0; l < n_basic_blocks; l++) - CLEAR_REGNO_REG_SET (basic_block_live_at_start[l], regno); + CLEAR_REGNO_REG_SET (BASIC_BLOCK (l)->global_live_at_start, + regno); } } } } } + +/* Mark REG as having no known equivalence. + Some instructions might have been proceessed before and furnished + with REG_EQUIV notes for this register; these notes will have to be + removed. + STORE is the piece of RTL that does the non-constant / conflicting + assignment - a SET, CLOBBER or REG_INC note. It is currently not used, + but needs to be there because this function is called from note_stores. */ +static void +no_equiv (reg, store) + rtx reg, store ATTRIBUTE_UNUSED; +{ + int regno; + rtx list; + + if (GET_CODE (reg) != REG) + return; + regno = REGNO (reg); + list = reg_equiv_init_insns[regno]; + if (list == const0_rtx) + return; + for (; list; list = XEXP (list, 1)) + { + rtx insn = XEXP (list, 0); + remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX)); + } + reg_equiv_init_insns[regno] = const0_rtx; + reg_equiv_replacement[regno] = NULL_RTX; +} /* Allocate hard regs to the pseudo regs used only within block number B. Only the pseudos that die but once can be handled. */ @@ -916,13 +1022,13 @@ block_alloc (b) /* Count the instructions in the basic block. */ - insn = basic_block_end[b]; + insn = BLOCK_END (b); while (1) { if (GET_CODE (insn) != NOTE) if (++insn_count > max_uid) abort (); - if (insn == basic_block_head[b]) + if (insn == BLOCK_HEAD (b)) break; insn = PREV_INSN (insn); } @@ -935,13 +1041,13 @@ block_alloc (b) /* Initialize table of hardware registers currently live. */ - REG_SET_TO_HARD_REG_SET (regs_live, basic_block_live_at_start[b]); + REG_SET_TO_HARD_REG_SET (regs_live, BASIC_BLOCK (b)->global_live_at_start); /* This loop scans the instructions of the basic block and assigns quantities to registers. It computes which registers to tie. */ - insn = basic_block_head[b]; + insn = BLOCK_HEAD (b); while (1) { register rtx body = PATTERN (insn); @@ -956,13 +1062,11 @@ block_alloc (b) register rtx r0, r1; int combined_regno = -1; int i; - int insn_code_number = recog_memoized (insn); this_insn_number = insn_number; this_insn = insn; - if (insn_code_number >= 0) - insn_extract (insn); + extract_insn (insn); which_alternative = -1; /* Is this insn suitable for tying two registers? @@ -983,11 +1087,11 @@ block_alloc (b) If tying is done, WIN is set nonzero. */ - if (insn_code_number >= 0 + if (1 #ifdef REGISTER_CONSTRAINTS - && insn_n_operands[insn_code_number] > 1 - && insn_operand_constraint[insn_code_number][0][0] == '=' - && insn_operand_constraint[insn_code_number][0][1] != '&' + && recog_n_operands > 1 + && recog_constraints[0][0] == '=' + && recog_constraints[0][1] != '&' #else && GET_CODE (PATTERN (insn)) == SET && rtx_equal_p (SET_DEST (PATTERN (insn)), recog_operand[0]) @@ -1001,19 +1105,19 @@ block_alloc (b) operand 0. */ int n_matching_alts = 0; - for (i = 1; i < insn_n_operands[insn_code_number]; i++) + for (i = 1; i < recog_n_operands; i++) { - char *p = insn_operand_constraint[insn_code_number][i]; + const char *p = recog_constraints[i]; int this_match = (requires_inout (p)); n_matching_alts += this_match; - if (this_match == insn_n_alternatives[insn_code_number]) + if (this_match == recog_n_alternatives) must_match_0 = i; } #endif r0 = recog_operand[0]; - for (i = 1; i < insn_n_operands[insn_code_number]; i++) + for (i = 1; i < recog_n_operands; i++) { #ifdef REGISTER_CONSTRAINTS /* Skip this operand if we found an operand that @@ -1022,9 +1126,9 @@ block_alloc (b) if (must_match_0 >= 0 && i != must_match_0 && ! (i == must_match_0 + 1 - && insn_operand_constraint[insn_code_number][i-1][0] == '%') + && recog_constraints[i-1][0] == '%') && ! (i == must_match_0 - 1 - && insn_operand_constraint[insn_code_number][i][0] == '%')) + && recog_constraints[i][0] == '%')) continue; /* Likewise if each alternative has some operand that @@ -1032,9 +1136,8 @@ block_alloc (b) operand that doesn't list operand 0 since we know that the operand always conflicts with operand 0. We ignore commutatity in this case to keep things simple. */ - if (n_matching_alts == insn_n_alternatives[insn_code_number] - && (0 == requires_inout - (insn_operand_constraint[insn_code_number][i]))) + if (n_matching_alts == recog_n_alternatives + && 0 == requires_inout (recog_constraints[i])) continue; #endif @@ -1045,9 +1148,9 @@ block_alloc (b) of them. */ if ( #ifdef REGISTER_CONSTRAINTS - insn_operand_constraint[insn_code_number][i][0] == 'p' + recog_constraints[i][0] == 'p' #else - insn_operand_address_p[insn_code_number][i] + recog_operand_address_p[i] #endif ) while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT) @@ -1182,7 +1285,7 @@ block_alloc (b) IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live); IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live); - if (insn == basic_block_end[b]) + if (insn == BLOCK_END (b)) break; insn = NEXT_INSN (insn); @@ -1297,8 +1400,8 @@ block_alloc (b) discourage the register allocator from creating false dependencies. - The adjustment by the value +-3 indicates precisely that - this qty conflicts with qtys in the instructions immediately + The adjustment value is choosen to indicate that this qty + conflicts with all the qtys in the instructions immediately before and after the lifetime of this qty. Experiments have shown that higher values tend to hurt @@ -1306,8 +1409,9 @@ block_alloc (b) If allocation using the extended lifetime fails we will try again with the qty's unadjusted lifetime. */ - int fake_birth = MAX (0, qty_birth[q] - 3); - int fake_death = MIN (insn_number * 2 + 1, qty_death[q] + 3); + int fake_birth = MAX (0, qty_birth[q] - 2 + qty_birth[q] % 2); + int fake_death = MIN (insn_number * 2 + 1, + qty_death[q] + 2 - qty_death[q] % 2); #endif if (N_REG_CLASSES > 1) @@ -1545,6 +1649,11 @@ combine_regs (usedreg, setreg, may_save_copy, insn_number, insn, already_dead) || ureg == sreg /* Don't try to connect two different hardware registers. */ || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER) + /* Don't use a hard reg that might be spilled. */ + || (ureg < FIRST_PSEUDO_REGISTER + && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (ureg))) + || (sreg < FIRST_PSEUDO_REGISTER + && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (sreg))) /* Don't connect two different machine modes if they have different implications as to which registers may be used. */ || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))) @@ -1758,9 +1867,16 @@ wipe_dead_reg (reg, output_p) /* If this insn has multiple results, and the dead reg is used in one of the results, extend its life to after this insn, - so it won't get allocated together with any other result of this insn. */ + so it won't get allocated together with any other result of this insn. + + 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 (this_insn)) == PARALLEL - && !single_set (this_insn)) + && multiple_sets (this_insn)) { int i; for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--) @@ -1859,7 +1975,7 @@ find_free_reg (class, mode, qty, accept_call_clobbered, just_try_suggested, This is true of any register that can be eliminated. */ #ifdef ELIMINABLE_REGS - for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++) + for (i = 0; i < (int)(sizeof eliminables / sizeof eliminables[0]); i++) SET_HARD_REG_BIT (used, eliminables[i].from); #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM /* If FRAME_POINTER_REGNUM is not a real register, then protect the one @@ -2068,7 +2184,7 @@ no_conflict_p (insn, r0, r1) static int requires_inout (p) - char *p; + const char *p; { char c; int found_zero = 0; |