This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Minor ivopts improvements
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 22 Apr 2005 10:38:39 +0200
- Subject: [patch] Minor ivopts improvements
Hello,
on two places (induction variable elimination and final value
elimination) ivopts calculate the same value twice (once to determine
whether the transformation is possible and profitable, the second time
to actually perform it).
Also, there is a minor imprecision in determine_use_iv_cost_condition --
in case there is an induction variable that cannot be used for iv
elimination, we mark that the invariants used in the condition
cannot be eliminated at all. This is wrong, since there may be
other induction variables that enable the elimination.
This affects only the cost function and consequently the choice
of the ivs, so it does not cause correctness problems, and it
is very hard to construct a testcase where this would cause us
to choose a suboptimal set of ivs, but it is easy to fix in
a proper way, by just recording the impossible to eliminate
invariants to the particular induction variable.
Bootstrapped & regtested on i686.
Zdenek
* tree-ssa-loop-ivopts.c (struct cost_pair): Add value field.
(find_interesting_uses_cond): Do not use integer_zerop and
integer_nonzerop to check for integer constants.
(set_use_iv_cost): Record the value field.
(determine_use_iv_cost_generic, determine_use_iv_cost_address,
determine_use_iv_cost_outer): Set the value field of the cost pair.
(may_eliminate_iv): Do not return the comparison code.
(iv_elimination_compare): New function.
(determine_use_iv_cost_condition): Set the value field. Record
noneliminable invariants correctly.
(rewrite_use_compare, rewrite_use_outer): Use the value field.
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.60
diff -c -3 -p -r2.60 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 17 Apr 2005 06:41:53 -0000 2.60
--- tree-ssa-loop-ivopts.c 22 Apr 2005 08:29:13 -0000
*************** struct cost_pair
*** 143,148 ****
--- 143,151 ----
unsigned cost; /* The cost. */
bitmap depends_on; /* The list of invariants that have to be
preserved. */
+ tree value; /* For final value elimination, the expression for
+ the final value of the iv. For iv elimination,
+ the new bound to compare with. */
};
/* Use. */
*************** find_interesting_uses_cond (struct ivopt
*** 1276,1283 ****
const_iv.step = NULL_TREE;
! if (integer_zerop (*cond_p)
! || integer_nonzerop (*cond_p))
return;
if (TREE_CODE (*cond_p) == SSA_NAME)
--- 1279,1286 ----
const_iv.step = NULL_TREE;
! if (TREE_CODE (*cond_p) != SSA_NAME
! && !COMPARISON_CLASS_P (*cond_p))
return;
if (TREE_CODE (*cond_p) == SSA_NAME)
*************** alloc_use_cost_map (struct ivopts_data *
*** 2270,2281 ****
}
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
! on invariants DEPENDS_ON. */
static void
set_use_iv_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand, unsigned cost,
! bitmap depends_on)
{
unsigned i, s;
--- 2273,2285 ----
}
/* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
! on invariants DEPENDS_ON and that the value used in expressing it
! is VALUE.*/
static void
set_use_iv_cost (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand, unsigned cost,
! bitmap depends_on, tree value)
{
unsigned i, s;
*************** set_use_iv_cost (struct ivopts_data *dat
*** 2290,2295 ****
--- 2294,2300 ----
use->cost_map[cand->id].cand = cand;
use->cost_map[cand->id].cost = cost;
use->cost_map[cand->id].depends_on = depends_on;
+ use->cost_map[cand->id].value = value;
return;
}
*************** found:
*** 2308,2313 ****
--- 2313,2319 ----
use->cost_map[i].cand = cand;
use->cost_map[i].cost = cost;
use->cost_map[i].depends_on = depends_on;
+ use->cost_map[i].value = value;
}
/* Gets cost of (USE, CANDIDATE) pair. */
*************** determine_use_iv_cost_generic (struct iv
*** 3307,3318 ****
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
! set_use_iv_cost (data, use, cand, 0, NULL);
return true;
}
cost = get_computation_cost (data, use, cand, false, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
}
--- 3313,3324 ----
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
! set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
return true;
}
cost = get_computation_cost (data, use, cand, false, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return cost != INFTY;
}
*************** determine_use_iv_cost_address (struct iv
*** 3326,3332 ****
bitmap depends_on;
unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
}
--- 3332,3338 ----
bitmap depends_on;
unsigned cost = get_computation_cost (data, use, cand, true, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return cost != INFTY;
}
*************** iv_period (struct iv *iv)
*** 3382,3395 ****
return period;
}
/* Check whether it is possible to express the condition in USE by comparison
! of candidate CAND. If so, store the comparison code to COMPARE and the
! value compared with to BOUND. */
static bool
may_eliminate_iv (struct ivopts_data *data,
! struct iv_use *use, struct iv_cand *cand,
! enum tree_code *compare, tree *bound)
{
basic_block ex_bb;
edge exit;
--- 3388,3416 ----
return period;
}
+ /* Returns the comparison operator used when eliminating the iv USE. */
+
+ static enum tree_code
+ iv_elimination_compare (struct ivopts_data *data, struct iv_use *use)
+ {
+ struct loop *loop = data->current_loop;
+ basic_block ex_bb;
+ edge exit;
+
+ ex_bb = bb_for_stmt (use->stmt);
+ exit = EDGE_SUCC (ex_bb, 0);
+ if (flow_bb_inside_loop_p (loop, exit->dest))
+ exit = EDGE_SUCC (ex_bb, 1);
+
+ return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
+ }
+
/* Check whether it is possible to express the condition in USE by comparison
! of candidate CAND. If so, store the value compared with to BOUND. */
static bool
may_eliminate_iv (struct ivopts_data *data,
! struct iv_use *use, struct iv_cand *cand, tree *bound)
{
basic_block ex_bb;
edge exit;
*************** may_eliminate_iv (struct ivopts_data *da
*** 3440,3450 ****
fold_convert (wider_type, nit)))))
return false;
- if (exit->flags & EDGE_TRUE_VALUE)
- *compare = EQ_EXPR;
- else
- *compare = NE_EXPR;
-
*bound = cand_value_at (loop, cand, use->stmt, nit);
return true;
}
--- 3461,3466 ----
*************** static bool
*** 3455,3491 ****
determine_use_iv_cost_condition (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
! tree bound;
! enum tree_code compare;
/* Only consider real candidates. */
if (!cand->iv)
{
! set_use_iv_cost (data, use, cand, INFTY, NULL);
return false;
}
! if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
! bitmap depends_on = NULL;
! unsigned cost = force_var_cost (data, bound, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
}
/* The induction variable elimination failed; just express the original
giv. If it is compared with an invariant, note that we cannot get
rid of it. */
! if (TREE_CODE (*use->op_p) == SSA_NAME)
! record_invariant (data, *use->op_p, true);
! else
{
! record_invariant (data, TREE_OPERAND (*use->op_p, 0), true);
! record_invariant (data, TREE_OPERAND (*use->op_p, 1), true);
}
! return determine_use_iv_cost_generic (data, use, cand);
}
/* Checks whether it is possible to replace the final value of USE by
--- 3471,3516 ----
determine_use_iv_cost_condition (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand)
{
! tree bound = NULL_TREE, op, cond;
! bitmap depends_on = NULL;
! unsigned cost;
/* Only consider real candidates. */
if (!cand->iv)
{
! set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
return false;
}
! if (may_eliminate_iv (data, use, cand, &bound))
{
! cost = force_var_cost (data, bound, &depends_on);
! set_use_iv_cost (data, use, cand, cost, depends_on, bound);
return cost != INFTY;
}
/* The induction variable elimination failed; just express the original
giv. If it is compared with an invariant, note that we cannot get
rid of it. */
! cost = get_computation_cost (data, use, cand, false, &depends_on);
!
! cond = *use->op_p;
! if (TREE_CODE (cond) != SSA_NAME)
{
! op = TREE_OPERAND (cond, 0);
! if (TREE_CODE (op) == SSA_NAME && !zero_p (get_iv (data, op)->step))
! op = TREE_OPERAND (cond, 1);
! if (TREE_CODE (op) == SSA_NAME)
! {
! op = get_iv (data, op)->base;
! fd_ivopts_data = data;
! walk_tree (&op, find_depends, &depends_on, NULL);
! }
}
! set_use_iv_cost (data, use, cand, cost, depends_on, NULL);
! return cost != INFTY;
}
/* Checks whether it is possible to replace the final value of USE by
*************** determine_use_iv_cost_outer (struct ivop
*** 3525,3531 ****
bitmap depends_on;
unsigned cost;
edge exit;
! tree value;
struct loop *loop = data->current_loop;
/* The simple case first -- if we need to express value of the preserved
--- 3550,3556 ----
bitmap depends_on;
unsigned cost;
edge exit;
! tree value = NULL_TREE;
struct loop *loop = data->current_loop;
/* The simple case first -- if we need to express value of the preserved
*************** determine_use_iv_cost_outer (struct ivop
*** 3535,3541 ****
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
! set_use_iv_cost (data, use, cand, 0, NULL);
return true;
}
--- 3560,3566 ----
if (cand->pos == IP_ORIGINAL
&& cand->incremented_at == use->stmt)
{
! set_use_iv_cost (data, use, cand, 0, NULL, NULL_TREE);
return true;
}
*************** determine_use_iv_cost_outer (struct ivop
*** 3543,3549 ****
{
if (!may_replace_final_value (data, use, &value))
{
! set_use_iv_cost (data, use, cand, INFTY, NULL);
return false;
}
--- 3568,3574 ----
{
if (!may_replace_final_value (data, use, &value))
{
! set_use_iv_cost (data, use, cand, INFTY, NULL, NULL_TREE);
return false;
}
*************** determine_use_iv_cost_outer (struct ivop
*** 3552,3558 ****
cost /= AVG_LOOP_NITER (loop);
! set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
}
--- 3577,3583 ----
cost /= AVG_LOOP_NITER (loop);
! set_use_iv_cost (data, use, cand, cost, depends_on, value);
return cost != INFTY;
}
*************** determine_use_iv_cost_outer (struct ivop
*** 3572,3578 ****
cost = get_computation_cost (data, use, cand, false, &depends_on);
}
! set_use_iv_cost (data, use, cand, cost, depends_on);
return cost != INFTY;
}
--- 3597,3603 ----
cost = get_computation_cost (data, use, cand, false, &depends_on);
}
! set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
return cost != INFTY;
}
*************** rewrite_use_compare (struct ivopts_data
*** 4907,4918 ****
tree *op_p, cond, op, stmts, bound;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
! if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
bound = fold_convert (var_type, bound);
op = force_gimple_operand (unshare_expr (bound), &stmts,
true, NULL_TREE);
--- 4932,4946 ----
tree *op_p, cond, op, stmts, bound;
block_stmt_iterator bsi = bsi_for_stmt (use->stmt);
enum tree_code compare;
+ struct cost_pair *cp = get_use_iv_cost (data, use, cand);
! bound = cp->value;
! if (bound)
{
tree var = var_at_stmt (data->current_loop, cand, use->stmt);
tree var_type = TREE_TYPE (var);
+ compare = iv_elimination_compare (data, use);
bound = fold_convert (var_type, bound);
op = force_gimple_operand (unshare_expr (bound), &stmts,
true, NULL_TREE);
*************** rewrite_use_outer (struct ivopts_data *d
*** 5087,5094 ****
{
if (!cand->iv)
{
! bool ok = may_replace_final_value (data, use, &value);
! gcc_assert (ok);
}
else
value = get_computation_at (data->current_loop,
--- 5115,5122 ----
{
if (!cand->iv)
{
! struct cost_pair *cp = get_use_iv_cost (data, use, cand);
! value = cp->value;
}
else
value = get_computation_at (data->current_loop,