diff options
Diffstat (limited to 'gcc/lra-eliminations.c')
| -rw-r--r-- | gcc/lra-eliminations.c | 1301 |
1 files changed, 1301 insertions, 0 deletions
diff --git a/gcc/lra-eliminations.c b/gcc/lra-eliminations.c new file mode 100644 index 00000000000..2222d805f1b --- /dev/null +++ b/gcc/lra-eliminations.c @@ -0,0 +1,1301 @@ +/* Code for RTL register eliminations. + Copyright (C) 2010, 2011, 2012 + Free Software Foundation, Inc. + Contributed by Vladimir Makarov <vmakarov@redhat.com>. + +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 3, 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 COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +/* Eliminable registers (like a soft argument or frame pointer) are + widely used in RTL. These eliminable registers should be replaced + by real hard registers (like the stack pointer or hard frame + pointer) plus some offset. The offsets usually change whenever the + stack is expanded. We know the final offsets only at the very end + of LRA. + + Within LRA, we usually keep the RTL in such a state that the + eliminable registers can be replaced by just the corresponding hard + register (without any offset). To achieve this we should add the + initial elimination offset at the beginning of LRA and update the + offsets whenever the stack is expanded. We need to do this before + every constraint pass because the choice of offset often affects + whether a particular address or memory constraint is satisfied. + + We keep RTL code at most time in such state that the virtual + registers can be changed by just the corresponding hard registers + (with zero offsets) and we have the right RTL code. To achieve this + we should add initial offset at the beginning of LRA work and update + offsets after each stack expanding. But actually we update virtual + registers to the same virtual registers + corresponding offsets + before every constraint pass because it affects constraint + satisfaction (e.g. an address displacement became too big for some + target). + + The final change of eliminable registers to the corresponding hard + registers are done at the very end of LRA when there were no change + in offsets anymore: + + fp + 42 => sp + 42 + +*/ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "hard-reg-set.h" +#include "rtl.h" +#include "tm_p.h" +#include "regs.h" +#include "insn-config.h" +#include "insn-codes.h" +#include "recog.h" +#include "output.h" +#include "addresses.h" +#include "target.h" +#include "function.h" +#include "expr.h" +#include "basic-block.h" +#include "except.h" +#include "optabs.h" +#include "df.h" +#include "ira.h" +#include "rtl-error.h" +#include "lra-int.h" + +/* This structure is used to record information about hard register + eliminations. */ +struct elim_table +{ + /* Hard register number to be eliminated. */ + int from; + /* Hard register number used as replacement. */ + int to; + /* Difference between values of the two hard registers above on + previous iteration. */ + HOST_WIDE_INT previous_offset; + /* Difference between the values on the current iteration. */ + HOST_WIDE_INT offset; + /* Nonzero if this elimination can be done. */ + bool can_eliminate; + /* CAN_ELIMINATE since the last check. */ + bool prev_can_eliminate; + /* REG rtx for the register to be eliminated. We cannot simply + compare the number since we might then spuriously replace a hard + register corresponding to a pseudo assigned to the reg to be + eliminated. */ + rtx from_rtx; + /* REG rtx for the replacement. */ + rtx to_rtx; +}; + +/* The elimination table. Each array entry describes one possible way + of eliminating a register in favor of another. If there is more + than one way of eliminating a particular register, the most + preferred should be specified first. */ +static struct elim_table *reg_eliminate = 0; + +/* This is an intermediate structure to initialize the table. It has + exactly the members provided by ELIMINABLE_REGS. */ +static const struct elim_table_1 +{ + const int from; + const int to; +} reg_eliminate_1[] = + +/* If a set of eliminable hard registers was specified, define the + table from it. Otherwise, default to the normal case of the frame + pointer being replaced by the stack pointer. */ + +#ifdef ELIMINABLE_REGS + ELIMINABLE_REGS; +#else + {{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}}; +#endif + +#define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1) + +/* Print info about elimination table to file F. */ +static void +print_elim_table (FILE *f) +{ + struct elim_table *ep; + + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + fprintf (f, "%s eliminate %d to %d (offset=" HOST_WIDE_INT_PRINT_DEC + ", prev_offset=" HOST_WIDE_INT_PRINT_DEC ")\n", + ep->can_eliminate ? "Can" : "Can't", + ep->from, ep->to, ep->offset, ep->previous_offset); +} + +/* Print info about elimination table to stderr. */ +void +lra_debug_elim_table (void) +{ + print_elim_table (stderr); +} + +/* Setup possibility of elimination in elimination table element EP to + VALUE. Setup FRAME_POINTER_NEEDED if elimination from frame + pointer to stack pointer is not possible anymore. */ +static void +setup_can_eliminate (struct elim_table *ep, bool value) +{ + ep->can_eliminate = ep->prev_can_eliminate = value; + if (! value + && ep->from == FRAME_POINTER_REGNUM && ep->to == STACK_POINTER_REGNUM) + frame_pointer_needed = 1; +} + +/* Map: eliminable "from" register -> its current elimination, + or NULL if none. The elimination table may contain more than + one elimination for the same hard register, but this map specifies + the one that we are currently using. */ +static struct elim_table *elimination_map[FIRST_PSEUDO_REGISTER]; + +/* When an eliminable hard register becomes not eliminable, we use the + following special structure to restore original offsets for the + register. */ +static struct elim_table self_elim_table; + +/* Offsets should be used to restore original offsets for eliminable + hard register which just became not eliminable. Zero, + otherwise. */ +static HOST_WIDE_INT self_elim_offsets[FIRST_PSEUDO_REGISTER]; + +/* Map: hard regno -> RTL presentation. RTL presentations of all + potentially eliminable hard registers are stored in the map. */ +static rtx eliminable_reg_rtx[FIRST_PSEUDO_REGISTER]; + +/* Set up ELIMINATION_MAP of the currently used eliminations. */ +static void +setup_elimination_map (void) +{ + int i; + struct elim_table *ep; + + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + elimination_map[i] = NULL; + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + if (ep->can_eliminate && elimination_map[ep->from] == NULL) + elimination_map[ep->from] = ep; +} + + + +/* Compute the sum of X and Y, making canonicalizations assumed in an + address, namely: sum constant integers, surround the sum of two + constants with a CONST, put the constant as the second operand, and + group the constant on the outermost sum. + + This routine assumes both inputs are already in canonical form. */ +static rtx +form_sum (rtx x, rtx y) +{ + rtx tem; + enum machine_mode mode = GET_MODE (x); + + if (mode == VOIDmode) + mode = GET_MODE (y); + + if (mode == VOIDmode) + mode = Pmode; + + if (CONST_INT_P (x)) + return plus_constant (mode, y, INTVAL (x)); + else if (CONST_INT_P (y)) + return plus_constant (mode, x, INTVAL (y)); + else if (CONSTANT_P (x)) + tem = x, x = y, y = tem; + + if (GET_CODE (x) == PLUS && CONSTANT_P (XEXP (x, 1))) + return form_sum (XEXP (x, 0), form_sum (XEXP (x, 1), y)); + + /* Note that if the operands of Y are specified in the opposite + order in the recursive calls below, infinite recursion will + occur. */ + if (GET_CODE (y) == PLUS && CONSTANT_P (XEXP (y, 1))) + return form_sum (form_sum (x, XEXP (y, 0)), XEXP (y, 1)); + + /* If both constant, encapsulate sum. Otherwise, just form sum. A + constant will have been placed second. */ + if (CONSTANT_P (x) && CONSTANT_P (y)) + { + if (GET_CODE (x) == CONST) + x = XEXP (x, 0); + if (GET_CODE (y) == CONST) + y = XEXP (y, 0); + + return gen_rtx_CONST (VOIDmode, gen_rtx_PLUS (mode, x, y)); + } + + return gen_rtx_PLUS (mode, x, y); +} + +/* Return the current substitution hard register of the elimination of + HARD_REGNO. If HARD_REGNO is not eliminable, return itself. */ +int +lra_get_elimination_hard_regno (int hard_regno) +{ + struct elim_table *ep; + + if (hard_regno < 0 || hard_regno >= FIRST_PSEUDO_REGISTER) + return hard_regno; + if ((ep = elimination_map[hard_regno]) == NULL) + return hard_regno; + return ep->to; +} + +/* Return elimination which will be used for hard reg REG, NULL + otherwise. */ +static struct elim_table * +get_elimination (rtx reg) +{ + int hard_regno; + struct elim_table *ep; + HOST_WIDE_INT offset; + + lra_assert (REG_P (reg)); + if ((hard_regno = REGNO (reg)) < 0 || hard_regno >= FIRST_PSEUDO_REGISTER) + return NULL; + if ((ep = elimination_map[hard_regno]) != NULL) + return ep->from_rtx != reg ? NULL : ep; + if ((offset = self_elim_offsets[hard_regno]) == 0) + return NULL; + /* This is an iteration to restore offsets just after HARD_REGNO + stopped to be eliminable. */ + self_elim_table.from = self_elim_table.to = hard_regno; + self_elim_table.from_rtx + = self_elim_table.to_rtx + = eliminable_reg_rtx[hard_regno]; + lra_assert (self_elim_table.from_rtx != NULL); + self_elim_table.offset = offset; + return &self_elim_table; +} + +/* Scan X and replace any eliminable registers (such as fp) with a + replacement (such as sp) if SUBST_P, plus an offset. The offset is + a change in the offset between the eliminable register and its + substitution if UPDATE_P, or the full offset if FULL_P, or + otherwise zero. + + MEM_MODE is the mode of an enclosing MEM. We need this to know how + much to adjust a register for, e.g., PRE_DEC. Also, if we are + inside a MEM, we are allowed to replace a sum of a hard register + and the constant zero with the hard register, which we cannot do + outside a MEM. In addition, we need to record the fact that a + hard register is referenced outside a MEM. + + Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST). + That's used when we eliminate in expressions stored in notes. */ +rtx +lra_eliminate_regs_1 (rtx x, enum machine_mode mem_mode, + bool subst_p, bool update_p, bool full_p) +{ + enum rtx_code code = GET_CODE (x); + struct elim_table *ep; + rtx new_rtx; + int i, j; + const char *fmt; + int copied = 0; + + if (! current_function_decl) + return x; + + switch (code) + { + CASE_CONST_ANY: + case CONST: + case SYMBOL_REF: + case CODE_LABEL: + case PC: + case CC0: + case ASM_INPUT: + case ADDR_VEC: + case ADDR_DIFF_VEC: + case RETURN: + return x; + + case REG: + /* First handle the case where we encounter a bare hard register + that is eliminable. Replace it with a PLUS. */ + if ((ep = get_elimination (x)) != NULL) + { + rtx to = subst_p ? ep->to_rtx : ep->from_rtx; + + if (update_p) + return plus_constant (Pmode, to, ep->offset - ep->previous_offset); + else if (full_p) + return plus_constant (Pmode, to, ep->offset); + else + return to; + } + return x; + + case PLUS: + /* If this is the sum of an eliminable register and a constant, rework + the sum. */ + if (REG_P (XEXP (x, 0)) && CONSTANT_P (XEXP (x, 1))) + { + if ((ep = get_elimination (XEXP (x, 0))) != NULL) + { + HOST_WIDE_INT offset; + rtx to = subst_p ? ep->to_rtx : ep->from_rtx; + + if (! update_p && ! full_p) + return gen_rtx_PLUS (Pmode, to, XEXP (x, 1)); + + offset = (update_p + ? ep->offset - ep->previous_offset : ep->offset); + if (CONST_INT_P (XEXP (x, 1)) + && INTVAL (XEXP (x, 1)) == -offset) + return to; + else + return gen_rtx_PLUS (Pmode, to, + plus_constant (Pmode, + XEXP (x, 1), offset)); + } + + /* If the hard register is not eliminable, we are done since + the other operand is a constant. */ + return x; + } + + /* If this is part of an address, we want to bring any constant + to the outermost PLUS. We will do this by doing hard + register replacement in our operands and seeing if a constant + shows up in one of them. + + Note that there is no risk of modifying the structure of the + insn, since we only get called for its operands, thus we are + either modifying the address inside a MEM, or something like + an address operand of a load-address insn. */ + + { + rtx new0 = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode, + subst_p, update_p, full_p); + rtx new1 = lra_eliminate_regs_1 (XEXP (x, 1), mem_mode, + subst_p, update_p, full_p); + + if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1)) + return form_sum (new0, new1); + } + return x; + + case MULT: + /* If this is the product of an eliminable hard register and a + constant, apply the distribute law and move the constant out + so that we have (plus (mult ..) ..). This is needed in order + to keep load-address insns valid. This case is pathological. + We ignore the possibility of overflow here. */ + if (REG_P (XEXP (x, 0)) && CONST_INT_P (XEXP (x, 1)) + && (ep = get_elimination (XEXP (x, 0))) != NULL) + { + rtx to = subst_p ? ep->to_rtx : ep->from_rtx; + + if (update_p) + return + plus_constant (Pmode, + gen_rtx_MULT (Pmode, to, XEXP (x, 1)), + (ep->offset - ep->previous_offset) + * INTVAL (XEXP (x, 1))); + else if (full_p) + return + plus_constant (Pmode, + gen_rtx_MULT (Pmode, to, XEXP (x, 1)), + ep->offset * INTVAL (XEXP (x, 1))); + else + return gen_rtx_MULT (Pmode, to, XEXP (x, 1)); + } + + /* ... fall through ... */ + + case CALL: + case COMPARE: + /* See comments before PLUS about handling MINUS. */ + case MINUS: + case DIV: case UDIV: + case MOD: case UMOD: + case AND: case IOR: case XOR: + case ROTATERT: case ROTATE: + case ASHIFTRT: case LSHIFTRT: case ASHIFT: + case NE: case EQ: + case GE: case GT: case GEU: case GTU: + case LE: case LT: case LEU: case LTU: + { + rtx new0 = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode, + subst_p, update_p, full_p); + rtx new1 = XEXP (x, 1) + ? lra_eliminate_regs_1 (XEXP (x, 1), mem_mode, + subst_p, update_p, full_p) : 0; + + if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1)) + return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1); + } + return x; + + case EXPR_LIST: + /* If we have something in XEXP (x, 0), the usual case, + eliminate it. */ + if (XEXP (x, 0)) + { + new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode, + subst_p, update_p, full_p); + if (new_rtx != XEXP (x, 0)) + { + /* If this is a REG_DEAD note, it is not valid anymore. + Using the eliminated version could result in creating a + REG_DEAD note for the stack or frame pointer. */ + if (REG_NOTE_KIND (x) == REG_DEAD) + return (XEXP (x, 1) + ? lra_eliminate_regs_1 (XEXP (x, 1), mem_mode, + subst_p, update_p, full_p) + : NULL_RTX); + + x = alloc_reg_note (REG_NOTE_KIND (x), new_rtx, XEXP (x, 1)); + } + } + + /* ... fall through ... */ + + case INSN_LIST: + /* Now do eliminations in the rest of the chain. If this was + an EXPR_LIST, this might result in allocating more memory than is + strictly needed, but it simplifies the code. */ + if (XEXP (x, 1)) + { + new_rtx = lra_eliminate_regs_1 (XEXP (x, 1), mem_mode, + subst_p, update_p, full_p); + if (new_rtx != XEXP (x, 1)) + return + gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x), + XEXP (x, 0), new_rtx); + } + return x; + + case PRE_INC: + case POST_INC: + case PRE_DEC: + case POST_DEC: + /* We do not support elimination of a register that is modified. + elimination_effects has already make sure that this does not + happen. */ + return x; + + case PRE_MODIFY: + case POST_MODIFY: + /* We do not support elimination of a hard register that is + modified. LRA has already make sure that this does not + happen. The only remaining case we need to consider here is + that the increment value may be an eliminable register. */ + if (GET_CODE (XEXP (x, 1)) == PLUS + && XEXP (XEXP (x, 1), 0) == XEXP (x, 0)) + { + rtx new_rtx = lra_eliminate_regs_1 (XEXP (XEXP (x, 1), 1), mem_mode, + subst_p, update_p, full_p); + + if (new_rtx != XEXP (XEXP (x, 1), 1)) + return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0), + gen_rtx_PLUS (GET_MODE (x), + XEXP (x, 0), new_rtx)); + } + return x; + + case STRICT_LOW_PART: + case NEG: case NOT: + case SIGN_EXTEND: case ZERO_EXTEND: + case TRUNCATE: case FLOAT_EXTEND: case FLOAT_TRUNCATE: + case FLOAT: case FIX: + case UNSIGNED_FIX: case UNSIGNED_FLOAT: + case ABS: + case SQRT: + case FFS: + case CLZ: + case CTZ: + case POPCOUNT: + case PARITY: + case BSWAP: + new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode, + subst_p, update_p, full_p); + if (new_rtx != XEXP (x, 0)) + return gen_rtx_fmt_e (code, GET_MODE (x), new_rtx); + return x; + + case SUBREG: + new_rtx = lra_eliminate_regs_1 (SUBREG_REG (x), mem_mode, + subst_p, update_p, full_p); + + if (new_rtx != SUBREG_REG (x)) + { + int x_size = GET_MODE_SIZE (GET_MODE (x)); + int new_size = GET_MODE_SIZE (GET_MODE (new_rtx)); + + if (MEM_P (new_rtx) && x_size <= new_size) + { + SUBREG_REG (x) = new_rtx; + alter_subreg (&x, false); + return x; + } + else + return gen_rtx_SUBREG (GET_MODE (x), new_rtx, SUBREG_BYTE (x)); + } + + return x; + + case MEM: + /* Our only special processing is to pass the mode of the MEM to our + recursive call and copy the flags. While we are here, handle this + case more efficiently. */ + return + replace_equiv_address_nv + (x, + lra_eliminate_regs_1 (XEXP (x, 0), GET_MODE (x), + subst_p, update_p, full_p)); + + case USE: + /* Handle insn_list USE that a call to a pure function may generate. */ + new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), VOIDmode, + subst_p, update_p, full_p); + if (new_rtx != XEXP (x, 0)) + return gen_rtx_USE (GET_MODE (x), new_rtx); + return x; + + case CLOBBER: + case SET: + gcc_unreachable (); + + default: + break; + } + + /* Process each of our operands recursively. If any have changed, make a + copy of the rtx. */ + fmt = GET_RTX_FORMAT (code); + for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) + { + if (*fmt == 'e') + { + new_rtx = lra_eliminate_regs_1 (XEXP (x, i), mem_mode, + subst_p, update_p, full_p); + if (new_rtx != XEXP (x, i) && ! copied) + { + x = shallow_copy_rtx (x); + copied = 1; + } + XEXP (x, i) = new_rtx; + } + else if (*fmt == 'E') + { + int copied_vec = 0; + for (j = 0; j < XVECLEN (x, i); j++) + { + new_rtx = lra_eliminate_regs_1 (XVECEXP (x, i, j), mem_mode, + subst_p, update_p, full_p); + if (new_rtx != XVECEXP (x, i, j) && ! copied_vec) + { + rtvec new_v = gen_rtvec_v (XVECLEN (x, i), + XVEC (x, i)->elem); + if (! copied) + { + x = shallow_copy_rtx (x); + copied = 1; + } + XVEC (x, i) = new_v; + copied_vec = 1; + } + XVECEXP (x, i, j) = new_rtx; + } + } + } + + return x; +} + +/* This function is used externally in subsequent passes of GCC. It + always does a full elimination of X. */ +rtx +lra_eliminate_regs (rtx x, enum machine_mode mem_mode, + rtx insn ATTRIBUTE_UNUSED) +{ + return lra_eliminate_regs_1 (x, mem_mode, true, false, true); +} + +/* Scan rtx X for references to elimination source or target registers + in contexts that would prevent the elimination from happening. + Update the table of eliminables to reflect the changed state. + MEM_MODE is the mode of an enclosing MEM rtx, or VOIDmode if not + within a MEM. */ +static void +mark_not_eliminable (rtx x) +{ + enum rtx_code code = GET_CODE (x); + struct elim_table *ep; + int i, j; + const char *fmt; + + switch (code) + { + case PRE_INC: + case POST_INC: + case PRE_DEC: + case POST_DEC: + case POST_MODIFY: + case PRE_MODIFY: + if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER) + /* If we modify the source of an elimination rule, disable + it. Do the same if it is the source and not the hard frame + register. */ + for (ep = reg_eliminate; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; + ep++) + if (ep->from_rtx == XEXP (x, 0) + || (ep->to_rtx == XEXP (x, 0) + && ep->to_rtx != hard_frame_pointer_rtx)) + setup_can_eliminate (ep, false); + return; + + case USE: + if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER) + /* If using a hard register that is the source of an eliminate + we still think can be performed, note it cannot be + performed since we don't know how this hard register is + used. */ + for (ep = reg_eliminate; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; + ep++) + if (ep->from_rtx == XEXP (x, 0) + && ep->to_rtx != hard_frame_pointer_rtx) + setup_can_eliminate (ep, false); + return; + + case CLOBBER: + if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER) + /* If clobbering a hard register that is the replacement + register for an elimination we still think can be + performed, note that it cannot be performed. Otherwise, we + need not be concerned about it. */ + for (ep = reg_eliminate; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; + ep++) + if (ep->to_rtx == XEXP (x, 0) + && ep->to_rtx != hard_frame_pointer_rtx) + setup_can_eliminate (ep, false); + return; + + case SET: + /* Check for setting a hard register that we know about. */ + if (REG_P (SET_DEST (x)) && REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER) + { + /* See if this is setting the replacement hard register for + an elimination. + + If DEST is the hard frame pointer, we do nothing because + we assume that all assignments to the frame pointer are + for non-local gotos and are being done at a time when + they are valid and do not disturb anything else. Some + machines want to eliminate a fake argument pointer (or + even a fake frame pointer) with either the real frame + pointer or the stack pointer. Assignments to the hard + frame pointer must not prevent this elimination. */ + + for (ep = reg_eliminate; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; + ep++) + if (ep->to_rtx == SET_DEST (x) + && SET_DEST (x) != hard_frame_pointer_rtx) + setup_can_eliminate (ep, false); + } + + mark_not_eliminable (SET_DEST (x)); + mark_not_eliminable (SET_SRC (x)); + return; + + default: + break; + } + + fmt = GET_RTX_FORMAT (code); + for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) + { + if (*fmt == 'e') + mark_not_eliminable (XEXP (x, i)); + else if (*fmt == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + mark_not_eliminable (XVECEXP (x, i, j)); + } +} + + + +/* Scan INSN and eliminate all eliminable hard registers in it. + + If REPLACE_P is true, do the replacement destructively. Also + delete the insn as dead it if it is setting an eliminable register. + + If REPLACE_P is false, just update the offsets while keeping the + base register the same. */ + +static void +eliminate_regs_in_insn (rtx insn, bool replace_p) +{ + int icode = recog_memoized (insn); + rtx old_set = single_set (insn); + bool validate_p; + int i; + rtx substed_operand[MAX_RECOG_OPERANDS]; + rtx orig_operand[MAX_RECOG_OPERANDS]; + struct elim_table *ep; + rtx plus_src, plus_cst_src; + lra_insn_recog_data_t id; + struct lra_static_insn_data *static_id; + + if (icode < 0 && asm_noperands (PATTERN (insn)) < 0 && ! DEBUG_INSN_P (insn)) + { + lra_assert (GET_CODE (PATTERN (insn)) == USE + || GET_CODE (PATTERN (insn)) == CLOBBER + || GET_CODE (PATTERN (insn)) == ADDR_VEC + || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC + || GET_CODE (PATTERN (insn)) == ASM_INPUT); + return; + } + + /* Check for setting an eliminable register. */ + if (old_set != 0 && REG_P (SET_DEST (old_set)) + && (ep = get_elimination (SET_DEST (old_set))) != NULL) + { + bool delete_p = replace_p; + +#ifdef HARD_FRAME_POINTER_REGNUM + /* If this is setting the frame pointer register to the hardware + frame pointer register and this is an elimination that will + be done (tested above), this insn is really adjusting the + frame pointer downward to compensate for the adjustment done + before a nonlocal goto. */ + if (ep->from == FRAME_POINTER_REGNUM + && ep->to == HARD_FRAME_POINTER_REGNUM) + { + if (replace_p) + { + SET_DEST (old_set) = ep->to_rtx; + lra_update_insn_recog_data (insn); + return; + } + else + { + rtx base = SET_SRC (old_set); + HOST_WIDE_INT offset = 0; + rtx base_insn = insn; + + while (base != ep->to_rtx) + { + rtx prev_insn, prev_set; + + if (GET_CODE (base) == PLUS && CONST_INT_P (XEXP (base, 1))) + { + offset += INTVAL (XEXP (base, 1)); + base = XEXP (base, 0); + } + else if ((prev_insn = prev_nonnote_insn (base_insn)) != 0 + && (prev_set = single_set (prev_insn)) != 0 + && rtx_equal_p (SET_DEST (prev_set), base)) + { + base = SET_SRC (prev_set); + base_insn = prev_insn; + } + else + break; + } + + if (base == ep->to_rtx) + { + rtx src; + + offset -= (ep->offset - ep->previous_offset); + src = plus_constant (Pmode, ep->to_rtx, offset); + + /* First see if this insn remains valid when we make + the change. If not, keep the INSN_CODE the same + and let the constraint pass fit it up. */ + validate_change (insn, &SET_SRC (old_set), src, 1); + validate_change (insn, &SET_DEST (old_set), + ep->from_rtx, 1); + if (! apply_change_group ()) + { + SET_SRC (old_set) = src; + SET_DEST (old_set) = ep->from_rtx; + } + lra_update_insn_recog_data (insn); + return; + } + } + + + /* We can't delete this insn, but needn't process it + since it won't be used unless something changes. */ + delete_p = false; + } +#endif + + /* This insn isn't serving a useful purpose. We delete it + when REPLACE is set. */ + if (delete_p) + lra_delete_dead_insn (insn); + return; + } + + /* We allow one special case which happens to work on all machines we + currently support: a single set with the source or a REG_EQUAL + note being a PLUS of an eliminable register and a constant. */ + plus_src = plus_cst_src = 0; + if (old_set && REG_P (SET_DEST (old_set))) + { + if (GET_CODE (SET_SRC (old_set)) == PLUS) + plus_src = SET_SRC (old_set); + /* First see if the source is of the form (plus (...) CST). */ + if (plus_src + && CONST_INT_P (XEXP (plus_src, 1))) + plus_cst_src = plus_src; + /* Check that the first operand of the PLUS is a hard reg or + the lowpart subreg of one. */ + if (plus_cst_src) + { + rtx reg = XEXP (plus_cst_src, 0); + + if (GET_CODE (reg) == SUBREG && subreg_lowpart_p (reg)) + reg = SUBREG_REG (reg); + + if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER) + plus_cst_src = 0; + } + } + if (plus_cst_src) + { + rtx reg = XEXP (plus_cst_src, 0); + HOST_WIDE_INT offset = INTVAL (XEXP (plus_cst_src, 1)); + + if (GET_CODE (reg) == SUBREG) + reg = SUBREG_REG (reg); + + if (REG_P (reg) && (ep = get_elimination (reg)) != NULL) + { + rtx to_rtx = replace_p ? ep->to_rtx : ep->from_rtx; + + if (! replace_p) + { + offset += (ep->offset - ep->previous_offset); + offset = trunc_int_for_mode (offset, GET_MODE (plus_cst_src)); + } + + if (GET_CODE (XEXP (plus_cst_src, 0)) == SUBREG) + to_rtx = gen_lowpart (GET_MODE (XEXP (plus_cst_src, 0)), to_rtx); + /* If we have a nonzero offset, and the source is already a + simple REG, the following transformation would increase + the cost of the insn by replacing a simple REG with (plus + (reg sp) CST). So try only when we already had a PLUS + before. */ + if (offset == 0 || plus_src) + { + rtx new_src = plus_constant (GET_MODE (to_rtx), to_rtx, offset); + + old_set = single_set (insn); + + /* First see if this insn remains valid when we make the + change. If not, try to replace the whole pattern + with a simple set (this may help if the original insn + was a PARALLEL that was only recognized as single_set + due to REG_UNUSED notes). If this isn't valid + either, keep the INSN_CODE the same and let the + constraint pass fix it up. */ + if (! validate_change (insn, &SET_SRC (old_set), new_src, 0)) + { + rtx new_pat = gen_rtx_SET (VOIDmode, + SET_DEST (old_set), new_src); + + if (! validate_change (insn, &PATTERN (insn), new_pat, 0)) + SET_SRC (old_set) = new_src; + } + lra_update_insn_recog_data (insn); + /* This can't have an effect on elimination offsets, so skip + right to the end. */ + return; + } + } + } + + /* Eliminate all eliminable registers occurring in operands that + can be handled by the constraint pass. */ + id = lra_get_insn_recog_data (insn); + static_id = id->insn_static_data; + validate_p = false; + for (i = 0; i < static_id->n_operands; i++) + { + orig_operand[i] = *id->operand_loc[i]; + substed_operand[i] = *id->operand_loc[i]; + + /* For an asm statement, every operand is eliminable. */ + if (icode < 0 || insn_data[icode].operand[i].eliminable) + { + /* Check for setting a hard register that we know about. */ + if (static_id->operand[i].type != OP_IN + && REG_P (orig_operand[i])) + { + /* If we are assigning to a hard register that can be + eliminated, it must be as part of a PARALLEL, since + the code above handles single SETs. This reg can not + be longer eliminated -- it is forced by + mark_not_eliminable. */ + for (ep = reg_eliminate; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; + ep++) + lra_assert (ep->from_rtx != orig_operand[i] + || ! ep->can_eliminate); + } + + /* Companion to the above plus substitution, we can allow + invariants as the source of a plain move. */ + substed_operand[i] + = lra_eliminate_regs_1 (*id->operand_loc[i], VOIDmode, + replace_p, ! replace_p, false); + if (substed_operand[i] != orig_operand[i]) + validate_p = true; + } + } + + /* Substitute the operands; the new values are in the substed_operand + array. */ + for (i = 0; i < static_id->n_operands; i++) + *id->operand_loc[i] = substed_operand[i]; + for (i = 0; i < static_id->n_dups; i++) + *id->dup_loc[i] = substed_operand[(int) static_id->dup_num[i]]; + + if (validate_p) + { + /* If we had a move insn but now we don't, re-recognize it. + This will cause spurious re-recognition if the old move had a + PARALLEL since the new one still will, but we can't call + single_set without having put new body into the insn and the + re-recognition won't hurt in this rare case. */ + id = lra_update_insn_recog_data (insn); + static_id = id->insn_static_data; + } +} + +/* Spill pseudos which are assigned to hard registers in SET. Add + affected insns for processing in the subsequent constraint + pass. */ +static void +spill_pseudos (HARD_REG_SET set) +{ + int i; + bitmap_head to_process; + rtx insn; + + if (hard_reg_set_empty_p (set)) + return; + if (lra_dump_file != NULL) + { + fprintf (lra_dump_file, " Spilling non-eliminable hard regs:"); + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (TEST_HARD_REG_BIT (set, i)) + fprintf (lra_dump_file, " %d", i); + fprintf (lra_dump_file, "\n"); + } + bitmap_initialize (&to_process, ®_obstack); + for (i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++) + if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0 + && overlaps_hard_reg_set_p (set, + PSEUDO_REGNO_MODE (i), reg_renumber[i])) + { + if (lra_dump_file != NULL) + fprintf (lra_dump_file, " Spilling r%d(%d)\n", + i, reg_renumber[i]); + reg_renumber[i] = -1; + bitmap_ior_into (&to_process, &lra_reg_info[i].insn_bitmap); + } + IOR_HARD_REG_SET (lra_no_alloc_regs, set); + for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn)) + if (bitmap_bit_p (&to_process, INSN_UID (insn))) + { + lra_push_insn (insn); + lra_set_used_insn_alternative (insn, -1); + } + bitmap_clear (&to_process); +} + +/* Update all offsets and possibility for elimination on eliminable + registers. Spill pseudos assigned to registers which became + uneliminable, update LRA_NO_ALLOC_REGS and ELIMINABLE_REG_SET. Add + insns to INSNS_WITH_CHANGED_OFFSETS containing eliminable hard + registers whose offsets should be changed. */ +static void +update_reg_eliminate (bitmap insns_with_changed_offsets) +{ + bool prev; + struct elim_table *ep, *ep1; + HARD_REG_SET temp_hard_reg_set; + + /* Clear self elimination offsets. */ + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + self_elim_offsets[ep->from] = 0; + CLEAR_HARD_REG_SET (temp_hard_reg_set); + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + { + /* If it is a currently used elimination: update the previous + offset. */ + if (elimination_map[ep->from] == ep) + ep->previous_offset = ep->offset; + + prev = ep->prev_can_eliminate; + setup_can_eliminate (ep, targetm.can_eliminate (ep->from, ep->to)); + if (ep->can_eliminate && ! prev) + { + /* It is possible that not eliminable register becomes + eliminable because we took other reasons into account to + set up eliminable regs in the initial set up. Just + ignore new eliminable registers. */ + setup_can_eliminate (ep, false); + continue; + } + if (ep->can_eliminate != prev && elimination_map[ep->from] == ep) + { + /* We cannot use this elimination anymore -- find another + one. */ + if (lra_dump_file != NULL) + fprintf (lra_dump_file, + " Elimination %d to %d is not possible anymore\n", + ep->from, ep->to); + /* Mark that is not eliminable anymore. */ + elimination_map[ep->from] = NULL; + for (ep1 = ep + 1; ep1 < ®_eliminate[NUM_ELIMINABLE_REGS]; ep1++) + if (ep1->can_eliminate && ep1->from == ep->from) + break; + if (ep1 < ®_eliminate[NUM_ELIMINABLE_REGS]) + { + if (lra_dump_file != NULL) + fprintf (lra_dump_file, " Using elimination %d to %d now\n", + ep1->from, ep1->to); + /* Prevent the hard register into which we eliminate now + from the usage for pseudos. */ + SET_HARD_REG_BIT (temp_hard_reg_set, ep1->to); + lra_assert (ep1->previous_offset == 0); + ep1->previous_offset = ep->offset; + } + else + { + /* There is no elimination anymore just use the hard + register `from' itself. Setup self elimination + offset to restore the original offset values. */ + if (lra_dump_file != NULL) + fprintf (lra_dump_file, " %d is not eliminable at all\n", + ep->from); + self_elim_offsets[ep->from] = -ep->offset; + SET_HARD_REG_BIT (temp_hard_reg_set, ep->from); + if (ep->offset != 0) + bitmap_ior_into (insns_with_changed_offsets, + &lra_reg_info[ep->from].insn_bitmap); + } + } + +#ifdef ELIMINABLE_REGS + INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, ep->offset); +#else + INITIAL_FRAME_POINTER_OFFSET (ep->offset); +#endif + } + IOR_HARD_REG_SET (lra_no_alloc_regs, temp_hard_reg_set); + AND_COMPL_HARD_REG_SET (eliminable_regset, temp_hard_reg_set); + spill_pseudos (temp_hard_reg_set); + setup_elimination_map (); + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + if (elimination_map[ep->from] == ep && ep->previous_offset != ep->offset) + bitmap_ior_into (insns_with_changed_offsets, + &lra_reg_info[ep->from].insn_bitmap); +} + +/* Initialize the table of hard registers to eliminate. + Pre-condition: global flag frame_pointer_needed has been set before + calling this function. */ +static void +init_elim_table (void) +{ + bool value_p; + struct elim_table *ep; +#ifdef ELIMINABLE_REGS + const struct elim_table_1 *ep1; +#endif + + if (!reg_eliminate) + reg_eliminate = XCNEWVEC (struct elim_table, NUM_ELIMINABLE_REGS); + + memset (self_elim_offsets, 0, sizeof (self_elim_offsets)); + /* Initiate member values which will be never changed. */ + self_elim_table.can_eliminate = self_elim_table.prev_can_eliminate = true; + self_elim_table.previous_offset = 0; +#ifdef ELIMINABLE_REGS + for (ep = reg_eliminate, ep1 = reg_eliminate_1; + ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++, ep1++) + { + ep->offset = ep->previous_offset = 0; + ep->from = ep1->from; + ep->to = ep1->to; + value_p = (targetm.can_eliminate (ep->from, ep->to) + && ! (ep->to == STACK_POINTER_REGNUM + && frame_pointer_needed + && (! SUPPORTS_STACK_ALIGNMENT + || ! stack_realign_fp))); + setup_can_eliminate (ep, value_p); + } +#else + reg_eliminate[0].offset = reg_eliminate[0].previous_offset = 0; + reg_eliminate[0].from = reg_eliminate_1[0].from; + reg_eliminate[0].to = reg_eliminate_1[0].to; + setup_can_eliminate (®_eliminate[0], ! frame_pointer_needed); +#endif + + /* Count the number of eliminable registers and build the FROM and TO + REG rtx's. Note that code in gen_rtx_REG will cause, e.g., + gen_rtx_REG (Pmode, STACK_POINTER_REGNUM) to equal stack_pointer_rtx. + We depend on this. */ + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + { + ep->from_rtx = gen_rtx_REG (Pmode, ep->from); + ep->to_rtx = gen_rtx_REG (Pmode, ep->to); + eliminable_reg_rtx[ep->from] = ep->from_rtx; + } +} + +/* Entry function for initialization of elimination once per + function. */ +void +lra_init_elimination (void) +{ + basic_block bb; + rtx insn; + + init_elim_table (); + FOR_EACH_BB (bb) + FOR_BB_INSNS (bb, insn) + if (NONDEBUG_INSN_P (insn)) + mark_not_eliminable (PATTERN (insn)); + setup_elimination_map (); +} + +/* Eliminate hard reg given by its location LOC. */ +void +lra_eliminate_reg_if_possible (rtx *loc) +{ + int regno; + struct elim_table *ep; + + lra_assert (REG_P (*loc)); + if ((regno = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER + || ! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)) + return; + if ((ep = get_elimination (*loc)) != NULL) + *loc = ep->to_rtx; +} + +/* Do (final if FINAL_P) elimination in INSN. Add the insn for + subsequent processing in the constraint pass, update the insn info. */ +static void +process_insn_for_elimination (rtx insn, bool final_p) +{ + eliminate_regs_in_insn (insn, final_p); + if (! final_p) + { + /* Check that insn changed its code. This is a case when a move + insn becomes an add insn and we do not want to process the + insn as a move anymore. */ + int icode = recog (PATTERN (insn), insn, 0); + + if (icode >= 0 && icode != INSN_CODE (insn)) + { + INSN_CODE (insn) = icode; + lra_update_insn_recog_data (insn); + } + lra_update_insn_regno_info (insn); + lra_push_insn (insn); + lra_set_used_insn_alternative (insn, -1); + } +} + +/* Entry function to do final elimination if FINAL_P or to update + elimination register offsets. */ +void +lra_eliminate (bool final_p) +{ + int i; + unsigned int uid; + rtx mem_loc, invariant; + bitmap_head insns_with_changed_offsets; + bitmap_iterator bi; + struct elim_table *ep; + int regs_num = max_reg_num (); + + timevar_push (TV_LRA_ELIMINATE); + + bitmap_initialize (&insns_with_changed_offsets, ®_obstack); + if (final_p) + { +#ifdef ENABLE_CHECKING + update_reg_eliminate (&insns_with_changed_offsets); + if (! bitmap_empty_p (&insns_with_changed_offsets)) + gcc_unreachable (); +#endif + /* We change eliminable hard registers in insns so we should do + this for all insns containing any eliminable hard + register. */ + for (ep = reg_eliminate; ep < ®_eliminate[NUM_ELIMINABLE_REGS]; ep++) + if (elimination_map[ep->from] != NULL) + bitmap_ior_into (&insns_with_changed_offsets, + &lra_reg_info[ep->from].insn_bitmap); + } + else + { + update_reg_eliminate (&insns_with_changed_offsets); + if (bitmap_empty_p (&insns_with_changed_offsets)) + goto lra_eliminate_done; + } + if (lra_dump_file != NULL) + { + fprintf (lra_dump_file, "New elimination table:\n"); + print_elim_table (lra_dump_file); + } + for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++) + if (lra_reg_info[i].nrefs != 0) + { + mem_loc = ira_reg_equiv[i].memory; + if (mem_loc != NULL_RTX) + mem_loc = lra_eliminate_regs_1 (mem_loc, VOIDmode, + final_p, ! final_p, false); + ira_reg_equiv[i].memory = mem_loc; + invariant = ira_reg_equiv[i].invariant; + if (invariant != NULL_RTX) + invariant = lra_eliminate_regs_1 (invariant, VOIDmode, + final_p, ! final_p, false); + ira_reg_equiv[i].invariant = invariant; + if (lra_dump_file != NULL + && (mem_loc != NULL_RTX || invariant != NULL)) + fprintf (lra_dump_file, + "Updating elimination of equiv for reg %d\n", i); + } + EXECUTE_IF_SET_IN_BITMAP (&insns_with_changed_offsets, 0, uid, bi) + process_insn_for_elimination (lra_insn_recog_data[uid]->insn, final_p); + bitmap_clear (&insns_with_changed_offsets); + +lra_eliminate_done: + timevar_pop (TV_LRA_ELIMINATE); +} |