tree-vrp.c revision 267654
118334Speter/* Support routines for Value Range Propagation (VRP). 218334Speter Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. 318334Speter Contributed by Diego Novillo <dnovillo@redhat.com>. 418334Speter 518334SpeterThis file is part of GCC. 618334Speter 718334SpeterGCC is free software; you can redistribute it and/or modify 818334Speterit under the terms of the GNU General Public License as published by 918334Speterthe Free Software Foundation; either version 2, or (at your option) 1018334Speterany later version. 1118334Speter 1218334SpeterGCC is distributed in the hope that it will be useful, 1318334Speterbut WITHOUT ANY WARRANTY; without even the implied warranty of 1418334SpeterMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1518334SpeterGNU General Public License for more details. 1618334Speter 1718334SpeterYou should have received a copy of the GNU General Public License 1818334Speteralong with GCC; see the file COPYING. If not, write to 1918334Speterthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 2018334SpeterBoston, MA 02110-1301, USA. */ 2118334Speter 2218334Speter#include "config.h" 2318334Speter#include "system.h" 2418334Speter#include "coretypes.h" 2518334Speter#include "tm.h" 2618334Speter#include "ggc.h" 2718334Speter#include "flags.h" 2818334Speter#include "tree.h" 2918334Speter#include "basic-block.h" 3018334Speter#include "tree-flow.h" 3118334Speter#include "tree-pass.h" 3218334Speter#include "tree-dump.h" 3318334Speter#include "timevar.h" 3418334Speter#include "diagnostic.h" 3518334Speter#include "toplev.h" 3618334Speter#include "intl.h" 3718334Speter#include "cfgloop.h" 3818334Speter#include "tree-scalar-evolution.h" 3918334Speter#include "tree-ssa-propagate.h" 4018334Speter#include "tree-chrec.h" 4118334Speter 4218334Speter/* Set of SSA names found during the dominator traversal of a 4318334Speter sub-graph in find_assert_locations. */ 4418334Speterstatic sbitmap found_in_subgraph; 4518334Speter 4618334Speter/* Local functions. */ 4718334Speterstatic int compare_values (tree val1, tree val2); 4818334Speterstatic int compare_values_warnv (tree val1, tree val2, bool *); 4918334Speterstatic tree vrp_evaluate_conditional_warnv (tree, bool, bool *); 5018334Speter 5118334Speter/* Location information for ASSERT_EXPRs. Each instance of this 5218334Speter structure describes an ASSERT_EXPR for an SSA name. Since a single 5318334Speter SSA name may have more than one assertion associated with it, these 5418334Speter locations are kept in a linked list attached to the corresponding 5518334Speter SSA name. */ 5618334Speterstruct assert_locus_d 5718334Speter{ 5818334Speter /* Basic block where the assertion would be inserted. */ 5918334Speter basic_block bb; 6018334Speter 6118334Speter /* Some assertions need to be inserted on an edge (e.g., assertions 6218334Speter generated by COND_EXPRs). In those cases, BB will be NULL. */ 6318334Speter edge e; 6418334Speter 6518334Speter /* Pointer to the statement that generated this assertion. */ 6618334Speter block_stmt_iterator si; 6718334Speter 6818334Speter /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */ 6918334Speter enum tree_code comp_code; 7018334Speter 7118334Speter /* Value being compared against. */ 7218334Speter tree val; 7318334Speter 7418334Speter /* Next node in the linked list. */ 7518334Speter struct assert_locus_d *next; 7618334Speter}; 7718334Speter 7818334Spetertypedef struct assert_locus_d *assert_locus_t; 7918334Speter 8018334Speter/* If bit I is present, it means that SSA name N_i has a list of 8118334Speter assertions that should be inserted in the IL. */ 8218334Speterstatic bitmap need_assert_for; 8318334Speter 8418334Speter/* Array of locations lists where to insert assertions. ASSERTS_FOR[I] 8518334Speter holds a list of ASSERT_LOCUS_T nodes that describe where 8618334Speter ASSERT_EXPRs for SSA name N_I should be inserted. */ 8718334Speterstatic assert_locus_t *asserts_for; 8818334Speter 8918334Speter/* Set of blocks visited in find_assert_locations. Used to avoid 9018334Speter visiting the same block more than once. */ 9118334Speterstatic sbitmap blocks_visited; 9218334Speter 9318334Speter/* Value range array. After propagation, VR_VALUE[I] holds the range 9418334Speter of values that SSA name N_I may take. */ 9518334Speterstatic value_range_t **vr_value; 9618334Speter 9718334Speter 9818334Speter/* Return whether TYPE should use an overflow infinity distinct from 9918334Speter TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to 10018334Speter represent a signed overflow during VRP computations. An infinity 10118334Speter is distinct from a half-range, which will go from some number to 10218334Speter TYPE_{MIN,MAX}_VALUE. */ 10318334Speter 10418334Speterstatic inline bool 10518334Speterneeds_overflow_infinity (tree type) 10618334Speter{ 10718334Speter return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); 10818334Speter} 10918334Speter 11018334Speter/* Return whether TYPE can support our overflow infinity 11118334Speter representation: we use the TREE_OVERFLOW flag, which only exists 11218334Speter for constants. If TYPE doesn't support this, we don't optimize 11318334Speter cases which would require signed overflow--we drop them to 11418334Speter VARYING. */ 11518334Speter 11618334Speterstatic inline bool 11718334Spetersupports_overflow_infinity (tree type) 11818334Speter{ 11918334Speter#ifdef ENABLE_CHECKING 12018334Speter gcc_assert (needs_overflow_infinity (type)); 12118334Speter#endif 12218334Speter return (TYPE_MIN_VALUE (type) != NULL_TREE 12318334Speter && CONSTANT_CLASS_P (TYPE_MIN_VALUE (type)) 12418334Speter && TYPE_MAX_VALUE (type) != NULL_TREE 12518334Speter && CONSTANT_CLASS_P (TYPE_MAX_VALUE (type))); 12618334Speter} 12718334Speter 12818334Speter/* VAL is the maximum or minimum value of a type. Return a 12918334Speter corresponding overflow infinity. */ 13018334Speter 13118334Speterstatic inline tree 13218334Spetermake_overflow_infinity (tree val) 13318334Speter{ 13418334Speter#ifdef ENABLE_CHECKING 13518334Speter gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); 13618334Speter#endif 13718334Speter val = copy_node (val); 13818334Speter TREE_OVERFLOW (val) = 1; 13918334Speter return val; 14018334Speter} 14118334Speter 14218334Speter/* Return a negative overflow infinity for TYPE. */ 14318334Speter 14418334Speterstatic inline tree 14518334Speternegative_overflow_infinity (tree type) 14618334Speter{ 14718334Speter#ifdef ENABLE_CHECKING 14818334Speter gcc_assert (supports_overflow_infinity (type)); 14918334Speter#endif 15018334Speter return make_overflow_infinity (TYPE_MIN_VALUE (type)); 15118334Speter} 15218334Speter 15318334Speter/* Return a positive overflow infinity for TYPE. */ 15418334Speter 15518334Speterstatic inline tree 15618334Speterpositive_overflow_infinity (tree type) 15718334Speter{ 15818334Speter#ifdef ENABLE_CHECKING 15918334Speter gcc_assert (supports_overflow_infinity (type)); 16018334Speter#endif 16118334Speter return make_overflow_infinity (TYPE_MAX_VALUE (type)); 16218334Speter} 16318334Speter 16418334Speter/* Return whether VAL is a negative overflow infinity. */ 16518334Speter 16618334Speterstatic inline bool 16718334Speteris_negative_overflow_infinity (tree val) 16818334Speter{ 16918334Speter return (needs_overflow_infinity (TREE_TYPE (val)) 17018334Speter && CONSTANT_CLASS_P (val) 17118334Speter && TREE_OVERFLOW (val) 17218334Speter && operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 17318334Speter} 17418334Speter 17518334Speter/* Return whether VAL is a positive overflow infinity. */ 17618334Speter 17718334Speterstatic inline bool 17818334Speteris_positive_overflow_infinity (tree val) 17918334Speter{ 18018334Speter return (needs_overflow_infinity (TREE_TYPE (val)) 18118334Speter && CONSTANT_CLASS_P (val) 18218334Speter && TREE_OVERFLOW (val) 18318334Speter && operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)); 18418334Speter} 18518334Speter 18618334Speter/* Return whether VAL is a positive or negative overflow infinity. */ 18718334Speter 18818334Speterstatic inline bool 18918334Speteris_overflow_infinity (tree val) 19018334Speter{ 19118334Speter return (needs_overflow_infinity (TREE_TYPE (val)) 19218334Speter && CONSTANT_CLASS_P (val) 19318334Speter && TREE_OVERFLOW (val) 19418334Speter && (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0) 19518334Speter || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0))); 19618334Speter} 19718334Speter 19818334Speter/* If VAL is now an overflow infinity, return VAL. Otherwise, return 19918334Speter the same value with TREE_OVERFLOW clear. This can be used to avoid 20018334Speter confusing a regular value with an overflow value. */ 20118334Speter 20218334Speterstatic inline tree 20318334Speteravoid_overflow_infinity (tree val) 20418334Speter{ 20518334Speter if (!is_overflow_infinity (val)) 20618334Speter return val; 20718334Speter 20818334Speter if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)) 20918334Speter return TYPE_MAX_VALUE (TREE_TYPE (val)); 21018334Speter else 21118334Speter { 21218334Speter#ifdef ENABLE_CHECKING 21318334Speter gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 21418334Speter#endif 21518334Speter return TYPE_MIN_VALUE (TREE_TYPE (val)); 21618334Speter } 21718334Speter} 21818334Speter 21918334Speter 22018334Speter/* Return whether VAL is equal to the maximum value of its type. This 22118334Speter will be true for a positive overflow infinity. We can't do a 22218334Speter simple equality comparison with TYPE_MAX_VALUE because C typedefs 22318334Speter and Ada subtypes can produce types whose TYPE_MAX_VALUE is not == 22418334Speter to the integer constant with the same value in the type. */ 22518334Speter 22618334Speterstatic inline bool 22718334Spetervrp_val_is_max (tree val) 22818334Speter{ 22918334Speter tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val)); 23018334Speter 23118334Speter return (val == type_max 23218334Speter || (type_max != NULL_TREE 23318334Speter && operand_equal_p (val, type_max, 0))); 23418334Speter} 23518334Speter 23618334Speter/* Return whether VAL is equal to the minimum value of its type. This 23718334Speter will be true for a negative overflow infinity. */ 23818334Speter 23918334Speterstatic inline bool 24018334Spetervrp_val_is_min (tree val) 24118334Speter{ 24218334Speter tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val)); 24318334Speter 24418334Speter return (val == type_min 24518334Speter || (type_min != NULL_TREE 24618334Speter && operand_equal_p (val, type_min, 0))); 24718334Speter} 24818334Speter 24918334Speter 25018334Speter/* Return true if ARG is marked with the nonnull attribute in the 25118334Speter current function signature. */ 25218334Speter 25318334Speterstatic bool 25418334Speternonnull_arg_p (tree arg) 25518334Speter{ 25618334Speter tree t, attrs, fntype; 25718334Speter unsigned HOST_WIDE_INT arg_num; 25818334Speter 25918334Speter gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg))); 26018334Speter 26118334Speter /* The static chain decl is always non null. */ 26218334Speter if (arg == cfun->static_chain_decl) 26318334Speter return true; 26418334Speter 26518334Speter fntype = TREE_TYPE (current_function_decl); 26618334Speter attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype)); 26718334Speter 26818334Speter /* If "nonnull" wasn't specified, we know nothing about the argument. */ 26918334Speter if (attrs == NULL_TREE) 27018334Speter return false; 27118334Speter 27218334Speter /* If "nonnull" applies to all the arguments, then ARG is non-null. */ 27318334Speter if (TREE_VALUE (attrs) == NULL_TREE) 27418334Speter return true; 27518334Speter 27618334Speter /* Get the position number for ARG in the function signature. */ 27718334Speter for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); 27818334Speter t; 27918334Speter t = TREE_CHAIN (t), arg_num++) 28018334Speter { 28118334Speter if (t == arg) 28218334Speter break; 28318334Speter } 28418334Speter 28518334Speter gcc_assert (t == arg); 28618334Speter 28718334Speter /* Now see if ARG_NUM is mentioned in the nonnull list. */ 28818334Speter for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) 28918334Speter { 29018334Speter if (compare_tree_int (TREE_VALUE (t), arg_num) == 0) 29118334Speter return true; 29218334Speter } 29318334Speter 29418334Speter return false; 29518334Speter} 29618334Speter 29718334Speter 29818334Speter/* Set value range VR to {T, MIN, MAX, EQUIV}. */ 29918334Speter 30018334Speterstatic void 30118334Speterset_value_range (value_range_t *vr, enum value_range_type t, tree min, 30218334Speter tree max, bitmap equiv) 30318334Speter{ 30418334Speter#if defined ENABLE_CHECKING 30518334Speter /* Check the validity of the range. */ 30618334Speter if (t == VR_RANGE || t == VR_ANTI_RANGE) 30718334Speter { 30818334Speter int cmp; 30918334Speter 31018334Speter gcc_assert (min && max); 31118334Speter 31218334Speter if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) 31318334Speter gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max)); 31418334Speter 31518334Speter cmp = compare_values (min, max); 31618334Speter gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); 31718334Speter 31818334Speter if (needs_overflow_infinity (TREE_TYPE (min))) 31918334Speter gcc_assert (!is_overflow_infinity (min) 32018334Speter || !is_overflow_infinity (max)); 32118334Speter } 32218334Speter 32318334Speter if (t == VR_UNDEFINED || t == VR_VARYING) 32418334Speter gcc_assert (min == NULL_TREE && max == NULL_TREE); 32518334Speter 32618334Speter if (t == VR_UNDEFINED || t == VR_VARYING) 32718334Speter gcc_assert (equiv == NULL || bitmap_empty_p (equiv)); 32818334Speter#endif 32918334Speter 33018334Speter vr->type = t; 33118334Speter vr->min = min; 33218334Speter vr->max = max; 33318334Speter 33418334Speter /* Since updating the equivalence set involves deep copying the 33518334Speter bitmaps, only do it if absolutely necessary. */ 33618334Speter if (vr->equiv == NULL) 33718334Speter vr->equiv = BITMAP_ALLOC (NULL); 33818334Speter 33918334Speter if (equiv != vr->equiv) 34018334Speter { 34118334Speter if (equiv && !bitmap_empty_p (equiv)) 34218334Speter bitmap_copy (vr->equiv, equiv); 34318334Speter else 34418334Speter bitmap_clear (vr->equiv); 34518334Speter } 34618334Speter} 34718334Speter 34818334Speter 34918334Speter/* Copy value range FROM into value range TO. */ 35018334Speter 35118334Speterstatic inline void 35218334Spetercopy_value_range (value_range_t *to, value_range_t *from) 35318334Speter{ 35418334Speter set_value_range (to, from->type, from->min, from->max, from->equiv); 35518334Speter} 35618334Speter 35718334Speter 35818334Speter/* Set value range VR to VR_VARYING. */ 35918334Speter 36018334Speterstatic inline void 36118334Speterset_value_range_to_varying (value_range_t *vr) 36218334Speter{ 36318334Speter vr->type = VR_VARYING; 36418334Speter vr->min = vr->max = NULL_TREE; 36518334Speter if (vr->equiv) 36618334Speter bitmap_clear (vr->equiv); 36718334Speter} 36818334Speter 36918334Speter/* Set value range VR to a single value. This function is only called 37018334Speter with values we get from statements, and exists to clear the 37118334Speter TREE_OVERFLOW flag so that we don't think we have an overflow 37218334Speter infinity when we shouldn't. */ 37318334Speter 37418334Speterstatic inline void 37518334Speterset_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) 37618334Speter{ 37718334Speter gcc_assert (is_gimple_min_invariant (val)); 37818334Speter val = avoid_overflow_infinity (val); 37918334Speter set_value_range (vr, VR_RANGE, val, val, equiv); 38018334Speter} 38118334Speter 38218334Speter/* Set value range VR to a non-negative range of type TYPE. 38318334Speter OVERFLOW_INFINITY indicates whether to use a overflow infinity 38418334Speter rather than TYPE_MAX_VALUE; this should be true if we determine 38518334Speter that the range is nonnegative based on the assumption that signed 38618334Speter overflow does not occur. */ 38718334Speter 38818334Speterstatic inline void 38918334Speterset_value_range_to_nonnegative (value_range_t *vr, tree type, 39018334Speter bool overflow_infinity) 39118334Speter{ 39218334Speter tree zero; 39318334Speter 39418334Speter if (overflow_infinity && !supports_overflow_infinity (type)) 39518334Speter { 39618334Speter set_value_range_to_varying (vr); 39718334Speter return; 39818334Speter } 39918334Speter 40018334Speter zero = build_int_cst (type, 0); 40118334Speter set_value_range (vr, VR_RANGE, zero, 40218334Speter (overflow_infinity 40318334Speter ? positive_overflow_infinity (type) 40418334Speter : TYPE_MAX_VALUE (type)), 40518334Speter vr->equiv); 40618334Speter} 40718334Speter 40818334Speter/* Set value range VR to a non-NULL range of type TYPE. */ 40918334Speter 41018334Speterstatic inline void 41118334Speterset_value_range_to_nonnull (value_range_t *vr, tree type) 41218334Speter{ 41318334Speter tree zero = build_int_cst (type, 0); 41418334Speter set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); 41518334Speter} 41618334Speter 41718334Speter 41818334Speter/* Set value range VR to a NULL range of type TYPE. */ 41918334Speter 42018334Speterstatic inline void 42118334Speterset_value_range_to_null (value_range_t *vr, tree type) 42218334Speter{ 42318334Speter set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); 42418334Speter} 42518334Speter 42618334Speter 42718334Speter/* Set value range VR to VR_UNDEFINED. */ 42818334Speter 42918334Speterstatic inline void 43018334Speterset_value_range_to_undefined (value_range_t *vr) 43118334Speter{ 43218334Speter vr->type = VR_UNDEFINED; 43318334Speter vr->min = vr->max = NULL_TREE; 43418334Speter if (vr->equiv) 43518334Speter bitmap_clear (vr->equiv); 43618334Speter} 43718334Speter 43818334Speter 43918334Speter/* Return value range information for VAR. 44018334Speter 44118334Speter If we have no values ranges recorded (ie, VRP is not running), then 44218334Speter return NULL. Otherwise create an empty range if none existed for VAR. */ 44318334Speter 44418334Speterstatic value_range_t * 44518334Speterget_value_range (tree var) 44618334Speter{ 44718334Speter value_range_t *vr; 44818334Speter tree sym; 44918334Speter unsigned ver = SSA_NAME_VERSION (var); 45018334Speter 45118334Speter /* If we have no recorded ranges, then return NULL. */ 45218334Speter if (! vr_value) 45318334Speter return NULL; 45418334Speter 45518334Speter vr = vr_value[ver]; 45618334Speter if (vr) 45718334Speter return vr; 45818334Speter 45918334Speter /* Create a default value range. */ 46018334Speter vr_value[ver] = vr = XNEW (value_range_t); 46118334Speter memset (vr, 0, sizeof (*vr)); 46218334Speter 46318334Speter /* Allocate an equivalence set. */ 46418334Speter vr->equiv = BITMAP_ALLOC (NULL); 46518334Speter 46618334Speter /* If VAR is a default definition, the variable can take any value 46718334Speter in VAR's type. */ 46818334Speter sym = SSA_NAME_VAR (var); 46918334Speter if (var == default_def (sym)) 47018334Speter { 47118334Speter /* Try to use the "nonnull" attribute to create ~[0, 0] 47218334Speter anti-ranges for pointers. Note that this is only valid with 47318334Speter default definitions of PARM_DECLs. */ 47418334Speter if (TREE_CODE (sym) == PARM_DECL 47518334Speter && POINTER_TYPE_P (TREE_TYPE (sym)) 47618334Speter && nonnull_arg_p (sym)) 47718334Speter set_value_range_to_nonnull (vr, TREE_TYPE (sym)); 47818334Speter else 47918334Speter set_value_range_to_varying (vr); 48018334Speter } 48118334Speter 48218334Speter return vr; 48318334Speter} 48418334Speter 48518334Speter/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ 48618334Speter 48718334Speterstatic inline bool 48818334Spetervrp_operand_equal_p (tree val1, tree val2) 48918334Speter{ 49018334Speter if (val1 == val2) 49118334Speter return true; 49218334Speter if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) 49318334Speter return false; 49418334Speter if (is_overflow_infinity (val1)) 49518334Speter return is_overflow_infinity (val2); 49618334Speter return true; 49718334Speter} 49818334Speter 49918334Speter/* Return true, if the bitmaps B1 and B2 are equal. */ 50018334Speter 50118334Speterstatic inline bool 50218334Spetervrp_bitmap_equal_p (bitmap b1, bitmap b2) 50318334Speter{ 50418334Speter return (b1 == b2 50518334Speter || (b1 && b2 50618334Speter && bitmap_equal_p (b1, b2))); 50718334Speter} 50818334Speter 50918334Speter/* Update the value range and equivalence set for variable VAR to 51018334Speter NEW_VR. Return true if NEW_VR is different from VAR's previous 51118334Speter value. 51218334Speter 51318334Speter NOTE: This function assumes that NEW_VR is a temporary value range 51418334Speter object created for the sole purpose of updating VAR's range. The 51518334Speter storage used by the equivalence set from NEW_VR will be freed by 51618334Speter this function. Do not call update_value_range when NEW_VR 51718334Speter is the range object associated with another SSA name. */ 51818334Speter 51918334Speterstatic inline bool 52018334Speterupdate_value_range (tree var, value_range_t *new_vr) 52118334Speter{ 52218334Speter value_range_t *old_vr; 52318334Speter bool is_new; 52418334Speter 52518334Speter /* Update the value range, if necessary. */ 52618334Speter old_vr = get_value_range (var); 52718334Speter is_new = old_vr->type != new_vr->type 52818334Speter || !vrp_operand_equal_p (old_vr->min, new_vr->min) 52918334Speter || !vrp_operand_equal_p (old_vr->max, new_vr->max) 53018334Speter || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv); 53118334Speter 53218334Speter if (is_new) 53318334Speter set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, 53418334Speter new_vr->equiv); 53518334Speter 53618334Speter BITMAP_FREE (new_vr->equiv); 53718334Speter new_vr->equiv = NULL; 53818334Speter 53918334Speter return is_new; 54018334Speter} 54118334Speter 54218334Speter 54318334Speter/* Add VAR and VAR's equivalence set to EQUIV. */ 54418334Speter 54518334Speterstatic void 54618334Speteradd_equivalence (bitmap equiv, tree var) 54718334Speter{ 54818334Speter unsigned ver = SSA_NAME_VERSION (var); 54918334Speter value_range_t *vr = vr_value[ver]; 55018334Speter 55118334Speter bitmap_set_bit (equiv, ver); 55218334Speter if (vr && vr->equiv) 55318334Speter bitmap_ior_into (equiv, vr->equiv); 55418334Speter} 55518334Speter 55618334Speter 55718334Speter/* Return true if VR is ~[0, 0]. */ 55818334Speter 55918334Speterstatic inline bool 56018334Speterrange_is_nonnull (value_range_t *vr) 56118334Speter{ 56218334Speter return vr->type == VR_ANTI_RANGE 56318334Speter && integer_zerop (vr->min) 56418334Speter && integer_zerop (vr->max); 56518334Speter} 56618334Speter 56718334Speter 56818334Speter/* Return true if VR is [0, 0]. */ 56918334Speter 57018334Speterstatic inline bool 57118334Speterrange_is_null (value_range_t *vr) 57218334Speter{ 57318334Speter return vr->type == VR_RANGE 57418334Speter && integer_zerop (vr->min) 57518334Speter && integer_zerop (vr->max); 57618334Speter} 57718334Speter 57818334Speter 57918334Speter/* Return true if value range VR involves at least one symbol. */ 58018334Speter 58118334Speterstatic inline bool 58218334Spetersymbolic_range_p (value_range_t *vr) 58318334Speter{ 58418334Speter return (!is_gimple_min_invariant (vr->min) 58518334Speter || !is_gimple_min_invariant (vr->max)); 58618334Speter} 58718334Speter 58818334Speter/* Return true if value range VR uses a overflow infinity. */ 58918334Speter 59018334Speterstatic inline bool 59118334Speteroverflow_infinity_range_p (value_range_t *vr) 59218334Speter{ 59318334Speter return (vr->type == VR_RANGE 59418334Speter && (is_overflow_infinity (vr->min) 59518334Speter || is_overflow_infinity (vr->max))); 59618334Speter} 59718334Speter 59818334Speter/* Return false if we can not make a valid comparison based on VR; 59918334Speter this will be the case if it uses an overflow infinity and overflow 60018334Speter is not undefined (i.e., -fno-strict-overflow is in effect). 60118334Speter Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR 60218334Speter uses an overflow infinity. */ 60318334Speter 60418334Speterstatic bool 60518334Speterusable_range_p (value_range_t *vr, bool *strict_overflow_p) 60618334Speter{ 60718334Speter gcc_assert (vr->type == VR_RANGE); 60818334Speter if (is_overflow_infinity (vr->min)) 60918334Speter { 61018334Speter *strict_overflow_p = true; 61118334Speter if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min))) 61218334Speter return false; 61318334Speter } 61418334Speter if (is_overflow_infinity (vr->max)) 61518334Speter { 61618334Speter *strict_overflow_p = true; 61718334Speter if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max))) 61818334Speter return false; 61918334Speter } 62018334Speter return true; 62118334Speter} 62218334Speter 62318334Speter 62418334Speter/* Like tree_expr_nonnegative_warnv_p, but this function uses value 62518334Speter ranges obtained so far. */ 62618334Speter 62718334Speterstatic bool 62818334Spetervrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p) 62918334Speter{ 63018334Speter return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p); 63118334Speter} 63218334Speter 63318334Speter/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges 63418334Speter obtained so far. */ 63518334Speter 63618334Speterstatic bool 63718334Spetervrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p) 63818334Speter{ 63918334Speter if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p)) 64018334Speter return true; 64118334Speter 64218334Speter /* If we have an expression of the form &X->a, then the expression 64318334Speter is nonnull if X is nonnull. */ 64418334Speter if (TREE_CODE (expr) == ADDR_EXPR) 64518334Speter { 64618334Speter tree base = get_base_address (TREE_OPERAND (expr, 0)); 64718334Speter 64818334Speter if (base != NULL_TREE 64918334Speter && TREE_CODE (base) == INDIRECT_REF 65018334Speter && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 65118334Speter { 65218334Speter value_range_t *vr = get_value_range (TREE_OPERAND (base, 0)); 65318334Speter if (range_is_nonnull (vr)) 65418334Speter return true; 65518334Speter } 65618334Speter } 65718334Speter 65818334Speter return false; 65918334Speter} 66018334Speter 66118334Speter/* Returns true if EXPR is a valid value (as expected by compare_values) -- 66218334Speter a gimple invariant, or SSA_NAME +- CST. */ 66318334Speter 66418334Speterstatic bool 66518334Spetervalid_value_p (tree expr) 66618334Speter{ 66718334Speter if (TREE_CODE (expr) == SSA_NAME) 66818334Speter return true; 66918334Speter 67018334Speter if (TREE_CODE (expr) == PLUS_EXPR 67118334Speter || TREE_CODE (expr) == MINUS_EXPR) 67218334Speter return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME 67318334Speter && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST); 67418334Speter 67518334Speter return is_gimple_min_invariant (expr); 67618334Speter} 67718334Speter 67818334Speter/* Compare two values VAL1 and VAL2. Return 67918334Speter 68018334Speter -2 if VAL1 and VAL2 cannot be compared at compile-time, 68118334Speter -1 if VAL1 < VAL2, 68218334Speter 0 if VAL1 == VAL2, 68318334Speter +1 if VAL1 > VAL2, and 68418334Speter +2 if VAL1 != VAL2 68518334Speter 68618334Speter This is similar to tree_int_cst_compare but supports pointer values 68718334Speter and values that cannot be compared at compile time. 68818334Speter 68918334Speter If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to 69018334Speter true if the return value is only valid if we assume that signed 69118334Speter overflow is undefined. */ 69218334Speter 69318334Speterstatic int 69418334Spetercompare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) 69518334Speter{ 69618334Speter if (val1 == val2) 69718334Speter return 0; 69818334Speter 69918334Speter /* Below we rely on the fact that VAL1 and VAL2 are both pointers or 70018334Speter both integers. */ 70118334Speter gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) 70218334Speter == POINTER_TYPE_P (TREE_TYPE (val2))); 70318334Speter 70418334Speter if ((TREE_CODE (val1) == SSA_NAME 70518334Speter || TREE_CODE (val1) == PLUS_EXPR 70618334Speter || TREE_CODE (val1) == MINUS_EXPR) 70718334Speter && (TREE_CODE (val2) == SSA_NAME 70818334Speter || TREE_CODE (val2) == PLUS_EXPR 70918334Speter || TREE_CODE (val2) == MINUS_EXPR)) 71018334Speter { 71118334Speter tree n1, c1, n2, c2; 71218334Speter enum tree_code code1, code2; 71318334Speter 71418334Speter /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', 71518334Speter return -1 or +1 accordingly. If VAL1 and VAL2 don't use the 71618334Speter same name, return -2. */ 71718334Speter if (TREE_CODE (val1) == SSA_NAME) 71818334Speter { 71918334Speter code1 = SSA_NAME; 72018334Speter n1 = val1; 72118334Speter c1 = NULL_TREE; 72218334Speter } 72318334Speter else 72418334Speter { 72518334Speter code1 = TREE_CODE (val1); 72618334Speter n1 = TREE_OPERAND (val1, 0); 72718334Speter c1 = TREE_OPERAND (val1, 1); 72818334Speter if (tree_int_cst_sgn (c1) == -1) 72918334Speter { 73018334Speter if (is_negative_overflow_infinity (c1)) 73118334Speter return -2; 73218334Speter c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1); 73318334Speter if (!c1) 73418334Speter return -2; 73518334Speter code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 73618334Speter } 73718334Speter } 73818334Speter 73918334Speter if (TREE_CODE (val2) == SSA_NAME) 74018334Speter { 74118334Speter code2 = SSA_NAME; 74218334Speter n2 = val2; 74318334Speter c2 = NULL_TREE; 74418334Speter } 74518334Speter else 74618334Speter { 74718334Speter code2 = TREE_CODE (val2); 74818334Speter n2 = TREE_OPERAND (val2, 0); 74918334Speter c2 = TREE_OPERAND (val2, 1); 75018334Speter if (tree_int_cst_sgn (c2) == -1) 75118334Speter { 75218334Speter if (is_negative_overflow_infinity (c2)) 75318334Speter return -2; 75418334Speter c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2); 75518334Speter if (!c2) 75618334Speter return -2; 75718334Speter code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 75818334Speter } 75918334Speter } 76018334Speter 76118334Speter /* Both values must use the same name. */ 76218334Speter if (n1 != n2) 76318334Speter return -2; 76418334Speter 76518334Speter if (code1 == SSA_NAME 76618334Speter && code2 == SSA_NAME) 76718334Speter /* NAME == NAME */ 76818334Speter return 0; 76918334Speter 77018334Speter /* If overflow is defined we cannot simplify more. */ 77118334Speter if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) 77218334Speter return -2; 77318334Speter 77418334Speter if (strict_overflow_p != NULL 77518334Speter && (code1 == SSA_NAME || !TREE_NO_WARNING (val1)) 77618334Speter && (code2 == SSA_NAME || !TREE_NO_WARNING (val2))) 77718334Speter *strict_overflow_p = true; 77818334Speter 77918334Speter if (code1 == SSA_NAME) 78018334Speter { 78118334Speter if (code2 == PLUS_EXPR) 78218334Speter /* NAME < NAME + CST */ 78318334Speter return -1; 78418334Speter else if (code2 == MINUS_EXPR) 78518334Speter /* NAME > NAME - CST */ 78618334Speter return 1; 78718334Speter } 78818334Speter else if (code1 == PLUS_EXPR) 78918334Speter { 79018334Speter if (code2 == SSA_NAME) 79118334Speter /* NAME + CST > NAME */ 79218334Speter return 1; 79318334Speter else if (code2 == PLUS_EXPR) 79418334Speter /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ 79518334Speter return compare_values_warnv (c1, c2, strict_overflow_p); 79618334Speter else if (code2 == MINUS_EXPR) 79718334Speter /* NAME + CST1 > NAME - CST2 */ 79818334Speter return 1; 79918334Speter } 80018334Speter else if (code1 == MINUS_EXPR) 80118334Speter { 80218334Speter if (code2 == SSA_NAME) 80318334Speter /* NAME - CST < NAME */ 80418334Speter return -1; 80518334Speter else if (code2 == PLUS_EXPR) 80618334Speter /* NAME - CST1 < NAME + CST2 */ 80718334Speter return -1; 80818334Speter else if (code2 == MINUS_EXPR) 80918334Speter /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that 81018334Speter C1 and C2 are swapped in the call to compare_values. */ 81118334Speter return compare_values_warnv (c2, c1, strict_overflow_p); 81218334Speter } 81318334Speter 81418334Speter gcc_unreachable (); 81518334Speter } 81618334Speter 81718334Speter /* We cannot compare non-constants. */ 81818334Speter if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)) 81918334Speter return -2; 82018334Speter 82118334Speter if (!POINTER_TYPE_P (TREE_TYPE (val1))) 82218334Speter { 82318334Speter /* We cannot compare overflowed values, except for overflow 82418334Speter infinities. */ 82518334Speter if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) 82618334Speter { 82718334Speter if (strict_overflow_p != NULL) 82818334Speter *strict_overflow_p = true; 82918334Speter if (is_negative_overflow_infinity (val1)) 83018334Speter return is_negative_overflow_infinity (val2) ? 0 : -1; 83118334Speter else if (is_negative_overflow_infinity (val2)) 83218334Speter return 1; 83318334Speter else if (is_positive_overflow_infinity (val1)) 83418334Speter return is_positive_overflow_infinity (val2) ? 0 : 1; 83518334Speter else if (is_positive_overflow_infinity (val2)) 83618334Speter return -1; 83718334Speter return -2; 83818334Speter } 83918334Speter 84018334Speter return tree_int_cst_compare (val1, val2); 84118334Speter } 84218334Speter else 84318334Speter { 84418334Speter tree t; 84518334Speter 84618334Speter /* First see if VAL1 and VAL2 are not the same. */ 84718334Speter if (val1 == val2 || operand_equal_p (val1, val2, 0)) 84818334Speter return 0; 84918334Speter 85018334Speter /* If VAL1 is a lower address than VAL2, return -1. */ 85118334Speter t = fold_binary (LT_EXPR, boolean_type_node, val1, val2); 85218334Speter if (t == boolean_true_node) 85318334Speter return -1; 85418334Speter 85518334Speter /* If VAL1 is a higher address than VAL2, return +1. */ 85618334Speter t = fold_binary (GT_EXPR, boolean_type_node, val1, val2); 85718334Speter if (t == boolean_true_node) 85818334Speter return 1; 85918334Speter 86018334Speter /* If VAL1 is different than VAL2, return +2. */ 86118334Speter t = fold_binary (NE_EXPR, boolean_type_node, val1, val2); 86218334Speter if (t == boolean_true_node) 86318334Speter return 2; 86418334Speter 86518334Speter return -2; 86618334Speter } 86718334Speter} 86818334Speter 86918334Speter/* Compare values like compare_values_warnv, but treat comparisons of 87018334Speter nonconstants which rely on undefined overflow as incomparable. */ 87118334Speter 87218334Speterstatic int 87318334Spetercompare_values (tree val1, tree val2) 87418334Speter{ 87518334Speter bool sop; 87618334Speter int ret; 87718334Speter 87818334Speter sop = false; 87918334Speter ret = compare_values_warnv (val1, val2, &sop); 88018334Speter if (sop 88118334Speter && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))) 88218334Speter ret = -2; 88318334Speter return ret; 88418334Speter} 88518334Speter 88618334Speter 88718334Speter/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), 88818334Speter 0 if VAL is not inside VR, 88918334Speter -2 if we cannot tell either way. 89018334Speter 89118334Speter FIXME, the current semantics of this functions are a bit quirky 89218334Speter when taken in the context of VRP. In here we do not care 89318334Speter about VR's type. If VR is the anti-range ~[3, 5] the call 89418334Speter value_inside_range (4, VR) will return 1. 89518334Speter 89618334Speter This is counter-intuitive in a strict sense, but the callers 89718334Speter currently expect this. They are calling the function 89818334Speter merely to determine whether VR->MIN <= VAL <= VR->MAX. The 89918334Speter callers are applying the VR_RANGE/VR_ANTI_RANGE semantics 90018334Speter themselves. 90118334Speter 90218334Speter This also applies to value_ranges_intersect_p and 90318334Speter range_includes_zero_p. The semantics of VR_RANGE and 90418334Speter VR_ANTI_RANGE should be encoded here, but that also means 90518334Speter adapting the users of these functions to the new semantics. */ 90618334Speter 90718334Speterstatic inline int 90818334Spetervalue_inside_range (tree val, value_range_t *vr) 90918334Speter{ 91018334Speter tree cmp1, cmp2; 91118334Speter 91218334Speter fold_defer_overflow_warnings (); 91318334Speter 91418334Speter cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min); 91518334Speter if (!cmp1) 91618334Speter { 91718334Speter fold_undefer_and_ignore_overflow_warnings (); 91818334Speter return -2; 91918334Speter } 92018334Speter 92118334Speter cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max); 92218334Speter 92318334Speter fold_undefer_and_ignore_overflow_warnings (); 92418334Speter 92518334Speter if (!cmp2) 92618334Speter return -2; 92718334Speter 92818334Speter return cmp1 == boolean_true_node && cmp2 == boolean_true_node; 92918334Speter} 93018334Speter 93118334Speter 93218334Speter/* Return true if value ranges VR0 and VR1 have a non-empty 93318334Speter intersection. */ 93418334Speter 93518334Speterstatic inline bool 93618334Spetervalue_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1) 93718334Speter{ 93818334Speter return (value_inside_range (vr1->min, vr0) == 1 93918334Speter || value_inside_range (vr1->max, vr0) == 1 94018334Speter || value_inside_range (vr0->min, vr1) == 1 94118334Speter || value_inside_range (vr0->max, vr1) == 1); 94218334Speter} 94318334Speter 94418334Speter 94518334Speter/* Return true if VR includes the value zero, false otherwise. FIXME, 94618334Speter currently this will return false for an anti-range like ~[-4, 3]. 94718334Speter This will be wrong when the semantics of value_inside_range are 94818334Speter modified (currently the users of this function expect these 94918334Speter semantics). */ 95018334Speter 95118334Speterstatic inline bool 95218334Speterrange_includes_zero_p (value_range_t *vr) 95318334Speter{ 95418334Speter tree zero; 95518334Speter 95618334Speter gcc_assert (vr->type != VR_UNDEFINED 95718334Speter && vr->type != VR_VARYING 95818334Speter && !symbolic_range_p (vr)); 95918334Speter 96018334Speter zero = build_int_cst (TREE_TYPE (vr->min), 0); 96118334Speter return (value_inside_range (zero, vr) == 1); 96218334Speter} 96318334Speter 96418334Speter/* Return true if T, an SSA_NAME, is known to be nonnegative. Return 96518334Speter false otherwise or if no value range information is available. */ 96618334Speter 96718334Speterbool 96818334Speterssa_name_nonnegative_p (tree t) 96918334Speter{ 97018334Speter value_range_t *vr = get_value_range (t); 97118334Speter 97218334Speter if (!vr) 97318334Speter return false; 97418334Speter 97518334Speter /* Testing for VR_ANTI_RANGE is not useful here as any anti-range 97618334Speter which would return a useful value should be encoded as a VR_RANGE. */ 97718334Speter if (vr->type == VR_RANGE) 97818334Speter { 97918334Speter int result = compare_values (vr->min, integer_zero_node); 98018334Speter 98118334Speter return (result == 0 || result == 1); 98218334Speter } 98318334Speter return false; 98418334Speter} 98518334Speter 98618334Speter/* Return true if T, an SSA_NAME, is known to be nonzero. Return 98718334Speter false otherwise or if no value range information is available. */ 98818334Speter 98918334Speterbool 99018334Speterssa_name_nonzero_p (tree t) 99118334Speter{ 99218334Speter value_range_t *vr = get_value_range (t); 99318334Speter 99418334Speter if (!vr) 99518334Speter return false; 99618334Speter 99718334Speter /* A VR_RANGE which does not include zero is a nonzero value. */ 99818334Speter if (vr->type == VR_RANGE && !symbolic_range_p (vr)) 99918334Speter return ! range_includes_zero_p (vr); 100018334Speter 100118334Speter /* A VR_ANTI_RANGE which does include zero is a nonzero value. */ 100218334Speter if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr)) 100318334Speter return range_includes_zero_p (vr); 100418334Speter 100518334Speter return false; 100618334Speter} 100718334Speter 100818334Speter 100918334Speter/* Extract value range information from an ASSERT_EXPR EXPR and store 101018334Speter it in *VR_P. */ 101118334Speter 101218334Speterstatic void 101318334Speterextract_range_from_assert (value_range_t *vr_p, tree expr) 101418334Speter{ 101518334Speter tree var, cond, limit, min, max, type; 101618334Speter value_range_t *var_vr, *limit_vr; 101718334Speter enum tree_code cond_code; 101818334Speter 101918334Speter var = ASSERT_EXPR_VAR (expr); 102018334Speter cond = ASSERT_EXPR_COND (expr); 102118334Speter 102218334Speter gcc_assert (COMPARISON_CLASS_P (cond)); 102318334Speter 102418334Speter /* Find VAR in the ASSERT_EXPR conditional. */ 102518334Speter if (var == TREE_OPERAND (cond, 0)) 102618334Speter { 102718334Speter /* If the predicate is of the form VAR COMP LIMIT, then we just 102818334Speter take LIMIT from the RHS and use the same comparison code. */ 102918334Speter limit = TREE_OPERAND (cond, 1); 103018334Speter cond_code = TREE_CODE (cond); 103118334Speter } 103218334Speter else 103318334Speter { 103418334Speter /* If the predicate is of the form LIMIT COMP VAR, then we need 103518334Speter to flip around the comparison code to create the proper range 103618334Speter for VAR. */ 103718334Speter limit = TREE_OPERAND (cond, 0); 103818334Speter cond_code = swap_tree_comparison (TREE_CODE (cond)); 103918334Speter } 104018334Speter 104118334Speter limit = avoid_overflow_infinity (limit); 104218334Speter 104318334Speter type = TREE_TYPE (limit); 104418334Speter gcc_assert (limit != var); 104518334Speter 104618334Speter /* For pointer arithmetic, we only keep track of pointer equality 104718334Speter and inequality. */ 104818334Speter if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) 104918334Speter { 105018334Speter set_value_range_to_varying (vr_p); 105118334Speter return; 105218334Speter } 105318334Speter 105418334Speter /* If LIMIT is another SSA name and LIMIT has a range of its own, 105518334Speter try to use LIMIT's range to avoid creating symbolic ranges 105618334Speter unnecessarily. */ 105718334Speter limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; 105818334Speter 105918334Speter /* LIMIT's range is only interesting if it has any useful information. */ 106018334Speter if (limit_vr 106118334Speter && (limit_vr->type == VR_UNDEFINED 106218334Speter || limit_vr->type == VR_VARYING 106318334Speter || symbolic_range_p (limit_vr))) 106418334Speter limit_vr = NULL; 106518334Speter 106618334Speter /* Initially, the new range has the same set of equivalences of 106718334Speter VAR's range. This will be revised before returning the final 106818334Speter value. Since assertions may be chained via mutually exclusive 106918334Speter predicates, we will need to trim the set of equivalences before 107018334Speter we are done. */ 107118334Speter gcc_assert (vr_p->equiv == NULL); 107218334Speter vr_p->equiv = BITMAP_ALLOC (NULL); 107318334Speter add_equivalence (vr_p->equiv, var); 107418334Speter 107518334Speter /* Extract a new range based on the asserted comparison for VAR and 107618334Speter LIMIT's value range. Notice that if LIMIT has an anti-range, we 107718334Speter will only use it for equality comparisons (EQ_EXPR). For any 107818334Speter other kind of assertion, we cannot derive a range from LIMIT's 107918334Speter anti-range that can be used to describe the new range. For 108018334Speter instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], 108118334Speter then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is 108218334Speter no single range for x_2 that could describe LE_EXPR, so we might 108318334Speter as well build the range [b_4, +INF] for it. */ 108418334Speter if (cond_code == EQ_EXPR) 108518334Speter { 108618334Speter enum value_range_type range_type; 108718334Speter 108818334Speter if (limit_vr) 108918334Speter { 109018334Speter range_type = limit_vr->type; 109118334Speter min = limit_vr->min; 109218334Speter max = limit_vr->max; 109318334Speter } 109418334Speter else 109518334Speter { 109618334Speter range_type = VR_RANGE; 109718334Speter min = limit; 109818334Speter max = limit; 109918334Speter } 110018334Speter 110118334Speter set_value_range (vr_p, range_type, min, max, vr_p->equiv); 110218334Speter 110318334Speter /* When asserting the equality VAR == LIMIT and LIMIT is another 110418334Speter SSA name, the new range will also inherit the equivalence set 110518334Speter from LIMIT. */ 110618334Speter if (TREE_CODE (limit) == SSA_NAME) 110718334Speter add_equivalence (vr_p->equiv, limit); 110818334Speter } 110918334Speter else if (cond_code == NE_EXPR) 111018334Speter { 111118334Speter /* As described above, when LIMIT's range is an anti-range and 111218334Speter this assertion is an inequality (NE_EXPR), then we cannot 111318334Speter derive anything from the anti-range. For instance, if 111418334Speter LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does 111518334Speter not imply that VAR's range is [0, 0]. So, in the case of 111618334Speter anti-ranges, we just assert the inequality using LIMIT and 111718334Speter not its anti-range. 111818334Speter 111918334Speter If LIMIT_VR is a range, we can only use it to build a new 112018334Speter anti-range if LIMIT_VR is a single-valued range. For 112118334Speter instance, if LIMIT_VR is [0, 1], the predicate 112218334Speter VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. 112318334Speter Rather, it means that for value 0 VAR should be ~[0, 0] 112418334Speter and for value 1, VAR should be ~[1, 1]. We cannot 112518334Speter represent these ranges. 112618334Speter 112718334Speter The only situation in which we can build a valid 112818334Speter anti-range is when LIMIT_VR is a single-valued range 112918334Speter (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, 113018334Speter build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ 113118334Speter if (limit_vr 113218334Speter && limit_vr->type == VR_RANGE 113318334Speter && compare_values (limit_vr->min, limit_vr->max) == 0) 113418334Speter { 113518334Speter min = limit_vr->min; 113618334Speter max = limit_vr->max; 113718334Speter } 113818334Speter else 113918334Speter { 114018334Speter /* In any other case, we cannot use LIMIT's range to build a 114118334Speter valid anti-range. */ 114218334Speter min = max = limit; 114318334Speter } 114418334Speter 114518334Speter /* If MIN and MAX cover the whole range for their type, then 114618334Speter just use the original LIMIT. */ 114718334Speter if (INTEGRAL_TYPE_P (type) 114818334Speter && vrp_val_is_min (min) 114918334Speter && vrp_val_is_max (max)) 115018334Speter min = max = limit; 115118334Speter 115218334Speter set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); 115318334Speter } 115418334Speter else if (cond_code == LE_EXPR || cond_code == LT_EXPR) 115518334Speter { 115618334Speter min = TYPE_MIN_VALUE (type); 115718334Speter 115818334Speter if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 115918334Speter max = limit; 116018334Speter else 116118334Speter { 116218334Speter /* If LIMIT_VR is of the form [N1, N2], we need to build the 116318334Speter range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for 116418334Speter LT_EXPR. */ 116518334Speter max = limit_vr->max; 116618334Speter } 116718334Speter 116818334Speter /* If the maximum value forces us to be out of bounds, simply punt. 116918334Speter It would be pointless to try and do anything more since this 117018334Speter all should be optimized away above us. */ 117118334Speter if ((cond_code == LT_EXPR 117218334Speter && compare_values (max, min) == 0) 117318334Speter || is_overflow_infinity (max)) 117418334Speter set_value_range_to_varying (vr_p); 117518334Speter else 117618334Speter { 117718334Speter /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ 117818334Speter if (cond_code == LT_EXPR) 117918334Speter { 118018334Speter tree one = build_int_cst (type, 1); 118118334Speter max = fold_build2 (MINUS_EXPR, type, max, one); 118218334Speter if (EXPR_P (max)) 118318334Speter TREE_NO_WARNING (max) = 1; 118418334Speter } 118518334Speter 118618334Speter set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 118718334Speter } 118818334Speter } 118918334Speter else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 119018334Speter { 119118334Speter max = TYPE_MAX_VALUE (type); 119218334Speter 119318334Speter if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 119418334Speter min = limit; 119518334Speter else 119618334Speter { 119718334Speter /* If LIMIT_VR is of the form [N1, N2], we need to build the 119818334Speter range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for 119918334Speter GT_EXPR. */ 120018334Speter min = limit_vr->min; 120118334Speter } 120218334Speter 120318334Speter /* If the minimum value forces us to be out of bounds, simply punt. 120418334Speter It would be pointless to try and do anything more since this 120518334Speter all should be optimized away above us. */ 120618334Speter if ((cond_code == GT_EXPR 120718334Speter && compare_values (min, max) == 0) 120818334Speter || is_overflow_infinity (min)) 120918334Speter set_value_range_to_varying (vr_p); 121018334Speter else 121118334Speter { 121218334Speter /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ 121318334Speter if (cond_code == GT_EXPR) 121418334Speter { 121518334Speter tree one = build_int_cst (type, 1); 121618334Speter min = fold_build2 (PLUS_EXPR, type, min, one); 121718334Speter if (EXPR_P (min)) 121818334Speter TREE_NO_WARNING (min) = 1; 121918334Speter } 122018334Speter 122118334Speter set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 122218334Speter } 122318334Speter } 122418334Speter else 122518334Speter gcc_unreachable (); 122618334Speter 122718334Speter /* If VAR already had a known range, it may happen that the new 122818334Speter range we have computed and VAR's range are not compatible. For 122918334Speter instance, 123018334Speter 123118334Speter if (p_5 == NULL) 123218334Speter p_6 = ASSERT_EXPR <p_5, p_5 == NULL>; 123318334Speter x_7 = p_6->fld; 123418334Speter p_8 = ASSERT_EXPR <p_6, p_6 != NULL>; 123518334Speter 123618334Speter While the above comes from a faulty program, it will cause an ICE 123718334Speter later because p_8 and p_6 will have incompatible ranges and at 123818334Speter the same time will be considered equivalent. A similar situation 123918334Speter would arise from 124018334Speter 124118334Speter if (i_5 > 10) 124218334Speter i_6 = ASSERT_EXPR <i_5, i_5 > 10>; 124318334Speter if (i_5 < 5) 124418334Speter i_7 = ASSERT_EXPR <i_6, i_6 < 5>; 124518334Speter 124618334Speter Again i_6 and i_7 will have incompatible ranges. It would be 124718334Speter pointless to try and do anything with i_7's range because 124818334Speter anything dominated by 'if (i_5 < 5)' will be optimized away. 124918334Speter Note, due to the wa in which simulation proceeds, the statement 125018334Speter i_7 = ASSERT_EXPR <...> we would never be visited because the 125118334Speter conditional 'if (i_5 < 5)' always evaluates to false. However, 125218334Speter this extra check does not hurt and may protect against future 125318334Speter changes to VRP that may get into a situation similar to the 125418334Speter NULL pointer dereference example. 125518334Speter 125618334Speter Note that these compatibility tests are only needed when dealing 125718334Speter with ranges or a mix of range and anti-range. If VAR_VR and VR_P 125818334Speter are both anti-ranges, they will always be compatible, because two 125918334Speter anti-ranges will always have a non-empty intersection. */ 126018334Speter 126118334Speter var_vr = get_value_range (var); 126218334Speter 126318334Speter /* We may need to make adjustments when VR_P and VAR_VR are numeric 126418334Speter ranges or anti-ranges. */ 126518334Speter if (vr_p->type == VR_VARYING 126618334Speter || vr_p->type == VR_UNDEFINED 126718334Speter || var_vr->type == VR_VARYING 126818334Speter || var_vr->type == VR_UNDEFINED 126918334Speter || symbolic_range_p (vr_p) 127018334Speter || symbolic_range_p (var_vr)) 127118334Speter return; 127218334Speter 127318334Speter if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE) 127418334Speter { 127518334Speter /* If the two ranges have a non-empty intersection, we can 127618334Speter refine the resulting range. Since the assert expression 127718334Speter creates an equivalency and at the same time it asserts a 127818334Speter predicate, we can take the intersection of the two ranges to 127918334Speter get better precision. */ 128018334Speter if (value_ranges_intersect_p (var_vr, vr_p)) 128118334Speter { 128218334Speter /* Use the larger of the two minimums. */ 128318334Speter if (compare_values (vr_p->min, var_vr->min) == -1) 128418334Speter min = var_vr->min; 128518334Speter else 128618334Speter min = vr_p->min; 128718334Speter 128818334Speter /* Use the smaller of the two maximums. */ 128918334Speter if (compare_values (vr_p->max, var_vr->max) == 1) 129018334Speter max = var_vr->max; 129118334Speter else 129218334Speter max = vr_p->max; 129318334Speter 129418334Speter set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv); 129518334Speter } 129618334Speter else 129718334Speter { 129818334Speter /* The two ranges do not intersect, set the new range to 129918334Speter VARYING, because we will not be able to do anything 130018334Speter meaningful with it. */ 130118334Speter set_value_range_to_varying (vr_p); 130218334Speter } 130318334Speter } 130418334Speter else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE) 130518334Speter || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE)) 130618334Speter { 130718334Speter /* A range and an anti-range will cancel each other only if 130818334Speter their ends are the same. For instance, in the example above, 130918334Speter p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible, 131018334Speter so VR_P should be set to VR_VARYING. */ 131118334Speter if (compare_values (var_vr->min, vr_p->min) == 0 131218334Speter && compare_values (var_vr->max, vr_p->max) == 0) 131318334Speter set_value_range_to_varying (vr_p); 131418334Speter else 131518334Speter { 131618334Speter tree min, max, anti_min, anti_max, real_min, real_max; 131718334Speter 131818334Speter /* We want to compute the logical AND of the two ranges; 131918334Speter there are three cases to consider. 132018334Speter 132118334Speter 132218334Speter 1. The VR_ANTI_RANGE range is completely within the 132318334Speter VR_RANGE and the endpoints of the ranges are 132418334Speter different. In that case the resulting range 132518334Speter should be whichever range is more precise. 132618334Speter Typically that will be the VR_RANGE. 132718334Speter 132818334Speter 2. The VR_ANTI_RANGE is completely disjoint from 132918334Speter the VR_RANGE. In this case the resulting range 133018334Speter should be the VR_RANGE. 133118334Speter 133218334Speter 3. There is some overlap between the VR_ANTI_RANGE 133318334Speter and the VR_RANGE. 133418334Speter 133518334Speter 3a. If the high limit of the VR_ANTI_RANGE resides 133618334Speter within the VR_RANGE, then the result is a new 133718334Speter VR_RANGE starting at the high limit of the 133818334Speter the VR_ANTI_RANGE + 1 and extending to the 133918334Speter high limit of the original VR_RANGE. 134018334Speter 134118334Speter 3b. If the low limit of the VR_ANTI_RANGE resides 134218334Speter within the VR_RANGE, then the result is a new 134318334Speter VR_RANGE starting at the low limit of the original 134418334Speter VR_RANGE and extending to the low limit of the 134518334Speter VR_ANTI_RANGE - 1. */ 134618334Speter if (vr_p->type == VR_ANTI_RANGE) 134718334Speter { 134818334Speter anti_min = vr_p->min; 134918334Speter anti_max = vr_p->max; 135018334Speter real_min = var_vr->min; 135118334Speter real_max = var_vr->max; 135218334Speter } 135318334Speter else 135418334Speter { 135518334Speter anti_min = var_vr->min; 135618334Speter anti_max = var_vr->max; 135718334Speter real_min = vr_p->min; 135818334Speter real_max = vr_p->max; 135918334Speter } 136018334Speter 136118334Speter 136218334Speter /* Case 1, VR_ANTI_RANGE completely within VR_RANGE, 136318334Speter not including any endpoints. */ 136418334Speter if (compare_values (anti_max, real_max) == -1 136518334Speter && compare_values (anti_min, real_min) == 1) 136618334Speter { 136718334Speter set_value_range (vr_p, VR_RANGE, real_min, 136818334Speter real_max, vr_p->equiv); 136918334Speter } 137018334Speter /* Case 2, VR_ANTI_RANGE completely disjoint from 137118334Speter VR_RANGE. */ 137218334Speter else if (compare_values (anti_min, real_max) == 1 137318334Speter || compare_values (anti_max, real_min) == -1) 137418334Speter { 137518334Speter set_value_range (vr_p, VR_RANGE, real_min, 137618334Speter real_max, vr_p->equiv); 137718334Speter } 137818334Speter /* Case 3a, the anti-range extends into the low 137918334Speter part of the real range. Thus creating a new 138018334Speter low for the real range. */ 138118334Speter else if ((compare_values (anti_max, real_min) == 1 138218334Speter || compare_values (anti_max, real_min) == 0) 138318334Speter && compare_values (anti_max, real_max) == -1) 138418334Speter { 138518334Speter gcc_assert (!is_positive_overflow_infinity (anti_max)); 138618334Speter if (needs_overflow_infinity (TREE_TYPE (anti_max)) 138718334Speter && vrp_val_is_max (anti_max)) 138818334Speter { 138918334Speter if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 139018334Speter { 139118334Speter set_value_range_to_varying (vr_p); 139218334Speter return; 139318334Speter } 139418334Speter min = positive_overflow_infinity (TREE_TYPE (var_vr->min)); 139518334Speter } 139618334Speter else 139718334Speter min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min), 139818334Speter anti_max, 139918334Speter build_int_cst (TREE_TYPE (var_vr->min), 1)); 140018334Speter max = real_max; 140118334Speter set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 140218334Speter } 140318334Speter /* Case 3b, the anti-range extends into the high 140418334Speter part of the real range. Thus creating a new 140518334Speter higher for the real range. */ 140618334Speter else if (compare_values (anti_min, real_min) == 1 140718334Speter && (compare_values (anti_min, real_max) == -1 140818334Speter || compare_values (anti_min, real_max) == 0)) 140918334Speter { 141018334Speter gcc_assert (!is_negative_overflow_infinity (anti_min)); 141118334Speter if (needs_overflow_infinity (TREE_TYPE (anti_min)) 141218334Speter && vrp_val_is_min (anti_min)) 141318334Speter { 141418334Speter if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 141518334Speter { 141618334Speter set_value_range_to_varying (vr_p); 141718334Speter return; 141818334Speter } 141918334Speter max = negative_overflow_infinity (TREE_TYPE (var_vr->min)); 142018334Speter } 142118334Speter else 142218334Speter max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min), 142318334Speter anti_min, 142418334Speter build_int_cst (TREE_TYPE (var_vr->min), 1)); 142518334Speter min = real_min; 142618334Speter set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 142718334Speter } 142818334Speter } 142918334Speter } 143018334Speter} 143118334Speter 143218334Speter 143318334Speter/* Extract range information from SSA name VAR and store it in VR. If 143418334Speter VAR has an interesting range, use it. Otherwise, create the 143518334Speter range [VAR, VAR] and return it. This is useful in situations where 143618334Speter we may have conditionals testing values of VARYING names. For 143718334Speter instance, 143818334Speter 143918334Speter x_3 = y_5; 144018334Speter if (x_3 > y_5) 144118334Speter ... 144218334Speter 144318334Speter Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is 144418334Speter always false. */ 144518334Speter 144618334Speterstatic void 144718334Speterextract_range_from_ssa_name (value_range_t *vr, tree var) 144818334Speter{ 144918334Speter value_range_t *var_vr = get_value_range (var); 145018334Speter 145118334Speter if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING) 145218334Speter copy_value_range (vr, var_vr); 145318334Speter else 145418334Speter set_value_range (vr, VR_RANGE, var, var, NULL); 145518334Speter 145618334Speter add_equivalence (vr->equiv, var); 145718334Speter} 145818334Speter 145918334Speter 146018334Speter/* Wrapper around int_const_binop. If the operation overflows and we 146118334Speter are not using wrapping arithmetic, then adjust the result to be 146218334Speter -INF or +INF depending on CODE, VAL1 and VAL2. This can return 146318334Speter NULL_TREE if we need to use an overflow infinity representation but 146418334Speter the type does not support it. */ 146518334Speter 146618334Speterstatic tree 146718334Spetervrp_int_const_binop (enum tree_code code, tree val1, tree val2) 146818334Speter{ 146918334Speter tree res; 147018334Speter 147118334Speter res = int_const_binop (code, val1, val2, 0); 147218334Speter 147318334Speter /* If we are not using wrapping arithmetic, operate symbolically 147418334Speter on -INF and +INF. */ 147518334Speter if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) 147618334Speter { 147718334Speter int checkz = compare_values (res, val1); 147818334Speter bool overflow = false; 147918334Speter 148018334Speter /* Ensure that res = val1 [+*] val2 >= val1 148118334Speter or that res = val1 - val2 <= val1. */ 148218334Speter if ((code == PLUS_EXPR 148318334Speter && !(checkz == 1 || checkz == 0)) 148418334Speter || (code == MINUS_EXPR 148518334Speter && !(checkz == 0 || checkz == -1))) 148618334Speter { 148718334Speter overflow = true; 148818334Speter } 148918334Speter /* Checking for multiplication overflow is done by dividing the 149018334Speter output of the multiplication by the first input of the 149118334Speter multiplication. If the result of that division operation is 149218334Speter not equal to the second input of the multiplication, then the 149318334Speter multiplication overflowed. */ 149418334Speter else if (code == MULT_EXPR && !integer_zerop (val1)) 149518334Speter { 149618334Speter tree tmp = int_const_binop (TRUNC_DIV_EXPR, 149718334Speter res, 149818334Speter val1, 0); 149918334Speter int check = compare_values (tmp, val2); 150018334Speter 150118334Speter if (check != 0) 150218334Speter overflow = true; 150318334Speter } 150418334Speter 150518334Speter if (overflow) 150618334Speter { 150718334Speter res = copy_node (res); 150818334Speter TREE_OVERFLOW (res) = 1; 150918334Speter } 151018334Speter 151118334Speter } 151218334Speter else if ((TREE_OVERFLOW (res) 151318334Speter && !TREE_OVERFLOW (val1) 151418334Speter && !TREE_OVERFLOW (val2)) 151518334Speter || is_overflow_infinity (val1) 151618334Speter || is_overflow_infinity (val2)) 151718334Speter { 151818334Speter /* If the operation overflowed but neither VAL1 nor VAL2 are 151918334Speter overflown, return -INF or +INF depending on the operation 152018334Speter and the combination of signs of the operands. */ 152118334Speter int sgn1 = tree_int_cst_sgn (val1); 152218334Speter int sgn2 = tree_int_cst_sgn (val2); 152318334Speter 152418334Speter if (needs_overflow_infinity (TREE_TYPE (res)) 152518334Speter && !supports_overflow_infinity (TREE_TYPE (res))) 152618334Speter return NULL_TREE; 152718334Speter 152818334Speter /* We have to punt on adding infinities of different signs, 152918334Speter since we can't tell what the sign of the result should be. 153018334Speter Likewise for subtracting infinities of the same sign. */ 153118334Speter if (((code == PLUS_EXPR && sgn1 != sgn2) 153218334Speter || (code == MINUS_EXPR && sgn1 == sgn2)) 153318334Speter && is_overflow_infinity (val1) 153418334Speter && is_overflow_infinity (val2)) 153518334Speter return NULL_TREE; 153618334Speter 153718334Speter /* Don't try to handle division or shifting of infinities. */ 153818334Speter if ((code == TRUNC_DIV_EXPR 153918334Speter || code == FLOOR_DIV_EXPR 154018334Speter || code == CEIL_DIV_EXPR 154118334Speter || code == EXACT_DIV_EXPR 154218334Speter || code == ROUND_DIV_EXPR 154318334Speter || code == RSHIFT_EXPR) 154418334Speter && (is_overflow_infinity (val1) 154518334Speter || is_overflow_infinity (val2))) 154618334Speter return NULL_TREE; 154718334Speter 154818334Speter /* Notice that we only need to handle the restricted set of 154918334Speter operations handled by extract_range_from_binary_expr. 155018334Speter Among them, only multiplication, addition and subtraction 155118334Speter can yield overflow without overflown operands because we 155218334Speter are working with integral types only... except in the 155318334Speter case VAL1 = -INF and VAL2 = -1 which overflows to +INF 155418334Speter for division too. */ 155518334Speter 155618334Speter /* For multiplication, the sign of the overflow is given 155718334Speter by the comparison of the signs of the operands. */ 155818334Speter if ((code == MULT_EXPR && sgn1 == sgn2) 155918334Speter /* For addition, the operands must be of the same sign 156018334Speter to yield an overflow. Its sign is therefore that 156118334Speter of one of the operands, for example the first. For 156218334Speter infinite operands X + -INF is negative, not positive. */ 156318334Speter || (code == PLUS_EXPR 156418334Speter && (sgn1 >= 0 156518334Speter ? !is_negative_overflow_infinity (val2) 156618334Speter : is_positive_overflow_infinity (val2))) 156718334Speter /* For subtraction, non-infinite operands must be of 156818334Speter different signs to yield an overflow. Its sign is 156918334Speter therefore that of the first operand or the opposite of 157018334Speter that of the second operand. A first operand of 0 counts 157118334Speter as positive here, for the corner case 0 - (-INF), which 157218334Speter overflows, but must yield +INF. For infinite operands 0 157318334Speter - INF is negative, not positive. */ 157418334Speter || (code == MINUS_EXPR 157518334Speter && (sgn1 >= 0 157618334Speter ? !is_positive_overflow_infinity (val2) 157718334Speter : is_negative_overflow_infinity (val2))) 157818334Speter /* For division, the only case is -INF / -1 = +INF. */ 157918334Speter || code == TRUNC_DIV_EXPR 158018334Speter || code == FLOOR_DIV_EXPR 158118334Speter || code == CEIL_DIV_EXPR 158218334Speter || code == EXACT_DIV_EXPR 158318334Speter || code == ROUND_DIV_EXPR) 158418334Speter return (needs_overflow_infinity (TREE_TYPE (res)) 158518334Speter ? positive_overflow_infinity (TREE_TYPE (res)) 158618334Speter : TYPE_MAX_VALUE (TREE_TYPE (res))); 158718334Speter else 158818334Speter return (needs_overflow_infinity (TREE_TYPE (res)) 158918334Speter ? negative_overflow_infinity (TREE_TYPE (res)) 159018334Speter : TYPE_MIN_VALUE (TREE_TYPE (res))); 159118334Speter } 159218334Speter 159318334Speter return res; 159418334Speter} 159518334Speter 159618334Speter 159718334Speter/* Extract range information from a binary expression EXPR based on 159818334Speter the ranges of each of its operands and the expression code. */ 159918334Speter 160018334Speterstatic void 160118334Speterextract_range_from_binary_expr (value_range_t *vr, tree expr) 160218334Speter{ 160318334Speter enum tree_code code = TREE_CODE (expr); 160418334Speter enum value_range_type type; 160518334Speter tree op0, op1, min, max; 160618334Speter int cmp; 160718334Speter value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 160818334Speter value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 160918334Speter 161018334Speter /* Not all binary expressions can be applied to ranges in a 161118334Speter meaningful way. Handle only arithmetic operations. */ 161218334Speter if (code != PLUS_EXPR 161318334Speter && code != MINUS_EXPR 161418334Speter && code != MULT_EXPR 161518334Speter && code != TRUNC_DIV_EXPR 161618334Speter && code != FLOOR_DIV_EXPR 161718334Speter && code != CEIL_DIV_EXPR 161818334Speter && code != EXACT_DIV_EXPR 161918334Speter && code != ROUND_DIV_EXPR 162018334Speter && code != MIN_EXPR 162118334Speter && code != MAX_EXPR 162218334Speter && code != BIT_AND_EXPR 162318334Speter && code != TRUTH_ANDIF_EXPR 162418334Speter && code != TRUTH_ORIF_EXPR 162518334Speter && code != TRUTH_AND_EXPR 162618334Speter && code != TRUTH_OR_EXPR) 162718334Speter { 162818334Speter set_value_range_to_varying (vr); 162918334Speter return; 163018334Speter } 163118334Speter 163218334Speter /* Get value ranges for each operand. For constant operands, create 163318334Speter a new value range with the operand to simplify processing. */ 163418334Speter op0 = TREE_OPERAND (expr, 0); 163518334Speter if (TREE_CODE (op0) == SSA_NAME) 163618334Speter vr0 = *(get_value_range (op0)); 163718334Speter else if (is_gimple_min_invariant (op0)) 163818334Speter set_value_range_to_value (&vr0, op0, NULL); 163918334Speter else 164018334Speter set_value_range_to_varying (&vr0); 164118334Speter 164218334Speter op1 = TREE_OPERAND (expr, 1); 164318334Speter if (TREE_CODE (op1) == SSA_NAME) 164418334Speter vr1 = *(get_value_range (op1)); 164518334Speter else if (is_gimple_min_invariant (op1)) 164618334Speter set_value_range_to_value (&vr1, op1, NULL); 164718334Speter else 164818334Speter set_value_range_to_varying (&vr1); 164918334Speter 165018334Speter /* If either range is UNDEFINED, so is the result. */ 165118334Speter if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED) 165218334Speter { 165318334Speter set_value_range_to_undefined (vr); 165418334Speter return; 165518334Speter } 165618334Speter 165718334Speter /* The type of the resulting value range defaults to VR0.TYPE. */ 165818334Speter type = vr0.type; 165918334Speter 166018334Speter /* Refuse to operate on VARYING ranges, ranges of different kinds 166118334Speter and symbolic ranges. As an exception, we allow BIT_AND_EXPR 166218334Speter because we may be able to derive a useful range even if one of 166318334Speter the operands is VR_VARYING or symbolic range. TODO, we may be 166418334Speter able to derive anti-ranges in some cases. */ 166518334Speter if (code != BIT_AND_EXPR 166618334Speter && code != TRUTH_AND_EXPR 166718334Speter && code != TRUTH_OR_EXPR 166818334Speter && (vr0.type == VR_VARYING 166918334Speter || vr1.type == VR_VARYING 167018334Speter || vr0.type != vr1.type 167118334Speter || symbolic_range_p (&vr0) 167218334Speter || symbolic_range_p (&vr1))) 167318334Speter { 167418334Speter set_value_range_to_varying (vr); 167518334Speter return; 167618334Speter } 167718334Speter 167818334Speter /* Now evaluate the expression to determine the new range. */ 167918334Speter if (POINTER_TYPE_P (TREE_TYPE (expr)) 168018334Speter || POINTER_TYPE_P (TREE_TYPE (op0)) 168118334Speter || POINTER_TYPE_P (TREE_TYPE (op1))) 168218334Speter { 168318334Speter /* For pointer types, we are really only interested in asserting 168418334Speter whether the expression evaluates to non-NULL. FIXME, we used 168518334Speter to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but 168618334Speter ivopts is generating expressions with pointer multiplication 168718334Speter in them. */ 168818334Speter if (code == PLUS_EXPR) 168918334Speter { 169018334Speter if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) 169118334Speter set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 169218334Speter else if (range_is_null (&vr0) && range_is_null (&vr1)) 169318334Speter set_value_range_to_null (vr, TREE_TYPE (expr)); 169418334Speter else 169518334Speter set_value_range_to_varying (vr); 169618334Speter } 169718334Speter else 169818334Speter { 169918334Speter /* Subtracting from a pointer, may yield 0, so just drop the 170018334Speter resulting range to varying. */ 170118334Speter set_value_range_to_varying (vr); 170218334Speter } 170318334Speter 170418334Speter return; 170518334Speter } 170618334Speter 170718334Speter /* For integer ranges, apply the operation to each end of the 170818334Speter range and see what we end up with. */ 170918334Speter if (code == TRUTH_ANDIF_EXPR 171018334Speter || code == TRUTH_ORIF_EXPR 171118334Speter || code == TRUTH_AND_EXPR 171218334Speter || code == TRUTH_OR_EXPR) 171318334Speter { 171418334Speter /* If one of the operands is zero, we know that the whole 171518334Speter expression evaluates zero. */ 171618334Speter if (code == TRUTH_AND_EXPR 171718334Speter && ((vr0.type == VR_RANGE 171818334Speter && integer_zerop (vr0.min) 171918334Speter && integer_zerop (vr0.max)) 172018334Speter || (vr1.type == VR_RANGE 172118334Speter && integer_zerop (vr1.min) 172218334Speter && integer_zerop (vr1.max)))) 172318334Speter { 172418334Speter type = VR_RANGE; 172518334Speter min = max = build_int_cst (TREE_TYPE (expr), 0); 172618334Speter } 172718334Speter /* If one of the operands is one, we know that the whole 172818334Speter expression evaluates one. */ 172918334Speter else if (code == TRUTH_OR_EXPR 173018334Speter && ((vr0.type == VR_RANGE 173118334Speter && integer_onep (vr0.min) 173218334Speter && integer_onep (vr0.max)) 173318334Speter || (vr1.type == VR_RANGE 173418334Speter && integer_onep (vr1.min) 173518334Speter && integer_onep (vr1.max)))) 173618334Speter { 173718334Speter type = VR_RANGE; 173818334Speter min = max = build_int_cst (TREE_TYPE (expr), 1); 173918334Speter } 174018334Speter else if (vr0.type != VR_VARYING 174118334Speter && vr1.type != VR_VARYING 174218334Speter && vr0.type == vr1.type 174318334Speter && !symbolic_range_p (&vr0) 174418334Speter && !overflow_infinity_range_p (&vr0) 174518334Speter && !symbolic_range_p (&vr1) 174618334Speter && !overflow_infinity_range_p (&vr1)) 174718334Speter { 174818334Speter /* Boolean expressions cannot be folded with int_const_binop. */ 174918334Speter min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min); 175018334Speter max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max); 175118334Speter } 175218334Speter else 175318334Speter { 175418334Speter set_value_range_to_varying (vr); 175518334Speter return; 175618334Speter } 175718334Speter } 175818334Speter else if (code == PLUS_EXPR 175918334Speter || code == MIN_EXPR 176018334Speter || code == MAX_EXPR) 176118334Speter { 176218334Speter /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to 176318334Speter VR_VARYING. It would take more effort to compute a precise 176418334Speter range for such a case. For example, if we have op0 == 1 and 176518334Speter op1 == -1 with their ranges both being ~[0,0], we would have 176618334Speter op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. 176718334Speter Note that we are guaranteed to have vr0.type == vr1.type at 176818334Speter this point. */ 176918334Speter if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) 177018334Speter { 177118334Speter set_value_range_to_varying (vr); 177218334Speter return; 177318334Speter } 177418334Speter 177518334Speter /* For operations that make the resulting range directly 177618334Speter proportional to the original ranges, apply the operation to 177718334Speter the same end of each range. */ 177818334Speter min = vrp_int_const_binop (code, vr0.min, vr1.min); 177918334Speter max = vrp_int_const_binop (code, vr0.max, vr1.max); 178018334Speter } 178118334Speter else if (code == MULT_EXPR 178218334Speter || code == TRUNC_DIV_EXPR 178318334Speter || code == FLOOR_DIV_EXPR 178418334Speter || code == CEIL_DIV_EXPR 178518334Speter || code == EXACT_DIV_EXPR 178618334Speter || code == ROUND_DIV_EXPR) 178718334Speter { 178818334Speter tree val[4]; 178918334Speter size_t i; 179018334Speter bool sop; 179118334Speter 179218334Speter /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, 179318334Speter drop to VR_VARYING. It would take more effort to compute a 179418334Speter precise range for such a case. For example, if we have 179518334Speter op0 == 65536 and op1 == 65536 with their ranges both being 179618334Speter ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so 179718334Speter we cannot claim that the product is in ~[0,0]. Note that we 179818334Speter are guaranteed to have vr0.type == vr1.type at this 179918334Speter point. */ 180018334Speter if (code == MULT_EXPR 180118334Speter && vr0.type == VR_ANTI_RANGE 180218334Speter && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) 180318334Speter { 180418334Speter set_value_range_to_varying (vr); 180518334Speter return; 180618334Speter } 180718334Speter 180818334Speter /* Multiplications and divisions are a bit tricky to handle, 180918334Speter depending on the mix of signs we have in the two ranges, we 181018334Speter need to operate on different values to get the minimum and 181118334Speter maximum values for the new range. One approach is to figure 181218334Speter out all the variations of range combinations and do the 181318334Speter operations. 181418334Speter 181518334Speter However, this involves several calls to compare_values and it 181618334Speter is pretty convoluted. It's simpler to do the 4 operations 181718334Speter (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP 181818334Speter MAX1) and then figure the smallest and largest values to form 181918334Speter the new range. */ 182018334Speter 182118334Speter /* Divisions by zero result in a VARYING value. */ 182218334Speter if (code != MULT_EXPR 182318334Speter && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) 182418334Speter { 182518334Speter set_value_range_to_varying (vr); 182618334Speter return; 182718334Speter } 182818334Speter 182918334Speter /* Compute the 4 cross operations. */ 183018334Speter sop = false; 183118334Speter val[0] = vrp_int_const_binop (code, vr0.min, vr1.min); 183218334Speter if (val[0] == NULL_TREE) 183318334Speter sop = true; 183418334Speter 183518334Speter if (vr1.max == vr1.min) 183618334Speter val[1] = NULL_TREE; 183718334Speter else 183818334Speter { 183918334Speter val[1] = vrp_int_const_binop (code, vr0.min, vr1.max); 184018334Speter if (val[1] == NULL_TREE) 184118334Speter sop = true; 184218334Speter } 184318334Speter 184418334Speter if (vr0.max == vr0.min) 184518334Speter val[2] = NULL_TREE; 184618334Speter else 184718334Speter { 184818334Speter val[2] = vrp_int_const_binop (code, vr0.max, vr1.min); 184918334Speter if (val[2] == NULL_TREE) 185018334Speter sop = true; 185118334Speter } 185218334Speter 185318334Speter if (vr0.min == vr0.max || vr1.min == vr1.max) 185418334Speter val[3] = NULL_TREE; 185518334Speter else 185618334Speter { 185718334Speter val[3] = vrp_int_const_binop (code, vr0.max, vr1.max); 185818334Speter if (val[3] == NULL_TREE) 185918334Speter sop = true; 186018334Speter } 186118334Speter 186218334Speter if (sop) 186318334Speter { 186418334Speter set_value_range_to_varying (vr); 186518334Speter return; 186618334Speter } 186718334Speter 186818334Speter /* Set MIN to the minimum of VAL[i] and MAX to the maximum 186918334Speter of VAL[i]. */ 187018334Speter min = val[0]; 187118334Speter max = val[0]; 187218334Speter for (i = 1; i < 4; i++) 187318334Speter { 187418334Speter if (!is_gimple_min_invariant (min) 187518334Speter || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 187618334Speter || !is_gimple_min_invariant (max) 187718334Speter || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 187818334Speter break; 187918334Speter 188018334Speter if (val[i]) 188118334Speter { 188218334Speter if (!is_gimple_min_invariant (val[i]) 188318334Speter || (TREE_OVERFLOW (val[i]) 188418334Speter && !is_overflow_infinity (val[i]))) 188518334Speter { 188618334Speter /* If we found an overflowed value, set MIN and MAX 188718334Speter to it so that we set the resulting range to 188818334Speter VARYING. */ 188918334Speter min = max = val[i]; 189018334Speter break; 189118334Speter } 189218334Speter 189318334Speter if (compare_values (val[i], min) == -1) 189418334Speter min = val[i]; 189518334Speter 189618334Speter if (compare_values (val[i], max) == 1) 189718334Speter max = val[i]; 189818334Speter } 189918334Speter } 190018334Speter } 190118334Speter else if (code == MINUS_EXPR) 190218334Speter { 190318334Speter /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to 190418334Speter VR_VARYING. It would take more effort to compute a precise 190518334Speter range for such a case. For example, if we have op0 == 1 and 190618334Speter op1 == 1 with their ranges both being ~[0,0], we would have 190718334Speter op0 - op1 == 0, so we cannot claim that the difference is in 190818334Speter ~[0,0]. Note that we are guaranteed to have 190918334Speter vr0.type == vr1.type at this point. */ 191018334Speter if (vr0.type == VR_ANTI_RANGE) 191118334Speter { 191218334Speter set_value_range_to_varying (vr); 191318334Speter return; 191418334Speter } 191518334Speter 191618334Speter /* For MINUS_EXPR, apply the operation to the opposite ends of 191718334Speter each range. */ 191818334Speter min = vrp_int_const_binop (code, vr0.min, vr1.max); 191918334Speter max = vrp_int_const_binop (code, vr0.max, vr1.min); 192018334Speter } 192118334Speter else if (code == BIT_AND_EXPR) 192218334Speter { 192318334Speter if (vr0.type == VR_RANGE 192418334Speter && vr0.min == vr0.max 192518334Speter && TREE_CODE (vr0.max) == INTEGER_CST 192618334Speter && !TREE_OVERFLOW (vr0.max) 192718334Speter && tree_int_cst_sgn (vr0.max) >= 0) 192818334Speter { 192918334Speter min = build_int_cst (TREE_TYPE (expr), 0); 193018334Speter max = vr0.max; 193118334Speter } 193218334Speter else if (vr1.type == VR_RANGE 193318334Speter && vr1.min == vr1.max 193418334Speter && TREE_CODE (vr1.max) == INTEGER_CST 193518334Speter && !TREE_OVERFLOW (vr1.max) 193618334Speter && tree_int_cst_sgn (vr1.max) >= 0) 193718334Speter { 193818334Speter type = VR_RANGE; 193918334Speter min = build_int_cst (TREE_TYPE (expr), 0); 194018334Speter max = vr1.max; 194118334Speter } 194218334Speter else 194318334Speter { 194418334Speter set_value_range_to_varying (vr); 194518334Speter return; 194618334Speter } 194718334Speter } 194818334Speter else 194918334Speter gcc_unreachable (); 195018334Speter 195118334Speter /* If either MIN or MAX overflowed, then set the resulting range to 195218334Speter VARYING. But we do accept an overflow infinity 195318334Speter representation. */ 195418334Speter if (min == NULL_TREE 195518334Speter || !is_gimple_min_invariant (min) 195618334Speter || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 195718334Speter || max == NULL_TREE 195818334Speter || !is_gimple_min_invariant (max) 195918334Speter || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 196018334Speter { 196118334Speter set_value_range_to_varying (vr); 196218334Speter return; 196318334Speter } 196418334Speter 196518334Speter /* We punt if: 196618334Speter 1) [-INF, +INF] 196718334Speter 2) [-INF, +-INF(OVF)] 196818334Speter 3) [+-INF(OVF), +INF] 196918334Speter 4) [+-INF(OVF), +-INF(OVF)] 197018334Speter We learn nothing when we have INF and INF(OVF) on both sides. 197118334Speter Note that we do accept [-INF, -INF] and [+INF, +INF] without 197218334Speter overflow. */ 197318334Speter if ((vrp_val_is_min (min) || is_overflow_infinity (min)) 197418334Speter && (vrp_val_is_max (max) || is_overflow_infinity (max))) 197518334Speter { 197618334Speter set_value_range_to_varying (vr); 197718334Speter return; 197818334Speter } 197918334Speter 198018334Speter cmp = compare_values (min, max); 198118334Speter if (cmp == -2 || cmp == 1) 198218334Speter { 198318334Speter /* If the new range has its limits swapped around (MIN > MAX), 198418334Speter then the operation caused one of them to wrap around, mark 198518334Speter the new range VARYING. */ 198618334Speter set_value_range_to_varying (vr); 198718334Speter } 198818334Speter else 198918334Speter set_value_range (vr, type, min, max, NULL); 199018334Speter} 199118334Speter 199218334Speter 199318334Speter/* Extract range information from a unary expression EXPR based on 199418334Speter the range of its operand and the expression code. */ 199518334Speter 199618334Speterstatic void 199718334Speterextract_range_from_unary_expr (value_range_t *vr, tree expr) 199818334Speter{ 199918334Speter enum tree_code code = TREE_CODE (expr); 200018334Speter tree min, max, op0; 200118334Speter int cmp; 200218334Speter value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 200318334Speter 200418334Speter /* Refuse to operate on certain unary expressions for which we 200518334Speter cannot easily determine a resulting range. */ 200618334Speter if (code == FIX_TRUNC_EXPR 200718334Speter || code == FIX_CEIL_EXPR 200818334Speter || code == FIX_FLOOR_EXPR 200918334Speter || code == FIX_ROUND_EXPR 201018334Speter || code == FLOAT_EXPR 201118334Speter || code == BIT_NOT_EXPR 201218334Speter || code == NON_LVALUE_EXPR 201318334Speter || code == CONJ_EXPR) 201418334Speter { 201518334Speter set_value_range_to_varying (vr); 201618334Speter return; 201718334Speter } 201818334Speter 201918334Speter /* Get value ranges for the operand. For constant operands, create 202018334Speter a new value range with the operand to simplify processing. */ 202118334Speter op0 = TREE_OPERAND (expr, 0); 202218334Speter if (TREE_CODE (op0) == SSA_NAME) 202318334Speter vr0 = *(get_value_range (op0)); 202418334Speter else if (is_gimple_min_invariant (op0)) 202518334Speter set_value_range_to_value (&vr0, op0, NULL); 202618334Speter else 202718334Speter set_value_range_to_varying (&vr0); 202818334Speter 202918334Speter /* If VR0 is UNDEFINED, so is the result. */ 203018334Speter if (vr0.type == VR_UNDEFINED) 203118334Speter { 203218334Speter set_value_range_to_undefined (vr); 203318334Speter return; 203418334Speter } 203518334Speter 203618334Speter /* Refuse to operate on symbolic ranges, or if neither operand is 203718334Speter a pointer or integral type. */ 203818334Speter if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 203918334Speter && !POINTER_TYPE_P (TREE_TYPE (op0))) 204018334Speter || (vr0.type != VR_VARYING 204118334Speter && symbolic_range_p (&vr0))) 204218334Speter { 204318334Speter set_value_range_to_varying (vr); 204418334Speter return; 204518334Speter } 204618334Speter 204718334Speter /* If the expression involves pointers, we are only interested in 204818334Speter determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ 204918334Speter if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0))) 205018334Speter { 205118334Speter bool sop; 205218334Speter 205318334Speter sop = false; 205418334Speter if (range_is_nonnull (&vr0) 205518334Speter || (tree_expr_nonzero_warnv_p (expr, &sop) 205618334Speter && !sop)) 205718334Speter set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 205818334Speter else if (range_is_null (&vr0)) 205918334Speter set_value_range_to_null (vr, TREE_TYPE (expr)); 206018334Speter else 206118334Speter set_value_range_to_varying (vr); 206218334Speter 206318334Speter return; 206418334Speter } 206518334Speter 206618334Speter /* Handle unary expressions on integer ranges. */ 206718334Speter if (code == NOP_EXPR || code == CONVERT_EXPR) 206818334Speter { 206918334Speter tree inner_type = TREE_TYPE (op0); 207018334Speter tree outer_type = TREE_TYPE (expr); 207118334Speter 207218334Speter /* If VR0 represents a simple range, then try to convert 207318334Speter the min and max values for the range to the same type 207418334Speter as OUTER_TYPE. If the results compare equal to VR0's 207518334Speter min and max values and the new min is still less than 207618334Speter or equal to the new max, then we can safely use the newly 207718334Speter computed range for EXPR. This allows us to compute 207818334Speter accurate ranges through many casts. */ 207918334Speter if ((vr0.type == VR_RANGE 208018334Speter && !overflow_infinity_range_p (&vr0)) 208118334Speter || (vr0.type == VR_VARYING 208218334Speter && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type))) 208318334Speter { 208418334Speter tree new_min, new_max, orig_min, orig_max; 208518334Speter 208618334Speter /* Convert the input operand min/max to OUTER_TYPE. If 208718334Speter the input has no range information, then use the min/max 208818334Speter for the input's type. */ 208918334Speter if (vr0.type == VR_RANGE) 209018334Speter { 209118334Speter orig_min = vr0.min; 209218334Speter orig_max = vr0.max; 209318334Speter } 209418334Speter else 209518334Speter { 209618334Speter orig_min = TYPE_MIN_VALUE (inner_type); 209718334Speter orig_max = TYPE_MAX_VALUE (inner_type); 209818334Speter } 209918334Speter 210018334Speter new_min = fold_convert (outer_type, orig_min); 210118334Speter new_max = fold_convert (outer_type, orig_max); 210218334Speter 210318334Speter /* Verify the new min/max values are gimple values and 210418334Speter that they compare equal to the original input's 210518334Speter min/max values. */ 210618334Speter if (is_gimple_val (new_min) 210718334Speter && is_gimple_val (new_max) 210818334Speter && tree_int_cst_equal (new_min, orig_min) 210918334Speter && tree_int_cst_equal (new_max, orig_max) 211018334Speter && (!is_overflow_infinity (new_min) 211118334Speter || !is_overflow_infinity (new_max)) 211218334Speter && compare_values (new_min, new_max) <= 0 211318334Speter && compare_values (new_min, new_max) >= -1) 211418334Speter { 211518334Speter set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv); 211618334Speter return; 211718334Speter } 211818334Speter } 211918334Speter 212018334Speter /* When converting types of different sizes, set the result to 212118334Speter VARYING. Things like sign extensions and precision loss may 212218334Speter change the range. For instance, if x_3 is of type 'long long 212318334Speter int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it 212418334Speter is impossible to know at compile time whether y_5 will be 212518334Speter ~[0, 0]. */ 212618334Speter if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type) 212718334Speter || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type)) 212818334Speter { 212918334Speter set_value_range_to_varying (vr); 213018334Speter return; 213118334Speter } 213218334Speter } 213318334Speter 213418334Speter /* Conversion of a VR_VARYING value to a wider type can result 213518334Speter in a usable range. So wait until after we've handled conversions 213618334Speter before dropping the result to VR_VARYING if we had a source 213718334Speter operand that is VR_VARYING. */ 213818334Speter if (vr0.type == VR_VARYING) 213918334Speter { 214018334Speter set_value_range_to_varying (vr); 214118334Speter return; 214218334Speter } 214318334Speter 214418334Speter /* Apply the operation to each end of the range and see what we end 214518334Speter up with. */ 214618334Speter if (code == NEGATE_EXPR 214718334Speter && !TYPE_UNSIGNED (TREE_TYPE (expr))) 214818334Speter { 214918334Speter /* NEGATE_EXPR flips the range around. We need to treat 215018334Speter TYPE_MIN_VALUE specially. */ 215118334Speter if (is_positive_overflow_infinity (vr0.max)) 215218334Speter min = negative_overflow_infinity (TREE_TYPE (expr)); 215318334Speter else if (is_negative_overflow_infinity (vr0.max)) 215418334Speter min = positive_overflow_infinity (TREE_TYPE (expr)); 215518334Speter else if (!vrp_val_is_min (vr0.max)) 215618334Speter min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 215718334Speter else if (needs_overflow_infinity (TREE_TYPE (expr))) 215818334Speter { 215918334Speter if (supports_overflow_infinity (TREE_TYPE (expr)) 216018334Speter && !is_overflow_infinity (vr0.min) 216118334Speter && !vrp_val_is_min (vr0.min)) 216218334Speter min = positive_overflow_infinity (TREE_TYPE (expr)); 216318334Speter else 216418334Speter { 216518334Speter set_value_range_to_varying (vr); 216618334Speter return; 216718334Speter } 216818334Speter } 216918334Speter else 217018334Speter min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 217118334Speter 217218334Speter if (is_positive_overflow_infinity (vr0.min)) 217318334Speter max = negative_overflow_infinity (TREE_TYPE (expr)); 217418334Speter else if (is_negative_overflow_infinity (vr0.min)) 217518334Speter max = positive_overflow_infinity (TREE_TYPE (expr)); 217618334Speter else if (!vrp_val_is_min (vr0.min)) 217718334Speter max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 217818334Speter else if (needs_overflow_infinity (TREE_TYPE (expr))) 217918334Speter { 218018334Speter if (supports_overflow_infinity (TREE_TYPE (expr))) 218118334Speter max = positive_overflow_infinity (TREE_TYPE (expr)); 218218334Speter else 218318334Speter { 218418334Speter set_value_range_to_varying (vr); 218518334Speter return; 218618334Speter } 218718334Speter } 218818334Speter else 218918334Speter max = TYPE_MIN_VALUE (TREE_TYPE (expr)); 219018334Speter } 219118334Speter else if (code == NEGATE_EXPR 219218334Speter && TYPE_UNSIGNED (TREE_TYPE (expr))) 219318334Speter { 219418334Speter if (!range_includes_zero_p (&vr0)) 219518334Speter { 219618334Speter max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 219718334Speter min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 219818334Speter } 219918334Speter else 220018334Speter { 220118334Speter if (range_is_null (&vr0)) 220218334Speter set_value_range_to_null (vr, TREE_TYPE (expr)); 220318334Speter else 220418334Speter set_value_range_to_varying (vr); 220518334Speter return; 220618334Speter } 220718334Speter } 220818334Speter else if (code == ABS_EXPR 220918334Speter && !TYPE_UNSIGNED (TREE_TYPE (expr))) 221018334Speter { 221118334Speter /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a 221218334Speter useful range. */ 221318334Speter if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr)) 221418334Speter && ((vr0.type == VR_RANGE 221518334Speter && vrp_val_is_min (vr0.min)) 221618334Speter || (vr0.type == VR_ANTI_RANGE 221718334Speter && !vrp_val_is_min (vr0.min) 221818334Speter && !range_includes_zero_p (&vr0)))) 221918334Speter { 222018334Speter set_value_range_to_varying (vr); 222118334Speter return; 222218334Speter } 222318334Speter 222418334Speter /* ABS_EXPR may flip the range around, if the original range 222518334Speter included negative values. */ 222618334Speter if (is_overflow_infinity (vr0.min)) 222718334Speter min = positive_overflow_infinity (TREE_TYPE (expr)); 222818334Speter else if (!vrp_val_is_min (vr0.min)) 222918334Speter min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 223018334Speter else if (!needs_overflow_infinity (TREE_TYPE (expr))) 223118334Speter min = TYPE_MAX_VALUE (TREE_TYPE (expr)); 223218334Speter else if (supports_overflow_infinity (TREE_TYPE (expr))) 223318334Speter min = positive_overflow_infinity (TREE_TYPE (expr)); 223418334Speter else 223518334Speter { 223618334Speter set_value_range_to_varying (vr); 223718334Speter return; 223818334Speter } 223918334Speter 224018334Speter if (is_overflow_infinity (vr0.max)) 224118334Speter max = positive_overflow_infinity (TREE_TYPE (expr)); 224218334Speter else if (!vrp_val_is_min (vr0.max)) 224318334Speter max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 224418334Speter else if (!needs_overflow_infinity (TREE_TYPE (expr))) 224518334Speter max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 224618334Speter else if (supports_overflow_infinity (TREE_TYPE (expr))) 224718334Speter max = positive_overflow_infinity (TREE_TYPE (expr)); 224818334Speter else 224918334Speter { 225018334Speter set_value_range_to_varying (vr); 225118334Speter return; 225218334Speter } 225318334Speter 225418334Speter cmp = compare_values (min, max); 225518334Speter 225618334Speter /* If a VR_ANTI_RANGEs contains zero, then we have 225718334Speter ~[-INF, min(MIN, MAX)]. */ 225818334Speter if (vr0.type == VR_ANTI_RANGE) 225918334Speter { 226018334Speter if (range_includes_zero_p (&vr0)) 226118334Speter { 226218334Speter /* Take the lower of the two values. */ 226318334Speter if (cmp != 1) 226418334Speter max = min; 226518334Speter 226618334Speter /* Create ~[-INF, min (abs(MIN), abs(MAX))] 226718334Speter or ~[-INF + 1, min (abs(MIN), abs(MAX))] when 226818334Speter flag_wrapv is set and the original anti-range doesn't include 226918334Speter TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ 227018334Speter if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) 227118334Speter { 227218334Speter tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); 227318334Speter 227418334Speter min = (vr0.min != type_min_value 227518334Speter ? int_const_binop (PLUS_EXPR, type_min_value, 227618334Speter integer_one_node, 0) 227718334Speter : type_min_value); 227818334Speter } 227918334Speter else 228018334Speter { 228118334Speter if (overflow_infinity_range_p (&vr0)) 228218334Speter min = negative_overflow_infinity (TREE_TYPE (expr)); 228318334Speter else 228418334Speter min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 228518334Speter } 228618334Speter } 228718334Speter else 228818334Speter { 228918334Speter /* All else has failed, so create the range [0, INF], even for 229018334Speter flag_wrapv since TYPE_MIN_VALUE is in the original 229118334Speter anti-range. */ 229218334Speter vr0.type = VR_RANGE; 229318334Speter min = build_int_cst (TREE_TYPE (expr), 0); 229418334Speter if (needs_overflow_infinity (TREE_TYPE (expr))) 229518334Speter { 229618334Speter if (supports_overflow_infinity (TREE_TYPE (expr))) 229718334Speter max = positive_overflow_infinity (TREE_TYPE (expr)); 229818334Speter else 229918334Speter { 230018334Speter set_value_range_to_varying (vr); 230118334Speter return; 230218334Speter } 230318334Speter } 230418334Speter else 230518334Speter max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 230618334Speter } 230718334Speter } 230818334Speter 230918334Speter /* If the range contains zero then we know that the minimum value in the 231018334Speter range will be zero. */ 231118334Speter else if (range_includes_zero_p (&vr0)) 231218334Speter { 231318334Speter if (cmp == 1) 231418334Speter max = min; 231518334Speter min = build_int_cst (TREE_TYPE (expr), 0); 231618334Speter } 231718334Speter else 231818334Speter { 231918334Speter /* If the range was reversed, swap MIN and MAX. */ 232018334Speter if (cmp == 1) 232118334Speter { 232218334Speter tree t = min; 232318334Speter min = max; 232418334Speter max = t; 232518334Speter } 232618334Speter } 232718334Speter } 232818334Speter else 232918334Speter { 233018334Speter /* Otherwise, operate on each end of the range. */ 233118334Speter min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 233218334Speter max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 233318334Speter 233418334Speter if (needs_overflow_infinity (TREE_TYPE (expr))) 233518334Speter { 233618334Speter gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR); 233718334Speter 233818334Speter /* If both sides have overflowed, we don't know 233918334Speter anything. */ 234018334Speter if ((is_overflow_infinity (vr0.min) 234118334Speter || TREE_OVERFLOW (min)) 234218334Speter && (is_overflow_infinity (vr0.max) 234318334Speter || TREE_OVERFLOW (max))) 234418334Speter { 234518334Speter set_value_range_to_varying (vr); 234618334Speter return; 234718334Speter } 234818334Speter 234918334Speter if (is_overflow_infinity (vr0.min)) 235018334Speter min = vr0.min; 235118334Speter else if (TREE_OVERFLOW (min)) 235218334Speter { 235318334Speter if (supports_overflow_infinity (TREE_TYPE (expr))) 235418334Speter min = (tree_int_cst_sgn (min) >= 0 235518334Speter ? positive_overflow_infinity (TREE_TYPE (min)) 235618334Speter : negative_overflow_infinity (TREE_TYPE (min))); 235718334Speter else 235818334Speter { 235918334Speter set_value_range_to_varying (vr); 236018334Speter return; 236118334Speter } 236218334Speter } 236318334Speter 236418334Speter if (is_overflow_infinity (vr0.max)) 236518334Speter max = vr0.max; 236618334Speter else if (TREE_OVERFLOW (max)) 236718334Speter { 236818334Speter if (supports_overflow_infinity (TREE_TYPE (expr))) 236918334Speter max = (tree_int_cst_sgn (max) >= 0 237018334Speter ? positive_overflow_infinity (TREE_TYPE (max)) 237118334Speter : negative_overflow_infinity (TREE_TYPE (max))); 237218334Speter else 237318334Speter { 237418334Speter set_value_range_to_varying (vr); 237518334Speter return; 237618334Speter } 237718334Speter } 237818334Speter } 237918334Speter } 238018334Speter 238118334Speter cmp = compare_values (min, max); 238218334Speter if (cmp == -2 || cmp == 1) 238318334Speter { 238418334Speter /* If the new range has its limits swapped around (MIN > MAX), 238518334Speter then the operation caused one of them to wrap around, mark 238618334Speter the new range VARYING. */ 238718334Speter set_value_range_to_varying (vr); 238818334Speter } 238918334Speter else 239018334Speter set_value_range (vr, vr0.type, min, max, NULL); 239118334Speter} 239218334Speter 239318334Speter 239418334Speter/* Extract range information from a comparison expression EXPR based 239518334Speter on the range of its operand and the expression code. */ 239618334Speter 239718334Speterstatic void 239818334Speterextract_range_from_comparison (value_range_t *vr, tree expr) 239918334Speter{ 240018334Speter bool sop = false; 240118334Speter tree val = vrp_evaluate_conditional_warnv (expr, false, &sop); 240218334Speter 240318334Speter /* A disadvantage of using a special infinity as an overflow 240418334Speter representation is that we lose the ability to record overflow 240518334Speter when we don't have an infinity. So we have to ignore a result 240618334Speter which relies on overflow. */ 240718334Speter 240818334Speter if (val && !is_overflow_infinity (val) && !sop) 240918334Speter { 241018334Speter /* Since this expression was found on the RHS of an assignment, 241118334Speter its type may be different from _Bool. Convert VAL to EXPR's 241218334Speter type. */ 241318334Speter val = fold_convert (TREE_TYPE (expr), val); 241418334Speter if (is_gimple_min_invariant (val)) 241518334Speter set_value_range_to_value (vr, val, vr->equiv); 241618334Speter else 241718334Speter set_value_range (vr, VR_RANGE, val, val, vr->equiv); 241818334Speter } 241918334Speter else 242018334Speter set_value_range_to_varying (vr); 242118334Speter} 242218334Speter 242318334Speter 242418334Speter/* Try to compute a useful range out of expression EXPR and store it 242518334Speter in *VR. */ 242618334Speter 242718334Speterstatic void 242818334Speterextract_range_from_expr (value_range_t *vr, tree expr) 242918334Speter{ 243018334Speter enum tree_code code = TREE_CODE (expr); 243118334Speter 243218334Speter if (code == ASSERT_EXPR) 243318334Speter extract_range_from_assert (vr, expr); 243418334Speter else if (code == SSA_NAME) 243518334Speter extract_range_from_ssa_name (vr, expr); 243618334Speter else if (TREE_CODE_CLASS (code) == tcc_binary 243718334Speter || code == TRUTH_ANDIF_EXPR 243818334Speter || code == TRUTH_ORIF_EXPR 243918334Speter || code == TRUTH_AND_EXPR 244018334Speter || code == TRUTH_OR_EXPR 244118334Speter || code == TRUTH_XOR_EXPR) 244218334Speter extract_range_from_binary_expr (vr, expr); 244318334Speter else if (TREE_CODE_CLASS (code) == tcc_unary) 244418334Speter extract_range_from_unary_expr (vr, expr); 244518334Speter else if (TREE_CODE_CLASS (code) == tcc_comparison) 244618334Speter extract_range_from_comparison (vr, expr); 244718334Speter else if (is_gimple_min_invariant (expr)) 244818334Speter set_value_range_to_value (vr, expr, NULL); 244918334Speter else 245018334Speter set_value_range_to_varying (vr); 245118334Speter 245218334Speter /* If we got a varying range from the tests above, try a final 245318334Speter time to derive a nonnegative or nonzero range. This time 245418334Speter relying primarily on generic routines in fold in conjunction 245518334Speter with range data. */ 245618334Speter if (vr->type == VR_VARYING) 245718334Speter { 245818334Speter bool sop = false; 245918334Speter 246018334Speter if (INTEGRAL_TYPE_P (TREE_TYPE (expr)) 246118334Speter && vrp_expr_computes_nonnegative (expr, &sop)) 246218334Speter set_value_range_to_nonnegative (vr, TREE_TYPE (expr), 246318334Speter sop || is_overflow_infinity (expr)); 246418334Speter else if (vrp_expr_computes_nonzero (expr, &sop) 246518334Speter && !sop) 246618334Speter set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 246718334Speter } 246818334Speter} 246918334Speter 247018334Speter/* Given a range VR, a LOOP and a variable VAR, determine whether it 247118334Speter would be profitable to adjust VR using scalar evolution information 247218334Speter for VAR. If so, update VR with the new limits. */ 247318334Speter 247418334Speterstatic void 247518334Speteradjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, 247618334Speter tree var) 247718334Speter{ 247818334Speter tree init, step, chrec, tmin, tmax, min, max, type; 247918334Speter enum ev_direction dir; 248018334Speter 248118334Speter /* TODO. Don't adjust anti-ranges. An anti-range may provide 248218334Speter better opportunities than a regular range, but I'm not sure. */ 248318334Speter if (vr->type == VR_ANTI_RANGE) 248418334Speter return; 248518334Speter 248618334Speter chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); 248718334Speter if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 248818334Speter return; 248918334Speter 249018334Speter init = initial_condition_in_loop_num (chrec, loop->num); 249118334Speter step = evolution_part_in_loop_num (chrec, loop->num); 249218334Speter 249318334Speter /* If STEP is symbolic, we can't know whether INIT will be the 249418334Speter minimum or maximum value in the range. Also, unless INIT is 249518334Speter a simple expression, compare_values and possibly other functions 249618334Speter in tree-vrp won't be able to handle it. */ 249718334Speter if (step == NULL_TREE 249818334Speter || !is_gimple_min_invariant (step) 249918334Speter || !valid_value_p (init)) 250018334Speter return; 250118334Speter 250218334Speter dir = scev_direction (chrec); 250318334Speter if (/* Do not adjust ranges if we do not know whether the iv increases 250418334Speter or decreases, ... */ 250518334Speter dir == EV_DIR_UNKNOWN 250618334Speter /* ... or if it may wrap. */ 250718334Speter || scev_probably_wraps_p (init, step, stmt, 250818334Speter current_loops->parray[CHREC_VARIABLE (chrec)], 250918334Speter true)) 251018334Speter return; 251118334Speter 251218334Speter type = TREE_TYPE (var); 251318334Speter 251418334Speter /* If we see a pointer type starting at a constant, then we have an 251518334Speter unusual ivopt. It may legitimately wrap. */ 251618334Speter if (POINTER_TYPE_P (type) && is_gimple_min_invariant (init)) 251718334Speter return; 251818334Speter 251918334Speter /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of 252018334Speter negative_overflow_infinity and positive_overflow_infinity, 252118334Speter because we have concluded that the loop probably does not 252218334Speter wrap. */ 252318334Speter 252418334Speter if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 252518334Speter tmin = lower_bound_in_type (type, type); 252618334Speter else 252718334Speter tmin = TYPE_MIN_VALUE (type); 252818334Speter if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 252918334Speter tmax = upper_bound_in_type (type, type); 253018334Speter else 253118334Speter tmax = TYPE_MAX_VALUE (type); 253218334Speter 253318334Speter if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 253418334Speter { 253518334Speter min = tmin; 253618334Speter max = tmax; 253718334Speter 253818334Speter /* For VARYING or UNDEFINED ranges, just about anything we get 253918334Speter from scalar evolutions should be better. */ 254018334Speter 254118334Speter if (dir == EV_DIR_DECREASES) 254218334Speter max = init; 254318334Speter else 254418334Speter min = init; 254518334Speter 254618334Speter /* If we would create an invalid range, then just assume we 254718334Speter know absolutely nothing. This may be over-conservative, 254818334Speter but it's clearly safe, and should happen only in unreachable 254918334Speter parts of code, or for invalid programs. */ 255018334Speter if (compare_values (min, max) == 1) 255118334Speter return; 255218334Speter 255318334Speter set_value_range (vr, VR_RANGE, min, max, vr->equiv); 255418334Speter } 255518334Speter else if (vr->type == VR_RANGE) 255618334Speter { 255718334Speter min = vr->min; 255818334Speter max = vr->max; 255918334Speter 256018334Speter if (dir == EV_DIR_DECREASES) 256118334Speter { 256218334Speter /* INIT is the maximum value. If INIT is lower than VR->MAX 256318334Speter but no smaller than VR->MIN, set VR->MAX to INIT. */ 256418334Speter if (compare_values (init, max) == -1) 256518334Speter { 256618334Speter max = init; 256718334Speter 256818334Speter /* If we just created an invalid range with the minimum 256918334Speter greater than the maximum, we fail conservatively. 257018334Speter This should happen only in unreachable 257118334Speter parts of code, or for invalid programs. */ 257218334Speter if (compare_values (min, max) == 1) 257318334Speter return; 257418334Speter } 257518334Speter 257618334Speter /* According to the loop information, the variable does not 257718334Speter overflow. If we think it does, probably because of an 257818334Speter overflow due to arithmetic on a different INF value, 257918334Speter reset now. */ 258018334Speter if (is_negative_overflow_infinity (min)) 258118334Speter min = tmin; 258218334Speter } 258318334Speter else 258418334Speter { 258518334Speter /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ 258618334Speter if (compare_values (init, min) == 1) 258718334Speter { 258818334Speter min = init; 258918334Speter 259018334Speter /* Again, avoid creating invalid range by failing. */ 259118334Speter if (compare_values (min, max) == 1) 259218334Speter return; 259318334Speter } 259418334Speter 259518334Speter if (is_positive_overflow_infinity (max)) 259618334Speter max = tmax; 259718334Speter } 259818334Speter 259918334Speter set_value_range (vr, VR_RANGE, min, max, vr->equiv); 260018334Speter } 260118334Speter} 260218334Speter 260318334Speter/* Return true if VAR may overflow at STMT. This checks any available 260418334Speter loop information to see if we can determine that VAR does not 260518334Speter overflow. */ 260618334Speter 260718334Speterstatic bool 260818334Spetervrp_var_may_overflow (tree var, tree stmt) 260918334Speter{ 261018334Speter struct loop *l; 261118334Speter tree chrec, init, step; 261218334Speter 261318334Speter if (current_loops == NULL) 261418334Speter return true; 261518334Speter 261618334Speter l = loop_containing_stmt (stmt); 261718334Speter if (l == NULL) 261818334Speter return true; 261918334Speter 262018334Speter chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var)); 262118334Speter if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 262218334Speter return true; 262318334Speter 262418334Speter init = initial_condition_in_loop_num (chrec, l->num); 262518334Speter step = evolution_part_in_loop_num (chrec, l->num); 262618334Speter 262718334Speter if (step == NULL_TREE 262818334Speter || !is_gimple_min_invariant (step) 262918334Speter || !valid_value_p (init)) 263018334Speter return true; 263118334Speter 263218334Speter /* If we get here, we know something useful about VAR based on the 263318334Speter loop information. If it wraps, it may overflow. */ 263418334Speter 263518334Speter if (scev_probably_wraps_p (init, step, stmt, 263618334Speter current_loops->parray[CHREC_VARIABLE (chrec)], 263718334Speter true)) 263818334Speter return true; 263918334Speter 264018334Speter if (dump_file && (dump_flags & TDF_DETAILS) != 0) 264118334Speter { 264218334Speter print_generic_expr (dump_file, var, 0); 264318334Speter fprintf (dump_file, ": loop information indicates does not overflow\n"); 264418334Speter } 264518334Speter 264618334Speter return false; 264718334Speter} 264818334Speter 264918334Speter 265018334Speter/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 265118334Speter 265218334Speter - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 265318334Speter all the values in the ranges. 265418334Speter 265518334Speter - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 265618334Speter 265718334Speter - Return NULL_TREE if it is not always possible to determine the 265818334Speter value of the comparison. 265918334Speter 266018334Speter Also set *STRICT_OVERFLOW_P to indicate whether a range with an 266118334Speter overflow infinity was used in the test. */ 266218334Speter 266318334Speter 266418334Speterstatic tree 266518334Spetercompare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, 266618334Speter bool *strict_overflow_p) 266718334Speter{ 266818334Speter /* VARYING or UNDEFINED ranges cannot be compared. */ 266918334Speter if (vr0->type == VR_VARYING 267018334Speter || vr0->type == VR_UNDEFINED 267118334Speter || vr1->type == VR_VARYING 267218334Speter || vr1->type == VR_UNDEFINED) 267318334Speter return NULL_TREE; 267418334Speter 267518334Speter /* Anti-ranges need to be handled separately. */ 267618334Speter if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 267718334Speter { 267818334Speter /* If both are anti-ranges, then we cannot compute any 267918334Speter comparison. */ 268018334Speter if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 268118334Speter return NULL_TREE; 268218334Speter 268318334Speter /* These comparisons are never statically computable. */ 268418334Speter if (comp == GT_EXPR 268518334Speter || comp == GE_EXPR 268618334Speter || comp == LT_EXPR 268718334Speter || comp == LE_EXPR) 268818334Speter return NULL_TREE; 268918334Speter 269018334Speter /* Equality can be computed only between a range and an 269118334Speter anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 269218334Speter if (vr0->type == VR_RANGE) 269318334Speter { 269418334Speter /* To simplify processing, make VR0 the anti-range. */ 269518334Speter value_range_t *tmp = vr0; 269618334Speter vr0 = vr1; 269718334Speter vr1 = tmp; 269818334Speter } 269918334Speter 270018334Speter gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 270118334Speter 270218334Speter if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0 270318334Speter && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0) 270418334Speter return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 270518334Speter 270618334Speter return NULL_TREE; 270718334Speter } 270818334Speter 270918334Speter if (!usable_range_p (vr0, strict_overflow_p) 271018334Speter || !usable_range_p (vr1, strict_overflow_p)) 271118334Speter return NULL_TREE; 271218334Speter 271318334Speter /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 271418334Speter operands around and change the comparison code. */ 271518334Speter if (comp == GT_EXPR || comp == GE_EXPR) 271618334Speter { 271718334Speter value_range_t *tmp; 271818334Speter comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 271918334Speter tmp = vr0; 272018334Speter vr0 = vr1; 272118334Speter vr1 = tmp; 272218334Speter } 272318334Speter 272418334Speter if (comp == EQ_EXPR) 272518334Speter { 272618334Speter /* Equality may only be computed if both ranges represent 272718334Speter exactly one value. */ 272818334Speter if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0 272918334Speter && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0) 273018334Speter { 273118334Speter int cmp_min = compare_values_warnv (vr0->min, vr1->min, 273218334Speter strict_overflow_p); 273318334Speter int cmp_max = compare_values_warnv (vr0->max, vr1->max, 273418334Speter strict_overflow_p); 273518334Speter if (cmp_min == 0 && cmp_max == 0) 273618334Speter return boolean_true_node; 273718334Speter else if (cmp_min != -2 && cmp_max != -2) 273818334Speter return boolean_false_node; 273918334Speter } 274018334Speter /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ 274118334Speter else if (compare_values_warnv (vr0->min, vr1->max, 274218334Speter strict_overflow_p) == 1 274318334Speter || compare_values_warnv (vr1->min, vr0->max, 274418334Speter strict_overflow_p) == 1) 274518334Speter return boolean_false_node; 274618334Speter 274718334Speter return NULL_TREE; 274818334Speter } 274918334Speter else if (comp == NE_EXPR) 275018334Speter { 275118334Speter int cmp1, cmp2; 275218334Speter 275318334Speter /* If VR0 is completely to the left or completely to the right 275418334Speter of VR1, they are always different. Notice that we need to 275518334Speter make sure that both comparisons yield similar results to 275618334Speter avoid comparing values that cannot be compared at 275718334Speter compile-time. */ 275818334Speter cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 275918334Speter cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 276018334Speter if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 276118334Speter return boolean_true_node; 276218334Speter 276318334Speter /* If VR0 and VR1 represent a single value and are identical, 276418334Speter return false. */ 276518334Speter else if (compare_values_warnv (vr0->min, vr0->max, 276618334Speter strict_overflow_p) == 0 276718334Speter && compare_values_warnv (vr1->min, vr1->max, 276818334Speter strict_overflow_p) == 0 276918334Speter && compare_values_warnv (vr0->min, vr1->min, 277018334Speter strict_overflow_p) == 0 277118334Speter && compare_values_warnv (vr0->max, vr1->max, 277218334Speter strict_overflow_p) == 0) 277318334Speter return boolean_false_node; 277418334Speter 277518334Speter /* Otherwise, they may or may not be different. */ 277618334Speter else 277718334Speter return NULL_TREE; 277818334Speter } 277918334Speter else if (comp == LT_EXPR || comp == LE_EXPR) 278018334Speter { 278118334Speter int tst; 278218334Speter 278318334Speter /* If VR0 is to the left of VR1, return true. */ 278418334Speter tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 278518334Speter if ((comp == LT_EXPR && tst == -1) 278618334Speter || (comp == LE_EXPR && (tst == -1 || tst == 0))) 278718334Speter { 278818334Speter if (overflow_infinity_range_p (vr0) 278918334Speter || overflow_infinity_range_p (vr1)) 279018334Speter *strict_overflow_p = true; 279118334Speter return boolean_true_node; 279218334Speter } 279318334Speter 279418334Speter /* If VR0 is to the right of VR1, return false. */ 279518334Speter tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 279618334Speter if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 279718334Speter || (comp == LE_EXPR && tst == 1)) 279818334Speter { 279918334Speter if (overflow_infinity_range_p (vr0) 280018334Speter || overflow_infinity_range_p (vr1)) 280118334Speter *strict_overflow_p = true; 280218334Speter return boolean_false_node; 280318334Speter } 280418334Speter 280518334Speter /* Otherwise, we don't know. */ 280618334Speter return NULL_TREE; 280718334Speter } 280818334Speter 280918334Speter gcc_unreachable (); 281018334Speter} 281118334Speter 281218334Speter 281318334Speter/* Given a value range VR, a value VAL and a comparison code COMP, return 281418334Speter BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 281518334Speter values in VR. Return BOOLEAN_FALSE_NODE if the comparison 281618334Speter always returns false. Return NULL_TREE if it is not always 281718334Speter possible to determine the value of the comparison. Also set 281818334Speter *STRICT_OVERFLOW_P to indicate whether a range with an overflow 281918334Speter infinity was used in the test. */ 282018334Speter 282118334Speterstatic tree 282218334Spetercompare_range_with_value (enum tree_code comp, value_range_t *vr, tree val, 282318334Speter bool *strict_overflow_p) 282418334Speter{ 282518334Speter if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 282618334Speter return NULL_TREE; 282718334Speter 282818334Speter /* Anti-ranges need to be handled separately. */ 282918334Speter if (vr->type == VR_ANTI_RANGE) 283018334Speter { 283118334Speter /* For anti-ranges, the only predicates that we can compute at 283218334Speter compile time are equality and inequality. */ 283318334Speter if (comp == GT_EXPR 283418334Speter || comp == GE_EXPR 283518334Speter || comp == LT_EXPR 283618334Speter || comp == LE_EXPR) 283718334Speter return NULL_TREE; 283818334Speter 283918334Speter /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 284018334Speter if (value_inside_range (val, vr) == 1) 284118334Speter return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 284218334Speter 284318334Speter return NULL_TREE; 284418334Speter } 284518334Speter 284618334Speter if (!usable_range_p (vr, strict_overflow_p)) 284718334Speter return NULL_TREE; 284818334Speter 284918334Speter if (comp == EQ_EXPR) 285018334Speter { 285118334Speter /* EQ_EXPR may only be computed if VR represents exactly 285218334Speter one value. */ 285318334Speter if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0) 285418334Speter { 285518334Speter int cmp = compare_values_warnv (vr->min, val, strict_overflow_p); 285618334Speter if (cmp == 0) 285718334Speter return boolean_true_node; 285818334Speter else if (cmp == -1 || cmp == 1 || cmp == 2) 285918334Speter return boolean_false_node; 286018334Speter } 286118334Speter else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1 286218334Speter || compare_values_warnv (vr->max, val, strict_overflow_p) == -1) 286318334Speter return boolean_false_node; 286418334Speter 286518334Speter return NULL_TREE; 286618334Speter } 286718334Speter else if (comp == NE_EXPR) 286818334Speter { 286918334Speter /* If VAL is not inside VR, then they are always different. */ 287018334Speter if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1 287118334Speter || compare_values_warnv (vr->min, val, strict_overflow_p) == 1) 287218334Speter return boolean_true_node; 287318334Speter 287418334Speter /* If VR represents exactly one value equal to VAL, then return 287518334Speter false. */ 287618334Speter if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0 287718334Speter && compare_values_warnv (vr->min, val, strict_overflow_p) == 0) 287818334Speter return boolean_false_node; 287918334Speter 288018334Speter /* Otherwise, they may or may not be different. */ 288118334Speter return NULL_TREE; 288218334Speter } 288318334Speter else if (comp == LT_EXPR || comp == LE_EXPR) 288418334Speter { 288518334Speter int tst; 288618334Speter 288718334Speter /* If VR is to the left of VAL, return true. */ 288818334Speter tst = compare_values_warnv (vr->max, val, strict_overflow_p); 288918334Speter if ((comp == LT_EXPR && tst == -1) 289018334Speter || (comp == LE_EXPR && (tst == -1 || tst == 0))) 289118334Speter { 289218334Speter if (overflow_infinity_range_p (vr)) 289318334Speter *strict_overflow_p = true; 289418334Speter return boolean_true_node; 289518334Speter } 289618334Speter 289718334Speter /* If VR is to the right of VAL, return false. */ 289818334Speter tst = compare_values_warnv (vr->min, val, strict_overflow_p); 289918334Speter if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 290018334Speter || (comp == LE_EXPR && tst == 1)) 290118334Speter { 290218334Speter if (overflow_infinity_range_p (vr)) 290318334Speter *strict_overflow_p = true; 290418334Speter return boolean_false_node; 290518334Speter } 290618334Speter 290718334Speter /* Otherwise, we don't know. */ 290818334Speter return NULL_TREE; 290918334Speter } 291018334Speter else if (comp == GT_EXPR || comp == GE_EXPR) 291118334Speter { 291218334Speter int tst; 291318334Speter 291418334Speter /* If VR is to the right of VAL, return true. */ 291518334Speter tst = compare_values_warnv (vr->min, val, strict_overflow_p); 291618334Speter if ((comp == GT_EXPR && tst == 1) 291718334Speter || (comp == GE_EXPR && (tst == 0 || tst == 1))) 291818334Speter { 291918334Speter if (overflow_infinity_range_p (vr)) 292018334Speter *strict_overflow_p = true; 292118334Speter return boolean_true_node; 292218334Speter } 292318334Speter 292418334Speter /* If VR is to the left of VAL, return false. */ 292518334Speter tst = compare_values_warnv (vr->max, val, strict_overflow_p); 292618334Speter if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 292718334Speter || (comp == GE_EXPR && tst == -1)) 292818334Speter { 292918334Speter if (overflow_infinity_range_p (vr)) 293018334Speter *strict_overflow_p = true; 293118334Speter return boolean_false_node; 293218334Speter } 293318334Speter 293418334Speter /* Otherwise, we don't know. */ 293518334Speter return NULL_TREE; 293618334Speter } 293718334Speter 293818334Speter gcc_unreachable (); 293918334Speter} 294018334Speter 294118334Speter 294218334Speter/* Debugging dumps. */ 294318334Speter 294418334Spetervoid dump_value_range (FILE *, value_range_t *); 294518334Spetervoid debug_value_range (value_range_t *); 294618334Spetervoid dump_all_value_ranges (FILE *); 294718334Spetervoid debug_all_value_ranges (void); 294818334Spetervoid dump_vr_equiv (FILE *, bitmap); 294918334Spetervoid debug_vr_equiv (bitmap); 295018334Speter 295118334Speter 295218334Speter/* Dump value range VR to FILE. */ 295318334Speter 295418334Spetervoid 295518334Speterdump_value_range (FILE *file, value_range_t *vr) 295618334Speter{ 295718334Speter if (vr == NULL) 295818334Speter fprintf (file, "[]"); 295918334Speter else if (vr->type == VR_UNDEFINED) 296018334Speter fprintf (file, "UNDEFINED"); 296118334Speter else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 296218334Speter { 296318334Speter tree type = TREE_TYPE (vr->min); 296418334Speter 296518334Speter fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 296618334Speter 296718334Speter if (is_negative_overflow_infinity (vr->min)) 296818334Speter fprintf (file, "-INF(OVF)"); 296918334Speter else if (INTEGRAL_TYPE_P (type) 297018334Speter && !TYPE_UNSIGNED (type) 297118334Speter && vrp_val_is_min (vr->min)) 297218334Speter fprintf (file, "-INF"); 297318334Speter else 297418334Speter print_generic_expr (file, vr->min, 0); 297518334Speter 297618334Speter fprintf (file, ", "); 297718334Speter 297818334Speter if (is_positive_overflow_infinity (vr->max)) 297918334Speter fprintf (file, "+INF(OVF)"); 298018334Speter else if (INTEGRAL_TYPE_P (type) 298118334Speter && vrp_val_is_max (vr->max)) 298218334Speter fprintf (file, "+INF"); 298318334Speter else 298418334Speter print_generic_expr (file, vr->max, 0); 298518334Speter 298618334Speter fprintf (file, "]"); 298718334Speter 298818334Speter if (vr->equiv) 298918334Speter { 299018334Speter bitmap_iterator bi; 299118334Speter unsigned i, c = 0; 299218334Speter 299318334Speter fprintf (file, " EQUIVALENCES: { "); 299418334Speter 299518334Speter EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 299618334Speter { 299718334Speter print_generic_expr (file, ssa_name (i), 0); 299818334Speter fprintf (file, " "); 299918334Speter c++; 300018334Speter } 300118334Speter 300218334Speter fprintf (file, "} (%u elements)", c); 300318334Speter } 300418334Speter } 300518334Speter else if (vr->type == VR_VARYING) 300618334Speter fprintf (file, "VARYING"); 300718334Speter else 300818334Speter fprintf (file, "INVALID RANGE"); 300918334Speter} 301018334Speter 301118334Speter 301218334Speter/* Dump value range VR to stderr. */ 301318334Speter 301418334Spetervoid 301518334Speterdebug_value_range (value_range_t *vr) 301618334Speter{ 301718334Speter dump_value_range (stderr, vr); 301818334Speter fprintf (stderr, "\n"); 301918334Speter} 302018334Speter 302118334Speter 302218334Speter/* Dump value ranges of all SSA_NAMEs to FILE. */ 302318334Speter 302418334Spetervoid 302518334Speterdump_all_value_ranges (FILE *file) 302618334Speter{ 302718334Speter size_t i; 302818334Speter 302918334Speter for (i = 0; i < num_ssa_names; i++) 303018334Speter { 303118334Speter if (vr_value[i]) 303218334Speter { 303318334Speter print_generic_expr (file, ssa_name (i), 0); 303418334Speter fprintf (file, ": "); 303518334Speter dump_value_range (file, vr_value[i]); 303618334Speter fprintf (file, "\n"); 303718334Speter } 303818334Speter } 303918334Speter 304018334Speter fprintf (file, "\n"); 304118334Speter} 304218334Speter 304318334Speter 304418334Speter/* Dump all value ranges to stderr. */ 304518334Speter 304618334Spetervoid 304718334Speterdebug_all_value_ranges (void) 304818334Speter{ 304918334Speter dump_all_value_ranges (stderr); 305018334Speter} 305118334Speter 305218334Speter 305318334Speter/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 305418334Speter create a new SSA name N and return the assertion assignment 305518334Speter 'V = ASSERT_EXPR <V, V OP W>'. */ 305618334Speter 305718334Speterstatic tree 305818334Speterbuild_assert_expr_for (tree cond, tree v) 305918334Speter{ 306018334Speter tree n, assertion; 306118334Speter 306218334Speter gcc_assert (TREE_CODE (v) == SSA_NAME); 306318334Speter n = duplicate_ssa_name (v, NULL_TREE); 306418334Speter 306518334Speter if (COMPARISON_CLASS_P (cond)) 306618334Speter { 306718334Speter tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 306818334Speter assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a); 306918334Speter } 307018334Speter else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 307118334Speter { 307218334Speter /* Given !V, build the assignment N = false. */ 307318334Speter tree op0 = TREE_OPERAND (cond, 0); 307418334Speter gcc_assert (op0 == v); 307518334Speter assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node); 307618334Speter } 307718334Speter else if (TREE_CODE (cond) == SSA_NAME) 307818334Speter { 307918334Speter /* Given V, build the assignment N = true. */ 308018334Speter gcc_assert (v == cond); 308118334Speter assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); 308218334Speter } 308318334Speter else 308418334Speter gcc_unreachable (); 308518334Speter 308618334Speter SSA_NAME_DEF_STMT (n) = assertion; 308718334Speter 308818334Speter /* The new ASSERT_EXPR, creates a new SSA name that replaces the 308918334Speter operand of the ASSERT_EXPR. Register the new name and the old one 309018334Speter in the replacement table so that we can fix the SSA web after 309118334Speter adding all the ASSERT_EXPRs. */ 309218334Speter register_new_name_mapping (n, v); 309318334Speter 309418334Speter return assertion; 309518334Speter} 309618334Speter 309718334Speter 309818334Speter/* Return false if EXPR is a predicate expression involving floating 309918334Speter point values. */ 310018334Speter 310118334Speterstatic inline bool 310218334Speterfp_predicate (tree expr) 310318334Speter{ 310418334Speter return (COMPARISON_CLASS_P (expr) 310518334Speter && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); 310618334Speter} 310718334Speter 310818334Speter 310918334Speter/* If the range of values taken by OP can be inferred after STMT executes, 311018334Speter return the comparison code (COMP_CODE_P) and value (VAL_P) that 311118334Speter describes the inferred range. Return true if a range could be 311218334Speter inferred. */ 311318334Speter 311418334Speterstatic bool 311518334Speterinfer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) 311618334Speter{ 311718334Speter *val_p = NULL_TREE; 311818334Speter *comp_code_p = ERROR_MARK; 311918334Speter 312018334Speter /* Do not attempt to infer anything in names that flow through 312118334Speter abnormal edges. */ 312218334Speter if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 312318334Speter return false; 312418334Speter 312518334Speter /* Similarly, don't infer anything from statements that may throw 312618334Speter exceptions. */ 312718334Speter if (tree_could_throw_p (stmt)) 312818334Speter return false; 312918334Speter 313018334Speter /* If STMT is the last statement of a basic block with no 313118334Speter successors, there is no point inferring anything about any of its 313218334Speter operands. We would not be able to find a proper insertion point 313318334Speter for the assertion, anyway. */ 313418334Speter if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) 313518334Speter return false; 313618334Speter 313718334Speter /* We can only assume that a pointer dereference will yield 313818334Speter non-NULL if -fdelete-null-pointer-checks is enabled. */ 313918334Speter if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op))) 314018334Speter { 314118334Speter bool is_store; 314218334Speter unsigned num_uses, num_derefs; 314318334Speter 314418334Speter count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 314518334Speter if (num_derefs > 0) 314618334Speter { 314718334Speter *val_p = build_int_cst (TREE_TYPE (op), 0); 314818334Speter *comp_code_p = NE_EXPR; 314918334Speter return true; 315018334Speter } 315118334Speter } 315218334Speter 315318334Speter return false; 315418334Speter} 315518334Speter 315618334Speter 315718334Spetervoid dump_asserts_for (FILE *, tree); 315818334Spetervoid debug_asserts_for (tree); 315918334Spetervoid dump_all_asserts (FILE *); 316018334Spetervoid debug_all_asserts (void); 316118334Speter 316218334Speter/* Dump all the registered assertions for NAME to FILE. */ 316318334Speter 316418334Spetervoid 316518334Speterdump_asserts_for (FILE *file, tree name) 316618334Speter{ 316718334Speter assert_locus_t loc; 316818334Speter 316918334Speter fprintf (file, "Assertions to be inserted for "); 317018334Speter print_generic_expr (file, name, 0); 317118334Speter fprintf (file, "\n"); 317218334Speter 317318334Speter loc = asserts_for[SSA_NAME_VERSION (name)]; 317418334Speter while (loc) 317518334Speter { 317618334Speter fprintf (file, "\t"); 317718334Speter print_generic_expr (file, bsi_stmt (loc->si), 0); 317818334Speter fprintf (file, "\n\tBB #%d", loc->bb->index); 317918334Speter if (loc->e) 318018334Speter { 318118334Speter fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 318218334Speter loc->e->dest->index); 318318334Speter dump_edge_info (file, loc->e, 0); 318418334Speter } 318518334Speter fprintf (file, "\n\tPREDICATE: "); 318618334Speter print_generic_expr (file, name, 0); 318718334Speter fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]); 318818334Speter print_generic_expr (file, loc->val, 0); 318918334Speter fprintf (file, "\n\n"); 319018334Speter loc = loc->next; 319118334Speter } 319218334Speter 319318334Speter fprintf (file, "\n"); 319418334Speter} 319518334Speter 319618334Speter 319718334Speter/* Dump all the registered assertions for NAME to stderr. */ 319818334Speter 319918334Spetervoid 320018334Speterdebug_asserts_for (tree name) 320118334Speter{ 320218334Speter dump_asserts_for (stderr, name); 320318334Speter} 320418334Speter 320518334Speter 320618334Speter/* Dump all the registered assertions for all the names to FILE. */ 320718334Speter 320818334Spetervoid 320918334Speterdump_all_asserts (FILE *file) 321018334Speter{ 321118334Speter unsigned i; 321218334Speter bitmap_iterator bi; 321318334Speter 321418334Speter fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 321518334Speter EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 321618334Speter dump_asserts_for (file, ssa_name (i)); 321718334Speter fprintf (file, "\n"); 321818334Speter} 321918334Speter 322018334Speter 322118334Speter/* Dump all the registered assertions for all the names to stderr. */ 322218334Speter 322318334Spetervoid 322418334Speterdebug_all_asserts (void) 322518334Speter{ 322618334Speter dump_all_asserts (stderr); 322718334Speter} 322818334Speter 322918334Speter 323018334Speter/* If NAME doesn't have an ASSERT_EXPR registered for asserting 323118334Speter 'NAME COMP_CODE VAL' at a location that dominates block BB or 323218334Speter E->DEST, then register this location as a possible insertion point 323318334Speter for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. 323418334Speter 323518334Speter BB, E and SI provide the exact insertion point for the new 323618334Speter ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 323718334Speter on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 323818334Speter BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 323918334Speter must not be NULL. */ 324018334Speter 324118334Speterstatic void 324218334Speterregister_new_assert_for (tree name, 324318334Speter enum tree_code comp_code, 324418334Speter tree val, 324518334Speter basic_block bb, 324618334Speter edge e, 324718334Speter block_stmt_iterator si) 324818334Speter{ 324918334Speter assert_locus_t n, loc, last_loc; 325018334Speter bool found; 325118334Speter basic_block dest_bb; 325218334Speter 325318334Speter#if defined ENABLE_CHECKING 325418334Speter gcc_assert (bb == NULL || e == NULL); 325518334Speter 325618334Speter if (e == NULL) 325718334Speter gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR 325818334Speter && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR); 325918334Speter#endif 326018334Speter 326118334Speter /* The new assertion A will be inserted at BB or E. We need to 326218334Speter determine if the new location is dominated by a previously 326318334Speter registered location for A. If we are doing an edge insertion, 326418334Speter assume that A will be inserted at E->DEST. Note that this is not 326518334Speter necessarily true. 326618334Speter 326718334Speter If E is a critical edge, it will be split. But even if E is 326818334Speter split, the new block will dominate the same set of blocks that 326918334Speter E->DEST dominates. 327018334Speter 327118334Speter The reverse, however, is not true, blocks dominated by E->DEST 327218334Speter will not be dominated by the new block created to split E. So, 327318334Speter if the insertion location is on a critical edge, we will not use 327418334Speter the new location to move another assertion previously registered 327518334Speter at a block dominated by E->DEST. */ 327618334Speter dest_bb = (bb) ? bb : e->dest; 327718334Speter 327818334Speter /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 327918334Speter VAL at a block dominating DEST_BB, then we don't need to insert a new 328018334Speter one. Similarly, if the same assertion already exists at a block 328118334Speter dominated by DEST_BB and the new location is not on a critical 328218334Speter edge, then update the existing location for the assertion (i.e., 328318334Speter move the assertion up in the dominance tree). 328418334Speter 328518334Speter Note, this is implemented as a simple linked list because there 328618334Speter should not be more than a handful of assertions registered per 328718334Speter name. If this becomes a performance problem, a table hashed by 328818334Speter COMP_CODE and VAL could be implemented. */ 328918334Speter loc = asserts_for[SSA_NAME_VERSION (name)]; 329018334Speter last_loc = loc; 329118334Speter found = false; 329218334Speter while (loc) 329318334Speter { 329418334Speter if (loc->comp_code == comp_code 329518334Speter && (loc->val == val 329618334Speter || operand_equal_p (loc->val, val, 0))) 329718334Speter { 329818334Speter /* If the assertion NAME COMP_CODE VAL has already been 329918334Speter registered at a basic block that dominates DEST_BB, then 330018334Speter we don't need to insert the same assertion again. Note 330118334Speter that we don't check strict dominance here to avoid 330218334Speter replicating the same assertion inside the same basic 330318334Speter block more than once (e.g., when a pointer is 330418334Speter dereferenced several times inside a block). 330518334Speter 330618334Speter An exception to this rule are edge insertions. If the 330718334Speter new assertion is to be inserted on edge E, then it will 330818334Speter dominate all the other insertions that we may want to 330918334Speter insert in DEST_BB. So, if we are doing an edge 331018334Speter insertion, don't do this dominance check. */ 331118334Speter if (e == NULL 331218334Speter && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) 331318334Speter return; 331418334Speter 331518334Speter /* Otherwise, if E is not a critical edge and DEST_BB 331618334Speter dominates the existing location for the assertion, move 331718334Speter the assertion up in the dominance tree by updating its 331818334Speter location information. */ 331918334Speter if ((e == NULL || !EDGE_CRITICAL_P (e)) 332018334Speter && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 332118334Speter { 332218334Speter loc->bb = dest_bb; 332318334Speter loc->e = e; 332418334Speter loc->si = si; 332518334Speter return; 332618334Speter } 332718334Speter } 332818334Speter 332918334Speter /* Update the last node of the list and move to the next one. */ 333018334Speter last_loc = loc; 333118334Speter loc = loc->next; 333218334Speter } 333318334Speter 333418334Speter /* If we didn't find an assertion already registered for 333518334Speter NAME COMP_CODE VAL, add a new one at the end of the list of 333618334Speter assertions associated with NAME. */ 333718334Speter n = XNEW (struct assert_locus_d); 333818334Speter n->bb = dest_bb; 333918334Speter n->e = e; 334018334Speter n->si = si; 334118334Speter n->comp_code = comp_code; 334218334Speter n->val = val; 334318334Speter n->next = NULL; 334418334Speter 334518334Speter if (last_loc) 334618334Speter last_loc->next = n; 334718334Speter else 334818334Speter asserts_for[SSA_NAME_VERSION (name)] = n; 334918334Speter 335018334Speter bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 335118334Speter} 335218334Speter 335318334Speter 335418334Speter/* Try to register an edge assertion for SSA name NAME on edge E for 335518334Speter the conditional jump pointed to by SI. Return true if an assertion 335618334Speter for NAME could be registered. */ 335718334Speter 335818334Speterstatic bool 335918334Speterregister_edge_assert_for (tree name, edge e, block_stmt_iterator si) 336018334Speter{ 336118334Speter tree val, stmt; 336218334Speter enum tree_code comp_code; 336318334Speter 336418334Speter stmt = bsi_stmt (si); 336518334Speter 336618334Speter /* Do not attempt to infer anything in names that flow through 336718334Speter abnormal edges. */ 336818334Speter if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 336918334Speter return false; 337018334Speter 337118334Speter /* If NAME was not found in the sub-graph reachable from E, then 337218334Speter there's nothing to do. */ 337318334Speter if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) 337418334Speter return false; 337518334Speter 337618334Speter /* We found a use of NAME in the sub-graph rooted at E->DEST. 337718334Speter Register an assertion for NAME according to the value that NAME 337818334Speter takes on edge E. */ 337918334Speter if (TREE_CODE (stmt) == COND_EXPR) 338018334Speter { 338118334Speter /* If BB ends in a COND_EXPR then NAME then we should insert 338218334Speter the original predicate on EDGE_TRUE_VALUE and the 338318334Speter opposite predicate on EDGE_FALSE_VALUE. */ 338418334Speter tree cond = COND_EXPR_COND (stmt); 338518334Speter bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 338618334Speter 338718334Speter /* Predicates may be a single SSA name or NAME OP VAL. */ 338818334Speter if (cond == name) 338918334Speter { 339018334Speter /* If the predicate is a name, it must be NAME, in which 339118334Speter case we create the predicate NAME == true or 339218334Speter NAME == false accordingly. */ 339318334Speter comp_code = EQ_EXPR; 339418334Speter val = (is_else_edge) ? boolean_false_node : boolean_true_node; 339518334Speter } 339618334Speter else 339718334Speter { 339818334Speter /* Otherwise, we have a comparison of the form NAME COMP VAL 339918334Speter or VAL COMP NAME. */ 340018334Speter if (name == TREE_OPERAND (cond, 1)) 340118334Speter { 340218334Speter /* If the predicate is of the form VAL COMP NAME, flip 340318334Speter COMP around because we need to register NAME as the 340418334Speter first operand in the predicate. */ 340518334Speter comp_code = swap_tree_comparison (TREE_CODE (cond)); 340618334Speter val = TREE_OPERAND (cond, 0); 340718334Speter } 340818334Speter else 340918334Speter { 341018334Speter /* The comparison is of the form NAME COMP VAL, so the 341118334Speter comparison code remains unchanged. */ 341218334Speter comp_code = TREE_CODE (cond); 341318334Speter val = TREE_OPERAND (cond, 1); 341418334Speter } 341518334Speter 341618334Speter /* If we are inserting the assertion on the ELSE edge, we 341718334Speter need to invert the sign comparison. */ 341818334Speter if (is_else_edge) 341918334Speter comp_code = invert_tree_comparison (comp_code, 0); 342018334Speter 342118334Speter /* Do not register always-false predicates. FIXME, this 342218334Speter works around a limitation in fold() when dealing with 342318334Speter enumerations. Given 'enum { N1, N2 } x;', fold will not 342418334Speter fold 'if (x > N2)' to 'if (0)'. */ 342518334Speter if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 342618334Speter && (INTEGRAL_TYPE_P (TREE_TYPE (val)) 342718334Speter || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))) 342818334Speter { 342918334Speter tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 343018334Speter tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 343118334Speter 343218334Speter if (comp_code == GT_EXPR && compare_values (val, max) == 0) 343318334Speter return false; 343418334Speter 343518334Speter if (comp_code == LT_EXPR && compare_values (val, min) == 0) 343618334Speter return false; 343718334Speter } 343818334Speter } 343918334Speter } 344018334Speter else 344118334Speter { 344218334Speter /* FIXME. Handle SWITCH_EXPR. */ 344318334Speter gcc_unreachable (); 344418334Speter } 344518334Speter 344618334Speter register_new_assert_for (name, comp_code, val, NULL, e, si); 344718334Speter return true; 344818334Speter} 344918334Speter 345018334Speter 345118334Speterstatic bool find_assert_locations (basic_block bb); 345218334Speter 345318334Speter/* Determine whether the outgoing edges of BB should receive an 345418334Speter ASSERT_EXPR for each of the operands of BB's last statement. The 345518334Speter last statement of BB must be a COND_EXPR or a SWITCH_EXPR. 345618334Speter 345718334Speter If any of the sub-graphs rooted at BB have an interesting use of 345818334Speter the predicate operands, an assert location node is added to the 345918334Speter list of assertions for the corresponding operands. */ 346018334Speter 346118334Speterstatic bool 346218334Speterfind_conditional_asserts (basic_block bb) 346318334Speter{ 346418334Speter bool need_assert; 346518334Speter block_stmt_iterator last_si; 346618334Speter tree op, last; 346718334Speter edge_iterator ei; 346818334Speter edge e; 346918334Speter ssa_op_iter iter; 347018334Speter 347118334Speter need_assert = false; 347218334Speter last_si = bsi_last (bb); 347318334Speter last = bsi_stmt (last_si); 347418334Speter 347518334Speter /* Look for uses of the operands in each of the sub-graphs 347618334Speter rooted at BB. We need to check each of the outgoing edges 347718334Speter separately, so that we know what kind of ASSERT_EXPR to 347818334Speter insert. */ 347918334Speter FOR_EACH_EDGE (e, ei, bb->succs) 348018334Speter { 348118334Speter if (e->dest == bb) 348218334Speter continue; 348318334Speter 348418334Speter /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. 348518334Speter Otherwise, when we finish traversing each of the sub-graphs, we 348618334Speter won't know whether the variables were found in the sub-graphs or 348718334Speter if they had been found in a block upstream from BB. 348818334Speter 348918334Speter This is actually a bad idea is some cases, particularly jump 349018334Speter threading. Consider a CFG like the following: 349118334Speter 349218334Speter 0 349318334Speter /| 349418334Speter 1 | 349518334Speter \| 349618334Speter 2 349718334Speter / \ 349818334Speter 3 4 349918334Speter 350018334Speter Assume that one or more operands in the conditional at the 350118334Speter end of block 0 are used in a conditional in block 2, but not 350218334Speter anywhere in block 1. In this case we will not insert any 350318334Speter assert statements in block 1, which may cause us to miss 350418334Speter opportunities to optimize, particularly for jump threading. */ 350518334Speter FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 350618334Speter RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 350718334Speter 350818334Speter /* Traverse the strictly dominated sub-graph rooted at E->DEST 350918334Speter to determine if any of the operands in the conditional 351018334Speter predicate are used. */ 351118334Speter if (e->dest != bb) 351218334Speter need_assert |= find_assert_locations (e->dest); 351318334Speter 351418334Speter /* Register the necessary assertions for each operand in the 351518334Speter conditional predicate. */ 351618334Speter FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 351718334Speter need_assert |= register_edge_assert_for (op, e, last_si); 351818334Speter } 351918334Speter 352018334Speter /* Finally, indicate that we have found the operands in the 352118334Speter conditional. */ 352218334Speter FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 352318334Speter SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 352418334Speter 352518334Speter return need_assert; 352618334Speter} 352718334Speter 352818334Speter 352918334Speter/* Traverse all the statements in block BB looking for statements that 353018334Speter may generate useful assertions for the SSA names in their operand. 353118334Speter If a statement produces a useful assertion A for name N_i, then the 353218334Speter list of assertions already generated for N_i is scanned to 353318334Speter determine if A is actually needed. 353418334Speter 353518334Speter If N_i already had the assertion A at a location dominating the 353618334Speter current location, then nothing needs to be done. Otherwise, the 353718334Speter new location for A is recorded instead. 353818334Speter 353918334Speter 1- For every statement S in BB, all the variables used by S are 354018334Speter added to bitmap FOUND_IN_SUBGRAPH. 354118334Speter 354218334Speter 2- If statement S uses an operand N in a way that exposes a known 354318334Speter value range for N, then if N was not already generated by an 354418334Speter ASSERT_EXPR, create a new assert location for N. For instance, 354518334Speter if N is a pointer and the statement dereferences it, we can 354618334Speter assume that N is not NULL. 354718334Speter 354818334Speter 3- COND_EXPRs are a special case of #2. We can derive range 354918334Speter information from the predicate but need to insert different 355018334Speter ASSERT_EXPRs for each of the sub-graphs rooted at the 355118334Speter conditional block. If the last statement of BB is a conditional 355218334Speter expression of the form 'X op Y', then 355318334Speter 355418334Speter a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 355518334Speter 355618334Speter b) If the conditional is the only entry point to the sub-graph 355718334Speter corresponding to the THEN_CLAUSE, recurse into it. On 355818334Speter return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 355918334Speter an ASSERT_EXPR is added for the corresponding variable. 356018334Speter 356118334Speter c) Repeat step (b) on the ELSE_CLAUSE. 356218334Speter 356318334Speter d) Mark X and Y in FOUND_IN_SUBGRAPH. 356418334Speter 356518334Speter For instance, 356618334Speter 356718334Speter if (a == 9) 356818334Speter b = a; 356918334Speter else 357018334Speter b = c + 1; 357118334Speter 357218334Speter In this case, an assertion on the THEN clause is useful to 357318334Speter determine that 'a' is always 9 on that edge. However, an assertion 357418334Speter on the ELSE clause would be unnecessary. 357518334Speter 357618334Speter 4- If BB does not end in a conditional expression, then we recurse 357718334Speter into BB's dominator children. 357818334Speter 357918334Speter At the end of the recursive traversal, every SSA name will have a 358018334Speter list of locations where ASSERT_EXPRs should be added. When a new 358118334Speter location for name N is found, it is registered by calling 358218334Speter register_new_assert_for. That function keeps track of all the 358318334Speter registered assertions to prevent adding unnecessary assertions. 358418334Speter For instance, if a pointer P_4 is dereferenced more than once in a 358518334Speter dominator tree, only the location dominating all the dereference of 358618334Speter P_4 will receive an ASSERT_EXPR. 358718334Speter 358818334Speter If this function returns true, then it means that there are names 358918334Speter for which we need to generate ASSERT_EXPRs. Those assertions are 359018334Speter inserted by process_assert_insertions. 359118334Speter 359218334Speter TODO. Handle SWITCH_EXPR. */ 359318334Speter 359418334Speterstatic bool 359518334Speterfind_assert_locations (basic_block bb) 359618334Speter{ 359718334Speter block_stmt_iterator si; 359818334Speter tree last, phi; 359918334Speter bool need_assert; 360018334Speter basic_block son; 360118334Speter 360218334Speter if (TEST_BIT (blocks_visited, bb->index)) 360318334Speter return false; 360418334Speter 360518334Speter SET_BIT (blocks_visited, bb->index); 360618334Speter 360718334Speter need_assert = false; 360818334Speter 360918334Speter /* Traverse all PHI nodes in BB marking used operands. */ 361018334Speter for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 361118334Speter { 361218334Speter use_operand_p arg_p; 361318334Speter ssa_op_iter i; 361418334Speter 361518334Speter FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 361618334Speter { 361718334Speter tree arg = USE_FROM_PTR (arg_p); 361818334Speter if (TREE_CODE (arg) == SSA_NAME) 361918334Speter { 362018334Speter gcc_assert (is_gimple_reg (PHI_RESULT (phi))); 362118334Speter SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg)); 362218334Speter } 362318334Speter } 362418334Speter } 362518334Speter 362618334Speter /* Traverse all the statements in BB marking used names and looking 362718334Speter for statements that may infer assertions for their used operands. */ 362818334Speter last = NULL_TREE; 362918334Speter for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 363018334Speter { 363118334Speter tree stmt, op; 363218334Speter ssa_op_iter i; 363318334Speter 363418334Speter stmt = bsi_stmt (si); 363518334Speter 363618334Speter /* See if we can derive an assertion for any of STMT's operands. */ 363718334Speter FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 363818334Speter { 363918334Speter tree value; 364018334Speter enum tree_code comp_code; 364118334Speter 364218334Speter /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside 364318334Speter the sub-graph of a conditional block, when we return from 364418334Speter this recursive walk, our parent will use the 364518334Speter FOUND_IN_SUBGRAPH bitset to determine if one of the 364618334Speter operands it was looking for was present in the sub-graph. */ 364718334Speter SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 364818334Speter 364918334Speter /* If OP is used in such a way that we can infer a value 365018334Speter range for it, and we don't find a previous assertion for 365118334Speter it, create a new assertion location node for OP. */ 365218334Speter if (infer_value_range (stmt, op, &comp_code, &value)) 365318334Speter { 365418334Speter /* If we are able to infer a nonzero value range for OP, 365518334Speter then walk backwards through the use-def chain to see if OP 365618334Speter was set via a typecast. 365718334Speter 365818334Speter If so, then we can also infer a nonzero value range 365918334Speter for the operand of the NOP_EXPR. */ 366018334Speter if (comp_code == NE_EXPR && integer_zerop (value)) 366118334Speter { 366218334Speter tree t = op; 366318334Speter tree def_stmt = SSA_NAME_DEF_STMT (t); 366418334Speter 366518334Speter while (TREE_CODE (def_stmt) == MODIFY_EXPR 366618334Speter && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR 366718334Speter && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME 366818334Speter && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)))) 366918334Speter { 367018334Speter t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 367118334Speter def_stmt = SSA_NAME_DEF_STMT (t); 367218334Speter 367318334Speter /* Note we want to register the assert for the 367418334Speter operand of the NOP_EXPR after SI, not after the 367518334Speter conversion. */ 367618334Speter if (! has_single_use (t)) 367718334Speter { 367818334Speter register_new_assert_for (t, comp_code, value, 367918334Speter bb, NULL, si); 368018334Speter need_assert = true; 368118334Speter } 368218334Speter } 368318334Speter } 368418334Speter 368518334Speter /* If OP is used only once, namely in this STMT, don't 368618334Speter bother creating an ASSERT_EXPR for it. Such an 368718334Speter ASSERT_EXPR would do nothing but increase compile time. */ 368818334Speter if (!has_single_use (op)) 368918334Speter { 369018334Speter register_new_assert_for (op, comp_code, value, bb, NULL, si); 369118334Speter need_assert = true; 369218334Speter } 369318334Speter } 369418334Speter } 369518334Speter 369618334Speter /* Remember the last statement of the block. */ 369718334Speter last = stmt; 369818334Speter } 369918334Speter 370018334Speter /* If BB's last statement is a conditional expression 370118334Speter involving integer operands, recurse into each of the sub-graphs 370218334Speter rooted at BB to determine if we need to add ASSERT_EXPRs. */ 370318334Speter if (last 370418334Speter && TREE_CODE (last) == COND_EXPR 370518334Speter && !fp_predicate (COND_EXPR_COND (last)) 370618334Speter && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 370718334Speter need_assert |= find_conditional_asserts (bb); 370818334Speter 370918334Speter /* Recurse into the dominator children of BB. */ 371018334Speter for (son = first_dom_son (CDI_DOMINATORS, bb); 371118334Speter son; 371218334Speter son = next_dom_son (CDI_DOMINATORS, son)) 371318334Speter need_assert |= find_assert_locations (son); 371418334Speter 371518334Speter return need_assert; 371618334Speter} 371718334Speter 371818334Speter 371918334Speter/* Create an ASSERT_EXPR for NAME and insert it in the location 372018334Speter indicated by LOC. Return true if we made any edge insertions. */ 372118334Speter 372218334Speterstatic bool 372318334Speterprocess_assert_insertions_for (tree name, assert_locus_t loc) 372418334Speter{ 372518334Speter /* Build the comparison expression NAME_i COMP_CODE VAL. */ 372618334Speter tree stmt, cond, assert_expr; 372718334Speter edge_iterator ei; 372818334Speter edge e; 372918334Speter 373018334Speter cond = build2 (loc->comp_code, boolean_type_node, name, loc->val); 373118334Speter assert_expr = build_assert_expr_for (cond, name); 373218334Speter 373318334Speter if (loc->e) 373418334Speter { 373518334Speter /* We have been asked to insert the assertion on an edge. This 373618334Speter is used only by COND_EXPR and SWITCH_EXPR assertions. */ 373718334Speter#if defined ENABLE_CHECKING 373818334Speter gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR 373918334Speter || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR); 374018334Speter#endif 374118334Speter 374218334Speter bsi_insert_on_edge (loc->e, assert_expr); 374318334Speter return true; 374418334Speter } 374518334Speter 374618334Speter /* Otherwise, we can insert right after LOC->SI iff the 374718334Speter statement must not be the last statement in the block. */ 374818334Speter stmt = bsi_stmt (loc->si); 374918334Speter if (!stmt_ends_bb_p (stmt)) 375018334Speter { 375118334Speter bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); 375218334Speter return false; 375318334Speter } 375418334Speter 375518334Speter /* If STMT must be the last statement in BB, we can only insert new 375618334Speter assertions on the non-abnormal edge out of BB. Note that since 375718334Speter STMT is not control flow, there may only be one non-abnormal edge 375818334Speter out of BB. */ 375918334Speter FOR_EACH_EDGE (e, ei, loc->bb->succs) 376018334Speter if (!(e->flags & EDGE_ABNORMAL)) 376118334Speter { 376218334Speter bsi_insert_on_edge (e, assert_expr); 376318334Speter return true; 376418334Speter } 376518334Speter 376618334Speter gcc_unreachable (); 376718334Speter} 376818334Speter 376918334Speter 377018334Speter/* Process all the insertions registered for every name N_i registered 377118334Speter in NEED_ASSERT_FOR. The list of assertions to be inserted are 377218334Speter found in ASSERTS_FOR[i]. */ 377318334Speter 377418334Speterstatic void 377518334Speterprocess_assert_insertions (void) 377618334Speter{ 377718334Speter unsigned i; 377818334Speter bitmap_iterator bi; 377918334Speter bool update_edges_p = false; 378018334Speter int num_asserts = 0; 378118334Speter 378218334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 378318334Speter dump_all_asserts (dump_file); 378418334Speter 378518334Speter EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 378618334Speter { 378718334Speter assert_locus_t loc = asserts_for[i]; 378818334Speter gcc_assert (loc); 378918334Speter 379018334Speter while (loc) 379118334Speter { 379218334Speter assert_locus_t next = loc->next; 379318334Speter update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 379418334Speter free (loc); 379518334Speter loc = next; 379618334Speter num_asserts++; 379718334Speter } 379818334Speter } 379918334Speter 380018334Speter if (update_edges_p) 380118334Speter bsi_commit_edge_inserts (); 380218334Speter 380318334Speter if (dump_file && (dump_flags & TDF_STATS)) 380418334Speter fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n", 380518334Speter num_asserts); 380618334Speter} 380718334Speter 380818334Speter 380918334Speter/* Traverse the flowgraph looking for conditional jumps to insert range 381018334Speter expressions. These range expressions are meant to provide information 381118334Speter to optimizations that need to reason in terms of value ranges. They 381218334Speter will not be expanded into RTL. For instance, given: 381318334Speter 381418334Speter x = ... 381518334Speter y = ... 381618334Speter if (x < y) 381718334Speter y = x - 2; 381818334Speter else 381918334Speter x = y + 3; 382018334Speter 382118334Speter this pass will transform the code into: 382218334Speter 382318334Speter x = ... 382418334Speter y = ... 382518334Speter if (x < y) 382618334Speter { 382718334Speter x = ASSERT_EXPR <x, x < y> 382818334Speter y = x - 2 382918334Speter } 383018334Speter else 383118334Speter { 383218334Speter y = ASSERT_EXPR <y, x <= y> 383318334Speter x = y + 3 383418334Speter } 383518334Speter 383618334Speter The idea is that once copy and constant propagation have run, other 383718334Speter optimizations will be able to determine what ranges of values can 'x' 383818334Speter take in different paths of the code, simply by checking the reaching 383918334Speter definition of 'x'. */ 384018334Speter 384118334Speterstatic void 384218334Speterinsert_range_assertions (void) 384318334Speter{ 384418334Speter edge e; 384518334Speter edge_iterator ei; 384618334Speter bool update_ssa_p; 384718334Speter 384818334Speter found_in_subgraph = sbitmap_alloc (num_ssa_names); 384918334Speter sbitmap_zero (found_in_subgraph); 385018334Speter 385118334Speter blocks_visited = sbitmap_alloc (last_basic_block); 385218334Speter sbitmap_zero (blocks_visited); 385318334Speter 385418334Speter need_assert_for = BITMAP_ALLOC (NULL); 385518334Speter asserts_for = XNEWVEC (assert_locus_t, num_ssa_names); 385618334Speter memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t)); 385718334Speter 385818334Speter calculate_dominance_info (CDI_DOMINATORS); 385918334Speter 386018334Speter update_ssa_p = false; 386118334Speter FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 386218334Speter if (find_assert_locations (e->dest)) 386318334Speter update_ssa_p = true; 386418334Speter 386518334Speter if (update_ssa_p) 386618334Speter { 386718334Speter process_assert_insertions (); 386818334Speter update_ssa (TODO_update_ssa_no_phi); 386918334Speter } 387018334Speter 387118334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 387218334Speter { 387318334Speter fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 387418334Speter dump_function_to_file (current_function_decl, dump_file, dump_flags); 387518334Speter } 387618334Speter 387718334Speter sbitmap_free (found_in_subgraph); 387818334Speter free (asserts_for); 387918334Speter BITMAP_FREE (need_assert_for); 388018334Speter} 388118334Speter 388218334Speter 388318334Speter/* Convert range assertion expressions into the implied copies and 388418334Speter copy propagate away the copies. Doing the trivial copy propagation 388518334Speter here avoids the need to run the full copy propagation pass after 388618334Speter VRP. 388718334Speter 388818334Speter FIXME, this will eventually lead to copy propagation removing the 388918334Speter names that had useful range information attached to them. For 389018334Speter instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 389118334Speter then N_i will have the range [3, +INF]. 389218334Speter 389318334Speter However, by converting the assertion into the implied copy 389418334Speter operation N_i = N_j, we will then copy-propagate N_j into the uses 389518334Speter of N_i and lose the range information. We may want to hold on to 389618334Speter ASSERT_EXPRs a little while longer as the ranges could be used in 389718334Speter things like jump threading. 389818334Speter 389918334Speter The problem with keeping ASSERT_EXPRs around is that passes after 390018334Speter VRP need to handle them appropriately. 390118334Speter 390218334Speter Another approach would be to make the range information a first 390318334Speter class property of the SSA_NAME so that it can be queried from 390418334Speter any pass. This is made somewhat more complex by the need for 390518334Speter multiple ranges to be associated with one SSA_NAME. */ 390618334Speter 390718334Speterstatic void 390818334Speterremove_range_assertions (void) 390918334Speter{ 391018334Speter basic_block bb; 391118334Speter block_stmt_iterator si; 391218334Speter 391318334Speter /* Note that the BSI iterator bump happens at the bottom of the 391418334Speter loop and no bump is necessary if we're removing the statement 391518334Speter referenced by the current BSI. */ 391618334Speter FOR_EACH_BB (bb) 391718334Speter for (si = bsi_start (bb); !bsi_end_p (si);) 391818334Speter { 391918334Speter tree stmt = bsi_stmt (si); 392018334Speter tree use_stmt; 392118334Speter 392218334Speter if (TREE_CODE (stmt) == MODIFY_EXPR 392318334Speter && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 392418334Speter { 392518334Speter tree rhs = TREE_OPERAND (stmt, 1), var; 392618334Speter tree cond = fold (ASSERT_EXPR_COND (rhs)); 392718334Speter use_operand_p use_p; 392818334Speter imm_use_iterator iter; 392918334Speter 393018334Speter gcc_assert (cond != boolean_false_node); 393118334Speter 393218334Speter /* Propagate the RHS into every use of the LHS. */ 393318334Speter var = ASSERT_EXPR_VAR (rhs); 393418334Speter FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0)) 393518334Speter FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 393618334Speter { 393718334Speter SET_USE (use_p, var); 393818334Speter gcc_assert (TREE_CODE (var) == SSA_NAME); 393918334Speter } 394018334Speter 394118334Speter /* And finally, remove the copy, it is not needed. */ 394218334Speter bsi_remove (&si, true); 394318334Speter } 394418334Speter else 394518334Speter bsi_next (&si); 394618334Speter } 394718334Speter 394818334Speter sbitmap_free (blocks_visited); 394918334Speter} 395018334Speter 395118334Speter 395218334Speter/* Return true if STMT is interesting for VRP. */ 395318334Speter 395418334Speterstatic bool 395518334Speterstmt_interesting_for_vrp (tree stmt) 395618334Speter{ 395718334Speter if (TREE_CODE (stmt) == PHI_NODE 395818334Speter && is_gimple_reg (PHI_RESULT (stmt)) 395918334Speter && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))) 396018334Speter || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))))) 396118334Speter return true; 396218334Speter else if (TREE_CODE (stmt) == MODIFY_EXPR) 396318334Speter { 396418334Speter tree lhs = TREE_OPERAND (stmt, 0); 396518334Speter tree rhs = TREE_OPERAND (stmt, 1); 396618334Speter 396718334Speter /* In general, assignments with virtual operands are not useful 396818334Speter for deriving ranges, with the obvious exception of calls to 396918334Speter builtin functions. */ 397018334Speter if (TREE_CODE (lhs) == SSA_NAME 397118334Speter && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 397218334Speter || POINTER_TYPE_P (TREE_TYPE (lhs))) 397318334Speter && ((TREE_CODE (rhs) == CALL_EXPR 397418334Speter && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 397518334Speter && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 397618334Speter && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 397718334Speter || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) 397818334Speter return true; 397918334Speter } 398018334Speter else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 398118334Speter return true; 398218334Speter 398318334Speter return false; 398418334Speter} 398518334Speter 398618334Speter 398718334Speter/* Initialize local data structures for VRP. */ 398818334Speter 398918334Speterstatic void 399018334Spetervrp_initialize (void) 399118334Speter{ 399218334Speter basic_block bb; 399318334Speter 399418334Speter vr_value = XNEWVEC (value_range_t *, num_ssa_names); 399518334Speter memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *)); 399618334Speter 399718334Speter FOR_EACH_BB (bb) 399818334Speter { 399918334Speter block_stmt_iterator si; 400018334Speter tree phi; 400118334Speter 400218334Speter for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 400318334Speter { 400418334Speter if (!stmt_interesting_for_vrp (phi)) 400518334Speter { 400618334Speter tree lhs = PHI_RESULT (phi); 400718334Speter set_value_range_to_varying (get_value_range (lhs)); 400818334Speter DONT_SIMULATE_AGAIN (phi) = true; 400918334Speter } 401018334Speter else 401118334Speter DONT_SIMULATE_AGAIN (phi) = false; 401218334Speter } 401318334Speter 401418334Speter for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 401518334Speter { 401618334Speter tree stmt = bsi_stmt (si); 401718334Speter 401818334Speter if (!stmt_interesting_for_vrp (stmt)) 401918334Speter { 402018334Speter ssa_op_iter i; 402118334Speter tree def; 402218334Speter FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 402318334Speter set_value_range_to_varying (get_value_range (def)); 402418334Speter DONT_SIMULATE_AGAIN (stmt) = true; 402518334Speter } 402618334Speter else 402718334Speter { 402818334Speter DONT_SIMULATE_AGAIN (stmt) = false; 402918334Speter } 403018334Speter } 403118334Speter } 403218334Speter} 403318334Speter 403418334Speter 403518334Speter/* Visit assignment STMT. If it produces an interesting range, record 403618334Speter the SSA name in *OUTPUT_P. */ 403718334Speter 403818334Speterstatic enum ssa_prop_result 403918334Spetervrp_visit_assignment (tree stmt, tree *output_p) 404018334Speter{ 404118334Speter tree lhs, rhs, def; 404218334Speter ssa_op_iter iter; 404318334Speter 404418334Speter lhs = TREE_OPERAND (stmt, 0); 404518334Speter rhs = TREE_OPERAND (stmt, 1); 404618334Speter 404718334Speter /* We only keep track of ranges in integral and pointer types. */ 404818334Speter if (TREE_CODE (lhs) == SSA_NAME 404918334Speter && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 405018334Speter /* It is valid to have NULL MIN/MAX values on a type. See 405118334Speter build_range_type. */ 405218334Speter && TYPE_MIN_VALUE (TREE_TYPE (lhs)) 405318334Speter && TYPE_MAX_VALUE (TREE_TYPE (lhs))) 405418334Speter || POINTER_TYPE_P (TREE_TYPE (lhs)))) 405518334Speter { 405618334Speter struct loop *l; 405718334Speter value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 405818334Speter 405918334Speter extract_range_from_expr (&new_vr, rhs); 406018334Speter 406118334Speter /* If STMT is inside a loop, we may be able to know something 406218334Speter else about the range of LHS by examining scalar evolution 406318334Speter information. */ 406418334Speter if (current_loops && (l = loop_containing_stmt (stmt))) 406518334Speter adjust_range_with_scev (&new_vr, l, stmt, lhs); 406618334Speter 406718334Speter if (update_value_range (lhs, &new_vr)) 406818334Speter { 406918334Speter *output_p = lhs; 407018334Speter 407118334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 407218334Speter { 407318334Speter fprintf (dump_file, "Found new range for "); 407418334Speter print_generic_expr (dump_file, lhs, 0); 407518334Speter fprintf (dump_file, ": "); 407618334Speter dump_value_range (dump_file, &new_vr); 407718334Speter fprintf (dump_file, "\n\n"); 407818334Speter } 407918334Speter 408018334Speter if (new_vr.type == VR_VARYING) 408118334Speter return SSA_PROP_VARYING; 408218334Speter 408318334Speter return SSA_PROP_INTERESTING; 408418334Speter } 408518334Speter 408618334Speter return SSA_PROP_NOT_INTERESTING; 408718334Speter } 408818334Speter 408918334Speter /* Every other statement produces no useful ranges. */ 409018334Speter FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 409118334Speter set_value_range_to_varying (get_value_range (def)); 409218334Speter 409318334Speter return SSA_PROP_VARYING; 409418334Speter} 409518334Speter 409618334Speter 409718334Speter/* Compare all the value ranges for names equivalent to VAR with VAL 409818334Speter using comparison code COMP. Return the same value returned by 409918334Speter compare_range_with_value, including the setting of 410018334Speter *STRICT_OVERFLOW_P. */ 410118334Speter 410218334Speterstatic tree 410318334Spetercompare_name_with_value (enum tree_code comp, tree var, tree val, 410418334Speter bool *strict_overflow_p) 410518334Speter{ 410618334Speter bitmap_iterator bi; 410718334Speter unsigned i; 410818334Speter bitmap e; 410918334Speter tree retval, t; 411018334Speter int used_strict_overflow; 411118334Speter 411218334Speter t = retval = NULL_TREE; 411318334Speter 411418334Speter /* Get the set of equivalences for VAR. */ 411518334Speter e = get_value_range (var)->equiv; 411618334Speter 411718334Speter /* Add VAR to its own set of equivalences so that VAR's value range 411818334Speter is processed by this loop (otherwise, we would have to replicate 411918334Speter the body of the loop just to check VAR's value range). */ 412018334Speter bitmap_set_bit (e, SSA_NAME_VERSION (var)); 412118334Speter 412218334Speter /* Start at -1. Set it to 0 if we do a comparison without relying 412318334Speter on overflow, or 1 if all comparisons rely on overflow. */ 412418334Speter used_strict_overflow = -1; 412518334Speter 412618334Speter EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 412718334Speter { 412818334Speter bool sop; 412918334Speter 413018334Speter value_range_t equiv_vr = *(vr_value[i]); 413118334Speter 413218334Speter /* If name N_i does not have a valid range, use N_i as its own 413318334Speter range. This allows us to compare against names that may 413418334Speter have N_i in their ranges. */ 413518334Speter if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) 413618334Speter { 413718334Speter equiv_vr.type = VR_RANGE; 413818334Speter equiv_vr.min = ssa_name (i); 413918334Speter equiv_vr.max = ssa_name (i); 414018334Speter } 414118334Speter 414218334Speter sop = false; 414318334Speter t = compare_range_with_value (comp, &equiv_vr, val, &sop); 414418334Speter if (t) 414518334Speter { 414618334Speter /* If we get different answers from different members 414718334Speter of the equivalence set this check must be in a dead 414818334Speter code region. Folding it to a trap representation 414918334Speter would be correct here. For now just return don't-know. */ 415018334Speter if (retval != NULL 415118334Speter && t != retval) 415218334Speter { 415318334Speter retval = NULL_TREE; 415418334Speter break; 415518334Speter } 415618334Speter retval = t; 415718334Speter 415818334Speter if (!sop) 415918334Speter used_strict_overflow = 0; 416018334Speter else if (used_strict_overflow < 0) 416118334Speter used_strict_overflow = 1; 416218334Speter } 416318334Speter } 416418334Speter 416518334Speter /* Remove VAR from its own equivalence set. */ 416618334Speter bitmap_clear_bit (e, SSA_NAME_VERSION (var)); 416718334Speter 416818334Speter if (retval) 416918334Speter { 417018334Speter if (used_strict_overflow > 0) 417118334Speter *strict_overflow_p = true; 417218334Speter return retval; 417318334Speter } 417418334Speter 417518334Speter /* We couldn't find a non-NULL value for the predicate. */ 417618334Speter return NULL_TREE; 417718334Speter} 417818334Speter 417918334Speter 418018334Speter/* Given a comparison code COMP and names N1 and N2, compare all the 418118334Speter ranges equivalent to N1 against all the ranges equivalent to N2 418218334Speter to determine the value of N1 COMP N2. Return the same value 418318334Speter returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate 418418334Speter whether we relied on an overflow infinity in the comparison. */ 418518334Speter 418618334Speter 418718334Speterstatic tree 418818334Spetercompare_names (enum tree_code comp, tree n1, tree n2, 418918334Speter bool *strict_overflow_p) 419018334Speter{ 419118334Speter tree t, retval; 419218334Speter bitmap e1, e2; 419318334Speter bitmap_iterator bi1, bi2; 419418334Speter unsigned i1, i2; 419518334Speter int used_strict_overflow; 419618334Speter 419718334Speter /* Compare the ranges of every name equivalent to N1 against the 419818334Speter ranges of every name equivalent to N2. */ 419918334Speter e1 = get_value_range (n1)->equiv; 420018334Speter e2 = get_value_range (n2)->equiv; 420118334Speter 420218334Speter /* Add N1 and N2 to their own set of equivalences to avoid 420318334Speter duplicating the body of the loop just to check N1 and N2 420418334Speter ranges. */ 420518334Speter bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 420618334Speter bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 420718334Speter 420818334Speter /* If the equivalence sets have a common intersection, then the two 420918334Speter names can be compared without checking their ranges. */ 421018334Speter if (bitmap_intersect_p (e1, e2)) 421118334Speter { 421218334Speter bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 421318334Speter bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 421418334Speter 421518334Speter return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 421618334Speter ? boolean_true_node 421718334Speter : boolean_false_node; 421818334Speter } 421918334Speter 422018334Speter /* Start at -1. Set it to 0 if we do a comparison without relying 422118334Speter on overflow, or 1 if all comparisons rely on overflow. */ 422218334Speter used_strict_overflow = -1; 422318334Speter 422418334Speter /* Otherwise, compare all the equivalent ranges. First, add N1 and 422518334Speter N2 to their own set of equivalences to avoid duplicating the body 422618334Speter of the loop just to check N1 and N2 ranges. */ 422718334Speter EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 422818334Speter { 422918334Speter value_range_t vr1 = *(vr_value[i1]); 423018334Speter 423118334Speter /* If the range is VARYING or UNDEFINED, use the name itself. */ 423218334Speter if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) 423318334Speter { 423418334Speter vr1.type = VR_RANGE; 423518334Speter vr1.min = ssa_name (i1); 423618334Speter vr1.max = ssa_name (i1); 423718334Speter } 423818334Speter 423918334Speter t = retval = NULL_TREE; 424018334Speter EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 424118334Speter { 424218334Speter bool sop = false; 424318334Speter 424418334Speter value_range_t vr2 = *(vr_value[i2]); 424518334Speter 424618334Speter if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) 424718334Speter { 424818334Speter vr2.type = VR_RANGE; 424918334Speter vr2.min = ssa_name (i2); 425018334Speter vr2.max = ssa_name (i2); 425118334Speter } 425218334Speter 425318334Speter t = compare_ranges (comp, &vr1, &vr2, &sop); 425418334Speter if (t) 425518334Speter { 425618334Speter /* If we get different answers from different members 425718334Speter of the equivalence set this check must be in a dead 425818334Speter code region. Folding it to a trap representation 425918334Speter would be correct here. For now just return don't-know. */ 426018334Speter if (retval != NULL 426118334Speter && t != retval) 426218334Speter { 426318334Speter bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 426418334Speter bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 426518334Speter return NULL_TREE; 426618334Speter } 426718334Speter retval = t; 426818334Speter 426918334Speter if (!sop) 427018334Speter used_strict_overflow = 0; 427118334Speter else if (used_strict_overflow < 0) 427218334Speter used_strict_overflow = 1; 427318334Speter } 427418334Speter } 427518334Speter 427618334Speter if (retval) 427718334Speter { 427818334Speter bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 427918334Speter bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 428018334Speter if (used_strict_overflow > 0) 428118334Speter *strict_overflow_p = true; 428218334Speter return retval; 428318334Speter } 428418334Speter } 428518334Speter 428618334Speter /* None of the equivalent ranges are useful in computing this 428718334Speter comparison. */ 428818334Speter bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 428918334Speter bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 429018334Speter return NULL_TREE; 429118334Speter} 429218334Speter 429318334Speter 429418334Speter/* Given a conditional predicate COND, try to determine if COND yields 429518334Speter true or false based on the value ranges of its operands. Return 429618334Speter BOOLEAN_TRUE_NODE if the conditional always evaluates to true, 429718334Speter BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, 429818334Speter NULL if the conditional cannot be evaluated at compile time. 429918334Speter 430018334Speter If USE_EQUIV_P is true, the ranges of all the names equivalent with 430118334Speter the operands in COND are used when trying to compute its value. 430218334Speter This is only used during final substitution. During propagation, 430318334Speter we only check the range of each variable and not its equivalents. 430418334Speter 430518334Speter Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow 430618334Speter infinity to produce the result. */ 430718334Speter 430818334Speterstatic tree 430918334Spetervrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p, 431018334Speter bool *strict_overflow_p) 431118334Speter{ 431218334Speter gcc_assert (TREE_CODE (cond) == SSA_NAME 431318334Speter || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); 431418334Speter 431518334Speter if (TREE_CODE (cond) == SSA_NAME) 431618334Speter { 431718334Speter value_range_t *vr; 431818334Speter tree retval; 431918334Speter 432018334Speter if (use_equiv_p) 432118334Speter retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node, 432218334Speter strict_overflow_p); 432318334Speter else 432418334Speter { 432518334Speter value_range_t *vr = get_value_range (cond); 432618334Speter retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node, 432718334Speter strict_overflow_p); 432818334Speter } 432918334Speter 433018334Speter /* If COND has a known boolean range, return it. */ 433118334Speter if (retval) 433218334Speter return retval; 433318334Speter 433418334Speter /* Otherwise, if COND has a symbolic range of exactly one value, 433518334Speter return it. */ 433618334Speter vr = get_value_range (cond); 433718334Speter if (vr->type == VR_RANGE && vr->min == vr->max) 433818334Speter return vr->min; 433918334Speter } 434018334Speter else 434118334Speter { 434218334Speter tree op0 = TREE_OPERAND (cond, 0); 434318334Speter tree op1 = TREE_OPERAND (cond, 1); 434418334Speter 434518334Speter /* We only deal with integral and pointer types. */ 434618334Speter if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 434718334Speter && !POINTER_TYPE_P (TREE_TYPE (op0))) 434818334Speter return NULL_TREE; 434918334Speter 435018334Speter if (use_equiv_p) 435118334Speter { 435218334Speter if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 435318334Speter return compare_names (TREE_CODE (cond), op0, op1, 435418334Speter strict_overflow_p); 435518334Speter else if (TREE_CODE (op0) == SSA_NAME) 435618334Speter return compare_name_with_value (TREE_CODE (cond), op0, op1, 435718334Speter strict_overflow_p); 435818334Speter else if (TREE_CODE (op1) == SSA_NAME) 435918334Speter return (compare_name_with_value 436018334Speter (swap_tree_comparison (TREE_CODE (cond)), op1, op0, 436118334Speter strict_overflow_p)); 436218334Speter } 436318334Speter else 436418334Speter { 436518334Speter value_range_t *vr0, *vr1; 436618334Speter 436718334Speter vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 436818334Speter vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 436918334Speter 437018334Speter if (vr0 && vr1) 437118334Speter return compare_ranges (TREE_CODE (cond), vr0, vr1, 437218334Speter strict_overflow_p); 437318334Speter else if (vr0 && vr1 == NULL) 437418334Speter return compare_range_with_value (TREE_CODE (cond), vr0, op1, 437518334Speter strict_overflow_p); 437618334Speter else if (vr0 == NULL && vr1) 437718334Speter return (compare_range_with_value 437818334Speter (swap_tree_comparison (TREE_CODE (cond)), vr1, op0, 437918334Speter strict_overflow_p)); 438018334Speter } 438118334Speter } 438218334Speter 438318334Speter /* Anything else cannot be computed statically. */ 438418334Speter return NULL_TREE; 438518334Speter} 438618334Speter 438718334Speter/* Given COND within STMT, try to simplify it based on value range 438818334Speter information. Return NULL if the conditional can not be evaluated. 438918334Speter The ranges of all the names equivalent with the operands in COND 439018334Speter will be used when trying to compute the value. If the result is 439118334Speter based on undefined signed overflow, issue a warning if 439218334Speter appropriate. */ 439318334Speter 439418334Spetertree 439518334Spetervrp_evaluate_conditional (tree cond, tree stmt) 439618334Speter{ 439718334Speter bool sop; 439818334Speter tree ret; 439918334Speter 440018334Speter sop = false; 440118334Speter ret = vrp_evaluate_conditional_warnv (cond, true, &sop); 440218334Speter 440318334Speter if (ret && sop) 440418334Speter { 440518334Speter enum warn_strict_overflow_code wc; 440618334Speter const char* warnmsg; 440718334Speter 440818334Speter if (is_gimple_min_invariant (ret)) 440918334Speter { 441018334Speter wc = WARN_STRICT_OVERFLOW_CONDITIONAL; 441118334Speter warnmsg = G_("assuming signed overflow does not occur when " 441218334Speter "simplifying conditional to constant"); 441318334Speter } 441418334Speter else 441518334Speter { 441618334Speter wc = WARN_STRICT_OVERFLOW_COMPARISON; 441718334Speter warnmsg = G_("assuming signed overflow does not occur when " 441818334Speter "simplifying conditional"); 441918334Speter } 442018334Speter 442118334Speter if (issue_strict_overflow_warning (wc)) 442218334Speter { 442318334Speter location_t locus; 442418334Speter 442518334Speter if (!EXPR_HAS_LOCATION (stmt)) 442618334Speter locus = input_location; 442718334Speter else 442818334Speter locus = EXPR_LOCATION (stmt); 442918334Speter warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg); 443018334Speter } 443118334Speter } 443218334Speter 443318334Speter return ret; 443418334Speter} 443518334Speter 443618334Speter 443718334Speter/* Visit conditional statement STMT. If we can determine which edge 443818334Speter will be taken out of STMT's basic block, record it in 443918334Speter *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return 444018334Speter SSA_PROP_VARYING. */ 444118334Speter 444218334Speterstatic enum ssa_prop_result 444318334Spetervrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) 444418334Speter{ 444518334Speter tree cond, val; 444618334Speter bool sop; 444718334Speter 444818334Speter *taken_edge_p = NULL; 444918334Speter 445018334Speter /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to 445118334Speter add ASSERT_EXPRs for them. */ 445218334Speter if (TREE_CODE (stmt) == SWITCH_EXPR) 445318334Speter return SSA_PROP_VARYING; 445418334Speter 445518334Speter cond = COND_EXPR_COND (stmt); 445618334Speter 445718334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 445818334Speter { 445918334Speter tree use; 446018334Speter ssa_op_iter i; 446118334Speter 446218334Speter fprintf (dump_file, "\nVisiting conditional with predicate: "); 446318334Speter print_generic_expr (dump_file, cond, 0); 446418334Speter fprintf (dump_file, "\nWith known ranges\n"); 446518334Speter 446618334Speter FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 446718334Speter { 446818334Speter fprintf (dump_file, "\t"); 446918334Speter print_generic_expr (dump_file, use, 0); 447018334Speter fprintf (dump_file, ": "); 447118334Speter dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 447218334Speter } 447318334Speter 447418334Speter fprintf (dump_file, "\n"); 447518334Speter } 447618334Speter 447718334Speter /* Compute the value of the predicate COND by checking the known 447818334Speter ranges of each of its operands. 447918334Speter 448018334Speter Note that we cannot evaluate all the equivalent ranges here 448118334Speter because those ranges may not yet be final and with the current 448218334Speter propagation strategy, we cannot determine when the value ranges 448318334Speter of the names in the equivalence set have changed. 448418334Speter 448518334Speter For instance, given the following code fragment 448618334Speter 448718334Speter i_5 = PHI <8, i_13> 448818334Speter ... 448918334Speter i_14 = ASSERT_EXPR <i_5, i_5 != 0> 449018334Speter if (i_14 == 1) 449118334Speter ... 449218334Speter 449318334Speter Assume that on the first visit to i_14, i_5 has the temporary 449418334Speter range [8, 8] because the second argument to the PHI function is 449518334Speter not yet executable. We derive the range ~[0, 0] for i_14 and the 449618334Speter equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 449718334Speter the first time, since i_14 is equivalent to the range [8, 8], we 449818334Speter determine that the predicate is always false. 449918334Speter 450018334Speter On the next round of propagation, i_13 is determined to be 450118334Speter VARYING, which causes i_5 to drop down to VARYING. So, another 450218334Speter visit to i_14 is scheduled. In this second visit, we compute the 450318334Speter exact same range and equivalence set for i_14, namely ~[0, 0] and 450418334Speter { i_5 }. But we did not have the previous range for i_5 450518334Speter registered, so vrp_visit_assignment thinks that the range for 450618334Speter i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 450718334Speter is not visited again, which stops propagation from visiting 450818334Speter statements in the THEN clause of that if(). 450918334Speter 451018334Speter To properly fix this we would need to keep the previous range 451118334Speter value for the names in the equivalence set. This way we would've 451218334Speter discovered that from one visit to the other i_5 changed from 451318334Speter range [8, 8] to VR_VARYING. 451418334Speter 451518334Speter However, fixing this apparent limitation may not be worth the 451618334Speter additional checking. Testing on several code bases (GCC, DLV, 451718334Speter MICO, TRAMP3D and SPEC2000) showed that doing this results in 451818334Speter 4 more predicates folded in SPEC. */ 451918334Speter sop = false; 452018334Speter val = vrp_evaluate_conditional_warnv (cond, false, &sop); 452118334Speter if (val) 452218334Speter { 452318334Speter if (!sop) 452418334Speter *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); 452518334Speter else 452618334Speter { 452718334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 452818334Speter fprintf (dump_file, 452918334Speter "\nIgnoring predicate evaluation because " 453018334Speter "it assumes that signed overflow is undefined"); 453118334Speter val = NULL_TREE; 453218334Speter } 453318334Speter } 453418334Speter 453518334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 453618334Speter { 453718334Speter fprintf (dump_file, "\nPredicate evaluates to: "); 453818334Speter if (val == NULL_TREE) 453918334Speter fprintf (dump_file, "DON'T KNOW\n"); 454018334Speter else 454118334Speter print_generic_stmt (dump_file, val, 0); 454218334Speter } 454318334Speter 454418334Speter return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 454518334Speter} 454618334Speter 454718334Speter 454818334Speter/* Evaluate statement STMT. If the statement produces a useful range, 454918334Speter return SSA_PROP_INTERESTING and record the SSA name with the 455018334Speter interesting range into *OUTPUT_P. 455118334Speter 455218334Speter If STMT is a conditional branch and we can determine its truth 455318334Speter value, the taken edge is recorded in *TAKEN_EDGE_P. 455418334Speter 455518334Speter If STMT produces a varying value, return SSA_PROP_VARYING. */ 455618334Speter 455718334Speterstatic enum ssa_prop_result 455818334Spetervrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 455918334Speter{ 456018334Speter tree def; 456118334Speter ssa_op_iter iter; 456218334Speter stmt_ann_t ann; 456318334Speter 456418334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 456518334Speter { 456618334Speter fprintf (dump_file, "\nVisiting statement:\n"); 456718334Speter print_generic_stmt (dump_file, stmt, dump_flags); 456818334Speter fprintf (dump_file, "\n"); 456918334Speter } 457018334Speter 457118334Speter ann = stmt_ann (stmt); 457218334Speter if (TREE_CODE (stmt) == MODIFY_EXPR) 457318334Speter { 457418334Speter tree rhs = TREE_OPERAND (stmt, 1); 457518334Speter 457618334Speter /* In general, assignments with virtual operands are not useful 457718334Speter for deriving ranges, with the obvious exception of calls to 457818334Speter builtin functions. */ 457918334Speter if ((TREE_CODE (rhs) == CALL_EXPR 458018334Speter && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 458118334Speter && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 458218334Speter && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 458318334Speter || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 458418334Speter return vrp_visit_assignment (stmt, output_p); 458518334Speter } 458618334Speter else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 458718334Speter return vrp_visit_cond_stmt (stmt, taken_edge_p); 458818334Speter 458918334Speter /* All other statements produce nothing of interest for VRP, so mark 459018334Speter their outputs varying and prevent further simulation. */ 459118334Speter FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 459218334Speter set_value_range_to_varying (get_value_range (def)); 459318334Speter 459418334Speter return SSA_PROP_VARYING; 459518334Speter} 459618334Speter 459718334Speter 459818334Speter/* Meet operation for value ranges. Given two value ranges VR0 and 459918334Speter VR1, store in VR0 the result of meeting VR0 and VR1. 460018334Speter 460118334Speter The meeting rules are as follows: 460218334Speter 460318334Speter 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. 460418334Speter 460518334Speter 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the 460618334Speter union of VR0 and VR1. */ 460718334Speter 460818334Speterstatic void 460918334Spetervrp_meet (value_range_t *vr0, value_range_t *vr1) 461018334Speter{ 461118334Speter if (vr0->type == VR_UNDEFINED) 461218334Speter { 461318334Speter copy_value_range (vr0, vr1); 461418334Speter return; 461518334Speter } 461618334Speter 461718334Speter if (vr1->type == VR_UNDEFINED) 461818334Speter { 461918334Speter /* Nothing to do. VR0 already has the resulting range. */ 462018334Speter return; 462118334Speter } 462218334Speter 462318334Speter if (vr0->type == VR_VARYING) 462418334Speter { 462518334Speter /* Nothing to do. VR0 already has the resulting range. */ 462618334Speter return; 462718334Speter } 462818334Speter 462918334Speter if (vr1->type == VR_VARYING) 463018334Speter { 463118334Speter set_value_range_to_varying (vr0); 463218334Speter return; 463318334Speter } 463418334Speter 463518334Speter if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) 463618334Speter { 463718334Speter /* If VR0 and VR1 have a non-empty intersection, compute the 463818334Speter union of both ranges. */ 463918334Speter if (value_ranges_intersect_p (vr0, vr1)) 464018334Speter { 464118334Speter int cmp; 464218334Speter tree min, max; 464318334Speter 464418334Speter /* The lower limit of the new range is the minimum of the 464518334Speter two ranges. If they cannot be compared, the result is 464618334Speter VARYING. */ 464718334Speter cmp = compare_values (vr0->min, vr1->min); 464818334Speter if (cmp == 0 || cmp == 1) 464918334Speter min = vr1->min; 465018334Speter else if (cmp == -1) 465118334Speter min = vr0->min; 465218334Speter else 465318334Speter { 465418334Speter set_value_range_to_varying (vr0); 465518334Speter return; 465618334Speter } 465718334Speter 465818334Speter /* Similarly, the upper limit of the new range is the 465918334Speter maximum of the two ranges. If they cannot be compared, 466018334Speter the result is VARYING. */ 466118334Speter cmp = compare_values (vr0->max, vr1->max); 466218334Speter if (cmp == 0 || cmp == -1) 466318334Speter max = vr1->max; 466418334Speter else if (cmp == 1) 466518334Speter max = vr0->max; 466618334Speter else 466718334Speter { 466818334Speter set_value_range_to_varying (vr0); 466918334Speter return; 467018334Speter } 467118334Speter 467218334Speter /* Check for useless ranges. */ 467318334Speter if (INTEGRAL_TYPE_P (TREE_TYPE (min)) 467418334Speter && ((vrp_val_is_min (min) || is_overflow_infinity (min)) 467518334Speter && (vrp_val_is_max (max) || is_overflow_infinity (max)))) 467618334Speter { 467718334Speter set_value_range_to_varying (vr0); 467818334Speter return; 467918334Speter } 468018334Speter 468118334Speter /* The resulting set of equivalences is the intersection of 468218334Speter the two sets. */ 468318334Speter if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 468418334Speter bitmap_and_into (vr0->equiv, vr1->equiv); 468518334Speter else if (vr0->equiv && !vr1->equiv) 468618334Speter bitmap_clear (vr0->equiv); 468718334Speter 468818334Speter set_value_range (vr0, vr0->type, min, max, vr0->equiv); 468918334Speter } 469018334Speter else 469118334Speter goto no_meet; 469218334Speter } 469318334Speter else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 469418334Speter { 469518334Speter /* Two anti-ranges meet only if they are both identical. */ 469618334Speter if (compare_values (vr0->min, vr1->min) == 0 469718334Speter && compare_values (vr0->max, vr1->max) == 0 469818334Speter && compare_values (vr0->min, vr0->max) == 0) 469918334Speter { 470018334Speter /* The resulting set of equivalences is the intersection of 470118334Speter the two sets. */ 470218334Speter if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 470318334Speter bitmap_and_into (vr0->equiv, vr1->equiv); 470418334Speter else if (vr0->equiv && !vr1->equiv) 470518334Speter bitmap_clear (vr0->equiv); 470618334Speter } 470718334Speter else 470818334Speter goto no_meet; 470918334Speter } 471018334Speter else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 471118334Speter { 471218334Speter /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] 471318334Speter meet only if the ranges have an empty intersection. The 471418334Speter result of the meet operation is the anti-range. */ 471518334Speter if (!symbolic_range_p (vr0) 471618334Speter && !symbolic_range_p (vr1) 471718334Speter && !value_ranges_intersect_p (vr0, vr1)) 471818334Speter { 471918334Speter /* Copy most of VR1 into VR0. Don't copy VR1's equivalence 472018334Speter set. We need to compute the intersection of the two 472118334Speter equivalence sets. */ 472218334Speter if (vr1->type == VR_ANTI_RANGE) 472318334Speter set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); 472418334Speter 472518334Speter /* The resulting set of equivalences is the intersection of 472618334Speter the two sets. */ 472718334Speter if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 472818334Speter bitmap_and_into (vr0->equiv, vr1->equiv); 472918334Speter else if (vr0->equiv && !vr1->equiv) 473018334Speter bitmap_clear (vr0->equiv); 473118334Speter } 473218334Speter else 473318334Speter goto no_meet; 473418334Speter } 473518334Speter else 473618334Speter gcc_unreachable (); 473718334Speter 473818334Speter return; 473918334Speter 474018334Speterno_meet: 474118334Speter /* The two range VR0 and VR1 do not meet. Before giving up and 474218334Speter setting the result to VARYING, see if we can at least derive a 474318334Speter useful anti-range. FIXME, all this nonsense about distinguishing 474418334Speter anti-ranges from ranges is necessary because of the odd 474518334Speter semantics of range_includes_zero_p and friends. */ 474618334Speter if (!symbolic_range_p (vr0) 474718334Speter && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0)) 474818334Speter || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0))) 474918334Speter && !symbolic_range_p (vr1) 475018334Speter && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1)) 475118334Speter || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1)))) 475218334Speter { 475318334Speter set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min)); 475418334Speter 475518334Speter /* Since this meet operation did not result from the meeting of 475618334Speter two equivalent names, VR0 cannot have any equivalences. */ 475718334Speter if (vr0->equiv) 475818334Speter bitmap_clear (vr0->equiv); 475918334Speter } 476018334Speter else 476118334Speter set_value_range_to_varying (vr0); 476218334Speter} 476318334Speter 476418334Speter 476518334Speter/* Visit all arguments for PHI node PHI that flow through executable 476618334Speter edges. If a valid value range can be derived from all the incoming 476718334Speter value ranges, set a new range for the LHS of PHI. */ 476818334Speter 476918334Speterstatic enum ssa_prop_result 477018334Spetervrp_visit_phi_node (tree phi) 477118334Speter{ 477218334Speter int i; 477318334Speter tree lhs = PHI_RESULT (phi); 477418334Speter value_range_t *lhs_vr = get_value_range (lhs); 477518334Speter value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 477618334Speter 477718334Speter copy_value_range (&vr_result, lhs_vr); 477818334Speter 477918334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 478018334Speter { 478118334Speter fprintf (dump_file, "\nVisiting PHI node: "); 478218334Speter print_generic_expr (dump_file, phi, dump_flags); 478318334Speter } 478418334Speter 478518334Speter for (i = 0; i < PHI_NUM_ARGS (phi); i++) 478618334Speter { 478718334Speter edge e = PHI_ARG_EDGE (phi, i); 478818334Speter 478918334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 479018334Speter { 479118334Speter fprintf (dump_file, 479218334Speter "\n Argument #%d (%d -> %d %sexecutable)\n", 479318334Speter i, e->src->index, e->dest->index, 479418334Speter (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 479518334Speter } 479618334Speter 479718334Speter if (e->flags & EDGE_EXECUTABLE) 479818334Speter { 479918334Speter tree arg = PHI_ARG_DEF (phi, i); 480018334Speter value_range_t vr_arg; 480118334Speter 480218334Speter if (TREE_CODE (arg) == SSA_NAME) 480318334Speter vr_arg = *(get_value_range (arg)); 480418334Speter else 480518334Speter { 480618334Speter if (is_overflow_infinity (arg)) 480718334Speter { 480818334Speter arg = copy_node (arg); 480918334Speter TREE_OVERFLOW (arg) = 0; 481018334Speter } 481118334Speter 481218334Speter vr_arg.type = VR_RANGE; 481318334Speter vr_arg.min = arg; 481418334Speter vr_arg.max = arg; 481518334Speter vr_arg.equiv = NULL; 481618334Speter } 481718334Speter 481818334Speter if (dump_file && (dump_flags & TDF_DETAILS)) 481918334Speter { 482018334Speter fprintf (dump_file, "\t"); 482118334Speter print_generic_expr (dump_file, arg, dump_flags); 482218334Speter fprintf (dump_file, "\n\tValue: "); 482318334Speter dump_value_range (dump_file, &vr_arg); 482418334Speter fprintf (dump_file, "\n"); 482518334Speter } 482618334Speter 482718334Speter vrp_meet (&vr_result, &vr_arg); 482818334Speter 482918334Speter if (vr_result.type == VR_VARYING) 483018334Speter break; 483118334Speter } 483218334Speter } 483318334Speter 483418334Speter if (vr_result.type == VR_VARYING) 483518334Speter goto varying; 483618334Speter 483718334Speter /* To prevent infinite iterations in the algorithm, derive ranges 483818334Speter when the new value is slightly bigger or smaller than the 483918334Speter previous one. */ 484018334Speter if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE) 484118334Speter { 484218334Speter if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 484318334Speter { 484418334Speter int cmp_min = compare_values (lhs_vr->min, vr_result.min); 484518334Speter int cmp_max = compare_values (lhs_vr->max, vr_result.max); 484618334Speter 484718334Speter /* If the new minimum is smaller or larger than the previous 484818334Speter one, go all the way to -INF. In the first case, to avoid 484918334Speter iterating millions of times to reach -INF, and in the 485018334Speter other case to avoid infinite bouncing between different 485118334Speter minimums. */ 485218334Speter if (cmp_min > 0 || cmp_min < 0) 485318334Speter { 485418334Speter /* If we will end up with a (-INF, +INF) range, set it 485518334Speter to VARYING. */ 485618334Speter if (vrp_val_is_max (vr_result.max)) 485718334Speter goto varying; 485818334Speter 485918334Speter if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) 486018334Speter || !vrp_var_may_overflow (lhs, phi)) 486118334Speter vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); 486218334Speter else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) 486318334Speter vr_result.min = 486418334Speter negative_overflow_infinity (TREE_TYPE (vr_result.min)); 486518334Speter else 486618334Speter goto varying; 486718334Speter } 486818334Speter 486918334Speter /* Similarly, if the new maximum is smaller or larger than 487018334Speter the previous one, go all the way to +INF. */ 487118334Speter if (cmp_max < 0 || cmp_max > 0) 487218334Speter { 487318334Speter /* If we will end up with a (-INF, +INF) range, set it 487418334Speter to VARYING. */ 487518334Speter if (vrp_val_is_min (vr_result.min)) 487618334Speter goto varying; 487718334Speter 487818334Speter if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) 487918334Speter || !vrp_var_may_overflow (lhs, phi)) 488018334Speter vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); 488118334Speter else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) 488218334Speter vr_result.max = 488318334Speter positive_overflow_infinity (TREE_TYPE (vr_result.max)); 488418334Speter else 488518334Speter goto varying; 488618334Speter } 488718334Speter } 488818334Speter } 488918334Speter 489018334Speter /* If the new range is different than the previous value, keep 489118334Speter iterating. */ 489218334Speter if (update_value_range (lhs, &vr_result)) 489318334Speter return SSA_PROP_INTERESTING; 489418334Speter 489518334Speter /* Nothing changed, don't add outgoing edges. */ 489618334Speter return SSA_PROP_NOT_INTERESTING; 489718334Speter 489818334Speter /* No match found. Set the LHS to VARYING. */ 489918334Spetervarying: 490018334Speter set_value_range_to_varying (lhs_vr); 490118334Speter return SSA_PROP_VARYING; 490218334Speter} 490318334Speter 490418334Speter/* Simplify a division or modulo operator to a right shift or 490518334Speter bitwise and if the first operand is unsigned or is greater 490618334Speter than zero and the second operand is an exact power of two. */ 490718334Speter 490818334Speterstatic void 490918334Spetersimplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) 491018334Speter{ 491118334Speter tree val = NULL; 491218334Speter tree op = TREE_OPERAND (rhs, 0); 491318334Speter value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 491418334Speter 491518334Speter if (TYPE_UNSIGNED (TREE_TYPE (op))) 491618334Speter { 491718334Speter val = integer_one_node; 491818334Speter } 491918334Speter else 492018334Speter { 492118334Speter bool sop = false; 492218334Speter 492318334Speter val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); 492418334Speter 492518334Speter if (val 492618334Speter && sop 492718334Speter && integer_onep (val) 492818334Speter && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 492918334Speter { 493018334Speter location_t locus; 493118334Speter 493218334Speter if (!EXPR_HAS_LOCATION (stmt)) 493318334Speter locus = input_location; 493418334Speter else 493518334Speter locus = EXPR_LOCATION (stmt); 493618334Speter warning (OPT_Wstrict_overflow, 493718334Speter ("%Hassuming signed overflow does not occur when " 493818334Speter "simplifying / or %% to >> or &"), 493918334Speter &locus); 494018334Speter } 494118334Speter } 494218334Speter 494318334Speter if (val && integer_onep (val)) 494418334Speter { 494518334Speter tree t; 494618334Speter tree op0 = TREE_OPERAND (rhs, 0); 494718334Speter tree op1 = TREE_OPERAND (rhs, 1); 494818334Speter 494918334Speter if (rhs_code == TRUNC_DIV_EXPR) 495018334Speter { 495118334Speter t = build_int_cst (NULL_TREE, tree_log2 (op1)); 495218334Speter t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t); 495318334Speter } 495418334Speter else 495518334Speter { 495618334Speter t = build_int_cst (TREE_TYPE (op1), 1); 495718334Speter t = int_const_binop (MINUS_EXPR, op1, t, 0); 495818334Speter t = fold_convert (TREE_TYPE (op0), t); 495918334Speter t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t); 496018334Speter } 496118334Speter 496218334Speter TREE_OPERAND (stmt, 1) = t; 496318334Speter update_stmt (stmt); 496418334Speter } 496518334Speter} 496618334Speter 496718334Speter/* If the operand to an ABS_EXPR is >= 0, then eliminate the 496818334Speter ABS_EXPR. If the operand is <= 0, then simplify the 496918334Speter ABS_EXPR into a NEGATE_EXPR. */ 497018334Speter 497118334Speterstatic void 497218334Spetersimplify_abs_using_ranges (tree stmt, tree rhs) 497318334Speter{ 497418334Speter tree val = NULL; 497518334Speter tree op = TREE_OPERAND (rhs, 0); 497618334Speter tree type = TREE_TYPE (op); 497718334Speter value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 497818334Speter 497918334Speter if (TYPE_UNSIGNED (type)) 498018334Speter { 498118334Speter val = integer_zero_node; 498218334Speter } 498318334Speter else if (vr) 498418334Speter { 498518334Speter bool sop = false; 498618334Speter 498718334Speter val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); 498818334Speter if (!val) 498918334Speter { 499018334Speter sop = false; 499118334Speter val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, 499218334Speter &sop); 499318334Speter 499418334Speter if (val) 499518334Speter { 499618334Speter if (integer_zerop (val)) 499718334Speter val = integer_one_node; 499818334Speter else if (integer_onep (val)) 499918334Speter val = integer_zero_node; 500018334Speter } 500118334Speter } 500218334Speter 500318334Speter if (val 500418334Speter && (integer_onep (val) || integer_zerop (val))) 500518334Speter { 500618334Speter tree t; 500718334Speter 500818334Speter if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 500918334Speter { 501018334Speter location_t locus; 501118334Speter 501218334Speter if (!EXPR_HAS_LOCATION (stmt)) 501318334Speter locus = input_location; 501418334Speter else 501518334Speter locus = EXPR_LOCATION (stmt); 501618334Speter warning (OPT_Wstrict_overflow, 501718334Speter ("%Hassuming signed overflow does not occur when " 501818334Speter "simplifying abs (X) to X or -X"), 501918334Speter &locus); 502018334Speter } 502118334Speter 502218334Speter if (integer_onep (val)) 502318334Speter t = build1 (NEGATE_EXPR, TREE_TYPE (op), op); 502418334Speter else 502518334Speter t = op; 502618334Speter 502718334Speter TREE_OPERAND (stmt, 1) = t; 502818334Speter update_stmt (stmt); 502918334Speter } 503018334Speter } 503118334Speter} 503218334Speter 503318334Speter/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 503418334Speter a known value range VR. 503518334Speter 503618334Speter If there is one and only one value which will satisfy the 503718334Speter conditional, then return that value. Else return NULL. */ 503818334Speter 503918334Speterstatic tree 504018334Spetertest_for_singularity (enum tree_code cond_code, tree op0, 504118334Speter tree op1, value_range_t *vr) 504218334Speter{ 504318334Speter tree min = NULL; 504418334Speter tree max = NULL; 504518334Speter 504618334Speter /* Extract minimum/maximum values which satisfy the 504718334Speter the conditional as it was written. */ 504818334Speter if (cond_code == LE_EXPR || cond_code == LT_EXPR) 504918334Speter { 505018334Speter /* This should not be negative infinity; there is no overflow 505118334Speter here. */ 505218334Speter min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 505318334Speter 505418334Speter max = op1; 505518334Speter if (cond_code == LT_EXPR && !is_overflow_infinity (max)) 505618334Speter { 505718334Speter tree one = build_int_cst (TREE_TYPE (op0), 1); 505818334Speter max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 505918334Speter if (EXPR_P (max)) 506018334Speter TREE_NO_WARNING (max) = 1; 506118334Speter } 506218334Speter } 506318334Speter else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 506418334Speter { 506518334Speter /* This should not be positive infinity; there is no overflow 506618334Speter here. */ 506718334Speter max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 506818334Speter 506918334Speter min = op1; 507018334Speter if (cond_code == GT_EXPR && !is_overflow_infinity (min)) 507118334Speter { 507218334Speter tree one = build_int_cst (TREE_TYPE (op0), 1); 507318334Speter min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); 507418334Speter if (EXPR_P (min)) 507518334Speter TREE_NO_WARNING (min) = 1; 507618334Speter } 507718334Speter } 507818334Speter 507918334Speter /* Now refine the minimum and maximum values using any 508018334Speter value range information we have for op0. */ 508118334Speter if (min && max) 508218334Speter { 508318334Speter if (compare_values (vr->min, min) == -1) 508418334Speter min = min; 508518334Speter else 508618334Speter min = vr->min; 508718334Speter if (compare_values (vr->max, max) == 1) 508818334Speter max = max; 508918334Speter else 509018334Speter max = vr->max; 509118334Speter 509218334Speter /* If the new min/max values have converged to a single value, 509318334Speter then there is only one value which can satisfy the condition, 509418334Speter return that value. */ 509518334Speter if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) 509618334Speter return min; 509718334Speter } 509818334Speter return NULL; 509918334Speter} 510018334Speter 510118334Speter/* Simplify a conditional using a relational operator to an equality 510218334Speter test if the range information indicates only one value can satisfy 510318334Speter the original conditional. */ 510418334Speter 510518334Speterstatic void 510618334Spetersimplify_cond_using_ranges (tree stmt) 510718334Speter{ 510818334Speter tree cond = COND_EXPR_COND (stmt); 510918334Speter tree op0 = TREE_OPERAND (cond, 0); 511018334Speter tree op1 = TREE_OPERAND (cond, 1); 511118334Speter enum tree_code cond_code = TREE_CODE (cond); 511218334Speter 511318334Speter if (cond_code != NE_EXPR 511418334Speter && cond_code != EQ_EXPR 511518334Speter && TREE_CODE (op0) == SSA_NAME 511618334Speter && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 511718334Speter && is_gimple_min_invariant (op1)) 511818334Speter { 511918334Speter value_range_t *vr = get_value_range (op0); 512018334Speter 512118334Speter /* If we have range information for OP0, then we might be 512218334Speter able to simplify this conditional. */ 512318334Speter if (vr->type == VR_RANGE) 512418334Speter { 512518334Speter tree new = test_for_singularity (cond_code, op0, op1, vr); 512618334Speter 512718334Speter if (new) 512818334Speter { 512918334Speter if (dump_file) 513018334Speter { 513118334Speter fprintf (dump_file, "Simplified relational "); 513218334Speter print_generic_expr (dump_file, cond, 0); 513318334Speter fprintf (dump_file, " into "); 513418334Speter } 513518334Speter 513618334Speter COND_EXPR_COND (stmt) 513718334Speter = build2 (EQ_EXPR, boolean_type_node, op0, new); 513818334Speter update_stmt (stmt); 513918334Speter 514018334Speter if (dump_file) 514118334Speter { 514218334Speter print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 514318334Speter fprintf (dump_file, "\n"); 514418334Speter } 514518334Speter return; 514618334Speter 514718334Speter } 514818334Speter 514918334Speter /* Try again after inverting the condition. We only deal 515018334Speter with integral types here, so no need to worry about 515118334Speter issues with inverting FP comparisons. */ 515218334Speter cond_code = invert_tree_comparison (cond_code, false); 515318334Speter new = test_for_singularity (cond_code, op0, op1, vr); 515418334Speter 515518334Speter if (new) 515618334Speter { 515718334Speter if (dump_file) 515818334Speter { 515918334Speter fprintf (dump_file, "Simplified relational "); 516018334Speter print_generic_expr (dump_file, cond, 0); 516118334Speter fprintf (dump_file, " into "); 516218334Speter } 516318334Speter 516418334Speter COND_EXPR_COND (stmt) 516518334Speter = build2 (NE_EXPR, boolean_type_node, op0, new); 516618334Speter update_stmt (stmt); 516718334Speter 516818334Speter if (dump_file) 516918334Speter { 517018334Speter print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 517118334Speter fprintf (dump_file, "\n"); 517218334Speter } 517318334Speter return; 517418334Speter 517518334Speter } 517618334Speter } 517718334Speter } 517818334Speter} 517918334Speter 518018334Speter/* Simplify STMT using ranges if possible. */ 518118334Speter 518218334Spetervoid 518318334Spetersimplify_stmt_using_ranges (tree stmt) 518418334Speter{ 518518334Speter if (TREE_CODE (stmt) == MODIFY_EXPR) 518618334Speter { 518718334Speter tree rhs = TREE_OPERAND (stmt, 1); 518818334Speter enum tree_code rhs_code = TREE_CODE (rhs); 518918334Speter 519018334Speter /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 519118334Speter and BIT_AND_EXPR respectively if the first operand is greater 519218334Speter than zero and the second operand is an exact power of two. */ 519318334Speter if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) 519418334Speter && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) 519518334Speter && integer_pow2p (TREE_OPERAND (rhs, 1))) 519618334Speter simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); 519718334Speter 519818334Speter /* Transform ABS (X) into X or -X as appropriate. */ 519918334Speter if (rhs_code == ABS_EXPR 520018334Speter && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 520118334Speter && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) 520218334Speter simplify_abs_using_ranges (stmt, rhs); 520318334Speter } 520418334Speter else if (TREE_CODE (stmt) == COND_EXPR 520518334Speter && COMPARISON_CLASS_P (COND_EXPR_COND (stmt))) 520618334Speter { 520718334Speter simplify_cond_using_ranges (stmt); 520818334Speter } 520918334Speter} 521018334Speter 521118334Speter/* Stack of dest,src equivalency pairs that need to be restored after 521218334Speter each attempt to thread a block's incoming edge to an outgoing edge. 521318334Speter 521418334Speter A NULL entry is used to mark the end of pairs which need to be 521518334Speter restored. */ 521618334Speterstatic VEC(tree,heap) *stack; 521718334Speter 521818334Speter/* A trivial wrapper so that we can present the generic jump threading 521918334Speter code with a simple API for simplifying statements. STMT is the 522018334Speter statement we want to simplify, WITHIN_STMT provides the location 522118334Speter for any overflow warnings. */ 522218334Speter 522318334Speterstatic tree 522418334Spetersimplify_stmt_for_jump_threading (tree stmt, tree within_stmt) 522518334Speter{ 522618334Speter /* We only use VRP information to simplify conditionals. This is 522718334Speter overly conservative, but it's unclear if doing more would be 522818334Speter worth the compile time cost. */ 522918334Speter if (TREE_CODE (stmt) != COND_EXPR) 523018334Speter return NULL; 523118334Speter 523218334Speter return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt); 523318334Speter} 523418334Speter 523518334Speter/* Blocks which have more than one predecessor and more than 523618334Speter one successor present jump threading opportunities. ie, 523718334Speter when the block is reached from a specific predecessor, we 523818334Speter may be able to determine which of the outgoing edges will 523918334Speter be traversed. When this optimization applies, we are able 524018334Speter to avoid conditionals at runtime and we may expose secondary 524118334Speter optimization opportunities. 524218334Speter 524318334Speter This routine is effectively a driver for the generic jump 524418334Speter threading code. It basically just presents the generic code 524518334Speter with edges that may be suitable for jump threading. 524618334Speter 524718334Speter Unlike DOM, we do not iterate VRP if jump threading was successful. 524818334Speter While iterating may expose new opportunities for VRP, it is expected 524918334Speter those opportunities would be very limited and the compile time cost 525018334Speter to expose those opportunities would be significant. 525118334Speter 525218334Speter As jump threading opportunities are discovered, they are registered 525318334Speter for later realization. */ 525418334Speter 525518334Speterstatic void 525618334Speteridentify_jump_threads (void) 525718334Speter{ 525818334Speter basic_block bb; 525918334Speter tree dummy; 526018334Speter 526118334Speter /* Ugh. When substituting values earlier in this pass we can 526218334Speter wipe the dominance information. So rebuild the dominator 526318334Speter information as we need it within the jump threading code. */ 526418334Speter calculate_dominance_info (CDI_DOMINATORS); 526518334Speter 526618334Speter /* We do not allow VRP information to be used for jump threading 526718334Speter across a back edge in the CFG. Otherwise it becomes too 526818334Speter difficult to avoid eliminating loop exit tests. Of course 526918334Speter EDGE_DFS_BACK is not accurate at this time so we have to 527018334Speter recompute it. */ 527118334Speter mark_dfs_back_edges (); 527218334Speter 527318334Speter /* Allocate our unwinder stack to unwind any temporary equivalences 527418334Speter that might be recorded. */ 527518334Speter stack = VEC_alloc (tree, heap, 20); 527618334Speter 527718334Speter /* To avoid lots of silly node creation, we create a single 527818334Speter conditional and just modify it in-place when attempting to 527918334Speter thread jumps. */ 528018334Speter dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL); 528118334Speter dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL); 528218334Speter 528318334Speter /* Walk through all the blocks finding those which present a 528418334Speter potential jump threading opportunity. We could set this up 528518334Speter as a dominator walker and record data during the walk, but 528618334Speter I doubt it's worth the effort for the classes of jump 528718334Speter threading opportunities we are trying to identify at this 528818334Speter point in compilation. */ 528918334Speter FOR_EACH_BB (bb) 529018334Speter { 529118334Speter tree last, cond; 529218334Speter 529318334Speter /* If the generic jump threading code does not find this block 529418334Speter interesting, then there is nothing to do. */ 529518334Speter if (! potentially_threadable_block (bb)) 529618334Speter continue; 529718334Speter 529818334Speter /* We only care about blocks ending in a COND_EXPR. While there 529918334Speter may be some value in handling SWITCH_EXPR here, I doubt it's 530018334Speter terribly important. */ 530118334Speter last = bsi_stmt (bsi_last (bb)); 530218334Speter if (TREE_CODE (last) != COND_EXPR) 530318334Speter continue; 530418334Speter 530518334Speter /* We're basically looking for any kind of conditional with 530618334Speter integral type arguments. */ 530718334Speter cond = COND_EXPR_COND (last); 530818334Speter if ((TREE_CODE (cond) == SSA_NAME 530918334Speter && INTEGRAL_TYPE_P (TREE_TYPE (cond))) 531018334Speter || (COMPARISON_CLASS_P (cond) 531118334Speter && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 531218334Speter && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0))) 531318334Speter && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME 531418334Speter || is_gimple_min_invariant (TREE_OPERAND (cond, 1))) 531518334Speter && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 531618334Speter { 531718334Speter edge_iterator ei; 531818334Speter edge e; 531918334Speter 532018334Speter /* We've got a block with multiple predecessors and multiple 532118334Speter successors which also ends in a suitable conditional. For 532218334Speter each predecessor, see if we can thread it to a specific 532318334Speter successor. */ 532418334Speter FOR_EACH_EDGE (e, ei, bb->preds) 532518334Speter { 532618334Speter /* Do not thread across back edges or abnormal edges 532718334Speter in the CFG. */ 532818334Speter if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 532918334Speter continue; 533018334Speter 533118334Speter thread_across_edge (dummy, e, true, 533218334Speter &stack, 533318334Speter simplify_stmt_for_jump_threading); 533418334Speter } 533518334Speter } 533618334Speter } 533718334Speter 533818334Speter /* We do not actually update the CFG or SSA graphs at this point as 533918334Speter ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet 534018334Speter handle ASSERT_EXPRs gracefully. */ 534118334Speter} 534218334Speter 534318334Speter/* We identified all the jump threading opportunities earlier, but could 534418334Speter not transform the CFG at that time. This routine transforms the 534518334Speter CFG and arranges for the dominator tree to be rebuilt if necessary. 534618334Speter 534718334Speter Note the SSA graph update will occur during the normal TODO 534818334Speter processing by the pass manager. */ 534918334Speterstatic void 535018334Speterfinalize_jump_threads (void) 535118334Speter{ 535218334Speter bool cfg_altered = false; 535318334Speter cfg_altered = thread_through_all_blocks (); 535418334Speter 535518334Speter /* If we threaded jumps, then we need to recompute the dominance 535618334Speter information, to safely do that we must clean up the CFG first. */ 535718334Speter if (cfg_altered) 535818334Speter { 535918334Speter free_dominance_info (CDI_DOMINATORS); 536018334Speter cleanup_tree_cfg (); 536118334Speter calculate_dominance_info (CDI_DOMINATORS); 536218334Speter } 536318334Speter VEC_free (tree, heap, stack); 536418334Speter} 536518334Speter 536618334Speter 536718334Speter/* Traverse all the blocks folding conditionals with known ranges. */ 536818334Speter 536918334Speterstatic void 537018334Spetervrp_finalize (void) 537118334Speter{ 537218334Speter size_t i; 537318334Speter prop_value_t *single_val_range; 537418334Speter bool do_value_subst_p; 537518334Speter 537618334Speter if (dump_file) 537718334Speter { 537818334Speter fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 537918334Speter dump_all_value_ranges (dump_file); 538018334Speter fprintf (dump_file, "\n"); 538118334Speter } 538218334Speter 538318334Speter /* We may have ended with ranges that have exactly one value. Those 538418334Speter values can be substituted as any other copy/const propagated 538518334Speter value using substitute_and_fold. */ 538618334Speter single_val_range = XNEWVEC (prop_value_t, num_ssa_names); 538718334Speter memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range)); 538818334Speter 538918334Speter do_value_subst_p = false; 539018334Speter for (i = 0; i < num_ssa_names; i++) 539118334Speter if (vr_value[i] 539218334Speter && vr_value[i]->type == VR_RANGE 539318334Speter && vr_value[i]->min == vr_value[i]->max) 539418334Speter { 539518334Speter single_val_range[i].value = vr_value[i]->min; 539618334Speter do_value_subst_p = true; 539718334Speter } 539818334Speter 539918334Speter if (!do_value_subst_p) 540018334Speter { 540118334Speter /* We found no single-valued ranges, don't waste time trying to 540218334Speter do single value substitution in substitute_and_fold. */ 540318334Speter free (single_val_range); 540418334Speter single_val_range = NULL; 540518334Speter } 540618334Speter 540718334Speter substitute_and_fold (single_val_range, true); 540818334Speter 540918334Speter /* We must identify jump threading opportunities before we release 541018334Speter the datastructures built by VRP. */ 541118334Speter identify_jump_threads (); 541218334Speter 541318334Speter /* Free allocated memory. */ 541418334Speter for (i = 0; i < num_ssa_names; i++) 541518334Speter if (vr_value[i]) 541618334Speter { 541718334Speter BITMAP_FREE (vr_value[i]->equiv); 541818334Speter free (vr_value[i]); 541918334Speter } 542018334Speter 542118334Speter free (single_val_range); 542218334Speter free (vr_value); 542318334Speter 542418334Speter /* So that we can distinguish between VRP data being available 542518334Speter and not available. */ 542618334Speter vr_value = NULL; 542718334Speter} 542818334Speter 542918334Speter 543018334Speter/* Main entry point to VRP (Value Range Propagation). This pass is 543118334Speter loosely based on J. R. C. Patterson, ``Accurate Static Branch 543218334Speter Prediction by Value Range Propagation,'' in SIGPLAN Conference on 543318334Speter Programming Language Design and Implementation, pp. 67-78, 1995. 543418334Speter Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 543518334Speter 543618334Speter This is essentially an SSA-CCP pass modified to deal with ranges 543718334Speter instead of constants. 543818334Speter 543918334Speter While propagating ranges, we may find that two or more SSA name 544018334Speter have equivalent, though distinct ranges. For instance, 544118334Speter 544218334Speter 1 x_9 = p_3->a; 544318334Speter 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 544418334Speter 3 if (p_4 == q_2) 544518334Speter 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 544618334Speter 5 endif 544718334Speter 6 if (q_2) 544818334Speter 544918334Speter In the code above, pointer p_5 has range [q_2, q_2], but from the 545018334Speter code we can also determine that p_5 cannot be NULL and, if q_2 had 545118334Speter a non-varying range, p_5's range should also be compatible with it. 545218334Speter 545318334Speter These equivalences are created by two expressions: ASSERT_EXPR and 545418334Speter copy operations. Since p_5 is an assertion on p_4, and p_4 was the 545518334Speter result of another assertion, then we can use the fact that p_5 and 545618334Speter p_4 are equivalent when evaluating p_5's range. 545718334Speter 545818334Speter Together with value ranges, we also propagate these equivalences 545918334Speter between names so that we can take advantage of information from 546018334Speter multiple ranges when doing final replacement. Note that this 546118334Speter equivalency relation is transitive but not symmetric. 546218334Speter 546318334Speter In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 546418334Speter cannot assert that q_2 is equivalent to p_5 because q_2 may be used 546518334Speter in contexts where that assertion does not hold (e.g., in line 6). 546618334Speter 546718334Speter TODO, the main difference between this pass and Patterson's is that 546818334Speter we do not propagate edge probabilities. We only compute whether 546918334Speter edges can be taken or not. That is, instead of having a spectrum 547018334Speter of jump probabilities between 0 and 1, we only deal with 0, 1 and 547118334Speter DON'T KNOW. In the future, it may be worthwhile to propagate 547218334Speter probabilities to aid branch prediction. */ 547318334Speter 547418334Speterstatic unsigned int 547518334Speterexecute_vrp (void) 547618334Speter{ 547718334Speter insert_range_assertions (); 547818334Speter 547918334Speter current_loops = loop_optimizer_init (LOOPS_NORMAL); 548018334Speter if (current_loops) 548118334Speter scev_initialize (current_loops); 548218334Speter 548318334Speter vrp_initialize (); 548418334Speter ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); 548518334Speter vrp_finalize (); 548618334Speter 548718334Speter if (current_loops) 548818334Speter { 548918334Speter scev_finalize (); 549018334Speter loop_optimizer_finalize (current_loops); 549118334Speter current_loops = NULL; 549218334Speter } 549318334Speter 549418334Speter /* ASSERT_EXPRs must be removed before finalizing jump threads 549518334Speter as finalizing jump threads calls the CFG cleanup code which 549618334Speter does not properly handle ASSERT_EXPRs. */ 549718334Speter remove_range_assertions (); 549818334Speter 549918334Speter /* If we exposed any new variables, go ahead and put them into 550018334Speter SSA form now, before we handle jump threading. This simplifies 550118334Speter interactions between rewriting of _DECL nodes into SSA form 550218334Speter and rewriting SSA_NAME nodes into SSA form after block 550318334Speter duplication and CFG manipulation. */ 550418334Speter update_ssa (TODO_update_ssa); 550518334Speter 550618334Speter finalize_jump_threads (); 550718334Speter return 0; 550818334Speter} 550918334Speter 551018334Speterstatic bool 551118334Spetergate_vrp (void) 551218334Speter{ 551318334Speter return flag_tree_vrp != 0; 551418334Speter} 551518334Speter 551618334Speterstruct tree_opt_pass pass_vrp = 551718334Speter{ 551818334Speter "vrp", /* name */ 551918334Speter gate_vrp, /* gate */ 552018334Speter execute_vrp, /* execute */ 552118334Speter NULL, /* sub */ 552218334Speter NULL, /* next */ 552318334Speter 0, /* static_pass_number */ 552418334Speter TV_TREE_VRP, /* tv_id */ 552518334Speter PROP_ssa | PROP_alias, /* properties_required */ 552618334Speter 0, /* properties_provided */ 552718334Speter PROP_smt_usage, /* properties_destroyed */ 552818334Speter 0, /* todo_flags_start */ 552918334Speter TODO_cleanup_cfg 553018334Speter | TODO_ggc_collect 553118334Speter | TODO_verify_ssa 553218334Speter | TODO_dump_func 553318334Speter | TODO_update_ssa 553418334Speter | TODO_update_smt_usage, /* todo_flags_finish */ 553518334Speter 0 /* letter */ 553618334Speter}; 553718334Speter