}
+/* Return true if ARG is marked with the nonnull attribute in the
+ current function signature. */
+
+static bool
+nonnull_arg_p (tree arg)
+{
+ tree t, attrs, fntype;
+ unsigned HOST_WIDE_INT arg_num;
+
+ gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
+
+ fntype = TREE_TYPE (current_function_decl);
+ attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
+
+ /* If "nonnull" wasn't specified, we know nothing about the argument. */
+ if (attrs == NULL_TREE)
+ return false;
+
+ /* If "nonnull" applies to all the arguments, then ARG is non-null. */
+ if (TREE_VALUE (attrs) == NULL_TREE)
+ return true;
+
+ /* Get the position number for ARG in the function signature. */
+ for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
+ t;
+ t = TREE_CHAIN (t), arg_num++)
+ {
+ if (t == arg)
+ break;
+ }
+
+ gcc_assert (t == arg);
+
+ /* Now see if ARG_NUM is mentioned in the nonnull list. */
+ for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
+ {
+ if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
+ return true;
+ }
+
+ return false;
+}
+
+
/* Set value range VR to {T, MIN, MAX, EQUIV}. */
static void
in VAR's type. */
sym = SSA_NAME_VAR (var);
if (var == var_ann (sym)->default_def)
- set_value_range_to_varying (vr);
+ {
+ /* Try to use the "nonnull" attribute to create ~[0, 0]
+ anti-ranges for pointers. Note that this is only valid with
+ default definitions of PARM_DECLs. */
+ if (TREE_CODE (sym) == PARM_DECL
+ && POINTER_TYPE_P (TREE_TYPE (sym))
+ && nonnull_arg_p (sym))
+ set_value_range_to_nonnull (vr, TREE_TYPE (sym));
+ else
+ set_value_range_to_varying (vr);
+ }
return vr;
}
}
-/* Return true if VR includes the value zero, false otheriwse. */
+/* Return true if VR includes the value zero, false otherwise. */
static inline bool
range_includes_zero_p (value_range_t *vr)
}
+/* Wrapper around int_const_binop. If the operation overflows and we
+ are not using wrapping arithmetic, then adjust the result to be
+ -INF or +INF depending on CODE, VAL1 and VAL2. */
+
+static inline tree
+vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+{
+ tree res;
+
+ if (flag_wrapv)
+ return int_const_binop (code, val1, val2, 0);
+
+ /* If we are not using wrapping arithmetic, operate symbolically
+ on -INF and +INF. */
+ res = int_const_binop (code, val1, val2, 0);
+
+ /* If the operation overflowed but neither VAL1 nor VAL2 are
+ overflown, return -INF or +INF depending on the operation
+ and the combination of signs of the operands. */
+ if (TREE_OVERFLOW (res)
+ && !TREE_OVERFLOW (val1)
+ && !TREE_OVERFLOW (val2))
+ {
+ int sgn1 = tree_int_cst_sgn (val1);
+ int sgn2 = tree_int_cst_sgn (val2);
+
+ /* 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
+ can yield overflow without overflown operands because we
+ are working with integral types only... except in the
+ case VAL1 = -INF and VAL2 = -1 which overflows to +INF
+ for division too. */
+
+ /* For multiplication, the sign of the overflow is given
+ by the comparison of the signs of the operands. */
+ 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)
+ /* For subtraction, the operands must be of different
+ signs to yield an overflow. Its sign is therefore
+ that of the first operand or the opposite of that
+ of the second operand. */
+ || (code == MINUS_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)
+ return TYPE_MAX_VALUE (TREE_TYPE (res));
+ else
+ return TYPE_MIN_VALUE (TREE_TYPE (res));
+ }
+
+ return res;
+}
+
+
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
}
else if (code == PLUS_EXPR
- || code == MULT_EXPR
|| code == MIN_EXPR
|| code == MAX_EXPR)
{
/* For operations that make the resulting range directly
proportional to the original ranges, apply the operation to
the same end of each range. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.max, 0);
+ min = vrp_int_const_binop (code, vr0.min, vr1.min);
+ max = vrp_int_const_binop (code, vr0.max, vr1.max);
}
- else if (code == TRUNC_DIV_EXPR
+ else if (code == MULT_EXPR
+ || code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
|| code == ROUND_DIV_EXPR)
{
- tree zero;
+ tree val[4];
+ size_t i;
+
+ /* 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
+ maximum values for the new range. One approach is to figure
+ out all the variations of range combinations and do the
+ operations.
- /* Divisions are a bit tricky to handle, depending on the mix of
- signs we have in the two range, we will need to divide
- different values to get the minimum and maximum values for
- the new range. If VR1 includes zero, the result is VARYING. */
- if (range_includes_zero_p (&vr1))
+ However, this involves several calls to compare_values and it
+ is pretty convoluted. It's simpler to do the 4 operations
+ (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
+ MAX1) and then figure the smallest and largest values to form
+ the new range. */
+
+ /* Divisions by zero result in a VARYING value. */
+ if (code != MULT_EXPR && range_includes_zero_p (&vr1))
{
set_value_range_to_varying (vr);
return;
}
- /* We have three main variations to handle for VR0: all negative
- values, all positive values and a mix of negative and
- positive. For each of these, we need to consider if VR1 is
- all negative or all positive. In total, there are 6
- combinations to handle. */
- zero = build_int_cst (TREE_TYPE (expr), 0);
- if (compare_values (vr0.max, zero) == -1)
- {
- /* VR0 is all negative. */
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX]. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.max, 0);
- }
- else
- {
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.min, 0);
- max = int_const_binop (code, vr0.min, vr1.max, 0);
- }
- }
- else if (range_includes_zero_p (&vr0))
- {
- /* VR0 is a mix of negative and positive values. */
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN]. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
- }
- else
- {
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.max, 0);
- max = int_const_binop (code, vr0.min, vr1.max, 0);
- }
- }
- else
+ /* Compute the 4 cross operations. */
+ val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
+
+ val[1] = (vr1.max != vr1.min)
+ ? vrp_int_const_binop (code, vr0.min, vr1.max)
+ : NULL_TREE;
+
+ val[2] = (vr0.max != vr0.min)
+ ? vrp_int_const_binop (code, vr0.max, vr1.min)
+ : NULL_TREE;
+
+ val[3] = (vr0.min != vr1.min && vr0.max != vr1.max)
+ ? vrp_int_const_binop (code, vr0.max, vr1.max)
+ : NULL_TREE;
+
+ /* Set MIN to the minimum of VAL[i] and MAX to the maximum
+ of VAL[i]. */
+ min = val[0];
+ max = val[0];
+ for (i = 1; i < 4; i++)
{
- /* VR0 is all positive. */
- gcc_assert (compare_values (vr0.min, zero) == 1);
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN]. */
- min = int_const_binop (code, vr0.min, vr1.max, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
- }
- else
+ if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
+ break;
+
+ if (val[i])
{
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.max, 0);
- max = int_const_binop (code, vr0.min, vr1.min, 0);
+ if (TREE_OVERFLOW (val[i]))
+ {
+ /* If we found an overflowed value, set MIN and MAX
+ to it so that we set the resulting range to
+ VARYING. */
+ min = max = val[i];
+ break;
+ }
+
+ if (compare_values (val[i], min) == -1)
+ min = val[i];
+
+ if (compare_values (val[i], max) == 1)
+ max = val[i];
}
}
}
{
/* For MINUS_EXPR, apply the operation to the opposite ends of
each range. */
- min = int_const_binop (code, vr0.min, vr1.max, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
+ min = vrp_int_const_binop (code, vr0.min, vr1.max);
+ max = vrp_int_const_binop (code, vr0.max, vr1.min);
}
else
gcc_unreachable ();
- /* If MAX overflowed, then the result depends on whether we are
- using wrapping arithmetic or not. */
- if (TREE_OVERFLOW (max))
- {
- /* If we are using wrapping arithmetic, set the result to
- VARYING. */
- if (flag_wrapv)
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* Otherwise, set MAX to +INF. */
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
- }
-
- /* If MIN overflowed, then the result depends on whether we are
- using wrapping arithmetic or not. */
- if (TREE_OVERFLOW (min))
+ /* If either MIN or MAX overflowed, then set the resulting range to
+ VARYING. */
+ if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
{
- /* If we are using wrapping arithmetic, set the result to
- VARYING. */
- if (flag_wrapv)
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* Otherwise, set MIN to -INF. */
- min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ set_value_range_to_varying (vr);
+ return;
}
cmp = compare_values (min, max);
}
/* Handle unary expressions on integer ranges. */
- if ((code == NOP_EXPR || code == CONVERT_EXPR)
- && (TYPE_SIZE (TREE_TYPE (vr0.min)) != TYPE_SIZE (TREE_TYPE (expr))))
+ if (code == NOP_EXPR || code == CONVERT_EXPR)
{
+ tree inner_type = TREE_TYPE (op0);
+ tree outer_type = TREE_TYPE (expr);
+
/* When converting types of different sizes, set the result to
VARYING. Things like sign extensions and precision loss may
change the range. For instance, if x_3 is of type 'long long
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_to_varying (vr);
- return;
+ if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
+ || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
}
/* Apply the operation to each end of the range and see what we end
set_value_range_to_varying (vr);
}
-
-/* Given a range VR, a loop L and a variable VAR, determine whether it
+/* Given a range VR, a LOOP and a variable VAR, determine whether it
would be profitable to adjust VR using scalar evolution information
for VAR. If so, update VR with the new limits. */
static void
-adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var)
+adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
+ tree var)
{
tree init, step, chrec;
bool init_is_max;
if (vr->type == VR_ANTI_RANGE)
return;
- chrec = analyze_scalar_evolution (l, var);
+ chrec = analyze_scalar_evolution (loop, var);
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return;
if (!is_gimple_min_invariant (step))
return;
- /* FIXME. When dealing with unsigned types,
- analyze_scalar_evolution sets STEP to very large unsigned values
- when the evolution goes backwards. This confuses this analysis
- because we think that INIT is the smallest value that the range
- can take, instead of the largest. Ignore these chrecs for now. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step)))
- return;
-
- /* Do not adjust ranges when using wrapping arithmetic. */
- if (flag_wrapv)
+ /* Do not adjust ranges when chrec may wrap. */
+ if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
+ cfg_loops->parray[CHREC_VARIABLE (chrec)],
+ &init_is_max))
return;
- /* If STEP is negative, then INIT is the maximum value the range
- will take. Otherwise, INIT is the minimum value. */
- init_is_max = (tree_int_cst_sgn (step) < 0);
-
if (!POINTER_TYPE_P (TREE_TYPE (init))
&& (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
{
}
-#if 0
-/* Return true if OP is the result of an ASSERT_EXPR that tests the
- same condition as COND. */
-
-static bool
-has_assert_expr (tree op, tree cond)
-{
- tree def_stmt = SSA_NAME_DEF_STMT (op);
- tree assert_expr, other_cond, other_op;
-
- /* If OP was not generated by an ASSERT_EXPR, return false. */
- if (TREE_CODE (def_stmt) != MODIFY_EXPR
- || TREE_CODE (TREE_OPERAND (def_stmt, 1)) != ASSERT_EXPR)
- return false;
-
- assert_expr = TREE_OPERAND (def_stmt, 1);
- other_cond = ASSERT_EXPR_COND (assert_expr);
- other_op = ASSERT_EXPR_VAR (assert_expr);
-
- if (TREE_CODE (cond) == TREE_CODE (other_cond))
- {
- tree t1, t2;
-
- /* If COND is not a comparison predicate, something is wrong. */
- gcc_assert (COMPARISON_CLASS_P (cond));
-
- /* Note that we only need to compare against one of the operands
- of OTHER_COND.
-
- Suppose that we are about to insert the assertion ASSERT_EXPR
- <x_4, x_4 != 0> and the defining statement for x_4 is x_4 =
- ASSERT_EXPR <x_3, x_3 != 0>.
-
- In this case, we don't really want to insert a new
- ASSERT_EXPR for x_4 because that would be redundant. We
- already know that x_4 is not 0. So, when comparing the
- conditionals 'x_3 != 0' and 'x_4 != 0', we don't want to
- compare x_3 and x_4, we just want to compare the predicate's
- code (!=) and the other operand (0). */
- if (TREE_OPERAND (cond, 0) == op)
- t1 = TREE_OPERAND (cond, 1);
- else
- t1 = TREE_OPERAND (cond, 0);
-
- if (TREE_OPERAND (other_cond, 0) == other_op)
- t2 = TREE_OPERAND (other_cond, 1);
- else
- t2 = TREE_OPERAND (other_cond, 0);
-
- return (t1 == t2 || operand_equal_p (t1, t2, 0));
- }
-
- return false;
-}
-
-
-/* Traverse all the statements in block BB looking for used variables.
- Variables used in BB are added to bitmap FOUND. The algorithm
- works in three main parts:
-
- 1- For every statement S in BB, all the variables used by S are
- added to bitmap FOUND.
-
- 2- If statement S uses an operand N in a way that exposes a known
- value range for N, then if N was not already generated by an
- ASSERT_EXPR, create a new ASSERT_EXPR for N. For instance, if N
- is a pointer and the statement dereferences it, we can assume
- that N is not NULL.
-
- 3- COND_EXPRs are a special case of #2. We can derive range
- information from the predicate but need to insert different
- ASSERT_EXPRs for each of the sub-graphs rooted at the
- conditional block. If the last statement of BB is a conditional
- expression of the form 'X op Y', then
-
- a) Remove X and Y from the set FOUND.
-
- b) If the conditional dominates its THEN_CLAUSE sub-graph,
- recurse into it. On return, if X and/or Y are marked in
- FOUND, then an ASSERT_EXPR is added for the corresponding
- variable.
-
- c) Repeat step (b) on the ELSE_CLAUSE.
-
- d) Mark X and Y in FOUND.
-
- 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
- added to the edges of COND_EXPR blocks that have sub-graphs using
- one or both predicate operands. For instance,
-
- if (a == 9)
- b = a;
- else
- b = c + 1;
-
- In this case, an assertion on the THEN clause is useful to
- determine that 'a' is always 9 on that edge. However, an assertion
- on the ELSE clause would be unnecessary.
-
- On exit from this function, all the names created by the newly
- inserted ASSERT_EXPRs need to be added to the SSA web by rewriting
- the SSA names that they replace.
-
- TODO. Handle SWITCH_EXPR. */
-
-static bool
-maybe_add_assert_expr (basic_block bb)
-{
- block_stmt_iterator si;
- tree last;
- bool added;
-
- /* Step 1. Mark all the SSA names used in BB in bitmap FOUND. */
- added = false;
- last = NULL_TREE;
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- tree stmt, op;
- ssa_op_iter i;
-
- stmt = bsi_stmt (si);
-
- /* Mark all the SSA names used by STMT in bitmap FOUND. If STMT
- is inside the sub-graph of a conditional block, when we
- return from this recursive walk, our parent will use the
- FOUND bitset to determine if one of the operands it was
- looking for was present in the sub-graph. */
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
- {
- 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 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 (has_assert_expr (op, cond))
- continue;
-
- if (!stmt_ends_bb_p (stmt))
- {
- /* If STMT does not end the block, we can insert the new
- assertion right after it. */
- tree t = build_assert_expr_for (cond, op);
- bsi_insert_after (&si, t, BSI_NEW_STMT);
- added = true;
- }
- else
- {
- /* STMT must be the last statement in BB. We can only
- insert new assertions on the non-abnormal edge out of
- BB. Note that since STMT is not control flow, there
- may only be one non-abnormal edge out of BB. */
- edge_iterator ei;
- edge e;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & EDGE_ABNORMAL))
- {
- tree t = build_assert_expr_for (cond, op);
- bsi_insert_on_edge (e, t);
- added = true;
- break;
- }
- }
- }
-
- /* Remember the last statement of the block. */
- last = stmt;
- }
-
- /* Step 3. If BB's last statement is a conditional expression
- involving integer operands, recurse into each of the sub-graphs
- rooted at BB to determine if we need to add ASSERT_EXPRs.
- Notice that we only care about the first operand of the
- conditional. Adding assertions for both operands may actually
- hinder VRP. FIXME, add example. */
- if (last
- && TREE_CODE (last) == COND_EXPR
- && !fp_predicate (COND_EXPR_COND (last))
- && !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. */
- RESET_BIT (found, SSA_NAME_VERSION (op));
-
- /* Look for uses of the operands in each of the sub-graphs
- rooted at BB. We need to check each of the outgoing edges
- separately, so that we know what kind of ASSERT_EXPR to
- insert. */
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- /* If BB strictly dominates the sub-graph at E->DEST,
- recurse into it. */
- if (e->dest != bb
- && dominated_by_p (CDI_DOMINATORS, e->dest, bb))
- added |= maybe_add_assert_expr (e->dest);
-
- /* Once we traversed the sub-graph, check if any block inside
- used either of the predicate's operands. If so, add the
- appropriate ASSERT_EXPR. */
- if (TEST_BIT (found, SSA_NAME_VERSION (op)))
- {
- /* We found a use of OP in the sub-graph rooted at
- E->DEST. Add an ASSERT_EXPR according to whether
- E goes to THEN_CLAUSE or ELSE_CLAUSE. */
- tree c, t;
-
- if (e->flags & EDGE_TRUE_VALUE)
- c = unshare_expr (cond);
- else if (e->flags & EDGE_FALSE_VALUE)
- c = invert_truthvalue (cond);
- else
- gcc_unreachable ();
-
- t = build_assert_expr_for (c, op);
- bsi_insert_on_edge (e, t);
- added = true;
- }
- }
-
- /* 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 4. Recurse into the dominator children of BB. */
- basic_block son;
-
- for (son = first_dom_son (CDI_DOMINATORS, bb);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
- added |= maybe_add_assert_expr (son);
- }
-
- return added;
-}
-#endif
-
-
void dump_asserts_for (FILE *, tree);
void debug_asserts_for (tree);
void dump_all_asserts (FILE *);
else about the range of LHS by examining scalar evolution
information. */
if (cfg_loops && (l = loop_containing_stmt (stmt)))
- adjust_range_with_scev (&new_vr, l, lhs);
+ adjust_range_with_scev (&new_vr, l, stmt, lhs);
if (update_value_range (lhs, &new_vr))
{
/* Given a comparison code COMP and names N1 and N2, compare all the
- ranges equivalent to N1 against all the ranges equivalente to N2
+ ranges equivalent to N1 against all the ranges equivalent to N2
to determine the value of N1 COMP N2. Return the same value
returned by compare_ranges. */
return;
}
- /* The resulting set of equivalencies is the intersection of
+ /* The resulting set of equivalences is the intersection of
the two sets. */
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
bitmap_and_into (vr0->equiv, vr1->equiv);
&& compare_values (vr0->max, vr1->max) == 0
&& compare_values (vr0->min, vr0->max) == 0)
{
- /* The resulting set of equivalencies is the intersection of
+ /* The resulting set of equivalences is the intersection of
the two sets. */
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
bitmap_and_into (vr0->equiv, vr1->equiv);
return SSA_PROP_VARYING;
}
+/* Walk through the IL simplifying expressions using knowledge
+ gathered by VRP. */
+
+static void
+simplify_using_ranges (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+ enum tree_code rhs_code = TREE_CODE (rhs);
+
+ /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
+ and BIT_AND_EXPR respectively if the first operand is greater
+ than zero and the second operand is an exact power of two. */
+ if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
+ && integer_pow2p (TREE_OPERAND (rhs, 1)))
+ {
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+
+ if (TYPE_UNSIGNED (TREE_TYPE (op)))
+ {
+ val = integer_one_node;
+ }
+ else
+ {
+ val = compare_range_with_value (GT_EXPR, vr,
+ integer_zero_node);
+ }
+
+ if (val && integer_onep (val))
+ {
+ tree t;
+ tree op0 = TREE_OPERAND (rhs, 0);
+ tree op1 = TREE_OPERAND (rhs, 1);
+
+ if (rhs_code == TRUNC_DIV_EXPR)
+ {
+ t = build_int_cst (NULL_TREE, tree_log2 (op1));
+ t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
+ }
+ else
+ {
+ t = build_int_cst (TREE_TYPE (op1), 1);
+ t = int_const_binop (MINUS_EXPR, op1, t, 0);
+ t = fold_convert (TREE_TYPE (op0), t);
+ t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
+ }
+
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+
+ }
+
+ /* Transform ABS (X) into X or -X as appropriate. */
+ if (rhs_code == ABS_EXPR
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+ {
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ tree type = TREE_TYPE (op);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+
+ if (TYPE_UNSIGNED (type))
+ {
+ val = integer_zero_node;
+ }
+ else if (vr)
+ {
+ val = compare_range_with_value (LE_EXPR, vr,
+ integer_zero_node);
+ if (!val)
+ {
+ val = compare_range_with_value (GE_EXPR, vr,
+ integer_zero_node);
+
+ if (val)
+ {
+ if (integer_zerop (val))
+ val = integer_one_node;
+ else if (integer_onep (val))
+ val = integer_zero_node;
+ }
+ }
+
+ if (val
+ && (integer_onep (val) || integer_zerop (val)))
+ {
+ tree t;
+
+ if (integer_onep (val))
+ t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
+ else
+ t = op;
+
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+ }
+ }
+ }
+
+ /* TODO. Simplify conditionals. */
+ }
+ }
+}
+
/* Traverse all the blocks folding conditionals with known ranges. */
substitute_and_fold (single_val_range, true);
+ /* One could argue all simplifications should be done here
+ rather than using substitute_and_fold since this code
+ is going to have to perform a complete walk through the
+ IL anyway. */
+ simplify_using_ranges ();
+
/* Free allocated memory. */
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i])
code we can also determine that p_5 cannot be NULL and, if q_2 had
a non-varying range, p_5's range should also be compatible with it.
- These equivalencies are created by two expressions: ASSERT_EXPR and
+ These equivalences are created by two expressions: ASSERT_EXPR and
copy operations. Since p_5 is an assertion on p_4, and p_4 was the
result of another assertion, then we can use the fact that p_5 and
p_4 are equivalent when evaluating p_5's range.
- Together with value ranges, we also propagate these equivalencies
+ Together with value ranges, we also propagate these equivalences
between names so that we can take advantage of information from
multiple ranges when doing final replacement. Note that this
equivalency relation is transitive but not symmetric.
OSDN Git Service
