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
 108 /* Return the maximum value for TYPEs base type.  */
 109
 110 static inline tree
 111 vrp_val_max (const_tree type)
 112 {
 113   if (!INTEGRAL_TYPE_P (type))
 114     return NULL_TREE;
 115
 116   /* For integer sub-types the values for the base type are relevant.  */
 117   if (TREE_TYPE (type))
 118     type = TREE_TYPE (type);
 119
 120   return TYPE_MAX_VALUE (type);
 121 }
 122
 123 /* Return the minimum value for TYPEs base type.  */
 124
 125 static inline tree
 126 vrp_val_min (const_tree type)
 127 {
 128   if (!INTEGRAL_TYPE_P (type))
 129     return NULL_TREE;
 130
 131   /* For integer sub-types the values for the base type are relevant.  */
 132   if (TREE_TYPE (type))
 133     type = TREE_TYPE (type);
 134
 135   return TYPE_MIN_VALUE (type);
 136 }
 137
 138 /* Return whether VAL is equal to the maximum value of its type.  This
 139    will be true for a positive overflow infinity.  We can't do a
 140    simple equality comparison with TYPE_MAX_VALUE because C typedefs
 141    and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
 142    to the integer constant with the same value in the type.  */
 143
 144 static inline bool
 145 vrp_val_is_max (const_tree val)
 146 {
 147   tree type_max = vrp_val_max (TREE_TYPE (val));
 148   return (val == type_max
 149           || (type_max != NULL_TREE
 150               && operand_equal_p (val, type_max, 0)));
 151 }
 152
 153 /* Return whether VAL is equal to the minimum value of its type.  This
 154    will be true for a negative overflow infinity.  */
 155
 156 static inline bool
 157 vrp_val_is_min (const_tree val)
 158 {
 159   tree type_min = vrp_val_min (TREE_TYPE (val));
 160   return (val == type_min
 161           || (type_min != NULL_TREE
 162               && operand_equal_p (val, type_min, 0)));
 163 }
 164
 165
 166 /* Return whether TYPE should use an overflow infinity distinct from
 167    TYPE_{MIN,MAX}_VALUE.  We use an overflow infinity value to
 168    represent a signed overflow during VRP computations.  An infinity
 169    is distinct from a half-range, which will go from some number to
 170    TYPE_{MIN,MAX}_VALUE.  */
 171
 172 static inline bool
 173 needs_overflow_infinity (const_tree type)
 174 {
 175   return (INTEGRAL_TYPE_P (type)
 176           && !TYPE_OVERFLOW_WRAPS (type)
 177           /* Integer sub-types never overflow as they are never
 178              operands of arithmetic operators.  */
 179           && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
 180 }
 181
 182 /* Return whether TYPE can support our overflow infinity
 183    representation: we use the TREE_OVERFLOW flag, which only exists
 184    for constants.  If TYPE doesn't support this, we don't optimize
 185    cases which would require signed overflow--we drop them to
 186    VARYING.  */
 187
 188 static inline bool
 189 supports_overflow_infinity (const_tree type)
 190 {
 191   tree min = vrp_val_min (type), max = vrp_val_max (type);
 192 #ifdef ENABLE_CHECKING
 193   gcc_assert (needs_overflow_infinity (type));
 194 #endif
 195   return (min != NULL_TREE
 196           && CONSTANT_CLASS_P (min)
 197           && max != NULL_TREE
 198           && CONSTANT_CLASS_P (max));
 199 }
 200
 201 /* VAL is the maximum or minimum value of a type.  Return a
 202    corresponding overflow infinity.  */
 203
 204 static inline tree
 205 make_overflow_infinity (tree val)
 206 {
 207 #ifdef ENABLE_CHECKING
 208   gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
 209 #endif
 210   val = copy_node (val);
 211   TREE_OVERFLOW (val) = 1;
 212   return val;
 213 }
 214
 215 /* Return a negative overflow infinity for TYPE.  */
 216
 217 static inline tree
 218 negative_overflow_infinity (tree type)
 219 {
 220 #ifdef ENABLE_CHECKING
 221   gcc_assert (supports_overflow_infinity (type));
 222 #endif
 223   return make_overflow_infinity (vrp_val_min (type));
 224 }
 225
 226 /* Return a positive overflow infinity for TYPE.  */
 227
 228 static inline tree
 229 positive_overflow_infinity (tree type)
 230 {
 231 #ifdef ENABLE_CHECKING
 232   gcc_assert (supports_overflow_infinity (type));
 233 #endif
 234   return make_overflow_infinity (vrp_val_max (type));
 235 }
 236
 237 /* Return whether VAL is a negative overflow infinity.  */
 238
 239 static inline bool
 240 is_negative_overflow_infinity (const_tree val)
 241 {
 242   return (needs_overflow_infinity (TREE_TYPE (val))
 243           && CONSTANT_CLASS_P (val)
 244           && TREE_OVERFLOW (val)
 245           && vrp_val_is_min (val));
 246 }
 247
 248 /* Return whether VAL is a positive overflow infinity.  */
 249
 250 static inline bool
 251 is_positive_overflow_infinity (const_tree val)
 252 {
 253   return (needs_overflow_infinity (TREE_TYPE (val))
 254           && CONSTANT_CLASS_P (val)
 255           && TREE_OVERFLOW (val)
 256           && vrp_val_is_max (val));
 257 }
 258
 259 /* Return whether VAL is a positive or negative overflow infinity.  */
 260
 261 static inline bool
 262 is_overflow_infinity (const_tree val)
 263 {
 264   return (needs_overflow_infinity (TREE_TYPE (val))
 265           && CONSTANT_CLASS_P (val)
 266           && TREE_OVERFLOW (val)
 267           && (vrp_val_is_min (val) || vrp_val_is_max (val)));
 268 }
 269
 270 /* If VAL is now an overflow infinity, return VAL.  Otherwise, return
 271    the same value with TREE_OVERFLOW clear.  This can be used to avoid
 272    confusing a regular value with an overflow value.  */
 273
 274 static inline tree
 275 avoid_overflow_infinity (tree val)
 276 {
 277   if (!is_overflow_infinity (val))
 278     return val;
 279
 280   if (vrp_val_is_max (val))
 281     return vrp_val_max (TREE_TYPE (val));
 282   else
 283     {
 284 #ifdef ENABLE_CHECKING
 285       gcc_assert (vrp_val_is_min (val));
 286 #endif
 287       return vrp_val_min (TREE_TYPE (val));
 288     }
 289 }
 290
 291
 292 /* Return true if ARG is marked with the nonnull attribute in the
 293    current function signature.  */
 294
 295 static bool
 296 nonnull_arg_p (const_tree arg)
 297 {
 298   tree t, attrs, fntype;
 299   unsigned HOST_WIDE_INT arg_num;
 300
 301   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
 302
 303   /* The static chain decl is always non null.  */
 304   if (arg == cfun->static_chain_decl)
 305     return true;
 306
 307   fntype = TREE_TYPE (current_function_decl);
 308   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
 309
 310   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
 311   if (attrs == NULL_TREE)
 312     return false;
 313
 314   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
 315   if (TREE_VALUE (attrs) == NULL_TREE)
 316     return true;
 317
 318   /* Get the position number for ARG in the function signature.  */
 319   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
 320        t;
 321        t = TREE_CHAIN (t), arg_num++)
 322     {
 323       if (t == arg)
 324         break;
 325     }
 326
 327   gcc_assert (t == arg);
 328
 329   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
 330   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
 331     {
 332       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
 333         return true;
 334     }
 335
 336   return false;
 337 }
 338
 339
 340 /* Set value range VR to VR_VARYING.  */
 341
 342 static inline void
 343 set_value_range_to_varying (value_range_t *vr)
 344 {
 345   vr->type = VR_VARYING;
 346   vr->min = vr->max = NULL_TREE;
 347   if (vr->equiv)
 348     bitmap_clear (vr->equiv);
 349 }
 350
 351
 352 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
 353
 354 static void
 355 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 356                  tree max, bitmap equiv)
 357 {
 358 #if defined ENABLE_CHECKING
 359   /* Check the validity of the range.  */
 360   if (t == VR_RANGE || t == VR_ANTI_RANGE)
 361     {
 362       int cmp;
 363
 364       gcc_assert (min && max);
 365
 366       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
 367         gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
 368
 369       cmp = compare_values (min, max);
 370       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
 371
 372       if (needs_overflow_infinity (TREE_TYPE (min)))
 373         gcc_assert (!is_overflow_infinity (min)
 374                     || !is_overflow_infinity (max));
 375     }
 376
 377   if (t == VR_UNDEFINED || t == VR_VARYING)
 378     gcc_assert (min == NULL_TREE && max == NULL_TREE);
 379
 380   if (t == VR_UNDEFINED || t == VR_VARYING)
 381     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
 382 #endif
 383
 384   vr->type = t;
 385   vr->min = min;
 386   vr->max = max;
 387
 388   /* Since updating the equivalence set involves deep copying the
 389      bitmaps, only do it if absolutely necessary.  */
 390   if (vr->equiv == NULL
 391       && equiv != NULL)
 392     vr->equiv = BITMAP_ALLOC (NULL);
 393
 394   if (equiv != vr->equiv)
 395     {
 396       if (equiv && !bitmap_empty_p (equiv))
 397         bitmap_copy (vr->equiv, equiv);
 398       else
 399         bitmap_clear (vr->equiv);
 400     }
 401 }
 402
 403
 404 /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
 405    This means adjusting T, MIN and MAX representing the case of a
 406    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
 407    as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
 408    In corner cases where MAX+1 or MIN-1 wraps this will fall back
 409    to varying.
 410    This routine exists to ease canonicalization in the case where we
 411    extract ranges from var + CST op limit.  */
 412
 413 static void
 414 set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
 415                                   tree min, tree max, bitmap equiv)
 416 {
 417   /* Nothing to canonicalize for symbolic or unknown or varying ranges.  */
 418   if ((t != VR_RANGE
 419        && t != VR_ANTI_RANGE)
 420       || TREE_CODE (min) != INTEGER_CST
 421       || TREE_CODE (max) != INTEGER_CST)
 422     {
 423       set_value_range (vr, t, min, max, equiv);
 424       return;
 425     }
 426
 427   /* Wrong order for min and max, to swap them and the VR type we need
 428      to adjust them.  */
 429   if (tree_int_cst_lt (max, min))
 430     {
 431       tree one = build_int_cst (TREE_TYPE (min), 1);
 432       tree tmp = int_const_binop (PLUS_EXPR, max, one, 0);
 433       max = int_const_binop (MINUS_EXPR, min, one, 0);
 434       min = tmp;
 435
 436       /* There's one corner case, if we had [C+1, C] before we now have
 437          that again.  But this represents an empty value range, so drop
 438          to varying in this case.  */
 439       if (tree_int_cst_lt (max, min))
 440         {
 441           set_value_range_to_varying (vr);
 442           return;
 443         }
 444
 445       t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
 446     }
 447
 448   /* Anti-ranges that can be represented as ranges should be so.  */
 449   if (t == VR_ANTI_RANGE)
 450     {
 451       bool is_min = vrp_val_is_min (min);
 452       bool is_max = vrp_val_is_max (max);
 453
 454       if (is_min && is_max)
 455         {
 456           /* We cannot deal with empty ranges, drop to varying.  */
 457           set_value_range_to_varying (vr);
 458           return;
 459         }
 460       else if (is_min
 461                /* As a special exception preserve non-null ranges.  */
 462                && !(TYPE_UNSIGNED (TREE_TYPE (min))
 463                     && integer_zerop (max)))
 464         {
 465           tree one = build_int_cst (TREE_TYPE (max), 1);
 466           min = int_const_binop (PLUS_EXPR, max, one, 0);
 467           max = vrp_val_max (TREE_TYPE (max));
 468           t = VR_RANGE;
 469         }
 470       else if (is_max)
 471         {
 472           tree one = build_int_cst (TREE_TYPE (min), 1);
 473           max = int_const_binop (MINUS_EXPR, min, one, 0);
 474           min = vrp_val_min (TREE_TYPE (min));
 475           t = VR_RANGE;
 476         }
 477     }
 478
 479   set_value_range (vr, t, min, max, equiv);
 480 }
 481
 482 /* Copy value range FROM into value range TO.  */
 483
 484 static inline void
 485 copy_value_range (value_range_t *to, value_range_t *from)
 486 {
 487   set_value_range (to, from->type, from->min, from->max, from->equiv);
 488 }
 489
 490 /* Set value range VR to a single value.  This function is only called
 491    with values we get from statements, and exists to clear the
 492    TREE_OVERFLOW flag so that we don't think we have an overflow
 493    infinity when we shouldn't.  */
 494
 495 static inline void
 496 set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
 497 {
 498   gcc_assert (is_gimple_min_invariant (val));
 499   val = avoid_overflow_infinity (val);
 500   set_value_range (vr, VR_RANGE, val, val, equiv);
 501 }
 502
 503 /* Set value range VR to a non-negative range of type TYPE.
 504    OVERFLOW_INFINITY indicates whether to use an overflow infinity
 505    rather than TYPE_MAX_VALUE; this should be true if we determine
 506    that the range is nonnegative based on the assumption that signed
 507    overflow does not occur.  */
 508
 509 static inline void
 510 set_value_range_to_nonnegative (value_range_t *vr, tree type,
 511                                 bool overflow_infinity)
 512 {
 513   tree zero;
 514
 515   if (overflow_infinity && !supports_overflow_infinity (type))
 516     {
 517       set_value_range_to_varying (vr);
 518       return;
 519     }
 520
 521   zero = build_int_cst (type, 0);
 522   set_value_range (vr, VR_RANGE, zero,
 523                    (overflow_infinity
 524                     ? positive_overflow_infinity (type)
 525                     : TYPE_MAX_VALUE (type)),
 526                    vr->equiv);
 527 }
 528
 529 /* Set value range VR to a non-NULL range of type TYPE.  */
 530
 531 static inline void
 532 set_value_range_to_nonnull (value_range_t *vr, tree type)
 533 {
 534   tree zero = build_int_cst (type, 0);
 535   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
 536 }
 537
 538
 539 /* Set value range VR to a NULL range of type TYPE.  */
 540
 541 static inline void
 542 set_value_range_to_null (value_range_t *vr, tree type)
 543 {
 544   set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
 545 }
 546
 547
 548 /* Set value range VR to a range of a truthvalue of type TYPE.  */
 549
 550 static inline void
 551 set_value_range_to_truthvalue (value_range_t *vr, tree type)
 552 {
 553   if (TYPE_PRECISION (type) == 1)
 554     set_value_range_to_varying (vr);
 555   else
 556     set_value_range (vr, VR_RANGE,
 557                      build_int_cst (type, 0), build_int_cst (type, 1),
 558                      vr->equiv);
 559 }
 560
 561
 562 /* Set value range VR to VR_UNDEFINED.  */
 563
 564 static inline void
 565 set_value_range_to_undefined (value_range_t *vr)
 566 {
 567   vr->type = VR_UNDEFINED;
 568   vr->min = vr->max = NULL_TREE;
 569   if (vr->equiv)
 570     bitmap_clear (vr->equiv);
 571 }
 572
 573
 574 /* Return value range information for VAR.
 575
 576    If we have no values ranges recorded (ie, VRP is not running), then
 577    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 578
 579 static value_range_t *
 580 get_value_range (const_tree var)
 581 {
 582   value_range_t *vr;
 583   tree sym;
 584   unsigned ver = SSA_NAME_VERSION (var);
 585
 586   /* If we have no recorded ranges, then return NULL.  */
 587   if (! vr_value)
 588     return NULL;
 589
 590   vr = vr_value[ver];
 591   if (vr)
 592     return vr;
 593
 594   /* Create a default value range.  */
 595   vr_value[ver] = vr = XCNEW (value_range_t);
 596
 597   /* Defer allocating the equivalence set.  */
 598   vr->equiv = NULL;
 599
 600   /* If VAR is a default definition, the variable can take any value
 601      in VAR's type.  */
 602   sym = SSA_NAME_VAR (var);
 603   if (SSA_NAME_IS_DEFAULT_DEF (var))
 604     {
 605       /* Try to use the "nonnull" attribute to create ~[0, 0]
 606          anti-ranges for pointers.  Note that this is only valid with
 607          default definitions of PARM_DECLs.  */
 608       if (TREE_CODE (sym) == PARM_DECL
 609           && POINTER_TYPE_P (TREE_TYPE (sym))
 610           && nonnull_arg_p (sym))
 611         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
 612       else
 613         set_value_range_to_varying (vr);
 614     }
 615
 616   return vr;
 617 }
 618
 619 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
 620
 621 static inline bool
 622 vrp_operand_equal_p (const_tree val1, const_tree val2)
 623 {
 624   if (val1 == val2)
 625     return true;
 626   if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
 627     return false;
 628   if (is_overflow_infinity (val1))
 629     return is_overflow_infinity (val2);
 630   return true;
 631 }
 632
 633 /* Return true, if the bitmaps B1 and B2 are equal.  */
 634
 635 static inline bool
 636 vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 637 {
 638   return (b1 == b2
 639           || (b1 && b2
 640               && bitmap_equal_p (b1, b2)));
 641 }
 642
 643 /* Update the value range and equivalence set for variable VAR to
 644    NEW_VR.  Return true if NEW_VR is different from VAR's previous
 645    value.
 646
 647    NOTE: This function assumes that NEW_VR is a temporary value range
 648    object created for the sole purpose of updating VAR's range.  The
 649    storage used by the equivalence set from NEW_VR will be freed by
 650    this function.  Do not call update_value_range when NEW_VR
 651    is the range object associated with another SSA name.  */
 652
 653 static inline bool
 654 update_value_range (const_tree var, value_range_t *new_vr)
 655 {
 656   value_range_t *old_vr;
 657   bool is_new;
 658
 659   /* Update the value range, if necessary.  */
 660   old_vr = get_value_range (var);
 661   is_new = old_vr->type != new_vr->type
 662            || !vrp_operand_equal_p (old_vr->min, new_vr->min)
 663            || !vrp_operand_equal_p (old_vr->max, new_vr->max)
 664            || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
 665
 666   if (is_new)
 667     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
 668                      new_vr->equiv);
 669
 670   BITMAP_FREE (new_vr->equiv);
 671
 672   return is_new;
 673 }
 674
 675
 676 /* Add VAR and VAR's equivalence set to EQUIV.  This is the central
 677    point where equivalence processing can be turned on/off.  */
 678
 679 static void
 680 add_equivalence (bitmap *equiv, const_tree var)
 681 {
 682   unsigned ver = SSA_NAME_VERSION (var);
 683   value_range_t *vr = vr_value[ver];
 684
 685   if (*equiv == NULL)
 686     *equiv = BITMAP_ALLOC (NULL);
 687   bitmap_set_bit (*equiv, ver);
 688   if (vr && vr->equiv)
 689     bitmap_ior_into (*equiv, vr->equiv);
 690 }
 691
 692
 693 /* Return true if VR is ~[0, 0].  */
 694
 695 static inline bool
 696 range_is_nonnull (value_range_t *vr)
 697 {
 698   return vr->type == VR_ANTI_RANGE
 699          && integer_zerop (vr->min)
 700          && integer_zerop (vr->max);
 701 }
 702
 703
 704 /* Return true if VR is [0, 0].  */
 705
 706 static inline bool
 707 range_is_null (value_range_t *vr)
 708 {
 709   return vr->type == VR_RANGE
 710          && integer_zerop (vr->min)
 711          && integer_zerop (vr->max);
 712 }
 713
 714
 715 /* Return true if value range VR involves at least one symbol.  */
 716
 717 static inline bool
 718 symbolic_range_p (value_range_t *vr)
 719 {
 720   return (!is_gimple_min_invariant (vr->min)
 721           || !is_gimple_min_invariant (vr->max));
 722 }
 723
 724 /* Return true if value range VR uses an overflow infinity.  */
 725
 726 static inline bool
 727 overflow_infinity_range_p (value_range_t *vr)
 728 {
 729   return (vr->type == VR_RANGE
 730           && (is_overflow_infinity (vr->min)
 731               || is_overflow_infinity (vr->max)));
 732 }
 733
 734 /* Return false if we can not make a valid comparison based on VR;
 735    this will be the case if it uses an overflow infinity and overflow
 736    is not undefined (i.e., -fno-strict-overflow is in effect).
 737    Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
 738    uses an overflow infinity.  */
 739
 740 static bool
 741 usable_range_p (value_range_t *vr, bool *strict_overflow_p)
 742 {
 743   gcc_assert (vr->type == VR_RANGE);
 744   if (is_overflow_infinity (vr->min))
 745     {
 746       *strict_overflow_p = true;
 747       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
 748         return false;
 749     }
 750   if (is_overflow_infinity (vr->max))
 751     {
 752       *strict_overflow_p = true;
 753       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
 754         return false;
 755     }
 756   return true;
 757 }
 758
 759
 760 /* Like tree_expr_nonnegative_warnv_p, but this function uses value
 761    ranges obtained so far.  */
 762
 763 static bool
 764 vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
 765 {
 766   return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p);
 767 }
 768
 769 /* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
 770    obtained so far.  */
 771
 772 static bool
 773 vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p)
 774 {
 775   if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p))
 776     return true;
 777
 778   /* If we have an expression of the form &X->a, then the expression
 779      is nonnull if X is nonnull.  */
 780   if (TREE_CODE (expr) == ADDR_EXPR)
 781     {
 782       tree base = get_base_address (TREE_OPERAND (expr, 0));
 783
 784       if (base != NULL_TREE
 785           && TREE_CODE (base) == INDIRECT_REF
 786           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
 787         {
 788           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
 789           if (range_is_nonnull (vr))
 790             return true;
 791         }
 792     }
 793
 794   return false;
 795 }
 796
 797 /* Returns true if EXPR is a valid value (as expected by compare_values) --
 798    a gimple invariant, or SSA_NAME +- CST.  */
 799
 800 static bool
 801 valid_value_p (tree expr)
 802 {
 803   if (TREE_CODE (expr) == SSA_NAME)
 804     return true;
 805
 806   if (TREE_CODE (expr) == PLUS_EXPR
 807       || TREE_CODE (expr) == MINUS_EXPR)
 808     return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
 809             && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
 810
 811   return is_gimple_min_invariant (expr);
 812 }
 813
 814 /* Return
 815    1 if VAL < VAL2
 816    0 if !(VAL < VAL2)
 817    -2 if those are incomparable.  */
 818 static inline int
 819 operand_less_p (tree val, tree val2)
 820 {
 821   /* LT is folded faster than GE and others.  Inline the common case.  */
 822   if (TREE_CODE (val) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
 823     {
 824       if (TYPE_UNSIGNED (TREE_TYPE (val)))
 825         return INT_CST_LT_UNSIGNED (val, val2);
 826       else
 827         {
 828           if (INT_CST_LT (val, val2))
 829             return 1;
 830         }
 831     }
 832   else
 833     {
 834       tree tcmp;
 835
 836       fold_defer_overflow_warnings ();
 837
 838       tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
 839
 840       fold_undefer_and_ignore_overflow_warnings ();
 841
 842       if (!tcmp
 843           || TREE_CODE (tcmp) != INTEGER_CST)
 844         return -2;
 845
 846       if (!integer_zerop (tcmp))
 847         return 1;
 848     }
 849
 850   /* val >= val2, not considering overflow infinity.  */
 851   if (is_negative_overflow_infinity (val))
 852     return is_negative_overflow_infinity (val2) ? 0 : 1;
 853   else if (is_positive_overflow_infinity (val2))
 854     return is_positive_overflow_infinity (val) ? 0 : 1;
 855
 856   return 0;
 857 }
 858
 859 /* Compare two values VAL1 and VAL2.  Return
 860
 861         -2 if VAL1 and VAL2 cannot be compared at compile-time,
 862         -1 if VAL1 < VAL2,
 863          0 if VAL1 == VAL2,
 864         +1 if VAL1 > VAL2, and
 865         +2 if VAL1 != VAL2
 866
 867    This is similar to tree_int_cst_compare but supports pointer values
 868    and values that cannot be compared at compile time.
 869
 870    If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
 871    true if the return value is only valid if we assume that signed
 872    overflow is undefined.  */
 873
 874 static int
 875 compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
 876 {
 877   if (val1 == val2)
 878     return 0;
 879
 880   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
 881      both integers.  */
 882   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
 883               == POINTER_TYPE_P (TREE_TYPE (val2)));
 884   /* Convert the two values into the same type.  This is needed because
 885      sizetype causes sign extension even for unsigned types.  */
 886   val2 = fold_convert (TREE_TYPE (val1), val2);
 887   STRIP_USELESS_TYPE_CONVERSION (val2);
 888
 889   if ((TREE_CODE (val1) == SSA_NAME
 890        || TREE_CODE (val1) == PLUS_EXPR
 891        || TREE_CODE (val1) == MINUS_EXPR)
 892       && (TREE_CODE (val2) == SSA_NAME
 893           || TREE_CODE (val2) == PLUS_EXPR
 894           || TREE_CODE (val2) == MINUS_EXPR))
 895     {
 896       tree n1, c1, n2, c2;
 897       enum tree_code code1, code2;
 898
 899       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
 900          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
 901          same name, return -2.  */
 902       if (TREE_CODE (val1) == SSA_NAME)
 903         {
 904           code1 = SSA_NAME;
 905           n1 = val1;
 906           c1 = NULL_TREE;
 907         }
 908       else
 909         {
 910           code1 = TREE_CODE (val1);
 911           n1 = TREE_OPERAND (val1, 0);
 912           c1 = TREE_OPERAND (val1, 1);
 913           if (tree_int_cst_sgn (c1) == -1)
 914             {
 915               if (is_negative_overflow_infinity (c1))
 916                 return -2;
 917               c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
 918               if (!c1)
 919                 return -2;
 920               code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 921             }
 922         }
 923
 924       if (TREE_CODE (val2) == SSA_NAME)
 925         {
 926           code2 = SSA_NAME;
 927           n2 = val2;
 928           c2 = NULL_TREE;
 929         }
 930       else
 931         {
 932           code2 = TREE_CODE (val2);
 933           n2 = TREE_OPERAND (val2, 0);
 934           c2 = TREE_OPERAND (val2, 1);
 935           if (tree_int_cst_sgn (c2) == -1)
 936             {
 937               if (is_negative_overflow_infinity (c2))
 938                 return -2;
 939               c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
 940               if (!c2)
 941                 return -2;
 942               code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 943             }
 944         }
 945
 946       /* Both values must use the same name.  */
 947       if (n1 != n2)
 948         return -2;
 949
 950       if (code1 == SSA_NAME
 951           && code2 == SSA_NAME)
 952         /* NAME == NAME  */
 953         return 0;
 954
 955       /* If overflow is defined we cannot simplify more.  */
 956       if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
 957         return -2;
 958
 959       if (strict_overflow_p != NULL
 960           && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
 961           && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
 962         *strict_overflow_p = true;
 963
 964       if (code1 == SSA_NAME)
 965         {
 966           if (code2 == PLUS_EXPR)
 967             /* NAME < NAME + CST  */
 968             return -1;
 969           else if (code2 == MINUS_EXPR)
 970             /* NAME > NAME - CST  */
 971             return 1;
 972         }
 973       else if (code1 == PLUS_EXPR)
 974         {
 975           if (code2 == SSA_NAME)
 976             /* NAME + CST > NAME  */
 977             return 1;
 978           else if (code2 == PLUS_EXPR)
 979             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
 980             return compare_values_warnv (c1, c2, strict_overflow_p);
 981           else if (code2 == MINUS_EXPR)
 982             /* NAME + CST1 > NAME - CST2  */
 983             return 1;
 984         }
 985       else if (code1 == MINUS_EXPR)
 986         {
 987           if (code2 == SSA_NAME)
 988             /* NAME - CST < NAME  */
 989             return -1;
 990           else if (code2 == PLUS_EXPR)
 991             /* NAME - CST1 < NAME + CST2  */
 992             return -1;
 993           else if (code2 == MINUS_EXPR)
 994             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
 995                C1 and C2 are swapped in the call to compare_values.  */
 996             return compare_values_warnv (c2, c1, strict_overflow_p);
 997         }
 998
 999       gcc_unreachable ();
1000     }
1001
1002   /* We cannot compare non-constants.  */
1003   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
1004     return -2;
1005
1006   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
1007     {
1008       /* We cannot compare overflowed values, except for overflow
1009          infinities.  */
1010       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
1011         {
1012           if (strict_overflow_p != NULL)
1013             *strict_overflow_p = true;
1014           if (is_negative_overflow_infinity (val1))
1015             return is_negative_overflow_infinity (val2) ? 0 : -1;
1016           else if (is_negative_overflow_infinity (val2))
1017             return 1;
1018           else if (is_positive_overflow_infinity (val1))
1019             return is_positive_overflow_infinity (val2) ? 0 : 1;
1020           else if (is_positive_overflow_infinity (val2))
1021             return -1;
1022           return -2;
1023         }
1024
1025       return tree_int_cst_compare (val1, val2);
1026     }
1027   else
1028     {
1029       tree t;
1030
1031       /* First see if VAL1 and VAL2 are not the same.  */
1032       if (val1 == val2 || operand_equal_p (val1, val2, 0))
1033         return 0;
1034
1035       /* If VAL1 is a lower address than VAL2, return -1.  */
1036       if (operand_less_p (val1, val2) == 1)
1037         return -1;
1038
1039       /* If VAL1 is a higher address than VAL2, return +1.  */
1040       if (operand_less_p (val2, val1) == 1)
1041         return 1;
1042
1043       /* If VAL1 is different than VAL2, return +2.
1044          For integer constants we either have already returned -1 or 1
1045          or they are equivalent.  We still might succeed in proving
1046          something about non-trivial operands.  */
1047       if (TREE_CODE (val1) != INTEGER_CST
1048           || TREE_CODE (val2) != INTEGER_CST)
1049         {
1050           t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
1051           if (t && integer_onep (t))
1052             return 2;
1053         }
1054
1055       return -2;
1056     }
1057 }
1058
1059 /* Compare values like compare_values_warnv, but treat comparisons of
1060    nonconstants which rely on undefined overflow as incomparable.  */
1061
1062 static int
1063 compare_values (tree val1, tree val2)
1064 {
1065   bool sop;
1066   int ret;
1067
1068   sop = false;
1069   ret = compare_values_warnv (val1, val2, &sop);
1070   if (sop
1071       && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
1072     ret = -2;
1073   return ret;
1074 }
1075
1076
1077 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
1078           0 if VAL is not inside VR,
1079          -2 if we cannot tell either way.
1080
1081    FIXME, the current semantics of this functions are a bit quirky
1082           when taken in the context of VRP.  In here we do not care
1083           about VR's type.  If VR is the anti-range ~[3, 5] the call
1084           value_inside_range (4, VR) will return 1.
1085
1086           This is counter-intuitive in a strict sense, but the callers
1087           currently expect this.  They are calling the function
1088           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
1089           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
1090           themselves.
1091
1092           This also applies to value_ranges_intersect_p and
1093           range_includes_zero_p.  The semantics of VR_RANGE and
1094           VR_ANTI_RANGE should be encoded here, but that also means
1095           adapting the users of these functions to the new semantics.
1096
1097    Benchmark compile/20001226-1.c compilation time after changing this
1098    function.  */
1099
1100 static inline int
1101 value_inside_range (tree val, value_range_t * vr)
1102 {
1103   int cmp1, cmp2;
1104
1105   cmp1 = operand_less_p (val, vr->min);
1106   if (cmp1 == -2)
1107     return -2;
1108   if (cmp1 == 1)
1109     return 0;
1110
1111   cmp2 = operand_less_p (vr->max, val);
1112   if (cmp2 == -2)
1113     return -2;
1114
1115   return !cmp2;
1116 }
1117
1118
1119 /* Return true if value ranges VR0 and VR1 have a non-empty
1120    intersection.
1121
1122    Benchmark compile/20001226-1.c compilation time after changing this
1123    function.
1124    */
1125
1126 static inline bool
1127 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
1128 {
1129   /* The value ranges do not intersect if the maximum of the first range is
1130      less than the minimum of the second range or vice versa.
1131      When those relations are unknown, we can't do any better.  */
1132   if (operand_less_p (vr0->max, vr1->min) != 0)
1133     return false;
1134   if (operand_less_p (vr1->max, vr0->min) != 0)
1135     return false;
1136   return true;
1137 }
1138
1139
1140 /* Return true if VR includes the value zero, false otherwise.  FIXME,
1141    currently this will return false for an anti-range like ~[-4, 3].
1142    This will be wrong when the semantics of value_inside_range are
1143    modified (currently the users of this function expect these
1144    semantics).  */
1145
1146 static inline bool
1147 range_includes_zero_p (value_range_t *vr)
1148 {
1149   tree zero;
1150
1151   gcc_assert (vr->type != VR_UNDEFINED
1152               && vr->type != VR_VARYING
1153               && !symbolic_range_p (vr));
1154
1155   zero = build_int_cst (TREE_TYPE (vr->min), 0);
1156   return (value_inside_range (zero, vr) == 1);
1157 }
1158
1159 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
1160    false otherwise or if no value range information is available.  */
1161
1162 bool
1163 ssa_name_nonnegative_p (const_tree t)
1164 {
1165   value_range_t *vr = get_value_range (t);
1166
1167   if (!vr)
1168     return false;
1169
1170   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
1171      which would return a useful value should be encoded as a VR_RANGE.  */
1172   if (vr->type == VR_RANGE)
1173     {
1174       int result = compare_values (vr->min, integer_zero_node);
1175
1176       return (result == 0 || result == 1);
1177     }
1178   return false;
1179 }
1180
1181 /* Return true if T, an SSA_NAME, is known to be nonzero.  Return
1182    false otherwise or if no value range information is available.  */
1183
1184 bool
1185 ssa_name_nonzero_p (const_tree t)
1186 {
1187   value_range_t *vr = get_value_range (t);
1188
1189   if (!vr)
1190     return false;
1191
1192   /* A VR_RANGE which does not include zero is a nonzero value.  */
1193   if (vr->type == VR_RANGE && !symbolic_range_p (vr))
1194     return ! range_includes_zero_p (vr);
1195
1196   /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
1197   if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
1198     return range_includes_zero_p (vr);
1199
1200   return false;
1201 }
1202
1203
1204 /* Extract value range information from an ASSERT_EXPR EXPR and store
1205    it in *VR_P.  */
1206
1207 static void
1208 extract_range_from_assert (value_range_t *vr_p, tree expr)
1209 {
1210   tree var, cond, limit, min, max, type;
1211   value_range_t *var_vr, *limit_vr;
1212   enum tree_code cond_code;
1213
1214   var = ASSERT_EXPR_VAR (expr);
1215   cond = ASSERT_EXPR_COND (expr);
1216
1217   gcc_assert (COMPARISON_CLASS_P (cond));
1218
1219   /* Find VAR in the ASSERT_EXPR conditional.  */
1220   if (var == TREE_OPERAND (cond, 0)
1221       || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
1222       || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
1223     {
1224       /* If the predicate is of the form VAR COMP LIMIT, then we just
1225          take LIMIT from the RHS and use the same comparison code.  */
1226       cond_code = TREE_CODE (cond);
1227       limit = TREE_OPERAND (cond, 1);
1228       cond = TREE_OPERAND (cond, 0);
1229     }
1230   else
1231     {
1232       /* If the predicate is of the form LIMIT COMP VAR, then we need
1233          to flip around the comparison code to create the proper range
1234          for VAR.  */
1235       cond_code = swap_tree_comparison (TREE_CODE (cond));
1236       limit = TREE_OPERAND (cond, 0);
1237       cond = TREE_OPERAND (cond, 1);
1238     }
1239
1240   limit = avoid_overflow_infinity (limit);
1241
1242   type = TREE_TYPE (limit);
1243   gcc_assert (limit != var);
1244
1245   /* For pointer arithmetic, we only keep track of pointer equality
1246      and inequality.  */
1247   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
1248     {
1249       set_value_range_to_varying (vr_p);
1250       return;
1251     }
1252
1253   /* If LIMIT is another SSA name and LIMIT has a range of its own,
1254      try to use LIMIT's range to avoid creating symbolic ranges
1255      unnecessarily. */
1256   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
1257
1258   /* LIMIT's range is only interesting if it has any useful information.  */
1259   if (limit_vr
1260       && (limit_vr->type == VR_UNDEFINED
1261           || limit_vr->type == VR_VARYING
1262           || symbolic_range_p (limit_vr)))
1263     limit_vr = NULL;
1264
1265   /* Initially, the new range has the same set of equivalences of
1266      VAR's range.  This will be revised before returning the final
1267      value.  Since assertions may be chained via mutually exclusive
1268      predicates, we will need to trim the set of equivalences before
1269      we are done.  */
1270   gcc_assert (vr_p->equiv == NULL);
1271   add_equivalence (&vr_p->equiv, var);
1272
1273   /* Extract a new range based on the asserted comparison for VAR and
1274      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
1275      will only use it for equality comparisons (EQ_EXPR).  For any
1276      other kind of assertion, we cannot derive a range from LIMIT's
1277      anti-range that can be used to describe the new range.  For
1278      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
1279      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
1280      no single range for x_2 that could describe LE_EXPR, so we might
1281      as well build the range [b_4, +INF] for it.
1282      One special case we handle is extracting a range from a
1283      range test encoded as (unsigned)var + CST <= limit.  */
1284   if (TREE_CODE (cond) == NOP_EXPR
1285       || TREE_CODE (cond) == PLUS_EXPR)
1286     {
1287       if (TREE_CODE (cond) == PLUS_EXPR)
1288         {
1289           min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
1290                              TREE_OPERAND (cond, 1));
1291           max = int_const_binop (PLUS_EXPR, limit, min, 0);
1292           cond = TREE_OPERAND (cond, 0);
1293         }
1294       else
1295         {
1296           min = build_int_cst (TREE_TYPE (var), 0);
1297           max = limit;
1298         }
1299
1300       /* Make sure to not set TREE_OVERFLOW on the final type
1301          conversion.  We are willingly interpreting large positive
1302          unsigned values as negative singed values here.  */
1303       min = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (min),
1304                                    TREE_INT_CST_HIGH (min), 0, false);
1305       max = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (max),
1306                                    TREE_INT_CST_HIGH (max), 0, false);
1307
1308       /* We can transform a max, min range to an anti-range or
1309          vice-versa.  Use set_and_canonicalize_value_range which does
1310          this for us.  */
1311       if (cond_code == LE_EXPR)
1312         set_and_canonicalize_value_range (vr_p, VR_RANGE,
1313                                           min, max, vr_p->equiv);
1314       else if (cond_code == GT_EXPR)
1315         set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
1316                                           min, max, vr_p->equiv);
1317       else
1318         gcc_unreachable ();
1319     }
1320   else if (cond_code == EQ_EXPR)
1321     {
1322       enum value_range_type range_type;
1323
1324       if (limit_vr)
1325         {
1326           range_type = limit_vr->type;
1327           min = limit_vr->min;
1328           max = limit_vr->max;
1329         }
1330       else
1331         {
1332           range_type = VR_RANGE;
1333           min = limit;
1334           max = limit;
1335         }
1336
1337       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
1338
1339       /* When asserting the equality VAR == LIMIT and LIMIT is another
1340          SSA name, the new range will also inherit the equivalence set
1341          from LIMIT.  */
1342       if (TREE_CODE (limit) == SSA_NAME)
1343         add_equivalence (&vr_p->equiv, limit);
1344     }
1345   else if (cond_code == NE_EXPR)
1346     {
1347       /* As described above, when LIMIT's range is an anti-range and
1348          this assertion is an inequality (NE_EXPR), then we cannot
1349          derive anything from the anti-range.  For instance, if
1350          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
1351          not imply that VAR's range is [0, 0].  So, in the case of
1352          anti-ranges, we just assert the inequality using LIMIT and
1353          not its anti-range.
1354
1355          If LIMIT_VR is a range, we can only use it to build a new
1356          anti-range if LIMIT_VR is a single-valued range.  For
1357          instance, if LIMIT_VR is [0, 1], the predicate
1358          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
1359          Rather, it means that for value 0 VAR should be ~[0, 0]
1360          and for value 1, VAR should be ~[1, 1].  We cannot
1361          represent these ranges.
1362
1363          The only situation in which we can build a valid
1364          anti-range is when LIMIT_VR is a single-valued range
1365          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case,
1366          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
1367       if (limit_vr
1368           && limit_vr->type == VR_RANGE
1369           && compare_values (limit_vr->min, limit_vr->max) == 0)
1370         {
1371           min = limit_vr->min;
1372           max = limit_vr->max;
1373         }
1374       else
1375         {
1376           /* In any other case, we cannot use LIMIT's range to build a
1377              valid anti-range.  */
1378           min = max = limit;
1379         }
1380
1381       /* If MIN and MAX cover the whole range for their type, then
1382          just use the original LIMIT.  */
1383       if (INTEGRAL_TYPE_P (type)
1384           && vrp_val_is_min (min)
1385           && vrp_val_is_max (max))
1386         min = max = limit;
1387
1388       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
1389     }
1390   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
1391     {
1392       min = TYPE_MIN_VALUE (type);
1393
1394       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1395         max = limit;
1396       else
1397         {
1398           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1399              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
1400              LT_EXPR.  */
1401           max = limit_vr->max;
1402         }
1403
1404       /* If the maximum value forces us to be out of bounds, simply punt.
1405          It would be pointless to try and do anything more since this
1406          all should be optimized away above us.  */
1407       if ((cond_code == LT_EXPR
1408            && compare_values (max, min) == 0)
1409           || is_overflow_infinity (max))
1410         set_value_range_to_varying (vr_p);
1411       else
1412         {
1413           /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
1414           if (cond_code == LT_EXPR)
1415             {
1416               tree one = build_int_cst (type, 1);
1417               max = fold_build2 (MINUS_EXPR, type, max, one);
1418               if (EXPR_P (max))
1419                 TREE_NO_WARNING (max) = 1;
1420             }
1421
1422           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1423         }
1424     }
1425   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
1426     {
1427       max = TYPE_MAX_VALUE (type);
1428
1429       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
1430         min = limit;
1431       else
1432         {
1433           /* If LIMIT_VR is of the form [N1, N2], we need to build the
1434              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
1435              GT_EXPR.  */
1436           min = limit_vr->min;
1437         }
1438
1439       /* If the minimum value forces us to be out of bounds, simply punt.
1440          It would be pointless to try and do anything more since this
1441          all should be optimized away above us.  */
1442       if ((cond_code == GT_EXPR
1443            && compare_values (min, max) == 0)
1444           || is_overflow_infinity (min))
1445         set_value_range_to_varying (vr_p);
1446       else
1447         {
1448           /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
1449           if (cond_code == GT_EXPR)
1450             {
1451               tree one = build_int_cst (type, 1);
1452               min = fold_build2 (PLUS_EXPR, type, min, one);
1453               if (EXPR_P (min))
1454                 TREE_NO_WARNING (min) = 1;
1455             }
1456
1457           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1458         }
1459     }
1460   else
1461     gcc_unreachable ();
1462
1463   /* If VAR already had a known range, it may happen that the new
1464      range we have computed and VAR's range are not compatible.  For
1465      instance,
1466
1467         if (p_5 == NULL)
1468           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1469           x_7 = p_6->fld;
1470           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1471
1472      While the above comes from a faulty program, it will cause an ICE
1473      later because p_8 and p_6 will have incompatible ranges and at
1474      the same time will be considered equivalent.  A similar situation
1475      would arise from
1476
1477         if (i_5 > 10)
1478           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1479           if (i_5 < 5)
1480             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1481
1482      Again i_6 and i_7 will have incompatible ranges.  It would be
1483      pointless to try and do anything with i_7's range because
1484      anything dominated by 'if (i_5 < 5)' will be optimized away.
1485      Note, due to the wa in which simulation proceeds, the statement
1486      i_7 = ASSERT_EXPR <...> we would never be visited because the
1487      conditional 'if (i_5 < 5)' always evaluates to false.  However,
1488      this extra check does not hurt and may protect against future
1489      changes to VRP that may get into a situation similar to the
1490      NULL pointer dereference example.
1491
1492      Note that these compatibility tests are only needed when dealing
1493      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
1494      are both anti-ranges, they will always be compatible, because two
1495      anti-ranges will always have a non-empty intersection.  */
1496
1497   var_vr = get_value_range (var);
1498
1499   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1500      ranges or anti-ranges.  */
1501   if (vr_p->type == VR_VARYING
1502       || vr_p->type == VR_UNDEFINED
1503       || var_vr->type == VR_VARYING
1504       || var_vr->type == VR_UNDEFINED
1505       || symbolic_range_p (vr_p)
1506       || symbolic_range_p (var_vr))
1507     return;
1508
1509   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1510     {
1511       /* If the two ranges have a non-empty intersection, we can
1512          refine the resulting range.  Since the assert expression
1513          creates an equivalency and at the same time it asserts a
1514          predicate, we can take the intersection of the two ranges to
1515          get better precision.  */
1516       if (value_ranges_intersect_p (var_vr, vr_p))
1517         {
1518           /* Use the larger of the two minimums.  */
1519           if (compare_values (vr_p->min, var_vr->min) == -1)
1520             min = var_vr->min;
1521           else
1522             min = vr_p->min;
1523
1524           /* Use the smaller of the two maximums.  */
1525           if (compare_values (vr_p->max, var_vr->max) == 1)
1526             max = var_vr->max;
1527           else
1528             max = vr_p->max;
1529
1530           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1531         }
1532       else
1533         {
1534           /* The two ranges do not intersect, set the new range to
1535              VARYING, because we will not be able to do anything
1536              meaningful with it.  */
1537           set_value_range_to_varying (vr_p);
1538         }
1539     }
1540   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1541            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1542     {
1543       /* A range and an anti-range will cancel each other only if
1544          their ends are the same.  For instance, in the example above,
1545          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1546          so VR_P should be set to VR_VARYING.  */
1547       if (compare_values (var_vr->min, vr_p->min) == 0
1548           && compare_values (var_vr->max, vr_p->max) == 0)
1549         set_value_range_to_varying (vr_p);
1550       else
1551         {
1552           tree min, max, anti_min, anti_max, real_min, real_max;
1553           int cmp;
1554
1555           /* We want to compute the logical AND of the two ranges;
1556              there are three cases to consider.
1557
1558
1559              1. The VR_ANTI_RANGE range is completely within the
1560                 VR_RANGE and the endpoints of the ranges are
1561                 different.  In that case the resulting range
1562                 should be whichever range is more precise.
1563                 Typically that will be the VR_RANGE.
1564
1565              2. The VR_ANTI_RANGE is completely disjoint from
1566                 the VR_RANGE.  In this case the resulting range
1567                 should be the VR_RANGE.
1568
1569              3. There is some overlap between the VR_ANTI_RANGE
1570                 and the VR_RANGE.
1571
1572                 3a. If the high limit of the VR_ANTI_RANGE resides
1573                     within the VR_RANGE, then the result is a new
1574                     VR_RANGE starting at the high limit of the
1575                     the VR_ANTI_RANGE + 1 and extending to the
1576                     high limit of the original VR_RANGE.
1577
1578                 3b. If the low limit of the VR_ANTI_RANGE resides
1579                     within the VR_RANGE, then the result is a new
1580                     VR_RANGE starting at the low limit of the original
1581                     VR_RANGE and extending to the low limit of the
1582                     VR_ANTI_RANGE - 1.  */
1583           if (vr_p->type == VR_ANTI_RANGE)
1584             {
1585               anti_min = vr_p->min;
1586               anti_max = vr_p->max;
1587               real_min = var_vr->min;
1588               real_max = var_vr->max;
1589             }
1590           else
1591             {
1592               anti_min = var_vr->min;
1593               anti_max = var_vr->max;
1594               real_min = vr_p->min;
1595               real_max = vr_p->max;
1596             }
1597
1598
1599           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1600              not including any endpoints.  */
1601           if (compare_values (anti_max, real_max) == -1
1602               && compare_values (anti_min, real_min) == 1)
1603             {
1604               /* If the range is covering the whole valid range of
1605                  the type keep the anti-range.  */
1606               if (!vrp_val_is_min (real_min)
1607                   || !vrp_val_is_max (real_max))
1608                 set_value_range (vr_p, VR_RANGE, real_min,
1609                                  real_max, vr_p->equiv);
1610             }
1611           /* Case 2, VR_ANTI_RANGE completely disjoint from
1612              VR_RANGE.  */
1613           else if (compare_values (anti_min, real_max) == 1
1614                    || compare_values (anti_max, real_min) == -1)
1615             {
1616               set_value_range (vr_p, VR_RANGE, real_min,
1617                                real_max, vr_p->equiv);
1618             }
1619           /* Case 3a, the anti-range extends into the low
1620              part of the real range.  Thus creating a new
1621              low for the real range.  */
1622           else if (((cmp = compare_values (anti_max, real_min)) == 1
1623                     || cmp == 0)
1624                    && compare_values (anti_max, real_max) == -1)
1625             {
1626               gcc_assert (!is_positive_overflow_infinity (anti_max));
1627               if (needs_overflow_infinity (TREE_TYPE (anti_max))
1628                   && vrp_val_is_max (anti_max))
1629                 {
1630                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1631                     {
1632                       set_value_range_to_varying (vr_p);
1633                       return;
1634                     }
1635                   min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
1636                 }
1637               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1638                 min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1639                                    anti_max,
1640                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1641               else
1642                 min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1643                                    anti_max, size_int (1));
1644               max = real_max;
1645               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1646             }
1647           /* Case 3b, the anti-range extends into the high
1648              part of the real range.  Thus creating a new
1649              higher for the real range.  */
1650           else if (compare_values (anti_min, real_min) == 1
1651                    && ((cmp = compare_values (anti_min, real_max)) == -1
1652                        || cmp == 0))
1653             {
1654               gcc_assert (!is_negative_overflow_infinity (anti_min));
1655               if (needs_overflow_infinity (TREE_TYPE (anti_min))
1656                   && vrp_val_is_min (anti_min))
1657                 {
1658                   if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
1659                     {
1660                       set_value_range_to_varying (vr_p);
1661                       return;
1662                     }
1663                   max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
1664                 }
1665               else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
1666                 max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1667                                    anti_min,
1668                                    build_int_cst (TREE_TYPE (var_vr->min), 1));
1669               else
1670                 max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
1671                                    anti_min,
1672                                    size_int (-1));
1673               min = real_min;
1674               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1675             }
1676         }
1677     }
1678 }
1679
1680
1681 /* Extract range information from SSA name VAR and store it in VR.  If
1682    VAR has an interesting range, use it.  Otherwise, create the
1683    range [VAR, VAR] and return it.  This is useful in situations where
1684    we may have conditionals testing values of VARYING names.  For
1685    instance,
1686
1687         x_3 = y_5;
1688         if (x_3 > y_5)
1689           ...
1690
1691     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1692     always false.  */
1693
1694 static void
1695 extract_range_from_ssa_name (value_range_t *vr, tree var)
1696 {
1697   value_range_t *var_vr = get_value_range (var);
1698
1699   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1700     copy_value_range (vr, var_vr);
1701   else
1702     set_value_range (vr, VR_RANGE, var, var, NULL);
1703
1704   add_equivalence (&vr->equiv, var);
1705 }
1706
1707
1708 /* Wrapper around int_const_binop.  If the operation overflows and we
1709    are not using wrapping arithmetic, then adjust the result to be
1710    -INF or +INF depending on CODE, VAL1 and VAL2.  This can return
1711    NULL_TREE if we need to use an overflow infinity representation but
1712    the type does not support it.  */
1713
1714 static tree
1715 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1716 {
1717   tree res;
1718
1719   res = int_const_binop (code, val1, val2, 0);
1720
1721   /* If we are not using wrapping arithmetic, operate symbolically
1722      on -INF and +INF.  */
1723   if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
1724     {
1725       int checkz = compare_values (res, val1);
1726       bool overflow = false;
1727
1728       /* Ensure that res = val1 [+*] val2 >= val1
1729          or that res = val1 - val2 <= val1.  */
1730       if ((code == PLUS_EXPR
1731            && !(checkz == 1 || checkz == 0))
1732           || (code == MINUS_EXPR
1733               && !(checkz == 0 || checkz == -1)))
1734         {
1735           overflow = true;
1736         }
1737       /* Checking for multiplication overflow is done by dividing the
1738          output of the multiplication by the first input of the
1739          multiplication.  If the result of that division operation is
1740          not equal to the second input of the multiplication, then the
1741          multiplication overflowed.  */
1742       else if (code == MULT_EXPR && !integer_zerop (val1))
1743         {
1744           tree tmp = int_const_binop (TRUNC_DIV_EXPR,
1745                                       res,
1746                                       val1, 0);
1747           int check = compare_values (tmp, val2);
1748
1749           if (check != 0)
1750             overflow = true;
1751         }
1752
1753       if (overflow)
1754         {
1755           res = copy_node (res);
1756           TREE_OVERFLOW (res) = 1;
1757         }
1758
1759     }
1760   else if ((TREE_OVERFLOW (res)
1761             && !TREE_OVERFLOW (val1)
1762             && !TREE_OVERFLOW (val2))
1763            || is_overflow_infinity (val1)
1764            || is_overflow_infinity (val2))
1765     {
1766       /* If the operation overflowed but neither VAL1 nor VAL2 are
1767          overflown, return -INF or +INF depending on the operation
1768          and the combination of signs of the operands.  */
1769       int sgn1 = tree_int_cst_sgn (val1);
1770       int sgn2 = tree_int_cst_sgn (val2);
1771
1772       if (needs_overflow_infinity (TREE_TYPE (res))
1773           && !supports_overflow_infinity (TREE_TYPE (res)))
1774         return NULL_TREE;
1775
1776       /* We have to punt on adding infinities of different signs,
1777          since we can't tell what the sign of the result should be.
1778          Likewise for subtracting infinities of the same sign.  */
1779       if (((code == PLUS_EXPR && sgn1 != sgn2)
1780            || (code == MINUS_EXPR && sgn1 == sgn2))
1781           && is_overflow_infinity (val1)
1782           && is_overflow_infinity (val2))
1783         return NULL_TREE;
1784
1785       /* Don't try to handle division or shifting of infinities.  */
1786       if ((code == TRUNC_DIV_EXPR
1787            || code == FLOOR_DIV_EXPR
1788            || code == CEIL_DIV_EXPR
1789            || code == EXACT_DIV_EXPR
1790            || code == ROUND_DIV_EXPR
1791            || code == RSHIFT_EXPR)
1792           && (is_overflow_infinity (val1)
1793               || is_overflow_infinity (val2)))
1794         return NULL_TREE;
1795
1796       /* Notice that we only need to handle the restricted set of
1797          operations handled by extract_range_from_binary_expr.
1798          Among them, only multiplication, addition and subtraction
1799          can yield overflow without overflown operands because we
1800          are working with integral types only... except in the
1801          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1802          for division too.  */
1803
1804       /* For multiplication, the sign of the overflow is given
1805          by the comparison of the signs of the operands.  */
1806       if ((code == MULT_EXPR && sgn1 == sgn2)
1807           /* For addition, the operands must be of the same sign
1808              to yield an overflow.  Its sign is therefore that
1809              of one of the operands, for example the first.  For
1810              infinite operands X + -INF is negative, not positive.  */
1811           || (code == PLUS_EXPR
1812               && (sgn1 >= 0
1813                   ? !is_negative_overflow_infinity (val2)
1814                   : is_positive_overflow_infinity (val2)))
1815           /* For subtraction, non-infinite operands must be of
1816              different signs to yield an overflow.  Its sign is
1817              therefore that of the first operand or the opposite of
1818              that of the second operand.  A first operand of 0 counts
1819              as positive here, for the corner case 0 - (-INF), which
1820              overflows, but must yield +INF.  For infinite operands 0
1821              - INF is negative, not positive.  */
1822           || (code == MINUS_EXPR
1823               && (sgn1 >= 0
1824                   ? !is_positive_overflow_infinity (val2)
1825                   : is_negative_overflow_infinity (val2)))
1826           /* We only get in here with positive shift count, so the
1827              overflow direction is the same as the sign of val1.
1828              Actually rshift does not overflow at all, but we only
1829              handle the case of shifting overflowed -INF and +INF.  */
1830           || (code == RSHIFT_EXPR
1831               && sgn1 >= 0)
1832           /* For division, the only case is -INF / -1 = +INF.  */
1833           || code == TRUNC_DIV_EXPR
1834           || code == FLOOR_DIV_EXPR
1835           || code == CEIL_DIV_EXPR
1836           || code == EXACT_DIV_EXPR
1837           || code == ROUND_DIV_EXPR)
1838         return (needs_overflow_infinity (TREE_TYPE (res))
1839                 ? positive_overflow_infinity (TREE_TYPE (res))
1840                 : TYPE_MAX_VALUE (TREE_TYPE (res)));
1841       else
1842         return (needs_overflow_infinity (TREE_TYPE (res))
1843                 ? negative_overflow_infinity (TREE_TYPE (res))
1844                 : TYPE_MIN_VALUE (TREE_TYPE (res)));
1845     }
1846
1847   return res;
1848 }
1849
1850
1851 /* Extract range information from a binary expression EXPR based on
1852    the ranges of each of its operands and the expression code.  */
1853
1854 static void
1855 extract_range_from_binary_expr (value_range_t *vr,
1856                                 enum tree_code code,
1857                                 tree expr_type, tree op0, tree op1)
1858 {
1859   enum value_range_type type;
1860   tree min, max;
1861   int cmp;
1862   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1863   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1864
1865   /* Not all binary expressions can be applied to ranges in a
1866      meaningful way.  Handle only arithmetic operations.  */
1867   if (code != PLUS_EXPR
1868       && code != MINUS_EXPR
1869       && code != POINTER_PLUS_EXPR
1870       && code != MULT_EXPR
1871       && code != TRUNC_DIV_EXPR
1872       && code != FLOOR_DIV_EXPR
1873       && code != CEIL_DIV_EXPR
1874       && code != EXACT_DIV_EXPR
1875       && code != ROUND_DIV_EXPR
1876       && code != RSHIFT_EXPR
1877       && code != MIN_EXPR
1878       && code != MAX_EXPR
1879       && code != BIT_AND_EXPR
1880       && code != TRUTH_ANDIF_EXPR
1881       && code != TRUTH_ORIF_EXPR
1882       && code != TRUTH_AND_EXPR
1883       && code != TRUTH_OR_EXPR)
1884     {
1885       set_value_range_to_varying (vr);
1886       return;
1887     }
1888
1889   /* Get value ranges for each operand.  For constant operands, create
1890      a new value range with the operand to simplify processing.  */
1891   if (TREE_CODE (op0) == SSA_NAME)
1892     vr0 = *(get_value_range (op0));
1893   else if (is_gimple_min_invariant (op0))
1894     set_value_range_to_value (&vr0, op0, NULL);
1895   else
1896     set_value_range_to_varying (&vr0);
1897
1898   if (TREE_CODE (op1) == SSA_NAME)
1899     vr1 = *(get_value_range (op1));
1900   else if (is_gimple_min_invariant (op1))
1901     set_value_range_to_value (&vr1, op1, NULL);
1902   else
1903     set_value_range_to_varying (&vr1);
1904
1905   /* If either range is UNDEFINED, so is the result.  */
1906   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1907     {
1908       set_value_range_to_undefined (vr);
1909       return;
1910     }
1911
1912   /* The type of the resulting value range defaults to VR0.TYPE.  */
1913   type = vr0.type;
1914
1915   /* Refuse to operate on VARYING ranges, ranges of different kinds
1916      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
1917      because we may be able to derive a useful range even if one of
1918      the operands is VR_VARYING or symbolic range.  TODO, we may be
1919      able to derive anti-ranges in some cases.  */
1920   if (code != BIT_AND_EXPR
1921       && code != TRUTH_AND_EXPR
1922       && code != TRUTH_OR_EXPR
1923       && (vr0.type == VR_VARYING
1924           || vr1.type == VR_VARYING
1925           || vr0.type != vr1.type
1926           || symbolic_range_p (&vr0)
1927           || symbolic_range_p (&vr1)))
1928     {
1929       set_value_range_to_varying (vr);
1930       return;
1931     }
1932
1933   /* Now evaluate the expression to determine the new range.  */
1934   if (POINTER_TYPE_P (expr_type)
1935       || POINTER_TYPE_P (TREE_TYPE (op0))
1936       || POINTER_TYPE_P (TREE_TYPE (op1)))
1937     {
1938       if (code == MIN_EXPR || code == MAX_EXPR)
1939         {
1940           /* For MIN/MAX expressions with pointers, we only care about
1941              nullness, if both are non null, then the result is nonnull.
1942              If both are null, then the result is null. Otherwise they
1943              are varying.  */
1944           if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
1945             set_value_range_to_nonnull (vr, expr_type);
1946           else if (range_is_null (&vr0) && range_is_null (&vr1))
1947             set_value_range_to_null (vr, expr_type);
1948           else
1949             set_value_range_to_varying (vr);
1950
1951           return;
1952         }
1953       gcc_assert (code == POINTER_PLUS_EXPR);
1954       /* For pointer types, we are really only interested in asserting
1955          whether the expression evaluates to non-NULL.  */
1956       if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1957         set_value_range_to_nonnull (vr, expr_type);
1958       else if (range_is_null (&vr0) && range_is_null (&vr1))
1959         set_value_range_to_null (vr, expr_type);
1960       else
1961         set_value_range_to_varying (vr);
1962
1963       return;
1964     }
1965
1966   /* For integer ranges, apply the operation to each end of the
1967      range and see what we end up with.  */
1968   if (code == TRUTH_ANDIF_EXPR
1969       || code == TRUTH_ORIF_EXPR
1970       || code == TRUTH_AND_EXPR
1971       || code == TRUTH_OR_EXPR)
1972     {
1973       /* If one of the operands is zero, we know that the whole
1974          expression evaluates zero.  */
1975       if (code == TRUTH_AND_EXPR
1976           && ((vr0.type == VR_RANGE
1977                && integer_zerop (vr0.min)
1978                && integer_zerop (vr0.max))
1979               || (vr1.type == VR_RANGE
1980                   && integer_zerop (vr1.min)
1981                   && integer_zerop (vr1.max))))
1982         {
1983           type = VR_RANGE;
1984           min = max = build_int_cst (expr_type, 0);
1985         }
1986       /* If one of the operands is one, we know that the whole
1987          expression evaluates one.  */
1988       else if (code == TRUTH_OR_EXPR
1989                && ((vr0.type == VR_RANGE
1990                     && integer_onep (vr0.min)
1991                     && integer_onep (vr0.max))
1992                    || (vr1.type == VR_RANGE
1993                        && integer_onep (vr1.min)
1994                        && integer_onep (vr1.max))))
1995         {
1996           type = VR_RANGE;
1997           min = max = build_int_cst (expr_type, 1);
1998         }
1999       else if (vr0.type != VR_VARYING
2000                && vr1.type != VR_VARYING
2001                && vr0.type == vr1.type
2002                && !symbolic_range_p (&vr0)
2003                && !overflow_infinity_range_p (&vr0)
2004                && !symbolic_range_p (&vr1)
2005                && !overflow_infinity_range_p (&vr1))
2006         {
2007           /* Boolean expressions cannot be folded with int_const_binop.  */
2008           min = fold_binary (code, expr_type, vr0.min, vr1.min);
2009           max = fold_binary (code, expr_type, vr0.max, vr1.max);
2010         }
2011       else
2012         {
2013           /* The result of a TRUTH_*_EXPR is always true or false.  */
2014           set_value_range_to_truthvalue (vr, expr_type);
2015           return;
2016         }
2017     }
2018   else if (code == PLUS_EXPR
2019            || code == MIN_EXPR
2020            || code == MAX_EXPR)
2021     {
2022       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
2023          VR_VARYING.  It would take more effort to compute a precise
2024          range for such a case.  For example, if we have op0 == 1 and
2025          op1 == -1 with their ranges both being ~[0,0], we would have
2026          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
2027          Note that we are guaranteed to have vr0.type == vr1.type at
2028          this point.  */
2029       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
2030         {
2031           set_value_range_to_varying (vr);
2032           return;
2033         }
2034
2035       /* For operations that make the resulting range directly
2036          proportional to the original ranges, apply the operation to
2037          the same end of each range.  */
2038       min = vrp_int_const_binop (code, vr0.min, vr1.min);
2039       max = vrp_int_const_binop (code, vr0.max, vr1.max);
2040     }
2041   else if (code == MULT_EXPR
2042            || code == TRUNC_DIV_EXPR
2043            || code == FLOOR_DIV_EXPR
2044            || code == CEIL_DIV_EXPR
2045            || code == EXACT_DIV_EXPR
2046            || code == ROUND_DIV_EXPR
2047            || code == RSHIFT_EXPR)
2048     {
2049       tree val[4];
2050       size_t i;
2051       bool sop;
2052
2053       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
2054          drop to VR_VARYING.  It would take more effort to compute a
2055          precise range for such a case.  For example, if we have
2056          op0 == 65536 and op1 == 65536 with their ranges both being
2057          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
2058          we cannot claim that the product is in ~[0,0].  Note that we
2059          are guaranteed to have vr0.type == vr1.type at this
2060          point.  */
2061       if (code == MULT_EXPR
2062           && vr0.type == VR_ANTI_RANGE
2063           && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
2064         {
2065           set_value_range_to_varying (vr);
2066           return;
2067         }
2068
2069       /* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
2070          then drop to VR_VARYING.  Outside of this range we get undefined
2071          behavior from the shift operation.  We cannot even trust
2072          SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
2073          shifts, and the operation at the tree level may be widened.  */
2074       if (code == RSHIFT_EXPR)
2075         {
2076           if (vr1.type == VR_ANTI_RANGE
2077               || !vrp_expr_computes_nonnegative (op1, &sop)
2078               || (operand_less_p
2079                   (build_int_cst (TREE_TYPE (vr1.max),
2080                                   TYPE_PRECISION (expr_type) - 1),
2081                    vr1.max) != 0))
2082             {
2083               set_value_range_to_varying (vr);
2084               return;
2085             }
2086         }
2087
2088       /* Multiplications and divisions are a bit tricky to handle,
2089          depending on the mix of signs we have in the two ranges, we
2090          need to operate on different values to get the minimum and
2091          maximum values for the new range.  One approach is to figure
2092          out all the variations of range combinations and do the
2093          operations.
2094
2095          However, this involves several calls to compare_values and it
2096          is pretty convoluted.  It's simpler to do the 4 operations
2097          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
2098          MAX1) and then figure the smallest and largest values to form
2099          the new range.  */
2100
2101       /* Divisions by zero result in a VARYING value.  */
2102       else if (code != MULT_EXPR
2103                && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
2104         {
2105           set_value_range_to_varying (vr);
2106           return;
2107         }
2108
2109       /* Compute the 4 cross operations.  */
2110       sop = false;
2111       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
2112       if (val[0] == NULL_TREE)
2113         sop = true;
2114
2115       if (vr1.max == vr1.min)
2116         val[1] = NULL_TREE;
2117       else
2118         {
2119           val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
2120           if (val[1] == NULL_TREE)
2121             sop = true;
2122         }
2123
2124       if (vr0.max == vr0.min)
2125         val[2] = NULL_TREE;
2126       else
2127         {
2128           val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
2129           if (val[2] == NULL_TREE)
2130             sop = true;
2131         }
2132
2133       if (vr0.min == vr0.max || vr1.min == vr1.max)
2134         val[3] = NULL_TREE;
2135       else
2136         {
2137           val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
2138           if (val[3] == NULL_TREE)
2139             sop = true;
2140         }
2141
2142       if (sop)
2143         {
2144           set_value_range_to_varying (vr);
2145           return;
2146         }
2147
2148       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
2149          of VAL[i].  */
2150       min = val[0];
2151       max = val[0];
2152       for (i = 1; i < 4; i++)
2153         {
2154           if (!is_gimple_min_invariant (min)
2155               || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2156               || !is_gimple_min_invariant (max)
2157               || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2158             break;
2159
2160           if (val[i])
2161             {
2162               if (!is_gimple_min_invariant (val[i])
2163                   || (TREE_OVERFLOW (val[i])
2164                       && !is_overflow_infinity (val[i])))
2165                 {
2166                   /* If we found an overflowed value, set MIN and MAX
2167                      to it so that we set the resulting range to
2168                      VARYING.  */
2169                   min = max = val[i];
2170                   break;
2171                 }
2172
2173               if (compare_values (val[i], min) == -1)
2174                 min = val[i];
2175
2176               if (compare_values (val[i], max) == 1)
2177                 max = val[i];
2178             }
2179         }
2180     }
2181   else if (code == MINUS_EXPR)
2182     {
2183       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
2184          VR_VARYING.  It would take more effort to compute a precise
2185          range for such a case.  For example, if we have op0 == 1 and
2186          op1 == 1 with their ranges both being ~[0,0], we would have
2187          op0 - op1 == 0, so we cannot claim that the difference is in
2188          ~[0,0].  Note that we are guaranteed to have
2189          vr0.type == vr1.type at this point.  */
2190       if (vr0.type == VR_ANTI_RANGE)
2191         {
2192           set_value_range_to_varying (vr);
2193           return;
2194         }
2195
2196       /* For MINUS_EXPR, apply the operation to the opposite ends of
2197          each range.  */
2198       min = vrp_int_const_binop (code, vr0.min, vr1.max);
2199       max = vrp_int_const_binop (code, vr0.max, vr1.min);
2200     }
2201   else if (code == BIT_AND_EXPR)
2202     {
2203       if (vr0.type == VR_RANGE
2204           && vr0.min == vr0.max
2205           && TREE_CODE (vr0.max) == INTEGER_CST
2206           && !TREE_OVERFLOW (vr0.max)
2207           && tree_int_cst_sgn (vr0.max) >= 0)
2208         {
2209           min = build_int_cst (expr_type, 0);
2210           max = vr0.max;
2211         }
2212       else if (vr1.type == VR_RANGE
2213                && vr1.min == vr1.max
2214                && TREE_CODE (vr1.max) == INTEGER_CST
2215                && !TREE_OVERFLOW (vr1.max)
2216                && tree_int_cst_sgn (vr1.max) >= 0)
2217         {
2218           type = VR_RANGE;
2219           min = build_int_cst (expr_type, 0);
2220           max = vr1.max;
2221         }
2222       else
2223         {
2224           set_value_range_to_varying (vr);
2225           return;
2226         }
2227     }
2228   else
2229     gcc_unreachable ();
2230
2231   /* If either MIN or MAX overflowed, then set the resulting range to
2232      VARYING.  But we do accept an overflow infinity
2233      representation.  */
2234   if (min == NULL_TREE
2235       || !is_gimple_min_invariant (min)
2236       || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
2237       || max == NULL_TREE
2238       || !is_gimple_min_invariant (max)
2239       || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
2240     {
2241       set_value_range_to_varying (vr);
2242       return;
2243     }
2244
2245   /* We punt if:
2246      1) [-INF, +INF]
2247      2) [-INF, +-INF(OVF)]
2248      3) [+-INF(OVF), +INF]
2249      4) [+-INF(OVF), +-INF(OVF)]
2250      We learn nothing when we have INF and INF(OVF) on both sides.
2251      Note that we do accept [-INF, -INF] and [+INF, +INF] without
2252      overflow.  */
2253   if ((vrp_val_is_min (min) || is_overflow_infinity (min))
2254       && (vrp_val_is_max (max) || is_overflow_infinity (max)))
2255     {
2256       set_value_range_to_varying (vr);
2257       return;
2258     }
2259
2260   cmp = compare_values (min, max);
2261   if (cmp == -2 || cmp == 1)
2262     {
2263       /* If the new range has its limits swapped around (MIN > MAX),
2264          then the operation caused one of them to wrap around, mark
2265          the new range VARYING.  */
2266       set_value_range_to_varying (vr);
2267     }
2268   else
2269     set_value_range (vr, type, min, max, NULL);
2270 }
2271
2272
2273 /* Extract range information from a unary expression EXPR based on
2274    the range of its operand and the expression code.  */
2275
2276 static void
2277 extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
2278                                tree type, tree op0)
2279 {
2280   tree min, max;
2281   int cmp;
2282   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2283
2284   /* Refuse to operate on certain unary expressions for which we
2285      cannot easily determine a resulting range.  */
2286   if (code == FIX_TRUNC_EXPR
2287       || code == FLOAT_EXPR
2288       || code == BIT_NOT_EXPR
2289       || code == NON_LVALUE_EXPR
2290       || code == CONJ_EXPR)
2291     {
2292       set_value_range_to_varying (vr);
2293       return;
2294     }
2295
2296   /* Get value ranges for the operand.  For constant operands, create
2297      a new value range with the operand to simplify processing.  */
2298   if (TREE_CODE (op0) == SSA_NAME)
2299     vr0 = *(get_value_range (op0));
2300   else if (is_gimple_min_invariant (op0))
2301     set_value_range_to_value (&vr0, op0, NULL);
2302   else
2303     set_value_range_to_varying (&vr0);
2304
2305   /* If VR0 is UNDEFINED, so is the result.  */
2306   if (vr0.type == VR_UNDEFINED)
2307     {
2308       set_value_range_to_undefined (vr);
2309       return;
2310     }
2311
2312   /* Refuse to operate on symbolic ranges, or if neither operand is
2313      a pointer or integral type.  */
2314   if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
2315        && !POINTER_TYPE_P (TREE_TYPE (op0)))
2316       || (vr0.type != VR_VARYING
2317           && symbolic_range_p (&vr0)))
2318     {
2319       set_value_range_to_varying (vr);
2320       return;
2321     }
2322
2323   /* If the expression involves pointers, we are only interested in
2324      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
2325   if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
2326     {
2327       bool sop;
2328
2329       sop = false;
2330       if (range_is_nonnull (&vr0)
2331           || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
2332               && !sop))
2333         set_value_range_to_nonnull (vr, type);
2334       else if (range_is_null (&vr0))
2335         set_value_range_to_null (vr, type);
2336       else
2337         set_value_range_to_varying (vr);
2338
2339       return;
2340     }
2341
2342   /* Handle unary expressions on integer ranges.  */
2343   if (code == NOP_EXPR || code == CONVERT_EXPR)
2344     {
2345       tree inner_type = TREE_TYPE (op0);
2346       tree outer_type = type;
2347
2348       /* If VR0 represents a simple range, then try to convert
2349          the min and max values for the range to the same type
2350          as OUTER_TYPE.  If the results compare equal to VR0's
2351          min and max values and the new min is still less than
2352          or equal to the new max, then we can safely use the newly
2353          computed range for EXPR.  This allows us to compute
2354          accurate ranges through many casts.  */
2355       if ((vr0.type == VR_RANGE
2356            && !overflow_infinity_range_p (&vr0))
2357           || (vr0.type == VR_VARYING
2358               && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
2359         {
2360           tree new_min, new_max, orig_min, orig_max;
2361
2362           /* Convert the input operand min/max to OUTER_TYPE.   If
2363              the input has no range information, then use the min/max
2364              for the input's type.  */
2365           if (vr0.type == VR_RANGE)
2366             {
2367               orig_min = vr0.min;
2368               orig_max = vr0.max;
2369             }
2370           else
2371             {
2372               orig_min = TYPE_MIN_VALUE (inner_type);
2373               orig_max = TYPE_MAX_VALUE (inner_type);
2374             }
2375
2376           new_min = fold_convert (outer_type, orig_min);
2377           new_max = fold_convert (outer_type, orig_max);
2378
2379           /* Verify the new min/max values are gimple values and
2380              that they compare equal to the original input's
2381              min/max values.  */
2382           if (is_gimple_val (new_min)
2383               && is_gimple_val (new_max)
2384               && tree_int_cst_equal (new_min, orig_min)
2385               && tree_int_cst_equal (new_max, orig_max)
2386               && (!is_overflow_infinity (new_min)
2387                   || !is_overflow_infinity (new_max))
2388               && (cmp = compare_values (new_min, new_max)) <= 0
2389               && cmp >= -1)
2390             {
2391               set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
2392               return;
2393             }
2394         }
2395
2396       /* When converting types of different sizes, set the result to
2397          VARYING.  Things like sign extensions and precision loss may
2398          change the range.  For instance, if x_3 is of type 'long long
2399          int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
2400          is impossible to know at compile time whether y_5 will be
2401          ~[0, 0].  */
2402       if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
2403           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
2404         {
2405           set_value_range_to_varying (vr);
2406           return;
2407         }
2408     }
2409
2410   /* Conversion of a VR_VARYING value to a wider type can result
2411      in a usable range.  So wait until after we've handled conversions
2412      before dropping the result to VR_VARYING if we had a source
2413      operand that is VR_VARYING.  */
2414   if (vr0.type == VR_VARYING)
2415     {
2416       set_value_range_to_varying (vr);
2417       return;
2418     }
2419
2420   /* Apply the operation to each end of the range and see what we end
2421      up with.  */
2422   if (code == NEGATE_EXPR
2423       && !TYPE_UNSIGNED (type))
2424     {
2425       /* NEGATE_EXPR flips the range around.  We need to treat
2426          TYPE_MIN_VALUE specially.  */
2427       if (is_positive_overflow_infinity (vr0.max))
2428         min = negative_overflow_infinity (type);
2429       else if (is_negative_overflow_infinity (vr0.max))
2430         min = positive_overflow_infinity (type);
2431       else if (!vrp_val_is_min (vr0.max))
2432         min = fold_unary_to_constant (code, type, vr0.max);
2433       else if (needs_overflow_infinity (type))
2434         {
2435           if (supports_overflow_infinity (type)
2436               && !is_overflow_infinity (vr0.min)
2437               && !vrp_val_is_min (vr0.min))
2438             min = positive_overflow_infinity (type);
2439           else
2440             {
2441               set_value_range_to_varying (vr);
2442               return;
2443             }
2444         }
2445       else
2446         min = TYPE_MIN_VALUE (type);
2447
2448       if (is_positive_overflow_infinity (vr0.min))
2449         max = negative_overflow_infinity (type);
2450       else if (is_negative_overflow_infinity (vr0.min))
2451         max = positive_overflow_infinity (type);
2452       else if (!vrp_val_is_min (vr0.min))
2453         max = fold_unary_to_constant (code, type, vr0.min);
2454       else if (needs_overflow_infinity (type))
2455         {
2456           if (supports_overflow_infinity (type))
2457             max = positive_overflow_infinity (type);
2458           else
2459             {
2460               set_value_range_to_varying (vr);
2461               return;
2462             }
2463         }
2464       else
2465         max = TYPE_MIN_VALUE (type);
2466     }
2467   else if (code == NEGATE_EXPR
2468            && TYPE_UNSIGNED (type))
2469     {
2470       if (!range_includes_zero_p (&vr0))
2471         {
2472           max = fold_unary_to_constant (code, type, vr0.min);
2473           min = fold_unary_to_constant (code, type, vr0.max);
2474         }
2475       else
2476         {
2477           if (range_is_null (&vr0))
2478             set_value_range_to_null (vr, type);
2479           else
2480             set_value_range_to_varying (vr);
2481           return;
2482         }
2483     }
2484   else if (code == ABS_EXPR
2485            && !TYPE_UNSIGNED (type))
2486     {
2487       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
2488          useful range.  */
2489       if (!TYPE_OVERFLOW_UNDEFINED (type)
2490           && ((vr0.type == VR_RANGE
2491                && vrp_val_is_min (vr0.min))
2492               || (vr0.type == VR_ANTI_RANGE
2493                   && !vrp_val_is_min (vr0.min)
2494                   && !range_includes_zero_p (&vr0))))
2495         {
2496           set_value_range_to_varying (vr);
2497           return;
2498         }
2499
2500       /* ABS_EXPR may flip the range around, if the original range
2501          included negative values.  */
2502       if (is_overflow_infinity (vr0.min))
2503         min = positive_overflow_infinity (type);
2504       else if (!vrp_val_is_min (vr0.min))
2505         min = fold_unary_to_constant (code, type, vr0.min);
2506       else if (!needs_overflow_infinity (type))
2507         min = TYPE_MAX_VALUE (type);
2508       else if (supports_overflow_infinity (type))
2509         min = positive_overflow_infinity (type);
2510       else
2511         {
2512           set_value_range_to_varying (vr);
2513           return;
2514         }
2515
2516       if (is_overflow_infinity (vr0.max))
2517         max = positive_overflow_infinity (type);
2518       else if (!vrp_val_is_min (vr0.max))
2519         max = fold_unary_to_constant (code, type, vr0.max);
2520       else if (!needs_overflow_infinity (type))
2521         max = TYPE_MAX_VALUE (type);
2522       else if (supports_overflow_infinity (type))
2523         max = positive_overflow_infinity (type);
2524       else
2525         {
2526           set_value_range_to_varying (vr);
2527           return;
2528         }
2529
2530       cmp = compare_values (min, max);
2531
2532       /* If a VR_ANTI_RANGEs contains zero, then we have
2533          ~[-INF, min(MIN, MAX)].  */
2534       if (vr0.type == VR_ANTI_RANGE)
2535         {
2536           if (range_includes_zero_p (&vr0))
2537             {
2538               /* Take the lower of the two values.  */
2539               if (cmp != 1)
2540                 max = min;
2541
2542               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
2543                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
2544                  flag_wrapv is set and the original anti-range doesn't include
2545                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
2546               if (TYPE_OVERFLOW_WRAPS (type))
2547                 {
2548                   tree type_min_value = TYPE_MIN_VALUE (type);
2549
2550                   min = (vr0.min != type_min_value
2551                          ? int_const_binop (PLUS_EXPR, type_min_value,
2552                                             integer_one_node, 0)
2553                          : type_min_value);
2554                 }
2555               else
2556                 {
2557                   if (overflow_infinity_range_p (&vr0))
2558                     min = negative_overflow_infinity (type);
2559                   else
2560                     min = TYPE_MIN_VALUE (type);
2561                 }
2562             }
2563           else
2564             {
2565               /* All else has failed, so create the range [0, INF], even for
2566                  flag_wrapv since TYPE_MIN_VALUE is in the original
2567                  anti-range.  */
2568               vr0.type = VR_RANGE;
2569               min = build_int_cst (type, 0);
2570               if (needs_overflow_infinity (type))
2571                 {
2572                   if (supports_overflow_infinity (type))
2573                     max = positive_overflow_infinity (type);
2574                   else
2575                     {
2576                       set_value_range_to_varying (vr);
2577                       return;
2578                     }
2579                 }
2580               else
2581                 max = TYPE_MAX_VALUE (type);
2582             }
2583         }
2584
2585       /* If the range contains zero then we know that the minimum value in the
2586          range will be zero.  */
2587       else if (range_includes_zero_p (&vr0))
2588         {
2589           if (cmp == 1)
2590             max = min;
2591           min = build_int_cst (type, 0);
2592         }
2593       else
2594         {
2595           /* If the range was reversed, swap MIN and MAX.  */
2596           if (cmp == 1)
2597             {
2598               tree t = min;
2599               min = max;
2600               max = t;
2601             }
2602         }
2603     }
2604   else
2605     {
2606       /* Otherwise, operate on each end of the range.  */
2607       min = fold_unary_to_constant (code, type, vr0.min);
2608       max = fold_unary_to_constant (code, type, vr0.max);
2609
2610       if (needs_overflow_infinity (type))
2611         {
2612           gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
2613
2614           /* If both sides have overflowed, we don't know
2615              anything.  */
2616           if ((is_overflow_infinity (vr0.min)
2617                || TREE_OVERFLOW (min))
2618               && (is_overflow_infinity (vr0.max)
2619                   || TREE_OVERFLOW (max)))
2620             {
2621               set_value_range_to_varying (vr);
2622               return;
2623             }
2624
2625           if (is_overflow_infinity (vr0.min))
2626             min = vr0.min;
2627           else if (TREE_OVERFLOW (min))
2628             {
2629               if (supports_overflow_infinity (type))
2630                 min = (tree_int_cst_sgn (min) >= 0
2631                        ? positive_overflow_infinity (TREE_TYPE (min))
2632                        : negative_overflow_infinity (TREE_TYPE (min)));
2633               else
2634                 {
2635                   set_value_range_to_varying (vr);
2636                   return;
2637                 }
2638             }
2639
2640           if (is_overflow_infinity (vr0.max))
2641             max = vr0.max;
2642           else if (TREE_OVERFLOW (max))
2643             {
2644               if (supports_overflow_infinity (type))
2645                 max = (tree_int_cst_sgn (max) >= 0
2646                        ? positive_overflow_infinity (TREE_TYPE (max))
2647                        : negative_overflow_infinity (TREE_TYPE (max)));
2648               else
2649                 {
2650                   set_value_range_to_varying (vr);
2651                   return;
2652                 }
2653             }
2654         }
2655     }
2656
2657   cmp = compare_values (min, max);
2658   if (cmp == -2 || cmp == 1)
2659     {
2660       /* If the new range has its limits swapped around (MIN > MAX),
2661          then the operation caused one of them to wrap around, mark
2662          the new range VARYING.  */
2663       set_value_range_to_varying (vr);
2664     }
2665   else
2666     set_value_range (vr, vr0.type, min, max, NULL);
2667 }
2668
2669
2670 /* Extract range information from a conditional expression EXPR based on
2671    the ranges of each of its operands and the expression code.  */
2672
2673 static void
2674 extract_range_from_cond_expr (value_range_t *vr, tree expr)
2675 {
2676   tree op0, op1;
2677   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2678   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
2679
2680   /* Get value ranges for each operand.  For constant operands, create
2681      a new value range with the operand to simplify processing.  */
2682   op0 = COND_EXPR_THEN (expr);
2683   if (TREE_CODE (op0) == SSA_NAME)
2684     vr0 = *(get_value_range (op0));
2685   else if (is_gimple_min_invariant (op0))
2686     set_value_range_to_value (&vr0, op0, NULL);
2687   else
2688     set_value_range_to_varying (&vr0);
2689
2690   op1 = COND_EXPR_ELSE (expr);
2691   if (TREE_CODE (op1) == SSA_NAME)
2692     vr1 = *(get_value_range (op1));
2693   else if (is_gimple_min_invariant (op1))
2694     set_value_range_to_value (&vr1, op1, NULL);
2695   else
2696     set_value_range_to_varying (&vr1);
2697
2698   /* The resulting value range is the union of the operand ranges */
2699   vrp_meet (&vr0, &vr1);
2700   copy_value_range (vr, &vr0);
2701 }
2702
2703
2704 /* Extract range information from a comparison expression EXPR based
2705    on the range of its operand and the expression code.  */
2706
2707 static void
2708 extract_range_from_comparison (value_range_t *vr, enum tree_code code,
2709                                tree type, tree op0, tree op1)
2710 {
2711   bool sop = false;
2712   tree val = vrp_evaluate_conditional_warnv_with_ops (code,
2713                                                       op0,
2714                                                       op1,
2715                                                       false, &sop);
2716
2717   /* A disadvantage of using a special infinity as an overflow
2718      representation is that we lose the ability to record overflow
2719      when we don't have an infinity.  So we have to ignore a result
2720      which relies on overflow.  */
2721
2722   if (val && !is_overflow_infinity (val) && !sop)
2723     {
2724       /* Since this expression was found on the RHS of an assignment,
2725          its type may be different from _Bool.  Convert VAL to EXPR's
2726          type.  */
2727       val = fold_convert (type, val);
2728       if (is_gimple_min_invariant (val))
2729         set_value_range_to_value (vr, val, vr->equiv);
2730       else
2731         set_value_range (vr, VR_RANGE, val, val, vr->equiv);
2732     }
2733   else
2734     /* The result of a comparison is always true or false.  */
2735     set_value_range_to_truthvalue (vr, type);
2736 }
2737
2738
2739 /* Try to compute a useful range out of expression EXPR and store it
2740    in *VR.  */
2741
2742 static void
2743 extract_range_from_expr (value_range_t *vr, tree expr)
2744 {
2745   enum tree_code code = TREE_CODE (expr);
2746
2747   if (code == ASSERT_EXPR)
2748     extract_range_from_assert (vr, expr);
2749   else if (code == SSA_NAME)
2750     extract_range_from_ssa_name (vr, expr);
2751   else if (TREE_CODE_CLASS (code) == tcc_binary
2752            || code == TRUTH_ANDIF_EXPR
2753            || code == TRUTH_ORIF_EXPR
2754            || code == TRUTH_AND_EXPR
2755            || code == TRUTH_OR_EXPR
2756            || code == TRUTH_XOR_EXPR)
2757     extract_range_from_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
2758                                     TREE_OPERAND (expr, 0),
2759                                     TREE_OPERAND (expr, 1));
2760   else if (TREE_CODE_CLASS (code) == tcc_unary)
2761     extract_range_from_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
2762                                    TREE_OPERAND (expr, 0));
2763   else if (code == COND_EXPR)
2764     extract_range_from_cond_expr (vr, expr);
2765   else if (TREE_CODE_CLASS (code) == tcc_comparison)
2766     extract_range_from_comparison (vr, TREE_CODE (expr), TREE_TYPE (expr),
2767                                    TREE_OPERAND (expr, 0),
2768                                    TREE_OPERAND (expr, 1));
2769   else if (is_gimple_min_invariant (expr))
2770     set_value_range_to_value (vr, expr, NULL);
2771   else
2772     set_value_range_to_varying (vr);
2773
2774   /* If we got a varying range from the tests above, try a final
2775      time to derive a nonnegative or nonzero range.  This time
2776      relying primarily on generic routines in fold in conjunction
2777      with range data.  */
2778   if (vr->type == VR_VARYING)
2779     {
2780       bool sop = false;
2781
2782       if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
2783           && vrp_expr_computes_nonnegative (expr, &sop))
2784         set_value_range_to_nonnegative (vr, TREE_TYPE (expr),
2785                                         sop || is_overflow_infinity (expr));
2786       else if (vrp_expr_computes_nonzero (expr, &sop)
2787                && !sop)
2788         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
2789     }
2790 }
2791
2792 /* Given a range VR, a LOOP and a variable VAR, determine whether it
2793    would be profitable to adjust VR using scalar evolution information
2794    for VAR.  If so, update VR with the new limits.  */
2795
2796 static void
2797 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
2798                         tree var)
2799 {
2800   tree init, step, chrec, tmin, tmax, min, max, type;
2801   enum ev_direction dir;
2802
2803   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
2804      better opportunities than a regular range, but I'm not sure.  */
2805   if (vr->type == VR_ANTI_RANGE)
2806     return;
2807
2808   /* Ensure that there are not values in the scev cache based on assumptions
2809      on ranges of ssa names that were changed
2810      (in set_value_range/set_value_range_to_varying).  Preserve cached numbers
2811      of iterations, that were computed before the start of VRP (we do not
2812      recompute these each time to save the compile time).  */
2813   scev_reset_except_niters ();
2814
2815   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
2816
2817   /* Like in PR19590, scev can return a constant function.  */
2818   if (is_gimple_min_invariant (chrec))
2819     {
2820       set_value_range_to_value (vr, chrec, vr->equiv);
2821       return;
2822     }
2823
2824   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2825     return;
2826
2827   init = initial_condition_in_loop_num (chrec, loop->num);
2828   step = evolution_part_in_loop_num (chrec, loop->num);
2829
2830   /* If STEP is symbolic, we can't know whether INIT will be the
2831      minimum or maximum value in the range.  Also, unless INIT is
2832      a simple expression, compare_values and possibly other functions
2833      in tree-vrp won't be able to handle it.  */
2834   if (step == NULL_TREE
2835       || !is_gimple_min_invariant (step)
2836       || !valid_value_p (init))
2837     return;
2838
2839   dir = scev_direction (chrec);
2840   if (/* Do not adjust ranges if we do not know whether the iv increases
2841          or decreases,  ... */
2842       dir == EV_DIR_UNKNOWN
2843       /* ... or if it may wrap.  */
2844       || scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
2845                                 true))
2846     return;
2847
2848   /* We use TYPE_MIN_VALUE and TYPE_MAX_VALUE here instead of
2849      negative_overflow_infinity and positive_overflow_infinity,
2850      because we have concluded that the loop probably does not
2851      wrap.  */
2852
2853   type = TREE_TYPE (var);
2854   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
2855     tmin = lower_bound_in_type (type, type);
2856   else
2857     tmin = TYPE_MIN_VALUE (type);
2858   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
2859     tmax = upper_bound_in_type (type, type);
2860   else
2861     tmax = TYPE_MAX_VALUE (type);
2862
2863   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2864     {
2865       min = tmin;
2866       max = tmax;
2867
2868       /* For VARYING or UNDEFINED ranges, just about anything we get
2869          from scalar evolutions should be better.  */
2870
2871       if (dir == EV_DIR_DECREASES)
2872         max = init;
2873       else
2874         min = init;
2875
2876       /* If we would create an invalid range, then just assume we
2877          know absolutely nothing.  This may be over-conservative,
2878          but it's clearly safe, and should happen only in unreachable
2879          parts of code, or for invalid programs.  */
2880       if (compare_values (min, max) == 1)
2881         return;
2882
2883       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2884     }
2885   else if (vr->type == VR_RANGE)
2886     {
2887       min = vr->min;
2888       max = vr->max;
2889
2890       if (dir == EV_DIR_DECREASES)
2891         {
2892           /* INIT is the maximum value.  If INIT is lower than VR->MAX
2893              but no smaller than VR->MIN, set VR->MAX to INIT.  */
2894           if (compare_values (init, max) == -1)
2895             {
2896               max = init;
2897
2898               /* If we just created an invalid range with the minimum
2899                  greater than the maximum, we fail conservatively.
2900                  This should happen only in unreachable
2901                  parts of code, or for invalid programs.  */
2902               if (compare_values (min, max) == 1)
2903                 return;
2904             }
2905
2906           /* According to the loop information, the variable does not
2907              overflow.  If we think it does, probably because of an
2908              overflow due to arithmetic on a different INF value,
2909              reset now.  */
2910           if (is_negative_overflow_infinity (min))
2911             min = tmin;
2912         }
2913       else
2914         {
2915           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
2916           if (compare_values (init, min) == 1)
2917             {
2918               min = init;
2919
2920               /* Again, avoid creating invalid range by failing.  */
2921               if (compare_values (min, max) == 1)
2922                 return;
2923             }
2924
2925           if (is_positive_overflow_infinity (max))
2926             max = tmax;
2927         }
2928
2929       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2930     }
2931 }
2932
2933 /* Return true if VAR may overflow at STMT.  This checks any available
2934    loop information to see if we can determine that VAR does not
2935    overflow.  */
2936
2937 static bool
2938 vrp_var_may_overflow (tree var, tree stmt)
2939 {
2940   struct loop *l;
2941   tree chrec, init, step;
2942
2943   if (current_loops == NULL)
2944     return true;
2945
2946   l = loop_containing_stmt (stmt);
2947   if (l == NULL)
2948     return true;
2949
2950   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
2951   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2952     return true;
2953
2954   init = initial_condition_in_loop_num (chrec, l->num);
2955   step = evolution_part_in_loop_num (chrec, l->num);
2956
2957   if (step == NULL_TREE
2958       || !is_gimple_min_invariant (step)
2959       || !valid_value_p (init))
2960     return true;
2961
2962   /* If we get here, we know something useful about VAR based on the
2963      loop information.  If it wraps, it may overflow.  */
2964
2965   if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
2966                              true))
2967     return true;
2968
2969   if (dump_file && (dump_flags & TDF_DETAILS) != 0)
2970     {
2971       print_generic_expr (dump_file, var, 0);
2972       fprintf (dump_file, ": loop information indicates does not overflow\n");
2973     }
2974
2975   return false;
2976 }
2977
2978
2979 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2980
2981    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2982      all the values in the ranges.
2983
2984    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2985
2986    - Return NULL_TREE if it is not always possible to determine the
2987      value of the comparison.
2988
2989    Also set *STRICT_OVERFLOW_P to indicate whether a range with an
2990    overflow infinity was used in the test.  */
2991
2992
2993 static tree
2994 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1,
2995                 bool *strict_overflow_p)
2996 {
2997   /* VARYING or UNDEFINED ranges cannot be compared.  */
2998   if (vr0->type == VR_VARYING
2999       || vr0->type == VR_UNDEFINED
3000       || vr1->type == VR_VARYING
3001       || vr1->type == VR_UNDEFINED)
3002     return NULL_TREE;
3003
3004   /* Anti-ranges need to be handled separately.  */
3005   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
3006     {
3007       /* If both are anti-ranges, then we cannot compute any
3008          comparison.  */
3009       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3010         return NULL_TREE;
3011
3012       /* These comparisons are never statically computable.  */
3013       if (comp == GT_EXPR
3014           || comp == GE_EXPR
3015           || comp == LT_EXPR
3016           || comp == LE_EXPR)
3017         return NULL_TREE;
3018
3019       /* Equality can be computed only between a range and an
3020          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
3021       if (vr0->type == VR_RANGE)
3022         {
3023           /* To simplify processing, make VR0 the anti-range.  */
3024           value_range_t *tmp = vr0;
3025           vr0 = vr1;
3026           vr1 = tmp;
3027         }
3028
3029       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
3030
3031       if (compare_values_warnv (vr0->min, vr1->min, strict_overflow_p) == 0
3032           && compare_values_warnv (vr0->max, vr1->max, strict_overflow_p) == 0)
3033         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3034
3035       return NULL_TREE;
3036     }
3037
3038   if (!usable_range_p (vr0, strict_overflow_p)
3039       || !usable_range_p (vr1, strict_overflow_p))
3040     return NULL_TREE;
3041
3042   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
3043      operands around and change the comparison code.  */
3044   if (comp == GT_EXPR || comp == GE_EXPR)
3045     {
3046       value_range_t *tmp;
3047       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
3048       tmp = vr0;
3049       vr0 = vr1;
3050       vr1 = tmp;
3051     }
3052
3053   if (comp == EQ_EXPR)
3054     {
3055       /* Equality may only be computed if both ranges represent
3056          exactly one value.  */
3057       if (compare_values_warnv (vr0->min, vr0->max, strict_overflow_p) == 0
3058           && compare_values_warnv (vr1->min, vr1->max, strict_overflow_p) == 0)
3059         {
3060           int cmp_min = compare_values_warnv (vr0->min, vr1->min,
3061                                               strict_overflow_p);
3062           int cmp_max = compare_values_warnv (vr0->max, vr1->max,
3063                                               strict_overflow_p);
3064           if (cmp_min == 0 && cmp_max == 0)
3065             return boolean_true_node;
3066           else if (cmp_min != -2 && cmp_max != -2)
3067             return boolean_false_node;
3068         }
3069       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
3070       else if (compare_values_warnv (vr0->min, vr1->max,
3071                                      strict_overflow_p) == 1
3072                || compare_values_warnv (vr1->min, vr0->max,
3073                                         strict_overflow_p) == 1)
3074         return boolean_false_node;
3075
3076       return NULL_TREE;
3077     }
3078   else if (comp == NE_EXPR)
3079     {
3080       int cmp1, cmp2;
3081
3082       /* If VR0 is completely to the left or completely to the right
3083          of VR1, they are always different.  Notice that we need to
3084          make sure that both comparisons yield similar results to
3085          avoid comparing values that cannot be compared at
3086          compile-time.  */
3087       cmp1 = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3088       cmp2 = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3089       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
3090         return boolean_true_node;
3091
3092       /* If VR0 and VR1 represent a single value and are identical,
3093          return false.  */
3094       else if (compare_values_warnv (vr0->min, vr0->max,
3095                                      strict_overflow_p) == 0
3096                && compare_values_warnv (vr1->min, vr1->max,
3097                                         strict_overflow_p) == 0
3098                && compare_values_warnv (vr0->min, vr1->min,
3099                                         strict_overflow_p) == 0
3100                && compare_values_warnv (vr0->max, vr1->max,
3101                                         strict_overflow_p) == 0)
3102         return boolean_false_node;
3103
3104       /* Otherwise, they may or may not be different.  */
3105       else
3106         return NULL_TREE;
3107     }
3108   else if (comp == LT_EXPR || comp == LE_EXPR)
3109     {
3110       int tst;
3111
3112       /* If VR0 is to the left of VR1, return true.  */
3113       tst = compare_values_warnv (vr0->max, vr1->min, strict_overflow_p);
3114       if ((comp == LT_EXPR && tst == -1)
3115           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3116         {
3117           if (overflow_infinity_range_p (vr0)
3118               || overflow_infinity_range_p (vr1))
3119             *strict_overflow_p = true;
3120           return boolean_true_node;
3121         }
3122
3123       /* If VR0 is to the right of VR1, return false.  */
3124       tst = compare_values_warnv (vr0->min, vr1->max, strict_overflow_p);
3125       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3126           || (comp == LE_EXPR && tst == 1))
3127         {
3128           if (overflow_infinity_range_p (vr0)
3129               || overflow_infinity_range_p (vr1))
3130             *strict_overflow_p = true;
3131           return boolean_false_node;
3132         }
3133
3134       /* Otherwise, we don't know.  */
3135       return NULL_TREE;
3136     }
3137
3138   gcc_unreachable ();
3139 }
3140
3141
3142 /* Given a value range VR, a value VAL and a comparison code COMP, return
3143    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
3144    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
3145    always returns false.  Return NULL_TREE if it is not always
3146    possible to determine the value of the comparison.  Also set
3147    *STRICT_OVERFLOW_P to indicate whether a range with an overflow
3148    infinity was used in the test.  */
3149
3150 static tree
3151 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val,
3152                           bool *strict_overflow_p)
3153 {
3154   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
3155     return NULL_TREE;
3156
3157   /* Anti-ranges need to be handled separately.  */
3158   if (vr->type == VR_ANTI_RANGE)
3159     {
3160       /* For anti-ranges, the only predicates that we can compute at
3161          compile time are equality and inequality.  */
3162       if (comp == GT_EXPR
3163           || comp == GE_EXPR
3164           || comp == LT_EXPR
3165           || comp == LE_EXPR)
3166         return NULL_TREE;
3167
3168       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
3169       if (value_inside_range (val, vr) == 1)
3170         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
3171
3172       return NULL_TREE;
3173     }
3174
3175   if (!usable_range_p (vr, strict_overflow_p))
3176     return NULL_TREE;
3177
3178   if (comp == EQ_EXPR)
3179     {
3180       /* EQ_EXPR may only be computed if VR represents exactly
3181          one value.  */
3182       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0)
3183         {
3184           int cmp = compare_values_warnv (vr->min, val, strict_overflow_p);
3185           if (cmp == 0)
3186             return boolean_true_node;
3187           else if (cmp == -1 || cmp == 1 || cmp == 2)
3188             return boolean_false_node;
3189         }
3190       else if (compare_values_warnv (val, vr->min, strict_overflow_p) == -1
3191                || compare_values_warnv (vr->max, val, strict_overflow_p) == -1)
3192         return boolean_false_node;
3193
3194       return NULL_TREE;
3195     }
3196   else if (comp == NE_EXPR)
3197     {
3198       /* If VAL is not inside VR, then they are always different.  */
3199       if (compare_values_warnv (vr->max, val, strict_overflow_p) == -1
3200           || compare_values_warnv (vr->min, val, strict_overflow_p) == 1)
3201         return boolean_true_node;
3202
3203       /* If VR represents exactly one value equal to VAL, then return
3204          false.  */
3205       if (compare_values_warnv (vr->min, vr->max, strict_overflow_p) == 0
3206           && compare_values_warnv (vr->min, val, strict_overflow_p) == 0)
3207         return boolean_false_node;
3208
3209       /* Otherwise, they may or may not be different.  */
3210       return NULL_TREE;
3211     }
3212   else if (comp == LT_EXPR || comp == LE_EXPR)
3213     {
3214       int tst;
3215
3216       /* If VR is to the left of VAL, return true.  */
3217       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3218       if ((comp == LT_EXPR && tst == -1)
3219           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
3220         {
3221           if (overflow_infinity_range_p (vr))
3222             *strict_overflow_p = true;
3223           return boolean_true_node;
3224         }
3225
3226       /* If VR is to the right of VAL, return false.  */
3227       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3228       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
3229           || (comp == LE_EXPR && tst == 1))
3230         {
3231           if (overflow_infinity_range_p (vr))
3232             *strict_overflow_p = true;
3233           return boolean_false_node;
3234         }
3235
3236       /* Otherwise, we don't know.  */
3237       return NULL_TREE;
3238     }
3239   else if (comp == GT_EXPR || comp == GE_EXPR)
3240     {
3241       int tst;
3242
3243       /* If VR is to the right of VAL, return true.  */
3244       tst = compare_values_warnv (vr->min, val, strict_overflow_p);
3245       if ((comp == GT_EXPR && tst == 1)
3246           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
3247         {
3248           if (overflow_infinity_range_p (vr))
3249             *strict_overflow_p = true;
3250           return boolean_true_node;
3251         }
3252
3253       /* If VR is to the left of VAL, return false.  */
3254       tst = compare_values_warnv (vr->max, val, strict_overflow_p);
3255       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
3256           || (comp == GE_EXPR && tst == -1))
3257         {
3258           if (overflow_infinity_range_p (vr))
3259             *strict_overflow_p = true;
3260           return boolean_false_node;
3261         }
3262
3263       /* Otherwise, we don't know.  */
3264       return NULL_TREE;
3265     }
3266
3267   gcc_unreachable ();
3268 }
3269
3270
3271 /* Debugging dumps.  */
3272
3273 void dump_value_range (FILE *, value_range_t *);
3274 void debug_value_range (value_range_t *);
3275 void dump_all_value_ranges (FILE *);
3276 void debug_all_value_ranges (void);
3277 void dump_vr_equiv (FILE *, bitmap);
3278 void debug_vr_equiv (bitmap);
3279
3280
3281 /* Dump value range VR to FILE.  */
3282
3283 void
3284 dump_value_range (FILE *file, value_range_t *vr)
3285 {
3286   if (vr == NULL)
3287     fprintf (file, "[]");
3288   else if (vr->type == VR_UNDEFINED)
3289     fprintf (file, "UNDEFINED");
3290   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
3291     {
3292       tree type = TREE_TYPE (vr->min);
3293
3294       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
3295
3296       if (is_negative_overflow_infinity (vr->min))
3297         fprintf (file, "-INF(OVF)");
3298       else if (INTEGRAL_TYPE_P (type)
3299                && !TYPE_UNSIGNED (type)
3300                && vrp_val_is_min (vr->min))
3301         fprintf (file, "-INF");
3302       else
3303         print_generic_expr (file, vr->min, 0);
3304
3305       fprintf (file, ", ");
3306
3307       if (is_positive_overflow_infinity (vr->max))
3308         fprintf (file, "+INF(OVF)");
3309       else if (INTEGRAL_TYPE_P (type)
3310                && vrp_val_is_max (vr->max))
3311         fprintf (file, "+INF");
3312       else
3313         print_generic_expr (file, vr->max, 0);
3314
3315       fprintf (file, "]");
3316
3317       if (vr->equiv)
3318         {
3319           bitmap_iterator bi;
3320           unsigned i, c = 0;
3321
3322           fprintf (file, "  EQUIVALENCES: { ");
3323
3324           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
3325             {
3326               print_generic_expr (file, ssa_name (i), 0);
3327               fprintf (file, " ");
3328               c++;
3329             }
3330
3331           fprintf (file, "} (%u elements)", c);
3332         }
3333     }
3334   else if (vr->type == VR_VARYING)
3335     fprintf (file, "VARYING");
3336   else
3337     fprintf (file, "INVALID RANGE");
3338 }
3339
3340
3341 /* Dump value range VR to stderr.  */
3342
3343 void
3344 debug_value_range (value_range_t *vr)
3345 {
3346   dump_value_range (stderr, vr);
3347   fprintf (stderr, "\n");
3348 }
3349
3350
3351 /* Dump value ranges of all SSA_NAMEs to FILE.  */
3352
3353 void
3354 dump_all_value_ranges (FILE *file)
3355 {
3356   size_t i;
3357
3358   for (i = 0; i < num_ssa_names; i++)
3359     {
3360       if (vr_value[i])
3361         {
3362           print_generic_expr (file, ssa_name (i), 0);
3363           fprintf (file, ": ");
3364           dump_value_range (file, vr_value[i]);
3365           fprintf (file, "\n");
3366         }
3367     }
3368
3369   fprintf (file, "\n");
3370 }
3371
3372
3373 /* Dump all value ranges to stderr.  */
3374
3375 void
3376 debug_all_value_ranges (void)
3377 {
3378   dump_all_value_ranges (stderr);
3379 }
3380
3381
3382 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
3383    create a new SSA name N and return the assertion assignment
3384    'V = ASSERT_EXPR <V, V OP W>'.  */
3385
3386 static tree
3387 build_assert_expr_for (tree cond, tree v)
3388 {
3389   tree n, assertion;
3390
3391   gcc_assert (TREE_CODE (v) == SSA_NAME);
3392   n = duplicate_ssa_name (v, NULL_TREE);
3393
3394   if (COMPARISON_CLASS_P (cond))
3395     {
3396       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
3397       assertion = build_gimple_modify_stmt (n, a);
3398     }
3399   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
3400     {
3401       /* Given !V, build the assignment N = false.  */
3402       tree op0 = TREE_OPERAND (cond, 0);
3403       gcc_assert (op0 == v);
3404       assertion = build_gimple_modify_stmt (n, boolean_false_node);
3405     }
3406   else if (TREE_CODE (cond) == SSA_NAME)
3407     {
3408       /* Given V, build the assignment N = true.  */
3409       gcc_assert (v == cond);
3410       assertion = build_gimple_modify_stmt (n, boolean_true_node);
3411     }
3412   else
3413     gcc_unreachable ();
3414
3415   SSA_NAME_DEF_STMT (n) = assertion;
3416
3417   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
3418      operand of the ASSERT_EXPR. Register the new name and the old one
3419      in the replacement table so that we can fix the SSA web after
3420      adding all the ASSERT_EXPRs.  */
3421   register_new_name_mapping (n, v);
3422
3423   return assertion;
3424 }
3425
3426
3427 /* Return false if EXPR is a predicate expression involving floating
3428    point values.  */
3429
3430 static inline bool
3431 fp_predicate (const_tree expr)
3432 {
3433   return (COMPARISON_CLASS_P (expr)
3434           && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
3435 }
3436
3437
3438 /* If the range of values taken by OP can be inferred after STMT executes,
3439    return the comparison code (COMP_CODE_P) and value (VAL_P) that
3440    describes the inferred range.  Return true if a range could be
3441    inferred.  */
3442
3443 static bool
3444 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
3445 {
3446   *val_p = NULL_TREE;
3447   *comp_code_p = ERROR_MARK;
3448
3449   /* Do not attempt to infer anything in names that flow through
3450      abnormal edges.  */
3451   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
3452     return false;
3453
3454   /* Similarly, don't infer anything from statements that may throw
3455      exceptions.  */
3456   if (tree_could_throw_p (stmt))
3457     return false;
3458
3459   /* If STMT is the last statement of a basic block with no
3460      successors, there is no point inferring anything about any of its
3461      operands.  We would not be able to find a proper insertion point
3462      for the assertion, anyway.  */
3463   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
3464     return false;
3465
3466   /* We can only assume that a pointer dereference will yield
3467      non-NULL if -fdelete-null-pointer-checks is enabled.  */
3468   if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
3469     {
3470       unsigned num_uses, num_loads, num_stores;
3471
3472       count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
3473       if (num_loads + num_stores > 0)
3474         {
3475           *val_p = build_int_cst (TREE_TYPE (op), 0);
3476           *comp_code_p = NE_EXPR;
3477           return true;
3478         }
3479     }
3480
3481   return false;
3482 }
3483
3484
3485 void dump_asserts_for (FILE *, tree);
3486 void debug_asserts_for (tree);
3487 void dump_all_asserts (FILE *);
3488 void debug_all_asserts (void);
3489
3490 /* Dump all the registered assertions for NAME to FILE.  */
3491
3492 void
3493 dump_asserts_for (FILE *file, tree name)
3494 {
3495   assert_locus_t loc;
3496
3497   fprintf (file, "Assertions to be inserted for ");
3498   print_generic_expr (file, name, 0);
3499   fprintf (file, "\n");
3500
3501   loc = asserts_for[SSA_NAME_VERSION (name)];
3502   while (loc)
3503     {