/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
#include "tree-dump.h"
#include "timevar.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "toplev.h"
#include "intl.h"
#include "cfgloop.h"
&& integer_zerop (vr->max);
}
+/* Return true if max and min of VR are INTEGER_CST. It's not necessary
+ a singleton. */
+
+static inline bool
+range_int_cst_p (value_range_t *vr)
+{
+ return (vr->type == VR_RANGE
+ && TREE_CODE (vr->max) == INTEGER_CST
+ && TREE_CODE (vr->min) == INTEGER_CST
+ && !TREE_OVERFLOW (vr->max)
+ && !TREE_OVERFLOW (vr->min));
+}
+
+/* Return true if VR is a INTEGER_CST singleton. */
+
+static inline bool
+range_int_cst_singleton_p (value_range_t *vr)
+{
+ return (range_int_cst_p (vr)
+ && tree_int_cst_equal (vr->min, vr->max));
+}
/* Return true if value range VR involves at least one symbol. */
{
value_range_t *vr = get_value_range (t);
+ if (INTEGRAL_TYPE_P (t)
+ && TYPE_UNSIGNED (t))
+ return true;
+
if (!vr)
return false;
res = int_const_binop (code, val1, val2, 0);
- /* If we are not using wrapping arithmetic, operate symbolically
- on -INF and +INF. */
- if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If we are using unsigned arithmetic, operate symbolically
+ on -INF and +INF as int_const_binop only handles signed overflow. */
+ if (TYPE_UNSIGNED (TREE_TYPE (val1)))
{
int checkz = compare_values (res, val1);
bool overflow = false;
}
}
+ else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If the singed operation wraps then int_const_binop has done
+ everything we want. */
+ ;
else if ((TREE_OVERFLOW (res)
&& !TREE_OVERFLOW (val1)
&& !TREE_OVERFLOW (val2))
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
&& code != RSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
}
}
}
+ else if (code == TRUNC_MOD_EXPR)
+ {
+ bool sop = false;
+ if (vr1.type != VR_RANGE
+ || symbolic_range_p (&vr1)
+ || range_includes_zero_p (&vr1)
+ || vrp_val_is_min (vr1.min))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ type = VR_RANGE;
+ /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */
+ max = fold_unary_to_constant (ABS_EXPR, TREE_TYPE (vr1.min), vr1.min);
+ if (tree_int_cst_lt (max, vr1.max))
+ max = vr1.max;
+ max = int_const_binop (MINUS_EXPR, max, integer_one_node, 0);
+ /* If the dividend is non-negative the modulus will be
+ non-negative as well. */
+ if (TYPE_UNSIGNED (TREE_TYPE (max))
+ || (vrp_expr_computes_nonnegative (op0, &sop) && !sop))
+ min = build_int_cst (TREE_TYPE (max), 0);
+ else
+ min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), max);
+ }
else if (code == MINUS_EXPR)
{
/* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
}
else if (code == BIT_AND_EXPR)
{
- if (vr0.type == VR_RANGE
- && vr0.min == vr0.max
- && TREE_CODE (vr0.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr0.max)
- && tree_int_cst_sgn (vr0.max) >= 0)
+ bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
+
+ vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
+ vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
+
+ if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
+ min = max = int_const_binop (code, vr0.max, vr1.max, 0);
+ else if (vr0_int_cst_singleton_p
+ && tree_int_cst_sgn (vr0.max) >= 0)
{
min = build_int_cst (expr_type, 0);
max = vr0.max;
}
- else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && TREE_CODE (vr1.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr1.max)
+ else if (vr1_int_cst_singleton_p
&& tree_int_cst_sgn (vr1.max) >= 0)
{
type = VR_RANGE;
}
else if (code == BIT_IOR_EXPR)
{
- if (vr0.type == VR_RANGE
- && vr1.type == VR_RANGE
- && TREE_CODE (vr0.min) == INTEGER_CST
- && TREE_CODE (vr1.min) == INTEGER_CST
- && TREE_CODE (vr0.max) == INTEGER_CST
- && TREE_CODE (vr1.max) == INTEGER_CST
+ if (range_int_cst_p (&vr0)
+ && range_int_cst_p (&vr1)
&& tree_int_cst_sgn (vr0.min) >= 0
&& tree_int_cst_sgn (vr1.min) >= 0)
{
|| vr0.type == VR_ANTI_RANGE)
&& TREE_CODE (vr0.min) == INTEGER_CST
&& TREE_CODE (vr0.max) == INTEGER_CST
- && !is_overflow_infinity (vr0.min)
- && !is_overflow_infinity (vr0.max)
+ && (!is_overflow_infinity (vr0.min)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
+ && (!is_overflow_infinity (vr0.max)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
&& (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
|| (vr0.type == VR_RANGE
&& integer_zerop (int_const_binop (RSHIFT_EXPR,
new_max = force_fit_type_double (outer_type,
TREE_INT_CST_LOW (vr0.max),
TREE_INT_CST_HIGH (vr0.max), 0, 0);
+ if (is_overflow_infinity (vr0.min))
+ new_min = negative_overflow_infinity (outer_type);
+ if (is_overflow_infinity (vr0.max))
+ new_max = positive_overflow_infinity (outer_type);
set_and_canonicalize_value_range (vr, vr0.type,
new_min, new_max, NULL);
return;
adjust_range_with_scev (value_range_t *vr, struct loop *loop,
gimple stmt, tree var)
{
- tree init, step, chrec, tmin, tmax, min, max, type;
+ tree init, step, chrec, tmin, tmax, min, max, type, tem;
enum ev_direction dir;
/* TODO. Don't adjust anti-ranges. An anti-range may provide
return;
init = initial_condition_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (init);
+ if (tem)
+ init = tem;
step = evolution_part_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (step);
+ if (tem)
+ step = tem;
/* If STEP is symbolic, we can't know whether INIT will be the
minimum or maximum value in the range. Also, unless INIT is
return true;
l = loop_containing_stmt (stmt);
- if (l == NULL)
+ if (l == NULL
+ || !loop_outer (l))
return true;
chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
edge_iterator ei;
edge e;
+ /* If we have X <=> X do not insert an assert expr for that. */
+ if (loc->expr == loc->val)
+ return false;
+
cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_stmt = build_assert_expr_for (cond, name);
if (loc->e)
{
value_range_t* vr = NULL;
tree low_sub, up_sub;
- tree low_bound, up_bound = array_ref_up_bound (ref);
+ tree low_bound, up_bound, up_bound_p1;
+ tree base;
+
+ if (TREE_NO_WARNING (ref))
+ return;
low_sub = up_sub = TREE_OPERAND (ref, 1);
+ up_bound = array_ref_up_bound (ref);
- if (!up_bound || TREE_NO_WARNING (ref)
- || TREE_CODE (up_bound) != INTEGER_CST
- /* Can not check flexible arrays. */
- || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
- && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
- && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
- /* Accesses after the end of arrays of size 0 (gcc
- extension) and 1 are likely intentional ("struct
- hack"). */
- || compare_tree_int (up_bound, 1) <= 0)
+ /* Can not check flexible arrays. */
+ if (!up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST)
return;
+ /* Accesses to trailing arrays via pointers may access storage
+ beyond the types array bounds. */
+ base = get_base_address (ref);
+ if (base
+ && INDIRECT_REF_P (base))
+ {
+ tree cref, next = NULL_TREE;
+
+ if (TREE_CODE (TREE_OPERAND (ref, 0)) != COMPONENT_REF)
+ return;
+
+ cref = TREE_OPERAND (ref, 0);
+ if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
+ for (next = TREE_CHAIN (TREE_OPERAND (cref, 1));
+ next && TREE_CODE (next) != FIELD_DECL;
+ next = TREE_CHAIN (next))
+ ;
+
+ /* If this is the last field in a struct type or a field in a
+ union type do not warn. */
+ if (!next)
+ return;
+ }
+
low_bound = array_ref_low_bound (ref);
+ up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, integer_one_node, 0);
if (TREE_CODE (low_sub) == SSA_NAME)
{
}
}
else if (TREE_CODE (up_sub) == INTEGER_CST
- && tree_int_cst_lt (up_bound, up_sub)
- && !tree_int_cst_equal (up_bound, up_sub)
- && (!ignore_off_by_one
- || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
- up_bound,
- integer_one_node,
- 0),
- up_sub)))
+ && (ignore_off_by_one
+ ? (tree_int_cst_lt (up_bound, up_sub)
+ && !tree_int_cst_equal (up_bound_p1, up_sub))
+ : (tree_int_cst_lt (up_bound, up_sub)
+ || tree_int_cst_equal (up_bound_p1, up_sub))))
{
warning_at (location, OPT_Warray_bounds,
"array subscript is above array bounds");
FOR_EACH_BB (bb)
{
- /* Skip bb's that are clearly unreachable. */
- if (single_pred_p (bb))
- {
- int i;
- bool reachable = true;
- edge e2;
- edge e = EDGE_PRED (bb, 0);
- basic_block pred_bb = e->src;
- gimple ls = NULL;
-
- for (i = 0; VEC_iterate (edge, to_remove_edges, i, e2); ++i)
- if (e == e2)
- {
- reachable = false;
- break;
- }
-
- if (!reachable)
- continue;
+ edge_iterator ei;
+ edge e;
+ bool executable = false;
- if (!gsi_end_p (gsi_last_bb (pred_bb)))
- ls = gsi_stmt (gsi_last_bb (pred_bb));
+ /* Skip blocks that were found to be unreachable. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ executable |= !!(e->flags & EDGE_EXECUTABLE);
+ if (!executable)
+ continue;
- if (ls && gimple_code (ls) == GIMPLE_COND
- && ((gimple_cond_false_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
- || (gimple_cond_true_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
- continue;
- }
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
gimple stmt = gsi_stmt (si);
&& TYPE_MAX_VALUE (TREE_TYPE (lhs)))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
- struct loop *l;
value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
if (code == GIMPLE_CALL)
else
extract_range_from_assignment (&new_vr, stmt);
- /* If STMT is inside a loop, we may be able to know something
- else about the range of LHS by examining scalar evolution
- information. */
- if (current_loops && (l = loop_containing_stmt (stmt)))
- adjust_range_with_scev (&new_vr, l, stmt, lhs);
-
if (update_value_range (lhs, &new_vr))
{
*output_p = lhs;
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
int edges, old_edges;
+ struct loop *l;
copy_value_range (&vr_result, lhs_vr);
}
}
+ /* If this is a loop PHI node SCEV may known more about its
+ value-range. */
+ if (current_loops
+ && (l = loop_containing_stmt (phi))
+ && l->header == gimple_bb (phi))
+ adjust_range_with_scev (&vr_result, l, phi, lhs);
+
if (vr_result.type == VR_VARYING)
goto varying;
/* If the new range is different than the previous value, keep
iterating. */
if (update_value_range (lhs, &vr_result))
- return SSA_PROP_INTERESTING;
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found new range for ");
+ print_generic_expr (dump_file, lhs, 0);
+ fprintf (dump_file, ": ");
+ dump_value_range (dump_file, &vr_result);
+ fprintf (dump_file, "\n\n");
+ }
+
+ return SSA_PROP_INTERESTING;
+ }
/* Nothing changed, don't add outgoing edges. */
return SSA_PROP_NOT_INTERESTING;
fprintf (dump_file, "removing unreachable case label\n");
}
VEC_safe_push (edge, heap, to_remove_edges, e);
+ e->flags &= ~EDGE_EXECUTABLE;
}
/* And queue an update for the stmt. */
substitute_and_fold (single_val_range, vrp_fold_stmt);
if (warn_array_bounds)
- check_all_array_refs ();
+ check_all_array_refs ();
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */