tree-vrp.c revision 171825
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 2512169689Skan /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of 2513169689Skan negative_overflow_infinity and positive_overflow_infinity, 2514169689Skan because we have concluded that the loop probably does not 2515169689Skan wrap. */ 2516169689Skan 2517169689Skan type = TREE_TYPE (var); 2518169689Skan if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type)) 2519169689Skan tmin = lower_bound_in_type (type, type); 2520169689Skan else 2521169689Skan tmin = TYPE_MIN_VALUE (type); 2522169689Skan if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type)) 2523169689Skan tmax = upper_bound_in_type (type, type); 2524169689Skan else 2525169689Skan tmax = TYPE_MAX_VALUE (type); 2526169689Skan 2527169689Skan if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2528169689Skan { 2529169689Skan min = tmin; 2530169689Skan max = tmax; 2531169689Skan 2532169689Skan /* For VARYING or UNDEFINED ranges, just about anything we get 2533169689Skan from scalar evolutions should be better. */ 2534169689Skan 2535169689Skan if (dir == EV_DIR_DECREASES) 2536169689Skan max = init; 2537169689Skan else 2538169689Skan min = init; 2539169689Skan 2540169689Skan /* If we would create an invalid range, then just assume we 2541169689Skan know absolutely nothing. This may be over-conservative, 2542169689Skan but it's clearly safe, and should happen only in unreachable 2543169689Skan parts of code, or for invalid programs. */ 2544169689Skan if (compare_values (min, max) == 1) 2545169689Skan return; 2546169689Skan 2547169689Skan set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2548169689Skan } 2549169689Skan else if (vr->type == VR_RANGE) 2550169689Skan { 2551169689Skan min = vr->min; 2552169689Skan max = vr->max; 2553169689Skan 2554169689Skan if (dir == EV_DIR_DECREASES) 2555169689Skan { 2556169689Skan /* INIT is the maximum value. If INIT is lower than VR->MAX 2557169689Skan but no smaller than VR->MIN, set VR->MAX to INIT. */ 2558169689Skan if (compare_values (init, max) == -1) 2559169689Skan { 2560169689Skan max = init; 2561169689Skan 2562169689Skan /* If we just created an invalid range with the minimum 2563169689Skan greater than the maximum, we fail conservatively. 2564169689Skan This should happen only in unreachable 2565169689Skan parts of code, or for invalid programs. */ 2566169689Skan if (compare_values (min, max) == 1) 2567169689Skan return; 2568169689Skan } 2569171825Skan 2570171825Skan /* According to the loop information, the variable does not 2571171825Skan overflow. If we think it does, probably because of an 2572171825Skan overflow due to arithmetic on a different INF value, 2573171825Skan reset now. */ 2574171825Skan if (is_negative_overflow_infinity (min)) 2575171825Skan min = tmin; 2576169689Skan } 2577169689Skan else 2578169689Skan { 2579169689Skan /* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */ 2580169689Skan if (compare_values (init, min) == 1) 2581169689Skan { 2582169689Skan min = init; 2583169689Skan 2584169689Skan /* Again, avoid creating invalid range by failing. */ 2585169689Skan if (compare_values (min, max) == 1) 2586169689Skan return; 2587169689Skan } 2588171825Skan 2589171825Skan if (is_positive_overflow_infinity (max)) 2590171825Skan max = tmax; 2591169689Skan } 2592169689Skan 2593169689Skan set_value_range (vr, VR_RANGE, min, max, vr->equiv); 2594169689Skan } 2595169689Skan} 2596169689Skan 2597171825Skan/* Return true if VAR may overflow at STMT. This checks any available 2598171825Skan loop information to see if we can determine that VAR does not 2599171825Skan overflow. */ 2600169689Skan 2601171825Skanstatic bool 2602171825Skanvrp_var_may_overflow (tree var, tree stmt) 2603171825Skan{ 2604171825Skan struct loop *l; 2605171825Skan tree chrec, init, step; 2606171825Skan 2607171825Skan if (current_loops == NULL) 2608171825Skan return true; 2609171825Skan 2610171825Skan l = loop_containing_stmt (stmt); 2611171825Skan if (l == NULL) 2612171825Skan return true; 2613171825Skan 2614171825Skan chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var)); 2615171825Skan if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2616171825Skan return true; 2617171825Skan 2618171825Skan init = initial_condition_in_loop_num (chrec, l->num); 2619171825Skan step = evolution_part_in_loop_num (chrec, l->num); 2620171825Skan 2621171825Skan if (step == NULL_TREE 2622171825Skan || !is_gimple_min_invariant (step) 2623171825Skan || !valid_value_p (init)) 2624171825Skan return true; 2625171825Skan 2626171825Skan /* If we get here, we know something useful about VAR based on the 2627171825Skan loop information. If it wraps, it may overflow. */ 2628171825Skan 2629171825Skan if (scev_probably_wraps_p (init, step, stmt, 2630171825Skan current_loops->parray[CHREC_VARIABLE (chrec)], 2631171825Skan true)) 2632171825Skan return true; 2633171825Skan 2634171825Skan if (dump_file && (dump_flags & TDF_DETAILS) != 0) 2635171825Skan { 2636171825Skan print_generic_expr (dump_file, var, 0); 2637171825Skan fprintf (dump_file, ": loop information indicates does not overflow\n"); 2638171825Skan } 2639171825Skan 2640171825Skan return false; 2641171825Skan} 2642171825Skan 2643171825Skan 2644169689Skan/* Given two numeric value ranges VR0, VR1 and a comparison code COMP: 2645169689Skan 2646169689Skan - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for 2647169689Skan all the values in the ranges. 2648169689Skan 2649169689Skan - Return BOOLEAN_FALSE_NODE if the comparison always returns false. 2650169689Skan 2651169689Skan - Return NULL_TREE if it is not always possible to determine the 2652169689Skan value of the comparison. 2653169689Skan 2654169689Skan Also set *STRICT_OVERFLOW_P to indicate whether a range with an 2655169689Skan overflow infinity was used in the test. */ 2656169689Skan 2657169689Skan 2658169689Skanstatic tree 2659169689Skancompare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1, 2660169689Skan bool *strict_overflow_p) 2661169689Skan{ 2662169689Skan /* VARYING or UNDEFINED ranges cannot be compared. */ 2663169689Skan if (vr0->type == VR_VARYING 2664169689Skan || vr0->type == VR_UNDEFINED 2665169689Skan || vr1->type == VR_VARYING 2666169689Skan || vr1->type == VR_UNDEFINED) 2667169689Skan return NULL_TREE; 2668169689Skan 2669169689Skan /* Anti-ranges need to be handled separately. */ 2670169689Skan if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 2671169689Skan { 2672169689Skan /* If both are anti-ranges, then we cannot compute any 2673169689Skan comparison. */ 2674169689Skan if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 2675169689Skan return NULL_TREE; 2676169689Skan 2677169689Skan /* These comparisons are never statically computable. */ 2678169689Skan if (comp == GT_EXPR 2679169689Skan || comp == GE_EXPR 2680169689Skan || comp == LT_EXPR 2681169689Skan || comp == LE_EXPR) 2682169689Skan return NULL_TREE; 2683169689Skan 2684169689Skan /* Equality can be computed only between a range and an 2685169689Skan anti-range. ~[VAL1, VAL2] == [VAL1, VAL2] is always false. */ 2686169689Skan if (vr0->type == VR_RANGE) 2687169689Skan { 2688169689Skan /* To simplify processing, make VR0 the anti-range. */ 2689169689Skan value_range_t *tmp = vr0; 2690169689Skan vr0 = vr1; 2691169689Skan vr1 = tmp; 2692169689Skan } 2693169689Skan 2694169689Skan gcc_assert (comp == NE_EXPR || comp == EQ_EXPR); 2695169689Skan 2696169689Skan if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0 2697169689Skan && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0) 2698169689Skan return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2699169689Skan 2700169689Skan return NULL_TREE; 2701169689Skan } 2702169689Skan 2703169689Skan if (!usable_range_p (vr0, strict_overflow_p) 2704169689Skan || !usable_range_p (vr1, strict_overflow_p)) 2705169689Skan return NULL_TREE; 2706169689Skan 2707169689Skan /* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the 2708169689Skan operands around and change the comparison code. */ 2709169689Skan if (comp == GT_EXPR || comp == GE_EXPR) 2710169689Skan { 2711169689Skan value_range_t *tmp; 2712169689Skan comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR; 2713169689Skan tmp = vr0; 2714169689Skan vr0 = vr1; 2715169689Skan vr1 = tmp; 2716169689Skan } 2717169689Skan 2718169689Skan if (comp == EQ_EXPR) 2719169689Skan { 2720169689Skan /* Equality may only be computed if both ranges represent 2721169689Skan exactly one value. */ 2722169689Skan if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0 2723169689Skan && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0) 2724169689Skan { 2725169689Skan int cmp_min = compare_values_warnv (vr0->min, vr1->min, 2726169689Skan strict_overflow_p); 2727169689Skan int cmp_max = compare_values_warnv (vr0->max, vr1->max, 2728169689Skan strict_overflow_p); 2729169689Skan if (cmp_min == 0 && cmp_max == 0) 2730169689Skan return boolean_true_node; 2731169689Skan else if (cmp_min != -2 && cmp_max != -2) 2732169689Skan return boolean_false_node; 2733169689Skan } 2734169689Skan /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */ 2735169689Skan else if (compare_values_warnv (vr0->min, vr1->max, 2736169689Skan strict_overflow_p) == 1 2737169689Skan || compare_values_warnv (vr1->min, vr0->max, 2738169689Skan strict_overflow_p) == 1) 2739169689Skan return boolean_false_node; 2740169689Skan 2741169689Skan return NULL_TREE; 2742169689Skan } 2743169689Skan else if (comp == NE_EXPR) 2744169689Skan { 2745169689Skan int cmp1, cmp2; 2746169689Skan 2747169689Skan /* If VR0 is completely to the left or completely to the right 2748169689Skan of VR1, they are always different. Notice that we need to 2749169689Skan make sure that both comparisons yield similar results to 2750169689Skan avoid comparing values that cannot be compared at 2751169689Skan compile-time. */ 2752169689Skan cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2753169689Skan cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2754169689Skan if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1)) 2755169689Skan return boolean_true_node; 2756169689Skan 2757169689Skan /* If VR0 and VR1 represent a single value and are identical, 2758169689Skan return false. */ 2759169689Skan else if (compare_values_warnv (vr0->min, vr0->max, 2760169689Skan strict_overflow_p) == 0 2761169689Skan && compare_values_warnv (vr1->min, vr1->max, 2762169689Skan strict_overflow_p) == 0 2763169689Skan && compare_values_warnv (vr0->min, vr1->min, 2764169689Skan strict_overflow_p) == 0 2765169689Skan && compare_values_warnv (vr0->max, vr1->max, 2766169689Skan strict_overflow_p) == 0) 2767169689Skan return boolean_false_node; 2768169689Skan 2769169689Skan /* Otherwise, they may or may not be different. */ 2770169689Skan else 2771169689Skan return NULL_TREE; 2772169689Skan } 2773169689Skan else if (comp == LT_EXPR || comp == LE_EXPR) 2774169689Skan { 2775169689Skan int tst; 2776169689Skan 2777169689Skan /* If VR0 is to the left of VR1, return true. */ 2778169689Skan tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p); 2779169689Skan if ((comp == LT_EXPR && tst == -1) 2780169689Skan || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2781169689Skan { 2782169689Skan if (overflow_infinity_range_p (vr0) 2783169689Skan || overflow_infinity_range_p (vr1)) 2784169689Skan *strict_overflow_p = true; 2785169689Skan return boolean_true_node; 2786169689Skan } 2787169689Skan 2788169689Skan /* If VR0 is to the right of VR1, return false. */ 2789169689Skan tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p); 2790169689Skan if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2791169689Skan || (comp == LE_EXPR && tst == 1)) 2792169689Skan { 2793169689Skan if (overflow_infinity_range_p (vr0) 2794169689Skan || overflow_infinity_range_p (vr1)) 2795169689Skan *strict_overflow_p = true; 2796169689Skan return boolean_false_node; 2797169689Skan } 2798169689Skan 2799169689Skan /* Otherwise, we don't know. */ 2800169689Skan return NULL_TREE; 2801169689Skan } 2802169689Skan 2803169689Skan gcc_unreachable (); 2804169689Skan} 2805169689Skan 2806169689Skan 2807169689Skan/* Given a value range VR, a value VAL and a comparison code COMP, return 2808169689Skan BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the 2809169689Skan values in VR. Return BOOLEAN_FALSE_NODE if the comparison 2810169689Skan always returns false. Return NULL_TREE if it is not always 2811169689Skan possible to determine the value of the comparison. Also set 2812169689Skan *STRICT_OVERFLOW_P to indicate whether a range with an overflow 2813169689Skan infinity was used in the test. */ 2814169689Skan 2815169689Skanstatic tree 2816169689Skancompare_range_with_value (enum tree_code comp, value_range_t *vr, tree val, 2817169689Skan bool *strict_overflow_p) 2818169689Skan{ 2819169689Skan if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED) 2820169689Skan return NULL_TREE; 2821169689Skan 2822169689Skan /* Anti-ranges need to be handled separately. */ 2823169689Skan if (vr->type == VR_ANTI_RANGE) 2824169689Skan { 2825169689Skan /* For anti-ranges, the only predicates that we can compute at 2826169689Skan compile time are equality and inequality. */ 2827169689Skan if (comp == GT_EXPR 2828169689Skan || comp == GE_EXPR 2829169689Skan || comp == LT_EXPR 2830169689Skan || comp == LE_EXPR) 2831169689Skan return NULL_TREE; 2832169689Skan 2833169689Skan /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */ 2834169689Skan if (value_inside_range (val, vr) == 1) 2835169689Skan return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node; 2836169689Skan 2837169689Skan return NULL_TREE; 2838169689Skan } 2839169689Skan 2840169689Skan if (!usable_range_p (vr, strict_overflow_p)) 2841169689Skan return NULL_TREE; 2842169689Skan 2843169689Skan if (comp == EQ_EXPR) 2844169689Skan { 2845169689Skan /* EQ_EXPR may only be computed if VR represents exactly 2846169689Skan one value. */ 2847169689Skan if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0) 2848169689Skan { 2849169689Skan int cmp = compare_values_warnv (vr->min, val, strict_overflow_p); 2850169689Skan if (cmp == 0) 2851169689Skan return boolean_true_node; 2852169689Skan else if (cmp == -1 || cmp == 1 || cmp == 2) 2853169689Skan return boolean_false_node; 2854169689Skan } 2855169689Skan else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1 2856169689Skan || compare_values_warnv (vr->max, val, strict_overflow_p) == -1) 2857169689Skan return boolean_false_node; 2858169689Skan 2859169689Skan return NULL_TREE; 2860169689Skan } 2861169689Skan else if (comp == NE_EXPR) 2862169689Skan { 2863169689Skan /* If VAL is not inside VR, then they are always different. */ 2864169689Skan if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1 2865169689Skan || compare_values_warnv (vr->min, val, strict_overflow_p) == 1) 2866169689Skan return boolean_true_node; 2867169689Skan 2868169689Skan /* If VR represents exactly one value equal to VAL, then return 2869169689Skan false. */ 2870169689Skan if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0 2871169689Skan && compare_values_warnv (vr->min, val, strict_overflow_p) == 0) 2872169689Skan return boolean_false_node; 2873169689Skan 2874169689Skan /* Otherwise, they may or may not be different. */ 2875169689Skan return NULL_TREE; 2876169689Skan } 2877169689Skan else if (comp == LT_EXPR || comp == LE_EXPR) 2878169689Skan { 2879169689Skan int tst; 2880169689Skan 2881169689Skan /* If VR is to the left of VAL, return true. */ 2882169689Skan tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2883169689Skan if ((comp == LT_EXPR && tst == -1) 2884169689Skan || (comp == LE_EXPR && (tst == -1 || tst == 0))) 2885169689Skan { 2886169689Skan if (overflow_infinity_range_p (vr)) 2887169689Skan *strict_overflow_p = true; 2888169689Skan return boolean_true_node; 2889169689Skan } 2890169689Skan 2891169689Skan /* If VR is to the right of VAL, return false. */ 2892169689Skan tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2893169689Skan if ((comp == LT_EXPR && (tst == 0 || tst == 1)) 2894169689Skan || (comp == LE_EXPR && tst == 1)) 2895169689Skan { 2896169689Skan if (overflow_infinity_range_p (vr)) 2897169689Skan *strict_overflow_p = true; 2898169689Skan return boolean_false_node; 2899169689Skan } 2900169689Skan 2901169689Skan /* Otherwise, we don't know. */ 2902169689Skan return NULL_TREE; 2903169689Skan } 2904169689Skan else if (comp == GT_EXPR || comp == GE_EXPR) 2905169689Skan { 2906169689Skan int tst; 2907169689Skan 2908169689Skan /* If VR is to the right of VAL, return true. */ 2909169689Skan tst = compare_values_warnv (vr->min, val, strict_overflow_p); 2910169689Skan if ((comp == GT_EXPR && tst == 1) 2911169689Skan || (comp == GE_EXPR && (tst == 0 || tst == 1))) 2912169689Skan { 2913169689Skan if (overflow_infinity_range_p (vr)) 2914169689Skan *strict_overflow_p = true; 2915169689Skan return boolean_true_node; 2916169689Skan } 2917169689Skan 2918169689Skan /* If VR is to the left of VAL, return false. */ 2919169689Skan tst = compare_values_warnv (vr->max, val, strict_overflow_p); 2920169689Skan if ((comp == GT_EXPR && (tst == -1 || tst == 0)) 2921169689Skan || (comp == GE_EXPR && tst == -1)) 2922169689Skan { 2923169689Skan if (overflow_infinity_range_p (vr)) 2924169689Skan *strict_overflow_p = true; 2925169689Skan return boolean_false_node; 2926169689Skan } 2927169689Skan 2928169689Skan /* Otherwise, we don't know. */ 2929169689Skan return NULL_TREE; 2930169689Skan } 2931169689Skan 2932169689Skan gcc_unreachable (); 2933169689Skan} 2934169689Skan 2935169689Skan 2936169689Skan/* Debugging dumps. */ 2937169689Skan 2938169689Skanvoid dump_value_range (FILE *, value_range_t *); 2939169689Skanvoid debug_value_range (value_range_t *); 2940169689Skanvoid dump_all_value_ranges (FILE *); 2941169689Skanvoid debug_all_value_ranges (void); 2942169689Skanvoid dump_vr_equiv (FILE *, bitmap); 2943169689Skanvoid debug_vr_equiv (bitmap); 2944169689Skan 2945169689Skan 2946169689Skan/* Dump value range VR to FILE. */ 2947169689Skan 2948169689Skanvoid 2949169689Skandump_value_range (FILE *file, value_range_t *vr) 2950169689Skan{ 2951169689Skan if (vr == NULL) 2952169689Skan fprintf (file, "[]"); 2953169689Skan else if (vr->type == VR_UNDEFINED) 2954169689Skan fprintf (file, "UNDEFINED"); 2955169689Skan else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE) 2956169689Skan { 2957169689Skan tree type = TREE_TYPE (vr->min); 2958169689Skan 2959169689Skan fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); 2960169689Skan 2961169689Skan if (is_negative_overflow_infinity (vr->min)) 2962169689Skan fprintf (file, "-INF(OVF)"); 2963169689Skan else if (INTEGRAL_TYPE_P (type) 2964169689Skan && !TYPE_UNSIGNED (type) 2965169689Skan && vrp_val_is_min (vr->min)) 2966169689Skan fprintf (file, "-INF"); 2967169689Skan else 2968169689Skan print_generic_expr (file, vr->min, 0); 2969169689Skan 2970169689Skan fprintf (file, ", "); 2971169689Skan 2972169689Skan if (is_positive_overflow_infinity (vr->max)) 2973169689Skan fprintf (file, "+INF(OVF)"); 2974169689Skan else if (INTEGRAL_TYPE_P (type) 2975169689Skan && vrp_val_is_max (vr->max)) 2976169689Skan fprintf (file, "+INF"); 2977169689Skan else 2978169689Skan print_generic_expr (file, vr->max, 0); 2979169689Skan 2980169689Skan fprintf (file, "]"); 2981169689Skan 2982169689Skan if (vr->equiv) 2983169689Skan { 2984169689Skan bitmap_iterator bi; 2985169689Skan unsigned i, c = 0; 2986169689Skan 2987169689Skan fprintf (file, " EQUIVALENCES: { "); 2988169689Skan 2989169689Skan EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi) 2990169689Skan { 2991169689Skan print_generic_expr (file, ssa_name (i), 0); 2992169689Skan fprintf (file, " "); 2993169689Skan c++; 2994169689Skan } 2995169689Skan 2996169689Skan fprintf (file, "} (%u elements)", c); 2997169689Skan } 2998169689Skan } 2999169689Skan else if (vr->type == VR_VARYING) 3000169689Skan fprintf (file, "VARYING"); 3001169689Skan else 3002169689Skan fprintf (file, "INVALID RANGE"); 3003169689Skan} 3004169689Skan 3005169689Skan 3006169689Skan/* Dump value range VR to stderr. */ 3007169689Skan 3008169689Skanvoid 3009169689Skandebug_value_range (value_range_t *vr) 3010169689Skan{ 3011169689Skan dump_value_range (stderr, vr); 3012169689Skan fprintf (stderr, "\n"); 3013169689Skan} 3014169689Skan 3015169689Skan 3016169689Skan/* Dump value ranges of all SSA_NAMEs to FILE. */ 3017169689Skan 3018169689Skanvoid 3019169689Skandump_all_value_ranges (FILE *file) 3020169689Skan{ 3021169689Skan size_t i; 3022169689Skan 3023169689Skan for (i = 0; i < num_ssa_names; i++) 3024169689Skan { 3025169689Skan if (vr_value[i]) 3026169689Skan { 3027169689Skan print_generic_expr (file, ssa_name (i), 0); 3028169689Skan fprintf (file, ": "); 3029169689Skan dump_value_range (file, vr_value[i]); 3030169689Skan fprintf (file, "\n"); 3031169689Skan } 3032169689Skan } 3033169689Skan 3034169689Skan fprintf (file, "\n"); 3035169689Skan} 3036169689Skan 3037169689Skan 3038169689Skan/* Dump all value ranges to stderr. */ 3039169689Skan 3040169689Skanvoid 3041169689Skandebug_all_value_ranges (void) 3042169689Skan{ 3043169689Skan dump_all_value_ranges (stderr); 3044169689Skan} 3045169689Skan 3046169689Skan 3047169689Skan/* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V, 3048169689Skan create a new SSA name N and return the assertion assignment 3049169689Skan 'V = ASSERT_EXPR <V, V OP W>'. */ 3050169689Skan 3051169689Skanstatic tree 3052169689Skanbuild_assert_expr_for (tree cond, tree v) 3053169689Skan{ 3054169689Skan tree n, assertion; 3055169689Skan 3056169689Skan gcc_assert (TREE_CODE (v) == SSA_NAME); 3057169689Skan n = duplicate_ssa_name (v, NULL_TREE); 3058169689Skan 3059169689Skan if (COMPARISON_CLASS_P (cond)) 3060169689Skan { 3061169689Skan tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond); 3062169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a); 3063169689Skan } 3064169689Skan else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 3065169689Skan { 3066169689Skan /* Given !V, build the assignment N = false. */ 3067169689Skan tree op0 = TREE_OPERAND (cond, 0); 3068169689Skan gcc_assert (op0 == v); 3069169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node); 3070169689Skan } 3071169689Skan else if (TREE_CODE (cond) == SSA_NAME) 3072169689Skan { 3073169689Skan /* Given V, build the assignment N = true. */ 3074169689Skan gcc_assert (v == cond); 3075169689Skan assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node); 3076169689Skan } 3077169689Skan else 3078169689Skan gcc_unreachable (); 3079169689Skan 3080169689Skan SSA_NAME_DEF_STMT (n) = assertion; 3081169689Skan 3082169689Skan /* The new ASSERT_EXPR, creates a new SSA name that replaces the 3083169689Skan operand of the ASSERT_EXPR. Register the new name and the old one 3084169689Skan in the replacement table so that we can fix the SSA web after 3085169689Skan adding all the ASSERT_EXPRs. */ 3086169689Skan register_new_name_mapping (n, v); 3087169689Skan 3088169689Skan return assertion; 3089169689Skan} 3090169689Skan 3091169689Skan 3092169689Skan/* Return false if EXPR is a predicate expression involving floating 3093169689Skan point values. */ 3094169689Skan 3095169689Skanstatic inline bool 3096169689Skanfp_predicate (tree expr) 3097169689Skan{ 3098169689Skan return (COMPARISON_CLASS_P (expr) 3099169689Skan && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)))); 3100169689Skan} 3101169689Skan 3102169689Skan 3103169689Skan/* If the range of values taken by OP can be inferred after STMT executes, 3104169689Skan return the comparison code (COMP_CODE_P) and value (VAL_P) that 3105169689Skan describes the inferred range. Return true if a range could be 3106169689Skan inferred. */ 3107169689Skan 3108169689Skanstatic bool 3109169689Skaninfer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p) 3110169689Skan{ 3111169689Skan *val_p = NULL_TREE; 3112169689Skan *comp_code_p = ERROR_MARK; 3113169689Skan 3114169689Skan /* Do not attempt to infer anything in names that flow through 3115169689Skan abnormal edges. */ 3116169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 3117169689Skan return false; 3118169689Skan 3119169689Skan /* Similarly, don't infer anything from statements that may throw 3120169689Skan exceptions. */ 3121169689Skan if (tree_could_throw_p (stmt)) 3122169689Skan return false; 3123169689Skan 3124169689Skan /* If STMT is the last statement of a basic block with no 3125169689Skan successors, there is no point inferring anything about any of its 3126169689Skan operands. We would not be able to find a proper insertion point 3127169689Skan for the assertion, anyway. */ 3128169689Skan if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0) 3129169689Skan return false; 3130169689Skan 3131169689Skan /* We can only assume that a pointer dereference will yield 3132169689Skan non-NULL if -fdelete-null-pointer-checks is enabled. */ 3133169689Skan if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op))) 3134169689Skan { 3135169689Skan bool is_store; 3136169689Skan unsigned num_uses, num_derefs; 3137169689Skan 3138169689Skan count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 3139169689Skan if (num_derefs > 0) 3140169689Skan { 3141169689Skan *val_p = build_int_cst (TREE_TYPE (op), 0); 3142169689Skan *comp_code_p = NE_EXPR; 3143169689Skan return true; 3144169689Skan } 3145169689Skan } 3146169689Skan 3147169689Skan return false; 3148169689Skan} 3149169689Skan 3150169689Skan 3151169689Skanvoid dump_asserts_for (FILE *, tree); 3152169689Skanvoid debug_asserts_for (tree); 3153169689Skanvoid dump_all_asserts (FILE *); 3154169689Skanvoid debug_all_asserts (void); 3155169689Skan 3156169689Skan/* Dump all the registered assertions for NAME to FILE. */ 3157169689Skan 3158169689Skanvoid 3159169689Skandump_asserts_for (FILE *file, tree name) 3160169689Skan{ 3161169689Skan assert_locus_t loc; 3162169689Skan 3163169689Skan fprintf (file, "Assertions to be inserted for "); 3164169689Skan print_generic_expr (file, name, 0); 3165169689Skan fprintf (file, "\n"); 3166169689Skan 3167169689Skan loc = asserts_for[SSA_NAME_VERSION (name)]; 3168169689Skan while (loc) 3169169689Skan { 3170169689Skan fprintf (file, "\t"); 3171169689Skan print_generic_expr (file, bsi_stmt (loc->si), 0); 3172169689Skan fprintf (file, "\n\tBB #%d", loc->bb->index); 3173169689Skan if (loc->e) 3174169689Skan { 3175169689Skan fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index, 3176169689Skan loc->e->dest->index); 3177169689Skan dump_edge_info (file, loc->e, 0); 3178169689Skan } 3179169689Skan fprintf (file, "\n\tPREDICATE: "); 3180169689Skan print_generic_expr (file, name, 0); 3181169689Skan fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]); 3182169689Skan print_generic_expr (file, loc->val, 0); 3183169689Skan fprintf (file, "\n\n"); 3184169689Skan loc = loc->next; 3185169689Skan } 3186169689Skan 3187169689Skan fprintf (file, "\n"); 3188169689Skan} 3189169689Skan 3190169689Skan 3191169689Skan/* Dump all the registered assertions for NAME to stderr. */ 3192169689Skan 3193169689Skanvoid 3194169689Skandebug_asserts_for (tree name) 3195169689Skan{ 3196169689Skan dump_asserts_for (stderr, name); 3197169689Skan} 3198169689Skan 3199169689Skan 3200169689Skan/* Dump all the registered assertions for all the names to FILE. */ 3201169689Skan 3202169689Skanvoid 3203169689Skandump_all_asserts (FILE *file) 3204169689Skan{ 3205169689Skan unsigned i; 3206169689Skan bitmap_iterator bi; 3207169689Skan 3208169689Skan fprintf (file, "\nASSERT_EXPRs to be inserted\n\n"); 3209169689Skan EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3210169689Skan dump_asserts_for (file, ssa_name (i)); 3211169689Skan fprintf (file, "\n"); 3212169689Skan} 3213169689Skan 3214169689Skan 3215169689Skan/* Dump all the registered assertions for all the names to stderr. */ 3216169689Skan 3217169689Skanvoid 3218169689Skandebug_all_asserts (void) 3219169689Skan{ 3220169689Skan dump_all_asserts (stderr); 3221169689Skan} 3222169689Skan 3223169689Skan 3224169689Skan/* If NAME doesn't have an ASSERT_EXPR registered for asserting 3225169689Skan 'NAME COMP_CODE VAL' at a location that dominates block BB or 3226169689Skan E->DEST, then register this location as a possible insertion point 3227169689Skan for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>. 3228169689Skan 3229169689Skan BB, E and SI provide the exact insertion point for the new 3230169689Skan ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted 3231169689Skan on edge E. Otherwise, if E is NULL, the ASSERT_EXPR is inserted on 3232169689Skan BB. If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E 3233169689Skan must not be NULL. */ 3234169689Skan 3235169689Skanstatic void 3236169689Skanregister_new_assert_for (tree name, 3237169689Skan enum tree_code comp_code, 3238169689Skan tree val, 3239169689Skan basic_block bb, 3240169689Skan edge e, 3241169689Skan block_stmt_iterator si) 3242169689Skan{ 3243169689Skan assert_locus_t n, loc, last_loc; 3244169689Skan bool found; 3245169689Skan basic_block dest_bb; 3246169689Skan 3247169689Skan#if defined ENABLE_CHECKING 3248169689Skan gcc_assert (bb == NULL || e == NULL); 3249169689Skan 3250169689Skan if (e == NULL) 3251169689Skan gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR 3252169689Skan && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR); 3253169689Skan#endif 3254169689Skan 3255169689Skan /* The new assertion A will be inserted at BB or E. We need to 3256169689Skan determine if the new location is dominated by a previously 3257169689Skan registered location for A. If we are doing an edge insertion, 3258169689Skan assume that A will be inserted at E->DEST. Note that this is not 3259169689Skan necessarily true. 3260169689Skan 3261169689Skan If E is a critical edge, it will be split. But even if E is 3262169689Skan split, the new block will dominate the same set of blocks that 3263169689Skan E->DEST dominates. 3264169689Skan 3265169689Skan The reverse, however, is not true, blocks dominated by E->DEST 3266169689Skan will not be dominated by the new block created to split E. So, 3267169689Skan if the insertion location is on a critical edge, we will not use 3268169689Skan the new location to move another assertion previously registered 3269169689Skan at a block dominated by E->DEST. */ 3270169689Skan dest_bb = (bb) ? bb : e->dest; 3271169689Skan 3272169689Skan /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and 3273169689Skan VAL at a block dominating DEST_BB, then we don't need to insert a new 3274169689Skan one. Similarly, if the same assertion already exists at a block 3275169689Skan dominated by DEST_BB and the new location is not on a critical 3276169689Skan edge, then update the existing location for the assertion (i.e., 3277169689Skan move the assertion up in the dominance tree). 3278169689Skan 3279169689Skan Note, this is implemented as a simple linked list because there 3280169689Skan should not be more than a handful of assertions registered per 3281169689Skan name. If this becomes a performance problem, a table hashed by 3282169689Skan COMP_CODE and VAL could be implemented. */ 3283169689Skan loc = asserts_for[SSA_NAME_VERSION (name)]; 3284169689Skan last_loc = loc; 3285169689Skan found = false; 3286169689Skan while (loc) 3287169689Skan { 3288169689Skan if (loc->comp_code == comp_code 3289169689Skan && (loc->val == val 3290169689Skan || operand_equal_p (loc->val, val, 0))) 3291169689Skan { 3292169689Skan /* If the assertion NAME COMP_CODE VAL has already been 3293169689Skan registered at a basic block that dominates DEST_BB, then 3294169689Skan we don't need to insert the same assertion again. Note 3295169689Skan that we don't check strict dominance here to avoid 3296169689Skan replicating the same assertion inside the same basic 3297169689Skan block more than once (e.g., when a pointer is 3298169689Skan dereferenced several times inside a block). 3299169689Skan 3300169689Skan An exception to this rule are edge insertions. If the 3301169689Skan new assertion is to be inserted on edge E, then it will 3302169689Skan dominate all the other insertions that we may want to 3303169689Skan insert in DEST_BB. So, if we are doing an edge 3304169689Skan insertion, don't do this dominance check. */ 3305169689Skan if (e == NULL 3306169689Skan && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb)) 3307169689Skan return; 3308169689Skan 3309169689Skan /* Otherwise, if E is not a critical edge and DEST_BB 3310169689Skan dominates the existing location for the assertion, move 3311169689Skan the assertion up in the dominance tree by updating its 3312169689Skan location information. */ 3313169689Skan if ((e == NULL || !EDGE_CRITICAL_P (e)) 3314169689Skan && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb)) 3315169689Skan { 3316169689Skan loc->bb = dest_bb; 3317169689Skan loc->e = e; 3318169689Skan loc->si = si; 3319169689Skan return; 3320169689Skan } 3321169689Skan } 3322169689Skan 3323169689Skan /* Update the last node of the list and move to the next one. */ 3324169689Skan last_loc = loc; 3325169689Skan loc = loc->next; 3326169689Skan } 3327169689Skan 3328169689Skan /* If we didn't find an assertion already registered for 3329169689Skan NAME COMP_CODE VAL, add a new one at the end of the list of 3330169689Skan assertions associated with NAME. */ 3331169689Skan n = XNEW (struct assert_locus_d); 3332169689Skan n->bb = dest_bb; 3333169689Skan n->e = e; 3334169689Skan n->si = si; 3335169689Skan n->comp_code = comp_code; 3336169689Skan n->val = val; 3337169689Skan n->next = NULL; 3338169689Skan 3339169689Skan if (last_loc) 3340169689Skan last_loc->next = n; 3341169689Skan else 3342169689Skan asserts_for[SSA_NAME_VERSION (name)] = n; 3343169689Skan 3344169689Skan bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name)); 3345169689Skan} 3346169689Skan 3347169689Skan 3348169689Skan/* Try to register an edge assertion for SSA name NAME on edge E for 3349169689Skan the conditional jump pointed to by SI. Return true if an assertion 3350169689Skan for NAME could be registered. */ 3351169689Skan 3352169689Skanstatic bool 3353169689Skanregister_edge_assert_for (tree name, edge e, block_stmt_iterator si) 3354169689Skan{ 3355169689Skan tree val, stmt; 3356169689Skan enum tree_code comp_code; 3357169689Skan 3358169689Skan stmt = bsi_stmt (si); 3359169689Skan 3360169689Skan /* Do not attempt to infer anything in names that flow through 3361169689Skan abnormal edges. */ 3362169689Skan if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 3363169689Skan return false; 3364169689Skan 3365169689Skan /* If NAME was not found in the sub-graph reachable from E, then 3366169689Skan there's nothing to do. */ 3367169689Skan if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))) 3368169689Skan return false; 3369169689Skan 3370169689Skan /* We found a use of NAME in the sub-graph rooted at E->DEST. 3371169689Skan Register an assertion for NAME according to the value that NAME 3372169689Skan takes on edge E. */ 3373169689Skan if (TREE_CODE (stmt) == COND_EXPR) 3374169689Skan { 3375169689Skan /* If BB ends in a COND_EXPR then NAME then we should insert 3376169689Skan the original predicate on EDGE_TRUE_VALUE and the 3377169689Skan opposite predicate on EDGE_FALSE_VALUE. */ 3378169689Skan tree cond = COND_EXPR_COND (stmt); 3379169689Skan bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0; 3380169689Skan 3381169689Skan /* Predicates may be a single SSA name or NAME OP VAL. */ 3382169689Skan if (cond == name) 3383169689Skan { 3384169689Skan /* If the predicate is a name, it must be NAME, in which 3385169689Skan case we create the predicate NAME == true or 3386169689Skan NAME == false accordingly. */ 3387169689Skan comp_code = EQ_EXPR; 3388169689Skan val = (is_else_edge) ? boolean_false_node : boolean_true_node; 3389169689Skan } 3390169689Skan else 3391169689Skan { 3392169689Skan /* Otherwise, we have a comparison of the form NAME COMP VAL 3393169689Skan or VAL COMP NAME. */ 3394169689Skan if (name == TREE_OPERAND (cond, 1)) 3395169689Skan { 3396169689Skan /* If the predicate is of the form VAL COMP NAME, flip 3397169689Skan COMP around because we need to register NAME as the 3398169689Skan first operand in the predicate. */ 3399169689Skan comp_code = swap_tree_comparison (TREE_CODE (cond)); 3400169689Skan val = TREE_OPERAND (cond, 0); 3401169689Skan } 3402169689Skan else 3403169689Skan { 3404169689Skan /* The comparison is of the form NAME COMP VAL, so the 3405169689Skan comparison code remains unchanged. */ 3406169689Skan comp_code = TREE_CODE (cond); 3407169689Skan val = TREE_OPERAND (cond, 1); 3408169689Skan } 3409169689Skan 3410169689Skan /* If we are inserting the assertion on the ELSE edge, we 3411169689Skan need to invert the sign comparison. */ 3412169689Skan if (is_else_edge) 3413169689Skan comp_code = invert_tree_comparison (comp_code, 0); 3414169689Skan 3415169689Skan /* Do not register always-false predicates. FIXME, this 3416169689Skan works around a limitation in fold() when dealing with 3417169689Skan enumerations. Given 'enum { N1, N2 } x;', fold will not 3418169689Skan fold 'if (x > N2)' to 'if (0)'. */ 3419169689Skan if ((comp_code == GT_EXPR || comp_code == LT_EXPR) 3420169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (val)) 3421169689Skan || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))) 3422169689Skan { 3423169689Skan tree min = TYPE_MIN_VALUE (TREE_TYPE (val)); 3424169689Skan tree max = TYPE_MAX_VALUE (TREE_TYPE (val)); 3425169689Skan 3426169689Skan if (comp_code == GT_EXPR && compare_values (val, max) == 0) 3427169689Skan return false; 3428169689Skan 3429169689Skan if (comp_code == LT_EXPR && compare_values (val, min) == 0) 3430169689Skan return false; 3431169689Skan } 3432169689Skan } 3433169689Skan } 3434169689Skan else 3435169689Skan { 3436169689Skan /* FIXME. Handle SWITCH_EXPR. */ 3437169689Skan gcc_unreachable (); 3438169689Skan } 3439169689Skan 3440169689Skan register_new_assert_for (name, comp_code, val, NULL, e, si); 3441169689Skan return true; 3442169689Skan} 3443169689Skan 3444169689Skan 3445169689Skanstatic bool find_assert_locations (basic_block bb); 3446169689Skan 3447169689Skan/* Determine whether the outgoing edges of BB should receive an 3448169689Skan ASSERT_EXPR for each of the operands of BB's last statement. The 3449169689Skan last statement of BB must be a COND_EXPR or a SWITCH_EXPR. 3450169689Skan 3451169689Skan If any of the sub-graphs rooted at BB have an interesting use of 3452169689Skan the predicate operands, an assert location node is added to the 3453169689Skan list of assertions for the corresponding operands. */ 3454169689Skan 3455169689Skanstatic bool 3456169689Skanfind_conditional_asserts (basic_block bb) 3457169689Skan{ 3458169689Skan bool need_assert; 3459169689Skan block_stmt_iterator last_si; 3460169689Skan tree op, last; 3461169689Skan edge_iterator ei; 3462169689Skan edge e; 3463169689Skan ssa_op_iter iter; 3464169689Skan 3465169689Skan need_assert = false; 3466169689Skan last_si = bsi_last (bb); 3467169689Skan last = bsi_stmt (last_si); 3468169689Skan 3469169689Skan /* Look for uses of the operands in each of the sub-graphs 3470169689Skan rooted at BB. We need to check each of the outgoing edges 3471169689Skan separately, so that we know what kind of ASSERT_EXPR to 3472169689Skan insert. */ 3473169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 3474169689Skan { 3475169689Skan if (e->dest == bb) 3476169689Skan continue; 3477169689Skan 3478169689Skan /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap. 3479169689Skan Otherwise, when we finish traversing each of the sub-graphs, we 3480169689Skan won't know whether the variables were found in the sub-graphs or 3481169689Skan if they had been found in a block upstream from BB. 3482169689Skan 3483169689Skan This is actually a bad idea is some cases, particularly jump 3484169689Skan threading. Consider a CFG like the following: 3485169689Skan 3486169689Skan 0 3487169689Skan /| 3488169689Skan 1 | 3489169689Skan \| 3490169689Skan 2 3491169689Skan / \ 3492169689Skan 3 4 3493169689Skan 3494169689Skan Assume that one or more operands in the conditional at the 3495169689Skan end of block 0 are used in a conditional in block 2, but not 3496169689Skan anywhere in block 1. In this case we will not insert any 3497169689Skan assert statements in block 1, which may cause us to miss 3498169689Skan opportunities to optimize, particularly for jump threading. */ 3499169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3500169689Skan RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3501169689Skan 3502169689Skan /* Traverse the strictly dominated sub-graph rooted at E->DEST 3503169689Skan to determine if any of the operands in the conditional 3504169689Skan predicate are used. */ 3505169689Skan if (e->dest != bb) 3506169689Skan need_assert |= find_assert_locations (e->dest); 3507169689Skan 3508169689Skan /* Register the necessary assertions for each operand in the 3509169689Skan conditional predicate. */ 3510169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3511169689Skan need_assert |= register_edge_assert_for (op, e, last_si); 3512169689Skan } 3513169689Skan 3514169689Skan /* Finally, indicate that we have found the operands in the 3515169689Skan conditional. */ 3516169689Skan FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE) 3517169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3518169689Skan 3519169689Skan return need_assert; 3520169689Skan} 3521169689Skan 3522169689Skan 3523169689Skan/* Traverse all the statements in block BB looking for statements that 3524169689Skan may generate useful assertions for the SSA names in their operand. 3525169689Skan If a statement produces a useful assertion A for name N_i, then the 3526169689Skan list of assertions already generated for N_i is scanned to 3527169689Skan determine if A is actually needed. 3528169689Skan 3529169689Skan If N_i already had the assertion A at a location dominating the 3530169689Skan current location, then nothing needs to be done. Otherwise, the 3531169689Skan new location for A is recorded instead. 3532169689Skan 3533169689Skan 1- For every statement S in BB, all the variables used by S are 3534169689Skan added to bitmap FOUND_IN_SUBGRAPH. 3535169689Skan 3536169689Skan 2- If statement S uses an operand N in a way that exposes a known 3537169689Skan value range for N, then if N was not already generated by an 3538169689Skan ASSERT_EXPR, create a new assert location for N. For instance, 3539169689Skan if N is a pointer and the statement dereferences it, we can 3540169689Skan assume that N is not NULL. 3541169689Skan 3542169689Skan 3- COND_EXPRs are a special case of #2. We can derive range 3543169689Skan information from the predicate but need to insert different 3544169689Skan ASSERT_EXPRs for each of the sub-graphs rooted at the 3545169689Skan conditional block. If the last statement of BB is a conditional 3546169689Skan expression of the form 'X op Y', then 3547169689Skan 3548169689Skan a) Remove X and Y from the set FOUND_IN_SUBGRAPH. 3549169689Skan 3550169689Skan b) If the conditional is the only entry point to the sub-graph 3551169689Skan corresponding to the THEN_CLAUSE, recurse into it. On 3552169689Skan return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then 3553169689Skan an ASSERT_EXPR is added for the corresponding variable. 3554169689Skan 3555169689Skan c) Repeat step (b) on the ELSE_CLAUSE. 3556169689Skan 3557169689Skan d) Mark X and Y in FOUND_IN_SUBGRAPH. 3558169689Skan 3559169689Skan For instance, 3560169689Skan 3561169689Skan if (a == 9) 3562169689Skan b = a; 3563169689Skan else 3564169689Skan b = c + 1; 3565169689Skan 3566169689Skan In this case, an assertion on the THEN clause is useful to 3567169689Skan determine that 'a' is always 9 on that edge. However, an assertion 3568169689Skan on the ELSE clause would be unnecessary. 3569169689Skan 3570169689Skan 4- If BB does not end in a conditional expression, then we recurse 3571169689Skan into BB's dominator children. 3572169689Skan 3573169689Skan At the end of the recursive traversal, every SSA name will have a 3574169689Skan list of locations where ASSERT_EXPRs should be added. When a new 3575169689Skan location for name N is found, it is registered by calling 3576169689Skan register_new_assert_for. That function keeps track of all the 3577169689Skan registered assertions to prevent adding unnecessary assertions. 3578169689Skan For instance, if a pointer P_4 is dereferenced more than once in a 3579169689Skan dominator tree, only the location dominating all the dereference of 3580169689Skan P_4 will receive an ASSERT_EXPR. 3581169689Skan 3582169689Skan If this function returns true, then it means that there are names 3583169689Skan for which we need to generate ASSERT_EXPRs. Those assertions are 3584169689Skan inserted by process_assert_insertions. 3585169689Skan 3586169689Skan TODO. Handle SWITCH_EXPR. */ 3587169689Skan 3588169689Skanstatic bool 3589169689Skanfind_assert_locations (basic_block bb) 3590169689Skan{ 3591169689Skan block_stmt_iterator si; 3592169689Skan tree last, phi; 3593169689Skan bool need_assert; 3594169689Skan basic_block son; 3595169689Skan 3596169689Skan if (TEST_BIT (blocks_visited, bb->index)) 3597169689Skan return false; 3598169689Skan 3599169689Skan SET_BIT (blocks_visited, bb->index); 3600169689Skan 3601169689Skan need_assert = false; 3602169689Skan 3603169689Skan /* Traverse all PHI nodes in BB marking used operands. */ 3604169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 3605169689Skan { 3606169689Skan use_operand_p arg_p; 3607169689Skan ssa_op_iter i; 3608169689Skan 3609169689Skan FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE) 3610169689Skan { 3611169689Skan tree arg = USE_FROM_PTR (arg_p); 3612169689Skan if (TREE_CODE (arg) == SSA_NAME) 3613169689Skan { 3614169689Skan gcc_assert (is_gimple_reg (PHI_RESULT (phi))); 3615169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg)); 3616169689Skan } 3617169689Skan } 3618169689Skan } 3619169689Skan 3620169689Skan /* Traverse all the statements in BB marking used names and looking 3621169689Skan for statements that may infer assertions for their used operands. */ 3622169689Skan last = NULL_TREE; 3623169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 3624169689Skan { 3625169689Skan tree stmt, op; 3626169689Skan ssa_op_iter i; 3627169689Skan 3628169689Skan stmt = bsi_stmt (si); 3629169689Skan 3630169689Skan /* See if we can derive an assertion for any of STMT's operands. */ 3631169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) 3632169689Skan { 3633169689Skan tree value; 3634169689Skan enum tree_code comp_code; 3635169689Skan 3636169689Skan /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside 3637169689Skan the sub-graph of a conditional block, when we return from 3638169689Skan this recursive walk, our parent will use the 3639169689Skan FOUND_IN_SUBGRAPH bitset to determine if one of the 3640169689Skan operands it was looking for was present in the sub-graph. */ 3641169689Skan SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op)); 3642169689Skan 3643169689Skan /* If OP is used in such a way that we can infer a value 3644169689Skan range for it, and we don't find a previous assertion for 3645169689Skan it, create a new assertion location node for OP. */ 3646169689Skan if (infer_value_range (stmt, op, &comp_code, &value)) 3647169689Skan { 3648169689Skan /* If we are able to infer a nonzero value range for OP, 3649169689Skan then walk backwards through the use-def chain to see if OP 3650169689Skan was set via a typecast. 3651169689Skan 3652169689Skan If so, then we can also infer a nonzero value range 3653169689Skan for the operand of the NOP_EXPR. */ 3654169689Skan if (comp_code == NE_EXPR && integer_zerop (value)) 3655169689Skan { 3656169689Skan tree t = op; 3657169689Skan tree def_stmt = SSA_NAME_DEF_STMT (t); 3658169689Skan 3659169689Skan while (TREE_CODE (def_stmt) == MODIFY_EXPR 3660169689Skan && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR 3661169689Skan && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME 3662169689Skan && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)))) 3663169689Skan { 3664169689Skan t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0); 3665169689Skan def_stmt = SSA_NAME_DEF_STMT (t); 3666169689Skan 3667169689Skan /* Note we want to register the assert for the 3668169689Skan operand of the NOP_EXPR after SI, not after the 3669169689Skan conversion. */ 3670169689Skan if (! has_single_use (t)) 3671169689Skan { 3672169689Skan register_new_assert_for (t, comp_code, value, 3673169689Skan bb, NULL, si); 3674169689Skan need_assert = true; 3675169689Skan } 3676169689Skan } 3677169689Skan } 3678169689Skan 3679169689Skan /* If OP is used only once, namely in this STMT, don't 3680169689Skan bother creating an ASSERT_EXPR for it. Such an 3681169689Skan ASSERT_EXPR would do nothing but increase compile time. */ 3682169689Skan if (!has_single_use (op)) 3683169689Skan { 3684169689Skan register_new_assert_for (op, comp_code, value, bb, NULL, si); 3685169689Skan need_assert = true; 3686169689Skan } 3687169689Skan } 3688169689Skan } 3689169689Skan 3690169689Skan /* Remember the last statement of the block. */ 3691169689Skan last = stmt; 3692169689Skan } 3693169689Skan 3694169689Skan /* If BB's last statement is a conditional expression 3695169689Skan involving integer operands, recurse into each of the sub-graphs 3696169689Skan rooted at BB to determine if we need to add ASSERT_EXPRs. */ 3697169689Skan if (last 3698169689Skan && TREE_CODE (last) == COND_EXPR 3699169689Skan && !fp_predicate (COND_EXPR_COND (last)) 3700169689Skan && !ZERO_SSA_OPERANDS (last, SSA_OP_USE)) 3701169689Skan need_assert |= find_conditional_asserts (bb); 3702169689Skan 3703169689Skan /* Recurse into the dominator children of BB. */ 3704169689Skan for (son = first_dom_son (CDI_DOMINATORS, bb); 3705169689Skan son; 3706169689Skan son = next_dom_son (CDI_DOMINATORS, son)) 3707169689Skan need_assert |= find_assert_locations (son); 3708169689Skan 3709169689Skan return need_assert; 3710169689Skan} 3711169689Skan 3712169689Skan 3713169689Skan/* Create an ASSERT_EXPR for NAME and insert it in the location 3714169689Skan indicated by LOC. Return true if we made any edge insertions. */ 3715169689Skan 3716169689Skanstatic bool 3717169689Skanprocess_assert_insertions_for (tree name, assert_locus_t loc) 3718169689Skan{ 3719169689Skan /* Build the comparison expression NAME_i COMP_CODE VAL. */ 3720169689Skan tree stmt, cond, assert_expr; 3721169689Skan edge_iterator ei; 3722169689Skan edge e; 3723169689Skan 3724169689Skan cond = build2 (loc->comp_code, boolean_type_node, name, loc->val); 3725169689Skan assert_expr = build_assert_expr_for (cond, name); 3726169689Skan 3727169689Skan if (loc->e) 3728169689Skan { 3729169689Skan /* We have been asked to insert the assertion on an edge. This 3730169689Skan is used only by COND_EXPR and SWITCH_EXPR assertions. */ 3731169689Skan#if defined ENABLE_CHECKING 3732169689Skan gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR 3733169689Skan || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR); 3734169689Skan#endif 3735169689Skan 3736169689Skan bsi_insert_on_edge (loc->e, assert_expr); 3737169689Skan return true; 3738169689Skan } 3739169689Skan 3740169689Skan /* Otherwise, we can insert right after LOC->SI iff the 3741169689Skan statement must not be the last statement in the block. */ 3742169689Skan stmt = bsi_stmt (loc->si); 3743169689Skan if (!stmt_ends_bb_p (stmt)) 3744169689Skan { 3745169689Skan bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT); 3746169689Skan return false; 3747169689Skan } 3748169689Skan 3749169689Skan /* If STMT must be the last statement in BB, we can only insert new 3750169689Skan assertions on the non-abnormal edge out of BB. Note that since 3751169689Skan STMT is not control flow, there may only be one non-abnormal edge 3752169689Skan out of BB. */ 3753169689Skan FOR_EACH_EDGE (e, ei, loc->bb->succs) 3754169689Skan if (!(e->flags & EDGE_ABNORMAL)) 3755169689Skan { 3756169689Skan bsi_insert_on_edge (e, assert_expr); 3757169689Skan return true; 3758169689Skan } 3759169689Skan 3760169689Skan gcc_unreachable (); 3761169689Skan} 3762169689Skan 3763169689Skan 3764169689Skan/* Process all the insertions registered for every name N_i registered 3765169689Skan in NEED_ASSERT_FOR. The list of assertions to be inserted are 3766169689Skan found in ASSERTS_FOR[i]. */ 3767169689Skan 3768169689Skanstatic void 3769169689Skanprocess_assert_insertions (void) 3770169689Skan{ 3771169689Skan unsigned i; 3772169689Skan bitmap_iterator bi; 3773169689Skan bool update_edges_p = false; 3774169689Skan int num_asserts = 0; 3775169689Skan 3776169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3777169689Skan dump_all_asserts (dump_file); 3778169689Skan 3779169689Skan EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi) 3780169689Skan { 3781169689Skan assert_locus_t loc = asserts_for[i]; 3782169689Skan gcc_assert (loc); 3783169689Skan 3784169689Skan while (loc) 3785169689Skan { 3786169689Skan assert_locus_t next = loc->next; 3787169689Skan update_edges_p |= process_assert_insertions_for (ssa_name (i), loc); 3788169689Skan free (loc); 3789169689Skan loc = next; 3790169689Skan num_asserts++; 3791169689Skan } 3792169689Skan } 3793169689Skan 3794169689Skan if (update_edges_p) 3795169689Skan bsi_commit_edge_inserts (); 3796169689Skan 3797169689Skan if (dump_file && (dump_flags & TDF_STATS)) 3798169689Skan fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n", 3799169689Skan num_asserts); 3800169689Skan} 3801169689Skan 3802169689Skan 3803169689Skan/* Traverse the flowgraph looking for conditional jumps to insert range 3804169689Skan expressions. These range expressions are meant to provide information 3805169689Skan to optimizations that need to reason in terms of value ranges. They 3806169689Skan will not be expanded into RTL. For instance, given: 3807169689Skan 3808169689Skan x = ... 3809169689Skan y = ... 3810169689Skan if (x < y) 3811169689Skan y = x - 2; 3812169689Skan else 3813169689Skan x = y + 3; 3814169689Skan 3815169689Skan this pass will transform the code into: 3816169689Skan 3817169689Skan x = ... 3818169689Skan y = ... 3819169689Skan if (x < y) 3820169689Skan { 3821169689Skan x = ASSERT_EXPR <x, x < y> 3822169689Skan y = x - 2 3823169689Skan } 3824169689Skan else 3825169689Skan { 3826169689Skan y = ASSERT_EXPR <y, x <= y> 3827169689Skan x = y + 3 3828169689Skan } 3829169689Skan 3830169689Skan The idea is that once copy and constant propagation have run, other 3831169689Skan optimizations will be able to determine what ranges of values can 'x' 3832169689Skan take in different paths of the code, simply by checking the reaching 3833169689Skan definition of 'x'. */ 3834169689Skan 3835169689Skanstatic void 3836169689Skaninsert_range_assertions (void) 3837169689Skan{ 3838169689Skan edge e; 3839169689Skan edge_iterator ei; 3840169689Skan bool update_ssa_p; 3841169689Skan 3842169689Skan found_in_subgraph = sbitmap_alloc (num_ssa_names); 3843169689Skan sbitmap_zero (found_in_subgraph); 3844169689Skan 3845169689Skan blocks_visited = sbitmap_alloc (last_basic_block); 3846169689Skan sbitmap_zero (blocks_visited); 3847169689Skan 3848169689Skan need_assert_for = BITMAP_ALLOC (NULL); 3849169689Skan asserts_for = XNEWVEC (assert_locus_t, num_ssa_names); 3850169689Skan memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t)); 3851169689Skan 3852169689Skan calculate_dominance_info (CDI_DOMINATORS); 3853169689Skan 3854169689Skan update_ssa_p = false; 3855169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 3856169689Skan if (find_assert_locations (e->dest)) 3857169689Skan update_ssa_p = true; 3858169689Skan 3859169689Skan if (update_ssa_p) 3860169689Skan { 3861169689Skan process_assert_insertions (); 3862169689Skan update_ssa (TODO_update_ssa_no_phi); 3863169689Skan } 3864169689Skan 3865169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3866169689Skan { 3867169689Skan fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n"); 3868169689Skan dump_function_to_file (current_function_decl, dump_file, dump_flags); 3869169689Skan } 3870169689Skan 3871169689Skan sbitmap_free (found_in_subgraph); 3872169689Skan free (asserts_for); 3873169689Skan BITMAP_FREE (need_assert_for); 3874169689Skan} 3875169689Skan 3876169689Skan 3877169689Skan/* Convert range assertion expressions into the implied copies and 3878169689Skan copy propagate away the copies. Doing the trivial copy propagation 3879169689Skan here avoids the need to run the full copy propagation pass after 3880169689Skan VRP. 3881169689Skan 3882169689Skan FIXME, this will eventually lead to copy propagation removing the 3883169689Skan names that had useful range information attached to them. For 3884169689Skan instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>, 3885169689Skan then N_i will have the range [3, +INF]. 3886169689Skan 3887169689Skan However, by converting the assertion into the implied copy 3888169689Skan operation N_i = N_j, we will then copy-propagate N_j into the uses 3889169689Skan of N_i and lose the range information. We may want to hold on to 3890169689Skan ASSERT_EXPRs a little while longer as the ranges could be used in 3891169689Skan things like jump threading. 3892169689Skan 3893169689Skan The problem with keeping ASSERT_EXPRs around is that passes after 3894169689Skan VRP need to handle them appropriately. 3895169689Skan 3896169689Skan Another approach would be to make the range information a first 3897169689Skan class property of the SSA_NAME so that it can be queried from 3898169689Skan any pass. This is made somewhat more complex by the need for 3899169689Skan multiple ranges to be associated with one SSA_NAME. */ 3900169689Skan 3901169689Skanstatic void 3902169689Skanremove_range_assertions (void) 3903169689Skan{ 3904169689Skan basic_block bb; 3905169689Skan block_stmt_iterator si; 3906169689Skan 3907169689Skan /* Note that the BSI iterator bump happens at the bottom of the 3908169689Skan loop and no bump is necessary if we're removing the statement 3909169689Skan referenced by the current BSI. */ 3910169689Skan FOR_EACH_BB (bb) 3911169689Skan for (si = bsi_start (bb); !bsi_end_p (si);) 3912169689Skan { 3913169689Skan tree stmt = bsi_stmt (si); 3914169689Skan tree use_stmt; 3915169689Skan 3916169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3917169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR) 3918169689Skan { 3919169689Skan tree rhs = TREE_OPERAND (stmt, 1), var; 3920169689Skan tree cond = fold (ASSERT_EXPR_COND (rhs)); 3921169689Skan use_operand_p use_p; 3922169689Skan imm_use_iterator iter; 3923169689Skan 3924169689Skan gcc_assert (cond != boolean_false_node); 3925169689Skan 3926169689Skan /* Propagate the RHS into every use of the LHS. */ 3927169689Skan var = ASSERT_EXPR_VAR (rhs); 3928169689Skan FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0)) 3929169689Skan FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 3930169689Skan { 3931169689Skan SET_USE (use_p, var); 3932169689Skan gcc_assert (TREE_CODE (var) == SSA_NAME); 3933169689Skan } 3934169689Skan 3935169689Skan /* And finally, remove the copy, it is not needed. */ 3936169689Skan bsi_remove (&si, true); 3937169689Skan } 3938169689Skan else 3939169689Skan bsi_next (&si); 3940169689Skan } 3941169689Skan 3942169689Skan sbitmap_free (blocks_visited); 3943169689Skan} 3944169689Skan 3945169689Skan 3946169689Skan/* Return true if STMT is interesting for VRP. */ 3947169689Skan 3948169689Skanstatic bool 3949169689Skanstmt_interesting_for_vrp (tree stmt) 3950169689Skan{ 3951169689Skan if (TREE_CODE (stmt) == PHI_NODE 3952169689Skan && is_gimple_reg (PHI_RESULT (stmt)) 3953169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))) 3954169689Skan || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt))))) 3955169689Skan return true; 3956169689Skan else if (TREE_CODE (stmt) == MODIFY_EXPR) 3957169689Skan { 3958169689Skan tree lhs = TREE_OPERAND (stmt, 0); 3959169689Skan tree rhs = TREE_OPERAND (stmt, 1); 3960169689Skan 3961169689Skan /* In general, assignments with virtual operands are not useful 3962169689Skan for deriving ranges, with the obvious exception of calls to 3963169689Skan builtin functions. */ 3964169689Skan if (TREE_CODE (lhs) == SSA_NAME 3965169689Skan && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 3966169689Skan || POINTER_TYPE_P (TREE_TYPE (lhs))) 3967169689Skan && ((TREE_CODE (rhs) == CALL_EXPR 3968169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 3969169689Skan && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 3970169689Skan && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 3971169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))) 3972169689Skan return true; 3973169689Skan } 3974169689Skan else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 3975169689Skan return true; 3976169689Skan 3977169689Skan return false; 3978169689Skan} 3979169689Skan 3980169689Skan 3981169689Skan/* Initialize local data structures for VRP. */ 3982169689Skan 3983169689Skanstatic void 3984169689Skanvrp_initialize (void) 3985169689Skan{ 3986169689Skan basic_block bb; 3987169689Skan 3988169689Skan vr_value = XNEWVEC (value_range_t *, num_ssa_names); 3989169689Skan memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *)); 3990169689Skan 3991169689Skan FOR_EACH_BB (bb) 3992169689Skan { 3993169689Skan block_stmt_iterator si; 3994169689Skan tree phi; 3995169689Skan 3996169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 3997169689Skan { 3998169689Skan if (!stmt_interesting_for_vrp (phi)) 3999169689Skan { 4000169689Skan tree lhs = PHI_RESULT (phi); 4001169689Skan set_value_range_to_varying (get_value_range (lhs)); 4002169689Skan DONT_SIMULATE_AGAIN (phi) = true; 4003169689Skan } 4004169689Skan else 4005169689Skan DONT_SIMULATE_AGAIN (phi) = false; 4006169689Skan } 4007169689Skan 4008169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 4009169689Skan { 4010169689Skan tree stmt = bsi_stmt (si); 4011169689Skan 4012169689Skan if (!stmt_interesting_for_vrp (stmt)) 4013169689Skan { 4014169689Skan ssa_op_iter i; 4015169689Skan tree def; 4016169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) 4017169689Skan set_value_range_to_varying (get_value_range (def)); 4018169689Skan DONT_SIMULATE_AGAIN (stmt) = true; 4019169689Skan } 4020169689Skan else 4021169689Skan { 4022169689Skan DONT_SIMULATE_AGAIN (stmt) = false; 4023169689Skan } 4024169689Skan } 4025169689Skan } 4026169689Skan} 4027169689Skan 4028169689Skan 4029169689Skan/* Visit assignment STMT. If it produces an interesting range, record 4030169689Skan the SSA name in *OUTPUT_P. */ 4031169689Skan 4032169689Skanstatic enum ssa_prop_result 4033169689Skanvrp_visit_assignment (tree stmt, tree *output_p) 4034169689Skan{ 4035169689Skan tree lhs, rhs, def; 4036169689Skan ssa_op_iter iter; 4037169689Skan 4038169689Skan lhs = TREE_OPERAND (stmt, 0); 4039169689Skan rhs = TREE_OPERAND (stmt, 1); 4040169689Skan 4041169689Skan /* We only keep track of ranges in integral and pointer types. */ 4042169689Skan if (TREE_CODE (lhs) == SSA_NAME 4043169689Skan && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 4044169689Skan /* It is valid to have NULL MIN/MAX values on a type. See 4045169689Skan build_range_type. */ 4046169689Skan && TYPE_MIN_VALUE (TREE_TYPE (lhs)) 4047169689Skan && TYPE_MAX_VALUE (TREE_TYPE (lhs))) 4048169689Skan || POINTER_TYPE_P (TREE_TYPE (lhs)))) 4049169689Skan { 4050169689Skan struct loop *l; 4051169689Skan value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4052169689Skan 4053169689Skan extract_range_from_expr (&new_vr, rhs); 4054169689Skan 4055169689Skan /* If STMT is inside a loop, we may be able to know something 4056169689Skan else about the range of LHS by examining scalar evolution 4057169689Skan information. */ 4058169689Skan if (current_loops && (l = loop_containing_stmt (stmt))) 4059169689Skan adjust_range_with_scev (&new_vr, l, stmt, lhs); 4060169689Skan 4061169689Skan if (update_value_range (lhs, &new_vr)) 4062169689Skan { 4063169689Skan *output_p = lhs; 4064169689Skan 4065169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4066169689Skan { 4067169689Skan fprintf (dump_file, "Found new range for "); 4068169689Skan print_generic_expr (dump_file, lhs, 0); 4069169689Skan fprintf (dump_file, ": "); 4070169689Skan dump_value_range (dump_file, &new_vr); 4071169689Skan fprintf (dump_file, "\n\n"); 4072169689Skan } 4073169689Skan 4074169689Skan if (new_vr.type == VR_VARYING) 4075169689Skan return SSA_PROP_VARYING; 4076169689Skan 4077169689Skan return SSA_PROP_INTERESTING; 4078169689Skan } 4079169689Skan 4080169689Skan return SSA_PROP_NOT_INTERESTING; 4081169689Skan } 4082169689Skan 4083169689Skan /* Every other statement produces no useful ranges. */ 4084169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4085169689Skan set_value_range_to_varying (get_value_range (def)); 4086169689Skan 4087169689Skan return SSA_PROP_VARYING; 4088169689Skan} 4089169689Skan 4090169689Skan 4091169689Skan/* Compare all the value ranges for names equivalent to VAR with VAL 4092169689Skan using comparison code COMP. Return the same value returned by 4093169689Skan compare_range_with_value, including the setting of 4094169689Skan *STRICT_OVERFLOW_P. */ 4095169689Skan 4096169689Skanstatic tree 4097169689Skancompare_name_with_value (enum tree_code comp, tree var, tree val, 4098169689Skan bool *strict_overflow_p) 4099169689Skan{ 4100169689Skan bitmap_iterator bi; 4101169689Skan unsigned i; 4102169689Skan bitmap e; 4103169689Skan tree retval, t; 4104169689Skan int used_strict_overflow; 4105169689Skan 4106169689Skan t = retval = NULL_TREE; 4107169689Skan 4108169689Skan /* Get the set of equivalences for VAR. */ 4109169689Skan e = get_value_range (var)->equiv; 4110169689Skan 4111169689Skan /* Add VAR to its own set of equivalences so that VAR's value range 4112169689Skan is processed by this loop (otherwise, we would have to replicate 4113169689Skan the body of the loop just to check VAR's value range). */ 4114169689Skan bitmap_set_bit (e, SSA_NAME_VERSION (var)); 4115169689Skan 4116169689Skan /* Start at -1. Set it to 0 if we do a comparison without relying 4117169689Skan on overflow, or 1 if all comparisons rely on overflow. */ 4118169689Skan used_strict_overflow = -1; 4119169689Skan 4120169689Skan EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi) 4121169689Skan { 4122169689Skan bool sop; 4123169689Skan 4124169689Skan value_range_t equiv_vr = *(vr_value[i]); 4125169689Skan 4126169689Skan /* If name N_i does not have a valid range, use N_i as its own 4127169689Skan range. This allows us to compare against names that may 4128169689Skan have N_i in their ranges. */ 4129169689Skan if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED) 4130169689Skan { 4131169689Skan equiv_vr.type = VR_RANGE; 4132169689Skan equiv_vr.min = ssa_name (i); 4133169689Skan equiv_vr.max = ssa_name (i); 4134169689Skan } 4135169689Skan 4136169689Skan sop = false; 4137169689Skan t = compare_range_with_value (comp, &equiv_vr, val, &sop); 4138169689Skan if (t) 4139169689Skan { 4140169689Skan /* If we get different answers from different members 4141169689Skan of the equivalence set this check must be in a dead 4142169689Skan code region. Folding it to a trap representation 4143169689Skan would be correct here. For now just return don't-know. */ 4144169689Skan if (retval != NULL 4145169689Skan && t != retval) 4146169689Skan { 4147169689Skan retval = NULL_TREE; 4148169689Skan break; 4149169689Skan } 4150169689Skan retval = t; 4151169689Skan 4152169689Skan if (!sop) 4153169689Skan used_strict_overflow = 0; 4154169689Skan else if (used_strict_overflow < 0) 4155169689Skan used_strict_overflow = 1; 4156169689Skan } 4157169689Skan } 4158169689Skan 4159169689Skan /* Remove VAR from its own equivalence set. */ 4160169689Skan bitmap_clear_bit (e, SSA_NAME_VERSION (var)); 4161169689Skan 4162169689Skan if (retval) 4163169689Skan { 4164169689Skan if (used_strict_overflow > 0) 4165169689Skan *strict_overflow_p = true; 4166169689Skan return retval; 4167169689Skan } 4168169689Skan 4169169689Skan /* We couldn't find a non-NULL value for the predicate. */ 4170169689Skan return NULL_TREE; 4171169689Skan} 4172169689Skan 4173169689Skan 4174169689Skan/* Given a comparison code COMP and names N1 and N2, compare all the 4175169689Skan ranges equivalent to N1 against all the ranges equivalent to N2 4176169689Skan to determine the value of N1 COMP N2. Return the same value 4177169689Skan returned by compare_ranges. Set *STRICT_OVERFLOW_P to indicate 4178169689Skan whether we relied on an overflow infinity in the comparison. */ 4179169689Skan 4180169689Skan 4181169689Skanstatic tree 4182169689Skancompare_names (enum tree_code comp, tree n1, tree n2, 4183169689Skan bool *strict_overflow_p) 4184169689Skan{ 4185169689Skan tree t, retval; 4186169689Skan bitmap e1, e2; 4187169689Skan bitmap_iterator bi1, bi2; 4188169689Skan unsigned i1, i2; 4189169689Skan int used_strict_overflow; 4190169689Skan 4191169689Skan /* Compare the ranges of every name equivalent to N1 against the 4192169689Skan ranges of every name equivalent to N2. */ 4193169689Skan e1 = get_value_range (n1)->equiv; 4194169689Skan e2 = get_value_range (n2)->equiv; 4195169689Skan 4196169689Skan /* Add N1 and N2 to their own set of equivalences to avoid 4197169689Skan duplicating the body of the loop just to check N1 and N2 4198169689Skan ranges. */ 4199169689Skan bitmap_set_bit (e1, SSA_NAME_VERSION (n1)); 4200169689Skan bitmap_set_bit (e2, SSA_NAME_VERSION (n2)); 4201169689Skan 4202169689Skan /* If the equivalence sets have a common intersection, then the two 4203169689Skan names can be compared without checking their ranges. */ 4204169689Skan if (bitmap_intersect_p (e1, e2)) 4205169689Skan { 4206169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4207169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4208169689Skan 4209169689Skan return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR) 4210169689Skan ? boolean_true_node 4211169689Skan : boolean_false_node; 4212169689Skan } 4213169689Skan 4214169689Skan /* Start at -1. Set it to 0 if we do a comparison without relying 4215169689Skan on overflow, or 1 if all comparisons rely on overflow. */ 4216169689Skan used_strict_overflow = -1; 4217169689Skan 4218169689Skan /* Otherwise, compare all the equivalent ranges. First, add N1 and 4219169689Skan N2 to their own set of equivalences to avoid duplicating the body 4220169689Skan of the loop just to check N1 and N2 ranges. */ 4221169689Skan EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1) 4222169689Skan { 4223169689Skan value_range_t vr1 = *(vr_value[i1]); 4224169689Skan 4225169689Skan /* If the range is VARYING or UNDEFINED, use the name itself. */ 4226169689Skan if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED) 4227169689Skan { 4228169689Skan vr1.type = VR_RANGE; 4229169689Skan vr1.min = ssa_name (i1); 4230169689Skan vr1.max = ssa_name (i1); 4231169689Skan } 4232169689Skan 4233169689Skan t = retval = NULL_TREE; 4234169689Skan EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2) 4235169689Skan { 4236171825Skan bool sop = false; 4237169689Skan 4238169689Skan value_range_t vr2 = *(vr_value[i2]); 4239169689Skan 4240169689Skan if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED) 4241169689Skan { 4242169689Skan vr2.type = VR_RANGE; 4243169689Skan vr2.min = ssa_name (i2); 4244169689Skan vr2.max = ssa_name (i2); 4245169689Skan } 4246169689Skan 4247169689Skan t = compare_ranges (comp, &vr1, &vr2, &sop); 4248169689Skan if (t) 4249169689Skan { 4250169689Skan /* If we get different answers from different members 4251169689Skan of the equivalence set this check must be in a dead 4252169689Skan code region. Folding it to a trap representation 4253169689Skan would be correct here. For now just return don't-know. */ 4254169689Skan if (retval != NULL 4255169689Skan && t != retval) 4256169689Skan { 4257169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4258169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4259169689Skan return NULL_TREE; 4260169689Skan } 4261169689Skan retval = t; 4262169689Skan 4263169689Skan if (!sop) 4264169689Skan used_strict_overflow = 0; 4265169689Skan else if (used_strict_overflow < 0) 4266169689Skan used_strict_overflow = 1; 4267169689Skan } 4268169689Skan } 4269169689Skan 4270169689Skan if (retval) 4271169689Skan { 4272169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4273169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4274169689Skan if (used_strict_overflow > 0) 4275169689Skan *strict_overflow_p = true; 4276169689Skan return retval; 4277169689Skan } 4278169689Skan } 4279169689Skan 4280169689Skan /* None of the equivalent ranges are useful in computing this 4281169689Skan comparison. */ 4282169689Skan bitmap_clear_bit (e1, SSA_NAME_VERSION (n1)); 4283169689Skan bitmap_clear_bit (e2, SSA_NAME_VERSION (n2)); 4284169689Skan return NULL_TREE; 4285169689Skan} 4286169689Skan 4287169689Skan 4288169689Skan/* Given a conditional predicate COND, try to determine if COND yields 4289169689Skan true or false based on the value ranges of its operands. Return 4290169689Skan BOOLEAN_TRUE_NODE if the conditional always evaluates to true, 4291169689Skan BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and, 4292169689Skan NULL if the conditional cannot be evaluated at compile time. 4293169689Skan 4294169689Skan If USE_EQUIV_P is true, the ranges of all the names equivalent with 4295169689Skan the operands in COND are used when trying to compute its value. 4296169689Skan This is only used during final substitution. During propagation, 4297169689Skan we only check the range of each variable and not its equivalents. 4298169689Skan 4299169689Skan Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow 4300169689Skan infinity to produce the result. */ 4301169689Skan 4302169689Skanstatic tree 4303169689Skanvrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p, 4304169689Skan bool *strict_overflow_p) 4305169689Skan{ 4306169689Skan gcc_assert (TREE_CODE (cond) == SSA_NAME 4307169689Skan || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison); 4308169689Skan 4309169689Skan if (TREE_CODE (cond) == SSA_NAME) 4310169689Skan { 4311169689Skan value_range_t *vr; 4312169689Skan tree retval; 4313169689Skan 4314169689Skan if (use_equiv_p) 4315169689Skan retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node, 4316169689Skan strict_overflow_p); 4317169689Skan else 4318169689Skan { 4319169689Skan value_range_t *vr = get_value_range (cond); 4320169689Skan retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node, 4321169689Skan strict_overflow_p); 4322169689Skan } 4323169689Skan 4324169689Skan /* If COND has a known boolean range, return it. */ 4325169689Skan if (retval) 4326169689Skan return retval; 4327169689Skan 4328169689Skan /* Otherwise, if COND has a symbolic range of exactly one value, 4329169689Skan return it. */ 4330169689Skan vr = get_value_range (cond); 4331169689Skan if (vr->type == VR_RANGE && vr->min == vr->max) 4332169689Skan return vr->min; 4333169689Skan } 4334169689Skan else 4335169689Skan { 4336169689Skan tree op0 = TREE_OPERAND (cond, 0); 4337169689Skan tree op1 = TREE_OPERAND (cond, 1); 4338169689Skan 4339169689Skan /* We only deal with integral and pointer types. */ 4340169689Skan if (!INTEGRAL_TYPE_P (TREE_TYPE (op0)) 4341169689Skan && !POINTER_TYPE_P (TREE_TYPE (op0))) 4342169689Skan return NULL_TREE; 4343169689Skan 4344169689Skan if (use_equiv_p) 4345169689Skan { 4346169689Skan if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME) 4347169689Skan return compare_names (TREE_CODE (cond), op0, op1, 4348169689Skan strict_overflow_p); 4349169689Skan else if (TREE_CODE (op0) == SSA_NAME) 4350169689Skan return compare_name_with_value (TREE_CODE (cond), op0, op1, 4351169689Skan strict_overflow_p); 4352169689Skan else if (TREE_CODE (op1) == SSA_NAME) 4353169689Skan return (compare_name_with_value 4354169689Skan (swap_tree_comparison (TREE_CODE (cond)), op1, op0, 4355169689Skan strict_overflow_p)); 4356169689Skan } 4357169689Skan else 4358169689Skan { 4359169689Skan value_range_t *vr0, *vr1; 4360169689Skan 4361169689Skan vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL; 4362169689Skan vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL; 4363169689Skan 4364169689Skan if (vr0 && vr1) 4365169689Skan return compare_ranges (TREE_CODE (cond), vr0, vr1, 4366169689Skan strict_overflow_p); 4367169689Skan else if (vr0 && vr1 == NULL) 4368169689Skan return compare_range_with_value (TREE_CODE (cond), vr0, op1, 4369169689Skan strict_overflow_p); 4370169689Skan else if (vr0 == NULL && vr1) 4371169689Skan return (compare_range_with_value 4372169689Skan (swap_tree_comparison (TREE_CODE (cond)), vr1, op0, 4373169689Skan strict_overflow_p)); 4374169689Skan } 4375169689Skan } 4376169689Skan 4377169689Skan /* Anything else cannot be computed statically. */ 4378169689Skan return NULL_TREE; 4379169689Skan} 4380169689Skan 4381169689Skan/* Given COND within STMT, try to simplify it based on value range 4382169689Skan information. Return NULL if the conditional can not be evaluated. 4383169689Skan The ranges of all the names equivalent with the operands in COND 4384169689Skan will be used when trying to compute the value. If the result is 4385169689Skan based on undefined signed overflow, issue a warning if 4386169689Skan appropriate. */ 4387169689Skan 4388169689Skantree 4389169689Skanvrp_evaluate_conditional (tree cond, tree stmt) 4390169689Skan{ 4391169689Skan bool sop; 4392169689Skan tree ret; 4393169689Skan 4394169689Skan sop = false; 4395169689Skan ret = vrp_evaluate_conditional_warnv (cond, true, &sop); 4396169689Skan 4397169689Skan if (ret && sop) 4398169689Skan { 4399169689Skan enum warn_strict_overflow_code wc; 4400169689Skan const char* warnmsg; 4401169689Skan 4402169689Skan if (is_gimple_min_invariant (ret)) 4403169689Skan { 4404169689Skan wc = WARN_STRICT_OVERFLOW_CONDITIONAL; 4405169689Skan warnmsg = G_("assuming signed overflow does not occur when " 4406169689Skan "simplifying conditional to constant"); 4407169689Skan } 4408169689Skan else 4409169689Skan { 4410169689Skan wc = WARN_STRICT_OVERFLOW_COMPARISON; 4411169689Skan warnmsg = G_("assuming signed overflow does not occur when " 4412169689Skan "simplifying conditional"); 4413169689Skan } 4414169689Skan 4415169689Skan if (issue_strict_overflow_warning (wc)) 4416169689Skan { 4417169689Skan location_t locus; 4418169689Skan 4419169689Skan if (!EXPR_HAS_LOCATION (stmt)) 4420169689Skan locus = input_location; 4421169689Skan else 4422169689Skan locus = EXPR_LOCATION (stmt); 4423169689Skan warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg); 4424169689Skan } 4425169689Skan } 4426169689Skan 4427169689Skan return ret; 4428169689Skan} 4429169689Skan 4430169689Skan 4431169689Skan/* Visit conditional statement STMT. If we can determine which edge 4432169689Skan will be taken out of STMT's basic block, record it in 4433169689Skan *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return 4434169689Skan SSA_PROP_VARYING. */ 4435169689Skan 4436169689Skanstatic enum ssa_prop_result 4437169689Skanvrp_visit_cond_stmt (tree stmt, edge *taken_edge_p) 4438169689Skan{ 4439169689Skan tree cond, val; 4440169689Skan bool sop; 4441169689Skan 4442169689Skan *taken_edge_p = NULL; 4443169689Skan 4444169689Skan /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to 4445169689Skan add ASSERT_EXPRs for them. */ 4446169689Skan if (TREE_CODE (stmt) == SWITCH_EXPR) 4447169689Skan return SSA_PROP_VARYING; 4448169689Skan 4449169689Skan cond = COND_EXPR_COND (stmt); 4450169689Skan 4451169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4452169689Skan { 4453169689Skan tree use; 4454169689Skan ssa_op_iter i; 4455169689Skan 4456169689Skan fprintf (dump_file, "\nVisiting conditional with predicate: "); 4457169689Skan print_generic_expr (dump_file, cond, 0); 4458169689Skan fprintf (dump_file, "\nWith known ranges\n"); 4459169689Skan 4460169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) 4461169689Skan { 4462169689Skan fprintf (dump_file, "\t"); 4463169689Skan print_generic_expr (dump_file, use, 0); 4464169689Skan fprintf (dump_file, ": "); 4465169689Skan dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]); 4466169689Skan } 4467169689Skan 4468169689Skan fprintf (dump_file, "\n"); 4469169689Skan } 4470169689Skan 4471169689Skan /* Compute the value of the predicate COND by checking the known 4472169689Skan ranges of each of its operands. 4473169689Skan 4474169689Skan Note that we cannot evaluate all the equivalent ranges here 4475169689Skan because those ranges may not yet be final and with the current 4476169689Skan propagation strategy, we cannot determine when the value ranges 4477169689Skan of the names in the equivalence set have changed. 4478169689Skan 4479169689Skan For instance, given the following code fragment 4480169689Skan 4481169689Skan i_5 = PHI <8, i_13> 4482169689Skan ... 4483169689Skan i_14 = ASSERT_EXPR <i_5, i_5 != 0> 4484169689Skan if (i_14 == 1) 4485169689Skan ... 4486169689Skan 4487169689Skan Assume that on the first visit to i_14, i_5 has the temporary 4488169689Skan range [8, 8] because the second argument to the PHI function is 4489169689Skan not yet executable. We derive the range ~[0, 0] for i_14 and the 4490169689Skan equivalence set { i_5 }. So, when we visit 'if (i_14 == 1)' for 4491169689Skan the first time, since i_14 is equivalent to the range [8, 8], we 4492169689Skan determine that the predicate is always false. 4493169689Skan 4494169689Skan On the next round of propagation, i_13 is determined to be 4495169689Skan VARYING, which causes i_5 to drop down to VARYING. So, another 4496169689Skan visit to i_14 is scheduled. In this second visit, we compute the 4497169689Skan exact same range and equivalence set for i_14, namely ~[0, 0] and 4498169689Skan { i_5 }. But we did not have the previous range for i_5 4499169689Skan registered, so vrp_visit_assignment thinks that the range for 4500169689Skan i_14 has not changed. Therefore, the predicate 'if (i_14 == 1)' 4501169689Skan is not visited again, which stops propagation from visiting 4502169689Skan statements in the THEN clause of that if(). 4503169689Skan 4504169689Skan To properly fix this we would need to keep the previous range 4505169689Skan value for the names in the equivalence set. This way we would've 4506169689Skan discovered that from one visit to the other i_5 changed from 4507169689Skan range [8, 8] to VR_VARYING. 4508169689Skan 4509169689Skan However, fixing this apparent limitation may not be worth the 4510169689Skan additional checking. Testing on several code bases (GCC, DLV, 4511169689Skan MICO, TRAMP3D and SPEC2000) showed that doing this results in 4512169689Skan 4 more predicates folded in SPEC. */ 4513169689Skan sop = false; 4514169689Skan val = vrp_evaluate_conditional_warnv (cond, false, &sop); 4515169689Skan if (val) 4516169689Skan { 4517169689Skan if (!sop) 4518169689Skan *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val); 4519169689Skan else 4520169689Skan { 4521169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4522169689Skan fprintf (dump_file, 4523169689Skan "\nIgnoring predicate evaluation because " 4524169689Skan "it assumes that signed overflow is undefined"); 4525169689Skan val = NULL_TREE; 4526169689Skan } 4527169689Skan } 4528169689Skan 4529169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4530169689Skan { 4531169689Skan fprintf (dump_file, "\nPredicate evaluates to: "); 4532169689Skan if (val == NULL_TREE) 4533169689Skan fprintf (dump_file, "DON'T KNOW\n"); 4534169689Skan else 4535169689Skan print_generic_stmt (dump_file, val, 0); 4536169689Skan } 4537169689Skan 4538169689Skan return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; 4539169689Skan} 4540169689Skan 4541169689Skan 4542169689Skan/* Evaluate statement STMT. If the statement produces a useful range, 4543169689Skan return SSA_PROP_INTERESTING and record the SSA name with the 4544169689Skan interesting range into *OUTPUT_P. 4545169689Skan 4546169689Skan If STMT is a conditional branch and we can determine its truth 4547169689Skan value, the taken edge is recorded in *TAKEN_EDGE_P. 4548169689Skan 4549169689Skan If STMT produces a varying value, return SSA_PROP_VARYING. */ 4550169689Skan 4551169689Skanstatic enum ssa_prop_result 4552169689Skanvrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p) 4553169689Skan{ 4554169689Skan tree def; 4555169689Skan ssa_op_iter iter; 4556169689Skan stmt_ann_t ann; 4557169689Skan 4558169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4559169689Skan { 4560169689Skan fprintf (dump_file, "\nVisiting statement:\n"); 4561169689Skan print_generic_stmt (dump_file, stmt, dump_flags); 4562169689Skan fprintf (dump_file, "\n"); 4563169689Skan } 4564169689Skan 4565169689Skan ann = stmt_ann (stmt); 4566169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 4567169689Skan { 4568169689Skan tree rhs = TREE_OPERAND (stmt, 1); 4569169689Skan 4570169689Skan /* In general, assignments with virtual operands are not useful 4571169689Skan for deriving ranges, with the obvious exception of calls to 4572169689Skan builtin functions. */ 4573169689Skan if ((TREE_CODE (rhs) == CALL_EXPR 4574169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR 4575169689Skan && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) 4576169689Skan && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) 4577169689Skan || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 4578169689Skan return vrp_visit_assignment (stmt, output_p); 4579169689Skan } 4580169689Skan else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) 4581169689Skan return vrp_visit_cond_stmt (stmt, taken_edge_p); 4582169689Skan 4583169689Skan /* All other statements produce nothing of interest for VRP, so mark 4584169689Skan their outputs varying and prevent further simulation. */ 4585169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 4586169689Skan set_value_range_to_varying (get_value_range (def)); 4587169689Skan 4588169689Skan return SSA_PROP_VARYING; 4589169689Skan} 4590169689Skan 4591169689Skan 4592169689Skan/* Meet operation for value ranges. Given two value ranges VR0 and 4593169689Skan VR1, store in VR0 the result of meeting VR0 and VR1. 4594169689Skan 4595169689Skan The meeting rules are as follows: 4596169689Skan 4597169689Skan 1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING. 4598169689Skan 4599169689Skan 2- If VR0 and VR1 have a non-empty intersection, set VR0 to the 4600169689Skan union of VR0 and VR1. */ 4601169689Skan 4602169689Skanstatic void 4603169689Skanvrp_meet (value_range_t *vr0, value_range_t *vr1) 4604169689Skan{ 4605169689Skan if (vr0->type == VR_UNDEFINED) 4606169689Skan { 4607169689Skan copy_value_range (vr0, vr1); 4608169689Skan return; 4609169689Skan } 4610169689Skan 4611169689Skan if (vr1->type == VR_UNDEFINED) 4612169689Skan { 4613169689Skan /* Nothing to do. VR0 already has the resulting range. */ 4614169689Skan return; 4615169689Skan } 4616169689Skan 4617169689Skan if (vr0->type == VR_VARYING) 4618169689Skan { 4619169689Skan /* Nothing to do. VR0 already has the resulting range. */ 4620169689Skan return; 4621169689Skan } 4622169689Skan 4623169689Skan if (vr1->type == VR_VARYING) 4624169689Skan { 4625169689Skan set_value_range_to_varying (vr0); 4626169689Skan return; 4627169689Skan } 4628169689Skan 4629169689Skan if (vr0->type == VR_RANGE && vr1->type == VR_RANGE) 4630169689Skan { 4631169689Skan /* If VR0 and VR1 have a non-empty intersection, compute the 4632169689Skan union of both ranges. */ 4633169689Skan if (value_ranges_intersect_p (vr0, vr1)) 4634169689Skan { 4635169689Skan int cmp; 4636169689Skan tree min, max; 4637169689Skan 4638169689Skan /* The lower limit of the new range is the minimum of the 4639169689Skan two ranges. If they cannot be compared, the result is 4640169689Skan VARYING. */ 4641169689Skan cmp = compare_values (vr0->min, vr1->min); 4642169689Skan if (cmp == 0 || cmp == 1) 4643169689Skan min = vr1->min; 4644169689Skan else if (cmp == -1) 4645169689Skan min = vr0->min; 4646169689Skan else 4647169689Skan { 4648169689Skan set_value_range_to_varying (vr0); 4649169689Skan return; 4650169689Skan } 4651169689Skan 4652169689Skan /* Similarly, the upper limit of the new range is the 4653169689Skan maximum of the two ranges. If they cannot be compared, 4654169689Skan the result is VARYING. */ 4655169689Skan cmp = compare_values (vr0->max, vr1->max); 4656169689Skan if (cmp == 0 || cmp == -1) 4657169689Skan max = vr1->max; 4658169689Skan else if (cmp == 1) 4659169689Skan max = vr0->max; 4660169689Skan else 4661169689Skan { 4662169689Skan set_value_range_to_varying (vr0); 4663169689Skan return; 4664169689Skan } 4665169689Skan 4666169689Skan /* Check for useless ranges. */ 4667169689Skan if (INTEGRAL_TYPE_P (TREE_TYPE (min)) 4668169689Skan && ((vrp_val_is_min (min) || is_overflow_infinity (min)) 4669169689Skan && (vrp_val_is_max (max) || is_overflow_infinity (max)))) 4670169689Skan { 4671169689Skan set_value_range_to_varying (vr0); 4672169689Skan return; 4673169689Skan } 4674169689Skan 4675169689Skan /* The resulting set of equivalences is the intersection of 4676169689Skan the two sets. */ 4677169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4678169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4679169689Skan else if (vr0->equiv && !vr1->equiv) 4680169689Skan bitmap_clear (vr0->equiv); 4681169689Skan 4682169689Skan set_value_range (vr0, vr0->type, min, max, vr0->equiv); 4683169689Skan } 4684169689Skan else 4685169689Skan goto no_meet; 4686169689Skan } 4687169689Skan else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE) 4688169689Skan { 4689169689Skan /* Two anti-ranges meet only if they are both identical. */ 4690169689Skan if (compare_values (vr0->min, vr1->min) == 0 4691169689Skan && compare_values (vr0->max, vr1->max) == 0 4692169689Skan && compare_values (vr0->min, vr0->max) == 0) 4693169689Skan { 4694169689Skan /* The resulting set of equivalences is the intersection of 4695169689Skan the two sets. */ 4696169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4697169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4698169689Skan else if (vr0->equiv && !vr1->equiv) 4699169689Skan bitmap_clear (vr0->equiv); 4700169689Skan } 4701169689Skan else 4702169689Skan goto no_meet; 4703169689Skan } 4704169689Skan else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE) 4705169689Skan { 4706169689Skan /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4] 4707169689Skan meet only if the ranges have an empty intersection. The 4708169689Skan result of the meet operation is the anti-range. */ 4709169689Skan if (!symbolic_range_p (vr0) 4710169689Skan && !symbolic_range_p (vr1) 4711169689Skan && !value_ranges_intersect_p (vr0, vr1)) 4712169689Skan { 4713169689Skan /* Copy most of VR1 into VR0. Don't copy VR1's equivalence 4714169689Skan set. We need to compute the intersection of the two 4715169689Skan equivalence sets. */ 4716169689Skan if (vr1->type == VR_ANTI_RANGE) 4717169689Skan set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv); 4718169689Skan 4719169689Skan /* The resulting set of equivalences is the intersection of 4720169689Skan the two sets. */ 4721169689Skan if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv) 4722169689Skan bitmap_and_into (vr0->equiv, vr1->equiv); 4723169689Skan else if (vr0->equiv && !vr1->equiv) 4724169689Skan bitmap_clear (vr0->equiv); 4725169689Skan } 4726169689Skan else 4727169689Skan goto no_meet; 4728169689Skan } 4729169689Skan else 4730169689Skan gcc_unreachable (); 4731169689Skan 4732169689Skan return; 4733169689Skan 4734169689Skanno_meet: 4735169689Skan /* The two range VR0 and VR1 do not meet. Before giving up and 4736169689Skan setting the result to VARYING, see if we can at least derive a 4737169689Skan useful anti-range. FIXME, all this nonsense about distinguishing 4738169689Skan anti-ranges from ranges is necessary because of the odd 4739169689Skan semantics of range_includes_zero_p and friends. */ 4740169689Skan if (!symbolic_range_p (vr0) 4741169689Skan && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0)) 4742169689Skan || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0))) 4743169689Skan && !symbolic_range_p (vr1) 4744169689Skan && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1)) 4745169689Skan || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1)))) 4746169689Skan { 4747169689Skan set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min)); 4748169689Skan 4749169689Skan /* Since this meet operation did not result from the meeting of 4750169689Skan two equivalent names, VR0 cannot have any equivalences. */ 4751169689Skan if (vr0->equiv) 4752169689Skan bitmap_clear (vr0->equiv); 4753169689Skan } 4754169689Skan else 4755169689Skan set_value_range_to_varying (vr0); 4756169689Skan} 4757169689Skan 4758169689Skan 4759169689Skan/* Visit all arguments for PHI node PHI that flow through executable 4760169689Skan edges. If a valid value range can be derived from all the incoming 4761169689Skan value ranges, set a new range for the LHS of PHI. */ 4762169689Skan 4763169689Skanstatic enum ssa_prop_result 4764169689Skanvrp_visit_phi_node (tree phi) 4765169689Skan{ 4766169689Skan int i; 4767169689Skan tree lhs = PHI_RESULT (phi); 4768169689Skan value_range_t *lhs_vr = get_value_range (lhs); 4769169689Skan value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; 4770169689Skan 4771169689Skan copy_value_range (&vr_result, lhs_vr); 4772169689Skan 4773169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4774169689Skan { 4775169689Skan fprintf (dump_file, "\nVisiting PHI node: "); 4776169689Skan print_generic_expr (dump_file, phi, dump_flags); 4777169689Skan } 4778169689Skan 4779169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 4780169689Skan { 4781169689Skan edge e = PHI_ARG_EDGE (phi, i); 4782169689Skan 4783169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4784169689Skan { 4785169689Skan fprintf (dump_file, 4786169689Skan "\n Argument #%d (%d -> %d %sexecutable)\n", 4787169689Skan i, e->src->index, e->dest->index, 4788169689Skan (e->flags & EDGE_EXECUTABLE) ? "" : "not "); 4789169689Skan } 4790169689Skan 4791169689Skan if (e->flags & EDGE_EXECUTABLE) 4792169689Skan { 4793169689Skan tree arg = PHI_ARG_DEF (phi, i); 4794169689Skan value_range_t vr_arg; 4795169689Skan 4796169689Skan if (TREE_CODE (arg) == SSA_NAME) 4797169689Skan vr_arg = *(get_value_range (arg)); 4798169689Skan else 4799169689Skan { 4800169689Skan if (is_overflow_infinity (arg)) 4801169689Skan { 4802169689Skan arg = copy_node (arg); 4803169689Skan TREE_OVERFLOW (arg) = 0; 4804169689Skan } 4805169689Skan 4806169689Skan vr_arg.type = VR_RANGE; 4807169689Skan vr_arg.min = arg; 4808169689Skan vr_arg.max = arg; 4809169689Skan vr_arg.equiv = NULL; 4810169689Skan } 4811169689Skan 4812169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4813169689Skan { 4814169689Skan fprintf (dump_file, "\t"); 4815169689Skan print_generic_expr (dump_file, arg, dump_flags); 4816169689Skan fprintf (dump_file, "\n\tValue: "); 4817169689Skan dump_value_range (dump_file, &vr_arg); 4818169689Skan fprintf (dump_file, "\n"); 4819169689Skan } 4820169689Skan 4821169689Skan vrp_meet (&vr_result, &vr_arg); 4822169689Skan 4823169689Skan if (vr_result.type == VR_VARYING) 4824169689Skan break; 4825169689Skan } 4826169689Skan } 4827169689Skan 4828169689Skan if (vr_result.type == VR_VARYING) 4829169689Skan goto varying; 4830169689Skan 4831169689Skan /* To prevent infinite iterations in the algorithm, derive ranges 4832169689Skan when the new value is slightly bigger or smaller than the 4833169689Skan previous one. */ 4834169689Skan if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE) 4835169689Skan { 4836169689Skan if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 4837169689Skan { 4838169689Skan int cmp_min = compare_values (lhs_vr->min, vr_result.min); 4839169689Skan int cmp_max = compare_values (lhs_vr->max, vr_result.max); 4840169689Skan 4841169689Skan /* If the new minimum is smaller or larger than the previous 4842169689Skan one, go all the way to -INF. In the first case, to avoid 4843169689Skan iterating millions of times to reach -INF, and in the 4844169689Skan other case to avoid infinite bouncing between different 4845169689Skan minimums. */ 4846169689Skan if (cmp_min > 0 || cmp_min < 0) 4847169689Skan { 4848169689Skan /* If we will end up with a (-INF, +INF) range, set it 4849169689Skan to VARYING. */ 4850169689Skan if (vrp_val_is_max (vr_result.max)) 4851169689Skan goto varying; 4852169689Skan 4853171825Skan if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) 4854171825Skan || !vrp_var_may_overflow (lhs, phi)) 4855169689Skan vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); 4856169689Skan else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) 4857169689Skan vr_result.min = 4858169689Skan negative_overflow_infinity (TREE_TYPE (vr_result.min)); 4859169689Skan else 4860169689Skan goto varying; 4861169689Skan } 4862169689Skan 4863169689Skan /* Similarly, if the new maximum is smaller or larger than 4864169689Skan the previous one, go all the way to +INF. */ 4865169689Skan if (cmp_max < 0 || cmp_max > 0) 4866169689Skan { 4867169689Skan /* If we will end up with a (-INF, +INF) range, set it 4868169689Skan to VARYING. */ 4869169689Skan if (vrp_val_is_min (vr_result.min)) 4870169689Skan goto varying; 4871169689Skan 4872171825Skan if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)) 4873171825Skan || !vrp_var_may_overflow (lhs, phi)) 4874169689Skan vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)); 4875169689Skan else if (supports_overflow_infinity (TREE_TYPE (vr_result.max))) 4876169689Skan vr_result.max = 4877169689Skan positive_overflow_infinity (TREE_TYPE (vr_result.max)); 4878169689Skan else 4879169689Skan goto varying; 4880169689Skan } 4881169689Skan } 4882169689Skan } 4883169689Skan 4884169689Skan /* If the new range is different than the previous value, keep 4885169689Skan iterating. */ 4886169689Skan if (update_value_range (lhs, &vr_result)) 4887169689Skan return SSA_PROP_INTERESTING; 4888169689Skan 4889169689Skan /* Nothing changed, don't add outgoing edges. */ 4890169689Skan return SSA_PROP_NOT_INTERESTING; 4891169689Skan 4892169689Skan /* No match found. Set the LHS to VARYING. */ 4893169689Skanvarying: 4894169689Skan set_value_range_to_varying (lhs_vr); 4895169689Skan return SSA_PROP_VARYING; 4896169689Skan} 4897169689Skan 4898169689Skan/* Simplify a division or modulo operator to a right shift or 4899169689Skan bitwise and if the first operand is unsigned or is greater 4900169689Skan than zero and the second operand is an exact power of two. */ 4901169689Skan 4902169689Skanstatic void 4903169689Skansimplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code) 4904169689Skan{ 4905169689Skan tree val = NULL; 4906169689Skan tree op = TREE_OPERAND (rhs, 0); 4907169689Skan value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4908169689Skan 4909169689Skan if (TYPE_UNSIGNED (TREE_TYPE (op))) 4910169689Skan { 4911169689Skan val = integer_one_node; 4912169689Skan } 4913169689Skan else 4914169689Skan { 4915169689Skan bool sop = false; 4916169689Skan 4917169689Skan val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop); 4918169689Skan 4919169689Skan if (val 4920169689Skan && sop 4921169689Skan && integer_onep (val) 4922169689Skan && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 4923169689Skan { 4924169689Skan location_t locus; 4925169689Skan 4926169689Skan if (!EXPR_HAS_LOCATION (stmt)) 4927169689Skan locus = input_location; 4928169689Skan else 4929169689Skan locus = EXPR_LOCATION (stmt); 4930169689Skan warning (OPT_Wstrict_overflow, 4931169689Skan ("%Hassuming signed overflow does not occur when " 4932169689Skan "simplifying / or %% to >> or &"), 4933169689Skan &locus); 4934169689Skan } 4935169689Skan } 4936169689Skan 4937169689Skan if (val && integer_onep (val)) 4938169689Skan { 4939169689Skan tree t; 4940169689Skan tree op0 = TREE_OPERAND (rhs, 0); 4941169689Skan tree op1 = TREE_OPERAND (rhs, 1); 4942169689Skan 4943169689Skan if (rhs_code == TRUNC_DIV_EXPR) 4944169689Skan { 4945169689Skan t = build_int_cst (NULL_TREE, tree_log2 (op1)); 4946169689Skan t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t); 4947169689Skan } 4948169689Skan else 4949169689Skan { 4950169689Skan t = build_int_cst (TREE_TYPE (op1), 1); 4951169689Skan t = int_const_binop (MINUS_EXPR, op1, t, 0); 4952169689Skan t = fold_convert (TREE_TYPE (op0), t); 4953169689Skan t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t); 4954169689Skan } 4955169689Skan 4956169689Skan TREE_OPERAND (stmt, 1) = t; 4957169689Skan update_stmt (stmt); 4958169689Skan } 4959169689Skan} 4960169689Skan 4961169689Skan/* If the operand to an ABS_EXPR is >= 0, then eliminate the 4962169689Skan ABS_EXPR. If the operand is <= 0, then simplify the 4963169689Skan ABS_EXPR into a NEGATE_EXPR. */ 4964169689Skan 4965169689Skanstatic void 4966169689Skansimplify_abs_using_ranges (tree stmt, tree rhs) 4967169689Skan{ 4968169689Skan tree val = NULL; 4969169689Skan tree op = TREE_OPERAND (rhs, 0); 4970169689Skan tree type = TREE_TYPE (op); 4971169689Skan value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0)); 4972169689Skan 4973169689Skan if (TYPE_UNSIGNED (type)) 4974169689Skan { 4975169689Skan val = integer_zero_node; 4976169689Skan } 4977169689Skan else if (vr) 4978169689Skan { 4979169689Skan bool sop = false; 4980169689Skan 4981169689Skan val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop); 4982169689Skan if (!val) 4983169689Skan { 4984169689Skan sop = false; 4985169689Skan val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, 4986169689Skan &sop); 4987169689Skan 4988169689Skan if (val) 4989169689Skan { 4990169689Skan if (integer_zerop (val)) 4991169689Skan val = integer_one_node; 4992169689Skan else if (integer_onep (val)) 4993169689Skan val = integer_zero_node; 4994169689Skan } 4995169689Skan } 4996169689Skan 4997169689Skan if (val 4998169689Skan && (integer_onep (val) || integer_zerop (val))) 4999169689Skan { 5000169689Skan tree t; 5001169689Skan 5002169689Skan if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC)) 5003169689Skan { 5004169689Skan location_t locus; 5005169689Skan 5006169689Skan if (!EXPR_HAS_LOCATION (stmt)) 5007169689Skan locus = input_location; 5008169689Skan else 5009169689Skan locus = EXPR_LOCATION (stmt); 5010169689Skan warning (OPT_Wstrict_overflow, 5011169689Skan ("%Hassuming signed overflow does not occur when " 5012169689Skan "simplifying abs (X) to X or -X"), 5013169689Skan &locus); 5014169689Skan } 5015169689Skan 5016169689Skan if (integer_onep (val)) 5017169689Skan t = build1 (NEGATE_EXPR, TREE_TYPE (op), op); 5018169689Skan else 5019169689Skan t = op; 5020169689Skan 5021169689Skan TREE_OPERAND (stmt, 1) = t; 5022169689Skan update_stmt (stmt); 5023169689Skan } 5024169689Skan } 5025169689Skan} 5026169689Skan 5027169689Skan/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has 5028169689Skan a known value range VR. 5029169689Skan 5030169689Skan If there is one and only one value which will satisfy the 5031169689Skan conditional, then return that value. Else return NULL. */ 5032169689Skan 5033169689Skanstatic tree 5034169689Skantest_for_singularity (enum tree_code cond_code, tree op0, 5035169689Skan tree op1, value_range_t *vr) 5036169689Skan{ 5037169689Skan tree min = NULL; 5038169689Skan tree max = NULL; 5039169689Skan 5040169689Skan /* Extract minimum/maximum values which satisfy the 5041169689Skan the conditional as it was written. */ 5042169689Skan if (cond_code == LE_EXPR || cond_code == LT_EXPR) 5043169689Skan { 5044169689Skan /* This should not be negative infinity; there is no overflow 5045169689Skan here. */ 5046169689Skan min = TYPE_MIN_VALUE (TREE_TYPE (op0)); 5047169689Skan 5048169689Skan max = op1; 5049169689Skan if (cond_code == LT_EXPR && !is_overflow_infinity (max)) 5050169689Skan { 5051169689Skan tree one = build_int_cst (TREE_TYPE (op0), 1); 5052169689Skan max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one); 5053171825Skan if (EXPR_P (max)) 5054171825Skan TREE_NO_WARNING (max) = 1; 5055169689Skan } 5056169689Skan } 5057169689Skan else if (cond_code == GE_EXPR || cond_code == GT_EXPR) 5058169689Skan { 5059169689Skan /* This should not be positive infinity; there is no overflow 5060169689Skan here. */ 5061169689Skan max = TYPE_MAX_VALUE (TREE_TYPE (op0)); 5062169689Skan 5063169689Skan min = op1; 5064169689Skan if (cond_code == GT_EXPR && !is_overflow_infinity (min)) 5065169689Skan { 5066169689Skan tree one = build_int_cst (TREE_TYPE (op0), 1); 5067169689Skan min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one); 5068171825Skan if (EXPR_P (min)) 5069171825Skan TREE_NO_WARNING (min) = 1; 5070169689Skan } 5071169689Skan } 5072169689Skan 5073169689Skan /* Now refine the minimum and maximum values using any 5074169689Skan value range information we have for op0. */ 5075169689Skan if (min && max) 5076169689Skan { 5077169689Skan if (compare_values (vr->min, min) == -1) 5078169689Skan min = min; 5079169689Skan else 5080169689Skan min = vr->min; 5081169689Skan if (compare_values (vr->max, max) == 1) 5082169689Skan max = max; 5083169689Skan else 5084169689Skan max = vr->max; 5085169689Skan 5086169689Skan /* If the new min/max values have converged to a single value, 5087169689Skan then there is only one value which can satisfy the condition, 5088169689Skan return that value. */ 5089169689Skan if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min)) 5090169689Skan return min; 5091169689Skan } 5092169689Skan return NULL; 5093169689Skan} 5094169689Skan 5095169689Skan/* Simplify a conditional using a relational operator to an equality 5096169689Skan test if the range information indicates only one value can satisfy 5097169689Skan the original conditional. */ 5098169689Skan 5099169689Skanstatic void 5100169689Skansimplify_cond_using_ranges (tree stmt) 5101169689Skan{ 5102169689Skan tree cond = COND_EXPR_COND (stmt); 5103169689Skan tree op0 = TREE_OPERAND (cond, 0); 5104169689Skan tree op1 = TREE_OPERAND (cond, 1); 5105169689Skan enum tree_code cond_code = TREE_CODE (cond); 5106169689Skan 5107169689Skan if (cond_code != NE_EXPR 5108169689Skan && cond_code != EQ_EXPR 5109169689Skan && TREE_CODE (op0) == SSA_NAME 5110169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (op0)) 5111169689Skan && is_gimple_min_invariant (op1)) 5112169689Skan { 5113169689Skan value_range_t *vr = get_value_range (op0); 5114169689Skan 5115169689Skan /* If we have range information for OP0, then we might be 5116169689Skan able to simplify this conditional. */ 5117169689Skan if (vr->type == VR_RANGE) 5118169689Skan { 5119169689Skan tree new = test_for_singularity (cond_code, op0, op1, vr); 5120169689Skan 5121169689Skan if (new) 5122169689Skan { 5123169689Skan if (dump_file) 5124169689Skan { 5125169689Skan fprintf (dump_file, "Simplified relational "); 5126169689Skan print_generic_expr (dump_file, cond, 0); 5127169689Skan fprintf (dump_file, " into "); 5128169689Skan } 5129169689Skan 5130169689Skan COND_EXPR_COND (stmt) 5131169689Skan = build2 (EQ_EXPR, boolean_type_node, op0, new); 5132169689Skan update_stmt (stmt); 5133169689Skan 5134169689Skan if (dump_file) 5135169689Skan { 5136169689Skan print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5137169689Skan fprintf (dump_file, "\n"); 5138169689Skan } 5139169689Skan return; 5140169689Skan 5141169689Skan } 5142169689Skan 5143169689Skan /* Try again after inverting the condition. We only deal 5144169689Skan with integral types here, so no need to worry about 5145169689Skan issues with inverting FP comparisons. */ 5146169689Skan cond_code = invert_tree_comparison (cond_code, false); 5147169689Skan new = test_for_singularity (cond_code, op0, op1, vr); 5148169689Skan 5149169689Skan if (new) 5150169689Skan { 5151169689Skan if (dump_file) 5152169689Skan { 5153169689Skan fprintf (dump_file, "Simplified relational "); 5154169689Skan print_generic_expr (dump_file, cond, 0); 5155169689Skan fprintf (dump_file, " into "); 5156169689Skan } 5157169689Skan 5158169689Skan COND_EXPR_COND (stmt) 5159169689Skan = build2 (NE_EXPR, boolean_type_node, op0, new); 5160169689Skan update_stmt (stmt); 5161169689Skan 5162169689Skan if (dump_file) 5163169689Skan { 5164169689Skan print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0); 5165169689Skan fprintf (dump_file, "\n"); 5166169689Skan } 5167169689Skan return; 5168169689Skan 5169169689Skan } 5170169689Skan } 5171169689Skan } 5172169689Skan} 5173169689Skan 5174169689Skan/* Simplify STMT using ranges if possible. */ 5175169689Skan 5176169689Skanvoid 5177169689Skansimplify_stmt_using_ranges (tree stmt) 5178169689Skan{ 5179169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 5180169689Skan { 5181169689Skan tree rhs = TREE_OPERAND (stmt, 1); 5182169689Skan enum tree_code rhs_code = TREE_CODE (rhs); 5183169689Skan 5184169689Skan /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR 5185169689Skan and BIT_AND_EXPR respectively if the first operand is greater 5186169689Skan than zero and the second operand is an exact power of two. */ 5187169689Skan if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR) 5188169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))) 5189169689Skan && integer_pow2p (TREE_OPERAND (rhs, 1))) 5190169689Skan simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code); 5191169689Skan 5192169689Skan /* Transform ABS (X) into X or -X as appropriate. */ 5193169689Skan if (rhs_code == ABS_EXPR 5194169689Skan && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME 5195169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))) 5196169689Skan simplify_abs_using_ranges (stmt, rhs); 5197169689Skan } 5198169689Skan else if (TREE_CODE (stmt) == COND_EXPR 5199169689Skan && COMPARISON_CLASS_P (COND_EXPR_COND (stmt))) 5200169689Skan { 5201169689Skan simplify_cond_using_ranges (stmt); 5202169689Skan } 5203169689Skan} 5204169689Skan 5205169689Skan/* Stack of dest,src equivalency pairs that need to be restored after 5206169689Skan each attempt to thread a block's incoming edge to an outgoing edge. 5207169689Skan 5208169689Skan A NULL entry is used to mark the end of pairs which need to be 5209169689Skan restored. */ 5210169689Skanstatic VEC(tree,heap) *stack; 5211169689Skan 5212169689Skan/* A trivial wrapper so that we can present the generic jump threading 5213169689Skan code with a simple API for simplifying statements. STMT is the 5214169689Skan statement we want to simplify, WITHIN_STMT provides the location 5215169689Skan for any overflow warnings. */ 5216169689Skan 5217169689Skanstatic tree 5218169689Skansimplify_stmt_for_jump_threading (tree stmt, tree within_stmt) 5219169689Skan{ 5220169689Skan /* We only use VRP information to simplify conditionals. This is 5221169689Skan overly conservative, but it's unclear if doing more would be 5222169689Skan worth the compile time cost. */ 5223169689Skan if (TREE_CODE (stmt) != COND_EXPR) 5224169689Skan return NULL; 5225169689Skan 5226169689Skan return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt); 5227169689Skan} 5228169689Skan 5229169689Skan/* Blocks which have more than one predecessor and more than 5230169689Skan one successor present jump threading opportunities. ie, 5231169689Skan when the block is reached from a specific predecessor, we 5232169689Skan may be able to determine which of the outgoing edges will 5233169689Skan be traversed. When this optimization applies, we are able 5234169689Skan to avoid conditionals at runtime and we may expose secondary 5235169689Skan optimization opportunities. 5236169689Skan 5237169689Skan This routine is effectively a driver for the generic jump 5238169689Skan threading code. It basically just presents the generic code 5239169689Skan with edges that may be suitable for jump threading. 5240169689Skan 5241169689Skan Unlike DOM, we do not iterate VRP if jump threading was successful. 5242169689Skan While iterating may expose new opportunities for VRP, it is expected 5243169689Skan those opportunities would be very limited and the compile time cost 5244169689Skan to expose those opportunities would be significant. 5245169689Skan 5246169689Skan As jump threading opportunities are discovered, they are registered 5247169689Skan for later realization. */ 5248169689Skan 5249169689Skanstatic void 5250169689Skanidentify_jump_threads (void) 5251169689Skan{ 5252169689Skan basic_block bb; 5253169689Skan tree dummy; 5254169689Skan 5255169689Skan /* Ugh. When substituting values earlier in this pass we can 5256169689Skan wipe the dominance information. So rebuild the dominator 5257169689Skan information as we need it within the jump threading code. */ 5258169689Skan calculate_dominance_info (CDI_DOMINATORS); 5259169689Skan 5260169689Skan /* We do not allow VRP information to be used for jump threading 5261169689Skan across a back edge in the CFG. Otherwise it becomes too 5262169689Skan difficult to avoid eliminating loop exit tests. Of course 5263169689Skan EDGE_DFS_BACK is not accurate at this time so we have to 5264169689Skan recompute it. */ 5265169689Skan mark_dfs_back_edges (); 5266169689Skan 5267169689Skan /* Allocate our unwinder stack to unwind any temporary equivalences 5268169689Skan that might be recorded. */ 5269169689Skan stack = VEC_alloc (tree, heap, 20); 5270169689Skan 5271169689Skan /* To avoid lots of silly node creation, we create a single 5272169689Skan conditional and just modify it in-place when attempting to 5273169689Skan thread jumps. */ 5274169689Skan dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL); 5275169689Skan dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL); 5276169689Skan 5277169689Skan /* Walk through all the blocks finding those which present a 5278169689Skan potential jump threading opportunity. We could set this up 5279169689Skan as a dominator walker and record data during the walk, but 5280169689Skan I doubt it's worth the effort for the classes of jump 5281169689Skan threading opportunities we are trying to identify at this 5282169689Skan point in compilation. */ 5283169689Skan FOR_EACH_BB (bb) 5284169689Skan { 5285169689Skan tree last, cond; 5286169689Skan 5287169689Skan /* If the generic jump threading code does not find this block 5288169689Skan interesting, then there is nothing to do. */ 5289169689Skan if (! potentially_threadable_block (bb)) 5290169689Skan continue; 5291169689Skan 5292169689Skan /* We only care about blocks ending in a COND_EXPR. While there 5293169689Skan may be some value in handling SWITCH_EXPR here, I doubt it's 5294169689Skan terribly important. */ 5295169689Skan last = bsi_stmt (bsi_last (bb)); 5296169689Skan if (TREE_CODE (last) != COND_EXPR) 5297169689Skan continue; 5298169689Skan 5299169689Skan /* We're basically looking for any kind of conditional with 5300169689Skan integral type arguments. */ 5301169689Skan cond = COND_EXPR_COND (last); 5302169689Skan if ((TREE_CODE (cond) == SSA_NAME 5303169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (cond))) 5304169689Skan || (COMPARISON_CLASS_P (cond) 5305169689Skan && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME 5306169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0))) 5307169689Skan && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME 5308169689Skan || is_gimple_min_invariant (TREE_OPERAND (cond, 1))) 5309169689Skan && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1))))) 5310169689Skan { 5311169689Skan edge_iterator ei; 5312169689Skan edge e; 5313169689Skan 5314169689Skan /* We've got a block with multiple predecessors and multiple 5315169689Skan successors which also ends in a suitable conditional. For 5316169689Skan each predecessor, see if we can thread it to a specific 5317169689Skan successor. */ 5318169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 5319169689Skan { 5320169689Skan /* Do not thread across back edges or abnormal edges 5321169689Skan in the CFG. */ 5322169689Skan if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) 5323169689Skan continue; 5324169689Skan 5325169689Skan thread_across_edge (dummy, e, true, 5326169689Skan &stack, 5327169689Skan simplify_stmt_for_jump_threading); 5328169689Skan } 5329169689Skan } 5330169689Skan } 5331169689Skan 5332169689Skan /* We do not actually update the CFG or SSA graphs at this point as 5333169689Skan ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet 5334169689Skan handle ASSERT_EXPRs gracefully. */ 5335169689Skan} 5336169689Skan 5337169689Skan/* We identified all the jump threading opportunities earlier, but could 5338169689Skan not transform the CFG at that time. This routine transforms the 5339169689Skan CFG and arranges for the dominator tree to be rebuilt if necessary. 5340169689Skan 5341169689Skan Note the SSA graph update will occur during the normal TODO 5342169689Skan processing by the pass manager. */ 5343169689Skanstatic void 5344169689Skanfinalize_jump_threads (void) 5345169689Skan{ 5346169689Skan bool cfg_altered = false; 5347169689Skan cfg_altered = thread_through_all_blocks (); 5348169689Skan 5349169689Skan /* If we threaded jumps, then we need to recompute the dominance 5350169689Skan information, to safely do that we must clean up the CFG first. */ 5351169689Skan if (cfg_altered) 5352169689Skan { 5353169689Skan free_dominance_info (CDI_DOMINATORS); 5354169689Skan cleanup_tree_cfg (); 5355169689Skan calculate_dominance_info (CDI_DOMINATORS); 5356169689Skan } 5357169689Skan VEC_free (tree, heap, stack); 5358169689Skan} 5359169689Skan 5360169689Skan 5361169689Skan/* Traverse all the blocks folding conditionals with known ranges. */ 5362169689Skan 5363169689Skanstatic void 5364169689Skanvrp_finalize (void) 5365169689Skan{ 5366169689Skan size_t i; 5367169689Skan prop_value_t *single_val_range; 5368169689Skan bool do_value_subst_p; 5369169689Skan 5370169689Skan if (dump_file) 5371169689Skan { 5372169689Skan fprintf (dump_file, "\nValue ranges after VRP:\n\n"); 5373169689Skan dump_all_value_ranges (dump_file); 5374169689Skan fprintf (dump_file, "\n"); 5375169689Skan } 5376169689Skan 5377169689Skan /* We may have ended with ranges that have exactly one value. Those 5378169689Skan values can be substituted as any other copy/const propagated 5379169689Skan value using substitute_and_fold. */ 5380169689Skan single_val_range = XNEWVEC (prop_value_t, num_ssa_names); 5381169689Skan memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range)); 5382169689Skan 5383169689Skan do_value_subst_p = false; 5384169689Skan for (i = 0; i < num_ssa_names; i++) 5385169689Skan if (vr_value[i] 5386169689Skan && vr_value[i]->type == VR_RANGE 5387169689Skan && vr_value[i]->min == vr_value[i]->max) 5388169689Skan { 5389169689Skan single_val_range[i].value = vr_value[i]->min; 5390169689Skan do_value_subst_p = true; 5391169689Skan } 5392169689Skan 5393169689Skan if (!do_value_subst_p) 5394169689Skan { 5395169689Skan /* We found no single-valued ranges, don't waste time trying to 5396169689Skan do single value substitution in substitute_and_fold. */ 5397169689Skan free (single_val_range); 5398169689Skan single_val_range = NULL; 5399169689Skan } 5400169689Skan 5401169689Skan substitute_and_fold (single_val_range, true); 5402169689Skan 5403169689Skan /* We must identify jump threading opportunities before we release 5404169689Skan the datastructures built by VRP. */ 5405169689Skan identify_jump_threads (); 5406169689Skan 5407169689Skan /* Free allocated memory. */ 5408169689Skan for (i = 0; i < num_ssa_names; i++) 5409169689Skan if (vr_value[i]) 5410169689Skan { 5411169689Skan BITMAP_FREE (vr_value[i]->equiv); 5412169689Skan free (vr_value[i]); 5413169689Skan } 5414169689Skan 5415169689Skan free (single_val_range); 5416169689Skan free (vr_value); 5417169689Skan 5418169689Skan /* So that we can distinguish between VRP data being available 5419169689Skan and not available. */ 5420169689Skan vr_value = NULL; 5421169689Skan} 5422169689Skan 5423169689Skan 5424169689Skan/* Main entry point to VRP (Value Range Propagation). This pass is 5425169689Skan loosely based on J. R. C. Patterson, ``Accurate Static Branch 5426169689Skan Prediction by Value Range Propagation,'' in SIGPLAN Conference on 5427169689Skan Programming Language Design and Implementation, pp. 67-78, 1995. 5428169689Skan Also available at http://citeseer.ist.psu.edu/patterson95accurate.html 5429169689Skan 5430169689Skan This is essentially an SSA-CCP pass modified to deal with ranges 5431169689Skan instead of constants. 5432169689Skan 5433169689Skan While propagating ranges, we may find that two or more SSA name 5434169689Skan have equivalent, though distinct ranges. For instance, 5435169689Skan 5436169689Skan 1 x_9 = p_3->a; 5437169689Skan 2 p_4 = ASSERT_EXPR <p_3, p_3 != 0> 5438169689Skan 3 if (p_4 == q_2) 5439169689Skan 4 p_5 = ASSERT_EXPR <p_4, p_4 == q_2>; 5440169689Skan 5 endif 5441169689Skan 6 if (q_2) 5442169689Skan 5443169689Skan In the code above, pointer p_5 has range [q_2, q_2], but from the 5444169689Skan code we can also determine that p_5 cannot be NULL and, if q_2 had 5445169689Skan a non-varying range, p_5's range should also be compatible with it. 5446169689Skan 5447169689Skan These equivalences are created by two expressions: ASSERT_EXPR and 5448169689Skan copy operations. Since p_5 is an assertion on p_4, and p_4 was the 5449169689Skan result of another assertion, then we can use the fact that p_5 and 5450169689Skan p_4 are equivalent when evaluating p_5's range. 5451169689Skan 5452169689Skan Together with value ranges, we also propagate these equivalences 5453169689Skan between names so that we can take advantage of information from 5454169689Skan multiple ranges when doing final replacement. Note that this 5455169689Skan equivalency relation is transitive but not symmetric. 5456169689Skan 5457169689Skan In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we 5458169689Skan cannot assert that q_2 is equivalent to p_5 because q_2 may be used 5459169689Skan in contexts where that assertion does not hold (e.g., in line 6). 5460169689Skan 5461169689Skan TODO, the main difference between this pass and Patterson's is that 5462169689Skan we do not propagate edge probabilities. We only compute whether 5463169689Skan edges can be taken or not. That is, instead of having a spectrum 5464169689Skan of jump probabilities between 0 and 1, we only deal with 0, 1 and 5465169689Skan DON'T KNOW. In the future, it may be worthwhile to propagate 5466169689Skan probabilities to aid branch prediction. */ 5467169689Skan 5468169689Skanstatic unsigned int 5469169689Skanexecute_vrp (void) 5470169689Skan{ 5471169689Skan insert_range_assertions (); 5472169689Skan 5473169689Skan current_loops = loop_optimizer_init (LOOPS_NORMAL); 5474169689Skan if (current_loops) 5475169689Skan scev_initialize (current_loops); 5476169689Skan 5477169689Skan vrp_initialize (); 5478169689Skan ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); 5479169689Skan vrp_finalize (); 5480169689Skan 5481169689Skan if (current_loops) 5482169689Skan { 5483169689Skan scev_finalize (); 5484169689Skan loop_optimizer_finalize (current_loops); 5485169689Skan current_loops = NULL; 5486169689Skan } 5487169689Skan 5488169689Skan /* ASSERT_EXPRs must be removed before finalizing jump threads 5489169689Skan as finalizing jump threads calls the CFG cleanup code which 5490169689Skan does not properly handle ASSERT_EXPRs. */ 5491169689Skan remove_range_assertions (); 5492169689Skan 5493169689Skan /* If we exposed any new variables, go ahead and put them into 5494169689Skan SSA form now, before we handle jump threading. This simplifies 5495169689Skan interactions between rewriting of _DECL nodes into SSA form 5496169689Skan and rewriting SSA_NAME nodes into SSA form after block 5497169689Skan duplication and CFG manipulation. */ 5498169689Skan update_ssa (TODO_update_ssa); 5499169689Skan 5500169689Skan finalize_jump_threads (); 5501169689Skan return 0; 5502169689Skan} 5503169689Skan 5504169689Skanstatic bool 5505169689Skangate_vrp (void) 5506169689Skan{ 5507169689Skan return flag_tree_vrp != 0; 5508169689Skan} 5509169689Skan 5510169689Skanstruct tree_opt_pass pass_vrp = 5511169689Skan{ 5512169689Skan "vrp", /* name */ 5513169689Skan gate_vrp, /* gate */ 5514169689Skan execute_vrp, /* execute */ 5515169689Skan NULL, /* sub */ 5516169689Skan NULL, /* next */ 5517169689Skan 0, /* static_pass_number */ 5518169689Skan TV_TREE_VRP, /* tv_id */ 5519169689Skan PROP_ssa | PROP_alias, /* properties_required */ 5520169689Skan 0, /* properties_provided */ 5521169689Skan PROP_smt_usage, /* properties_destroyed */ 5522169689Skan 0, /* todo_flags_start */ 5523169689Skan TODO_cleanup_cfg 5524169689Skan | TODO_ggc_collect 5525169689Skan | TODO_verify_ssa 5526169689Skan | TODO_dump_func 5527169689Skan | TODO_update_ssa 5528169689Skan | TODO_update_smt_usage, /* todo_flags_finish */ 5529169689Skan 0 /* letter */ 5530169689Skan}; 5531