This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for PR 18316
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 2 Feb 2005 09:55:34 +0100
- Subject: [patch] for PR 18316
Hello,
this patch adds an ability to handle ivs with nonconstant (but loop
invariant) steps to ivopts. This is one of the optimizations old
loop optimizer handles, but ivopts do not. Not urgent, probably not
suitable for this stage of development, posting here mostly to keep
track of the patch.
Bootstrapped & regtested on i686 and ia64.
Zdenek
PR tree-optimization/18316
* tree-scalar-evolution.c (simple_iv): Add allow_nonconstant_step
argument.
(add_to_evolution): Use correct constant
for -1.
* tree-scalar-evolution.h (simple_iv): Declaration changed.
* tree-ssa-loop-ivopts.c (struct iv_cand): Add depends_on
field.
(dump_cand): Dump depends_on information.
(determine_biv_step): Add argument to simple_iv call.
(contains_abnormal_ssa_name_p): Handle case expr == NULL.
(find_bivs, find_givs_in_stmt_scev): Do not require step to be a
constant.
(add_candidate_1): Record depends_on for candidates.
(tree_int_cst_sign_bit, constant_multiple_of): New functions.
(get_computation_at, get_computation_cost_at, may_eliminate_iv):
Handle ivs with nonconstant step.
(iv_ca_set_remove_invariants, iv_ca_set_add_invariants): New functions.
(iv_ca_set_no_cp, iv_ca_set_cp): Handle cand->depends_on.
(create_new_iv): Unshare the step before passing it to create_iv.
(free_loop_data): Free cand->depends_on.
* tree-ssa-loop-manip.c (create_iv): Handle ivs with nonconstant step.
* tree-ssa-loop-niter.c (number_of_iterations_exit): Add argument
to simple_iv call.
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-scalar-evolution.c
*** tree-scalar-evolution.c 18 Jan 2005 11:36:26 -0000 2.16
--- tree-scalar-evolution.c 1 Feb 2005 23:12:38 -0000
*************** add_to_evolution (unsigned loop_nb,
*** 894,901 ****
}
if (code == MINUS_EXPR)
! to_add = chrec_fold_multiply (type, to_add,
! build_int_cst_type (type, -1));
res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
--- 894,903 ----
}
if (code == MINUS_EXPR)
! {
! tree minusone = build_low_bits_mask (type, TYPE_PRECISION (type));
! to_add = chrec_fold_multiply (type, to_add, minusone);
! }
res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
*************** scev_reset (void)
*** 2496,2505 ****
}
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
! its BASE and STEP if possible. */
bool
! simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
--- 2498,2510 ----
}
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
! its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
! want STEP to be invariant in LOOP. Otherwise we require it to be an
! integer constant. */
bool
! simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
! bool allow_nonconstant_step)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
*************** simple_iv (struct loop *loop, tree stmt,
*** 2528,2535 ****
return false;
*step = CHREC_RIGHT (ev);
! if (TREE_CODE (*step) != INTEGER_CST)
! return false;
*base = CHREC_LEFT (ev);
if (tree_contains_chrecs (*base)
|| chrec_contains_symbols_defined_in_loop (*base, loop->num))
--- 2533,2550 ----
return false;
*step = CHREC_RIGHT (ev);
! if (allow_nonconstant_step)
! {
! if (tree_contains_chrecs (*step)
! || chrec_contains_symbols_defined_in_loop (*step, loop->num))
! return false;
! }
! else
! {
! if (TREE_CODE (*step) != INTEGER_CST)
! return false;
! }
!
*base = CHREC_LEFT (ev);
if (tree_contains_chrecs (*base)
|| chrec_contains_symbols_defined_in_loop (*base, loop->num))
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.h,v
retrieving revision 2.3
diff -c -3 -p -r2.3 tree-scalar-evolution.h
*** tree-scalar-evolution.h 17 Nov 2004 22:06:00 -0000 2.3
--- tree-scalar-evolution.h 1 Feb 2005 23:12:38 -0000
*************** extern tree analyze_scalar_evolution (st
*** 32,37 ****
extern tree instantiate_parameters (struct loop *, tree);
extern void gather_stats_on_scev_database (void);
extern void scev_analysis (void);
! extern bool simple_iv (struct loop *, tree, tree, tree *, tree *);
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
--- 32,37 ----
extern tree instantiate_parameters (struct loop *, tree);
extern void gather_stats_on_scev_database (void);
extern void scev_analysis (void);
! extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool);
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.42
diff -c -3 -p -r2.42 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 19 Jan 2005 22:50:04 -0000 2.42
--- tree-ssa-loop-ivopts.c 1 Feb 2005 23:12:38 -0000
*************** struct iv_cand
*** 190,195 ****
--- 190,197 ----
to replace the final value of an iv by direct
computation of the value. */
unsigned cost; /* Cost of the candidate. */
+ bitmap depends_on; /* The list of invariants that are used in step of the
+ biv. */
};
/* The data used by the induction variable optimizations. */
*************** dump_cand (FILE *file, struct iv_cand *c
*** 480,485 ****
--- 482,493 ----
fprintf (file, "candidate %d%s\n",
cand->id, cand->important ? " (important)" : "");
+ if (cand->depends_on)
+ {
+ fprintf (file, " depends on ");
+ dump_bitmap (file, cand->depends_on);
+ }
+
if (!iv)
{
fprintf (file, " final value replacement\n");
*************** get_iv (struct ivopts_data *data, tree v
*** 767,789 ****
return name_info (data, var)->iv;
}
! /* Determines the step of a biv defined in PHI. */
static tree
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
tree name = PHI_RESULT (phi), base, step;
- tree type = TREE_TYPE (name);
if (!is_gimple_reg (name))
return NULL_TREE;
! if (!simple_iv (loop, phi, name, &base, &step))
return NULL_TREE;
! if (!step)
! return build_int_cst (type, 0);
return step;
}
--- 775,797 ----
return name_info (data, var)->iv;
}
! /* Determines the step of a biv defined in PHI. Returns NULL if PHI does
! not define a simple affine biv with nonzero step. */
static tree
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
tree name = PHI_RESULT (phi), base, step;
if (!is_gimple_reg (name))
return NULL_TREE;
! if (!simple_iv (loop, phi, name, &base, &step, true))
return NULL_TREE;
! if (zero_p (step))
! return NULL_TREE;
return step;
}
*************** idx_contains_abnormal_ssa_name_p (tree b
*** 826,834 ****
static bool
contains_abnormal_ssa_name_p (tree expr)
{
! enum tree_code code = TREE_CODE (expr);
! enum tree_code_class class = TREE_CODE_CLASS (code);
!
if (code == SSA_NAME)
return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
--- 834,848 ----
static bool
contains_abnormal_ssa_name_p (tree expr)
{
! enum tree_code code;
! enum tree_code_class class;
!
! if (!expr)
! return false;
!
! code = TREE_CODE (expr);
! class = TREE_CODE_CLASS (code);
!
if (code == SSA_NAME)
return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0;
*************** find_bivs (struct ivopts_data *data)
*** 877,901 ****
continue;
step = determine_biv_step (phi);
-
if (!step)
continue;
- if (cst_and_fits_in_hwi (step)
- && int_cst_value (step) == 0)
- continue;
base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
! if (contains_abnormal_ssa_name_p (base))
continue;
type = TREE_TYPE (PHI_RESULT (phi));
base = fold_convert (type, base);
! step = fold_convert (type, step);
!
! /* FIXME: We do not handle induction variables whose step does
! not satisfy cst_and_fits_in_hwi. */
! if (!cst_and_fits_in_hwi (step))
! continue;
set_iv (data, PHI_RESULT (phi), base, step);
found = true;
--- 891,908 ----
continue;
step = determine_biv_step (phi);
if (!step)
continue;
base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
! if (contains_abnormal_ssa_name_p (base)
! || contains_abnormal_ssa_name_p (step))
continue;
type = TREE_TYPE (PHI_RESULT (phi));
base = fold_convert (type, base);
! if (step)
! step = fold_convert (type, step);
set_iv (data, PHI_RESULT (phi), base, step);
found = true;
*************** find_givs_in_stmt_scev (struct ivopts_da
*** 956,971 ****
if (TREE_CODE (lhs) != SSA_NAME)
return false;
! if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step))
return false;
! /* FIXME: We do not handle induction variables whose step does
! not satisfy cst_and_fits_in_hwi. */
! if (!zero_p (*step)
! && !cst_and_fits_in_hwi (*step))
! return false;
!
! if (contains_abnormal_ssa_name_p (*base))
return false;
return true;
--- 963,973 ----
if (TREE_CODE (lhs) != SSA_NAME)
return false;
! if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true))
return false;
! if (contains_abnormal_ssa_name_p (*base)
! || contains_abnormal_ssa_name_p (*step))
return false;
return true;
*************** find_interesting_uses (struct ivopts_dat
*** 1675,1680 ****
--- 1677,1706 ----
free (body);
}
+ /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
+ the bitmap to that we should store it. */
+
+ static struct ivopts_data *fd_ivopts_data;
+ static tree
+ find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
+ {
+ bitmap *depends_on = data;
+ struct version_info *info;
+
+ if (TREE_CODE (*expr_p) != SSA_NAME)
+ return NULL_TREE;
+ info = name_info (fd_ivopts_data, *expr_p);
+
+ if (!info->inv_id || info->has_nonlin_use)
+ return NULL_TREE;
+
+ if (!*depends_on)
+ *depends_on = BITMAP_XMALLOC ();
+ bitmap_set_bit (*depends_on, info->inv_id);
+
+ return NULL_TREE;
+ }
+
/* Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and
position to POS. If USE is not NULL, the candidate is set as related to
it. If both BASE and STEP are NULL, we add a pseudocandidate for the
*************** add_candidate_1 (struct ivopts_data *dat
*** 1757,1762 ****
--- 1783,1795 ----
cand->incremented_at = incremented_at;
VARRAY_PUSH_GENERIC_PTR_NOGC (data->iv_candidates, cand);
+ if (step
+ && TREE_CODE (step) != INTEGER_CST)
+ {
+ fd_ivopts_data = data;
+ walk_tree (&step, find_depends, &cand->depends_on, NULL);
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_cand (dump_file, cand);
}
*************** var_at_stmt (struct loop *loop, struct i
*** 2309,2314 ****
--- 2342,2446 ----
return cand->var_before;
}
+ /* Return the most significant (sign) bit of T. Similar to tree_int_cst_msb,
+ but the bit is determined from TYPE_PRECISION, not MODE_BITSIZE. */
+
+ static int
+ tree_int_cst_sign_bit (tree t)
+ {
+ unsigned bitno = TYPE_PRECISION (TREE_TYPE (t)) - 1;
+ unsigned HOST_WIDE_INT w;
+
+ if (bitno < HOST_BITS_PER_WIDE_INT)
+ w = TREE_INT_CST_LOW (t);
+ else
+ {
+ w = TREE_INT_CST_HIGH (t);
+ bitno -= HOST_BITS_PER_WIDE_INT;
+ }
+
+ return (w >> bitno) & 1;
+ }
+
+ /* If we can prove that TOP = cst * BOT for some constant cst in TYPE,
+ return cst. Otherwise return NULL_TREE. */
+
+ static tree
+ constant_multiple_of (tree type, tree top, tree bot)
+ {
+ tree res, mby, p0, p1;
+ enum tree_code code;
+ bool negate;
+
+ STRIP_NOPS (top);
+ STRIP_NOPS (bot);
+
+ if (operand_equal_p (top, bot, 0))
+ return build_int_cst (type, 1);
+
+ code = TREE_CODE (top);
+ switch (code)
+ {
+ case MULT_EXPR:
+ mby = TREE_OPERAND (top, 1);
+ if (TREE_CODE (mby) != INTEGER_CST)
+ return NULL_TREE;
+
+ res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
+ if (!res)
+ return NULL_TREE;
+
+ return fold_binary_to_constant (MULT_EXPR, type, res,
+ fold_convert (type, mby));
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
+ if (!p0)
+ return NULL_TREE;
+ p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
+ if (!p1)
+ return NULL_TREE;
+
+ return fold_binary_to_constant (code, type, p0, p1);
+
+ case INTEGER_CST:
+ if (TREE_CODE (bot) != INTEGER_CST)
+ return NULL_TREE;
+
+ bot = fold_convert (type, bot);
+ top = fold_convert (type, top);
+
+ /* If BOT seems to be negative, try dividing by -BOT instead, and negate
+ the result afterwards. */
+ if (tree_int_cst_sign_bit (bot))
+ {
+ negate = true;
+ bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
+ }
+ else
+ negate = false;
+
+ /* Ditto for TOP. */
+ if (tree_int_cst_sign_bit (top))
+ {
+ negate = !negate;
+ top = fold_unary_to_constant (NEGATE_EXPR, type, top);
+ }
+
+ if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
+ return NULL_TREE;
+
+ res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
+ if (negate)
+ res = fold_unary_to_constant (NEGATE_EXPR, type, res);
+ return res;
+
+ default:
+ return NULL_TREE;
+ }
+ }
+
/* Determines the expression by that USE is expressed from induction variable
CAND at statement AT in LOOP. */
*************** get_computation_at (struct loop *loop,
*** 2357,2375 ****
cstep = fold_convert (uutype, cstep);
}
! if (!cst_and_fits_in_hwi (cstep)
! || !cst_and_fits_in_hwi (ustep))
! return NULL_TREE;
! ustepi = int_cst_value (ustep);
! cstepi = int_cst_value (cstep);
! if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
{
! /* TODO maybe consider case when ustep divides cstep and the ratio is
! a power of 2 (so that the division is fast to execute)? We would
! need to be much more careful with overflows etc. then. */
! return NULL_TREE;
}
/* We may need to shift the value if we are after the increment. */
--- 2489,2529 ----
cstep = fold_convert (uutype, cstep);
}
! if (cst_and_fits_in_hwi (cstep)
! && cst_and_fits_in_hwi (ustep))
! {
! ustepi = int_cst_value (ustep);
! cstepi = int_cst_value (cstep);
! if (!divide (TYPE_PRECISION (uutype), ustepi, cstepi, &ratioi))
! {
! /* TODO maybe consider case when ustep divides cstep and the ratio is
! a power of 2 (so that the division is fast to execute)? We would
! need to be much more careful with overflows etc. then. */
! return NULL_TREE;
! }
! ratio = build_int_cst_type (uutype, ratioi);
! }
! else
{
! ratio = constant_multiple_of (uutype, ustep, cstep);
! if (!ratio)
! return NULL_TREE;
!
! /* Ratioi is only used to detect special cases when the multiplicative
! factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
! we may set it to 0. We prefer cst_and_fits_in_hwi/int_cst_value
! to integer_onep/integer_all_onesp, since the former ignores
! TREE_OVERFLOW. */
! if (cst_and_fits_in_hwi (ratio))
! ratioi = int_cst_value (ratio);
! else if (integer_onep (ratio))
! ratioi = 1;
! else if (integer_all_onesp (ratio))
! ratioi = -1;
! else
! ratioi = 0;
}
/* We may need to shift the value if we are after the increment. */
*************** get_computation_at (struct loop *loop,
*** 2393,2399 ****
}
else if (TREE_CODE (cbase) == INTEGER_CST)
{
- ratio = build_int_cst_type (uutype, ratioi);
delta = fold (build2 (MULT_EXPR, uutype, ratio, cbase));
delta = fold (build2 (MINUS_EXPR, uutype, ubase, delta));
expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
--- 2547,2552 ----
*************** get_computation_at (struct loop *loop,
*** 2402,2408 ****
else
{
expr = fold (build2 (MINUS_EXPR, uutype, expr, cbase));
- ratio = build_int_cst_type (uutype, ratioi);
expr = fold (build2 (MULT_EXPR, uutype, ratio, expr));
expr = fold (build2 (PLUS_EXPR, uutype, ubase, expr));
}
--- 2555,2560 ----
*************** get_address_cost (bool symbol_present, b
*** 2715,2745 ****
return cost + acost;
}
-
- /* Records invariants in *EXPR_P. Callback for walk_tree. DATA contains
- the bitmap to that we should store it. */
-
- static struct ivopts_data *fd_ivopts_data;
- static tree
- find_depends (tree *expr_p, int *ws ATTRIBUTE_UNUSED, void *data)
- {
- bitmap *depends_on = data;
- struct version_info *info;
-
- if (TREE_CODE (*expr_p) != SSA_NAME)
- return NULL_TREE;
- info = name_info (fd_ivopts_data, *expr_p);
-
- if (!info->inv_id || info->has_nonlin_use)
- return NULL_TREE;
-
- if (!*depends_on)
- *depends_on = BITMAP_XMALLOC ();
- bitmap_set_bit (*depends_on, info->inv_id);
-
- return NULL_TREE;
- }
-
/* Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the
invariants the computation depends on. */
--- 2867,2872 ----
*************** get_computation_cost_at (struct ivopts_d
*** 3050,3078 ****
return INFTY;
}
- if (!cst_and_fits_in_hwi (ustep)
- || !cst_and_fits_in_hwi (cstep))
- return INFTY;
-
- if (TREE_CODE (ubase) == INTEGER_CST
- && !cst_and_fits_in_hwi (ubase))
- goto fallback;
-
- if (TREE_CODE (cbase) == INTEGER_CST
- && !cst_and_fits_in_hwi (cbase))
- goto fallback;
-
- ustepi = int_cst_value (ustep);
- cstepi = int_cst_value (cstep);
-
if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
}
! if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
! return INFTY;
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
--- 3177,3225 ----
return INFTY;
}
if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
{
/* TODO -- add direct handling of this case. */
goto fallback;
}
! /* CSTEPI is removed from the offset in case statement is after the
! increment. If the step is not constant, we use zero instead.
! This is a bit inprecise (there is the extra addition), but
! redundancy elimination is likely to transform the code so that
! it uses value of the variable before increment anyway,
! so it is not that much unrealistic. */
! if (cst_and_fits_in_hwi (cstep))
! cstepi = int_cst_value (cstep);
! else
! cstepi = 0;
!
! if (cst_and_fits_in_hwi (ustep)
! && cst_and_fits_in_hwi (cstep))
! {
! ustepi = int_cst_value (ustep);
!
! if (!divide (TYPE_PRECISION (utype), ustepi, cstepi, &ratio))
! return INFTY;
! }
! else
! {
! tree rat;
!
! rat = constant_multiple_of (utype, ustep, cstep);
!
! if (!rat)
! return INFTY;
!
! if (cst_and_fits_in_hwi (rat))
! ratio = int_cst_value (rat);
! else if (integer_onep (rat))
! ratio = 1;
! else if (integer_all_onesp (rat))
! ratio = -1;
! else
! return INFTY;
! }
/* use = ubase + ratio * (var - cbase). If either cbase is a constant
or ratio == 1, it is better to handle this like
*************** get_computation_cost_at (struct ivopts_d
*** 3081,3087 ****
(also holds in the case ratio == -1, TODO. */
! if (TREE_CODE (cbase) == INTEGER_CST)
{
offset = - ratio * int_cst_value (cbase);
cost += difference_cost (data,
--- 3228,3234 ----
(also holds in the case ratio == -1, TODO. */
! if (cst_and_fits_in_hwi (cbase))
{
offset = - ratio * int_cst_value (cbase);
cost += difference_cost (data,
*************** may_eliminate_iv (struct loop *loop,
*** 3250,3256 ****
edge exit;
struct tree_niter_desc niter, new_niter;
tree wider_type, type, base;
!
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
ex_bb = bb_for_stmt (use->stmt);
--- 3397,3406 ----
edge exit;
struct tree_niter_desc niter, new_niter;
tree wider_type, type, base;
!
! if (TREE_CODE (cand->iv->step) != INTEGER_CST)
! return false;
!
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
ex_bb = bb_for_stmt (use->stmt);
*************** iv_ca_recount_cost (struct ivopts_data *
*** 3720,3735 ****
ivs->cost = cost;
}
/* Set USE not to be expressed by any candidate in IVS. */
static void
iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
! unsigned uid = use->id, cid, iid;
! bitmap deps;
struct cost_pair *cp;
- bitmap_iterator bi;
cp = ivs->cand_for_use[uid];
if (!cp)
--- 3870,3902 ----
ivs->cost = cost;
}
+ /* Remove invariants in set INVS to set IVS. */
+
+ static void
+ iv_ca_set_remove_invariants (struct iv_ca *ivs, bitmap invs)
+ {
+ bitmap_iterator bi;
+ unsigned iid;
+
+ if (!invs)
+ return;
+
+ EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
+ {
+ ivs->n_invariant_uses[iid]--;
+ if (ivs->n_invariant_uses[iid] == 0)
+ ivs->n_regs--;
+ }
+ }
+
/* Set USE not to be expressed by any candidate in IVS. */
static void
iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use)
{
! unsigned uid = use->id, cid;
struct cost_pair *cp;
cp = ivs->cand_for_use[uid];
if (!cp)
*************** iv_ca_set_no_cp (struct ivopts_data *dat
*** 3748,3770 ****
ivs->n_regs--;
ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
}
ivs->cand_use_cost -= cp->cost;
! deps = cp->depends_on;
! if (deps)
{
! EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
! {
! ivs->n_invariant_uses[iid]--;
! if (ivs->n_invariant_uses[iid] == 0)
! ivs->n_regs--;
! }
}
-
- iv_ca_recount_cost (data, ivs);
}
/* Set cost pair for USE in set IVS to CP. */
--- 3915,3947 ----
ivs->n_regs--;
ivs->n_cands--;
ivs->cand_cost -= cp->cand->cost;
+
+ iv_ca_set_remove_invariants (ivs, cp->cand->depends_on);
}
ivs->cand_use_cost -= cp->cost;
! iv_ca_set_remove_invariants (ivs, cp->depends_on);
! iv_ca_recount_cost (data, ivs);
! }
!
! /* Add invariants in set INVS to set IVS. */
! static void
! iv_ca_set_add_invariants (struct iv_ca *ivs, bitmap invs)
! {
! bitmap_iterator bi;
! unsigned iid;
!
! if (!invs)
! return;
!
! EXECUTE_IF_SET_IN_BITMAP (invs, 0, iid, bi)
{
! ivs->n_invariant_uses[iid]++;
! if (ivs->n_invariant_uses[iid] == 1)
! ivs->n_regs++;
}
}
/* Set cost pair for USE in set IVS to CP. */
*************** static void
*** 3773,3781 ****
iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use, struct cost_pair *cp)
{
! unsigned uid = use->id, cid, iid;
! bitmap deps;
! bitmap_iterator bi;
if (ivs->cand_for_use[uid] == cp)
return;
--- 3950,3956 ----
iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs,
struct iv_use *use, struct cost_pair *cp)
{
! unsigned uid = use->id, cid;
if (ivs->cand_for_use[uid] == cp)
return;
*************** iv_ca_set_cp (struct ivopts_data *data,
*** 3798,3819 ****
ivs->n_regs++;
ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
- }
-
- ivs->cand_use_cost += cp->cost;
! deps = cp->depends_on;
!
! if (deps)
! {
! EXECUTE_IF_SET_IN_BITMAP (deps, 0, iid, bi)
! {
! ivs->n_invariant_uses[iid]++;
! if (ivs->n_invariant_uses[iid] == 1)
! ivs->n_regs++;
! }
}
iv_ca_recount_cost (data, ivs);
}
}
--- 3973,3984 ----
ivs->n_regs++;
ivs->n_cands++;
ivs->cand_cost += cp->cand->cost;
! iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
}
+ ivs->cand_use_cost += cp->cost;
+ iv_ca_set_add_invariants (ivs, cp->depends_on);
iv_ca_recount_cost (data, ivs);
}
}
*************** create_new_iv (struct ivopts_data *data,
*** 4496,4502 ****
base = unshare_expr (cand->iv->base);
! create_iv (base, cand->iv->step, cand->var_before, data->current_loop,
&incr_pos, after, &cand->var_before, &cand->var_after);
}
--- 4661,4668 ----
base = unshare_expr (cand->iv->base);
! create_iv (base, unshare_expr (cand->iv->step),
! cand->var_before, data->current_loop,
&incr_pos, after, &cand->var_before, &cand->var_after);
}
*************** free_loop_data (struct ivopts_data *data
*** 5063,5068 ****
--- 5229,5236 ----
if (cand->iv)
free (cand->iv);
+ if (cand->depends_on)
+ BITMAP_XFREE (cand->depends_on);
free (cand);
}
VARRAY_POP_ALL (data->iv_candidates);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-manip.c,v
retrieving revision 2.21
diff -c -3 -p -r2.21 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c 29 Nov 2004 17:53:47 -0000 2.21
--- tree-ssa-loop-manip.c 1 Feb 2005 23:12:38 -0000
*************** create_iv (tree base, tree step, tree va
*** 50,58 ****
block_stmt_iterator *incr_pos, bool after,
tree *var_before, tree *var_after)
{
! tree stmt, initial, step1, stmts;
tree vb, va;
enum tree_code incr_op = PLUS_EXPR;
if (!var)
{
--- 50,59 ----
block_stmt_iterator *incr_pos, bool after,
tree *var_before, tree *var_after)
{
! tree stmt, initial, step1, stmts, *step_ptr;
tree vb, va;
enum tree_code incr_op = PLUS_EXPR;
+ edge pe = loop_preheader_edge (loop);
if (!var)
{
*************** create_iv (tree base, tree step, tree va
*** 94,112 ****
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
vb, step));
SSA_NAME_DEF_STMT (va) = stmt;
if (after)
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
else
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
! initial = force_gimple_operand (base, &stmts, true, var);
if (stmts)
! {
! edge pe = loop_preheader_edge (loop);
! bsi_insert_on_edge_immediate_loop (pe, stmts);
! }
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
--- 95,117 ----
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
vb, step));
+ step_ptr = &TREE_OPERAND (TREE_OPERAND (stmt, 1), 1);
SSA_NAME_DEF_STMT (va) = stmt;
if (after)
bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
else
bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
! /* Gimplify the step if necessary. We put the computations in front of the
! loop (i.e. the step should be loop invariant). */
! step = force_gimple_operand (step, &stmts, true, var);
if (stmts)
! bsi_insert_on_edge_immediate_loop (pe, stmts);
! *step_ptr = step;
! initial = force_gimple_operand (base, &stmts, true, var);
! if (stmts)
! bsi_insert_on_edge_immediate_loop (pe, stmts);
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 23 Nov 2004 01:27:42 -0000 2.18
--- tree-ssa-loop-niter.c 1 Feb 2005 23:12:38 -0000
*************** number_of_iterations_exit (struct loop *
*** 794,802 ****
&& !POINTER_TYPE_P (type))
return false;
! if (!simple_iv (loop, stmt, op0, &base0, &step0))
return false;
! if (!simple_iv (loop, stmt, op1, &base1, &step1))
return false;
niter->niter = NULL_TREE;
--- 794,802 ----
&& !POINTER_TYPE_P (type))
return false;
! if (!simple_iv (loop, stmt, op0, &base0, &step0, false))
return false;
! if (!simple_iv (loop, stmt, op1, &base1, &step1, false))
return false;
niter->niter = NULL_TREE;