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. */
#include "config.h"
#include "system.h"
/* Ignore loops of while (i-- < 10) type. */
if (code != NE_EXPR)
{
- if (step0 && !tree_expr_nonnegative_p (step0))
+ if (step0 && tree_int_cst_sign_bit (step0))
return;
- if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
+ if (!zero_p (step1) && !tree_int_cst_sign_bit (step1))
return;
}
if (!zero_p (step1))
step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
step1 = NULL_TREE;
- if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
+ if (tree_int_cst_sign_bit (fold_convert (signed_niter_type, step0)))
{
step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
base1 = fold_build1 (NEGATE_EXPR, type, base1);
/* Expand definitions of ssa names in EXPR as long as they are simple
enough, and return the new expression. */
-static tree
+tree
expand_simple_operations (tree expr)
{
unsigned i, n;
chain_of_csts_start (struct loop *loop, tree x)
{
tree stmt = SSA_NAME_DEF_STMT (x);
+ tree use;
basic_block bb = bb_for_stmt (stmt);
- use_optype uses;
if (!bb
|| !flow_bb_inside_loop_p (loop, bb))
if (TREE_CODE (stmt) != MODIFY_EXPR)
return NULL_TREE;
- if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
- return NULL_TREE;
- if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return NULL_TREE;
- if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
+ if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
return NULL_TREE;
- if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
- return NULL_TREE;
- uses = STMT_USE_OPS (stmt);
- if (NUM_USES (uses) != 1)
+
+ use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
+ if (use == NULL_USE_OPERAND_P)
return NULL_TREE;
- return chain_of_csts_start (loop, USE_OP (uses, 0));
+ return chain_of_csts_start (loop, use);
}
/* Determines whether the expression X is derived from a result of a phi node
get_val_for (tree x, tree base)
{
tree stmt, nx, val;
- use_optype uses;
use_operand_p op;
+ ssa_op_iter iter;
if (!x)
return base;
if (TREE_CODE (stmt) == PHI_NODE)
return base;
- uses = STMT_USE_OPS (stmt);
- op = USE_OP_PTR (uses, 0);
-
- nx = USE_FROM_PTR (op);
- val = get_val_for (nx, base);
- SET_USE (op, val);
- val = fold (TREE_OPERAND (stmt, 1));
- SET_USE (op, nx);
+ FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
+ {
+ nx = USE_FROM_PTR (op);
+ val = get_val_for (nx, base);
+ SET_USE (op, val);
+ val = fold (TREE_OPERAND (stmt, 1));
+ SET_USE (op, nx);
+ /* only iterate loop once. */
+ return val;
+ }
- return val;
+ /* Should never reach here. */
+ gcc_unreachable();
}
/* Tries to count the number of iterations of LOOP till it exits by EXIT
unsigned i, n_exits;
struct tree_niter_desc niter_desc;
+ /* Give up if we already have tried to compute an estimation. */
+ if (loop->estimated_nb_iterations == chrec_dont_know
+ /* Or when we already have an estimation. */
+ || (loop->estimated_nb_iterations != NULL_TREE
+ && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
+ return;
+ else
+ loop->estimated_nb_iterations = chrec_dont_know;
+
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
{
free (exits);
/* Analyzes the bounds of arrays accessed in the loop. */
- if (loop->estimated_nb_iterations == NULL_TREE)
+ if (chrec_contains_undetermined (loop->estimated_nb_iterations))
{
varray_type datarefs;
VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
}
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
- at AT_STMT in wider TYPE, using the fact that statement OF is executed at
- most BOUND times in the loop. If it is possible, return the value of step
- of the induction variable in the TYPE, otherwise return NULL_TREE.
+/* Return true when it is possible to prove that the induction
+ variable does not wrap: vary outside the type specified bounds.
+ Checks whether BOUND < VALID_NITER that means in the context of iv
+ conversion that all the iterations in the loop are safe: not
+ producing wraps.
+
+ The statement NITER_BOUND->AT_STMT is executed at most
+ NITER_BOUND->BOUND times in the loop.
- ADDITIONAL is the additional condition recorded for operands of the bound.
- This is useful in the following case, created by loop header copying:
+ NITER_BOUND->ADDITIONAL is the additional condition recorded for
+ operands of the bound. This is useful in the following case,
+ created by loop header copying:
i = 0;
if (n > 0)
assumption "n > 0" says us that the value of the number of iterations is at
most MAX_TYPE - 1 (without this assumption, it might overflow). */
-static tree
-can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
- tree at_stmt,
- tree bound,
- tree additional,
- tree of)
+static bool
+proved_non_wrapping_p (tree at_stmt,
+ struct nb_iter_bound *niter_bound,
+ tree new_type,
+ tree valid_niter)
{
- tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
- tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
+ tree bound = niter_bound->bound;
+
+ if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
+ bound = fold_convert (unsigned_type_for (new_type), bound);
+ else
+ valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
+
+ /* After the statement niter_bound->at_stmt we know that anything is
+ executed at most BOUND times. */
+ if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
+ cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
+
+ /* Before the statement niter_bound->at_stmt we know that anything
+ is executed at most BOUND + 1 times. */
+ else
+ cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
+
+ if (nonzero_p (cond))
+ return true;
+
+ /* Try taking additional conditions into account. */
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ invert_truthvalue (niter_bound->additional),
+ cond);
+
+ if (nonzero_p (cond))
+ return true;
- b = fold_convert (type, base);
- bplusstep = fold_convert (type,
- fold_build2 (PLUS_EXPR, inner_type, base, step));
- new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b);
- if (TREE_CODE (new_step) != INTEGER_CST)
+ return false;
+}
+
+/* Checks whether it is correct to count the induction variable BASE +
+ STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
+ numbers of iterations of a LOOP. If it is possible, return the
+ value of step of the induction variable in the NEW_TYPE, otherwise
+ return NULL_TREE. */
+
+static tree
+convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
+ tree at_stmt)
+{
+ struct nb_iter_bound *bound;
+ tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
+ tree delta, step_abs;
+ tree unsigned_type, valid_niter;
+
+ /* Compute the new step. For example, {(uchar) 100, +, (uchar) 240}
+ is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
+ keep the values of the induction variable unchanged: 100, 84, 68,
+ ...
+
+ Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
+ to {(uint)100, +, (uint)3}.
+
+ Before returning the new step, verify that the number of
+ iterations is less than DELTA / STEP_ABS (i.e. in the previous
+ example (256 - 100) / 3) such that the iv does not wrap (in which
+ case the operations are too difficult to be represented and
+ handled: the values of the iv should be taken modulo 256 in the
+ wider type; this is not implemented). */
+ base_in_new_type = fold_convert (new_type, base);
+ base_plus_step_in_new_type =
+ fold_convert (new_type,
+ fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
+ step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
+ base_plus_step_in_new_type,
+ base_in_new_type);
+
+ if (TREE_CODE (step_in_new_type) != INTEGER_CST)
return NULL_TREE;
- switch (compare_trees (bplusstep, b))
+ switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
{
case -1:
- extreme = upper_bound_in_type (type, inner_type);
- delta = fold_build2 (MINUS_EXPR, type, extreme, b);
- new_step_abs = new_step;
- break;
+ {
+ tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, new_type, extreme,
+ base_in_new_type);
+ step_abs = step_in_new_type;
+ break;
+ }
case 1:
- extreme = lower_bound_in_type (type, inner_type);
- new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
- delta = fold_build2 (MINUS_EXPR, type, b, extreme);
- break;
+ {
+ tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
+ extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
+ break;
+ }
case 0:
- return new_step;
+ return step_in_new_type;
default:
return NULL_TREE;
}
- unsigned_type = unsigned_type_for (type);
+ unsigned_type = unsigned_type_for (new_type);
delta = fold_convert (unsigned_type, delta);
- new_step_abs = fold_convert (unsigned_type, new_step_abs);
+ step_abs = fold_convert (unsigned_type, step_abs);
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
- delta, new_step_abs);
+ delta, step_abs);
- bound_type = TREE_TYPE (bound);
- if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
- bound = fold_convert (unsigned_type, bound);
- else
- valid_niter = fold_convert (bound_type, valid_niter);
-
- if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
+ estimate_numbers_of_iterations_loop (loop);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
+ return step_in_new_type;
+
+ /* Fail when the loop has no bound estimations, or when no bound can
+ be used for verifying the conversion. */
+ return NULL_TREE;
+}
+
+/* Return false only when the induction variable BASE + STEP * I is
+ known to not overflow: i.e. when the number of iterations is small
+ enough with respect to the step and initial condition in order to
+ keep the evolution confined in TYPEs bounds. Return true when the
+ iv is known to overflow or when the property is not computable.
+
+ Initialize INIT_IS_MAX to true when the evolution goes from
+ INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case, not
+ defined when the function returns true. */
+
+bool
+scev_probably_wraps_p (tree type, tree base, tree step,
+ tree at_stmt, struct loop *loop,
+ bool *init_is_max)
+{
+ struct nb_iter_bound *bound;
+ tree delta, step_abs;
+ tree unsigned_type, valid_niter;
+ tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
+
+ switch (compare_trees (base_plus_step, base))
{
- /* After the statement OF we know that anything is executed at most
- BOUND times. */
- cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
+ case -1:
+ {
+ tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, extreme, base);
+ step_abs = step;
+ *init_is_max = false;
+ break;
+ }
+
+ case 1:
+ {
+ tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, base, extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, type, step);
+ *init_is_max = true;
+ break;
+ }
+
+ case 0:
+ /* This means step is equal to 0. This should not happen. It
+ could happen in convert step, but not here. Safely answer
+ don't know as in the default case. */
+
+ default:
+ return true;
}
- else
+
+ /* If AT_STMT represents a cast operation, we may not be able to
+ take advantage of the undefinedness of signed type evolutions.
+ See PR 21959 for a test case. Essentially, given a cast
+ operation
+ unsigned char i;
+ signed char i.0;
+ ...
+ i.0_6 = (signed char) i_2;
+ if (i.0_6 < 0)
+ ...
+
+ where i_2 and i.0_6 have the scev {0, +, 1}, we would consider
+ i_2 to wrap around, but not i.0_6, because it is of a signed
+ type. This causes VRP to erroneously fold the predicate above
+ because it thinks that i.0_6 cannot be negative. */
+ if (TREE_CODE (at_stmt) == MODIFY_EXPR)
{
- /* Before the statement OF we know that anything is executed at most
- BOUND + 1 times. */
- cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
+ tree rhs = TREE_OPERAND (at_stmt, 1);
+ tree outer_t = TREE_TYPE (rhs);
+
+ if (!TYPE_UNSIGNED (outer_t)
+ && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
+ {
+ tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
+
+ /* If the inner type is unsigned and its size and/or
+ precision are smaller to that of the outer type, then the
+ expression may wrap around. */
+ if (TYPE_UNSIGNED (inner_t)
+ && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
+ || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
+ return true;
+ }
}
- if (nonzero_p (cond))
- return new_step;
+ /* After having set INIT_IS_MAX, we can return false: when not using
+ wrapping arithmetic, signed types don't wrap. */
+ if (!flag_wrapv && !TYPE_UNSIGNED (type))
+ return false;
- /* Try taking additional conditions into account. */
- cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
- invert_truthvalue (additional),
- cond);
- if (nonzero_p (cond))
- return new_step;
+ unsigned_type = unsigned_type_for (type);
+ delta = fold_convert (unsigned_type, delta);
+ step_abs = fold_convert (unsigned_type, step_abs);
+ valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
- return NULL_TREE;
+ estimate_numbers_of_iterations_loop (loop);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
+ return false;
+
+ /* At this point we still don't have a proof that the iv does not
+ overflow: give up. */
+ return true;
}
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
- at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
- LOOP. If it is possible, return the value of step of the induction variable
- in the TYPE, otherwise return NULL_TREE. */
+/* Return the conversion to NEW_TYPE of the STEP of an induction
+ variable BASE + STEP * I at AT_STMT. */
tree
-can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
- tree at_stmt)
+convert_step (struct loop *loop, tree new_type, tree base, tree step,
+ tree at_stmt)
{
- struct nb_iter_bound *bound;
- tree new_step;
+ tree base_type = TREE_TYPE (base);
- for (bound = loop->bounds; bound; bound = bound->next)
- {
- new_step = can_count_iv_in_wider_type_bound (type, base, step,
- at_stmt,
- bound->bound,
- bound->additional,
- bound->at_stmt);
-
- if (new_step)
- return new_step;
- }
+ /* When not using wrapping arithmetic, signed types don't wrap. */
+ if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
+ return fold_convert (new_type, step);
- return NULL_TREE;
+ if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
+ return convert_step_widening (loop, new_type, base, step, at_stmt);
+
+ return fold_convert (new_type, step);
}
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
free_numbers_of_iterations_estimates_loop (loop);
}
}
+
+/* Substitute value VAL for ssa name NAME inside expressions held
+ at LOOP. */
+
+void
+substitute_in_loop_info (struct loop *loop, tree name, tree val)
+{
+ struct nb_iter_bound *bound;
+
+ loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
+ loop->estimated_nb_iterations
+ = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ {
+ bound->bound = simplify_replace_tree (bound->bound, name, val);
+ bound->additional = simplify_replace_tree (bound->additional, name, val);
+ }
+}
OSDN Git Service
