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)
to the integer constant with the same value in the type. */
static inline bool
-vrp_val_is_max (tree val)
+vrp_val_is_max (const_tree val)
{
tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val));
will be true for a negative overflow infinity. */
static inline bool
-vrp_val_is_min (tree val)
+vrp_val_is_min (const_tree val)
{
tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val));
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;
}
/* 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. */
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;
/* 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;
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];
|| !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);
{
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);
}
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);
}
}
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);
}
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
|| 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;
}
&& 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)
{
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:
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
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)
}
/* Helper that gets the value range of the SSA_NAME with version I
- or a symbolic range contaning the SSA_NAME only if the value range
+ or a symbolic range containing the SSA_NAME only if the value range
is varying or undefined. */
static inline value_range_t
equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
sop = false;
retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
- if (sop)
- used_strict_overflow = 1;
+ if (retval)
+ used_strict_overflow = sop ? 1 : 0;
/* If the equiv set is empty we have done all work we need to do. */
if (e == NULL)
t = retval = NULL_TREE;
EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
{
- bool sop;
+ bool sop = false;
value_range_t vr2 = get_vr_for_comparison (i2);
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 (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;
}
}
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
execute_vrp (void)
{
loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
- if (current_loops)
- {
- rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
- scev_initialize ();
- }
+ rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+ scev_initialize ();
insert_range_assertions ();
+ /* 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 ();
update_ssa (TODO_update_ssa);
finalize_jump_threads ();
- if (current_loops)
- {
- scev_finalize ();
- loop_optimizer_finalize ();
- }
+ scev_finalize ();
+ loop_optimizer_finalize ();
return 0;
}
OSDN Git Service
