diff options
Diffstat (limited to 'gcc/tree-vrp.c')
| -rw-r--r-- | gcc/tree-vrp.c | 5530 |
1 files changed, 5530 insertions, 0 deletions
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c new file mode 100644 index 0000000..4626485 --- /dev/null +++ b/gcc/tree-vrp.c @@ -0,0 +1,5530 @@ +/* Support routines for Value Range Propagation (VRP). + Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. + Contributed by Diego Novillo <dnovillo@redhat.com>. + +This file is part of GCC. + +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) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +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. */ + +#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" + +/* Set of SSA names found during the dominator traversal of a + sub-graph in find_assert_locations. */ +static sbitmap found_in_subgraph; + +/* Local functions. */ +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 *); + +/* Location information for ASSERT_EXPRs. Each instance of this + structure describes an ASSERT_EXPR for an SSA name. Since a single + SSA name may have more than one assertion associated with it, these + locations are kept in a linked list attached to the corresponding + SSA name. */ +struct assert_locus_d +{ + /* Basic block where the assertion would be inserted. */ + basic_block bb; + + /* Some assertions need to be inserted on an edge (e.g., assertions + generated by COND_EXPRs). In those cases, BB will be NULL. */ + edge e; + + /* Pointer to the statement that generated this assertion. */ + block_stmt_iterator si; + + /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */ + enum tree_code comp_code; + + /* Value being compared against. */ + tree val; + + /* Next node in the linked list. */ + struct assert_locus_d *next; +}; + +typedef struct assert_locus_d *assert_locus_t; + +/* If bit I is present, it means that SSA name N_i has a list of + assertions that should be inserted in the IL. */ +static bitmap need_assert_for; + +/* Array of locations lists where to insert assertions. ASSERTS_FOR[I] + holds a list of ASSERT_LOCUS_T nodes that describe where + ASSERT_EXPRs for SSA name N_I should be inserted. */ +static assert_locus_t *asserts_for; + +/* Set of blocks visited in find_assert_locations. Used to avoid + visiting the same block more than once. */ +static sbitmap blocks_visited; + +/* Value range array. After propagation, VR_VALUE[I] holds the range + of values that SSA name N_I may take. */ +static value_range_t **vr_value; + + +/* Return whether TYPE should use an overflow infinity distinct from + TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to + represent a signed overflow during VRP computations. An infinity + is distinct from a half-range, which will go from some number to + TYPE_{MIN,MAX}_VALUE. */ + +static inline bool +needs_overflow_infinity (tree type) +{ + return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); +} + +/* Return whether TYPE can support our overflow infinity + representation: we use the TREE_OVERFLOW flag, which only exists + for constants. If TYPE doesn't support this, we don't optimize + cases which would require signed overflow--we drop them to + VARYING. */ + +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))); +} + +/* VAL is the maximum or minimum value of a type. Return a + corresponding overflow infinity. */ + +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; +} + +/* Return a negative overflow infinity for TYPE. */ + +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)); +} + +/* Return a positive overflow infinity for 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)); +} + +/* Return whether VAL is a negative overflow infinity. */ + +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)); +} + +/* Return whether VAL is a positive overflow infinity. */ + +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)); +} + +/* Return whether VAL is a positive or negative overflow infinity. */ + +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))); +} + +/* If VAL is now an overflow infinity, return VAL. Otherwise, return + the same value with TREE_OVERFLOW clear. This can be used to avoid + confusing a regular value with an overflow value. */ + +static inline tree +avoid_overflow_infinity (tree val) +{ + if (!is_overflow_infinity (val)) + return val; + + if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)) + return TYPE_MAX_VALUE (TREE_TYPE (val)); + else + { +#ifdef ENABLE_CHECKING + gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); +#endif + return TYPE_MIN_VALUE (TREE_TYPE (val)); + } +} + + +/* Return whether VAL is equal to the maximum value of its type. This + will be true for a positive overflow infinity. We can't do a + simple equality comparison with TYPE_MAX_VALUE because C typedefs + and Ada subtypes can produce types whose TYPE_MAX_VALUE is not == + to the integer constant with the same value in the type. */ + +static inline bool +vrp_val_is_max (tree val) +{ + tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val)); + + return (val == type_max + || (type_max != NULL_TREE + && operand_equal_p (val, type_max, 0))); +} + +/* Return whether VAL is equal to the minimum value of its type. This + will be true for a negative overflow infinity. */ + +static inline bool +vrp_val_is_min (tree val) +{ + tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val)); + + return (val == type_min + || (type_min != NULL_TREE + && operand_equal_p (val, type_min, 0))); +} + + +/* Return true if ARG is marked with the nonnull attribute in the + current function signature. */ + +static bool +nonnull_arg_p (tree arg) +{ + tree t, attrs, fntype; + unsigned HOST_WIDE_INT arg_num; + + gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg))); + + /* The static chain decl is always non null. */ + if (arg == cfun->static_chain_decl) + return true; + + fntype = TREE_TYPE (current_function_decl); + attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype)); + + /* If "nonnull" wasn't specified, we know nothing about the argument. */ + if (attrs == NULL_TREE) + return false; + + /* If "nonnull" applies to all the arguments, then ARG is non-null. */ + if (TREE_VALUE (attrs) == NULL_TREE) + return true; + + /* Get the position number for ARG in the function signature. */ + for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); + t; + t = TREE_CHAIN (t), arg_num++) + { + if (t == arg) + break; + } + + gcc_assert (t == arg); + + /* Now see if ARG_NUM is mentioned in the nonnull list. */ + for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) + { + if (compare_tree_int (TREE_VALUE (t), arg_num) == 0) + return true; + } + + return false; +} + + +/* Set value range VR to {T, MIN, MAX, EQUIV}. */ + +static void +set_value_range (value_range_t *vr, enum value_range_type t, tree min, + tree max, bitmap equiv) +{ +#if defined ENABLE_CHECKING + /* Check the validity of the range. */ + 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; + + /* Since updating the equivalence set involves deep copying the + bitmaps, only do it if absolutely necessary. */ + 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); + } +} + + +/* Copy value range FROM into value range TO. */ + +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); +} + + +/* Set value range VR to VR_VARYING. */ + +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); +} + +/* Set value range VR to a single value. This function is only called + with values we get from statements, and exists to clear the + TREE_OVERFLOW flag so that we don't think we have an overflow + infinity when we shouldn't. */ + +static inline void +set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) +{ + gcc_assert (is_gimple_min_invariant (val)); + val = avoid_overflow_infinity (val); + set_value_range (vr, VR_RANGE, val, val, equiv); +} + +/* Set value range VR to a non-negative range of type TYPE. + OVERFLOW_INFINITY indicates whether to use a overflow infinity + rather than TYPE_MAX_VALUE; this should be true if we determine + that the range is nonnegative based on the assumption that signed + overflow does not occur. */ + +static inline void +set_value_range_to_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); +} + +/* Set value range VR to a non-NULL range of type TYPE. */ + +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); +} + + +/* Set value range VR to a NULL range of type TYPE. */ + +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); +} + + +/* Set value range VR to VR_UNDEFINED. */ + +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); +} + + +/* Return value range information for VAR. + + If we have no values ranges recorded (ie, VRP is not running), then + return NULL. Otherwise create an empty range if none existed for VAR. */ + +static value_range_t * +get_value_range (tree var) +{ + value_range_t *vr; + tree sym; + unsigned ver = SSA_NAME_VERSION (var); + + /* If we have no recorded ranges, then return NULL. */ + if (! vr_value) + return NULL; + + vr = vr_value[ver]; + if (vr) + return vr; + + /* Create a default value range. */ + vr_value[ver] = vr = XNEW (value_range_t); + memset (vr, 0, sizeof (*vr)); + + /* Allocate an equivalence set. */ + vr->equiv = BITMAP_ALLOC (NULL); + + /* If VAR is a default definition, the variable can take any value + in VAR's type. */ + sym = SSA_NAME_VAR (var); + if (var == default_def (sym)) + { + /* Try to use the "nonnull" attribute to create ~[0, 0] + anti-ranges for pointers. Note that this is only valid with + default definitions of PARM_DECLs. */ + if (TREE_CODE (sym) == PARM_DECL + && POINTER_TYPE_P (TREE_TYPE (sym)) + && nonnull_arg_p (sym)) + set_value_range_to_nonnull (vr, TREE_TYPE (sym)); + else + set_value_range_to_varying (vr); + } + + return vr; +} + +/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ + +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; +} + +/* Return true, if the bitmaps B1 and B2 are equal. */ + +static inline bool +vrp_bitmap_equal_p (bitmap b1, bitmap b2) +{ + return (b1 == b2 + || (b1 && b2 + && bitmap_equal_p (b1, b2))); +} + +/* Update the value range and equivalence set for variable VAR to + NEW_VR. Return true if NEW_VR is different from VAR's previous + value. + + NOTE: This function assumes that NEW_VR is a temporary value range + object created for the sole purpose of updating VAR's range. The + storage used by the equivalence set from NEW_VR will be freed by + this function. Do not call update_value_range when NEW_VR + is the range object associated with another SSA name. */ + +static inline bool +update_value_range (tree var, value_range_t *new_vr) +{ + value_range_t *old_vr; + bool is_new; + + /* Update the value range, if necessary. */ + 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; +} + + +/* Add VAR and VAR's equivalence set to EQUIV. */ + +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); +} + + +/* Return true if VR is ~[0, 0]. */ + +static inline bool +range_is_nonnull (value_range_t *vr) +{ + return vr->type == VR_ANTI_RANGE + && integer_zerop (vr->min) + && integer_zerop (vr->max); +} + + +/* Return true if VR is [0, 0]. */ + +static inline bool +range_is_null (value_range_t *vr) +{ + return vr->type == VR_RANGE + && integer_zerop (vr->min) + && integer_zerop (vr->max); +} + + +/* Return true if value range VR involves at least one symbol. */ + +static inline bool +symbolic_range_p (value_range_t *vr) +{ + return (!is_gimple_min_invariant (vr->min) + || !is_gimple_min_invariant (vr->max)); +} + +/* Return true if value range VR uses a overflow infinity. */ + +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))); +} + +/* Return false if we can not make a valid comparison based on VR; + this will be the case if it uses an overflow infinity and overflow + is not undefined (i.e., -fno-strict-overflow is in effect). + Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR + uses an overflow infinity. */ + +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; +} + + +/* Like tree_expr_nonnegative_warnv_p, but this function uses value + ranges obtained so far. */ + +static bool +vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p) +{ + return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p); +} + +/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges + obtained so far. */ + +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 we have an expression of the form &X->a, then the expression + is nonnull if X is nonnull. */ + 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; +} + +/* Returns true if EXPR is a valid value (as expected by compare_values) -- + a gimple invariant, or SSA_NAME +- CST. */ + +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); +} + +/* Compare two values VAL1 and VAL2. Return + + -2 if VAL1 and VAL2 cannot be compared at compile-time, + -1 if VAL1 < VAL2, + 0 if VAL1 == VAL2, + +1 if VAL1 > VAL2, and + +2 if VAL1 != VAL2 + + This is similar to tree_int_cst_compare but supports pointer values + and values that cannot be compared at compile time. + + If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to + true if the return value is only valid if we assume that signed + overflow is undefined. */ + +static int +compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) +{ + if (val1 == val2) + return 0; + + /* Below we rely on the fact that VAL1 and VAL2 are both pointers or + both integers. */ + 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 VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', + return -1 or +1 accordingly. If VAL1 and VAL2 don't use the + same name, return -2. */ + 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; + } + } + + /* Both values must use the same name. */ + if (n1 != n2) + return -2; + + if (code1 == SSA_NAME + && code2 == SSA_NAME) + /* NAME == NAME */ + return 0; + + /* If overflow is defined we cannot simplify more. */ + 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) + /* NAME < NAME + CST */ + return -1; + else if (code2 == MINUS_EXPR) + /* NAME > NAME - CST */ + return 1; + } + else if (code1 == PLUS_EXPR) + { + if (code2 == SSA_NAME) + /* NAME + CST > NAME */ + return 1; + else if (code2 == PLUS_EXPR) + /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ + return compare_values_warnv (c1, c2, strict_overflow_p); + else if (code2 == MINUS_EXPR) + /* NAME + CST1 > NAME - CST2 */ + return 1; + } + else if (code1 == MINUS_EXPR) + { + if (code2 == SSA_NAME) + /* NAME - CST < NAME */ + return -1; + else if (code2 == PLUS_EXPR) + /* NAME - CST1 < NAME + CST2 */ + return -1; + else if (code2 == MINUS_EXPR) + /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that + C1 and C2 are swapped in the call to compare_values. */ + return compare_values_warnv (c2, c1, strict_overflow_p); + } + + gcc_unreachable (); + } + + /* We cannot compare non-constants. */ + if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)) + return -2; + + if (!POINTER_TYPE_P (TREE_TYPE (val1))) + { + /* We cannot compare overflowed values, except for overflow + infinities. */ + 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; + + /* First see if VAL1 and VAL2 are not the same. */ + if (val1 == val2 || operand_equal_p (val1, val2, 0)) + return 0; + + /* If VAL1 is a lower address than VAL2, return -1. */ + t = fold_binary (LT_EXPR, boolean_type_node, val1, val2); + if (t == boolean_true_node) + return -1; + + /* If VAL1 is a higher address than VAL2, return +1. */ + t = fold_binary (GT_EXPR, boolean_type_node, val1, val2); + if (t == boolean_true_node) + return 1; + + /* If VAL1 is different than VAL2, return +2. */ + t = fold_binary (NE_EXPR, boolean_type_node, val1, val2); + if (t == boolean_true_node) + return 2; + + return -2; + } +} + +/* Compare values like compare_values_warnv, but treat comparisons of + nonconstants which rely on undefined overflow as incomparable. */ + +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; +} + + +/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), + 0 if VAL is not inside VR, + -2 if we cannot tell either way. + + FIXME, the current semantics of this functions are a bit quirky + when taken in the context of VRP. In here we do not care + about VR's type. If VR is the anti-range ~[3, 5] the call + value_inside_range (4, VR) will return 1. + + This is counter-intuitive in a strict sense, but the callers + currently expect this. They are calling the function + merely to determine whether VR->MIN <= VAL <= VR->MAX. The + callers are applying the VR_RANGE/VR_ANTI_RANGE semantics + themselves. + + This also applies to value_ranges_intersect_p and + range_includes_zero_p. The semantics of VR_RANGE and + VR_ANTI_RANGE should be encoded here, but that also means + adapting the users of these functions to the new semantics. */ + +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; + + return cmp1 == boolean_true_node && cmp2 == boolean_true_node; +} + + +/* Return true if value ranges VR0 and VR1 have a non-empty + intersection. */ + +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); +} + + +/* Return true if VR includes the value zero, false otherwise. FIXME, + currently this will return false for an anti-range like ~[-4, 3]. + This will be wrong when the semantics of value_inside_range are + modified (currently the users of this function expect these + semantics). */ + +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); + return (value_inside_range (zero, vr) == 1); +} + +/* Return true if T, an SSA_NAME, is known to be nonnegative. Return + false otherwise or if no value range information is available. */ + +bool +ssa_name_nonnegative_p (tree t) +{ + value_range_t *vr = get_value_range (t); + + if (!vr) + return false; + + /* Testing for VR_ANTI_RANGE is not useful here as any anti-range + which would return a useful value should be encoded as a VR_RANGE. */ + if (vr->type == VR_RANGE) + { + int result = compare_values (vr->min, integer_zero_node); + + return (result == 0 || result == 1); + } + return false; +} + +/* Return true if T, an SSA_NAME, is known to be nonzero. Return + false otherwise or if no value range information is available. */ + +bool +ssa_name_nonzero_p (tree t) +{ + value_range_t *vr = get_value_range (t); + + if (!vr) + return false; + + /* A VR_RANGE which does not include zero is a nonzero value. */ + if (vr->type == VR_RANGE && !symbolic_range_p (vr)) + return ! range_includes_zero_p (vr); + + /* A VR_ANTI_RANGE which does include zero is a nonzero value. */ + if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr)) + return range_includes_zero_p (vr); + + return false; +} + + +/* Extract value range information from an ASSERT_EXPR EXPR and store + it in *VR_P. */ + +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)); + + /* Find VAR in the ASSERT_EXPR conditional. */ + if (var == TREE_OPERAND (cond, 0)) + { + /* If the predicate is of the form VAR COMP LIMIT, then we just + take LIMIT from the RHS and use the same comparison code. */ + limit = TREE_OPERAND (cond, 1); + cond_code = TREE_CODE (cond); + } + else + { + /* If the predicate is of the form LIMIT COMP VAR, then we need + to flip around the comparison code to create the proper range + for VAR. */ + 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); + + /* For pointer arithmetic, we only keep track of pointer equality + and inequality. */ + if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) + { + set_value_range_to_varying (vr_p); + return; + } + + /* If LIMIT is another SSA name and LIMIT has a range of its own, + try to use LIMIT's range to avoid creating symbolic ranges + unnecessarily. */ + limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; + + /* LIMIT's range is only interesting if it has any useful information. */ + if (limit_vr + && (limit_vr->type == VR_UNDEFINED + || limit_vr->type == VR_VARYING + || symbolic_range_p (limit_vr))) + limit_vr = NULL; + + /* Initially, the new range has the same set of equivalences of + VAR's range. This will be revised before returning the final + value. Since assertions may be chained via mutually exclusive + predicates, we will need to trim the set of equivalences before + we are done. */ + gcc_assert (vr_p->equiv == NULL); + vr_p->equiv = BITMAP_ALLOC (NULL); + add_equivalence (vr_p->equiv, var); + + /* Extract a new range based on the asserted comparison for VAR and + LIMIT's value range. Notice that if LIMIT has an anti-range, we + will only use it for equality comparisons (EQ_EXPR). For any + other kind of assertion, we cannot derive a range from LIMIT's + anti-range that can be used to describe the new range. For + instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], + then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is + no single range for x_2 that could describe LE_EXPR, so we might + as well build the range [b_4, +INF] for it. */ + 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); + + /* When asserting the equality VAR == LIMIT and LIMIT is another + SSA name, the new range will also inherit the equivalence set + from LIMIT. */ + if (TREE_CODE (limit) == SSA_NAME) + add_equivalence (vr_p->equiv, limit); + } + else if (cond_code == NE_EXPR) + { + /* As described above, when LIMIT's range is an anti-range and + this assertion is an inequality (NE_EXPR), then we cannot + derive anything from the anti-range. For instance, if + LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does + not imply that VAR's range is [0, 0]. So, in the case of + anti-ranges, we just assert the inequality using LIMIT and + not its anti-range. + + If LIMIT_VR is a range, we can only use it to build a new + anti-range if LIMIT_VR is a single-valued range. For + instance, if LIMIT_VR is [0, 1], the predicate + VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. + Rather, it means that for value 0 VAR should be ~[0, 0] + and for value 1, VAR should be ~[1, 1]. We cannot + represent these ranges. + + The only situation in which we can build a valid + anti-range is when LIMIT_VR is a single-valued range + (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, + build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ + 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 + { + /* In any other case, we cannot use LIMIT's range to build a + valid anti-range. */ + min = max = limit; + } + + /* If MIN and MAX cover the whole range for their type, then + just use the original 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 + { + /* If LIMIT_VR is of the form [N1, N2], we need to build the + range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for + LT_EXPR. */ + max = limit_vr->max; + } + + /* If the maximum value forces us to be out of bounds, simply punt. + It would be pointless to try and do anything more since this + all should be optimized away above us. */ + if ((cond_code == LT_EXPR + && compare_values (max, min) == 0) + || is_overflow_infinity (max)) + set_value_range_to_varying (vr_p); + else + { + /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ + 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 + { + /* If LIMIT_VR is of the form [N1, N2], we need to build the + range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for + GT_EXPR. */ + min = limit_vr->min; + } + + /* If the minimum value forces us to be out of bounds, simply punt. + It would be pointless to try and do anything more since this + all should be optimized away above us. */ + if ((cond_code == GT_EXPR + && compare_values (min, max) == 0) + || is_overflow_infinity (min)) + set_value_range_to_varying (vr_p); + else + { + /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ + 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 (); + + /* If VAR already had a known range, it may happen that the new + range we have computed and VAR's range are not compatible. For + instance, + + if (p_5 == NULL) + p_6 = ASSERT_EXPR <p_5, p_5 == NULL>; + x_7 = p_6->fld; + p_8 = ASSERT_EXPR <p_6, p_6 != NULL>; + + While the above comes from a faulty program, it will cause an ICE + later because p_8 and p_6 will have incompatible ranges and at + the same time will be considered equivalent. A similar situation + would arise from + + if (i_5 > 10) + i_6 = ASSERT_EXPR <i_5, i_5 > 10>; + if (i_5 < 5) + i_7 = ASSERT_EXPR <i_6, i_6 < 5>; + + Again i_6 and i_7 will have incompatible ranges. It would be + pointless to try and do anything with i_7's range because + anything dominated by 'if (i_5 < 5)' will be optimized away. + Note, due to the wa in which simulation proceeds, the statement + i_7 = ASSERT_EXPR <...> we would never be visited because the + conditional 'if (i_5 < 5)' always evaluates to false. However, + this extra check does not hurt and may protect against future + changes to VRP that may get into a situation similar to the + NULL pointer dereference example. + + Note that these compatibility tests are only needed when dealing + with ranges or a mix of range and anti-range. If VAR_VR and VR_P + are both anti-ranges, they will always be compatible, because two + anti-ranges will always have a non-empty intersection. */ + + var_vr = get_value_range (var); + + /* We may need to make adjustments when VR_P and VAR_VR are numeric + ranges or anti-ranges. */ + 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 the two ranges have a non-empty intersection, we can + refine the resulting range. Since the assert expression + creates an equivalency and at the same time it asserts a + predicate, we can take the intersection of the two ranges to + get better precision. */ + if (value_ranges_intersect_p (var_vr, vr_p)) + { + /* Use the larger of the two minimums. */ + if (compare_values (vr_p->min, var_vr->min) == -1) + min = var_vr->min; + else + min = vr_p->min; + + /* Use the smaller of the two maximums. */ + 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 + { + /* The two ranges do not intersect, set the new range to + VARYING, because we will not be able to do anything + meaningful with it. */ + 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)) + { + /* A range and an anti-range will cancel each other only if + their ends are the same. For instance, in the example above, + p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible, + so VR_P should be set to VR_VARYING. */ + 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; + + /* We want to compute the logical AND of the two ranges; + there are three cases to consider. + + + 1. The VR_ANTI_RANGE range is completely within the + VR_RANGE and the endpoints of the ranges are + different. In that case the resulting range + should be whichever range is more precise. + Typically that will be the VR_RANGE. + + 2. The VR_ANTI_RANGE is completely disjoint from + the VR_RANGE. In this case the resulting range + should be the VR_RANGE. + + 3. There is some overlap between the VR_ANTI_RANGE + and the VR_RANGE. + + 3a. If the high limit of the VR_ANTI_RANGE resides + within the VR_RANGE, then the result is a new + VR_RANGE starting at the high limit of the + the VR_ANTI_RANGE + 1 and extending to the + high limit of the original VR_RANGE. + + 3b. If the low limit of the VR_ANTI_RANGE resides + within the VR_RANGE, then the result is a new + VR_RANGE starting at the low limit of the original + VR_RANGE and extending to the low limit of the + VR_ANTI_RANGE - 1. */ + 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; + } + + + /* Case 1, VR_ANTI_RANGE completely within VR_RANGE, + not including any endpoints. */ + 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); + } + /* Case 2, VR_ANTI_RANGE completely disjoint from + VR_RANGE. */ + 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); + } + /* Case 3a, the anti-range extends into the low + part of the real range. Thus creating a new + low for the real range. */ + 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); + } + /* Case 3b, the anti-range extends into the high + part of the real range. Thus creating a new + higher for the real range. */ + 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); + } + } + } +} + + +/* Extract range information from SSA name VAR and store it in VR. If + VAR has an interesting range, use it. Otherwise, create the + range [VAR, VAR] and return it. This is useful in situations where + we may have conditionals testing values of VARYING names. For + instance, + + x_3 = y_5; + if (x_3 > y_5) + ... + + Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is + always false. */ + +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); +} + + +/* Wrapper around int_const_binop. If the operation overflows and we + are not using wrapping arithmetic, then adjust the result to be + -INF or +INF depending on CODE, VAL1 and VAL2. This can return + NULL_TREE if we need to use an overflow infinity representation but + the type does not support it. */ + +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 we are not using wrapping arithmetic, operate symbolically + on -INF and +INF. */ + if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) + { + int checkz = compare_values (res, val1); + bool overflow = false; + + /* Ensure that res = val1 [+*] val2 >= val1 + or that res = val1 - val2 <= val1. */ + if ((code == PLUS_EXPR + && !(checkz == 1 || checkz == 0)) + || (code == MINUS_EXPR + && !(checkz == 0 || checkz == -1))) + { + overflow = true; + } + /* Checking for multiplication overflow is done by dividing the + output of the multiplication by the first input of the + multiplication. If the result of that division operation is + not equal to the second input of the multiplication, then the + multiplication overflowed. */ + 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)) + { + /* If the operation overflowed but neither VAL1 nor VAL2 are + overflown, return -INF or +INF depending on the operation + and the combination of signs of the operands. */ + 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; + + /* We have to punt on adding infinities of different signs, + since we can't tell what the sign of the result should be. + Likewise for subtracting infinities of the same sign. */ + if (((code == PLUS_EXPR && sgn1 != sgn2) + || (code == MINUS_EXPR && sgn1 == sgn2)) + && is_overflow_infinity (val1) + && is_overflow_infinity (val2)) + return NULL_TREE; + + /* Don't try to handle division or shifting of infinities. */ + 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; + + /* Notice that we only need to handle the restricted set of + operations handled by extract_range_from_binary_expr. + Among them, only multiplication, addition and subtraction + can yield overflow without overflown operands because we + are working with integral types only... except in the + case VAL1 = -INF and VAL2 = -1 which overflows to +INF + for division too. */ + + /* For multiplication, the sign of the overflow is given + by the comparison of the signs of the operands. */ + if ((code == MULT_EXPR && sgn1 == sgn2) + /* For addition, the operands must be of the same sign + to yield an overflow. Its sign is therefore that + of one of the operands, for example the first. For + infinite operands X + -INF is negative, not positive. */ + || (code == PLUS_EXPR + && (sgn1 >= 0 + ? !is_negative_overflow_infinity (val2) + : is_positive_overflow_infinity (val2))) + /* For subtraction, non-infinite operands must be of + different signs to yield an overflow. Its sign is + therefore that of the first operand or the opposite of + that of the second operand. A first operand of 0 counts + as positive here, for the corner case 0 - (-INF), which + overflows, but must yield +INF. For infinite operands 0 + - INF is negative, not positive. */ + || (code == MINUS_EXPR + && (sgn1 >= 0 + ? !is_positive_overflow_infinity (val2) + : is_negative_overflow_infinity (val2))) + /* For division, the only case is -INF / -1 = +INF. */ + || code == TRUNC_DIV_EXPR + || code == FLOOR_DIV_EXPR + || code == CEIL_DIV_EXPR + || code == EXACT_DIV_EXPR + || code == ROUND_DIV_EXPR) + return (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; +} + + +/* Extract range information from a binary expression EXPR based on + the ranges of each of its operands and the expression code. */ + +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 }; + + /* Not all binary expressions can be applied to ranges in a + meaningful way. Handle only arithmetic operations. */ + 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; + } + + /* Get value ranges for each operand. For constant operands, create + a new value range with the operand to simplify processing. */ + 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 either range is UNDEFINED, so is the result. */ + if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED) + { + set_value_range_to_undefined (vr); + return; + } + + /* The type of the resulting value range defaults to VR0.TYPE. */ + type = vr0.type; + + /* Refuse to operate on VARYING ranges, ranges of different kinds + and symbolic ranges. As an exception, we allow BIT_AND_EXPR + because we may be able to derive a useful range even if one of + the operands is VR_VARYING or symbolic range. TODO, we may be + able to derive anti-ranges in some cases. */ + 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; + } + + /* Now evaluate the expression to determine the new range. */ + if (POINTER_TYPE_P (TREE_TYPE (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 (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 + { + /* Subtracting from a pointer, may yield 0, so just drop the + resulting range to varying. */ + set_value_range_to_varying (vr); + } + + return; + } + + /* For integer ranges, apply the operation to each end of the + range and see what we end up with. */ + if (code == TRUTH_ANDIF_EXPR + || code == TRUTH_ORIF_EXPR + || code == TRUTH_AND_EXPR + || code == TRUTH_OR_EXPR) + { + /* If one of the operands is zero, we know that the whole + expression evaluates zero. */ + 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); + } + /* If one of the operands is one, we know that the whole + expression evaluates one. */ + 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)) + { + /* Boolean expressions cannot be folded with int_const_binop. */ + 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 we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to + VR_VARYING. It would take more effort to compute a precise + range for such a case. For example, if we have op0 == 1 and + op1 == -1 with their ranges both being ~[0,0], we would have + op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. + Note that we are guaranteed to have vr0.type == vr1.type at + this point. */ + if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) + { + set_value_range_to_varying (vr); + return; + } + + /* For operations that make the resulting range directly + proportional to the original ranges, apply the operation to + the same end of each range. */ + 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 we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, + drop to VR_VARYING. It would take more effort to compute a + precise range for such a case. For example, if we have + op0 == 65536 and op1 == 65536 with their ranges both being + ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so + we cannot claim that the product is in ~[0,0]. Note that we + are guaranteed to have vr0.type == vr1.type at this + point. */ + if (code == MULT_EXPR + && vr0.type == VR_ANTI_RANGE + && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) + { + set_value_range_to_varying (vr); + return; + } + + /* Multiplications and divisions are a bit tricky to handle, + depending on the mix of signs we have in the two ranges, we + need to operate on different values to get the minimum and + maximum values for the new range. One approach is to figure + out all the variations of range combinations and do the + operations. + + However, this involves several calls to compare_values and it + is pretty convoluted. It's simpler to do the 4 operations + (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP + MAX1) and then figure the smallest and largest values to form + the new range. */ + + /* Divisions by zero result in a VARYING value. */ + if (code != MULT_EXPR + && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) + { + set_value_range_to_varying (vr); + return; + } + + /* Compute the 4 cross operations. */ + 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; + } + + /* Set MIN to the minimum of VAL[i] and MAX to the maximum + of VAL[i]. */ + min = val[0]; + max = val[0]; + for (i = 1; i < 4; i++) + { + 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]))) + { + /* If we found an overflowed value, set MIN and MAX + to it so that we set the resulting range to + VARYING. */ + min = max = val[i]; + break; + } + + if (compare_values (val[i], min) == -1) + min = val[i]; + + if (compare_values (val[i], max) == 1) + max = val[i]; + } + } + } + else if (code == MINUS_EXPR) + { + /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to + VR_VARYING. It would take more effort to compute a precise + range for such a case. For example, if we have op0 == 1 and + op1 == 1 with their ranges both being ~[0,0], we would have + op0 - op1 == 0, so we cannot claim that the difference is in + ~[0,0]. Note that we are guaranteed to have + vr0.type == vr1.type at this point. */ + if (vr0.type == VR_ANTI_RANGE) + { + set_value_range_to_varying (vr); + return; + } + + /* For MINUS_EXPR, apply the operation to the opposite ends of + each range. */ + 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 either MIN or MAX overflowed, then set the resulting range to + VARYING. But we do accept an overflow infinity + representation. */ + 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; + } + + /* We punt if: + 1) [-INF, +INF] + 2) [-INF, +-INF(OVF)] + 3) [+-INF(OVF), +INF] + 4) [+-INF(OVF), +-INF(OVF)] + We learn nothing when we have INF and INF(OVF) on both sides. + Note that we do accept [-INF, -INF] and [+INF, +INF] without + overflow. */ + if ((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) + { + /* If the new range has its limits swapped around (MIN > MAX), + then the operation caused one of them to wrap around, mark + the new range VARYING. */ + set_value_range_to_varying (vr); + } + else + set_value_range (vr, type, min, max, NULL); +} + + +/* Extract range information from a unary expression EXPR based on + the range of its operand and the expression code. */ + +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 }; + + /* Refuse to operate on certain unary expressions for which we + cannot easily determine a resulting range. */ + 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; + } + + /* Get value ranges for the operand. For constant operands, create + a new value range with the operand to simplify processing. */ + 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 is UNDEFINED, so is the result. */ + if (vr0.type == VR_UNDEFINED) + { + set_value_range_to_undefined (vr); + return; + } + + /* Refuse to operate on symbolic ranges, or if neither operand is + a pointer or integral type. */ + 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 the expression involves pointers, we are only interested in + determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ + 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; + } + + /* Handle unary expressions on integer ranges. */ + if (code == NOP_EXPR || code == CONVERT_EXPR) + { + tree inner_type = TREE_TYPE (op0); + tree outer_type = TREE_TYPE (expr); + + /* If VR0 represents a simple range, then try to convert + the min and max values for the range to the same type + as OUTER_TYPE. If the results compare equal to VR0's + min and max values and the new min is still less than + or equal to the new max, then we can safely use the newly + computed range for EXPR. This allows us to compute + accurate ranges through many casts. */ + 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; + + /* Convert the input operand min/max to OUTER_TYPE. If + the input has no range information, then use the min/max + for the input's type. */ + 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); + + /* Verify the new min/max values are gimple values and + that they compare equal to the original input's + min/max values. */ + 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; + } + } + + /* When converting types of different sizes, set the result to + VARYING. Things like sign extensions and precision loss may + change the range. For instance, if x_3 is of type 'long long + int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it + is impossible to know at compile time whether y_5 will be + ~[0, 0]. */ + if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type) + || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type)) + { + set_value_range_to_varying (vr); + return; + } + } + + /* Conversion of a VR_VARYING value to a wider type can result + in a usable range. So wait until after we've handled conversions + before dropping the result to VR_VARYING if we had a source + operand that is VR_VARYING. */ + if (vr0.type == VR_VARYING) + { + set_value_range_to_varying (vr); + return; + } + + /* Apply the operation to each end of the range and see what we end + up with. */ + if (code == NEGATE_EXPR + && !TYPE_UNSIGNED (TREE_TYPE (expr))) + { + /* NEGATE_EXPR flips the range around. We need to treat + TYPE_MIN_VALUE specially. */ + 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))) + { + /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a + useful range. */ + 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; + } + + /* ABS_EXPR may flip the range around, if the original range + included negative values. */ + 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 a VR_ANTI_RANGEs contains zero, then we have + ~[-INF, min(MIN, MAX)]. */ + if (vr0.type == VR_ANTI_RANGE) + { + if (range_includes_zero_p (&vr0)) + { + /* Take the lower of the two values. */ + if (cmp != 1) + max = min; + + /* Create ~[-INF, min (abs(MIN), abs(MAX))] + or ~[-INF + 1, min (abs(MIN), abs(MAX))] when + flag_wrapv is set and the original anti-range doesn't include + TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ + 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 + { + /* All else has failed, so create the range [0, INF], even for + flag_wrapv since TYPE_MIN_VALUE is in the original + anti-range. */ + 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)); + } + } + + /* If the range contains zero then we know that the minimum value in the + range will be zero. */ + else if (range_includes_zero_p (&vr0)) + { + if (cmp == 1) + max = min; + min = build_int_cst (TREE_TYPE (expr), 0); + } + else + { + /* If the range was reversed, swap MIN and MAX. */ + if (cmp == 1) + { + tree t = min; + min = max; + max = t; + } + } + } + else + { + /* Otherwise, operate on each end of the range. */ + 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 both sides have overflowed, we don't know + anything. */ + if ((is_overflow_infinity (vr0.min) + || TREE_OVERFLOW (min)) + && (is_overflow_infinity (vr0.max) + || TREE_OVERFLOW (max))) + { + set_value_range_to_varying (vr); + return; + } + + if (is_overflow_infinity (vr0.min)) + min = vr0.min; + else if (TREE_OVERFLOW (min)) + { + if (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) + { + /* If the new range has its limits swapped around (MIN > MAX), + then the operation caused one of them to wrap around, mark + the new range VARYING. */ + set_value_range_to_varying (vr); + } + else + set_value_range (vr, vr0.type, min, max, NULL); +} + + +/* Extract range information from a comparison expression EXPR based + on the range of its operand and the expression code. */ + +static void +extract_range_from_comparison (value_range_t *vr, tree expr) +{ + bool sop = false; + tree val = vrp_evaluate_conditional_warnv (expr, false, &sop); + + /* A disadvantage of using a special infinity as an overflow + representation is that we lose the ability to record overflow + when we don't have an infinity. So we have to ignore a result + which relies on overflow. */ + + if (val && !is_overflow_infinity (val) && !sop) + { + /* Since this expression was found on the RHS of an assignment, + its type may be different from _Bool. Convert VAL to EXPR's + type. */ + 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); +} + + +/* Try to compute a useful range out of expression EXPR and store it + in *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 we got a varying range from the tests above, try a final + time to derive a nonnegative or nonzero range. This time + relying primarily on generic routines in fold in conjunction + with range data. */ + 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)); + } +} + +/* Given a range VR, a LOOP and a variable VAR, determine whether it + would be profitable to adjust VR using scalar evolution information + for VAR. If so, update VR with the new limits. */ + +static void +adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, + tree var) +{ + tree init, step, chrec, tmin, tmax, min, max, type; + enum ev_direction dir; + + /* TODO. Don't adjust anti-ranges. An anti-range may provide + better opportunities than a regular range, but I'm not sure. */ + 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 is symbolic, we can't know whether INIT will be the + minimum or maximum value in the range. Also, unless INIT is + a simple expression, compare_values and possibly other functions + in tree-vrp won't be able to handle it. */ + if (step == NULL_TREE + || !is_gimple_min_invariant (step) + || !valid_value_p (init)) + return; + + dir = scev_direction (chrec); + if (/* Do not adjust ranges if we do not know whether the iv increases + or decreases, ... */ + dir == EV_DIR_UNKNOWN + /* ... or if it may wrap. */ + || scev_probably_wraps_p (init, step, stmt, + current_loops->parray[CHREC_VARIABLE (chrec)], + true)) + return; + + /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of + negative_overflow_infinity and positive_overflow_infinity, + because we have concluded that the loop probably does not + wrap. */ + + 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; + + /* For VARYING or UNDEFINED ranges, just about anything we get + from scalar evolutions should be better. */ + + if (dir == EV_DIR_DECREASES) + max = init; + else + min = init; + + /* If we would create an invalid range, then just assume we + know absolutely nothing. This may be over-conservative, + but it's clearly safe, and should happen only in unreachable + parts of code, or for invalid programs. */ + 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) + { + /* INIT is the maximum value. If INIT is lower than VR->MAX + but no smaller than VR->MIN, set VR->MAX to INIT. */ + if (compare_values (init, max) == -1) + { + max = init; + + /* If we just created an invalid range with the minimum + greater than the maximum, we fail conservatively. + This should happen only in unreachable + parts of code, or for invalid programs. */ + 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 INIT is bigger than VR->MIN, set VR->MIN to INIT. */ + if (compare_values (init, min) == 1) + { + min = init; + + /* Again, avoid creating invalid range by failing. */ + 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, + 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; +} + + +/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: + + - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for + all the values in the ranges. + + - Return BOOLEAN_FALSE_NODE if the comparison always returns false. + + - Return NULL_TREE if it is not always possible to determine the + value of the comparison. + + Also set *STRICT_OVERFLOW_P to indicate whether a range with an + overflow infinity was used in the test. */ + + +static tree +compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, + bool *strict_overflow_p) +{ + /* VARYING or UNDEFINED ranges cannot be compared. */ + if (vr0->type == VR_VARYING + || vr0->type == VR_UNDEFINED + || vr1->type == VR_VARYING + || vr1->type == VR_UNDEFINED) + return NULL_TREE; + + /* Anti-ranges need to be handled separately. */ + if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) + { + /* If both are anti-ranges, then we cannot compute any + comparison. */ + if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) + return NULL_TREE; + + /* These comparisons are never statically computable. */ + if (comp == GT_EXPR + || comp == GE_EXPR + || comp == LT_EXPR + || comp == LE_EXPR) + return NULL_TREE; + + /* Equality can be computed only between a range and an + anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ + if (vr0->type == VR_RANGE) + { + /* To simplify processing, make VR0 the anti-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; + + /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the + operands around and change the comparison code. */ + 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) + { + /* Equality may only be computed if both ranges represent + exactly one value. */ + 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; + } + /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ + 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; + + /* If VR0 is completely to the left or completely to the right + of VR1, they are always different. Notice that we need to + make sure that both comparisons yield similar results to + avoid comparing values that cannot be compared at + compile-time. */ + 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; + + /* If VR0 and VR1 represent a single value and are identical, + return false. */ + 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; + + /* Otherwise, they may or may not be different. */ + else + return NULL_TREE; + } + else if (comp == LT_EXPR || comp == LE_EXPR) + { + int tst; + + /* If VR0 is to the left of VR1, return true. */ + 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; + } + + /* If VR0 is to the right of VR1, return false. */ + 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; + } + + /* Otherwise, we don't know. */ + return NULL_TREE; + } + + gcc_unreachable (); +} + + +/* Given a value range VR, a value VAL and a comparison code COMP, return + BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the + values in VR. Return BOOLEAN_FALSE_NODE if the comparison + always returns false. Return NULL_TREE if it is not always + possible to determine the value of the comparison. Also set + *STRICT_OVERFLOW_P to indicate whether a range with an overflow + infinity was used in the test. */ + +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; + + /* Anti-ranges need to be handled separately. */ + if (vr->type == VR_ANTI_RANGE) + { + /* For anti-ranges, the only predicates that we can compute at + compile time are equality and inequality. */ + if (comp == GT_EXPR + || comp == GE_EXPR + || comp == LT_EXPR + || comp == LE_EXPR) + return NULL_TREE; + + /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ + 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) + { + /* EQ_EXPR may only be computed if VR represents exactly + one value. */ + 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 VAL is not inside VR, then they are always different. */ + 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 VR represents exactly one value equal to VAL, then return + false. */ + 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; + + /* Otherwise, they may or may not be different. */ + return NULL_TREE; + } + else if (comp == LT_EXPR || comp == LE_EXPR) + { + int tst; + + /* If VR is to the left of VAL, return true. */ + 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; + } + + /* If VR is to the right of VAL, return false. */ + 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; + } + + /* Otherwise, we don't know. */ + return NULL_TREE; + } + else if (comp == GT_EXPR || comp == GE_EXPR) + { + int tst; + + /* If VR is to the right of VAL, return true. */ + 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; + } + + /* If VR is to the left of VAL, return false. */ + 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; + } + + /* Otherwise, we don't know. */ + return NULL_TREE; + } + + gcc_unreachable (); +} + + +/* Debugging dumps. */ + +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); + + +/* Dump value range VR to FILE. */ + +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"); +} + + +/* Dump value range VR to stderr. */ + +void +debug_value_range (value_range_t *vr) +{ + dump_value_range (stderr, vr); + fprintf (stderr, "\n"); +} + + +/* Dump value ranges of all SSA_NAMEs to FILE. */ + +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"); +} + + +/* Dump all value ranges to stderr. */ + +void +debug_all_value_ranges (void) +{ + dump_all_value_ranges (stderr); +} + + +/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, + create a new SSA name N and return the assertion assignment + 'V = ASSERT_EXPR <V, V OP W>'. */ + +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) + { + /* Given !V, build the assignment N = false. */ + 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) + { + /* Given V, build the assignment N = true. */ + gcc_assert (v == cond); + assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); + } + else + gcc_unreachable (); + + SSA_NAME_DEF_STMT (n) = assertion; + + /* The new ASSERT_EXPR, creates a new SSA name that replaces the + operand of the ASSERT_EXPR. Register the new name and the old one + in the replacement table so that we can fix the SSA web after + adding all the ASSERT_EXPRs. */ + register_new_name_mapping (n, v); + + return assertion; +} + + +/* Return false if EXPR is a predicate expression involving floating + point values. */ + +static inline bool +fp_predicate (tree expr) +{ + return (COMPARISON_CLASS_P (expr) + && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); +} + + +/* If the range of values taken by OP can be inferred after STMT executes, + return the comparison code (COMP_CODE_P) and value (VAL_P) that + describes the inferred range. Return true if a range could be + inferred. */ + +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; + + /* Do not attempt to infer anything in names that flow through + abnormal edges. */ + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) + return false; + + /* Similarly, don't infer anything from statements that may throw + exceptions. */ + if (tree_could_throw_p (stmt)) + return false; + + /* If STMT is the last statement of a basic block with no + successors, there is no point inferring anything about any of its + operands. We would not be able to find a proper insertion point + for the assertion, anyway. */ + if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) + return false; + + /* We can only assume that a pointer dereference will yield + non-NULL if -fdelete-null-pointer-checks is enabled. */ + 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); + +/* Dump all the registered assertions for NAME to FILE. */ + +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"); +} + + +/* Dump all the registered assertions for NAME to stderr. */ + +void +debug_asserts_for (tree name) +{ + dump_asserts_for (stderr, name); +} + + +/* Dump all the registered assertions for all the names to FILE. */ + +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"); +} + + +/* Dump all the registered assertions for all the names to stderr. */ + +void +debug_all_asserts (void) +{ + dump_all_asserts (stderr); +} + + +/* If NAME doesn't have an ASSERT_EXPR registered for asserting + 'NAME COMP_CODE VAL' at a location that dominates block BB or + E->DEST, then register this location as a possible insertion point + for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. + + BB, E and SI provide the exact insertion point for the new + ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted + on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on + BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E + must not be NULL. */ + +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 + + /* The new assertion A will be inserted at BB or E. We need to + determine if the new location is dominated by a previously + registered location for A. If we are doing an edge insertion, + assume that A will be inserted at E->DEST. Note that this is not + necessarily true. + + If E is a critical edge, it will be split. But even if E is + split, the new block will dominate the same set of blocks that + E->DEST dominates. + + The reverse, however, is not true, blocks dominated by E->DEST + will not be dominated by the new block created to split E. So, + if the insertion location is on a critical edge, we will not use + the new location to move another assertion previously registered + at a block dominated by E->DEST. */ + dest_bb = (bb) ? bb : e->dest; + + /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and + VAL at a block dominating DEST_BB, then we don't need to insert a new + one. Similarly, if the same assertion already exists at a block + dominated by DEST_BB and the new location is not on a critical + edge, then update the existing location for the assertion (i.e., + move the assertion up in the dominance tree). + + Note, this is implemented as a simple linked list because there + should not be more than a handful of assertions registered per + name. If this becomes a performance problem, a table hashed by + COMP_CODE and VAL could be implemented. */ + 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 the assertion NAME COMP_CODE VAL has already been + registered at a basic block that dominates DEST_BB, then + we don't need to insert the same assertion again. Note + that we don't check strict dominance here to avoid + replicating the same assertion inside the same basic + block more than once (e.g., when a pointer is + dereferenced several times inside a block). + + An exception to this rule are edge insertions. If the + new assertion is to be inserted on edge E, then it will + dominate all the other insertions that we may want to + insert in DEST_BB. So, if we are doing an edge + insertion, don't do this dominance check. */ + if (e == NULL + && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) + return; + + /* Otherwise, if E is not a critical edge and DEST_BB + dominates the existing location for the assertion, move + the assertion up in the dominance tree by updating its + location information. */ + 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; + } + } + + /* Update the last node of the list and move to the next one. */ + last_loc = loc; + loc = loc->next; + } + + /* If we didn't find an assertion already registered for + NAME COMP_CODE VAL, add a new one at the end of the list of + assertions associated with NAME. */ + 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)); +} + + +/* Try to register an edge assertion for SSA name NAME on edge E for + the conditional jump pointed to by SI. Return true if an assertion + for NAME could be registered. */ + +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); + + /* Do not attempt to infer anything in names that flow through + abnormal edges. */ + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) + return false; + + /* If NAME was not found in the sub-graph reachable from E, then + there's nothing to do. */ + if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) + return false; + + /* We found a use of NAME in the sub-graph rooted at E->DEST. + Register an assertion for NAME according to the value that NAME + takes on edge E. */ + if (TREE_CODE (stmt) == COND_EXPR) + { + /* If BB ends in a COND_EXPR then NAME then we should insert + the original predicate on EDGE_TRUE_VALUE and the + opposite predicate on EDGE_FALSE_VALUE. */ + tree cond = COND_EXPR_COND (stmt); + bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; + + /* Predicates may be a single SSA name or NAME OP VAL. */ + if (cond == name) + { + /* If the predicate is a name, it must be NAME, in which + case we create the predicate NAME == true or + NAME == false accordingly. */ + comp_code = EQ_EXPR; + val = (is_else_edge) ? boolean_false_node : boolean_true_node; + } + else + { + /* Otherwise, we have a comparison of the form NAME COMP VAL + or VAL COMP NAME. */ + if (name == TREE_OPERAND (cond, 1)) + { + /* If the predicate is of the form VAL COMP NAME, flip + COMP around because we need to register NAME as the + first operand in the predicate. */ + comp_code = swap_tree_comparison (TREE_CODE (cond)); + val = TREE_OPERAND (cond, 0); + } + else + { + /* The comparison is of the form NAME COMP VAL, so the + comparison code remains unchanged. */ + comp_code = TREE_CODE (cond); + val = TREE_OPERAND (cond, 1); + } + + /* If we are inserting the assertion on the ELSE edge, we + need to invert the sign comparison. */ + if (is_else_edge) + comp_code = invert_tree_comparison (comp_code, 0); + + /* Do not register always-false predicates. FIXME, this + works around a limitation in fold() when dealing with + enumerations. Given 'enum { N1, N2 } x;', fold will not + fold 'if (x > N2)' to 'if (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 + { + /* FIXME. Handle SWITCH_EXPR. */ + gcc_unreachable (); + } + + register_new_assert_for (name, comp_code, val, NULL, e, si); + return true; +} + + +static bool find_assert_locations (basic_block bb); + +/* Determine whether the outgoing edges of BB should receive an + ASSERT_EXPR for each of the operands of BB's last statement. The + last statement of BB must be a COND_EXPR or a SWITCH_EXPR. + + If any of the sub-graphs rooted at BB have an interesting use of + the predicate operands, an assert location node is added to the + list of assertions for the corresponding operands. */ + +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); + + /* Look for uses of the operands in each of the sub-graphs + rooted at BB. We need to check each of the outgoing edges + separately, so that we know what kind of ASSERT_EXPR to + insert. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (e->dest == bb) + continue; + + /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. + Otherwise, when we finish traversing each of the sub-graphs, we + won't know whether the variables were found in the sub-graphs or + if they had been found in a block upstream from BB. + + This is actually a bad idea is some cases, particularly jump + threading. Consider a CFG like the following: + + 0 + /| + 1 | + \| + 2 + / \ + 3 4 + + Assume that one or more operands in the conditional at the + end of block 0 are used in a conditional in block 2, but not + anywhere in block 1. In this case we will not insert any + assert statements in block 1, which may cause us to miss + opportunities to optimize, particularly for jump threading. */ + FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) + RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); + + /* 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); + + /* Register the necessary assertions for each operand in the + conditional predicate. */ + FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) + need_assert |= register_edge_assert_for (op, e, last_si); + } + + /* Finally, indicate that we have found the operands in the + conditional. */ + FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) + SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); + + return need_assert; +} + + +/* Traverse all the statements in block BB looking for statements that + may generate useful assertions for the SSA names in their operand. + If a statement produces a useful assertion A for name N_i, then the + list of assertions already generated for N_i is scanned to + determine if A is actually needed. + + If N_i already had the assertion A at a location dominating the + current location, then nothing needs to be done. Otherwise, the + new location for A is recorded instead. + + 1- For every statement S in BB, all the variables used by S are + added to bitmap FOUND_IN_SUBGRAPH. + + 2- If statement S uses an operand N in a way that exposes a known + value range for N, then if N was not already generated by an + ASSERT_EXPR, create a new assert location for N. For instance, + if N is a pointer and the statement dereferences it, we can + assume that N is not NULL. + + 3- COND_EXPRs are a special case of #2. We can derive range + information from the predicate but need to insert different + ASSERT_EXPRs for each of the sub-graphs rooted at the + conditional block. If the last statement of BB is a conditional + expression of the form 'X op Y', then + + a) Remove X and Y from the set FOUND_IN_SUBGRAPH. + + b) If the conditional is the only entry point to the sub-graph + corresponding to the THEN_CLAUSE, recurse into it. On + return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then + an ASSERT_EXPR is added for the corresponding variable. + + c) Repeat step (b) on the ELSE_CLAUSE. + + d) Mark X and Y in FOUND_IN_SUBGRAPH. + + For instance, + + if (a == 9) + b = a; + else + b = c + 1; + + In this case, an assertion on the THEN clause is useful to + determine that 'a' is always 9 on that edge. However, an assertion + on the ELSE clause would be unnecessary. + + 4- If BB does not end in a conditional expression, then we recurse + into BB's dominator children. + + At the end of the recursive traversal, every SSA name will have a + list of locations where ASSERT_EXPRs should be added. When a new + location for name N is found, it is registered by calling + register_new_assert_for. That function keeps track of all the + registered assertions to prevent adding unnecessary assertions. + For instance, if a pointer P_4 is dereferenced more than once in a + dominator tree, only the location dominating all the dereference of + P_4 will receive an ASSERT_EXPR. + + If this function returns true, then it means that there are names + for which we need to generate ASSERT_EXPRs. Those assertions are + inserted by process_assert_insertions. + + TODO. Handle SWITCH_EXPR. */ + +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; + + /* Traverse all PHI nodes in BB marking used operands. */ + 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)); + } + } + } + + /* Traverse all the statements in BB marking used names and looking + for statements that may infer assertions for their used operands. */ + 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); + + /* See if we can derive an assertion for any of STMT's operands. */ + FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) + { + tree value; + enum tree_code comp_code; + + /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside + the sub-graph of a conditional block, when we return from + this recursive walk, our parent will use the + FOUND_IN_SUBGRAPH bitset to determine if one of the + operands it was looking for was present in the sub-graph. */ + SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); + + /* If OP is used in such a way that we can infer a value + range for it, and we don't find a previous assertion for + it, create a new assertion location node for OP. */ + if (infer_value_range (stmt, op, &comp_code, &value)) + { + /* If we are able to infer a nonzero value range for OP, + then walk backwards through the use-def chain to see if OP + was set via a typecast. + + If so, then we can also infer a nonzero value range + for the operand of the NOP_EXPR. */ + 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); + + /* Note we want to register the assert for the + operand of the NOP_EXPR after SI, not after the + conversion. */ + if (! has_single_use (t)) + { + register_new_assert_for (t, comp_code, value, + bb, NULL, si); + need_assert = true; + } + } + } + + /* If OP is used only once, namely in this STMT, don't + bother creating an ASSERT_EXPR for it. Such an + ASSERT_EXPR would do nothing but increase compile time. */ + if (!has_single_use (op)) + { + register_new_assert_for (op, comp_code, value, bb, NULL, si); + need_assert = true; + } + } + } + + /* Remember the last statement of the block. */ + last = stmt; + } + + /* If BB's last statement is a conditional expression + involving integer operands, recurse into each of the sub-graphs + rooted at BB to determine if we need to add ASSERT_EXPRs. */ + 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); + + /* Recurse into the dominator children of 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; +} + + +/* Create an ASSERT_EXPR for NAME and insert it in the location + indicated by LOC. Return true if we made any edge insertions. */ + +static bool +process_assert_insertions_for (tree name, assert_locus_t loc) +{ + /* Build the comparison expression NAME_i COMP_CODE VAL. */ + 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) + { + /* We have been asked to insert the assertion on an edge. This + is used only by COND_EXPR and SWITCH_EXPR assertions. */ +#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; + } + + /* Otherwise, we can insert right after LOC->SI iff the + statement must not be the last statement in the block. */ + stmt = bsi_stmt (loc->si); + if (!stmt_ends_bb_p (stmt)) + { + bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); + return false; + } + + /* If STMT must be the last statement in BB, we can only insert new + assertions on the non-abnormal edge out of BB. Note that since + STMT is not control flow, there may only be one non-abnormal edge + out of BB. */ + FOR_EACH_EDGE (e, ei, loc->bb->succs) + if (!(e->flags & EDGE_ABNORMAL)) + { + bsi_insert_on_edge (e, assert_expr); + return true; + } + + gcc_unreachable (); +} + + +/* Process all the insertions registered for every name N_i registered + in NEED_ASSERT_FOR. The list of assertions to be inserted are + found in ASSERTS_FOR[i]. */ + +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); +} + + +/* Traverse the flowgraph looking for conditional jumps to insert range + expressions. These range expressions are meant to provide information + to optimizations that need to reason in terms of value ranges. They + will not be expanded into RTL. For instance, given: + + x = ... + y = ... + if (x < y) + y = x - 2; + else + x = y + 3; + + this pass will transform the code into: + + x = ... + y = ... + if (x < y) + { + x = ASSERT_EXPR <x, x < y> + y = x - 2 + } + else + { + y = ASSERT_EXPR <y, x <= y> + x = y + 3 + } + + The idea is that once copy and constant propagation have run, other + optimizations will be able to determine what ranges of values can 'x' + take in different paths of the code, simply by checking the reaching + definition of 'x'. */ + +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); +} + + +/* Convert range assertion expressions into the implied copies and + copy propagate away the copies. Doing the trivial copy propagation + here avoids the need to run the full copy propagation pass after + VRP. + + FIXME, this will eventually lead to copy propagation removing the + names that had useful range information attached to them. For + instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, + then N_i will have the range [3, +INF]. + + However, by converting the assertion into the implied copy + operation N_i = N_j, we will then copy-propagate N_j into the uses + of N_i and lose the range information. We may want to hold on to + ASSERT_EXPRs a little while longer as the ranges could be used in + things like jump threading. + + The problem with keeping ASSERT_EXPRs around is that passes after + VRP need to handle them appropriately. + + Another approach would be to make the range information a first + class property of the SSA_NAME so that it can be queried from + any pass. This is made somewhat more complex by the need for + multiple ranges to be associated with one SSA_NAME. */ + +static void +remove_range_assertions (void) +{ + basic_block bb; + block_stmt_iterator si; + + /* Note that the BSI iterator bump happens at the bottom of the + loop and no bump is necessary if we're removing the statement + referenced by the current BSI. */ + 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); + + /* Propagate the RHS into every use of the LHS. */ + 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); + } + + /* And finally, remove the copy, it is not needed. */ + bsi_remove (&si, true); + } + else + bsi_next (&si); + } + + sbitmap_free (blocks_visited); +} + + +/* Return true if STMT is interesting for VRP. */ + +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); + + /* In general, assignments with virtual operands are not useful + for deriving ranges, with the obvious exception of calls to + builtin functions. */ + 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; +} + + +/* Initialize local data structures for VRP. */ + +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; + } + } + } +} + + +/* Visit assignment STMT. If it produces an interesting range, record + the SSA name in *OUTPUT_P. */ + +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); + + /* We only keep track of ranges in integral and pointer types. */ + if (TREE_CODE (lhs) == SSA_NAME + && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) + /* It is valid to have NULL MIN/MAX values on a type. See + build_range_type. */ + && 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 STMT is inside a loop, we may be able to know something + else about the range of LHS by examining scalar evolution + information. */ + 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; + } + + /* Every other statement produces no useful ranges. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) + set_value_range_to_varying (get_value_range (def)); + + return SSA_PROP_VARYING; +} + + +/* Compare all the value ranges for names equivalent to VAR with VAL + using comparison code COMP. Return the same value returned by + compare_range_with_value, including the setting of + *STRICT_OVERFLOW_P. */ + +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; + + /* Get the set of equivalences for VAR. */ + e = get_value_range (var)->equiv; + + /* Add VAR to its own set of equivalences so that VAR's value range + is processed by this loop (otherwise, we would have to replicate + the body of the loop just to check VAR's value range). */ + bitmap_set_bit (e, SSA_NAME_VERSION (var)); + + /* Start at -1. Set it to 0 if we do a comparison without relying + on overflow, or 1 if all comparisons rely on overflow. */ + used_strict_overflow = -1; + + EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) + { + bool sop; + + value_range_t equiv_vr = *(vr_value[i]); + + /* If name N_i does not have a valid range, use N_i as its own + range. This allows us to compare against names that may + have N_i in their ranges. */ + if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) + { + equiv_vr.type = VR_RANGE; + equiv_vr.min = ssa_name (i); + equiv_vr.max = ssa_name (i); + } + + sop = false; + t = compare_range_with_value (comp, &equiv_vr, val, &sop); + if (t) + { + /* If we get different answers from different members + of the equivalence set this check must be in a dead + code region. Folding it to a trap representation + would be correct here. For now just return don't-know. */ + 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; + } + } + + /* Remove VAR from its own equivalence set. */ + bitmap_clear_bit (e, SSA_NAME_VERSION (var)); + + if (retval) + { + if (used_strict_overflow > 0) + *strict_overflow_p = true; + return retval; + } + + /* We couldn't find a non-NULL value for the predicate. */ + return NULL_TREE; +} + + +/* Given a comparison code COMP and names N1 and N2, compare all the + ranges equivalent to N1 against all the ranges equivalent to N2 + to determine the value of N1 COMP N2. Return the same value + returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate + whether we relied on an overflow infinity in the comparison. */ + + +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; + + /* Compare the ranges of every name equivalent to N1 against the + ranges of every name equivalent to N2. */ + e1 = get_value_range (n1)->equiv; + e2 = get_value_range (n2)->equiv; + + /* Add N1 and N2 to their own set of equivalences to avoid + duplicating the body of the loop just to check N1 and N2 + ranges. */ + bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); + bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); + + /* If the equivalence sets have a common intersection, then the two + names can be compared without checking their ranges. */ + 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; + } + + /* Start at -1. Set it to 0 if we do a comparison without relying + on overflow, or 1 if all comparisons rely on overflow. */ + used_strict_overflow = -1; + + /* Otherwise, compare all the equivalent ranges. First, add N1 and + N2 to their own set of equivalences to avoid duplicating the body + of the loop just to check N1 and N2 ranges. */ + EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) + { + value_range_t vr1 = *(vr_value[i1]); + + /* If the range is VARYING or UNDEFINED, use the name itself. */ + if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) + { + vr1.type = VR_RANGE; + vr1.min = ssa_name (i1); + vr1.max = ssa_name (i1); + } + + 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 we get different answers from different members + of the equivalence set this check must be in a dead + code region. Folding it to a trap representation + would be correct here. For now just return don't-know. */ + 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; + } + } + + /* None of the equivalent ranges are useful in computing this + comparison. */ + bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); + bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); + return NULL_TREE; +} + + +/* Given a conditional predicate COND, try to determine if COND yields + true or false based on the value ranges of its operands. Return + BOOLEAN_TRUE_NODE if the conditional always evaluates to true, + BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, + NULL if the conditional cannot be evaluated at compile time. + + If USE_EQUIV_P is true, the ranges of all the names equivalent with + the operands in COND are used when trying to compute its value. + This is only used during final substitution. During propagation, + we only check the range of each variable and not its equivalents. + + Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow + infinity to produce the result. */ + +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 COND has a known boolean range, return it. */ + if (retval) + return retval; + + /* Otherwise, if COND has a symbolic range of exactly one value, + return it. */ + 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); + + /* We only deal with integral and pointer types. */ + 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)); + } + } + + /* Anything else cannot be computed statically. */ + return NULL_TREE; +} + +/* Given COND within STMT, try to simplify it based on value range + information. Return NULL if the conditional can not be evaluated. + The ranges of all the names equivalent with the operands in COND + will be used when trying to compute the value. If the result is + based on undefined signed overflow, issue a warning if + appropriate. */ + +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; +} + + +/* Visit conditional statement STMT. If we can determine which edge + will be taken out of STMT's basic block, record it in + *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return + SSA_PROP_VARYING. */ + +static enum ssa_prop_result +vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) +{ + tree cond, val; + bool sop; + + *taken_edge_p = NULL; + + /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to + add ASSERT_EXPRs for them. */ + 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"); + } + + /* Compute the value of the predicate COND by checking the known + ranges of each of its operands. + + Note that we cannot evaluate all the equivalent ranges here + because those ranges may not yet be final and with the current + propagation strategy, we cannot determine when the value ranges + of the names in the equivalence set have changed. + + For instance, given the following code fragment + + i_5 = PHI <8, i_13> + ... + i_14 = ASSERT_EXPR <i_5, i_5 != 0> + if (i_14 == 1) + ... + + Assume that on the first visit to i_14, i_5 has the temporary + range [8, 8] because the second argument to the PHI function is + not yet executable. We derive the range ~[0, 0] for i_14 and the + equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for + the first time, since i_14 is equivalent to the range [8, 8], we + determine that the predicate is always false. + + On the next round of propagation, i_13 is determined to be + VARYING, which causes i_5 to drop down to VARYING. So, another + visit to i_14 is scheduled. In this second visit, we compute the + exact same range and equivalence set for i_14, namely ~[0, 0] and + { i_5 }. But we did not have the previous range for i_5 + registered, so vrp_visit_assignment thinks that the range for + i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' + is not visited again, which stops propagation from visiting + statements in the THEN clause of that if(). + + To properly fix this we would need to keep the previous range + value for the names in the equivalence set. This way we would've + discovered that from one visit to the other i_5 changed from + range [8, 8] to VR_VARYING. + + However, fixing this apparent limitation may not be worth the + additional checking. Testing on several code bases (GCC, DLV, + MICO, TRAMP3D and SPEC2000) showed that doing this results in + 4 more predicates folded in SPEC. */ + 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; +} + + +/* Evaluate statement STMT. If the statement produces a useful range, + return SSA_PROP_INTERESTING and record the SSA name with the + interesting range into *OUTPUT_P. + + If STMT is a conditional branch and we can determine its truth + value, the taken edge is recorded in *TAKEN_EDGE_P. + + If STMT produces a varying value, return 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); + + /* In general, assignments with virtual operands are not useful + for deriving ranges, with the obvious exception of calls to + builtin functions. */ + 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); + + /* All other statements produce nothing of interest for VRP, so mark + their outputs varying and prevent further simulation. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) + set_value_range_to_varying (get_value_range (def)); + + return SSA_PROP_VARYING; +} + + +/* Meet operation for value ranges. Given two value ranges VR0 and + VR1, store in VR0 the result of meeting VR0 and VR1. + + The meeting rules are as follows: + + 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. + + 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the + union of VR0 and VR1. */ + +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) + { + /* Nothing to do. VR0 already has the resulting range. */ + return; + } + + if (vr0->type == VR_VARYING) + { + /* Nothing to do. VR0 already has the resulting range. */ + return; + } + + if (vr1->type == VR_VARYING) + { + set_value_range_to_varying (vr0); + return; + } + + if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) + { + /* If VR0 and VR1 have a non-empty intersection, compute the + union of both ranges. */ + if (value_ranges_intersect_p (vr0, vr1)) + { + int cmp; + tree min, max; + + /* The lower limit of the new range is the minimum of the + two ranges. If they cannot be compared, the result is + VARYING. */ + 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; + } + + /* Similarly, the upper limit of the new range is the + maximum of the two ranges. If they cannot be compared, + the result is VARYING. */ + 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; + } + + /* Check for useless ranges. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (min)) + && ((vrp_val_is_min (min) || is_overflow_infinity (min)) + && (vrp_val_is_max (max) || is_overflow_infinity (max)))) + { + set_value_range_to_varying (vr0); + return; + } + + /* The resulting set of equivalences is the intersection of + the two sets. */ + if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) + bitmap_and_into (vr0->equiv, vr1->equiv); + 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) + { + /* Two anti-ranges meet only if they are both identical. */ + if (compare_values (vr0->min, vr1->min) == 0 + && compare_values (vr0->max, vr1->max) == 0 + && compare_values (vr0->min, vr0->max) == 0) + { + /* The resulting set of equivalences is the intersection of + the two sets. */ + if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) + bitmap_and_into (vr0->equiv, vr1->equiv); + 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) + { + /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] + meet only if the ranges have an empty intersection. The + result of the meet operation is the anti-range. */ + if (!symbolic_range_p (vr0) + && !symbolic_range_p (vr1) + && !value_ranges_intersect_p (vr0, vr1)) + { + /* Copy most of VR1 into VR0. Don't copy VR1's equivalence + set. We need to compute the intersection of the two + equivalence sets. */ + if (vr1->type == VR_ANTI_RANGE) + set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); + + /* The resulting set of equivalences is the intersection of + the two sets. */ + if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) + bitmap_and_into (vr0->equiv, vr1->equiv); + else if (vr0->equiv && !vr1->equiv) + bitmap_clear (vr0->equiv); + } + else + goto no_meet; + } + else + gcc_unreachable (); + + return; + +no_meet: + /* The two range VR0 and VR1 do not meet. Before giving up and + setting the result to VARYING, see if we can at least derive a + useful anti-range. FIXME, all this nonsense about distinguishing + anti-ranges from ranges is necessary because of the odd + semantics of range_includes_zero_p and friends. */ + 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)); + + /* Since this meet operation did not result from the meeting of + two equivalent names, VR0 cannot have any equivalences. */ + if (vr0->equiv) + bitmap_clear (vr0->equiv); + } + else + set_value_range_to_varying (vr0); +} + + +/* Visit all arguments for PHI node PHI that flow through executable + edges. If a valid value range can be derived from all the incoming + value ranges, set a new range for the LHS of PHI. */ + +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; + + /* To prevent infinite iterations in the algorithm, derive ranges + when the new value is slightly bigger or smaller than the + previous one. */ + 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 the new minimum is smaller or larger than the previous + one, go all the way to -INF. In the first case, to avoid + iterating millions of times to reach -INF, and in the + other case to avoid infinite bouncing between different + minimums. */ + if (cmp_min > 0 || cmp_min < 0) + { + /* If we will end up with a (-INF, +INF) range, set it + to VARYING. */ + 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; + } + + /* Similarly, if the new maximum is smaller or larger than + the previous one, go all the way to +INF. */ + if (cmp_max < 0 || cmp_max > 0) + { + /* If we will end up with a (-INF, +INF) range, set it + to VARYING. */ + 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 the new range is different than the previous value, keep + iterating. */ + if (update_value_range (lhs, &vr_result)) + return SSA_PROP_INTERESTING; + + /* Nothing changed, don't add outgoing edges. */ + return SSA_PROP_NOT_INTERESTING; + + /* No match found. Set the LHS to VARYING. */ +varying: + set_value_range_to_varying (lhs_vr); + return SSA_PROP_VARYING; +} + +/* Simplify a division or modulo operator to a right shift or + bitwise and if the first operand is unsigned or is greater + than zero and the second operand is an exact power of two. */ + +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); + } +} + +/* If the operand to an ABS_EXPR is >= 0, then eliminate the + ABS_EXPR. If the operand is <= 0, then simplify the + ABS_EXPR into a NEGATE_EXPR. */ + +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); + } + } +} + +/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has + a known value range VR. + + If there is one and only one value which will satisfy the + conditional, then return that value. Else return NULL. */ + +static tree +test_for_singularity (enum tree_code cond_code, tree op0, + tree op1, value_range_t *vr) +{ + tree min = NULL; + tree max = NULL; + + /* Extract minimum/maximum values which satisfy the + the conditional as it was written. */ + if (cond_code == LE_EXPR || cond_code == LT_EXPR) + { + /* This should not be negative infinity; there is no overflow + here. */ + 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) + { + /* This should not be positive infinity; there is no overflow + here. */ + 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; + } + } + + /* Now refine the minimum and maximum values using any + value range information we have for op0. */ + 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 the new min/max values have converged to a single value, + then there is only one value which can satisfy the condition, + return that value. */ + if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) + return min; + } + return NULL; +} + +/* Simplify a conditional using a relational operator to an equality + test if the range information indicates only one value can satisfy + the original conditional. */ + +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 we have range information for OP0, then we might be + able to simplify this conditional. */ + 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; + + } + + /* Try again after inverting the condition. We only deal + with integral types here, so no need to worry about + issues with inverting FP comparisons. */ + 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; + + } + } + } +} + +/* Simplify STMT using ranges if possible. */ + +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); + + /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR + and BIT_AND_EXPR respectively if the first operand is greater + than zero and the second operand is an exact power of two. */ + if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) + && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) + && integer_pow2p (TREE_OPERAND (rhs, 1))) + simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); + + /* Transform ABS (X) into X or -X as appropriate. */ + if (rhs_code == ABS_EXPR + && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) + 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); + } +} + +/* Stack of dest,src equivalency pairs that need to be restored after + each attempt to thread a block's incoming edge to an outgoing edge. + + A NULL entry is used to mark the end of pairs which need to be + restored. */ +static VEC(tree,heap) *stack; + +/* A trivial wrapper so that we can present the generic jump threading + code with a simple API for simplifying statements. STMT is the + statement we want to simplify, WITHIN_STMT provides the location + for any overflow warnings. */ + +static tree +simplify_stmt_for_jump_threading (tree stmt, tree within_stmt) +{ + /* We only use VRP information to simplify conditionals. This is + overly conservative, but it's unclear if doing more would be + worth the compile time cost. */ + if (TREE_CODE (stmt) != COND_EXPR) + return NULL; + + return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt); +} + +/* Blocks which have more than one predecessor and more than + one successor present jump threading opportunities. ie, + when the block is reached from a specific predecessor, we + may be able to determine which of the outgoing edges will + be traversed. When this optimization applies, we are able + to avoid conditionals at runtime and we may expose secondary + optimization opportunities. + + This routine is effectively a driver for the generic jump + threading code. It basically just presents the generic code + with edges that may be suitable for jump threading. + + Unlike DOM, we do not iterate VRP if jump threading was successful. + While iterating may expose new opportunities for VRP, it is expected + those opportunities would be very limited and the compile time cost + to expose those opportunities would be significant. + + As jump threading opportunities are discovered, they are registered + for later realization. */ + +static void +identify_jump_threads (void) +{ + basic_block bb; + tree dummy; + + /* Ugh. When substituting values earlier in this pass we can + wipe the dominance information. So rebuild the dominator + information as we need it within the jump threading code. */ + calculate_dominance_info (CDI_DOMINATORS); + + /* We do not allow VRP information to be used for jump threading + across a back edge in the CFG. Otherwise it becomes too + difficult to avoid eliminating loop exit tests. Of course + EDGE_DFS_BACK is not accurate at this time so we have to + recompute it. */ + mark_dfs_back_edges (); + + /* Allocate our unwinder stack to unwind any temporary equivalences + that might be recorded. */ + stack = VEC_alloc (tree, heap, 20); + + /* To avoid lots of silly node creation, we create a single + conditional and just modify it in-place when attempting to + thread jumps. */ + dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL); + dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL); + + /* Walk through all the blocks finding those which present a + potential jump threading opportunity. We could set this up + as a dominator walker and record data during the walk, but + I doubt it's worth the effort for the classes of jump + threading opportunities we are trying to identify at this + point in compilation. */ + FOR_EACH_BB (bb) + { + tree last, cond; + + /* If the generic jump threading code does not find this block + interesting, then there is nothing to do. */ + if (! potentially_threadable_block (bb)) + continue; + + /* We only care about blocks ending in a COND_EXPR. While there + may be some value in handling SWITCH_EXPR here, I doubt it's + terribly important. */ + last = bsi_stmt (bsi_last (bb)); + if (TREE_CODE (last) != COND_EXPR) + continue; + + /* We're basically looking for any kind of conditional with + integral type arguments. */ + 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; + + /* We've got a block with multiple predecessors and multiple + successors which also ends in a suitable conditional. For + each predecessor, see if we can thread it to a specific + successor. */ + FOR_EACH_EDGE (e, ei, bb->preds) + { + /* Do not thread across back edges or abnormal edges + in the CFG. */ + if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) + continue; + + thread_across_edge (dummy, e, true, + &stack, + simplify_stmt_for_jump_threading); + } + } + } + + /* We do not actually update the CFG or SSA graphs at this point as + ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet + handle ASSERT_EXPRs gracefully. */ +} + +/* We identified all the jump threading opportunities earlier, but could + not transform the CFG at that time. This routine transforms the + CFG and arranges for the dominator tree to be rebuilt if necessary. + + Note the SSA graph update will occur during the normal TODO + processing by the pass manager. */ +static void +finalize_jump_threads (void) +{ + bool cfg_altered = false; + cfg_altered = thread_through_all_blocks (); + + /* If we threaded jumps, then we need to recompute the dominance + information, to safely do that we must clean up the CFG first. */ + if (cfg_altered) + { + free_dominance_info (CDI_DOMINATORS); + cleanup_tree_cfg (); + calculate_dominance_info (CDI_DOMINATORS); + } + VEC_free (tree, heap, stack); +} + + +/* Traverse all the blocks folding conditionals with known ranges. */ + +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"); + } + + /* We may have ended with ranges that have exactly one value. Those + values can be substituted as any other copy/const propagated + value using substitute_and_fold. */ + 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) + { + /* We found no single-valued ranges, don't waste time trying to + do single value substitution in substitute_and_fold. */ + free (single_val_range); + single_val_range = NULL; + } + + substitute_and_fold (single_val_range, true); + + /* We must identify jump threading opportunities before we release + the datastructures built by VRP. */ + identify_jump_threads (); + + /* Free allocated memory. */ + 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); + + /* So that we can distinguish between VRP data being available + and not available. */ + vr_value = NULL; +} + + +/* Main entry point to VRP (Value Range Propagation). This pass is + loosely based on J. R. C. Patterson, ``Accurate Static Branch + Prediction by Value Range Propagation,'' in SIGPLAN Conference on + Programming Language Design and Implementation, pp. 67-78, 1995. + Also available at http://citeseer.ist.psu.edu/patterson95accurate.html + + This is essentially an SSA-CCP pass modified to deal with ranges + instead of constants. + + While propagating ranges, we may find that two or more SSA name + have equivalent, though distinct ranges. For instance, + + 1 x_9 = p_3->a; + 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> + 3 if (p_4 == q_2) + 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; + 5 endif + 6 if (q_2) + + In the code above, pointer p_5 has range [q_2, q_2], but from the + code we can also determine that p_5 cannot be NULL and, if q_2 had + a non-varying range, p_5's range should also be compatible with it. + + These equivalences are created by two expressions: ASSERT_EXPR and + copy operations. Since p_5 is an assertion on p_4, and p_4 was the + result of another assertion, then we can use the fact that p_5 and + p_4 are equivalent when evaluating p_5's range. + + Together with value ranges, we also propagate these equivalences + between names so that we can take advantage of information from + multiple ranges when doing final replacement. Note that this + equivalency relation is transitive but not symmetric. + + In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we + cannot assert that q_2 is equivalent to p_5 because q_2 may be used + in contexts where that assertion does not hold (e.g., in line 6). + + TODO, the main difference between this pass and Patterson's is that + we do not propagate edge probabilities. We only compute whether + edges can be taken or not. That is, instead of having a spectrum + of jump probabilities between 0 and 1, we only deal with 0, 1 and + DON'T KNOW. In the future, it may be worthwhile to propagate + probabilities to aid branch prediction. */ + +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; + } + + /* ASSERT_EXPRs must be removed before finalizing jump threads + as finalizing jump threads calls the CFG cleanup code which + does not properly handle ASSERT_EXPRs. */ + remove_range_assertions (); + + /* If we exposed any new variables, go ahead and put them into + SSA form now, before we handle jump threading. This simplifies + interactions between rewriting of _DECL nodes into SSA form + and rewriting SSA_NAME nodes into SSA form after block + duplication and CFG manipulation. */ + 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", /* name */ + gate_vrp, /* gate */ + execute_vrp, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_VRP, /* tv_id */ + PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + PROP_smt_usage, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_cleanup_cfg + | TODO_ggc_collect + | TODO_verify_ssa + | TODO_dump_func + | TODO_update_ssa + | TODO_update_smt_usage, /* todo_flags_finish */ + 0 /* letter */ +}; |
