#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "flags.h"
#include "tree.h"
#include "basic-block.h"
#include "tree-flow.h"
#include "tree-pass.h"
#include "tree-dump.h"
#include "timevar.h"
#include "diagnostic.h"
#include "toplev.h"
#include "intl.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
static sbitmap found_in_subgraph;
static int compare_values (tree val1, tree val2);
static int compare_values_warnv (tree val1, tree val2, bool *);
static tree vrp_evaluate_conditional_warnv (tree, bool, bool *);
struct assert_locus_d
{
basic_block bb;
edge e;
block_stmt_iterator si;
enum tree_code comp_code;
tree val;
struct assert_locus_d *next;
};
typedef struct assert_locus_d *assert_locus_t;
static bitmap need_assert_for;
static assert_locus_t *asserts_for;
static sbitmap blocks_visited;
static value_range_t **vr_value;
static inline bool
needs_overflow_infinity (tree type)
{
return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
}
static inline bool
supports_overflow_infinity (tree type)
{
#ifdef ENABLE_CHECKING
gcc_assert (needs_overflow_infinity (type));
#endif
return (TYPE_MIN_VALUE (type) != NULL_TREE
&& CONSTANT_CLASS_P (TYPE_MIN_VALUE (type))
&& TYPE_MAX_VALUE (type) != NULL_TREE
&& CONSTANT_CLASS_P (TYPE_MAX_VALUE (type)));
}
static inline tree
make_overflow_infinity (tree val)
{
#ifdef ENABLE_CHECKING
gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
#endif
val = copy_node (val);
TREE_OVERFLOW (val) = 1;
return val;
}
static inline tree
negative_overflow_infinity (tree type)
{
#ifdef ENABLE_CHECKING
gcc_assert (supports_overflow_infinity (type));
#endif
return make_overflow_infinity (TYPE_MIN_VALUE (type));
}
static inline tree
positive_overflow_infinity (tree type)
{
#ifdef ENABLE_CHECKING
gcc_assert (supports_overflow_infinity (type));
#endif
return make_overflow_infinity (TYPE_MAX_VALUE (type));
}
static inline bool
is_negative_overflow_infinity (tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
&& operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0));
}
static inline bool
is_positive_overflow_infinity (tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
&& operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0));
}
static inline bool
is_overflow_infinity (tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
&& (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)
|| operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)));
}
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));
}
}
static inline bool
vrp_val_is_max (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)));
}
static inline bool
vrp_val_is_min (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)));
}
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)));
if (arg == cfun->static_chain_decl)
return true;
fntype = TREE_TYPE (current_function_decl);
attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
if (attrs == NULL_TREE)
return false;
if (TREE_VALUE (attrs) == NULL_TREE)
return true;
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);
for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
{
if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
return true;
}
return false;
}
static void
set_value_range (value_range_t *vr, enum value_range_type t, tree min,
tree max, bitmap equiv)
{
#if defined ENABLE_CHECKING
if (t == VR_RANGE || t == VR_ANTI_RANGE)
{
int cmp;
gcc_assert (min && max);
if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
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)
gcc_assert (min == NULL_TREE && max == NULL_TREE);
if (t == VR_UNDEFINED || t == VR_VARYING)
gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
#endif
vr->type = t;
vr->min = min;
vr->max = max;
if (vr->equiv == NULL)
vr->equiv = BITMAP_ALLOC (NULL);
if (equiv != vr->equiv)
{
if (equiv && !bitmap_empty_p (equiv))
bitmap_copy (vr->equiv, equiv);
else
bitmap_clear (vr->equiv);
}
}
static inline void
copy_value_range (value_range_t *to, value_range_t *from)
{
set_value_range (to, from->type, from->min, from->max, from->equiv);
}
static inline void
set_value_range_to_varying (value_range_t *vr)
{
vr->type = VR_VARYING;
vr->min = vr->max = NULL_TREE;
if (vr->equiv)
bitmap_clear (vr->equiv);
}
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);
}
static inline void
set_value_range_to_nonnegative (value_range_t *vr, tree type,
bool overflow_infinity)
{
tree zero;
if (overflow_infinity && !supports_overflow_infinity (type))
{
set_value_range_to_varying (vr);
return;
}
zero = build_int_cst (type, 0);
set_value_range (vr, VR_RANGE, zero,
(overflow_infinity
? positive_overflow_infinity (type)
: TYPE_MAX_VALUE (type)),
vr->equiv);
}
static inline void
set_value_range_to_nonnull (value_range_t *vr, tree type)
{
tree zero = build_int_cst (type, 0);
set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
}
static inline void
set_value_range_to_null (value_range_t *vr, tree type)
{
set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
}
static inline void
set_value_range_to_undefined (value_range_t *vr)
{
vr->type = VR_UNDEFINED;
vr->min = vr->max = NULL_TREE;
if (vr->equiv)
bitmap_clear (vr->equiv);
}
static value_range_t *
get_value_range (tree var)
{
value_range_t *vr;
tree sym;
unsigned ver = SSA_NAME_VERSION (var);
if (! vr_value)
return NULL;
vr = vr_value[ver];
if (vr)
return vr;
vr_value[ver] = vr = XNEW (value_range_t);
memset (vr, 0, sizeof (*vr));
vr->equiv = BITMAP_ALLOC (NULL);
sym = SSA_NAME_VAR (var);
if (var == default_def (sym))
{
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;
}
static inline bool
vrp_operand_equal_p (tree val1, tree val2)
{
if (val1 == val2)
return true;
if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
return false;
if (is_overflow_infinity (val1))
return is_overflow_infinity (val2);
return true;
}
static inline bool
vrp_bitmap_equal_p (bitmap b1, bitmap b2)
{
return (b1 == b2
|| (b1 && b2
&& bitmap_equal_p (b1, b2)));
}
static inline bool
update_value_range (tree var, value_range_t *new_vr)
{
value_range_t *old_vr;
bool is_new;
old_vr = get_value_range (var);
is_new = old_vr->type != new_vr->type
|| !vrp_operand_equal_p (old_vr->min, new_vr->min)
|| !vrp_operand_equal_p (old_vr->max, new_vr->max)
|| !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
if (is_new)
set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
new_vr->equiv);
BITMAP_FREE (new_vr->equiv);
new_vr->equiv = NULL;
return is_new;
}
static void
add_equivalence (bitmap equiv, tree var)
{
unsigned ver = SSA_NAME_VERSION (var);
value_range_t *vr = vr_value[ver];
bitmap_set_bit (equiv, ver);
if (vr && vr->equiv)
bitmap_ior_into (equiv, vr->equiv);
}
static inline bool
range_is_nonnull (value_range_t *vr)
{
return vr->type == VR_ANTI_RANGE
&& integer_zerop (vr->min)
&& integer_zerop (vr->max);
}
static inline bool
range_is_null (value_range_t *vr)
{
return vr->type == VR_RANGE
&& integer_zerop (vr->min)
&& integer_zerop (vr->max);
}
static inline bool
symbolic_range_p (value_range_t *vr)
{
return (!is_gimple_min_invariant (vr->min)
|| !is_gimple_min_invariant (vr->max));
}
static inline bool
overflow_infinity_range_p (value_range_t *vr)
{
return (vr->type == VR_RANGE
&& (is_overflow_infinity (vr->min)
|| is_overflow_infinity (vr->max)));
}
static bool
usable_range_p (value_range_t *vr, bool *strict_overflow_p)
{
gcc_assert (vr->type == VR_RANGE);
if (is_overflow_infinity (vr->min))
{
*strict_overflow_p = true;
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
return false;
}
if (is_overflow_infinity (vr->max))
{
*strict_overflow_p = true;
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
return false;
}
return true;
}
static bool
vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
{
return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p);
}
static bool
vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p)
{
if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p))
return true;
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_t *vr = get_value_range (TREE_OPERAND (base, 0));
if (range_is_nonnull (vr))
return true;
}
}
return false;
}
static bool
valid_value_p (tree expr)
{
if (TREE_CODE (expr) == SSA_NAME)
return true;
if (TREE_CODE (expr) == PLUS_EXPR
|| TREE_CODE (expr) == MINUS_EXPR)
return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
&& TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
return is_gimple_min_invariant (expr);
}
static int
compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
{
if (val1 == val2)
return 0;
gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
== POINTER_TYPE_P (TREE_TYPE (val2)));
if ((TREE_CODE (val1) == SSA_NAME
|| TREE_CODE (val1) == PLUS_EXPR
|| TREE_CODE (val1) == MINUS_EXPR)
&& (TREE_CODE (val2) == SSA_NAME
|| TREE_CODE (val2) == PLUS_EXPR
|| TREE_CODE (val2) == MINUS_EXPR))
{
tree n1, c1, n2, c2;
enum tree_code code1, code2;
if (TREE_CODE (val1) == SSA_NAME)
{
code1 = SSA_NAME;
n1 = val1;
c1 = NULL_TREE;
}
else
{
code1 = TREE_CODE (val1);
n1 = TREE_OPERAND (val1, 0);
c1 = TREE_OPERAND (val1, 1);
if (tree_int_cst_sgn (c1) == -1)
{
if (is_negative_overflow_infinity (c1))
return -2;
c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
if (!c1)
return -2;
code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
}
}
if (TREE_CODE (val2) == SSA_NAME)
{
code2 = SSA_NAME;
n2 = val2;
c2 = NULL_TREE;
}
else
{
code2 = TREE_CODE (val2);
n2 = TREE_OPERAND (val2, 0);
c2 = TREE_OPERAND (val2, 1);
if (tree_int_cst_sgn (c2) == -1)
{
if (is_negative_overflow_infinity (c2))
return -2;
c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
if (!c2)
return -2;
code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
}
}
if (n1 != n2)
return -2;
if (code1 == SSA_NAME
&& code2 == SSA_NAME)
return 0;
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
return -2;
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)
{
if (code2 == PLUS_EXPR)
return -1;
else if (code2 == MINUS_EXPR)
return 1;
}
else if (code1 == PLUS_EXPR)
{
if (code2 == SSA_NAME)
return 1;
else if (code2 == PLUS_EXPR)
return compare_values_warnv (c1, c2, strict_overflow_p);
else if (code2 == MINUS_EXPR)
return 1;
}
else if (code1 == MINUS_EXPR)
{
if (code2 == SSA_NAME)
return -1;
else if (code2 == PLUS_EXPR)
return -1;
else if (code2 == MINUS_EXPR)
return compare_values_warnv (c2, c1, strict_overflow_p);
}
gcc_unreachable ();
}
if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
return -2;
if (!POINTER_TYPE_P (TREE_TYPE (val1)))
{
if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
{
if (strict_overflow_p != NULL)
*strict_overflow_p = true;
if (is_negative_overflow_infinity (val1))
return is_negative_overflow_infinity (val2) ? 0 : -1;
else if (is_negative_overflow_infinity (val2))
return 1;
else if (is_positive_overflow_infinity (val1))
return is_positive_overflow_infinity (val2) ? 0 : 1;
else if (is_positive_overflow_infinity (val2))
return -1;
return -2;
}
return tree_int_cst_compare (val1, val2);
}
else
{
tree t;
if (val1 == val2 || operand_equal_p (val1, val2, 0))
return 0;
t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return -1;
t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return 1;
t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
if (t == boolean_true_node)
return 2;
return -2;
}
}
static int
compare_values (tree val1, tree val2)
{
bool sop;
int ret;
sop = false;
ret = compare_values_warnv (val1, val2, &sop);
if (sop
&& (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
ret = -2;
return ret;
}
static inline int
value_inside_range (tree val, value_range_t *vr)
{
tree cmp1, cmp2;
fold_defer_overflow_warnings ();
cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min);
if (!cmp1)
{
fold_undefer_and_ignore_overflow_warnings ();
return -2;
}
cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max);
fold_undefer_and_ignore_overflow_warnings ();
if (!cmp2)
return -2;
if ((cmp1 != boolean_true_node && cmp1 != boolean_false_node)
|| (cmp2 != boolean_true_node && cmp2 != boolean_false_node))
return -2;
return cmp1 == boolean_true_node && cmp2 == boolean_true_node;
}
static inline bool
value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
{
return (value_inside_range (vr1->min, vr0) == 1
|| value_inside_range (vr1->max, vr0) == 1
|| value_inside_range (vr0->min, vr1) == 1
|| value_inside_range (vr0->max, vr1) == 1);
}
static inline bool
range_includes_zero_p (value_range_t *vr)
{
tree zero;
gcc_assert (vr->type != VR_UNDEFINED
&& vr->type != VR_VARYING
&& !symbolic_range_p (vr));
zero = build_int_cst (TREE_TYPE (vr->min), 0);
switch (value_inside_range (zero, vr))
{
case 1:
case -2:
return TRUE;
default:
return FALSE;
}
}
bool
ssa_name_nonnegative_p (tree t)
{
value_range_t *vr = get_value_range (t);
if (!vr)
return false;
if (vr->type == VR_RANGE)
{
int result = compare_values (vr->min, integer_zero_node);
return (result == 0 || result == 1);
}
return false;
}
bool
ssa_name_nonzero_p (tree t)
{
value_range_t *vr = get_value_range (t);
if (!vr)
return false;
if (vr->type == VR_RANGE && !symbolic_range_p (vr))
return ! range_includes_zero_p (vr);
if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
return range_includes_zero_p (vr);
return false;
}
static void
extract_range_from_assert (value_range_t *vr_p, tree expr)
{
tree var, cond, limit, min, max, type;
value_range_t *var_vr, *limit_vr;
enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
cond = ASSERT_EXPR_COND (expr);
gcc_assert (COMPARISON_CLASS_P (cond));
if (var == TREE_OPERAND (cond, 0))
{
limit = TREE_OPERAND (cond, 1);
cond_code = TREE_CODE (cond);
}
else
{
limit = TREE_OPERAND (cond, 0);
cond_code = swap_tree_comparison (TREE_CODE (cond));
}
limit = avoid_overflow_infinity (limit);
type = TREE_TYPE (limit);
gcc_assert (limit != var);
if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
{
set_value_range_to_varying (vr_p);
return;
}
limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
if (limit_vr
&& (limit_vr->type == VR_UNDEFINED
|| limit_vr->type == VR_VARYING
|| symbolic_range_p (limit_vr)))
limit_vr = NULL;
gcc_assert (vr_p->equiv == NULL);
vr_p->equiv = BITMAP_ALLOC (NULL);
add_equivalence (vr_p->equiv, var);
if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
if (limit_vr)
{
range_type = limit_vr->type;
min = limit_vr->min;
max = limit_vr->max;
}
else
{
range_type = VR_RANGE;
min = limit;
max = limit;
}
set_value_range (vr_p, range_type, min, max, vr_p->equiv);
if (TREE_CODE (limit) == SSA_NAME)
add_equivalence (vr_p->equiv, limit);
}
else if (cond_code == NE_EXPR)
{
if (limit_vr
&& limit_vr->type == VR_RANGE
&& compare_values (limit_vr->min, limit_vr->max) == 0)
{
min = limit_vr->min;
max = limit_vr->max;
}
else
{
min = max = limit;
}
if (INTEGRAL_TYPE_P (type)
&& 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);
}
else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
{
min = TYPE_MIN_VALUE (type);
if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
max = limit;
else
{
max = limit_vr->max;
}
if ((cond_code == LT_EXPR
&& compare_values (max, min) == 0)
|| is_overflow_infinity (max))
set_value_range_to_varying (vr_p);
else
{
if (cond_code == LT_EXPR)
{
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);
}
}
else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
{
max = TYPE_MAX_VALUE (type);
if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
min = limit;
else
{
min = limit_vr->min;
}
if ((cond_code == GT_EXPR
&& compare_values (min, max) == 0)
|| is_overflow_infinity (min))
set_value_range_to_varying (vr_p);
else
{
if (cond_code == GT_EXPR)
{
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);
}
}
else
gcc_unreachable ();
var_vr = get_value_range (var);
if (vr_p->type == VR_VARYING
|| vr_p->type == VR_UNDEFINED
|| var_vr->type == VR_VARYING
|| var_vr->type == VR_UNDEFINED
|| symbolic_range_p (vr_p)
|| symbolic_range_p (var_vr))
return;
if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
{
if (value_ranges_intersect_p (var_vr, vr_p))
{
if (compare_values (vr_p->min, var_vr->min) == -1)
min = var_vr->min;
else
min = vr_p->min;
if (compare_values (vr_p->max, var_vr->max) == 1)
max = var_vr->max;
else
max = vr_p->max;
set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
}
else
{
set_value_range_to_varying (vr_p);
}
}
else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
|| (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
{
if (compare_values (var_vr->min, vr_p->min) == 0
&& compare_values (var_vr->max, vr_p->max) == 0)
set_value_range_to_varying (vr_p);
else
{
tree min, max, anti_min, anti_max, real_min, real_max;
if (vr_p->type == VR_ANTI_RANGE)
{
anti_min = vr_p->min;
anti_max = vr_p->max;
real_min = var_vr->min;
real_max = var_vr->max;
}
else
{
anti_min = var_vr->min;
anti_max = var_vr->max;
real_min = vr_p->min;
real_max = vr_p->max;
}
if (compare_values (anti_max, real_max) == -1
&& compare_values (anti_min, real_min) == 1)
{
set_value_range (vr_p, VR_RANGE, real_min,
real_max, vr_p->equiv);
}
else if (compare_values (anti_min, real_max) == 1
|| compare_values (anti_max, real_min) == -1)
{
set_value_range (vr_p, VR_RANGE, real_min,
real_max, vr_p->equiv);
}
else if ((compare_values (anti_max, real_min) == 1
|| compare_values (anti_max, real_min) == 0)
&& compare_values (anti_max, real_max) == -1)
{
gcc_assert (!is_positive_overflow_infinity (anti_max));
if (needs_overflow_infinity (TREE_TYPE (anti_max))
&& vrp_val_is_max (anti_max))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
set_value_range_to_varying (vr_p);
return;
}
min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
}
else
min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
anti_max,
build_int_cst (TREE_TYPE (var_vr->min), 1));
max = real_max;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
else if (compare_values (anti_min, real_min) == 1
&& (compare_values (anti_min, real_max) == -1
|| compare_values (anti_min, real_max) == 0))
{
gcc_assert (!is_negative_overflow_infinity (anti_min));
if (needs_overflow_infinity (TREE_TYPE (anti_min))
&& vrp_val_is_min (anti_min))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
set_value_range_to_varying (vr_p);
return;
}
max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
}
else
max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
anti_min,
build_int_cst (TREE_TYPE (var_vr->min), 1));
min = real_min;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
}
}
}
static void
extract_range_from_ssa_name (value_range_t *vr, tree var)
{
value_range_t *var_vr = get_value_range (var);
if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
copy_value_range (vr, var_vr);
else
set_value_range (vr, VR_RANGE, var, var, NULL);
add_equivalence (vr->equiv, var);
}
static tree
vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
{
tree res;
res = int_const_binop (code, val1, val2, 0);
if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
{
int checkz = compare_values (res, val1);
bool overflow = false;
if ((code == PLUS_EXPR
&& !(checkz == 1 || checkz == 0))
|| (code == MINUS_EXPR
&& !(checkz == 0 || checkz == -1)))
{
overflow = true;
}
else if (code == MULT_EXPR && !integer_zerop (val1))
{
tree tmp = int_const_binop (TRUNC_DIV_EXPR,
res,
val1, 0);
int check = compare_values (tmp, val2);
if (check != 0)
overflow = true;
}
if (overflow)
{
res = copy_node (res);
TREE_OVERFLOW (res) = 1;
}
}
else if ((TREE_OVERFLOW (res)
&& !TREE_OVERFLOW (val1)
&& !TREE_OVERFLOW (val2))
|| is_overflow_infinity (val1)
|| is_overflow_infinity (val2))
{
int sgn1 = tree_int_cst_sgn (val1);
int sgn2 = tree_int_cst_sgn (val2);
if (needs_overflow_infinity (TREE_TYPE (res))
&& !supports_overflow_infinity (TREE_TYPE (res)))
return NULL_TREE;
if (((code == PLUS_EXPR && sgn1 != sgn2)
|| (code == MINUS_EXPR && sgn1 == sgn2))
&& is_overflow_infinity (val1)
&& is_overflow_infinity (val2))
return NULL_TREE;
if ((code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
|| code == ROUND_DIV_EXPR
|| code == RSHIFT_EXPR)
&& (is_overflow_infinity (val1)
|| is_overflow_infinity (val2)))
return NULL_TREE;
if ((code == MULT_EXPR && sgn1 == sgn2)
|| (code == PLUS_EXPR
&& (sgn1 >= 0
? !is_negative_overflow_infinity (val2)
: is_positive_overflow_infinity (val2)))
|| (code == MINUS_EXPR
&& (sgn1 >= 0
? !is_positive_overflow_infinity (val2)
: is_negative_overflow_infinity (val2)))
|| code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
|| code == ROUND_DIV_EXPR)
return (needs_overflow_infinity (TREE_TYPE (res))
? positive_overflow_infinity (TREE_TYPE (res))
: TYPE_MAX_VALUE (TREE_TYPE (res)));
else
return (needs_overflow_infinity (TREE_TYPE (res))
? negative_overflow_infinity (TREE_TYPE (res))
: TYPE_MIN_VALUE (TREE_TYPE (res)));
}
return res;
}
static void
extract_range_from_binary_expr (value_range_t *vr, tree expr)
{
enum tree_code code = TREE_CODE (expr);
enum value_range_type type;
tree op0, op1, min, max;
int cmp;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
if (code != PLUS_EXPR
&& code != MINUS_EXPR
&& code != MULT_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
&& code != TRUTH_ANDIF_EXPR
&& code != TRUTH_ORIF_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR)
{
set_value_range_to_varying (vr);
return;
}
op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
op1 = TREE_OPERAND (expr, 1);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
{
set_value_range_to_undefined (vr);
return;
}
type = vr0.type;
if (code != BIT_AND_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
|| symbolic_range_p (&vr0)
|| symbolic_range_p (&vr1)))
{
set_value_range_to_varying (vr);
return;
}
if (POINTER_TYPE_P (TREE_TYPE (expr))
|| POINTER_TYPE_P (TREE_TYPE (op0))
|| POINTER_TYPE_P (TREE_TYPE (op1)))
{
if (code == PLUS_EXPR)
{
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);
}
else
{
set_value_range_to_varying (vr);
}
return;
}
if (code == TRUTH_ANDIF_EXPR
|| code == TRUTH_ORIF_EXPR
|| code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR)
{
if (code == TRUTH_AND_EXPR
&& ((vr0.type == VR_RANGE
&& integer_zerop (vr0.min)
&& integer_zerop (vr0.max))
|| (vr1.type == VR_RANGE
&& integer_zerop (vr1.min)
&& integer_zerop (vr1.max))))
{
type = VR_RANGE;
min = max = build_int_cst (TREE_TYPE (expr), 0);
}
else if (code == TRUTH_OR_EXPR
&& ((vr0.type == VR_RANGE
&& integer_onep (vr0.min)
&& integer_onep (vr0.max))
|| (vr1.type == VR_RANGE
&& integer_onep (vr1.min)
&& integer_onep (vr1.max))))
{
type = VR_RANGE;
min = max = build_int_cst (TREE_TYPE (expr), 1);
}
else if (vr0.type != VR_VARYING
&& vr1.type != VR_VARYING
&& vr0.type == vr1.type
&& !symbolic_range_p (&vr0)
&& !overflow_infinity_range_p (&vr0)
&& !symbolic_range_p (&vr1)
&& !overflow_infinity_range_p (&vr1))
{
min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
}
else
{
set_value_range_to_varying (vr);
return;
}
}
else if (code == PLUS_EXPR
|| code == MIN_EXPR
|| code == MAX_EXPR)
{
if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
}
min = vrp_int_const_binop (code, vr0.min, vr1.min);
max = vrp_int_const_binop (code, vr0.max, vr1.max);
}
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 val[4];
size_t i;
bool sop;
if (code == MULT_EXPR
&& vr0.type == VR_ANTI_RANGE
&& !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
{
set_value_range_to_varying (vr);
return;
}
if (code != MULT_EXPR
&& (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
{
set_value_range_to_varying (vr);
return;
}
sop = false;
val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
if (val[0] == NULL_TREE)
sop = true;
if (vr1.max == vr1.min)
val[1] = NULL_TREE;
else
{
val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
if (val[1] == NULL_TREE)
sop = true;
}
if (vr0.max == vr0.min)
val[2] = NULL_TREE;
else
{
val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
if (val[2] == NULL_TREE)
sop = true;
}
if (vr0.min == vr0.max || vr1.min == vr1.max)
val[3] = NULL_TREE;
else
{
val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
if (val[3] == NULL_TREE)
sop = true;
}
if (sop)
{
set_value_range_to_varying (vr);
return;
}
min = val[0];
max = val[0];
for (i = 1; i < 4; i++)
{
if (!is_gimple_min_invariant (min)
|| (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
|| !is_gimple_min_invariant (max)
|| (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
break;
if (val[i])
{
if (!is_gimple_min_invariant (val[i])
|| (TREE_OVERFLOW (val[i])
&& !is_overflow_infinity (val[i])))
{
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];
}
}
}
else if (code == MINUS_EXPR)
{
if (vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
}
min = vrp_int_const_binop (code, vr0.min, vr1.max);
max = vrp_int_const_binop (code, vr0.max, vr1.min);
}
else if (code == BIT_AND_EXPR)
{
if (vr0.type == VR_RANGE
&& vr0.min == vr0.max
&& TREE_CODE (vr0.max) == INTEGER_CST
&& !TREE_OVERFLOW (vr0.max)
&& tree_int_cst_sgn (vr0.max) >= 0)
{
min = build_int_cst (TREE_TYPE (expr), 0);
max = vr0.max;
}
else if (vr1.type == VR_RANGE
&& vr1.min == vr1.max
&& TREE_CODE (vr1.max) == INTEGER_CST
&& !TREE_OVERFLOW (vr1.max)
&& tree_int_cst_sgn (vr1.max) >= 0)
{
type = VR_RANGE;
min = build_int_cst (TREE_TYPE (expr), 0);
max = vr1.max;
}
else
{
set_value_range_to_varying (vr);
return;
}
}
else
gcc_unreachable ();
if (min == NULL_TREE
|| !is_gimple_min_invariant (min)
|| (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
|| max == NULL_TREE
|| !is_gimple_min_invariant (max)
|| (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
}
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;
}
cmp = compare_values (min, max);
if (cmp == -2 || cmp == 1)
{
set_value_range_to_varying (vr);
}
else
set_value_range (vr, type, min, max, NULL);
}
static void
extract_range_from_unary_expr (value_range_t *vr, tree expr)
{
enum tree_code code = TREE_CODE (expr);
tree min, max, op0;
int cmp;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
if (code == FIX_TRUNC_EXPR
|| code == FIX_CEIL_EXPR
|| code == FIX_FLOOR_EXPR
|| code == FIX_ROUND_EXPR
|| code == FLOAT_EXPR
|| code == BIT_NOT_EXPR
|| code == NON_LVALUE_EXPR
|| code == CONJ_EXPR)
{
set_value_range_to_varying (vr);
return;
}
op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
if (vr0.type == VR_UNDEFINED)
{
set_value_range_to_undefined (vr);
return;
}
if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& !POINTER_TYPE_P (TREE_TYPE (op0)))
|| (vr0.type != VR_VARYING
&& symbolic_range_p (&vr0)))
{
set_value_range_to_varying (vr);
return;
}
if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
{
bool sop;
sop = false;
if (range_is_nonnull (&vr0)
|| (tree_expr_nonzero_warnv_p (expr, &sop)
&& !sop))
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
else if (range_is_null (&vr0))
set_value_range_to_null (vr, TREE_TYPE (expr));
else
set_value_range_to_varying (vr);
return;
}
if (code == NOP_EXPR || code == CONVERT_EXPR)
{
tree inner_type = TREE_TYPE (op0);
tree outer_type = TREE_TYPE (expr);
if ((vr0.type == VR_RANGE
&& !overflow_infinity_range_p (&vr0))
|| (vr0.type == VR_VARYING
&& TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
{
tree new_min, new_max, orig_min, orig_max;
if (vr0.type == VR_RANGE)
{
orig_min = vr0.min;
orig_max = vr0.max;
}
else
{
orig_min = TYPE_MIN_VALUE (inner_type);
orig_max = TYPE_MAX_VALUE (inner_type);
}
new_min = fold_convert (outer_type, orig_min);
new_max = fold_convert (outer_type, orig_max);
if (is_gimple_val (new_min)
&& 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))
&& compare_values (new_min, new_max) <= 0
&& compare_values (new_min, new_max) >= -1)
{
set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
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;
}
}
if (vr0.type == VR_VARYING)
{
set_value_range_to_varying (vr);
return;
}
if (code == NEGATE_EXPR
&& !TYPE_UNSIGNED (TREE_TYPE (expr)))
{
if (is_positive_overflow_infinity (vr0.max))
min = negative_overflow_infinity (TREE_TYPE (expr));
else if (is_negative_overflow_infinity (vr0.max))
min = positive_overflow_infinity (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))
&& !is_overflow_infinity (vr0.min)
&& !vrp_val_is_min (vr0.min))
min = positive_overflow_infinity (TREE_TYPE (expr));
else
{
set_value_range_to_varying (vr);
return;
}
}
else
min = TYPE_MIN_VALUE (TREE_TYPE (expr));
if (is_positive_overflow_infinity (vr0.min))
max = negative_overflow_infinity (TREE_TYPE (expr));
else if (is_negative_overflow_infinity (vr0.min))
max = positive_overflow_infinity (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)))
{
if (supports_overflow_infinity (TREE_TYPE (expr)))
max = positive_overflow_infinity (TREE_TYPE (expr));
else
{
set_value_range_to_varying (vr);
return;
}
}
else
max = TYPE_MIN_VALUE (TREE_TYPE (expr));
}
else if (code == NEGATE_EXPR
&& TYPE_UNSIGNED (TREE_TYPE (expr)))
{
if (!range_includes_zero_p (&vr0))
{
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
}
else
{
if (range_is_null (&vr0))
set_value_range_to_null (vr, TREE_TYPE (expr));
else
set_value_range_to_varying (vr);
return;
}
}
else if (code == ABS_EXPR
&& !TYPE_UNSIGNED (TREE_TYPE (expr)))
{
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr))
&& ((vr0.type == VR_RANGE
&& vrp_val_is_min (vr0.min))
|| (vr0.type == VR_ANTI_RANGE
&& !vrp_val_is_min (vr0.min)
&& !range_includes_zero_p (&vr0))))
{
set_value_range_to_varying (vr);
return;
}
if (is_overflow_infinity (vr0.min))
min = positive_overflow_infinity (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));
else if (supports_overflow_infinity (TREE_TYPE (expr)))
min = positive_overflow_infinity (TREE_TYPE (expr));
else
{
set_value_range_to_varying (vr);
return;
}
if (is_overflow_infinity (vr0.max))
max = positive_overflow_infinity (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));
else if (supports_overflow_infinity (TREE_TYPE (expr)))
max = positive_overflow_infinity (TREE_TYPE (expr));
else
{
set_value_range_to_varying (vr);
return;
}
cmp = compare_values (min, max);
if (vr0.type == VR_ANTI_RANGE)
{
if (range_includes_zero_p (&vr0))
{
if (cmp != 1)
max = min;
if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
{
tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
min = (vr0.min != type_min_value
? int_const_binop (PLUS_EXPR, type_min_value,
integer_one_node, 0)
: type_min_value);
}
else
{
if (overflow_infinity_range_p (&vr0))
min = negative_overflow_infinity (TREE_TYPE (expr));
else
min = TYPE_MIN_VALUE (TREE_TYPE (expr));
}
}
else
{
vr0.type = VR_RANGE;
min = build_int_cst (TREE_TYPE (expr), 0);
if (needs_overflow_infinity (TREE_TYPE (expr)))
{
if (supports_overflow_infinity (TREE_TYPE (expr)))
max = positive_overflow_infinity (TREE_TYPE (expr));
else
{
set_value_range_to_varying (vr);
return;
}
}
else
max = TYPE_MAX_VALUE (TREE_TYPE (expr));
}
}
else if (range_includes_zero_p (&vr0))
{
if (cmp == 1)
max = min;
min = build_int_cst (TREE_TYPE (expr), 0);
}
else
{
if (cmp == 1)
{
tree t = min;
min = max;
max = t;
}
}
}
else
{
min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
if (needs_overflow_infinity (TREE_TYPE (expr)))
{
gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
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 (supports_overflow_infinity (TREE_TYPE (expr)))
min = (tree_int_cst_sgn (min) >= 0
? positive_overflow_infinity (TREE_TYPE (min))
: negative_overflow_infinity (TREE_TYPE (min)));
else
{
set_value_range_to_varying (vr);
return;
}
}
if (is_overflow_infinity (vr0.max))
max = vr0.max;
else if (TREE_OVERFLOW (max))
{
if (supports_overflow_infinity (TREE_TYPE (expr)))
max = (tree_int_cst_sgn (max) >= 0
? positive_overflow_infinity (TREE_TYPE (max))
: negative_overflow_infinity (TREE_TYPE (max)));
else
{
set_value_range_to_varying (vr);
return;
}
}
}
}
cmp = compare_values (min, max);
if (cmp == -2 || cmp == 1)
{
set_value_range_to_varying (vr);
}
else
set_value_range (vr, vr0.type, min, max, NULL);
}
static void
extract_range_from_comparison (value_range_t *vr, tree expr)
{
bool sop = false;
tree val = vrp_evaluate_conditional_warnv (expr, false, &sop);
if (val && !is_overflow_infinity (val) && !sop)
{
val = fold_convert (TREE_TYPE (expr), val);
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
set_value_range_to_varying (vr);
}
static void
extract_range_from_expr (value_range_t *vr, tree expr)
{
enum tree_code code = TREE_CODE (expr);
if (code == ASSERT_EXPR)
extract_range_from_assert (vr, expr);
else if (code == SSA_NAME)
extract_range_from_ssa_name (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_binary
|| code == TRUTH_ANDIF_EXPR
|| code == TRUTH_ORIF_EXPR
|| code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR
|| code == TRUTH_XOR_EXPR)
extract_range_from_binary_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_unary)
extract_range_from_unary_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, expr);
else if (is_gimple_min_invariant (expr))
set_value_range_to_value (vr, expr, NULL);
else
set_value_range_to_varying (vr);
if (vr->type == VR_VARYING)
{
bool sop = false;
if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
&& vrp_expr_computes_nonnegative (expr, &sop))
set_value_range_to_nonnegative (vr, TREE_TYPE (expr),
sop || is_overflow_infinity (expr));
else if (vrp_expr_computes_nonzero (expr, &sop)
&& !sop)
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
}
}
static void
adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
tree var)
{
tree init, step, chrec, tmin, tmax, min, max, type;
enum ev_direction dir;
if (vr->type == VR_ANTI_RANGE)
return;
chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return;
init = initial_condition_in_loop_num (chrec, loop->num);
step = evolution_part_in_loop_num (chrec, loop->num);
if (step == NULL_TREE
|| !is_gimple_min_invariant (step)
|| !valid_value_p (init))
return;
dir = scev_direction (chrec);
if (
dir == EV_DIR_UNKNOWN
|| scev_probably_wraps_p (init, step, stmt,
current_loops->parray[CHREC_VARIABLE (chrec)],
true))
return;
type = TREE_TYPE (var);
if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
tmin = lower_bound_in_type (type, type);
else
tmin = TYPE_MIN_VALUE (type);
if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
tmax = upper_bound_in_type (type, type);
else
tmax = TYPE_MAX_VALUE (type);
if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
{
min = tmin;
max = tmax;
if (dir == EV_DIR_DECREASES)
max = init;
else
min = init;
if (compare_values (min, max) == 1)
return;
set_value_range (vr, VR_RANGE, min, max, vr->equiv);
}
else if (vr->type == VR_RANGE)
{
min = vr->min;
max = vr->max;
if (dir == EV_DIR_DECREASES)
{
if (compare_values (init, max) == -1)
{
max = init;
if (compare_values (min, max) == 1)
return;
}
if (is_negative_overflow_infinity (min))
min = tmin;
}
else
{
if (compare_values (init, min) == 1)
{
min = init;
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);
}
}
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 (scev_probably_wraps_p (init, step, stmt,
current_loops->parray[CHREC_VARIABLE (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;
}
static tree
compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
bool *strict_overflow_p)
{
if (vr0->type == VR_VARYING
|| vr0->type == VR_UNDEFINED
|| vr1->type == VR_VARYING
|| vr1->type == VR_UNDEFINED)
return NULL_TREE;
if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
return NULL_TREE;
if (comp == GT_EXPR
|| comp == GE_EXPR
|| comp == LT_EXPR
|| comp == LE_EXPR)
return NULL_TREE;
if (vr0->type == VR_RANGE)
{
value_range_t *tmp = vr0;
vr0 = vr1;
vr1 = tmp;
}
gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
&& compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
return NULL_TREE;
}
if (!usable_range_p (vr0, strict_overflow_p)
|| !usable_range_p (vr1, strict_overflow_p))
return NULL_TREE;
if (comp == GT_EXPR || comp == GE_EXPR)
{
value_range_t *tmp;
comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
tmp = vr0;
vr0 = vr1;
vr1 = tmp;
}
if (comp == EQ_EXPR)
{
if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
&& compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
{
int cmp_min = compare_values_warnv (vr0->min, vr1->min,
strict_overflow_p);
int cmp_max = compare_values_warnv (vr0->max, vr1->max,
strict_overflow_p);
if (cmp_min == 0 && cmp_max == 0)
return boolean_true_node;
else if (cmp_min != -2 && cmp_max != -2)
return boolean_false_node;
}
else if (compare_values_warnv (vr0->min, vr1->max,
strict_overflow_p) == 1
|| compare_values_warnv (vr1->min, vr0->max,
strict_overflow_p) == 1)
return boolean_false_node;
return NULL_TREE;
}
else if (comp == NE_EXPR)
{
int cmp1, cmp2;
cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
return boolean_true_node;
else if (compare_values_warnv (vr0->min, vr0->max,
strict_overflow_p) == 0
&& compare_values_warnv (vr1->min, vr1->max,
strict_overflow_p) == 0
&& compare_values_warnv (vr0->min, vr1->min,
strict_overflow_p) == 0
&& compare_values_warnv (vr0->max, vr1->max,
strict_overflow_p) == 0)
return boolean_false_node;
else
return NULL_TREE;
}
else if (comp == LT_EXPR || comp == LE_EXPR)
{
int tst;
tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
if ((comp == LT_EXPR && tst == -1)
|| (comp == LE_EXPR && (tst == -1 || tst == 0)))
{
if (overflow_infinity_range_p (vr0)
|| overflow_infinity_range_p (vr1))
*strict_overflow_p = true;
return boolean_true_node;
}
tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
if ((comp == LT_EXPR && (tst == 0 || tst == 1))
|| (comp == LE_EXPR && tst == 1))
{
if (overflow_infinity_range_p (vr0)
|| overflow_infinity_range_p (vr1))
*strict_overflow_p = true;
return boolean_false_node;
}
return NULL_TREE;
}
gcc_unreachable ();
}
static tree
compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val,
bool *strict_overflow_p)
{
if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
return NULL_TREE;
if (vr->type == VR_ANTI_RANGE)
{
if (comp == GT_EXPR
|| comp == GE_EXPR
|| comp == LT_EXPR
|| comp == LE_EXPR)
return NULL_TREE;
if (value_inside_range (val, vr) == 1)
return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
return NULL_TREE;
}
if (!usable_range_p (vr, strict_overflow_p))
return NULL_TREE;
if (comp == EQ_EXPR)
{
if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
{
int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
if (cmp == 0)
return boolean_true_node;
else if (cmp == -1 || cmp == 1 || cmp == 2)
return boolean_false_node;
}
else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
|| compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
return boolean_false_node;
return NULL_TREE;
}
else if (comp == NE_EXPR)
{
if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
|| compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
return boolean_true_node;
if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
&& compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
return boolean_false_node;
return NULL_TREE;
}
else if (comp == LT_EXPR || comp == LE_EXPR)
{
int tst;
tst = compare_values_warnv (vr->max, val, strict_overflow_p);
if ((comp == LT_EXPR && tst == -1)
|| (comp == LE_EXPR && (tst == -1 || tst == 0)))
{
if (overflow_infinity_range_p (vr))
*strict_overflow_p = true;
return boolean_true_node;
}
tst = compare_values_warnv (vr->min, val, strict_overflow_p);
if ((comp == LT_EXPR && (tst == 0 || tst == 1))
|| (comp == LE_EXPR && tst == 1))
{
if (overflow_infinity_range_p (vr))
*strict_overflow_p = true;
return boolean_false_node;
}
return NULL_TREE;
}
else if (comp == GT_EXPR || comp == GE_EXPR)
{
int tst;
tst = compare_values_warnv (vr->min, val, strict_overflow_p);
if ((comp == GT_EXPR && tst == 1)
|| (comp == GE_EXPR && (tst == 0 || tst == 1)))
{
if (overflow_infinity_range_p (vr))
*strict_overflow_p = true;
return boolean_true_node;
}
tst = compare_values_warnv (vr->max, val, strict_overflow_p);
if ((comp == GT_EXPR && (tst == -1 || tst == 0))
|| (comp == GE_EXPR && tst == -1))
{
if (overflow_infinity_range_p (vr))
*strict_overflow_p = true;
return boolean_false_node;
}
return NULL_TREE;
}
gcc_unreachable ();
}
void dump_value_range (FILE *, value_range_t *);
void debug_value_range (value_range_t *);
void dump_all_value_ranges (FILE *);
void debug_all_value_ranges (void);
void dump_vr_equiv (FILE *, bitmap);
void debug_vr_equiv (bitmap);
void
dump_value_range (FILE *file, value_range_t *vr)
{
if (vr == NULL)
fprintf (file, "[]");
else if (vr->type == VR_UNDEFINED)
fprintf (file, "UNDEFINED");
else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
{
tree type = TREE_TYPE (vr->min);
fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
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 (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);
fprintf (file, "]");
if (vr->equiv)
{
bitmap_iterator bi;
unsigned i, c = 0;
fprintf (file, " EQUIVALENCES: { ");
EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
{
print_generic_expr (file, ssa_name (i), 0);
fprintf (file, " ");
c++;
}
fprintf (file, "} (%u elements)", c);
}
}
else if (vr->type == VR_VARYING)
fprintf (file, "VARYING");
else
fprintf (file, "INVALID RANGE");
}
void
debug_value_range (value_range_t *vr)
{
dump_value_range (stderr, vr);
fprintf (stderr, "\n");
}
void
dump_all_value_ranges (FILE *file)
{
size_t i;
for (i = 0; i < num_ssa_names; i++)
{
if (vr_value[i])
{
print_generic_expr (file, ssa_name (i), 0);
fprintf (file, ": ");
dump_value_range (file, vr_value[i]);
fprintf (file, "\n");
}
}
fprintf (file, "\n");
}
void
debug_all_value_ranges (void)
{
dump_all_value_ranges (stderr);
}
static tree
build_assert_expr_for (tree cond, tree v)
{
tree n, assertion;
gcc_assert (TREE_CODE (v) == SSA_NAME);
n = duplicate_ssa_name (v, NULL_TREE);
if (COMPARISON_CLASS_P (cond))
{
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
}
else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
{
tree op0 = TREE_OPERAND (cond, 0);
gcc_assert (op0 == v);
assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
}
else if (TREE_CODE (cond) == SSA_NAME)
{
gcc_assert (v == cond);
assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
}
else
gcc_unreachable ();
SSA_NAME_DEF_STMT (n) = assertion;
register_new_name_mapping (n, v);
return assertion;
}
static inline bool
fp_predicate (tree expr)
{
return (COMPARISON_CLASS_P (expr)
&& FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
}
static bool
infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
{
*val_p = NULL_TREE;
*comp_code_p = ERROR_MARK;
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
return false;
if (tree_could_throw_p (stmt))
return false;
if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
return false;
if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
{
bool is_store;
unsigned num_uses, num_derefs;
count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
if (num_derefs > 0)
{
*val_p = build_int_cst (TREE_TYPE (op), 0);
*comp_code_p = NE_EXPR;
return true;
}
}
return false;
}
void dump_asserts_for (FILE *, tree);
void debug_asserts_for (tree);
void dump_all_asserts (FILE *);
void debug_all_asserts (void);
void
dump_asserts_for (FILE *file, tree name)
{
assert_locus_t loc;
fprintf (file, "Assertions to be inserted for ");
print_generic_expr (file, name, 0);
fprintf (file, "\n");
loc = asserts_for[SSA_NAME_VERSION (name)];
while (loc)
{
fprintf (file, "\t");
print_generic_expr (file, bsi_stmt (loc->si), 0);
fprintf (file, "\n\tBB #%d", loc->bb->index);
if (loc->e)
{
fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
loc->e->dest->index);
dump_edge_info (file, loc->e, 0);
}
fprintf (file, "\n\tPREDICATE: ");
print_generic_expr (file, name, 0);
fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
print_generic_expr (file, loc->val, 0);
fprintf (file, "\n\n");
loc = loc->next;
}
fprintf (file, "\n");
}
void
debug_asserts_for (tree name)
{
dump_asserts_for (stderr, name);
}
void
dump_all_asserts (FILE *file)
{
unsigned i;
bitmap_iterator bi;
fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
dump_asserts_for (file, ssa_name (i));
fprintf (file, "\n");
}
void
debug_all_asserts (void)
{
dump_all_asserts (stderr);
}
static void
register_new_assert_for (tree name,
enum tree_code comp_code,
tree val,
basic_block bb,
edge e,
block_stmt_iterator si)
{
assert_locus_t n, loc, last_loc;
bool found;
basic_block dest_bb;
#if defined ENABLE_CHECKING
gcc_assert (bb == NULL || e == NULL);
if (e == NULL)
gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
&& TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
#endif
dest_bb = (bb) ? bb : e->dest;
loc = asserts_for[SSA_NAME_VERSION (name)];
last_loc = loc;
found = false;
while (loc)
{
if (loc->comp_code == comp_code
&& (loc->val == val
|| operand_equal_p (loc->val, val, 0)))
{
if (e == NULL
&& dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
return;
if ((e == NULL || !EDGE_CRITICAL_P (e))
&& dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
{
loc->bb = dest_bb;
loc->e = e;
loc->si = si;
return;
}
}
last_loc = loc;
loc = loc->next;
}
n = XNEW (struct assert_locus_d);
n->bb = dest_bb;
n->e = e;
n->si = si;
n->comp_code = comp_code;
n->val = val;
n->next = NULL;
if (last_loc)
last_loc->next = n;
else
asserts_for[SSA_NAME_VERSION (name)] = n;
bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
}
static bool
register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
{
tree val, stmt;
enum tree_code comp_code;
stmt = bsi_stmt (si);
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
return false;
if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
return false;
if (TREE_CODE (stmt) == COND_EXPR)
{
tree cond = COND_EXPR_COND (stmt);
bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
if (cond == name)
{
comp_code = EQ_EXPR;
val = (is_else_edge) ? boolean_false_node : boolean_true_node;
}
else
{
if (name == TREE_OPERAND (cond, 1))
{
comp_code = swap_tree_comparison (TREE_CODE (cond));
val = TREE_OPERAND (cond, 0);
}
else
{
comp_code = TREE_CODE (cond);
val = TREE_OPERAND (cond, 1);
}
if (is_else_edge)
comp_code = invert_tree_comparison (comp_code, 0);
if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
&& (INTEGRAL_TYPE_P (TREE_TYPE (val))
|| SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
{
tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
if (comp_code == GT_EXPR && compare_values (val, max) == 0)
return false;
if (comp_code == LT_EXPR && compare_values (val, min) == 0)
return false;
}
}
}
else
{
gcc_unreachable ();
}
register_new_assert_for (name, comp_code, val, NULL, e, si);
return true;
}
static bool find_assert_locations (basic_block bb);
static bool
find_conditional_asserts (basic_block bb)
{
bool need_assert;
block_stmt_iterator last_si;
tree op, last;
edge_iterator ei;
edge e;
ssa_op_iter iter;
need_assert = false;
last_si = bsi_last (bb);
last = bsi_stmt (last_si);
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest == bb)
continue;
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
if (e->dest != bb)
need_assert |= find_assert_locations (e->dest);
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
need_assert |= register_edge_assert_for (op, e, last_si);
}
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
return need_assert;
}
static bool
find_assert_locations (basic_block bb)
{
block_stmt_iterator si;
tree last, phi;
bool need_assert;
basic_block son;
if (TEST_BIT (blocks_visited, bb->index))
return false;
SET_BIT (blocks_visited, bb->index);
need_assert = false;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
use_operand_p arg_p;
ssa_op_iter i;
FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
{
tree arg = USE_FROM_PTR (arg_p);
if (TREE_CODE (arg) == SSA_NAME)
{
gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
}
}
}
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);
FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
{
tree value;
enum tree_code comp_code;
SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
if (infer_value_range (stmt, op, &comp_code, &value))
{
if (comp_code == NE_EXPR && integer_zerop (value))
{
tree t = op;
tree def_stmt = SSA_NAME_DEF_STMT (t);
while (TREE_CODE (def_stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR
&& TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))))
{
t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
def_stmt = SSA_NAME_DEF_STMT (t);
if (! has_single_use (t))
{
register_new_assert_for (t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
}
}
if (!has_single_use (op))
{
register_new_assert_for (op, comp_code, value, bb, NULL, si);
need_assert = true;
}
}
}
last = stmt;
}
if (last
&& TREE_CODE (last) == COND_EXPR
&& !fp_predicate (COND_EXPR_COND (last))
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
need_assert |= find_conditional_asserts (bb);
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
son = next_dom_son (CDI_DOMINATORS, son))
need_assert |= find_assert_locations (son);
return need_assert;
}
static bool
process_assert_insertions_for (tree name, assert_locus_t loc)
{
tree stmt, cond, assert_expr;
edge_iterator ei;
edge e;
cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
{
#if defined ENABLE_CHECKING
gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
|| TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
#endif
bsi_insert_on_edge (loc->e, assert_expr);
return true;
}
stmt = bsi_stmt (loc->si);
if (!stmt_ends_bb_p (stmt))
{
bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
return false;
}
FOR_EACH_EDGE (e, ei, loc->bb->succs)
if (!(e->flags & EDGE_ABNORMAL))
{
bsi_insert_on_edge (e, assert_expr);
return true;
}
gcc_unreachable ();
}
static void
process_assert_insertions (void)
{
unsigned i;
bitmap_iterator bi;
bool update_edges_p = false;
int num_asserts = 0;
if (dump_file && (dump_flags & TDF_DETAILS))
dump_all_asserts (dump_file);
EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
{
assert_locus_t loc = asserts_for[i];
gcc_assert (loc);
while (loc)
{
assert_locus_t next = loc->next;
update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
free (loc);
loc = next;
num_asserts++;
}
}
if (update_edges_p)
bsi_commit_edge_inserts ();
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
num_asserts);
}
static void
insert_range_assertions (void)
{
edge e;
edge_iterator ei;
bool update_ssa_p;
found_in_subgraph = sbitmap_alloc (num_ssa_names);
sbitmap_zero (found_in_subgraph);
blocks_visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (blocks_visited);
need_assert_for = BITMAP_ALLOC (NULL);
asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
calculate_dominance_info (CDI_DOMINATORS);
update_ssa_p = false;
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
if (find_assert_locations (e->dest))
update_ssa_p = true;
if (update_ssa_p)
{
process_assert_insertions ();
update_ssa (TODO_update_ssa_no_phi);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
dump_function_to_file (current_function_decl, dump_file, dump_flags);
}
sbitmap_free (found_in_subgraph);
free (asserts_for);
BITMAP_FREE (need_assert_for);
}
static void
remove_range_assertions (void)
{
basic_block bb;
block_stmt_iterator si;
FOR_EACH_BB (bb)
for (si = bsi_start (bb); !bsi_end_p (si);)
{
tree stmt = bsi_stmt (si);
tree use_stmt;
if (TREE_CODE (stmt) == MODIFY_EXPR
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
{
tree rhs = TREE_OPERAND (stmt, 1), var;
tree cond = fold (ASSERT_EXPR_COND (rhs));
use_operand_p use_p;
imm_use_iterator iter;
gcc_assert (cond != boolean_false_node);
var = ASSERT_EXPR_VAR (rhs);
FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0))
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
{
SET_USE (use_p, var);
gcc_assert (TREE_CODE (var) == SSA_NAME);
}
bsi_remove (&si, true);
}
else
bsi_next (&si);
}
sbitmap_free (blocks_visited);
}
static bool
stmt_interesting_for_vrp (tree stmt)
{
if (TREE_CODE (stmt) == PHI_NODE
&& is_gimple_reg (PHI_RESULT (stmt))
&& (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
|| POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
return true;
else if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
tree rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (lhs) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| POINTER_TYPE_P (TREE_TYPE (lhs)))
&& ((TREE_CODE (rhs) == CALL_EXPR
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
&& DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
&& DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
return true;
}
else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
return true;
return false;
}
static void
vrp_initialize (void)
{
basic_block bb;
vr_value = XNEWVEC (value_range_t *, num_ssa_names);
memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
FOR_EACH_BB (bb)
{
block_stmt_iterator si;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
if (!stmt_interesting_for_vrp (phi))
{
tree lhs = PHI_RESULT (phi);
set_value_range_to_varying (get_value_range (lhs));
DONT_SIMULATE_AGAIN (phi) = true;
}
else
DONT_SIMULATE_AGAIN (phi) = false;
}
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
tree stmt = bsi_stmt (si);
if (!stmt_interesting_for_vrp (stmt))
{
ssa_op_iter i;
tree def;
FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
set_value_range_to_varying (get_value_range (def));
DONT_SIMULATE_AGAIN (stmt) = true;
}
else
{
DONT_SIMULATE_AGAIN (stmt) = false;
}
}
}
}
static enum ssa_prop_result
vrp_visit_assignment (tree stmt, tree *output_p)
{
tree lhs, rhs, def;
ssa_op_iter iter;
lhs = TREE_OPERAND (stmt, 0);
rhs = TREE_OPERAND (stmt, 1);
if (TREE_CODE (lhs) == SSA_NAME
&& ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
&& TYPE_MIN_VALUE (TREE_TYPE (lhs))
&& TYPE_MAX_VALUE (TREE_TYPE (lhs)))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
struct loop *l;
value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
extract_range_from_expr (&new_vr, rhs);
if (current_loops && (l = loop_containing_stmt (stmt)))
adjust_range_with_scev (&new_vr, l, stmt, lhs);
if (update_value_range (lhs, &new_vr))
{
*output_p = lhs;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found new range for ");
print_generic_expr (dump_file, lhs, 0);
fprintf (dump_file, ": ");
dump_value_range (dump_file, &new_vr);
fprintf (dump_file, "\n\n");
}
if (new_vr.type == VR_VARYING)
return SSA_PROP_VARYING;
return SSA_PROP_INTERESTING;
}
return SSA_PROP_NOT_INTERESTING;
}
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
set_value_range_to_varying (get_value_range (def));
return SSA_PROP_VARYING;
}
static tree
compare_name_with_value (enum tree_code comp, tree var, tree val,
bool *strict_overflow_p)
{
bitmap_iterator bi;
unsigned i;
bitmap e;
tree retval, t;
int used_strict_overflow;
t = retval = NULL_TREE;
e = get_value_range (var)->equiv;
bitmap_set_bit (e, SSA_NAME_VERSION (var));
used_strict_overflow = -1;
EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
{
bool sop;
value_range_t equiv_vr = *(vr_value[i]);
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);
}
sop = false;
t = compare_range_with_value (comp, &equiv_vr, val, &sop);
if (t)
{
if (retval != NULL
&& t != retval)
{
retval = NULL_TREE;
break;
}
retval = t;
if (!sop)
used_strict_overflow = 0;
else if (used_strict_overflow < 0)
used_strict_overflow = 1;
}
}
bitmap_clear_bit (e, SSA_NAME_VERSION (var));
if (retval)
{
if (used_strict_overflow > 0)
*strict_overflow_p = true;
return retval;
}
return NULL_TREE;
}
static tree
compare_names (enum tree_code comp, tree n1, tree n2,
bool *strict_overflow_p)
{
tree t, retval;
bitmap e1, e2;
bitmap_iterator bi1, bi2;
unsigned i1, i2;
int used_strict_overflow;
e1 = get_value_range (n1)->equiv;
e2 = get_value_range (n2)->equiv;
bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
if (bitmap_intersect_p (e1, e2))
{
bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
? boolean_true_node
: boolean_false_node;
}
used_strict_overflow = -1;
EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
{
value_range_t vr1 = *(vr_value[i1]);
if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
{
vr1.type = VR_RANGE;
vr1.min = ssa_name (i1);
vr1.max = ssa_name (i1);
}
t = retval = NULL_TREE;
EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
{
bool sop = false;
value_range_t vr2 = *(vr_value[i2]);
if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
{
vr2.type = VR_RANGE;
vr2.min = ssa_name (i2);
vr2.max = ssa_name (i2);
}
t = compare_ranges (comp, &vr1, &vr2, &sop);
if (t)
{
if (retval != NULL
&& t != retval)
{
bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
return NULL_TREE;
}
retval = t;
if (!sop)
used_strict_overflow = 0;
else if (used_strict_overflow < 0)
used_strict_overflow = 1;
}
}
if (retval)
{
bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
if (used_strict_overflow > 0)
*strict_overflow_p = true;
return retval;
}
}
bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
return NULL_TREE;
}
static tree
vrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p,
bool *strict_overflow_p)
{
gcc_assert (TREE_CODE (cond) == SSA_NAME
|| TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
if (TREE_CODE (cond) == SSA_NAME)
{
value_range_t *vr;
tree retval;
if (use_equiv_p)
retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node,
strict_overflow_p);
else
{
value_range_t *vr = get_value_range (cond);
retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node,
strict_overflow_p);
}
if (retval)
return retval;
vr = get_value_range (cond);
if (vr->type == VR_RANGE && vr->min == vr->max)
return vr->min;
}
else
{
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& !POINTER_TYPE_P (TREE_TYPE (op0)))
return NULL_TREE;
if (use_equiv_p)
{
if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
return compare_names (TREE_CODE (cond), op0, op1,
strict_overflow_p);
else if (TREE_CODE (op0) == SSA_NAME)
return compare_name_with_value (TREE_CODE (cond), op0, op1,
strict_overflow_p);
else if (TREE_CODE (op1) == SSA_NAME)
return (compare_name_with_value
(swap_tree_comparison (TREE_CODE (cond)), op1, op0,
strict_overflow_p));
}
else
{
value_range_t *vr0, *vr1;
vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
if (vr0 && vr1)
return compare_ranges (TREE_CODE (cond), vr0, vr1,
strict_overflow_p);
else if (vr0 && vr1 == NULL)
return compare_range_with_value (TREE_CODE (cond), vr0, op1,
strict_overflow_p);
else if (vr0 == NULL && vr1)
return (compare_range_with_value
(swap_tree_comparison (TREE_CODE (cond)), vr1, op0,
strict_overflow_p));
}
}
return NULL_TREE;
}
tree
vrp_evaluate_conditional (tree cond, tree stmt)
{
bool sop;
tree ret;
sop = false;
ret = vrp_evaluate_conditional_warnv (cond, true, &sop);
if (ret && sop)
{
enum warn_strict_overflow_code wc;
const char* warnmsg;
if (is_gimple_min_invariant (ret))
{
wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
warnmsg = G_("assuming signed overflow does not occur when "
"simplifying conditional to constant");
}
else
{
wc = WARN_STRICT_OVERFLOW_COMPARISON;
warnmsg = G_("assuming signed overflow does not occur when "
"simplifying conditional");
}
if (issue_strict_overflow_warning (wc))
{
location_t locus;
if (!EXPR_HAS_LOCATION (stmt))
locus = input_location;
else
locus = EXPR_LOCATION (stmt);
warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg);
}
}
return ret;
}
static enum ssa_prop_result
vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
tree cond, val;
bool sop;
*taken_edge_p = NULL;
if (TREE_CODE (stmt) == SWITCH_EXPR)
return SSA_PROP_VARYING;
cond = COND_EXPR_COND (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
tree use;
ssa_op_iter i;
fprintf (dump_file, "\nVisiting conditional with predicate: ");
print_generic_expr (dump_file, cond, 0);
fprintf (dump_file, "\nWith known ranges\n");
FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
{
fprintf (dump_file, "\t");
print_generic_expr (dump_file, use, 0);
fprintf (dump_file, ": ");
dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
}
fprintf (dump_file, "\n");
}
sop = false;
val = vrp_evaluate_conditional_warnv (cond, false, &sop);
if (val)
{
if (!sop)
*taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"\nIgnoring predicate evaluation because "
"it assumes that signed overflow is undefined");
val = NULL_TREE;
}
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nPredicate evaluates to: ");
if (val == NULL_TREE)
fprintf (dump_file, "DON'T KNOW\n");
else
print_generic_stmt (dump_file, val, 0);
}
return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
}
static enum ssa_prop_result
vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
stmt_ann_t ann;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting statement:\n");
print_generic_stmt (dump_file, stmt, dump_flags);
fprintf (dump_file, "\n");
}
ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree rhs = TREE_OPERAND (stmt, 1);
if ((TREE_CODE (rhs) == CALL_EXPR
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
&& DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
&& DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 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);
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
set_value_range_to_varying (get_value_range (def));
return SSA_PROP_VARYING;
}
static void
vrp_meet (value_range_t *vr0, value_range_t *vr1)
{
if (vr0->type == VR_UNDEFINED)
{
copy_value_range (vr0, vr1);
return;
}
if (vr1->type == VR_UNDEFINED)
{
return;
}
if (vr0->type == VR_VARYING)
{
return;
}
if (vr1->type == VR_VARYING)
{
set_value_range_to_varying (vr0);
return;
}
if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
{
if (value_ranges_intersect_p (vr0, vr1))
{
int cmp;
tree min, max;
cmp = compare_values (vr0->min, vr1->min);
if (cmp == 0 || cmp == 1)
min = vr1->min;
else if (cmp == -1)
min = vr0->min;
else
{
set_value_range_to_varying (vr0);
return;
}
cmp = compare_values (vr0->max, vr1->max);
if (cmp == 0 || cmp == -1)
max = vr1->max;
else if (cmp == 1)
max = vr0->max;
else
{
set_value_range_to_varying (vr0);
return;
}
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))))
{
set_value_range_to_varying (vr0);
return;
}
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
bitmap_and_into (vr0->equiv, vr1->equiv);
else if (vr0->equiv && !vr1->equiv)
bitmap_clear (vr0->equiv);
set_value_range (vr0, vr0->type, min, max, vr0->equiv);
}
else
goto no_meet;
}
else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
{
if (compare_values (vr0->min, vr1->min) == 0
&& compare_values (vr0->max, vr1->max) == 0
&& compare_values (vr0->min, vr0->max) == 0)
{
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
bitmap_and_into (vr0->equiv, vr1->equiv);
else if (vr0->equiv && !vr1->equiv)
bitmap_clear (vr0->equiv);
}
else
goto no_meet;
}
else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
if (!symbolic_range_p (vr0)
&& !symbolic_range_p (vr1)
&& !value_ranges_intersect_p (vr0, vr1))
{
if (vr1->type == VR_ANTI_RANGE)
set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
bitmap_and_into (vr0->equiv, vr1->equiv);
else if (vr0->equiv && !vr1->equiv)
bitmap_clear (vr0->equiv);
}
else
goto no_meet;
}
else
gcc_unreachable ();
return;
no_meet:
if (!symbolic_range_p (vr0)
&& ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
|| (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
&& !symbolic_range_p (vr1)
&& ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
|| (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
{
set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
if (vr0->equiv)
bitmap_clear (vr0->equiv);
}
else
set_value_range_to_varying (vr0);
}
static enum ssa_prop_result
vrp_visit_phi_node (tree phi)
{
int i;
tree lhs = PHI_RESULT (phi);
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
copy_value_range (&vr_result, lhs_vr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
print_generic_expr (dump_file, phi, dump_flags);
}
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
edge e = PHI_ARG_EDGE (phi, i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"\n Argument #%d (%d -> %d %sexecutable)\n",
i, e->src->index, e->dest->index,
(e->flags & EDGE_EXECUTABLE) ? "" : "not ");
}
if (e->flags & EDGE_EXECUTABLE)
{
tree arg = PHI_ARG_DEF (phi, i);
value_range_t vr_arg;
if (TREE_CODE (arg) == SSA_NAME)
vr_arg = *(get_value_range (arg));
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;
vr_arg.equiv = NULL;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\t");
print_generic_expr (dump_file, arg, dump_flags);
fprintf (dump_file, "\n\tValue: ");
dump_value_range (dump_file, &vr_arg);
fprintf (dump_file, "\n");
}
vrp_meet (&vr_result, &vr_arg);
if (vr_result.type == VR_VARYING)
break;
}
}
if (vr_result.type == VR_VARYING)
goto varying;
if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
{
if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
{
int cmp_min = compare_values (lhs_vr->min, vr_result.min);
int cmp_max = compare_values (lhs_vr->max, vr_result.max);
if (cmp_min > 0 || cmp_min < 0)
{
if (vrp_val_is_max (vr_result.max))
goto varying;
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 =
negative_overflow_infinity (TREE_TYPE (vr_result.min));
else
goto varying;
}
if (cmp_max < 0 || cmp_max > 0)
{
if (vrp_val_is_min (vr_result.min))
goto varying;
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 =
positive_overflow_infinity (TREE_TYPE (vr_result.max));
else
goto varying;
}
}
}
if (update_value_range (lhs, &vr_result))
return SSA_PROP_INTERESTING;
return SSA_PROP_NOT_INTERESTING;
varying:
set_value_range_to_varying (lhs_vr);
return SSA_PROP_VARYING;
}
static void
simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
{
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
{
bool sop = false;
val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop);
if (val
&& sop
&& integer_onep (val)
&& issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
{
location_t locus;
if (!EXPR_HAS_LOCATION (stmt))
locus = input_location;
else
locus = EXPR_LOCATION (stmt);
warning (OPT_Wstrict_overflow,
("%Hassuming signed overflow does not occur when "
"simplifying / or %% to >> or &"),
&locus);
}
}
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 = build2 (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);
}
}
static void
simplify_abs_using_ranges (tree stmt, tree rhs)
{
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)
{
bool sop = false;
val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
if (!val)
{
sop = false;
val = compare_range_with_value (GE_EXPR, vr, integer_zero_node,
&sop);
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 (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
{
location_t locus;
if (!EXPR_HAS_LOCATION (stmt))
locus = input_location;
else
locus = EXPR_LOCATION (stmt);
warning (OPT_Wstrict_overflow,
("%Hassuming signed overflow does not occur when "
"simplifying abs (X) to X or -X"),
&locus);
}
if (integer_onep (val))
t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
else
t = op;
TREE_OPERAND (stmt, 1) = t;
update_stmt (stmt);
}
}
}
static tree
test_for_singularity (enum tree_code cond_code, tree op0,
tree op1, value_range_t *vr)
{
tree min = NULL;
tree max = NULL;
if (cond_code == LE_EXPR || cond_code == LT_EXPR)
{
min = TYPE_MIN_VALUE (TREE_TYPE (op0));
max = op1;
if (cond_code == LT_EXPR && !is_overflow_infinity (max))
{
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)
{
max = TYPE_MAX_VALUE (TREE_TYPE (op0));
min = op1;
if (cond_code == GT_EXPR && !is_overflow_infinity (min))
{
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;
}
}
if (min && max)
{
if (compare_values (vr->min, min) == -1)
min = min;
else
min = vr->min;
if (compare_values (vr->max, max) == 1)
max = max;
else
max = vr->max;
if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
return min;
}
return NULL;
}
static void
simplify_cond_using_ranges (tree stmt)
{
tree cond = COND_EXPR_COND (stmt);
tree op0 = TREE_OPERAND (cond, 0);
tree op1 = TREE_OPERAND (cond, 1);
enum tree_code cond_code = TREE_CODE (cond);
if (cond_code != NE_EXPR
&& cond_code != EQ_EXPR
&& TREE_CODE (op0) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& is_gimple_min_invariant (op1))
{
value_range_t *vr = get_value_range (op0);
if (vr->type == VR_RANGE)
{
tree new = test_for_singularity (cond_code, op0, op1, vr);
if (new)
{
if (dump_file)
{
fprintf (dump_file, "Simplified relational ");
print_generic_expr (dump_file, cond, 0);
fprintf (dump_file, " into ");
}
COND_EXPR_COND (stmt)
= build2 (EQ_EXPR, boolean_type_node, op0, new);
update_stmt (stmt);
if (dump_file)
{
print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
fprintf (dump_file, "\n");
}
return;
}
cond_code = invert_tree_comparison (cond_code, false);
new = test_for_singularity (cond_code, op0, op1, vr);
if (new)
{
if (dump_file)
{
fprintf (dump_file, "Simplified relational ");
print_generic_expr (dump_file, cond, 0);
fprintf (dump_file, " into ");
}
COND_EXPR_COND (stmt)
= build2 (NE_EXPR, boolean_type_node, op0, new);
update_stmt (stmt);
if (dump_file)
{
print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
fprintf (dump_file, "\n");
}
return;
}
}
}
}
void
simplify_stmt_using_ranges (tree stmt)
{
if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree rhs = TREE_OPERAND (stmt, 1);
enum tree_code rhs_code = TREE_CODE (rhs);
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)))
simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
if (rhs_code == ABS_EXPR
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
simplify_abs_using_ranges (stmt, rhs);
}
else if (TREE_CODE (stmt) == COND_EXPR
&& COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
{
simplify_cond_using_ranges (stmt);
}
}
static VEC(tree,heap) *stack;
static tree
simplify_stmt_for_jump_threading (tree stmt, tree within_stmt)
{
if (TREE_CODE (stmt) != COND_EXPR)
return NULL;
return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt);
}
static void
identify_jump_threads (void)
{
basic_block bb;
tree dummy;
calculate_dominance_info (CDI_DOMINATORS);
mark_dfs_back_edges ();
stack = VEC_alloc (tree, heap, 20);
dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
FOR_EACH_BB (bb)
{
tree last, cond;
if (! potentially_threadable_block (bb))
continue;
last = bsi_stmt (bsi_last (bb));
if (TREE_CODE (last) != COND_EXPR)
continue;
cond = COND_EXPR_COND (last);
if ((TREE_CODE (cond) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (cond)))
|| (COMPARISON_CLASS_P (cond)
&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
&& (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
|| is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
continue;
thread_across_edge (dummy, e, true,
&stack,
simplify_stmt_for_jump_threading);
}
}
}
}
static void
finalize_jump_threads (void)
{
bool cfg_altered = false;
cfg_altered = thread_through_all_blocks ();
if (cfg_altered)
{
free_dominance_info (CDI_DOMINATORS);
cleanup_tree_cfg ();
calculate_dominance_info (CDI_DOMINATORS);
}
VEC_free (tree, heap, stack);
}
static void
vrp_finalize (void)
{
size_t i;
prop_value_t *single_val_range;
bool do_value_subst_p;
if (dump_file)
{
fprintf (dump_file, "\nValue ranges after VRP:\n\n");
dump_all_value_ranges (dump_file);
fprintf (dump_file, "\n");
}
single_val_range = XNEWVEC (prop_value_t, num_ssa_names);
memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
do_value_subst_p = false;
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i]
&& vr_value[i]->type == VR_RANGE
&& vr_value[i]->min == vr_value[i]->max)
{
single_val_range[i].value = vr_value[i]->min;
do_value_subst_p = true;
}
if (!do_value_subst_p)
{
free (single_val_range);
single_val_range = NULL;
}
substitute_and_fold (single_val_range, true);
identify_jump_threads ();
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i])
{
BITMAP_FREE (vr_value[i]->equiv);
free (vr_value[i]);
}
free (single_val_range);
free (vr_value);
vr_value = NULL;
}
static unsigned int
execute_vrp (void)
{
insert_range_assertions ();
current_loops = loop_optimizer_init (LOOPS_NORMAL);
if (current_loops)
scev_initialize (current_loops);
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize ();
if (current_loops)
{
scev_finalize ();
loop_optimizer_finalize (current_loops);
current_loops = NULL;
}
remove_range_assertions ();
update_ssa (TODO_update_ssa);
finalize_jump_threads ();
return 0;
}
static bool
gate_vrp (void)
{
return flag_tree_vrp != 0;
}
struct tree_opt_pass pass_vrp =
{
"vrp",
gate_vrp,
execute_vrp,
NULL,
NULL,
0,
TV_TREE_VRP,
PROP_ssa | PROP_alias,
0,
PROP_smt_usage,
0,
TODO_cleanup_cfg
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_dump_func
| TODO_update_ssa
| TODO_update_smt_usage,
0
};