/* Scalar evolution detector.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
- Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
basic block INSTANTIATED_BELOW, the value of VAR can be expressed
as CHREC. */
-struct scev_info_str GTY(())
-{
+struct GTY(()) scev_info_str {
basic_block instantiated_below;
tree var;
tree chrec;
follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
gimple halting_phi, tree *evolution_of_loop, int limit)
{
- t_bool res = t_false;
- tree rhs0, rhs1;
- tree type = TREE_TYPE (expr);
- enum tree_code code;
-
+ enum tree_code code = TREE_CODE (expr);
+ tree type = TREE_TYPE (expr), rhs0, rhs1;
+ t_bool res;
+
/* The EXPR is one of the following cases:
- an SSA_NAME,
- an INTEGER_CST,
- a MINUS_EXPR,
- an ASSERT_EXPR,
- other cases are not yet handled. */
- code = TREE_CODE (expr);
+
switch (code)
{
- case NOP_EXPR:
+ CASE_CONVERT:
/* This assignment is under the form "a_1 = (cast) rhs. */
res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
halting_phi, evolution_of_loop, limit);
/* This assignment is under the form "a_1 = 7". */
res = t_false;
break;
-
+
case SSA_NAME:
/* This assignment is under the form: "a_1 = b_2". */
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
break;
-
+
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
case MINUS_EXPR:
/* This case is under the form "rhs0 +- rhs1". */
rhs0 = TREE_OPERAND (expr, 0);
rhs1 = TREE_OPERAND (expr, 1);
- STRIP_TYPE_NOPS (rhs0);
- STRIP_TYPE_NOPS (rhs1);
- return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
- halting_phi, evolution_of_loop, limit);
+ type = TREE_TYPE (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
+ halting_phi, evolution_of_loop, limit);
+ break;
case ASSERT_EXPR:
- {
- /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
- It must be handled as a copy assignment of the form a_1 = a_2. */
- tree op0 = ASSERT_EXPR_VAR (expr);
- if (TREE_CODE (op0) == SSA_NAME)
- res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
- halting_phi, evolution_of_loop, limit);
- else
- res = t_false;
- break;
- }
-
+ /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+ It must be handled as a copy assignment of the form a_1 = a_2. */
+ rhs0 = ASSERT_EXPR_VAR (expr);
+ if (TREE_CODE (rhs0) == SSA_NAME)
+ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
+ halting_phi, evolution_of_loop, limit);
+ else
+ res = t_false;
+ break;
default:
res = t_false;
break;
}
-
+
return res;
}
follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
gimple halting_phi, tree *evolution_of_loop, int limit)
{
- tree type = TREE_TYPE (gimple_assign_lhs (stmt));
enum tree_code code = gimple_assign_rhs_code (stmt);
+ tree type = gimple_expr_type (stmt), rhs1, rhs2;
+ t_bool res;
- switch (get_gimple_rhs_class (code))
+ switch (code)
{
- case GIMPLE_BINARY_RHS:
- return follow_ssa_edge_binary (loop, stmt, type,
- gimple_assign_rhs1 (stmt), code,
- gimple_assign_rhs2 (stmt),
- halting_phi, evolution_of_loop, limit);
- case GIMPLE_SINGLE_RHS:
- return follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
- halting_phi, evolution_of_loop, limit);
- case GIMPLE_UNARY_RHS:
- if (code == NOP_EXPR)
- {
- /* This assignment is under the form "a_1 = (cast) rhs. */
- t_bool res
- = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ CASE_CONVERT:
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ halting_phi, evolution_of_loop, limit);
+ *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
+ break;
+
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ rhs1 = gimple_assign_rhs1 (stmt);
+ rhs2 = gimple_assign_rhs2 (stmt);
+ type = TREE_TYPE (rhs1);
+ res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
halting_phi, evolution_of_loop, limit);
- *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
- return res;
- }
- /* FALLTHRU */
+ break;
default:
- return t_false;
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ halting_phi, evolution_of_loop, limit);
+ else
+ res = t_false;
+ break;
}
+
+ return res;
}
/* Checks whether the I-th argument of a PHI comes from a backedge. */
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
n = gimple_phi_num_args (condition_phi);
- if (n > 1)
- limit++;
-
for (i = 1; i < n; i++)
{
/* Quickly give up when the evolution of one of the branches is
if (*evolution_of_loop == chrec_dont_know)
return t_true;
+ /* Increase the limit by the PHI argument number to avoid exponential
+ time and memory complexity. */
res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
- init, limit);
+ init, limit + i);
if (res == t_false || res == t_dont_know)
return res;
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_dont_know;
+ /* During early loop unrolling we do not have fully constant propagated IL.
+ Handle degenerate PHIs here to not miss important unrollings. */
+ if (TREE_CODE (init_cond) == SSA_NAME)
+ {
+ gimple def = SSA_NAME_DEF_STMT (init_cond);
+ tree res;
+ if (gimple_code (def) == GIMPLE_PHI
+ && (res = degenerate_phi_result (def)) != NULL_TREE
+ /* Only allow invariants here, otherwise we may break
+ loop-closed SSA form. */
+ && is_gimple_min_invariant (res))
+ init_cond = res;
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (init_cond = ");
fold_convert (type, integer_minus_one_node));
break;
+ case BIT_NOT_EXPR:
+ /* Handle ~X as -1 - X. */
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ res = chrec_fold_minus (type,
+ fold_convert (type, integer_minus_one_node),
+ chrec1);
+ break;
+
case MULT_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
chrec2 = analyze_scalar_evolution (loop, rhs2);
}
/* 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).
+ WRTO_LOOP (which should be a superloop of USE_LOOP)
FOLDED_CASTS is set to true if resolve_mixers used
chrec_convert_aggressive (TODO -- not really, we are way too conservative
- at the moment in order to keep things simple). */
+ at the moment in order to keep things simple).
+
+ To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
+ example:
+
+ for (i = 0; i < 100; i++) -- loop 1
+ {
+ for (j = 0; j < 100; j++) -- loop 2
+ {
+ k1 = i;
+ k2 = j;
+
+ use2 (k1, k2);
+
+ for (t = 0; t < 100; t++) -- loop 3
+ use3 (k1, k2);
+
+ }
+ use1 (k1, k2);
+ }
+
+ Both k1 and k2 are invariants in loop3, thus
+ analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
+ analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
+
+ As they are invariant, it does not matter whether we consider their
+ usage in loop 3 or loop 2, hence
+ analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
+ analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
+ analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
+ analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
+
+ Similarly for their evolutions with respect to loop 1. The values of K2
+ in the use in loop 2 vary independently on loop 1, thus we cannot express
+ the evolution with respect to loop 1:
+ analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
+ analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
+ analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
+ analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
+
+ The value of k2 in the use in loop 1 is known, though:
+ analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
+ analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
+ */
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
bool val = false;
tree ev = version, tmp;
+ /* We cannot just do
+
+ tmp = analyze_scalar_evolution (use_loop, version);
+ ev = resolve_mixers (wrto_loop, tmp);
+
+ as resolve_mixers would query the scalar evolution with respect to
+ wrto_loop. For example, in the situation described in the function
+ comment, suppose that wrto_loop = loop1, use_loop = loop3 and
+ version = k2. Then
+
+ analyze_scalar_evolution (use_loop, version) = k2
+
+ and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
+ is 100, which is a wrong result, since we are interested in the
+ value in loop 3.
+
+ Instead, we need to proceed from use_loop to wrto_loop loop by loop,
+ each time checking that there is no evolution in the inner loop. */
+
if (folded_casts)
*folded_casts = false;
while (1)
return chrec_convert (TREE_TYPE (chrec), op0, NULL);
+ case BIT_NOT_EXPR:
+ /* Handle ~X as -1 - X. */
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
+ TREE_OPERAND (chrec, 0),
+ fold_conversions, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0)
+ {
+ op0 = chrec_convert (type, op0, NULL);
+ chrec = chrec_fold_minus (type,
+ fold_convert (type,
+ integer_minus_one_node),
+ op0);
+ }
+ return chrec;
+
case SCEV_NOT_KNOWN:
return chrec_dont_know;
}
}
-/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
- its base and step in IV 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. IV->no_overflow is set to true if we are sure the iv cannot
- overflow (e.g. because it is computed in signed arithmetics). */
+/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
+ respect to WRTO_LOOP and returns its base and step in IV if possible
+ (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
+ and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
+ invariant in LOOP. Otherwise we require it to be an integer constant.
+
+ IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
+ because it is computed in signed arithmetics). Consequently, adding an
+ induction variable
+
+ for (i = IV->base; ; i += IV->step)
+
+ is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
+ false for the type of the induction variable, or you can prove that i does
+ not wrap by some other argument. Otherwise, this might introduce undefined
+ behavior, and
+
+ for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
+
+ must be used instead. */
bool
-simple_iv (struct loop *loop, gimple stmt, tree op, affine_iv *iv,
- bool allow_nonconstant_step)
+simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
+ affine_iv *iv, bool allow_nonconstant_step)
{
- basic_block bb = gimple_bb (stmt);
tree type, ev;
bool folded_casts;
&& TREE_CODE (type) != POINTER_TYPE)
return false;
- ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
+ ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
&folded_casts);
- if (chrec_contains_undetermined (ev))
+ if (chrec_contains_undetermined (ev)
+ || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
return false;
- if (tree_does_not_contain_chrecs (ev)
- && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
+ if (tree_does_not_contain_chrecs (ev))
{
iv->base = ev;
iv->step = build_int_cst (TREE_TYPE (ev), 0);
}
if (TREE_CODE (ev) != POLYNOMIAL_CHREC
- || CHREC_VARIABLE (ev) != (unsigned) loop->num)
+ || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
return false;
iv->step = CHREC_RIGHT (ev);
- if (allow_nonconstant_step)
- {
- if (tree_contains_chrecs (iv->step, NULL)
- || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
- return false;
- }
- else if (TREE_CODE (iv->step) != INTEGER_CST)
+ if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
+ || tree_contains_chrecs (iv->step, NULL))
return false;
iv->base = CHREC_LEFT (ev);
- if (tree_contains_chrecs (iv->base, NULL)
- || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
+ if (tree_contains_chrecs (iv->base, NULL))
return false;
iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
OSDN Git Service
