diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/struct-equiv.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/struct-equiv.c | 1347 |
1 files changed, 1347 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/struct-equiv.c b/gcc-4.2.1-5666.3/gcc/struct-equiv.c new file mode 100644 index 000000000..e580b889f --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/struct-equiv.c @@ -0,0 +1,1347 @@ +/* Control flow optimization code for GNU compiler. + Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, + 1999, 2000, 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* Try to match two basic blocks - or their ends - for structural equivalence. + We scan the blocks from their ends backwards, and expect that insns are + identical, except for certain cases involving registers. A mismatch + We scan the blocks from their ends backwards, hoping to find a match, I.e. + insns are identical, except for certain cases involving registers. A + mismatch between register number RX (used in block X) and RY (used in the + same way in block Y) can be handled in one of the following cases: + 1. RX and RY are local to their respective blocks; they are set there and + die there. If so, they can effectively be ignored. + 2. RX and RY die in their blocks, but live at the start. If any path + gets redirected through X instead of Y, the caller must emit + compensation code to move RY to RX. If there are overlapping inputs, + the function resolve_input_conflict ensures that this can be done. + Information about these registers are tracked in the X_LOCAL, Y_LOCAL, + LOCAL_COUNT and LOCAL_RVALUE fields. + 3. RX and RY live throughout their blocks, including the start and the end. + Either RX and RY must be identical, or we have to replace all uses in + block X with a new pseudo, which is stored in the INPUT_REG field. The + caller can then use block X instead of block Y by copying RY to the new + pseudo. + + The main entry point to this file is struct_equiv_block_eq. This function + uses a struct equiv_info to accept some of its inputs, to keep track of its + internal state, to pass down to its helper functions, and to communicate + some of the results back to the caller. + + Most scans will result in a failure to match a sufficient number of insns + to make any optimization worth while, therefore the process is geared more + to quick scanning rather than the ability to exactly backtrack when we + find a mismatch. The information gathered is still meaningful to make a + preliminary decision if we want to do an optimization, we might only + slightly overestimate the number of matchable insns, and underestimate + the number of inputs an miss an input conflict. Sufficient information + is gathered so that when we make another pass, we won't have to backtrack + at the same point. + Another issue is that information in memory attributes and/or REG_NOTES + might have to be merged or discarded to make a valid match. We don't want + to discard such information when we are not certain that we want to merge + the two (partial) blocks. + For these reasons, struct_equiv_block_eq has to be called first with the + STRUCT_EQUIV_START bit set in the mode parameter. This will calculate the + number of matched insns and the number and types of inputs. If the + need_rerun field is set, the results are only tentative, and the caller + has to call again with STRUCT_EQUIV_RERUN till need_rerun is false in + order to get a reliable match. + To install the changes necessary for the match, the function has to be + called again with STRUCT_EQUIV_FINAL. + + While scanning an insn, we process first all the SET_DESTs, then the + SET_SRCes, then the REG_NOTES, in order to keep the register liveness + information consistent. + If we were to mix up the order for sources / destinations in an insn where + a source is also a destination, we'd end up being mistaken to think that + the register is not live in the preceding insn. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "rtl.h" +#include "regs.h" +#include "output.h" +#include "insn-config.h" +#include "flags.h" +#include "recog.h" +#include "tm_p.h" +#include "target.h" +#include "emit-rtl.h" +#include "reload.h" + +static void merge_memattrs (rtx, rtx); +static bool set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info); +static bool set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info); +static void find_dying_inputs (struct equiv_info *info); +static bool resolve_input_conflict (struct equiv_info *info); + +/* After reload, some moves, as indicated by SECONDARY_RELOAD_CLASS and + SECONDARY_MEMORY_NEEDED, cannot be done directly. For our purposes, we + consider them impossible to generate after reload (even though some + might be synthesized when you throw enough code at them). + Since we don't know while processing a cross-jump if a local register + that is currently live will eventually be live and thus be an input, + we keep track of potential inputs that would require an impossible move + by using a prohibitively high cost for them. + This number, multiplied with the larger of STRUCT_EQUIV_MAX_LOCAL and + FIRST_PSEUDO_REGISTER, must fit in the input_cost field of + struct equiv_info. */ +#define IMPOSSIBLE_MOVE_FACTOR 20000 + + + +/* Removes the memory attributes of MEM expression + if they are not equal. */ + +void +merge_memattrs (rtx x, rtx y) +{ + int i; + int j; + enum rtx_code code; + const char *fmt; + + if (x == y) + return; + if (x == 0 || y == 0) + return; + + code = GET_CODE (x); + + if (code != GET_CODE (y)) + return; + + if (GET_MODE (x) != GET_MODE (y)) + return; + + if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y)) + { + if (! MEM_ATTRS (x)) + MEM_ATTRS (y) = 0; + else if (! MEM_ATTRS (y)) + MEM_ATTRS (x) = 0; + else + { + rtx mem_size; + + if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) + { + set_mem_alias_set (x, 0); + set_mem_alias_set (y, 0); + } + + if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y))) + { + set_mem_expr (x, 0); + set_mem_expr (y, 0); + set_mem_offset (x, 0); + set_mem_offset (y, 0); + } + else if (MEM_OFFSET (x) != MEM_OFFSET (y)) + { + set_mem_offset (x, 0); + set_mem_offset (y, 0); + } + + if (!MEM_SIZE (x)) + mem_size = NULL_RTX; + else if (!MEM_SIZE (y)) + mem_size = NULL_RTX; + else + mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)), + INTVAL (MEM_SIZE (y)))); + set_mem_size (x, mem_size); + set_mem_size (y, mem_size); + + set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y))); + set_mem_align (y, MEM_ALIGN (x)); + } + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + switch (fmt[i]) + { + case 'E': + /* Two vectors must have the same length. */ + if (XVECLEN (x, i) != XVECLEN (y, i)) + return; + + for (j = 0; j < XVECLEN (x, i); j++) + merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j)); + + break; + + case 'e': + merge_memattrs (XEXP (x, i), XEXP (y, i)); + } + } + return; +} + +/* In SET, assign the bit for the register number of REG the value VALUE. + If REG is a hard register, do so for all its constituent registers. + Return the number of registers that have become included (as a positive + number) or excluded (as a negative number). */ +static int +assign_reg_reg_set (regset set, rtx reg, int value) +{ + unsigned regno = REGNO (reg); + int nregs, i, old; + + if (regno >= FIRST_PSEUDO_REGISTER) + { + gcc_assert (!reload_completed); + nregs = 1; + } + else + nregs = hard_regno_nregs[regno][GET_MODE (reg)]; + for (old = 0, i = nregs; --i >= 0; regno++) + { + if ((value != 0) == REGNO_REG_SET_P (set, regno)) + continue; + if (value) + old++, SET_REGNO_REG_SET (set, regno); + else + old--, CLEAR_REGNO_REG_SET (set, regno); + } + return old; +} + +/* Record state about current inputs / local registers / liveness + in *P. */ +static inline void +struct_equiv_make_checkpoint (struct struct_equiv_checkpoint *p, + struct equiv_info *info) +{ + *p = info->cur; +} + +/* Call struct_equiv_make_checkpoint (P, INFO) if the current partial block + is suitable to split off - i.e. there is no dangling cc0 user - and + if the current cost of the common instructions, minus the cost for + setting up the inputs, is higher than what has been recorded before + in CHECKPOINT[N]. Also, if we do so, confirm or cancel any pending + changes. */ +static void +struct_equiv_improve_checkpoint (struct struct_equiv_checkpoint *p, + struct equiv_info *info) +{ +#ifdef HAVE_cc0 + if (reg_mentioned_p (cc0_rtx, info->cur.x_start) + && !sets_cc0_p (info->cur.x_start)) + return; +#endif + if (info->cur.input_count >= IMPOSSIBLE_MOVE_FACTOR) + return; + if (info->input_cost >= 0 + ? (COSTS_N_INSNS(info->cur.ninsns - p->ninsns) + > info->input_cost * (info->cur.input_count - p->input_count)) + : info->cur.ninsns > p->ninsns && !info->cur.input_count) + { + if (info->check_input_conflict && ! resolve_input_conflict (info)) + return; + /* We have a profitable set of changes. If this is the final pass, + commit them now. Otherwise, we don't know yet if we can make any + change, so put the old code back for now. */ + if (info->mode & STRUCT_EQUIV_FINAL) + confirm_change_group (); + else + cancel_changes (0); + struct_equiv_make_checkpoint (p, info); + } +} + +/* Restore state about current inputs / local registers / liveness + from P. */ +static void +struct_equiv_restore_checkpoint (struct struct_equiv_checkpoint *p, + struct equiv_info *info) +{ + info->cur.ninsns = p->ninsns; + info->cur.x_start = p->x_start; + info->cur.y_start = p->y_start; + info->cur.input_count = p->input_count; + info->cur.input_valid = p->input_valid; + while (info->cur.local_count > p->local_count) + { + info->cur.local_count--; + info->cur.version--; + if (REGNO_REG_SET_P (info->x_local_live, + REGNO (info->x_local[info->cur.local_count]))) + { + assign_reg_reg_set (info->x_local_live, + info->x_local[info->cur.local_count], 0); + assign_reg_reg_set (info->y_local_live, + info->y_local[info->cur.local_count], 0); + info->cur.version--; + } + } + if (info->cur.version != p->version) + info->need_rerun = true; +} + + +/* Update register liveness to reflect that X is now life (if rvalue is + nonzero) or dead (if rvalue is zero) in INFO->x_block, and likewise Y + in INFO->y_block. Return the number of registers the liveness of which + changed in each block (as a negative number if registers became dead). */ +static int +note_local_live (struct equiv_info *info, rtx x, rtx y, int rvalue) +{ + unsigned x_regno = REGNO (x); + unsigned y_regno = REGNO (y); + int x_nominal_nregs = (x_regno >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]); + int y_nominal_nregs = (y_regno >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]); + int x_change = assign_reg_reg_set (info->x_local_live, x, rvalue); + int y_change = assign_reg_reg_set (info->y_local_live, y, rvalue); + + gcc_assert (x_nominal_nregs && y_nominal_nregs); + gcc_assert (x_change * y_nominal_nregs == y_change * x_nominal_nregs); + if (y_change) + { + if (reload_completed) + { + unsigned x_regno ATTRIBUTE_UNUSED = REGNO (x); + unsigned y_regno = REGNO (y); + enum machine_mode x_mode = GET_MODE (x); + + if (secondary_reload_class (0, REGNO_REG_CLASS (y_regno), x_mode, x) + != NO_REGS +#ifdef SECONDARY_MEMORY_NEEDED + || SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (y_regno), + REGNO_REG_CLASS (x_regno), x_mode) +#endif + ) + y_change *= IMPOSSIBLE_MOVE_FACTOR; + } + info->cur.input_count += y_change; + info->cur.version++; + } + return x_change; +} + +/* Check if *XP is equivalent to Y. Until an an unreconcilable difference is + found, use in-group changes with validate_change on *XP to make register + assignments agree. It is the (not necessarily direct) callers + responsibility to verify / confirm / cancel these changes, as appropriate. + RVALUE indicates if the processed piece of rtl is used as a destination, in + which case we can't have different registers being an input. Returns + nonzero if the two blocks have been identified as equivalent, zero otherwise. + RVALUE == 0: destination + RVALUE == 1: source + RVALUE == -1: source, ignore SET_DEST of SET / clobber. */ +bool +rtx_equiv_p (rtx *xp, rtx y, int rvalue, struct equiv_info *info) +{ + rtx x = *xp; + enum rtx_code code; + int length; + const char *format; + int i; + + if (!y || !x) + return x == y; + code = GET_CODE (y); + if (code != REG && x == y) + return true; + if (GET_CODE (x) != code + || GET_MODE (x) != GET_MODE (y)) + return false; + + /* ??? could extend to allow CONST_INT inputs. */ + switch (code) + { + case REG: + { + unsigned x_regno = REGNO (x); + unsigned y_regno = REGNO (y); + int x_common_live, y_common_live; + + if (reload_completed + && (x_regno >= FIRST_PSEUDO_REGISTER + || y_regno >= FIRST_PSEUDO_REGISTER)) + { + /* We should only see this in REG_NOTEs. */ + gcc_assert (!info->live_update); + /* Returning false will cause us to remove the notes. */ + return false; + } +#ifdef STACK_REGS + /* After reg-stack, can only accept literal matches of stack regs. */ + if (info->mode & CLEANUP_POST_REGSTACK + && (IN_RANGE (x_regno, FIRST_STACK_REG, LAST_STACK_REG) + || IN_RANGE (y_regno, FIRST_STACK_REG, LAST_STACK_REG))) + return x_regno == y_regno; +#endif + + /* If the register is a locally live one in one block, the + corresponding one must be locally live in the other, too, and + match of identical regnos doesn't apply. */ + if (REGNO_REG_SET_P (info->x_local_live, x_regno)) + { + if (!REGNO_REG_SET_P (info->y_local_live, y_regno)) + return false; + } + else if (REGNO_REG_SET_P (info->y_local_live, y_regno)) + return false; + else if (x_regno == y_regno) + { + if (!rvalue && info->cur.input_valid + && (reg_overlap_mentioned_p (x, info->x_input) + || reg_overlap_mentioned_p (x, info->y_input))) + return false; + + /* Update liveness information. */ + if (info->live_update + && assign_reg_reg_set (info->common_live, x, rvalue)) + info->cur.version++; + + return true; + } + + x_common_live = REGNO_REG_SET_P (info->common_live, x_regno); + y_common_live = REGNO_REG_SET_P (info->common_live, y_regno); + if (x_common_live != y_common_live) + return false; + else if (x_common_live) + { + if (! rvalue || info->input_cost < 0 || no_new_pseudos) + return false; + /* If info->live_update is not set, we are processing notes. + We then allow a match with x_input / y_input found in a + previous pass. */ + if (info->live_update && !info->cur.input_valid) + { + info->cur.input_valid = true; + info->x_input = x; + info->y_input = y; + info->cur.input_count += optimize_size ? 2 : 1; + if (info->input_reg + && GET_MODE (info->input_reg) != GET_MODE (info->x_input)) + info->input_reg = NULL_RTX; + if (!info->input_reg) + info->input_reg = gen_reg_rtx (GET_MODE (info->x_input)); + } + else if ((info->live_update + ? ! info->cur.input_valid : ! info->x_input) + || ! rtx_equal_p (x, info->x_input) + || ! rtx_equal_p (y, info->y_input)) + return false; + validate_change (info->cur.x_start, xp, info->input_reg, 1); + } + else + { + int x_nregs = (x_regno >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[x_regno][GET_MODE (x)]); + int y_nregs = (y_regno >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[y_regno][GET_MODE (y)]); + int size = GET_MODE_SIZE (GET_MODE (x)); + enum machine_mode x_mode = GET_MODE (x); + unsigned x_regno_i, y_regno_i; + int x_nregs_i, y_nregs_i, size_i; + int local_count = info->cur.local_count; + + /* This might be a register local to each block. See if we have + it already registered. */ + for (i = local_count - 1; i >= 0; i--) + { + x_regno_i = REGNO (info->x_local[i]); + x_nregs_i = (x_regno_i >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[x_regno_i][GET_MODE (x)]); + y_regno_i = REGNO (info->y_local[i]); + y_nregs_i = (y_regno_i >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[y_regno_i][GET_MODE (y)]); + size_i = GET_MODE_SIZE (GET_MODE (info->x_local[i])); + + /* If we have a new pair of registers that is wider than an + old pair and enclosing it with matching offsets, + remove the old pair. If we find a matching, wider, old + pair, use the old one. If the width is the same, use the + old one if the modes match, but the new if they don't. + We don't want to get too fancy with subreg_regno_offset + here, so we just test two straightforward cases each. */ + if (info->live_update + && (x_mode != GET_MODE (info->x_local[i]) + ? size >= size_i : size > size_i)) + { + /* If the new pair is fully enclosing a matching + existing pair, remove the old one. N.B. because + we are removing one entry here, the check below + if we have space for a new entry will succeed. */ + if ((x_regno <= x_regno_i + && x_regno + x_nregs >= x_regno_i + x_nregs_i + && x_nregs == y_nregs && x_nregs_i == y_nregs_i + && x_regno - x_regno_i == y_regno - y_regno_i) + || (x_regno == x_regno_i && y_regno == y_regno_i + && x_nregs >= x_nregs_i && y_nregs >= y_nregs_i)) + { + info->cur.local_count = --local_count; + info->x_local[i] = info->x_local[local_count]; + info->y_local[i] = info->y_local[local_count]; + continue; + } + } + else + { + + /* If the new pair is fully enclosed within a matching + existing pair, succeed. */ + if (x_regno >= x_regno_i + && x_regno + x_nregs <= x_regno_i + x_nregs_i + && x_nregs == y_nregs && x_nregs_i == y_nregs_i + && x_regno - x_regno_i == y_regno - y_regno_i) + break; + if (x_regno == x_regno_i && y_regno == y_regno_i + && x_nregs <= x_nregs_i && y_nregs <= y_nregs_i) + break; + } + + /* Any other overlap causes a match failure. */ + if (x_regno + x_nregs > x_regno_i + && x_regno_i + x_nregs_i > x_regno) + return false; + if (y_regno + y_nregs > y_regno_i + && y_regno_i + y_nregs_i > y_regno) + return false; + } + if (i < 0) + { + /* Not found. Create a new entry if possible. */ + if (!info->live_update + || info->cur.local_count >= STRUCT_EQUIV_MAX_LOCAL) + return false; + info->x_local[info->cur.local_count] = x; + info->y_local[info->cur.local_count] = y; + info->cur.local_count++; + info->cur.version++; + } + note_local_live (info, x, y, rvalue); + } + return true; + } + case SET: + gcc_assert (rvalue < 0); + /* Ignore the destinations role as a destination. Still, we have + to consider input registers embedded in the addresses of a MEM. + N.B., we process the rvalue aspect of STRICT_LOW_PART / + ZERO_EXTEND / SIGN_EXTEND along with their lvalue aspect. */ + if(!set_dest_addr_equiv_p (SET_DEST (x), SET_DEST (y), info)) + return false; + /* Process source. */ + return rtx_equiv_p (&SET_SRC (x), SET_SRC (y), 1, info); + case PRE_MODIFY: + /* Process destination. */ + if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)) + return false; + /* Process source. */ + return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info); + case POST_MODIFY: + { + rtx x_dest0, x_dest1; + + /* Process destination. */ + x_dest0 = XEXP (x, 0); + gcc_assert (REG_P (x_dest0)); + if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info)) + return false; + x_dest1 = XEXP (x, 0); + /* validate_change might have changed the destination. Put it back + so that we can do a proper match for its role a an input. */ + XEXP (x, 0) = x_dest0; + if (!rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info)) + return false; + gcc_assert (x_dest1 == XEXP (x, 0)); + /* Process source. */ + return rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), 1, info); + } + case CLOBBER: + gcc_assert (rvalue < 0); + return true; + /* Some special forms are also rvalues when they appear in lvalue + positions. However, we must ont try to match a register after we + have already altered it with validate_change, consider the rvalue + aspect while we process the lvalue. */ + case STRICT_LOW_PART: + case ZERO_EXTEND: + case SIGN_EXTEND: + { + rtx x_inner, y_inner; + enum rtx_code code; + int change; + + if (rvalue) + break; + x_inner = XEXP (x, 0); + y_inner = XEXP (y, 0); + if (GET_MODE (x_inner) != GET_MODE (y_inner)) + return false; + code = GET_CODE (x_inner); + if (code != GET_CODE (y_inner)) + return false; + /* The address of a MEM is an input that will be processed during + rvalue == -1 processing. */ + if (code == SUBREG) + { + if (SUBREG_BYTE (x_inner) != SUBREG_BYTE (y_inner)) + return false; + x = x_inner; + x_inner = SUBREG_REG (x_inner); + y_inner = SUBREG_REG (y_inner); + if (GET_MODE (x_inner) != GET_MODE (y_inner)) + return false; + code = GET_CODE (x_inner); + if (code != GET_CODE (y_inner)) + return false; + } + if (code == MEM) + return true; + gcc_assert (code == REG); + if (! rtx_equiv_p (&XEXP (x, 0), y_inner, rvalue, info)) + return false; + if (REGNO (x_inner) == REGNO (y_inner)) + { + change = assign_reg_reg_set (info->common_live, x_inner, 1); + info->cur.version++; + } + else + change = note_local_live (info, x_inner, y_inner, 1); + gcc_assert (change); + return true; + } + /* The AUTO_INC / POST_MODIFY / PRE_MODIFY sets are modelled to take + place during input processing, however, that is benign, since they + are paired with reads. */ + case MEM: + return !rvalue || rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info); + case POST_INC: case POST_DEC: case PRE_INC: case PRE_DEC: + return (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info) + && rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info)); + case PARALLEL: + /* If this is a top-level PATTERN PARALLEL, we expect the caller to + have handled the SET_DESTs. A complex or vector PARALLEL can be + identified by having a mode. */ + gcc_assert (rvalue < 0 || GET_MODE (x) != VOIDmode); + break; + case LABEL_REF: + /* Check special tablejump match case. */ + if (XEXP (y, 0) == info->y_label) + return (XEXP (x, 0) == info->x_label); + /* We can't assume nonlocal labels have their following insns yet. */ + if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y)) + return XEXP (x, 0) == XEXP (y, 0); + + /* Two label-refs are equivalent if they point at labels + in the same position in the instruction stream. */ + return (next_real_insn (XEXP (x, 0)) + == next_real_insn (XEXP (y, 0))); + case SYMBOL_REF: + return XSTR (x, 0) == XSTR (y, 0); + /* Some rtl is guaranteed to be shared, or unique; If we didn't match + EQ equality above, they aren't the same. */ + case CONST_INT: + case CODE_LABEL: + return false; + default: + break; + } + + /* For commutative operations, the RTX match if the operands match in any + order. */ + if (targetm.commutative_p (x, UNKNOWN)) + return ((rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), rvalue, info) + && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 1), rvalue, info)) + || (rtx_equiv_p (&XEXP (x, 0), XEXP (y, 1), rvalue, info) + && rtx_equiv_p (&XEXP (x, 1), XEXP (y, 0), rvalue, info))); + + /* Process subexpressions - this is similar to rtx_equal_p. */ + length = GET_RTX_LENGTH (code); + format = GET_RTX_FORMAT (code); + + for (i = 0; i < length; ++i) + { + switch (format[i]) + { + case 'w': + if (XWINT (x, i) != XWINT (y, i)) + return false; + break; + case 'n': + case 'i': + if (XINT (x, i) != XINT (y, i)) + return false; + break; + case 'V': + case 'E': + if (XVECLEN (x, i) != XVECLEN (y, i)) + return false; + if (XVEC (x, i) != 0) + { + int j; + for (j = 0; j < XVECLEN (x, i); ++j) + { + if (! rtx_equiv_p (&XVECEXP (x, i, j), XVECEXP (y, i, j), + rvalue, info)) + return false; + } + } + break; + case 'e': + if (! rtx_equiv_p (&XEXP (x, i), XEXP (y, i), rvalue, info)) + return false; + break; + case 'S': + case 's': + if ((XSTR (x, i) || XSTR (y, i)) + && (! XSTR (x, i) || ! XSTR (y, i) + || strcmp (XSTR (x, i), XSTR (y, i)))) + return false; + break; + case 'u': + /* These are just backpointers, so they don't matter. */ + break; + case '0': + case 't': + break; + /* It is believed that rtx's at this level will never + contain anything but integers and other rtx's, + except for within LABEL_REFs and SYMBOL_REFs. */ + default: + gcc_unreachable (); + } + } + return true; +} + +/* Do only the rtx_equiv_p SET_DEST processing for SETs and CLOBBERs. + Since we are scanning backwards, this the first step in processing each + insn. Return true for success. */ +static bool +set_dest_equiv_p (rtx x, rtx y, struct equiv_info *info) +{ + if (!x || !y) + return x == y; + if (GET_CODE (x) != GET_CODE (y)) + return false; + else if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER) + return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 0, info); + else if (GET_CODE (x) == PARALLEL) + { + int j; + + if (XVECLEN (x, 0) != XVECLEN (y, 0)) + return false; + for (j = 0; j < XVECLEN (x, 0); ++j) + { + rtx xe = XVECEXP (x, 0, j); + rtx ye = XVECEXP (y, 0, j); + + if (GET_CODE (xe) != GET_CODE (ye)) + return false; + if ((GET_CODE (xe) == SET || GET_CODE (xe) == CLOBBER) + && ! rtx_equiv_p (&XEXP (xe, 0), XEXP (ye, 0), 0, info)) + return false; + } + } + return true; +} + +/* Process MEMs in SET_DEST destinations. We must not process this together + with REG SET_DESTs, but must do it separately, lest when we see + [(set (reg:SI foo) (bar)) + (set (mem:SI (reg:SI foo) (baz)))] + struct_equiv_block_eq could get confused to assume that (reg:SI foo) + is not live before this instruction. */ +static bool +set_dest_addr_equiv_p (rtx x, rtx y, struct equiv_info *info) +{ + enum rtx_code code = GET_CODE (x); + int length; + const char *format; + int i; + + if (code != GET_CODE (y)) + return false; + if (code == MEM) + return rtx_equiv_p (&XEXP (x, 0), XEXP (y, 0), 1, info); + + /* Process subexpressions. */ + length = GET_RTX_LENGTH (code); + format = GET_RTX_FORMAT (code); + + for (i = 0; i < length; ++i) + { + switch (format[i]) + { + case 'V': + case 'E': + if (XVECLEN (x, i) != XVECLEN (y, i)) + return false; + if (XVEC (x, i) != 0) + { + int j; + for (j = 0; j < XVECLEN (x, i); ++j) + { + if (! set_dest_addr_equiv_p (XVECEXP (x, i, j), + XVECEXP (y, i, j), info)) + return false; + } + } + break; + case 'e': + if (! set_dest_addr_equiv_p (XEXP (x, i), XEXP (y, i), info)) + return false; + break; + default: + break; + } + } + return true; +} + +/* Check if the set of REG_DEAD notes attached to I1 and I2 allows us to + go ahead with merging I1 and I2, which otherwise look fine. + Inputs / local registers for the inputs of I1 and I2 have already been + set up. */ +static bool +death_notes_match_p (rtx i1 ATTRIBUTE_UNUSED, rtx i2 ATTRIBUTE_UNUSED, + struct equiv_info *info ATTRIBUTE_UNUSED) +{ +#ifdef STACK_REGS + /* If cross_jump_death_matters is not 0, the insn's mode + indicates whether or not the insn contains any stack-like regs. */ + + if ((info->mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1)) + { + /* If register stack conversion has already been done, then + death notes must also be compared before it is certain that + the two instruction streams match. */ + + rtx note; + HARD_REG_SET i1_regset, i2_regset; + + CLEAR_HARD_REG_SET (i1_regset); + CLEAR_HARD_REG_SET (i2_regset); + + for (note = REG_NOTES (i1); note; note = XEXP (note, 1)) + if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) + SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0))); + + for (note = REG_NOTES (i2); note; note = XEXP (note, 1)) + if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) + { + unsigned regno = REGNO (XEXP (note, 0)); + int i; + + for (i = info->cur.local_count - 1; i >= 0; i--) + if (regno == REGNO (info->y_local[i])) + { + regno = REGNO (info->x_local[i]); + break; + } + SET_HARD_REG_BIT (i2_regset, regno); + } + + GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done); + + return false; + + done: + ; + } +#endif + return true; +} + +/* Return true if I1 and I2 are equivalent and thus can be crossjumped. */ + +bool +insns_match_p (rtx i1, rtx i2, struct equiv_info *info) +{ + int rvalue_change_start; + struct struct_equiv_checkpoint before_rvalue_change; + + /* Verify that I1 and I2 are equivalent. */ + if (GET_CODE (i1) != GET_CODE (i2)) + return false; + + info->cur.x_start = i1; + info->cur.y_start = i2; + + /* If this is a CALL_INSN, compare register usage information. + If we don't check this on stack register machines, the two + CALL_INSNs might be merged leaving reg-stack.c with mismatching + numbers of stack registers in the same basic block. + If we don't check this on machines with delay slots, a delay slot may + be filled that clobbers a parameter expected by the subroutine. + + ??? We take the simple route for now and assume that if they're + equal, they were constructed identically. */ + + if (CALL_P (i1)) + { + if (SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2) + || ! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info) + || ! set_dest_equiv_p (CALL_INSN_FUNCTION_USAGE (i1), + CALL_INSN_FUNCTION_USAGE (i2), info) + || ! rtx_equiv_p (&CALL_INSN_FUNCTION_USAGE (i1), + CALL_INSN_FUNCTION_USAGE (i2), -1, info)) + { + cancel_changes (0); + return false; + } + } + else if (INSN_P (i1)) + { + if (! set_dest_equiv_p (PATTERN (i1), PATTERN (i2), info)) + { + cancel_changes (0); + return false; + } + } + rvalue_change_start = num_validated_changes (); + struct_equiv_make_checkpoint (&before_rvalue_change, info); + /* Check death_notes_match_p *after* the inputs have been processed, + so that local inputs will already have been set up. */ + if (! INSN_P (i1) + || (!bitmap_bit_p (info->equiv_used, info->cur.ninsns) + && rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info) + && death_notes_match_p (i1, i2, info) + && verify_changes (0))) + return true; + + /* Do not do EQUIV substitution after reload. First, we're undoing the + work of reload_cse. Second, we may be undoing the work of the post- + reload splitting pass. */ + /* ??? Possibly add a new phase switch variable that can be used by + targets to disallow the troublesome insns after splitting. */ + if (!reload_completed) + { + rtx equiv1, equiv2; + + cancel_changes (rvalue_change_start); + struct_equiv_restore_checkpoint (&before_rvalue_change, info); + + /* The following code helps take care of G++ cleanups. */ + equiv1 = find_reg_equal_equiv_note (i1); + equiv2 = find_reg_equal_equiv_note (i2); + if (equiv1 && equiv2 + /* If the equivalences are not to a constant, they may + reference pseudos that no longer exist, so we can't + use them. */ + && (! reload_completed + || (CONSTANT_P (XEXP (equiv1, 0)) + && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0))))) + { + rtx s1 = single_set (i1); + rtx s2 = single_set (i2); + + if (s1 != 0 && s2 != 0) + { + validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1); + validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1); + /* Only inspecting the new SET_SRC is not good enough, + because there may also be bare USEs in a single_set + PARALLEL. */ + if (rtx_equiv_p (&PATTERN (i1), PATTERN (i2), -1, info) + && death_notes_match_p (i1, i2, info) + && verify_changes (0)) + { + /* Mark this insn so that we'll use the equivalence in + all subsequent passes. */ + bitmap_set_bit (info->equiv_used, info->cur.ninsns); + return true; + } + } + } + } + + cancel_changes (0); + return false; +} + +/* Set up mode and register information in INFO. Return true for success. */ +bool +struct_equiv_init (int mode, struct equiv_info *info) +{ + if ((info->x_block->flags | info->y_block->flags) & BB_DIRTY) + update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES, + (PROP_DEATH_NOTES + | ((mode & CLEANUP_POST_REGSTACK) + ? PROP_POST_REGSTACK : 0))); + if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end, + info->y_block->il.rtl->global_live_at_end)) + { +#ifdef STACK_REGS + unsigned rn; + + if (!(mode & CLEANUP_POST_REGSTACK)) + return false; + /* After reg-stack. Remove bogus live info about stack regs. N.B. + these regs are not necessarily all dead - we swap random bogosity + against constant bogosity. However, clearing these bits at + least makes the regsets comparable. */ + for (rn = FIRST_STACK_REG; rn <= LAST_STACK_REG; rn++) + { + CLEAR_REGNO_REG_SET (info->x_block->il.rtl->global_live_at_end, rn); + CLEAR_REGNO_REG_SET (info->y_block->il.rtl->global_live_at_end, rn); + } + if (!REG_SET_EQUAL_P (info->x_block->il.rtl->global_live_at_end, + info->y_block->il.rtl->global_live_at_end)) +#endif + return false; + } + info->mode = mode; + if (mode & STRUCT_EQUIV_START) + { + info->x_input = info->y_input = info->input_reg = NULL_RTX; + info->equiv_used = ALLOC_REG_SET (®_obstack); + info->check_input_conflict = false; + } + info->had_input_conflict = false; + info->cur.ninsns = info->cur.version = 0; + info->cur.local_count = info->cur.input_count = 0; + info->cur.x_start = info->cur.y_start = NULL_RTX; + info->x_label = info->y_label = NULL_RTX; + info->need_rerun = false; + info->live_update = true; + info->cur.input_valid = false; + info->common_live = ALLOC_REG_SET (®_obstack); + info->x_local_live = ALLOC_REG_SET (®_obstack); + info->y_local_live = ALLOC_REG_SET (®_obstack); + COPY_REG_SET (info->common_live, info->x_block->il.rtl->global_live_at_end); + struct_equiv_make_checkpoint (&info->best_match, info); + return true; +} + +/* Insns XI and YI have been matched. Merge memory attributes and reg + notes. */ +static void +struct_equiv_merge (rtx xi, rtx yi, struct equiv_info *info) +{ + rtx equiv1, equiv2; + + merge_memattrs (xi, yi); + + /* If the merged insns have different REG_EQUAL notes, then + remove them. */ + info->live_update = false; + equiv1 = find_reg_equal_equiv_note (xi); + equiv2 = find_reg_equal_equiv_note (yi); + if (equiv1 && !equiv2) + remove_note (xi, equiv1); + else if (!equiv1 && equiv2) + remove_note (yi, equiv2); + else if (equiv1 && equiv2 + && !rtx_equiv_p (&XEXP (equiv1, 0), XEXP (equiv2, 0), + 1, info)) + { + remove_note (xi, equiv1); + remove_note (yi, equiv2); + } + info->live_update = true; +} + +/* Return number of matched insns. + This function must be called up to three times for a successful cross-jump + match: + first to find out which instructions do match. While trying to match + another instruction that doesn't match, we destroy information in info + about the actual inputs. So if there have been any before the last + match attempt, we need to call this function again to recompute the + actual inputs up to the actual start of the matching sequence. + When we are then satisfied that the cross-jump is worthwhile, we + call this function a third time to make any changes needed to make the + sequences match: apply equivalences, remove non-matching + notes and merge memory attributes. */ +int +struct_equiv_block_eq (int mode, struct equiv_info *info) +{ + rtx x_stop, y_stop; + rtx xi, yi; + int i; + + if (mode & STRUCT_EQUIV_START) + { + x_stop = BB_HEAD (info->x_block); + y_stop = BB_HEAD (info->y_block); + if (!x_stop || !y_stop) + return 0; + } + else + { + x_stop = info->cur.x_start; + y_stop = info->cur.y_start; + } + if (!struct_equiv_init (mode, info)) + gcc_unreachable (); + + /* Skip simple jumps at the end of the blocks. Complex jumps still + need to be compared for equivalence, which we'll do below. */ + + xi = BB_END (info->x_block); + if (onlyjump_p (xi) + || (returnjump_p (xi) && !side_effects_p (PATTERN (xi)))) + { + info->cur.x_start = xi; + xi = PREV_INSN (xi); + } + + yi = BB_END (info->y_block); + if (onlyjump_p (yi) + || (returnjump_p (yi) && !side_effects_p (PATTERN (yi)))) + { + info->cur.y_start = yi; + /* Count everything except for unconditional jump as insn. */ + /* ??? Is it right to count unconditional jumps with a clobber? + Should we count conditional returns? */ + if (!simplejump_p (yi) && !returnjump_p (yi) && info->cur.x_start) + info->cur.ninsns++; + yi = PREV_INSN (yi); + } + + if (mode & STRUCT_EQUIV_MATCH_JUMPS) + { + /* The caller is expected to have compared the jumps already, but we + need to match them again to get any local registers and inputs. */ + gcc_assert (!info->cur.x_start == !info->cur.y_start); + if (info->cur.x_start) + { + if (any_condjump_p (info->cur.x_start) + ? !condjump_equiv_p (info, false) + : !insns_match_p (info->cur.x_start, info->cur.y_start, info)) + gcc_unreachable (); + } + else if (any_condjump_p (xi) && any_condjump_p (yi)) + { + info->cur.x_start = xi; + info->cur.y_start = yi; + xi = PREV_INSN (xi); + yi = PREV_INSN (yi); + info->cur.ninsns++; + if (!condjump_equiv_p (info, false)) + gcc_unreachable (); + } + if (info->cur.x_start && info->mode & STRUCT_EQUIV_FINAL) + struct_equiv_merge (info->cur.x_start, info->cur.y_start, info); + } + + struct_equiv_improve_checkpoint (&info->best_match, info); + info->x_end = xi; + info->y_end = yi; + if (info->cur.x_start != x_stop) + for (;;) + { + /* Ignore notes. */ + while (!INSN_P (xi) && xi != x_stop) + xi = PREV_INSN (xi); + + while (!INSN_P (yi) && yi != y_stop) + yi = PREV_INSN (yi); + + if (!insns_match_p (xi, yi, info)) + break; + if (INSN_P (xi)) + { + if (info->mode & STRUCT_EQUIV_FINAL) + struct_equiv_merge (xi, yi, info); + info->cur.ninsns++; + struct_equiv_improve_checkpoint (&info->best_match, info); + } + if (xi == x_stop || yi == y_stop) + { + /* If we reached the start of at least one of the blocks, but + best_match hasn't been advanced back to the first valid insn + yet, represent the increased benefit of completing the block + as an increased instruction count. */ + if (info->best_match.x_start != info->cur.x_start + && (xi == BB_HEAD (info->x_block) + || yi == BB_HEAD (info->y_block))) + { + info->cur.ninsns++; + struct_equiv_improve_checkpoint (&info->best_match, info); + info->cur.ninsns--; + if (info->best_match.ninsns > info->cur.ninsns) + info->best_match.ninsns = info->cur.ninsns; + } + break; + } + xi = PREV_INSN (xi); + yi = PREV_INSN (yi); + } + + /* If we failed to match an insn, but had some changes registered from + trying to make the insns match, we need to cancel these changes now. */ + cancel_changes (0); + /* Restore to best_match to get the sequence with the best known-so-far + cost-benefit difference. */ + struct_equiv_restore_checkpoint (&info->best_match, info); + + /* Include preceding notes and labels in the cross-jump / if-conversion. + One, this may bring us to the head of the blocks. + Two, it keeps line number notes as matched as may be. */ + if (info->cur.ninsns) + { + xi = info->cur.x_start; + yi = info->cur.y_start; + while (xi != x_stop && !INSN_P (PREV_INSN (xi))) + xi = PREV_INSN (xi); + + while (yi != y_stop && !INSN_P (PREV_INSN (yi))) + yi = PREV_INSN (yi); + + info->cur.x_start = xi; + info->cur.y_start = yi; + } + + if (!info->cur.input_valid) + info->x_input = info->y_input = info->input_reg = NULL_RTX; + if (!info->need_rerun) + { + find_dying_inputs (info); + if (info->mode & STRUCT_EQUIV_FINAL) + { + if (info->check_input_conflict && ! resolve_input_conflict (info)) + gcc_unreachable (); + } + else + { + bool input_conflict = info->had_input_conflict; + + if (!input_conflict + && info->dying_inputs > 1 + && bitmap_intersect_p (info->x_local_live, info->y_local_live)) + { + regset_head clobbered_regs; + + INIT_REG_SET (&clobbered_regs); + for (i = 0; i < info->cur.local_count; i++) + { + if (assign_reg_reg_set (&clobbered_regs, info->y_local[i], 0)) + { + input_conflict = true; + break; + } + assign_reg_reg_set (&clobbered_regs, info->x_local[i], 1); + } + CLEAR_REG_SET (&clobbered_regs); + } + if (input_conflict && !info->check_input_conflict) + info->need_rerun = true; + info->check_input_conflict = input_conflict; + } + } + + if (info->mode & STRUCT_EQUIV_NEED_FULL_BLOCK + && (info->cur.x_start != x_stop || info->cur.y_start != y_stop)) + return 0; + return info->cur.ninsns; +} + +/* For each local register, set info->local_rvalue to true iff the register + is a dying input. Store the total number of these in info->dying_inputs. */ +static void +find_dying_inputs (struct equiv_info *info) +{ + int i; + + info->dying_inputs = 0; + for (i = info->cur.local_count-1; i >=0; i--) + { + rtx x = info->x_local[i]; + unsigned regno = REGNO (x); + int nregs = (regno >= FIRST_PSEUDO_REGISTER + ? 1 : hard_regno_nregs[regno][GET_MODE (x)]); + + for (info->local_rvalue[i] = false; nregs > 0; regno++, --nregs) + if (REGNO_REG_SET_P (info->x_local_live, regno)) + { + info->dying_inputs++; + info->local_rvalue[i] = true; + break; + } + } +} + +/* For each local register that is a dying input, y_local[i] will be + copied to x_local[i]. We'll do this in ascending order. Try to + re-order the locals to avoid conflicts like r3 = r2; r4 = r3; . + Return true iff the re-ordering is successful, or not necessary. */ +static bool +resolve_input_conflict (struct equiv_info *info) +{ + int i, j, end; + int nswaps = 0; + rtx save_x_local[STRUCT_EQUIV_MAX_LOCAL]; + rtx save_y_local[STRUCT_EQUIV_MAX_LOCAL]; + + find_dying_inputs (info); + if (info->dying_inputs <= 1) + return true; + memcpy (save_x_local, info->x_local, sizeof save_x_local); + memcpy (save_y_local, info->y_local, sizeof save_y_local); + end = info->cur.local_count - 1; + for (i = 0; i <= end; i++) + { + /* Cycle detection with regsets is expensive, so we just check that + we don't exceed the maximum number of swaps needed in the acyclic + case. */ + int max_swaps = end - i; + + /* Check if x_local[i] will be clobbered. */ + if (!info->local_rvalue[i]) + continue; + /* Check if any later value needs to be copied earlier. */ + for (j = i + 1; j <= end; j++) + { + rtx tmp; + + if (!info->local_rvalue[j]) + continue; + if (!reg_overlap_mentioned_p (info->x_local[i], info->y_local[j])) + continue; + if (--max_swaps < 0) + { + memcpy (info->x_local, save_x_local, sizeof save_x_local); + memcpy (info->y_local, save_y_local, sizeof save_y_local); + return false; + } + nswaps++; + tmp = info->x_local[i]; + info->x_local[i] = info->x_local[j]; + info->x_local[j] = tmp; + tmp = info->y_local[i]; + info->y_local[i] = info->y_local[j]; + info->y_local[j] = tmp; + j = i; + } + } + info->had_input_conflict = true; + if (dump_file && nswaps) + fprintf (dump_file, "Resolved input conflict, %d %s.\n", + nswaps, nswaps == 1 ? "swap" : "swaps"); + return true; +} |