1169689Skan/* Support routines for Value Range Propagation (VRP). 2169689Skan Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com>. 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "ggc.h" 27169689Skan#include "flags.h" 28169689Skan#include "tree.h" 29169689Skan#include "basic-block.h" 30169689Skan#include "tree-flow.h" 31169689Skan#include "tree-pass.h" 32169689Skan#include "tree-dump.h" 33169689Skan#include "timevar.h" 34169689Skan#include "diagnostic.h" 35169689Skan#include "toplev.h" 36169689Skan#include "intl.h" 37169689Skan#include "cfgloop.h" 38169689Skan#include "tree-scalar-evolution.h" 39169689Skan#include "tree-ssa-propagate.h" 40169689Skan#include "tree-chrec.h" 41169689Skan 42169689Skan/* Set of SSA names found during the dominator traversal of a 43169689Skan sub-graph in find_assert_locations. */ 44169689Skanstatic sbitmap found_in_subgraph; 45169689Skan 46169689Skan/* Local functions. */ 47169689Skanstatic int compare_values (tree val1, tree val2); 48169689Skanstatic int compare_values_warnv (tree val1, tree val2, bool *); 49169689Skanstatic tree vrp_evaluate_conditional_warnv (tree, bool, bool *); 50169689Skan 51169689Skan/* Location information for ASSERT_EXPRs. Each instance of this 52169689Skan structure describes an ASSERT_EXPR for an SSA name. Since a single 53169689Skan SSA name may have more than one assertion associated with it, these 54169689Skan locations are kept in a linked list attached to the corresponding 55169689Skan SSA name. */ 56169689Skanstruct assert_locus_d 57169689Skan{ 58169689Skan /* Basic block where the assertion would be inserted. */ 59169689Skan basic_block bb; 60169689Skan 61169689Skan /* Some assertions need to be inserted on an edge (e.g., assertions 62169689Skan generated by COND_EXPRs). In those cases, BB will be NULL. */ 63169689Skan edge e; 64169689Skan 65169689Skan /* Pointer to the statement that generated this assertion. */ 66169689Skan block_stmt_iterator si; 67169689Skan 68169689Skan /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */ 69169689Skan enum tree_code comp_code; 70169689Skan 71169689Skan /* Value being compared against. */ 72169689Skan tree val; 73169689Skan 74169689Skan /* Next node in the linked list. */ 75169689Skan struct assert_locus_d *next; 76169689Skan}; 77169689Skan 78169689Skantypedef struct assert_locus_d *assert_locus_t; 79169689Skan 80169689Skan/* If bit I is present, it means that SSA name N_i has a list of 81169689Skan assertions that should be inserted in the IL. */ 82169689Skanstatic bitmap need_assert_for; 83169689Skan 84169689Skan/* Array of locations lists where to insert assertions. ASSERTS_FOR[I] 85169689Skan holds a list of ASSERT_LOCUS_T nodes that describe where 86169689Skan ASSERT_EXPRs for SSA name N_I should be inserted. */ 87169689Skanstatic assert_locus_t *asserts_for; 88169689Skan 89169689Skan/* Set of blocks visited in find_assert_locations. Used to avoid 90169689Skan visiting the same block more than once. */ 91169689Skanstatic sbitmap blocks_visited; 92169689Skan 93169689Skan/* Value range array. After propagation, VR_VALUE[I] holds the range 94169689Skan of values that SSA name N_I may take. */ 95169689Skanstatic value_range_t **vr_value; 96169689Skan 97169689Skan 98169689Skan/* Return whether TYPE should use an overflow infinity distinct from 99169689Skan TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to 100169689Skan represent a signed overflow during VRP computations. An infinity 101169689Skan is distinct from a half-range, which will go from some number to 102169689Skan TYPE_{MIN,MAX}_VALUE. */ 103169689Skan 104169689Skanstatic inline bool 105169689Skanneeds_overflow_infinity (tree type) 106169689Skan{ 107169689Skan return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type); 108169689Skan} 109169689Skan 110169689Skan/* Return whether TYPE can support our overflow infinity 111169689Skan representation: we use the TREE_OVERFLOW flag, which only exists 112169689Skan for constants. If TYPE doesn't support this, we don't optimize 113169689Skan cases which would require signed overflow--we drop them to 114169689Skan VARYING. */ 115169689Skan 116169689Skanstatic inline bool 117169689Skansupports_overflow_infinity (tree type) 118169689Skan{ 119169689Skan#ifdef ENABLE_CHECKING 120169689Skan gcc_assert (needs_overflow_infinity (type)); 121169689Skan#endif 122169689Skan return (TYPE_MIN_VALUE (type) != NULL_TREE 123169689Skan && CONSTANT_CLASS_P (TYPE_MIN_VALUE (type)) 124169689Skan && TYPE_MAX_VALUE (type) != NULL_TREE 125169689Skan && CONSTANT_CLASS_P (TYPE_MAX_VALUE (type))); 126169689Skan} 127169689Skan 128169689Skan/* VAL is the maximum or minimum value of a type. Return a 129169689Skan corresponding overflow infinity. */ 130169689Skan 131169689Skanstatic inline tree 132169689Skanmake_overflow_infinity (tree val) 133169689Skan{ 134169689Skan#ifdef ENABLE_CHECKING 135169689Skan gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val)); 136169689Skan#endif 137169689Skan val = copy_node (val); 138169689Skan TREE_OVERFLOW (val) = 1; 139169689Skan return val; 140169689Skan} 141169689Skan 142169689Skan/* Return a negative overflow infinity for TYPE. */ 143169689Skan 144169689Skanstatic inline tree 145169689Skannegative_overflow_infinity (tree type) 146169689Skan{ 147169689Skan#ifdef ENABLE_CHECKING 148169689Skan gcc_assert (supports_overflow_infinity (type)); 149169689Skan#endif 150169689Skan return make_overflow_infinity (TYPE_MIN_VALUE (type)); 151169689Skan} 152169689Skan 153169689Skan/* Return a positive overflow infinity for TYPE. */ 154169689Skan 155169689Skanstatic inline tree 156169689Skanpositive_overflow_infinity (tree type) 157169689Skan{ 158169689Skan#ifdef ENABLE_CHECKING 159169689Skan gcc_assert (supports_overflow_infinity (type)); 160169689Skan#endif 161169689Skan return make_overflow_infinity (TYPE_MAX_VALUE (type)); 162169689Skan} 163169689Skan 164169689Skan/* Return whether VAL is a negative overflow infinity. */ 165169689Skan 166169689Skanstatic inline bool 167169689Skanis_negative_overflow_infinity (tree val) 168169689Skan{ 169169689Skan return (needs_overflow_infinity (TREE_TYPE (val)) 170169689Skan && CONSTANT_CLASS_P (val) 171169689Skan && TREE_OVERFLOW (val) 172169689Skan && operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 173169689Skan} 174169689Skan 175169689Skan/* Return whether VAL is a positive overflow infinity. */ 176169689Skan 177169689Skanstatic inline bool 178169689Skanis_positive_overflow_infinity (tree val) 179169689Skan{ 180169689Skan return (needs_overflow_infinity (TREE_TYPE (val)) 181169689Skan && CONSTANT_CLASS_P (val) 182169689Skan && TREE_OVERFLOW (val) 183169689Skan && operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)); 184169689Skan} 185169689Skan 186169689Skan/* Return whether VAL is a positive or negative overflow infinity. */ 187169689Skan 188169689Skanstatic inline bool 189169689Skanis_overflow_infinity (tree val) 190169689Skan{ 191169689Skan return (needs_overflow_infinity (TREE_TYPE (val)) 192169689Skan && CONSTANT_CLASS_P (val) 193169689Skan && TREE_OVERFLOW (val) 194169689Skan && (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0) 195169689Skan || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0))); 196169689Skan} 197169689Skan 198171825Skan/* If VAL is now an overflow infinity, return VAL. Otherwise, return 199171825Skan the same value with TREE_OVERFLOW clear. This can be used to avoid 200171825Skan confusing a regular value with an overflow value. */ 201169689Skan 202171825Skanstatic inline tree 203171825Skanavoid_overflow_infinity (tree val) 204171825Skan{ 205171825Skan if (!is_overflow_infinity (val)) 206171825Skan return val; 207171825Skan 208171825Skan if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)) 209171825Skan return TYPE_MAX_VALUE (TREE_TYPE (val)); 210171825Skan else 211171825Skan { 212171825Skan#ifdef ENABLE_CHECKING 213171825Skan gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)); 214171825Skan#endif 215171825Skan return TYPE_MIN_VALUE (TREE_TYPE (val)); 216171825Skan } 217171825Skan} 218171825Skan 219171825Skan 220169689Skan/* Return whether VAL is equal to the maximum value of its type. This 221169689Skan will be true for a positive overflow infinity. We can't do a 222169689Skan simple equality comparison with TYPE_MAX_VALUE because C typedefs 223169689Skan and Ada subtypes can produce types whose TYPE_MAX_VALUE is not == 224169689Skan to the integer constant with the same value in the type. */ 225169689Skan 226169689Skanstatic inline bool 227169689Skanvrp_val_is_max (tree val) 228169689Skan{ 229169689Skan tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val)); 230169689Skan 231169689Skan return (val == type_max 232169689Skan || (type_max != NULL_TREE 233169689Skan && operand_equal_p (val, type_max, 0))); 234169689Skan} 235169689Skan 236169689Skan/* Return whether VAL is equal to the minimum value of its type. This 237169689Skan will be true for a negative overflow infinity. */ 238169689Skan 239169689Skanstatic inline bool 240169689Skanvrp_val_is_min (tree val) 241169689Skan{ 242169689Skan tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val)); 243169689Skan 244169689Skan return (val == type_min 245169689Skan || (type_min != NULL_TREE 246169689Skan && operand_equal_p (val, type_min, 0))); 247169689Skan} 248169689Skan 249169689Skan 250169689Skan/* Return true if ARG is marked with the nonnull attribute in the 251169689Skan current function signature. */ 252169689Skan 253169689Skanstatic bool 254169689Skannonnull_arg_p (tree arg) 255169689Skan{ 256169689Skan tree t, attrs, fntype; 257169689Skan unsigned HOST_WIDE_INT arg_num; 258169689Skan 259169689Skan gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg))); 260169689Skan 261169689Skan /* The static chain decl is always non null. */ 262169689Skan if (arg == cfun->static_chain_decl) 263169689Skan return true; 264169689Skan 265169689Skan fntype = TREE_TYPE (current_function_decl); 266169689Skan attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype)); 267169689Skan 268169689Skan /* If "nonnull" wasn't specified, we know nothing about the argument. */ 269169689Skan if (attrs == NULL_TREE) 270169689Skan return false; 271169689Skan 272169689Skan /* If "nonnull" applies to all the arguments, then ARG is non-null. */ 273169689Skan if (TREE_VALUE (attrs) == NULL_TREE) 274169689Skan return true; 275169689Skan 276169689Skan /* Get the position number for ARG in the function signature. */ 277169689Skan for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl); 278169689Skan t; 279169689Skan t = TREE_CHAIN (t), arg_num++) 280169689Skan { 281169689Skan if (t == arg) 282169689Skan break; 283169689Skan } 284169689Skan 285169689Skan gcc_assert (t == arg); 286169689Skan 287169689Skan /* Now see if ARG_NUM is mentioned in the nonnull list. */ 288169689Skan for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t)) 289169689Skan { 290169689Skan if (compare_tree_int (TREE_VALUE (t), arg_num) == 0) 291169689Skan return true; 292169689Skan } 293169689Skan 294169689Skan return false; 295169689Skan} 296169689Skan 297169689Skan 298169689Skan/* Set value range VR to {T, MIN, MAX, EQUIV}. */ 299169689Skan 300169689Skanstatic void 301169689Skanset_value_range (value_range_t *vr, enum value_range_type t, tree min, 302169689Skan tree max, bitmap equiv) 303169689Skan{ 304169689Skan#if defined ENABLE_CHECKING 305169689Skan /* Check the validity of the range. */ 306169689Skan if (t == VR_RANGE || t == VR_ANTI_RANGE) 307169689Skan { 308169689Skan int cmp; 309169689Skan 310169689Skan gcc_assert (min && max); 311169689Skan 312169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE) 313169689Skan gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max)); 314169689Skan 315169689Skan cmp = compare_values (min, max); 316169689Skan gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); 317169689Skan 318169689Skan if (needs_overflow_infinity (TREE_TYPE (min))) 319169689Skan gcc_assert (!is_overflow_infinity (min) 320169689Skan || !is_overflow_infinity (max)); 321169689Skan } 322169689Skan 323169689Skan if (t == VR_UNDEFINED || t == VR_VARYING) 324169689Skan gcc_assert (min == NULL_TREE && max == NULL_TREE); 325169689Skan 326169689Skan if (t == VR_UNDEFINED || t == VR_VARYING) 327169689Skan gcc_assert (equiv == NULL || bitmap_empty_p (equiv)); 328169689Skan#endif 329169689Skan 330169689Skan vr->type = t; 331169689Skan vr->min = min; 332169689Skan vr->max = max; 333169689Skan 334169689Skan /* Since updating the equivalence set involves deep copying the 335169689Skan bitmaps, only do it if absolutely necessary. */ 336169689Skan if (vr->equiv == NULL) 337169689Skan vr->equiv = BITMAP_ALLOC (NULL); 338169689Skan 339169689Skan if (equiv != vr->equiv) 340169689Skan { 341169689Skan if (equiv && !bitmap_empty_p (equiv)) 342169689Skan bitmap_copy (vr->equiv, equiv); 343169689Skan else 344169689Skan bitmap_clear (vr->equiv); 345169689Skan } 346169689Skan} 347169689Skan 348169689Skan 349169689Skan/* Copy value range FROM into value range TO. */ 350169689Skan 351169689Skanstatic inline void 352169689Skancopy_value_range (value_range_t *to, value_range_t *from) 353169689Skan{ 354169689Skan set_value_range (to, from->type, from->min, from->max, from->equiv); 355169689Skan} 356169689Skan 357169689Skan 358169689Skan/* Set value range VR to VR_VARYING. */ 359169689Skan 360169689Skanstatic inline void 361169689Skanset_value_range_to_varying (value_range_t *vr) 362169689Skan{ 363169689Skan vr->type = VR_VARYING; 364169689Skan vr->min = vr->max = NULL_TREE; 365169689Skan if (vr->equiv) 366169689Skan bitmap_clear (vr->equiv); 367169689Skan} 368169689Skan 369169689Skan/* Set value range VR to a single value. This function is only called 370169689Skan with values we get from statements, and exists to clear the 371169689Skan TREE_OVERFLOW flag so that we don't think we have an overflow 372169689Skan infinity when we shouldn't. */ 373169689Skan 374169689Skanstatic inline void 375171825Skanset_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) 376169689Skan{ 377169689Skan gcc_assert (is_gimple_min_invariant (val)); 378171825Skan val = avoid_overflow_infinity (val); 379171825Skan set_value_range (vr, VR_RANGE, val, val, equiv); 380169689Skan} 381169689Skan 382169689Skan/* Set value range VR to a non-negative range of type TYPE. 383169689Skan OVERFLOW_INFINITY indicates whether to use a overflow infinity 384169689Skan rather than TYPE_MAX_VALUE; this should be true if we determine 385169689Skan that the range is nonnegative based on the assumption that signed 386169689Skan overflow does not occur. */ 387169689Skan 388169689Skanstatic inline void 389169689Skanset_value_range_to_nonnegative (value_range_t *vr, tree type, 390169689Skan bool overflow_infinity) 391169689Skan{ 392169689Skan tree zero; 393169689Skan 394169689Skan if (overflow_infinity && !supports_overflow_infinity (type)) 395169689Skan { 396169689Skan set_value_range_to_varying (vr); 397169689Skan return; 398169689Skan } 399169689Skan 400169689Skan zero = build_int_cst (type, 0); 401169689Skan set_value_range (vr, VR_RANGE, zero, 402169689Skan (overflow_infinity 403169689Skan ? positive_overflow_infinity (type) 404169689Skan : TYPE_MAX_VALUE (type)), 405169689Skan vr->equiv); 406169689Skan} 407169689Skan 408169689Skan/* Set value range VR to a non-NULL range of type TYPE. */ 409169689Skan 410169689Skanstatic inline void 411169689Skanset_value_range_to_nonnull (value_range_t *vr, tree type) 412169689Skan{ 413169689Skan tree zero = build_int_cst (type, 0); 414169689Skan set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); 415169689Skan} 416169689Skan 417169689Skan 418169689Skan/* Set value range VR to a NULL range of type TYPE. */ 419169689Skan 420169689Skanstatic inline void 421169689Skanset_value_range_to_null (value_range_t *vr, tree type) 422169689Skan{ 423171825Skan set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); 424169689Skan} 425169689Skan 426169689Skan 427169689Skan/* Set value range VR to VR_UNDEFINED. */ 428169689Skan 429169689Skanstatic inline void 430169689Skanset_value_range_to_undefined (value_range_t *vr) 431169689Skan{ 432169689Skan vr->type = VR_UNDEFINED; 433169689Skan vr->min = vr->max = NULL_TREE; 434169689Skan if (vr->equiv) 435169689Skan bitmap_clear (vr->equiv); 436169689Skan} 437169689Skan 438169689Skan 439169689Skan/* Return value range information for VAR. 440169689Skan 441169689Skan If we have no values ranges recorded (ie, VRP is not running), then 442169689Skan return NULL. Otherwise create an empty range if none existed for VAR. */ 443169689Skan 444169689Skanstatic value_range_t * 445169689Skanget_value_range (tree var) 446169689Skan{ 447169689Skan value_range_t *vr; 448169689Skan tree sym; 449169689Skan unsigned ver = SSA_NAME_VERSION (var); 450169689Skan 451169689Skan /* If we have no recorded ranges, then return NULL. */ 452169689Skan if (! vr_value) 453169689Skan return NULL; 454169689Skan 455169689Skan vr = vr_value[ver]; 456169689Skan if (vr) 457169689Skan return vr; 458169689Skan 459169689Skan /* Create a default value range. */ 460169689Skan vr_value[ver] = vr = XNEW (value_range_t); 461169689Skan memset (vr, 0, sizeof (*vr)); 462169689Skan 463169689Skan /* Allocate an equivalence set. */ 464169689Skan vr->equiv = BITMAP_ALLOC (NULL); 465169689Skan 466169689Skan /* If VAR is a default definition, the variable can take any value 467169689Skan in VAR's type. */ 468169689Skan sym = SSA_NAME_VAR (var); 469169689Skan if (var == default_def (sym)) 470169689Skan { 471169689Skan /* Try to use the "nonnull" attribute to create ~[0, 0] 472169689Skan anti-ranges for pointers. Note that this is only valid with 473169689Skan default definitions of PARM_DECLs. */ 474169689Skan if (TREE_CODE (sym) == PARM_DECL 475169689Skan && POINTER_TYPE_P (TREE_TYPE (sym)) 476169689Skan && nonnull_arg_p (sym)) 477169689Skan set_value_range_to_nonnull (vr, TREE_TYPE (sym)); 478169689Skan else 479169689Skan set_value_range_to_varying (vr); 480169689Skan } 481169689Skan 482169689Skan return vr; 483169689Skan} 484169689Skan 485169689Skan/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ 486169689Skan 487169689Skanstatic inline bool 488169689Skanvrp_operand_equal_p (tree val1, tree val2) 489169689Skan{ 490169689Skan if (val1 == val2) 491169689Skan return true; 492169689Skan if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) 493169689Skan return false; 494169689Skan if (is_overflow_infinity (val1)) 495169689Skan return is_overflow_infinity (val2); 496169689Skan return true; 497169689Skan} 498169689Skan 499169689Skan/* Return true, if the bitmaps B1 and B2 are equal. */ 500169689Skan 501169689Skanstatic inline bool 502169689Skanvrp_bitmap_equal_p (bitmap b1, bitmap b2) 503169689Skan{ 504169689Skan return (b1 == b2 505169689Skan || (b1 && b2 506169689Skan && bitmap_equal_p (b1, b2))); 507169689Skan} 508169689Skan 509169689Skan/* Update the value range and equivalence set for variable VAR to 510169689Skan NEW_VR. Return true if NEW_VR is different from VAR's previous 511169689Skan value. 512169689Skan 513169689Skan NOTE: This function assumes that NEW_VR is a temporary value range 514169689Skan object created for the sole purpose of updating VAR's range. The 515169689Skan storage used by the equivalence set from NEW_VR will be freed by 516169689Skan this function. Do not call update_value_range when NEW_VR 517169689Skan is the range object associated with another SSA name. */ 518169689Skan 519169689Skanstatic inline bool 520169689Skanupdate_value_range (tree var, value_range_t *new_vr) 521169689Skan{ 522169689Skan value_range_t *old_vr; 523169689Skan bool is_new; 524169689Skan 525169689Skan /* Update the value range, if necessary. */ 526169689Skan old_vr = get_value_range (var); 527169689Skan is_new = old_vr->type != new_vr->type 528169689Skan || !vrp_operand_equal_p (old_vr->min, new_vr->min) 529169689Skan || !vrp_operand_equal_p (old_vr->max, new_vr->max) 530169689Skan || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv); 531169689Skan 532169689Skan if (is_new) 533169689Skan set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, 534169689Skan new_vr->equiv); 535169689Skan 536169689Skan BITMAP_FREE (new_vr->equiv); 537169689Skan new_vr->equiv = NULL; 538169689Skan 539169689Skan return is_new; 540169689Skan} 541169689Skan 542169689Skan 543169689Skan/* Add VAR and VAR's equivalence set to EQUIV. */ 544169689Skan 545169689Skanstatic void 546169689Skanadd_equivalence (bitmap equiv, tree var) 547169689Skan{ 548169689Skan unsigned ver = SSA_NAME_VERSION (var); 549169689Skan value_range_t *vr = vr_value[ver]; 550169689Skan 551169689Skan bitmap_set_bit (equiv, ver); 552169689Skan if (vr && vr->equiv) 553169689Skan bitmap_ior_into (equiv, vr->equiv); 554169689Skan} 555169689Skan 556169689Skan 557169689Skan/* Return true if VR is ~[0, 0]. */ 558169689Skan 559169689Skanstatic inline bool 560169689Skanrange_is_nonnull (value_range_t *vr) 561169689Skan{ 562169689Skan return vr->type == VR_ANTI_RANGE 563169689Skan && integer_zerop (vr->min) 564169689Skan && integer_zerop (vr->max); 565169689Skan} 566169689Skan 567169689Skan 568169689Skan/* Return true if VR is [0, 0]. */ 569169689Skan 570169689Skanstatic inline bool 571169689Skanrange_is_null (value_range_t *vr) 572169689Skan{ 573169689Skan return vr->type == VR_RANGE 574169689Skan && integer_zerop (vr->min) 575169689Skan && integer_zerop (vr->max); 576169689Skan} 577169689Skan 578169689Skan 579169689Skan/* Return true if value range VR involves at least one symbol. */ 580169689Skan 581169689Skanstatic inline bool 582169689Skansymbolic_range_p (value_range_t *vr) 583169689Skan{ 584169689Skan return (!is_gimple_min_invariant (vr->min) 585169689Skan || !is_gimple_min_invariant (vr->max)); 586169689Skan} 587169689Skan 588169689Skan/* Return true if value range VR uses a overflow infinity. */ 589169689Skan 590169689Skanstatic inline bool 591169689Skanoverflow_infinity_range_p (value_range_t *vr) 592169689Skan{ 593169689Skan return (vr->type == VR_RANGE 594169689Skan && (is_overflow_infinity (vr->min) 595169689Skan || is_overflow_infinity (vr->max))); 596169689Skan} 597169689Skan 598169689Skan/* Return false if we can not make a valid comparison based on VR; 599169689Skan this will be the case if it uses an overflow infinity and overflow 600169689Skan is not undefined (i.e., -fno-strict-overflow is in effect). 601169689Skan Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR 602169689Skan uses an overflow infinity. */ 603169689Skan 604169689Skanstatic bool 605169689Skanusable_range_p (value_range_t *vr, bool *strict_overflow_p) 606169689Skan{ 607169689Skan gcc_assert (vr->type == VR_RANGE); 608169689Skan if (is_overflow_infinity (vr->min)) 609169689Skan { 610169689Skan *strict_overflow_p = true; 611169689Skan if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min))) 612169689Skan return false; 613169689Skan } 614169689Skan if (is_overflow_infinity (vr->max)) 615169689Skan { 616169689Skan *strict_overflow_p = true; 617169689Skan if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max))) 618169689Skan return false; 619169689Skan } 620169689Skan return true; 621169689Skan} 622169689Skan 623169689Skan 624169689Skan/* Like tree_expr_nonnegative_warnv_p, but this function uses value 625169689Skan ranges obtained so far. */ 626169689Skan 627169689Skanstatic bool 628169689Skanvrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p) 629169689Skan{ 630169689Skan return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p); 631169689Skan} 632169689Skan 633169689Skan/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges 634169689Skan obtained so far. */ 635169689Skan 636169689Skanstatic bool 637169689Skanvrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p) 638169689Skan{ 639169689Skan if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p)) 640169689Skan return true; 641169689Skan 642169689Skan /* If we have an expression of the form &X->a, then the expression 643169689Skan is nonnull if X is nonnull. */ 644169689Skan if (TREE_CODE (expr) == ADDR_EXPR) 645169689Skan { 646169689Skan tree base = get_base_address (TREE_OPERAND (expr, 0)); 647169689Skan 648169689Skan if (base != NULL_TREE 649169689Skan && TREE_CODE (base) == INDIRECT_REF 650169689Skan && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) 651169689Skan { 652169689Skan value_range_t *vr = get_value_range (TREE_OPERAND (base, 0)); 653169689Skan if (range_is_nonnull (vr)) 654169689Skan return true; 655169689Skan } 656169689Skan } 657169689Skan 658169689Skan return false; 659169689Skan} 660169689Skan 661169689Skan/* Returns true if EXPR is a valid value (as expected by compare_values) -- 662169689Skan a gimple invariant, or SSA_NAME +- CST. */ 663169689Skan 664169689Skanstatic bool 665169689Skanvalid_value_p (tree expr) 666169689Skan{ 667169689Skan if (TREE_CODE (expr) == SSA_NAME) 668169689Skan return true; 669169689Skan 670169689Skan if (TREE_CODE (expr) == PLUS_EXPR 671169689Skan || TREE_CODE (expr) == MINUS_EXPR) 672169689Skan return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME 673169689Skan && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST); 674169689Skan 675169689Skan return is_gimple_min_invariant (expr); 676169689Skan} 677169689Skan 678169689Skan/* Compare two values VAL1 and VAL2. Return 679169689Skan 680169689Skan -2 if VAL1 and VAL2 cannot be compared at compile-time, 681169689Skan -1 if VAL1 < VAL2, 682169689Skan 0 if VAL1 == VAL2, 683169689Skan +1 if VAL1 > VAL2, and 684169689Skan +2 if VAL1 != VAL2 685169689Skan 686169689Skan This is similar to tree_int_cst_compare but supports pointer values 687169689Skan and values that cannot be compared at compile time. 688169689Skan 689169689Skan If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to 690169689Skan true if the return value is only valid if we assume that signed 691169689Skan overflow is undefined. */ 692169689Skan 693169689Skanstatic int 694169689Skancompare_values_warnv (tree val1, tree val2, bool *strict_overflow_p) 695169689Skan{ 696169689Skan if (val1 == val2) 697169689Skan return 0; 698169689Skan 699169689Skan /* Below we rely on the fact that VAL1 and VAL2 are both pointers or 700169689Skan both integers. */ 701169689Skan gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) 702169689Skan == POINTER_TYPE_P (TREE_TYPE (val2))); 703169689Skan 704169689Skan if ((TREE_CODE (val1) == SSA_NAME 705169689Skan || TREE_CODE (val1) == PLUS_EXPR 706169689Skan || TREE_CODE (val1) == MINUS_EXPR) 707169689Skan && (TREE_CODE (val2) == SSA_NAME 708169689Skan || TREE_CODE (val2) == PLUS_EXPR 709169689Skan || TREE_CODE (val2) == MINUS_EXPR)) 710169689Skan { 711169689Skan tree n1, c1, n2, c2; 712169689Skan enum tree_code code1, code2; 713169689Skan 714169689Skan /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', 715169689Skan return -1 or +1 accordingly. If VAL1 and VAL2 don't use the 716169689Skan same name, return -2. */ 717169689Skan if (TREE_CODE (val1) == SSA_NAME) 718169689Skan { 719169689Skan code1 = SSA_NAME; 720169689Skan n1 = val1; 721169689Skan c1 = NULL_TREE; 722169689Skan } 723169689Skan else 724169689Skan { 725169689Skan code1 = TREE_CODE (val1); 726169689Skan n1 = TREE_OPERAND (val1, 0); 727169689Skan c1 = TREE_OPERAND (val1, 1); 728169689Skan if (tree_int_cst_sgn (c1) == -1) 729169689Skan { 730169689Skan if (is_negative_overflow_infinity (c1)) 731169689Skan return -2; 732169689Skan c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1); 733169689Skan if (!c1) 734169689Skan return -2; 735169689Skan code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 736169689Skan } 737169689Skan } 738169689Skan 739169689Skan if (TREE_CODE (val2) == SSA_NAME) 740169689Skan { 741169689Skan code2 = SSA_NAME; 742169689Skan n2 = val2; 743169689Skan c2 = NULL_TREE; 744169689Skan } 745169689Skan else 746169689Skan { 747169689Skan code2 = TREE_CODE (val2); 748169689Skan n2 = TREE_OPERAND (val2, 0); 749169689Skan c2 = TREE_OPERAND (val2, 1); 750169689Skan if (tree_int_cst_sgn (c2) == -1) 751169689Skan { 752169689Skan if (is_negative_overflow_infinity (c2)) 753169689Skan return -2; 754169689Skan c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2); 755169689Skan if (!c2) 756169689Skan return -2; 757169689Skan code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR; 758169689Skan } 759169689Skan } 760169689Skan 761169689Skan /* Both values must use the same name. */ 762169689Skan if (n1 != n2) 763169689Skan return -2; 764169689Skan 765169689Skan if (code1 == SSA_NAME 766169689Skan && code2 == SSA_NAME) 767169689Skan /* NAME == NAME */ 768169689Skan return 0; 769169689Skan 770169689Skan /* If overflow is defined we cannot simplify more. */ 771169689Skan if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1))) 772169689Skan return -2; 773169689Skan 774171825Skan if (strict_overflow_p != NULL 775171825Skan && (code1 == SSA_NAME || !TREE_NO_WARNING (val1)) 776171825Skan && (code2 == SSA_NAME || !TREE_NO_WARNING (val2))) 777169689Skan *strict_overflow_p = true; 778169689Skan 779169689Skan if (code1 == SSA_NAME) 780169689Skan { 781169689Skan if (code2 == PLUS_EXPR) 782169689Skan /* NAME < NAME + CST */ 783169689Skan return -1; 784169689Skan else if (code2 == MINUS_EXPR) 785169689Skan /* NAME > NAME - CST */ 786169689Skan return 1; 787169689Skan } 788169689Skan else if (code1 == PLUS_EXPR) 789169689Skan { 790169689Skan if (code2 == SSA_NAME) 791169689Skan /* NAME + CST > NAME */ 792169689Skan return 1; 793169689Skan else if (code2 == PLUS_EXPR) 794169689Skan /* NAME + CST1 > NAME + CST2, if CST1 > CST2 */ 795169689Skan return compare_values_warnv (c1, c2, strict_overflow_p); 796169689Skan else if (code2 == MINUS_EXPR) 797169689Skan /* NAME + CST1 > NAME - CST2 */ 798169689Skan return 1; 799169689Skan } 800169689Skan else if (code1 == MINUS_EXPR) 801169689Skan { 802169689Skan if (code2 == SSA_NAME) 803169689Skan /* NAME - CST < NAME */ 804169689Skan return -1; 805169689Skan else if (code2 == PLUS_EXPR) 806169689Skan /* NAME - CST1 < NAME + CST2 */ 807169689Skan return -1; 808169689Skan else if (code2 == MINUS_EXPR) 809169689Skan /* NAME - CST1 > NAME - CST2, if CST1 < CST2. Notice that 810169689Skan C1 and C2 are swapped in the call to compare_values. */ 811169689Skan return compare_values_warnv (c2, c1, strict_overflow_p); 812169689Skan } 813169689Skan 814169689Skan gcc_unreachable (); 815169689Skan } 816169689Skan 817169689Skan /* We cannot compare non-constants. */ 818169689Skan if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)) 819169689Skan return -2; 820169689Skan 821169689Skan if (!POINTER_TYPE_P (TREE_TYPE (val1))) 822169689Skan { 823169689Skan /* We cannot compare overflowed values, except for overflow 824169689Skan infinities. */ 825169689Skan if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2)) 826169689Skan { 827169689Skan if (strict_overflow_p != NULL) 828169689Skan *strict_overflow_p = true; 829169689Skan if (is_negative_overflow_infinity (val1)) 830169689Skan return is_negative_overflow_infinity (val2) ? 0 : -1; 831169689Skan else if (is_negative_overflow_infinity (val2)) 832169689Skan return 1; 833169689Skan else if (is_positive_overflow_infinity (val1)) 834169689Skan return is_positive_overflow_infinity (val2) ? 0 : 1; 835169689Skan else if (is_positive_overflow_infinity (val2)) 836169689Skan return -1; 837169689Skan return -2; 838169689Skan } 839169689Skan 840169689Skan return tree_int_cst_compare (val1, val2); 841169689Skan } 842169689Skan else 843169689Skan { 844169689Skan tree t; 845169689Skan 846169689Skan /* First see if VAL1 and VAL2 are not the same. */ 847169689Skan if (val1 == val2 || operand_equal_p (val1, val2, 0)) 848169689Skan return 0; 849169689Skan 850169689Skan /* If VAL1 is a lower address than VAL2, return -1. */ 851169689Skan t = fold_binary (LT_EXPR, boolean_type_node, val1, val2); 852169689Skan if (t == boolean_true_node) 853169689Skan return -1; 854169689Skan 855169689Skan /* If VAL1 is a higher address than VAL2, return +1. */ 856169689Skan t = fold_binary (GT_EXPR, boolean_type_node, val1, val2); 857169689Skan if (t == boolean_true_node) 858169689Skan return 1; 859169689Skan 860169689Skan /* If VAL1 is different than VAL2, return +2. */ 861169689Skan t = fold_binary (NE_EXPR, boolean_type_node, val1, val2); 862169689Skan if (t == boolean_true_node) 863169689Skan return 2; 864169689Skan 865169689Skan return -2; 866169689Skan } 867169689Skan} 868169689Skan 869169689Skan/* Compare values like compare_values_warnv, but treat comparisons of 870169689Skan nonconstants which rely on undefined overflow as incomparable. */ 871169689Skan 872169689Skanstatic int 873169689Skancompare_values (tree val1, tree val2) 874169689Skan{ 875169689Skan bool sop; 876169689Skan int ret; 877169689Skan 878169689Skan sop = false; 879169689Skan ret = compare_values_warnv (val1, val2, &sop); 880169689Skan if (sop 881169689Skan && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))) 882169689Skan ret = -2; 883169689Skan return ret; 884169689Skan} 885169689Skan 886169689Skan 887169689Skan/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX), 888169689Skan 0 if VAL is not inside VR, 889169689Skan -2 if we cannot tell either way. 890169689Skan 891169689Skan FIXME, the current semantics of this functions are a bit quirky 892169689Skan when taken in the context of VRP. In here we do not care 893169689Skan about VR's type. If VR is the anti-range ~[3, 5] the call 894169689Skan value_inside_range (4, VR) will return 1. 895169689Skan 896169689Skan This is counter-intuitive in a strict sense, but the callers 897169689Skan currently expect this. They are calling the function 898169689Skan merely to determine whether VR->MIN <= VAL <= VR->MAX. The 899169689Skan callers are applying the VR_RANGE/VR_ANTI_RANGE semantics 900169689Skan themselves. 901169689Skan 902169689Skan This also applies to value_ranges_intersect_p and 903169689Skan range_includes_zero_p. The semantics of VR_RANGE and 904169689Skan VR_ANTI_RANGE should be encoded here, but that also means 905169689Skan adapting the users of these functions to the new semantics. */ 906169689Skan 907169689Skanstatic inline int 908169689Skanvalue_inside_range (tree val, value_range_t *vr) 909169689Skan{ 910169689Skan tree cmp1, cmp2; 911169689Skan 912169689Skan fold_defer_overflow_warnings (); 913169689Skan 914169689Skan cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min); 915169689Skan if (!cmp1) 916169689Skan { 917169689Skan fold_undefer_and_ignore_overflow_warnings (); 918169689Skan return -2; 919169689Skan } 920169689Skan 921169689Skan cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max); 922169689Skan 923169689Skan fold_undefer_and_ignore_overflow_warnings (); 924169689Skan 925169689Skan if (!cmp2) 926169689Skan return -2; 927169689Skan 928169689Skan return cmp1 == boolean_true_node && cmp2 == boolean_true_node; 929169689Skan} 930169689Skan 931169689Skan 932169689Skan/* Return true if value ranges VR0 and VR1 have a non-empty 933169689Skan intersection. */ 934169689Skan 935169689Skanstatic inline bool 936169689Skanvalue_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1) 937169689Skan{ 938169689Skan return (value_inside_range (vr1->min, vr0) == 1 939169689Skan || value_inside_range (vr1->max, vr0) == 1 940169689Skan || value_inside_range (vr0->min, vr1) == 1 941169689Skan || value_inside_range (vr0->max, vr1) == 1); 942169689Skan} 943169689Skan 944169689Skan 945169689Skan/* Return true if VR includes the value zero, false otherwise. FIXME, 946169689Skan currently this will return false for an anti-range like ~[-4, 3]. 947169689Skan This will be wrong when the semantics of value_inside_range are 948169689Skan modified (currently the users of this function expect these 949169689Skan semantics). */ 950169689Skan 951169689Skanstatic inline bool 952169689Skanrange_includes_zero_p (value_range_t *vr) 953169689Skan{ 954169689Skan tree zero; 955169689Skan 956169689Skan gcc_assert (vr->type != VR_UNDEFINED 957169689Skan && vr->type != VR_VARYING 958169689Skan && !symbolic_range_p (vr)); 959169689Skan 960169689Skan zero = build_int_cst (TREE_TYPE (vr->min), 0); 961169689Skan return (value_inside_range (zero, vr) == 1); 962169689Skan} 963169689Skan 964169689Skan/* Return true if T, an SSA_NAME, is known to be nonnegative. Return 965169689Skan false otherwise or if no value range information is available. */ 966169689Skan 967169689Skanbool 968169689Skanssa_name_nonnegative_p (tree t) 969169689Skan{ 970169689Skan value_range_t *vr = get_value_range (t); 971169689Skan 972169689Skan if (!vr) 973169689Skan return false; 974169689Skan 975169689Skan /* Testing for VR_ANTI_RANGE is not useful here as any anti-range 976169689Skan which would return a useful value should be encoded as a VR_RANGE. */ 977169689Skan if (vr->type == VR_RANGE) 978169689Skan { 979169689Skan int result = compare_values (vr->min, integer_zero_node); 980169689Skan 981169689Skan return (result == 0 || result == 1); 982169689Skan } 983169689Skan return false; 984169689Skan} 985169689Skan 986169689Skan/* Return true if T, an SSA_NAME, is known to be nonzero. Return 987169689Skan false otherwise or if no value range information is available. */ 988169689Skan 989169689Skanbool 990169689Skanssa_name_nonzero_p (tree t) 991169689Skan{ 992169689Skan value_range_t *vr = get_value_range (t); 993169689Skan 994169689Skan if (!vr) 995169689Skan return false; 996169689Skan 997169689Skan /* A VR_RANGE which does not include zero is a nonzero value. */ 998169689Skan if (vr->type == VR_RANGE && !symbolic_range_p (vr)) 999169689Skan return ! range_includes_zero_p (vr); 1000169689Skan 1001169689Skan /* A VR_ANTI_RANGE which does include zero is a nonzero value. */ 1002169689Skan if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr)) 1003169689Skan return range_includes_zero_p (vr); 1004169689Skan 1005169689Skan return false; 1006169689Skan} 1007169689Skan 1008169689Skan 1009169689Skan/* Extract value range information from an ASSERT_EXPR EXPR and store 1010169689Skan it in *VR_P. */ 1011169689Skan 1012169689Skanstatic void 1013169689Skanextract_range_from_assert (value_range_t *vr_p, tree expr) 1014169689Skan{ 1015169689Skan tree var, cond, limit, min, max, type; 1016169689Skan value_range_t *var_vr, *limit_vr; 1017169689Skan enum tree_code cond_code; 1018169689Skan 1019169689Skan var = ASSERT_EXPR_VAR (expr); 1020169689Skan cond = ASSERT_EXPR_COND (expr); 1021169689Skan 1022169689Skan gcc_assert (COMPARISON_CLASS_P (cond)); 1023169689Skan 1024169689Skan /* Find VAR in the ASSERT_EXPR conditional. */ 1025169689Skan if (var == TREE_OPERAND (cond, 0)) 1026169689Skan { 1027169689Skan /* If the predicate is of the form VAR COMP LIMIT, then we just 1028169689Skan take LIMIT from the RHS and use the same comparison code. */ 1029169689Skan limit = TREE_OPERAND (cond, 1); 1030169689Skan cond_code = TREE_CODE (cond); 1031169689Skan } 1032169689Skan else 1033169689Skan { 1034169689Skan /* If the predicate is of the form LIMIT COMP VAR, then we need 1035169689Skan to flip around the comparison code to create the proper range 1036169689Skan for VAR. */ 1037169689Skan limit = TREE_OPERAND (cond, 0); 1038169689Skan cond_code = swap_tree_comparison (TREE_CODE (cond)); 1039169689Skan } 1040169689Skan 1041171825Skan limit = avoid_overflow_infinity (limit); 1042171825Skan 1043169689Skan type = TREE_TYPE (limit); 1044169689Skan gcc_assert (limit != var); 1045169689Skan 1046169689Skan /* For pointer arithmetic, we only keep track of pointer equality 1047169689Skan and inequality. */ 1048169689Skan if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR) 1049169689Skan { 1050169689Skan set_value_range_to_varying (vr_p); 1051169689Skan return; 1052169689Skan } 1053169689Skan 1054169689Skan /* If LIMIT is another SSA name and LIMIT has a range of its own, 1055169689Skan try to use LIMIT's range to avoid creating symbolic ranges 1056169689Skan unnecessarily. */ 1057169689Skan limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL; 1058169689Skan 1059169689Skan /* LIMIT's range is only interesting if it has any useful information. */ 1060169689Skan if (limit_vr 1061169689Skan && (limit_vr->type == VR_UNDEFINED 1062169689Skan || limit_vr->type == VR_VARYING 1063169689Skan || symbolic_range_p (limit_vr))) 1064169689Skan limit_vr = NULL; 1065169689Skan 1066169689Skan /* Initially, the new range has the same set of equivalences of 1067169689Skan VAR's range. This will be revised before returning the final 1068169689Skan value. Since assertions may be chained via mutually exclusive 1069169689Skan predicates, we will need to trim the set of equivalences before 1070169689Skan we are done. */ 1071169689Skan gcc_assert (vr_p->equiv == NULL); 1072169689Skan vr_p->equiv = BITMAP_ALLOC (NULL); 1073169689Skan add_equivalence (vr_p->equiv, var); 1074169689Skan 1075169689Skan /* Extract a new range based on the asserted comparison for VAR and 1076169689Skan LIMIT's value range. Notice that if LIMIT has an anti-range, we 1077169689Skan will only use it for equality comparisons (EQ_EXPR). For any 1078169689Skan other kind of assertion, we cannot derive a range from LIMIT's 1079169689Skan anti-range that can be used to describe the new range. For 1080169689Skan instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10], 1081169689Skan then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is 1082169689Skan no single range for x_2 that could describe LE_EXPR, so we might 1083169689Skan as well build the range [b_4, +INF] for it. */ 1084169689Skan if (cond_code == EQ_EXPR) 1085169689Skan { 1086169689Skan enum value_range_type range_type; 1087169689Skan 1088169689Skan if (limit_vr) 1089169689Skan { 1090169689Skan range_type = limit_vr->type; 1091169689Skan min = limit_vr->min; 1092169689Skan max = limit_vr->max; 1093169689Skan } 1094169689Skan else 1095169689Skan { 1096169689Skan range_type = VR_RANGE; 1097169689Skan min = limit; 1098169689Skan max = limit; 1099169689Skan } 1100169689Skan 1101169689Skan set_value_range (vr_p, range_type, min, max, vr_p->equiv); 1102169689Skan 1103169689Skan /* When asserting the equality VAR == LIMIT and LIMIT is another 1104169689Skan SSA name, the new range will also inherit the equivalence set 1105169689Skan from LIMIT. */ 1106169689Skan if (TREE_CODE (limit) == SSA_NAME) 1107169689Skan add_equivalence (vr_p->equiv, limit); 1108169689Skan } 1109169689Skan else if (cond_code == NE_EXPR) 1110169689Skan { 1111169689Skan /* As described above, when LIMIT's range is an anti-range and 1112169689Skan this assertion is an inequality (NE_EXPR), then we cannot 1113169689Skan derive anything from the anti-range. For instance, if 1114169689Skan LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does 1115169689Skan not imply that VAR's range is [0, 0]. So, in the case of 1116169689Skan anti-ranges, we just assert the inequality using LIMIT and 1117169689Skan not its anti-range. 1118169689Skan 1119169689Skan If LIMIT_VR is a range, we can only use it to build a new 1120169689Skan anti-range if LIMIT_VR is a single-valued range. For 1121169689Skan instance, if LIMIT_VR is [0, 1], the predicate 1122169689Skan VAR != [0, 1] does not mean that VAR's range is ~[0, 1]. 1123169689Skan Rather, it means that for value 0 VAR should be ~[0, 0] 1124169689Skan and for value 1, VAR should be ~[1, 1]. We cannot 1125169689Skan represent these ranges. 1126169689Skan 1127169689Skan The only situation in which we can build a valid 1128169689Skan anti-range is when LIMIT_VR is a single-valued range 1129169689Skan (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case, 1130169689Skan build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */ 1131169689Skan if (limit_vr 1132169689Skan && limit_vr->type == VR_RANGE 1133169689Skan && compare_values (limit_vr->min, limit_vr->max) == 0) 1134169689Skan { 1135169689Skan min = limit_vr->min; 1136169689Skan max = limit_vr->max; 1137169689Skan } 1138169689Skan else 1139169689Skan { 1140169689Skan /* In any other case, we cannot use LIMIT's range to build a 1141169689Skan valid anti-range. */ 1142169689Skan min = max = limit; 1143169689Skan } 1144169689Skan 1145169689Skan /* If MIN and MAX cover the whole range for their type, then 1146169689Skan just use the original LIMIT. */ 1147169689Skan if (INTEGRAL_TYPE_P (type) 1148169689Skan && vrp_val_is_min (min) 1149169689Skan && vrp_val_is_max (max)) 1150169689Skan min = max = limit; 1151169689Skan 1152169689Skan set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv); 1153169689Skan } 1154169689Skan else if (cond_code == LE_EXPR || cond_code == LT_EXPR) 1155169689Skan { 1156169689Skan min = TYPE_MIN_VALUE (type); 1157169689Skan 1158169689Skan if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 1159169689Skan max = limit; 1160169689Skan else 1161169689Skan { 1162169689Skan /* If LIMIT_VR is of the form [N1, N2], we need to build the 1163169689Skan range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for 1164169689Skan LT_EXPR. */ 1165169689Skan max = limit_vr->max; 1166169689Skan } 1167169689Skan 1168169689Skan /* If the maximum value forces us to be out of bounds, simply punt. 1169169689Skan It would be pointless to try and do anything more since this 1170169689Skan all should be optimized away above us. */ 1171169689Skan if ((cond_code == LT_EXPR 1172169689Skan && compare_values (max, min) == 0) 1173169689Skan || is_overflow_infinity (max)) 1174169689Skan set_value_range_to_varying (vr_p); 1175169689Skan else 1176169689Skan { 1177169689Skan /* For LT_EXPR, we create the range [MIN, MAX - 1]. */ 1178169689Skan if (cond_code == LT_EXPR) 1179169689Skan { 1180169689Skan tree one = build_int_cst (type, 1); 1181169689Skan max = fold_build2 (MINUS_EXPR, type, max, one); 1182171825Skan if (EXPR_P (max)) 1183171825Skan TREE_NO_WARNING (max) = 1; 1184169689Skan } 1185169689Skan 1186169689Skan set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1187169689Skan } 1188169689Skan } 1189169689Skan else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 1190169689Skan { 1191169689Skan max = TYPE_MAX_VALUE (type); 1192169689Skan 1193169689Skan if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE) 1194169689Skan min = limit; 1195169689Skan else 1196169689Skan { 1197169689Skan /* If LIMIT_VR is of the form [N1, N2], we need to build the 1198169689Skan range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for 1199169689Skan GT_EXPR. */ 1200169689Skan min = limit_vr->min; 1201169689Skan } 1202169689Skan 1203169689Skan /* If the minimum value forces us to be out of bounds, simply punt. 1204169689Skan It would be pointless to try and do anything more since this 1205169689Skan all should be optimized away above us. */ 1206169689Skan if ((cond_code == GT_EXPR 1207169689Skan && compare_values (min, max) == 0) 1208169689Skan || is_overflow_infinity (min)) 1209169689Skan set_value_range_to_varying (vr_p); 1210169689Skan else 1211169689Skan { 1212169689Skan /* For GT_EXPR, we create the range [MIN + 1, MAX]. */ 1213169689Skan if (cond_code == GT_EXPR) 1214169689Skan { 1215169689Skan tree one = build_int_cst (type, 1); 1216169689Skan min = fold_build2 (PLUS_EXPR, type, min, one); 1217171825Skan if (EXPR_P (min)) 1218171825Skan TREE_NO_WARNING (min) = 1; 1219169689Skan } 1220169689Skan 1221169689Skan set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1222169689Skan } 1223169689Skan } 1224169689Skan else 1225169689Skan gcc_unreachable (); 1226169689Skan 1227169689Skan /* If VAR already had a known range, it may happen that the new 1228169689Skan range we have computed and VAR's range are not compatible. For 1229169689Skan instance, 1230169689Skan 1231169689Skan if (p_5 == NULL) 1232169689Skan p_6 = ASSERT_EXPR <p_5, p_5 == NULL>; 1233169689Skan x_7 = p_6->fld; 1234169689Skan p_8 = ASSERT_EXPR <p_6, p_6 != NULL>; 1235169689Skan 1236169689Skan While the above comes from a faulty program, it will cause an ICE 1237169689Skan later because p_8 and p_6 will have incompatible ranges and at 1238169689Skan the same time will be considered equivalent. A similar situation 1239169689Skan would arise from 1240169689Skan 1241169689Skan if (i_5 > 10) 1242169689Skan i_6 = ASSERT_EXPR <i_5, i_5 > 10>; 1243169689Skan if (i_5 < 5) 1244169689Skan i_7 = ASSERT_EXPR <i_6, i_6 < 5>; 1245169689Skan 1246169689Skan Again i_6 and i_7 will have incompatible ranges. It would be 1247169689Skan pointless to try and do anything with i_7's range because 1248169689Skan anything dominated by 'if (i_5 < 5)' will be optimized away. 1249169689Skan Note, due to the wa in which simulation proceeds, the statement 1250169689Skan i_7 = ASSERT_EXPR <...> we would never be visited because the 1251169689Skan conditional 'if (i_5 < 5)' always evaluates to false. However, 1252169689Skan this extra check does not hurt and may protect against future 1253169689Skan changes to VRP that may get into a situation similar to the 1254169689Skan NULL pointer dereference example. 1255169689Skan 1256169689Skan Note that these compatibility tests are only needed when dealing 1257169689Skan with ranges or a mix of range and anti-range. If VAR_VR and VR_P 1258169689Skan are both anti-ranges, they will always be compatible, because two 1259169689Skan anti-ranges will always have a non-empty intersection. */ 1260169689Skan 1261169689Skan var_vr = get_value_range (var); 1262169689Skan 1263169689Skan /* We may need to make adjustments when VR_P and VAR_VR are numeric 1264169689Skan ranges or anti-ranges. */ 1265169689Skan if (vr_p->type == VR_VARYING 1266169689Skan || vr_p->type == VR_UNDEFINED 1267169689Skan || var_vr->type == VR_VARYING 1268169689Skan || var_vr->type == VR_UNDEFINED 1269169689Skan || symbolic_range_p (vr_p) 1270169689Skan || symbolic_range_p (var_vr)) 1271169689Skan return; 1272169689Skan 1273169689Skan if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE) 1274169689Skan { 1275169689Skan /* If the two ranges have a non-empty intersection, we can 1276169689Skan refine the resulting range. Since the assert expression 1277169689Skan creates an equivalency and at the same time it asserts a 1278169689Skan predicate, we can take the intersection of the two ranges to 1279169689Skan get better precision. */ 1280169689Skan if (value_ranges_intersect_p (var_vr, vr_p)) 1281169689Skan { 1282169689Skan /* Use the larger of the two minimums. */ 1283169689Skan if (compare_values (vr_p->min, var_vr->min) == -1) 1284169689Skan min = var_vr->min; 1285169689Skan else 1286169689Skan min = vr_p->min; 1287169689Skan 1288169689Skan /* Use the smaller of the two maximums. */ 1289169689Skan if (compare_values (vr_p->max, var_vr->max) == 1) 1290169689Skan max = var_vr->max; 1291169689Skan else 1292169689Skan max = vr_p->max; 1293169689Skan 1294169689Skan set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv); 1295169689Skan } 1296169689Skan else 1297169689Skan { 1298169689Skan /* The two ranges do not intersect, set the new range to 1299169689Skan VARYING, because we will not be able to do anything 1300169689Skan meaningful with it. */ 1301169689Skan set_value_range_to_varying (vr_p); 1302169689Skan } 1303169689Skan } 1304169689Skan else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE) 1305169689Skan || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE)) 1306169689Skan { 1307169689Skan /* A range and an anti-range will cancel each other only if 1308169689Skan their ends are the same. For instance, in the example above, 1309169689Skan p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible, 1310169689Skan so VR_P should be set to VR_VARYING. */ 1311169689Skan if (compare_values (var_vr->min, vr_p->min) == 0 1312169689Skan && compare_values (var_vr->max, vr_p->max) == 0) 1313169689Skan set_value_range_to_varying (vr_p); 1314169689Skan else 1315169689Skan { 1316169689Skan tree min, max, anti_min, anti_max, real_min, real_max; 1317169689Skan 1318169689Skan /* We want to compute the logical AND of the two ranges; 1319169689Skan there are three cases to consider. 1320169689Skan 1321169689Skan 1322169689Skan 1. The VR_ANTI_RANGE range is completely within the 1323169689Skan VR_RANGE and the endpoints of the ranges are 1324169689Skan different. In that case the resulting range 1325169689Skan should be whichever range is more precise. 1326169689Skan Typically that will be the VR_RANGE. 1327169689Skan 1328169689Skan 2. The VR_ANTI_RANGE is completely disjoint from 1329169689Skan the VR_RANGE. In this case the resulting range 1330169689Skan should be the VR_RANGE. 1331169689Skan 1332169689Skan 3. There is some overlap between the VR_ANTI_RANGE 1333169689Skan and the VR_RANGE. 1334169689Skan 1335169689Skan 3a. If the high limit of the VR_ANTI_RANGE resides 1336169689Skan within the VR_RANGE, then the result is a new 1337169689Skan VR_RANGE starting at the high limit of the 1338169689Skan the VR_ANTI_RANGE + 1 and extending to the 1339169689Skan high limit of the original VR_RANGE. 1340169689Skan 1341169689Skan 3b. If the low limit of the VR_ANTI_RANGE resides 1342169689Skan within the VR_RANGE, then the result is a new 1343169689Skan VR_RANGE starting at the low limit of the original 1344169689Skan VR_RANGE and extending to the low limit of the 1345169689Skan VR_ANTI_RANGE - 1. */ 1346169689Skan if (vr_p->type == VR_ANTI_RANGE) 1347169689Skan { 1348169689Skan anti_min = vr_p->min; 1349169689Skan anti_max = vr_p->max; 1350169689Skan real_min = var_vr->min; 1351169689Skan real_max = var_vr->max; 1352169689Skan } 1353169689Skan else 1354169689Skan { 1355169689Skan anti_min = var_vr->min; 1356169689Skan anti_max = var_vr->max; 1357169689Skan real_min = vr_p->min; 1358169689Skan real_max = vr_p->max; 1359169689Skan } 1360169689Skan 1361169689Skan 1362169689Skan /* Case 1, VR_ANTI_RANGE completely within VR_RANGE, 1363169689Skan not including any endpoints. */ 1364169689Skan if (compare_values (anti_max, real_max) == -1 1365169689Skan && compare_values (anti_min, real_min) == 1) 1366169689Skan { 1367169689Skan set_value_range (vr_p, VR_RANGE, real_min, 1368169689Skan real_max, vr_p->equiv); 1369169689Skan } 1370169689Skan /* Case 2, VR_ANTI_RANGE completely disjoint from 1371169689Skan VR_RANGE. */ 1372169689Skan else if (compare_values (anti_min, real_max) == 1 1373169689Skan || compare_values (anti_max, real_min) == -1) 1374169689Skan { 1375169689Skan set_value_range (vr_p, VR_RANGE, real_min, 1376169689Skan real_max, vr_p->equiv); 1377169689Skan } 1378169689Skan /* Case 3a, the anti-range extends into the low 1379169689Skan part of the real range. Thus creating a new 1380169689Skan low for the real range. */ 1381169689Skan else if ((compare_values (anti_max, real_min) == 1 1382169689Skan || compare_values (anti_max, real_min) == 0) 1383169689Skan && compare_values (anti_max, real_max) == -1) 1384169689Skan { 1385169689Skan gcc_assert (!is_positive_overflow_infinity (anti_max)); 1386169689Skan if (needs_overflow_infinity (TREE_TYPE (anti_max)) 1387169689Skan && vrp_val_is_max (anti_max)) 1388169689Skan { 1389169689Skan if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 1390169689Skan { 1391169689Skan set_value_range_to_varying (vr_p); 1392169689Skan return; 1393169689Skan } 1394169689Skan min = positive_overflow_infinity (TREE_TYPE (var_vr->min)); 1395169689Skan } 1396169689Skan else 1397169689Skan min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min), 1398169689Skan anti_max, 1399169689Skan build_int_cst (TREE_TYPE (var_vr->min), 1)); 1400169689Skan max = real_max; 1401169689Skan set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1402169689Skan } 1403169689Skan /* Case 3b, the anti-range extends into the high 1404169689Skan part of the real range. Thus creating a new 1405169689Skan higher for the real range. */ 1406169689Skan else if (compare_values (anti_min, real_min) == 1 1407169689Skan && (compare_values (anti_min, real_max) == -1 1408169689Skan || compare_values (anti_min, real_max) == 0)) 1409169689Skan { 1410169689Skan gcc_assert (!is_negative_overflow_infinity (anti_min)); 1411169689Skan if (needs_overflow_infinity (TREE_TYPE (anti_min)) 1412169689Skan && vrp_val_is_min (anti_min)) 1413169689Skan { 1414169689Skan if (!supports_overflow_infinity (TREE_TYPE (var_vr->min))) 1415169689Skan { 1416169689Skan set_value_range_to_varying (vr_p); 1417169689Skan return; 1418169689Skan } 1419169689Skan max = negative_overflow_infinity (TREE_TYPE (var_vr->min)); 1420169689Skan } 1421169689Skan else 1422169689Skan max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min), 1423169689Skan anti_min, 1424169689Skan build_int_cst (TREE_TYPE (var_vr->min), 1)); 1425169689Skan min = real_min; 1426169689Skan set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); 1427169689Skan } 1428169689Skan } 1429169689Skan } 1430169689Skan} 1431169689Skan 1432169689Skan 1433169689Skan/* Extract range information from SSA name VAR and store it in VR. If 1434169689Skan VAR has an interesting range, use it. Otherwise, create the 1435169689Skan range [VAR, VAR] and return it. This is useful in situations where 1436169689Skan we may have conditionals testing values of VARYING names. For 1437169689Skan instance, 1438169689Skan 1439169689Skan x_3 = y_5; 1440169689Skan if (x_3 > y_5) 1441169689Skan ... 1442169689Skan 1443169689Skan Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is 1444169689Skan always false. */ 1445169689Skan 1446169689Skanstatic void 1447169689Skanextract_range_from_ssa_name (value_range_t *vr, tree var) 1448169689Skan{ 1449169689Skan value_range_t *var_vr = get_value_range (var); 1450169689Skan 1451169689Skan if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING) 1452169689Skan copy_value_range (vr, var_vr); 1453169689Skan else 1454169689Skan set_value_range (vr, VR_RANGE, var, var, NULL); 1455169689Skan 1456169689Skan add_equivalence (vr->equiv, var); 1457169689Skan} 1458169689Skan 1459169689Skan 1460169689Skan/* Wrapper around int_const_binop. If the operation overflows and we 1461169689Skan are not using wrapping arithmetic, then adjust the result to be 1462169689Skan -INF or +INF depending on CODE, VAL1 and VAL2. This can return 1463169689Skan NULL_TREE if we need to use an overflow infinity representation but 1464169689Skan the type does not support it. */ 1465169689Skan 1466169689Skanstatic tree 1467169689Skanvrp_int_const_binop (enum tree_code code, tree val1, tree val2) 1468169689Skan{ 1469169689Skan tree res; 1470169689Skan 1471169689Skan res = int_const_binop (code, val1, val2, 0); 1472169689Skan 1473169689Skan /* If we are not using wrapping arithmetic, operate symbolically 1474169689Skan on -INF and +INF. */ 1475169689Skan if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) 1476169689Skan { 1477169689Skan int checkz = compare_values (res, val1); 1478169689Skan bool overflow = false; 1479169689Skan 1480169689Skan /* Ensure that res = val1 [+*] val2 >= val1 1481169689Skan or that res = val1 - val2 <= val1. */ 1482169689Skan if ((code == PLUS_EXPR 1483169689Skan && !(checkz == 1 || checkz == 0)) 1484169689Skan || (code == MINUS_EXPR 1485169689Skan && !(checkz == 0 || checkz == -1))) 1486169689Skan { 1487169689Skan overflow = true; 1488169689Skan } 1489169689Skan /* Checking for multiplication overflow is done by dividing the 1490169689Skan output of the multiplication by the first input of the 1491169689Skan multiplication. If the result of that division operation is 1492169689Skan not equal to the second input of the multiplication, then the 1493169689Skan multiplication overflowed. */ 1494169689Skan else if (code == MULT_EXPR && !integer_zerop (val1)) 1495169689Skan { 1496169689Skan tree tmp = int_const_binop (TRUNC_DIV_EXPR, 1497169689Skan res, 1498169689Skan val1, 0); 1499169689Skan int check = compare_values (tmp, val2); 1500169689Skan 1501169689Skan if (check != 0) 1502169689Skan overflow = true; 1503169689Skan } 1504169689Skan 1505169689Skan if (overflow) 1506169689Skan { 1507169689Skan res = copy_node (res); 1508169689Skan TREE_OVERFLOW (res) = 1; 1509169689Skan } 1510169689Skan 1511169689Skan } 1512169689Skan else if ((TREE_OVERFLOW (res) 1513169689Skan && !TREE_OVERFLOW (val1) 1514169689Skan && !TREE_OVERFLOW (val2)) 1515169689Skan || is_overflow_infinity (val1) 1516169689Skan || is_overflow_infinity (val2)) 1517169689Skan { 1518169689Skan /* If the operation overflowed but neither VAL1 nor VAL2 are 1519169689Skan overflown, return -INF or +INF depending on the operation 1520169689Skan and the combination of signs of the operands. */ 1521169689Skan int sgn1 = tree_int_cst_sgn (val1); 1522169689Skan int sgn2 = tree_int_cst_sgn (val2); 1523169689Skan 1524169689Skan if (needs_overflow_infinity (TREE_TYPE (res)) 1525169689Skan && !supports_overflow_infinity (TREE_TYPE (res))) 1526169689Skan return NULL_TREE; 1527169689Skan 1528169689Skan /* We have to punt on adding infinities of different signs, 1529169689Skan since we can't tell what the sign of the result should be. 1530169689Skan Likewise for subtracting infinities of the same sign. */ 1531169689Skan if (((code == PLUS_EXPR && sgn1 != sgn2) 1532169689Skan || (code == MINUS_EXPR && sgn1 == sgn2)) 1533169689Skan && is_overflow_infinity (val1) 1534169689Skan && is_overflow_infinity (val2)) 1535169689Skan return NULL_TREE; 1536169689Skan 1537169689Skan /* Don't try to handle division or shifting of infinities. */ 1538169689Skan if ((code == TRUNC_DIV_EXPR 1539169689Skan || code == FLOOR_DIV_EXPR 1540169689Skan || code == CEIL_DIV_EXPR 1541169689Skan || code == EXACT_DIV_EXPR 1542169689Skan || code == ROUND_DIV_EXPR 1543169689Skan || code == RSHIFT_EXPR) 1544169689Skan && (is_overflow_infinity (val1) 1545169689Skan || is_overflow_infinity (val2))) 1546169689Skan return NULL_TREE; 1547169689Skan 1548169689Skan /* Notice that we only need to handle the restricted set of 1549169689Skan operations handled by extract_range_from_binary_expr. 1550169689Skan Among them, only multiplication, addition and subtraction 1551169689Skan can yield overflow without overflown operands because we 1552169689Skan are working with integral types only... except in the 1553169689Skan case VAL1 = -INF and VAL2 = -1 which overflows to +INF 1554169689Skan for division too. */ 1555169689Skan 1556169689Skan /* For multiplication, the sign of the overflow is given 1557169689Skan by the comparison of the signs of the operands. */ 1558169689Skan if ((code == MULT_EXPR && sgn1 == sgn2) 1559169689Skan /* For addition, the operands must be of the same sign 1560169689Skan to yield an overflow. Its sign is therefore that 1561169689Skan of one of the operands, for example the first. For 1562169689Skan infinite operands X + -INF is negative, not positive. */ 1563169689Skan || (code == PLUS_EXPR 1564169689Skan && (sgn1 >= 0 1565169689Skan ? !is_negative_overflow_infinity (val2) 1566169689Skan : is_positive_overflow_infinity (val2))) 1567169689Skan /* For subtraction, non-infinite operands must be of 1568169689Skan different signs to yield an overflow. Its sign is 1569169689Skan therefore that of the first operand or the opposite of 1570169689Skan that of the second operand. A first operand of 0 counts 1571169689Skan as positive here, for the corner case 0 - (-INF), which 1572169689Skan overflows, but must yield +INF. For infinite operands 0 1573169689Skan - INF is negative, not positive. */ 1574169689Skan || (code == MINUS_EXPR 1575169689Skan && (sgn1 >= 0 1576169689Skan ? !is_positive_overflow_infinity (val2) 1577169689Skan : is_negative_overflow_infinity (val2))) 1578169689Skan /* For division, the only case is -INF / -1 = +INF. */ 1579169689Skan || code == TRUNC_DIV_EXPR 1580169689Skan || code == FLOOR_DIV_EXPR 1581169689Skan || code == CEIL_DIV_EXPR 1582169689Skan || code == EXACT_DIV_EXPR 1583169689Skan || code == ROUND_DIV_EXPR) 1584169689Skan return (needs_overflow_infinity (TREE_TYPE (res)) 1585169689Skan ? positive_overflow_infinity (TREE_TYPE (res)) 1586169689Skan : TYPE_MAX_VALUE (TREE_TYPE (res))); 1587169689Skan else 1588169689Skan return (needs_overflow_infinity (TREE_TYPE (res)) 1589169689Skan ? negative_overflow_infinity (TREE_TYPE (res)) 1590169689Skan : TYPE_MIN_VALUE (TREE_TYPE (res))); 1591169689Skan } 1592169689Skan 1593169689Skan return res; 1594169689Skan} 1595169689Skan 1596169689Skan 1597169689Skan/* Extract range information from a binary expression EXPR based on 1598169689Skan the ranges of each of its operands and the expression code. */ 1599169689Skan 1600169689Skanstatic void 1601169689Skanextract_range_from_binary_expr (value_range_t *vr, tree expr) 1602169689Skan{ 1603169689Skan enum tree_code code = TREE_CODE (expr); 1604169689Skan enum value_range_type type; 1605169689Skan tree op0, op1, min, max; 1606169689Skan int cmp; 1607169689Skan value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1608169689Skan value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 1609169689Skan 1610169689Skan /* Not all binary expressions can be applied to ranges in a 1611169689Skan meaningful way. Handle only arithmetic operations. */ 1612169689Skan if (code != PLUS_EXPR 1613169689Skan && code != MINUS_EXPR 1614169689Skan && code != MULT_EXPR 1615169689Skan && code != TRUNC_DIV_EXPR 1616169689Skan && code != FLOOR_DIV_EXPR 1617169689Skan && code != CEIL_DIV_EXPR 1618169689Skan && code != EXACT_DIV_EXPR 1619169689Skan && code != ROUND_DIV_EXPR 1620169689Skan && code != MIN_EXPR 1621169689Skan && code != MAX_EXPR 1622169689Skan && code != BIT_AND_EXPR 1623169689Skan && code != TRUTH_ANDIF_EXPR 1624169689Skan && code != TRUTH_ORIF_EXPR 1625169689Skan && code != TRUTH_AND_EXPR 1626169689Skan && code != TRUTH_OR_EXPR) 1627169689Skan { 1628169689Skan set_value_range_to_varying (vr); 1629169689Skan return; 1630169689Skan } 1631169689Skan 1632169689Skan /* Get value ranges for each operand. For constant operands, create 1633169689Skan a new value range with the operand to simplify processing. */ 1634169689Skan op0 = TREE_OPERAND (expr, 0); 1635169689Skan if (TREE_CODE (op0) == SSA_NAME) 1636169689Skan vr0 = *(get_value_range (op0)); 1637169689Skan else if (is_gimple_min_invariant (op0)) 1638171825Skan set_value_range_to_value (&vr0, op0, NULL); 1639169689Skan else 1640169689Skan set_value_range_to_varying (&vr0); 1641169689Skan 1642169689Skan op1 = TREE_OPERAND (expr, 1); 1643169689Skan if (TREE_CODE (op1) == SSA_NAME) 1644169689Skan vr1 = *(get_value_range (op1)); 1645169689Skan else if (is_gimple_min_invariant (op1)) 1646171825Skan set_value_range_to_value (&vr1, op1, NULL); 1647169689Skan else 1648169689Skan set_value_range_to_varying (&vr1); 1649169689Skan 1650169689Skan /* If either range is UNDEFINED, so is the result. */ 1651169689Skan if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED) 1652169689Skan { 1653169689Skan set_value_range_to_undefined (vr); 1654169689Skan return; 1655169689Skan } 1656169689Skan 1657169689Skan /* The type of the resulting value range defaults to VR0.TYPE. */ 1658169689Skan type = vr0.type; 1659169689Skan 1660169689Skan /* Refuse to operate on VARYING ranges, ranges of different kinds 1661169689Skan and symbolic ranges. As an exception, we allow BIT_AND_EXPR 1662169689Skan because we may be able to derive a useful range even if one of 1663169689Skan the operands is VR_VARYING or symbolic range. TODO, we may be 1664169689Skan able to derive anti-ranges in some cases. */ 1665169689Skan if (code != BIT_AND_EXPR 1666169689Skan && code != TRUTH_AND_EXPR 1667169689Skan && code != TRUTH_OR_EXPR 1668169689Skan && (vr0.type == VR_VARYING 1669169689Skan || vr1.type == VR_VARYING 1670169689Skan || vr0.type != vr1.type 1671169689Skan || symbolic_range_p (&vr0) 1672169689Skan || symbolic_range_p (&vr1))) 1673169689Skan { 1674169689Skan set_value_range_to_varying (vr); 1675169689Skan return; 1676169689Skan } 1677169689Skan 1678169689Skan /* Now evaluate the expression to determine the new range. */ 1679169689Skan if (POINTER_TYPE_P (TREE_TYPE (expr)) 1680169689Skan || POINTER_TYPE_P (TREE_TYPE (op0)) 1681169689Skan || POINTER_TYPE_P (TREE_TYPE (op1))) 1682169689Skan { 1683169689Skan /* For pointer types, we are really only interested in asserting 1684169689Skan whether the expression evaluates to non-NULL. FIXME, we used 1685169689Skan to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but 1686169689Skan ivopts is generating expressions with pointer multiplication 1687169689Skan in them. */ 1688169689Skan if (code == PLUS_EXPR) 1689169689Skan { 1690169689Skan if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1)) 1691169689Skan set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 1692169689Skan else if (range_is_null (&vr0) && range_is_null (&vr1)) 1693169689Skan set_value_range_to_null (vr, TREE_TYPE (expr)); 1694169689Skan else 1695169689Skan set_value_range_to_varying (vr); 1696169689Skan } 1697169689Skan else 1698169689Skan { 1699169689Skan /* Subtracting from a pointer, may yield 0, so just drop the 1700169689Skan resulting range to varying. */ 1701169689Skan set_value_range_to_varying (vr); 1702169689Skan } 1703169689Skan 1704169689Skan return; 1705169689Skan } 1706169689Skan 1707169689Skan /* For integer ranges, apply the operation to each end of the 1708169689Skan range and see what we end up with. */ 1709169689Skan if (code == TRUTH_ANDIF_EXPR 1710169689Skan || code == TRUTH_ORIF_EXPR 1711169689Skan || code == TRUTH_AND_EXPR 1712169689Skan || code == TRUTH_OR_EXPR) 1713169689Skan { 1714169689Skan /* If one of the operands is zero, we know that the whole 1715169689Skan expression evaluates zero. */ 1716169689Skan if (code == TRUTH_AND_EXPR 1717169689Skan && ((vr0.type == VR_RANGE 1718169689Skan && integer_zerop (vr0.min) 1719169689Skan && integer_zerop (vr0.max)) 1720169689Skan || (vr1.type == VR_RANGE 1721169689Skan && integer_zerop (vr1.min) 1722169689Skan && integer_zerop (vr1.max)))) 1723169689Skan { 1724169689Skan type = VR_RANGE; 1725169689Skan min = max = build_int_cst (TREE_TYPE (expr), 0); 1726169689Skan } 1727169689Skan /* If one of the operands is one, we know that the whole 1728169689Skan expression evaluates one. */ 1729169689Skan else if (code == TRUTH_OR_EXPR 1730169689Skan && ((vr0.type == VR_RANGE 1731169689Skan && integer_onep (vr0.min) 1732169689Skan && integer_onep (vr0.max)) 1733169689Skan || (vr1.type == VR_RANGE 1734169689Skan && integer_onep (vr1.min) 1735169689Skan && integer_onep (vr1.max)))) 1736169689Skan { 1737169689Skan type = VR_RANGE; 1738169689Skan min = max = build_int_cst (TREE_TYPE (expr), 1); 1739169689Skan } 1740169689Skan else if (vr0.type != VR_VARYING 1741169689Skan && vr1.type != VR_VARYING 1742169689Skan && vr0.type == vr1.type 1743169689Skan && !symbolic_range_p (&vr0) 1744169689Skan && !overflow_infinity_range_p (&vr0) 1745169689Skan && !symbolic_range_p (&vr1) 1746169689Skan && !overflow_infinity_range_p (&vr1)) 1747169689Skan { 1748169689Skan /* Boolean expressions cannot be folded with int_const_binop. */ 1749169689Skan min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min); 1750169689Skan max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max); 1751169689Skan } 1752169689Skan else 1753169689Skan { 1754169689Skan set_value_range_to_varying (vr); 1755169689Skan return; 1756169689Skan } 1757169689Skan } 1758169689Skan else if (code == PLUS_EXPR 1759169689Skan || code == MIN_EXPR 1760169689Skan || code == MAX_EXPR) 1761169689Skan { 1762169689Skan /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to 1763169689Skan VR_VARYING. It would take more effort to compute a precise 1764169689Skan range for such a case. For example, if we have op0 == 1 and 1765169689Skan op1 == -1 with their ranges both being ~[0,0], we would have 1766169689Skan op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0]. 1767169689Skan Note that we are guaranteed to have vr0.type == vr1.type at 1768169689Skan this point. */ 1769169689Skan if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE) 1770169689Skan { 1771169689Skan set_value_range_to_varying (vr); 1772169689Skan return; 1773169689Skan } 1774169689Skan 1775169689Skan /* For operations that make the resulting range directly 1776169689Skan proportional to the original ranges, apply the operation to 1777169689Skan the same end of each range. */ 1778169689Skan min = vrp_int_const_binop (code, vr0.min, vr1.min); 1779169689Skan max = vrp_int_const_binop (code, vr0.max, vr1.max); 1780169689Skan } 1781169689Skan else if (code == MULT_EXPR 1782169689Skan || code == TRUNC_DIV_EXPR 1783169689Skan || code == FLOOR_DIV_EXPR 1784169689Skan || code == CEIL_DIV_EXPR 1785169689Skan || code == EXACT_DIV_EXPR 1786169689Skan || code == ROUND_DIV_EXPR) 1787169689Skan { 1788169689Skan tree val[4]; 1789169689Skan size_t i; 1790169689Skan bool sop; 1791169689Skan 1792169689Skan /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs, 1793169689Skan drop to VR_VARYING. It would take more effort to compute a 1794169689Skan precise range for such a case. For example, if we have 1795169689Skan op0 == 65536 and op1 == 65536 with their ranges both being 1796169689Skan ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so 1797169689Skan we cannot claim that the product is in ~[0,0]. Note that we 1798169689Skan are guaranteed to have vr0.type == vr1.type at this 1799169689Skan point. */ 1800169689Skan if (code == MULT_EXPR 1801169689Skan && vr0.type == VR_ANTI_RANGE 1802169689Skan && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))) 1803169689Skan { 1804169689Skan set_value_range_to_varying (vr); 1805169689Skan return; 1806169689Skan } 1807169689Skan 1808169689Skan /* Multiplications and divisions are a bit tricky to handle, 1809169689Skan depending on the mix of signs we have in the two ranges, we 1810169689Skan need to operate on different values to get the minimum and 1811169689Skan maximum values for the new range. One approach is to figure 1812169689Skan out all the variations of range combinations and do the 1813169689Skan operations. 1814169689Skan 1815169689Skan However, this involves several calls to compare_values and it 1816169689Skan is pretty convoluted. It's simpler to do the 4 operations 1817169689Skan (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP 1818169689Skan MAX1) and then figure the smallest and largest values to form 1819169689Skan the new range. */ 1820169689Skan 1821169689Skan /* Divisions by zero result in a VARYING value. */ 1822169689Skan if (code != MULT_EXPR 1823169689Skan && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1))) 1824169689Skan { 1825169689Skan set_value_range_to_varying (vr); 1826169689Skan return; 1827169689Skan } 1828169689Skan 1829169689Skan /* Compute the 4 cross operations. */ 1830169689Skan sop = false; 1831169689Skan val[0] = vrp_int_const_binop (code, vr0.min, vr1.min); 1832169689Skan if (val[0] == NULL_TREE) 1833169689Skan sop = true; 1834169689Skan 1835169689Skan if (vr1.max == vr1.min) 1836169689Skan val[1] = NULL_TREE; 1837169689Skan else 1838169689Skan { 1839169689Skan val[1] = vrp_int_const_binop (code, vr0.min, vr1.max); 1840169689Skan if (val[1] == NULL_TREE) 1841169689Skan sop = true; 1842169689Skan } 1843169689Skan 1844169689Skan if (vr0.max == vr0.min) 1845169689Skan val[2] = NULL_TREE; 1846169689Skan else 1847169689Skan { 1848169689Skan val[2] = vrp_int_const_binop (code, vr0.max, vr1.min); 1849169689Skan if (val[2] == NULL_TREE) 1850169689Skan sop = true; 1851169689Skan } 1852169689Skan 1853169689Skan if (vr0.min == vr0.max || vr1.min == vr1.max) 1854169689Skan val[3] = NULL_TREE; 1855169689Skan else 1856169689Skan { 1857169689Skan val[3] = vrp_int_const_binop (code, vr0.max, vr1.max); 1858169689Skan if (val[3] == NULL_TREE) 1859169689Skan sop = true; 1860169689Skan } 1861169689Skan 1862169689Skan if (sop) 1863169689Skan { 1864169689Skan set_value_range_to_varying (vr); 1865169689Skan return; 1866169689Skan } 1867169689Skan 1868169689Skan /* Set MIN to the minimum of VAL[i] and MAX to the maximum 1869169689Skan of VAL[i]. */ 1870169689Skan min = val[0]; 1871169689Skan max = val[0]; 1872169689Skan for (i = 1; i < 4; i++) 1873169689Skan { 1874169689Skan if (!is_gimple_min_invariant (min) 1875169689Skan || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 1876169689Skan || !is_gimple_min_invariant (max) 1877169689Skan || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 1878169689Skan break; 1879169689Skan 1880169689Skan if (val[i]) 1881169689Skan { 1882169689Skan if (!is_gimple_min_invariant (val[i]) 1883169689Skan || (TREE_OVERFLOW (val[i]) 1884169689Skan && !is_overflow_infinity (val[i]))) 1885169689Skan { 1886169689Skan /* If we found an overflowed value, set MIN and MAX 1887169689Skan to it so that we set the resulting range to 1888169689Skan VARYING. */ 1889169689Skan min = max = val[i]; 1890169689Skan break; 1891169689Skan } 1892169689Skan 1893169689Skan if (compare_values (val[i], min) == -1) 1894169689Skan min = val[i]; 1895169689Skan 1896169689Skan if (compare_values (val[i], max) == 1) 1897169689Skan max = val[i]; 1898169689Skan } 1899169689Skan } 1900169689Skan } 1901169689Skan else if (code == MINUS_EXPR) 1902169689Skan { 1903169689Skan /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to 1904169689Skan VR_VARYING. It would take more effort to compute a precise 1905169689Skan range for such a case. For example, if we have op0 == 1 and 1906169689Skan op1 == 1 with their ranges both being ~[0,0], we would have 1907169689Skan op0 - op1 == 0, so we cannot claim that the difference is in 1908169689Skan ~[0,0]. Note that we are guaranteed to have 1909169689Skan vr0.type == vr1.type at this point. */ 1910169689Skan if (vr0.type == VR_ANTI_RANGE) 1911169689Skan { 1912169689Skan set_value_range_to_varying (vr); 1913169689Skan return; 1914169689Skan } 1915169689Skan 1916169689Skan /* For MINUS_EXPR, apply the operation to the opposite ends of 1917169689Skan each range. */ 1918169689Skan min = vrp_int_const_binop (code, vr0.min, vr1.max); 1919169689Skan max = vrp_int_const_binop (code, vr0.max, vr1.min); 1920169689Skan } 1921169689Skan else if (code == BIT_AND_EXPR) 1922169689Skan { 1923169689Skan if (vr0.type == VR_RANGE 1924169689Skan && vr0.min == vr0.max 1925169689Skan && TREE_CODE (vr0.max) == INTEGER_CST 1926169689Skan && !TREE_OVERFLOW (vr0.max) 1927169689Skan && tree_int_cst_sgn (vr0.max) >= 0) 1928169689Skan { 1929169689Skan min = build_int_cst (TREE_TYPE (expr), 0); 1930169689Skan max = vr0.max; 1931169689Skan } 1932169689Skan else if (vr1.type == VR_RANGE 1933169689Skan && vr1.min == vr1.max 1934169689Skan && TREE_CODE (vr1.max) == INTEGER_CST 1935169689Skan && !TREE_OVERFLOW (vr1.max) 1936169689Skan && tree_int_cst_sgn (vr1.max) >= 0) 1937169689Skan { 1938169689Skan type = VR_RANGE; 1939169689Skan min = build_int_cst (TREE_TYPE (expr), 0); 1940169689Skan max = vr1.max; 1941169689Skan } 1942169689Skan else 1943169689Skan { 1944169689Skan set_value_range_to_varying (vr); 1945169689Skan return; 1946169689Skan } 1947169689Skan } 1948169689Skan else 1949169689Skan gcc_unreachable (); 1950169689Skan 1951169689Skan /* If either MIN or MAX overflowed, then set the resulting range to 1952169689Skan VARYING. But we do accept an overflow infinity 1953169689Skan representation. */ 1954169689Skan if (min == NULL_TREE 1955169689Skan || !is_gimple_min_invariant (min) 1956169689Skan || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) 1957169689Skan || max == NULL_TREE 1958169689Skan || !is_gimple_min_invariant (max) 1959169689Skan || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) 1960169689Skan { 1961169689Skan set_value_range_to_varying (vr); 1962169689Skan return; 1963169689Skan } 1964169689Skan 1965169689Skan /* We punt if: 1966169689Skan 1) [-INF, +INF] 1967169689Skan 2) [-INF, +-INF(OVF)] 1968169689Skan 3) [+-INF(OVF), +INF] 1969169689Skan 4) [+-INF(OVF), +-INF(OVF)] 1970169689Skan We learn nothing when we have INF and INF(OVF) on both sides. 1971169689Skan Note that we do accept [-INF, -INF] and [+INF, +INF] without 1972169689Skan overflow. */ 1973169689Skan if ((vrp_val_is_min (min) || is_overflow_infinity (min)) 1974169689Skan && (vrp_val_is_max (max) || is_overflow_infinity (max))) 1975169689Skan { 1976169689Skan set_value_range_to_varying (vr); 1977169689Skan return; 1978169689Skan } 1979169689Skan 1980169689Skan cmp = compare_values (min, max); 1981169689Skan if (cmp == -2 || cmp == 1) 1982169689Skan { 1983169689Skan /* If the new range has its limits swapped around (MIN > MAX), 1984169689Skan then the operation caused one of them to wrap around, mark 1985169689Skan the new range VARYING. */ 1986169689Skan set_value_range_to_varying (vr); 1987169689Skan } 1988169689Skan else 1989169689Skan set_value_range (vr, type, min, max, NULL); 1990169689Skan} 1991169689Skan 1992169689Skan 1993169689Skan/* Extract range information from a unary expression EXPR based on 1994169689Skan the range of its operand and the expression code. */ 1995169689Skan 1996169689Skanstatic void 1997169689Skanextract_range_from_unary_expr (value_range_t *vr, tree expr) 1998169689Skan{ 1999169689Skan enum tree_code code = TREE_CODE (expr); 2000169689Skan tree min, max, op0; 2001169689Skan int cmp; 2002169689Skan value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 2003169689Skan 2004169689Skan /* Refuse to operate on certain unary expressions for which we 2005169689Skan cannot easily determine a resulting range. */ 2006169689Skan if (code == FIX_TRUNC_EXPR 2007169689Skan || code == FIX_CEIL_EXPR 2008169689Skan || code == FIX_FLOOR_EXPR 2009169689Skan || code == FIX_ROUND_EXPR 2010169689Skan || code == FLOAT_EXPR 2011169689Skan || code == BIT_NOT_EXPR 2012169689Skan || code == NON_LVALUE_EXPR 2013169689Skan || code == CONJ_EXPR) 2014169689Skan { 2015169689Skan set_value_range_to_varying (vr); 2016169689Skan return; 2017169689Skan } 2018169689Skan 2019169689Skan /* Get value ranges for the operand. For constant operands, create 2020169689Skan a new value range with the operand to simplify processing. */ 2021169689Skan op0 = TREE_OPERAND (expr, 0); 2022169689Skan if (TREE_CODE (op0) == SSA_NAME) 2023169689Skan vr0 = *(get_value_range (op0)); 2024169689Skan else if (is_gimple_min_invariant (op0)) 2025171825Skan set_value_range_to_value (&vr0, op0, NULL); 2026169689Skan else 2027169689Skan set_value_range_to_varying (&vr0); 2028169689Skan 2029169689Skan /* If VR0 is UNDEFINED, so is the result. */ 2030169689Skan if (vr0.type == VR_UNDEFINED) 2031169689Skan { 2032169689Skan set_value_range_to_undefined (vr); 2033169689Skan return; 2034169689Skan } 2035169689Skan 2036169689Skan /* Refuse to operate on symbolic ranges, or if neither operand is 2037169689Skan a pointer or integral type. */ 2038169689Skan if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 2039169689Skan && !POINTER_TYPE_P (TREE_TYPE (op0))) 2040169689Skan || (vr0.type != VR_VARYING 2041169689Skan && symbolic_range_p (&vr0))) 2042169689Skan { 2043169689Skan set_value_range_to_varying (vr); 2044169689Skan return; 2045169689Skan } 2046169689Skan 2047169689Skan /* If the expression involves pointers, we are only interested in 2048169689Skan determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */ 2049169689Skan if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0))) 2050169689Skan { 2051169689Skan bool sop; 2052169689Skan 2053169689Skan sop = false; 2054169689Skan if (range_is_nonnull (&vr0) 2055169689Skan || (tree_expr_nonzero_warnv_p (expr, &sop) 2056169689Skan && !sop)) 2057169689Skan set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 2058169689Skan else if (range_is_null (&vr0)) 2059169689Skan set_value_range_to_null (vr, TREE_TYPE (expr)); 2060169689Skan else 2061169689Skan set_value_range_to_varying (vr); 2062169689Skan 2063169689Skan return; 2064169689Skan } 2065169689Skan 2066169689Skan /* Handle unary expressions on integer ranges. */ 2067169689Skan if (code == NOP_EXPR || code == CONVERT_EXPR) 2068169689Skan { 2069169689Skan tree inner_type = TREE_TYPE (op0); 2070169689Skan tree outer_type = TREE_TYPE (expr); 2071169689Skan 2072169689Skan /* If VR0 represents a simple range, then try to convert 2073169689Skan the min and max values for the range to the same type 2074169689Skan as OUTER_TYPE. If the results compare equal to VR0's 2075169689Skan min and max values and the new min is still less than 2076169689Skan or equal to the new max, then we can safely use the newly 2077169689Skan computed range for EXPR. This allows us to compute 2078169689Skan accurate ranges through many casts. */ 2079169689Skan if ((vr0.type == VR_RANGE 2080169689Skan && !overflow_infinity_range_p (&vr0)) 2081169689Skan || (vr0.type == VR_VARYING 2082169689Skan && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type))) 2083169689Skan { 2084169689Skan tree new_min, new_max, orig_min, orig_max; 2085169689Skan 2086169689Skan /* Convert the input operand min/max to OUTER_TYPE. If 2087169689Skan the input has no range information, then use the min/max 2088169689Skan for the input's type. */ 2089169689Skan if (vr0.type == VR_RANGE) 2090169689Skan { 2091169689Skan orig_min = vr0.min; 2092169689Skan orig_max = vr0.max; 2093169689Skan } 2094169689Skan else 2095169689Skan { 2096169689Skan orig_min = TYPE_MIN_VALUE (inner_type); 2097169689Skan orig_max = TYPE_MAX_VALUE (inner_type); 2098169689Skan } 2099169689Skan 2100169689Skan new_min = fold_convert (outer_type, orig_min); 2101169689Skan new_max = fold_convert (outer_type, orig_max); 2102169689Skan 2103169689Skan /* Verify the new min/max values are gimple values and 2104169689Skan that they compare equal to the original input's 2105169689Skan min/max values. */ 2106169689Skan if (is_gimple_val (new_min) 2107169689Skan && is_gimple_val (new_max) 2108169689Skan && tree_int_cst_equal (new_min, orig_min) 2109169689Skan && tree_int_cst_equal (new_max, orig_max) 2110171825Skan && (!is_overflow_infinity (new_min) 2111171825Skan || !is_overflow_infinity (new_max)) 2112169689Skan && compare_values (new_min, new_max) <= 0 2113169689Skan && compare_values (new_min, new_max) >= -1) 2114169689Skan { 2115169689Skan set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv); 2116169689Skan return; 2117169689Skan } 2118169689Skan } 2119169689Skan 2120169689Skan /* When converting types of different sizes, set the result to 2121169689Skan VARYING. Things like sign extensions and precision loss may 2122169689Skan change the range. For instance, if x_3 is of type 'long long 2123169689Skan int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it 2124169689Skan is impossible to know at compile time whether y_5 will be 2125169689Skan ~[0, 0]. */ 2126169689Skan if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type) 2127169689Skan || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type)) 2128169689Skan { 2129169689Skan set_value_range_to_varying (vr); 2130169689Skan return; 2131169689Skan } 2132169689Skan } 2133169689Skan 2134169689Skan /* Conversion of a VR_VARYING value to a wider type can result 2135169689Skan in a usable range. So wait until after we've handled conversions 2136169689Skan before dropping the result to VR_VARYING if we had a source 2137169689Skan operand that is VR_VARYING. */ 2138169689Skan if (vr0.type == VR_VARYING) 2139169689Skan { 2140169689Skan set_value_range_to_varying (vr); 2141169689Skan return; 2142169689Skan } 2143169689Skan 2144169689Skan /* Apply the operation to each end of the range and see what we end 2145169689Skan up with. */ 2146169689Skan if (code == NEGATE_EXPR 2147169689Skan && !TYPE_UNSIGNED (TREE_TYPE (expr))) 2148169689Skan { 2149169689Skan /* NEGATE_EXPR flips the range around. We need to treat 2150169689Skan TYPE_MIN_VALUE specially. */ 2151169689Skan if (is_positive_overflow_infinity (vr0.max)) 2152169689Skan min = negative_overflow_infinity (TREE_TYPE (expr)); 2153169689Skan else if (is_negative_overflow_infinity (vr0.max)) 2154169689Skan min = positive_overflow_infinity (TREE_TYPE (expr)); 2155169689Skan else if (!vrp_val_is_min (vr0.max)) 2156169689Skan min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2157169689Skan else if (needs_overflow_infinity (TREE_TYPE (expr))) 2158169689Skan { 2159169689Skan if (supports_overflow_infinity (TREE_TYPE (expr)) 2160169689Skan && !is_overflow_infinity (vr0.min) 2161169689Skan && !vrp_val_is_min (vr0.min)) 2162169689Skan min = positive_overflow_infinity (TREE_TYPE (expr)); 2163169689Skan else 2164169689Skan { 2165169689Skan set_value_range_to_varying (vr); 2166169689Skan return; 2167169689Skan } 2168169689Skan } 2169169689Skan else 2170169689Skan min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2171169689Skan 2172169689Skan if (is_positive_overflow_infinity (vr0.min)) 2173169689Skan max = negative_overflow_infinity (TREE_TYPE (expr)); 2174169689Skan else if (is_negative_overflow_infinity (vr0.min)) 2175169689Skan max = positive_overflow_infinity (TREE_TYPE (expr)); 2176169689Skan else if (!vrp_val_is_min (vr0.min)) 2177169689Skan max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2178169689Skan else if (needs_overflow_infinity (TREE_TYPE (expr))) 2179169689Skan { 2180169689Skan if (supports_overflow_infinity (TREE_TYPE (expr))) 2181169689Skan max = positive_overflow_infinity (TREE_TYPE (expr)); 2182169689Skan else 2183169689Skan { 2184169689Skan set_value_range_to_varying (vr); 2185169689Skan return; 2186169689Skan } 2187169689Skan } 2188169689Skan else 2189169689Skan max = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2190169689Skan } 2191169689Skan else if (code == NEGATE_EXPR 2192169689Skan && TYPE_UNSIGNED (TREE_TYPE (expr))) 2193169689Skan { 2194169689Skan if (!range_includes_zero_p (&vr0)) 2195169689Skan { 2196169689Skan max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2197169689Skan min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2198169689Skan } 2199169689Skan else 2200169689Skan { 2201169689Skan if (range_is_null (&vr0)) 2202169689Skan set_value_range_to_null (vr, TREE_TYPE (expr)); 2203169689Skan else 2204169689Skan set_value_range_to_varying (vr); 2205169689Skan return; 2206169689Skan } 2207169689Skan } 2208169689Skan else if (code == ABS_EXPR 2209169689Skan && !TYPE_UNSIGNED (TREE_TYPE (expr))) 2210169689Skan { 2211169689Skan /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a 2212169689Skan useful range. */ 2213169689Skan if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr)) 2214169689Skan && ((vr0.type == VR_RANGE 2215169689Skan && vrp_val_is_min (vr0.min)) 2216169689Skan || (vr0.type == VR_ANTI_RANGE 2217169689Skan && !vrp_val_is_min (vr0.min) 2218169689Skan && !range_includes_zero_p (&vr0)))) 2219169689Skan { 2220169689Skan set_value_range_to_varying (vr); 2221169689Skan return; 2222169689Skan } 2223169689Skan 2224169689Skan /* ABS_EXPR may flip the range around, if the original range 2225169689Skan included negative values. */ 2226169689Skan if (is_overflow_infinity (vr0.min)) 2227169689Skan min = positive_overflow_infinity (TREE_TYPE (expr)); 2228169689Skan else if (!vrp_val_is_min (vr0.min)) 2229169689Skan min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2230169689Skan else if (!needs_overflow_infinity (TREE_TYPE (expr))) 2231169689Skan min = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2232169689Skan else if (supports_overflow_infinity (TREE_TYPE (expr))) 2233169689Skan min = positive_overflow_infinity (TREE_TYPE (expr)); 2234169689Skan else 2235169689Skan { 2236169689Skan set_value_range_to_varying (vr); 2237169689Skan return; 2238169689Skan } 2239169689Skan 2240169689Skan if (is_overflow_infinity (vr0.max)) 2241169689Skan max = positive_overflow_infinity (TREE_TYPE (expr)); 2242169689Skan else if (!vrp_val_is_min (vr0.max)) 2243169689Skan max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2244169689Skan else if (!needs_overflow_infinity (TREE_TYPE (expr))) 2245169689Skan max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2246169689Skan else if (supports_overflow_infinity (TREE_TYPE (expr))) 2247169689Skan max = positive_overflow_infinity (TREE_TYPE (expr)); 2248169689Skan else 2249169689Skan { 2250169689Skan set_value_range_to_varying (vr); 2251169689Skan return; 2252169689Skan } 2253169689Skan 2254169689Skan cmp = compare_values (min, max); 2255169689Skan 2256169689Skan /* If a VR_ANTI_RANGEs contains zero, then we have 2257169689Skan ~[-INF, min(MIN, MAX)]. */ 2258169689Skan if (vr0.type == VR_ANTI_RANGE) 2259169689Skan { 2260169689Skan if (range_includes_zero_p (&vr0)) 2261169689Skan { 2262169689Skan /* Take the lower of the two values. */ 2263169689Skan if (cmp != 1) 2264169689Skan max = min; 2265169689Skan 2266169689Skan /* Create ~[-INF, min (abs(MIN), abs(MAX))] 2267169689Skan or ~[-INF + 1, min (abs(MIN), abs(MAX))] when 2268169689Skan flag_wrapv is set and the original anti-range doesn't include 2269169689Skan TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */ 2270169689Skan if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) 2271169689Skan { 2272169689Skan tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2273169689Skan 2274169689Skan min = (vr0.min != type_min_value 2275169689Skan ? int_const_binop (PLUS_EXPR, type_min_value, 2276169689Skan integer_one_node, 0) 2277169689Skan : type_min_value); 2278169689Skan } 2279169689Skan else 2280169689Skan { 2281169689Skan if (overflow_infinity_range_p (&vr0)) 2282169689Skan min = negative_overflow_infinity (TREE_TYPE (expr)); 2283169689Skan else 2284169689Skan min = TYPE_MIN_VALUE (TREE_TYPE (expr)); 2285169689Skan } 2286169689Skan } 2287169689Skan else 2288169689Skan { 2289169689Skan /* All else has failed, so create the range [0, INF], even for 2290169689Skan flag_wrapv since TYPE_MIN_VALUE is in the original 2291169689Skan anti-range. */ 2292169689Skan vr0.type = VR_RANGE; 2293169689Skan min = build_int_cst (TREE_TYPE (expr), 0); 2294169689Skan if (needs_overflow_infinity (TREE_TYPE (expr))) 2295169689Skan { 2296169689Skan if (supports_overflow_infinity (TREE_TYPE (expr))) 2297169689Skan max = positive_overflow_infinity (TREE_TYPE (expr)); 2298169689Skan else 2299169689Skan { 2300169689Skan set_value_range_to_varying (vr); 2301169689Skan return; 2302169689Skan } 2303169689Skan } 2304169689Skan else 2305169689Skan max = TYPE_MAX_VALUE (TREE_TYPE (expr)); 2306169689Skan } 2307169689Skan } 2308169689Skan 2309169689Skan /* If the range contains zero then we know that the minimum value in the 2310169689Skan range will be zero. */ 2311169689Skan else if (range_includes_zero_p (&vr0)) 2312169689Skan { 2313169689Skan if (cmp == 1) 2314169689Skan max = min; 2315169689Skan min = build_int_cst (TREE_TYPE (expr), 0); 2316169689Skan } 2317169689Skan else 2318169689Skan { 2319169689Skan /* If the range was reversed, swap MIN and MAX. */ 2320169689Skan if (cmp == 1) 2321169689Skan { 2322169689Skan tree t = min; 2323169689Skan min = max; 2324169689Skan max = t; 2325169689Skan } 2326169689Skan } 2327169689Skan } 2328169689Skan else 2329169689Skan { 2330169689Skan /* Otherwise, operate on each end of the range. */ 2331169689Skan min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min); 2332169689Skan max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max); 2333169689Skan 2334169689Skan if (needs_overflow_infinity (TREE_TYPE (expr))) 2335169689Skan { 2336169689Skan gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR); 2337169689Skan 2338169689Skan /* If both sides have overflowed, we don't know 2339169689Skan anything. */ 2340169689Skan if ((is_overflow_infinity (vr0.min) 2341169689Skan || TREE_OVERFLOW (min)) 2342169689Skan && (is_overflow_infinity (vr0.max) 2343169689Skan || TREE_OVERFLOW (max))) 2344169689Skan { 2345169689Skan set_value_range_to_varying (vr); 2346169689Skan return; 2347169689Skan } 2348169689Skan 2349169689Skan if (is_overflow_infinity (vr0.min)) 2350169689Skan min = vr0.min; 2351169689Skan else if (TREE_OVERFLOW (min)) 2352169689Skan { 2353169689Skan if (supports_overflow_infinity (TREE_TYPE (expr))) 2354169689Skan min = (tree_int_cst_sgn (min) >= 0 2355169689Skan ? positive_overflow_infinity (TREE_TYPE (min)) 2356169689Skan : negative_overflow_infinity (TREE_TYPE (min))); 2357169689Skan else 2358169689Skan { 2359169689Skan set_value_range_to_varying (vr); 2360169689Skan return; 2361169689Skan } 2362169689Skan } 2363169689Skan 2364169689Skan if (is_overflow_infinity (vr0.max)) 2365169689Skan max = vr0.max; 2366169689Skan else if (TREE_OVERFLOW (max)) 2367169689Skan { 2368169689Skan if (supports_overflow_infinity (TREE_TYPE (expr))) 2369169689Skan max = (tree_int_cst_sgn (max) >= 0 2370169689Skan ? positive_overflow_infinity (TREE_TYPE (max)) 2371169689Skan : negative_overflow_infinity (TREE_TYPE (max))); 2372169689Skan else 2373169689Skan { 2374169689Skan set_value_range_to_varying (vr); 2375169689Skan return; 2376169689Skan } 2377169689Skan } 2378169689Skan } 2379169689Skan } 2380169689Skan 2381169689Skan cmp = compare_values (min, max); 2382169689Skan if (cmp == -2 || cmp == 1) 2383169689Skan { 2384169689Skan /* If the new range has its limits swapped around (MIN > MAX), 2385169689Skan then the operation caused one of them to wrap around, mark 2386169689Skan the new range VARYING. */ 2387169689Skan set_value_range_to_varying (vr); 2388169689Skan } 2389169689Skan else 2390169689Skan set_value_range (vr, vr0.type, min, max, NULL); 2391169689Skan} 2392169689Skan 2393169689Skan 2394169689Skan/* Extract range information from a comparison expression EXPR based 2395169689Skan on the range of its operand and the expression code. */ 2396169689Skan 2397169689Skanstatic void 2398169689Skanextract_range_from_comparison (value_range_t *vr, tree expr) 2399169689Skan{ 2400169689Skan bool sop = false; 2401169689Skan tree val = vrp_evaluate_conditional_warnv (expr, false, &sop); 2402169689Skan 2403169689Skan /* A disadvantage of using a special infinity as an overflow 2404169689Skan representation is that we lose the ability to record overflow 2405169689Skan when we don't have an infinity. So we have to ignore a result 2406169689Skan which relies on overflow. */ 2407169689Skan 2408169689Skan if (val && !is_overflow_infinity (val) && !sop) 2409169689Skan { 2410169689Skan /* Since this expression was found on the RHS of an assignment, 2411169689Skan its type may be different from _Bool. Convert VAL to EXPR's 2412169689Skan type. */ 2413169689Skan val = fold_convert (TREE_TYPE (expr), val); 2414171825Skan if (is_gimple_min_invariant (val)) 2415171825Skan set_value_range_to_value (vr, val, vr->equiv); 2416171825Skan else 2417171825Skan set_value_range (vr, VR_RANGE, val, val, vr->equiv); 2418169689Skan } 2419169689Skan else 2420169689Skan set_value_range_to_varying (vr); 2421169689Skan} 2422169689Skan 2423169689Skan 2424169689Skan/* Try to compute a useful range out of expression EXPR and store it 2425169689Skan in *VR. */ 2426169689Skan 2427169689Skanstatic void 2428169689Skanextract_range_from_expr (value_range_t *vr, tree expr) 2429169689Skan{ 2430169689Skan enum tree_code code = TREE_CODE (expr); 2431169689Skan 2432169689Skan if (code == ASSERT_EXPR) 2433169689Skan extract_range_from_assert (vr, expr); 2434169689Skan else if (code == SSA_NAME) 2435169689Skan extract_range_from_ssa_name (vr, expr); 2436169689Skan else if (TREE_CODE_CLASS (code) == tcc_binary 2437169689Skan || code == TRUTH_ANDIF_EXPR 2438169689Skan || code == TRUTH_ORIF_EXPR 2439169689Skan || code == TRUTH_AND_EXPR 2440169689Skan || code == TRUTH_OR_EXPR 2441169689Skan || code == TRUTH_XOR_EXPR) 2442169689Skan extract_range_from_binary_expr (vr, expr); 2443169689Skan else if (TREE_CODE_CLASS (code) == tcc_unary) 2444169689Skan extract_range_from_unary_expr (vr, expr); 2445169689Skan else if (TREE_CODE_CLASS (code) == tcc_comparison) 2446169689Skan extract_range_from_comparison (vr, expr); 2447169689Skan else if (is_gimple_min_invariant (expr)) 2448171825Skan set_value_range_to_value (vr, expr, NULL); 2449169689Skan else 2450169689Skan set_value_range_to_varying (vr); 2451169689Skan 2452169689Skan /* If we got a varying range from the tests above, try a final 2453169689Skan time to derive a nonnegative or nonzero range. This time 2454169689Skan relying primarily on generic routines in fold in conjunction 2455169689Skan with range data. */ 2456169689Skan if (vr->type == VR_VARYING) 2457169689Skan { 2458169689Skan bool sop = false; 2459169689Skan 2460169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (expr)) 2461169689Skan && vrp_expr_computes_nonnegative (expr, &sop)) 2462169689Skan set_value_range_to_nonnegative (vr, TREE_TYPE (expr), 2463169689Skan sop || is_overflow_infinity (expr)); 2464169689Skan else if (vrp_expr_computes_nonzero (expr, &sop) 2465169689Skan && !sop) 2466169689Skan set_value_range_to_nonnull (vr, TREE_TYPE (expr)); 2467169689Skan } 2468169689Skan} 2469169689Skan 2470169689Skan/* Given a range VR, a LOOP and a variable VAR, determine whether it 2471169689Skan would be profitable to adjust VR using scalar evolution information 2472169689Skan for VAR. If so, update VR with the new limits. */ 2473169689Skan 2474169689Skanstatic void 2475169689Skanadjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, 2476169689Skan tree var) 2477169689Skan{ 2478169689Skan tree init, step, chrec, tmin, tmax, min, max, type; 2479169689Skan enum ev_direction dir; 2480169689Skan 2481169689Skan /* TODO. Don't adjust anti-ranges. An anti-range may provide 2482169689Skan better opportunities than a regular range, but I'm not sure. */ 2483169689Skan if (vr->type == VR_ANTI_RANGE) 2484169689Skan return; 2485169689Skan 2486169689Skan chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var)); 2487169689Skan if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2488169689Skan return; 2489169689Skan 2490169689Skan init = initial_condition_in_loop_num (chrec, loop->num); 2491169689Skan step = evolution_part_in_loop_num (chrec, loop->num); 2492169689Skan 2493169689Skan /* If STEP is symbolic, we can't know whether INIT will be the 2494169689Skan minimum or maximum value in the range. Also, unless INIT is 2495169689Skan a simple expression, compare_values and possibly other functions 2496169689Skan in tree-vrp won't be able to handle it. */ 2497169689Skan if (step == NULL_TREE 2498169689Skan || !is_gimple_min_invariant (step) 2499169689Skan || !valid_value_p (init)) 2500169689Skan return; 2501169689Skan 2502169689Skan dir = scev_direction (chrec); 2503169689Skan if (/* Do not adjust ranges if we do not know whether the iv increases 2504169689Skan or decreases, ... */ 2505169689Skan dir == EV_DIR_UNKNOWN 2506169689Skan /* ... or if it may wrap. */ 2507169689Skan || scev_probably_wraps_p (init, step, stmt, 2508169689Skan current_loops->parray[CHREC_VARIABLE (chrec)], 2509169689Skan true)) 2510169689Skan return; 2511169689Skan 2512259405Spfg type = TREE_TYPE (var); 2513259405Spfg 2514259405Spfg /* If we see a pointer type starting at a constant, then we have an 2515259405Spfg unusual ivopt. It may legitimately wrap. */ 2516259405Spfg if (POINTER_TYPE_P (type) && is_gimple_min_invariant (init)) 2517259405Spfg return; 2518259405Spfg 2519169689Skan /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of 2520169689Skan negative_overflow_infinity and positive_overflow_infinity, 2521169689Skan because we have concluded that the loop probably does not 2522169689Skan wrap. */ 2523169689Skan 2524169689Skan if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 2525169689Skan tmin = lower_bound_in_type (type, type); 2526169689Skan else 2527169689Skan tmin = TYPE_MIN_VALUE (type); 2528169689Skan if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 2529169689Skan tmax = upper_bound_in_type (type, type); 2530169689Skan else 2531169689Skan tmax = TYPE_MAX_VALUE (type); 2532169689Skan 2533169689Skan if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2534169689Skan { 2535169689Skan min = tmin; 2536169689Skan max = tmax; 2537169689Skan 2538169689Skan /* For VARYING or UNDEFINED ranges, just about anything we get 2539169689Skan from scalar evolutions should be better. */ 2540169689Skan 2541169689Skan if (dir == EV_DIR_DECREASES) 2542169689Skan max = init; 2543169689Skan else 2544169689Skan min = init; 2545169689Skan 2546169689Skan /* If we would create an invalid range, then just assume we 2547169689Skan know absolutely nothing. This may be over-conservative, 2548169689Skan but it's clearly safe, and should happen only in unreachable 2549169689Skan parts of code, or for invalid programs. */ 2550169689Skan if (compare_values (min, max) == 1) 2551169689Skan return; 2552169689Skan 2553169689Skan set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2554169689Skan } 2555169689Skan else if (vr->type == VR_RANGE) 2556169689Skan { 2557169689Skan min = vr->min; 2558169689Skan max = vr->max; 2559169689Skan 2560169689Skan if (dir == EV_DIR_DECREASES) 2561169689Skan { 2562169689Skan /* INIT is the maximum value. If INIT is lower than VR->MAX 2563169689Skan but no smaller than VR->MIN, set VR->MAX to INIT. */ 2564169689Skan if (compare_values (init, max) == -1) 2565169689Skan { 2566169689Skan max = init; 2567169689Skan 2568169689Skan /* If we just created an invalid range with the minimum 2569169689Skan greater than the maximum, we fail conservatively. 2570169689Skan This should happen only in unreachable 2571169689Skan parts of code, or for invalid programs. */ 2572169689Skan if (compare_values (min, max) == 1) 2573169689Skan return; 2574169689Skan } 2575171825Skan 2576171825Skan /* According to the loop information, the variable does not 2577171825Skan overflow. If we think it does, probably because of an 2578171825Skan overflow due to arithmetic on a different INF value, 2579171825Skan reset now. */ 2580171825Skan if (is_negative_overflow_infinity (min)) 2581171825Skan min = tmin; 2582169689Skan } 2583169689Skan else 2584169689Skan { 2585169689Skan /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ 2586169689Skan if (compare_values (init, min) == 1) 2587169689Skan { 2588169689Skan min = init; 2589169689Skan 2590169689Skan /* Again, avoid creating invalid range by failing. */ 2591169689Skan if (compare_values (min, max) == 1) 2592169689Skan return; 2593169689Skan } 2594171825Skan 2595171825Skan if (is_positive_overflow_infinity (max)) 2596171825Skan max = tmax; 2597169689Skan } 2598169689Skan 2599169689Skan set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2600169689Skan } 2601169689Skan} 2602169689Skan 2603171825Skan/* Return true if VAR may overflow at STMT. This checks any available 2604171825Skan loop information to see if we can determine that VAR does not 2605171825Skan overflow. */ 2606169689Skan 2607171825Skanstatic bool 2608171825Skanvrp_var_may_overflow (tree var, tree stmt) 2609171825Skan{ 2610171825Skan struct loop *l; 2611171825Skan tree chrec, init, step; 2612171825Skan 2613171825Skan if (current_loops == NULL) 2614171825Skan return true; 2615171825Skan 2616171825Skan l = loop_containing_stmt (stmt); 2617171825Skan if (l == NULL) 2618171825Skan return true; 2619171825Skan 2620171825Skan chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var)); 2621171825Skan if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2622171825Skan return true; 2623171825Skan 2624171825Skan init = initial_condition_in_loop_num (chrec, l->num); 2625171825Skan step = evolution_part_in_loop_num (chrec, l->num); 2626171825Skan 2627171825Skan if (step == NULL_TREE 2628171825Skan || !is_gimple_min_invariant (step) 2629171825Skan || !valid_value_p (init)) 2630171825Skan return true; 2631171825Skan 2632171825Skan /* If we get here, we know something useful about VAR based on the 2633171825Skan loop information. If it wraps, it may overflow. */ 2634171825Skan 2635171825Skan if (scev_probably_wraps_p (init, step, stmt, 2636171825Skan current_loops->parray[CHREC_VARIABLE (chrec)], 2637171825Skan true)) 2638171825Skan return true; 2639171825Skan 2640171825Skan if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2641171825Skan { 2642171825Skan print_generic_expr (dump_file, var, 0); 2643171825Skan fprintf (dump_file, ": loop information indicates does not overflow\n"); 2644171825Skan } 2645171825Skan 2646171825Skan return false; 2647171825Skan} 2648171825Skan 2649171825Skan 2650169689Skan/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 2651169689Skan 2652169689Skan - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 2653169689Skan all the values in the ranges. 2654169689Skan 2655169689Skan - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 2656169689Skan 2657169689Skan - Return NULL_TREE if it is not always possible to determine the 2658169689Skan value of the comparison. 2659169689Skan 2660169689Skan Also set *STRICT_OVERFLOW_P to indicate whether a range with an 2661169689Skan overflow infinity was used in the test. */ 2662169689Skan 2663169689Skan 2664169689Skanstatic tree 2665169689Skancompare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, 2666169689Skan bool *strict_overflow_p) 2667169689Skan{ 2668169689Skan /* VARYING or UNDEFINED ranges cannot be compared. */ 2669169689Skan if (vr0->type == VR_VARYING 2670169689Skan || vr0->type == VR_UNDEFINED 2671169689Skan || vr1->type == VR_VARYING 2672169689Skan || vr1->type == VR_UNDEFINED) 2673169689Skan return NULL_TREE; 2674169689Skan 2675169689Skan /* Anti-ranges need to be handled separately. */ 2676169689Skan if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 2677169689Skan { 2678169689Skan /* If both are anti-ranges, then we cannot compute any 2679169689Skan comparison. */ 2680169689Skan if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 2681169689Skan return NULL_TREE; 2682169689Skan 2683169689Skan /* These comparisons are never statically computable. */ 2684169689Skan if (comp == GT_EXPR 2685169689Skan || comp == GE_EXPR 2686169689Skan || comp == LT_EXPR 2687169689Skan || comp == LE_EXPR) 2688169689Skan return NULL_TREE; 2689169689Skan 2690169689Skan /* Equality can be computed only between a range and an 2691169689Skan anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 2692169689Skan if (vr0->type == VR_RANGE) 2693169689Skan { 2694169689Skan /* To simplify processing, make VR0 the anti-range. */ 2695169689Skan value_range_t *tmp = vr0; 2696169689Skan vr0 = vr1; 2697169689Skan vr1 = tmp; 2698169689Skan } 2699169689Skan 2700169689Skan gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 2701169689Skan 2702169689Skan if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0 2703169689Skan && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0) 2704169689Skan return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2705169689Skan 2706169689Skan return NULL_TREE; 2707169689Skan } 2708169689Skan 2709169689Skan if (!usable_range_p (vr0, strict_overflow_p) 2710169689Skan || !usable_range_p (vr1, strict_overflow_p)) 2711169689Skan return NULL_TREE; 2712169689Skan 2713169689Skan /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 2714169689Skan operands around and change the comparison code. */ 2715169689Skan if (comp == GT_EXPR || comp == GE_EXPR) 2716169689Skan { 2717169689Skan value_range_t *tmp; 2718169689Skan comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 2719169689Skan tmp = vr0; 2720169689Skan vr0 = vr1; 2721169689Skan vr1 = tmp; 2722169689Skan } 2723169689Skan 2724169689Skan if (comp == EQ_EXPR) 2725169689Skan { 2726169689Skan /* Equality may only be computed if both ranges represent 2727169689Skan exactly one value. */ 2728169689Skan if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0 2729169689Skan && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0) 2730169689Skan { 2731169689Skan int cmp_min = compare_values_warnv (vr0->min, vr1->min, 2732169689Skan strict_overflow_p); 2733169689Skan int cmp_max = compare_values_warnv (vr0->max, vr1->max, 2734169689Skan strict_overflow_p); 2735169689Skan if (cmp_min == 0 && cmp_max == 0) 2736169689Skan return boolean_true_node; 2737169689Skan else if (cmp_min != -2 && cmp_max != -2) 2738169689Skan return boolean_false_node; 2739169689Skan } 2740169689Skan /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ 2741169689Skan else if (compare_values_warnv (vr0->min, vr1->max, 2742169689Skan strict_overflow_p) == 1 2743169689Skan || compare_values_warnv (vr1->min, vr0->max, 2744169689Skan strict_overflow_p) == 1) 2745169689Skan return boolean_false_node; 2746169689Skan 2747169689Skan return NULL_TREE; 2748169689Skan } 2749169689Skan else if (comp == NE_EXPR) 2750169689Skan { 2751169689Skan int cmp1, cmp2; 2752169689Skan 2753169689Skan /* If VR0 is completely to the left or completely to the right 2754169689Skan of VR1, they are always different. Notice that we need to 2755169689Skan make sure that both comparisons yield similar results to 2756169689Skan avoid comparing values that cannot be compared at 2757169689Skan compile-time. */ 2758169689Skan cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2759169689Skan cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2760169689Skan if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 2761169689Skan return boolean_true_node; 2762169689Skan 2763169689Skan /* If VR0 and VR1 represent a single value and are identical, 2764169689Skan return false. */ 2765169689Skan else if (compare_values_warnv (vr0->min, vr0->max, 2766169689Skan strict_overflow_p) == 0 2767169689Skan && compare_values_warnv (vr1->min, vr1->max, 2768169689Skan strict_overflow_p) == 0 2769169689Skan && compare_values_warnv (vr0->min, vr1->min, 2770169689Skan strict_overflow_p) == 0 2771169689Skan && compare_values_warnv (vr0->max, vr1->max, 2772169689Skan strict_overflow_p) == 0) 2773169689Skan return boolean_false_node; 2774169689Skan 2775169689Skan /* Otherwise, they may or may not be different. */ 2776169689Skan else 2777169689Skan return NULL_TREE; 2778169689Skan } 2779169689Skan else if (comp == LT_EXPR || comp == LE_EXPR) 2780169689Skan { 2781169689Skan int tst; 2782169689Skan 2783169689Skan /* If VR0 is to the left of VR1, return true. */ 2784169689Skan tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2785169689Skan if ((comp == LT_EXPR && tst == -1) 2786169689Skan || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2787169689Skan { 2788169689Skan if (overflow_infinity_range_p (vr0) 2789169689Skan || overflow_infinity_range_p (vr1)) 2790169689Skan *strict_overflow_p = true; 2791169689Skan return boolean_true_node; 2792169689Skan } 2793169689Skan 2794169689Skan /* If VR0 is to the right of VR1, return false. */ 2795169689Skan tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2796169689Skan if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2797169689Skan || (comp == LE_EXPR && tst == 1)) 2798169689Skan { 2799169689Skan if (overflow_infinity_range_p (vr0) 2800169689Skan || overflow_infinity_range_p (vr1)) 2801169689Skan *strict_overflow_p = true; 2802169689Skan return boolean_false_node; 2803169689Skan } 2804169689Skan 2805169689Skan /* Otherwise, we don't know. */ 2806169689Skan return NULL_TREE; 2807169689Skan } 2808169689Skan 2809169689Skan gcc_unreachable (); 2810169689Skan} 2811169689Skan 2812169689Skan 2813169689Skan/* Given a value range VR, a value VAL and a comparison code COMP, return 2814169689Skan BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 2815169689Skan values in VR. Return BOOLEAN_FALSE_NODE if the comparison 2816169689Skan always returns false. Return NULL_TREE if it is not always 2817169689Skan possible to determine the value of the comparison. Also set 2818169689Skan *STRICT_OVERFLOW_P to indicate whether a range with an overflow 2819169689Skan infinity was used in the test. */ 2820169689Skan 2821169689Skanstatic tree 2822169689Skancompare_range_with_value (enum tree_code comp, value_range_t *vr, tree val, 2823169689Skan bool *strict_overflow_p) 2824169689Skan{ 2825169689Skan if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2826169689Skan return NULL_TREE; 2827169689Skan 2828169689Skan /* Anti-ranges need to be handled separately. */ 2829169689Skan if (vr->type == VR_ANTI_RANGE) 2830169689Skan { 2831169689Skan /* For anti-ranges, the only predicates that we can compute at 2832169689Skan compile time are equality and inequality. */ 2833169689Skan if (comp == GT_EXPR 2834169689Skan || comp == GE_EXPR 2835169689Skan || comp == LT_EXPR 2836169689Skan || comp == LE_EXPR) 2837169689Skan return NULL_TREE; 2838169689Skan 2839169689Skan /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 2840169689Skan if (value_inside_range (val, vr) == 1) 2841169689Skan return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2842169689Skan 2843169689Skan return NULL_TREE; 2844169689Skan } 2845169689Skan 2846169689Skan if (!usable_range_p (vr, strict_overflow_p)) 2847169689Skan return NULL_TREE; 2848169689Skan 2849169689Skan if (comp == EQ_EXPR) 2850169689Skan { 2851169689Skan /* EQ_EXPR may only be computed if VR represents exactly 2852169689Skan one value. */ 2853169689Skan if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0) 2854169689Skan { 2855169689Skan int cmp = compare_values_warnv (vr->min, val, strict_overflow_p); 2856169689Skan if (cmp == 0) 2857169689Skan return boolean_true_node; 2858169689Skan else if (cmp == -1 || cmp == 1 || cmp == 2) 2859169689Skan return boolean_false_node; 2860169689Skan } 2861169689Skan else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1 2862169689Skan || compare_values_warnv (vr->max, val, strict_overflow_p) == -1) 2863169689Skan return boolean_false_node; 2864169689Skan 2865169689Skan return NULL_TREE; 2866169689Skan } 2867169689Skan else if (comp == NE_EXPR) 2868169689Skan { 2869169689Skan /* If VAL is not inside VR, then they are always different. */ 2870169689Skan if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1 2871169689Skan || compare_values_warnv (vr->min, val, strict_overflow_p) == 1) 2872169689Skan return boolean_true_node; 2873169689Skan 2874169689Skan /* If VR represents exactly one value equal to VAL, then return 2875169689Skan false. */ 2876169689Skan if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0 2877169689Skan && compare_values_warnv (vr->min, val, strict_overflow_p) == 0) 2878169689Skan return boolean_false_node; 2879169689Skan 2880169689Skan /* Otherwise, they may or may not be different. */ 2881169689Skan return NULL_TREE; 2882169689Skan } 2883169689Skan else if (comp == LT_EXPR || comp == LE_EXPR) 2884169689Skan { 2885169689Skan int tst; 2886169689Skan 2887169689Skan /* If VR is to the left of VAL, return true. */ 2888169689Skan tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2889169689Skan if ((comp == LT_EXPR && tst == -1) 2890169689Skan || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2891169689Skan { 2892169689Skan if (overflow_infinity_range_p (vr)) 2893169689Skan *strict_overflow_p = true; 2894169689Skan return boolean_true_node; 2895169689Skan } 2896169689Skan 2897169689Skan /* If VR is to the right of VAL, return false. */ 2898169689Skan tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2899169689Skan if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2900169689Skan || (comp == LE_EXPR && tst == 1)) 2901169689Skan { 2902169689Skan if (overflow_infinity_range_p (vr)) 2903169689Skan *strict_overflow_p = true; 2904169689Skan return boolean_false_node; 2905169689Skan } 2906169689Skan 2907169689Skan /* Otherwise, we don't know. */ 2908169689Skan return NULL_TREE; 2909169689Skan } 2910169689Skan else if (comp == GT_EXPR || comp == GE_EXPR) 2911169689Skan { 2912169689Skan int tst; 2913169689Skan 2914169689Skan /* If VR is to the right of VAL, return true. */ 2915169689Skan tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2916169689Skan if ((comp == GT_EXPR && tst == 1) 2917169689Skan || (comp == GE_EXPR && (tst == 0 || tst == 1))) 2918169689Skan { 2919169689Skan if (overflow_infinity_range_p (vr)) 2920169689Skan *strict_overflow_p = true; 2921169689Skan return boolean_true_node; 2922169689Skan } 2923169689Skan 2924169689Skan /* If VR is to the left of VAL, return false. */ 2925169689Skan tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2926169689Skan if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 2927169689Skan || (comp == GE_EXPR && tst == -1)) 2928169689Skan { 2929169689Skan if (overflow_infinity_range_p (vr)) 2930169689Skan *strict_overflow_p = true; 2931169689Skan return boolean_false_node; 2932169689Skan } 2933169689Skan 2934169689Skan /* Otherwise, we don't know. */ 2935169689Skan return NULL_TREE; 2936169689Skan } 2937169689Skan 2938169689Skan gcc_unreachable (); 2939169689Skan} 2940169689Skan 2941169689Skan 2942169689Skan/* Debugging dumps. */ 2943169689Skan 2944169689Skanvoid dump_value_range (FILE *, value_range_t *); 2945169689Skanvoid debug_value_range (value_range_t *); 2946169689Skanvoid dump_all_value_ranges (FILE *); 2947169689Skanvoid debug_all_value_ranges (void); 2948169689Skanvoid dump_vr_equiv (FILE *, bitmap); 2949169689Skanvoid debug_vr_equiv (bitmap); 2950169689Skan 2951169689Skan 2952169689Skan/* Dump value range VR to FILE. */ 2953169689Skan 2954169689Skanvoid 2955169689Skandump_value_range (FILE *file, value_range_t *vr) 2956169689Skan{ 2957169689Skan if (vr == NULL) 2958169689Skan fprintf (file, "[]"); 2959169689Skan else if (vr->type == VR_UNDEFINED) 2960169689Skan fprintf (file, "UNDEFINED"); 2961169689Skan else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 2962169689Skan { 2963169689Skan tree type = TREE_TYPE (vr->min); 2964169689Skan 2965169689Skan fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 2966169689Skan 2967169689Skan if (is_negative_overflow_infinity (vr->min)) 2968169689Skan fprintf (file, "-INF(OVF)"); 2969169689Skan else if (INTEGRAL_TYPE_P (type) 2970169689Skan && !TYPE_UNSIGNED (type) 2971169689Skan && vrp_val_is_min (vr->min)) 2972169689Skan fprintf (file, "-INF"); 2973169689Skan else 2974169689Skan print_generic_expr (file, vr->min, 0); 2975169689Skan 2976169689Skan fprintf (file, ", "); 2977169689Skan 2978169689Skan if (is_positive_overflow_infinity (vr->max)) 2979169689Skan fprintf (file, "+INF(OVF)"); 2980169689Skan else if (INTEGRAL_TYPE_P (type) 2981169689Skan && vrp_val_is_max (vr->max)) 2982169689Skan fprintf (file, "+INF"); 2983169689Skan else 2984169689Skan print_generic_expr (file, vr->max, 0); 2985169689Skan 2986169689Skan fprintf (file, "]"); 2987169689Skan 2988169689Skan if (vr->equiv) 2989169689Skan { 2990169689Skan bitmap_iterator bi; 2991169689Skan unsigned i, c = 0; 2992169689Skan 2993169689Skan fprintf (file, " EQUIVALENCES: { "); 2994169689Skan 2995169689Skan EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 2996169689Skan { 2997169689Skan print_generic_expr (file, ssa_name (i), 0); 2998169689Skan fprintf (file, " "); 2999169689Skan c++; 3000169689Skan } 3001169689Skan 3002169689Skan fprintf (file, "} (%u elements)", c); 3003169689Skan } 3004169689Skan } 3005169689Skan else if (vr->type == VR_VARYING) 3006169689Skan fprintf (file, "VARYING"); 3007169689Skan else 3008169689Skan fprintf (file, "INVALID RANGE"); 3009169689Skan} 3010169689Skan 3011169689Skan 3012169689Skan/* Dump value range VR to stderr. */ 3013169689Skan 3014169689Skanvoid 3015169689Skandebug_value_range (value_range_t *vr) 3016169689Skan{ 3017169689Skan dump_value_range (stderr, vr); 3018169689Skan fprintf (stderr, "\n"); 3019169689Skan} 3020169689Skan 3021169689Skan 3022169689Skan/* Dump value ranges of all SSA_NAMEs to FILE. */ 3023169689Skan 3024169689Skanvoid 3025169689Skandump_all_value_ranges (FILE *file) 3026169689Skan{ 3027169689Skan size_t i; 3028169689Skan 3029169689Skan for (i = 0; i < num_ssa_names; i++) 3030169689Skan { 3031169689Skan if (vr_value[i]) 3032169689Skan { 3033169689Skan print_generic_expr (file, ssa_name (i), 0); 3034169689Skan fprintf (file, ": "); 3035169689Skan dump_value_range (file, vr_value[i]); 3036169689Skan fprintf (file, "\n"); 3037169689Skan } 3038169689Skan } 3039169689Skan 3040169689Skan fprintf (file, "\n"); 3041169689Skan} 3042169689Skan 3043169689Skan 3044169689Skan/* Dump all value ranges to stderr. */ 3045169689Skan 3046169689Skanvoid 3047169689Skandebug_all_value_ranges (void) 3048169689Skan{ 3049169689Skan dump_all_value_ranges (stderr); 3050169689Skan} 3051169689Skan 3052169689Skan 3053169689Skan/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 3054169689Skan create a new SSA name N and return the assertion assignment 3055169689Skan 'V = ASSERT_EXPR <V, V OP W>'. */ 3056169689Skan 3057169689Skanstatic tree 3058169689Skanbuild_assert_expr_for (tree cond, tree v) 3059169689Skan{ 3060169689Skan tree n, assertion; 3061169689Skan 3062169689Skan gcc_assert (TREE_CODE (v) == SSA_NAME); 3063169689Skan n = duplicate_ssa_name (v, NULL_TREE); 3064169689Skan 3065169689Skan if (COMPARISON_CLASS_P (cond)) 3066169689Skan { 3067169689Skan tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 3068169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a); 3069169689Skan } 3070169689Skan else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 3071169689Skan { 3072169689Skan /* Given !V, build the assignment N = false. */ 3073169689Skan tree op0 = TREE_OPERAND (cond, 0); 3074169689Skan gcc_assert (op0 == v); 3075169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node); 3076169689Skan } 3077169689Skan else if (TREE_CODE (cond) == SSA_NAME) 3078169689Skan { 3079169689Skan /* Given V, build the assignment N = true. */ 3080169689Skan gcc_assert (v == cond); 3081169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); 3082169689Skan } 3083169689Skan else 3084169689Skan gcc_unreachable (); 3085169689Skan 3086169689Skan SSA_NAME_DEF_STMT (n) = assertion; 3087169689Skan 3088169689Skan /* The new ASSERT_EXPR, creates a new SSA name that replaces the 3089169689Skan operand of the ASSERT_EXPR. Register the new name and the old one 3090169689Skan in the replacement table so that we can fix the SSA web after 3091169689Skan adding all the ASSERT_EXPRs. */ 3092169689Skan register_new_name_mapping (n, v); 3093169689Skan 3094169689Skan return assertion; 3095169689Skan} 3096169689Skan 3097169689Skan 3098169689Skan/* Return false if EXPR is a predicate expression involving floating 3099169689Skan point values. */ 3100169689Skan 3101169689Skanstatic inline bool 3102169689Skanfp_predicate (tree expr) 3103169689Skan{ 3104169689Skan return (COMPARISON_CLASS_P (expr) 3105169689Skan && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); 3106169689Skan} 3107169689Skan 3108169689Skan 3109169689Skan/* If the range of values taken by OP can be inferred after STMT executes, 3110169689Skan return the comparison code (COMP_CODE_P) and value (VAL_P) that 3111169689Skan describes the inferred range. Return true if a range could be 3112169689Skan inferred. */ 3113169689Skan 3114169689Skanstatic bool 3115169689Skaninfer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) 3116169689Skan{ 3117169689Skan *val_p = NULL_TREE; 3118169689Skan *comp_code_p = ERROR_MARK; 3119169689Skan 3120169689Skan /* Do not attempt to infer anything in names that flow through 3121169689Skan abnormal edges. */ 3122169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 3123169689Skan return false; 3124169689Skan 3125169689Skan /* Similarly, don't infer anything from statements that may throw 3126169689Skan exceptions. */ 3127169689Skan if (tree_could_throw_p (stmt)) 3128169689Skan return false; 3129169689Skan 3130169689Skan /* If STMT is the last statement of a basic block with no 3131169689Skan successors, there is no point inferring anything about any of its 3132169689Skan operands. We would not be able to find a proper insertion point 3133169689Skan for the assertion, anyway. */ 3134169689Skan if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) 3135169689Skan return false; 3136169689Skan 3137169689Skan /* We can only assume that a pointer dereference will yield 3138169689Skan non-NULL if -fdelete-null-pointer-checks is enabled. */ 3139169689Skan if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op))) 3140169689Skan { 3141169689Skan bool is_store; 3142169689Skan unsigned num_uses, num_derefs; 3143169689Skan 3144169689Skan count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 3145169689Skan if (num_derefs > 0) 3146169689Skan { 3147169689Skan *val_p = build_int_cst (TREE_TYPE (op), 0); 3148169689Skan *comp_code_p = NE_EXPR; 3149169689Skan return true; 3150169689Skan } 3151169689Skan } 3152169689Skan 3153169689Skan return false; 3154169689Skan} 3155169689Skan 3156169689Skan 3157169689Skanvoid dump_asserts_for (FILE *, tree); 3158169689Skanvoid debug_asserts_for (tree); 3159169689Skanvoid dump_all_asserts (FILE *); 3160169689Skanvoid debug_all_asserts (void); 3161169689Skan 3162169689Skan/* Dump all the registered assertions for NAME to FILE. */ 3163169689Skan 3164169689Skanvoid 3165169689Skandump_asserts_for (FILE *file, tree name) 3166169689Skan{ 3167169689Skan assert_locus_t loc; 3168169689Skan 3169169689Skan fprintf (file, "Assertions to be inserted for "); 3170169689Skan print_generic_expr (file, name, 0); 3171169689Skan fprintf (file, "\n"); 3172169689Skan 3173169689Skan loc = asserts_for[SSA_NAME_VERSION (name)]; 3174169689Skan while (loc) 3175169689Skan { 3176169689Skan fprintf (file, "\t"); 3177169689Skan print_generic_expr (file, bsi_stmt (loc->si), 0); 3178169689Skan fprintf (file, "\n\tBB #%d", loc->bb->index); 3179169689Skan if (loc->e) 3180169689Skan { 3181169689Skan fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 3182169689Skan loc->e->dest->index); 3183169689Skan dump_edge_info (file, loc->e, 0); 3184169689Skan } 3185169689Skan fprintf (file, "\n\tPREDICATE: "); 3186169689Skan print_generic_expr (file, name, 0); 3187169689Skan fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]); 3188169689Skan print_generic_expr (file, loc->val, 0); 3189169689Skan fprintf (file, "\n\n"); 3190169689Skan loc = loc->next; 3191169689Skan } 3192169689Skan 3193169689Skan fprintf (file, "\n"); 3194169689Skan} 3195169689Skan 3196169689Skan 3197169689Skan/* Dump all the registered assertions for NAME to stderr. */ 3198169689Skan 3199169689Skanvoid 3200169689Skandebug_asserts_for (tree name) 3201169689Skan{ 3202169689Skan dump_asserts_for (stderr, name); 3203169689Skan} 3204169689Skan 3205169689Skan 3206169689Skan/* Dump all the registered assertions for all the names to FILE. */ 3207169689Skan 3208169689Skanvoid 3209169689Skandump_all_asserts (FILE *file) 3210169689Skan{ 3211169689Skan unsigned i; 3212169689Skan bitmap_iterator bi; 3213169689Skan 3214169689Skan fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 3215169689Skan EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3216169689Skan dump_asserts_for (file, ssa_name (i)); 3217169689Skan fprintf (file, "\n"); 3218169689Skan} 3219169689Skan 3220169689Skan 3221169689Skan/* Dump all the registered assertions for all the names to stderr. */ 3222169689Skan 3223169689Skanvoid 3224169689Skandebug_all_asserts (void) 3225169689Skan{ 3226169689Skan dump_all_asserts (stderr); 3227169689Skan} 3228169689Skan 3229169689Skan 3230169689Skan/* If NAME doesn't have an ASSERT_EXPR registered for asserting 3231169689Skan 'NAME COMP_CODE VAL' at a location that dominates block BB or 3232169689Skan E->DEST, then register this location as a possible insertion point 3233169689Skan for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. 3234169689Skan 3235169689Skan BB, E and SI provide the exact insertion point for the new 3236169689Skan ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 3237169689Skan on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 3238169689Skan BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 3239169689Skan must not be NULL. */ 3240169689Skan 3241169689Skanstatic void 3242169689Skanregister_new_assert_for (tree name, 3243169689Skan enum tree_code comp_code, 3244169689Skan tree val, 3245169689Skan basic_block bb, 3246169689Skan edge e, 3247169689Skan block_stmt_iterator si) 3248169689Skan{ 3249169689Skan assert_locus_t n, loc, last_loc; 3250169689Skan bool found; 3251169689Skan basic_block dest_bb; 3252169689Skan 3253169689Skan#if defined ENABLE_CHECKING 3254169689Skan gcc_assert (bb == NULL || e == NULL); 3255169689Skan 3256169689Skan if (e == NULL) 3257169689Skan gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR 3258169689Skan && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR); 3259169689Skan#endif 3260169689Skan 3261169689Skan /* The new assertion A will be inserted at BB or E. We need to 3262169689Skan determine if the new location is dominated by a previously 3263169689Skan registered location for A. If we are doing an edge insertion, 3264169689Skan assume that A will be inserted at E->DEST. Note that this is not 3265169689Skan necessarily true. 3266169689Skan 3267169689Skan If E is a critical edge, it will be split. But even if E is 3268169689Skan split, the new block will dominate the same set of blocks that 3269169689Skan E->DEST dominates. 3270169689Skan 3271169689Skan The reverse, however, is not true, blocks dominated by E->DEST 3272169689Skan will not be dominated by the new block created to split E. So, 3273169689Skan if the insertion location is on a critical edge, we will not use 3274169689Skan the new location to move another assertion previously registered 3275169689Skan at a block dominated by E->DEST. */ 3276169689Skan dest_bb = (bb) ? bb : e->dest; 3277169689Skan 3278169689Skan /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 3279169689Skan VAL at a block dominating DEST_BB, then we don't need to insert a new 3280169689Skan one. Similarly, if the same assertion already exists at a block 3281169689Skan dominated by DEST_BB and the new location is not on a critical 3282169689Skan edge, then update the existing location for the assertion (i.e., 3283169689Skan move the assertion up in the dominance tree). 3284169689Skan 3285169689Skan Note, this is implemented as a simple linked list because there 3286169689Skan should not be more than a handful of assertions registered per 3287169689Skan name. If this becomes a performance problem, a table hashed by 3288169689Skan COMP_CODE and VAL could be implemented. */ 3289169689Skan loc = asserts_for[SSA_NAME_VERSION (name)]; 3290169689Skan last_loc = loc; 3291169689Skan found = false; 3292169689Skan while (loc) 3293169689Skan { 3294169689Skan if (loc->comp_code == comp_code 3295169689Skan && (loc->val == val 3296169689Skan || operand_equal_p (loc->val, val, 0))) 3297169689Skan { 3298169689Skan /* If the assertion NAME COMP_CODE VAL has already been 3299169689Skan registered at a basic block that dominates DEST_BB, then 3300169689Skan we don't need to insert the same assertion again. Note 3301169689Skan that we don't check strict dominance here to avoid 3302169689Skan replicating the same assertion inside the same basic 3303169689Skan block more than once (e.g., when a pointer is 3304169689Skan dereferenced several times inside a block). 3305169689Skan 3306169689Skan An exception to this rule are edge insertions. If the 3307169689Skan new assertion is to be inserted on edge E, then it will 3308169689Skan dominate all the other insertions that we may want to 3309169689Skan insert in DEST_BB. So, if we are doing an edge 3310169689Skan insertion, don't do this dominance check. */ 3311169689Skan if (e == NULL 3312169689Skan && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) 3313169689Skan return; 3314169689Skan 3315169689Skan /* Otherwise, if E is not a critical edge and DEST_BB 3316169689Skan dominates the existing location for the assertion, move 3317169689Skan the assertion up in the dominance tree by updating its 3318169689Skan location information. */ 3319169689Skan if ((e == NULL || !EDGE_CRITICAL_P (e)) 3320169689Skan && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 3321169689Skan { 3322169689Skan loc->bb = dest_bb; 3323169689Skan loc->e = e; 3324169689Skan loc->si = si; 3325169689Skan return; 3326169689Skan } 3327169689Skan } 3328169689Skan 3329169689Skan /* Update the last node of the list and move to the next one. */ 3330169689Skan last_loc = loc; 3331169689Skan loc = loc->next; 3332169689Skan } 3333169689Skan 3334169689Skan /* If we didn't find an assertion already registered for 3335169689Skan NAME COMP_CODE VAL, add a new one at the end of the list of 3336169689Skan assertions associated with NAME. */ 3337169689Skan n = XNEW (struct assert_locus_d); 3338169689Skan n->bb = dest_bb; 3339169689Skan n->e = e; 3340169689Skan n->si = si; 3341169689Skan n->comp_code = comp_code; 3342169689Skan n->val = val; 3343169689Skan n->next = NULL; 3344169689Skan 3345169689Skan if (last_loc) 3346169689Skan last_loc->next = n; 3347169689Skan else 3348169689Skan asserts_for[SSA_NAME_VERSION (name)] = n; 3349169689Skan 3350169689Skan bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 3351169689Skan} 3352169689Skan 3353169689Skan 3354169689Skan/* Try to register an edge assertion for SSA name NAME on edge E for 3355169689Skan the conditional jump pointed to by SI. Return true if an assertion 3356169689Skan for NAME could be registered. */ 3357169689Skan 3358169689Skanstatic bool 3359169689Skanregister_edge_assert_for (tree name, edge e, block_stmt_iterator si) 3360169689Skan{ 3361169689Skan tree val, stmt; 3362169689Skan enum tree_code comp_code; 3363169689Skan 3364169689Skan stmt = bsi_stmt (si); 3365169689Skan 3366169689Skan /* Do not attempt to infer anything in names that flow through 3367169689Skan abnormal edges. */ 3368169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 3369169689Skan return false; 3370169689Skan 3371169689Skan /* If NAME was not found in the sub-graph reachable from E, then 3372169689Skan there's nothing to do. */ 3373169689Skan if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) 3374169689Skan return false; 3375169689Skan 3376169689Skan /* We found a use of NAME in the sub-graph rooted at E->DEST. 3377169689Skan Register an assertion for NAME according to the value that NAME 3378169689Skan takes on edge E. */ 3379169689Skan if (TREE_CODE (stmt) == COND_EXPR) 3380169689Skan { 3381169689Skan /* If BB ends in a COND_EXPR then NAME then we should insert 3382169689Skan the original predicate on EDGE_TRUE_VALUE and the 3383169689Skan opposite predicate on EDGE_FALSE_VALUE. */ 3384169689Skan tree cond = COND_EXPR_COND (stmt); 3385169689Skan bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 3386169689Skan 3387169689Skan /* Predicates may be a single SSA name or NAME OP VAL. */ 3388169689Skan if (cond == name) 3389169689Skan { 3390169689Skan /* If the predicate is a name, it must be NAME, in which 3391169689Skan case we create the predicate NAME == true or 3392169689Skan NAME == false accordingly. */ 3393169689Skan comp_code = EQ_EXPR; 3394169689Skan val = (is_else_edge) ? boolean_false_node : boolean_true_node; 3395169689Skan } 3396169689Skan else 3397169689Skan { 3398169689Skan /* Otherwise, we have a comparison of the form NAME COMP VAL 3399169689Skan or VAL COMP NAME. */ 3400169689Skan if (name == TREE_OPERAND (cond, 1)) 3401169689Skan { 3402169689Skan /* If the predicate is of the form VAL COMP NAME, flip 3403169689Skan COMP around because we need to register NAME as the 3404169689Skan first operand in the predicate. */ 3405169689Skan comp_code = swap_tree_comparison (TREE_CODE (cond)); 3406169689Skan val = TREE_OPERAND (cond, 0); 3407169689Skan } 3408169689Skan else 3409169689Skan { 3410169689Skan /* The comparison is of the form NAME COMP VAL, so the 3411169689Skan comparison code remains unchanged. */ 3412169689Skan comp_code = TREE_CODE (cond); 3413169689Skan val = TREE_OPERAND (cond, 1); 3414169689Skan } 3415169689Skan 3416169689Skan /* If we are inserting the assertion on the ELSE edge, we 3417169689Skan need to invert the sign comparison. */ 3418169689Skan if (is_else_edge) 3419169689Skan comp_code = invert_tree_comparison (comp_code, 0); 3420169689Skan 3421169689Skan /* Do not register always-false predicates. FIXME, this 3422169689Skan works around a limitation in fold() when dealing with 3423169689Skan enumerations. Given 'enum { N1, N2 } x;', fold will not 3424169689Skan fold 'if (x > N2)' to 'if (0)'. */ 3425169689Skan if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 3426169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (val)) 3427169689Skan || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))) 3428169689Skan { 3429169689Skan tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 3430169689Skan tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 3431169689Skan 3432169689Skan if (comp_code == GT_EXPR && compare_values (val, max) == 0) 3433169689Skan return false; 3434169689Skan 3435169689Skan if (comp_code == LT_EXPR && compare_values (val, min) == 0) 3436169689Skan return false; 3437169689Skan } 3438169689Skan } 3439169689Skan } 3440169689Skan else 3441169689Skan { 3442169689Skan /* FIXME. Handle SWITCH_EXPR. */ 3443169689Skan gcc_unreachable (); 3444169689Skan } 3445169689Skan 3446169689Skan register_new_assert_for (name, comp_code, val, NULL, e, si); 3447169689Skan return true; 3448169689Skan} 3449169689Skan 3450169689Skan 3451169689Skanstatic bool find_assert_locations (basic_block bb); 3452169689Skan 3453169689Skan/* Determine whether the outgoing edges of BB should receive an 3454169689Skan ASSERT_EXPR for each of the operands of BB's last statement. The 3455169689Skan last statement of BB must be a COND_EXPR or a SWITCH_EXPR. 3456169689Skan 3457169689Skan If any of the sub-graphs rooted at BB have an interesting use of 3458169689Skan the predicate operands, an assert location node is added to the 3459169689Skan list of assertions for the corresponding operands. */ 3460169689Skan 3461169689Skanstatic bool 3462169689Skanfind_conditional_asserts (basic_block bb) 3463169689Skan{ 3464169689Skan bool need_assert; 3465169689Skan block_stmt_iterator last_si; 3466169689Skan tree op, last; 3467169689Skan edge_iterator ei; 3468169689Skan edge e; 3469169689Skan ssa_op_iter iter; 3470169689Skan 3471169689Skan need_assert = false; 3472169689Skan last_si = bsi_last (bb); 3473169689Skan last = bsi_stmt (last_si); 3474169689Skan 3475169689Skan /* Look for uses of the operands in each of the sub-graphs 3476169689Skan rooted at BB. We need to check each of the outgoing edges 3477169689Skan separately, so that we know what kind of ASSERT_EXPR to 3478169689Skan insert. */ 3479169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 3480169689Skan { 3481169689Skan if (e->dest == bb) 3482169689Skan continue; 3483169689Skan 3484169689Skan /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. 3485169689Skan Otherwise, when we finish traversing each of the sub-graphs, we 3486169689Skan won't know whether the variables were found in the sub-graphs or 3487169689Skan if they had been found in a block upstream from BB. 3488169689Skan 3489169689Skan This is actually a bad idea is some cases, particularly jump 3490169689Skan threading. Consider a CFG like the following: 3491169689Skan 3492169689Skan 0 3493169689Skan /| 3494169689Skan 1 | 3495169689Skan \| 3496169689Skan 2 3497169689Skan / \ 3498169689Skan 3 4 3499169689Skan 3500169689Skan Assume that one or more operands in the conditional at the 3501169689Skan end of block 0 are used in a conditional in block 2, but not 3502169689Skan anywhere in block 1. In this case we will not insert any 3503169689Skan assert statements in block 1, which may cause us to miss 3504169689Skan opportunities to optimize, particularly for jump threading. */ 3505169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3506169689Skan RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3507169689Skan 3508169689Skan /* Traverse the strictly dominated sub-graph rooted at E->DEST 3509169689Skan to determine if any of the operands in the conditional 3510169689Skan predicate are used. */ 3511169689Skan if (e->dest != bb) 3512169689Skan need_assert |= find_assert_locations (e->dest); 3513169689Skan 3514169689Skan /* Register the necessary assertions for each operand in the 3515169689Skan conditional predicate. */ 3516169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3517169689Skan need_assert |= register_edge_assert_for (op, e, last_si); 3518169689Skan } 3519169689Skan 3520169689Skan /* Finally, indicate that we have found the operands in the 3521169689Skan conditional. */ 3522169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3523169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3524169689Skan 3525169689Skan return need_assert; 3526169689Skan} 3527169689Skan 3528169689Skan 3529169689Skan/* Traverse all the statements in block BB looking for statements that 3530169689Skan may generate useful assertions for the SSA names in their operand. 3531169689Skan If a statement produces a useful assertion A for name N_i, then the 3532169689Skan list of assertions already generated for N_i is scanned to 3533169689Skan determine if A is actually needed. 3534169689Skan 3535169689Skan If N_i already had the assertion A at a location dominating the 3536169689Skan current location, then nothing needs to be done. Otherwise, the 3537169689Skan new location for A is recorded instead. 3538169689Skan 3539169689Skan 1- For every statement S in BB, all the variables used by S are 3540169689Skan added to bitmap FOUND_IN_SUBGRAPH. 3541169689Skan 3542169689Skan 2- If statement S uses an operand N in a way that exposes a known 3543169689Skan value range for N, then if N was not already generated by an 3544169689Skan ASSERT_EXPR, create a new assert location for N. For instance, 3545169689Skan if N is a pointer and the statement dereferences it, we can 3546169689Skan assume that N is not NULL. 3547169689Skan 3548169689Skan 3- COND_EXPRs are a special case of #2. We can derive range 3549169689Skan information from the predicate but need to insert different 3550169689Skan ASSERT_EXPRs for each of the sub-graphs rooted at the 3551169689Skan conditional block. If the last statement of BB is a conditional 3552169689Skan expression of the form 'X op Y', then 3553169689Skan 3554169689Skan a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 3555169689Skan 3556169689Skan b) If the conditional is the only entry point to the sub-graph 3557169689Skan corresponding to the THEN_CLAUSE, recurse into it. On 3558169689Skan return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 3559169689Skan an ASSERT_EXPR is added for the corresponding variable. 3560169689Skan 3561169689Skan c) Repeat step (b) on the ELSE_CLAUSE. 3562169689Skan 3563169689Skan d) Mark X and Y in FOUND_IN_SUBGRAPH. 3564169689Skan 3565169689Skan For instance, 3566169689Skan 3567169689Skan if (a == 9) 3568169689Skan b = a; 3569169689Skan else 3570169689Skan b = c + 1; 3571169689Skan 3572169689Skan In this case, an assertion on the THEN clause is useful to 3573169689Skan determine that 'a' is always 9 on that edge. However, an assertion 3574169689Skan on the ELSE clause would be unnecessary. 3575169689Skan 3576169689Skan 4- If BB does not end in a conditional expression, then we recurse 3577169689Skan into BB's dominator children. 3578169689Skan 3579169689Skan At the end of the recursive traversal, every SSA name will have a 3580169689Skan list of locations where ASSERT_EXPRs should be added. When a new 3581169689Skan location for name N is found, it is registered by calling 3582169689Skan register_new_assert_for. That function keeps track of all the 3583169689Skan registered assertions to prevent adding unnecessary assertions. 3584169689Skan For instance, if a pointer P_4 is dereferenced more than once in a 3585169689Skan dominator tree, only the location dominating all the dereference of 3586169689Skan P_4 will receive an ASSERT_EXPR. 3587169689Skan 3588169689Skan If this function returns true, then it means that there are names 3589169689Skan for which we need to generate ASSERT_EXPRs. Those assertions are 3590169689Skan inserted by process_assert_insertions. 3591169689Skan 3592169689Skan TODO. Handle SWITCH_EXPR. */ 3593169689Skan 3594169689Skanstatic bool 3595169689Skanfind_assert_locations (basic_block bb) 3596169689Skan{ 3597169689Skan block_stmt_iterator si; 3598169689Skan tree last, phi; 3599169689Skan bool need_assert; 3600169689Skan basic_block son; 3601169689Skan 3602169689Skan if (TEST_BIT (blocks_visited, bb->index)) 3603169689Skan return false; 3604169689Skan 3605169689Skan SET_BIT (blocks_visited, bb->index); 3606169689Skan 3607169689Skan need_assert = false; 3608169689Skan 3609169689Skan /* Traverse all PHI nodes in BB marking used operands. */ 3610169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 3611169689Skan { 3612169689Skan use_operand_p arg_p; 3613169689Skan ssa_op_iter i; 3614169689Skan 3615169689Skan FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 3616169689Skan { 3617169689Skan tree arg = USE_FROM_PTR (arg_p); 3618169689Skan if (TREE_CODE (arg) == SSA_NAME) 3619169689Skan { 3620169689Skan gcc_assert (is_gimple_reg (PHI_RESULT (phi))); 3621169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg)); 3622169689Skan } 3623169689Skan } 3624169689Skan } 3625169689Skan 3626169689Skan /* Traverse all the statements in BB marking used names and looking 3627169689Skan for statements that may infer assertions for their used operands. */ 3628169689Skan last = NULL_TREE; 3629169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 3630169689Skan { 3631169689Skan tree stmt, op; 3632169689Skan ssa_op_iter i; 3633169689Skan 3634169689Skan stmt = bsi_stmt (si); 3635169689Skan 3636169689Skan /* See if we can derive an assertion for any of STMT's operands. */ 3637169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 3638169689Skan { 3639169689Skan tree value; 3640169689Skan enum tree_code comp_code; 3641169689Skan 3642169689Skan /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside 3643169689Skan the sub-graph of a conditional block, when we return from 3644169689Skan this recursive walk, our parent will use the 3645169689Skan FOUND_IN_SUBGRAPH bitset to determine if one of the 3646169689Skan operands it was looking for was present in the sub-graph. */ 3647169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3648169689Skan 3649169689Skan /* If OP is used in such a way that we can infer a value 3650169689Skan range for it, and we don't find a previous assertion for 3651169689Skan it, create a new assertion location node for OP. */ 3652169689Skan if (infer_value_range (stmt, op, &comp_code, &value)) 3653169689Skan { 3654169689Skan /* If we are able to infer a nonzero value range for OP, 3655169689Skan then walk backwards through the use-def chain to see if OP 3656169689Skan was set via a typecast. 3657169689Skan 3658169689Skan If so, then we can also infer a nonzero value range 3659169689Skan for the operand of the NOP_EXPR. */ 3660169689Skan if (comp_code == NE_EXPR && integer_zerop (value)) 3661169689Skan { 3662169689Skan tree t = op; 3663169689Skan tree def_stmt = SSA_NAME_DEF_STMT (t); 3664169689Skan 3665169689Skan while (TREE_CODE (def_stmt) == MODIFY_EXPR 3666169689Skan && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR 3667169689Skan && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME 3668169689Skan && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)))) 3669169689Skan { 3670169689Skan t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 3671169689Skan def_stmt = SSA_NAME_DEF_STMT (t); 3672169689Skan 3673169689Skan /* Note we want to register the assert for the 3674169689Skan operand of the NOP_EXPR after SI, not after the 3675169689Skan conversion. */ 3676169689Skan if (! has_single_use (t)) 3677169689Skan { 3678169689Skan register_new_assert_for (t, comp_code, value, 3679169689Skan bb, NULL, si); 3680169689Skan need_assert = true; 3681169689Skan } 3682169689Skan } 3683169689Skan } 3684169689Skan 3685169689Skan /* If OP is used only once, namely in this STMT, don't 3686169689Skan bother creating an ASSERT_EXPR for it. Such an 3687169689Skan ASSERT_EXPR would do nothing but increase compile time. */ 3688169689Skan if (!has_single_use (op)) 3689169689Skan { 3690169689Skan register_new_assert_for (op, comp_code, value, bb, NULL, si); 3691169689Skan need_assert = true; 3692169689Skan } 3693169689Skan } 3694169689Skan } 3695169689Skan 3696169689Skan /* Remember the last statement of the block. */ 3697169689Skan last = stmt; 3698169689Skan } 3699169689Skan 3700169689Skan /* If BB's last statement is a conditional expression 3701169689Skan involving integer operands, recurse into each of the sub-graphs 3702169689Skan rooted at BB to determine if we need to add ASSERT_EXPRs. */ 3703169689Skan if (last 3704169689Skan && TREE_CODE (last) == COND_EXPR 3705169689Skan && !fp_predicate (COND_EXPR_COND (last)) 3706169689Skan && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 3707169689Skan need_assert |= find_conditional_asserts (bb); 3708169689Skan 3709169689Skan /* Recurse into the dominator children of BB. */ 3710169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 3711169689Skan son; 3712169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 3713169689Skan need_assert |= find_assert_locations (son); 3714169689Skan 3715169689Skan return need_assert; 3716169689Skan} 3717169689Skan 3718169689Skan 3719169689Skan/* Create an ASSERT_EXPR for NAME and insert it in the location 3720169689Skan indicated by LOC. Return true if we made any edge insertions. */ 3721169689Skan 3722169689Skanstatic bool 3723169689Skanprocess_assert_insertions_for (tree name, assert_locus_t loc) 3724169689Skan{ 3725169689Skan /* Build the comparison expression NAME_i COMP_CODE VAL. */ 3726169689Skan tree stmt, cond, assert_expr; 3727169689Skan edge_iterator ei; 3728169689Skan edge e; 3729169689Skan 3730169689Skan cond = build2 (loc->comp_code, boolean_type_node, name, loc->val); 3731169689Skan assert_expr = build_assert_expr_for (cond, name); 3732169689Skan 3733169689Skan if (loc->e) 3734169689Skan { 3735169689Skan /* We have been asked to insert the assertion on an edge. This 3736169689Skan is used only by COND_EXPR and SWITCH_EXPR assertions. */ 3737169689Skan#if defined ENABLE_CHECKING 3738169689Skan gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR 3739169689Skan || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR); 3740169689Skan#endif 3741169689Skan 3742169689Skan bsi_insert_on_edge (loc->e, assert_expr); 3743169689Skan return true; 3744169689Skan } 3745169689Skan 3746169689Skan /* Otherwise, we can insert right after LOC->SI iff the 3747169689Skan statement must not be the last statement in the block. */ 3748169689Skan stmt = bsi_stmt (loc->si); 3749169689Skan if (!stmt_ends_bb_p (stmt)) 3750169689Skan { 3751169689Skan bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); 3752169689Skan return false; 3753169689Skan } 3754169689Skan 3755169689Skan /* If STMT must be the last statement in BB, we can only insert new 3756169689Skan assertions on the non-abnormal edge out of BB. Note that since 3757169689Skan STMT is not control flow, there may only be one non-abnormal edge 3758169689Skan out of BB. */ 3759169689Skan FOR_EACH_EDGE (e, ei, loc->bb->succs) 3760169689Skan if (!(e->flags & EDGE_ABNORMAL)) 3761169689Skan { 3762169689Skan bsi_insert_on_edge (e, assert_expr); 3763169689Skan return true; 3764169689Skan } 3765169689Skan 3766169689Skan gcc_unreachable (); 3767169689Skan} 3768169689Skan 3769169689Skan 3770169689Skan/* Process all the insertions registered for every name N_i registered 3771169689Skan in NEED_ASSERT_FOR. The list of assertions to be inserted are 3772169689Skan found in ASSERTS_FOR[i]. */ 3773169689Skan 3774169689Skanstatic void 3775169689Skanprocess_assert_insertions (void) 3776169689Skan{ 3777169689Skan unsigned i; 3778169689Skan bitmap_iterator bi; 3779169689Skan bool update_edges_p = false; 3780169689Skan int num_asserts = 0; 3781169689Skan 3782169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3783169689Skan dump_all_asserts (dump_file); 3784169689Skan 3785169689Skan EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3786169689Skan { 3787169689Skan assert_locus_t loc = asserts_for[i]; 3788169689Skan gcc_assert (loc); 3789169689Skan 3790169689Skan while (loc) 3791169689Skan { 3792169689Skan assert_locus_t next = loc->next; 3793169689Skan update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 3794169689Skan free (loc); 3795169689Skan loc = next; 3796169689Skan num_asserts++; 3797169689Skan } 3798169689Skan } 3799169689Skan 3800169689Skan if (update_edges_p) 3801169689Skan bsi_commit_edge_inserts (); 3802169689Skan 3803169689Skan if (dump_file && (dump_flags & TDF_STATS)) 3804169689Skan fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n", 3805169689Skan num_asserts); 3806169689Skan} 3807169689Skan 3808169689Skan 3809169689Skan/* Traverse the flowgraph looking for conditional jumps to insert range 3810169689Skan expressions. These range expressions are meant to provide information 3811169689Skan to optimizations that need to reason in terms of value ranges. They 3812169689Skan will not be expanded into RTL. For instance, given: 3813169689Skan 3814169689Skan x = ... 3815169689Skan y = ... 3816169689Skan if (x < y) 3817169689Skan y = x - 2; 3818169689Skan else 3819169689Skan x = y + 3; 3820169689Skan 3821169689Skan this pass will transform the code into: 3822169689Skan 3823169689Skan x = ... 3824169689Skan y = ... 3825169689Skan if (x < y) 3826169689Skan { 3827169689Skan x = ASSERT_EXPR <x, x < y> 3828169689Skan y = x - 2 3829169689Skan } 3830169689Skan else 3831169689Skan { 3832169689Skan y = ASSERT_EXPR <y, x <= y> 3833169689Skan x = y + 3 3834169689Skan } 3835169689Skan 3836169689Skan The idea is that once copy and constant propagation have run, other 3837169689Skan optimizations will be able to determine what ranges of values can 'x' 3838169689Skan take in different paths of the code, simply by checking the reaching 3839169689Skan definition of 'x'. */ 3840169689Skan 3841169689Skanstatic void 3842169689Skaninsert_range_assertions (void) 3843169689Skan{ 3844169689Skan edge e; 3845169689Skan edge_iterator ei; 3846169689Skan bool update_ssa_p; 3847169689Skan 3848169689Skan found_in_subgraph = sbitmap_alloc (num_ssa_names); 3849169689Skan sbitmap_zero (found_in_subgraph); 3850169689Skan 3851169689Skan blocks_visited = sbitmap_alloc (last_basic_block); 3852169689Skan sbitmap_zero (blocks_visited); 3853169689Skan 3854169689Skan need_assert_for = BITMAP_ALLOC (NULL); 3855169689Skan asserts_for = XNEWVEC (assert_locus_t, num_ssa_names); 3856169689Skan memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t)); 3857169689Skan 3858169689Skan calculate_dominance_info (CDI_DOMINATORS); 3859169689Skan 3860169689Skan update_ssa_p = false; 3861169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 3862169689Skan if (find_assert_locations (e->dest)) 3863169689Skan update_ssa_p = true; 3864169689Skan 3865169689Skan if (update_ssa_p) 3866169689Skan { 3867169689Skan process_assert_insertions (); 3868169689Skan update_ssa (TODO_update_ssa_no_phi); 3869169689Skan } 3870169689Skan 3871169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3872169689Skan { 3873169689Skan fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 3874169689Skan dump_function_to_file (current_function_decl, dump_file, dump_flags); 3875169689Skan } 3876169689Skan 3877169689Skan sbitmap_free (found_in_subgraph); 3878169689Skan free (asserts_for); 3879169689Skan BITMAP_FREE (need_assert_for); 3880169689Skan} 3881169689Skan 3882169689Skan 3883169689Skan/* Convert range assertion expressions into the implied copies and 3884169689Skan copy propagate away the copies. Doing the trivial copy propagation 3885169689Skan here avoids the need to run the full copy propagation pass after 3886169689Skan VRP. 3887169689Skan 3888169689Skan FIXME, this will eventually lead to copy propagation removing the 3889169689Skan names that had useful range information attached to them. For 3890169689Skan instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 3891169689Skan then N_i will have the range [3, +INF]. 3892169689Skan 3893169689Skan However, by converting the assertion into the implied copy 3894169689Skan operation N_i = N_j, we will then copy-propagate N_j into the uses 3895169689Skan of N_i and lose the range information. We may want to hold on to 3896169689Skan ASSERT_EXPRs a little while longer as the ranges could be used in 3897169689Skan things like jump threading. 3898169689Skan 3899169689Skan The problem with keeping ASSERT_EXPRs around is that passes after 3900169689Skan VRP need to handle them appropriately. 3901169689Skan 3902169689Skan Another approach would be to make the range information a first 3903169689Skan class property of the SSA_NAME so that it can be queried from 3904169689Skan any pass. This is made somewhat more complex by the need for 3905169689Skan multiple ranges to be associated with one SSA_NAME. */ 3906169689Skan 3907169689Skanstatic void 3908169689Skanremove_range_assertions (void) 3909169689Skan{ 3910169689Skan basic_block bb; 3911169689Skan block_stmt_iterator si; 3912169689Skan 3913169689Skan /* Note that the BSI iterator bump happens at the bottom of the 3914169689Skan loop and no bump is necessary if we're removing the statement 3915169689Skan referenced by the current BSI. */ 3916169689Skan FOR_EACH_BB (bb) 3917169689Skan for (si = bsi_start (bb); !bsi_end_p (si);) 3918169689Skan { 3919169689Skan tree stmt = bsi_stmt (si); 3920169689Skan tree use_stmt; 3921169689Skan 3922169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3923169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 3924169689Skan { 3925169689Skan tree rhs = TREE_OPERAND (stmt, 1), var; 3926169689Skan tree cond = fold (ASSERT_EXPR_COND (rhs)); 3927169689Skan use_operand_p use_p; 3928169689Skan imm_use_iterator iter; 3929169689Skan 3930169689Skan gcc_assert (cond != boolean_false_node); 3931169689Skan 3932169689Skan /* Propagate the RHS into every use of the LHS. */ 3933169689Skan var = ASSERT_EXPR_VAR (rhs); 3934169689Skan FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0)) 3935169689Skan FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 3936169689Skan { 3937169689Skan SET_USE (use_p, var); 3938169689Skan gcc_assert (TREE_CODE (var) == SSA_NAME); 3939169689Skan } 3940169689Skan 3941169689Skan /* And finally, remove the copy, it is not needed. */ 3942169689Skan bsi_remove (&si, true); 3943169689Skan } 3944169689Skan else 3945169689Skan bsi_next (&si); 3946169689Skan } 3947169689Skan 3948169689Skan sbitmap_free (blocks_visited); 3949169689Skan} 3950169689Skan 3951169689Skan 3952169689Skan/* Return true if STMT is interesting for VRP. */ 3953169689Skan 3954169689Skanstatic bool 3955169689Skanstmt_interesting_for_vrp (tree stmt) 3956169689Skan{ 3957169689Skan if (TREE_CODE (stmt) == PHI_NODE 3958169689Skan && is_gimple_reg (PHI_RESULT (stmt)) 3959169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))) 3960169689Skan || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))))) 3961169689Skan return true; 3962169689Skan else if (TREE_CODE (stmt) == MODIFY_EXPR) 3963169689Skan { 3964169689Skan tree lhs = TREE_OPERAND (stmt, 0); 3965169689Skan tree rhs = TREE_OPERAND (stmt, 1); 3966169689Skan 3967169689Skan /* In general, assignments with virtual operands are not useful 3968169689Skan for deriving ranges, with the obvious exception of calls to 3969169689Skan builtin functions. */ 3970169689Skan if (TREE_CODE (lhs) == SSA_NAME 3971169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3972169689Skan || POINTER_TYPE_P (TREE_TYPE (lhs))) 3973169689Skan && ((TREE_CODE (rhs) == CALL_EXPR 3974169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 3975169689Skan && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 3976169689Skan && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 3977169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) 3978169689Skan return true; 3979169689Skan } 3980169689Skan else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 3981169689Skan return true; 3982169689Skan 3983169689Skan return false; 3984169689Skan} 3985169689Skan 3986169689Skan 3987169689Skan/* Initialize local data structures for VRP. */ 3988169689Skan 3989169689Skanstatic void 3990169689Skanvrp_initialize (void) 3991169689Skan{ 3992169689Skan basic_block bb; 3993169689Skan 3994169689Skan vr_value = XNEWVEC (value_range_t *, num_ssa_names); 3995169689Skan memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *)); 3996169689Skan 3997169689Skan FOR_EACH_BB (bb) 3998169689Skan { 3999169689Skan block_stmt_iterator si; 4000169689Skan tree phi; 4001169689Skan 4002169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 4003169689Skan { 4004169689Skan if (!stmt_interesting_for_vrp (phi)) 4005169689Skan { 4006169689Skan tree lhs = PHI_RESULT (phi); 4007169689Skan set_value_range_to_varying (get_value_range (lhs)); 4008169689Skan DONT_SIMULATE_AGAIN (phi) = true; 4009169689Skan } 4010169689Skan else 4011169689Skan DONT_SIMULATE_AGAIN (phi) = false; 4012169689Skan } 4013169689Skan 4014169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 4015169689Skan { 4016169689Skan tree stmt = bsi_stmt (si); 4017169689Skan 4018169689Skan if (!stmt_interesting_for_vrp (stmt)) 4019169689Skan { 4020169689Skan ssa_op_iter i; 4021169689Skan tree def; 4022169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 4023169689Skan set_value_range_to_varying (get_value_range (def)); 4024169689Skan DONT_SIMULATE_AGAIN (stmt) = true; 4025169689Skan } 4026169689Skan else 4027169689Skan { 4028169689Skan DONT_SIMULATE_AGAIN (stmt) = false; 4029169689Skan } 4030169689Skan } 4031169689Skan } 4032169689Skan} 4033169689Skan 4034169689Skan 4035169689Skan/* Visit assignment STMT. If it produces an interesting range, record 4036169689Skan the SSA name in *OUTPUT_P. */ 4037169689Skan 4038169689Skanstatic enum ssa_prop_result 4039169689Skanvrp_visit_assignment (tree stmt, tree *output_p) 4040169689Skan{ 4041169689Skan tree lhs, rhs, def; 4042169689Skan ssa_op_iter iter; 4043169689Skan 4044169689Skan lhs = TREE_OPERAND (stmt, 0); 4045169689Skan rhs = TREE_OPERAND (stmt, 1); 4046169689Skan 4047169689Skan /* We only keep track of ranges in integral and pointer types. */ 4048169689Skan if (TREE_CODE (lhs) == SSA_NAME 4049169689Skan && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 4050169689Skan /* It is valid to have NULL MIN/MAX values on a type. See 4051169689Skan build_range_type. */ 4052169689Skan && TYPE_MIN_VALUE (TREE_TYPE (lhs)) 4053169689Skan && TYPE_MAX_VALUE (TREE_TYPE (lhs))) 4054169689Skan || POINTER_TYPE_P (TREE_TYPE (lhs)))) 4055169689Skan { 4056169689Skan struct loop *l; 4057169689Skan value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4058169689Skan 4059169689Skan extract_range_from_expr (&new_vr, rhs); 4060169689Skan 4061169689Skan /* If STMT is inside a loop, we may be able to know something 4062169689Skan else about the range of LHS by examining scalar evolution 4063169689Skan information. */ 4064169689Skan if (current_loops && (l = loop_containing_stmt (stmt))) 4065169689Skan adjust_range_with_scev (&new_vr, l, stmt, lhs); 4066169689Skan 4067169689Skan if (update_value_range (lhs, &new_vr)) 4068169689Skan { 4069169689Skan *output_p = lhs; 4070169689Skan 4071169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4072169689Skan { 4073169689Skan fprintf (dump_file, "Found new range for "); 4074169689Skan print_generic_expr (dump_file, lhs, 0); 4075169689Skan fprintf (dump_file, ": "); 4076169689Skan dump_value_range (dump_file, &new_vr); 4077169689Skan fprintf (dump_file, "\n\n"); 4078169689Skan } 4079169689Skan 4080169689Skan if (new_vr.type == VR_VARYING) 4081169689Skan return SSA_PROP_VARYING; 4082169689Skan 4083169689Skan return SSA_PROP_INTERESTING; 4084169689Skan } 4085169689Skan 4086169689Skan return SSA_PROP_NOT_INTERESTING; 4087169689Skan } 4088169689Skan 4089169689Skan /* Every other statement produces no useful ranges. */ 4090169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4091169689Skan set_value_range_to_varying (get_value_range (def)); 4092169689Skan 4093169689Skan return SSA_PROP_VARYING; 4094169689Skan} 4095169689Skan 4096169689Skan 4097169689Skan/* Compare all the value ranges for names equivalent to VAR with VAL 4098169689Skan using comparison code COMP. Return the same value returned by 4099169689Skan compare_range_with_value, including the setting of 4100169689Skan *STRICT_OVERFLOW_P. */ 4101169689Skan 4102169689Skanstatic tree 4103169689Skancompare_name_with_value (enum tree_code comp, tree var, tree val, 4104169689Skan bool *strict_overflow_p) 4105169689Skan{ 4106169689Skan bitmap_iterator bi; 4107169689Skan unsigned i; 4108169689Skan bitmap e; 4109169689Skan tree retval, t; 4110169689Skan int used_strict_overflow; 4111169689Skan 4112169689Skan t = retval = NULL_TREE; 4113169689Skan 4114169689Skan /* Get the set of equivalences for VAR. */ 4115169689Skan e = get_value_range (var)->equiv; 4116169689Skan 4117169689Skan /* Add VAR to its own set of equivalences so that VAR's value range 4118169689Skan is processed by this loop (otherwise, we would have to replicate 4119169689Skan the body of the loop just to check VAR's value range). */ 4120169689Skan bitmap_set_bit (e, SSA_NAME_VERSION (var)); 4121169689Skan 4122169689Skan /* Start at -1. Set it to 0 if we do a comparison without relying 4123169689Skan on overflow, or 1 if all comparisons rely on overflow. */ 4124169689Skan used_strict_overflow = -1; 4125169689Skan 4126169689Skan EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 4127169689Skan { 4128169689Skan bool sop; 4129169689Skan 4130169689Skan value_range_t equiv_vr = *(vr_value[i]); 4131169689Skan 4132169689Skan /* If name N_i does not have a valid range, use N_i as its own 4133169689Skan range. This allows us to compare against names that may 4134169689Skan have N_i in their ranges. */ 4135169689Skan if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) 4136169689Skan { 4137169689Skan equiv_vr.type = VR_RANGE; 4138169689Skan equiv_vr.min = ssa_name (i); 4139169689Skan equiv_vr.max = ssa_name (i); 4140169689Skan } 4141169689Skan 4142169689Skan sop = false; 4143169689Skan t = compare_range_with_value (comp, &equiv_vr, val, &sop); 4144169689Skan if (t) 4145169689Skan { 4146169689Skan /* If we get different answers from different members 4147169689Skan of the equivalence set this check must be in a dead 4148169689Skan code region. Folding it to a trap representation 4149169689Skan would be correct here. For now just return don't-know. */ 4150169689Skan if (retval != NULL 4151169689Skan && t != retval) 4152169689Skan { 4153169689Skan retval = NULL_TREE; 4154169689Skan break; 4155169689Skan } 4156169689Skan retval = t; 4157169689Skan 4158169689Skan if (!sop) 4159169689Skan used_strict_overflow = 0; 4160169689Skan else if (used_strict_overflow < 0) 4161169689Skan used_strict_overflow = 1; 4162169689Skan } 4163169689Skan } 4164169689Skan 4165169689Skan /* Remove VAR from its own equivalence set. */ 4166169689Skan bitmap_clear_bit (e, SSA_NAME_VERSION (var)); 4167169689Skan 4168169689Skan if (retval) 4169169689Skan { 4170169689Skan if (used_strict_overflow > 0) 4171169689Skan *strict_overflow_p = true; 4172169689Skan return retval; 4173169689Skan } 4174169689Skan 4175169689Skan /* We couldn't find a non-NULL value for the predicate. */ 4176169689Skan return NULL_TREE; 4177169689Skan} 4178169689Skan 4179169689Skan 4180169689Skan/* Given a comparison code COMP and names N1 and N2, compare all the 4181169689Skan ranges equivalent to N1 against all the ranges equivalent to N2 4182169689Skan to determine the value of N1 COMP N2. Return the same value 4183169689Skan returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate 4184169689Skan whether we relied on an overflow infinity in the comparison. */ 4185169689Skan 4186169689Skan 4187169689Skanstatic tree 4188169689Skancompare_names (enum tree_code comp, tree n1, tree n2, 4189169689Skan bool *strict_overflow_p) 4190169689Skan{ 4191169689Skan tree t, retval; 4192169689Skan bitmap e1, e2; 4193169689Skan bitmap_iterator bi1, bi2; 4194169689Skan unsigned i1, i2; 4195169689Skan int used_strict_overflow; 4196169689Skan 4197169689Skan /* Compare the ranges of every name equivalent to N1 against the 4198169689Skan ranges of every name equivalent to N2. */ 4199169689Skan e1 = get_value_range (n1)->equiv; 4200169689Skan e2 = get_value_range (n2)->equiv; 4201169689Skan 4202169689Skan /* Add N1 and N2 to their own set of equivalences to avoid 4203169689Skan duplicating the body of the loop just to check N1 and N2 4204169689Skan ranges. */ 4205169689Skan bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 4206169689Skan bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 4207169689Skan 4208169689Skan /* If the equivalence sets have a common intersection, then the two 4209169689Skan names can be compared without checking their ranges. */ 4210169689Skan if (bitmap_intersect_p (e1, e2)) 4211169689Skan { 4212169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4213169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4214169689Skan 4215169689Skan return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 4216169689Skan ? boolean_true_node 4217169689Skan : boolean_false_node; 4218169689Skan } 4219169689Skan 4220169689Skan /* Start at -1. Set it to 0 if we do a comparison without relying 4221169689Skan on overflow, or 1 if all comparisons rely on overflow. */ 4222169689Skan used_strict_overflow = -1; 4223169689Skan 4224169689Skan /* Otherwise, compare all the equivalent ranges. First, add N1 and 4225169689Skan N2 to their own set of equivalences to avoid duplicating the body 4226169689Skan of the loop just to check N1 and N2 ranges. */ 4227169689Skan EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 4228169689Skan { 4229169689Skan value_range_t vr1 = *(vr_value[i1]); 4230169689Skan 4231169689Skan /* If the range is VARYING or UNDEFINED, use the name itself. */ 4232169689Skan if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) 4233169689Skan { 4234169689Skan vr1.type = VR_RANGE; 4235169689Skan vr1.min = ssa_name (i1); 4236169689Skan vr1.max = ssa_name (i1); 4237169689Skan } 4238169689Skan 4239169689Skan t = retval = NULL_TREE; 4240169689Skan EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 4241169689Skan { 4242171825Skan bool sop = false; 4243169689Skan 4244169689Skan value_range_t vr2 = *(vr_value[i2]); 4245169689Skan 4246169689Skan if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) 4247169689Skan { 4248169689Skan vr2.type = VR_RANGE; 4249169689Skan vr2.min = ssa_name (i2); 4250169689Skan vr2.max = ssa_name (i2); 4251169689Skan } 4252169689Skan 4253169689Skan t = compare_ranges (comp, &vr1, &vr2, &sop); 4254169689Skan if (t) 4255169689Skan { 4256169689Skan /* If we get different answers from different members 4257169689Skan of the equivalence set this check must be in a dead 4258169689Skan code region. Folding it to a trap representation 4259169689Skan would be correct here. For now just return don't-know. */ 4260169689Skan if (retval != NULL 4261169689Skan && t != retval) 4262169689Skan { 4263169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4264169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4265169689Skan return NULL_TREE; 4266169689Skan } 4267169689Skan retval = t; 4268169689Skan 4269169689Skan if (!sop) 4270169689Skan used_strict_overflow = 0; 4271169689Skan else if (used_strict_overflow < 0) 4272169689Skan used_strict_overflow = 1; 4273169689Skan } 4274169689Skan } 4275169689Skan 4276169689Skan if (retval) 4277169689Skan { 4278169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4279169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4280169689Skan if (used_strict_overflow > 0) 4281169689Skan *strict_overflow_p = true; 4282169689Skan return retval; 4283169689Skan } 4284169689Skan } 4285169689Skan 4286169689Skan /* None of the equivalent ranges are useful in computing this 4287169689Skan comparison. */ 4288169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4289169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4290169689Skan return NULL_TREE; 4291169689Skan} 4292169689Skan 4293169689Skan 4294169689Skan/* Given a conditional predicate COND, try to determine if COND yields 4295169689Skan true or false based on the value ranges of its operands. Return 4296169689Skan BOOLEAN_TRUE_NODE if the conditional always evaluates to true, 4297169689Skan BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, 4298169689Skan NULL if the conditional cannot be evaluated at compile time. 4299169689Skan 4300169689Skan If USE_EQUIV_P is true, the ranges of all the names equivalent with 4301169689Skan the operands in COND are used when trying to compute its value. 4302169689Skan This is only used during final substitution. During propagation, 4303169689Skan we only check the range of each variable and not its equivalents. 4304169689Skan 4305169689Skan Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow 4306169689Skan infinity to produce the result. */ 4307169689Skan 4308169689Skanstatic tree 4309169689Skanvrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p, 4310169689Skan bool *strict_overflow_p) 4311169689Skan{ 4312169689Skan gcc_assert (TREE_CODE (cond) == SSA_NAME 4313169689Skan || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); 4314169689Skan 4315169689Skan if (TREE_CODE (cond) == SSA_NAME) 4316169689Skan { 4317169689Skan value_range_t *vr; 4318169689Skan tree retval; 4319169689Skan 4320169689Skan if (use_equiv_p) 4321169689Skan retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node, 4322169689Skan strict_overflow_p); 4323169689Skan else 4324169689Skan { 4325169689Skan value_range_t *vr = get_value_range (cond); 4326169689Skan retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node, 4327169689Skan strict_overflow_p); 4328169689Skan } 4329169689Skan 4330169689Skan /* If COND has a known boolean range, return it. */ 4331169689Skan if (retval) 4332169689Skan return retval; 4333169689Skan 4334169689Skan /* Otherwise, if COND has a symbolic range of exactly one value, 4335169689Skan return it. */ 4336169689Skan vr = get_value_range (cond); 4337169689Skan if (vr->type == VR_RANGE && vr->min == vr->max) 4338169689Skan return vr->min; 4339169689Skan } 4340169689Skan else 4341169689Skan { 4342169689Skan tree op0 = TREE_OPERAND (cond, 0); 4343169689Skan tree op1 = TREE_OPERAND (cond, 1); 4344169689Skan 4345169689Skan /* We only deal with integral and pointer types. */ 4346169689Skan if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 4347169689Skan && !POINTER_TYPE_P (TREE_TYPE (op0))) 4348169689Skan return NULL_TREE; 4349169689Skan 4350169689Skan if (use_equiv_p) 4351169689Skan { 4352169689Skan if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 4353169689Skan return compare_names (TREE_CODE (cond), op0, op1, 4354169689Skan strict_overflow_p); 4355169689Skan else if (TREE_CODE (op0) == SSA_NAME) 4356169689Skan return compare_name_with_value (TREE_CODE (cond), op0, op1, 4357169689Skan strict_overflow_p); 4358169689Skan else if (TREE_CODE (op1) == SSA_NAME) 4359169689Skan return (compare_name_with_value 4360169689Skan (swap_tree_comparison (TREE_CODE (cond)), op1, op0, 4361169689Skan strict_overflow_p)); 4362169689Skan } 4363169689Skan else 4364169689Skan { 4365169689Skan value_range_t *vr0, *vr1; 4366169689Skan 4367169689Skan vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 4368169689Skan vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 4369169689Skan 4370169689Skan if (vr0 && vr1) 4371169689Skan return compare_ranges (TREE_CODE (cond), vr0, vr1, 4372169689Skan strict_overflow_p); 4373169689Skan else if (vr0 && vr1 == NULL) 4374169689Skan return compare_range_with_value (TREE_CODE (cond), vr0, op1, 4375169689Skan strict_overflow_p); 4376169689Skan else if (vr0 == NULL && vr1) 4377169689Skan return (compare_range_with_value 4378169689Skan (swap_tree_comparison (TREE_CODE (cond)), vr1, op0, 4379169689Skan strict_overflow_p)); 4380169689Skan } 4381169689Skan } 4382169689Skan 4383169689Skan /* Anything else cannot be computed statically. */ 4384169689Skan return NULL_TREE; 4385169689Skan} 4386169689Skan 4387169689Skan/* Given COND within STMT, try to simplify it based on value range 4388169689Skan information. Return NULL if the conditional can not be evaluated. 4389169689Skan The ranges of all the names equivalent with the operands in COND 4390169689Skan will be used when trying to compute the value. If the result is 4391169689Skan based on undefined signed overflow, issue a warning if 4392169689Skan appropriate. */ 4393169689Skan 4394169689Skantree 4395169689Skanvrp_evaluate_conditional (tree cond, tree stmt) 4396169689Skan{ 4397169689Skan bool sop; 4398169689Skan tree ret; 4399169689Skan 4400169689Skan sop = false; 4401169689Skan ret = vrp_evaluate_conditional_warnv (cond, true, &sop); 4402169689Skan 4403169689Skan if (ret && sop) 4404169689Skan { 4405169689Skan enum warn_strict_overflow_code wc; 4406169689Skan const char* warnmsg; 4407169689Skan 4408169689Skan if (is_gimple_min_invariant (ret)) 4409169689Skan { 4410169689Skan wc = WARN_STRICT_OVERFLOW_CONDITIONAL; 4411169689Skan warnmsg = G_("assuming signed overflow does not occur when " 4412169689Skan "simplifying conditional to constant"); 4413169689Skan } 4414169689Skan else 4415169689Skan { 4416169689Skan wc = WARN_STRICT_OVERFLOW_COMPARISON; 4417169689Skan warnmsg = G_("assuming signed overflow does not occur when " 4418169689Skan "simplifying conditional"); 4419169689Skan } 4420169689Skan 4421169689Skan if (issue_strict_overflow_warning (wc)) 4422169689Skan { 4423169689Skan location_t locus; 4424169689Skan 4425169689Skan if (!EXPR_HAS_LOCATION (stmt)) 4426169689Skan locus = input_location; 4427169689Skan else 4428169689Skan locus = EXPR_LOCATION (stmt); 4429169689Skan warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg); 4430169689Skan } 4431169689Skan } 4432169689Skan 4433169689Skan return ret; 4434169689Skan} 4435169689Skan 4436169689Skan 4437169689Skan/* Visit conditional statement STMT. If we can determine which edge 4438169689Skan will be taken out of STMT's basic block, record it in 4439169689Skan *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return 4440169689Skan SSA_PROP_VARYING. */ 4441169689Skan 4442169689Skanstatic enum ssa_prop_result 4443169689Skanvrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) 4444169689Skan{ 4445169689Skan tree cond, val; 4446169689Skan bool sop; 4447169689Skan 4448169689Skan *taken_edge_p = NULL; 4449169689Skan 4450169689Skan /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to 4451169689Skan add ASSERT_EXPRs for them. */ 4452169689Skan if (TREE_CODE (stmt) == SWITCH_EXPR) 4453169689Skan return SSA_PROP_VARYING; 4454169689Skan 4455169689Skan cond = COND_EXPR_COND (stmt); 4456169689Skan 4457169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4458169689Skan { 4459169689Skan tree use; 4460169689Skan ssa_op_iter i; 4461169689Skan 4462169689Skan fprintf (dump_file, "\nVisiting conditional with predicate: "); 4463169689Skan print_generic_expr (dump_file, cond, 0); 4464169689Skan fprintf (dump_file, "\nWith known ranges\n"); 4465169689Skan 4466169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 4467169689Skan { 4468169689Skan fprintf (dump_file, "\t"); 4469169689Skan print_generic_expr (dump_file, use, 0); 4470169689Skan fprintf (dump_file, ": "); 4471169689Skan dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 4472169689Skan } 4473169689Skan 4474169689Skan fprintf (dump_file, "\n"); 4475169689Skan } 4476169689Skan 4477169689Skan /* Compute the value of the predicate COND by checking the known 4478169689Skan ranges of each of its operands. 4479169689Skan 4480169689Skan Note that we cannot evaluate all the equivalent ranges here 4481169689Skan because those ranges may not yet be final and with the current 4482169689Skan propagation strategy, we cannot determine when the value ranges 4483169689Skan of the names in the equivalence set have changed. 4484169689Skan 4485169689Skan For instance, given the following code fragment 4486169689Skan 4487169689Skan i_5 = PHI <8, i_13> 4488169689Skan ... 4489169689Skan i_14 = ASSERT_EXPR <i_5, i_5 != 0> 4490169689Skan if (i_14 == 1) 4491169689Skan ... 4492169689Skan 4493169689Skan Assume that on the first visit to i_14, i_5 has the temporary 4494169689Skan range [8, 8] because the second argument to the PHI function is 4495169689Skan not yet executable. We derive the range ~[0, 0] for i_14 and the 4496169689Skan equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 4497169689Skan the first time, since i_14 is equivalent to the range [8, 8], we 4498169689Skan determine that the predicate is always false. 4499169689Skan 4500169689Skan On the next round of propagation, i_13 is determined to be 4501169689Skan VARYING, which causes i_5 to drop down to VARYING. So, another 4502169689Skan visit to i_14 is scheduled. In this second visit, we compute the 4503169689Skan exact same range and equivalence set for i_14, namely ~[0, 0] and 4504169689Skan { i_5 }. But we did not have the previous range for i_5 4505169689Skan registered, so vrp_visit_assignment thinks that the range for 4506169689Skan i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 4507169689Skan is not visited again, which stops propagation from visiting 4508169689Skan statements in the THEN clause of that if(). 4509169689Skan 4510169689Skan To properly fix this we would need to keep the previous range 4511169689Skan value for the names in the equivalence set. This way we would've 4512169689Skan discovered that from one visit to the other i_5 changed from 4513169689Skan range [8, 8] to VR_VARYING. 4514169689Skan 4515169689Skan However, fixing this apparent limitation may not be worth the 4516169689Skan additional checking. Testing on several code bases (GCC, DLV, 4517169689Skan MICO, TRAMP3D and SPEC2000) showed that doing this results in 4518169689Skan 4 more predicates folded in SPEC. */ 4519169689Skan sop = false; 4520169689Skan val = vrp_evaluate_conditional_warnv (cond, false, &sop); 4521169689Skan if (val) 4522169689Skan { 4523169689Skan if (!sop) 4524169689Skan *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); 4525169689Skan else 4526169689Skan { 4527169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4528169689Skan fprintf (dump_file, 4529169689Skan "\nIgnoring predicate evaluation because " 4530169689Skan "it assumes that signed overflow is undefined"); 4531169689Skan val = NULL_TREE; 4532169689Skan } 4533169689Skan } 4534169689Skan 4535169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4536169689Skan { 4537169689Skan fprintf (dump_file, "\nPredicate evaluates to: "); 4538169689Skan if (val == NULL_TREE) 4539169689Skan fprintf (dump_file, "DON'T KNOW\n"); 4540169689Skan else 4541169689Skan print_generic_stmt (dump_file, val, 0); 4542169689Skan } 4543169689Skan 4544169689Skan return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 4545169689Skan} 4546169689Skan 4547169689Skan 4548169689Skan/* Evaluate statement STMT. If the statement produces a useful range, 4549169689Skan return SSA_PROP_INTERESTING and record the SSA name with the 4550169689Skan interesting range into *OUTPUT_P. 4551169689Skan 4552169689Skan If STMT is a conditional branch and we can determine its truth 4553169689Skan value, the taken edge is recorded in *TAKEN_EDGE_P. 4554169689Skan 4555169689Skan If STMT produces a varying value, return SSA_PROP_VARYING. */ 4556169689Skan 4557169689Skanstatic enum ssa_prop_result 4558169689Skanvrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 4559169689Skan{ 4560169689Skan tree def; 4561169689Skan ssa_op_iter iter; 4562169689Skan stmt_ann_t ann; 4563169689Skan 4564169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4565169689Skan { 4566169689Skan fprintf (dump_file, "\nVisiting statement:\n"); 4567169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 4568169689Skan fprintf (dump_file, "\n"); 4569169689Skan } 4570169689Skan 4571169689Skan ann = stmt_ann (stmt); 4572169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 4573169689Skan { 4574169689Skan tree rhs = TREE_OPERAND (stmt, 1); 4575169689Skan 4576169689Skan /* In general, assignments with virtual operands are not useful 4577169689Skan for deriving ranges, with the obvious exception of calls to 4578169689Skan builtin functions. */ 4579169689Skan if ((TREE_CODE (rhs) == CALL_EXPR 4580169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 4581169689Skan && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 4582169689Skan && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 4583169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 4584169689Skan return vrp_visit_assignment (stmt, output_p); 4585169689Skan } 4586169689Skan else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 4587169689Skan return vrp_visit_cond_stmt (stmt, taken_edge_p); 4588169689Skan 4589169689Skan /* All other statements produce nothing of interest for VRP, so mark 4590169689Skan their outputs varying and prevent further simulation. */ 4591169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4592169689Skan set_value_range_to_varying (get_value_range (def)); 4593169689Skan 4594169689Skan return SSA_PROP_VARYING; 4595169689Skan} 4596169689Skan 4597169689Skan 4598169689Skan/* Meet operation for value ranges. Given two value ranges VR0 and 4599169689Skan VR1, store in VR0 the result of meeting VR0 and VR1. 4600169689Skan 4601169689Skan The meeting rules are as follows: 4602169689Skan 4603169689Skan 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. 4604169689Skan 4605169689Skan 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the 4606169689Skan union of VR0 and VR1. */ 4607169689Skan 4608169689Skanstatic void 4609169689Skanvrp_meet (value_range_t *vr0, value_range_t *vr1) 4610169689Skan{ 4611169689Skan if (vr0->type == VR_UNDEFINED) 4612169689Skan { 4613169689Skan copy_value_range (vr0, vr1); 4614169689Skan return; 4615169689Skan } 4616169689Skan 4617169689Skan if (vr1->type == VR_UNDEFINED) 4618169689Skan { 4619169689Skan /* Nothing to do. VR0 already has the resulting range. */ 4620169689Skan return; 4621169689Skan } 4622169689Skan 4623169689Skan if (vr0->type == VR_VARYING) 4624169689Skan { 4625169689Skan /* Nothing to do. VR0 already has the resulting range. */ 4626169689Skan return; 4627169689Skan } 4628169689Skan 4629169689Skan if (vr1->type == VR_VARYING) 4630169689Skan { 4631169689Skan set_value_range_to_varying (vr0); 4632169689Skan return; 4633169689Skan } 4634169689Skan 4635169689Skan if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) 4636169689Skan { 4637169689Skan /* If VR0 and VR1 have a non-empty intersection, compute the 4638169689Skan union of both ranges. */ 4639169689Skan if (value_ranges_intersect_p (vr0, vr1)) 4640169689Skan { 4641169689Skan int cmp; 4642169689Skan tree min, max; 4643169689Skan 4644169689Skan /* The lower limit of the new range is the minimum of the 4645169689Skan two ranges. If they cannot be compared, the result is 4646169689Skan VARYING. */ 4647169689Skan cmp = compare_values (vr0->min, vr1->min); 4648169689Skan if (cmp == 0 || cmp == 1) 4649169689Skan min = vr1->min; 4650169689Skan else if (cmp == -1) 4651169689Skan min = vr0->min; 4652169689Skan else 4653169689Skan { 4654169689Skan set_value_range_to_varying (vr0); 4655169689Skan return; 4656169689Skan } 4657169689Skan 4658169689Skan /* Similarly, the upper limit of the new range is the 4659169689Skan maximum of the two ranges. If they cannot be compared, 4660169689Skan the result is VARYING. */ 4661169689Skan cmp = compare_values (vr0->max, vr1->max); 4662169689Skan if (cmp == 0 || cmp == -1) 4663169689Skan max = vr1->max; 4664169689Skan else if (cmp == 1) 4665169689Skan max = vr0->max; 4666169689Skan else 4667169689Skan { 4668169689Skan set_value_range_to_varying (vr0); 4669169689Skan return; 4670169689Skan } 4671169689Skan 4672169689Skan /* Check for useless ranges. */ 4673169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (min)) 4674169689Skan && ((vrp_val_is_min (min) || is_overflow_infinity (min)) 4675169689Skan && (vrp_val_is_max (max) || is_overflow_infinity (max)))) 4676169689Skan { 4677169689Skan set_value_range_to_varying (vr0); 4678169689Skan return; 4679169689Skan } 4680169689Skan 4681169689Skan /* The resulting set of equivalences is the intersection of 4682169689Skan the two sets. */ 4683169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4684169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4685169689Skan else if (vr0->equiv && !vr1->equiv) 4686169689Skan bitmap_clear (vr0->equiv); 4687169689Skan 4688169689Skan set_value_range (vr0, vr0->type, min, max, vr0->equiv); 4689169689Skan } 4690169689Skan else 4691169689Skan goto no_meet; 4692169689Skan } 4693169689Skan else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 4694169689Skan { 4695169689Skan /* Two anti-ranges meet only if they are both identical. */ 4696169689Skan if (compare_values (vr0->min, vr1->min) == 0 4697169689Skan && compare_values (vr0->max, vr1->max) == 0 4698169689Skan && compare_values (vr0->min, vr0->max) == 0) 4699169689Skan { 4700169689Skan /* The resulting set of equivalences is the intersection of 4701169689Skan the two sets. */ 4702169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4703169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4704169689Skan else if (vr0->equiv && !vr1->equiv) 4705169689Skan bitmap_clear (vr0->equiv); 4706169689Skan } 4707169689Skan else 4708169689Skan goto no_meet; 4709169689Skan } 4710169689Skan else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 4711169689Skan { 4712169689Skan /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] 4713169689Skan meet only if the ranges have an empty intersection. The 4714169689Skan result of the meet operation is the anti-range. */ 4715169689Skan if (!symbolic_range_p (vr0) 4716169689Skan && !symbolic_range_p (vr1) 4717169689Skan && !value_ranges_intersect_p (vr0, vr1)) 4718169689Skan { 4719169689Skan /* Copy most of VR1 into VR0. Don't copy VR1's equivalence 4720169689Skan set. We need to compute the intersection of the two 4721169689Skan equivalence sets. */ 4722169689Skan if (vr1->type == VR_ANTI_RANGE) 4723169689Skan set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); 4724169689Skan 4725169689Skan /* The resulting set of equivalences is the intersection of 4726169689Skan the two sets. */ 4727169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4728169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4729169689Skan else if (vr0->equiv && !vr1->equiv) 4730169689Skan bitmap_clear (vr0->equiv); 4731169689Skan } 4732169689Skan else 4733169689Skan goto no_meet; 4734169689Skan } 4735169689Skan else 4736169689Skan gcc_unreachable (); 4737169689Skan 4738169689Skan return; 4739169689Skan 4740169689Skanno_meet: 4741169689Skan /* The two range VR0 and VR1 do not meet. Before giving up and 4742169689Skan setting the result to VARYING, see if we can at least derive a 4743169689Skan useful anti-range. FIXME, all this nonsense about distinguishing 4744169689Skan anti-ranges from ranges is necessary because of the odd 4745169689Skan semantics of range_includes_zero_p and friends. */ 4746169689Skan if (!symbolic_range_p (vr0) 4747169689Skan && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0)) 4748169689Skan || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0))) 4749169689Skan && !symbolic_range_p (vr1) 4750169689Skan && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1)) 4751169689Skan || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1)))) 4752169689Skan { 4753169689Skan set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min)); 4754169689Skan 4755169689Skan /* Since this meet operation did not result from the meeting of 4756169689Skan two equivalent names, VR0 cannot have any equivalences. */ 4757169689Skan if (vr0->equiv) 4758169689Skan bitmap_clear (vr0->equiv); 4759169689Skan } 4760169689Skan else 4761169689Skan set_value_range_to_varying (vr0); 4762169689Skan} 4763169689Skan 4764169689Skan 4765169689Skan/* Visit all arguments for PHI node PHI that flow through executable 4766169689Skan edges. If a valid value range can be derived from all the incoming 4767169689Skan value ranges, set a new range for the LHS of PHI. */ 4768169689Skan 4769169689Skanstatic enum ssa_prop_result 4770169689Skanvrp_visit_phi_node (tree phi) 4771169689Skan{ 4772169689Skan int i; 4773169689Skan tree lhs = PHI_RESULT (phi); 4774169689Skan value_range_t *lhs_vr = get_value_range (lhs); 4775169689Skan value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4776169689Skan 4777169689Skan copy_value_range (&vr_result, lhs_vr); 4778169689Skan 4779169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4780169689Skan { 4781169689Skan fprintf (dump_file, "\nVisiting PHI node: "); 4782169689Skan print_generic_expr (dump_file, phi, dump_flags); 4783169689Skan } 4784169689Skan 4785169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 4786169689Skan { 4787169689Skan edge e = PHI_ARG_EDGE (phi, i); 4788169689Skan 4789169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4790169689Skan { 4791169689Skan fprintf (dump_file, 4792169689Skan "\n Argument #%d (%d -> %d %sexecutable)\n", 4793169689Skan i, e->src->index, e->dest->index, 4794169689Skan (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 4795169689Skan } 4796169689Skan 4797169689Skan if (e->flags & EDGE_EXECUTABLE) 4798169689Skan { 4799169689Skan tree arg = PHI_ARG_DEF (phi, i); 4800169689Skan value_range_t vr_arg; 4801169689Skan 4802169689Skan if (TREE_CODE (arg) == SSA_NAME) 4803169689Skan vr_arg = *(get_value_range (arg)); 4804169689Skan else 4805169689Skan { 4806169689Skan if (is_overflow_infinity (arg)) 4807169689Skan { 4808169689Skan arg = copy_node (arg); 4809169689Skan TREE_OVERFLOW (arg) = 0; 4810169689Skan } 4811169689Skan 4812169689Skan vr_arg.type = VR_RANGE; 4813169689Skan vr_arg.min = arg; 4814169689Skan vr_arg.max = arg; 4815169689Skan vr_arg.equiv = NULL; 4816169689Skan } 4817169689Skan 4818169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4819169689Skan { 4820169689Skan fprintf (dump_file, "\t"); 4821169689Skan print_generic_expr (dump_file, arg, dump_flags); 4822169689Skan fprintf (dump_file, "\n\tValue: "); 4823169689Skan dump_value_range (dump_file, &vr_arg); 4824169689Skan fprintf (dump_file, "\n"); 4825169689Skan } 4826169689Skan 4827169689Skan vrp_meet (&vr_result, &vr_arg); 4828169689Skan 4829169689Skan if (vr_result.type == VR_VARYING) 4830169689Skan break; 4831169689Skan } 4832169689Skan } 4833169689Skan 4834169689Skan if (vr_result.type == VR_VARYING) 4835169689Skan goto varying; 4836169689Skan 4837169689Skan /* To prevent infinite iterations in the algorithm, derive ranges 4838169689Skan when the new value is slightly bigger or smaller than the 4839169689Skan previous one. */ 4840169689Skan if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE) 4841169689Skan { 4842169689Skan if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 4843169689Skan { 4844169689Skan int cmp_min = compare_values (lhs_vr->min, vr_result.min); 4845169689Skan int cmp_max = compare_values (lhs_vr->max, vr_result.max); 4846169689Skan 4847169689Skan /* If the new minimum is smaller or larger than the previous 4848169689Skan one, go all the way to -INF. In the first case, to avoid 4849169689Skan iterating millions of times to reach -INF, and in the 4850169689Skan other case to avoid infinite bouncing between different 4851169689Skan minimums. */ 4852169689Skan if (cmp_min > 0 || cmp_min < 0) 4853169689Skan { 4854169689Skan /* If we will end up with a (-INF, +INF) range, set it 4855169689Skan to VARYING. */ 4856169689Skan if (vrp_val_is_max (vr_result.max)) 4857169689Skan goto varying; 4858169689Skan 4859171825Skan if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) 4860171825Skan || !vrp_var_may_overflow (lhs, phi)) 4861169689Skan vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); 4862169689Skan else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) 4863169689Skan vr_result.min = 4864169689Skan negative_overflow_infinity (TREE_TYPE (vr_result.min)); 4865169689Skan else 4866169689Skan goto varying; 4867169689Skan } 4868169689Skan 4869169689Skan /* Similarly, if the new maximum is smaller or larger than 4870169689Skan the previous one, go all the way to +INF. */ 4871169689Skan if (cmp_max < 0 || cmp_max > 0) 4872169689Skan { 4873169689Skan /* If we will end up with a (-INF, +INF) range, set it 4874169689Skan to VARYING. */ 4875169689Skan if (vrp_val_is_min (vr_result.min)) 4876169689Skan goto varying; 4877169689Skan 4878171825Skan if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) 4879171825Skan || !vrp_var_may_overflow (lhs, phi)) 4880169689Skan vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); 4881169689Skan else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) 4882169689Skan vr_result.max = 4883169689Skan positive_overflow_infinity (TREE_TYPE (vr_result.max)); 4884169689Skan else 4885169689Skan goto varying; 4886169689Skan } 4887169689Skan } 4888169689Skan } 4889169689Skan 4890169689Skan /* If the new range is different than the previous value, keep 4891169689Skan iterating. */ 4892169689Skan if (update_value_range (lhs, &vr_result)) 4893169689Skan return SSA_PROP_INTERESTING; 4894169689Skan 4895169689Skan /* Nothing changed, don't add outgoing edges. */ 4896169689Skan return SSA_PROP_NOT_INTERESTING; 4897169689Skan 4898169689Skan /* No match found. Set the LHS to VARYING. */ 4899169689Skanvarying: 4900169689Skan set_value_range_to_varying (lhs_vr); 4901169689Skan return SSA_PROP_VARYING; 4902169689Skan} 4903169689Skan 4904169689Skan/* Simplify a division or modulo operator to a right shift or 4905169689Skan bitwise and if the first operand is unsigned or is greater 4906169689Skan than zero and the second operand is an exact power of two. */ 4907169689Skan 4908169689Skanstatic void 4909169689Skansimplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) 4910169689Skan{ 4911169689Skan tree val = NULL; 4912169689Skan tree op = TREE_OPERAND (rhs, 0); 4913169689Skan value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4914169689Skan 4915169689Skan if (TYPE_UNSIGNED (TREE_TYPE (op))) 4916169689Skan { 4917169689Skan val = integer_one_node; 4918169689Skan } 4919169689Skan else 4920169689Skan { 4921169689Skan bool sop = false; 4922169689Skan 4923259268Spfg val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop); 4924169689Skan 4925169689Skan if (val 4926169689Skan && sop 4927169689Skan && integer_onep (val) 4928169689Skan && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 4929169689Skan { 4930169689Skan location_t locus; 4931169689Skan 4932169689Skan if (!EXPR_HAS_LOCATION (stmt)) 4933169689Skan locus = input_location; 4934169689Skan else 4935169689Skan locus = EXPR_LOCATION (stmt); 4936169689Skan warning (OPT_Wstrict_overflow, 4937169689Skan ("%Hassuming signed overflow does not occur when " 4938169689Skan "simplifying / or %% to >> or &"), 4939169689Skan &locus); 4940169689Skan } 4941169689Skan } 4942169689Skan 4943169689Skan if (val && integer_onep (val)) 4944169689Skan { 4945169689Skan tree t; 4946169689Skan tree op0 = TREE_OPERAND (rhs, 0); 4947169689Skan tree op1 = TREE_OPERAND (rhs, 1); 4948169689Skan 4949169689Skan if (rhs_code == TRUNC_DIV_EXPR) 4950169689Skan { 4951169689Skan t = build_int_cst (NULL_TREE, tree_log2 (op1)); 4952169689Skan t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t); 4953169689Skan } 4954169689Skan else 4955169689Skan { 4956169689Skan t = build_int_cst (TREE_TYPE (op1), 1); 4957169689Skan t = int_const_binop (MINUS_EXPR, op1, t, 0); 4958169689Skan t = fold_convert (TREE_TYPE (op0), t); 4959169689Skan t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t); 4960169689Skan } 4961169689Skan 4962169689Skan TREE_OPERAND (stmt, 1) = t; 4963169689Skan update_stmt (stmt); 4964169689Skan } 4965169689Skan} 4966169689Skan 4967169689Skan/* If the operand to an ABS_EXPR is >= 0, then eliminate the 4968169689Skan ABS_EXPR. If the operand is <= 0, then simplify the 4969169689Skan ABS_EXPR into a NEGATE_EXPR. */ 4970169689Skan 4971169689Skanstatic void 4972169689Skansimplify_abs_using_ranges (tree stmt, tree rhs) 4973169689Skan{ 4974169689Skan tree val = NULL; 4975169689Skan tree op = TREE_OPERAND (rhs, 0); 4976169689Skan tree type = TREE_TYPE (op); 4977169689Skan value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4978169689Skan 4979169689Skan if (TYPE_UNSIGNED (type)) 4980169689Skan { 4981169689Skan val = integer_zero_node; 4982169689Skan } 4983169689Skan else if (vr) 4984169689Skan { 4985169689Skan bool sop = false; 4986169689Skan 4987169689Skan val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); 4988169689Skan if (!val) 4989169689Skan { 4990169689Skan sop = false; 4991169689Skan val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, 4992169689Skan &sop); 4993169689Skan 4994169689Skan if (val) 4995169689Skan { 4996169689Skan if (integer_zerop (val)) 4997169689Skan val = integer_one_node; 4998169689Skan else if (integer_onep (val)) 4999169689Skan val = integer_zero_node; 5000169689Skan } 5001169689Skan } 5002169689Skan 5003169689Skan if (val 5004169689Skan && (integer_onep (val) || integer_zerop (val))) 5005169689Skan { 5006169689Skan tree t; 5007169689Skan 5008169689Skan if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 5009169689Skan { 5010169689Skan location_t locus; 5011169689Skan 5012169689Skan if (!EXPR_HAS_LOCATION (stmt)) 5013169689Skan locus = input_location; 5014169689Skan else 5015169689Skan locus = EXPR_LOCATION (stmt); 5016169689Skan warning (OPT_Wstrict_overflow, 5017169689Skan ("%Hassuming signed overflow does not occur when " 5018169689Skan "simplifying abs (X) to X or -X"), 5019169689Skan &locus); 5020169689Skan } 5021169689Skan 5022169689Skan if (integer_onep (val)) 5023169689Skan t = build1 (NEGATE_EXPR, TREE_TYPE (op), op); 5024169689Skan else 5025169689Skan t = op; 5026169689Skan 5027169689Skan TREE_OPERAND (stmt, 1) = t; 5028169689Skan update_stmt (stmt); 5029169689Skan } 5030169689Skan } 5031169689Skan} 5032169689Skan 5033169689Skan/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 5034169689Skan a known value range VR. 5035169689Skan 5036169689Skan If there is one and only one value which will satisfy the 5037169689Skan conditional, then return that value. Else return NULL. */ 5038169689Skan 5039169689Skanstatic tree 5040169689Skantest_for_singularity (enum tree_code cond_code, tree op0, 5041169689Skan tree op1, value_range_t *vr) 5042169689Skan{ 5043169689Skan tree min = NULL; 5044169689Skan tree max = NULL; 5045169689Skan 5046169689Skan /* Extract minimum/maximum values which satisfy the 5047169689Skan the conditional as it was written. */ 5048169689Skan if (cond_code == LE_EXPR || cond_code == LT_EXPR) 5049169689Skan { 5050169689Skan /* This should not be negative infinity; there is no overflow 5051169689Skan here. */ 5052169689Skan min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 5053169689Skan 5054169689Skan max = op1; 5055169689Skan if (cond_code == LT_EXPR && !is_overflow_infinity (max)) 5056169689Skan { 5057169689Skan tree one = build_int_cst (TREE_TYPE (op0), 1); 5058169689Skan max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 5059171825Skan if (EXPR_P (max)) 5060171825Skan TREE_NO_WARNING (max) = 1; 5061169689Skan } 5062169689Skan } 5063169689Skan else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 5064169689Skan { 5065169689Skan /* This should not be positive infinity; there is no overflow 5066169689Skan here. */ 5067169689Skan max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 5068169689Skan 5069169689Skan min = op1; 5070169689Skan if (cond_code == GT_EXPR && !is_overflow_infinity (min)) 5071169689Skan { 5072169689Skan tree one = build_int_cst (TREE_TYPE (op0), 1); 5073169689Skan min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); 5074171825Skan if (EXPR_P (min)) 5075171825Skan TREE_NO_WARNING (min) = 1; 5076169689Skan } 5077169689Skan } 5078169689Skan 5079169689Skan /* Now refine the minimum and maximum values using any 5080169689Skan value range information we have for op0. */ 5081169689Skan if (min && max) 5082169689Skan { 5083169689Skan if (compare_values (vr->min, min) == -1) 5084169689Skan min = min; 5085169689Skan else 5086169689Skan min = vr->min; 5087169689Skan if (compare_values (vr->max, max) == 1) 5088169689Skan max = max; 5089169689Skan else 5090169689Skan max = vr->max; 5091169689Skan 5092169689Skan /* If the new min/max values have converged to a single value, 5093169689Skan then there is only one value which can satisfy the condition, 5094169689Skan return that value. */ 5095169689Skan if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) 5096169689Skan return min; 5097169689Skan } 5098169689Skan return NULL; 5099169689Skan} 5100169689Skan 5101169689Skan/* Simplify a conditional using a relational operator to an equality 5102169689Skan test if the range information indicates only one value can satisfy 5103169689Skan the original conditional. */ 5104169689Skan 5105169689Skanstatic void 5106169689Skansimplify_cond_using_ranges (tree stmt) 5107169689Skan{ 5108169689Skan tree cond = COND_EXPR_COND (stmt); 5109169689Skan tree op0 = TREE_OPERAND (cond, 0); 5110169689Skan tree op1 = TREE_OPERAND (cond, 1); 5111169689Skan enum tree_code cond_code = TREE_CODE (cond); 5112169689Skan 5113169689Skan if (cond_code != NE_EXPR 5114169689Skan && cond_code != EQ_EXPR 5115169689Skan && TREE_CODE (op0) == SSA_NAME 5116169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 5117169689Skan && is_gimple_min_invariant (op1)) 5118169689Skan { 5119169689Skan value_range_t *vr = get_value_range (op0); 5120169689Skan 5121169689Skan /* If we have range information for OP0, then we might be 5122169689Skan able to simplify this conditional. */ 5123169689Skan if (vr->type == VR_RANGE) 5124169689Skan { 5125169689Skan tree new = test_for_singularity (cond_code, op0, op1, vr); 5126169689Skan 5127169689Skan if (new) 5128169689Skan { 5129169689Skan if (dump_file) 5130169689Skan { 5131169689Skan fprintf (dump_file, "Simplified relational "); 5132169689Skan print_generic_expr (dump_file, cond, 0); 5133169689Skan fprintf (dump_file, " into "); 5134169689Skan } 5135169689Skan 5136169689Skan COND_EXPR_COND (stmt) 5137169689Skan = build2 (EQ_EXPR, boolean_type_node, op0, new); 5138169689Skan update_stmt (stmt); 5139169689Skan 5140169689Skan if (dump_file) 5141169689Skan { 5142169689Skan print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5143169689Skan fprintf (dump_file, "\n"); 5144169689Skan } 5145169689Skan return; 5146169689Skan 5147169689Skan } 5148169689Skan 5149169689Skan /* Try again after inverting the condition. We only deal 5150169689Skan with integral types here, so no need to worry about 5151169689Skan issues with inverting FP comparisons. */ 5152169689Skan cond_code = invert_tree_comparison (cond_code, false); 5153169689Skan new = test_for_singularity (cond_code, op0, op1, vr); 5154169689Skan 5155169689Skan if (new) 5156169689Skan { 5157169689Skan if (dump_file) 5158169689Skan { 5159169689Skan fprintf (dump_file, "Simplified relational "); 5160169689Skan print_generic_expr (dump_file, cond, 0); 5161169689Skan fprintf (dump_file, " into "); 5162169689Skan } 5163169689Skan 5164169689Skan COND_EXPR_COND (stmt) 5165169689Skan = build2 (NE_EXPR, boolean_type_node, op0, new); 5166169689Skan update_stmt (stmt); 5167169689Skan 5168169689Skan if (dump_file) 5169169689Skan { 5170169689Skan print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5171169689Skan fprintf (dump_file, "\n"); 5172169689Skan } 5173169689Skan return; 5174169689Skan 5175169689Skan } 5176169689Skan } 5177169689Skan } 5178169689Skan} 5179169689Skan 5180169689Skan/* Simplify STMT using ranges if possible. */ 5181169689Skan 5182169689Skanvoid 5183169689Skansimplify_stmt_using_ranges (tree stmt) 5184169689Skan{ 5185169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 5186169689Skan { 5187169689Skan tree rhs = TREE_OPERAND (stmt, 1); 5188169689Skan enum tree_code rhs_code = TREE_CODE (rhs); 5189169689Skan 5190169689Skan /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 5191169689Skan and BIT_AND_EXPR respectively if the first operand is greater 5192169689Skan than zero and the second operand is an exact power of two. */ 5193169689Skan if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) 5194169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) 5195169689Skan && integer_pow2p (TREE_OPERAND (rhs, 1))) 5196169689Skan simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); 5197169689Skan 5198169689Skan /* Transform ABS (X) into X or -X as appropriate. */ 5199169689Skan if (rhs_code == ABS_EXPR 5200169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 5201169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) 5202169689Skan simplify_abs_using_ranges (stmt, rhs); 5203169689Skan } 5204169689Skan else if (TREE_CODE (stmt) == COND_EXPR 5205169689Skan && COMPARISON_CLASS_P (COND_EXPR_COND (stmt))) 5206169689Skan { 5207169689Skan simplify_cond_using_ranges (stmt); 5208169689Skan } 5209169689Skan} 5210169689Skan 5211169689Skan/* Stack of dest,src equivalency pairs that need to be restored after 5212169689Skan each attempt to thread a block's incoming edge to an outgoing edge. 5213169689Skan 5214169689Skan A NULL entry is used to mark the end of pairs which need to be 5215169689Skan restored. */ 5216169689Skanstatic VEC(tree,heap) *stack; 5217169689Skan 5218169689Skan/* A trivial wrapper so that we can present the generic jump threading 5219169689Skan code with a simple API for simplifying statements. STMT is the 5220169689Skan statement we want to simplify, WITHIN_STMT provides the location 5221169689Skan for any overflow warnings. */ 5222169689Skan 5223169689Skanstatic tree 5224169689Skansimplify_stmt_for_jump_threading (tree stmt, tree within_stmt) 5225169689Skan{ 5226169689Skan /* We only use VRP information to simplify conditionals. This is 5227169689Skan overly conservative, but it's unclear if doing more would be 5228169689Skan worth the compile time cost. */ 5229169689Skan if (TREE_CODE (stmt) != COND_EXPR) 5230169689Skan return NULL; 5231169689Skan 5232169689Skan return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt); 5233169689Skan} 5234169689Skan 5235169689Skan/* Blocks which have more than one predecessor and more than 5236169689Skan one successor present jump threading opportunities. ie, 5237169689Skan when the block is reached from a specific predecessor, we 5238169689Skan may be able to determine which of the outgoing edges will 5239169689Skan be traversed. When this optimization applies, we are able 5240169689Skan to avoid conditionals at runtime and we may expose secondary 5241169689Skan optimization opportunities. 5242169689Skan 5243169689Skan This routine is effectively a driver for the generic jump 5244169689Skan threading code. It basically just presents the generic code 5245169689Skan with edges that may be suitable for jump threading. 5246169689Skan 5247169689Skan Unlike DOM, we do not iterate VRP if jump threading was successful. 5248169689Skan While iterating may expose new opportunities for VRP, it is expected 5249169689Skan those opportunities would be very limited and the compile time cost 5250169689Skan to expose those opportunities would be significant. 5251169689Skan 5252169689Skan As jump threading opportunities are discovered, they are registered 5253169689Skan for later realization. */ 5254169689Skan 5255169689Skanstatic void 5256169689Skanidentify_jump_threads (void) 5257169689Skan{ 5258169689Skan basic_block bb; 5259169689Skan tree dummy; 5260169689Skan 5261169689Skan /* Ugh. When substituting values earlier in this pass we can 5262169689Skan wipe the dominance information. So rebuild the dominator 5263169689Skan information as we need it within the jump threading code. */ 5264169689Skan calculate_dominance_info (CDI_DOMINATORS); 5265169689Skan 5266169689Skan /* We do not allow VRP information to be used for jump threading 5267169689Skan across a back edge in the CFG. Otherwise it becomes too 5268169689Skan difficult to avoid eliminating loop exit tests. Of course 5269169689Skan EDGE_DFS_BACK is not accurate at this time so we have to 5270169689Skan recompute it. */ 5271169689Skan mark_dfs_back_edges (); 5272169689Skan 5273169689Skan /* Allocate our unwinder stack to unwind any temporary equivalences 5274169689Skan that might be recorded. */ 5275169689Skan stack = VEC_alloc (tree, heap, 20); 5276169689Skan 5277169689Skan /* To avoid lots of silly node creation, we create a single 5278169689Skan conditional and just modify it in-place when attempting to 5279169689Skan thread jumps. */ 5280169689Skan dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL); 5281169689Skan dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL); 5282169689Skan 5283169689Skan /* Walk through all the blocks finding those which present a 5284169689Skan potential jump threading opportunity. We could set this up 5285169689Skan as a dominator walker and record data during the walk, but 5286169689Skan I doubt it's worth the effort for the classes of jump 5287169689Skan threading opportunities we are trying to identify at this 5288169689Skan point in compilation. */ 5289169689Skan FOR_EACH_BB (bb) 5290169689Skan { 5291169689Skan tree last, cond; 5292169689Skan 5293169689Skan /* If the generic jump threading code does not find this block 5294169689Skan interesting, then there is nothing to do. */ 5295169689Skan if (! potentially_threadable_block (bb)) 5296169689Skan continue; 5297169689Skan 5298169689Skan /* We only care about blocks ending in a COND_EXPR. While there 5299169689Skan may be some value in handling SWITCH_EXPR here, I doubt it's 5300169689Skan terribly important. */ 5301169689Skan last = bsi_stmt (bsi_last (bb)); 5302169689Skan if (TREE_CODE (last) != COND_EXPR) 5303169689Skan continue; 5304169689Skan 5305169689Skan /* We're basically looking for any kind of conditional with 5306169689Skan integral type arguments. */ 5307169689Skan cond = COND_EXPR_COND (last); 5308169689Skan if ((TREE_CODE (cond) == SSA_NAME 5309169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (cond))) 5310169689Skan || (COMPARISON_CLASS_P (cond) 5311169689Skan && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 5312169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0))) 5313169689Skan && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME 5314169689Skan || is_gimple_min_invariant (TREE_OPERAND (cond, 1))) 5315169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 5316169689Skan { 5317169689Skan edge_iterator ei; 5318169689Skan edge e; 5319169689Skan 5320169689Skan /* We've got a block with multiple predecessors and multiple 5321169689Skan successors which also ends in a suitable conditional. For 5322169689Skan each predecessor, see if we can thread it to a specific 5323169689Skan successor. */ 5324169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 5325169689Skan { 5326169689Skan /* Do not thread across back edges or abnormal edges 5327169689Skan in the CFG. */ 5328169689Skan if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 5329169689Skan continue; 5330169689Skan 5331169689Skan thread_across_edge (dummy, e, true, 5332169689Skan &stack, 5333169689Skan simplify_stmt_for_jump_threading); 5334169689Skan } 5335169689Skan } 5336169689Skan } 5337169689Skan 5338169689Skan /* We do not actually update the CFG or SSA graphs at this point as 5339169689Skan ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet 5340169689Skan handle ASSERT_EXPRs gracefully. */ 5341169689Skan} 5342169689Skan 5343169689Skan/* We identified all the jump threading opportunities earlier, but could 5344169689Skan not transform the CFG at that time. This routine transforms the 5345169689Skan CFG and arranges for the dominator tree to be rebuilt if necessary. 5346169689Skan 5347169689Skan Note the SSA graph update will occur during the normal TODO 5348169689Skan processing by the pass manager. */ 5349169689Skanstatic void 5350169689Skanfinalize_jump_threads (void) 5351169689Skan{ 5352169689Skan bool cfg_altered = false; 5353169689Skan cfg_altered = thread_through_all_blocks (); 5354169689Skan 5355169689Skan /* If we threaded jumps, then we need to recompute the dominance 5356169689Skan information, to safely do that we must clean up the CFG first. */ 5357169689Skan if (cfg_altered) 5358169689Skan { 5359169689Skan free_dominance_info (CDI_DOMINATORS); 5360169689Skan cleanup_tree_cfg (); 5361169689Skan calculate_dominance_info (CDI_DOMINATORS); 5362169689Skan } 5363169689Skan VEC_free (tree, heap, stack); 5364169689Skan} 5365169689Skan 5366169689Skan 5367169689Skan/* Traverse all the blocks folding conditionals with known ranges. */ 5368169689Skan 5369169689Skanstatic void 5370169689Skanvrp_finalize (void) 5371169689Skan{ 5372169689Skan size_t i; 5373169689Skan prop_value_t *single_val_range; 5374169689Skan bool do_value_subst_p; 5375169689Skan 5376169689Skan if (dump_file) 5377169689Skan { 5378169689Skan fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 5379169689Skan dump_all_value_ranges (dump_file); 5380169689Skan fprintf (dump_file, "\n"); 5381169689Skan } 5382169689Skan 5383169689Skan /* We may have ended with ranges that have exactly one value. Those 5384169689Skan values can be substituted as any other copy/const propagated 5385169689Skan value using substitute_and_fold. */ 5386169689Skan single_val_range = XNEWVEC (prop_value_t, num_ssa_names); 5387169689Skan memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range)); 5388169689Skan 5389169689Skan do_value_subst_p = false; 5390169689Skan for (i = 0; i < num_ssa_names; i++) 5391169689Skan if (vr_value[i] 5392169689Skan && vr_value[i]->type == VR_RANGE 5393169689Skan && vr_value[i]->min == vr_value[i]->max) 5394169689Skan { 5395169689Skan single_val_range[i].value = vr_value[i]->min; 5396169689Skan do_value_subst_p = true; 5397169689Skan } 5398169689Skan 5399169689Skan if (!do_value_subst_p) 5400169689Skan { 5401169689Skan /* We found no single-valued ranges, don't waste time trying to 5402169689Skan do single value substitution in substitute_and_fold. */ 5403169689Skan free (single_val_range); 5404169689Skan single_val_range = NULL; 5405169689Skan } 5406169689Skan 5407169689Skan substitute_and_fold (single_val_range, true); 5408169689Skan 5409169689Skan /* We must identify jump threading opportunities before we release 5410169689Skan the datastructures built by VRP. */ 5411169689Skan identify_jump_threads (); 5412169689Skan 5413169689Skan /* Free allocated memory. */ 5414169689Skan for (i = 0; i < num_ssa_names; i++) 5415169689Skan if (vr_value[i]) 5416169689Skan { 5417169689Skan BITMAP_FREE (vr_value[i]->equiv); 5418169689Skan free (vr_value[i]); 5419169689Skan } 5420169689Skan 5421169689Skan free (single_val_range); 5422169689Skan free (vr_value); 5423169689Skan 5424169689Skan /* So that we can distinguish between VRP data being available 5425169689Skan and not available. */ 5426169689Skan vr_value = NULL; 5427169689Skan} 5428169689Skan 5429169689Skan 5430169689Skan/* Main entry point to VRP (Value Range Propagation). This pass is 5431169689Skan loosely based on J. R. C. Patterson, ``Accurate Static Branch 5432169689Skan Prediction by Value Range Propagation,'' in SIGPLAN Conference on 5433169689Skan Programming Language Design and Implementation, pp. 67-78, 1995. 5434169689Skan Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 5435169689Skan 5436169689Skan This is essentially an SSA-CCP pass modified to deal with ranges 5437169689Skan instead of constants. 5438169689Skan 5439169689Skan While propagating ranges, we may find that two or more SSA name 5440169689Skan have equivalent, though distinct ranges. For instance, 5441169689Skan 5442169689Skan 1 x_9 = p_3->a; 5443169689Skan 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 5444169689Skan 3 if (p_4 == q_2) 5445169689Skan 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 5446169689Skan 5 endif 5447169689Skan 6 if (q_2) 5448169689Skan 5449169689Skan In the code above, pointer p_5 has range [q_2, q_2], but from the 5450169689Skan code we can also determine that p_5 cannot be NULL and, if q_2 had 5451169689Skan a non-varying range, p_5's range should also be compatible with it. 5452169689Skan 5453169689Skan These equivalences are created by two expressions: ASSERT_EXPR and 5454169689Skan copy operations. Since p_5 is an assertion on p_4, and p_4 was the 5455169689Skan result of another assertion, then we can use the fact that p_5 and 5456169689Skan p_4 are equivalent when evaluating p_5's range. 5457169689Skan 5458169689Skan Together with value ranges, we also propagate these equivalences 5459169689Skan between names so that we can take advantage of information from 5460169689Skan multiple ranges when doing final replacement. Note that this 5461169689Skan equivalency relation is transitive but not symmetric. 5462169689Skan 5463169689Skan In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 5464169689Skan cannot assert that q_2 is equivalent to p_5 because q_2 may be used 5465169689Skan in contexts where that assertion does not hold (e.g., in line 6). 5466169689Skan 5467169689Skan TODO, the main difference between this pass and Patterson's is that 5468169689Skan we do not propagate edge probabilities. We only compute whether 5469169689Skan edges can be taken or not. That is, instead of having a spectrum 5470169689Skan of jump probabilities between 0 and 1, we only deal with 0, 1 and 5471169689Skan DON'T KNOW. In the future, it may be worthwhile to propagate 5472169689Skan probabilities to aid branch prediction. */ 5473169689Skan 5474169689Skanstatic unsigned int 5475169689Skanexecute_vrp (void) 5476169689Skan{ 5477169689Skan insert_range_assertions (); 5478169689Skan 5479169689Skan current_loops = loop_optimizer_init (LOOPS_NORMAL); 5480169689Skan if (current_loops) 5481169689Skan scev_initialize (current_loops); 5482169689Skan 5483169689Skan vrp_initialize (); 5484169689Skan ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); 5485169689Skan vrp_finalize (); 5486169689Skan 5487169689Skan if (current_loops) 5488169689Skan { 5489169689Skan scev_finalize (); 5490169689Skan loop_optimizer_finalize (current_loops); 5491169689Skan current_loops = NULL; 5492169689Skan } 5493169689Skan 5494169689Skan /* ASSERT_EXPRs must be removed before finalizing jump threads 5495169689Skan as finalizing jump threads calls the CFG cleanup code which 5496169689Skan does not properly handle ASSERT_EXPRs. */ 5497169689Skan remove_range_assertions (); 5498169689Skan 5499169689Skan /* If we exposed any new variables, go ahead and put them into 5500169689Skan SSA form now, before we handle jump threading. This simplifies 5501169689Skan interactions between rewriting of _DECL nodes into SSA form 5502169689Skan and rewriting SSA_NAME nodes into SSA form after block 5503169689Skan duplication and CFG manipulation. */ 5504169689Skan update_ssa (TODO_update_ssa); 5505169689Skan 5506169689Skan finalize_jump_threads (); 5507169689Skan return 0; 5508169689Skan} 5509169689Skan 5510169689Skanstatic bool 5511169689Skangate_vrp (void) 5512169689Skan{ 5513169689Skan return flag_tree_vrp != 0; 5514169689Skan} 5515169689Skan 5516169689Skanstruct tree_opt_pass pass_vrp = 5517169689Skan{ 5518169689Skan "vrp", /* name */ 5519169689Skan gate_vrp, /* gate */ 5520169689Skan execute_vrp, /* execute */ 5521169689Skan NULL, /* sub */ 5522169689Skan NULL, /* next */ 5523169689Skan 0, /* static_pass_number */ 5524169689Skan TV_TREE_VRP, /* tv_id */ 5525169689Skan PROP_ssa | PROP_alias, /* properties_required */ 5526169689Skan 0, /* properties_provided */ 5527169689Skan PROP_smt_usage, /* properties_destroyed */ 5528169689Skan 0, /* todo_flags_start */ 5529169689Skan TODO_cleanup_cfg 5530169689Skan | TODO_ggc_collect 5531169689Skan | TODO_verify_ssa 5532169689Skan | TODO_dump_func 5533169689Skan | TODO_update_ssa 5534169689Skan | TODO_update_smt_usage, /* todo_flags_finish */ 5535169689Skan 0 /* letter */ 5536169689Skan}; 5537