This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Use scev in ivopts
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 15 Apr 2004 00:36:48 +0200
- Subject: [lno] Use scev in ivopts
Hello,
this patch replaces the ivopts induction variable analysis by
usage of scev analysis. It also fixes several bugs I found in
progress.
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.122
diff -c -3 -p -r1.1.2.122 ChangeLog.lno
*** ChangeLog.lno 13 Apr 2004 16:11:41 -0000 1.1.2.122
--- ChangeLog.lno 14 Apr 2004 22:34:59 -0000
***************
*** 1,3 ****
--- 1,25 ----
+ 2004-04-14 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
+ * tree-chrec.c (chrec_convert): Handle extending correctly.
+ * tree-scalar-evolution.c (set_scev_keep_symbolic): Removed.
+ (set_scalar_evolution): Do not use it.
+ (get_scalar_evolution): Only handle ssa names and constants.
+ (interpret_loop_phi): When interpreting subloop, compute the
+ evolution in outer loop afterwards.
+ (analyze_scalar_evolution_in_loop): New.
+ * tree-scalar-evolution.h (analyze_scalar_evolution_in_loop): Declare.
+ * tree-ssa-loop-ivopts.c: Include tree-fold-const.h, tree-chrec.h
+ and tree-scalar-evolution.h.
+ (tree_ssa_iv_optimize_init): Call scev_initialize.
+ (determine_biv_step, find_bivs, mark_bivs,
+ find_givs_in_stmt): Use scev analyzer.
+ (find_givs_in_stmt_scev): New function.
+ (find_induction_variables): Remove TODO comment.
+ (force_var_cost): Test for TREE_INVARIANT, not for
+ is_gimple_min_invariant.
+ (find_optimal_iv_set): Update comment.
+ (tree_ssa_iv_optimize_finalize): Call scev_finalize.
+
2004-04-13 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
* tree-ssa.c (raise_value): Removed.
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-chrec.c
*** tree-chrec.c 30 Mar 2004 21:06:44 -0000 1.1.2.12
--- tree-chrec.c 14 Apr 2004 22:34:59 -0000
*************** chrec_convert (tree type,
*** 2841,2847 ****
ct = chrec_type (chrec);
if (ct == type)
return chrec;
!
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
--- 2841,2850 ----
ct = chrec_type (chrec);
if (ct == type)
return chrec;
!
! if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
! return convert (type, chrec);
!
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.29
diff -c -3 -p -r1.1.2.29 tree-scalar-evolution.c
*** tree-scalar-evolution.c 4 Apr 2004 22:51:21 -0000 1.1.2.29
--- tree-scalar-evolution.c 14 Apr 2004 22:34:59 -0000
*************** chrec_is_positive (tree chrec, bool *val
*** 568,608 ****
}
}
- /* Determine whether the set_chrec has to keep this expression
- symbolic. */
-
- static tree
- set_scev_keep_symbolic (tree def,
- tree chrec)
- {
- if (chrec == chrec_not_analyzed_yet)
- return chrec;
-
- if (chrec == chrec_top)
- /* return def; */
- return chrec;
-
- switch (TREE_CODE (chrec))
- {
- case ADDR_EXPR:
- case ARRAY_REF:
- case INDIRECT_REF:
- case COMPONENT_REF:
- /* KEEP_IT_SYMBOLIC. */
- return def;
-
- default:
- return chrec;
- }
- }
-
/* Associate CHREC to SCALAR in LOOP. */
static void
set_scalar_evolution (struct loop *loop, tree scalar, tree chrec)
{
tree *scalar_info = find_var_scev_info (loop, scalar);
- chrec = set_scev_keep_symbolic (scalar, chrec);
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 568,579 ----
*************** get_scalar_evolution (struct loop *loop,
*** 639,689 ****
res = *find_var_scev_info (loop, scalar);
break;
- case VAR_DECL:
- case PARM_DECL:
case REAL_CST:
case INTEGER_CST:
- case FLOAT_EXPR:
- case NEGATE_EXPR:
- case ABS_EXPR:
- case LSHIFT_EXPR:
- case RSHIFT_EXPR:
- case LROTATE_EXPR:
- case RROTATE_EXPR:
- case BIT_IOR_EXPR:
- case BIT_XOR_EXPR:
- case BIT_AND_EXPR:
- case BIT_NOT_EXPR:
- case TRUTH_ANDIF_EXPR:
- case TRUTH_ORIF_EXPR:
- case TRUTH_AND_EXPR:
- case TRUTH_OR_EXPR:
- case TRUTH_XOR_EXPR:
- case TRUTH_NOT_EXPR:
- case ADDR_EXPR:
- case ARRAY_REF:
- case INDIRECT_REF:
- case COMPONENT_REF:
- /* KEEP_IT_SYMBOLIC. These nodes are kept in "symbolic" form. */
res = scalar;
break;
!
! case CONVERT_EXPR:
! case NOP_EXPR:
! {
! /* KEEP_IT_SYMBOLIC. In the case of a cast, keep it symbolic,
! otherwise just answer chrec_top. */
! tree opnd0 = TREE_OPERAND (scalar, 0);
!
! if (opnd0 && TREE_CODE (opnd0) == SSA_NAME)
! res = scalar;
! else
! res = chrec_top;
! break;
! }
!
default:
- /* We don't want to do symbolic computations on these nodes. */
res = chrec_top;
break;
}
--- 610,621 ----
res = *find_var_scev_info (loop, scalar);
break;
case REAL_CST:
case INTEGER_CST:
res = scalar;
break;
!
default:
res = chrec_top;
break;
}
*************** interpret_loop_phi (struct loop *loop, t
*** 2623,2632 ****
/* Dive one level deeper. */
subloop = superloop_at_depth (phi_loop, loop->depth + 1);
! /* And interpret the subloop. */
res = compute_overall_effect_of_inner_loop (subloop,
PHI_RESULT (loop_phi));
! return res;
}
/* Otherwise really interpret the loop phi. */
--- 2555,2566 ----
/* Dive one level deeper. */
subloop = superloop_at_depth (phi_loop, loop->depth + 1);
! /* Interpret the subloop. */
res = compute_overall_effect_of_inner_loop (subloop,
PHI_RESULT (loop_phi));
!
! /* And get the evolution of the result. */
! return analyze_scalar_evolution (loop, res);
}
/* Otherwise really interpret the loop phi. */
*************** end:
*** 2839,2844 ****
--- 2773,2805 ----
fprintf (dump_file, ")\n");
return res;
+ }
+
+ /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
+ WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
+ of VERSION). */
+
+ tree
+ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
+ tree version)
+ {
+ tree ev = version;
+
+ while (1)
+ {
+ ev = analyze_scalar_evolution (use_loop, ev);
+
+ if (use_loop == wrto_loop)
+ return ev;
+
+ /* If the value of the use changes in the inner loop, we cannot express
+ its value in the outer loop (we might try to return interval chrec,
+ but we do not have a user for it anyway) */
+ if (!no_evolution_in_loop_p (ev, use_loop->num))
+ return chrec_top;
+
+ use_loop = use_loop->outer;
+ }
}
/* Analyze all the parameters of the chrec that were left under a
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.h,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 tree-scalar-evolution.h
*** tree-scalar-evolution.h 30 Mar 2004 21:06:44 -0000 1.1.2.9
--- tree-scalar-evolution.h 14 Apr 2004 22:34:59 -0000
*************** extern tree get_loop_exit_condition (str
*** 30,35 ****
--- 30,37 ----
extern void scev_initialize (struct loops *loops);
extern void scev_finalize (void);
extern tree analyze_scalar_evolution (struct loop *, tree);
+ extern tree analyze_scalar_evolution_in_loop (struct loop *, struct loop *,
+ tree);
extern tree instantiate_parameters (struct loop *, tree);
extern void eliminate_redundant_checks (void);
extern void gather_stats_on_scev_database (void);
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.25
diff -c -3 -p -r1.1.2.25 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 8 Apr 2004 21:20:21 -0000 1.1.2.25
--- tree-ssa-loop-ivopts.c 14 Apr 2004 22:34:59 -0000
*************** Software Foundation, 59 Temple Place - S
*** 84,89 ****
--- 84,92 ----
#include "insn-config.h"
#include "recog.h"
#include "hashtab.h"
+ #include "tree-fold-const.h"
+ #include "tree-chrec.h"
+ #include "tree-scalar-evolution.h"
/* The infinite cost. */
#define INFTY 10000000
*************** tree_ssa_iv_optimize_init (struct loops
*** 966,971 ****
--- 969,976 ----
VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_uses, 20, "iv_uses");
VARRAY_GENERIC_PTR_NOGC_INIT (data->iv_candidates, 20, "iv_candidates");
VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
+
+ scev_initialize (loops);
}
/* Allocates an induction variable with given initial value BASE and step STEP
*************** static tree
*** 1029,1041 ****
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
! tree var = phi_element_for_edge (phi, loop_latch_edge (loop))->def;
! tree type = TREE_TYPE (var);
! tree step, stmt, lhs, rhs, op0, op1;
! enum tree_code code;
! if (TREE_CODE (var) != SSA_NAME
! || !is_gimple_reg (var))
return NULL_TREE;
/* Just work for integers and pointers. */
--- 1034,1043 ----
determine_biv_step (tree phi)
{
struct loop *loop = bb_for_stmt (phi)->loop_father;
! tree name = PHI_RESULT (phi), ev, step;
! tree type = TREE_TYPE (name);
! if (!is_gimple_reg (name))
return NULL_TREE;
/* Just work for integers and pointers. */
*************** determine_biv_step (tree phi)
*** 1043,1097 ****
&& TREE_CODE (type) != POINTER_TYPE)
return NULL_TREE;
! step = convert (type, integer_zero_node);
!
! while (1)
! {
! stmt = SSA_NAME_DEF_STMT (var);
! if (stmt == phi)
! return step;
!
! if (TREE_CODE (stmt) != MODIFY_EXPR)
! return NULL_TREE;
!
! lhs = TREE_OPERAND (stmt, 0);
! rhs = TREE_OPERAND (stmt, 1);
!
! if (lhs != var)
! return NULL_TREE;
!
! code = TREE_CODE (rhs);
! switch (code)
! {
! case SSA_NAME:
! var = rhs;
! break;
!
! case PLUS_EXPR:
! case MINUS_EXPR:
! op0 = TREE_OPERAND (rhs, 0);
! op1 = TREE_OPERAND (rhs, 1);
! if (TREE_CODE (op1) != INTEGER_CST)
! {
! if (code == MINUS_EXPR
! || TREE_CODE (op0) != INTEGER_CST)
! return NULL_TREE;
! SWAP (op0, op1);
! }
! if (TREE_CODE (op0) != SSA_NAME)
! return NULL_TREE;
! step = EXEC_BINARY (code, type, step, op1);
! var = op0;
! break;
!
! default:
! return NULL_TREE;
! }
! }
}
/* Finds basic ivs. */
--- 1045,1064 ----
&& TREE_CODE (type) != POINTER_TYPE)
return NULL_TREE;
! ev = analyze_scalar_evolution (loop, name);
! if (TREE_CODE (ev) == INTEGER_CST
! || TREE_CODE (ev) == SSA_NAME)
! return convert (type, integer_zero_node);
! if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
! return NULL_TREE;
! step = CHREC_RIGHT (ev);
! if (TREE_CODE (step) != INTEGER_CST)
! return NULL_TREE;
! return step;
}
/* Finds basic ivs. */
*************** determine_biv_step (tree phi)
*** 1099,1121 ****
static bool
find_bivs (struct ivopts_data *data)
{
! tree phi, base, step, type;
bool found = false;
struct loop *loop = data->current_loop;
for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
{
step = determine_biv_step (phi);
if (!step)
continue;
! base = phi_element_for_edge (phi, loop_preheader_edge (loop))->def;
type = TREE_TYPE (PHI_RESULT (phi));
base = convert (type, base);
step = convert (type, step);
!
set_iv (data, PHI_RESULT (phi), base, step);
! found |= (integer_nonzerop (step) != 0);
}
return found;
--- 1066,1092 ----
static bool
find_bivs (struct ivopts_data *data)
{
! tree phi, step, type, base;
bool found = false;
struct loop *loop = data->current_loop;
for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
{
step = determine_biv_step (phi);
+
if (!step)
continue;
! if (cst_and_fits_in_hwi (step)
! && int_cst_value (step) == 0)
! continue;
+ base = phi_element_for_edge (phi, loop_preheader_edge (loop))->def;
type = TREE_TYPE (PHI_RESULT (phi));
base = convert (type, base);
step = convert (type, step);
!
set_iv (data, PHI_RESULT (phi), base, step);
! found = true;
}
return found;
*************** find_bivs (struct ivopts_data *data)
*** 1126,1134 ****
static void
mark_bivs (struct ivopts_data *data)
{
! tree phi, stmt, var, rhs, op0, op1;
! struct iv *iv;
struct loop *loop = data->current_loop;
for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
{
--- 1097,1106 ----
static void
mark_bivs (struct ivopts_data *data)
{
! tree phi, var;
! struct iv *iv, *incr_iv;
struct loop *loop = data->current_loop;
+ basic_block incr_bb;
for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi))
{
*************** mark_bivs (struct ivopts_data *data)
*** 1136,1171 ****
if (!iv)
continue;
- iv->biv_p = true;
var = phi_element_for_edge (phi, loop_latch_edge (loop))->def;
! stmt = SSA_NAME_DEF_STMT (var);
!
! while (TREE_CODE (stmt) != PHI_NODE)
! {
! var = TREE_OPERAND (stmt, 0);
! iv = get_iv (data, var);
! iv->biv_p = true;
!
! rhs = TREE_OPERAND (stmt, 1);
! switch (TREE_CODE (rhs))
! {
! case SSA_NAME:
! var = rhs;
! break;
!
! case PLUS_EXPR:
! case MINUS_EXPR:
! op0 = TREE_OPERAND (rhs, 0);
! op1 = TREE_OPERAND (rhs, 1);
! var = TREE_CODE (op1) != INTEGER_CST ? op1 : op0;
! break;
! default:
! abort ();
! }
! stmt = SSA_NAME_DEF_STMT (var);
! }
}
}
--- 1108,1126 ----
if (!iv)
continue;
var = phi_element_for_edge (phi, loop_latch_edge (loop))->def;
! incr_iv = get_iv (data, var);
! if (!incr_iv)
! continue;
! /* If the increment is in the subloop, ignore it. */
! incr_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
! if (incr_bb->loop_father != data->current_loop
! || (incr_bb->flags & BB_IRREDUCIBLE_LOOP))
! continue;
! iv->biv_p = true;
! incr_iv->biv_p = true;
}
}
*************** get_var_def (struct ivopts_data *data, t
*** 1196,1336 ****
return true;
}
! /* Finds general ivs in statement STMT. */
! static void
! find_givs_in_stmt (struct ivopts_data *data, tree stmt)
{
! tree lhs, rhs, op0, op1, mul = NULL_TREE;
! bool negate = false;
! tree base = NULL_TREE, step = NULL_TREE, type;
! tree base0 = NULL_TREE, step0 = NULL_TREE;
! enum tree_code code;
! char class;
if (TREE_CODE (stmt) != MODIFY_EXPR)
! return;
lhs = TREE_OPERAND (stmt, 0);
- rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (lhs) != SSA_NAME)
! return;
type = TREE_TYPE (lhs);
if (TREE_CODE (type) != INTEGER_TYPE
&& TREE_CODE (type) != POINTER_TYPE)
! return;
!
! code = TREE_CODE (rhs);
! class = TREE_CODE_CLASS (code);
! if (class == '1' || class == '2')
! {
! op0 = TREE_OPERAND (rhs, 0);
! if (!get_var_def (data, op0, &base0, &step0))
! return;
!
! if (TREE_TYPE (op0) != type)
! {
! base0 = convert (type, base0);
! if (step0)
! step0 = convert (type, step0);
! }
! }
! if (class == '2')
{
! op1 = TREE_OPERAND (rhs, 1);
! if (!get_var_def (data, op1, &base, &step))
! return;
!
! if (TREE_TYPE (op1) != type)
! {
! base = convert (type, base);
! if (step)
! step = convert (type, step);
! }
}
! switch (code)
! {
! case SSA_NAME:
! if (!get_var_def (data, rhs, &base, &step))
! return;
! break;
!
! case PLUS_EXPR:
! break;
!
! case MINUS_EXPR:
! negate = true;
! break;
!
! case MULT_EXPR:
! if (step0)
! {
! if (step)
! return;
!
! if (TREE_CODE (base) != INTEGER_CST)
! return;
!
! mul = base;
! base = base0;
! step = step0;
! base0 = NULL_TREE;
! step0 = NULL_TREE;
! }
! else if (step)
! {
! if (TREE_CODE (base0) != INTEGER_CST)
! return;
! mul = base0;
! base0 = NULL_TREE;
! }
! else
! return;
! break;
!
! case NEGATE_EXPR:
! negate = true;
! base = base0;
! step = step0;
! base0 = NULL_TREE;
! step0 = NULL_TREE;
! break;
! default:
! return;
! }
! if (negate)
! {
! base = fold (build1 (NEGATE_EXPR, type, base));
! if (step)
! step = EXEC_UNARY (NEGATE_EXPR, type, step);
! }
! if (mul)
! {
! base = fold (build (MULT_EXPR, type, mul, base));
! if (step)
! step = EXEC_BINARY (MULT_EXPR, type, mul, step);
! }
! if (base0)
! base = fold (build (PLUS_EXPR, type, base, base0));
!
! if (step0)
! {
! if (step)
! step = EXEC_BINARY (PLUS_EXPR, type, step, step0);
! else
! step = step0;
! }
!
! set_iv (data, lhs, base, step);
}
/* Finds general ivs in basic block BB. */
--- 1151,1214 ----
return true;
}
! /* Checks whether STMT defines a linear induction variable and stores its
! parameters to BASE and STEP. */
! static bool
! find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt,
! tree *base, tree *step)
{
! tree lhs, type, ev;
! struct loop *loop = data->current_loop;
! basic_block bb = bb_for_stmt (stmt);
!
! *base = NULL_TREE;
! *step = NULL_TREE;
if (TREE_CODE (stmt) != MODIFY_EXPR)
! return false;
lhs = TREE_OPERAND (stmt, 0);
if (TREE_CODE (lhs) != SSA_NAME)
! return false;
type = TREE_TYPE (lhs);
if (TREE_CODE (type) != INTEGER_TYPE
&& TREE_CODE (type) != POINTER_TYPE)
! return false;
! ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, lhs);
! if (tree_does_not_contain_chrecs (ev))
{
! *base = ev;
! return true;
}
! if (TREE_CODE (ev) != POLYNOMIAL_CHREC
! || CHREC_VARIABLE (ev) != (unsigned) loop->num)
! return false;
! *step = CHREC_RIGHT (ev);
! if (TREE_CODE (*step) != INTEGER_CST)
! return false;
! *base = CHREC_LEFT (ev);
! if (tree_contains_chrecs (*base))
! return false;
! return true;
! }
! /* Finds general ivs in statement STMT. */
! static void
! find_givs_in_stmt (struct ivopts_data *data, tree stmt)
! {
! tree base, step;
! if (!find_givs_in_stmt_scev (data, stmt, &base, &step))
! return;
! set_iv (data, TREE_OPERAND (stmt, 0), base, step);
}
/* Finds general ivs in basic block BB. */
*************** find_induction_variables (struct ivopts_
*** 1748,1756 ****
unsigned i;
struct loop *loop = data->current_loop;
- /* TODO (FIXME?) Use scev for this. ??? Perhaps the code could still be
- useful at lower optimization levels, since it might be faster. */
-
if (!find_bivs (data))
return false;
--- 1626,1631 ----
*************** force_var_cost (struct ivopts_data *data
*** 3220,3226 ****
walk_tree (&expr, find_depends, depends_on, NULL);
}
! if (is_gimple_min_invariant (expr)
|| SSA_VAR_P (expr))
return 0;
--- 3095,3101 ----
walk_tree (&expr, find_depends, depends_on, NULL);
}
! if (TREE_INVARIANT (expr)
|| SSA_VAR_P (expr))
return 0;
*************** try_improve_iv_set (struct ivopts_data *
*** 4325,4334 ****
return true;
}
! /* Attempts to find the optimal set of induction variables. TODO document
! the algorithm, once it converges to the final form. For now we do simple
! greedy heuristic (trying to replace at most one candidate in the selected
! solution). */
static bitmap
find_optimal_iv_set (struct ivopts_data *data)
--- 4200,4208 ----
return true;
}
! /* Attempts to find the optimal set of induction variables. We do simple
! greedy heuristic -- we try to replace at most one candidate in the selected
! solution and remove the unused ivs while this improves the cost. */
static bitmap
find_optimal_iv_set (struct ivopts_data *data)
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 5022,5027 ****
--- 4896,4903 ----
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (data->iv_uses);
VARRAY_FREE (data->iv_candidates);
+
+ scev_finalize ();
}
/* Optimizes the LOOP. Returns true if anything changed. */