#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "cfghooks.h"
+#include "tree.h"
+#include "gimple.h"
+#include "rtl.h"
+#include "ssa.h"
#include "flags.h"
-#include "hash-set.h"
-#include "machmode.h"
-#include "vec.h"
-#include "double-int.h"
-#include "input.h"
#include "alias.h"
-#include "symtab.h"
-#include "wide-int.h"
-#include "inchash.h"
-#include "tree.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "calls.h"
-#include "predict.h"
-#include "hard-reg-set.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
#include "cfganal.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "gimple-fold.h"
#include "tree-eh.h"
-#include "gimple-expr.h"
-#include "is-a.h"
-#include "gimple.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
-#include "gimple-ssa.h"
#include "tree-cfg.h"
-#include "tree-phinodes.h"
-#include "ssa-iterators.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
#include "tree-ssa-threadupdate.h"
-#include "hashtab.h"
-#include "rtl.h"
-#include "statistics.h"
-#include "real.h"
-#include "fixed-value.h"
#include "insn-config.h"
#include "expmed.h"
#include "dojump.h"
#include "expr.h"
#include "insn-codes.h"
#include "optabs.h"
+#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
if (is_new)
{
/* Do not allow transitions up the lattice. The following
- is slightly more awkward than just new_vr->type < old_vr->type
+ is slightly more awkward than just new_vr->type < old_vr->type
because VR_RANGE and VR_ANTI_RANGE need to be considered
the same. We may not have is_new when transitioning to
- UNDEFINED or from VARYING. */
- if (new_vr->type == VR_UNDEFINED
- || old_vr->type == VR_VARYING)
- set_value_range_to_varying (old_vr);
+ UNDEFINED. If old_vr->type is VARYING, we shouldn't be
+ called. */
+ if (new_vr->type == VR_UNDEFINED)
+ {
+ BITMAP_FREE (new_vr->equiv);
+ set_value_range_to_varying (old_vr);
+ set_value_range_to_varying (new_vr);
+ return true;
+ }
else
set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
new_vr->equiv);
strict_overflow_p);
}
-/* Return true if STMT is know to to compute a non-negative value.
+/* Return true if STMT is know to compute a non-negative value.
If the return value is based on the assumption that signed overflow is
undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
*STRICT_OVERFLOW_P.*/
prod3. */
/* min0min1 > max0max1 */
if (wi::gts_p (prod0, prod3))
- {
- vrp_int tmp = prod3;
- prod3 = prod0;
- prod0 = tmp;
- }
+ std::swap (prod0, prod3);
/* min0max1 > max0min1 */
if (wi::gts_p (prod1, prod2))
- {
- vrp_int tmp = prod2;
- prod2 = prod1;
- prod1 = tmp;
- }
+ std::swap (prod1, prod2);
if (wi::gts_p (prod0, prod1))
- {
- vrp_int tmp = prod1;
- prod1 = prod0;
- prod0 = tmp;
- }
+ std::swap (prod0, prod1);
if (wi::gts_p (prod2, prod3))
- {
- vrp_int tmp = prod3;
- prod3 = prod2;
- prod2 = tmp;
- }
+ std::swap (prod2, prod3);
/* diff = max - min. */
prod2 = prod3 - prod0;
and all numbers from min to 0 for negative min. */
cmp = compare_values (vr0.max, zero);
if (cmp == -1)
- max = zero;
+ {
+ /* When vr0.max < 0, vr1.min != 0 and value
+ ranges for dividend and divisor are available. */
+ if (vr1.type == VR_RANGE
+ && !symbolic_range_p (&vr0)
+ && !symbolic_range_p (&vr1)
+ && !compare_values (vr1.min, zero))
+ max = int_const_binop (code, vr0.max, vr1.min);
+ else
+ max = zero;
+ }
else if (cmp == 0 || cmp == 1)
max = vr0.max;
else
type = VR_VARYING;
cmp = compare_values (vr0.min, zero);
if (cmp == 1)
- min = zero;
+ {
+ /* For unsigned division when value ranges for dividend
+ and divisor are available. */
+ if (vr1.type == VR_RANGE
+ && !symbolic_range_p (&vr0)
+ && !symbolic_range_p (&vr1))
+ min = int_const_binop (code, vr0.min, vr1.max);
+ else
+ min = zero;
+ }
else if (cmp == 0 || cmp == -1)
min = vr0.min;
else
}
else if (code == TRUNC_MOD_EXPR)
{
- if (vr1.type != VR_RANGE
- || range_includes_zero_p (vr1.min, vr1.max) != 0
- || vrp_val_is_min (vr1.min))
+ if (range_is_null (&vr1))
{
- set_value_range_to_varying (vr);
+ set_value_range_to_undefined (vr);
return;
}
+ /* ABS (A % B) < ABS (B) and either
+ 0 <= A % B <= A or A <= A % B <= 0. */
type = VR_RANGE;
- /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */
- max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
- if (tree_int_cst_lt (max, vr1.max))
- max = vr1.max;
- max = int_const_binop (MINUS_EXPR, max, build_int_cst (TREE_TYPE (max), 1));
- /* If the dividend is non-negative the modulus will be
- non-negative as well. */
- if (TYPE_UNSIGNED (expr_type)
- || value_range_nonnegative_p (&vr0))
- min = build_int_cst (TREE_TYPE (max), 0);
+ signop sgn = TYPE_SIGN (expr_type);
+ unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int wmin, wmax, tmp;
+ wide_int zero = wi::zero (prec);
+ wide_int one = wi::one (prec);
+ if (vr1.type == VR_RANGE && !symbolic_range_p (&vr1))
+ {
+ wmax = wi::sub (vr1.max, one);
+ if (sgn == SIGNED)
+ {
+ tmp = wi::sub (wi::minus_one (prec), vr1.min);
+ wmax = wi::smax (wmax, tmp);
+ }
+ }
+ else
+ {
+ wmax = wi::max_value (prec, sgn);
+ /* X % INT_MIN may be INT_MAX. */
+ if (sgn == UNSIGNED)
+ wmax = wmax - one;
+ }
+
+ if (sgn == UNSIGNED)
+ wmin = zero;
else
- min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
+ {
+ wmin = -wmax;
+ if (vr0.type == VR_RANGE && TREE_CODE (vr0.min) == INTEGER_CST)
+ {
+ tmp = vr0.min;
+ if (wi::gts_p (tmp, zero))
+ tmp = zero;
+ wmin = wi::smax (wmin, tmp);
+ }
+ }
+
+ if (vr0.type == VR_RANGE && TREE_CODE (vr0.max) == INTEGER_CST)
+ {
+ tmp = vr0.max;
+ if (sgn == SIGNED && wi::neg_p (tmp))
+ tmp = zero;
+ wmax = wi::min (wmax, tmp, sgn);
+ }
+
+ min = wide_int_to_tree (expr_type, wmin);
+ max = wide_int_to_tree (expr_type, wmax);
}
else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
{
/* Extract range information from a unary operation CODE based on
the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE.
- The The resulting range is stored in *VR. */
+ The resulting range is stored in *VR. */
static void
extract_range_from_unary_expr_1 (value_range_t *vr,
{
/* If the range was reversed, swap MIN and MAX. */
if (cmp == 1)
- {
- tree t = min;
- min = max;
- max = t;
- }
+ std::swap (min, max);
}
cmp = compare_values (min, max);
operands around and change the comparison code. */
if (comp == GT_EXPR || comp == GE_EXPR)
{
- value_range_t *tmp;
comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
- tmp = vr0;
- vr0 = vr1;
- vr1 = tmp;
+ std::swap (vr0, vr1);
}
if (comp == EQ_EXPR)
/* In the case of post-in/decrement tests like if (i++) ... and uses
of the in/decremented value on the edge the extra name we want to
assert for is not on the def chain of the name compared. Instead
- it is in the set of use stmts. */
+ it is in the set of use stmts.
+ Similar cases happen for conversions that were simplified through
+ fold_{sign_changed,widened}_comparison. */
if ((comp_code == NE_EXPR
|| comp_code == EQ_EXPR)
&& TREE_CODE (val) == INTEGER_CST)
gimple use_stmt;
FOR_EACH_IMM_USE_STMT (use_stmt, ui, name)
{
- /* Cut off to use-stmts that are in the predecessor. */
- if (gimple_bb (use_stmt) != e->src)
- continue;
-
if (!is_gimple_assign (use_stmt))
continue;
- enum tree_code code = gimple_assign_rhs_code (use_stmt);
- if (code != PLUS_EXPR
- && code != MINUS_EXPR)
+ /* Cut off to use-stmts that are dominating the predecessor. */
+ if (!dominated_by_p (CDI_DOMINATORS, e->src, gimple_bb (use_stmt)))
continue;
- tree cst = gimple_assign_rhs2 (use_stmt);
- if (TREE_CODE (cst) != INTEGER_CST)
+ tree name2 = gimple_assign_lhs (use_stmt);
+ if (TREE_CODE (name2) != SSA_NAME
+ || !live_on_edge (e, name2))
continue;
- tree name2 = gimple_assign_lhs (use_stmt);
- if (live_on_edge (e, name2))
+ enum tree_code code = gimple_assign_rhs_code (use_stmt);
+ tree cst;
+ if (code == PLUS_EXPR
+ || code == MINUS_EXPR)
{
+ cst = gimple_assign_rhs2 (use_stmt);
+ if (TREE_CODE (cst) != INTEGER_CST)
+ continue;
cst = int_const_binop (code, val, cst);
- register_new_assert_for (name2, name2, comp_code, cst,
- NULL, e, bsi);
}
+ else if (CONVERT_EXPR_CODE_P (code))
+ {
+ /* For truncating conversions we cannot record
+ an inequality. */
+ if (comp_code == NE_EXPR
+ && (TYPE_PRECISION (TREE_TYPE (name2))
+ < TYPE_PRECISION (TREE_TYPE (name))))
+ continue;
+ cst = fold_convert (TREE_TYPE (name2), val);
+ }
+ else
+ continue;
+
+ if (TREE_OVERFLOW_P (cst))
+ cst = drop_tree_overflow (cst);
+ register_new_assert_for (name2, name2, comp_code, cst,
+ NULL, e, bsi);
}
}
up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound,
build_int_cst (TREE_TYPE (up_bound), 1));
+ /* Empty array. */
+ if (tree_int_cst_equal (low_bound, up_bound_p1))
+ {
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is above array bounds");
+ TREE_NO_WARNING (ref) = 1;
+ }
+
if (TREE_CODE (low_sub) == SSA_NAME)
{
vr = get_value_range (low_sub);
if (vr && vr->type == VR_ANTI_RANGE)
{
if (TREE_CODE (up_sub) == INTEGER_CST
- && tree_int_cst_lt (up_bound, up_sub)
+ && (ignore_off_by_one
+ ? tree_int_cst_lt (up_bound, up_sub)
+ : tree_int_cst_le (up_bound, up_sub))
&& TREE_CODE (low_sub) == INTEGER_CST
- && tree_int_cst_lt (low_sub, low_bound))
+ && tree_int_cst_le (low_sub, low_bound))
{
warning_at (location, OPT_Warray_bounds,
"array subscript is outside array bounds");
}
else if (TREE_CODE (up_sub) == INTEGER_CST
&& (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))))
+ ? !tree_int_cst_le (up_sub, up_bound_p1)
+ : !tree_int_cst_le (up_sub, up_bound)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
static void
search_for_addr_array (tree t, location_t location)
{
- while (TREE_CODE (t) == SSA_NAME)
- {
- gimple g = SSA_NAME_DEF_STMT (t);
-
- if (gimple_code (g) != GIMPLE_ASSIGN)
- return;
-
- if (get_gimple_rhs_class (gimple_assign_rhs_code (g))
- != GIMPLE_SINGLE_RHS)
- return;
-
- t = gimple_assign_rhs1 (g);
- }
-
-
- /* We are only interested in addresses of ARRAY_REF's. */
- if (TREE_CODE (t) != ADDR_EXPR)
- return;
-
/* Check each ARRAY_REFs in the reference chain. */
do
{
if (TREE_CODE (t) == ARRAY_REF)
check_array_ref (location, t, false /*ignore_off_by_one*/);
- if (TREE_CODE (t) == MEM_REF
- || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
- search_for_addr_array (TREE_OPERAND (t, 0), location);
-
- if (TREE_CODE (t) == ADDR_EXPR)
- *walk_subtree = FALSE;
+ else if (TREE_CODE (t) == ADDR_EXPR)
+ {
+ search_for_addr_array (t, location);
+ *walk_subtree = FALSE;
+ }
return NULL_TREE;
}
{
gimple stmt = gsi_stmt (si);
struct walk_stmt_info wi;
- if (!gimple_has_location (stmt))
+ if (!gimple_has_location (stmt)
+ || is_gimple_debug (stmt))
continue;
- if (is_gimple_call (stmt))
- {
- size_t i;
- size_t n = gimple_call_num_args (stmt);
- for (i = 0; i < n; i++)
- {
- tree arg = gimple_call_arg (stmt, i);
- search_for_addr_array (arg, gimple_location (stmt));
- }
- }
- else
- {
- memset (&wi, 0, sizeof (wi));
- wi.info = CONST_CAST (void *, (const void *)
- gimple_location_ptr (stmt));
+ memset (&wi, 0, sizeof (wi));
+ wi.info = CONST_CAST (void *, (const void *)
+ gimple_location_ptr (stmt));
- walk_gimple_op (gsi_stmt (si),
- check_array_bounds,
- &wi);
- }
+ walk_gimple_op (gsi_stmt (si),
+ check_array_bounds,
+ &wi);
}
}
}
&& (cmp_min != 0 || cmp_max != 0))
goto varying;
- /* If the new minimum is larger than than the previous one
+ /* If the new minimum is larger than the previous one
retain the old value. If the new minimum value is smaller
than the previous one and not -INF go all the way to -INF + 1.
In the first case, to avoid infinite bouncing between different
fprintf (dump_file, "\n");
}
+ if (vr_result.type == VR_VARYING)
+ return SSA_PROP_VARYING;
+
return SSA_PROP_INTERESTING;
}
return simplify_stmt_using_ranges (si);
}
-/* Stack of dest,src equivalency pairs that need to be restored after
- each attempt to thread a block's incoming edge to an outgoing edge.
-
- A NULL entry is used to mark the end of pairs which need to be
- restored. */
-static vec<tree> equiv_stack;
+/* Unwindable const/copy equivalences. */
+const_and_copies *equiv_stack;
/* A trivial wrapper so that we can present the generic jump threading
code with a simple API for simplifying statements. STMT is the
/* Allocate our unwinder stack to unwind any temporary equivalences
that might be recorded. */
- equiv_stack.create (20);
+ equiv_stack = new const_and_copies (dump_file, dump_flags);
/* To avoid lots of silly node creation, we create a single
conditional and just modify it in-place when attempting to
if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
continue;
- thread_across_edge (dummy, e, true, &equiv_stack,
+ thread_across_edge (dummy, e, true, equiv_stack,
simplify_stmt_for_jump_threading);
}
}
finalize_jump_threads (void)
{
thread_through_all_blocks (false);
- equiv_stack.release ();
+ delete equiv_stack;
}
|| (vr_value[i]->type == VR_UNDEFINED))
continue;
- if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
- && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
- && (vr_value[i]->type == VR_RANGE
- || vr_value[i]->type == VR_ANTI_RANGE))
- set_range_info (name, vr_value[i]->type, vr_value[i]->min,
- vr_value[i]->max);
+ if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
+ && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
+ && (vr_value[i]->type == VR_RANGE
+ || vr_value[i]->type == VR_ANTI_RANGE))
+ set_range_info (name, vr_value[i]->type, vr_value[i]->min,
+ vr_value[i]->max);
}
/* Free allocated memory. */
projects / gcc.git / blobdiff