You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This is the loop optimization pass of the compiler.
It finds invariant computations within loops and moves them
#include "optabs.h"
#include "cfgloop.h"
#include "ggc.h"
+#include "timevar.h"
+#include "tree-pass.h"
/* Get the loop info pointer of a loop. */
#define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux)
if (! in_libcall
&& (set = single_set (p))
&& REG_P (SET_DEST (set))
+ && SET_DEST (set) != frame_pointer_rtx
#ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
&& SET_DEST (set) != pic_offset_table_rtx
#endif
- with -Os (this certainly increases size),
- if the mode doesn't support copy operations (obviously),
- if the source is already a reg (the motion will gain nothing),
- - if the source is a legitimate constant (likewise). */
+ - if the source is a legitimate constant (likewise),
+ - if the dest is a hard register (may be unrecognizable). */
else if (insert_temp
&& (optimize_size
|| ! can_copy_p (GET_MODE (SET_SRC (set)))
|| REG_P (SET_SRC (set))
|| (CONSTANT_P (SET_SRC (set))
- && LEGITIMATE_CONSTANT_P (SET_SRC (set)))))
+ && LEGITIMATE_CONSTANT_P (SET_SRC (set)))
+ || REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER))
;
else if ((tem = loop_invariant_p (loop, src))
&& (dependencies == 0
{
struct movable *m;
int regno = REGNO (SET_DEST (set));
+ rtx user, user_set;
- /* A potential lossage is where we have a case where two insns
- can be combined as long as they are both in the loop, but
- we move one of them outside the loop. For large loops,
- this can lose. The most common case of this is the address
- of a function being called.
+ /* A potential lossage is where we have a case where two
+ insns can be combined as long as they are both in the
+ loop, but we move one of them outside the loop. For
+ large loops, this can lose. The most common case of
+ this is the address of a function being called.
Therefore, if this register is marked as being used
exactly once if we are in a loop with calls
this register with the source of this SET. If we can,
delete this insn.
- Don't do this if P has a REG_RETVAL note or if we have
- SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
+ Don't do this if:
+ (1) P has a REG_RETVAL note or
+ (2) if we have SMALL_REGISTER_CLASSES and
+ (a) SET_SRC is a hard register or
+ (b) the destination of the user is a hard register. */
if (loop_info->has_call
- && regs->array[regno].single_usage != 0
- && regs->array[regno].single_usage != const0_rtx
+ && regno >= FIRST_PSEUDO_REGISTER
+ && (user = regs->array[regno].single_usage) != NULL
+ && user != const0_rtx
&& REGNO_FIRST_UID (regno) == INSN_UID (p)
- && (REGNO_LAST_UID (regno)
- == INSN_UID (regs->array[regno].single_usage))
+ && REGNO_LAST_UID (regno) == INSN_UID (user)
&& regs->array[regno].set_in_loop == 1
&& GET_CODE (SET_SRC (set)) != ASM_OPERANDS
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
- && (! SMALL_REGISTER_CLASSES
- || (! (REG_P (SET_SRC (set))
- && (REGNO (SET_SRC (set))
- < FIRST_PSEUDO_REGISTER))))
- && regno >= FIRST_PSEUDO_REGISTER
+ && (!SMALL_REGISTER_CLASSES
+ || !REG_P (SET_SRC (set))
+ || !HARD_REGISTER_P (SET_SRC (set)))
+ && (!SMALL_REGISTER_CLASSES
+ || !NONJUMP_INSN_P (user)
+ || !(user_set = single_set (user))
+ || !REG_P (SET_DEST (user_set))
+ || !HARD_REGISTER_P (SET_DEST (user_set)))
/* This test is not redundant; SET_SRC (set) might be
a call-clobbered register and the life of REGNO
might span a call. */
- && ! modified_between_p (SET_SRC (set), p,
- regs->array[regno].single_usage)
- && no_labels_between_p (p,
- regs->array[regno].single_usage)
- && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
- regs->array[regno].single_usage))
+ && ! modified_between_p (SET_SRC (set), p, user)
+ && no_labels_between_p (p, user)
+ && validate_replace_rtx (SET_DEST (set),
+ SET_SRC (set), user))
{
/* Replace any usage in a REG_EQUAL note. Must copy
the new source, so that we don't get rtx sharing
between the SET_SOURCE and REG_NOTES of insn p. */
- REG_NOTES (regs->array[regno].single_usage)
- = (replace_rtx
- (REG_NOTES (regs->array[regno].single_usage),
- SET_DEST (set), copy_rtx (SET_SRC (set))));
+ REG_NOTES (user)
+ = replace_rtx (REG_NOTES (user), SET_DEST (set),
+ copy_rtx (SET_SRC (set)));
delete_insn (p);
for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set));
&& !m1->partial
&& (matched_regs[m1->regno]
||
- (
- /* Can combine regs with different modes loaded from the
- same constant only if the modes are the same or
- if both are integer modes with M wider or the same
- width as M1. The check for integer is redundant, but
- safe, since the only case of differing destination
- modes with equal sources is when both sources are
- VOIDmode, i.e., CONST_INT. */
- (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
- || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
- && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
- && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
- >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
+ (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
/* See if the source of M1 says it matches M. */
&& ((REG_P (m1->set_src)
&& matched_regs[REGNO (m1->set_src)])
if (GET_MODE (x) != GET_MODE (y))
return 0;
- /* These three types of rtx's can be compared nonrecursively. */
- if (code == REG)
- return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
+ /* These types of rtx's can be compared nonrecursively. */
+ switch (code)
+ {
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ return 0;
- if (code == LABEL_REF)
- return XEXP (x, 0) == XEXP (y, 0);
- if (code == SYMBOL_REF)
- return XSTR (x, 0) == XSTR (y, 0);
+ case REG:
+ return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
+
+ case LABEL_REF:
+ return XEXP (x, 0) == XEXP (y, 0);
+ case SYMBOL_REF:
+ return XSTR (x, 0) == XSTR (y, 0);
+
+ default:
+ break;
+ }
/* Compare the elements. If any pair of corresponding elements
fail to match, return 0 for the whole things. */
{
rtx temp;
- /* Schedule the reg loaded by M1
- for replacement so that shares the reg of M.
- If the modes differ (only possible in restricted
- circumstances, make a SUBREG.
-
- Note this assumes that the target dependent files
- treat REG and SUBREG equally, including within
- GO_IF_LEGITIMATE_ADDRESS and in all the
- predicates since we never verify that replacing the
- original register with a SUBREG results in a
- recognizable insn. */
- if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
- reg_map[m1->regno] = m->set_dest;
- else
- reg_map[m1->regno]
- = gen_lowpart_common (GET_MODE (m1->set_dest),
- m->set_dest);
+ reg_map[m1->regno] = m->set_dest;
/* Get rid of the matching insn
and prevent further processing of it. */
if (code != GET_CODE (y))
return 0;
+ if (GET_MODE (x) != GET_MODE (y))
+ return 0;
+
+ switch (code)
+ {
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ return 0;
+
+ case LABEL_REF:
+ return XEXP (x, 0) == XEXP (y, 0);
+
+ default:
+ break;
+ }
+
if (COMMUTATIVE_ARITH_P (x))
{
return ((rtx_equal_for_prefetch_p (XEXP (x, 0), XEXP (y, 0))
/* Not replaceable; emit an insn to set the original
giv reg from the reduced giv. */
else if (REG_P (*v->location))
- loop_insn_emit_before (loop, 0, v->insn,
- gen_move_insn (*v->location,
- v->new_reg));
+ {
+ rtx tem;
+ start_sequence ();
+ tem = force_operand (v->new_reg, *v->location);
+ if (tem != *v->location)
+ emit_move_insn (*v->location, tem);
+ tem = get_insns ();
+ end_sequence ();
+ loop_insn_emit_before (loop, 0, v->insn, tem);
+ }
else if (GET_CODE (*v->location) == PLUS
&& REG_P (XEXP (*v->location, 0))
&& CONSTANT_P (XEXP (*v->location, 1)))
- loop_insn_emit_before (loop, 0, v->insn,
- gen_move_insn (XEXP (*v->location, 0),
- gen_rtx_MINUS
- (GET_MODE (*v->location),
- v->new_reg,
- XEXP (*v->location, 1))));
+ {
+ rtx tem;
+ start_sequence ();
+ tem = expand_simple_binop (GET_MODE (*v->location), MINUS,
+ v->new_reg, XEXP (*v->location, 1),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ emit_move_insn (XEXP (*v->location, 0), tem);
+ tem = get_insns ();
+ end_sequence ();
+ loop_insn_emit_before (loop, 0, v->insn, tem);
+ }
else
{
/* If it wasn't a reg, create a pseudo and use that. */
rtx reg, seq;
start_sequence ();
reg = force_reg (v->mode, *v->location);
- seq = get_insns ();
- end_sequence ();
- loop_insn_emit_before (loop, 0, v->insn, seq);
- if (!validate_change_maybe_volatile (v->insn, v->location, reg))
- gcc_unreachable ();
+ if (validate_change_maybe_volatile (v->insn, v->location, reg))
+ {
+ seq = get_insns ();
+ end_sequence ();
+ loop_insn_emit_before (loop, 0, v->insn, seq);
+ }
+ else
+ {
+ end_sequence ();
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "unable to reduce iv in insn %d\n",
+ INSN_UID (v->insn));
+ bl->all_reduced = 0;
+ v->ignore = 1;
+ continue;
+ }
}
}
else if (v->replaceable)
}
+/* Return false iff it is provable that biv BL plus BIAS will not wrap
+ at any point in its update sequence. Note that at the rtl level we
+ may not have information about the signedness of BL; in that case,
+ check for both signed and unsigned overflow. */
+
+static bool
+biased_biv_may_wrap_p (const struct loop *loop, struct iv_class *bl,
+ unsigned HOST_WIDE_INT bias)
+{
+ HOST_WIDE_INT incr;
+ bool check_signed, check_unsigned;
+ enum machine_mode mode;
+
+ /* If the increment is not monotonic, we'd have to check separately
+ at each increment step. Not Worth It. */
+ incr = get_monotonic_increment (bl);
+ if (incr == 0)
+ return true;
+
+ /* If this biv is the loop iteration variable, then we may be able to
+ deduce a sign based on the loop condition. */
+ /* ??? This is not 100% reliable; consider an unsigned biv that is cast
+ to signed for the comparison. However, this same bug appears all
+ through loop.c. */
+ check_signed = check_unsigned = true;
+ if (bl->biv->src_reg == LOOP_INFO (loop)->iteration_var)
+ {
+ switch (LOOP_INFO (loop)->comparison_code)
+ {
+ case GTU: case GEU: case LTU: case LEU:
+ check_signed = false;
+ break;
+ case GT: case GE: case LT: case LE:
+ check_unsigned = false;
+ break;
+ default:
+ break;
+ }
+ }
+
+ mode = GET_MODE (bl->biv->src_reg);
+
+ if (check_unsigned
+ && !biased_biv_fits_mode_p (loop, bl, incr, mode, bias))
+ return true;
+
+ if (check_signed)
+ {
+ bias += (GET_MODE_MASK (mode) >> 1) + 1;
+ if (!biased_biv_fits_mode_p (loop, bl, incr, mode, bias))
+ return true;
+ }
+
+ return false;
+}
+
+
/* Given that X is an extension or truncation of BL, return true
if it is unaffected by overflow. LOOP is the loop to which
BL belongs and INCR is its per-iteration increment. */
else
break;
- if (CONSTANT_P (arg))
- {
- /* First try to replace with any giv that has constant positive
- mult_val and constant add_val. We might be able to support
- negative mult_val, but it seems complex to do it in general. */
-
- for (v = bl->giv; v; v = v->next_iv)
- if (GET_CODE (v->mult_val) == CONST_INT
- && INTVAL (v->mult_val) > 0
- && (GET_CODE (v->add_val) == SYMBOL_REF
- || GET_CODE (v->add_val) == LABEL_REF
- || GET_CODE (v->add_val) == CONST
- || (REG_P (v->add_val)
- && REG_POINTER (v->add_val)))
- && ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
- {
- if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
- continue;
-
- /* Don't eliminate if the linear combination that makes up
- the giv overflows when it is applied to ARG. */
- if (GET_CODE (arg) == CONST_INT)
- {
- rtx add_val;
-
- if (GET_CODE (v->add_val) == CONST_INT)
- add_val = v->add_val;
- else
- add_val = const0_rtx;
-
- if (const_mult_add_overflow_p (arg, v->mult_val,
- add_val, mode, 1))
- continue;
- }
-
- if (! eliminate_p)
- return 1;
-
- /* Replace biv with the giv's reduced reg. */
- validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
-
- /* If all constants are actually constant integers and
- the derived constant can be directly placed in the COMPARE,
- do so. */
- if (GET_CODE (arg) == CONST_INT
- && GET_CODE (v->add_val) == CONST_INT)
- {
- tem = expand_mult_add (arg, NULL_RTX, v->mult_val,
- v->add_val, mode, 1);
- }
- else
- {
- /* Otherwise, load it into a register. */
- tem = gen_reg_rtx (mode);
- loop_iv_add_mult_emit_before (loop, arg,
- v->mult_val, v->add_val,
- tem, where_bb, where_insn);
- }
-
- validate_change (insn, &XEXP (x, arg_operand), tem, 1);
-
- if (apply_change_group ())
- return 1;
- }
-
- /* Look for giv with positive constant mult_val and nonconst add_val.
- Insert insns to calculate new compare value.
- ??? Turn this off due to possible overflow. */
-
- for (v = bl->giv; v; v = v->next_iv)
- if (GET_CODE (v->mult_val) == CONST_INT
- && INTVAL (v->mult_val) > 0
- && ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode
- && 0)
- {
- rtx tem;
-
- if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
- continue;
-
- if (! eliminate_p)
- return 1;
-
- tem = gen_reg_rtx (mode);
-
- /* Replace biv with giv's reduced register. */
- validate_change (insn, &XEXP (x, 1 - arg_operand),
- v->new_reg, 1);
-
- /* Compute value to compare against. */
- loop_iv_add_mult_emit_before (loop, arg,
- v->mult_val, v->add_val,
- tem, where_bb, where_insn);
- /* Use it in this insn. */
- validate_change (insn, &XEXP (x, arg_operand), tem, 1);
- if (apply_change_group ())
- return 1;
- }
- }
- else if (REG_P (arg) || MEM_P (arg))
- {
- if (loop_invariant_p (loop, arg) == 1)
- {
- /* Look for giv with constant positive mult_val and nonconst
- add_val. Insert insns to compute new compare value.
- ??? Turn this off due to possible overflow. */
-
- for (v = bl->giv; v; v = v->next_iv)
- if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
- && ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode
- && 0)
- {
- rtx tem;
-
- if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
- continue;
-
- if (! eliminate_p)
- return 1;
-
- tem = gen_reg_rtx (mode);
-
- /* Replace biv with giv's reduced register. */
- validate_change (insn, &XEXP (x, 1 - arg_operand),
- v->new_reg, 1);
-
- /* Compute value to compare against. */
- loop_iv_add_mult_emit_before (loop, arg,
- v->mult_val, v->add_val,
- tem, where_bb, where_insn);
- validate_change (insn, &XEXP (x, arg_operand), tem, 1);
- if (apply_change_group ())
- return 1;
- }
- }
-
- /* This code has problems. Basically, you can't know when
- seeing if we will eliminate BL, whether a particular giv
- of ARG will be reduced. If it isn't going to be reduced,
- we can't eliminate BL. We can try forcing it to be reduced,
- but that can generate poor code.
+ if (GET_CODE (arg) != CONST_INT)
+ return 0;
- The problem is that the benefit of reducing TV, below should
- be increased if BL can actually be eliminated, but this means
- we might have to do a topological sort of the order in which
- we try to process biv. It doesn't seem worthwhile to do
- this sort of thing now. */
+ /* Unless we're dealing with an equality comparison, if we can't
+ determine that the original biv doesn't wrap, then we must not
+ apply the transformation. */
+ /* ??? Actually, what we must do is verify that the transformed
+ giv doesn't wrap. But the general case of this transformation
+ was disabled long ago due to wrapping problems, and there's no
+ point reviving it this close to end-of-life for loop.c. The
+ only case still enabled is known (via the check on add_val) to
+ be pointer arithmetic, which in theory never overflows for
+ valid programs. */
+ /* Without lifetime analysis, we don't know how COMPARE will be
+ used, so we must assume the worst. */
+ if (code != EQ && code != NE
+ && biased_biv_may_wrap_p (loop, bl, INTVAL (arg)))
+ return 0;
-#if 0
- /* Otherwise the reg compared with had better be a biv. */
- if (!REG_P (arg)
- || REG_IV_TYPE (ivs, REGNO (arg)) != BASIC_INDUCT)
- return 0;
+ /* Try to replace with any giv that has constant positive mult_val
+ and a pointer add_val. */
+ for (v = bl->giv; v; v = v->next_iv)
+ if (GET_CODE (v->mult_val) == CONST_INT
+ && INTVAL (v->mult_val) > 0
+ && (GET_CODE (v->add_val) == SYMBOL_REF
+ || GET_CODE (v->add_val) == LABEL_REF
+ || GET_CODE (v->add_val) == CONST
+ || (REG_P (v->add_val) && REG_POINTER (v->add_val)))
+ && ! v->ignore && ! v->maybe_dead && v->always_computable
+ && v->mode == mode)
+ {
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
+ continue;
- /* Look for a pair of givs, one for each biv,
- with identical coefficients. */
- for (v = bl->giv; v; v = v->next_iv)
- {
- struct induction *tv;
+ if (! eliminate_p)
+ return 1;
- if (v->ignore || v->maybe_dead || v->mode != mode)
- continue;
+ /* Replace biv with the giv's reduced reg. */
+ validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
- for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
- tv = tv->next_iv)
- if (! tv->ignore && ! tv->maybe_dead
- && rtx_equal_p (tv->mult_val, v->mult_val)
- && rtx_equal_p (tv->add_val, v->add_val)
- && tv->mode == mode)
- {
- if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
- continue;
+ /* Load the value into a register. */
+ tem = gen_reg_rtx (mode);
+ loop_iv_add_mult_emit_before (loop, arg, v->mult_val, v->add_val,
+ tem, where_bb, where_insn);
- if (! eliminate_p)
- return 1;
+ validate_change (insn, &XEXP (x, arg_operand), tem, 1);
- /* Replace biv with its giv's reduced reg. */
- XEXP (x, 1 - arg_operand) = v->new_reg;
- /* Replace other operand with the other giv's
- reduced reg. */
- XEXP (x, arg_operand) = tv->new_reg;
- return 1;
- }
- }
-#endif
- }
+ if (apply_change_group ())
+ return 1;
+ }
/* If we get here, the biv can't be eliminated. */
return 0;
}
if (flag_float_store && written
- && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
+ && SCALAR_FLOAT_MODE_P (GET_MODE (mem)))
loop_info->mems[i].optimize = 0;
/* If this MEM is written to, we must be sure that there
{
flow_loops_dump (loops, stderr, loop_dump_aux, 1);
}
+\f
+static bool
+gate_handle_loop_optimize (void)
+{
+ return (optimize > 0 && flag_loop_optimize);
+}
+
+/* Move constant computations out of loops. */
+static void
+rest_of_handle_loop_optimize (void)
+{
+ int do_prefetch;
+
+ /* CFG is no longer maintained up-to-date. */
+ free_bb_for_insn ();
+ profile_status = PROFILE_ABSENT;
+
+ do_prefetch = flag_prefetch_loop_arrays ? LOOP_PREFETCH : 0;
+
+ if (flag_rerun_loop_opt)
+ {
+ cleanup_barriers ();
+
+ /* We only want to perform unrolling once. */
+ loop_optimize (get_insns (), dump_file, 0);
+
+ /* The first call to loop_optimize makes some instructions
+ trivially dead. We delete those instructions now in the
+ hope that doing so will make the heuristics in loop work
+ better and possibly speed up compilation. */
+ delete_trivially_dead_insns (get_insns (), max_reg_num ());
+
+ /* The regscan pass is currently necessary as the alias
+ analysis code depends on this information. */
+ reg_scan (get_insns (), max_reg_num ());
+ }
+ cleanup_barriers ();
+ loop_optimize (get_insns (), dump_file, do_prefetch);
+
+ /* Loop can create trivially dead instructions. */
+ delete_trivially_dead_insns (get_insns (), max_reg_num ());
+ find_basic_blocks (get_insns ());
+}
+
+struct tree_opt_pass pass_loop_optimize =
+{
+ "old-loop", /* name */
+ gate_handle_loop_optimize, /* gate */
+ rest_of_handle_loop_optimize, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_LOOP, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'L' /* letter */
+};
+
+
OSDN Git Service
