GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
TYPE_{MIN,MAX}_VALUE. */
static inline bool
-needs_overflow_infinity (tree type)
+needs_overflow_infinity (const_tree type)
{
return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
}
VARYING. */
static inline bool
-supports_overflow_infinity (tree type)
+supports_overflow_infinity (const_tree type)
{
#ifdef ENABLE_CHECKING
gcc_assert (needs_overflow_infinity (type));
/* Return whether VAL is a negative overflow infinity. */
static inline bool
-is_negative_overflow_infinity (tree val)
+is_negative_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
/* Return whether VAL is a positive overflow infinity. */
static inline bool
-is_positive_overflow_infinity (tree val)
+is_positive_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
/* Return whether VAL is a positive or negative overflow infinity. */
static inline bool
-is_overflow_infinity (tree val)
+is_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
|| operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)));
}
+/* If VAL is now an overflow infinity, return VAL. Otherwise, return
+ the same value with TREE_OVERFLOW clear. This can be used to avoid
+ confusing a regular value with an overflow value. */
+
+static inline tree
+avoid_overflow_infinity (tree val)
+{
+ if (!is_overflow_infinity (val))
+ return val;
+
+ if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0))
+ return TYPE_MAX_VALUE (TREE_TYPE (val));
+ else
+ {
+#ifdef ENABLE_CHECKING
+ gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0));
+#endif
+ return TYPE_MIN_VALUE (TREE_TYPE (val));
+ }
+}
+
+
+/* Return whether VAL is equal to the maximum value of its type. This
+ will be true for a positive overflow infinity. We can't do a
+ simple equality comparison with TYPE_MAX_VALUE because C typedefs
+ and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
+ to the integer constant with the same value in the type. */
+
+static inline bool
+vrp_val_is_max (const_tree val)
+{
+ tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val));
+
+ return (val == type_max
+ || (type_max != NULL_TREE
+ && operand_equal_p (val, type_max, 0)));
+}
+
+/* Return whether VAL is equal to the minimum value of its type. This
+ will be true for a negative overflow infinity. */
+
+static inline bool
+vrp_val_is_min (const_tree val)
+{
+ tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val));
+
+ return (val == type_min
+ || (type_min != NULL_TREE
+ && operand_equal_p (val, type_min, 0)));
+}
+
/* Return true if ARG is marked with the nonnull attribute in the
current function signature. */
static bool
-nonnull_arg_p (tree arg)
+nonnull_arg_p (const_tree arg)
{
tree t, attrs, fntype;
unsigned HOST_WIDE_INT arg_num;
gcc_assert (min && max);
if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
- gcc_assert ((min != TYPE_MIN_VALUE (TREE_TYPE (min))
- && !is_negative_overflow_infinity (min))
- || (max != TYPE_MAX_VALUE (TREE_TYPE (max))
- && !is_positive_overflow_infinity (max)));
+ gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
cmp = compare_values (min, max);
gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+
+ if (needs_overflow_infinity (TREE_TYPE (min)))
+ gcc_assert (!is_overflow_infinity (min)
+ || !is_overflow_infinity (max));
}
if (t == VR_UNDEFINED || t == VR_VARYING)
/* Since updating the equivalence set involves deep copying the
bitmaps, only do it if absolutely necessary. */
- if (vr->equiv == NULL)
+ if (vr->equiv == NULL
+ && equiv != NULL)
vr->equiv = BITMAP_ALLOC (NULL);
if (equiv != vr->equiv)
bitmap_clear (vr->equiv);
}
+/* Set value range VR to a single value. This function is only called
+ with values we get from statements, and exists to clear the
+ TREE_OVERFLOW flag so that we don't think we have an overflow
+ infinity when we shouldn't. */
+
+static inline void
+set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
+{
+ gcc_assert (is_gimple_min_invariant (val));
+ val = avoid_overflow_infinity (val);
+ set_value_range (vr, VR_RANGE, val, val, equiv);
+}
+
/* Set value range VR to a non-negative range of type TYPE.
- OVERFLOW_INFINITY indicates whether to use a overflow infinity
+ OVERFLOW_INFINITY indicates whether to use an overflow infinity
rather than TYPE_MAX_VALUE; this should be true if we determine
that the range is nonnegative based on the assumption that signed
overflow does not occur. */
static inline void
set_value_range_to_null (value_range_t *vr, tree type)
{
- tree zero = build_int_cst (type, 0);
- set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
+ set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
}
return NULL. Otherwise create an empty range if none existed for VAR. */
static value_range_t *
-get_value_range (tree var)
+get_value_range (const_tree var)
{
value_range_t *vr;
tree sym;
/* Create a default value range. */
vr_value[ver] = vr = XCNEW (value_range_t);
- /* Allocate an equivalence set. */
- vr->equiv = BITMAP_ALLOC (NULL);
+ /* Defer allocating the equivalence set. */
+ vr->equiv = NULL;
/* If VAR is a default definition, the variable can take any value
in VAR's type. */
/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
static inline bool
-vrp_operand_equal_p (tree val1, tree val2)
+vrp_operand_equal_p (const_tree val1, const_tree val2)
{
if (val1 == val2)
return true;
/* Return true, if the bitmaps B1 and B2 are equal. */
static inline bool
-vrp_bitmap_equal_p (bitmap b1, bitmap b2)
+vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
{
return (b1 == b2
|| (b1 && b2
is the range object associated with another SSA name. */
static inline bool
-update_value_range (tree var, value_range_t *new_vr)
+update_value_range (const_tree var, value_range_t *new_vr)
{
value_range_t *old_vr;
bool is_new;
new_vr->equiv);
BITMAP_FREE (new_vr->equiv);
- new_vr->equiv = NULL;
return is_new;
}
-/* Add VAR and VAR's equivalence set to EQUIV. */
+/* Add VAR and VAR's equivalence set to EQUIV. This is the central
+ point where equivalence processing can be turned on/off. */
static void
-add_equivalence (bitmap equiv, tree var)
+add_equivalence (bitmap *equiv, const_tree var)
{
unsigned ver = SSA_NAME_VERSION (var);
value_range_t *vr = vr_value[ver];
- bitmap_set_bit (equiv, ver);
+ if (*equiv == NULL)
+ *equiv = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (*equiv, ver);
if (vr && vr->equiv)
- bitmap_ior_into (equiv, vr->equiv);
+ bitmap_ior_into (*equiv, vr->equiv);
}
|| !is_gimple_min_invariant (vr->max));
}
-/* Return true if value range VR uses a overflow infinity. */
+/* Return true if value range VR uses an overflow infinity. */
static inline bool
overflow_infinity_range_p (value_range_t *vr)
both integers. */
gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
== POINTER_TYPE_P (TREE_TYPE (val2)));
+ /* Convert the two values into the same type. This is needed because
+ sizetype causes sign extension even for unsigned types. */
+ val2 = fold_convert (TREE_TYPE (val1), val2);
+ STRIP_USELESS_TYPE_CONVERSION (val2);
if ((TREE_CODE (val1) == SSA_NAME
|| TREE_CODE (val1) == PLUS_EXPR
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
return -2;
- if (strict_overflow_p != NULL)
+ if (strict_overflow_p != NULL
+ && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
+ && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
*strict_overflow_p = true;
if (code1 == SSA_NAME)
false otherwise or if no value range information is available. */
bool
-ssa_name_nonnegative_p (tree t)
+ssa_name_nonnegative_p (const_tree t)
{
value_range_t *vr = get_value_range (t);
false otherwise or if no value range information is available. */
bool
-ssa_name_nonzero_p (tree t)
+ssa_name_nonzero_p (const_tree t)
{
value_range_t *vr = get_value_range (t);
cond_code = swap_tree_comparison (TREE_CODE (cond));
}
+ limit = avoid_overflow_infinity (limit);
+
type = TREE_TYPE (limit);
gcc_assert (limit != var);
predicates, we will need to trim the set of equivalences before
we are done. */
gcc_assert (vr_p->equiv == NULL);
- vr_p->equiv = BITMAP_ALLOC (NULL);
- add_equivalence (vr_p->equiv, var);
+ add_equivalence (&vr_p->equiv, var);
/* Extract a new range based on the asserted comparison for VAR and
LIMIT's value range. Notice that if LIMIT has an anti-range, we
SSA name, the new range will also inherit the equivalence set
from LIMIT. */
if (TREE_CODE (limit) == SSA_NAME)
- add_equivalence (vr_p->equiv, limit);
+ add_equivalence (&vr_p->equiv, limit);
}
else if (cond_code == NE_EXPR)
{
/* If MIN and MAX cover the whole range for their type, then
just use the original LIMIT. */
if (INTEGRAL_TYPE_P (type)
- && (min == TYPE_MIN_VALUE (type)
- || is_negative_overflow_infinity (min))
- && (max == TYPE_MAX_VALUE (type)
- || is_positive_overflow_infinity (max)))
+ && vrp_val_is_min (min)
+ && vrp_val_is_max (max))
min = max = limit;
set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
{
tree one = build_int_cst (type, 1);
max = fold_build2 (MINUS_EXPR, type, max, one);
+ if (EXPR_P (max))
+ TREE_NO_WARNING (max) = 1;
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
{
tree one = build_int_cst (type, 1);
min = fold_build2 (PLUS_EXPR, type, min, one);
+ if (EXPR_P (min))
+ TREE_NO_WARNING (min) = 1;
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
{
gcc_assert (!is_positive_overflow_infinity (anti_max));
if (needs_overflow_infinity (TREE_TYPE (anti_max))
- && anti_max == TYPE_MAX_VALUE (TREE_TYPE (anti_max)))
+ && vrp_val_is_max (anti_max))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
}
min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
}
- else
+ else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
anti_max,
build_int_cst (TREE_TYPE (var_vr->min), 1));
+ else
+ min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_max, size_int (1));
max = real_max;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
{
gcc_assert (!is_negative_overflow_infinity (anti_min));
if (needs_overflow_infinity (TREE_TYPE (anti_min))
- && anti_min == TYPE_MIN_VALUE (TREE_TYPE (anti_min)))
+ && vrp_val_is_min (anti_min))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
}
max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
}
- else
+ else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
anti_min,
build_int_cst (TREE_TYPE (var_vr->min), 1));
+ else
+ max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_min,
+ size_int (-1));
min = real_min;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
else
set_value_range (vr, VR_RANGE, var, var, NULL);
- add_equivalence (vr->equiv, var);
+ add_equivalence (&vr->equiv, var);
}
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
&& code != MINUS_EXPR
+ && code != POINTER_PLUS_EXPR
&& code != MULT_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
- set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+ set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
|| POINTER_TYPE_P (TREE_TYPE (op0))
|| POINTER_TYPE_P (TREE_TYPE (op1)))
{
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. FIXME, we used
- to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
- ivopts is generating expressions with pointer multiplication
- in them. */
- if (code == PLUS_EXPR)
+ if (code == MIN_EXPR || code == MAX_EXPR)
{
- if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
+ /* For MIN/MAX expressions with pointers, we only care about
+ nullness, if both are non null, then the result is nonnull.
+ If both are null, then the result is null. Otherwise they
+ are varying. */
+ if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
else if (range_is_null (&vr0) && range_is_null (&vr1))
set_value_range_to_null (vr, TREE_TYPE (expr));
else
set_value_range_to_varying (vr);
+
+ return;
}
+ gcc_assert (code == POINTER_PLUS_EXPR);
+ /* For pointer types, we are really only interested in asserting
+ whether the expression evaluates to non-NULL. */
+ if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
+ set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ else if (range_is_null (&vr0) && range_is_null (&vr1))
+ set_value_range_to_null (vr, TREE_TYPE (expr));
else
- {
- /* Subtracting from a pointer, may yield 0, so just drop the
- resulting range to varying. */
- set_value_range_to_varying (vr);
- }
+ set_value_range_to_varying (vr);
return;
}
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_overflow_infinity (min))
- && (max == TYPE_MAX_VALUE (TREE_TYPE (max))
- || is_overflow_infinity (max)))
+ if ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
&& is_gimple_val (new_max)
&& tree_int_cst_equal (new_min, orig_min)
&& tree_int_cst_equal (new_max, orig_max)
+ && (!is_overflow_infinity (new_min)
+ || !is_overflow_infinity (new_max))
&& (cmp = compare_values (new_min, new_max)) <= 0
&& cmp >= -1)
{
min = negative_overflow_infinity (TREE_TYPE (expr));
else if (is_negative_overflow_infinity (vr0.max))
min = positive_overflow_infinity (TREE_TYPE (expr));
- else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ else if (!vrp_val_is_min (vr0.max))
min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
else if (needs_overflow_infinity (TREE_TYPE (expr)))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
+ if (supports_overflow_infinity (TREE_TYPE (expr))
+ && !is_overflow_infinity (vr0.min)
+ && !vrp_val_is_min (vr0.min))
min = positive_overflow_infinity (TREE_TYPE (expr));
else
{
max = negative_overflow_infinity (TREE_TYPE (expr));
else if (is_negative_overflow_infinity (vr0.min))
max = positive_overflow_infinity (TREE_TYPE (expr));
- else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ else if (!vrp_val_is_min (vr0.min))
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
else if (needs_overflow_infinity (TREE_TYPE (expr)))
{
useful range. */
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr))
&& ((vr0.type == VR_RANGE
- && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ && vrp_val_is_min (vr0.min))
|| (vr0.type == VR_ANTI_RANGE
- && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
+ && !vrp_val_is_min (vr0.min)
&& !range_includes_zero_p (&vr0))))
{
set_value_range_to_varying (vr);
included negative values. */
if (is_overflow_infinity (vr0.min))
min = positive_overflow_infinity (TREE_TYPE (expr));
- else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ else if (!vrp_val_is_min (vr0.min))
min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
else if (!needs_overflow_infinity (TREE_TYPE (expr)))
min = TYPE_MAX_VALUE (TREE_TYPE (expr));
if (is_overflow_infinity (vr0.max))
max = positive_overflow_infinity (TREE_TYPE (expr));
- else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ else if (!vrp_val_is_min (vr0.max))
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
else if (!needs_overflow_infinity (TREE_TYPE (expr)))
max = TYPE_MAX_VALUE (TREE_TYPE (expr));
if (needs_overflow_infinity (TREE_TYPE (expr)))
{
gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
+
+ /* If both sides have overflowed, we don't know
+ anything. */
+ if ((is_overflow_infinity (vr0.min)
+ || TREE_OVERFLOW (min))
+ && (is_overflow_infinity (vr0.max)
+ || TREE_OVERFLOW (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
if (is_overflow_infinity (vr0.min))
min = vr0.min;
else if (TREE_OVERFLOW (min))
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
- set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+ set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
its type may be different from _Bool. Convert VAL to EXPR's
type. */
val = fold_convert (TREE_TYPE (expr), val);
- set_value_range (vr, VR_RANGE, val, val, vr->equiv);
+ if (is_gimple_min_invariant (val))
+ set_value_range_to_value (vr, val, vr->equiv);
+ else
+ set_value_range (vr, VR_RANGE, val, val, vr->equiv);
}
else
/* The result of a comparison is always true or false. */
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, expr);
else if (is_gimple_min_invariant (expr))
- set_value_range (vr, VR_RANGE, expr, expr, NULL);
+ set_value_range_to_value (vr, expr, NULL);
else
set_value_range_to_varying (vr);
if (vr->type == VR_ANTI_RANGE)
return;
+ /* Ensure that there are not values in the scev cache based on assumptions
+ on ranges of ssa names that were changed
+ (in set_value_range/set_value_range_to_varying). Preserve cached numbers
+ of iterations, that were computed before the start of VRP (we do not
+ recompute these each time to save the compile time). */
+ scev_reset_except_niters ();
+
chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
+
+ /* Like in PR19590, scev can return a constant function. */
+ if (is_gimple_min_invariant (chrec))
+ {
+ set_value_range_to_value (vr, chrec, vr->equiv);
+ return;
+ }
+
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return;
if (compare_values (min, max) == 1)
return;
}
+
+ /* According to the loop information, the variable does not
+ overflow. If we think it does, probably because of an
+ overflow due to arithmetic on a different INF value,
+ reset now. */
+ if (is_negative_overflow_infinity (min))
+ min = tmin;
}
else
{
if (compare_values (min, max) == 1)
return;
}
+
+ if (is_positive_overflow_infinity (max))
+ max = tmax;
}
set_value_range (vr, VR_RANGE, min, max, vr->equiv);
}
}
+/* Return true if VAR may overflow at STMT. This checks any available
+ loop information to see if we can determine that VAR does not
+ overflow. */
+
+static bool
+vrp_var_may_overflow (tree var, tree stmt)
+{
+ struct loop *l;
+ tree chrec, init, step;
+
+ if (current_loops == NULL)
+ return true;
+
+ l = loop_containing_stmt (stmt);
+ if (l == NULL)
+ return true;
+
+ chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
+ if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
+ return true;
+
+ init = initial_condition_in_loop_num (chrec, l->num);
+ step = evolution_part_in_loop_num (chrec, l->num);
+
+ if (step == NULL_TREE
+ || !is_gimple_min_invariant (step)
+ || !valid_value_p (init))
+ return true;
+
+ /* If we get here, we know something useful about VAR based on the
+ loop information. If it wraps, it may overflow. */
+
+ if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
+ true))
+ return true;
+
+ if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+ {
+ print_generic_expr (dump_file, var, 0);
+ fprintf (dump_file, ": loop information indicates does not overflow\n");
+ }
+
+ return false;
+}
+
/* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
- if (INTEGRAL_TYPE_P (type)
- && !TYPE_UNSIGNED (type)
- && vr->min == TYPE_MIN_VALUE (type))
- fprintf (file, "-INF");
- else if (needs_overflow_infinity (type)
- && is_negative_overflow_infinity (vr->min))
+ if (is_negative_overflow_infinity (vr->min))
fprintf (file, "-INF(OVF)");
+ else if (INTEGRAL_TYPE_P (type)
+ && !TYPE_UNSIGNED (type)
+ && vrp_val_is_min (vr->min))
+ fprintf (file, "-INF");
else
print_generic_expr (file, vr->min, 0);
fprintf (file, ", ");
- if (INTEGRAL_TYPE_P (type)
- && vr->max == TYPE_MAX_VALUE (type))
- fprintf (file, "+INF");
- else if (needs_overflow_infinity (type)
- && is_positive_overflow_infinity (vr->max))
+ if (is_positive_overflow_infinity (vr->max))
fprintf (file, "+INF(OVF)");
+ else if (INTEGRAL_TYPE_P (type)
+ && vrp_val_is_max (vr->max))
+ fprintf (file, "+INF");
else
print_generic_expr (file, vr->max, 0);
point values. */
static inline bool
-fp_predicate (tree expr)
+fp_predicate (const_tree expr)
{
return (COMPARISON_CLASS_P (expr)
&& FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
/* 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);
+ need_assert |= find_assert_locations (e->dest);
/* Register the necessary assertions for each operand in the
conditional predicate. */
static int
compare_case_labels (const void *p1, const void *p2)
{
- tree case1 = *(tree *)p1;
- tree case2 = *(tree *)p2;
+ const_tree const case1 = *(const_tree const*)p1;
+ const_tree const case2 = *(const_tree const*)p2;
unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
low_sub = up_sub = TREE_OPERAND (ref, 1);
- if (!up_bound || !locus || TREE_NO_WARNING (ref)
+ if (!up_bound || TREE_NO_WARNING (ref)
|| TREE_CODE (up_bound) != INTEGER_CST
/* Can not check flexible arrays. */
|| (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
}
}
+/* Searches if the expr T, located at LOCATION computes
+ address of an ARRAY_REF, and call check_array_ref on it. */
+
+static void
+search_for_addr_array(tree t, location_t* location)
+{
+ while (TREE_CODE (t) == SSA_NAME)
+ {
+ t = SSA_NAME_DEF_STMT (t);
+ if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
+ return;
+ t = GIMPLE_STMT_OPERAND (t, 1);
+ }
+
+
+ /* 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 (t, location, true /*ignore_off_by_one*/);
+
+ t = TREE_OPERAND(t,0);
+ }
+ while (handled_component_p (t));
+}
+
/* walk_tree() callback that checks if *TP is
an ARRAY_REF inside an ADDR_EXPR (in which an array
subscript one outside the valid range is allowed). Call
tree stmt = (tree)data;
location_t *location = EXPR_LOCUS (stmt);
+ if (!EXPR_HAS_LOCATION (stmt))
+ {
+ *walk_subtree = FALSE;
+ return NULL_TREE;
+ }
+
*walk_subtree = TRUE;
if (TREE_CODE (t) == ARRAY_REF)
check_array_ref (t, location, false /*ignore_off_by_one*/);
- else if (TREE_CODE (t) == ADDR_EXPR)
- {
- use_operand_p op;
- tree use_stmt;
- t = TREE_OPERAND (t, 0);
-
- /* Don't warn on statements like
-
- ssa_name = 500 + &array[-200]
-
- or
-
- ssa_name = &array[-200]
- other_name = ssa_name + 300;
-
- which are sometimes
- produced by other optimizing passes. */
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1)))
- *walk_subtree = FALSE;
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
- && single_imm_use (GIMPLE_STMT_OPERAND (stmt, 0), &op, &use_stmt)
- && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
- && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1)))
- *walk_subtree = FALSE;
+ if (TREE_CODE (t) == INDIRECT_REF
+ || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
+ search_for_addr_array (TREE_OPERAND (t, 0), location);
+ else if (TREE_CODE (t) == CALL_EXPR)
+ {
+ tree arg;
+ call_expr_arg_iterator iter;
- while (*walk_subtree && handled_component_p (t))
- {
- if (TREE_CODE (t) == ARRAY_REF)
- check_array_ref (t, location, true /*ignore_off_by_one*/);
- t = TREE_OPERAND (t, 0);
- }
- *walk_subtree = FALSE;
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, t)
+ search_for_addr_array (arg, location);
}
+ if (TREE_CODE (t) == ADDR_EXPR)
+ *walk_subtree = FALSE;
+
return NULL_TREE;
}
return SSA_PROP_VARYING;
}
+/* Helper that gets the value range of the SSA_NAME with version I
+ or a symbolic range containing the SSA_NAME only if the value range
+ is varying or undefined. */
+
+static inline value_range_t
+get_vr_for_comparison (int i)
+{
+ value_range_t vr = *(vr_value[i]);
+
+ /* If name N_i does not have a valid range, use N_i as its own
+ range. This allows us to compare against names that may
+ have N_i in their ranges. */
+ if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
+ {
+ vr.type = VR_RANGE;
+ vr.min = ssa_name (i);
+ vr.max = ssa_name (i);
+ }
+
+ return vr;
+}
/* Compare all the value ranges for names equivalent to VAR with VAL
using comparison code COMP. Return the same value returned by
bitmap e;
tree retval, t;
int used_strict_overflow;
-
- t = retval = NULL_TREE;
+ bool sop;
+ value_range_t equiv_vr;
/* Get the set of equivalences for VAR. */
e = get_value_range (var)->equiv;
- /* Add VAR to its own set of equivalences so that VAR's value range
- is processed by this loop (otherwise, we would have to replicate
- the body of the loop just to check VAR's value range). */
- bitmap_set_bit (e, SSA_NAME_VERSION (var));
-
/* Start at -1. Set it to 0 if we do a comparison without relying
on overflow, or 1 if all comparisons rely on overflow. */
used_strict_overflow = -1;
- EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
- {
- bool sop;
-
- value_range_t equiv_vr = *(vr_value[i]);
+ /* Compare vars' value range with val. */
+ equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
+ sop = false;
+ retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
+ if (retval)
+ used_strict_overflow = sop ? 1 : 0;
- /* If name N_i does not have a valid range, use N_i as its own
- range. This allows us to compare against names that may
- have N_i in their ranges. */
- if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
- {
- equiv_vr.type = VR_RANGE;
- equiv_vr.min = ssa_name (i);
- equiv_vr.max = ssa_name (i);
- }
+ /* If the equiv set is empty we have done all work we need to do. */
+ if (e == NULL)
+ {
+ if (retval
+ && used_strict_overflow > 0)
+ *strict_overflow_p = true;
+ return retval;
+ }
+ EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
+ {
+ equiv_vr = get_vr_for_comparison (i);
sop = false;
t = compare_range_with_value (comp, &equiv_vr, val, &sop);
if (t)
}
}
- /* Remove VAR from its own equivalence set. */
- bitmap_clear_bit (e, SSA_NAME_VERSION (var));
-
- if (retval)
- {
- if (used_strict_overflow > 0)
- *strict_overflow_p = true;
- return retval;
- }
+ if (retval
+ && used_strict_overflow > 0)
+ *strict_overflow_p = true;
- /* We couldn't find a non-NULL value for the predicate. */
- return NULL_TREE;
+ return retval;
}
bitmap_iterator bi1, bi2;
unsigned i1, i2;
int used_strict_overflow;
+ static bitmap_obstack *s_obstack = NULL;
+ static bitmap s_e1 = NULL, s_e2 = NULL;
/* Compare the ranges of every name equivalent to N1 against the
ranges of every name equivalent to N2. */
e1 = get_value_range (n1)->equiv;
e2 = get_value_range (n2)->equiv;
+ /* Use the fake bitmaps if e1 or e2 are not available. */
+ if (s_obstack == NULL)
+ {
+ s_obstack = XNEW (bitmap_obstack);
+ bitmap_obstack_initialize (s_obstack);
+ s_e1 = BITMAP_ALLOC (s_obstack);
+ s_e2 = BITMAP_ALLOC (s_obstack);
+ }
+ if (e1 == NULL)
+ e1 = s_e1;
+ if (e2 == NULL)
+ e2 = s_e2;
+
/* Add N1 and N2 to their own set of equivalences to avoid
duplicating the body of the loop just to check N1 and N2
ranges. */
of the loop just to check N1 and N2 ranges. */
EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
{
- value_range_t vr1 = *(vr_value[i1]);
-
- /* If the range is VARYING or UNDEFINED, use the name itself. */
- if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
- {
- vr1.type = VR_RANGE;
- vr1.min = ssa_name (i1);
- vr1.max = ssa_name (i1);
- }
+ value_range_t vr1 = get_vr_for_comparison (i1);
t = retval = NULL_TREE;
EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
{
- bool sop;
-
- value_range_t vr2 = *(vr_value[i2]);
+ bool sop = false;
- if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
- {
- vr2.type = VR_RANGE;
- vr2.min = ssa_name (i2);
- vr2.max = ssa_name (i2);
- }
+ value_range_t vr2 = get_vr_for_comparison (i2);
t = compare_ranges (comp, &vr1, &vr2, &sop);
if (t)
}
}
+ if (warn_type_limits
+ && ret
+ && TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
+ {
+ /* If the comparison is being folded and the operand on the LHS
+ is being compared against a constant value that is outside of
+ the natural range of OP0's type, then the predicate will
+ always fold regardless of the value of OP0. If -Wtype-limits
+ was specified, emit a warning. */
+ const char *warnmsg = NULL;
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+ tree type = TREE_TYPE (op0);
+ value_range_t *vr0 = get_value_range (op0);
+
+ if (vr0->type != VR_VARYING
+ && INTEGRAL_TYPE_P (type)
+ && vrp_val_is_min (vr0->min)
+ && vrp_val_is_max (vr0->max)
+ && is_gimple_min_invariant (op1))
+ {
+ if (integer_zerop (ret))
+ warnmsg = G_("comparison always false due to limited range of "
+ "data type");
+ else
+ warnmsg = G_("comparison always true due to limited range of "
+ "data type");
+ }
+
+ if (warnmsg)
+ {
+ location_t locus;
+
+ if (!EXPR_HAS_LOCATION (stmt))
+ locus = input_location;
+ else
+ locus = EXPR_LOCATION (stmt);
+
+ warning (OPT_Wextra, "%H%s", &locus, warnmsg);
+ }
+ }
+
return ret;
}
else
goto give_up;
+ /* Check for useless ranges. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (min))
+ && ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max))))
+ goto give_up;
+
/* The resulting set of equivalences is the intersection of
the two sets. */
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
}
else
{
+ if (is_overflow_infinity (arg))
+ {
+ arg = copy_node (arg);
+ TREE_OVERFLOW (arg) = 0;
+ }
+
vr_arg.type = VR_RANGE;
vr_arg.min = arg;
vr_arg.max = arg;
{
/* If we will end up with a (-INF, +INF) range, set it
to VARYING. */
- if (is_positive_overflow_infinity (vr_result.max)
- || (vr_result.max
- == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max))))
+ if (vrp_val_is_max (vr_result.max))
goto varying;
- if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)))
+ if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
+ || !vrp_var_may_overflow (lhs, phi))
vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
vr_result.min =
{
/* If we will end up with a (-INF, +INF) range, set it
to VARYING. */
- if (is_negative_overflow_infinity (vr_result.min)
- || (vr_result.min
- == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))))
+ if (vrp_val_is_min (vr_result.min))
goto varying;
- if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)))
+ if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
+ || !vrp_var_may_overflow (lhs, phi))
vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
vr_result.max =
{
bool sop = false;
- val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
if (val
&& sop
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
+ if (EXPR_P (max))
+ TREE_NO_WARNING (max) = 1;
}
}
else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
+ if (EXPR_P (min))
+ TREE_NO_WARNING (min) = 1;
}
}
static void
finalize_jump_threads (void)
{
- bool cfg_altered = false;
- cfg_altered = thread_through_all_blocks ();
-
- /* If we threaded jumps, then we need to recompute the dominance
- information. */
- if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
+ thread_through_all_blocks (false);
VEC_free (tree, heap, stack);
}
vr_phi_edge_counts = NULL;
}
+/* Calculates number of iterations for all loops, to ensure that they are
+ cached. */
+
+static void
+record_numbers_of_iterations (void)
+{
+ loop_iterator li;
+ struct loop *loop;
+
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ number_of_latch_executions (loop);
+ }
+}
/* Main entry point to VRP (Value Range Propagation). This pass is
loosely based on J. R. C. Patterson, ``Accurate Static Branch
static unsigned int
execute_vrp (void)
{
+ loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ scev_initialize ();
+
insert_range_assertions ();
- loop_optimizer_init (LOOPS_NORMAL);
- if (current_loops)
- scev_initialize ();
+ /* Compute the # of iterations for each loop before we start the VRP
+ analysis. The value ranges determined by VRP are used in expression
+ simplification, that is also used by the # of iterations analysis.
+ However, in the middle of the VRP analysis, the value ranges do not take
+ all the possible paths in CFG into account, so they do not have to be
+ correct, and the # of iterations analysis can obtain wrong results.
+ This is a problem, since the results of the # of iterations analysis
+ are cached, so these mistakes would not be corrected when the value
+ ranges are corrected. */
+ record_numbers_of_iterations ();
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize ();
- if (current_loops)
- {
- scev_finalize ();
- loop_optimizer_finalize ();
- }
-
/* ASSERT_EXPRs must be removed before finalizing jump threads
as finalizing jump threads calls the CFG cleanup code which
does not properly handle ASSERT_EXPRs. */
update_ssa (TODO_update_ssa);
finalize_jump_threads ();
+ scev_finalize ();
+ loop_optimizer_finalize ();
+
return 0;
}
OSDN Git Service
