#include "timevar.h"
#include "diagnostic.h"
#include "toplev.h"
+#include "intl.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
static int compare_values (tree val1, tree val2);
static int compare_values_warnv (tree val1, tree val2, bool *);
static void vrp_meet (value_range_t *, value_range_t *);
+static tree vrp_evaluate_conditional_warnv (tree, bool, bool *);
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
|| is_overflow_infinity (vr->max)));
}
+/* Return false if we can not make a valid comparison based on VR;
+ this will be the case if it uses an overflow infinity and overflow
+ is not undefined (i.e., -fno-strict-overflow is in effect).
+ Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
+ uses an overflow infinity. */
+
+static bool
+usable_range_p (value_range_t *vr, bool *strict_overflow_p)
+{
+ gcc_assert (vr->type == VR_RANGE);
+ if (is_overflow_infinity (vr->min))
+ {
+ *strict_overflow_p = true;
+ if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
+ return false;
+ }
+ if (is_overflow_infinity (vr->max))
+ {
+ *strict_overflow_p = true;
+ if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
+ return false;
+ }
+ return true;
+}
+
+
/* Like tree_expr_nonnegative_warnv_p, but this function uses value
ranges obtained so far. */
{
tree tcmp;
+ fold_defer_overflow_warnings ();
+
tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
+
+ fold_undefer_and_ignore_overflow_warnings ();
+
if (!tcmp)
return -2;
infinities. */
if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
{
- if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
- return -2;
-
+ if (strict_overflow_p != NULL)
+ *strict_overflow_p = true;
if (is_negative_overflow_infinity (val1))
return is_negative_overflow_infinity (val2) ? 0 : -1;
else if (is_negative_overflow_infinity (val2))
}
}
-/* Compare values like compare_values_warnv, but treat comparisons
- which rely on undefined overflow as incomparable. */
+/* Compare values like compare_values_warnv, but treat comparisons of
+ nonconstants which rely on undefined overflow as incomparable. */
static int
compare_values (tree val1, tree val2)
sop = false;
ret = compare_values_warnv (val1, val2, &sop);
- if (sop)
+ if (sop
+ && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
ret = -2;
return ret;
}
/* If the maximum value forces us to be out of bounds, simply punt.
It would be pointless to try and do anything more since this
all should be optimized away above us. */
- if (cond_code == LT_EXPR && compare_values (max, min) == 0)
+ if ((cond_code == LT_EXPR
+ && compare_values (max, min) == 0)
+ || is_overflow_infinity (max))
set_value_range_to_varying (vr_p);
else
{
/* For LT_EXPR, we create the range [MIN, MAX - 1]. */
- if (cond_code == LT_EXPR
- && !is_positive_overflow_infinity (max))
+ if (cond_code == LT_EXPR)
{
tree one = build_int_cst (type, 1);
max = fold_build2 (MINUS_EXPR, type, max, one);
/* If the minimum value forces us to be out of bounds, simply punt.
It would be pointless to try and do anything more since this
all should be optimized away above us. */
- if (cond_code == GT_EXPR && compare_values (min, max) == 0)
+ if ((cond_code == GT_EXPR
+ && compare_values (min, max) == 0)
+ || is_overflow_infinity (min))
set_value_range_to_varying (vr_p);
else
{
/* For GT_EXPR, we create the range [MIN + 1, MAX]. */
- if (cond_code == GT_EXPR
- && !is_negative_overflow_infinity (min))
+ if (cond_code == GT_EXPR)
{
tree one = build_int_cst (type, 1);
min = fold_build2 (PLUS_EXPR, type, min, one);
&& !supports_overflow_infinity (TREE_TYPE (res)))
return NULL_TREE;
- /* We have to punt on subtracting infinities of the same sign,
- since we can't tell what the sign of the result should
- be. */
- if (code == MINUS_EXPR
- && sgn1 == sgn2
+ /* We have to punt on adding infinities of different signs,
+ since we can't tell what the sign of the result should be.
+ Likewise for subtracting infinities of the same sign. */
+ if (((code == PLUS_EXPR && sgn1 != sgn2)
+ || (code == MINUS_EXPR && sgn1 == sgn2))
&& is_overflow_infinity (val1)
&& is_overflow_infinity (val2))
return NULL_TREE;
+ /* Don't try to handle division or shifting of infinities. */
+ if ((code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR)
+ && (is_overflow_infinity (val1)
+ || is_overflow_infinity (val2)))
+ return NULL_TREE;
+
/* Notice that we only need to handle the restricted set of
operations handled by extract_range_from_binary_expr.
Among them, only multiplication, addition and subtraction
if ((code == MULT_EXPR && sgn1 == sgn2)
/* For addition, the operands must be of the same sign
to yield an overflow. Its sign is therefore that
- of one of the operands, for example the first. */
- || (code == PLUS_EXPR && sgn1 > 0)
+ of one of the operands, for example the first. For
+ infinite operands X + -INF is negative, not positive. */
+ || (code == PLUS_EXPR
+ && (sgn1 >= 0
+ ? !is_negative_overflow_infinity (val2)
+ : is_positive_overflow_infinity (val2)))
/* For subtraction, non-infinite operands must be of
different signs to yield an overflow. Its sign is
therefore that of the first operand or the opposite of
&& (sgn1 >= 0
? !is_positive_overflow_infinity (val2)
: is_negative_overflow_infinity (val2)))
+ /* We only get in here with positive shift count, so the
+ overflow direction is the same as the sign of val1.
+ Actually rshift does not overflow at all, but we only
+ handle the case of shifting overflowed -INF and +INF. */
+ || (code == RSHIFT_EXPR
+ && sgn1 >= 0)
/* For division, the only case is -INF / -1 = +INF. */
|| code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != RSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR)
{
tree val[4];
size_t i;
return;
}
+ /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
+ then drop to VR_VARYING. Outside of this range we get undefined
+ behaviour from the shift operation. We cannot even trust
+ SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
+ shifts, and the operation at the tree level may be widened. */
+ if (code == RSHIFT_EXPR)
+ {
+ if (vr1.type == VR_ANTI_RANGE
+ || !vrp_expr_computes_nonnegative (op1, &sop)
+ || (operand_less_p
+ (build_int_cst (TREE_TYPE (vr1.max),
+ TYPE_PRECISION (TREE_TYPE (expr)) - 1),
+ vr1.max) != 0))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
+
/* Multiplications and divisions are a bit tricky to handle,
depending on the mix of signs we have in the two ranges, we
need to operate on different values to get the minimum and
the new range. */
/* Divisions by zero result in a VARYING value. */
- if (code != MULT_EXPR
- && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
+ else if (code != MULT_EXPR
+ && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
{
set_value_range_to_varying (vr);
return;
return;
}
+ /* We punt if:
+ 1) [-INF, +INF]
+ 2) [-INF, +-INF(OVF)]
+ 3) [+-INF(OVF), +INF]
+ 4) [+-INF(OVF), +-INF(OVF)]
+ We learn nothing when we have INF and INF(OVF) on both sides.
+ Note that we do accept [-INF, -INF] and [+INF, +INF] without
+ overflow. */
if ((min == TYPE_MIN_VALUE (TREE_TYPE (min))
- || is_negative_overflow_infinity (min))
+ || is_overflow_infinity (min))
&& (max == TYPE_MAX_VALUE (TREE_TYPE (max))
- || is_positive_overflow_infinity (max)))
+ || is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
extract_range_from_comparison (value_range_t *vr, tree expr)
{
bool sop = false;
- tree val = vrp_evaluate_conditional (expr, false, &sop);
+ tree val = vrp_evaluate_conditional_warnv (expr, false, &sop);
/* A disadvantage of using a special infinity as an overflow
representation is that we lose the ability to record overflow
return NULL_TREE;
}
+ if (!usable_range_p (vr0, strict_overflow_p)
+ || !usable_range_p (vr1, strict_overflow_p))
+ return NULL_TREE;
+
/* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
operands around and change the comparison code. */
if (comp == GT_EXPR || comp == GE_EXPR)
return NULL_TREE;
}
+ if (!usable_range_p (vr, strict_overflow_p))
+ return NULL_TREE;
+
if (comp == EQ_EXPR)
{
/* EQ_EXPR may only be computed if VR represents exactly
if (COMPARISON_CLASS_P (cond))
{
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
- assertion = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (v), n, a);
+ assertion = build_gimple_modify_stmt (n, a);
}
else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
gcc_assert (op0 == v);
- assertion = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (v), n,
- boolean_false_node);
+ assertion = build_gimple_modify_stmt (n, boolean_false_node);
}
else if (TREE_CODE (cond) == SSA_NAME)
{
/* Given V, build the assignment N = true. */
gcc_assert (v == cond);
- assertion = build2 (GIMPLE_MODIFY_STMT,
- TREE_TYPE (v), n, boolean_true_node);
+ assertion = build_gimple_modify_stmt (n, boolean_true_node);
}
else
gcc_unreachable ();
non-NULL if -fdelete-null-pointer-checks is enabled. */
if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
{
- bool is_store;
- unsigned num_uses, num_derefs;
+ unsigned num_uses, num_loads, num_stores;
- count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
- if (num_derefs > 0)
+ count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
+ if (num_loads + num_stores > 0)
{
*val_p = build_int_cst (TREE_TYPE (op), 0);
*comp_code_p = NE_EXPR;
}
else if (TREE_CODE (rhs) == NOP_EXPR
|| TREE_CODE (rhs) == CONVERT_EXPR
- || TREE_CODE (rhs) == VIEW_CONVERT_EXPR
|| TREE_CODE (rhs) == NON_LVALUE_EXPR)
{
/* Recurse through the type conversion. */
/* Determine whether the outgoing edges of BB should receive an
ASSERT_EXPR for each of the operands of BB's LAST statement.
- The last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
+ The last statement of BB must be a COND_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
return need_assert;
}
+/* Compare two case labels sorting first by the destination label uid
+ and then by the case value. */
+
+static int
+compare_case_labels (const void *p1, const void *p2)
+{
+ tree case1 = *(tree *)p1;
+ tree case2 = *(tree *)p2;
+ unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
+ unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
+
+ if (uid1 < uid2)
+ return -1;
+ else if (uid1 == uid2)
+ {
+ /* Make sure the default label is first in a group. */
+ if (!CASE_LOW (case1))
+ return -1;
+ else if (!CASE_LOW (case2))
+ return 1;
+ else
+ return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
+ }
+ else
+ return 1;
+}
+
+/* Determine whether the outgoing edges of BB should receive an
+ ASSERT_EXPR for each of the operands of BB's LAST statement.
+ The last statement of BB must be a SWITCH_EXPR.
+
+ If any of the sub-graphs rooted at BB have an interesting use of
+ the predicate operands, an assert location node is added to the
+ list of assertions for the corresponding operands. */
+
+static bool
+find_switch_asserts (basic_block bb, tree last)
+{
+ bool need_assert;
+ block_stmt_iterator bsi;
+ tree op, cond;
+ edge e;
+ tree vec = SWITCH_LABELS (last), vec2;
+ size_t n = TREE_VEC_LENGTH (vec);
+ unsigned int idx;
+
+ need_assert = false;
+ bsi = bsi_for_stmt (last);
+ op = TREE_OPERAND (last, 0);
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ /* Build a vector of case labels sorted by destination label. */
+ vec2 = make_tree_vec (n);
+ for (idx = 0; idx < n; ++idx)
+ TREE_VEC_ELT (vec2, idx) = TREE_VEC_ELT (vec, idx);
+ qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
+
+ for (idx = 0; idx < n; ++idx)
+ {
+ tree min, max;
+ tree cl = TREE_VEC_ELT (vec2, idx);
+
+ min = CASE_LOW (cl);
+ max = CASE_HIGH (cl);
+
+ /* If there are multiple case labels with the same destination
+ we need to combine them to a single value range for the edge. */
+ if (idx + 1 < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
+ {
+ /* Skip labels until the last of the group. */
+ do {
+ ++idx;
+ } while (idx < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
+ --idx;
+
+ /* Pick up the maximum of the case label range. */
+ if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
+ max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
+ else
+ max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
+ }
+
+ /* Nothing to do if the range includes the default label until we
+ can register anti-ranges. */
+ if (min == NULL_TREE)
+ continue;
+
+ /* Find the edge to register the assert expr on. */
+ e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
+
+ /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
+ Otherwise, when we finish traversing each of the sub-graphs, we
+ won't know whether the variables were found in the sub-graphs or
+ if they had been found in a block upstream from BB. */
+ RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+
+ /* Traverse the strictly dominated sub-graph rooted at E->DEST
+ to determine if any of the operands in the conditional
+ predicate are used. */
+ if (e->dest != bb)
+ need_assert |= find_assert_locations (e->dest);
+
+ /* Register the necessary assertions for the operand in the
+ SWITCH_EXPR. */
+ cond = build2 (max ? GE_EXPR : EQ_EXPR, boolean_type_node,
+ op, fold_convert (TREE_TYPE (op), min));
+ need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ if (max)
+ {
+ cond = build2 (LE_EXPR, boolean_type_node,
+ op, fold_convert (TREE_TYPE (op), max));
+ need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ }
+ }
+
+ /* Finally, indicate that we have found the operand in the
+ SWITCH_EXPR. */
+ SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+
+ return need_assert;
+}
+
/* Traverse all the statements in block BB looking for statements that
may generate useful assertions for the SSA names in their operand.
If this function returns true, then it means that there are names
for which we need to generate ASSERT_EXPRs. Those assertions are
- inserted by process_assert_insertions.
-
- TODO. Handle SWITCH_EXPR. */
+ inserted by process_assert_insertions. */
static bool
find_assert_locations (basic_block bb)
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
need_assert |= find_conditional_asserts (bb, last);
+ if (last
+ && TREE_CODE (last) == SWITCH_EXPR
+ && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+ need_assert |= find_switch_asserts (bb, last);
+
/* Recurse into the dominator children of BB. */
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow
infinity to produce the result. */
-tree
-vrp_evaluate_conditional (tree cond, bool use_equiv_p, bool *strict_overflow_p)
+static tree
+vrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p,
+ bool *strict_overflow_p)
{
gcc_assert (TREE_CODE (cond) == SSA_NAME
|| TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
return NULL_TREE;
}
+/* Given COND within STMT, try to simplify it based on value range
+ information. Return NULL if the conditional can not be evaluated.
+ The ranges of all the names equivalent with the operands in COND
+ will be used when trying to compute the value. If the result is
+ based on undefined signed overflow, issue a warning if
+ appropriate. */
+
+tree
+vrp_evaluate_conditional (tree cond, tree stmt)
+{
+ bool sop;
+ tree ret;
+
+ sop = false;
+ ret = vrp_evaluate_conditional_warnv (cond, true, &sop);
+
+ if (ret && sop)
+ {
+ enum warn_strict_overflow_code wc;
+ const char* warnmsg;
+
+ if (is_gimple_min_invariant (ret))
+ {
+ wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
+ warnmsg = G_("assuming signed overflow does not occur when "
+ "simplifying conditional to constant");
+ }
+ else
+ {
+ wc = WARN_STRICT_OVERFLOW_COMPARISON;
+ warnmsg = G_("assuming signed overflow does not occur when "
+ "simplifying conditional");
+ }
+
+ if (issue_strict_overflow_warning (wc))
+ {
+ location_t locus;
+
+ if (!EXPR_HAS_LOCATION (stmt))
+ locus = input_location;
+ else
+ locus = EXPR_LOCATION (stmt);
+ warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg);
+ }
+ }
+
+ return ret;
+}
+
/* Visit conditional statement STMT. If we can determine which edge
will be taken out of STMT's basic block, record it in
*taken_edge_p = NULL;
- /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
- add ASSERT_EXPRs for them. */
+ /* FIXME. Handle SWITCH_EXPRs. */
if (TREE_CODE (stmt) == SWITCH_EXPR)
return SSA_PROP_VARYING;
MICO, TRAMP3D and SPEC2000) showed that doing this results in
4 more predicates folded in SPEC. */
sop = false;
- val = vrp_evaluate_conditional (cond, false, &sop);
+ val = vrp_evaluate_conditional_warnv (cond, false, &sop);
if (val)
{
if (!sop)
bool sop = false;
val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop);
+
+ if (val
+ && sop
+ && integer_onep (val)
+ && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t locus;
+
+ if (!EXPR_HAS_LOCATION (stmt))
+ locus = input_location;
+ else
+ locus = EXPR_LOCATION (stmt);
+ warning (OPT_Wstrict_overflow,
+ ("%Hassuming signed overflow does not occur when "
+ "simplifying / or %% to >> or &"),
+ &locus);
+ }
}
if (val && integer_onep (val))
{
tree t;
+ if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t locus;
+
+ if (!EXPR_HAS_LOCATION (stmt))
+ locus = input_location;
+ else
+ locus = EXPR_LOCATION (stmt);
+ warning (OPT_Wstrict_overflow,
+ ("%Hassuming signed overflow does not occur when "
+ "simplifying abs (X) to X or -X"),
+ &locus);
+ }
+
if (integer_onep (val))
t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
else
restored. */
static VEC(tree,heap) *stack;
-/* A trivial wrapper so that we can present the generic jump
- threading code with a simple API for simplifying statements. */
+/* A trivial wrapper so that we can present the generic jump threading
+ code with a simple API for simplifying statements. STMT is the
+ statement we want to simplify, WITHIN_STMT provides the location
+ for any overflow warnings. */
+
static tree
-simplify_stmt_for_jump_threading (tree stmt)
+simplify_stmt_for_jump_threading (tree stmt, tree within_stmt)
{
- bool sop;
-
/* We only use VRP information to simplify conditionals. This is
overly conservative, but it's unclear if doing more would be
worth the compile time cost. */
if (TREE_CODE (stmt) != COND_EXPR)
return NULL;
- sop = false;
- return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true, &sop);
+ return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt);
}
/* Blocks which have more than one predecessor and more than
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_dump_func
- | TODO_update_ssa
- | TODO_update_smt_usage, /* todo_flags_finish */
+ | TODO_update_ssa, /* todo_flags_finish */
0 /* letter */
};
OSDN Git Service
