diff options
Diffstat (limited to 'gcc/struct-equiv.c')
| -rw-r--r-- | gcc/struct-equiv.c | 1339 |
1 files changed, 0 insertions, 1339 deletions
diff --git a/gcc/struct-equiv.c b/gcc/struct-equiv.c deleted file mode 100644 index 6675e5b..0000000 --- a/gcc/struct-equiv.c +++ /dev/null @@ -1,1339 +0,0 @@ -/* 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, 2006, 2007 - 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 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/>. */ - -/* 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" -#include "df.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 ATTRIBUTE_UNUSED = 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 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 || reload_completed) - 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 as 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); - } - - if (!hard_reg_set_equal_p (i1_regset, i2_regset)) - return false; - } -#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 (!REG_SET_EQUAL_P (DF_LR_OUT (info->x_block), - DF_LR_OUT (info->y_block))) - { -#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 (DF_LR_OUT (info->x_block), rn); - CLEAR_REGNO_REG_SET (DF_LR_OUT (info->y_block), rn); - } - if (!REG_SET_EQUAL_P (DF_LR_OUT (info->x_block), - DF_LR_OUT (info->y_block))) -#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, DF_LR_OUT (info->x_block)); - 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; -} |