}
+/* 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;
- /* 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))
+ /* 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.
+
+ 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);
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)))
+ /* 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;
- /* Do not adjust ranges when using wrapping arithmetic. */
- if (flag_wrapv)
- 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))
{
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))
{
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])
OSDN Git Service
