gcc/tree-vrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "flags.h"
  27 #include "tree.h"
  28 #include "basic-block.h"
  29 #include "tree-flow.h"
  30 #include "tree-pass.h"
  31 #include "tree-dump.h"
  32 #include "timevar.h"
  33 #include "diagnostic.h"
  34 #include "toplev.h"
  35 #include "intl.h"
  36 #include "cfgloop.h"
  37 #include "tree-scalar-evolution.h"
  38 #include "tree-ssa-propagate.h"
  39 #include "tree-chrec.h"
  40
  41 /* Set of SSA names found during the dominator traversal of a
  42    sub-graph in find_assert_locations.  */
  43 static sbitmap found_in_subgraph;
  44
  45 /* Local functions.  */
  46 static int compare_values (tree val1, tree val2);
  47 static int compare_values_warnv (tree val1, tree val2, bool *);
  48 static void vrp_meet (value_range_t *, value_range_t *);
  49 static tree vrp_evaluate_conditional_warnv (tree, bool, bool *);
  50 static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
  51                                                      tree, tree, bool, bool *);
  52
  53 /* Location information for ASSERT_EXPRs.  Each instance of this
  54    structure describes an ASSERT_EXPR for an SSA name.  Since a single
  55    SSA name may have more than one assertion associated with it, these
  56    locations are kept in a linked list attached to the corresponding
  57    SSA name.  */
  58 struct assert_locus_d
  59 {
  60   /* Basic block where the assertion would be inserted.  */
  61   basic_block bb;
  62
  63   /* Some assertions need to be inserted on an edge (e.g., assertions
  64      generated by COND_EXPRs).  In those cases, BB will be NULL.  */
  65   edge e;
  66
  67   /* Pointer to the statement that generated this assertion.  */
  68   block_stmt_iterator si;
  69
  70   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
  71   enum tree_code comp_code;
  72
  73   /* Value being compared against.  */
  74   tree val;
  75
  76   /* Expression to compare.  */
  77   tree expr;
  78
  79   /* Next node in the linked list.  */
  80   struct assert_locus_d *next;
  81 };
  82
  83 typedef struct assert_locus_d *assert_locus_t;
  84
  85 /* If bit I is present, it means that SSA name N_i has a list of
  86    assertions that should be inserted in the IL.  */
  87 static bitmap need_assert_for;
  88
  89 /* Array of locations lists where to insert assertions.  ASSERTS_FOR[I]
  90    holds a list of ASSERT_LOCUS_T nodes that describe where
  91    ASSERT_EXPRs for SSA name N_I should be inserted.  */
  92 static assert_locus_t *asserts_for;
  93
  94 /* Set of blocks visited in find_assert_locations.  Used to avoid
  95    visiting the same block more than once.  */
  96 static sbitmap blocks_visited;
  97
  98 /* Value range array.  After propagation, VR_VALUE[I] holds the range
  99    of values that SSA name N_I may take.  */
 100 static value_range_t **vr_value;
 101
 102 /* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
 103    number of executable edges we saw the last time we visited the
 104    node.  */
 105 static int *vr_phi_edge_counts;
 106
 107 typedef struct {
 108   tree stmt;
 109   tree vec;
 110 } switch_update;
 111
 112 static VEC (edge, heap) *to_remove_edges;
 113 DEF_VEC_O(switch_update);
 114 DEF_VEC_ALLOC_O(switch_update, heap);
 115 static VEC (switch_update, heap) *to_update_switch_stmts;
 116
 117
 118 /* Return the maximum value for TYPEs base type.  */
 119
 120 static inline tree
 121 vrp_val_max (const_tree type)
 122 {
 123   if (!INTEGRAL_TYPE_P (type))
 124     return NULL_TREE;
 125
 126   /* For integer sub-types the values for the base type are relevant.  */
 127   if (TREE_TYPE (type))
 128     type = TREE_TYPE (type);
 129
 130   return TYPE_MAX_VALUE (type);
 131 }
 132
 133 /* Return the minimum value for TYPEs base type.  */
 134
 135 static inline tree
 136 vrp_val_min (const_tree type)
 137 {
 138   if (!INTEGRAL_TYPE_P (type))
 139     return NULL_TREE;
 140
 141   /* For integer sub-types the values for the base type are relevant.  */
 142   if (TREE_TYPE (type))
 143     type = TREE_TYPE (type);
 144
 145   return TYPE_MIN_VALUE (type);
 146 }
 147
 148 /* Return whether VAL is equal to the maximum value of its type.  This
 149    will be true for a positive overflow infinity.  We can't do a
 150    simple equality comparison with TYPE_MAX_VALUE because C typedefs
 151    and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
 152    to the integer constant with the same value in the type.  */
 153
 154 static inline bool
 155 vrp_val_is_max (const_tree val)
 156 {
 157   tree type_max = vrp_val_max (TREE_TYPE (val));
 158   return (val == type_max
 159           || (type_max != NULL_TREE
 160               && operand_equal_p (val, type_max, 0)));
 161 }
 162
 163 /* Return whether VAL is equal to the minimum value of its type.  This
 164    will be true for a negative overflow infinity.  */
 165
 166 static inline bool
 167 vrp_val_is_min (const_tree val)
 168 {
 169   tree type_min = vrp_val_min (TREE_TYPE (val));
 170   return (val == type_min
 171           || (type_min != NULL_TREE
 172               && operand_equal_p (val, type_min, 0)));
 173 }
 174
 175
 176 /* Return whether TYPE should use an overflow infinity distinct from
 177    TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
 178    represent a signed overflow during VRP computations.  An infinity
 179    is distinct from a half-range, which will go from some number to
 180    TYPE_{MIN,MAX}_VALUE.  */
 181
 182 static inline bool
 183 needs_overflow_infinity (const_tree type)
 184 {
 185   return (INTEGRAL_TYPE_P (type)
 186           && !TYPE_OVERFLOW_WRAPS (type)
 187           /* Integer sub-types never overflow as they are never
 188              operands of arithmetic operators.  */
 189           && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
 190 }
 191
 192 /* Return whether TYPE can support our overflow infinity
 193    representation: we use the TREE_OVERFLOW flag, which only exists
 194    for constants.  If TYPE doesn't support this, we don't optimize
 195    cases which would require signed overflow--we drop them to
 196    VARYING.  */
 197
 198 static inline bool
 199 supports_overflow_infinity (const_tree type)
 200 {
 201   tree min = vrp_val_min (type), max = vrp_val_max (type);
 202 #ifdef ENABLE_CHECKING
 203   gcc_assert (needs_overflow_infinity (type));
 204 #endif
 205   return (min != NULL_TREE
 206           && CONSTANT_CLASS_P (min)
 207           && max != NULL_TREE
 208           && CONSTANT_CLASS_P (max));
 209 }
 210
 211 /* VAL is the maximum or minimum value of a type.  Return a
 212    corresponding overflow infinity.  */
 213
 214 static inline tree
 215 make_overflow_infinity (tree val)
 216 {
 217 #ifdef ENABLE_CHECKING
 218   gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
 219 #endif
 220   val = copy_node (val);
 221   TREE_OVERFLOW (val) = 1;
 222   return val;
 223 }
 224
 225 /* Return a negative overflow infinity for TYPE.  */
 226
 227 static inline tree
 228 negative_overflow_infinity (tree type)
 229 {
 230 #ifdef ENABLE_CHECKING
 231   gcc_assert (supports_overflow_infinity (type));
 232 #endif
 233   return make_overflow_infinity (vrp_val_min (type));
 234 }
 235
 236 /* Return a positive overflow infinity for TYPE.  */
 237
 238 static inline tree
 239 positive_overflow_infinity (tree type)
 240 {
 241 #ifdef ENABLE_CHECKING
 242   gcc_assert (supports_overflow_infinity (type));
 243 #endif
 244   return make_overflow_infinity (vrp_val_max (type));
 245 }
 246
 247 /* Return whether VAL is a negative overflow infinity.  */
 248
 249 static inline bool
 250 is_negative_overflow_infinity (const_tree val)
 251 {
 252   return (needs_overflow_infinity (TREE_TYPE (val))
 253           && CONSTANT_CLASS_P (val)
 254           && TREE_OVERFLOW (val)
 255           && vrp_val_is_min (val));
 256 }
 257
 258 /* Return whether VAL is a positive overflow infinity.  */
 259
 260 static inline bool
 261 is_positive_overflow_infinity (const_tree val)
 262 {
 263   return (needs_overflow_infinity (TREE_TYPE (val))
 264           && CONSTANT_CLASS_P (val)
 265           && TREE_OVERFLOW (val)
 266           && vrp_val_is_max (val));
 267 }
 268
 269 /* Return whether VAL is a positive or negative overflow infinity.  */
 270
 271 static inline bool
 272 is_overflow_infinity (const_tree val)
 273 {
 274   return (needs_overflow_infinity (TREE_TYPE (val))
 275           && CONSTANT_CLASS_P (val)
 276           && TREE_OVERFLOW (val)
 277           && (vrp_val_is_min (val) || vrp_val_is_max (val)));
 278 }
 279
 280 /* If VAL is now an overflow infinity, return VAL.  Otherwise, return
 281    the same value with TREE_OVERFLOW clear.  This can be used to avoid
 282    confusing a regular value with an overflow value.  */
 283
 284 static inline tree
 285 avoid_overflow_infinity (tree val)
 286 {
 287   if (!is_overflow_infinity (val))
 288     return val;
 289
 290   if (vrp_val_is_max (val))
 291     return vrp_val_max (TREE_TYPE (val));
 292   else
 293     {
 294 #ifdef ENABLE_CHECKING
 295       gcc_assert (vrp_val_is_min (val));
 296 #endif
 297       return vrp_val_min (TREE_TYPE (val));
 298     }
 299 }
 300
 301
 302 /* Return true if ARG is marked with the nonnull attribute in the
 303    current function signature.  */
 304
 305 static bool
 306 nonnull_arg_p (const_tree arg)
 307 {
 308   tree t, attrs, fntype;
 309   unsigned HOST_WIDE_INT arg_num;
 310
 311   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
 312
 313   /* The static chain decl is always non null.  */
 314   if (arg == cfun->static_chain_decl)
 315     return true;
 316
 317   fntype = TREE_TYPE (current_function_decl);
 318   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
 319
 320   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
 321   if (attrs == NULL_TREE)
 322     return false;
 323
 324   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
 325   if (TREE_VALUE (attrs) == NULL_TREE)
 326     return true;
 327
 328   /* Get the position number for ARG in the function signature.  */
 329   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
 330        t;
 331        t = TREE_CHAIN (t), arg_num++)
 332     {
 333       if (t == arg)
 334         break;
 335     }
 336
 337   gcc_assert (t == arg);
 338
 339   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
 340   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
 341     {
 342       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
 343         return true;
 344     }
 345
 346   return false;
 347 }
 348
 349
 350 /* Set value range VR to VR_VARYING.  */
 351
 352 static inline void
 353 set_value_range_to_varying (value_range_t *vr)
 354 {
 355   vr->type = VR_VARYING;
 356   vr->min = vr->max = NULL_TREE;
 357   if (vr->equiv)
 358     bitmap_clear (vr->equiv);
 359 }
 360
 361
 362 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
 363
 364 static void
 365 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 366                  tree max, bitmap equiv)
 367 {
 368 #if defined ENABLE_CHECKING
 369   /* Check the validity of the range.  */
 370   if (t == VR_RANGE || t == VR_ANTI_RANGE)
 371     {
 372       int cmp;
 373
 374       gcc_assert (min && max);
 375
 376       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
 377         gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
 378
 379       cmp = compare_values (min, max);
 380       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
 381
 382       if (needs_overflow_infinity (TREE_TYPE (min)))
 383         gcc_assert (!is_overflow_infinity (min)
 384                     || !is_overflow_infinity (max));
 385     }
 386
 387   if (t == VR_UNDEFINED || t == VR_VARYING)
 388     gcc_assert (min == NULL_TREE && max == NULL_TREE);
 389
 390   if (t == VR_UNDEFINED || t == VR_VARYING)
 391     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
 392 #endif
 393
 394   vr->type = t;
 395   vr->min = min;
 396   vr->max = max;
 397
 398   /* Since updating the equivalence set involves deep copying the
 399      bitmaps, only do it if absolutely necessary.  */
 400   if (vr->equiv == NULL
 401       && equiv != NULL)
 402     vr->equiv = BITMAP_ALLOC (NULL);
 403
 404   if (equiv != vr->equiv)
 405     {
 406       if (equiv && !bitmap_empty_p (equiv))
 407         bitmap_copy (vr->equiv, equiv);
 408       else
 409         bitmap_clear (vr->equiv);
 410     }
 411 }
 412
 413
 414 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
 415    This means adjusting T, MIN and MAX representing the case of a
 416    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
 417    as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
 418    In corner cases where MAX+1 or MIN-1 wraps this will fall back
 419    to varying.
 420    This routine exists to ease canonicalization in the case where we
 421    extract ranges from var + CST op limit.  */
 422
 423 static void
 424 set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
 425                                   tree min, tree max, bitmap equiv)
 426 {
 427   /* Nothing to canonicalize for symbolic or unknown or varying ranges.  */
 428   if ((t != VR_RANGE
 429        && t != VR_ANTI_RANGE)
 430       || TREE_CODE (min) != INTEGER_CST
 431       || TREE_CODE (max) != INTEGER_CST)
 432     {
 433       set_value_range (vr, t, min, max, equiv);
 434       return;
 435     }
 436
 437   /* Wrong order for min and max, to swap them and the VR type we need
 438      to adjust them.  */
 439   if (tree_int_cst_lt (max, min))
 440     {
 441       tree one = build_int_cst (TREE_TYPE (min), 1);
 442       tree tmp = int_const_binop (PLUS_EXPR, max, one, 0);
 443       max = int_const_binop (MINUS_EXPR, min, one, 0);
 444       min = tmp;
 445
 446       /* There's one corner case, if we had [C+1, C] before we now have
 447          that again.  But this represents an empty value range, so drop
 448          to varying in this case.  */
 449       if (tree_int_cst_lt (max, min))
 450         {
 451           set_value_range_to_varying (vr);
 452           return;
 453         }
 454
 455       t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
 456     }
 457
 458   /* Anti-ranges that can be represented as ranges should be so.  */
 459   if (t == VR_ANTI_RANGE)
 460     {
 461       bool is_min = vrp_val_is_min (min);
 462       bool is_max = vrp_val_is_max (max);
 463
 464       if (is_min && is_max)
 465         {
 466           /* We cannot deal with empty ranges, drop to varying.  */
 467           set_value_range_to_varying (vr);
 468           return;
 469         }
 470       else if (is_min
 471                /* As a special exception preserve non-null ranges.  */
 472                && !(TYPE_UNSIGNED (TREE_TYPE (min))
 473                     && integer_zerop (max)))
 474         {
 475           tree one = build_int_cst (TREE_TYPE (max), 1);
 476           min = int_const_binop (PLUS_EXPR, max, one, 0);
 477           max = vrp_val_max (TREE_TYPE (max));
 478           t = VR_RANGE;
 479         }
 480       else if (is_max)
 481         {
 482           tree one = build_int_cst (TREE_TYPE (min), 1);
 483           max = int_const_binop (MINUS_EXPR, min, one, 0);
 484           min = vrp_val_min (TREE_TYPE (min));
 485           t = VR_RANGE;
 486         }
 487     }
 488
 489   set_value_range (vr, t, min, max, equiv);
 490 }
 491
 492 /* Copy value range FROM into value range TO.  */
 493
 494 static inline void
 495 copy_value_range (value_range_t *to, value_range_t *from)
 496 {
 497   set_value_range (to, from->type, from->min, from->max, from->equiv);
 498 }
 499
 500 /* Set value range VR to a single value.  This function is only called
 501    with values we get from statements, and exists to clear the
 502    TREE_OVERFLOW flag so that we don't think we have an overflow
 503    infinity when we shouldn't.  */
 504
 505 static inline void
 506 set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
 507 {
 508   gcc_assert (is_gimple_min_invariant (val));
 509   val = avoid_overflow_infinity (val);
 510   set_value_range (vr, VR_RANGE, val, val, equiv);
 511 }
 512
 513 /* Set value range VR to a non-negative range of type TYPE.
 514    OVERFLOW_INFINITY indicates whether to use an overflow infinity
 515    rather than TYPE_MAX_VALUE; this should be true if we determine
 516    that the range is nonnegative based on the assumption that signed
 517    overflow does not occur.  */
 518
 519 static inline void
 520 set_value_range_to_nonnegative (value_range_t *vr, tree type,
 521                                 bool overflow_infinity)
 522 {
 523   tree zero;
 524
 525   if (overflow_infinity && !supports_overflow_infinity (type))
 526     {
 527       set_value_range_to_varying (vr);
 528       return;
 529     }
 530
 531   zero = build_int_cst (type, 0);
 532   set_value_range (vr, VR_RANGE, zero,
 533                    (overflow_infinity
 534                     ? positive_overflow_infinity (type)
 535                     : TYPE_MAX_VALUE (type)),
 536                    vr->equiv);
 537 }
 538
 539 /* Set value range VR to a non-NULL range of type TYPE.  */
 540
 541 static inline void
 542 set_value_range_to_nonnull (value_range_t *vr, tree type)
 543 {
 544   tree zero = build_int_cst (type, 0);
 545   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
 546 }
 547
 548
 549 /* Set value range VR to a NULL range of type TYPE.  */
 550
 551 static inline void
 552 set_value_range_to_null (value_range_t *vr, tree type)
 553 {
 554   set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
 555 }
 556
 557
 558 /* Set value range VR to a range of a truthvalue of type TYPE.  */
 559
 560 static inline void
 561 set_value_range_to_truthvalue (value_range_t *vr, tree type)
 562 {
 563   if (TYPE_PRECISION (type) == 1)
 564     set_value_range_to_varying (vr);
 565   else
 566     set_value_range (vr, VR_RANGE,
 567                      build_int_cst (type, 0), build_int_cst (type, 1),
 568                      vr->equiv);
 569 }
 570
 571
 572 /* Set value range VR to VR_UNDEFINED.  */
 573
 574 static inline void
 575 set_value_range_to_undefined (value_range_t *vr)
 576 {
 577   vr->type = VR_UNDEFINED;
 578   vr->min = vr->max = NULL_TREE;
 579   if (vr->equiv)
 580     bitmap_clear (vr->equiv);
 581 }
 582
 583
 584 /* Return value range information for VAR.
 585
 586    If we have no values ranges recorded (ie, VRP is not running), then
 587    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 588
 589 static value_range_t *
 590 get_value_range (const_tree var)
 591 {
 592   value_range_t *vr;
 593   tree sym;
 594   unsigned ver = SSA_NAME_VERSION (var);
 595
 596   /* If we have no recorded ranges, then return NULL.  */
 597   if (! vr_value)
 598     return NULL;
 599
 600   vr = vr_value[ver];
 601   if (vr)
 602     return vr;
 603
 604   /* Create a default value range.  */
 605   vr_value[ver] = vr = XCNEW (value_range_t);
 606
 607   /* Defer allocating the equivalence set.  */
 608   vr->equiv = NULL;
 609
 610   /* If VAR is a default definition, the variable can take any value
 611      in VAR's type.  */
 612   sym = SSA_NAME_VAR (var);
 613   if (SSA_NAME_IS_DEFAULT_DEF (var))
 614     {
 615       /* Try to use the "nonnull" attribute to create ~[0, 0]
 616          anti-ranges for pointers.  Note that this is only valid with
 617          default definitions of PARM_DECLs.  */
 618       if (TREE_CODE (sym) == PARM_DECL
 619           && POINTER_TYPE_P (TREE_TYPE (sym))
 620           && nonnull_arg_p (sym))
 621         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
 622       else
 623         set_value_range_to_varying (vr);
 624     }
 625
 626   return vr;
 627 }
 628
 629 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
 630
 631 static inline bool
 632 vrp_operand_equal_p (const_tree val1, const_tree val2)
 633 {
 634   if (val1 == val2)
 635     return true;
 636   if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
 637     return false;
 638   if (is_overflow_infinity (val1))
 639     return is_overflow_infinity (val2);
 640   return true;
 641 }
 642
 643 /* Return true, if the bitmaps B1 and B2 are equal.  */
 644
 645 static inline bool
 646 vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 647 {
 648   return (b1 == b2
 649           || (b1 && b2
 650               && bitmap_equal_p (b1, b2)));
 651 }
 652
 653 /* Update the value range and equivalence set for variable VAR to
 654    NEW_VR.  Return true if NEW_VR is different from VAR's previous
 655    value.
 656
 657    NOTE: This function assumes that NEW_VR is a temporary value range
 658    object created for the sole purpose of updating VAR's range.  The
 659    storage used by the equivalence set from NEW_VR will be freed by
 660    this function.  Do not call update_value_range when NEW_VR
 661    is the range object associated with another SSA name.  */
 662
 663 static inline bool
 664 update_value_range (const_tree var, value_range_t *new_vr)
 665 {
 666   value_range_t *old_vr;
 667   bool is_new;
 668
 669   /* Update the value range, if necessary.  */
 670   old_vr = get_value_range (var);
 671   is_new = old_vr->type != new_vr->type
 672            || !vrp_operand_equal_p (old_vr->min, new_vr->min)
 673            || !vrp_operand_equal_p (old_vr->max, new_vr->max)
 674            || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
 675
 676   if (is_new)
 677     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
 678                      new_vr->equiv);
 679
 680   BITMAP_FREE (new_vr->equiv);
 681
 682   return is_new;
 683 }
 684
 685
 686 /* Add VAR and VAR's equivalence set to EQUIV.  This is the central
 687    point where equivalence processing can be turned on/off.  */
 688
 689 static void
 690 add_equivalence (bitmap *equiv, const_tree var)
 691 {
 692   unsigned ver = SSA_NAME_VERSION (var);
 693   value_range_t *vr = vr_value[ver];
 694
 695   if (*equiv == NULL)
 696     *equiv = BITMAP_ALLOC (NULL);
 697   bitmap_set_bit (*equiv, ver);
 698   if (vr && vr->equiv)
 699     bitmap_ior_into (*equiv, vr->equiv);
 700 }
 701
 702
 703 /* Return true if VR is ~[0, 0].  */
 704
 705 static inline bool
 706 range_is_nonnull (value_range_t *vr)
 707 {
 708   return vr->type == VR_ANTI_RANGE
 709          && integer_zerop (vr->min)
 710          && integer_zerop (vr->max);
 711 }
 712
 713
 714 /* Return true if VR is [0, 0].  */
 715
 716 static inline bool
 717 range_is_null (value_range_t *vr)
 718 {
 719   return vr->type == VR_RANGE
 720          && integer_zerop (vr->min)
 721          && integer_zerop (vr->max);
 722 }
 723
 724
 725 /* Return true if value range VR involves at least one symbol.  */
 726
 727 static inline bool
 728 symbolic_range_p (value_range_t *vr)
 729 {
 730   return (!is_gimple_min_invariant (vr->min)
 731           || !is_gimple_min_invariant (vr->max));
 732 }
 733
 734 /* Return true if value range VR uses an overflow infinity.  */
 735
 736 static inline bool
 737 overflow_infinity_range_p (value_range_t *vr)
 738 {
 739   return (vr->type == VR_RANGE
 740           && (is_overflow_infinity (vr->min)
 741               || is_overflow_infinity (vr->max)));
 742 }
 743
 744 /* Return false if we can not make a valid comparison based on VR;
 745    this will be the case if it uses an overflow infinity and overflow
 746    is not undefined (i.e., -fno-strict-overflow is in effect).
 747    Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
 748    uses an overflow infinity.  */
 749
 750 static bool
 751 usable_range_p (value_range_t *vr, bool *strict_overflow_p)
 752 {
 753   gcc_assert (vr->type == VR_RANGE);
 754   if (is_overflow_infinity (vr->min))
 755     {
 756       *strict_overflow_p = true;
 757       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
 758         return false;
 759     }
 760   if (is_overflow_infinity (vr->max))
 761     {
 762       *strict_overflow_p = true;
 763       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
 764         return false;
 765     }
 766   return true;
 767 }
 768
 769
 770 /* Like tree_expr_nonnegative_warnv_p, but this function uses value
 771    ranges obtained so far.  */
 772
 773 static bool
 774 vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
 775 {
 776   return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p);
 777 }
 778
 779 /* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
 780    obtained so far.  */
 781
 782 static bool
 783 vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p)
 784 {
 785   if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p))
 786     return true;
 787
 788   /* If we have an expression of the form &X->a, then the expression
 789      is nonnull if X is nonnull.  */
 790   if (TREE_CODE (expr) == ADDR_EXPR)
 791     {
 792       tree base = get_base_address (TREE_OPERAND (expr, 0));
 793
 794       if (base != NULL_TREE
 795           && TREE_CODE (base) == INDIRECT_REF
 796           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
 797         {
 798           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
 799           if (range_is_nonnull (vr))
 800             return true;
 801         }
 802     }
 803
 804   return false;
 805 }
 806
 807 /* Returns true if EXPR is a valid value (as expected by compare_values) --
 808    a gimple invariant, or SSA_NAME +- CST.  */
 809
 810 static bool
 811 valid_value_p (tree expr)
 812 {
 813   if (TREE_CODE (expr) == SSA_NAME)
 814     return true;
 815
 816   if (TREE_CODE (expr) == PLUS_EXPR
 817       || TREE_CODE (expr) == MINUS_EXPR)
 818     return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
 819             && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
 820
 821   return is_gimple_min_invariant (expr);
 822 }
 823
 824 /* Return
 825    1 if VAL < VAL2
 826    0 if !(VAL < VAL2)
 827    -2 if those are incomparable.  */
 828 static inline int
 829 operand_less_p (tree val, tree val2)
 830 {
 831   /* LT is folded faster than GE and others.  Inline the common case.  */
 832   if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
 833     {
 834       if (TYPE_UNSIGNED (TREE_TYPE (val)))
 835         return INT_CST_LT_UNSIGNED (val, val2);
 836       else
 837         {
 838           if (INT_CST_LT (val, val2))
 839             return 1;
 840         }
 841     }
 842   else
 843     {
 844       tree tcmp;
 845
 846       fold_defer_overflow_warnings ();
 847
 848       tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
 849
 850       fold_undefer_and_ignore_overflow_warnings ();
 851
 852       if (!tcmp
 853           || TREE_CODE (tcmp) != INTEGER_CST)
 854         return -2;
 855
 856       if (!integer_zerop (tcmp))
 857         return 1;
 858     }
 859
 860   /* val >= val2, not considering overflow infinity.  */
 861   if (is_negative_overflow_infinity (val))
 862     return is_negative_overflow_infinity (val2) ? 0 : 1;
 863   else if (is_positive_overflow_infinity (val2))
 864     return is_positive_overflow_infinity (val) ? 0 : 1;
 865
 866   return 0;
 867 }
 868
 869 /* Compare two values VAL1 and VAL2.  Return
 870
 871         -2 if VAL1 and VAL2 cannot be compared at compile-time,
 872         -1 if VAL1 < VAL2,
 873          0 if VAL1 == VAL2,
 874         +1 if VAL1 > VAL2, and
 875         +2 if VAL1 != VAL2
 876
 877    This is similar to tree_int_cst_compare but supports pointer values
 878    and values that cannot be compared at compile time.
 879
 880    If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
 881    true if the return value is only valid if we assume that signed
 882    overflow is undefined.  */
 883
 884 static int
 885 compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
 886 {
 887   if (val1 == val2)
 888     return 0;
 889
 890   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
 891      both integers.  */
 892   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
 893               == POINTER_TYPE_P (TREE_TYPE (val2)));
 894   /* Convert the two values into the same type.  This is needed because
 895      sizetype causes sign extension even for unsigned types.  */
 896   val2 = fold_convert (TREE_TYPE (val1), val2);
 897   STRIP_USELESS_TYPE_CONVERSION (val2);
 898
 899   if ((TREE_CODE (val1) == SSA_NAME
 900        || TREE_CODE (val1) == PLUS_EXPR
 901        || TREE_CODE (val1) == MINUS_EXPR)
 902       && (TREE_CODE (val2) == SSA_NAME
 903           || TREE_CODE (val2) == PLUS_EXPR
 904           || TREE_CODE (val2) == MINUS_EXPR))
 905     {
 906       tree n1, c1, n2, c2;
 907       enum tree_code code1, code2;
 908
 909       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
 910          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
 911          same name, return -2.  */
 912       if (TREE_CODE (val1) == SSA_NAME)
 913         {
 914           code1 = SSA_NAME;
 915           n1 = val1;
 916           c1 = NULL_TREE;
 917         }
 918       else
 919         {
 920           code1 = TREE_CODE (val1);
 921           n1 = TREE_OPERAND (val1, 0);
 922           c1 = TREE_OPERAND (val1, 1);
 923           if (tree_int_cst_sgn (c1) == -1)
 924             {
 925               if (is_negative_overflow_infinity (c1))
 926                 return -2;
 927               c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
 928               if (!c1)
 929                 return -2;
 930               code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 931             }
 932         }
 933
 934       if (TREE_CODE (val2) == SSA_NAME)
 935         {
 936           code2 = SSA_NAME;
 937           n2 = val2;
 938           c2 = NULL_TREE;
 939         }
 940       else
 941         {
 942           code2 = TREE_CODE (val2);
 943           n2 = TREE_OPERAND (val2, 0);
 944           c2 = TREE_OPERAND (val2, 1);
 945           if (tree_int_cst_sgn (c2) == -1)
 946             {
 947               if (is_negative_overflow_infinity (c2))
 948                 return -2;
 949               c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
 950               if (!c2)
 951                 return -2;
 952               code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 953             }
 954         }
 955
 956       /* Both values must use the same name.  */
 957       if (n1 != n2)
 958         return -2;
 959
 960       if (code1 == SSA_NAME
 961           && code2 == SSA_NAME)
 962         /* NAME == NAME  */
 963         return 0;
 964
 965       /* If overflow is defined we cannot simplify more.  */
 966       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
 967         return -2;
 968
 969       if (strict_overflow_p != NULL
 970           && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
 971           && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
 972         *strict_overflow_p = true;
 973
 974       if (code1 == SSA_NAME)
 975         {
 976           if (code2 == PLUS_EXPR)
 977             /* NAME < NAME + CST  */
 978             return -1;
 979           else if (code2 == MINUS_EXPR)
 980             /* NAME > NAME - CST  */
 981             return 1;
 982         }
 983       else if (code1 == PLUS_EXPR)
 984         {
 985           if (code2 == SSA_NAME)
 986             /* NAME + CST > NAME  */
 987             return 1;
 988           else if (code2 == PLUS_EXPR)
 989             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
 990             return compare_values_warnv (c1, c2, strict_overflow_p);
 991           else if (code2 == MINUS_EXPR)
 992             /* NAME + CST1 > NAME - CST2  */
 993             return 1;
 994         }
 995       else if (code1 == MINUS_EXPR)
 996         {
 997           if (code2 == SSA_NAME)
 998             /* NAME - CST < NAME  */
 999             return -1;
1000           else if (code2 == PLUS_EXPR)
1001             /* NAME - CST1 < NAME + CST2  */
1002             return -1;
1003           else if (code2 == MINUS_EXPR)
1004             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
1005                C1 and C2 are swapped in the call to compare_values.  */
1006             return compare_values_warnv (c2, c1, strict_overflow_p);
1007         }
1008
1009       gcc_unreachable ();
1010     }
1011
1012   /* We cannot compare non-constants.  */
1013   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
1014     return -2;
1015
1016   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
1017     {
1018       /* We cannot compare overflowed values, except for overflow
1019          infinities.  */
1020       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
1021         {
1022           if (strict_overflow_p != NULL)
1023             *strict_overflow_p = true;
1024           if (is_negative_overflow_infinity (val1))
1025             return is_negative_overflow_infinity (val2) ? 0 : -1;
1026           else if (is_negative_overflow_infinity (val2))
1027             return 1;
1028           else if (is_positive_overflow_infinity (val1))
1029             return is_positive_overflow_infinity (val2) ? 0 : 1;
1030           else if (is_positive_overflow_infinity (val2))
1031             return -1;
1032           return -2;
1033         }
1034
1035       return tree_int_cst_compare (val1, val2);
1036     }
1037   else
1038     {
1039       tree t;
1040
1041       /* First see if VAL1 and VAL2 are not the same.  */
1042       if (val1 == val2 || operand_equal_p (val1, val2, 0))
1043         return 0;
1044
1045       /* If VAL1 is a lower address than VAL2, return -1.  */
1046       if (operand_less_p (val1, val2) == 1)
1047         return -1;
1048
1049       /* If VAL1 is a higher address than VAL2, return +1.  */
1050       if (operand_less_p (val2, val1) == 1)
1051         return 1;
1052
1053       /* If VAL1 is different than VAL2, return +2.
1054          For integer constants we either have already returned -1 or 1
1055          or they are equivalent.  We still might succeed in proving
1056          something about non-trivial operands.  */
1057       if (TREE_CODE (val1) != INTEGER_CST
1058           || TREE_CODE (val2) != INTEGER_CST)
1059         {
1060           t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
1061           if (t && integer_onep (t))
1062             return 2;
1063         }
1064
1065       return -2;
1066     }
1067 }
1068
1069 /* Compare values like compare_values_warnv, but treat comparisons of
1070    nonconstants which rely on undefined overflow as incomparable.  */
1071
1072 static int
1073 compare_values (tree val1, tree val2)
1074 {
1075   bool sop;
1076   int ret;
1077
1078   sop = false;
1079   ret = compare_values_warnv (val1, val2, &sop);
1080   if (sop
1081       && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
1082     ret = -2;
1083   return ret;
1084 }
1085
1086
1087 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
1088           0 if VAL is not inside VR,
1089          -2 if we cannot tell either way.
1090
1091    FIXME, the current semantics of this functions are a bit quirky
1092           when taken in the context of VRP.  In here we do not care
1093           about VR's type.  If VR is the anti-range ~[3, 5] the call
1094           value_inside_range (4, VR) will return 1.
1095
1096           This is counter-intuitive in a strict sense, but the callers
1097           currently expect this.  They are calling the function
1098           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
1099           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
1100           themselves.
1101
1102           This also applies to value_ranges_intersect_p and
1103           range_includes_zero_p.  The semantics of VR_RANGE and
1104           VR_ANTI_RANGE should be encoded here, but that also means
1105           adapting the users of these functions to the new semantics.
1106
1107    Benchmark compile/20001226-1.c compilation time after changing this
1108    function.  */
1109
1110 static inline int
1111 value_inside_range (tree val, value_range_t * vr)
1112 {
1113   int cmp1, cmp2;
1114
1115   cmp1 = operand_less_p (val, vr->min);
1116   if (cmp1 == -2)
1117     return -2;
1118   if (cmp1 == 1)
1119     return 0;
1120
1121   cmp2 = operand_less_p (vr->max, val);
1122   if (cmp2 == -2)
1123     return -2;
1124
1125   return !cmp2;
1126 }
1127
1128
1129 /* Return true if value ranges VR0 and VR1 have a non-empty
1130    intersection.
1131
1132    Benchmark compile/20001226-1.c compilation time after changing this
1133    function.
1134    */
1135
1136 static inline bool
1137 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
1138 {
1139   /* The value ranges do not intersect if the maximum of the first range is
1140      less than the minimum of the second range or vice versa.
1141      When those relations are unknown, we can't do any better.  */
1142   if (operand_less_p (vr0->max, vr1->min) != 0)
1143     return false;
1144   if (operand_less_p (vr1->max, vr0->min) != 0)
1145     return false;
1146   return true;
1147 }
1148
1149
1150 /* Return true if VR includes the value zero, false otherwise.  FIXME,
1151    currently this will return false for an anti-range like ~[-4, 3].
1152    This will be wrong when the semantics of value_inside_range are
1153    modified (currently the users of this function expect these
1154    semantics).  */
1155
1156 static inline bool
1157 range_includes_zero_p (value_range_t *vr)
1158 {
1159   tree zero;
1160
1161   gcc_assert (vr->type != VR_UNDEFINED
1162               && vr->type != VR_VARYING
1163               && !symbolic_range_p (vr));
1164
1165   zero = build_int_cst (TREE_TYPE (vr->min), 0);
1166   return (value_inside_range (zero, vr) == 1);
1167 }
1168
1169 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
1170    false otherwise or if no value range information is available.  */
1171
1172 bool
1173 ssa_name_nonnegative_p (const_tree t)
1174 {
1175   value_range_t *vr = get_value_range (t);
1176
1177   if (!vr)
1178     return false;
1179
1180   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
1181      which would return a useful value should be encoded as a VR_RANGE.  */
1182   if (vr->type == VR_RANGE)
1183     {
1184       int result = compare_values (vr->min, integer_zero_node);
1185
1186       return (result == 0 || result == 1);
1187     }
1188   return false;
1189 }
1190
1191 /* Return true if T, an SSA_NAME, is known to be nonzero.  Return
1192    false otherwise or if no value range information is available.  */
1193
1194 bool
1195 ssa_name_nonzero_p (const_tree t)
1196 {
1197   value_range_t *vr = get_value_range (t);
1198
1199   if (!vr)
1200     return false;
1201
1202   /* A VR_RANGE which does not include zero is a nonzero value.  */
1203   if (vr->type == VR_RANGE && !symbolic_range_p (vr))
1204     return ! range_includes_zero_p (vr);
1205
1206   /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
1207   if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
1208     return range_includes_zero_p (vr);
1209
1210   return false;
1211 }
1212
1213
1214 /* Extract value range information from an ASSERT_EXPR EXPR and store
1215    it in *VR_P.  */
1216
1217 static void
1218 extract_range_from_assert (value_range_t *vr_p, tree expr)
1219 {
1220   tree var, cond, limit, min, max, type;
1221   value_range_t *var_vr, *limit_vr;
1222   enum tree_code cond_code;
1223
1224   var = ASSERT_EXPR_VAR (expr);
1225   cond = ASSERT_EXPR_COND (expr);
1226
1227   gcc_assert (COMPARISON_CLASS_P (cond));
1228
1229   /* Find VAR in the ASSERT_EXPR conditional.  */
1230   if (var == TREE_OPERAND (cond, 0)
1231       || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
1232       || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
1233     {
1234       /* If the predicate is of the form VAR COMP LIMIT, then we just
1235          take LIMIT from the RHS and use the same comparison code.  */
1236       cond_code = TREE_CODE (cond);
1237       limit = TREE_OPERAND (cond, 1);
1238       cond = TREE_OPERAND (cond, 0);
1239     }
1240   else
1241     {
1242       /* If the predicate is of the form LIMIT COMP VAR, then we need
1243          to flip around the comparison code to create the proper range
1244          for VAR.  */
1245       cond_code = swap_tree_comparison (TREE_CODE (cond));
1246       limit = TREE_OPERAND (cond, 0);
1247       cond = TREE_OPERAND (cond, 1);
1248     }
1249
1250   limit = avoid_overflow_infinity (limit);
1251
1252   type = TREE_TYPE (limit);
1253   gcc_assert (limit != var);
1254
1255   /* For pointer arithmetic, we only keep track of pointer equality
1256      and inequality.  */
1257   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
1258     {
1259       set_value_range_to_varying (vr_p);
1260       return;
1261     }
1262
1263   /* If LIMIT is another SSA name and LIMIT has a range of its own,
1264      try to use LIMIT's range to avoid creating symbolic ranges
1265      unnecessarily. */
1266   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
1267
1268   /* LIMIT's range is only interesting if it has any useful information.  */
1269   if (limit_vr
1270       && (limit_vr->type == VR_UNDEFINED
1271           || limit_vr->type == VR_VARYING
1272           || symbolic_range_p (limit_vr)))
1273     limit_vr = NULL;
1274
1275   /* Initially, the new range has the same set of equivalences of
1276      VAR's range.  This will be revised before returning the final
1277      value.  Since assertions may be chained via mutually exclusive
1278      predicates, we will need to trim the set of equivalences before
1279      we are done.  */
1280   gcc_assert (vr_p->equiv == NULL);
1281   add_equivalence (&vr_p->equiv, var);
1282
1283   /* Extract a new range based on the asserted comparison for VAR and
1284      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
1285      will only use it for equality comparisons (EQ_EXPR).  For any
1286      other kind of assertion, we cannot derive a range from LIMIT's
1287      anti-range that can be used to describe the new range.  For
1288      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
1289      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
1290      no single range for x_2 that could describe LE_EXPR, so we might
1291      as well build the range [b_4, +INF] for it.
1292      One special case we handle is extracting a range from a
1293      range test encoded as (unsigned)var + CST <= limit.  */
1294   if (TREE_CODE (cond) == NOP_EXPR
1295       || TREE_CODE (cond) == PLUS_EXPR)
1296     {
1297       if (TREE_CODE (cond) == PLUS_EXPR)
1298         {
1299           min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
1300                              TREE_OPERAND (cond, 1));
1301           max = int_const_binop (PLUS_EXPR, limit, min, 0);
1302           cond = TREE_OPERAND (cond, 0);
1303         }
1304       else
1305         {
1306           min = build_int_cst (TREE_TYPE (var), 0);
1307           max = limit;
1308         }
1309
1310       /* Make sure to not set TREE_OVERFLOW on the final type
1311          conversion.  We are willingly interpreting large positive
1312          unsigned values as negative singed values here.  */
1313       min = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (min),
1314                                    TREE_INT_CST_HIGH (min), 0, false);
1315       max = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (max),
1316                                    TREE_INT_CST_HIGH (max), 0, false);
1317
1318       /* We can transform a max, min range to an anti-range or
1319          vice-versa.  Use set_and_canonicalize_value_range which does
1320          this for us.  */
1321       if (cond_code == LE_EXPR)
1322         set_and_canonicalize_value_range (vr_p, VR_RANGE,
1323                                           min, max, vr_p->equiv);
1324       else if (cond_code == GT_EXPR)
1325         set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
1326                                           min, max, vr_p->equiv);
1327       else
1328         gcc_unreachable ();
1329     }
1330   else if (cond_code == EQ_EXPR)
1331     {
1332       enum value_range_type range_type;
1333
1334       if (limit_vr)
1335         {
1336           range_type = limit_vr->type;
1337           min = limit_vr->min;
1338           max = limit_vr->max;
1339         }
1340       else
1341         {
1342           range_type = VR_RANGE;
1343           min = limit;
1344           max = limit;
1345         }
1346
1347       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
1348
1349       /* When asserting the equality VAR == LIMIT and LIMIT is another
1350          SSA name, the new range will also inherit the equivalence set
1351          from LIMIT.  */
1352       if (TREE_CODE (limit) == SSA_NAME)
1353         add_equivalence (&vr_p->equiv, limit);
1354     }
1355   else if (cond_code == NE_EXPR)
1356     {
1357       /* As described above, when LIMIT's range is an anti-range and
1358          this assertion is an inequality (NE_EXPR), then we cannot
1359          derive anything from the anti-range.  For instance, if
1360          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
1361          not imply that VAR's range is [0, 0].  So, in the case of
1362          anti-ranges, we just assert the inequality using LIMIT and
1363          not its anti-range.
1364
1365          If LIMIT_VR is a range, we can only use it to build a new
1366          anti-range if LIMIT_VR is a single-valued range.  For
1367          instance, if LIMIT_VR is [0, 1], the predicate
1368          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
1369          Rather, it means that for value 0 VAR should be ~[0, 0]
1370          and for value 1, VAR should be ~[1, 1].  We cannot
1371          represent these ranges.
1372
1373          The only situation in which we can build a valid
1374          anti-range is when LIMIT_VR is a single-valued range
1375          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case,
1376          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
1377       if (limit_vr
1378           && limit_vr->type == VR_RANGE
1379           && compare_values (limit_vr->min, limit_vr->max) == 0)
1380         {
1381           min = limit_vr->min;
1382           max = limit_vr->max;
1383         }
1384       else
1385         {
1386           /* In any other case, we cannot use LIMIT's range to build a
1387              valid anti-range.  */
1388           min = max = limit;
1389         }
1390
1391       /* If MIN and MAX cover the whole range for their type, then
1392          just use the original LIMIT.  */
1393       if (INTEGRAL_TYPE_P (type)
1394           && vrp_val_is_min (min)
1395           && vrp_val_is_max (max))
1396         min = max = limit;
1397
1398       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
1399     }
1400   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
1401     {
1402       min = TYPE_MIN_VALUE (type);
1403
1404       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1405         max = limit;
1406       else
1407         {
1408           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1409              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
1410              LT_EXPR.  */
1411           max = limit_vr->max;
1412         }
1413
1414       /* If the maximum value forces us to be out of bounds, simply punt.
1415          It would be pointless to try and do anything more since this
1416          all should be optimized away above us.  */
1417       if ((cond_code == LT_EXPR
1418            && compare_values (max, min) == 0)
1419           || is_overflow_infinity (max))
1420         set_value_range_to_varying (vr_p);
1421       else
1422         {
1423           /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
1424           if (cond_code == LT_EXPR)
1425             {
1426               tree one = build_int_cst (type, 1);
1427               max = fold_build2 (MINUS_EXPR, type, max, one);
1428               if (EXPR_P (max))
1429                 TREE_NO_WARNING (max) = 1;
1430             }
1431
1432           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1433         }
1434     }
1435   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
1436     {
1437       max = TYPE_MAX_VALUE (type);
1438
1439       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1440         min = limit;
1441       else
1442         {
1443           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1444              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
1445              GT_EXPR.  */
1446           min = limit_vr->min;
1447         }
1448
1449       /* If the minimum value forces us to be out of bounds, simply punt.
1450          It would be pointless to try and do anything more since this
1451          all should be optimized away above us.  */
1452       if ((cond_code == GT_EXPR
1453            && compare_values (min, max) == 0)
1454           || is_overflow_infinity (min))
1455         set_value_range_to_varying (vr_p);
1456       else
1457         {
1458           /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
1459           if (cond_code == GT_EXPR)
1460             {
1461               tree one = build_int_cst (type, 1);
1462               min = fold_build2 (PLUS_EXPR, type, min, one);
1463               if (EXPR_P (min))
1464                 TREE_NO_WARNING (min) = 1;
1465             }
1466
1467           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1468         }
1469     }
1470   else
1471     gcc_unreachable ();
1472
1473   /* If VAR already had a known range, it may happen that the new
1474      range we have computed and VAR's range are not compatible.  For
1475      instance,
1476
1477         if (p_5 == NULL)
1478           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1479           x_7 = p_6->fld;
1480           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1481
1482      While the above comes from a faulty program, it will cause an ICE
1483      later because p_8 and p_6 will have incompatible ranges and at
1484      the same time will be considered equivalent.  A similar situation
1485      would arise from
1486
1487         if (i_5 > 10)
1488           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1489           if (i_5 < 5)
1490             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1491
1492      Again i_6 and i_7 will have incompatible ranges.  It would be
1493      pointless to try and do anything with i_7's range because
1494      anything dominated by 'if (i_5 < 5)' will be optimized away.
1495      Note, due to the wa in which simulation proceeds, the statement
1496      i_7 = ASSERT_EXPR <...> we would never be visited because the
1497      conditional 'if (i_5 < 5)' always evaluates to false.  However,
1498      this extra check does not hurt and may protect against future
1499      changes to VRP that may get into a situation similar to the
1500      NULL pointer dereference example.
1501
1502      Note that these compatibility tests are only needed when dealing
1503      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
1504      are both anti-ranges, they will always be compatible, because two
1505      anti-ranges will always have a non-empty intersection.  */
1506
1507   var_vr = get_value_range (var);
1508
1509   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1510      ranges or anti-ranges.  */
1511   if (vr_p->type == VR_VARYING
1512       || vr_p->type == VR_UNDEFINED
1513       || var_vr->type == VR_VARYING
1514       || var_vr->type == VR_UNDEFINED
1515       || symbolic_range_p (vr_p)
1516       || symbolic_range_p (var_vr))
1517     return;
1518
1519   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1520     {
1521       /* If the two ranges have a non-empty intersection, we can
1522          refine the resulting range.  Since the assert expression
1523          creates an equivalency and at the same time it asserts a
1524          predicate, we can take the intersection of the two ranges to
1525          get better precision.  */
1526       if (value_ranges_intersect_p (var_vr, vr_p))
1527         {
1528           /* Use the larger of the two minimums.  */
1529           if (compare_values (vr_p->min, var_vr->min) == -1)
1530             min = var_vr->min;
1531           else
1532             min = vr_p->min;
1533
1534           /* Use the smaller of the two maximums.  */
1535           if (compare_values (vr_p->max, var_vr->max) == 1)
1536             max = var_vr->max;
1537           else
1538             max = vr_p->max;
1539
1540           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1541         }
1542       else
1543         {
1544           /* The two ranges do not intersect, set the new range to
1545              VARYING, because we will not be able to do anything
1546              meaningful with it.  */
1547           set_value_range_to_varying (vr_p);
1548         }
1549     }
1550   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1551            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1552     {
1553       /* A range and an anti-range will cancel each other only if
1554          their ends are the same.  For instance, in the example above,
1555          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1556          so VR_P should be set to VR_VARYING.  */
1557       if (compare_values (var_vr->min, vr_p->min) == 0
1558           && compare_values (var_vr->max, vr_p->max) == 0)
1559         set_value_range_to_varying (vr_p);
1560       else
1561         {
1562           tree min, max, anti_min, anti_max, real_min, real_max;
1563           int cmp;
1564
1565           /* We want to compute the logical AND of the two ranges;
1566              there are three cases to consider.
1567
1568
1569              1. The VR_ANTI_RANGE range is completely within the
1570                 VR_RANGE and the endpoints of the ranges are
1571                 different.  In that case the resulting range
1572                 should be whichever range is more precise.
1573                 Typically that will be the VR_RANGE.
1574
1575              2. The VR_ANTI_RANGE is completely disjoint from
1576                 the VR_RANGE.  In this case the resulting range
1577                 should be the VR_RANGE.
1578
1579              3. There is some overlap between the VR_ANTI_RANGE
1580                 and the VR_RANGE.
1581
1582                 3a. If the high limit of the VR_ANTI_RANGE resides
1583                     within the VR_RANGE, then the result is a new
1584                     VR_RANGE starting at the high limit of the
1585                     the VR_ANTI_RANGE + 1 and extending to the
1586                     high limit of the original VR_RANGE.
1587
1588                 3b. If the low limit of the VR_ANTI_RANGE resides
1589                     within the VR_RANGE, then the result is a new
1590                     VR_RANGE starting at the low limit of the original
1591                     VR_RANGE and extending to the low limit of the
1592                     VR_ANTI_RANGE - 1.  */
1593           if (vr_p->type == VR_ANTI_RANGE)
1594             {
1595               anti_min = vr_p->min;
1596               anti_max = vr_p->max;
1597               real_min = var_vr->min;
1598               real_max = var_vr->max;
1599             }
1600           else
1601             {
1602               anti_min = var_vr->min;
1603               anti_max = var_vr->max;
1604               real_min = vr_p->min;
1605               real_max = vr_p->max;
1606             }
1607
1608
1609           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1610              not including any endpoints.  */
1611           if (compare_values (anti_max, real_max) == -1
1612               && compare_values (anti_min, real_min) == 1)
1613             {
1614               /* If the range is covering the whole valid range of
1615                  the type keep the anti-range.  */
1616               if (!vrp_val_is_min (real_min)
1617                   || !vrp_val_is_max (real_max))
1618                 set_value_range (vr_p, VR_RANGE, real_min,
1619                                  real_max, vr_p->equiv);
1620             }
1621           /* Case 2, VR_ANTI_RANGE completely disjoint from
1622              VR_RANGE.  */
1623           else if (compare_values (anti_min, real_max) == 1
1624                    || compare_values (anti_max, real_min) == -1)
1625             {
1626               set_value_range (vr_p, VR_RANGE, real_min,
1627                                real_max, vr_p->equiv);
1628             }
1629           /* Case 3a, the anti-range extends into the low
1630              part of the real range.  Thus creating a new
1631              low for the real range.  */
1632           else if (((cmp = compare_values (anti_max, real_min)) == 1
1633                     || cmp == 0)
1634                    && compare_values (anti_max, real_max) == -1)
1635             {
1636               gcc_assert (!is_positive_overflow_infinity (anti_max));
1637               if (needs_overflow_infinity (TREE_TYPE (anti_max))
1638                   && vrp_val_is_max (anti_max))
1639                 {
1640                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1641                     {
1642                       set_value_range_to_varying (vr_p);
1643                       return;
1644                     }
1645                   min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
1646                 }
1647               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1648                 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1649                                    anti_max,
1650                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1651               else
1652                 min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1653                                    anti_max, size_int (1));
1654               max = real_max;
1655               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1656             }
1657           /* Case 3b, the anti-range extends into the high
1658              part of the real range.  Thus creating a new
1659              higher for the real range.  */
1660           else if (compare_values (anti_min, real_min) == 1
1661                    && ((cmp = compare_values (anti_min, real_max)) == -1
1662                        || cmp == 0))
1663             {
1664               gcc_assert (!is_negative_overflow_infinity (anti_min));
1665               if (needs_overflow_infinity (TREE_TYPE (anti_min))
1666                   && vrp_val_is_min (anti_min))
1667                 {
1668                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1669                     {
1670                       set_value_range_to_varying (vr_p);
1671                       return;
1672                     }
1673                   max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
1674                 }
1675               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1676                 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1677                                    anti_min,
1678                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1679               else
1680                 max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1681                                    anti_min,
1682                                    size_int (-1));
1683               min = real_min;
1684               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1685             }
1686         }
1687     }
1688 }
1689
1690
1691 /* Extract range information from SSA name VAR and store it in VR.  If
1692    VAR has an interesting range, use it.  Otherwise, create the
1693    range [VAR, VAR] and return it.  This is useful in situations where
1694    we may have conditionals testing values of VARYING names.  For
1695    instance,
1696
1697         x_3 = y_5;
1698         if (x_3 > y_5)
1699           ...
1700
1701     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1702     always false.  */
1703
1704 static void
1705 extract_range_from_ssa_name (value_range_t *vr, tree var)
1706 {
1707   value_range_t *var_vr = get_value_range (var);
1708
1709   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1710     copy_value_range (vr, var_vr);
1711   else
1712     set_value_range (vr, VR_RANGE, var, var, NULL);
1713
1714   add_equivalence (&vr->equiv, var);
1715 }
1716
1717
1718 /* Wrapper around int_const_binop.  If the operation overflows and we
1719    are not using wrapping arithmetic, then adjust the result to be
1720    -INF or +INF depending on CODE, VAL1 and VAL2.  This can return
1721    NULL_TREE if we need to use an overflow infinity representation but
1722    the type does not support it.  */
1723
1724 static tree
1725 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1726 {
1727   tree res;
1728
1729   res = int_const_binop (code, val1, val2, 0);
1730
1731   /* If we are not using wrapping arithmetic, operate symbolically
1732      on -INF and +INF.  */
1733   if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
1734     {
1735       int checkz = compare_values (res, val1);
1736       bool overflow = false;
1737
1738       /* Ensure that res = val1 [+*] val2 >= val1
1739          or that res = val1 - val2 <= val1.  */
1740       if ((code == PLUS_EXPR
1741            && !(checkz == 1 || checkz == 0))
1742           || (code == MINUS_EXPR
1743               && !(checkz == 0 || checkz == -1)))
1744         {
1745           overflow = true;
1746         }
1747       /* Checking for multiplication overflow is done by dividing the
1748          output of the multiplication by the first input of the
1749          multiplication.  If the result of that division operation is
1750          not equal to the second input of the multiplication, then the
1751          multiplication overflowed.  */
1752       else if (code == MULT_EXPR && !integer_zerop (val1))
1753         {
1754           tree tmp = int_const_binop (TRUNC_DIV_EXPR,
1755                                       res,
1756                                       val1, 0);
1757           int check = compare_values (tmp, val2);
1758
1759           if (check != 0)
1760             overflow = true;
1761         }
1762
1763       if (overflow)
1764         {
1765           res = copy_node (res);
1766           TREE_OVERFLOW (res) = 1;
1767         }
1768
1769     }
1770   else if ((TREE_OVERFLOW (res)
1771             && !TREE_OVERFLOW (val1)
1772             && !TREE_OVERFLOW (val2))
1773            || is_overflow_infinity (val1)
1774            || is_overflow_infinity (val2))
1775     {
1776       /* If the operation overflowed but neither VAL1 nor VAL2 are
1777          overflown, return -INF or +INF depending on the operation
1778          and the combination of signs of the operands.  */
1779       int sgn1 = tree_int_cst_sgn (val1);
1780       int sgn2 = tree_int_cst_sgn (val2);
1781
1782       if (needs_overflow_infinity (TREE_TYPE (res))
1783           && !supports_overflow_infinity (TREE_TYPE (res)))
1784         return NULL_TREE;
1785
1786       /* We have to punt on adding infinities of different signs,
1787          since we can't tell what the sign of the result should be.
1788          Likewise for subtracting infinities of the same sign.  */
1789       if (((code == PLUS_EXPR && sgn1 != sgn2)
1790            || (code == MINUS_EXPR && sgn1 == sgn2))
1791           && is_overflow_infinity (val1)
1792           && is_overflow_infinity (val2))
1793         return NULL_TREE;
1794
1795       /* Don't try to handle division or shifting of infinities.  */
1796       if ((code == TRUNC_DIV_EXPR
1797            || code == FLOOR_DIV_EXPR
1798            || code == CEIL_DIV_EXPR
1799            || code == EXACT_DIV_EXPR
1800            || code == ROUND_DIV_EXPR
1801            || code == RSHIFT_EXPR)
1802           && (is_overflow_infinity (val1)
1803               || is_overflow_infinity (val2)))
1804         return NULL_TREE;
1805
1806       /* Notice that we only need to handle the restricted set of
1807          operations handled by extract_range_from_binary_expr.
1808          Among them, only multiplication, addition and subtraction
1809          can yield overflow without overflown operands because we
1810          are working with integral types only... except in the
1811          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1812          for division too.  */
1813
1814       /* For multiplication, the sign of the overflow is given
1815          by the comparison of the signs of the operands.  */
1816       if ((code == MULT_EXPR && sgn1 == sgn2)
1817           /* For addition, the operands must be of the same sign
1818              to yield an overflow.  Its sign is therefore that
1819              of one of the operands, for example the first.  For
1820              infinite operands X + -INF is negative, not positive.  */
1821           || (code == PLUS_EXPR
1822               && (sgn1 >= 0
1823                   ? !is_negative_overflow_infinity (val2)
1824                   : is_positive_overflow_infinity (val2)))
1825           /* For subtraction, non-infinite operands must be of
1826              different signs to yield an overflow.  Its sign is
1827              therefore that of the first operand or the opposite of
1828              that of the second operand.  A first operand of 0 counts
1829              as positive here, for the corner case 0 - (-INF), which
1830              overflows, but must yield +INF.  For infinite operands 0
1831              - INF is negative, not positive.  */
1832           || (code == MINUS_EXPR
1833               && (sgn1 >= 0
1834                   ? !is_positive_overflow_infinity (val2)
1835                   : is_negative_overflow_infinity (val2)))
1836           /* We only get in here with positive shift count, so the
1837              overflow direction is the same as the sign of val1.
1838              Actually rshift does not overflow at all, but we only
1839              handle the case of shifting overflowed -INF and +INF.  */
1840           || (code == RSHIFT_EXPR
1841               && sgn1 >= 0)
1842           /* For division, the only case is -INF / -1 = +INF.  */
1843           || code == TRUNC_DIV_EXPR
1844           || code == FLOOR_DIV_EXPR
1845           || code == CEIL_DIV_EXPR
1846           || code == EXACT_DIV_EXPR
1847           || code == ROUND_DIV_EXPR)
1848         return (needs_overflow_infinity (TREE_TYPE (res))
1849                 ? positive_overflow_infinity (TREE_TYPE (res))
1850                 : TYPE_MAX_VALUE (TREE_TYPE (res)));
1851       else
1852         return (needs_overflow_infinity (TREE_TYPE (res))
1853                 ? negative_overflow_infinity (TREE_TYPE (res))
1854                 : TYPE_MIN_VALUE (TREE_TYPE (res)));
1855     }
1856
1857   return res;
1858 }
1859
1860
1861 /* Extract range information from a binary expression EXPR based on
1862    the ranges of each of its operands and the expression code.  */
1863
1864 static void
1865 extract_range_from_binary_expr (value_range_t *vr,
1866                                 enum tree_code code,
1867                                 tree expr_type, tree op0, tree op1)
1868 {
1869   enum value_range_type type;
1870   tree min, max;
1871   int cmp;
1872   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1873   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1874
1875   /* Not all binary expressions can be applied to ranges in a
1876      meaningful way.  Handle only arithmetic operations.  */
1877   if (code != PLUS_EXPR
1878       && code != MINUS_EXPR
1879       && code != POINTER_PLUS_EXPR
1880       && code != MULT_EXPR
1881       && code != TRUNC_DIV_EXPR
1882       && code != FLOOR_DIV_EXPR
1883       && code != CEIL_DIV_EXPR
1884       && code != EXACT_DIV_EXPR
1885       && code != ROUND_DIV_EXPR
1886       && code != RSHIFT_EXPR
1887       && code != MIN_EXPR
1888       && code != MAX_EXPR
1889       && code != BIT_AND_EXPR
1890       && code != TRUTH_AND_EXPR
1891       && code != TRUTH_OR_EXPR)
1892     {
1893       set_value_range_to_varying (vr);
1894       return;
1895     }
1896
1897   /* Get value ranges for each operand.  For constant operands, create
1898      a new value range with the operand to simplify processing.  */
1899   if (TREE_CODE (op0) == SSA_NAME)
1900     vr0 = *(get_value_range (op0));
1901   else if (is_gimple_min_invariant (op0))
1902     set_value_range_to_value (&vr0, op0, NULL);
1903   else
1904     set_value_range_to_varying (&vr0);
1905
1906   if (TREE_CODE (op1) == SSA_NAME)
1907     vr1 = *(get_value_range (op1));
1908   else if (is_gimple_min_invariant (op1))
1909     set_value_range_to_value (&vr1, op1, NULL);
1910   else
1911     set_value_range_to_varying (&vr1);
1912
1913   /* If either range is UNDEFINED, so is the result.  */
1914   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1915     {
1916       set_value_range_to_undefined (vr);
1917       return;
1918     }
1919
1920   /* The type of the resulting value range defaults to VR0.TYPE.  */
1921   type = vr0.type;
1922
1923   /* Refuse to operate on VARYING ranges, ranges of different kinds
1924      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
1925      because we may be able to derive a useful range even if one of
1926      the operands is VR_VARYING or symbolic range.  TODO, we may be
1927      able to derive anti-ranges in some cases.  */
1928   if (code != BIT_AND_EXPR
1929       && code != TRUTH_AND_EXPR
1930       && code != TRUTH_OR_EXPR
1931       && (vr0.type == VR_VARYING
1932           || vr1.type == VR_VARYING
1933           || vr0.type != vr1.type
1934           || symbolic_range_p (&vr0)
1935           || symbolic_range_p (&vr1)))
1936     {
1937       set_value_range_to_varying (vr);
1938       return;
1939     }
1940
1941   /* Now evaluate the expression to determine the new range.  */
1942   if (POINTER_TYPE_P (expr_type)
1943       || POINTER_TYPE_P (TREE_TYPE (op0))
1944       || POINTER_TYPE_P (TREE_TYPE (op1)))
1945     {
1946       if (code == MIN_EXPR || code == MAX_EXPR)
1947         {
1948           /* For MIN/MAX expressions with pointers, we only care about
1949              nullness, if both are non null, then the result is nonnull.
1950              If both are null, then the result is null. Otherwise they
1951              are varying.  */
1952           if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
1953             set_value_range_to_nonnull (vr, expr_type);
1954           else if (range_is_null (&vr0) && range_is_null (&vr1))
1955             set_value_range_to_null (vr, expr_type);
1956           else
1957             set_value_range_to_varying (vr);
1958
1959           return;
1960         }
1961       gcc_assert (code == POINTER_PLUS_EXPR);
1962       /* For pointer types, we are really only interested in asserting
1963          whether the expression evaluates to non-NULL.  */
1964       if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1965         set_value_range_to_nonnull (vr, expr_type);
1966       else if (range_is_null (&vr0) && range_is_null (&vr1))
1967         set_value_range_to_null (vr, expr_type);
1968       else
1969         set_value_range_to_varying (vr);
1970
1971       return;
1972     }
1973
1974   /* For integer ranges, apply the operation to each end of the
1975      range and see what we end up with.  */
1976   if (code == TRUTH_AND_EXPR
1977       || code == TRUTH_OR_EXPR)
1978     {
1979       /* If one of the operands is zero, we know that the whole
1980          expression evaluates zero.  */
1981       if (code == TRUTH_AND_EXPR
1982           && ((vr0.type == VR_RANGE
1983                && integer_zerop (vr0.min)
1984                && integer_zerop (vr0.max))
1985               || (vr1.type == VR_RANGE
1986                   && integer_zerop (vr1.min)
1987                   && integer_zerop (vr1.max))))
1988         {
1989           type = VR_RANGE;
1990           min = max = build_int_cst (expr_type, 0);
1991         }
1992       /* If one of the operands is one, we know that the whole
1993          expression evaluates one.  */
1994       else if (code == TRUTH_OR_EXPR
1995                && ((vr0.type == VR_RANGE
1996                     && integer_onep (vr0.min)
1997                     && integer_onep (vr0.max))
1998                    || (vr1.type == VR_RANGE
1999                        && integer_onep (vr1.min)
2000                        && integer_onep (vr1.max))))
2001         {
2002           type = VR_RANGE;
2003           min = max = build_int_cst (expr_type, 1);
2004         }
2005       else if (vr0.type != VR_VARYING
2006                && vr1.type != VR_VARYING
2007                && vr0.type == vr1.type
2008                && !symbolic_range_p (&vr0)
2009                && !overflow_infinity_range_p (&vr0)
2010                && !symbolic_range_p (&vr1)
2011                && !overflow_infinity_range_p (&vr1))
2012         {
2013           /* Boolean expressions cannot be folded with int_const_binop.  */
2014           min = fold_binary (code, expr_type, vr0.min, vr1.min);
2015           max = fold_binary (code, expr_type, vr0.max, vr1.max);
2016         }
2017       else
2018         {
2019           /* The result of a TRUTH_*_EXPR is always true or false.  */
2020           set_value_range_to_truthvalue (vr, expr_type);
2021           return;
2022         }
2023     }
2024   else if (code == PLUS_EXPR
2025            || code == MIN_EXPR
2026            || code == MAX_EXPR)
2027     {
2028       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2029          VR_VARYING.  It would take more effort to compute a precise
2030          range for such a case.  For example, if we have op0 == 1 and
2031          op1 == -1 with their ranges both being ~[0,0], we would have
2032          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2033          Note that we are guaranteed to have vr0.type == vr1.type at
2034          this point.  */
2035       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
2036         {
2037           set_value_range_to_varying (vr);
2038           return;
2039         }
2040
2041       /* For operations that make the resulting range directly
2042          proportional to the original ranges, apply the operation to
2043          the same end of each range.  */
2044       min = vrp_int_const_binop (code, vr0.min, vr1.min);
2045       max = vrp_int_const_binop (code, vr0.max, vr1.max);
2046     }
2047   else if (code == MULT_EXPR
2048            || code == TRUNC_DIV_EXPR
2049            || code == FLOOR_DIV_EXPR
2050            || code == CEIL_DIV_EXPR
2051            || code == EXACT_DIV_EXPR
2052            || code == ROUND_DIV_EXPR
2053            || code == RSHIFT_EXPR)
2054     {
2055       tree val[4];
2056       size_t i;
2057       bool sop;
2058
2059       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2060          drop to VR_VARYING.  It would take more effort to compute a
2061          precise range for such a case.  For example, if we have
2062          op0 == 65536 and op1 == 65536 with their ranges both being
2063          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2064          we cannot claim that the product is in ~[0,0].  Note that we
2065          are guaranteed to have vr0.type == vr1.type at this
2066          point.  */
2067       if (code == MULT_EXPR
2068           && vr0.type == VR_ANTI_RANGE
2069           && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
2070         {
2071           set_value_range_to_varying (vr);
2072           return;
2073         }
2074
2075       /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2076          then drop to VR_VARYING.  Outside of this range we get undefined
2077          behavior from the shift operation.  We cannot even trust
2078          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2079          shifts, and the operation at the tree level may be widened.  */
2080       if (code == RSHIFT_EXPR)
2081         {
2082           if (vr1.type == VR_ANTI_RANGE
2083               || !vrp_expr_computes_nonnegative (op1, &sop)
2084               || (operand_less_p
2085                   (build_int_cst (TREE_TYPE (vr1.max),
2086                                   TYPE_PRECISION (expr_type) - 1),
2087                    vr1.max) != 0))
2088             {
2089               set_value_range_to_varying (vr);
2090               return;
2091             }
2092         }
2093
2094       /* Multiplications and divisions are a bit tricky to handle,
2095          depending on the mix of signs we have in the two ranges, we
2096          need to operate on different values to get the minimum and
2097          maximum values for the new range.  One approach is to figure
2098          out all the variations of range combinations and do the
2099          operations.
2100
2101          However, this involves several calls to compare_values and it
2102          is pretty convoluted.  It's simpler to do the 4 operations
2103          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2104          MAX1) and then figure the smallest and largest values to form
2105          the new range.  */
2106
2107       /* Divisions by zero result in a VARYING value.  */
2108       else if (code != MULT_EXPR
2109                && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
2110         {
2111           set_value_range_to_varying (vr);
2112           return;
2113         }
2114
2115       /* Compute the 4 cross operations.  */
2116       sop = false;
2117       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
2118       if (val[0] == NULL_TREE)
2119         sop = true;
2120
2121       if (vr1.max == vr1.min)
2122         val[1] = NULL_TREE;
2123       else
2124         {
2125           val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
2126           if (val[1] == NULL_TREE)
2127             sop = true;
2128         }
2129
2130       if (vr0.max == vr0.min)
2131         val[2] = NULL_TREE;
2132       else
2133         {
2134           val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
2135           if (val[2] == NULL_TREE)
2136             sop = true;
2137         }
2138
2139       if (vr0.min == vr0.max || vr1.min == vr1.max)
2140         val[3] = NULL_TREE;
2141       else
2142         {
2143           val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
2144           if (val[3] == NULL_TREE)
2145             sop = true;
2146         }
2147
2148       if (sop)
2149         {
2150           set_value_range_to_varying (vr);
2151           return;
2152         }
2153
2154       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2155          of VAL[i].  */
2156       min = val[0];
2157       max = val[0];
2158       for (i = 1; i < 4; i++)
2159         {
2160           if (!is_gimple_min_invariant (min)
2161               || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2162               || !is_gimple_min_invariant (max)
2163               || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2164             break;
2165
2166           if (val[i])
2167             {
2168               if (!is_gimple_min_invariant (val[i])
2169                   || (TREE_OVERFLOW (val[i])
2170                       && !is_overflow_infinity (val[i])))
2171                 {
2172                   /* If we found an overflowed value, set MIN and MAX
2173                      to it so that we set the resulting range to
2174                      VARYING.  */
2175                   min = max = val[i];
2176                   break;
2177                 }
2178
2179               if (compare_values (val[i], min) == -1)
2180                 min = val[i];
2181
2182               if (compare_values (val[i], max) == 1)
2183                 max = val[i];
2184             }
2185         }
2186     }
2187   else if (code == MINUS_EXPR)
2188     {
2189       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2190          VR_VARYING.  It would take more effort to compute a precise
2191          range for such a case.  For example, if we have op0 == 1 and
2192          op1 == 1 with their ranges both being ~[0,0], we would have
2193          op0 - op1 == 0, so we cannot claim that the difference is in
2194          ~[0,0].  Note that we are guaranteed to have
2195          vr0.type == vr1.type at this point.  */
2196       if (vr0.type == VR_ANTI_RANGE)
2197         {
2198           set_value_range_to_varying (vr);
2199           return;
2200         }
2201
2202       /* For MINUS_EXPR, apply the operation to the opposite ends of
2203          each range.  */
2204       min = vrp_int_const_binop (code, vr0.min, vr1.max);
2205       max = vrp_int_const_binop (code, vr0.max, vr1.min);
2206     }
2207   else if (code == BIT_AND_EXPR)
2208     {
2209       if (vr0.type == VR_RANGE
2210           && vr0.min == vr0.max
2211           && TREE_CODE (vr0.max) == INTEGER_CST
2212           && !TREE_OVERFLOW (vr0.max)
2213           && tree_int_cst_sgn (vr0.max) >= 0)
2214         {
2215           min = build_int_cst (expr_type, 0);
2216           max = vr0.max;
2217         }
2218       else if (vr1.type == VR_RANGE
2219                && vr1.min == vr1.max
2220                && TREE_CODE (vr1.max) == INTEGER_CST
2221                && !TREE_OVERFLOW (vr1.max)
2222                && tree_int_cst_sgn (vr1.max) >= 0)
2223         {
2224           type = VR_RANGE;
2225           min = build_int_cst (expr_type, 0);
2226           max = vr1.max;
2227         }
2228       else
2229         {
2230           set_value_range_to_varying (vr);
2231           return;
2232         }
2233     }
2234   else
2235     gcc_unreachable ();
2236
2237   /* If either MIN or MAX overflowed, then set the resulting range to
2238      VARYING.  But we do accept an overflow infinity
2239      representation.  */
2240   if (min == NULL_TREE
2241       || !is_gimple_min_invariant (min)
2242       || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2243       || max == NULL_TREE
2244       || !is_gimple_min_invariant (max)
2245       || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2246     {
2247       set_value_range_to_varying (vr);
2248       return;
2249     }
2250
2251   /* We punt if:
2252      1) [-INF, +INF]
2253      2) [-INF, +-INF(OVF)]
2254      3) [+-INF(OVF), +INF]
2255      4) [+-INF(OVF), +-INF(OVF)]
2256      We learn nothing when we have INF and INF(OVF) on both sides.
2257      Note that we do accept [-INF, -INF] and [+INF, +INF] without
2258      overflow.  */
2259   if ((vrp_val_is_min (min) || is_overflow_infinity (min))
2260       && (vrp_val_is_max (max) || is_overflow_infinity (max)))
2261     {
2262       set_value_range_to_varying (vr);
2263       return;
2264     }
2265
2266   cmp = compare_values (min, max);
2267   if (cmp == -2 || cmp == 1)
2268     {
2269       /* If the new range has its limits swapped around (MIN > MAX),
2270          then the operation caused one of them to wrap around, mark
2271          the new range VARYING.  */
2272       set_value_range_to_varying (vr);
2273     }
2274   else
2275     set_value_range (vr, type, min, max, NULL);
2276 }
2277
2278
2279 /* Extract range information from a unary expression EXPR based on
2280    the range of its operand and the expression code.  */
2281
2282 static void
2283 extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
2284                                tree type, tree op0)
2285 {
2286   tree min, max;
2287   int cmp;
2288   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2289
2290   /* Refuse to operate on certain unary expressions for which we
2291      cannot easily determine a resulting range.  */
2292   if (code == FIX_TRUNC_EXPR
2293       || code == FLOAT_EXPR
2294       || code == BIT_NOT_EXPR
2295       || code == NON_LVALUE_EXPR
2296       || code == CONJ_EXPR)
2297     {
2298       set_value_range_to_varying (vr);
2299       return;
2300     }
2301
2302   /* Get value ranges for the operand.  For constant operands, create
2303      a new value range with the operand to simplify processing.  */
2304   if (TREE_CODE (op0) == SSA_NAME)
2305     vr0 = *(get_value_range (op0));
2306   else if (is_gimple_min_invariant (op0))
2307     set_value_range_to_value (&vr0, op0, NULL);
2308   else
2309     set_value_range_to_varying (&vr0);
2310
2311   /* If VR0 is UNDEFINED, so is the result.  */
2312   if (vr0.type == VR_UNDEFINED)
2313     {
2314       set_value_range_to_undefined (vr);
2315       return;
2316     }
2317
2318   /* Refuse to operate on symbolic ranges, or if neither operand is
2319      a pointer or integral type.  */
2320   if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2321        && !POINTER_TYPE_P (TREE_TYPE (op0)))
2322       || (vr0.type != VR_VARYING
2323           && symbolic_range_p (&vr0)))
2324     {
2325       set_value_range_to_varying (vr);
2326       return;
2327     }
2328
2329   /* If the expression involves pointers, we are only interested in
2330      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
2331   if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
2332     {
2333       bool sop;
2334
2335       sop = false;
2336       if (range_is_nonnull (&vr0)
2337           || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
2338               && !sop))
2339         set_value_range_to_nonnull (vr, type);
2340       else if (range_is_null (&vr0))
2341         set_value_range_to_null (vr, type);
2342       else
2343         set_value_range_to_varying (vr);
2344
2345       return;
2346     }
2347
2348   /* Handle unary expressions on integer ranges.  */
2349   if ((code == NOP_EXPR
2350        || code == CONVERT_EXPR)
2351       && INTEGRAL_TYPE_P (type)
2352       && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2353     {
2354       tree inner_type = TREE_TYPE (op0);
2355       tree outer_type = type;
2356
2357       /* Always use base-types here.  This is important for the
2358          correct signedness.  */
2359       if (TREE_TYPE (inner_type))
2360         inner_type = TREE_TYPE (inner_type);
2361       if (TREE_TYPE (outer_type))
2362         outer_type = TREE_TYPE (outer_type);
2363
2364       /* If VR0 is varying and we increase the type precision, assume
2365          a full range for the following transformation.  */
2366       if (vr0.type == VR_VARYING
2367           && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
2368         {
2369           vr0.type = VR_RANGE;
2370           vr0.min = TYPE_MIN_VALUE (inner_type);
2371           vr0.max = TYPE_MAX_VALUE (inner_type);
2372         }
2373
2374       /* If VR0 is a constant range or anti-range and the conversion is
2375          not truncating we can convert the min and max values and
2376          canonicalize the resulting range.  Otherwise we can do the
2377          conversion if the size of the range is less than what the
2378          precision of the target type can represent and the range is
2379          not an anti-range.  */
2380       if ((vr0.type == VR_RANGE
2381            || vr0.type == VR_ANTI_RANGE)
2382           && TREE_CODE (vr0.min) == INTEGER_CST
2383           && TREE_CODE (vr0.max) == INTEGER_CST
2384           && !is_overflow_infinity (vr0.min)
2385           && !is_overflow_infinity (vr0.max)
2386           && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
2387               || (vr0.type == VR_RANGE
2388                   && integer_zerop (int_const_binop (RSHIFT_EXPR,
2389                        int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0),
2390                          size_int (TYPE_PRECISION (outer_type)), 0)))))
2391         {
2392           tree new_min, new_max;
2393           new_min = force_fit_type_double (outer_type,
2394                                            TREE_INT_CST_LOW (vr0.min),
2395                                            TREE_INT_CST_HIGH (vr0.min), 0, 0);
2396           new_max = force_fit_type_double (outer_type,
2397                                            TREE_INT_CST_LOW (vr0.max),
2398                                            TREE_INT_CST_HIGH (vr0.max), 0, 0);
2399           set_and_canonicalize_value_range (vr, vr0.type,
2400                                             new_min, new_max, NULL);
2401           return;
2402         }
2403
2404       set_value_range_to_varying (vr);
2405       return;
2406     }
2407
2408   /* Conversion of a VR_VARYING value to a wider type can result
2409      in a usable range.  So wait until after we've handled conversions
2410      before dropping the result to VR_VARYING if we had a source
2411      operand that is VR_VARYING.  */
2412   if (vr0.type == VR_VARYING)
2413     {
2414       set_value_range_to_varying (vr);
2415       return;
2416     }
2417
2418   /* Apply the operation to each end of the range and see what we end
2419      up with.  */
2420   if (code == NEGATE_EXPR
2421       && !TYPE_UNSIGNED (type))
2422     {
2423       /* NEGATE_EXPR flips the range around.  We need to treat
2424          TYPE_MIN_VALUE specially.  */
2425       if (is_positive_overflow_infinity (vr0.max))
2426         min = negative_overflow_infinity (type);
2427       else if (is_negative_overflow_infinity (vr0.max))
2428         min = positive_overflow_infinity (type);
2429       else if (!vrp_val_is_min (vr0.max))
2430         min = fold_unary_to_constant (code, type, vr0.max);
2431       else if (needs_overflow_infinity (type))
2432         {
2433           if (supports_overflow_infinity (type)
2434               && !is_overflow_infinity (vr0.min)
2435               && !vrp_val_is_min (vr0.min))
2436             min = positive_overflow_infinity (type);
2437           else
2438             {
2439               set_value_range_to_varying (vr);
2440               return;
2441             }
2442         }
2443       else
2444         min = TYPE_MIN_VALUE (type);
2445
2446       if (is_positive_overflow_infinity (vr0.min))
2447         max = negative_overflow_infinity (type);
2448       else if (is_negative_overflow_infinity (vr0.min))
2449         max = positive_overflow_infinity (type);
2450       else if (!vrp_val_is_min (vr0.min))
2451         max = fold_unary_to_constant (code, type, vr0.min);
2452       else if (needs_overflow_infinity (type))
2453         {
2454           if (supports_overflow_infinity (type))
2455             max = positive_overflow_infinity (type);
2456           else
2457             {
2458               set_value_range_to_varying (vr);
2459               return;
2460             }
2461         }
2462       else
2463         max = TYPE_MIN_VALUE (type);
2464     }
2465   else if (code == NEGATE_EXPR
2466            && TYPE_UNSIGNED (type))
2467     {
2468       if (!range_includes_zero_p (&vr0))
2469         {
2470           max = fold_unary_to_constant (code, type, vr0.min);
2471           min = fold_unary_to_constant (code, type, vr0.max);
2472         }
2473       else
2474         {
2475           if (range_is_null (&vr0))
2476             set_value_range_to_null (vr, type);
2477           else
2478             set_value_range_to_varying (vr);
2479           return;
2480         }
2481     }
2482   else if (code == ABS_EXPR
2483            && !TYPE_UNSIGNED (type))
2484     {
2485       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
2486          useful range.  */
2487       if (!TYPE_OVERFLOW_UNDEFINED (type)
2488           && ((vr0.type == VR_RANGE
2489                && vrp_val_is_min (vr0.min))
2490               || (vr0.type == VR_ANTI_RANGE
2491                   && !vrp_val_is_min (vr0.min)
2492                   && !range_includes_zero_p (&vr0))))
2493         {
2494           set_value_range_to_varying (vr);
2495           return;
2496         }
2497
2498       /* ABS_EXPR may flip the range around, if the original range
2499          included negative values.  */
2500       if (is_overflow_infinity (vr0.min))
2501         min = positive_overflow_infinity (type);
2502       else if (!vrp_val_is_min (vr0.min))
2503         min = fold_unary_to_constant (code, type, vr0.min);
2504       else if (!needs_overflow_infinity (type))
2505         min = TYPE_MAX_VALUE (type);
2506       else if (supports_overflow_infinity (type))
2507         min = positive_overflow_infinity (type);
2508       else
2509         {
2510           set_value_range_to_varying (vr);
2511           return;
2512         }
2513
2514       if (is_overflow_infinity (vr0.max))
2515         max = positive_overflow_infinity (type);
2516       else if (!vrp_val_is_min (vr0.max))
2517         max = fold_unary_to_constant (code, type, vr0.max);
2518       else if (!needs_overflow_infinity (type))
2519         max = TYPE_MAX_VALUE (type);
2520       else if (supports_overflow_infinity (type))
2521         max = positive_overflow_infinity (type);
2522       else
2523         {
2524           set_value_range_to_varying (vr);
2525           return;
2526         }
2527
2528       cmp = compare_values (min, max);
2529
2530       /* If a VR_ANTI_RANGEs contains zero, then we have
2531          ~[-INF, min(MIN, MAX)].  */
2532       if (vr0.type == VR_ANTI_RANGE)
2533         {
2534           if (range_includes_zero_p (&vr0))
2535             {
2536               /* Take the lower of the two values.  */
2537               if (cmp != 1)
2538                 max = min;
2539
2540               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
2541                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
2542                  flag_wrapv is set and the original anti-range doesn't include
2543                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
2544               if (TYPE_OVERFLOW_WRAPS (type))
2545                 {
2546                   tree type_min_value = TYPE_MIN_VALUE (type);
2547
2548                   min = (vr0.min != type_min_value
2549                          ? int_const_binop (PLUS_EXPR, type_min_value,
2550                                             integer_one_node, 0)
2551                          : type_min_value);
2552                 }
2553               else
2554                 {
2555                   if (overflow_infinity_range_p (&vr0))
2556                     min = negative_overflow_infinity (type);
2557                   else
2558                     min = TYPE_MIN_VALUE (type);
2559                 }
2560             }
2561           else
2562             {
2563               /* All else has failed, so create the range [0, INF], even for
2564                  flag_wrapv since TYPE_MIN_VALUE is in the original
2565                  anti-range.  */
2566               vr0.type = VR_RANGE;
2567               min = build_int_cst (type, 0);
2568               if (needs_overflow_infinity (type))
2569                 {
2570                   if (supports_overflow_infinity (type))
2571                     max = positive_overflow_infinity (type);
2572                   else
2573                     {
2574                       set_value_range_to_varying (vr);
2575                       return;
2576                     }
2577                 }
2578               else
2579                 max = TYPE_MAX_VALUE (type);
2580             }
2581         }
2582
2583       /* If the range contains zero then we know that the minimum value in the
2584          range will be zero.  */
2585       else if (range_includes_zero_p (&vr0))
2586         {
2587           if (cmp == 1)
2588             max = min;
2589           min = build_int_cst (type, 0);
2590         }
2591       else
2592         {
2593           /* If the range was reversed, swap MIN and MAX.  */
2594           if (cmp == 1)
2595             {
2596               tree t = min;
2597               min = max;
2598               max = t;
2599             }
2600         }
2601     }
2602   else
2603     {
2604       /* Otherwise, operate on each end of the range.  */
2605       min = fold_unary_to_constant (code, type, vr0.min);
2606       max = fold_unary_to_constant (code, type, vr0.max);
2607
2608       if (needs_overflow_infinity (type))
2609         {
2610           gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
2611
2612           /* If both sides have overflowed, we don't know
2613              anything.  */
2614           if ((is_overflow_infinity (vr0.min)
2615                || TREE_OVERFLOW (min))
2616               && (is_overflow_infinity (vr0.max)
2617                   || TREE_OVERFLOW (max)))
2618             {
2619               set_value_range_to_varying (vr);
2620               return;
2621             }
2622
2623           if (is_overflow_infinity (vr0.min))
2624             min = vr0.min;
2625           else if (TREE_OVERFLOW (min))
2626             {
2627               if (supports_overflow_infinity (type))
2628                 min = (tree_int_cst_sgn (min) >= 0
2629                        ? positive_overflow_infinity (TREE_TYPE (min))
2630                        : negative_overflow_infinity (TREE_TYPE (min)));
2631               else
2632                 {
2633                   set_value_range_to_varying (vr);
2634                   return;
2635                 }
2636             }
2637
2638           if (is_overflow_infinity (vr0.max))
2639             max = vr0.max;
2640           else if (TREE_OVERFLOW (max))
2641             {
2642               if (supports_overflow_infinity (type))
2643                 max = (tree_int_cst_sgn (max) >= 0
2644                        ? positive_overflow_infinity (TREE_TYPE (max))
2645                        : negative_overflow_infinity (TREE_TYPE (max)));
2646               else
2647                 {
2648                   set_value_range_to_varying (vr);
2649                   return;
2650                 }
2651             }
2652         }
2653     }
2654
2655   cmp = compare_values (min, max);
2656   if (cmp == -2 || cmp == 1)
2657     {
2658       /* If the new range has its limits swapped around (MIN > MAX),
2659          then the operation caused one of them to wrap around, mark
2660          the new range VARYING.  */
2661       set_value_range_to_varying (vr);
2662     }
2663   else
2664     set_value_range (vr, vr0.type, min, max, NULL);
2665 }
2666
2667
2668 /* Extract range information from a conditional expression EXPR based on
2669    the ranges of each of its operands and the expression code.  */
2670
2671 static void
2672 extract_range_from_cond_expr (value_range_t *vr, tree expr)
2673 {
2674   tree op0, op1;
2675   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2676   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2677
2678   /* Get value ranges for each operand.  For constant operands, create
2679      a new value range with the operand to simplify processing.  */
2680   op0 = COND_EXPR_THEN (expr);
2681   if (TREE_CODE (op0) == SSA_NAME)
2682     vr0 = *(get_value_range (op0));
2683   else if (is_gimple_min_invariant (op0))
2684     set_value_range_to_value (&vr0, op0, NULL);
2685   else
2686     set_value_range_to_varying (&vr0);
2687
2688   op1 = COND_EXPR_ELSE (expr);
2689   if (TREE_CODE (op1) == SSA_NAME)
2690     vr1 = *(get_value_range (op1));
2691   else if (is_gimple_min_invariant (op1))
2692     set_value_range_to_value (&vr1, op1, NULL);
2693   else
2694     set_value_range_to_varying (&vr1);
2695
2696   /* The resulting value range is the union of the operand ranges */
2697   vrp_meet (&vr0, &vr1);
2698   copy_value_range (vr, &vr0);
2699 }
2700
2701
2702 /* Extract range information from a comparison expression EXPR based
2703    on the range of its operand and the expression code.  */
2704
2705 static void
2706 extract_range_from_comparison (value_range_t *vr, enum tree_code code,
2707                                tree type, tree op0, tree op1)
2708 {
2709   bool sop = false;
2710   tree val = vrp_evaluate_conditional_warnv_with_ops (code,
2711                                                       op0,
2712                                                       op1,
2713                                                       false, &sop);
2714
2715   /* A disadvantage of using a special infinity as an overflow
2716      representation is that we lose the ability to record overflow
2717      when we don't have an infinity.  So we have to ignore a result
2718      which relies on overflow.  */
2719
2720   if (val && !is_overflow_infinity (val) && !sop)
2721     {
2722       /* Since this expression was found on the RHS of an assignment,
2723          its type may be different from _Bool.  Convert VAL to EXPR's
2724          type.  */
2725       val = fold_convert (type, val);
2726       if (is_gimple_min_invariant (val))
2727         set_value_range_to_value (vr, val, vr->equiv);
2728       else
2729         set_value_range (vr, VR_RANGE, val, val, vr->equiv);
2730     }
2731   else
2732     /* The result of a comparison is always true or false.  */
2733     set_value_range_to_truthvalue (vr, type);
2734 }
2735
2736
2737 /* Try to compute a useful range out of expression EXPR and store it
2738    in *VR.  */
2739
2740 static void
2741 extract_range_from_expr (value_range_t *vr, tree expr)
2742 {
2743   enum tree_code code = TREE_CODE (expr);
2744
2745   if (code == ASSERT_EXPR)
2746     extract_range_from_assert (vr, expr);
2747   else if (code == SSA_NAME)
2748     extract_range_from_ssa_name (vr, expr);
2749   else if (TREE_CODE_CLASS (code) == tcc_binary
2750            || code == TRUTH_AND_EXPR
2751            || code == TRUTH_OR_EXPR
2752            || code == TRUTH_XOR_EXPR)
2753     extract_range_from_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
2754                                     TREE_OPERAND (expr, 0),
2755                                     TREE_OPERAND (expr, 1));
2756   else if (TREE_CODE_CLASS (code) == tcc_unary)
2757     extract_range_from_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
2758                                    TREE_OPERAND (expr, 0));
2759   else if (code == COND_EXPR)
2760     extract_range_from_cond_expr (vr, expr);
2761   else if (TREE_CODE_CLASS (code) == tcc_comparison)
2762     extract_range_from_comparison (vr, TREE_CODE (expr), TREE_TYPE (expr),
2763                                    TREE_OPERAND (expr, 0),
2764                                    TREE_OPERAND (expr, 1));
2765   else if (is_gimple_min_invariant (expr))
2766     set_value_range_to_value (vr, expr, NULL);
2767   else
2768     set_value_range_to_varying (vr);
2769
2770   /* If we got a varying range from the tests above, try a final
2771      time to derive a nonnegative or nonzero range.  This time
2772      relying primarily on generic routines in fold in conjunction
2773      with range data.  */
2774   if (vr->type == VR_VARYING)
2775     {
2776       bool sop = false;
2777
2778       if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
2779           && vrp_expr_computes_nonnegative (expr, &sop))
2780         set_value_range_to_nonnegative (vr, TREE_TYPE (expr),
2781                                         sop || is_overflow_infinity (expr));
2782       else if (vrp_expr_computes_nonzero (expr, &sop)
2783                && !sop)
2784         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
2785     }
2786 }
2787
2788 /* Given a range VR, a LOOP and a variable VAR, determine whether it
2789    would be profitable to adjust VR using scalar evolution information
2790    for VAR.  If so, update VR with the new limits.  */
2791
2792 static void
2793 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
2794                         tree var)
2795 {
2796   tree init, step, chrec, tmin, tmax, min, max, type;
2797   enum ev_direction dir;
2798
2799   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
2800      better opportunities than a regular range, but I'm not sure.  */
2801   if (vr->type == VR_ANTI_RANGE)
2802     return;
2803
2804   /* Ensure that there are not values in the scev cache based on assumptions
2805      on ranges of ssa names that were changed
2806      (in set_value_range/set_value_range_to_varying).  Preserve cached numbers
2807      of iterations, that were computed before the start of VRP (we do not
2808      recompute these each time to save the compile time).  */
2809   scev_reset_except_niters ();
2810
2811   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
2812
2813   /* Like in PR19590, scev can return a constant function.  */
2814   if (is_gimple_min_invariant (chrec))
2815     {
2816       set_value_range_to_value (vr, chrec, vr->equiv);
2817       return;
2818     }
2819
2820   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2821     return;
2822
2823   init = initial_condition_in_loop_num (chrec, loop->num);
2824   step = evolution_part_in_loop_num (chrec, loop->num);
2825
2826   /* If STEP is symbolic, we can't know whether INIT will be the
2827      minimum or maximum value in the range.  Also, unless INIT is
2828      a simple expression, compare_values and possibly other functions
2829      in tree-vrp won't be able to handle it.  */
2830   if (step == NULL_TREE
2831       || !is_gimple_min_invariant (step)
2832       || !valid_value_p (init))
2833     return;
2834
2835   dir = scev_direction (chrec);
2836   if (/* Do not adjust ranges if we do not know whether the iv increases
2837          or decreases,  ... */
2838       dir == EV_DIR_UNKNOWN
2839       /* ... or if it may wrap.  */
2840       || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
2841                                 true))
2842     return;
2843
2844   /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
2845      negative_overflow_infinity and positive_overflow_infinity,
2846      because we have concluded that the loop probably does not
2847      wrap.  */
2848
2849   type = TREE_TYPE (var);
2850   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
2851     tmin = lower_bound_in_type (type, type);
2852   else
2853     tmin = TYPE_MIN_VALUE (type);
2854   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
2855     tmax = upper_bound_in_type (type, type);
2856   else
2857     tmax = TYPE_MAX_VALUE (type);
2858
2859   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2860     {
2861       min = tmin;
2862       max = tmax;
2863
2864       /* For VARYING or UNDEFINED ranges, just about anything we get
2865          from scalar evolutions should be better.  */
2866
2867       if (dir == EV_DIR_DECREASES)
2868         max = init;
2869       else
2870         min = init;
2871
2872       /* If we would create an invalid range, then just assume we
2873          know absolutely nothing.  This may be over-conservative,
2874          but it's clearly safe, and should happen only in unreachable
2875          parts of code, or for invalid programs.  */
2876       if (compare_values (min, max) == 1)
2877         return;
2878
2879       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2880     }
2881   else if (vr->type == VR_RANGE)
2882     {
2883       min = vr->min;
2884       max = vr->max;
2885
2886       if (dir == EV_DIR_DECREASES)
2887         {
2888           /* INIT is the maximum value.  If INIT is lower than VR->MAX
2889              but no smaller than VR->MIN, set VR->MAX to INIT.  */
2890           if (compare_values (init, max) == -1)
2891             {
2892               max = init;
2893
2894               /* If we just created an invalid range with the minimum
2895                  greater than the maximum, we fail conservatively.
2896                  This should happen only in unreachable
2897                  parts of code, or for invalid programs.  */
2898               if (compare_values (min, max) == 1)
2899                 return;
2900             }
2901
2902           /* According to the loop information, the variable does not
2903              overflow.  If we think it does, probably because of an
2904              overflow due to arithmetic on a different INF value,
2905              reset now.  */
2906           if (is_negative_overflow_infinity (min))
2907             min = tmin;
2908         }
2909       else
2910         {
2911           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
2912           if (compare_values (init, min) == 1)
2913             {
2914               min = init;
2915
2916               /* Again, avoid creating invalid range by failing.  */
2917               if (compare_values (min, max) == 1)
2918                 return;
2919             }
2920
2921           if (is_positive_overflow_infinity (max))
2922             max = tmax;
2923         }
2924
2925       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2926     }
2927 }
2928
2929 /* Return true if VAR may overflow at STMT.  This checks any available
2930    loop information to see if we can determine that VAR does not
2931    overflow.  */
2932
2933 static bool
2934 vrp_var_may_overflow (tree var, tree stmt)
2935 {
2936   struct loop *l;
2937   tree chrec, init, step;
2938
2939   if (current_loops == NULL)
2940     return true;
2941
2942   l = loop_containing_stmt (stmt);
2943   if (l == NULL)
2944     return true;
2945
2946   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
2947   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2948     return true;
2949
2950   init = initial_condition_in_loop_num (chrec, l->num);
2951   step = evolution_part_in_loop_num (chrec, l->num);
2952
2953   if (step == NULL_TREE
2954       || !is_gimple_min_invariant (step)
2955       || !valid_value_p (init))
2956     return true;
2957
2958   /* If we get here, we know something useful about VAR based on the
2959      loop information.  If it wraps, it may overflow.  */
2960
2961   if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
2962                              true))
2963     return true;
2964
2965   if (dump_file && (dump_flags & TDF_DETAILS) != 0)
2966     {
2967       print_generic_expr (dump_file, var, 0);
2968       fprintf (dump_file, ": loop information indicates does not overflow\n");
2969     }
2970
2971   return false;
2972 }
2973
2974
2975 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2976
2977    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2978      all the values in the ranges.
2979
2980    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2981
2982    - Return NULL_TREE if it is not always possible to determine the
2983      value of the comparison.
2984
2985    Also set *STRICT_OVERFLOW_P to indicate whether a range with an
2986    overflow infinity was used in the test.  */
2987
2988
2989 static tree
2990 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
2991                 bool *strict_overflow_p)
2992 {
2993   /* VARYING or UNDEFINED ranges cannot be compared.  */
2994   if (vr0->type == VR_VARYING
2995       || vr0->type == VR_UNDEFINED
2996       || vr1->type == VR_VARYING
2997       || vr1->type == VR_UNDEFINED)
2998     return NULL_TREE;
2999
3000   /* Anti-ranges need to be handled separately.  */
3001   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3002     {
3003       /* If both are anti-ranges, then we cannot compute any
3004          comparison.  */
3005       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3006         return NULL_TREE;
3007
3008       /* These comparisons are never statically computable.  */
3009       if (comp == GT_EXPR
3010           || comp == GE_EXPR
3011           || comp == LT_EXPR
3012           || comp == LE_EXPR)
3013         return NULL_TREE;
3014
3015       /* Equality can be computed only between a range and an
3016          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
3017       if (vr0->type == VR_RANGE)
3018         {
3019           /* To simplify processing, make VR0 the anti-range.  */
3020           value_range_t *tmp = vr0;
3021           vr0 = vr1;
3022           vr1 = tmp;
3023         }
3024
3025       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
3026
3027       if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
3028           && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
3029         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3030
3031       return NULL_TREE;
3032     }
3033
3034   if (!usable_range_p (vr0, strict_overflow_p)
3035       || !usable_range_p (vr1, strict_overflow_p))
3036     return NULL_TREE;
3037
3038   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
3039      operands around and change the comparison code.  */
3040   if (comp == GT_EXPR || comp == GE_EXPR)
3041     {
3042       value_range_t *tmp;
3043       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
3044       tmp = vr0;
3045       vr0 = vr1;
3046       vr1 = tmp;
3047     }
3048
3049   if (comp == EQ_EXPR)
3050     {
3051       /* Equality may only be computed if both ranges represent
3052          exactly one value.  */
3053       if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
3054           && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
3055         {
3056           int cmp_min = compare_values_warnv (vr0->min, vr1->min,
3057                                               strict_overflow_p);
3058           int cmp_max = compare_values_warnv (vr0->max, vr1->max,
3059                                               strict_overflow_p);
3060           if (cmp_min == 0 && cmp_max == 0)
3061             return boolean_true_node;
3062           else if (cmp_min != -2 && cmp_max != -2)
3063             return boolean_false_node;
3064         }
3065       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
3066       else if (compare_values_warnv (vr0->min, vr1->max,
3067                                      strict_overflow_p) == 1
3068                || compare_values_warnv (vr1->min, vr0->max,
3069                                         strict_overflow_p) == 1)
3070         return boolean_false_node;
3071
3072       return NULL_TREE;
3073     }
3074   else if (comp == NE_EXPR)
3075     {
3076       int cmp1, cmp2;
3077
3078       /* If VR0 is completely to the left or completely to the right
3079          of VR1, they are always different.  Notice that we need to
3080          make sure that both comparisons yield similar results to
3081          avoid comparing values that cannot be compared at
3082          compile-time.  */
3083       cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3084       cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3085       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
3086         return boolean_true_node;
3087
3088       /* If VR0 and VR1 represent a single value and are identical,
3089          return false.  */
3090       else if (compare_values_warnv (vr0->min, vr0->max,
3091                                      strict_overflow_p) == 0
3092                && compare_values_warnv (vr1->min, vr1->max,
3093                                         strict_overflow_p) == 0
3094                && compare_values_warnv (vr0->min, vr1->min,
3095                                         strict_overflow_p) == 0
3096                && compare_values_warnv (vr0->max, vr1->max,
3097                                         strict_overflow_p) == 0)
3098         return boolean_false_node;
3099
3100       /* Otherwise, they may or may not be different.  */
3101       else
3102         return NULL_TREE;
3103     }
3104   else if (comp == LT_EXPR || comp == LE_EXPR)
3105     {
3106       int tst;
3107
3108       /* If VR0 is to the left of VR1, return true.  */
3109       tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3110       if ((comp == LT_EXPR && tst == -1)
3111           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3112         {
3113           if (overflow_infinity_range_p (vr0)
3114               || overflow_infinity_range_p (vr1))
3115             *strict_overflow_p = true;
3116           return boolean_true_node;
3117         }
3118
3119       /* If VR0 is to the right of VR1, return false.  */
3120       tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3121       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3122           || (comp == LE_EXPR && tst == 1))
3123         {
3124           if (overflow_infinity_range_p (vr0)
3125               || overflow_infinity_range_p (vr1))
3126             *strict_overflow_p = true;
3127           return boolean_false_node;
3128         }
3129
3130       /* Otherwise, we don't know.  */
3131       return NULL_TREE;
3132     }
3133
3134   gcc_unreachable ();
3135 }
3136
3137
3138 /* Given a value range VR, a value VAL and a comparison code COMP, return
3139    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
3140    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
3141    always returns false.  Return NULL_TREE if it is not always
3142    possible to determine the value of the comparison.  Also set
3143    *STRICT_OVERFLOW_P to indicate whether a range with an overflow
3144    infinity was used in the test.  */
3145
3146 static tree
3147 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val,
3148                           bool *strict_overflow_p)
3149 {
3150   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3151     return NULL_TREE;
3152
3153   /* Anti-ranges need to be handled separately.  */
3154   if (vr->type == VR_ANTI_RANGE)
3155     {
3156       /* For anti-ranges, the only predicates that we can compute at
3157          compile time are equality and inequality.  */
3158       if (comp == GT_EXPR
3159           || comp == GE_EXPR
3160           || comp == LT_EXPR
3161           || comp == LE_EXPR)
3162         return NULL_TREE;
3163
3164       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
3165       if (value_inside_range (val, vr) == 1)
3166         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3167
3168       return NULL_TREE;
3169     }
3170
3171   if (!usable_range_p (vr, strict_overflow_p))
3172     return NULL_TREE;
3173
3174   if (comp == EQ_EXPR)
3175     {
3176       /* EQ_EXPR may only be computed if VR represents exactly
3177          one value.  */
3178       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
3179         {
3180           int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
3181           if (cmp == 0)
3182             return boolean_true_node;
3183           else if (cmp == -1 || cmp == 1 || cmp == 2)
3184             return boolean_false_node;
3185         }
3186       else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
3187                || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
3188         return boolean_false_node;
3189
3190       return NULL_TREE;
3191     }
3192   else if (comp == NE_EXPR)
3193     {
3194       /* If VAL is not inside VR, then they are always different.  */
3195       if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
3196           || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
3197         return boolean_true_node;
3198
3199       /* If VR represents exactly one value equal to VAL, then return
3200          false.  */
3201       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
3202           && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
3203         return boolean_false_node;
3204
3205       /* Otherwise, they may or may not be different.  */
3206       return NULL_TREE;
3207     }
3208   else if (comp == LT_EXPR || comp == LE_EXPR)
3209     {
3210       int tst;
3211
3212       /* If VR is to the left of VAL, return true.  */
3213       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3214       if ((comp == LT_EXPR && tst == -1)
3215           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3216         {
3217           if (overflow_infinity_range_p (vr))
3218             *strict_overflow_p = true;
3219           return boolean_true_node;
3220         }
3221
3222       /* If VR is to the right of VAL, return false.  */
3223       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3224       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3225           || (comp == LE_EXPR && tst == 1))
3226         {
3227           if (overflow_infinity_range_p (vr))
3228             *strict_overflow_p = true;
3229           return boolean_false_node;
3230         }
3231
3232       /* Otherwise, we don't know.  */
3233       return NULL_TREE;
3234     }
3235   else if (comp == GT_EXPR || comp == GE_EXPR)
3236     {
3237       int tst;
3238
3239       /* If VR is to the right of VAL, return true.  */
3240       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3241       if ((comp == GT_EXPR && tst == 1)
3242           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
3243         {
3244           if (overflow_infinity_range_p (vr))
3245             *strict_overflow_p = true;
3246           return boolean_true_node;
3247         }
3248
3249       /* If VR is to the left of VAL, return false.  */
3250       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3251       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
3252           || (comp == GE_EXPR && tst == -1))
3253         {
3254           if (overflow_infinity_range_p (vr))
3255             *strict_overflow_p = true;
3256           return boolean_false_node;
3257         }
3258
3259       /* Otherwise, we don't know.  */
3260       return NULL_TREE;
3261     }
3262
3263   gcc_unreachable ();
3264 }
3265
3266
3267 /* Debugging dumps.  */
3268
3269 void dump_value_range (FILE *, value_range_t *);
3270 void debug_value_range (value_range_t *);
3271 void dump_all_value_ranges (FILE *);
3272 void debug_all_value_ranges (void);
3273 void dump_vr_equiv (FILE *, bitmap);
3274 void debug_vr_equiv (bitmap);
3275
3276
3277 /* Dump value range VR to FILE.  */
3278
3279 void
3280 dump_value_range (FILE *file, value_range_t *vr)
3281 {
3282   if (vr == NULL)
3283     fprintf (file, "[]");
3284   else if (vr->type == VR_UNDEFINED)
3285     fprintf (file, "UNDEFINED");
3286   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
3287     {
3288       tree type = TREE_TYPE (vr->min);
3289
3290       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
3291
3292       if (is_negative_overflow_infinity (vr->min))
3293         fprintf (file, "-INF(OVF)");
3294       else if (INTEGRAL_TYPE_P (type)
3295                && !TYPE_UNSIGNED (type)
3296                && vrp_val_is_min (vr->min))
3297         fprintf (file, "-INF");
3298       else
3299         print_generic_expr (file, vr->min, 0);
3300
3301       fprintf (file, ", ");
3302
3303       if (is_positive_overflow_infinity (vr->max))
3304         fprintf (file, "+INF(OVF)");
3305       else if (INTEGRAL_TYPE_P (type)
3306                && vrp_val_is_max (vr->max))
3307         fprintf (file, "+INF");
3308       else
3309         print_generic_expr (file, vr->max, 0);
3310
3311       fprintf (file, "]");
3312
3313       if (vr->equiv)
3314         {
3315           bitmap_iterator bi;
3316           unsigned i, c = 0;
3317
3318           fprintf (file, "  EQUIVALENCES: { ");
3319
3320           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
3321             {
3322               print_generic_expr (file, ssa_name (i), 0);
3323               fprintf (file, " ");
3324               c++;
3325             }
3326
3327           fprintf (file, "} (%u elements)", c);
3328         }
3329     }
3330   else if (vr->type == VR_VARYING)
3331     fprintf (file, "VARYING");
3332   else
3333     fprintf (file, "INVALID RANGE");
3334 }
3335
3336
3337 /* Dump value range VR to stderr.  */
3338
3339 void
3340 debug_value_range (value_range_t *vr)
3341 {
3342   dump_value_range (stderr, vr);
3343   fprintf (stderr, "\n");
3344 }
3345
3346
3347 /* Dump value ranges of all SSA_NAMEs to FILE.  */
3348
3349 void
3350 dump_all_value_ranges (FILE *file)
3351 {
3352   size_t i;
3353
3354   for (i = 0; i < num_ssa_names; i++)
3355     {
3356       if (vr_value[i])
3357         {
3358           print_generic_expr (file, ssa_name (i), 0);
3359           fprintf (file, ": ");
3360           dump_value_range (file, vr_value[i]);
3361           fprintf (file, "\n");
3362         }
3363     }
3364
3365   fprintf (file, "\n");
3366 }
3367
3368
3369 /* Dump all value ranges to stderr.  */
3370
3371 void
3372 debug_all_value_ranges (void)
3373 {
3374   dump_all_value_ranges (stderr);
3375 }
3376
3377
3378 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
3379    create a new SSA name N and return the assertion assignment
3380    'V = ASSERT_EXPR <V, V OP W>'.  */
3381
3382 static tree
3383 build_assert_expr_for (tree cond, tree v)
3384 {
3385   tree n, assertion;
3386
3387   gcc_assert (TREE_CODE (v) == SSA_NAME);
3388   n = duplicate_ssa_name (v, NULL_TREE);
3389
3390   if (COMPARISON_CLASS_P (cond))
3391     {
3392       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
3393       assertion = build_gimple_modify_stmt (n, a);
3394     }
3395   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
3396     {
3397       /* Given !V, build the assignment N = false.  */
3398       tree op0 = TREE_OPERAND (cond, 0);
3399       gcc_assert (op0 == v);
3400       assertion = build_gimple_modify_stmt (n, boolean_false_node);
3401     }
3402   else if (TREE_CODE (cond) == SSA_NAME)
3403     {
3404       /* Given V, build the assignment N = true.  */
3405       gcc_assert (v == cond);
3406       assertion = build_gimple_modify_stmt (n, boolean_true_node);
3407     }
3408   else
3409     gcc_unreachable ();
3410
3411   SSA_NAME_DEF_STMT (n) = assertion;
3412
3413   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
3414      operand of the ASSERT_EXPR. Register the new name and the old one
3415      in the replacement table so that we can fix the SSA web after
3416      adding all the ASSERT_EXPRs.  */
3417   register_new_name_mapping (n, v);
3418
3419   return assertion;
3420 }
3421
3422
3423 /* Return false if EXPR is a predicate expression involving floating
3424    point values.  */
3425
3426 static inline bool
3427 fp_predicate (const_tree expr)
3428 {
3429   return (COMPARISON_CLASS_P (expr)
3430           && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
3431 }
3432
3433
3434 /* If the range of values taken by OP can be inferred after STMT executes,
3435    return the comparison code (COMP_CODE_P) and value (VAL_P) that
3436    describes the inferred range.  Return true if a range could be
3437    inferred.  */
3438
3439 static bool
3440 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
3441 {
3442   *val_p = NULL_TREE;
3443   *comp_code_p = ERROR_MARK;
3444
3445   /* Do not attempt to infer anything in names that flow through
3446      abnormal edges.  */
3447   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
3448     return false;
3449
3450   /* Similarly, don't infer anything from statements that may throw
3451      exceptions.  */
3452   if (tree_could_throw_p (stmt))
3453     return false;
3454
3455   /* If STMT is the last statement of a basic block with no
3456      successors, there is no point inferring anything about any of its
3457      operands.  We would not be able to find a proper insertion point
3458      for the assertion, anyway.  */
3459   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
3460     return false;
3461
3462   /* We can only assume that a pointer dereference will yield
3463      non-NULL if -fdelete-null-pointer-checks is enabled.  */
3464   if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
3465     {
3466       unsigned num_uses, num_loads, num_stores;
3467
3468       count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
3469       if (num_loads + num_stores > 0)
3470         {
3471           *val_p = build_int_cst (TREE_TYPE (op), 0);
3472           *comp_code_p = NE_EXPR;
3473           return true;
3474         }
3475     }
3476
3477   return false;
3478 }
3479
3480
3481 void dump_asserts_for (FILE *, tree);
3482 void debug_asserts_for (tree);
3483 void dump_all_asserts (FILE *);
3484 void debug_all_asserts (void);
3485
3486 /* Dump all the registered assertions for NAME to FILE.  */
3487
3488 void
3489 dump_asserts_for (FILE *file, tree name)
3490 {
3491   assert_locus_t loc;
3492
3493   fprintf (file, "Assertions to be inserted for ");
3494   print_generic_expr (file, name, 0);
3495   fprintf (file, "\n");
3496
3497   loc = asserts_for[SSA_NAME_VERSION (name)];
3498   while (loc)
3499     {
3500       fprintf (file, "\t");
3501       print_generic_expr (file, bsi_stmt (loc->si), 0);
3502       fprintf (file, "\n\tBB #%d", loc->bb->index);
3503       if (loc->e)
3504         {
3505           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
3506                    loc->e->dest->index);
3507           dump_edge_info (file, loc->e, 0);
3508         }
3509       fprintf (file, "\n\tPREDICATE: ");
3510       print_generic_expr (file, name, 0);
3511       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
3512       print_generic_expr (file, loc->val, 0);
3513       fprintf (file, "\n\n");
3514       loc = loc->next;
3515     }
3516
3517   fprintf (file, "\n");
3518 }
3519
3520
3521 /* Dump all the registered assertions for NAME to stderr.  */
3522
3523 void
3524 debug_asserts_for (tree name)
3525 {
3526   dump_asserts_for (stderr, name);
3527 }
3528
3529
3530 /* Dump all the registered assertions for all the names to FILE.  */
3531
3532 void
3533 dump_all_asserts (FILE *file)
3534 {
3535   unsigned i;
3536   bitmap_iterator bi;
3537
3538   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
3539   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3540     dump_asserts_for (file, ssa_name (i));
3541   fprintf (file, "\n");
3542 }
3543
3544
3545 /* Dump all the registered assertions for all the names to stderr.  */
3546
3547 void
3548 debug_all_asserts (void)
3549 {
3550   dump_all_asserts (stderr);
3551 }
3552
3553
3554 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
3555    'EXPR COMP_CODE VAL' at a location that dominates block BB or
3556    E->DEST, then register this location as a possible insertion point
3557    for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
3558
3559    BB, E and SI provide the exact insertion point for the new
3560    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
3561    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
3562    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
3563    must not be NULL.  */
3564
3565 static void
3566 register_new_assert_for (tree name, tree expr,
3567                          enum tree_code comp_code,
3568                          tree val,
3569                          basic_block bb,
3570                          edge e,
3571                          block_stmt_iterator si)
3572 {
3573   assert_locus_t n, loc, last_loc;
3574   bool found;
3575   basic_block dest_bb;
3576
3577 #if defined ENABLE_CHECKING
3578   gcc_assert (bb == NULL || e == NULL);
3579
3580   if (e == NULL)
3581     gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
3582                 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
3583 #endif
3584
3585   /* The new assertion A will be inserted at BB or E.  We need to
3586      determine if the new location is dominated by a previously
3587      registered location for A.  If we are doing an edge insertion,
3588      assume that A will be inserted at E->DEST.  Note that this is not
3589      necessarily true.
3590
3591      If E is a critical edge, it will be split.  But even if E is
3592      split, the new block will dominate the same set of blocks that
3593      E->DEST dominates.
3594
3595      The reverse, however, is not true, blocks dominated by E->DEST
3596      will not be dominated by the new block created to split E.  So,
3597      if the insertion location is on a critical edge, we will not use
3598      the new location to move another assertion previously registered
3599      at a block dominated by E->DEST.  */
3600   dest_bb = (bb) ? bb : e->dest;
3601
3602   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
3603      VAL at a block dominating DEST_BB, then we don't need to insert a new
3604      one.  Similarly, if the same assertion already exists at a block
3605      dominated by DEST_BB and the new location is not on a critical
3606      edge, then update the existing location for the assertion (i.e.,
3607      move the assertion up in the dominance tree).
3608
3609      Note, this is implemented as a simple linked list because there
3610      should not be more than a handful of assertions registered per
3611      name.  If this becomes a performance problem, a table hashed by
3612      COMP_CODE and VAL could be implemented.  */
3613   loc = asserts_for[SSA_NAME_VERSION (name)];
3614   last_loc = loc;
3615   found = false;
3616   while (loc)
3617     {
3618       if (loc->comp_code == comp_code
3619           && (loc->val == val
3620               || operand_equal_p (loc->val, val, 0))
3621           && (loc->expr == expr
3622               || operand_equal_p (loc->expr, expr, 0)))
3623         {
3624           /* If the assertion NAME COMP_CODE VAL has already been
3625              registered at a basic block that dominates DEST_BB, then
3626              we don't need to insert the same assertion again.  Note
3627              that we don't check strict dominance here to avoid
3628              replicating the same assertion inside the same basic
3629              block more than once (e.g., when a pointer is
3630              dereferenced several times inside a block).
3631
3632              An exception to this rule are edge insertions.  If the
3633              new assertion is to be inserted on edge E, then it will
3634              dominate all the other insertions that we may want to
3635              insert in DEST_BB.  So, if we are doing an edge
3636              insertion, don't do this dominance check.  */
3637           if (e == NULL
3638               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
3639             return;
3640
3641           /* Otherwise, if E is not a critical edge and DEST_BB
3642              dominates the existing location for the assertion, move
3643              the assertion up in the dominance tree by updating its
3644              location information.  */
3645           if ((e == NULL || !EDGE_CRITICAL_P (e))
3646               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
3647             {
3648               loc->bb = dest_bb;
3649               loc->e = e;
3650               loc->si = si;
3651               return;
3652             }
3653         }
3654
3655       /* Update the last node of the list and move to the next one.  */
3656       last_loc = loc;
3657       loc = loc->next;
3658     }
3659
3660   /* If we didn't find an assertion already registered for
3661      NAME COMP_CODE VAL, add a new one at the end of the list of
3662      assertions associated with NAME.  */
3663   n = XNEW (struct assert_locus_d);
3664   n->bb = dest_bb;
3665   n->e = e;
3666   n->si = si;
3667   n->comp_code = comp_code;
3668   n->val = val;
3669   n->expr = expr;
3670   n->next = NULL;
3671
3672   if (last_loc)
3673     last_loc->next = n;
3674   else
3675     asserts_for[SSA_NAME_VERSION (name)] = n;
3676
3677   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
3678 }
3679
3680 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
3681    Extract a suitable test code and value and store them into *CODE_P and
3682    *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
3683
3684    If no extraction was possible, return FALSE, otherwise return TRUE.
3685
3686    If INVERT is true, then we invert the result stored into *CODE_P.  */
3687
3688 static bool
3689 extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
3690                                          tree cond_op0, tree cond_op1,
3691                                          bool invert, enum tree_code *code_p,
3692                                          tree *val_p)
3693 {
3694   enum tree_code comp_code;
3695   tree val;
3696
3697   /* Otherwise, we have a comparison of the form NAME COMP VAL
3698      or VAL COMP NAME.  */
3699   if (name == cond_op1)
3700     {
3701       /* If the predicate is of the form VAL COMP NAME, flip
3702          COMP around because we need to register NAME as the
3703          first operand in the predicate.  */
3704       comp_code = swap_tree_comparison (cond_code);
3705       val = cond_op0;
3706     }
3707   else
3708     {
3709       /* The comparison is of the form NAME COMP VAL, so the
3710          comparison code remains unchanged.  */
3711       comp_code = cond_code;
3712       val = cond_op1;
3713     }
3714
3715   /* Invert the comparison code as necessary.  */
3716   if (invert)
3717     comp_code = invert_tree_comparison (comp_code, 0);
3718
3719   /* VRP does not handle float types.  */
3720   if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
3721     return false;
3722
3723   /* Do not register always-false predicates.
3724      FIXME:  this works around a limitation in fold() when dealing with
3725      enumerations.  Given 'enum { N1, N2 } x;', fold will not
3726      fold 'if (x > N2)' to 'if (0)'.  */
3727   if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
3728       && INTEGRAL_TYPE_P (TREE_TYPE (val)))
3729     {
3730       tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
3731       tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
3732
3733       if (comp_code == GT_EXPR
3734           && (!max
3735               || compare_values (val, max) == 0))
3736         return false;
3737
3738       if (comp_code == LT_EXPR
3739           && (!min
3740               || compare_values (val, min) == 0))
3741         return false;
3742     }
3743   *code_p = comp_code;
3744   *val_p = val;
3745   return true;
3746 }
3747
3748 /* Try to register an edge assertion for SSA name NAME on edge E for
3749    the condition COND contributing to the conditional jump pointed to by BSI.
3750    Invert the condition COND if INVERT is true.
3751    Return true if an assertion for NAME could be registered.  */
3752
3753 static bool
3754 register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
3755                             enum tree_code cond_code,
3756                             tree cond_op0, tree cond_op1, bool invert)
3757 {
3758   tree val;
3759   enum tree_code comp_code;
3760   bool retval = false;
3761
3762   if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
3763                                                 cond_op0,
3764                                                 cond_op1,
3765                                                 invert, &comp_code, &val))
3766     return false;
3767
3768   /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
3769      reachable from E.  */
3770   if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
3771       && !has_single_use (name))
3772     {
3773       register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
3774       retval = true;
3775     }
3776
3777   /* In the case of NAME <= CST and NAME being defined as
3778      NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
3779      and NAME2 <= CST - CST2.  We can do the same for NAME > CST.
3780      This catches range and anti-range tests.  */
3781   if ((comp_code == LE_EXPR
3782        || comp_code == GT_EXPR)
3783       && TREE_CODE (val) == INTEGER_CST
3784       && TYPE_UNSIGNED (TREE_TYPE (val)))
3785     {
3786       tree def_stmt = SSA_NAME_DEF_STMT (name);
3787       tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE;
3788
3789       /* Extract CST2 from the (optional) addition.  */
3790       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
3791           && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
3792         {
3793           name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
3794           cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
3795           if (TREE_CODE (name2) == SSA_NAME
3796               && TREE_CODE (cst2) == INTEGER_CST)
3797             def_stmt = SSA_NAME_DEF_STMT (name2);
3798         }
3799
3800       /* Extract NAME2 from the (optional) sign-changing cast.  */
3801       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
3802           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
3803               || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == CONVERT_EXPR))
3804         {
3805           tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
3806           if ((TREE_CODE (rhs) == NOP_EXPR
3807                || TREE_CODE (rhs) == CONVERT_EXPR)
3808               && ! TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (rhs, 0)))
3809               && (TYPE_PRECISION (TREE_TYPE (rhs))
3810                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0)))))
3811             name3 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
3812         }
3813
3814       /* If name3 is used later, create an ASSERT_EXPR for it.  */
3815       if (name3 != NULL_TREE
3816           && TREE_CODE (name3) == SSA_NAME
3817           && (cst2 == NULL_TREE
3818               || TREE_CODE (cst2) == INTEGER_CST)
3819           && INTEGRAL_TYPE_P (TREE_TYPE (name3))
3820           && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name3))
3821           && !has_single_use (name3))
3822         {
3823           tree tmp;
3824
3825           /* Build an expression for the range test.  */
3826           tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3);
3827           if (cst2 != NULL_TREE)
3828             tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
3829
3830           if (dump_file)
3831             {
3832               fprintf (dump_file, "Adding assert for ");
3833               print_generic_expr (dump_file, name3, 0);
3834               fprintf (dump_file, " from ");
3835               print_generic_expr (dump_file, tmp, 0);
3836               fprintf (dump_file, "\n");
3837             }
3838
3839           register_new_assert_for (name3, tmp, comp_code, val, NULL, e, bsi);
3840
3841           retval = true;
3842         }
3843
3844       /* If name2 is used later, create an ASSERT_EXPR for it.  */
3845       if (name2 != NULL_TREE
3846           && TREE_CODE (name2) == SSA_NAME
3847           && TREE_CODE (cst2) == INTEGER_CST
3848           && INTEGRAL_TYPE_P (TREE_TYPE (name2))
3849           && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
3850           && !has_single_use (name2))
3851         {
3852           tree tmp;
3853
3854           /* Build an expression for the range test.  */
3855           tmp = name2;
3856           if (TREE_TYPE (name) != TREE_TYPE (name2))
3857             tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
3858           if (cst2 != NULL_TREE)
3859             tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
3860
3861           if (dump_file)
3862             {
3863               fprintf (dump_file, "Adding assert for ");
3864               print_generic_expr (dump_file, name2, 0);
3865               fprintf (dump_file, " from ");
3866               print_generic_expr (dump_file, tmp, 0);
3867               fprintf (dump_file, "\n");
3868             }
3869
3870           register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
3871
3872           retval = true;
3873         }
3874     }
3875
3876   return retval;
3877 }
3878
3879 /* OP is an operand of a truth value expression which is known to have
3880    a particular value.  Register any asserts for OP and for any
3881    operands in OP's defining statement.
3882
3883    If CODE is EQ_EXPR, then we want to register OP is zero (false),
3884    if CODE is NE_EXPR, then we want to register OP is nonzero (true).   */
3885
3886 static bool
3887 register_edge_assert_for_1 (tree op, enum tree_code code,
3888                             edge e, block_stmt_iterator bsi)
3889 {
3890   bool retval = false;
3891   tree op_def, rhs, val;
3892   enum tree_code rhs_code;
3893
3894   /* We only care about SSA_NAMEs.  */
3895   if (TREE_CODE (op) != SSA_NAME)
3896     return false;
3897
3898   /* We know that OP will have a zero or nonzero value.  If OP is used
3899      more than once go ahead and register an assert for OP.
3900
3901      The FOUND_IN_SUBGRAPH support is not helpful in this situation as
3902      it will always be set for OP (because OP is used in a COND_EXPR in
3903      the subgraph).  */
3904   if (!has_single_use (op))
3905     {
3906       val = build_int_cst (TREE_TYPE (op), 0);
3907       register_new_assert_for (op, op, code, val, NULL, e, bsi);
3908       retval = true;
3909     }
3910
3911   /* Now look at how OP is set.  If it's set from a comparison,
3912      a truth operation or some bit operations, then we may be able
3913      to register information about the operands of that assignment.  */
3914   op_def = SSA_NAME_DEF_STMT (op);
3915   if (TREE_CODE (op_def) != GIMPLE_MODIFY_STMT)
3916     return retval;
3917
3918   rhs = GIMPLE_STMT_OPERAND (op_def, 1);
3919   rhs_code = TREE_CODE (rhs);
3920
3921   if (COMPARISON_CLASS_P (rhs))
3922     {
3923       bool invert = (code == EQ_EXPR ? true : false);
3924       tree op0 = TREE_OPERAND (rhs, 0);
3925       tree op1 = TREE_OPERAND (rhs, 1);
3926
3927       if (TREE_CODE (op0) == SSA_NAME)
3928         retval |= register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1,
3929                                               invert);
3930       if (TREE_CODE (op1) == SSA_NAME)
3931         retval |= register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1,
3932                                               invert);
3933     }
3934   else if ((code == NE_EXPR
3935             && (TREE_CODE (rhs) == TRUTH_AND_EXPR
3936                 || TREE_CODE (rhs) == BIT_AND_EXPR))
3937            || (code == EQ_EXPR
3938                && (TREE_CODE (rhs) == TRUTH_OR_EXPR
3939                    || TREE_CODE (rhs) == BIT_IOR_EXPR)))
3940     {
3941       /* Recurse on each operand.  */
3942       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3943                                             code, e, bsi);
3944       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 1),
3945                                             code, e, bsi);
3946     }
3947   else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
3948     {
3949       /* Recurse, flipping CODE.  */
3950       code = invert_tree_comparison (code, false);
3951       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3952                                             code, e, bsi);
3953     }
3954   else if (TREE_CODE (rhs) == SSA_NAME)
3955     {
3956       /* Recurse through the copy.  */
3957       retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
3958     }
3959   else if (TREE_CODE (rhs) == NOP_EXPR
3960            || TREE_CODE (rhs) == CONVERT_EXPR
3961            || TREE_CODE (rhs) == NON_LVALUE_EXPR)
3962     {
3963       /* Recurse through the type conversion.  */
3964       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3965                                             code, e, bsi);
3966     }
3967
3968   return retval;
3969 }
3970
3971 /* Try to register an edge assertion for SSA name NAME on edge E for
3972    the condition COND contributing to the conditional jump pointed to by SI.
3973    Return true if an assertion for NAME could be registered.  */
3974
3975 static bool
3976 register_edge_assert_for (tree name, edge e, block_stmt_iterator si,
3977                           enum tree_code cond_code, tree cond_op0,
3978                           tree cond_op1)
3979 {
3980   tree val;
3981   enum tree_code comp_code;
3982   bool retval = false;
3983   bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
3984
3985   /* Do not attempt to infer anything in names that flow through
3986      abnormal edges.  */
3987   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
3988     return false;
3989
3990   if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
3991                                                 cond_op0, cond_op1,
3992                                                 is_else_edge,
3993                                                 &comp_code, &val))
3994     return false;
3995
3996   /* Register ASSERT_EXPRs for name.  */
3997   retval |= register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
3998                                         cond_op1, is_else_edge);
3999
4000
4001   /* If COND is effectively an equality test of an SSA_NAME against
4002      the value zero or one, then we may be able to assert values
4003      for SSA_NAMEs which flow into COND.  */
4004
4005   /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
4006      statement of NAME we can assert both operands of the TRUTH_AND_EXPR
4007      have nonzero value.  */
4008   if (((comp_code == EQ_EXPR && integer_onep (val))
4009        || (comp_code == NE_EXPR && integer_zerop (val))))
4010     {
4011       tree def_stmt = SSA_NAME_DEF_STMT (name);
4012
4013       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4014           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_AND_EXPR
4015               || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == BIT_AND_EXPR))
4016         {
4017           tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4018           tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
4019           retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
4020           retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
4021         }
4022     }
4023
4024   /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
4025      statement of NAME we can assert both operands of the TRUTH_OR_EXPR
4026      have zero value.  */
4027   if (((comp_code == EQ_EXPR && integer_zerop (val))
4028        || (comp_code == NE_EXPR && integer_onep (val))))
4029     {
4030       tree def_stmt = SSA_NAME_DEF_STMT (name);
4031
4032       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4033           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_OR_EXPR
4034               /* For BIT_IOR_EXPR only if NAME == 0 both operands have
4035                  necessarily zero value.  */
4036               || (comp_code == EQ_EXPR
4037                   && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1))
4038                         == BIT_IOR_EXPR))))
4039         {
4040           tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4041           tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
4042           retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
4043           retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
4044         }
4045     }
4046
4047   return retval;
4048 }
4049
4050
4051 static bool find_assert_locations (basic_block bb);
4052
4053 /* Determine whether the outgoing edges of BB should receive an
4054    ASSERT_EXPR for each of the operands of BB's LAST statement.
4055    The last statement of BB must be a COND_EXPR.
4056
4057    If any of the sub-graphs rooted at BB have an interesting use of
4058    the predicate operands, an assert location node is added to the
4059    list of assertions for the corresponding operands.  */
4060
4061 static bool
4062 find_conditional_asserts (basic_block bb, tree last)
4063 {
4064   bool need_assert;
4065   block_stmt_iterator bsi;
4066   tree op;
4067   edge_iterator ei;
4068   edge e;
4069   ssa_op_iter iter;
4070
4071   need_assert = false;
4072   bsi = bsi_for_stmt (last);
4073
4074   /* Look for uses of the operands in each of the sub-graphs
4075      rooted at BB.  We need to check each of the outgoing edges
4076      separately, so that we know what kind of ASSERT_EXPR to
4077      insert.  */
4078   FOR_EACH_EDGE (e, ei, bb->succs)
4079     {
4080       if (e->dest == bb)
4081         continue;
4082
4083       /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
4084          Otherwise, when we finish traversing each of the sub-graphs, we
4085          won't know whether the variables were found in the sub-graphs or
4086          if they had been found in a block upstream from BB.
4087
4088          This is actually a bad idea is some cases, particularly jump
4089          threading.  Consider a CFG like the following:
4090
4091                     0
4092                    /|
4093                   1 |
4094                    \|
4095                     2
4096                    / \
4097                   3   4
4098
4099          Assume that one or more operands in the conditional at the
4100          end of block 0 are used in a conditional in block 2, but not
4101          anywhere in block 1.  In this case we will not insert any
4102          assert statements in block 1, which may cause us to miss
4103          opportunities to optimize, particularly for jump threading.  */
4104       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4105         RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4106
4107       /* Traverse the strictly dominated sub-graph rooted at E->DEST
4108          to determine if any of the operands in the conditional
4109          predicate are used.  */
4110       need_assert |= find_assert_locations (e->dest);
4111
4112       /* Register the necessary assertions for each operand in the
4113          conditional predicate.  */
4114       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4115         {
4116           tree cond = COND_EXPR_COND (last);
4117           if (op != cond)
4118             need_assert |= register_edge_assert_for (op, e, bsi,
4119                                                      TREE_CODE (cond),
4120                                                      TREE_OPERAND (cond, 0),
4121                                                      TREE_OPERAND (cond, 1));
4122           else
4123             need_assert |= register_edge_assert_for (op, e, bsi, EQ_EXPR, op,
4124                                                      boolean_true_node);
4125         }
4126     }
4127
4128   /* Finally, indicate that we have found the operands in the
4129      conditional.  */
4130   FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4131     SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4132
4133   return need_assert;
4134 }
4135
4136 /* Compare two case labels sorting first by the destination label uid
4137    and then by the case value.  */
4138
4139 static int
4140 compare_case_labels (const void *p1, const void *p2)
4141 {
4142   const_tree const case1 = *(const_tree const*)p1;
4143   const_tree const case2 = *(const_tree const*)p2;
4144   unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
4145   unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
4146
4147   if (uid1 < uid2)
4148     return -1;
4149   else if (uid1 == uid2)
4150     {
4151       /* Make sure the default label is first in a group.  */
4152       if (!CASE_LOW (case1))
4153         return -1;
4154       else if (!CASE_LOW (case2))
4155         return 1;
4156       else
4157         return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
4158     }
4159   else
4160     return 1;
4161 }
4162
4163 /* Determine whether the outgoing edges of BB should receive an
4164    ASSERT_EXPR for each of the operands of BB's LAST statement.
4165    The last statement of BB must be a SWITCH_EXPR.
4166
4167    If any of the sub-graphs rooted at BB have an interesting use of
4168    the predicate operands, an assert location node is added to the
4169    list of assertions for the corresponding operands.  */
4170
4171 static bool
4172 find_switch_asserts (basic_block bb, tree last)
4173 {
4174   bool need_assert;
4175   block_stmt_iterator bsi;
4176   tree op;
4177   edge e;
4178   tree vec = SWITCH_LABELS (last), vec2;
4179   size_t n = TREE_VEC_LENGTH (vec);
4180   unsigned int idx;
4181
4182   need_assert = false;
4183   bsi = bsi_for_stmt (last);
4184   op = TREE_OPERAND (last, 0);
4185   if (TREE_CODE (op) != SSA_NAME)
4186     return false;
4187
4188   /* Build a vector of case labels sorted by destination label.  */
4189   vec2 = make_tree_vec (n);
4190   for (idx = 0; idx < n; ++idx)
4191     TREE_VEC_ELT (vec2, idx) = TREE_VEC_ELT (vec, idx);
4192   qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
4193
4194   for (idx = 0; idx < n; ++idx)
4195     {
4196       tree min, max;
4197       tree cl = TREE_VEC_ELT (vec2, idx);
4198
4199       min = CASE_LOW (cl);
4200       max = CASE_HIGH (cl);
4201
4202       /* If there are multiple case labels with the same destination
4203          we need to combine them to a single value range for the edge.  */
4204       if (idx + 1 < n
4205           && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
4206         {
4207           /* Skip labels until the last of the group.  */
4208           do {
4209             ++idx;
4210           } while (idx < n
4211                    && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
4212           --idx;
4213
4214           /* Pick up the maximum of the case label range.  */
4215           if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
4216             max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
4217           else
4218             max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
4219         }
4220
4221       /* Nothing to do if the range includes the default label until we
4222          can register anti-ranges.  */
4223       if (min == NULL_TREE)
4224         continue;
4225
4226       /* Find the edge to register the assert expr on.  */
4227       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
4228
4229       /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
4230          Otherwise, when we finish traversing each of the sub-graphs, we
4231          won't know whether the variables were found in the sub-graphs or
4232          if they had been found in a block upstream from BB.  */
4233       RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4234
4235       /* Traverse the strictly dominated sub-graph rooted at E->DEST
4236          to determine if any of the operands in the conditional
4237          predicate are used.  */
4238       if (e->dest != bb)
4239         need_assert |= find_assert_locations (e->dest);
4240
4241       /* Register the necessary assertions for the operand in the
4242          SWITCH_EXPR.  */
4243       need_assert |= register_edge_assert_for (op, e, bsi,
4244                                                max ? GE_EXPR : EQ_EXPR,
4245                                                op,
4246                                                fold_convert (TREE_TYPE (op),
4247                                                              min));
4248       if (max)
4249         {
4250           need_assert |= register_edge_assert_for (op, e, bsi, LE_EXPR,
4251                                                    op,
4252                                                    fold_convert (TREE_TYPE (op),
4253                                                                  max));
4254         }
4255     }
4256
4257   /* Finally, indicate that we have found the operand in the
4258      SWITCH_EXPR.  */
4259   SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4260
4261   return need_assert;
4262 }
4263
4264
4265 /* Traverse all the statements in block BB looking for statements that
4266    may generate useful assertions for the SSA names in their operand.
4267    If a statement produces a useful assertion A for name N_i, then the
4268    list of assertions already generated for N_i is scanned to
4269    determine if A is actually needed.
4270
4271    If N_i already had the assertion A at a location dominating the
4272    current location, then nothing needs to be done.  Otherwise, the
4273    new location for A is recorded instead.
4274
4275    1- For every statement S in BB, all the variables used by S are
4276       added to bitmap FOUND_IN_SUBGRAPH.
4277
4278    2- If statement S uses an operand N in a way that exposes a known
4279       value range for N, then if N was not already generated by an
4280       ASSERT_EXPR, create a new assert location for N.  For instance,
4281       if N is a pointer and the statement dereferences it, we can
4282       assume that N is not NULL.
4283
4284    3- COND_EXPRs are a special case of #2.  We can derive range
4285       information from the predicate but need to insert different
4286       ASSERT_EXPRs for each of the sub-graphs rooted at the
4287       conditional block.  If the last statement of BB is a conditional
4288       expression of the form 'X op Y', then
4289
4290       a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
4291
4292       b) If the conditional is the only entry point to the sub-graph
4293          corresponding to the THEN_CLAUSE, recurse into it.  On
4294          return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
4295          an ASSERT_EXPR is added for the corresponding variable.
4296
4297       c) Repeat step (b) on the ELSE_CLAUSE.
4298
4299       d) Mark X and Y in FOUND_IN_SUBGRAPH.
4300
4301       For instance,
4302
4303             if (a == 9)
4304               b = a;
4305             else
4306               b = c + 1;
4307
4308       In this case, an assertion on the THEN clause is useful to
4309       determine that 'a' is always 9 on that edge.  However, an assertion
4310       on the ELSE clause would be unnecessary.
4311
4312    4- If BB does not end in a conditional expression, then we recurse
4313       into BB's dominator children.
4314
4315    At the end of the recursive traversal, every SSA name will have a
4316    list of locations where ASSERT_EXPRs should be added.  When a new
4317    location for name N is found, it is registered by calling
4318    register_new_assert_for.  That function keeps track of all the
4319    registered assertions to prevent adding unnecessary assertions.
4320    For instance, if a pointer P_4 is dereferenced more than once in a
4321    dominator tree, only the location dominating all the dereference of
4322    P_4 will receive an ASSERT_EXPR.
4323
4324    If this function returns true, then it means that there are names
4325    for which we need to generate ASSERT_EXPRs.  Those assertions are
4326    inserted by process_assert_insertions.  */
4327
4328 static bool
4329 find_assert_locations (basic_block bb)
4330 {
4331   block_stmt_iterator si;
4332   tree last, phi;
4333   bool need_assert;
4334   basic_block son;
4335
4336   if (TEST_BIT (blocks_visited, bb->index))
4337     return false;
4338
4339   SET_BIT (blocks_visited, bb->index);
4340
4341   need_assert = false;
4342
4343   /* Traverse all PHI nodes in BB marking used operands.  */
4344   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4345     {
4346       use_operand_p arg_p;
4347       ssa_op_iter i;
4348
4349       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
4350         {
4351           tree arg = USE_FROM_PTR (arg_p);
4352           if (TREE_CODE (arg) == SSA_NAME)
4353             {
4354               gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
4355               SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
4356             }
4357         }
4358     }
4359
4360   /* Traverse all the statements in BB marking used names and looking
4361      for statements that may infer assertions for their used operands.  */
4362   last = NULL_TREE;
4363   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4364     {
4365       tree stmt, op;
4366       ssa_op_iter i;
4367
4368       stmt = bsi_stmt (si);
4369
4370       /* See if we can derive an assertion for any of STMT's operands.  */
4371       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
4372         {
4373           tree value;
4374           enum tree_code comp_code;
4375
4376           /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
4377              the sub-graph of a conditional block, when we return from
4378              this recursive walk, our parent will use the
4379              FOUND_IN_SUBGRAPH bitset to determine if one of the
4380              operands it was looking for was present in the sub-graph.  */
4381           SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4382
4383           /* If OP is used in such a way that we can infer a value
4384              range for it, and we don't find a previous assertion for
4385              it, create a new assertion location node for OP.  */
4386           if (infer_value_range (stmt, op, &comp_code, &value))
4387             {
4388               /* If we are able to infer a nonzero value range for OP,
4389                  then walk backwards through the use-def chain to see if OP
4390                  was set via a typecast.
4391
4392                  If so, then we can also infer a nonzero value range
4393                  for the operand of the NOP_EXPR.  */
4394               if (comp_code == NE_EXPR && integer_zerop (value))
4395                 {
4396                   tree t = op;
4397                   tree def_stmt = SSA_NAME_DEF_STMT (t);
4398
4399                   while (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4400                          && TREE_CODE
4401                              (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
4402                          && TREE_CODE
4403                              (TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1),
4404                                             0)) == SSA_NAME
4405                          && POINTER_TYPE_P
4406                              (TREE_TYPE (TREE_OPERAND
4407                                           (GIMPLE_STMT_OPERAND (def_stmt,
4408                                                                 1), 0))))
4409                     {
4410                       t = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4411                       def_stmt = SSA_NAME_DEF_STMT (t);
4412
4413                       /* Note we want to register the assert for the
4414                          operand of the NOP_EXPR after SI, not after the
4415                          conversion.  */
4416                       if (! has_single_use (t))
4417                         {
4418                           register_new_assert_for (t, t, comp_code, value,
4419                                                    bb, NULL, si);
4420                           need_assert = true;
4421                         }
4422                     }
4423                 }
4424
4425               /* If OP is used only once, namely in this STMT, don't
4426                  bother creating an ASSERT_EXPR for it.  Such an
4427                  ASSERT_EXPR would do nothing but increase compile time.  */
4428               if (!has_single_use (op))
4429                 {
4430                   register_new_assert_for (op, op, comp_code, value,
4431                                            bb, NULL, si);
4432                   need_assert = true;
4433                 }
4434             }
4435         }
4436
4437       /* Remember the last statement of the block.  */
4438       last = stmt;
4439     }
4440
4441   /* If BB's last statement is a conditional expression
4442      involving integer operands, recurse into each of the sub-graphs
4443      rooted at BB to determine if we need to add ASSERT_EXPRs.  */
4444   if (last
4445       && TREE_CODE (last) == COND_EXPR
4446       && !fp_predicate (COND_EXPR_COND (last))
4447       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4448     need_assert |= find_conditional_asserts (bb, last);
4449
4450   if (last
4451       && TREE_CODE (last) == SWITCH_EXPR
4452       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4453     need_assert |= find_switch_asserts (bb, last);
4454
4455   /* Recurse into the dominator children of BB.  */
4456   for (son = first_dom_son (CDI_DOMINATORS, bb);
4457        son;
4458        son = next_dom_son (CDI_DOMINATORS, son))
4459     need_assert |= find_assert_locations (son);
4460
4461   return need_assert;
4462 }
4463
4464
4465 /* Create an ASSERT_EXPR for NAME and insert it in the location
4466    indicated by LOC.  Return true if we made any edge insertions.  */
4467
4468 static bool
4469 process_assert_insertions_for (tree name, assert_locus_t loc)
4470 {
4471   /* Build the comparison expression NAME_i COMP_CODE VAL.  */
4472   tree stmt, cond, assert_expr;
4473   edge_iterator ei;
4474   edge e;
4475
4476   cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
4477   assert_expr = build_assert_expr_for (cond, name);
4478
4479   if (loc->e)
4480     {
4481       /* We have been asked to insert the assertion on an edge.  This
4482          is used only by COND_EXPR and SWITCH_EXPR assertions.  */
4483 #if defined ENABLE_CHECKING
4484       gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
4485           || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
4486 #endif
4487
4488       bsi_insert_on_edge (loc->e, assert_expr);
4489       return true;
4490     }
4491
4492   /* Otherwise, we can insert right after LOC->SI iff the
4493      statement must not be the last statement in the block.  */
4494   stmt = bsi_stmt (loc->si);
4495   if (!stmt_ends_bb_p (stmt))
4496     {
4497       bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
4498       return false;
4499     }
4500
4501   /* If STMT must be the last statement in BB, we can only insert new
4502      assertions on the non-abnormal edge out of BB.  Note that since
4503      STMT is not control flow, there may only be one non-abnormal edge
4504      out of BB.  */
4505   FOR_EACH_EDGE (e, ei, loc->bb->succs)
4506     if (!(e->flags & EDGE_ABNORMAL))
4507       {
4508         bsi_insert_on_edge (e, assert_expr);
4509         return true;
4510       }
4511
4512   gcc_unreachable ();
4513 }
4514
4515
4516 /* Process all the insertions registered for every name N_i registered
4517    in NEED_ASSERT_FOR.  The list of assertions to be inserted are
4518    found in ASSERTS_FOR[i].  */
4519
4520 static void
4521 process_assert_insertions (void)
4522 {
4523   unsigned i;
4524   bitmap_iterator bi;
4525   bool update_edges_p = false;
4526   int num_asserts = 0;
4527
4528   if (dump_file && (dump_flags & TDF_DETAILS))
4529     dump_all_asserts (dump_file);
4530
4531   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
4532     {
4533       assert_locus_t loc = asserts_for[i];
4534       gcc_assert (loc);
4535
4536       while (loc)
4537         {
4538           assert_locus_t next = loc->next;
4539           update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
4540           free (loc);
4541           loc = next;
4542           num_asserts++;
4543         }
4544     }
4545
4546   if (update_edges_p)
4547     bsi_commit_edge_inserts ();
4548
4549   if (dump_file && (dump_flags & TDF_STATS))
4550     fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
4551              num_asserts);
4552 }
4553
4554
4555 /* Traverse the flowgraph looking for conditional jumps to insert range
4556    expressions.  These range expressions are meant to provide information
4557    to optimizations that need to reason in terms of value ranges.  They
4558    will not be expanded into RTL.  For instance, given:
4559
4560    x = ...
4561    y = ...
4562    if (x < y)
4563      y = x - 2;
4564    else
4565      x = y + 3;
4566
4567    this pass will transform the code into:
4568
4569    x = ...
4570    y = ...
4571    if (x < y)
4572     {
4573       x = ASSERT_EXPR <x, x < y>
4574       y = x - 2
4575     }
4576    else
4577     {
4578       y = ASSERT_EXPR <y, x <= y>
4579       x = y + 3
4580     }
4581
4582    The idea is that once copy and constant propagation have run, other
4583    optimizations will be able to determine what ranges of values can 'x'
4584    take in different paths of the code, simply by checking the reaching
4585    definition of 'x'.  */
4586
4587 static void
4588 insert_range_assertions (void)
4589 {
4590   edge e;
4591   edge_iterator ei;
4592   bool update_ssa_p;
4593
4594   found_in_subgraph = sbitmap_alloc (num_ssa_names);
4595   sbitmap_zero (found_in_subgraph);
4596
4597   blocks_visited = sbitmap_alloc (last_basic_block);
4598   sbitmap_zero (blocks_visited);
4599
4600   need_assert_for = BITMAP_ALLOC (NULL);
4601   asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
4602
4603   calculate_dominance_info (CDI_DOMINATORS);
4604
4605   update_ssa_p = false;
4606   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
4607     if (find_assert_locations (e->dest))
4608       update_ssa_p = true;
4609
4610   if (update_ssa_p)
4611     {
4612       process_assert_insertions ();
4613       update_ssa (TODO_update_ssa_no_phi);
4614     }
4615
4616   if (dump_file && (dump_flags & TDF_DETAILS))
4617     {
4618       fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
4619       dump_function_to_file (current_function_decl, dump_file, dump_flags);
4620     }
4621
4622   sbitmap_free (found_in_subgraph);
4623   free (asserts_for);
4624   BITMAP_FREE (need_assert_for);
4625 }
4626
4627 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
4628    and "struct" hacks. If VRP can determine that the
4629    array subscript is a constant, check if it is outside valid
4630    range. If the array subscript is a RANGE, warn if it is
4631    non-overlapping with valid range.
4632    IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.  */
4633
4634 static void
4635 check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one)
4636 {
4637   value_range_t* vr = NULL;
4638   tree low_sub, up_sub;
4639   tree low_bound, up_bound = array_ref_up_bound (ref);
4640
4641   low_sub = up_sub = TREE_OPERAND (ref, 1);
4642
4643   if (!up_bound || TREE_NO_WARNING (ref)
4644       || TREE_CODE (up_bound) != INTEGER_CST
4645       /* Can not check flexible arrays.  */
4646       || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
4647           && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
4648           && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
4649       /* Accesses after the end of arrays of size 0 (gcc
4650          extension) and 1 are likely intentional ("struct
4651          hack").  */
4652       || compare_tree_int (up_bound, 1) <= 0)
4653     return;
4654
4655   low_bound = array_ref_low_bound (ref);
4656
4657   if (TREE_CODE (low_sub) == SSA_NAME)
4658     {
4659       vr = get_value_range (low_sub);
4660       if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
4661         {
4662           low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
4663           up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
4664         }
4665     }
4666
4667   if (vr && vr->type == VR_ANTI_RANGE)
4668     {
4669       if (TREE_CODE (up_sub) == INTEGER_CST
4670           && tree_int_cst_lt (up_bound, up_sub)
4671           && TREE_CODE (low_sub) == INTEGER_CST
4672           && tree_int_cst_lt (low_sub, low_bound))
4673         {
4674           warning (OPT_Warray_bounds,
4675                    "%Harray subscript is outside array bounds", locus);
4676           TREE_NO_WARNING (ref) = 1;
4677         }
4678     }
4679   else if (TREE_CODE (up_sub) == INTEGER_CST
4680            && tree_int_cst_lt (up_bound, up_sub)
4681            && !tree_int_cst_equal (up_bound, up_sub)
4682            && (!ignore_off_by_one
4683                || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
4684                                                         up_bound,
4685                                                         integer_one_node,
4686                                                         0),
4687                                        up_sub)))
4688     {
4689       warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
4690                locus);
4691       TREE_NO_WARNING (ref) = 1;
4692     }
4693   else if (TREE_CODE (low_sub) == INTEGER_CST
4694            && tree_int_cst_lt (low_sub, low_bound))
4695     {
4696       warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
4697                locus);
4698       TREE_NO_WARNING (ref) = 1;
4699     }
4700 }
4701
4702 /* Searches if the expr T, located at LOCATION computes
4703    address of an ARRAY_REF, and call check_array_ref on it.  */
4704
4705 static void
4706 search_for_addr_array(tree t, location_t* location)
4707 {
4708   while (TREE_CODE (t) == SSA_NAME)
4709     {
4710       t = SSA_NAME_DEF_STMT (t);
4711       if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
4712         return;
4713       t = GIMPLE_STMT_OPERAND (t, 1);
4714     }
4715
4716
4717   /* We are only interested in addresses of ARRAY_REF's.  */
4718   if (TREE_CODE (t) != ADDR_EXPR)
4719     return;
4720
4721   /* Check each ARRAY_REFs in the reference chain. */
4722   do
4723     {
4724       if (TREE_CODE (t) == ARRAY_REF)
4725         check_array_ref (t, location, true /*ignore_off_by_one*/);
4726
4727       t = TREE_OPERAND(t,0);
4728     }
4729   while (handled_component_p (t));
4730 }
4731
4732 /* walk_tree() callback that checks if *TP is
4733    an ARRAY_REF inside an ADDR_EXPR (in which an array
4734    subscript one outside the valid range is allowed). Call
4735    check_array_ref for each ARRAY_REF found. The location is
4736    passed in DATA.  */
4737
4738 static tree
4739 check_array_bounds (tree *tp, int *walk_subtree, void *data)
4740 {
4741   tree t = *tp;
4742   tree stmt = (tree)data;
4743   location_t *location = EXPR_LOCUS (stmt);
4744
4745   if (!EXPR_HAS_LOCATION (stmt))
4746     {
4747       *walk_subtree = FALSE;
4748       return NULL_TREE;
4749     }
4750
4751   *walk_subtree = TRUE;
4752
4753   if (TREE_CODE (t) == ARRAY_REF)
4754     check_array_ref (t, location, false /*ignore_off_by_one*/);
4755
4756   if (TREE_CODE (t) == INDIRECT_REF
4757       || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
4758     search_for_addr_array (TREE_OPERAND (t, 0), location);
4759   else if (TREE_CODE (t) == CALL_EXPR)
4760     {
4761       tree arg;
4762       call_expr_arg_iterator iter;
4763
4764       FOR_EACH_CALL_EXPR_ARG (arg, iter, t)
4765         search_for_addr_array (arg, location);
4766     }
4767
4768   if (TREE_CODE (t) == ADDR_EXPR)
4769     *walk_subtree = FALSE;
4770
4771   return NULL_TREE;
4772 }
4773
4774 /* Walk over all statements of all reachable BBs and call check_array_bounds
4775    on them.  */
4776
4777 static void
4778 check_all_array_refs (void)
4779 {
4780   basic_block bb;
4781   block_stmt_iterator si;
4782
4783   FOR_EACH_BB (bb)
4784     {
4785       /* Skip bb's that are clearly unreachable.  */
4786       if (single_pred_p (bb))
4787       {
4788         basic_block pred_bb = EDGE_PRED (bb, 0)->src;
4789         tree ls = NULL_TREE;
4790
4791         if (!bsi_end_p (bsi_last (pred_bb)))
4792           ls = bsi_stmt (bsi_last (pred_bb));
4793
4794         if (ls && TREE_CODE (ls) == COND_EXPR
4795             && ((COND_EXPR_COND (ls) == boolean_false_node
4796                  && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
4797                 || (COND_EXPR_COND (ls) == boolean_true_node
4798                     && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
4799           continue;
4800       }
4801       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4802         walk_tree (bsi_stmt_ptr (si), check_array_bounds,
4803                    bsi_stmt (si), NULL);
4804     }
4805 }
4806
4807 /* Convert range assertion expressions into the implied copies and
4808    copy propagate away the copies.  Doing the trivial copy propagation
4809    here avoids the need to run the full copy propagation pass after
4810    VRP.
4811
4812    FIXME, this will eventually lead to copy propagation removing the
4813    names that had useful range information attached to them.  For
4814    instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
4815    then N_i will have the range [3, +INF].
4816
4817    However, by converting the assertion into the implied copy
4818    operation N_i = N_j, we will then copy-propagate N_j into the uses
4819    of N_i and lose the range information.  We may want to hold on to
4820    ASSERT_EXPRs a little while longer as the ranges could be used in
4821    things like jump threading.
4822
4823    The problem with keeping ASSERT_EXPRs around is that passes after
4824    VRP need to handle them appropriately.
4825
4826    Another approach would be to make the range information a first
4827    class property of the SSA_NAME so that it can be queried from
4828    any pass.  This is made somewhat more complex by the need for
4829    multiple ranges to be associated with one SSA_NAME.  */
4830
4831 static void
4832 remove_range_assertions (void)
4833 {
4834   basic_block bb;
4835   block_stmt_iterator si;
4836
4837   /* Note that the BSI iterator bump happens at the bottom of the
4838      loop and no bump is necessary if we're removing the statement
4839      referenced by the current BSI.  */
4840   FOR_EACH_BB (bb)
4841     for (si = bsi_start (bb); !bsi_end_p (si);)
4842       {
4843         tree stmt = bsi_stmt (si);
4844         tree use_stmt;
4845
4846         if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
4847             && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
4848           {
4849             tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), var;
4850             tree cond = fold (ASSERT_EXPR_COND (rhs));
4851             use_operand_p use_p;
4852             imm_use_iterator iter;
4853
4854             gcc_assert (cond != boolean_false_node);
4855
4856             /* Propagate the RHS into every use of the LHS.  */
4857             var = ASSERT_EXPR_VAR (rhs);
4858             FOR_EACH_IMM_USE_STMT (use_stmt, iter,
4859                                    GIMPLE_STMT_OPERAND (stmt, 0))
4860               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
4861                 {
4862                   SET_USE (use_p, var);
4863                   gcc_assert (TREE_CODE (var) == SSA_NAME);
4864                 }
4865
4866             /* And finally, remove the copy, it is not needed.  */
4867             bsi_remove (&si, true);
4868             release_defs (stmt);
4869           }
4870         else
4871           bsi_next (&si);
4872       }
4873
4874   sbitmap_free (blocks_visited);
4875 }
4876
4877
4878 /* Return true if STMT is interesting for VRP.  */
4879
4880 static bool
4881 stmt_interesting_for_vrp (tree stmt)
4882 {
4883   if (TREE_CODE (stmt) == PHI_NODE
4884       && is_gimple_reg (PHI_RESULT (stmt))
4885       && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
4886           || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
4887     return true;
4888   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4889     {
4890       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
4891       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
4892
4893       /* In general, assignments with virtual operands are not useful
4894          for deriving ranges, with the obvious exception of calls to
4895          builtin functions.  */
4896       if (TREE_CODE (lhs) == SSA_NAME
4897           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4898               || POINTER_TYPE_P (TREE_TYPE (lhs)))
4899           && ((TREE_CODE (rhs) == CALL_EXPR
4900                && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
4901                && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
4902                && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
4903               || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
4904         return true;
4905     }
4906   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
4907     return true;
4908
4909   return false;
4910 }
4911
4912
4913 /* Initialize local data structures for VRP.  */
4914
4915 static void
4916 vrp_initialize (void)
4917 {
4918   basic_block bb;
4919
4920   vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
4921   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
4922
4923   FOR_EACH_BB (bb)
4924     {
4925       block_stmt_iterator si;
4926       tree phi;
4927
4928       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4929         {
4930           if (!stmt_interesting_for_vrp (phi))
4931             {
4932               tree lhs = PHI_RESULT (phi);
4933               set_value_range_to_varying (get_value_range (lhs));
4934               DONT_SIMULATE_AGAIN (phi) = true;
4935             }
4936           else
4937             DONT_SIMULATE_AGAIN (phi) = false;
4938         }
4939
4940       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4941         {
4942           tree stmt = bsi_stmt (si);
4943
4944           if (!stmt_interesting_for_vrp (stmt))
4945             {
4946               ssa_op_iter i;
4947               tree def;
4948               FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
4949                 set_value_range_to_varying (get_value_range (def));
4950               DONT_SIMULATE_AGAIN (stmt) = true;
4951             }
4952           else
4953             {
4954               DONT_SIMULATE_AGAIN (stmt) = false;
4955             }
4956         }
4957     }
4958 }
4959
4960
4961 /* Visit assignment STMT.  If it produces an interesting range, record
4962    the SSA name in *OUTPUT_P.  */
4963
4964 static enum ssa_prop_result
4965 vrp_visit_assignment (tree stmt, tree *output_p)
4966 {
4967   tree lhs, rhs, def;
4968   ssa_op_iter iter;
4969
4970   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
4971   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
4972
4973   /* We only keep track of ranges in integral and pointer types.  */
4974   if (TREE_CODE (lhs) == SSA_NAME
4975       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4976            /* It is valid to have NULL MIN/MAX values on a type.  See
4977               build_range_type.  */
4978            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
4979            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
4980           || POINTER_TYPE_P (TREE_TYPE (lhs))))
4981     {
4982       struct loop *l;
4983       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
4984
4985       extract_range_from_expr (&new_vr, rhs);
4986
4987       /* If STMT is inside a loop, we may be able to know something
4988          else about the range of LHS by examining scalar evolution
4989          information.  */
4990       if (current_loops && (l = loop_containing_stmt (stmt)))
4991         adjust_range_with_scev (&new_vr, l, stmt, lhs);
4992
4993       if (update_value_range (lhs, &new_vr))
4994         {
4995           *output_p = lhs;
4996
4997           if (dump_file && (dump_flags & TDF_DETAILS))
4998             {
4999               fprintf (dump_file, "Found new range for ");
5000               print_generic_expr (dump_file, lhs, 0);
5001               fprintf (dump_file, ": ");
5002               dump_value_range (dump_file, &new_vr);
5003               fprintf (dump_file, "\n\n");
5004             }
5005
5006           if (new_vr.type == VR_VARYING)
5007             return SSA_PROP_VARYING;
5008
5009           return SSA_PROP_INTERESTING;
5010         }
5011
5012       return SSA_PROP_NOT_INTERESTING;
5013     }
5014
5015   /* Every other statement produces no useful ranges.  */
5016   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
5017     set_value_range_to_varying (get_value_range (def));
5018
5019   return SSA_PROP_VARYING;
5020 }
5021
5022 /* Helper that gets the value range of the SSA_NAME with version I
5023    or a symbolic range containing the SSA_NAME only if the value range
5024    is varying or undefined.  */
5025
5026 static inline value_range_t
5027 get_vr_for_comparison (int i)
5028 {
5029   value_range_t vr = *(vr_value[i]);
5030
5031   /* If name N_i does not have a valid range, use N_i as its own
5032      range.  This allows us to compare against names that may
5033      have N_i in their ranges.  */
5034   if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
5035     {
5036       vr.type = VR_RANGE;
5037       vr.min = ssa_name (i);
5038       vr.max = ssa_name (i);
5039     }
5040
5041   return vr;
5042 }
5043
5044 /* Compare all the value ranges for names equivalent to VAR with VAL
5045    using comparison code COMP.  Return the same value returned by
5046    compare_range_with_value, including the setting of
5047    *STRICT_OVERFLOW_P.  */
5048
5049 static tree
5050 compare_name_with_value (enum tree_code comp, tree var, tree val,
5051                          bool *strict_overflow_p)
5052 {
5053   bitmap_iterator bi;
5054   unsigned i;
5055   bitmap e;
5056   tree retval, t;
5057   int used_strict_overflow;
5058   bool sop;
5059   value_range_t equiv_vr;
5060
5061   /* Get the set of equivalences for VAR.  */
5062   e = get_value_range (var)->equiv;
5063
5064   /* Start at -1.  Set it to 0 if we do a comparison without relying
5065      on overflow, or 1 if all comparisons rely on overflow.  */
5066   used_strict_overflow = -1;
5067
5068   /* Compare vars' value range with val.  */
5069   equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
5070   sop = false;
5071   retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
5072   if (retval)
5073     used_strict_overflow = sop ? 1 : 0;
5074
5075   /* If the equiv set is empty we have done all work we need to do.  */
5076   if (e == NULL)
5077     {
5078       if (retval
5079           && used_strict_overflow > 0)
5080         *strict_overflow_p = true;
5081       return retval;
5082     }
5083
5084   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
5085     {
5086       equiv_vr = get_vr_for_comparison (i);
5087       sop = false;
5088       t = compare_range_with_value (comp, &equiv_vr, val, &sop);
5089       if (t)
5090         {
5091           /* If we get different answers from different members
5092              of the equivalence set this check must be in a dead
5093              code region.  Folding it to a trap representation
5094              would be correct here.  For now just return don't-know.  */
5095           if (retval != NULL
5096               && t != retval)
5097             {
5098               retval = NULL_TREE;
5099               break;
5100             }
5101           retval = t;
5102
5103           if (!sop)
5104             used_strict_overflow = 0;
5105           else if (used_strict_overflow < 0)
5106             used_strict_overflow = 1;
5107         }
5108     }
5109
5110   if (retval
5111       && used_strict_overflow > 0)
5112     *strict_overflow_p = true;
5113
5114   return retval;
5115 }
5116
5117
5118 /* Given a comparison code COMP and names N1 and N2, compare all the
5119    ranges equivalent to N1 against all the ranges equivalent to N2
5120    to determine the value of N1 COMP N2.  Return the same value
5121    returned by compare_ranges.  Set *STRICT_OVERFLOW_P to indicate
5122    whether we relied on an overflow infinity in the comparison.  */
5123
5124
5125 static tree
5126 compare_names (enum tree_code comp, tree n1, tree n2,
5127                bool *strict_overflow_p)
5128 {
5129   tree t, retval;
5130   bitmap e1, e2;
5131   bitmap_iterator bi1, bi2;
5132   unsigned i1, i2;
5133   int used_strict_overflow;
5134   static bitmap_obstack *s_obstack = NULL;
5135   static bitmap s_e1 = NULL, s_e2 = NULL;
5136
5137   /* Compare the ranges of every name equivalent to N1 against the
5138      ranges of every name equivalent to N2.  */
5139   e1 = get_value_range (n1)->equiv;
5140   e2 = get_value_range (n2)->equiv;
5141
5142   /* Use the fake bitmaps if e1 or e2 are not available.  */
5143   if (s_obstack == NULL)
5144     {
5145       s_obstack = XNEW (bitmap_obstack);
5146       bitmap_obstack_initialize (s_obstack);
5147       s_e1 = BITMAP_ALLOC (s_obstack);
5148       s_e2 = BITMAP_ALLOC (s_obstack);
5149     }
5150   if (e1 == NULL)
5151     e1 = s_e1;
5152   if (e2 == NULL)
5153     e2 = s_e2;
5154
5155   /* Add N1 and N2 to their own set of equivalences to avoid
5156      duplicating the body of the loop just to check N1 and N2
5157      ranges.  */
5158   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
5159   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
5160
5161   /* If the equivalence sets have a common intersection, then the two
5162      names can be compared without checking their ranges.  */
5163   if (bitmap_intersect_p (e1, e2))
5164     {
5165       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5166       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5167
5168       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
5169              ? boolean_true_node
5170              : boolean_false_node;
5171     }
5172
5173   /* Start at -1.  Set it to 0 if we do a comparison without relying
5174      on overflow, or 1 if all comparisons rely on overflow.  */
5175   used_strict_overflow = -1;
5176
5177   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
5178      N2 to their own set of equivalences to avoid duplicating the body
5179      of the loop just to check N1 and N2 ranges.  */
5180   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
5181     {
5182       value_range_t vr1 = get_vr_for_comparison (i1);
5183
5184       t = retval = NULL_TREE;
5185       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
5186         {
5187           bool sop = false;
5188
5189           value_range_t vr2 = get_vr_for_comparison (i2);
5190
5191           t = compare_ranges (comp, &vr1, &vr2, &sop);
5192           if (t)
5193             {
5194               /* If we get different answers from different members
5195                  of the equivalence set this check must be in a dead
5196                  code region.  Folding it to a trap representation
5197                  would be correct here.  For now just return don't-know.  */
5198               if (retval != NULL
5199                   && t != retval)
5200                 {
5201                   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5202                   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5203                   return NULL_TREE;
5204                 }
5205               retval = t;
5206
5207               if (!sop)
5208                 used_strict_overflow = 0;
5209               else if (used_strict_overflow < 0)
5210                 used_strict_overflow = 1;
5211             }
5212         }
5213
5214       if (retval)
5215         {
5216           bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5217           bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5218           if (used_strict_overflow > 0)
5219             *strict_overflow_p = true;
5220           return retval;
5221         }
5222     }
5223
5224   /* None of the equivalent ranges are useful in computing this
5225      comparison.  */
5226   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5227   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5228   return NULL_TREE;
5229 }
5230
5231 /* Helper function for vrp_evaluate_conditional_warnv. */
5232
5233 static tree
5234 vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
5235                                          tree op1, bool use_equiv_p,
5236                                          bool *strict_overflow_p)
5237 {
5238   /* We only deal with integral and pointer types.  */
5239   if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
5240       && !POINTER_TYPE_P (TREE_TYPE (op0)))
5241     return NULL_TREE;
5242
5243   if (use_equiv_p)
5244     {
5245       if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
5246         return compare_names (code, op0, op1,
5247                               strict_overflow_p);
5248       else if (TREE_CODE (op0) == SSA_NAME)
5249         return compare_name_with_value (code, op0, op1,
5250                                         strict_overflow_p);
5251       else if (TREE_CODE (op1) == SSA_NAME)
5252         return (compare_name_with_value
5253                 (swap_tree_comparison (code), op1, op0,
5254                  strict_overflow_p));
5255     }
5256   else
5257     {
5258       value_range_t *vr0, *vr1;
5259
5260       vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
5261       vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
5262
5263       if (vr0 && vr1)
5264         return compare_ranges (code, vr0, vr1,
5265                                strict_overflow_p);
5266       else if (vr0 && vr1 == NULL)
5267         return compare_range_with_value (code, vr0, op1,
5268                                          strict_overflow_p);
5269       else if (vr0 == NULL && vr1)
5270         return (compare_range_with_value
5271                 (swap_tree_comparison (code), vr1, op0,
5272                  strict_overflow_p));
5273     }
5274   return NULL_TREE;
5275 }
5276
5277 /* Given a conditional predicate COND, try to determine if COND yields
5278    true or false based on the value ranges of its operands.  Return
5279    BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
5280    BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
5281    NULL if the conditional cannot be evaluated at compile time.
5282
5283    If USE_EQUIV_P is true, the ranges of all the names equivalent with
5284    the operands in COND are used when trying to compute its value.
5285    This is only used during final substitution.  During propagation,
5286    we only check the range of each variable and not its equivalents.
5287
5288    Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow
5289    infinity to produce the result.  */
5290
5291 static tree
5292 vrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p,
5293                                 bool *strict_overflow_p)
5294 {
5295   gcc_assert (TREE_CODE (cond) == SSA_NAME
5296               || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
5297
5298   if (TREE_CODE (cond) == SSA_NAME)
5299     {
5300       value_range_t *vr;
5301       tree retval;
5302
5303       if (use_equiv_p)
5304         retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node,
5305                                           strict_overflow_p);
5306       else
5307         {
5308           value_range_t *vr = get_value_range (cond);
5309           retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node,
5310                                              strict_overflow_p);
5311         }
5312
5313       /* If COND has a known boolean range, return it.  */
5314       if (retval)
5315         return retval;
5316
5317       /* Otherwise, if COND has a symbolic range of exactly one value,
5318          return it.  */
5319       vr = get_value_range (cond);
5320       if (vr->type == VR_RANGE && vr->min == vr->max)
5321         return vr->min;
5322     }
5323   else
5324     return vrp_evaluate_conditional_warnv_with_ops (TREE_CODE (cond),
5325                                                     TREE_OPERAND (cond, 0),
5326                                                     TREE_OPERAND (cond, 1),
5327                                                     use_equiv_p,
5328                                                     strict_overflow_p);
5329
5330   /* Anything else cannot be computed statically.  */
5331   return NULL_TREE;
5332 }
5333
5334 /* Given COND within STMT, try to simplify it based on value range
5335    information.  Return NULL if the conditional can not be evaluated.
5336    The ranges of all the names equivalent with the operands in COND
5337    will be used when trying to compute the value.  If the result is
5338    based on undefined signed overflow, issue a warning if
5339    appropriate.  */
5340
5341 tree
5342 vrp_evaluate_conditional (tree cond, tree stmt)
5343 {
5344   bool sop;
5345   tree ret;
5346
5347   sop = false;
5348   ret = vrp_evaluate_conditional_warnv (cond, true, &sop);
5349
5350   if (ret && sop)
5351     {
5352       enum warn_strict_overflow_code wc;
5353       const char* warnmsg;
5354
5355       if (is_gimple_min_invariant (ret))
5356         {
5357           wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
5358           warnmsg = G_("assuming signed overflow does not occur when "
5359                        "simplifying conditional to constant");
5360         }
5361       else
5362         {
5363           wc = WARN_STRICT_OVERFLOW_COMPARISON;
5364           warnmsg = G_("assuming signed overflow does not occur when "
5365                        "simplifying conditional");
5366         }
5367
5368       if (issue_strict_overflow_warning (wc))
5369         {
5370           location_t locus;
5371
5372           if (!EXPR_HAS_LOCATION (stmt))
5373             locus = input_location;
5374           else
5375             locus = EXPR_LOCATION (stmt);
5376           warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg);
5377         }
5378     }
5379
5380   if (warn_type_limits
5381       && ret
5382       && TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
5383       && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
5384     {
5385       /* If the comparison is being folded and the operand on the LHS
5386          is being compared against a constant value that is outside of
5387          the natural range of OP0's type, then the predicate will
5388          always fold regardless of the value of OP0.  If -Wtype-limits
5389          was specified, emit a warning.  */
5390       const char *warnmsg = NULL;
5391       tree op0 = TREE_OPERAND (cond, 0);
5392       tree op1 = TREE_OPERAND (cond, 1);
5393       tree type = TREE_TYPE (op0);
5394       value_range_t *vr0 = get_value_range (op0);
5395
5396       if (vr0->type != VR_VARYING
5397           && INTEGRAL_TYPE_P (type)
5398           && vrp_val_is_min (vr0->min)
5399           && vrp_val_is_max (vr0->max)
5400           && is_gimple_min_invariant (op1))
5401         {
5402           if (integer_zerop (ret))
5403             warnmsg = G_("comparison always false due to limited range of "
5404                          "data type");
5405           else
5406             warnmsg = G_("comparison always true due to limited range of "
5407                          "data type");
5408         }
5409
5410       if (warnmsg)
5411         {
5412           location_t locus;
5413
5414           if (!EXPR_HAS_LOCATION (stmt))
5415             locus = input_location;
5416           else
5417             locus = EXPR_LOCATION (stmt);
5418
5419           warning (OPT_Wtype_limits, "%H%s", &locus, warnmsg);
5420         }
5421     }
5422
5423   return ret;
5424 }
5425
5426
5427 /* Visit conditional statement STMT.  If we can determine which edge
5428    will be taken out of STMT's basic block, record it in
5429    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
5430    SSA_PROP_VARYING.  */
5431
5432 static enum ssa_prop_result
5433 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
5434 {
5435   tree cond, val;
5436   bool sop;
5437
5438   *taken_edge_p = NULL;
5439   cond = COND_EXPR_COND (stmt);
5440
5441   if (dump_file && (dump_flags & TDF_DETAILS))
5442     {
5443       tree use;
5444       ssa_op_iter i;
5445
5446       fprintf (dump_file, "\nVisiting conditional with predicate: ");
5447       print_generic_expr (dump_file, cond, 0);
5448       fprintf (dump_file, "\nWith known ranges\n");
5449
5450       FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
5451         {
5452           fprintf (dump_file, "\t");
5453           print_generic_expr (dump_file, use, 0);
5454           fprintf (dump_file, ": ");
5455           dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
5456         }
5457
5458       fprintf (dump_file, "\n");
5459     }
5460
5461   /* Compute the value of the predicate COND by checking the known
5462      ranges of each of its operands.
5463
5464      Note that we cannot evaluate all the equivalent ranges here
5465      because those ranges may not yet be final and with the current
5466      propagation strategy, we cannot determine when the value ranges
5467      of the names in the equivalence set have changed.
5468
5469      For instance, given the following code fragment
5470
5471         i_5 = PHI <8, i_13>
5472         ...
5473         i_14 = ASSERT_EXPR <i_5, i_5 != 0>
5474         if (i_14 == 1)
5475           ...
5476
5477      Assume that on the first visit to i_14, i_5 has the temporary
5478      range [8, 8] because the second argument to the PHI function is
5479      not yet executable.  We derive the range ~[0, 0] for i_14 and the
5480      equivalence set { i_5 }.  So, when we visit 'if (i_14 == 1)' for
5481      the first time, since i_14 is equivalent to the range [8, 8], we
5482      determine that the predicate is always false.
5483
5484      On the next round of propagation, i_13 is determined to be
5485      VARYING, which causes i_5 to drop down to VARYING.  So, another
5486      visit to i_14 is scheduled.  In this second visit, we compute the
5487      exact same range and equivalence set for i_14, namely ~[0, 0] and
5488      { i_5 }.  But we did not have the previous range for i_5
5489      registered, so vrp_visit_assignment thinks that the range for
5490      i_14 has not changed.  Therefore, the predicate 'if (i_14 == 1)'
5491      is not visited again, which stops propagation from visiting
5492      statements in the THEN clause of that if().
5493
5494      To properly fix this we would need to keep the previous range
5495      value for the names in the equivalence set.  This way we would've
5496      discovered that from one visit to the other i_5 changed from
5497      range [8, 8] to VR_VARYING.
5498
5499      However, fixing this apparent limitation may not be worth the
5500      additional checking.  Testing on several code bases (GCC, DLV,
5501      MICO, TRAMP3D and SPEC2000) showed that doing this results in
5502      4 more predicates folded in SPEC.  */
5503   sop = false;
5504   val = vrp_evaluate_conditional_warnv (cond, false, &sop);
5505   if (val)
5506     {
5507       if (!sop)
5508         *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
5509       else
5510         {
5511           if (dump_file && (dump_flags & TDF_DETAILS))
5512             fprintf (dump_file,
5513                      "\nIgnoring predicate evaluation because "
5514                      "it assumes that signed overflow is undefined");
5515           val = NULL_TREE;
5516         }
5517     }
5518
5519   if (dump_file && (dump_flags & TDF_DETAILS))
5520     {
5521       fprintf (dump_file, "\nPredicate evaluates to: ");
5522       if (val == NULL_TREE)
5523         fprintf (dump_file, "DON'T KNOW\n");
5524       else
5525         print_generic_stmt (dump_file, val, 0);
5526     }
5527
5528   return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
5529 }
5530
5531
5532 /* Searches the case label vector VEC for the index *IDX the CASE_LABEL
5533    includes the value VAL.  The search starts at index START_IDX and
5534    true is returned if *IDX corresponds to such an index.  False is
5535    returned in case VAL hits the default case label and *IDX in this
5536    case is the next higher or the next lower case label index.  */
5537
5538 static bool
5539 find_case_label_index (tree vec, size_t start_idx, tree val, size_t *idx)
5540 {
5541   size_t n = TREE_VEC_LENGTH (vec);
5542   size_t low, high, i = start_idx;
5543
5544   /* Find case label for minimum of the value range or the next one.  */
5545   for (low = start_idx - 1, high = n - 1; high - low > 1; )
5546     {
5547       tree t;
5548       int cmp;
5549       i = (high + low) / 2;
5550       t = TREE_VEC_ELT (vec, i);
5551
5552       /* Cache the result of comparing CASE_LOW and val.  */
5553       cmp = tree_int_cst_compare (CASE_LOW (t), val);
5554
5555       if (cmp > 0)
5556         high = i;
5557       else
5558         low = i;
5559
5560       if (CASE_HIGH (t) == NULL)
5561         {
5562           /* A singe-valued case label.  */
5563           if (cmp == 0)
5564             {
5565               *idx = i;
5566               return true;
5567             }
5568         }
5569       else
5570         {
5571           /* A case range.  We can only handle integer ranges.  */
5572           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
5573             {
5574               *idx = i;
5575               return true;
5576             }
5577         }
5578     }
5579
5580   *idx = i;
5581   return false;
5582 }
5583
5584 /* Visit switch statement STMT.  If we can determine which edge
5585    will be taken out of STMT's basic block, record it in
5586    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
5587    SSA_PROP_VARYING.  */
5588
5589 static enum ssa_prop_result
5590 vrp_visit_switch_stmt (tree stmt, edge *taken_edge_p)
5591 {
5592   tree op, val;
5593   value_range_t *vr;
5594   size_t i = 0, j = 0, n;
5595   tree vec;
5596   bool min_take_default, max_take_default;
5597
5598   *taken_edge_p = NULL;
5599   op = TREE_OPERAND (stmt, 0);
5600   if (TREE_CODE (op) != SSA_NAME)
5601     return SSA_PROP_VARYING;
5602
5603   vr = get_value_range (op);
5604   if (dump_file && (dump_flags & TDF_DETAILS))
5605     {
5606       fprintf (dump_file, "\nVisiting switch expression with operand ");
5607       print_generic_expr (dump_file, op, 0);
5608       fprintf (dump_file, " with known range ");
5609       dump_value_range (dump_file, vr);
5610       fprintf (dump_file, "\n");
5611     }
5612
5613   if (vr->type != VR_RANGE
5614       || symbolic_range_p (vr))
5615     return SSA_PROP_VARYING;
5616
5617   /* Find the single edge that is taken from the switch expression.  */
5618   vec = SWITCH_LABELS (stmt);
5619   n = TREE_VEC_LENGTH (vec);
5620
5621   /* Find case label for minimum of the value range or the next one.  */
5622   min_take_default = !find_case_label_index (vec, 0, vr->min, &i);
5623
5624   /* Find case label for maximum of the value range or the previous one.  */
5625   max_take_default = !find_case_label_index (vec, i, vr->max, &j);
5626
5627   /* Check if we reach the default label only.  */
5628   if (j < i)
5629     val = TREE_VEC_ELT (vec, n - 1);
5630   /* Check if we reach exactly one label and not the default label.  */
5631   else if (i == j
5632            && !min_take_default
5633            && !max_take_default)
5634     val = TREE_VEC_ELT (vec, i);
5635   else
5636     {
5637       /* Check if labels with index i to j are all reaching the same label.
5638          If we don't hit a single case label only, the default case also has
5639          to branch to the same label.  */
5640       val = TREE_VEC_ELT (vec, i);
5641       if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
5642         {
5643           if (dump_file && (dump_flags & TDF_DETAILS))
5644             fprintf (dump_file, "  not a single destination for this "
5645                      "range\n");
5646           return SSA_PROP_VARYING;
5647         }
5648       for (++i; i <= j; ++i)
5649         {
5650           if (CASE_LABEL (TREE_VEC_ELT (vec, i)) != CASE_LABEL (val))
5651             {
5652               if (dump_file && (dump_flags & TDF_DETAILS))
5653                 fprintf (dump_file, "  not a single destination for this "
5654                          "range\n");
5655               return SSA_PROP_VARYING;
5656             }
5657         }
5658     }
5659
5660   *taken_edge_p = find_edge (bb_for_stmt (stmt),
5661                              label_to_block (CASE_LABEL (val)));
5662
5663   if (dump_file && (dump_flags & TDF_DETAILS))
5664     {
5665       fprintf (dump_file, "  will take edge to ");
5666       print_generic_stmt (dump_file, CASE_LABEL (val), 0);
5667     }
5668
5669   return SSA_PROP_INTERESTING;
5670 }
5671
5672
5673 /* Evaluate statement STMT.  If the statement produces a useful range,
5674    return SSA_PROP_INTERESTING and record the SSA name with the
5675    interesting range into *OUTPUT_P.
5676
5677    If STMT is a conditional branch and we can determine its truth
5678    value, the taken edge is recorded in *TAKEN_EDGE_P.
5679
5680    If STMT produces a varying value, return SSA_PROP_VARYING.  */
5681
5682 static enum ssa_prop_result
5683 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
5684 {
5685   tree def;
5686   ssa_op_iter iter;
5687   stmt_ann_t ann;
5688
5689   if (dump_file && (dump_flags & TDF_DETAILS))
5690     {
5691       fprintf (dump_file, "\nVisiting statement:\n");
5692       print_generic_stmt (dump_file, stmt, dump_flags);
5693       fprintf (dump_file, "\n");
5694     }
5695
5696   ann = stmt_ann (stmt);
5697   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
5698     {
5699       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
5700
5701       /* In general, assignments with virtual operands are not useful
5702          for deriving ranges, with the obvious exception of calls to
5703          builtin functions.  */
5704       if ((TREE_CODE (rhs) == CALL_EXPR
5705            && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
5706            && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
5707            && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
5708           || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
5709         return vrp_visit_assignment (stmt, output_p);
5710     }
5711   else if (TREE_CODE (stmt) == COND_EXPR)
5712     return vrp_visit_cond_stmt (stmt, taken_edge_p);
5713   else if (TREE_CODE (stmt) == SWITCH_EXPR)
5714     return vrp_visit_switch_stmt (stmt, taken_edge_p);
5715
5716   /* All other statements produce nothing of interest for VRP, so mark
5717      their outputs varying and prevent further simulation.  */
5718   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
5719     set_value_range_to_varying (get_value_range (def));
5720
5721   return SSA_PROP_VARYING;
5722 }
5723
5724
5725 /* Meet operation for value ranges.  Given two value ranges VR0 and
5726    VR1, store in VR0 a range that contains both VR0 and VR1.  This
5727    may not be the smallest possible such range.  */
5728
5729 static void
5730 vrp_meet (value_range_t *vr0, value_range_t *vr1)
5731 {
5732   if (vr0->type == VR_UNDEFINED)
5733     {
5734       copy_value_range (vr0, vr1);
5735       return;
5736     }
5737
5738   if (vr1->type == VR_UNDEFINED)
5739     {
5740       /* Nothing to do.  VR0 already has the resulting range.  */
5741       return;
5742     }
5743
5744   if (vr0->type == VR_VARYING)
5745     {
5746       /* Nothing to do.  VR0 already has the resulting range.  */
5747       return;
5748     }
5749
5750   if (vr1->type == VR_VARYING)
5751     {
5752       set_value_range_to_varying (vr0);
5753       return;
5754     }
5755
5756   if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
5757     {
5758       int cmp;
5759       tree min, max;
5760
5761       /* Compute the convex hull of the ranges.  The lower limit of
5762          the new range is the minimum of the two ranges.  If they
5763          cannot be compared, then give up.  */
5764       cmp = compare_values (vr0->min, vr1->min);
5765       if (cmp == 0 || cmp == 1)
5766         min = vr1->min;
5767       else if (cmp == -1)
5768         min = vr0->min;
5769       else
5770         goto give_up;
5771
5772       /* Similarly, the upper limit of the new range is the maximum
5773          of the two ranges.  If they cannot be compared, then
5774          give up.  */
5775       cmp = compare_values (vr0->max, vr1->max);
5776       if (cmp == 0 || cmp == -1)
5777         max = vr1->max;
5778       else if (cmp == 1)
5779         max = vr0->max;
5780       else
5781         goto give_up;
5782
5783       /* Check for useless ranges.  */
5784       if (INTEGRAL_TYPE_P (TREE_TYPE (min))
5785           && ((vrp_val_is_min (min) || is_overflow_infinity (min))
5786               && (vrp_val_is_max (max) || is_overflow_infinity (max))))
5787         goto give_up;
5788
5789       /* The resulting set of equivalences is the intersection of
5790          the two sets.  */
5791       if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5792         bitmap_and_into (vr0->equiv, vr1->equiv);
5793       else if (vr0->equiv && !vr1->equiv)
5794         bitmap_clear (vr0->equiv);
5795
5796       set_value_range (vr0, vr0->type, min, max, vr0->equiv);
5797     }
5798   else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
5799     {
5800       /* Two anti-ranges meet only if their complements intersect.
5801          Only handle the case of identical ranges.  */
5802       if (compare_values (vr0->min, vr1->min) == 0
5803           && compare_values (vr0->max, vr1->max) == 0
5804           && compare_values (vr0->min, vr0->max) == 0)
5805         {
5806           /* The resulting set of equivalences is the intersection of
5807              the two sets.  */
5808           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5809             bitmap_and_into (vr0->equiv, vr1->equiv);
5810           else if (vr0->equiv && !vr1->equiv)
5811             bitmap_clear (vr0->equiv);
5812         }
5813       else
5814         goto give_up;
5815     }
5816   else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
5817     {
5818       /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
5819          only handle the case where the ranges have an empty intersection.
5820          The result of the meet operation is the anti-range.  */
5821       if (!symbolic_range_p (vr0)
5822           && !symbolic_range_p (vr1)
5823           && !value_ranges_intersect_p (vr0, vr1))
5824         {
5825           /* Copy most of VR1 into VR0.  Don't copy VR1's equivalence
5826              set.  We need to compute the intersection of the two
5827              equivalence sets.  */
5828           if (vr1->type == VR_ANTI_RANGE)
5829             set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
5830
5831           /* The resulting set of equivalences is the intersection of
5832              the two sets.  */
5833           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5834             bitmap_and_into (vr0->equiv, vr1->equiv);
5835           else if (vr0->equiv && !vr1->equiv)
5836             bitmap_clear (vr0->equiv);
5837         }
5838       else
5839         goto give_up;
5840     }
5841   else
5842     gcc_unreachable ();
5843
5844   return;
5845
5846 give_up:
5847   /* Failed to find an efficient meet.  Before giving up and setting
5848      the result to VARYING, see if we can at least derive a useful
5849      anti-range.  FIXME, all this nonsense about distinguishing
5850      anti-ranges from ranges is necessary because of the odd
5851      semantics of range_includes_zero_p and friends.  */
5852   if (!symbolic_range_p (vr0)
5853       && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
5854           || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
5855       && !symbolic_range_p (vr1)
5856       && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
5857           || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
5858     {
5859       set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
5860
5861       /* Since this meet operation did not result from the meeting of
5862          two equivalent names, VR0 cannot have any equivalences.  */
5863       if (vr0->equiv)
5864         bitmap_clear (vr0->equiv);
5865     }
5866   else
5867     set_value_range_to_varying (vr0);
5868 }
5869
5870
5871 /* Visit all arguments for PHI node PHI that flow through executable
5872    edges.  If a valid value range can be derived from all the incoming
5873    value ranges, set a new range for the LHS of PHI.  */
5874
5875 static enum ssa_prop_result
5876 vrp_visit_phi_node (tree phi)
5877 {
5878   int i;
5879   tree lhs = PHI_RESULT (phi);
5880   value_range_t *lhs_vr = get_value_range (lhs);
5881   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
5882   int edges, old_edges;
5883
5884   copy_value_range (&vr_result, lhs_vr);
5885
5886   if (dump_file && (dump_flags & TDF_DETAILS))
5887     {
5888       fprintf (dump_file, "\nVisiting PHI node: ");
5889       print_generic_expr (dump_file, phi, dump_flags);
5890     }
5891
5892   edges = 0;
5893   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
5894     {
5895       edge e = PHI_ARG_EDGE (phi, i);
5896
5897       if (dump_file && (dump_flags & TDF_DETAILS))
5898         {
5899           fprintf (dump_file,
5900               "\n    Argument #%d (%d -> %d %sexecutable)\n",
5901               i, e->src->index, e->dest->index,
5902               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
5903         }
5904
5905       if (e->flags & EDGE_EXECUTABLE)
5906         {
5907           tree arg = PHI_ARG_DEF (phi, i);
5908           value_range_t vr_arg;
5909
5910           ++edges;
5911
5912           if (TREE_CODE (arg) == SSA_NAME)
5913             {
5914               vr_arg = *(get_value_range (arg));
5915             }
5916           else
5917             {
5918               if (is_overflow_infinity (arg))
5919                 {
5920                   arg = copy_node (arg);
5921                   TREE_OVERFLOW (arg) = 0;
5922                 }
5923
5924               vr_arg.type = VR_RANGE;
5925               vr_arg.min = arg;
5926               vr_arg.max = arg;
5927               vr_arg.equiv = NULL;
5928             }
5929
5930           if (dump_file && (dump_flags & TDF_DETAILS))
5931             {
5932               fprintf (dump_file, "\t");
5933               print_generic_expr (dump_file, arg, dump_flags);
5934               fprintf (dump_file, "\n\tValue: ");
5935               dump_value_range (dump_file, &vr_arg);
5936               fprintf (dump_file, "\n");
5937             }
5938
5939           vrp_meet (&vr_result, &vr_arg);
5940
5941           if (vr_result.type == VR_VARYING)
5942             break;
5943         }
5944     }
5945
5946   if (vr_result.type == VR_VARYING)
5947     goto varying;
5948
5949   old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
5950   vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
5951
5952   /* To prevent infinite iterations in the algorithm, derive ranges
5953      when the new value is slightly bigger or smaller than the
5954      previous one.  We don't do this if we have seen a new executable
5955      edge; this helps us avoid an overflow infinity for conditionals
5956      which are not in a loop.  */
5957   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
5958       && edges <= old_edges)
5959     {
5960       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
5961         {
5962           int cmp_min = compare_values (lhs_vr->min, vr_result.min);
5963           int cmp_max = compare_values (lhs_vr->max, vr_result.max);
5964
5965           /* If the new minimum is smaller or larger than the previous
5966              one, go all the way to -INF.  In the first case, to avoid
5967              iterating millions of times to reach -INF, and in the
5968              other case to avoid infinite bouncing between different
5969              minimums.  */
5970           if (cmp_min > 0 || cmp_min < 0)
5971             {
5972               /* If we will end up with a (-INF, +INF) range, set it
5973                  to VARYING.  */
5974               if (vrp_val_is_max (vr_result.max))
5975                 goto varying;
5976
5977               if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
5978                   || !vrp_var_may_overflow (lhs, phi))
5979                 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
5980               else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
5981                 vr_result.min =
5982                   negative_overflow_infinity (TREE_TYPE (vr_result.min));
5983               else
5984                 goto varying;
5985             }
5986
5987           /* Similarly, if the new maximum is smaller or larger than
5988              the previous one, go all the way to +INF.  */
5989           if (cmp_max < 0 || cmp_max > 0)
5990             {
5991               /* If we will end up with a (-INF, +INF) range, set it
5992                  to VARYING.  */
5993               if (vrp_val_is_min (vr_result.min))
5994                 goto varying;
5995
5996               if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
5997                   || !vrp_var_may_overflow (lhs, phi))
5998                 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
5999               else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
6000                 vr_result.max =
6001                   positive_overflow_infinity (TREE_TYPE (vr_result.max));
6002               else
6003                 goto varying;
6004             }
6005         }
6006     }
6007
6008   /* If the new range is different than the previous value, keep
6009      iterating.  */
6010   if (update_value_range (lhs, &vr_result))
6011     return SSA_PROP_INTERESTING;
6012
6013   /* Nothing changed, don't add outgoing edges.  */
6014   return SSA_PROP_NOT_INTERESTING;
6015
6016   /* No match found.  Set the LHS to VARYING.  */
6017 varying:
6018   set_value_range_to_varying (lhs_vr);
6019   return SSA_PROP_VARYING;
6020 }
6021
6022 /* Simplify a division or modulo operator to a right shift or
6023    bitwise and if the first operand is unsigned or is greater
6024    than zero and the second operand is an exact power of two.  */
6025
6026 static void
6027 simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
6028 {
6029   tree val = NULL;
6030   tree op = TREE_OPERAND (rhs, 0);
6031   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
6032
6033   if (TYPE_UNSIGNED (TREE_TYPE (op)))
6034     {
6035       val = integer_one_node;
6036     }
6037   else
6038     {
6039       bool sop = false;
6040
6041       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
6042
6043       if (val
6044           && sop
6045           && integer_onep (val)
6046           && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
6047         {
6048           location_t locus;
6049
6050           if (!EXPR_HAS_LOCATION (stmt))
6051             locus = input_location;
6052           else
6053             locus = EXPR_LOCATION (stmt);
6054           warning (OPT_Wstrict_overflow,
6055                    ("%Hassuming signed overflow does not occur when "
6056                     "simplifying / or %% to >> or &"),
6057                    &locus);
6058         }
6059     }
6060
6061   if (val && integer_onep (val))
6062     {
6063       tree t;
6064       tree op0 = TREE_OPERAND (rhs, 0);
6065       tree op1 = TREE_OPERAND (rhs, 1);
6066
6067       if (rhs_code == TRUNC_DIV_EXPR)
6068         {
6069           t = build_int_cst (NULL_TREE, tree_log2 (op1));
6070           t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
6071         }
6072       else
6073         {
6074           t = build_int_cst (TREE_TYPE (op1), 1);
6075           t = int_const_binop (MINUS_EXPR, op1, t, 0);
6076           t = fold_convert (TREE_TYPE (op0), t);
6077           t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
6078         }
6079
6080       GIMPLE_STMT_OPERAND (stmt, 1) = t;
6081       update_stmt (stmt);
6082     }
6083 }
6084
6085 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
6086    ABS_EXPR.  If the operand is <= 0, then simplify the
6087    ABS_EXPR into a NEGATE_EXPR.  */
6088
6089 static void
6090 simplify_abs_using_ranges (tree stmt, tree rhs)
6091 {
6092   tree val = NULL;
6093   tree op = TREE_OPERAND (rhs, 0);
6094   tree type = TREE_TYPE (op);
6095   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
6096
6097   if (TYPE_UNSIGNED (type))
6098     {
6099       val = integer_zero_node;
6100     }
6101   else if (vr)
6102     {
6103       bool sop = false;
6104
6105       val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
6106       if (!val)
6107         {
6108           sop = false;
6109           val = compare_range_with_value (GE_EXPR, vr, integer_zero_node,
6110                                           &sop);
6111
6112           if (val)
6113             {
6114               if (integer_zerop (val))
6115                 val = integer_one_node;
6116               else if (integer_onep (val))
6117                 val = integer_zero_node;
6118             }
6119         }
6120
6121       if (val
6122           && (integer_onep (val) || integer_zerop (val)))
6123         {
6124           tree t;
6125
6126           if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
6127             {
6128               location_t locus;
6129
6130               if (!EXPR_HAS_LOCATION (stmt))
6131                 locus = input_location;
6132               else
6133                 locus = EXPR_LOCATION (stmt);
6134               warning (OPT_Wstrict_overflow,
6135                        ("%Hassuming signed overflow does not occur when "
6136                         "simplifying abs (X) to X or -X"),
6137                        &locus);
6138             }
6139
6140           if (integer_onep (val))
6141             t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
6142           else
6143             t = op;
6144
6145           GIMPLE_STMT_OPERAND (stmt, 1) = t;
6146           update_stmt (stmt);
6147         }
6148     }
6149 }
6150
6151 /* We are comparing trees OP0 and OP1 using COND_CODE.  OP0 has
6152    a known value range VR.
6153
6154    If there is one and only one value which will satisfy the
6155    conditional, then return that value.  Else return NULL.  */
6156
6157 static tree
6158 test_for_singularity (enum tree_code cond_code, tree op0,
6159                       tree op1, value_range_t *vr)
6160 {
6161   tree min = NULL;
6162   tree max = NULL;
6163
6164   /* Extract minimum/maximum values which satisfy the
6165      the conditional as it was written.  */
6166   if (cond_code == LE_EXPR || cond_code == LT_EXPR)
6167     {
6168       /* This should not be negative infinity; there is no overflow
6169          here.  */
6170       min = TYPE_MIN_VALUE (TREE_TYPE (op0));
6171
6172       max = op1;
6173       if (cond_code == LT_EXPR && !is_overflow_infinity (max))
6174         {
6175           tree one = build_int_cst (TREE_TYPE (op0), 1);
6176           max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
6177           if (EXPR_P (max))
6178             TREE_NO_WARNING (max) = 1;
6179         }
6180     }
6181   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
6182     {
6183       /* This should not be positive infinity; there is no overflow
6184          here.  */
6185       max = TYPE_MAX_VALUE (TREE_TYPE (op0));
6186
6187       min = op1;
6188       if (cond_code == GT_EXPR && !is_overflow_infinity (min))
6189         {
6190           tree one = build_int_cst (TREE_TYPE (op0), 1);
6191           min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
6192           if (EXPR_P (min))
6193             TREE_NO_WARNING (min) = 1;
6194         }
6195     }
6196
6197   /* Now refine the minimum and maximum values using any
6198      value range information we have for op0.  */
6199   if (min && max)
6200     {
6201       if (compare_values (vr->min, min) == -1)
6202         min = min;
6203       else
6204         min = vr->min;
6205       if (compare_values (vr->max, max) == 1)
6206         max = max;
6207       else
6208         max = vr->max;
6209
6210       /* If the new min/max values have converged to a single value,
6211          then there is only one value which can satisfy the condition,
6212          return that value.  */
6213       if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
6214         return min;
6215     }
6216   return NULL;
6217 }
6218
6219 /* Simplify a conditional using a relational operator to an equality
6220    test if the range information indicates only one value can satisfy
6221    the original conditional.  */
6222
6223 static void
6224 simplify_cond_using_ranges (tree stmt)
6225 {
6226   tree cond = COND_EXPR_COND (stmt);
6227   tree op0 = TREE_OPERAND (cond, 0);
6228   tree op1 = TREE_OPERAND (cond, 1);
6229   enum tree_code cond_code = TREE_CODE (cond);
6230
6231   if (cond_code != NE_EXPR
6232       && cond_code != EQ_EXPR
6233       && TREE_CODE (op0) == SSA_NAME
6234       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
6235       && is_gimple_min_invariant (op1))
6236     {
6237       value_range_t *vr = get_value_range (op0);
6238
6239       /* If we have range information for OP0, then we might be
6240          able to simplify this conditional. */
6241       if (vr->type == VR_RANGE)
6242         {
6243           tree new = test_for_singularity (cond_code, op0, op1, vr);
6244
6245           if (new)
6246             {
6247               if (dump_file)
6248                 {
6249                   fprintf (dump_file, "Simplified relational ");
6250                   print_generic_expr (dump_file, cond, 0);
6251                   fprintf (dump_file, " into ");
6252                 }
6253
6254               COND_EXPR_COND (stmt)
6255                 = build2 (EQ_EXPR, boolean_type_node, op0, new);
6256               update_stmt (stmt);
6257
6258               if (dump_file)
6259                 {
6260                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
6261                   fprintf (dump_file, "\n");
6262                 }
6263               return;
6264
6265             }
6266
6267           /* Try again after inverting the condition.  We only deal
6268              with integral types here, so no need to worry about
6269              issues with inverting FP comparisons.  */
6270           cond_code = invert_tree_comparison (cond_code, false);
6271           new = test_for_singularity (cond_code, op0, op1, vr);
6272
6273           if (new)
6274             {
6275               if (dump_file)
6276                 {
6277                   fprintf (dump_file, "Simplified relational ");
6278                   print_generic_expr (dump_file, cond, 0);
6279                   fprintf (dump_file, " into ");
6280                 }
6281
6282               COND_EXPR_COND (stmt)
6283                 = build2 (NE_EXPR, boolean_type_node, op0, new);
6284               update_stmt (stmt);
6285
6286               if (dump_file)
6287                 {
6288                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
6289                   fprintf (dump_file, "\n");
6290                 }
6291               return;
6292
6293             }
6294         }
6295     }
6296 }
6297
6298 /* Simplify a switch statement using the value range of the switch
6299    argument.  */
6300
6301 static void
6302 simplify_switch_using_ranges (tree stmt)
6303 {
6304   tree op = TREE_OPERAND (stmt, 0);
6305   value_range_t *vr;
6306   bool take_default;
6307   edge e;
6308   edge_iterator ei;
6309   size_t i = 0, j = 0, n, n2;
6310   tree vec, vec2;
6311   switch_update su;
6312
6313   if (TREE_CODE (op) != SSA_NAME)
6314     return;
6315
6316   vr = get_value_range (op);
6317
6318   /* We can only handle integer ranges.  */
6319   if (vr->type != VR_RANGE
6320       || symbolic_range_p (vr))
6321     return;
6322
6323   /* Find case label for min/max of the value range.  */
6324   vec = SWITCH_LABELS (stmt);
6325   n = TREE_VEC_LENGTH (vec);
6326   take_default = !find_case_label_index (vec, 0, vr->min, &i);
6327   take_default |= !find_case_label_index (vec, i, vr->max, &j);
6328
6329   /* If the case label range is continuous, we do not need to
6330      preserve the default case label.  Verify that.  */
6331   if (!take_default && j > i)
6332     {
6333       tree low, high;
6334       size_t k;
6335
6336       high = CASE_LOW (TREE_VEC_ELT (vec, i));
6337       if (CASE_HIGH (TREE_VEC_ELT (vec, i)))
6338         high = CASE_HIGH (TREE_VEC_ELT (vec, i));
6339       for (k = i + 1; k <= j; ++k)
6340         {
6341           low = CASE_LOW (TREE_VEC_ELT (vec, k));
6342           if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
6343             {
6344               take_default = true;
6345               break;
6346             }
6347           high = low;
6348           if (CASE_HIGH (TREE_VEC_ELT (vec, k)))
6349             high = CASE_HIGH (TREE_VEC_ELT (vec, k));
6350         }
6351     }
6352
6353   /* Bail out if this is just all edges taken.  */
6354   if (i == 0
6355       && j == n - 2
6356       && take_default)
6357     return;
6358
6359   /* Build a new vector of taken case labels.  */
6360   vec2 = make_tree_vec (j - i + 1 + (int)take_default);
6361   for (n2 = 0; i <= j; ++i, ++n2)
6362     TREE_VEC_ELT (vec2, n2) = TREE_VEC_ELT (vec, i);
6363
6364   /* Add the default edge, if necessary.  */
6365   if (take_default)
6366     TREE_VEC_ELT (vec2, n2++) = TREE_VEC_ELT (vec, n - 1);
6367
6368   /* Mark needed edges.  */
6369   for (i = 0; i < n2; ++i)
6370     {
6371       e = find_edge (bb_for_stmt (stmt),
6372                      label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
6373       e->aux = (void *)-1;
6374     }
6375
6376   /* Queue not needed edges for later removal.  */
6377   FOR_EACH_EDGE (e, ei, bb_for_stmt (stmt)->succs)
6378     {
6379       if (e->aux == (void *)-1)
6380         {
6381           e->aux = NULL;
6382           continue;
6383         }
6384
6385       if (dump_file && (dump_flags & TDF_DETAILS))
6386         {
6387           fprintf (dump_file, "removing unreachable case label\n");
6388         }
6389       VEC_safe_push (edge, heap, to_remove_edges, e);
6390     }
6391
6392   /* And queue an update for the stmt.  */
6393   su.stmt = stmt;
6394   su.vec = vec2;
6395   VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
6396 }
6397
6398 /* Simplify STMT using ranges if possible.  */
6399
6400 void
6401 simplify_stmt_using_ranges (tree stmt)
6402 {
6403   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
6404     {
6405       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
6406       enum tree_code rhs_code = TREE_CODE (rhs);
6407
6408       /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
6409          and BIT_AND_EXPR respectively if the first operand is greater
6410          than zero and the second operand is an exact power of two.  */
6411       if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
6412           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
6413           && integer_pow2p (TREE_OPERAND (rhs, 1)))
6414         simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
6415
6416       /* Transform ABS (X) into X or -X as appropriate.  */
6417       if (rhs_code == ABS_EXPR
6418           && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
6419           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
6420         simplify_abs_using_ranges (stmt, rhs);
6421     }
6422   else if (TREE_CODE (stmt) == COND_EXPR
6423            && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
6424     simplify_cond_using_ranges (stmt);
6425   else if (TREE_CODE (stmt) == SWITCH_EXPR)
6426     simplify_switch_using_ranges (stmt);
6427 }
6428
6429 /* Stack of dest,src equivalency pairs that need to be restored after
6430    each attempt to thread a block's incoming edge to an outgoing edge.
6431
6432    A NULL entry is used to mark the end of pairs which need to be
6433    restored.  */
6434 static VEC(tree,heap) *stack;
6435
6436 /* A trivial wrapper so that we can present the generic jump threading
6437    code with a simple API for simplifying statements.  STMT is the
6438    statement we want to simplify, WITHIN_STMT provides the location
6439    for any overflow warnings.  */
6440
6441 static tree
6442 simplify_stmt_for_jump_threading (tree stmt, tree within_stmt)
6443 {
6444   /* We only use VRP information to simplify conditionals.  This is
6445      overly conservative, but it's unclear if doing more would be
6446      worth the compile time cost.  */
6447   if (TREE_CODE (stmt) != COND_EXPR)
6448     return NULL;
6449
6450   return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt);
6451 }
6452
6453 /* Blocks which have more than one predecessor and more than
6454    one successor present jump threading opportunities.  ie,
6455    when the block is reached from a specific predecessor, we
6456    may be able to determine which of the outgoing edges will
6457    be traversed.  When this optimization applies, we are able
6458    to avoid conditionals at runtime and we may expose secondary
6459    optimization opportunities.
6460
6461    This routine is effectively a driver for the generic jump
6462    threading code.  It basically just presents the generic code
6463    with edges that may be suitable for jump threading.
6464
6465    Unlike DOM, we do not iterate VRP if jump threading was successful.
6466    While iterating may expose new opportunities for VRP, it is expected
6467    those opportunities would be very limited and the compile time cost
6468    to expose those opportunities would be significant.
6469
6470    As jump threading opportunities are discovered, they are registered
6471    for later realization.  */
6472
6473 static void
6474 identify_jump_threads (void)
6475 {
6476   basic_block bb;
6477   tree dummy;
6478   int i;
6479   edge e;
6480
6481   /* Ugh.  When substituting values earlier in this pass we can
6482      wipe the dominance information.  So rebuild the dominator
6483      information as we need it within the jump threading code.  */
6484   calculate_dominance_info (CDI_DOMINATORS);
6485
6486   /* We do not allow VRP information to be used for jump threading
6487      across a back edge in the CFG.  Otherwise it becomes too
6488      difficult to avoid eliminating loop exit tests.  Of course
6489      EDGE_DFS_BACK is not accurate at this time so we have to
6490      recompute it.  */
6491   mark_dfs_back_edges ();
6492
6493   /* Do not thread across edges we are about to remove.  Just marking
6494      them as EDGE_DFS_BACK will do.  */
6495   for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
6496     e->flags |= EDGE_DFS_BACK;
6497
6498   /* Allocate our unwinder stack to unwind any temporary equivalences
6499      that might be recorded.  */
6500   stack = VEC_alloc (tree, heap, 20);
6501
6502   /* To avoid lots of silly node creation, we create a single
6503      conditional and just modify it in-place when attempting to
6504      thread jumps.  */
6505   dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
6506   dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
6507
6508   /* Walk through all the blocks finding those which present a
6509      potential jump threading opportunity.  We could set this up
6510      as a dominator walker and record data during the walk, but
6511      I doubt it's worth the effort for the classes of jump
6512      threading opportunities we are trying to identify at this
6513      point in compilation.  */
6514   FOR_EACH_BB (bb)
6515     {
6516       tree last, cond;
6517
6518       /* If the generic jump threading code does not find this block
6519          interesting, then there is nothing to do.  */
6520       if (! potentially_threadable_block (bb))
6521         continue;
6522
6523       /* We only care about blocks ending in a COND_EXPR.  While there
6524          may be some value in handling SWITCH_EXPR here, I doubt it's
6525          terribly important.  */
6526       last = bsi_stmt (bsi_last (bb));
6527       if (TREE_CODE (last) != COND_EXPR)
6528         continue;
6529
6530       /* We're basically looking for any kind of conditional with
6531          integral type arguments.  */
6532       cond = COND_EXPR_COND (last);
6533       if ((TREE_CODE (cond) == SSA_NAME
6534            && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
6535           || (COMPARISON_CLASS_P (cond)
6536               && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
6537               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
6538               && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
6539                   || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
6540               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
6541         {
6542           edge_iterator ei;
6543
6544           /* We've got a block with multiple predecessors and multiple
6545              successors which also ends in a suitable conditional.  For
6546              each predecessor, see if we can thread it to a specific
6547              successor.  */
6548           FOR_EACH_EDGE (e, ei, bb->preds)
6549             {
6550               /* Do not thread across back edges or abnormal edges
6551                  in the CFG.  */
6552               if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
6553                 continue;
6554
6555               thread_across_edge (dummy, e, true,
6556                                   &stack,
6557                                   simplify_stmt_for_jump_threading);
6558             }
6559         }
6560     }
6561
6562   /* We do not actually update the CFG or SSA graphs at this point as
6563      ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
6564      handle ASSERT_EXPRs gracefully.  */
6565 }
6566
6567 /* We identified all the jump threading opportunities earlier, but could
6568    not transform the CFG at that time.  This routine transforms the
6569    CFG and arranges for the dominator tree to be rebuilt if necessary.
6570
6571    Note the SSA graph update will occur during the normal TODO
6572    processing by the pass manager.  */
6573 static void
6574 finalize_jump_threads (void)
6575 {
6576   thread_through_all_blocks (false);
6577   VEC_free (tree, heap, stack);
6578 }
6579
6580
6581 /* Traverse all the blocks folding conditionals with known ranges.  */
6582
6583 static void
6584 vrp_finalize (void)
6585 {
6586   size_t i;
6587   prop_value_t *single_val_range;
6588   bool do_value_subst_p;
6589
6590   if (dump_file)
6591     {
6592       fprintf (dump_file, "\nValue ranges after VRP:\n\n");
6593       dump_all_value_ranges (dump_file);
6594       fprintf (dump_file, "\n");
6595     }
6596
6597   /* We may have ended with ranges that have exactly one value.  Those
6598      values can be substituted as any other copy/const propagated
6599      value using substitute_and_fold.  */
6600   single_val_range = XCNEWVEC (prop_value_t, num_ssa_names);
6601
6602   do_value_subst_p = false;
6603   for (i = 0; i < num_ssa_names; i++)
6604     if (vr_value[i]
6605         && vr_value[i]->type == VR_RANGE
6606         && vr_value[i]->min == vr_value[i]->max)
6607       {
6608         single_val_range[i].value = vr_value[i]->min;
6609         do_value_subst_p = true;
6610       }
6611
6612   if (!do_value_subst_p)
6613     {
6614       /* We found no single-valued ranges, don't waste time trying to
6615          do single value substitution in substitute_and_fold.  */
6616       free (single_val_range);
6617       single_val_range = NULL;
6618     }
6619
6620   substitute_and_fold (single_val_range, true);
6621
6622   if (warn_array_bounds)
6623       check_all_array_refs ();
6624
6625   /* We must identify jump threading opportunities before we release
6626      the datastructures built by VRP.  */
6627   identify_jump_threads ();
6628
6629   /* Free allocated memory.  */
6630   for (i = 0; i < num_ssa_names; i++)
6631     if (vr_value[i])
6632       {
6633         BITMAP_FREE (vr_value[i]->equiv);
6634         free (vr_value[i]);
6635       }
6636
6637   free (single_val_range);
6638   free (vr_value);
6639   free (vr_phi_edge_counts);
6640
6641   /* So that we can distinguish between VRP data being available
6642      and not available.  */
6643   vr_value = NULL;
6644   vr_phi_edge_counts = NULL;
6645 }
6646
6647 /* Calculates number of iterations for all loops, to ensure that they are
6648    cached.  */
6649
6650 static void
6651 record_numbers_of_iterations (void)
6652 {
6653   loop_iterator li;
6654   struct loop *loop;
6655
6656   FOR_EACH_LOOP (li, loop, 0)
6657     {
6658       number_of_latch_executions (loop);
6659     }
6660 }
6661
6662 /* Main entry point to VRP (Value Range Propagation).  This pass is
6663    loosely based on J. R. C. Patterson, ``Accurate Static Branch
6664    Prediction by Value Range Propagation,'' in SIGPLAN Conference on
6665    Programming Language Design and Implementation, pp. 67-78, 1995.
6666    Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
6667
6668    This is essentially an SSA-CCP pass modified to deal with ranges
6669    instead of constants.
6670
6671    While propagating ranges, we may find that two or more SSA name
6672    have equivalent, though distinct ranges.  For instance,
6673
6674      1  x_9 = p_3->a;
6675      2  p_4 = ASSERT_EXPR <p_3, p_3 != 0>
6676      3  if (p_4 == q_2)
6677      4    p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
6678      5  endif
6679      6  if (q_2)
6680
6681    In the code above, pointer p_5 has range [q_2, q_2], but from the
6682    code we can also determine that p_5 cannot be NULL and, if q_2 had
6683    a non-varying range, p_5's range should also be compatible with it.
6684
6685    These equivalences are created by two expressions: ASSERT_EXPR and
6686    copy operations.  Since p_5 is an assertion on p_4, and p_4 was the
6687    result of another assertion, then we can use the fact that p_5 and
6688    p_4 are equivalent when evaluating p_5's range.
6689
6690    Together with value ranges, we also propagate these equivalences
6691    between names so that we can take advantage of information from
6692    multiple ranges when doing final replacement.  Note that this
6693    equivalency relation is transitive but not symmetric.
6694
6695    In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
6696    cannot assert that q_2 is equivalent to p_5 because q_2 may be used
6697    in contexts where that assertion does not hold (e.g., in line 6).
6698
6699    TODO, the main difference between this pass and Patterson's is that
6700    we do not propagate edge probabilities.  We only compute whether
6701    edges can be taken or not.  That is, instead of having a spectrum
6702    of jump probabilities between 0 and 1, we only deal with 0, 1 and
6703    DON'T KNOW.  In the future, it may be worthwhile to propagate
6704    probabilities to aid branch prediction.  */
6705
6706 static unsigned int
6707 execute_vrp (void)
6708 {
6709   int i;
6710   edge e;
6711   switch_update *su;
6712
6713   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
6714   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
6715   scev_initialize ();
6716
6717   insert_range_assertions ();
6718
6719   /* Compute the # of iterations for each loop before we start the VRP
6720      analysis.  The value ranges determined by VRP are used in expression
6721      simplification, that is also used by the # of iterations analysis.
6722      However, in the middle of the VRP analysis, the value ranges do not take
6723      all the possible paths in CFG into account, so they do not have to be
6724      correct, and the # of iterations analysis can obtain wrong results.
6725      This is a problem, since the results of the # of iterations analysis
6726      are cached, so these mistakes would not be corrected when the value
6727      ranges are corrected.  */
6728   record_numbers_of_iterations ();
6729
6730   to_remove_edges = VEC_alloc (edge, heap, 10);
6731   to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
6732
6733   vrp_initialize ();
6734   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
6735   vrp_finalize ();
6736
6737   /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
6738      CFG in a broken state and requires a cfg_cleanup run.  */
6739   for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
6740     remove_edge (e);
6741   /* Update SWITCH_EXPR case label vector.  */
6742   for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
6743     SWITCH_LABELS (su->stmt) = su->vec;
6744
6745   if (VEC_length (edge, to_remove_edges) > 0)
6746     free_dominance_info (CDI_DOMINATORS);
6747
6748   VEC_free (edge, heap, to_remove_edges);
6749   VEC_free (switch_update, heap, to_update_switch_stmts);
6750
6751   /* ASSERT_EXPRs must be removed before finalizing jump threads
6752      as finalizing jump threads calls the CFG cleanup code which
6753      does not properly handle ASSERT_EXPRs.  */
6754   remove_range_assertions ();
6755
6756   /* If we exposed any new variables, go ahead and put them into
6757      SSA form now, before we handle jump threading.  This simplifies
6758      interactions between rewriting of _DECL nodes into SSA form
6759      and rewriting SSA_NAME nodes into SSA form after block
6760      duplication and CFG manipulation.  */
6761   update_ssa (TODO_update_ssa);
6762
6763   finalize_jump_threads ();
6764   scev_finalize ();
6765   loop_optimizer_finalize ();
6766
6767   return 0;
6768 }
6769
6770 static bool
6771 gate_vrp (void)
6772 {
6773   return flag_tree_vrp != 0;
6774 }
6775
6776 struct gimple_opt_pass pass_vrp =
6777 {
6778  {
6779   GIMPLE_PASS,
6780   "vrp",                                /* name */
6781   gate_vrp,                             /* gate */
6782   execute_vrp,                          /* execute */
6783   NULL,                                 /* sub */
6784   NULL,                                 /* next */
6785   0,                                    /* static_pass_number */
6786   TV_TREE_VRP,                          /* tv_id */
6787   PROP_ssa | PROP_alias,                /* properties_required */
6788   0,                                    /* properties_provided */
6789   0,                                    /* properties_destroyed */
6790   0,                                    /* todo_flags_start */
6791   TODO_cleanup_cfg
6792     | TODO_ggc_collect
6793     | TODO_verify_ssa
6794     | TODO_dump_func
6795     | TODO_update_ssa                   /* todo_flags_finish */
6796  }
6797 };