#include "tree-chrec.h"
/* Set of SSA names found during the dominator traversal of a
- sub-graph in maybe_add_assert_expr_on_edges. */
+ sub-graph in maybe_add_assert_expr. */
static sbitmap found;
/* Loop structure of the program. Used to analyze scalar evolutions
/* Set value range VR to a non-NULL range of type TYPE. */
-static void
+static inline void
set_value_range_to_nonnull (value_range *vr, tree type)
{
tree zero = build_int_cst (type, 0);
/* Set value range VR to a NULL range of type TYPE. */
-static void
+static inline void
set_value_range_to_null (value_range *vr, tree type)
{
tree zero = build_int_cst (type, 0);
}
+/* Set value range VR to VR_VARYING. */
+
+static inline void
+set_value_range_to_varying (value_range *vr)
+{
+ set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+}
+
+
/* Compare two values VAL1 and VAL2. Return
-2 if VAL1 and VAL2 cannot be compared at compile-time,
if (val1 == val2)
return 0;
+ /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
+ both integers. */
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
+ == POINTER_TYPE_P (TREE_TYPE (val2)));
+
/* Do some limited symbolic comparisons. */
if (!POINTER_TYPE_P (TREE_TYPE (val1)))
{
return 0;
/* If VAL1 is a lower address than VAL2, return -1. */
- t = fold (build2 (LT_EXPR, TREE_TYPE (val1), val1, val2));
+ t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return -1;
/* If VAL1 is a higher address than VAL2, return +1. */
- t = fold (build2 (GT_EXPR, TREE_TYPE (val1), val1, val2));
+ t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return 1;
/* If VAL1 is different than VAL2, return +2. */
- t = fold (build2 (NE_EXPR, TREE_TYPE (val1), val1, val2));
+ t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return 2;
{
tree var, cond, limit, type;
value_range *var_vr;
+ enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
cond = ASSERT_EXPR_COND (expr);
+ cond_code = TREE_CODE (cond);
- gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
+ gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
limit = get_opposite_operand (cond, var);
(NE_EXPR). Notice that we don't need to handle EQ_EXPR in these
cases because assertions with equalities are never generated.
The assert pass generates straight assignments in those cases. */
- if (POINTER_TYPE_P (type) && TREE_CODE (cond) != NE_EXPR)
+ if (POINTER_TYPE_P (type) && cond_code != NE_EXPR)
{
- set_value_range (vr_p, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr_p);
return;
}
+ /* Special handling for integral types with super-types. Some FEs
+ construct integral types derived from other types and restrict
+ the range of values these new types may take.
+
+ It may happen that LIMIT is actually smaller than TYPE's minimum
+ value. For instance, the Ada FE is generating code like this
+ during bootstrap:
+
+ D.1480_32 = nam_30 - 300000361;
+ if (D.1480_32 <= 1) goto <L112>; else goto <L52>;
+ <L112>:;
+ D.1480_94 = ASSERT_EXPR <D.1480_32, D.1480_32 <= 1>;
+
+ All the names are of type types__name_id___XDLU_300000000__399999999
+ which has min == 300000000 and max == 399999999. This means that
+ the ASSERT_EXPR would try to create the range [3000000, 1] which
+ is invalid.
+
+ The fact that the type specifies MIN and MAX values does not
+ automatically mean that every variable of that type will always
+ be within that range, so the predicate may well be true at run
+ time. If we had symbolic -INF and +INF values, we could
+ represent this range, but we currently represent -INF and +INF
+ using the type's min and max values.
+
+ So, the only sensible thing we can do for now is set the
+ resulting range to VR_VARYING. TODO, would having symbolic -INF
+ and +INF values be worth the trouble? */
+ if (TREE_TYPE (type))
+ {
+ if (cond_code == LE_EXPR || cond_code == LT_EXPR)
+ {
+ tree type_min = TYPE_MIN_VALUE (type);
+ int cmp = compare_values (limit, type_min);
+
+ /* For < or <= comparisons, if LIMIT is smaller than
+ TYPE_MIN, set the range to VR_VARYING. */
+ if (cmp == -1 || cmp == 0)
+ {
+ set_value_range_to_varying (vr_p);
+ return;
+ }
+ }
+ else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
+ {
+ tree type_max = TYPE_MIN_VALUE (type);
+ int cmp = compare_values (limit, type_max);
+
+ /* For > or >= comparisons, if LIMIT is bigger than
+ TYPE_MAX, set the range to VR_VARYING. */
+ if (cmp == 1 || cmp == 0)
+ {
+ set_value_range_to_varying (vr_p);
+ return;
+ }
+ }
+ }
+
if (TREE_CODE (cond) == NE_EXPR)
set_value_range (vr_p, VR_ANTI_RANGE, limit, limit);
else if (TREE_CODE (cond) == LE_EXPR)
&& code != MIN_EXPR
&& code != MAX_EXPR)
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
if (is_gimple_min_invariant (op0))
set_value_range (&vr0, VR_RANGE, op0, op0);
else
- set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (&vr0);
}
op1 = TREE_OPERAND (expr, 1);
if (is_gimple_min_invariant (op1))
set_value_range (&vr1, VR_RANGE, op1, op1);
else
- set_value_range (&vr1, VR_VARYING, 0, 0);
+ set_value_range_to_varying (&vr1);
}
/* If either range is UNDEFINED, so is the result. */
/* If either range is VARYING, so is the result. */
if (vr0.type == VR_VARYING || vr1.type == VR_VARYING)
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
/* If the ranges are of different types, the result is VARYING. */
if (vr0.type != vr1.type)
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
/* TODO. Refuse to do any symbolic range operations for now. */
if (symbolic_range_p (&vr0) || symbolic_range_p (&vr1))
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
{
/* Subtracting from a pointer, may yield 0, so just drop the
resulting range to varying. */
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
}
return;
/* If the new range has its limits swapped around (MIN > MAX),
then the operation caused one of them to wrap around, mark
the new range VARYING. */
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
}
else
set_value_range (vr, vr0.type, min, max);
}
+/* Like expr_computes_nonzero, but this function uses value ranges
+ obtained so far. */
+
+static bool
+vrp_expr_computes_nonzero (tree expr)
+{
+ if (expr_computes_nonzero (expr))
+ return true;
+
+ /* If we have an expression of the form &X->a, then the expression
+ is nonnull if X is nonnull. */
+ if (TREE_CODE (expr) == ADDR_EXPR)
+ {
+ tree base = get_base_address (TREE_OPERAND (expr, 0));
+
+ if (base != NULL_TREE
+ && TREE_CODE (base) == INDIRECT_REF
+ && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
+ {
+ value_range *vr = get_value_range (TREE_OPERAND (base, 0));
+ if (range_is_nonnull (vr))
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
/* Extract range information from a unary expression EXPR based on
the range of its operand and the expression code. */
if (is_gimple_min_invariant (op0))
set_value_range (&vr0, VR_RANGE, op0, op0);
else
- set_value_range (&vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (&vr0);
}
/* If VR0 is UNDEFINED, so is the result. */
/* If VR0 is VARYING, so is the result. */
if (vr0.type == VR_VARYING)
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
/* TODO. Refuse to do any symbolic range operations for now. */
if (symbolic_range_p (&vr0))
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& !POINTER_TYPE_P (TREE_TYPE (op0)))
{
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
else if (range_is_null (&vr0))
set_value_range_to_null (vr, TREE_TYPE (expr));
else
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
is impossible to know at compile time whether y_5 will be
~[0, 0]. */
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
return;
}
/* If the new range has its limits swapped around (MIN > MAX),
then the operation caused one of them to wrap around, mark
the new range VARYING. */
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
}
else
set_value_range (vr, vr0.type, min, max);
extract_range_from_binary_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_unary)
extract_range_from_unary_expr (vr, expr);
- else if (expr_computes_nonzero (expr))
+ else if (vrp_expr_computes_nonzero (expr))
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ else if (TREE_CODE (expr) == INTEGER_CST)
+ set_value_range (vr, VR_RANGE, expr, expr);
else
- set_value_range (vr, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr);
}
}
else if (vr->type == VR_RANGE)
{
+ tree min = vr->min;
+ tree max = vr->max;
+
if (init_is_max)
{
- /* INIT is the maximum value. If INIT is lower than
- VR->MAX, set VR->MAX to INIT. */
- if (compare_values (init, vr->max) == -1)
- set_value_range (vr, VR_RANGE, vr->min, init);
+ /* INIT is the maximum value. If INIT is lower than VR->MAX
+ but no smaller than VR->MIN, set VR->MAX to INIT. */
+ if (compare_values (init, max) == -1)
+ {
+ max = init;
+
+ /* If we just created an invalid range with the minimum
+ greater than the maximum, take the minimum all the
+ way to -INF. */
+ if (compare_values (min, max) == 1)
+ min = TYPE_MIN_VALUE (TREE_TYPE (min));
+ }
}
else
{
/* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
- if (compare_values (init, vr->min) == 1)
- set_value_range (vr, VR_RANGE, init, vr->max);
+ if (compare_values (init, min) == 1)
+ {
+ min = init;
+
+ /* If we just created an invalid range with the minimum
+ greater than the maximum, take the maximum all the
+ way to +INF. */
+ if (compare_values (min, max) == 1)
+ max = TYPE_MAX_VALUE (TREE_TYPE (max));
+ }
}
+
+ set_value_range (vr, VR_RANGE, min, max);
}
}
gcc_assert (TREE_CODE (v) == SSA_NAME);
n = duplicate_ssa_name (v, NULL_TREE);
- if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
+ if (COMPARISON_CLASS_P (cond))
{
/* Build N = ASSERT_EXPR <V, COND>. As a special case, if the
conditional is an EQ_EXPR (V == Z), just build the assignment
static inline bool
fp_predicate (tree expr)
{
- return TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison
- && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
+ return (COMPARISON_CLASS_P (expr)
+ && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
}
static tree
infer_value_range (tree stmt, tree op)
{
+ /* Do not attempt to infer anything in names that flow through
+ abnormal edges. */
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
+ return NULL_TREE;
+
if (POINTER_TYPE_P (TREE_TYPE (op)))
{
bool is_store;
tree t1, t2;
/* If COND is not a comparison predicate, something is wrong. */
- gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
+ gcc_assert (COMPARISON_CLASS_P (cond));
/* Note that we only need to compare against one of the operands
of OTHER_COND.
d) Mark X and Y in FOUND.
- 3- If BB does not end in a conditional expression, then we recurse
+ 4- If BB does not end in a conditional expression, then we recurse
into BB's dominator children.
At the end of the recursive traversal, ASSERT_EXPRs will have been
block_stmt_iterator si;
tree last;
bool added;
- use_optype uses;
/* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
added = false;
ssa_op_iter i;
stmt = bsi_stmt (si);
- get_stmt_operands (stmt);
/* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
is inside the sub-graph of a conditional block, when we
{
tree cond;
+ /* If OP is used only once, namely in this STMT, don't
+ bother inserting an ASSERT_EXPR for it. Such an
+ ASSERT_EXPR would do nothing but increase compile time.
+ Experiments show that with this simple check, we can save
+ more than 20% of ASSERT_EXPRs. */
+ if (has_single_use (op))
+ continue;
+
SET_BIT (found, SSA_NAME_VERSION (op));
cond = infer_value_range (stmt, op);
if (!cond)
continue;
- /* Step 3. If OP is used in such a way that we can infer a
+ /* Step 2. If OP is used in such a way that we can infer a
value range for it, create a new ASSERT_EXPR for OP
(unless OP already has an ASSERT_EXPR). */
gcc_assert (!is_ctrl_stmt (stmt));
if (last
&& TREE_CODE (last) == COND_EXPR
&& !fp_predicate (COND_EXPR_COND (last))
- && NUM_USES (uses = STMT_USE_OPS (last)) > 0)
+ && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
{
edge e;
edge_iterator ei;
tree op, cond;
+ basic_block son;
+ ssa_op_iter iter;
cond = COND_EXPR_COND (last);
+ /* Get just the first use operand. */
+ FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
+ break;
+ gcc_assert (op != NULL);
+
+ /* Do not attempt to infer anything in names that flow through
+ abnormal edges. */
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
+ return false;
+
/* Remove the COND_EXPR operand from the FOUND 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. */
- op = USE_OP (uses, 0);
RESET_BIT (found, SSA_NAME_VERSION (op));
/* Look for uses of the operands in each of the sub-graphs
/* Finally, mark all the COND_EXPR operands as found. */
SET_BIT (found, SSA_NAME_VERSION (op));
+
+ /* Recurse into the dominator children of BB that are not BB's
+ immediate successors. Note that we have already visited BB's
+ other dominator children above. */
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ {
+ if (find_edge (bb, son) == NULL)
+ added |= maybe_add_assert_expr (son);
+ }
}
else
{
- /* Step 3. Recurse into the dominator children of BB. */
+ /* Step 4. Recurse into the dominator children of BB. */
basic_block son;
for (son = first_dom_son (CDI_DOMINATORS, bb);
else if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
- stmt_ann_t ann = stmt_ann (stmt);
if (TREE_CODE (lhs) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| POINTER_TYPE_P (TREE_TYPE (lhs)))
- && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
- && NUM_VUSES (VUSE_OPS (ann)) == 0
- && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
+ && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return true;
}
else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
if (!stmt_interesting_for_vrp (phi))
{
tree lhs = PHI_RESULT (phi);
- set_value_range (get_value_range (lhs), VR_VARYING, 0, 0);
+ set_value_range_to_varying (get_value_range (lhs));
DONT_SIMULATE_AGAIN (phi) = true;
}
else
ssa_op_iter i;
tree def;
FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
- set_value_range (get_value_range (def), VR_VARYING, 0, 0);
+ set_value_range_to_varying (get_value_range (def));
DONT_SIMULATE_AGAIN (stmt) = true;
}
else
/* Every other statements produces no useful ranges. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- set_value_range (get_value_range (def), VR_VARYING, 0, 0);
+ set_value_range_to_varying (get_value_range (def));
return SSA_PROP_VARYING;
}
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR
- && NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
- && NUM_VUSES (VUSE_OPS (ann)) == 0
- && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
+ && ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return vrp_visit_assignment (stmt, output_p);
else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
return vrp_visit_cond_stmt (stmt, taken_edge_p);
/* All other statements produce nothing of interest for VRP, so mark
their outputs varying and prevent further simulation. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- set_value_range (get_value_range (def), VR_VARYING, 0, 0);
+ set_value_range_to_varying (get_value_range (def));
return SSA_PROP_VARYING;
}
/* If either is a symbolic range, drop to VARYING. */
if (symbolic_range_p (vr0) || symbolic_range_p (vr1))
{
- set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr0);
return;
}
else
{
/* The two ranges don't intersect, set the result to VR_VARYING. */
- set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr0);
}
}
else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
&& compare_values (vr0->min, vr0->max) == 0)
/* Nothing to do. */ ;
else
- set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr0);
}
else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
*vr0 = *vr1;
}
else
- set_value_range (vr0, VR_VARYING, NULL_TREE, NULL_TREE);
+ set_value_range_to_varying (vr0);
}
else
gcc_unreachable ();
if (vr_result.type == VR_VARYING)
{
- set_value_range (lhs_vr, VR_VARYING, 0, 0);
+ set_value_range_to_varying (lhs_vr);
return SSA_PROP_VARYING;
}
if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
&& vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
{
- set_value_range (lhs_vr, VR_VARYING, 0, 0);
+ set_value_range_to_varying (lhs_vr);
return SSA_PROP_VARYING;
}
}
OSDN Git Service
