/* Discovery of auto-inc and auto-dec instructions. Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011 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 . */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "tree.h" #include "rtl.h" #include "tm_p.h" #include "hard-reg-set.h" #include "basic-block.h" #include "insn-config.h" #include "regs.h" #include "flags.h" #include "output.h" #include "function.h" #include "except.h" #include "diagnostic-core.h" #include "recog.h" #include "expr.h" #include "timevar.h" #include "tree-pass.h" #include "df.h" #include "dbgcnt.h" #include "target.h" #include "optabs.h" #include "addresses.h" #ifdef AUTO_INC_DEC /* This pass goes through each basic block looking for references of the form: REG (implicitly REG + 0) REG + CONST_INT REG + REG These references may occur as MEM addresses (in which case we call them "memory references") or as the source of a single register set (in which case we call them "addition references"). We refer to the first plus operand as the "base" and the second operand as the "offset". We chain these references together based on three things: (C1) instruction order, so that all references in the basic block are chained together (C2) the same base register live range (that is, uses of the same base register rtx that have the same point of definition) (C3) the same base + offset value (this is, references whose base + offset expressions are known to have the same value, regardless of the actual base + offset representation) We also try to look for natural "postmod" (POST_INC or POST_DEC) and "premod" (PRE_INC or PRE_DEC) chains. In the general case, these chains can be any sequence of references in which: - the first reference is a memory reference that can be converted into a {POST,PRE}_{INC,DEC}. - each subsequent memory reference can be converted into either the same {POST,PRE}_{INC,DEC} or a plain REG. - each addition reference can be converted into a REG. For example, a POST_INC chain might include the references on the left-hand side of this diagram, with the idea of converting them to the form on the right-hand side: ... = *r1 ... = *rN++ ... = *(r1 + 4) ... = *rN *(r1 + 4) = ... *rN++ = ... r2 = r1 + 8 r2 = rN ... = *r2 ---> ... = rN++ r3 = r2 + 4 r3 = rN ... = *r3 ... = rN++ r4 = r1 + 16 r4 = rN ... = *r4 ... = rN However, which chains are profitable depends on whether we are optimizing for speed (where extra dependencies would hurt scheduling) or for size (where replacing offset addresses with plain register addresses might be a win). After we have recorded all the references for a basic block, we go through them and try to apply the postmod and premod chains. We first try to find a live range that can be extended to span the entire chain, and whose register value can be represented as a constant offset from the final chain address. If we find such a live range for register rB, we will try to use rB as the base register. We then try to adjust all non-chain references to rB by the amount that has been added to rB by earlier parts of the chain. For example: *rB -> *rB++ ... rB + 16 ... -> ... rB + 15 ... r1 = rB + 1 -> r1 = rB *r1 -> *rB++ ... rB + 32 ... -> ... rB + 30 ... r2 = rB + 2 [rB dead] -> r2 = rB *r2 -> *rB [rB dead] Using such a base register should not increase register pressure, and may actually reduce it. However, if no such register is available, or if the cost of modifying the other references is too high, we instead consider using a new register. Again, the cost of modifying the other references depends on whether we are optimizing for size or speed; in the latter case, we want to avoid adding unnecessary dependencies. We then go through any remaining references looking for simple pre-modification or post-modification pairs. Taking each in turn: Pre-modification pairs ---------------------- These pairs concern a reference REF2 and the previous reference REF1 to the same base + offset value (chain C3). There are three cases of interest: REF1: Y = R1 + X1 ---> Y = R1 REF2: *(R2 + X2) ---> *(pre Y + X1) REF1: Y = R1 + X1 ---> Y = R2 REF2: *(R2 + X2) ---> *(pre Y + X2) REF1: *(R1 + X1) ---> Y = R1 REF2: Y = R2 + X2 ---> *(pre Y + X1) where R1 + X1 == R2 + X2 in each case. The pre-modification may be a PRE_INC, a PRE_DEC, a constant PRE_MODIFY or a register PRE_MODIFY. Post-modification pairs ----------------------- These pairs concern a reference REF2 and the previous reference REF1 to the same base register definition R (chain C2). There are three cases of interest: REF1: R = B + C ---> R = B REF2: *(R - C) ---> *(post R + C) REF1: Y = R + X ---> Y = R REF2: *R ---> *(post Y + X) REF1: *R ---> Y = R REF2: Y = R + X ---> *(post Y + X). The post-modification may be a POST_INC, a POST_DEC, a constant POST_MODIFY or a register POST_MODIFY. */ /* Enumerates the type of a ref_point. */ enum ref_type { /* The reference is no longer valid, and shouldn't be used. */ REF_INVALID, /* An addition reference. */ REF_ADD, /* A memory reference. */ REF_MEM }; /* Represents the offset in a reference. An external boolean specifies whether the offset is constant, in which case C is the CONST_INT offset, or whether the offset is a variable, in which case LR specifies the live range of the offset register. */ union ref_offset { rtx c; struct reg_live_range *lr; }; /* Flags that describe one reference in a postmod or premod chain. MOD_INC the chain as a whole uses increments rather than decrements MOD_HERE the current reference must use an automodification MOD_TARGET the current reference is not the final one. */ #define MOD_INC 1 #define MOD_HERE 2 #define MOD_TARGET 4 /* Describe a reference to a valno. Each reference is a base register plus a (possibly zero) constant or register offset. */ struct ref_point { /* The type of reference. */ ENUM_BITFIELD (ref_type) type : 8; /* The MOD_* flags that describe this entry in the postmod and premod chains respectively. */ unsigned int postmod_flags : 8; unsigned int premod_flags : 8; /* True if the offset is constant. */ unsigned int const_offset_p : 1; /* True for REF_MEMs if no target-independent rules prevent automodification. */ unsigned int allow_automod_p : 1; /* For future expansion, and to keep the fields nicely aligned. */ unsigned int unused : 6; /* The instruction in which the reference occurs. */ rtx insn; /* Type-specific information. */ union { /* The MEM rtx for a REF_MEM. */ rtx mem; /* Information about a REF_ADD. */ struct { /* The previous live range of the destination register, before this definition. */ struct reg_live_range *old_dest_range; /* The live range of the destination register, starting with this definition. */ struct reg_live_range *new_dest_range; } add; } u; /* The base register and offset. */ struct reg_live_range *base; union ref_offset offset; /* The value of BASE + OFFSET. */ struct valno_def *valno; /* The previous reference that was recorded in the same basic block, or null if none. This is chain C1 in the commentary at the top of the file. */ struct ref_point *prev_ref; /* The previous and next references with the same BASE, or null if none. This is chain C2 in the commentary at the top of the file. */ struct ref_point *prev_base_ref; struct ref_point *next_base_ref; /* The previous reference to the same valno, or null if none. This is chain C3 in the commentary at the top of the file. */ struct ref_point *prev_valno_ref; /* The previous references in the postmod and premod chains respectively. */ struct ref_point *postmod_ref; struct ref_point *premod_ref; }; /* Information about the live range of a register rtx (as opposed to an individual register number). */ struct reg_live_range { /* The register rtx whose range is being tracked. */ rtx reg; /* The valno that has been assigned to this live range, or null if none. */ struct valno_def *valno; /* The addition reference that defined the register, or null if the definition didn't come from an addition reference. */ struct ref_point *def; /* The uses of this live range as a base register, as a doubly-linked list. */ struct ref_point *first_base_ref; struct ref_point *last_base_ref; /* True if the definition and all uses of this live range are part of the same premod chain. */ bool premod_chain_p; /* Likewise the same postmod chain. */ bool postmod_chain_p; /* True if we have tried to use this live range as a base register for a premod or postmod chain, but found the changes to be too expensive. */ bool tried_offset_mod_p; /* The consolidated luid of the effective point of definition. If the register rtx was set by an addition reference, this value is exact, otherwise it is a conservative upper bound. For example, given something like: I1: r4 = ... I2: r5 = ... a live range for (r4,r5) would have a def_luid >= I2's luid. */ unsigned int def_luid; /* The consolidated luid of the first and last uses in the range that could not be represented in the base_ref chain. */ unsigned int first_untracked_luid; unsigned int last_untracked_luid; /* The consolidated luid of the point after which the value defined by def_luid is no longer available. This is the maximum luid (~0U) if the value is available until the end of the block. */ unsigned int next_def_luid; }; /* Represents an offset that is applied to a valno base. */ union valno_offset { HOST_WIDE_INT constant; struct valno_def *valno; }; /* Information about a value number. Leaf values have a null BASE and OFFSET, while derived values are the sum of a valno BASE and a constant or valno OFFSET. */ struct valno_def { /* A function-wide unique identifier for this valno. */ int id; /* The mode of the valno. */ ENUM_BITFIELD (machine_mode) mode : 16; /* True if OFFSET is constant, false if it is a valno. */ unsigned int const_offset_p : 1; /* For future expansion, and to keep the fields nicely aligned. */ unsigned int unused : 7; /* The postmod_flags that should be given to last_postmod_ref, if used. */ unsigned int last_postmod_flags : 8; /* See above. The offset is the splay key. */ struct valno_def *base; union valno_offset offset; /* Splay trees of valnos that use this one as their base. In each case the splay key is the offset. There is one tree for constant offsets and one for variable offsets. */ struct valno_def *const_sums; struct valno_def *var_sums; /* The left and right subnodes in the base valno's splay tree. */ struct valno_def *splay_child[2]; /* The previous reference to this value, or null if none. */ struct ref_point *last_ref; /* The previous reference that could calculate this value by becoming part of a postmod chain, or null if none. */ struct ref_point *last_postmod_ref; }; /* Represents a zero valno for a given mode. */ struct zero_valno { /* The basic block for which the valno was created. */ basic_block bb; /* The valno itself, or null if it hasn't been created for this function. */ struct valno_def *valno; }; /* Information about the state of an individual register. */ struct regno_state_info { /* The consolidated luid of the last instruction to use or set the register. */ unsigned int last_ref_luid; /* If this field is >= bb_live_range_base, then the register is being tracked as part of the live range at index: live_range_id - bb_live_range_base in the live_ranges vector. */ unsigned int live_range_id; }; /* Vector definitions for live ranges. */ typedef struct reg_live_range *reg_live_range_ptr; DEF_VEC_P (reg_live_range_ptr); DEF_VEC_ALLOC_P (reg_live_range_ptr, heap); /* The current basic block. */ static basic_block current_bb; /* The first consolidated luid that is associated with this basic block. */ static unsigned int bb_luid_base; /* The first live range identifier that is associated with this basic block; see regno_state_info. */ static unsigned int bb_live_range_base; /* A list of all recorded references in this basic block, starting with the one that is executed last. */ static struct ref_point *bb_refs; /* The first unused valno id. */ static unsigned int next_valno; /* Information about all registers that existed before this pass, indexed by register number. */ static struct regno_state_info *regno_state; /* An obstack used for allocating most bb-local data. */ static struct obstack bb_obstack; /* All zero valnos, indexed by mode. */ static struct zero_valno zeros[(int) MAX_MACHINE_MODE]; /* A vector of all live ranges belonging to this basic block; see regno_state_info. */ static VEC (reg_live_range_ptr, heap) *live_ranges; /* Pseudo registers that were created but not used, indexed by their mode. */ static rtx new_regs[(int) MAX_MACHINE_MODE]; /* Temporary rtxes used when testing the cost of new instructions. */ static rtx test_set; static rtx test_plus; /* Return a "consolidated" luid for instruction INSN. Unlike DF_INSN_LUID, these luids are unique at the function rather than block level. They also have a gap between each pair of pre-pass instructions so that new instructions can be handled correctly. */ static unsigned int consolidated_luid (rtx insn) { return DF_INSN_LUID (insn) * 2 + 1 + bb_luid_base; } /* A consolidated luid that represents the end of a block. */ #define END_OF_BLOCK ~0U /* Return true if it is OK to move the definition of REG in principle, assuming register liveness permits it. */ static bool moveable_reg_p (rtx reg) { return !HARD_REGISTER_P (reg) || !fixed_regs[REGNO (reg)]; } /* If register REGNO is part of a tracked live range, return that range, otherwise return null. */ static inline struct reg_live_range * maybe_get_live_range_for_regno (unsigned int regno) { unsigned int id; id = regno_state[regno].live_range_id; if (id >= bb_live_range_base) return VEC_index (reg_live_range_ptr, live_ranges, id - bb_live_range_base); return 0; } /* Create a new live range for REG. DEF_LUID is the consolidated luid of the instruction that sets REG, or 0 if that isn't yet known. */ static struct reg_live_range * new_live_range (rtx reg, unsigned int def_luid) { struct reg_live_range *lr; lr = XOBNEW (&bb_obstack, struct reg_live_range); memset (lr, 0, sizeof (*lr)); lr->reg = reg; lr->def_luid = def_luid; lr->next_def_luid = END_OF_BLOCK; return lr; } /* Get a live range for the current definition of REG. */ static struct reg_live_range * get_live_range (rtx reg) { unsigned int regno, end_regno, def_luid, live_range_id; struct reg_live_range *lr; /* If we are already tracking REG, return the current range. */ lr = maybe_get_live_range_for_regno (REGNO (reg)); if (lr && rtx_equal_p (lr->reg, reg)) return lr; /* Get a conservative estimate of the def_luid. */ def_luid = 0; end_regno = END_REGNO (reg); for (regno = REGNO (reg); regno < end_regno; regno++) if (regno_state[regno].last_ref_luid > def_luid) def_luid = regno_state[regno].last_ref_luid; /* Create the reference. */ lr = new_live_range (reg, def_luid); /* Record the new live range of each individual register. */ live_range_id = bb_live_range_base + VEC_length (reg_live_range_ptr, live_ranges); for (regno = REGNO (reg); regno < end_regno; regno++) regno_state[regno].live_range_id = live_range_id; VEC_safe_push (reg_live_range_ptr, heap, live_ranges, lr); return lr; } /* Return true if LR is available at the instruction with consolidated luid LUID. */ static inline bool lr_available_at_p (struct reg_live_range *lr, unsigned int luid) { return lr->def_luid < luid && lr->next_def_luid >= luid; } /* Return true if LR is referenced before consolidated luid LUID, excluding a base reference in REF (if nonnull). REF itself may be before, in, or after LUID. */ static bool other_uses_before_p (struct reg_live_range *lr, struct ref_point *ref, unsigned int luid) { struct ref_point *other; /* Check for untracked uses. */ if (lr->first_untracked_luid && lr->first_untracked_luid < luid) return true; /* Check the first tracked use, excluding REF. */ other = lr->first_base_ref; if (ref && other == ref) other = other->next_base_ref; if (other && consolidated_luid (other->insn) < luid) return true; return false; } /* Return true if LR is referenced after consolidated luid LUID, excluding a base reference in REF (if nonnull). REF itself may be before, in, or after LUID. */ static bool other_uses_after_p (struct reg_live_range *lr, struct ref_point *ref, unsigned int luid) { struct ref_point *other; /* Check for untracked uses. */ if (lr->last_untracked_luid > luid) return true; /* Check the last tracked use, excluding REF. */ other = lr->last_base_ref; if (ref && other == ref) other = other->prev_base_ref; if (other && consolidated_luid (other->insn) > luid) return true; return false; } /* Record an untracked use of LR in the instruction with consolidated luid LUID. */ static void record_live_range_use (struct reg_live_range *lr, unsigned int luid) { gcc_checking_assert (luid > lr->def_luid && luid <= lr->next_def_luid); if (!lr->first_untracked_luid || lr->first_untracked_luid > luid) lr->first_untracked_luid = luid; if (lr->last_untracked_luid < luid) lr->last_untracked_luid = luid; lr->premod_chain_p = 0; lr->postmod_chain_p = 0; } /* Record that LR starts at the instruction with consolidated luid LUID. */ static void record_live_range_set (struct reg_live_range *lr, unsigned int luid) { gcc_checking_assert (!other_uses_before_p (lr, 0, luid + 1)); lr->def_luid = luid; gcc_checking_assert (lr->next_def_luid >= luid); } /* Record that LR ends at the instruction with consolidated luid LUID, which clobbers some or all of the register. There must be no untracked references to LR after LUID. */ static void record_live_range_clobber (struct reg_live_range *lr, unsigned int luid) { gcc_checking_assert (lr->def_luid <= luid); gcc_checking_assert (!other_uses_after_p (lr, 0, luid)); lr->next_def_luid = luid; } /* Return a pointer to the part of REF->insn that contains the sum of REF->base and REF->offset. */ static rtx * get_ref_loc (struct ref_point *ref) { rtx set; switch (ref->type) { case REF_MEM: return &XEXP (ref->u.mem, 0); case REF_ADD: set = single_set (ref->insn); gcc_assert (set); return &SET_SRC (set); default: gcc_unreachable (); } } /* INSN is the current iteration point and it uses LR at location *LOC. Return true if that reference is tracked as a ref_point. */ static bool tracked_reference_p (struct reg_live_range *lr, rtx insn, rtx *loc) { struct ref_point *ref; rtx *ref_loc; for (ref = lr->last_base_ref; ref && ref->insn == insn; ref = ref->prev_base_ref) { ref_loc = get_ref_loc (ref); if (GET_CODE (*ref_loc) == PLUS) ref_loc = &XEXP (*ref_loc, 0); if (ref_loc == loc) return true; } return false; } /* INSN is the next unprocessed instruction in the basic block, walking forwards. Process all the uses and definitions and update the liveness information accordingly. */ static void update_liveness (rtx insn) { unsigned int luid, regno, end_regno; df_ref *ref; struct reg_live_range *lr; luid = consolidated_luid (insn); for (ref = DF_INSN_USES (insn); *ref; ref++) { regno = DF_REF_REGNO (*ref); regno_state[regno].last_ref_luid = luid; lr = maybe_get_live_range_for_regno (regno); if (lr && !tracked_reference_p (lr, insn, DF_REF_LOC (*ref))) record_live_range_use (lr, luid); } for (ref = DF_INSN_DEFS (insn); *ref; ref++) { regno = DF_REF_REGNO (*ref); regno_state[regno].last_ref_luid = luid; lr = maybe_get_live_range_for_regno (regno); if (lr) { /* This instruction ends LR. */ record_live_range_clobber (lr, luid); end_regno = END_REGNO (lr->reg); for (regno = REGNO (lr->reg); regno < end_regno; regno++) regno_state[regno].live_range_id = 0; } } } /* LIVE_REGS is the set of registers that are live at the end of the current basic block. Update the liveness information accordingly. */ static void record_live_regs (bitmap live_regs) { unsigned int regno; bitmap_iterator bi; struct reg_live_range *lr; EXECUTE_IF_SET_IN_BITMAP (live_regs, 0, regno, bi) { lr = maybe_get_live_range_for_regno (regno); if (lr) record_live_range_use (lr, END_OF_BLOCK); } } /* Return a new valno of mode MODE. */ static struct valno_def * new_valno (enum machine_mode mode) { struct valno_def *valno; valno = XOBNEW (&bb_obstack, struct valno_def); memset (valno, 0, sizeof (*valno)); valno->id = next_valno++; valno->mode = mode; return valno; } /* Return true if VALNO is zero. */ static inline bool zero_valno_p (struct valno_def *valno) { return (zeros[(int) valno->mode].bb == current_bb && zeros[(int) valno->mode].valno == valno); } /* Return the zero valno for mode MODE. */ static struct valno_def * get_zero_valno (enum machine_mode mode) { struct valno_def *valno; if (zeros[(int) mode].bb == current_bb && zeros[(int) mode].valno) return zeros[(int) mode].valno; valno = new_valno (mode); if (dump_file) fprintf (dump_file, ";;\tv%d = 0:%s\n", valno->id, GET_MODE_NAME (mode)); zeros[(int) mode].bb = current_bb; zeros[(int) mode].valno = valno; return valno; } /* Return true if VALNO has splay key KEY, which is constant if CONSTANT_P. When returning false, set *DIR to 0 if VALNO is bigger than KEY and 1 if it is smaller. */ static inline bool same_splay_key (struct valno_def *valno, bool constant_p, union valno_offset *key, unsigned int *dir) { gcc_assert (constant_p == valno->const_offset_p); if (constant_p) { if (valno->offset.constant == key->constant) return true; *dir = (valno->offset.constant < key->constant); } else { if (valno->offset.valno == key->valno) return true; *dir = (valno->offset.valno->id < key->valno->id); } return false; } /* Create a new valno for BASE + OFFSET. OFFSET is constant if CONSTANT_P. */ static struct valno_def * new_splay_valno (struct valno_def *base, bool constant_p, union valno_offset *offset) { struct valno_def *valno; valno = new_valno (base->mode); valno->const_offset_p = constant_p; valno->base = base; if (constant_p) { valno->offset.constant = offset->constant; if (dump_file) fprintf (dump_file, ";;\tv%d = v%d + " HOST_WIDE_INT_PRINT_DEC " [%s]\n", valno->id, valno->base->id, valno->offset.constant, GET_MODE_NAME (valno->mode)); } else { valno->offset.valno = offset->valno; if (dump_file) fprintf (dump_file, ";;\tv%d = v%d + v%d [%s]\n", valno->id, valno->base->id, valno->offset.valno->id, GET_MODE_NAME (valno->mode)); } return valno; } /* Rotate a valno splay tree at address *PTR, promoting child number DIR and relegating its parent. */ static inline void valno_splay_rotate (struct valno_def **ptr, unsigned int dir) { struct valno_def *p, *c; p = *ptr; c = p->splay_child[dir]; p->splay_child[dir] = c->splay_child[1 - dir]; c->splay_child[1 - dir] = p; *ptr = c; } /* Ensure that there is a valno for BASE + OFFSET. CONSTANT_P is true if OFFSET is constant. This version of the splay algorithm is based on the libiberty one. */ static struct valno_def * valno_splay (struct valno_def *base, bool constant_p, union valno_offset *offset) { struct valno_def *g, *p, *c, **root; unsigned int g_to_p, p_to_c; root = constant_p ? &base->const_sums : &base->var_sums; if (!*root) *root = new_splay_valno (base, constant_p, offset); else do { /* See if the current root is the right one. */ g = *root; if (same_splay_key (g, constant_p, offset, &g_to_p)) break; /* Go left if KEY is smaller than the G's key, right otherwise. */ p = g->splay_child[g_to_p]; if (!p) { /* Create a new P and rotate it to the root. */ g->splay_child[g_to_p] = new_splay_valno (base, constant_p, offset); valno_splay_rotate (root, g_to_p); break; } /* See if P is the right one. */ if (same_splay_key (p, constant_p, offset, &p_to_c)) { /* Rotate P to the root. */ valno_splay_rotate (root, g_to_p); break; } /* Go left if KEY is smaller than the P's key, right otherwise. */ c = p->splay_child[p_to_c]; if (!c) p->splay_child[p_to_c] = new_splay_valno (base, constant_p, offset); /* Do a double rotation. */ valno_splay_rotate (&g->splay_child[g_to_p], p_to_c); valno_splay_rotate (root, g_to_p); } while (c); return *root; } /* Return a valno for a MODE integer with value VALUE. */ static struct valno_def * get_constant_valno (enum machine_mode mode, HOST_WIDE_INT value) { struct valno_def *zero; union valno_offset offset; zero = get_zero_valno (mode); if (value == 0) return zero; offset.constant = value; return valno_splay (zero, true, &offset); } /* Return a valno for live range LR. */ static struct valno_def * get_live_range_valno (struct reg_live_range *lr) { if (!lr->valno) { lr->valno = new_valno (GET_MODE (lr->reg)); if (dump_file) fprintf (dump_file, ";;\tv%d = current value of r%d\n", lr->valno->id, REGNO (lr->reg)); } return lr->valno; } /* Decompose VALNO into a base and a (possibly zero) constant offset, storing them in *BASE_VALNO and *CONST_OFFSET respectively. */ static void get_base_and_const_offset (struct valno_def *valno, struct valno_def **base_valno, unsigned HOST_WIDE_INT *const_offset) { if (valno->const_offset_p) { *base_valno = valno->base; *const_offset = valno->offset.constant; } else { *base_valno = valno; *const_offset = 0; } } /* A subroutine of add_valnos. Handle the case in which neither VALNO1 nor VALNO2 have constant offsets. */ static struct valno_def * add_valnos_1 (struct valno_def *valno1, struct valno_def *valno2) { struct valno_def *tmp; union valno_offset offset; if (zero_valno_p (valno1)) return valno2; if (zero_valno_p (valno2)) return valno1; /* Canonicalize values so that lower-number valnos come first. */ if (valno1->id > valno2->id) { tmp = valno2; valno2 = valno1; valno1 = tmp; } /* Look for an existing valno or create a new one. */ offset.valno = valno2; return valno_splay (valno1, false, &offset); } /* Return a representation of VALNO + CONSTANT. */ static struct valno_def * add_valno_and_constant (struct valno_def *valno, unsigned HOST_WIDE_INT constant) { struct valno_def *base; union valno_offset offset; unsigned HOST_WIDE_INT combined; get_base_and_const_offset (valno, &base, &combined); combined = trunc_int_for_mode (combined + constant, valno->mode); if (combined) { offset.constant = combined; base = valno_splay (base, true, &offset); } return base; } /* Return a valno that represents the sum of VALNO1 and VALNO2. */ static struct valno_def * add_valnos (struct valno_def *valno1, struct valno_def *valno2) { struct valno_def *base1, *base2, *valno; unsigned HOST_WIDE_INT offset1, offset2; union valno_offset offset; enum machine_mode mode; mode = valno1->mode; gcc_checking_assert (mode == valno2->mode); get_base_and_const_offset (valno1, &base1, &offset1); get_base_and_const_offset (valno2, &base2, &offset2); valno = add_valnos_1 (base1, base2); offset.constant = trunc_int_for_mode (offset1 + offset2, mode); if (offset.constant != 0) valno = valno_splay (valno, true, &offset); return valno; } /* Return true if REF2 is strictly later than REF1. */ static inline bool ref_order_p (struct ref_point *ref1, struct ref_point *ref2) { return DF_INSN_LUID (ref1->insn) < DF_INSN_LUID (ref2->insn); } /* Return true if reference REF has a zero offset. */ static inline bool zero_offset_p (struct ref_point *ref) { return ref->const_offset_p && ref->offset.c == const0_rtx; } /* Return true if REF2's offset is the negative of REF1's. */ static inline bool opposite_offsets_p (struct ref_point *ref1, struct ref_point *ref2) { return (ref1->const_offset_p && ref2->const_offset_p && UINTVAL (ref1->offset.c) == -UINTVAL (ref2->offset.c)); } /* Return an rtx representation of OFFSET. CONSTANT_P says whether the offset is a constant or a register. */ static inline rtx get_ref_offset_rtx (bool constant_p, union ref_offset *offset) { return constant_p ? offset->c : offset->lr->reg; } /* REF is a memory reference. Return true if REF->insn refers to REG outside the memory address. */ static bool other_refs_in_insn_p (struct ref_point *ref, rtx reg) { gcc_assert (ref->type == REF_MEM); return (reg_set_p (reg, ref->insn) || refers_to_regno_p (REGNO (reg), END_REGNO (reg), PATTERN (ref->insn), &XEXP (ref->u.mem, 0))); } /* Link REF to the end if its base register's chain. */ static void add_base_ref_to_end (struct ref_point *ref) { ref->prev_base_ref = ref->base->last_base_ref; ref->next_base_ref = 0; if (ref->prev_base_ref) ref->prev_base_ref->next_base_ref = ref; else ref->base->first_base_ref = ref; ref->base->last_base_ref = ref; } /* Link REF to the beginning of its base register's chain. */ static void add_base_ref_to_beginning (struct ref_point *ref) { ref->prev_base_ref = 0; ref->next_base_ref = ref->base->last_base_ref; ref->base->first_base_ref = ref; if (ref->next_base_ref) ref->next_base_ref->prev_base_ref = ref; else ref->base->last_base_ref = ref; } /* Unlink REF from its base register chain. */ static void unlink_base_ref (struct ref_point *ref) { if (ref->prev_base_ref) ref->prev_base_ref->next_base_ref = ref->next_base_ref; else ref->base->first_base_ref = ref->next_base_ref; if (ref->next_base_ref) ref->next_base_ref->prev_base_ref = ref->prev_base_ref; else ref->base->last_base_ref = ref->prev_base_ref; } /* Invalidate reference REF, so that no future optimizations can use it. */ static void invalidate_ref (struct ref_point *ref) { ref->type = REF_INVALID; if (ref->premod_ref) ref->premod_ref->premod_flags &= ~MOD_TARGET; if (ref->postmod_ref) ref->postmod_ref->postmod_flags &= ~MOD_TARGET; unlink_base_ref (ref); } /* REF1 and REF2 compute the same value, and REF1 occurs before REF2. Return true if REF2 should be added to a premod or postmod chain that ends with REF1, even though no automodification would occur between REF1 and REF2. CODE specifies the type of chain; PRE_MODIFY for premod and POST_MODIFY for postmod. */ static bool link_in_mod_chain_p (struct ref_point *ref1, struct ref_point *ref2, enum rtx_code code) { /* Replacing REF2 with a base register might be a win sizewise. Allow the chain and rely on rtx costs to make the final decision. */ if (!optimize_bb_for_speed_p (current_bb)) return true; /* If we turn an addition into a move, that move might be removed. */ if (ref2->type == REF_ADD) return true; /* If REF1 has the form X = Y + Z, and if REF2 is a memory reference of the form *X, treat REF2 in the same way as *(Y + Z). REF1 might exist simply because the target doesn't allow Y + Z addresses for this mode (which is one of the cases where using auto-modified addresses gives the most benefit). */ if (code == POST_MODIFY && ref1->type == REF_ADD && ref1->u.add.new_dest_range == ref2->base && zero_offset_p (ref2)) return true; return false; } /* X is an expression of type TYPE that occurs in INSN. If it can be represented as a ref_point, create and return one for it, otherwise return null. */ static struct ref_point * start_ref_point (enum ref_type type, rtx insn, rtx x) { rtx base, offset; struct ref_point *ref; struct valno_def *valno; /* Early out if the expression doesn't have a mode we care about. */ if (!SCALAR_INT_MODE_P (GET_MODE (x))) return false; if (GET_CODE (x) == PLUS) { base = XEXP (x, 0); offset = XEXP (x, 1); } else { base = x; offset = const0_rtx; } if (!REG_P (base)) return 0; if (!(REG_P (offset) || CONST_INT_P (offset))) return 0; /* Create a new entry. */ ref = XOBNEW (&bb_obstack, struct ref_point); memset (ref, 0, sizeof (*ref)); ref->type = type; ref->insn = insn; ref->base = get_live_range (base); ref->const_offset_p = CONST_INT_P (offset); if (ref->const_offset_p) ref->offset.c = offset; else ref->offset.lr = get_live_range (offset); /* Work out the value of X. */ valno = get_live_range_valno (ref->base); if (!ref->const_offset_p) valno = add_valnos (valno, get_live_range_valno (ref->offset.lr)); else if (ref->offset.c != const0_rtx) valno = add_valno_and_constant (valno, INTVAL (ref->offset.c)); ref->valno = valno; /* Chain all references. */ ref->prev_ref = bb_refs; bb_refs = ref; /* Chain references to the base register. */ add_base_ref_to_end (ref); /* See whether the reference can be part of a postmod chain. */ if (valno->last_postmod_ref && !(valno->last_postmod_ref->postmod_flags & MOD_TARGET)) { /* A previous instruction could produce X's value through a post-modification. */ ref->postmod_ref = valno->last_postmod_ref; ref->postmod_ref->postmod_flags = valno->last_postmod_flags; valno->last_postmod_ref = 0; } else if (valno->last_ref && valno->last_ref->postmod_ref && !(valno->last_ref->postmod_flags & MOD_TARGET) && link_in_mod_chain_p (valno->last_ref, ref, POST_MODIFY)) { /* A previous instruction used X's value, and was itself the end of a post-modification chain. Add this reference to that chain. If we end up implementing the chain, the previous instruction will just se a base register without modifying it. */ ref->postmod_ref = valno->last_ref; ref->postmod_ref->postmod_flags = ref->postmod_ref->postmod_ref->postmod_flags & ~MOD_HERE; } /* See whether the reference can be part of a premod chain. The caller can override this choice. */ if (valno->last_ref && valno->last_ref->premod_ref && !(valno->last_ref->premod_flags & MOD_TARGET) && link_in_mod_chain_p (valno->last_ref, ref, PRE_MODIFY)) { /* A previous instruction used X's value, and was itself the end of a pre-modification chain. Add this reference to that chain. If we end up using the chain, this instruction will just use a base register without modifying it. */ ref->premod_ref = valno->last_ref; ref->premod_flags = ref->premod_ref->premod_flags & MOD_INC; } /* Chain references to X's value. */ ref->prev_valno_ref = valno->last_ref; valno->last_ref = ref; return ref; } /* Complete REF, which was created by start_ref_point. */ static void end_ref_point (struct ref_point *ref) { struct ref_point *base_automod_ref; /* Check whether this use of the base register is part of the same chain as the definition and the other uses. */ base_automod_ref = ref->prev_base_ref ? ref->prev_base_ref : ref->base->def; if (ref->postmod_ref != base_automod_ref) ref->base->postmod_chain_p = 0; if (ref->premod_ref != base_automod_ref) ref->base->premod_chain_p = 0; /* Now that we've finalized the choice of premod reference, record that it is part of chain. */ if (ref->premod_ref) ref->premod_ref->premod_flags |= MOD_TARGET; if (dump_file) { fprintf (dump_file, ";;\tRecording %d as a reference to v%d\n", INSN_UID (ref->insn), ref->valno->id); if (ref->prev_ref) fprintf (dump_file, ";;\t-- previous reference of any kind is %d\n", INSN_UID (ref->prev_ref->insn)); if (ref->prev_valno_ref) fprintf (dump_file, ";;\t-- previous reference to v%d is %d\n", ref->valno->id, INSN_UID (ref->prev_valno_ref->insn)); if (ref->prev_base_ref) fprintf (dump_file, ";;\t-- previous reference to base r%d is %d\n", REGNO (ref->base->reg), INSN_UID (ref->prev_base_ref->insn)); if (ref->postmod_ref) fprintf (dump_file, ";;\t-- post-mod chain %s %d\n", !(ref->postmod_ref->postmod_flags & MOD_HERE) ? "makes no change to" : ref->postmod_ref->postmod_flags & MOD_INC ? "uses a post_inc in" : "uses a post_dec in", INSN_UID (ref->postmod_ref->insn)); if (ref->premod_ref) fprintf (dump_file, ";;\t-- pre-mod chain %s after %d\n", !(ref->premod_flags & MOD_HERE) ? "makes no change" : ref->premod_flags & MOD_INC ? "uses a pre_inc" : "uses a pre_dec", INSN_UID (ref->premod_ref->insn)); } } /* Try to record INSN as an addition reference. Return true on success. When returning true, update the register liveness information to describe the state after INSN. */ static bool process_reg_arithmetic (rtx insn) { struct ref_point *ref; struct reg_live_range *lr; rtx set; set = single_set (insn); if (!set || !REG_P (SET_DEST (set))) return false; if (CONST_INT_P (SET_SRC (set))) { /* We don't want to change (set (reg) (const_int)) instructions, but they provide useful value-numbering information. */ update_liveness (insn); lr = get_live_range (SET_DEST (set)); lr->valno = get_constant_valno (GET_MODE (SET_DEST (set)), INTVAL (SET_SRC (set))); return true; } ref = start_ref_point (REF_ADD, insn, SET_SRC (set)); if (!ref) return false; ref->u.add.old_dest_range = get_live_range (SET_DEST (set)); update_liveness (insn); lr = get_live_range (SET_DEST (set)); lr->def = ref; lr->valno = ref->valno; if (ref->premod_ref) lr->premod_chain_p = 1; if (ref->postmod_ref) lr->postmod_chain_p = 1; ref->u.add.new_dest_range = lr; end_ref_point (ref); return true; } /* REF is a reference that could calculate VALNO using a post-modification; the MOD_INC flag in POSTMOD_FLAGS says whether this is through an increment or a decrement. If the post-modification would form a valid chain, record it in VALNO. */ static void consider_postmod (struct ref_point *ref, struct valno_def *valno, unsigned int postmod_flags) { /* If REF is already part of a chain, this modification must be in the same direction. */ if (ref->postmod_ref && (ref->postmod_ref->postmod_flags ^ postmod_flags) & MOD_INC) return; valno->last_postmod_flags = postmod_flags | MOD_HERE | MOD_TARGET; valno->last_postmod_ref = ref; } /* REF2 is a reference that could calculate its value by applying a pre-modification after REF1; the MOD_INC flag in PREMOD_FLAGS says whether this is through an increment or a decrement. If the pre-modification would form a valid chain, and if the chain is "better" than any current one, add REF2 to that chain. */ static void consider_premod (struct ref_point *ref1, struct ref_point *ref2, unsigned int premod_flags) { /* If REF1 is already part of a premod chain, it must be the end of the chain, and the chain must go in the same direction as REF1-to-REF2. */ if (ref1->premod_ref) { if (ref1->premod_flags & MOD_TARGET) return; if ((ref1->premod_flags ^ premod_flags) & MOD_INC) return; } /* Prefer any current chain unless REF1 is later. */ if (ref2->premod_ref && !ref_order_p (ref2->premod_ref, ref1)) return; ref2->premod_flags = premod_flags | MOD_HERE; ref2->premod_ref = ref1; } /* Used to pass information between process_mem_refs and record_mem_refs. */ struct mem_ref_info { /* The instruction that contains the memory reference. */ rtx insn; /* Nonzero if there is something that stops the memory reference from being automodified. */ int block_automod; }; /* A for_each_rtx callback for which DATA is a mem_ref_info. Record any memory references. */ static int record_mem_refs (rtx *loc, void *data) { struct mem_ref_info *info; rtx x; struct ref_point *ref; struct valno_def *dec, *inc; unsigned HOST_WIDE_INT size; info = (struct mem_ref_info *) data; x = *loc; if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT) { /* We cannot use auto-modified addresses in extract operations. */ info->block_automod++; for_each_rtx (&XEXP (x, 0), record_mem_refs, data); info->block_automod--; return -1; } if (!MEM_P (x)) return 0; ref = start_ref_point (REF_MEM, info->insn, XEXP (x, 0)); if (!ref) return 0; ref->u.mem = x; ref->allow_automod_p = (info->block_automod == 0); /* See whether the MEM could become an active member of a premod or postmod chain. */ if (ref->allow_automod_p && GET_MODE (x) != BLKmode) { size = GET_MODE_SIZE (GET_MODE (x)); /* Handle PRE_INC from -SIZE and POST_DEC to -SIZE. */ dec = add_valno_and_constant (ref->valno, -size); if (dec->last_ref) consider_premod (dec->last_ref, ref, MOD_INC); consider_postmod (ref, dec, 0); /* Handle PRE_DEC from +SIZE and POST_INC to +SIZE. */ inc = add_valno_and_constant (ref->valno, size); if (inc->last_ref) consider_premod (inc->last_ref, ref, 0); consider_postmod (ref, inc, MOD_INC); } end_ref_point (ref); return -1; } /* Record all memory references in INSN. Update the register liveness information to reflect the state after INSN. */ static void process_mem_refs (rtx insn) { struct mem_ref_info info; info.insn = insn; info.block_automod = JUMP_P (insn); for_each_rtx (&PATTERN (insn), record_mem_refs, &info); update_liveness (insn); } /* Return the current cost of instruction pattern PAT. ??? The logical thing would be to use insn_rtx_cost, but that ignores memory SET_DESTs. Fixing that is unfortunately a can of worms. Since in this pass we do not change the form of an instruction, only its addresses, we can simply sum up the cost of each individual set. */ static int pattern_cost (rtx pat) { bool speed_p; int cost; int i; speed_p = optimize_bb_for_speed_p (current_bb); cost = 0; if (GET_CODE (pat) == SET) cost += set_rtx_cost (pat, speed_p); else if (GET_CODE (pat) == PARALLEL) for (i = 0; i < XVECLEN (pat, 0); i++) if (GET_CODE (XVECEXP (pat, 0, i)) == SET) cost += set_rtx_cost (XVECEXP (pat, 0, i), speed_p); return cost == 0 ? COSTS_N_INSNS (1) : cost; } /* Return the rtx cost of emitting DEST = BASE + OFFSET immediately before INSN. CONSTANT_P says whether OFFSET is constant. */ static int test_move_before (rtx insn, rtx dest, struct reg_live_range *base, bool constant_p, union ref_offset *offset) { rtx sum, src1; int cost; sum = base->reg; src1 = get_ref_offset_rtx (constant_p, offset); if (src1 != const0_rtx) { if (!test_plus) test_plus = gen_rtx_PLUS (GET_MODE (dest), sum, src1); else { PUT_MODE (test_plus, GET_MODE (dest)); XEXP (test_plus, 0) = sum; XEXP (test_plus, 1) = src1; } sum = test_plus; } if (!test_set) test_set = gen_rtx_SET (VOIDmode, dest, sum); else { SET_DEST (test_set) = dest; SET_SRC (test_set) = sum; } cost = pattern_cost (test_set); if (dump_file) { fprintf (dump_file, "%5d [before] r%d:%s=r%d:%s", INSN_UID (insn), REGNO (dest), GET_MODE_NAME (GET_MODE (dest)), REGNO (base->reg), GET_MODE_NAME (GET_MODE (base->reg))); if (REG_P (src1)) fprintf (dump_file, "+r%d:%s", REGNO (src1), GET_MODE_NAME (GET_MODE (src1))); else if (src1 != const0_rtx && CONST_INT_P (src1)) fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, INTVAL (src1)); fprintf (dump_file, "\n;;\tCost = %d\n", cost); } return cost; } /* Emit DEST = BASE + OFFSET immediately before INSN. CONSTANT_P says whether OFFSET is constant. OLD_DEST, if nonnull, is the previous live range of DEST. */ static void commit_move_before (rtx insn, struct reg_live_range *old_dest, rtx dest, struct reg_live_range *base, bool constant_p, union ref_offset *offset) { rtx src, src1, move; unsigned int luid; start_sequence (); src = base->reg; src1 = get_ref_offset_rtx (constant_p, offset); if (src1 != const0_rtx) src = expand_binop (GET_MODE (src), add_optab, src, src1, dest, false, OPTAB_LIB_WIDEN); if (!rtx_equal_p (dest, src)) emit_move_insn (dest, src); move = get_insns (); end_sequence (); if (dump_file) { fprintf (dump_file, "adding before insn %d:\n", INSN_UID (insn)); dump_insn_slim (dump_file, move); } emit_insn_before (move, insn); luid = consolidated_luid (insn) - 1; record_live_range_use (base, luid); if (old_dest) record_live_range_clobber (old_dest, luid); } /* Return the cost of deleting addition reference REF. */ static int test_ref_deletion (struct ref_point *ref) { int cost; gcc_assert (ref->type == REF_ADD); cost = pattern_cost (PATTERN (ref->insn)); if (dump_file) { dump_insn_slim (dump_file, ref->insn); fprintf (dump_file, " - [deleted]\n"); fprintf (dump_file, ";;\tOld cost = %d, new_cost = 0\n", cost); } return -cost; } /* Delete addition reference REF. */ static void commit_ref_deletion (struct ref_point *ref) { gcc_assert (ref->type == REF_ADD); invalidate_ref (ref); delete_insn (ref->insn); } /* Tentatively replace REF's expression with SRC. Return the change in rtx costs that the change would produce. */ static int rewrite_ref (struct ref_point *ref, rtx src) { int old_cost, new_cost; rtx insn; insn = ref->insn; if (dump_file) dump_insn_slim (dump_file, insn); old_cost = pattern_cost (PATTERN (insn)); /* If we're replacing an addition with a move, also try to replace a PARALLEL with a simple SET. Moves that are special enough to need clobbers are unlikely to be worth generating anyway. */ if (ref->type == REF_ADD && REG_P (src) && GET_CODE (PATTERN (insn)) == PARALLEL) validate_change (insn, &PATTERN (insn), XVECEXP (PATTERN (insn), 0, 0), 1); validate_change (ref->insn, get_ref_loc (ref), src, 1); new_cost = pattern_cost (PATTERN (ref->insn)); if (dump_file) { dump_insn_slim (dump_file, ref->insn); fprintf (dump_file, ";;\tOld cost = %d, new cost = %d\n", old_cost, new_cost); } return new_cost - old_cost; } /* Create an expression to perform auto-modification CODE for a memory of mode MEM_MODE. CODE is either a PRE_MODIFY or POST_MODIFY; BASE and OFFSET are the operands to the sum. */ static rtx automodify_address (enum machine_mode mem_mode, enum rtx_code code, rtx base, rtx offset) { unsigned HOST_WIDE_INT size; if (CONST_INT_P (offset)) { size = GET_MODE_SIZE (mem_mode); if (code == PRE_MODIFY) { if (HAVE_PRE_DECREMENT && UINTVAL (offset) == -size) return gen_rtx_PRE_DEC (GET_MODE (base), base); if (HAVE_PRE_INCREMENT && UINTVAL (offset) == size) return gen_rtx_PRE_INC (GET_MODE (base), base); } else { if (HAVE_POST_DECREMENT && UINTVAL (offset) == -size) return gen_rtx_POST_DEC (GET_MODE (base), base); if (HAVE_POST_INCREMENT && UINTVAL (offset) == size) return gen_rtx_POST_INC (GET_MODE (base), base); } } return gen_rtx_fmt_ee (code, GET_MODE (base), base, gen_rtx_PLUS (GET_MODE (base), base, offset)); } /* Tentatively replace memory reference REF with the equivalent of (CODE BASE OFFSET), where CODE is either POST_MODIFY or PRE_MODIFY. Return the change in rtx costs that the change would produce. */ static unsigned int test_automodification (struct ref_point *ref, enum rtx_code code, rtx base, rtx offset) { return rewrite_ref (ref, automodify_address (GET_MODE (ref->u.mem), code, base, offset)); } /* Commit an automodification in REF. NEW_BASE is the live range that the instruction defines. OLD_BASE, if nonnull, is the live range of the base register's previous value. */ static void commit_automodification (struct ref_point *ref, struct reg_live_range *old_base, struct reg_live_range *new_base) { unsigned int luid; gcc_assert (ref->type == REF_MEM); luid = consolidated_luid (ref->insn); add_reg_note (ref->insn, REG_INC, new_base->reg); invalidate_ref (ref); record_live_range_set (new_base, luid); if (old_base) { record_live_range_clobber (old_base, luid); record_live_range_use (old_base, luid); } } /* Validate the replacements made by the previous calls, given that the replacements have a cumulative cost of COST_DELTA, and that they must have a cumulative cost no greater than MAX_COST_DELTA. Return true if the changes should be kept, false if they should be reversed. */ static bool test_replacements (int max_cost_delta, int cost_delta, int from) { if (dump_file) fprintf (dump_file, ";;\tCost delta = %d\n", cost_delta); if (cost_delta > max_cost_delta) { if (dump_file) fprintf (dump_file, ";;\tChange not worthwhile\n"); return false; } if (!dbg_cnt (auto_inc_dec)) { if (dump_file) fprintf (dump_file, ";;\tRejecting due to dbgcnt\n"); return false; } if (!verify_changes (from)) { if (dump_file) fprintf (dump_file, ";;\tChange failed\n"); return false; } return true; } /* Return true if REF1's offset is available in REF2. */ static bool offset_available_at_p (struct ref_point *ref1, struct ref_point *ref2) { return (ref1->const_offset_p || lr_available_at_p (ref1->offset.lr, consolidated_luid (ref2->insn))); } /* CODE is either PRE_MODIFY or POST_MODIFY. Return the reference before REF in the associated premod or postmod chain. */ static inline struct ref_point * get_prev_automod_ref (struct ref_point *ref, enum rtx_code code) { return code == PRE_MODIFY ? ref->premod_ref : ref->postmod_ref; } /* CODE is either PRE_MODIFY or POST_MODIFY. Return the associated MOD_* flags for reference REF. */ static inline unsigned int get_automod_flags (struct ref_point *ref, enum rtx_code code) { return code == PRE_MODIFY ? ref->premod_flags : ref->postmod_flags; } /* CODE is either PRE_MODIFY or POST_MODIFY. Return true if LR exists only for the benefit of such a chain. If we are able to optimize that chain, the definition of LR is no longer needed. */ static inline bool lr_automod_chain_p (struct reg_live_range *lr, enum rtx_code code) { return code == PRE_MODIFY ? lr->premod_chain_p : lr->postmod_chain_p; } /* CODE is either PRE_MODIFY or POST_MODIFY. Return the offset that REF applies in the associated premod or postmod chain. */ static unsigned HOST_WIDE_INT get_automod_delta (struct ref_point *ref, enum rtx_code code) { unsigned HOST_WIDE_INT size; unsigned int flags; flags = get_automod_flags (ref, code); if (!(flags & MOD_HERE)) return 0; gcc_assert (ref->type == REF_MEM); size = GET_MODE_SIZE (GET_MODE (ref->u.mem)); return flags & MOD_INC ? size : -size; } /* REF has a constant offset. Return an rtx that adds OFFSET to its expression. */ static rtx get_adjusted_src (struct ref_point *ref, unsigned HOST_WIDE_INT offset) { gcc_assert (ref->const_offset_p); offset = trunc_int_for_mode (UINTVAL (ref->offset.c) + offset, GET_MODE (ref->base->reg)); return plus_constant (ref->base->reg, offset); } /* REF's rtx has had its constant offset updated. Record the new offset in REF. */ static void update_const_offset (struct ref_point *ref) { rtx x; x = *get_ref_loc (ref); if (GET_CODE (x) == PLUS) x = XEXP (x, 1); else x = const0_rtx; gcc_assert (ref->const_offset_p && CONST_INT_P (x)); ref->offset.c = x; } /* Describes the result of an automod chain optimization. */ enum automod_chain_result { /* The optimization was successful. */ AUTOMOD_OK, /* The optimization failed because the chain itself is either impossible or too expensive. */ AUTOMOD_BAD_CHAIN, /* The optimization failed because of a bad choice of base register. */ AUTOMOD_BAD_BASE }; /* Describes an automod chain that we're trying to optimize. */ struct automod_chain { /* The code that describes the chain; POST_MODIFY or PRE_MODIFY. */ enum rtx_code code; /* The final reference in the chain. */ struct ref_point *last; /* The first reference in the chain. This is always a memory reference that needs to perform an automodification. */ struct ref_point *first; /* The reference before FIRST, or null if none. Loops over the chain should stop once they reach this value. */ struct ref_point *stop; /* The number of register offsets that will be removed by the chain. */ int num_reg_offsets; /* The base register we want to use. */ rtx base; /* If there are other uses of BASE outside the chain, this is the affected live range, otherwise it is null. */ struct reg_live_range *base_lr; /* The offset that will be added to BASE_LR's original value by the chain. */ unsigned HOST_WIDE_INT final_offset; /* If MOVE_P, MOVE_OP0 + MOVE_OP1 must be moved into the base register before FIRST->insn. MOVE_OP1_CONSTANT_P says whether MOVE_OP1 is constant. */ bool move_p; bool move_op1_constant_p; struct reg_live_range *move_op0; union ref_offset move_op1; }; /* See whether END ends a postmod chain or premod chain. Return true if so, describing it in *C. CODE is the type of chain; either POST_MODIFY or PRE_MODIFY. */ static bool describe_automod_chain (struct automod_chain *c, struct ref_point *end, enum rtx_code code) { struct ref_point *ref, *first; unsigned HOST_WIDE_INT delta; if (get_automod_flags (end, code) & MOD_TARGET) return false; /* Find the extent of the chain. */ first = 0; for (ref = end; ref && ref->type != REF_INVALID; ref = get_prev_automod_ref (ref, code)) { delta = get_automod_delta (ref, code); /* The chain always starts on a {PRE,POST}_{INC,DEC}, rather than on a passive reference. We also need a start offset that can easily be moved into the base register; see get_adjusted_src. */ if (delta != 0 && (code == POST_MODIFY || ref->const_offset_p)) first = ref; } if (!first) return false; c->last = end; c->first = first; c->stop = get_prev_automod_ref (first, code); c->code = code; c->num_reg_offsets = 0; return true; } /* Return true if REF, which is part of C, can simply be deleted. */ static bool discardable_chain_member_p (struct automod_chain *c, struct ref_point *ref) { struct reg_live_range *dest; if (ref->type == REF_ADD) { dest = ref->u.add.new_dest_range; if (lr_automod_chain_p (dest, c->code)) /* The addition only serves memory references in the chain. */ return true; if (rtx_equal_p (dest->reg, c->base)) /* The chain will ensure that C->base holds the original value of the SET_SRC, so the reference would become a no-op move. */ return true; } return false; } /* Return the number of register references that will be added or removed by chain C. */ static int get_reg_count_delta_for_chain (struct automod_chain *c) { /* Each register offset will be removed. If we are creating a new base register, count 1 for it. */ return (c->base_lr ? 0 : 1) - c->num_reg_offsets; } /* Apply automod chain C. Calculate the difference in rtx costs that it produces, and add that value to *COST_DELTA. Decrement *INSN_DELTA for each instruction we want to delete and increment it for each instruction we want to add. */ static void rewrite_automod_chain (struct automod_chain *c, int *cost_delta, int *insn_delta) { struct ref_point *ref; unsigned HOST_WIDE_INT delta; ref = c->last; do { delta = get_automod_delta (ref, c->code); if (delta != 0) /* A REF_MEM that needs an automodification. */ *cost_delta += test_automodification (ref, c->code, c->base, GEN_INT (delta)); else if (discardable_chain_member_p (c, ref)) { /* A REF_ADD that is no longer needed. */ *cost_delta += test_ref_deletion (ref); *insn_delta -= 1; } else /* A REF_MEM or a REF_ADD that should use (but not modify) the current value of the base register. */ *cost_delta += rewrite_ref (ref, c->base); ref = get_prev_automod_ref (ref, c->code); } while (ref != c->stop); /* Set up the base register. */ if (c->move_p) { *cost_delta += test_move_before (c->first->insn, c->base, c->move_op0, c->move_op1_constant_p, &c->move_op1); *insn_delta += 1; } } /* We have tentatively applied automod chain C. Go through any overlapping references to the base register and try to adjust them by the appropriate amount. Return true on success, adding the difference in rtx costs to *COST_DELTA. */ static bool adjust_other_base_refs (struct automod_chain *c, int *cost_delta) { struct ref_point *base_ref, *chain_ref; unsigned HOST_WIDE_INT offset; rtx sum; /* Loop over all references to C->base_lr. Stop once we reach the beginning of C. */ offset = c->final_offset; base_ref = c->base_lr->last_base_ref; chain_ref = c->last; while (base_ref && chain_ref != c->stop) { /* See whether BASE_REF is the next member of C, or whether it comes before the next member of C. Move up C if so. */ if (base_ref == chain_ref || ref_order_p (base_ref, chain_ref)) { offset -= get_automod_delta (chain_ref, c->code); if (base_ref == chain_ref) base_ref = base_ref->prev_base_ref; chain_ref = get_prev_automod_ref (chain_ref, c->code); } /* Make sure that the new form is still representable. Converting REG1 + REG2 to REG1 + REG2 + OFFSET is likely to be a loss anyway. */ else if (!base_ref->const_offset_p) { if (dump_file) fprintf (dump_file, "\n;;\t%d applies a non-constant offset" " to r%d\n", INSN_UID (base_ref->insn), REGNO (c->base)); return false; } /* When optimizing for speed, don't introduce dependencies between memory references in the chain and memory references outside of it, since doing so would limit scheduling. If the chain is truly worthwhile, we can still try again using a new pseudo register. */ else if (base_ref->type == REF_MEM && optimize_bb_for_speed_p (current_bb)) { if (dump_file) fprintf (dump_file, "\n;;\tModifying %d would introduce new" " dependencies between memory references\n", INSN_UID (base_ref->insn)); return false; } /* Otherwise, BASE_REF is not part of C but is affected by it. C will have added OFFSET to the base register by now, so adjust the reference by -OFFSET. */ else { sum = get_adjusted_src (base_ref, -offset); *cost_delta += rewrite_ref (base_ref, sum); base_ref = base_ref->prev_base_ref; } } return true; } /* REF now uses live range BASE as its base. Remove REF from its old chain and add it to the beginning of BASE's. */ static void change_base_range (struct ref_point *ref, struct reg_live_range *base) { unlink_base_ref (ref); ref->base = base; add_base_ref_to_beginning (ref); } /* Commit all the changes made by automod chain C. */ static void commit_automod_chain (struct automod_chain *c) { struct ref_point *base_ref, *chain_ref, *prev_ref; struct reg_live_range *base, *new_base; /* Create a new live range for the final value of the base register. */ base = new_live_range (c->base, 0); /* Loop over every reference in the chain, and every overlapping reference to the original base register. BASE is the current live range of the base register. */ base_ref = (c->base_lr ? c->base_lr->last_base_ref : 0); chain_ref = c->last; do { /* If BASE_REF is part of the chain, just process it as a normal chain reference. */ if (base_ref == chain_ref) base_ref = base_ref->prev_base_ref; if (!base_ref || ref_order_p (base_ref, chain_ref)) { if (get_automod_delta (chain_ref, c->code) != 0) { /* A REF_MEM that needs an automodification. It defines BASE and uses and clobbers the register's previous value. Set BASE to the live range of that previous value, or to null if we don't need to track it. */ new_base = base; if (chain_ref != c->first) /* Create a live range for the previous base value. */ base = new_live_range (c->base, 0); else if (c->move_p) /* We need no live range to represent the value of the base register between the move and the immediately-following automodification. */ base = 0; else /* The first instruction uses the original value of the base register. */ base = c->base_lr; commit_automodification (chain_ref, base, new_base); } else if (discardable_chain_member_p (c, chain_ref)) /* A REF_ADD that is no longer needed. */ commit_ref_deletion (chain_ref); else { /* A passive member of the chain. It now has the form (mem (C->base)). */ change_base_range (chain_ref, base); chain_ref->const_offset_p = 1; chain_ref->offset.c = const0_rtx; } chain_ref = get_prev_automod_ref (chain_ref, c->code); } else { /* A reference to BASE whose value was adjusted by a constant offset. */ prev_ref = base_ref->prev_base_ref; change_base_range (base_ref, base); update_const_offset (base_ref); base_ref = prev_ref; } } while (chain_ref != c->stop); if (c->move_p) /* Emit the move before the first instruction in the chain. */ commit_move_before (c->first->insn, c->base_lr, c->base, c->move_op0, c->move_op1_constant_p, &c->move_op1); } /* Try to apply the automodification chain described by C, using C->base as the base register. */ static enum automod_chain_result apply_automod_chain_with_base (struct automod_chain *c) { struct ref_point *ref; int first_change, cost_delta, max_cost_delta, insn_delta; unsigned HOST_WIDE_INT offset; if (dump_file) fprintf (dump_file, "\n;;\tTrying a %s chain on %d, using r%d" " as the base register\n", GET_RTX_NAME (c->code), INSN_UID (c->last->insn), REGNO (c->base)); /* Check that the chain instructions have no incompatible uses of the base register. */ if (c->base_lr) for (ref = c->last; ref != c->stop; ref = get_prev_automod_ref (ref, c->code)) if ((get_automod_flags (ref, c->code) & MOD_HERE) && other_refs_in_insn_p (ref, c->base)) { if (dump_file) fprintf (dump_file, "\n;;\t%d refers to r%d in an incompatible" " way\n", INSN_UID (ref->insn), REGNO (c->base)); return AUTOMOD_BAD_BASE; } /* Decide whether we need a move before the start of the chain, and if so, what its operands should be. */ c->move_op1_constant_p = c->first->const_offset_p; c->move_op0 = c->first->base; c->move_op1 = c->first->offset; if (c->code == PRE_MODIFY) { /* C->move_op0 + C->move_op1 is the value after automodification. Calculate the value before automodification. */ gcc_assert (c->move_op1_constant_p); offset = UINTVAL (c->move_op1.c) - get_automod_delta (c->first, c->code); c->move_op1.c = gen_int_mode (offset, GET_MODE (c->move_op0->reg)); } c->move_p = !(rtx_equal_p (c->base, c->move_op0->reg) && c->move_op1_constant_p && c->move_op1.c == const0_rtx); /* Try the change on the chain itself. If this fails, assume that the chain itself is bad. */ cost_delta = 0; insn_delta = 0; rewrite_automod_chain (c, &cost_delta, &insn_delta); if (insn_delta < 0) { /* All other things being equal, prefer a sequence that has fewer instructions. */ max_cost_delta = 0; if (dump_file) fprintf (dump_file, ";;\tAllowing a 0 cost delta because there" " are fewer instructions\n"); } else if (get_reg_count_delta_for_chain (c) < 0) { /* Otherwise, prefer a sequence that has fewer register references. */ max_cost_delta = 0; if (dump_file) fprintf (dump_file, ";;\tAllowing a 0 cost delta because the" " chain replaces register offsets\n"); } else max_cost_delta = -1; if (!test_replacements (max_cost_delta, cost_delta, 0)) { cancel_changes (0); return AUTOMOD_BAD_CHAIN; } /* Now adjust any references to C->base in the affected range. This must not increase the cost; if it does, we'd prefer a different base register. */ if (c->base_lr) { if (dump_file) fprintf (dump_file, ";;\tAdjusting other uses of the base register\n"); first_change = num_changes_pending (); cost_delta = 0; if (!adjust_other_base_refs (c, &cost_delta) || !test_replacements (0, cost_delta, first_change)) { c->base_lr->tried_offset_mod_p = 1; cancel_changes (0); return AUTOMOD_BAD_BASE; } } /* Commit the changes. */ confirm_change_group (); commit_automod_chain (c); return AUTOMOD_OK; } /* Try to apply the automodification chain described by C. Return true on success. */ static bool apply_automod_chain (struct automod_chain *c) { struct ref_point *ref; struct reg_live_range *base1; unsigned int first_luid, last_luid; unsigned HOST_WIDE_INT offset, offset1; enum machine_mode mode; /* Look for existing registers that could be used as the base. Set BASE1 to the earliest such candidate. Set OFFSET1 to the offset that will be added to BASE1 by the chain. See the comment at the head of the file for details about how this base register is selected and used. While we're making a pass, also set up num_reg_offsets In this loop, OFFSET is the amount that will be added to the base register between REF and the end of the chain. */ offset = 0; offset1 = 0; base1 = 0; last_luid = consolidated_luid (c->last->insn); first_luid = consolidated_luid (c->first->insn); for (ref = c->last; ref != c->stop; ref = get_prev_automod_ref (ref, c->code)) { if (c->code == POST_MODIFY) offset += get_automod_delta (ref, c->code); if (ref->const_offset_p && !ref->base->tried_offset_mod_p && moveable_reg_p (ref->base->reg) && first_luid > ref->base->def_luid && first_luid > ref->base->last_untracked_luid && last_luid <= ref->base->next_def_luid) { base1 = ref->base; offset1 = offset + UINTVAL (ref->offset.c); } /* Don't count the first reference, since its address will be used to initialize the base register. */ if (ref != c->first && !ref->const_offset_p) c->num_reg_offsets++; if (c->code == PRE_MODIFY) offset += get_automod_delta (ref, c->code); } /* First try using BASE1. */ if (base1) { c->base_lr = base1; c->base = base1->reg; c->final_offset = trunc_int_for_mode (offset1, GET_MODE (base1->reg)); switch (apply_automod_chain_with_base (c)) { case AUTOMOD_OK: return true; case AUTOMOD_BAD_CHAIN: /* The chain just doesn't seem worthwhile. Don't bother trying any more variations. */ return false; case AUTOMOD_BAD_BASE: /* The change appeared to fail because of the choice of base register. Try again with a pseudo register. */ break; } } /* Get a base register of the appropriate mode. */ mode = GET_MODE (c->last->base->reg); if (!new_regs[(int) mode]) new_regs[(int) mode] = gen_reg_rtx (mode); /* Try using it. The final offset is arbitrary in this case. */ c->base_lr = 0; c->base = new_regs[(int) mode]; c->final_offset = 0; if (apply_automod_chain_with_base (c) == AUTOMOD_OK) { /* The register is now in use. Create a new one next time. */ new_regs[(int) mode] = 0; return true; } return false; } /* Try to optimize a postmod or premod chain ending at END. CODE selects the type of chain; either POST_MODIFY or PRE_MODIFY. */ static bool optimize_automod_chain (struct ref_point *end, enum rtx_code code) { struct automod_chain c; return describe_automod_chain (&c, end, code) && apply_automod_chain (&c); } /* REF1 comes before REF2. Return true if REF1 is an addition reference, REF2 is an automodifiable memory reference, and if the definition of REF1's destination can move down to REF2. */ static bool valid_add_mem_pair_p (struct ref_point *ref1, struct ref_point *ref2) { struct reg_live_range *base_lr; unsigned int luid2; if (ref1->type != REF_ADD || ref2->type != REF_MEM || !ref2->allow_automod_p) return false; base_lr = ref1->u.add.new_dest_range; if (!moveable_reg_p (base_lr->reg)) return false; luid2 = consolidated_luid (ref2->insn); if (other_uses_before_p (base_lr, 0, luid2)) /* REF1's destination is used before REF2. */ return false; if (other_refs_in_insn_p (ref2, base_lr->reg)) /* REF2 refers to REF1's destination outside the mem. */ return false; if (!other_uses_after_p (base_lr, 0, luid2)) /* REF2 is the only consumer of REF1, so nothing would use the modified value. */ return false; return true; } /* REF1 comes before REF2. Return true if REF1 is an automodifiable memory reference, REF2 is an addition reference, and if the definition of REF2's destination can move up to REF1. */ static bool valid_mem_add_pair_p (struct ref_point *ref1, struct ref_point *ref2) { struct reg_live_range *base_lr; unsigned int luid1; if (ref1->type != REF_MEM || ref2->type != REF_ADD || !ref1->allow_automod_p) return false; base_lr = ref2->u.add.old_dest_range; if (!moveable_reg_p (base_lr->reg)) return false; luid1 = consolidated_luid (ref1->insn); if (base_lr->def_luid >= luid1 || other_uses_after_p (base_lr, ref2, luid1)) /* The old value of REF2's destination is referenced between REF1 and REF2. (That is, there is a reference to the old value of REF2's definition after REF1, even if we exclude the source of REF2.) */ return false; if (other_refs_in_insn_p (ref1, base_lr->reg)) /* REF1 refers to REF2's destination outside the mem. */ return false; return true; } /* We have a pair of instructions: MEM_REF: *(RM + XM) ADD_REF: BASE = RA + XA which may appear in either order. OPERANDS_REF is one of these two instructions; let its rhs be RO + XO. CODE is either PRE_MODIFY or POST_MODIFY. The caller has already verified that pair is semantically equivalent to: [new] BASE = RO MEM_REF: *(CODE BASE + XO) Try to use the latter sequence, returning on true on success. */ static bool optimize_pair (struct ref_point *mem_ref, struct ref_point *add_ref, enum rtx_code code, struct ref_point *operands_ref) { rtx src1, src0_insn; struct reg_live_range *old_base, *new_base, *src0; union ref_offset zero_offset; int cost_delta, max_cost_delta; bool move_p; /* Avoid pointless automodifications by zero. */ if (zero_offset_p (operands_ref)) return false; if (dump_file) fprintf (dump_file, "\n;;\tTrying to optimize memref %d" " and addition %d using a %s\n", INSN_UID (mem_ref->insn), INSN_UID (add_ref->insn), GET_RTX_NAME (code)); /* Get the before and after live ranges for the base register. */ old_base = add_ref->u.add.old_dest_range; new_base = add_ref->u.add.new_dest_range; /* Get the rhs operands. */ src0 = operands_ref->base; src1 = get_ref_offset_rtx (operands_ref->const_offset_p, &operands_ref->offset); /* Decide where the new move should go. It's generally better to put it immediately before MEM_REF, in order to reduce the live range of the base register, and to increase the chances that the base register can be tied to SRC0. However, if SRC0 comes from an earlier ADD_REF, SRC0 might not live that long. */ if (lr_available_at_p (src0, consolidated_luid (mem_ref->insn))) src0_insn = mem_ref->insn; else { gcc_checking_assert (add_ref == operands_ref); gcc_checking_assert (ref_order_p (add_ref, mem_ref)); src0_insn = add_ref->insn; } /* By default, the change must be a strict improvement. */ max_cost_delta = -1; /* See whether we need a move at all. */ move_p = !rtx_equal_p (new_base->reg, src0->reg); zero_offset.c = const0_rtx; /* Tentatively make the changes and estimate their cost. */ cost_delta = test_automodification (mem_ref, code, new_base->reg, src1); cost_delta += test_ref_deletion (add_ref); if (!move_p) { /* A natural automodification, such as *R; R = R + N. */ max_cost_delta = 0; if (dump_file) fprintf (dump_file, ";;\tAllowing a 0 cost delta because there" " are fewer instructions\n"); } else if (!other_uses_after_p (src0, operands_ref, consolidated_luid (src0_insn))) { /* SRC0 will die in the move BASE <- SRC0. It's quite likely that we'll be able to allocate the same hard register to both BASE and SRC0. */ max_cost_delta = 0; if (dump_file) fprintf (dump_file, ";;\tIgnoring the cost of the move and allowing" " a 0 cost delta because the registers seem tieable\n"); } else { cost_delta += test_move_before (src0_insn, new_base->reg, src0, true, &zero_offset); if (operands_ref == add_ref ? !mem_ref->const_offset_p : !add_ref->const_offset_p) { /* We are removing a use of an offset register. All other things being equal, we might as well prefer the new version, since it gives other optimizers more freedom when dealing with that register. */ max_cost_delta = 0; if (dump_file) fprintf (dump_file, ";;\tAllowing a 0 cost delta because the" " change removes a register use\n"); } } if (!test_replacements (max_cost_delta, cost_delta, 0)) { cancel_changes (0); return false; } /* MEM_REF now uses the offset from OPERANDS_REF. */ if (!operands_ref->const_offset_p) record_live_range_use (operands_ref->offset.lr, consolidated_luid (mem_ref->insn)); /* Commit the changes. */ confirm_change_group (); commit_ref_deletion (add_ref); commit_automodification (mem_ref, move_p ? 0 : old_base, new_base); if (move_p) commit_move_before (src0_insn, old_base, old_base->reg, src0, true, &zero_offset); return true; } /* See whether there is an earlier reference to the same valno as REF2, and whether the two instructions can be optimized using automodifications. Return true on success. */ static bool optimize_same_valno (struct ref_point *ref2) { struct ref_point *ref1; struct reg_live_range *base_lr; ref1 = ref2->prev_valno_ref; if (ref1 && valid_add_mem_pair_p (ref1, ref2)) { /* We have: REF1: Y = R1 + X1 REF2: *(R2 + X2) where R1 + X1 at REF1 equals R2 + X2 at REF2. First try turning this into: [new] Y = R2 REF2: *(pre Y + X2) This is only possible if R2 + X2 does not use the value of Y set by REF1. */ base_lr = ref1->u.add.new_dest_range; if (base_lr != ref2->base && (ref2->const_offset_p || base_lr != ref2->offset.lr) && optimize_pair (ref2, ref1, PRE_MODIFY, ref2)) return true; /* Now try turning it into: [new] Y = R1 REF2: *(pre Y + X1) This is only possible if X1 has the same value at REF2 as it does at REF1. */ if (offset_available_at_p (ref1, ref2) && optimize_pair (ref2, ref1, PRE_MODIFY, ref1)) return true; } else if (ref1 && valid_mem_add_pair_p (ref1, ref2)) { /* We have: REF1: *(R1 + X1) REF2: Y = R2 + X2 where R1 + X1 at REF1 equals R2 + X2 at REF2. Try turning this into: [new] Y = R1 REF1: *(pre Y + X1). */ if (optimize_pair (ref1, ref2, PRE_MODIFY, ref1)) return true; } return false; } /* See whether there is an earlier reference to REF2's base, and whether the two instructions can be optimized using automodifications. Return true on success. */ static bool optimize_same_range (struct ref_point *ref2) { struct ref_point *ref1; ref1 = ref2->base->def; if (ref1 && valid_add_mem_pair_p (ref1, ref2)) { /* We have: REF1: Y = R1 + X1 REF2: *(Y + X2) If X2 == -X1, try turning this into: [new] Y = R1 REF2: *(post Y + X1). */ if (opposite_offsets_p (ref1, ref2) && optimize_pair (ref2, ref1, POST_MODIFY, ref1)) return true; } ref1 = ref2->prev_base_ref; if (ref1 && valid_add_mem_pair_p (ref1, ref2)) { if (zero_offset_p (ref2)) { /* We have: REF1: Y = R1 + X1 REF2: *R1 Try turning this into: [new] Y = R1 REF2: *(post Y + X1) This is only possible if X1 has the same value at REF2 as it does at REF1. */ if (offset_available_at_p (ref1, ref2) && optimize_pair (ref2, ref1, POST_MODIFY, ref1)) return true; } } else if (ref1 && valid_mem_add_pair_p (ref1, ref2)) { if (zero_offset_p (ref1)) { /* We have: REF1: *R REF2: Y = R + X2 Try turning this into: [new] Y = R REF1: *(post Y + X2) This is only possible if X2 has the same value at REF1 as it does at REF2. */ if (offset_available_at_p (ref2, ref1) && optimize_pair (ref1, ref2, POST_MODIFY, ref2)) return true; } } return false; } /* Optimize the current basic block based on the information recorded in bb_refs. */ static void optimize_refs (void) { struct ref_point *ref; /* First try premod and postmod chains, since they tend to give the greatest benefit. */ for (ref = bb_refs; ref; ref = ref->prev_ref) if (optimize_automod_chain (ref, POST_MODIFY) || optimize_automod_chain (ref, PRE_MODIFY)) continue; /* Now try optimizing individual pairs. */ for (ref = bb_refs; ref; ref = ref->prev_ref) if (optimize_same_range (ref) || optimize_same_valno (ref)) continue; } /* Perform auto-inc-dec optimizations in BB. */ static void merge_in_block (basic_block bb) { rtx insn, curr; unsigned int last_luid; void *obstack_start; if (dump_file) fprintf (dump_file, "\n\nStarting bb %d\n", bb->index); /* All live-range, valno and reference information is local to a block. */ current_bb = bb; bb_live_range_base += VEC_length (reg_live_range_ptr, live_ranges); bb_refs = 0; obstack_start = XOBNEWVAR (&bb_obstack, char, 0); VEC_truncate (reg_live_range_ptr, live_ranges, 0); /* Record information about this block. */ last_luid = bb_luid_base; FOR_BB_INSNS_SAFE (bb, insn, curr) if (NONDEBUG_INSN_P (insn)) { last_luid = consolidated_luid (insn); if (dump_file) { fprintf (dump_file, "\n"); dump_insn_slim (dump_file, insn); } if (!process_reg_arithmetic (insn)) process_mem_refs (insn); } record_live_regs (DF_LIVE_OUT (bb)); /* Optimize the block based on all recorded information. */ optimize_refs (); bb_luid_base = last_luid + 1; obstack_free (&bb_obstack, obstack_start); } /* Initialize the pass's global state. */ static void init_auto_inc_dec (void) { next_valno = 1; bb_live_range_base = 1; bb_luid_base = 1; regno_state = XCNEWVEC (struct regno_state_info, max_reg_num ()); gcc_obstack_init (&bb_obstack); memset (zeros, 0, sizeof (zeros)); memset (new_regs, 0, sizeof (new_regs)); test_set = 0; test_plus = 0; } /* Free the memory allocated during the pass. */ static void fini_auto_inc_dec (void) { VEC_free (reg_live_range_ptr, heap, live_ranges); XDELETEVEC (regno_state); } #endif /* Look for auto-inc and auto-dec opportunities. */ static unsigned int rest_of_handle_auto_inc_dec (void) { #ifdef AUTO_INC_DEC basic_block bb; init_auto_inc_dec (); if (optimize == 1) { df_live_add_problem (); df_live_set_all_dirty (); } df_analyze (); FOR_EACH_BB (bb) merge_in_block (bb); if (dbg_cnt (auto_inc_dec)) delete_trivially_dead_insns (get_insns (), max_reg_num ()); fini_auto_inc_dec (); #endif return 0; } static bool gate_auto_inc_dec (void) { #ifdef AUTO_INC_DEC return (optimize > 0 && flag_auto_inc_dec); #else return false; #endif } struct rtl_opt_pass pass_inc_dec = { { RTL_PASS, "auto_inc_dec", /* name */ gate_auto_inc_dec, /* gate */ rest_of_handle_auto_inc_dec, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ TV_AUTO_INC_DEC, /* tv_id */ 0, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_dump_func | TODO_df_finish, /* todo_flags_finish */ } };