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     {
3504       fprintf (file, "\t");
3505       print_generic_expr (file, bsi_stmt (loc->si), 0);
3506       fprintf (file, "\n\tBB #%d", loc->bb->index);
3507       if (loc->e)
3508         {
3509           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
3510                    loc->e->dest->index);
3511           dump_edge_info (file, loc->e, 0);
3512         }
3513       fprintf (file, "\n\tPREDICATE: ");
3514       print_generic_expr (file, name, 0);
3515       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
3516       print_generic_expr (file, loc->val, 0);
3517       fprintf (file, "\n\n");
3518       loc = loc->next;
3519     }
3520
3521   fprintf (file, "\n");
3522 }
3523
3524
3525 /* Dump all the registered assertions for NAME to stderr.  */
3526
3527 void
3528 debug_asserts_for (tree name)
3529 {
3530   dump_asserts_for (stderr, name);
3531 }
3532
3533
3534 /* Dump all the registered assertions for all the names to FILE.  */
3535
3536 void
3537 dump_all_asserts (FILE *file)
3538 {
3539   unsigned i;
3540   bitmap_iterator bi;
3541
3542   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
3543   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3544     dump_asserts_for (file, ssa_name (i));
3545   fprintf (file, "\n");
3546 }
3547
3548
3549 /* Dump all the registered assertions for all the names to stderr.  */
3550
3551 void
3552 debug_all_asserts (void)
3553 {
3554   dump_all_asserts (stderr);
3555 }
3556
3557
3558 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
3559    'EXPR COMP_CODE VAL' at a location that dominates block BB or
3560    E->DEST, then register this location as a possible insertion point
3561    for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
3562
3563    BB, E and SI provide the exact insertion point for the new
3564    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
3565    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
3566    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
3567    must not be NULL.  */
3568
3569 static void
3570 register_new_assert_for (tree name, tree expr,
3571                          enum tree_code comp_code,
3572                          tree val,
3573                          basic_block bb,
3574                          edge e,
3575                          block_stmt_iterator si)
3576 {
3577   assert_locus_t n, loc, last_loc;
3578   bool found;
3579   basic_block dest_bb;
3580
3581 #if defined ENABLE_CHECKING
3582   gcc_assert (bb == NULL || e == NULL);
3583
3584   if (e == NULL)
3585     gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
3586                 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
3587 #endif
3588
3589   /* The new assertion A will be inserted at BB or E.  We need to
3590      determine if the new location is dominated by a previously
3591      registered location for A.  If we are doing an edge insertion,
3592      assume that A will be inserted at E->DEST.  Note that this is not
3593      necessarily true.
3594
3595      If E is a critical edge, it will be split.  But even if E is
3596      split, the new block will dominate the same set of blocks that
3597      E->DEST dominates.
3598
3599      The reverse, however, is not true, blocks dominated by E->DEST
3600      will not be dominated by the new block created to split E.  So,
3601      if the insertion location is on a critical edge, we will not use
3602      the new location to move another assertion previously registered
3603      at a block dominated by E->DEST.  */
3604   dest_bb = (bb) ? bb : e->dest;
3605
3606   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
3607      VAL at a block dominating DEST_BB, then we don't need to insert a new
3608      one.  Similarly, if the same assertion already exists at a block
3609      dominated by DEST_BB and the new location is not on a critical
3610      edge, then update the existing location for the assertion (i.e.,
3611      move the assertion up in the dominance tree).
3612
3613      Note, this is implemented as a simple linked list because there
3614      should not be more than a handful of assertions registered per
3615      name.  If this becomes a performance problem, a table hashed by
3616      COMP_CODE and VAL could be implemented.  */
3617   loc = asserts_for[SSA_NAME_VERSION (name)];
3618   last_loc = loc;
3619   found = false;
3620   while (loc)
3621     {
3622       if (loc->comp_code == comp_code
3623           && (loc->val == val
3624               || operand_equal_p (loc->val, val, 0))
3625           && (loc->expr == expr
3626               || operand_equal_p (loc->expr, expr, 0)))
3627         {
3628           /* If the assertion NAME COMP_CODE VAL has already been
3629              registered at a basic block that dominates DEST_BB, then
3630              we don't need to insert the same assertion again.  Note
3631              that we don't check strict dominance here to avoid
3632              replicating the same assertion inside the same basic
3633              block more than once (e.g., when a pointer is
3634              dereferenced several times inside a block).
3635
3636              An exception to this rule are edge insertions.  If the
3637              new assertion is to be inserted on edge E, then it will
3638              dominate all the other insertions that we may want to
3639              insert in DEST_BB.  So, if we are doing an edge
3640              insertion, don't do this dominance check.  */
3641           if (e == NULL
3642               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
3643             return;
3644
3645           /* Otherwise, if E is not a critical edge and DEST_BB
3646              dominates the existing location for the assertion, move
3647              the assertion up in the dominance tree by updating its
3648              location information.  */
3649           if ((e == NULL || !EDGE_CRITICAL_P (e))
3650               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
3651             {
3652               loc->bb = dest_bb;
3653               loc->e = e;
3654               loc->si = si;
3655               return;
3656             }
3657         }
3658
3659       /* Update the last node of the list and move to the next one.  */
3660       last_loc = loc;
3661       loc = loc->next;
3662     }
3663
3664   /* If we didn't find an assertion already registered for
3665      NAME COMP_CODE VAL, add a new one at the end of the list of
3666      assertions associated with NAME.  */
3667   n = XNEW (struct assert_locus_d);
3668   n->bb = dest_bb;
3669   n->e = e;
3670   n->si = si;
3671   n->comp_code = comp_code;
3672   n->val = val;
3673   n->expr = expr;
3674   n->next = NULL;
3675
3676   if (last_loc)
3677     last_loc->next = n;
3678   else
3679     asserts_for[SSA_NAME_VERSION (name)] = n;
3680
3681   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
3682 }
3683
3684 /* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
3685    Extract a suitable test code and value and store them into *CODE_P and
3686    *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
3687
3688    If no extraction was possible, return FALSE, otherwise return TRUE.
3689
3690    If INVERT is true, then we invert the result stored into *CODE_P.  */
3691
3692 static bool
3693 extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
3694                                          tree cond_op0, tree cond_op1,
3695                                          bool invert, enum tree_code *code_p,
3696                                          tree *val_p)
3697 {
3698   enum tree_code comp_code;
3699   tree val;
3700
3701   /* Otherwise, we have a comparison of the form NAME COMP VAL
3702      or VAL COMP NAME.  */
3703   if (name == cond_op1)
3704     {
3705       /* If the predicate is of the form VAL COMP NAME, flip
3706          COMP around because we need to register NAME as the
3707          first operand in the predicate.  */
3708       comp_code = swap_tree_comparison (cond_code);
3709       val = cond_op0;
3710     }
3711   else
3712     {
3713       /* The comparison is of the form NAME COMP VAL, so the
3714          comparison code remains unchanged.  */
3715       comp_code = cond_code;
3716       val = cond_op1;
3717     }
3718
3719   /* Invert the comparison code as necessary.  */
3720   if (invert)
3721     comp_code = invert_tree_comparison (comp_code, 0);
3722
3723   /* VRP does not handle float types.  */
3724   if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
3725     return false;
3726
3727   /* Do not register always-false predicates.
3728      FIXME:  this works around a limitation in fold() when dealing with
3729      enumerations.  Given 'enum { N1, N2 } x;', fold will not
3730      fold 'if (x > N2)' to 'if (0)'.  */
3731   if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
3732       && INTEGRAL_TYPE_P (TREE_TYPE (val)))
3733     {
3734       tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
3735       tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
3736
3737       if (comp_code == GT_EXPR
3738           && (!max
3739               || compare_values (val, max) == 0))
3740         return false;
3741
3742       if (comp_code == LT_EXPR
3743           && (!min
3744               || compare_values (val, min) == 0))
3745         return false;
3746     }
3747   *code_p = comp_code;
3748   *val_p = val;
3749   return true;
3750 }
3751
3752 /* Try to register an edge assertion for SSA name NAME on edge E for
3753    the condition COND contributing to the conditional jump pointed to by BSI.
3754    Invert the condition COND if INVERT is true.
3755    Return true if an assertion for NAME could be registered.  */
3756
3757 static bool
3758 register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
3759                             enum tree_code cond_code,
3760                             tree cond_op0, tree cond_op1, bool invert)
3761 {
3762   tree val;
3763   enum tree_code comp_code;
3764   bool retval = false;
3765
3766   if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
3767                                                 cond_op0,
3768                                                 cond_op1,
3769                                                 invert, &comp_code, &val))
3770     return false;
3771
3772   /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
3773      reachable from E.  */
3774   if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
3775       && !has_single_use (name))
3776     {
3777       register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
3778       retval = true;
3779     }
3780
3781   /* In the case of NAME <= CST and NAME being defined as
3782      NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
3783      and NAME2 <= CST - CST2.  We can do the same for NAME > CST.
3784      This catches range and anti-range tests.  */
3785   if ((comp_code == LE_EXPR
3786        || comp_code == GT_EXPR)
3787       && TREE_CODE (val) == INTEGER_CST
3788       && TYPE_UNSIGNED (TREE_TYPE (val)))
3789     {
3790       tree def_stmt = SSA_NAME_DEF_STMT (name);
3791       tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE;
3792
3793       /* Extract CST2 from the (optional) addition.  */
3794       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
3795           && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
3796         {
3797           name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
3798           cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
3799           if (TREE_CODE (name2) == SSA_NAME
3800               && TREE_CODE (cst2) == INTEGER_CST)
3801             def_stmt = SSA_NAME_DEF_STMT (name2);
3802         }
3803
3804       /* Extract NAME2 from the (optional) sign-changing cast.  */
3805       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
3806           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
3807               || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == CONVERT_EXPR))
3808         {
3809           tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
3810           if ((TREE_CODE (rhs) == NOP_EXPR
3811                || TREE_CODE (rhs) == CONVERT_EXPR)
3812               && ! TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (rhs, 0)))
3813               && (TYPE_PRECISION (TREE_TYPE (rhs))
3814                   == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0)))))
3815             name3 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
3816         }
3817
3818       /* If name3 is used later, create an ASSERT_EXPR for it.  */
3819       if (name3 != NULL_TREE
3820           && TREE_CODE (name3) == SSA_NAME
3821           && (cst2 == NULL_TREE
3822               || TREE_CODE (cst2) == INTEGER_CST)
3823           && INTEGRAL_TYPE_P (TREE_TYPE (name3))
3824           && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name3))
3825           && !has_single_use (name3))
3826         {
3827           tree tmp;
3828
3829           /* Build an expression for the range test.  */
3830           tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3);
3831           if (cst2 != NULL_TREE)
3832             tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
3833
3834           if (dump_file)
3835             {
3836               fprintf (dump_file, "Adding assert for ");
3837               print_generic_expr (dump_file, name3, 0);
3838               fprintf (dump_file, " from ");
3839               print_generic_expr (dump_file, tmp, 0);
3840               fprintf (dump_file, "\n");
3841             }
3842
3843           register_new_assert_for (name3, tmp, comp_code, val, NULL, e, bsi);
3844
3845           retval = true;
3846         }
3847
3848       /* If name2 is used later, create an ASSERT_EXPR for it.  */
3849       if (name2 != NULL_TREE
3850           && TREE_CODE (name2) == SSA_NAME
3851           && TREE_CODE (cst2) == INTEGER_CST
3852           && INTEGRAL_TYPE_P (TREE_TYPE (name2))
3853           && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
3854           && !has_single_use (name2))
3855         {
3856           tree tmp;
3857
3858           /* Build an expression for the range test.  */
3859           tmp = name2;
3860           if (TREE_TYPE (name) != TREE_TYPE (name2))
3861             tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
3862           if (cst2 != NULL_TREE)
3863             tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
3864
3865           if (dump_file)
3866             {
3867               fprintf (dump_file, "Adding assert for ");
3868               print_generic_expr (dump_file, name2, 0);
3869               fprintf (dump_file, " from ");
3870               print_generic_expr (dump_file, tmp, 0);
3871               fprintf (dump_file, "\n");
3872             }
3873
3874           register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
3875
3876           retval = true;
3877         }
3878     }
3879
3880   return retval;
3881 }
3882
3883 /* OP is an operand of a truth value expression which is known to have
3884    a particular value.  Register any asserts for OP and for any
3885    operands in OP's defining statement.
3886
3887    If CODE is EQ_EXPR, then we want to register OP is zero (false),
3888    if CODE is NE_EXPR, then we want to register OP is nonzero (true).   */
3889
3890 static bool
3891 register_edge_assert_for_1 (tree op, enum tree_code code,
3892                             edge e, block_stmt_iterator bsi)
3893 {
3894   bool retval = false;
3895   tree op_def, rhs, val;
3896   enum tree_code rhs_code;
3897
3898   /* We only care about SSA_NAMEs.  */
3899   if (TREE_CODE (op) != SSA_NAME)
3900     return false;
3901
3902   /* We know that OP will have a zero or nonzero value.  If OP is used
3903      more than once go ahead and register an assert for OP.
3904
3905      The FOUND_IN_SUBGRAPH support is not helpful in this situation as
3906      it will always be set for OP (because OP is used in a COND_EXPR in
3907      the subgraph).  */
3908   if (!has_single_use (op))
3909     {
3910       val = build_int_cst (TREE_TYPE (op), 0);
3911       register_new_assert_for (op, op, code, val, NULL, e, bsi);
3912       retval = true;
3913     }
3914
3915   /* Now look at how OP is set.  If it's set from a comparison,
3916      a truth operation or some bit operations, then we may be able
3917      to register information about the operands of that assignment.  */
3918   op_def = SSA_NAME_DEF_STMT (op);
3919   if (TREE_CODE (op_def) != GIMPLE_MODIFY_STMT)
3920     return retval;
3921
3922   rhs = GIMPLE_STMT_OPERAND (op_def, 1);
3923   rhs_code = TREE_CODE (rhs);
3924
3925   if (COMPARISON_CLASS_P (rhs))
3926     {
3927       bool invert = (code == EQ_EXPR ? true : false);
3928       tree op0 = TREE_OPERAND (rhs, 0);
3929       tree op1 = TREE_OPERAND (rhs, 1);
3930
3931       if (TREE_CODE (op0) == SSA_NAME)
3932         retval |= register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1,
3933                                               invert);
3934       if (TREE_CODE (op1) == SSA_NAME)
3935         retval |= register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1,
3936                                               invert);
3937     }
3938   else if ((code == NE_EXPR
3939             && (TREE_CODE (rhs) == TRUTH_AND_EXPR
3940                 || TREE_CODE (rhs) == BIT_AND_EXPR))
3941            || (code == EQ_EXPR
3942                && (TREE_CODE (rhs) == TRUTH_OR_EXPR
3943                    || TREE_CODE (rhs) == BIT_IOR_EXPR)))
3944     {
3945       /* Recurse on each operand.  */
3946       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3947                                             code, e, bsi);
3948       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 1),
3949                                             code, e, bsi);
3950     }
3951   else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
3952     {
3953       /* Recurse, flipping CODE.  */
3954       code = invert_tree_comparison (code, false);
3955       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3956                                             code, e, bsi);
3957     }
3958   else if (TREE_CODE (rhs) == SSA_NAME)
3959     {
3960       /* Recurse through the copy.  */
3961       retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
3962     }
3963   else if (TREE_CODE (rhs) == NOP_EXPR
3964            || TREE_CODE (rhs) == CONVERT_EXPR
3965            || TREE_CODE (rhs) == NON_LVALUE_EXPR)
3966     {
3967       /* Recurse through the type conversion.  */
3968       retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
3969                                             code, e, bsi);
3970     }
3971
3972   return retval;
3973 }
3974
3975 /* Try to register an edge assertion for SSA name NAME on edge E for
3976    the condition COND contributing to the conditional jump pointed to by SI.
3977    Return true if an assertion for NAME could be registered.  */
3978
3979 static bool
3980 register_edge_assert_for (tree name, edge e, block_stmt_iterator si,
3981                           enum tree_code cond_code, tree cond_op0,
3982                           tree cond_op1)
3983 {
3984   tree val;
3985   enum tree_code comp_code;
3986   bool retval = false;
3987   bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
3988
3989   /* Do not attempt to infer anything in names that flow through
3990      abnormal edges.  */
3991   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
3992     return false;
3993
3994   if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
3995                                                 cond_op0, cond_op1,
3996                                                 is_else_edge,
3997                                                 &comp_code, &val))
3998     return false;
3999
4000   /* Register ASSERT_EXPRs for name.  */
4001   retval |= register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
4002                                         cond_op1, is_else_edge);
4003
4004
4005   /* If COND is effectively an equality test of an SSA_NAME against
4006      the value zero or one, then we may be able to assert values
4007      for SSA_NAMEs which flow into COND.  */
4008
4009   /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
4010      statement of NAME we can assert both operands of the TRUTH_AND_EXPR
4011      have nonzero value.  */
4012   if (((comp_code == EQ_EXPR && integer_onep (val))
4013        || (comp_code == NE_EXPR && integer_zerop (val))))
4014     {
4015       tree def_stmt = SSA_NAME_DEF_STMT (name);
4016
4017       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4018           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_AND_EXPR
4019               || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == BIT_AND_EXPR))
4020         {
4021           tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4022           tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
4023           retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
4024           retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
4025         }
4026     }
4027
4028   /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
4029      statement of NAME we can assert both operands of the TRUTH_OR_EXPR
4030      have zero value.  */
4031   if (((comp_code == EQ_EXPR && integer_zerop (val))
4032        || (comp_code == NE_EXPR && integer_onep (val))))
4033     {
4034       tree def_stmt = SSA_NAME_DEF_STMT (name);
4035
4036       if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4037           && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_OR_EXPR
4038               /* For BIT_IOR_EXPR only if NAME == 0 both operands have
4039                  necessarily zero value.  */
4040               || (comp_code == EQ_EXPR
4041                   && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1))
4042                         == BIT_IOR_EXPR))))
4043         {
4044           tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4045           tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
4046           retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
4047           retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
4048         }
4049     }
4050
4051   return retval;
4052 }
4053
4054
4055 static bool find_assert_locations (basic_block bb);
4056
4057 /* Determine whether the outgoing edges of BB should receive an
4058    ASSERT_EXPR for each of the operands of BB's LAST statement.
4059    The last statement of BB must be a COND_EXPR.
4060
4061    If any of the sub-graphs rooted at BB have an interesting use of
4062    the predicate operands, an assert location node is added to the
4063    list of assertions for the corresponding operands.  */
4064
4065 static bool
4066 find_conditional_asserts (basic_block bb, tree last)
4067 {
4068   bool need_assert;
4069   block_stmt_iterator bsi;
4070   tree op;
4071   edge_iterator ei;
4072   edge e;
4073   ssa_op_iter iter;
4074
4075   need_assert = false;
4076   bsi = bsi_for_stmt (last);
4077
4078   /* Look for uses of the operands in each of the sub-graphs
4079      rooted at BB.  We need to check each of the outgoing edges
4080      separately, so that we know what kind of ASSERT_EXPR to
4081      insert.  */
4082   FOR_EACH_EDGE (e, ei, bb->succs)
4083     {
4084       if (e->dest == bb)
4085         continue;
4086
4087       /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
4088          Otherwise, when we finish traversing each of the sub-graphs, we
4089          won't know whether the variables were found in the sub-graphs or
4090          if they had been found in a block upstream from BB.
4091
4092          This is actually a bad idea is some cases, particularly jump
4093          threading.  Consider a CFG like the following:
4094
4095                     0
4096                    /|
4097                   1 |
4098                    \|
4099                     2
4100                    / \
4101                   3   4
4102
4103          Assume that one or more operands in the conditional at the
4104          end of block 0 are used in a conditional in block 2, but not
4105          anywhere in block 1.  In this case we will not insert any
4106          assert statements in block 1, which may cause us to miss
4107          opportunities to optimize, particularly for jump threading.  */
4108       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4109         RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4110
4111       /* Traverse the strictly dominated sub-graph rooted at E->DEST
4112          to determine if any of the operands in the conditional
4113          predicate are used.  */
4114       need_assert |= find_assert_locations (e->dest);
4115
4116       /* Register the necessary assertions for each operand in the
4117          conditional predicate.  */
4118       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4119         {
4120           tree cond = COND_EXPR_COND (last);
4121           if (op != cond)
4122             need_assert |= register_edge_assert_for (op, e, bsi,
4123                                                      TREE_CODE (cond),
4124                                                      TREE_OPERAND (cond, 0),
4125                                                      TREE_OPERAND (cond, 1));
4126           else
4127             need_assert |= register_edge_assert_for (op, e, bsi, EQ_EXPR, op,
4128                                                      boolean_true_node);
4129         }
4130     }
4131
4132   /* Finally, indicate that we have found the operands in the
4133      conditional.  */
4134   FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
4135     SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4136
4137   return need_assert;
4138 }
4139
4140 /* Compare two case labels sorting first by the destination label uid
4141    and then by the case value.  */
4142
4143 static int
4144 compare_case_labels (const void *p1, const void *p2)
4145 {
4146   const_tree const case1 = *(const_tree const*)p1;
4147   const_tree const case2 = *(const_tree const*)p2;
4148   unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
4149   unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
4150
4151   if (uid1 < uid2)
4152     return -1;
4153   else if (uid1 == uid2)
4154     {
4155       /* Make sure the default label is first in a group.  */
4156       if (!CASE_LOW (case1))
4157         return -1;
4158       else if (!CASE_LOW (case2))
4159         return 1;
4160       else
4161         return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
4162     }
4163   else
4164     return 1;
4165 }
4166
4167 /* Determine whether the outgoing edges of BB should receive an
4168    ASSERT_EXPR for each of the operands of BB's LAST statement.
4169    The last statement of BB must be a SWITCH_EXPR.
4170
4171    If any of the sub-graphs rooted at BB have an interesting use of
4172    the predicate operands, an assert location node is added to the
4173    list of assertions for the corresponding operands.  */
4174
4175 static bool
4176 find_switch_asserts (basic_block bb, tree last)
4177 {
4178   bool need_assert;
4179   block_stmt_iterator bsi;
4180   tree op;
4181   edge e;
4182   tree vec = SWITCH_LABELS (last), vec2;
4183   size_t n = TREE_VEC_LENGTH (vec);
4184   unsigned int idx;
4185
4186   need_assert = false;
4187   bsi = bsi_for_stmt (last);
4188   op = TREE_OPERAND (last, 0);
4189   if (TREE_CODE (op) != SSA_NAME)
4190     return false;
4191
4192   /* Build a vector of case labels sorted by destination label.  */
4193   vec2 = make_tree_vec (n);
4194   for (idx = 0; idx < n; ++idx)
4195     TREE_VEC_ELT (vec2, idx) = TREE_VEC_ELT (vec, idx);
4196   qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
4197
4198   for (idx = 0; idx < n; ++idx)
4199     {
4200       tree min, max;
4201       tree cl = TREE_VEC_ELT (vec2, idx);
4202
4203       min = CASE_LOW (cl);
4204       max = CASE_HIGH (cl);
4205
4206       /* If there are multiple case labels with the same destination
4207          we need to combine them to a single value range for the edge.  */
4208       if (idx + 1 < n
4209           && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
4210         {
4211           /* Skip labels until the last of the group.  */
4212           do {
4213             ++idx;
4214           } while (idx < n
4215                    && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
4216           --idx;
4217
4218           /* Pick up the maximum of the case label range.  */
4219           if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
4220             max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
4221           else
4222             max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
4223         }
4224
4225       /* Nothing to do if the range includes the default label until we
4226          can register anti-ranges.  */
4227       if (min == NULL_TREE)
4228         continue;
4229
4230       /* Find the edge to register the assert expr on.  */
4231       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
4232
4233       /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
4234          Otherwise, when we finish traversing each of the sub-graphs, we
4235          won't know whether the variables were found in the sub-graphs or
4236          if they had been found in a block upstream from BB.  */
4237       RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4238
4239       /* Traverse the strictly dominated sub-graph rooted at E->DEST
4240          to determine if any of the operands in the conditional
4241          predicate are used.  */
4242       if (e->dest != bb)
4243         need_assert |= find_assert_locations (e->dest);
4244
4245       /* Register the necessary assertions for the operand in the
4246          SWITCH_EXPR.  */
4247       need_assert |= register_edge_assert_for (op, e, bsi,
4248                                                max ? GE_EXPR : EQ_EXPR,
4249                                                op,
4250                                                fold_convert (TREE_TYPE (op),
4251                                                              min));
4252       if (max)
4253         {
4254           need_assert |= register_edge_assert_for (op, e, bsi, LE_EXPR,
4255                                                    op,
4256                                                    fold_convert (TREE_TYPE (op),
4257                                                                  max));
4258         }
4259     }
4260
4261   /* Finally, indicate that we have found the operand in the
4262      SWITCH_EXPR.  */
4263   SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4264
4265   return need_assert;
4266 }
4267
4268
4269 /* Traverse all the statements in block BB looking for statements that
4270    may generate useful assertions for the SSA names in their operand.
4271    If a statement produces a useful assertion A for name N_i, then the
4272    list of assertions already generated for N_i is scanned to
4273    determine if A is actually needed.
4274
4275    If N_i already had the assertion A at a location dominating the
4276    current location, then nothing needs to be done.  Otherwise, the
4277    new location for A is recorded instead.
4278
4279    1- For every statement S in BB, all the variables used by S are
4280       added to bitmap FOUND_IN_SUBGRAPH.
4281
4282    2- If statement S uses an operand N in a way that exposes a known
4283       value range for N, then if N was not already generated by an
4284       ASSERT_EXPR, create a new assert location for N.  For instance,
4285       if N is a pointer and the statement dereferences it, we can
4286       assume that N is not NULL.
4287
4288    3- COND_EXPRs are a special case of #2.  We can derive range
4289       information from the predicate but need to insert different
4290       ASSERT_EXPRs for each of the sub-graphs rooted at the
4291       conditional block.  If the last statement of BB is a conditional
4292       expression of the form 'X op Y', then
4293
4294       a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
4295
4296       b) If the conditional is the only entry point to the sub-graph
4297          corresponding to the THEN_CLAUSE, recurse into it.  On
4298          return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
4299          an ASSERT_EXPR is added for the corresponding variable.
4300
4301       c) Repeat step (b) on the ELSE_CLAUSE.
4302
4303       d) Mark X and Y in FOUND_IN_SUBGRAPH.
4304
4305       For instance,
4306
4307             if (a == 9)
4308               b = a;
4309             else
4310               b = c + 1;
4311
4312       In this case, an assertion on the THEN clause is useful to
4313       determine that 'a' is always 9 on that edge.  However, an assertion
4314       on the ELSE clause would be unnecessary.
4315
4316    4- If BB does not end in a conditional expression, then we recurse
4317       into BB's dominator children.
4318
4319    At the end of the recursive traversal, every SSA name will have a
4320    list of locations where ASSERT_EXPRs should be added.  When a new
4321    location for name N is found, it is registered by calling
4322    register_new_assert_for.  That function keeps track of all the
4323    registered assertions to prevent adding unnecessary assertions.
4324    For instance, if a pointer P_4 is dereferenced more than once in a
4325    dominator tree, only the location dominating all the dereference of
4326    P_4 will receive an ASSERT_EXPR.
4327
4328    If this function returns true, then it means that there are names
4329    for which we need to generate ASSERT_EXPRs.  Those assertions are
4330    inserted by process_assert_insertions.  */
4331
4332 static bool
4333 find_assert_locations (basic_block bb)
4334 {
4335   block_stmt_iterator si;
4336   tree last, phi;
4337   bool need_assert;
4338   basic_block son;
4339
4340   if (TEST_BIT (blocks_visited, bb->index))
4341     return false;
4342
4343   SET_BIT (blocks_visited, bb->index);
4344
4345   need_assert = false;
4346
4347   /* Traverse all PHI nodes in BB marking used operands.  */
4348   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4349     {
4350       use_operand_p arg_p;
4351       ssa_op_iter i;
4352
4353       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
4354         {
4355           tree arg = USE_FROM_PTR (arg_p);
4356           if (TREE_CODE (arg) == SSA_NAME)
4357             {
4358               gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
4359               SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
4360             }
4361         }
4362     }
4363
4364   /* Traverse all the statements in BB marking used names and looking
4365      for statements that may infer assertions for their used operands.  */
4366   last = NULL_TREE;
4367   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4368     {
4369       tree stmt, op;
4370       ssa_op_iter i;
4371
4372       stmt = bsi_stmt (si);
4373
4374       /* See if we can derive an assertion for any of STMT's operands.  */
4375       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
4376         {
4377           tree value;
4378           enum tree_code comp_code;
4379
4380           /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
4381              the sub-graph of a conditional block, when we return from
4382              this recursive walk, our parent will use the
4383              FOUND_IN_SUBGRAPH bitset to determine if one of the
4384              operands it was looking for was present in the sub-graph.  */
4385           SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
4386
4387           /* If OP is used in such a way that we can infer a value
4388              range for it, and we don't find a previous assertion for
4389              it, create a new assertion location node for OP.  */
4390           if (infer_value_range (stmt, op, &comp_code, &value))
4391             {
4392               /* If we are able to infer a nonzero value range for OP,
4393                  then walk backwards through the use-def chain to see if OP
4394                  was set via a typecast.
4395
4396                  If so, then we can also infer a nonzero value range
4397                  for the operand of the NOP_EXPR.  */
4398               if (comp_code == NE_EXPR && integer_zerop (value))
4399                 {
4400                   tree t = op;
4401                   tree def_stmt = SSA_NAME_DEF_STMT (t);
4402
4403                   while (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
4404                          && TREE_CODE
4405                              (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
4406                          && TREE_CODE
4407                              (TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1),
4408                                             0)) == SSA_NAME
4409                          && POINTER_TYPE_P
4410                              (TREE_TYPE (TREE_OPERAND
4411                                           (GIMPLE_STMT_OPERAND (def_stmt,
4412                                                                 1), 0))))
4413                     {
4414                       t = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
4415                       def_stmt = SSA_NAME_DEF_STMT (t);
4416
4417                       /* Note we want to register the assert for the
4418                          operand of the NOP_EXPR after SI, not after the
4419                          conversion.  */
4420                       if (! has_single_use (t))
4421                         {
4422                           register_new_assert_for (t, t, comp_code, value,
4423                                                    bb, NULL, si);
4424                           need_assert = true;
4425                         }
4426                     }
4427                 }
4428
4429               /* If OP is used only once, namely in this STMT, don't
4430                  bother creating an ASSERT_EXPR for it.  Such an
4431                  ASSERT_EXPR would do nothing but increase compile time.  */
4432               if (!has_single_use (op))
4433                 {
4434                   register_new_assert_for (op, op, comp_code, value,
4435                                            bb, NULL, si);
4436                   need_assert = true;
4437                 }
4438             }
4439         }
4440
4441       /* Remember the last statement of the block.  */
4442       last = stmt;
4443     }
4444
4445   /* If BB's last statement is a conditional expression
4446      involving integer operands, recurse into each of the sub-graphs
4447      rooted at BB to determine if we need to add ASSERT_EXPRs.  */
4448   if (last
4449       && TREE_CODE (last) == COND_EXPR
4450       && !fp_predicate (COND_EXPR_COND (last))
4451       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4452     need_assert |= find_conditional_asserts (bb, last);
4453
4454   if (last
4455       && TREE_CODE (last) == SWITCH_EXPR
4456       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
4457     need_assert |= find_switch_asserts (bb, last);
4458
4459   /* Recurse into the dominator children of BB.  */
4460   for (son = first_dom_son (CDI_DOMINATORS, bb);
4461        son;
4462        son = next_dom_son (CDI_DOMINATORS, son))
4463     need_assert |= find_assert_locations (son);
4464
4465   return need_assert;
4466 }
4467
4468
4469 /* Create an ASSERT_EXPR for NAME and insert it in the location
4470    indicated by LOC.  Return true if we made any edge insertions.  */
4471
4472 static bool
4473 process_assert_insertions_for (tree name, assert_locus_t loc)
4474 {
4475   /* Build the comparison expression NAME_i COMP_CODE VAL.  */
4476   tree stmt, cond, assert_expr;
4477   edge_iterator ei;
4478   edge e;
4479
4480   cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
4481   assert_expr = build_assert_expr_for (cond, name);
4482
4483   if (loc->e)
4484     {
4485       /* We have been asked to insert the assertion on an edge.  This
4486          is used only by COND_EXPR and SWITCH_EXPR assertions.  */
4487 #if defined ENABLE_CHECKING
4488       gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
4489           || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
4490 #endif
4491
4492       bsi_insert_on_edge (loc->e, assert_expr);
4493       return true;
4494     }
4495
4496   /* Otherwise, we can insert right after LOC->SI iff the
4497      statement must not be the last statement in the block.  */
4498   stmt = bsi_stmt (loc->si);
4499   if (!stmt_ends_bb_p (stmt))
4500     {
4501       bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
4502       return false;
4503     }
4504
4505   /* If STMT must be the last statement in BB, we can only insert new
4506      assertions on the non-abnormal edge out of BB.  Note that since
4507      STMT is not control flow, there may only be one non-abnormal edge
4508      out of BB.  */
4509   FOR_EACH_EDGE (e, ei, loc->bb->succs)
4510     if (!(e->flags & EDGE_ABNORMAL))
4511       {
4512         bsi_insert_on_edge (e, assert_expr);
4513         return true;
4514       }
4515
4516   gcc_unreachable ();
4517 }
4518
4519
4520 /* Process all the insertions registered for every name N_i registered
4521    in NEED_ASSERT_FOR.  The list of assertions to be inserted are
4522    found in ASSERTS_FOR[i].  */
4523
4524 static void
4525 process_assert_insertions (void)
4526 {
4527   unsigned i;
4528   bitmap_iterator bi;
4529   bool update_edges_p = false;
4530   int num_asserts = 0;
4531
4532   if (dump_file && (dump_flags & TDF_DETAILS))
4533     dump_all_asserts (dump_file);
4534
4535   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
4536     {
4537       assert_locus_t loc = asserts_for[i];
4538       gcc_assert (loc);
4539
4540       while (loc)
4541         {
4542           assert_locus_t next = loc->next;
4543           update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
4544           free (loc);
4545           loc = next;
4546           num_asserts++;
4547         }
4548     }
4549
4550   if (update_edges_p)
4551     bsi_commit_edge_inserts ();
4552
4553   if (dump_file && (dump_flags & TDF_STATS))
4554     fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
4555              num_asserts);
4556 }
4557
4558
4559 /* Traverse the flowgraph looking for conditional jumps to insert range
4560    expressions.  These range expressions are meant to provide information
4561    to optimizations that need to reason in terms of value ranges.  They
4562    will not be expanded into RTL.  For instance, given:
4563
4564    x = ...
4565    y = ...
4566    if (x < y)
4567      y = x - 2;
4568    else
4569      x = y + 3;
4570
4571    this pass will transform the code into:
4572
4573    x = ...
4574    y = ...
4575    if (x < y)
4576     {
4577       x = ASSERT_EXPR <x, x < y>
4578       y = x - 2
4579     }
4580    else
4581     {
4582       y = ASSERT_EXPR <y, x <= y>
4583       x = y + 3
4584     }
4585
4586    The idea is that once copy and constant propagation have run, other
4587    optimizations will be able to determine what ranges of values can 'x'
4588    take in different paths of the code, simply by checking the reaching
4589    definition of 'x'.  */
4590
4591 static void
4592 insert_range_assertions (void)
4593 {
4594   edge e;
4595   edge_iterator ei;
4596   bool update_ssa_p;
4597
4598   found_in_subgraph = sbitmap_alloc (num_ssa_names);
4599   sbitmap_zero (found_in_subgraph);
4600
4601   blocks_visited = sbitmap_alloc (last_basic_block);
4602   sbitmap_zero (blocks_visited);
4603
4604   need_assert_for = BITMAP_ALLOC (NULL);
4605   asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
4606
4607   calculate_dominance_info (CDI_DOMINATORS);
4608
4609   update_ssa_p = false;
4610   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
4611     if (find_assert_locations (e->dest))
4612       update_ssa_p = true;
4613
4614   if (update_ssa_p)
4615     {
4616       process_assert_insertions ();
4617       update_ssa (TODO_update_ssa_no_phi);
4618     }
4619
4620   if (dump_file && (dump_flags & TDF_DETAILS))
4621     {
4622       fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
4623       dump_function_to_file (current_function_decl, dump_file, dump_flags);
4624     }
4625
4626   sbitmap_free (found_in_subgraph);
4627   free (asserts_for);
4628   BITMAP_FREE (need_assert_for);
4629 }
4630
4631 /* Checks one ARRAY_REF in REF, located at LOCUS. Ignores flexible arrays
4632    and "struct" hacks. If VRP can determine that the
4633    array subscript is a constant, check if it is outside valid
4634    range. If the array subscript is a RANGE, warn if it is
4635    non-overlapping with valid range.
4636    IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR.  */
4637
4638 static void
4639 check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one)
4640 {
4641   value_range_t* vr = NULL;
4642   tree low_sub, up_sub;
4643   tree low_bound, up_bound = array_ref_up_bound (ref);
4644
4645   low_sub = up_sub = TREE_OPERAND (ref, 1);
4646
4647   if (!up_bound || TREE_NO_WARNING (ref)
4648       || TREE_CODE (up_bound) != INTEGER_CST
4649       /* Can not check flexible arrays.  */
4650       || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
4651           && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
4652           && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
4653       /* Accesses after the end of arrays of size 0 (gcc
4654          extension) and 1 are likely intentional ("struct
4655          hack").  */
4656       || compare_tree_int (up_bound, 1) <= 0)
4657     return;
4658
4659   low_bound = array_ref_low_bound (ref);
4660
4661   if (TREE_CODE (low_sub) == SSA_NAME)
4662     {
4663       vr = get_value_range (low_sub);
4664       if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
4665         {
4666           low_sub = vr->type == VR_RANGE ? vr->max : vr->min;
4667           up_sub = vr->type == VR_RANGE ? vr->min : vr->max;
4668         }
4669     }
4670
4671   if (vr && vr->type == VR_ANTI_RANGE)
4672     {
4673       if (TREE_CODE (up_sub) == INTEGER_CST
4674           && tree_int_cst_lt (up_bound, up_sub)
4675           && TREE_CODE (low_sub) == INTEGER_CST
4676           && tree_int_cst_lt (low_sub, low_bound))
4677         {
4678           warning (OPT_Warray_bounds,
4679                    "%Harray subscript is outside array bounds", locus);
4680           TREE_NO_WARNING (ref) = 1;
4681         }
4682     }
4683   else if (TREE_CODE (up_sub) == INTEGER_CST
4684            && tree_int_cst_lt (up_bound, up_sub)
4685            && !tree_int_cst_equal (up_bound, up_sub)
4686            && (!ignore_off_by_one
4687                || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
4688                                                         up_bound,
4689                                                         integer_one_node,
4690                                                         0),
4691                                        up_sub)))
4692     {
4693       warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
4694                locus);
4695       TREE_NO_WARNING (ref) = 1;
4696     }
4697   else if (TREE_CODE (low_sub) == INTEGER_CST
4698            && tree_int_cst_lt (low_sub, low_bound))
4699     {
4700       warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
4701                locus);
4702       TREE_NO_WARNING (ref) = 1;
4703     }
4704 }
4705
4706 /* Searches if the expr T, located at LOCATION computes
4707    address of an ARRAY_REF, and call check_array_ref on it.  */
4708
4709 static void
4710 search_for_addr_array(tree t, location_t* location)
4711 {
4712   while (TREE_CODE (t) == SSA_NAME)
4713     {
4714       t = SSA_NAME_DEF_STMT (t);
4715       if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
4716         return;
4717       t = GIMPLE_STMT_OPERAND (t, 1);
4718     }
4719
4720
4721   /* We are only interested in addresses of ARRAY_REF's.  */
4722   if (TREE_CODE (t) != ADDR_EXPR)
4723     return;
4724
4725   /* Check each ARRAY_REFs in the reference chain. */
4726   do
4727     {
4728       if (TREE_CODE (t) == ARRAY_REF)
4729         check_array_ref (t, location, true /*ignore_off_by_one*/);
4730
4731       t = TREE_OPERAND(t,0);
4732     }
4733   while (handled_component_p (t));
4734 }
4735
4736 /* walk_tree() callback that checks if *TP is
4737    an ARRAY_REF inside an ADDR_EXPR (in which an array
4738    subscript one outside the valid range is allowed). Call
4739    check_array_ref for each ARRAY_REF found. The location is
4740    passed in DATA.  */
4741
4742 static tree
4743 check_array_bounds (tree *tp, int *walk_subtree, void *data)
4744 {
4745   tree t = *tp;
4746   tree stmt = (tree)data;
4747   location_t *location = EXPR_LOCUS (stmt);
4748
4749   if (!EXPR_HAS_LOCATION (stmt))
4750     {
4751       *walk_subtree = FALSE;
4752       return NULL_TREE;
4753     }
4754
4755   *walk_subtree = TRUE;
4756
4757   if (TREE_CODE (t) == ARRAY_REF)
4758     check_array_ref (t, location, false /*ignore_off_by_one*/);
4759
4760   if (TREE_CODE (t) == INDIRECT_REF
4761       || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
4762     search_for_addr_array (TREE_OPERAND (t, 0), location);
4763   else if (TREE_CODE (t) == CALL_EXPR)
4764     {
4765       tree arg;
4766       call_expr_arg_iterator iter;
4767
4768       FOR_EACH_CALL_EXPR_ARG (arg, iter, t)
4769         search_for_addr_array (arg, location);
4770     }
4771
4772   if (TREE_CODE (t) == ADDR_EXPR)
4773     *walk_subtree = FALSE;
4774
4775   return NULL_TREE;
4776 }
4777
4778 /* Walk over all statements of all reachable BBs and call check_array_bounds
4779    on them.  */
4780
4781 static void
4782 check_all_array_refs (void)
4783 {
4784   basic_block bb;
4785   block_stmt_iterator si;
4786
4787   FOR_EACH_BB (bb)
4788     {
4789       /* Skip bb's that are clearly unreachable.  */
4790       if (single_pred_p (bb))
4791       {
4792         basic_block pred_bb = EDGE_PRED (bb, 0)->src;
4793         tree ls = NULL_TREE;
4794
4795         if (!bsi_end_p (bsi_last (pred_bb)))
4796           ls = bsi_stmt (bsi_last (pred_bb));
4797
4798         if (ls && TREE_CODE (ls) == COND_EXPR
4799             && ((COND_EXPR_COND (ls) == boolean_false_node
4800                  && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
4801                 || (COND_EXPR_COND (ls) == boolean_true_node
4802                     && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
4803           continue;
4804       }
4805       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4806         walk_tree (bsi_stmt_ptr (si), check_array_bounds,
4807                    bsi_stmt (si), NULL);
4808     }
4809 }
4810
4811 /* Convert range assertion expressions into the implied copies and
4812    copy propagate away the copies.  Doing the trivial copy propagation
4813    here avoids the need to run the full copy propagation pass after
4814    VRP.
4815
4816    FIXME, this will eventually lead to copy propagation removing the
4817    names that had useful range information attached to them.  For
4818    instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
4819    then N_i will have the range [3, +INF].
4820
4821    However, by converting the assertion into the implied copy
4822    operation N_i = N_j, we will then copy-propagate N_j into the uses
4823    of N_i and lose the range information.  We may want to hold on to
4824    ASSERT_EXPRs a little while longer as the ranges could be used in
4825    things like jump threading.
4826
4827    The problem with keeping ASSERT_EXPRs around is that passes after
4828    VRP need to handle them appropriately.
4829
4830    Another approach would be to make the range information a first
4831    class property of the SSA_NAME so that it can be queried from
4832    any pass.  This is made somewhat more complex by the need for
4833    multiple ranges to be associated with one SSA_NAME.  */
4834
4835 static void
4836 remove_range_assertions (void)
4837 {
4838   basic_block bb;
4839   block_stmt_iterator si;
4840
4841   /* Note that the BSI iterator bump happens at the bottom of the
4842      loop and no bump is necessary if we're removing the statement
4843      referenced by the current BSI.  */
4844   FOR_EACH_BB (bb)
4845     for (si = bsi_start (bb); !bsi_end_p (si);)
4846       {
4847         tree stmt = bsi_stmt (si);
4848         tree use_stmt;
4849
4850         if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
4851             && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
4852           {
4853             tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), var;
4854             tree cond = fold (ASSERT_EXPR_COND (rhs));
4855             use_operand_p use_p;
4856             imm_use_iterator iter;
4857
4858             gcc_assert (cond != boolean_false_node);
4859
4860             /* Propagate the RHS into every use of the LHS.  */
4861             var = ASSERT_EXPR_VAR (rhs);
4862             FOR_EACH_IMM_USE_STMT (use_stmt, iter,
4863                                    GIMPLE_STMT_OPERAND (stmt, 0))
4864               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
4865                 {
4866                   SET_USE (use_p, var);
4867                   gcc_assert (TREE_CODE (var) == SSA_NAME);
4868                 }
4869
4870             /* And finally, remove the copy, it is not needed.  */
4871             bsi_remove (&si, true);
4872             release_defs (stmt);
4873           }
4874         else
4875           bsi_next (&si);
4876       }
4877
4878   sbitmap_free (blocks_visited);
4879 }
4880
4881
4882 /* Return true if STMT is interesting for VRP.  */
4883
4884 static bool
4885 stmt_interesting_for_vrp (tree stmt)
4886 {
4887   if (TREE_CODE (stmt) == PHI_NODE
4888       && is_gimple_reg (PHI_RESULT (stmt))
4889       && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
4890           || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
4891     return true;
4892   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
4893     {
4894       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
4895       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
4896
4897       /* In general, assignments with virtual operands are not useful
4898          for deriving ranges, with the obvious exception of calls to
4899          builtin functions.  */
4900       if (TREE_CODE (lhs) == SSA_NAME
4901           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4902               || POINTER_TYPE_P (TREE_TYPE (lhs)))
4903           && ((TREE_CODE (rhs) == CALL_EXPR
4904                && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
4905                && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
4906                && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
4907               || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
4908         return true;
4909     }
4910   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
4911     return true;
4912
4913   return false;
4914 }
4915
4916
4917 /* Initialize local data structures for VRP.  */
4918
4919 static void
4920 vrp_initialize (void)
4921 {
4922   basic_block bb;
4923
4924   vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
4925   vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
4926
4927   FOR_EACH_BB (bb)
4928     {
4929       block_stmt_iterator si;
4930       tree phi;
4931
4932       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4933         {
4934           if (!stmt_interesting_for_vrp (phi))
4935             {
4936               tree lhs = PHI_RESULT (phi);
4937               set_value_range_to_varying (get_value_range (lhs));
4938               DONT_SIMULATE_AGAIN (phi) = true;
4939             }
4940           else
4941             DONT_SIMULATE_AGAIN (phi) = false;
4942         }
4943
4944       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4945         {
4946           tree stmt = bsi_stmt (si);
4947
4948           if (!stmt_interesting_for_vrp (stmt))
4949             {
4950               ssa_op_iter i;
4951               tree def;
4952               FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
4953                 set_value_range_to_varying (get_value_range (def));
4954               DONT_SIMULATE_AGAIN (stmt) = true;
4955             }
4956           else
4957             {
4958               DONT_SIMULATE_AGAIN (stmt) = false;
4959             }
4960         }
4961     }
4962 }
4963
4964
4965 /* Visit assignment STMT.  If it produces an interesting range, record
4966    the SSA name in *OUTPUT_P.  */
4967
4968 static enum ssa_prop_result
4969 vrp_visit_assignment (tree stmt, tree *output_p)
4970 {
4971   tree lhs, rhs, def;
4972   ssa_op_iter iter;
4973
4974   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
4975   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
4976
4977   /* We only keep track of ranges in integral and pointer types.  */
4978   if (TREE_CODE (lhs) == SSA_NAME
4979       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
4980            /* It is valid to have NULL MIN/MAX values on a type.  See
4981               build_range_type.  */
4982            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
4983            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
4984           || POINTER_TYPE_P (TREE_TYPE (lhs))))
4985     {
4986       struct loop *l;
4987       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
4988
4989       extract_range_from_expr (&new_vr, rhs);
4990
4991       /* If STMT is inside a loop, we may be able to know something
4992          else about the range of LHS by examining scalar evolution
4993          information.  */
4994       if (current_loops && (l = loop_containing_stmt (stmt)))
4995         adjust_range_with_scev (&new_vr, l, stmt, lhs);
4996
4997       if (update_value_range (lhs, &new_vr))
4998         {
4999           *output_p = lhs;
5000
5001           if (dump_file && (dump_flags & TDF_DETAILS))
5002             {
5003               fprintf (dump_file, "Found new range for ");
5004               print_generic_expr (dump_file, lhs, 0);
5005               fprintf (dump_file, ": ");
5006               dump_value_range (dump_file, &new_vr);
5007               fprintf (dump_file, "\n\n");
5008             }
5009
5010           if (new_vr.type == VR_VARYING)
5011             return SSA_PROP_VARYING;
5012
5013           return SSA_PROP_INTERESTING;
5014         }
5015
5016       return SSA_PROP_NOT_INTERESTING;
5017     }
5018
5019   /* Every other statement produces no useful ranges.  */
5020   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
5021     set_value_range_to_varying (get_value_range (def));
5022
5023   return SSA_PROP_VARYING;
5024 }
5025
5026 /* Helper that gets the value range of the SSA_NAME with version I
5027    or a symbolic range containing the SSA_NAME only if the value range
5028    is varying or undefined.  */
5029
5030 static inline value_range_t
5031 get_vr_for_comparison (int i)
5032 {
5033   value_range_t vr = *(vr_value[i]);
5034
5035   /* If name N_i does not have a valid range, use N_i as its own
5036      range.  This allows us to compare against names that may
5037      have N_i in their ranges.  */
5038   if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
5039     {
5040       vr.type = VR_RANGE;
5041       vr.min = ssa_name (i);
5042       vr.max = ssa_name (i);
5043     }
5044
5045   return vr;
5046 }
5047
5048 /* Compare all the value ranges for names equivalent to VAR with VAL
5049    using comparison code COMP.  Return the same value returned by
5050    compare_range_with_value, including the setting of
5051    *STRICT_OVERFLOW_P.  */
5052
5053 static tree
5054 compare_name_with_value (enum tree_code comp, tree var, tree val,
5055                          bool *strict_overflow_p)
5056 {
5057   bitmap_iterator bi;
5058   unsigned i;
5059   bitmap e;
5060   tree retval, t;
5061   int used_strict_overflow;
5062   bool sop;
5063   value_range_t equiv_vr;
5064
5065   /* Get the set of equivalences for VAR.  */
5066   e = get_value_range (var)->equiv;
5067
5068   /* Start at -1.  Set it to 0 if we do a comparison without relying
5069      on overflow, or 1 if all comparisons rely on overflow.  */
5070   used_strict_overflow = -1;
5071
5072   /* Compare vars' value range with val.  */
5073   equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
5074   sop = false;
5075   retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
5076   if (retval)
5077     used_strict_overflow = sop ? 1 : 0;
5078
5079   /* If the equiv set is empty we have done all work we need to do.  */
5080   if (e == NULL)
5081     {
5082       if (retval
5083           && used_strict_overflow > 0)
5084         *strict_overflow_p = true;
5085       return retval;
5086     }
5087
5088   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
5089     {
5090       equiv_vr = get_vr_for_comparison (i);
5091       sop = false;
5092       t = compare_range_with_value (comp, &equiv_vr, val, &sop);
5093       if (t)
5094         {
5095           /* If we get different answers from different members
5096              of the equivalence set this check must be in a dead
5097              code region.  Folding it to a trap representation
5098              would be correct here.  For now just return don't-know.  */
5099           if (retval != NULL
5100               && t != retval)
5101             {
5102               retval = NULL_TREE;
5103               break;
5104             }
5105           retval = t;
5106
5107           if (!sop)
5108             used_strict_overflow = 0;
5109           else if (used_strict_overflow < 0)
5110             used_strict_overflow = 1;
5111         }
5112     }
5113
5114   if (retval
5115       && used_strict_overflow > 0)
5116     *strict_overflow_p = true;
5117
5118   return retval;
5119 }
5120
5121
5122 /* Given a comparison code COMP and names N1 and N2, compare all the
5123    ranges equivalent to N1 against all the ranges equivalent to N2
5124    to determine the value of N1 COMP N2.  Return the same value
5125    returned by compare_ranges.  Set *STRICT_OVERFLOW_P to indicate
5126    whether we relied on an overflow infinity in the comparison.  */
5127
5128
5129 static tree
5130 compare_names (enum tree_code comp, tree n1, tree n2,
5131                bool *strict_overflow_p)
5132 {
5133   tree t, retval;
5134   bitmap e1, e2;
5135   bitmap_iterator bi1, bi2;
5136   unsigned i1, i2;
5137   int used_strict_overflow;
5138   static bitmap_obstack *s_obstack = NULL;
5139   static bitmap s_e1 = NULL, s_e2 = NULL;
5140
5141   /* Compare the ranges of every name equivalent to N1 against the
5142      ranges of every name equivalent to N2.  */
5143   e1 = get_value_range (n1)->equiv;
5144   e2 = get_value_range (n2)->equiv;
5145
5146   /* Use the fake bitmaps if e1 or e2 are not available.  */
5147   if (s_obstack == NULL)
5148     {
5149       s_obstack = XNEW (bitmap_obstack);
5150       bitmap_obstack_initialize (s_obstack);
5151       s_e1 = BITMAP_ALLOC (s_obstack);
5152       s_e2 = BITMAP_ALLOC (s_obstack);
5153     }
5154   if (e1 == NULL)
5155     e1 = s_e1;
5156   if (e2 == NULL)
5157     e2 = s_e2;
5158
5159   /* Add N1 and N2 to their own set of equivalences to avoid
5160      duplicating the body of the loop just to check N1 and N2
5161      ranges.  */
5162   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
5163   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
5164
5165   /* If the equivalence sets have a common intersection, then the two
5166      names can be compared without checking their ranges.  */
5167   if (bitmap_intersect_p (e1, e2))
5168     {
5169       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5170       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5171
5172       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
5173              ? boolean_true_node
5174              : boolean_false_node;
5175     }
5176
5177   /* Start at -1.  Set it to 0 if we do a comparison without relying
5178      on overflow, or 1 if all comparisons rely on overflow.  */
5179   used_strict_overflow = -1;
5180
5181   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
5182      N2 to their own set of equivalences to avoid duplicating the body
5183      of the loop just to check N1 and N2 ranges.  */
5184   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
5185     {
5186       value_range_t vr1 = get_vr_for_comparison (i1);
5187
5188       t = retval = NULL_TREE;
5189       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
5190         {
5191           bool sop = false;
5192
5193           value_range_t vr2 = get_vr_for_comparison (i2);
5194
5195           t = compare_ranges (comp, &vr1, &vr2, &sop);
5196           if (t)
5197             {
5198               /* If we get different answers from different members
5199                  of the equivalence set this check must be in a dead
5200                  code region.  Folding it to a trap representation
5201                  would be correct here.  For now just return don't-know.  */
5202               if (retval != NULL
5203                   && t != retval)
5204                 {
5205                   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5206                   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5207                   return NULL_TREE;
5208                 }
5209               retval = t;
5210
5211               if (!sop)
5212                 used_strict_overflow = 0;
5213               else if (used_strict_overflow < 0)
5214                 used_strict_overflow = 1;
5215             }
5216         }
5217
5218       if (retval)
5219         {
5220           bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5221           bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5222           if (used_strict_overflow > 0)
5223             *strict_overflow_p = true;
5224           return retval;
5225         }
5226     }
5227
5228   /* None of the equivalent ranges are useful in computing this
5229      comparison.  */
5230   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
5231   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
5232   return NULL_TREE;
5233 }
5234
5235 /* Helper function for vrp_evaluate_conditional_warnv. */
5236
5237 static tree
5238 vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
5239                                          tree op1, bool use_equiv_p,
5240                                          bool *strict_overflow_p)
5241 {
5242   /* We only deal with integral and pointer types.  */
5243   if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
5244       && !POINTER_TYPE_P (TREE_TYPE (op0)))
5245     return NULL_TREE;
5246
5247   if (use_equiv_p)
5248     {
5249       if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
5250         return compare_names (code, op0, op1,
5251                               strict_overflow_p);
5252       else if (TREE_CODE (op0) == SSA_NAME)
5253         return compare_name_with_value (code, op0, op1,
5254                                         strict_overflow_p);
5255       else if (TREE_CODE (op1) == SSA_NAME)
5256         return (compare_name_with_value
5257                 (swap_tree_comparison (code), op1, op0,
5258                  strict_overflow_p));
5259     }
5260   else
5261     {
5262       value_range_t *vr0, *vr1;
5263
5264       vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
5265       vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
5266
5267       if (vr0 && vr1)
5268         return compare_ranges (code, vr0, vr1,
5269                                strict_overflow_p);
5270       else if (vr0 && vr1 == NULL)
5271         return compare_range_with_value (code, vr0, op1,
5272                                          strict_overflow_p);
5273       else if (vr0 == NULL && vr1)
5274         return (compare_range_with_value
5275                 (swap_tree_comparison (code), vr1, op0,
5276                  strict_overflow_p));
5277     }
5278   return NULL_TREE;
5279 }
5280
5281 /* Given a conditional predicate COND, try to determine if COND yields
5282    true or false based on the value ranges of its operands.  Return
5283    BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
5284    BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
5285    NULL if the conditional cannot be evaluated at compile time.
5286
5287    If USE_EQUIV_P is true, the ranges of all the names equivalent with
5288    the operands in COND are used when trying to compute its value.
5289    This is only used during final substitution.  During propagation,
5290    we only check the range of each variable and not its equivalents.
5291
5292    Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow
5293    infinity to produce the result.  */
5294
5295 static tree
5296 vrp_evaluate_conditional_warnv (tree cond, bool use_equiv_p,
5297                                 bool *strict_overflow_p)
5298 {
5299   gcc_assert (TREE_CODE (cond) == SSA_NAME
5300               || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
5301
5302   if (TREE_CODE (cond) == SSA_NAME)
5303     {
5304       value_range_t *vr;
5305       tree retval;
5306
5307       if (use_equiv_p)
5308         retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node,
5309                                           strict_overflow_p);
5310       else
5311         {
5312           value_range_t *vr = get_value_range (cond);
5313           retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node,
5314                                              strict_overflow_p);
5315         }
5316
5317       /* If COND has a known boolean range, return it.  */
5318       if (retval)
5319         return retval;
5320
5321       /* Otherwise, if COND has a symbolic range of exactly one value,
5322          return it.  */
5323       vr = get_value_range (cond);
5324       if (vr->type == VR_RANGE && vr->min == vr->max)
5325         return vr->min;
5326     }
5327   else
5328     return vrp_evaluate_conditional_warnv_with_ops (TREE_CODE (cond),
5329                                                     TREE_OPERAND (cond, 0),
5330                                                     TREE_OPERAND (cond, 1),
5331                                                     use_equiv_p,
5332                                                     strict_overflow_p);
5333
5334   /* Anything else cannot be computed statically.  */
5335   return NULL_TREE;
5336 }
5337
5338 /* Given COND within STMT, try to simplify it based on value range
5339    information.  Return NULL if the conditional can not be evaluated.
5340    The ranges of all the names equivalent with the operands in COND
5341    will be used when trying to compute the value.  If the result is
5342    based on undefined signed overflow, issue a warning if
5343    appropriate.  */
5344
5345 tree
5346 vrp_evaluate_conditional (tree cond, tree stmt)
5347 {
5348   bool sop;
5349   tree ret;
5350
5351   sop = false;
5352   ret = vrp_evaluate_conditional_warnv (cond, true, &sop);
5353
5354   if (ret && sop)
5355     {
5356       enum warn_strict_overflow_code wc;
5357       const char* warnmsg;
5358
5359       if (is_gimple_min_invariant (ret))
5360         {
5361           wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
5362           warnmsg = G_("assuming signed overflow does not occur when "
5363                        "simplifying conditional to constant");
5364         }
5365       else
5366         {
5367           wc = WARN_STRICT_OVERFLOW_COMPARISON;
5368           warnmsg = G_("assuming signed overflow does not occur when "
5369                        "simplifying conditional");
5370         }
5371
5372       if (issue_strict_overflow_warning (wc))
5373         {
5374           location_t locus;
5375
5376           if (!EXPR_HAS_LOCATION (stmt))
5377             locus = input_location;
5378           else
5379             locus = EXPR_LOCATION (stmt);
5380           warning (OPT_Wstrict_overflow, "%H%s", &locus, warnmsg);
5381         }
5382     }
5383
5384   if (warn_type_limits
5385       && ret
5386       && TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
5387     {
5388       /* If the comparison is being folded and the operand on the LHS
5389          is being compared against a constant value that is outside of
5390          the natural range of OP0's type, then the predicate will
5391          always fold regardless of the value of OP0.  If -Wtype-limits
5392          was specified, emit a warning.  */
5393       const char *warnmsg = NULL;
5394       tree op0 = TREE_OPERAND (cond, 0);
5395       tree op1 = TREE_OPERAND (cond, 1);
5396       tree type = TREE_TYPE (op0);
5397       value_range_t *vr0 = get_value_range (op0);
5398
5399       if (vr0->type != VR_VARYING
5400           && INTEGRAL_TYPE_P (type)
5401           && vrp_val_is_min (vr0->min)
5402           && vrp_val_is_max (vr0->max)
5403           && is_gimple_min_invariant (op1))
5404         {
5405           if (integer_zerop (ret))
5406             warnmsg = G_("comparison always false due to limited range of "
5407                          "data type");
5408           else
5409             warnmsg = G_("comparison always true due to limited range of "
5410                          "data type");
5411         }
5412
5413       if (warnmsg)
5414         {
5415           location_t locus;
5416
5417           if (!EXPR_HAS_LOCATION (stmt))
5418             locus = input_location;
5419           else
5420             locus = EXPR_LOCATION (stmt);
5421
5422           warning (OPT_Wtype_limits, "%H%s", &locus, warnmsg);
5423         }
5424     }
5425
5426   return ret;
5427 }
5428
5429
5430 /* Visit conditional statement STMT.  If we can determine which edge
5431    will be taken out of STMT's basic block, record it in
5432    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
5433    SSA_PROP_VARYING.  */
5434
5435 static enum ssa_prop_result
5436 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
5437 {
5438   tree cond, val;
5439   bool sop;
5440
5441   *taken_edge_p = NULL;
5442
5443   /* FIXME.  Handle SWITCH_EXPRs.  */
5444   if (TREE_CODE (stmt) == SWITCH_EXPR)
5445     return SSA_PROP_VARYING;
5446
5447   cond = COND_EXPR_COND (stmt);
5448
5449   if (dump_file && (dump_flags & TDF_DETAILS))
5450     {
5451       tree use;
5452       ssa_op_iter i;
5453
5454       fprintf (dump_file, "\nVisiting conditional with predicate: ");
5455       print_generic_expr (dump_file, cond, 0);
5456       fprintf (dump_file, "\nWith known ranges\n");
5457
5458       FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
5459         {
5460           fprintf (dump_file, "\t");
5461           print_generic_expr (dump_file, use, 0);
5462           fprintf (dump_file, ": ");
5463           dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
5464         }
5465
5466       fprintf (dump_file, "\n");
5467     }
5468
5469   /* Compute the value of the predicate COND by checking the known
5470      ranges of each of its operands.
5471
5472      Note that we cannot evaluate all the equivalent ranges here
5473      because those ranges may not yet be final and with the current
5474      propagation strategy, we cannot determine when the value ranges
5475      of the names in the equivalence set have changed.
5476
5477      For instance, given the following code fragment
5478
5479         i_5 = PHI <8, i_13>
5480         ...
5481         i_14 = ASSERT_EXPR <i_5, i_5 != 0>
5482         if (i_14 == 1)
5483           ...
5484
5485      Assume that on the first visit to i_14, i_5 has the temporary
5486      range [8, 8] because the second argument to the PHI function is
5487      not yet executable.  We derive the range ~[0, 0] for i_14 and the
5488      equivalence set { i_5 }.  So, when we visit 'if (i_14 == 1)' for
5489      the first time, since i_14 is equivalent to the range [8, 8], we
5490      determine that the predicate is always false.
5491
5492      On the next round of propagation, i_13 is determined to be
5493      VARYING, which causes i_5 to drop down to VARYING.  So, another
5494      visit to i_14 is scheduled.  In this second visit, we compute the
5495      exact same range and equivalence set for i_14, namely ~[0, 0] and
5496      { i_5 }.  But we did not have the previous range for i_5
5497      registered, so vrp_visit_assignment thinks that the range for
5498      i_14 has not changed.  Therefore, the predicate 'if (i_14 == 1)'
5499      is not visited again, which stops propagation from visiting
5500      statements in the THEN clause of that if().
5501
5502      To properly fix this we would need to keep the previous range
5503      value for the names in the equivalence set.  This way we would've
5504      discovered that from one visit to the other i_5 changed from
5505      range [8, 8] to VR_VARYING.
5506
5507      However, fixing this apparent limitation may not be worth the
5508      additional checking.  Testing on several code bases (GCC, DLV,
5509      MICO, TRAMP3D and SPEC2000) showed that doing this results in
5510      4 more predicates folded in SPEC.  */
5511   sop = false;
5512   val = vrp_evaluate_conditional_warnv (cond, false, &sop);
5513   if (val)
5514     {
5515       if (!sop)
5516         *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
5517       else
5518         {
5519           if (dump_file && (dump_flags & TDF_DETAILS))
5520             fprintf (dump_file,
5521                      "\nIgnoring predicate evaluation because "
5522                      "it assumes that signed overflow is undefined");
5523           val = NULL_TREE;
5524         }
5525     }
5526
5527   if (dump_file && (dump_flags & TDF_DETAILS))
5528     {
5529       fprintf (dump_file, "\nPredicate evaluates to: ");
5530       if (val == NULL_TREE)
5531         fprintf (dump_file, "DON'T KNOW\n");
5532       else
5533         print_generic_stmt (dump_file, val, 0);
5534     }
5535
5536   return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
5537 }
5538
5539
5540 /* Evaluate statement STMT.  If the statement produces a useful range,
5541    return SSA_PROP_INTERESTING and record the SSA name with the
5542    interesting range into *OUTPUT_P.
5543
5544    If STMT is a conditional branch and we can determine its truth
5545    value, the taken edge is recorded in *TAKEN_EDGE_P.
5546
5547    If STMT produces a varying value, return SSA_PROP_VARYING.  */
5548
5549 static enum ssa_prop_result
5550 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
5551 {
5552   tree def;
5553   ssa_op_iter iter;
5554   stmt_ann_t ann;
5555
5556   if (dump_file && (dump_flags & TDF_DETAILS))
5557     {
5558       fprintf (dump_file, "\nVisiting statement:\n");
5559       print_generic_stmt (dump_file, stmt, dump_flags);
5560       fprintf (dump_file, "\n");
5561     }
5562
5563   ann = stmt_ann (stmt);
5564   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
5565     {
5566       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
5567
5568       /* In general, assignments with virtual operands are not useful
5569          for deriving ranges, with the obvious exception of calls to
5570          builtin functions.  */
5571       if ((TREE_CODE (rhs) == CALL_EXPR
5572            && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
5573            && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
5574            && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
5575           || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
5576         return vrp_visit_assignment (stmt, output_p);
5577     }
5578   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
5579     return vrp_visit_cond_stmt (stmt, taken_edge_p);
5580
5581   /* All other statements produce nothing of interest for VRP, so mark
5582      their outputs varying and prevent further simulation.  */
5583   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
5584     set_value_range_to_varying (get_value_range (def));
5585
5586   return SSA_PROP_VARYING;
5587 }
5588
5589
5590 /* Meet operation for value ranges.  Given two value ranges VR0 and
5591    VR1, store in VR0 a range that contains both VR0 and VR1.  This
5592    may not be the smallest possible such range.  */
5593
5594 static void
5595 vrp_meet (value_range_t *vr0, value_range_t *vr1)
5596 {
5597   if (vr0->type == VR_UNDEFINED)
5598     {
5599       copy_value_range (vr0, vr1);
5600       return;
5601     }
5602
5603   if (vr1->type == VR_UNDEFINED)
5604     {
5605       /* Nothing to do.  VR0 already has the resulting range.  */
5606       return;
5607     }
5608
5609   if (vr0->type == VR_VARYING)
5610     {
5611       /* Nothing to do.  VR0 already has the resulting range.  */
5612       return;
5613     }
5614
5615   if (vr1->type == VR_VARYING)
5616     {
5617       set_value_range_to_varying (vr0);
5618       return;
5619     }
5620
5621   if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
5622     {
5623       int cmp;
5624       tree min, max;
5625
5626       /* Compute the convex hull of the ranges.  The lower limit of
5627          the new range is the minimum of the two ranges.  If they
5628          cannot be compared, then give up.  */
5629       cmp = compare_values (vr0->min, vr1->min);
5630       if (cmp == 0 || cmp == 1)
5631         min = vr1->min;
5632       else if (cmp == -1)
5633         min = vr0->min;
5634       else
5635         goto give_up;
5636
5637       /* Similarly, the upper limit of the new range is the maximum
5638          of the two ranges.  If they cannot be compared, then
5639          give up.  */
5640       cmp = compare_values (vr0->max, vr1->max);
5641       if (cmp == 0 || cmp == -1)
5642         max = vr1->max;
5643       else if (cmp == 1)
5644         max = vr0->max;
5645       else
5646         goto give_up;
5647
5648       /* Check for useless ranges.  */
5649       if (INTEGRAL_TYPE_P (TREE_TYPE (min))
5650           && ((vrp_val_is_min (min) || is_overflow_infinity (min))
5651               && (vrp_val_is_max (max) || is_overflow_infinity (max))))
5652         goto give_up;
5653
5654       /* The resulting set of equivalences is the intersection of
5655          the two sets.  */
5656       if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5657         bitmap_and_into (vr0->equiv, vr1->equiv);
5658       else if (vr0->equiv && !vr1->equiv)
5659         bitmap_clear (vr0->equiv);
5660
5661       set_value_range (vr0, vr0->type, min, max, vr0->equiv);
5662     }
5663   else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
5664     {
5665       /* Two anti-ranges meet only if their complements intersect.
5666          Only handle the case of identical ranges.  */
5667       if (compare_values (vr0->min, vr1->min) == 0
5668           && compare_values (vr0->max, vr1->max) == 0
5669           && compare_values (vr0->min, vr0->max) == 0)
5670         {
5671           /* The resulting set of equivalences is the intersection of
5672              the two sets.  */
5673           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5674             bitmap_and_into (vr0->equiv, vr1->equiv);
5675           else if (vr0->equiv && !vr1->equiv)
5676             bitmap_clear (vr0->equiv);
5677         }
5678       else
5679         goto give_up;
5680     }
5681   else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
5682     {
5683       /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
5684          only handle the case where the ranges have an empty intersection.
5685          The result of the meet operation is the anti-range.  */
5686       if (!symbolic_range_p (vr0)
5687           && !symbolic_range_p (vr1)
5688           && !value_ranges_intersect_p (vr0, vr1))
5689         {
5690           /* Copy most of VR1 into VR0.  Don't copy VR1's equivalence
5691              set.  We need to compute the intersection of the two
5692              equivalence sets.  */
5693           if (vr1->type == VR_ANTI_RANGE)
5694             set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
5695
5696           /* The resulting set of equivalences is the intersection of
5697              the two sets.  */
5698           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
5699             bitmap_and_into (vr0->equiv, vr1->equiv);
5700           else if (vr0->equiv && !vr1->equiv)
5701             bitmap_clear (vr0->equiv);
5702         }
5703       else
5704         goto give_up;
5705     }
5706   else
5707     gcc_unreachable ();
5708
5709   return;
5710
5711 give_up:
5712   /* Failed to find an efficient meet.  Before giving up and setting
5713      the result to VARYING, see if we can at least derive a useful
5714      anti-range.  FIXME, all this nonsense about distinguishing
5715      anti-ranges from ranges is necessary because of the odd
5716      semantics of range_includes_zero_p and friends.  */
5717   if (!symbolic_range_p (vr0)
5718       && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
5719           || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
5720       && !symbolic_range_p (vr1)
5721       && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
5722           || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
5723     {
5724       set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
5725
5726       /* Since this meet operation did not result from the meeting of
5727          two equivalent names, VR0 cannot have any equivalences.  */
5728       if (vr0->equiv)
5729         bitmap_clear (vr0->equiv);
5730     }
5731   else
5732     set_value_range_to_varying (vr0);
5733 }
5734
5735
5736 /* Visit all arguments for PHI node PHI that flow through executable
5737    edges.  If a valid value range can be derived from all the incoming
5738    value ranges, set a new range for the LHS of PHI.  */
5739
5740 static enum ssa_prop_result
5741 vrp_visit_phi_node (tree phi)
5742 {
5743   int i;
5744   tree lhs = PHI_RESULT (phi);
5745   value_range_t *lhs_vr = get_value_range (lhs);
5746   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
5747   int edges, old_edges;
5748
5749   copy_value_range (&vr_result, lhs_vr);
5750
5751   if (dump_file && (dump_flags & TDF_DETAILS))
5752     {
5753       fprintf (dump_file, "\nVisiting PHI node: ");
5754       print_generic_expr (dump_file, phi, dump_flags);
5755     }
5756
5757   edges = 0;
5758   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
5759     {
5760       edge e = PHI_ARG_EDGE (phi, i);
5761
5762       if (dump_file && (dump_flags & TDF_DETAILS))
5763         {
5764           fprintf (dump_file,
5765               "\n    Argument #%d (%d -> %d %sexecutable)\n",
5766               i, e->src->index, e->dest->index,
5767               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
5768         }
5769
5770       if (e->flags & EDGE_EXECUTABLE)
5771         {
5772           tree arg = PHI_ARG_DEF (phi, i);
5773           value_range_t vr_arg;
5774
5775           ++edges;
5776
5777           if (TREE_CODE (arg) == SSA_NAME)
5778             {
5779               vr_arg = *(get_value_range (arg));
5780             }
5781           else
5782             {
5783               if (is_overflow_infinity (arg))
5784                 {
5785                   arg = copy_node (arg);
5786                   TREE_OVERFLOW (arg) = 0;
5787                 }
5788
5789               vr_arg.type = VR_RANGE;
5790               vr_arg.min = arg;
5791               vr_arg.max = arg;
5792               vr_arg.equiv = NULL;
5793             }
5794
5795           if (dump_file && (dump_flags & TDF_DETAILS))
5796             {
5797               fprintf (dump_file, "\t");
5798               print_generic_expr (dump_file, arg, dump_flags);
5799               fprintf (dump_file, "\n\tValue: ");
5800               dump_value_range (dump_file, &vr_arg);
5801               fprintf (dump_file, "\n");
5802             }
5803
5804           vrp_meet (&vr_result, &vr_arg);
5805
5806           if (vr_result.type == VR_VARYING)
5807             break;
5808         }
5809     }
5810
5811   if (vr_result.type == VR_VARYING)
5812     goto varying;
5813
5814   old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
5815   vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
5816
5817   /* To prevent infinite iterations in the algorithm, derive ranges
5818      when the new value is slightly bigger or smaller than the
5819      previous one.  We don't do this if we have seen a new executable
5820      edge; this helps us avoid an overflow infinity for conditionals
5821      which are not in a loop.  */
5822   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
5823       && edges <= old_edges)
5824     {
5825       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
5826         {
5827           int cmp_min = compare_values (lhs_vr->min, vr_result.min);
5828           int cmp_max = compare_values (lhs_vr->max, vr_result.max);
5829
5830           /* If the new minimum is smaller or larger than the previous
5831              one, go all the way to -INF.  In the first case, to avoid
5832              iterating millions of times to reach -INF, and in the
5833              other case to avoid infinite bouncing between different
5834              minimums.  */
5835           if (cmp_min > 0 || cmp_min < 0)
5836             {
5837               /* If we will end up with a (-INF, +INF) range, set it
5838                  to VARYING.  */
5839               if (vrp_val_is_max (vr_result.max))
5840                 goto varying;
5841
5842               if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
5843                   || !vrp_var_may_overflow (lhs, phi))
5844                 vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
5845               else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
5846                 vr_result.min =
5847                   negative_overflow_infinity (TREE_TYPE (vr_result.min));
5848               else
5849                 goto varying;
5850             }
5851
5852           /* Similarly, if the new maximum is smaller or larger than
5853              the previous one, go all the way to +INF.  */
5854           if (cmp_max < 0 || cmp_max > 0)
5855             {
5856               /* If we will end up with a (-INF, +INF) range, set it
5857                  to VARYING.  */
5858               if (vrp_val_is_min (vr_result.min))
5859                 goto varying;
5860
5861               if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
5862                   || !vrp_var_may_overflow (lhs, phi))
5863                 vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
5864               else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
5865                 vr_result.max =
5866                   positive_overflow_infinity (TREE_TYPE (vr_result.max));
5867               else
5868                 goto varying;
5869             }
5870         }
5871     }
5872
5873   /* If the new range is different than the previous value, keep
5874      iterating.  */
5875   if (update_value_range (lhs, &vr_result))
5876     return SSA_PROP_INTERESTING;
5877
5878   /* Nothing changed, don't add outgoing edges.  */
5879   return SSA_PROP_NOT_INTERESTING;
5880
5881   /* No match found.  Set the LHS to VARYING.  */
5882 varying:
5883   set_value_range_to_varying (lhs_vr);
5884   return SSA_PROP_VARYING;
5885 }
5886
5887 /* Simplify a division or modulo operator to a right shift or
5888    bitwise and if the first operand is unsigned or is greater
5889    than zero and the second operand is an exact power of two.  */
5890
5891 static void
5892 simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
5893 {
5894   tree val = NULL;
5895   tree op = TREE_OPERAND (rhs, 0);
5896   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
5897
5898   if (TYPE_UNSIGNED (TREE_TYPE (op)))
5899     {
5900       val = integer_one_node;
5901     }
5902   else
5903     {
5904       bool sop = false;
5905
5906       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
5907
5908       if (val
5909           && sop
5910           && integer_onep (val)
5911           && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
5912         {
5913           location_t locus;
5914
5915           if (!EXPR_HAS_LOCATION (stmt))
5916             locus = input_location;
5917           else
5918             locus = EXPR_LOCATION (stmt);
5919           warning (OPT_Wstrict_overflow,
5920                    ("%Hassuming signed overflow does not occur when "
5921                     "simplifying / or %% to >> or &"),
5922                    &locus);
5923         }
5924     }
5925
5926   if (val && integer_onep (val))
5927     {
5928       tree t;
5929       tree op0 = TREE_OPERAND (rhs, 0);
5930       tree op1 = TREE_OPERAND (rhs, 1);
5931
5932       if (rhs_code == TRUNC_DIV_EXPR)
5933         {
5934           t = build_int_cst (NULL_TREE, tree_log2 (op1));
5935           t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
5936         }
5937       else
5938         {
5939           t = build_int_cst (TREE_TYPE (op1), 1);
5940           t = int_const_binop (MINUS_EXPR, op1, t, 0);
5941           t = fold_convert (TREE_TYPE (op0), t);
5942           t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
5943         }
5944
5945       GIMPLE_STMT_OPERAND (stmt, 1) = t;
5946       update_stmt (stmt);
5947     }
5948 }
5949
5950 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
5951    ABS_EXPR.  If the operand is <= 0, then simplify the
5952    ABS_EXPR into a NEGATE_EXPR.  */
5953
5954 static void
5955 simplify_abs_using_ranges (tree stmt, tree rhs)
5956 {
5957   tree val = NULL;
5958   tree op = TREE_OPERAND (rhs, 0);
5959   tree type = TREE_TYPE (op);
5960   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
5961
5962   if (TYPE_UNSIGNED (type))
5963     {
5964       val = integer_zero_node;
5965     }
5966   else if (vr)
5967     {
5968       bool sop = false;
5969
5970       val = compare_range_with_value (LE_EXPR, vr, integer_zero_node, &sop);
5971       if (!val)
5972         {
5973           sop = false;
5974           val = compare_range_with_value (GE_EXPR, vr, integer_zero_node,
5975                                           &sop);
5976
5977           if (val)
5978             {
5979               if (integer_zerop (val))
5980                 val = integer_one_node;
5981               else if (integer_onep (val))
5982                 val = integer_zero_node;
5983             }
5984         }
5985
5986       if (val
5987           && (integer_onep (val) || integer_zerop (val)))
5988         {
5989           tree t;
5990
5991           if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
5992             {
5993               location_t locus;
5994
5995               if (!EXPR_HAS_LOCATION (stmt))
5996                 locus = input_location;
5997               else
5998                 locus = EXPR_LOCATION (stmt);
5999               warning (OPT_Wstrict_overflow,
6000                        ("%Hassuming signed overflow does not occur when "
6001                         "simplifying abs (X) to X or -X"),
6002                        &locus);
6003             }
6004
6005           if (integer_onep (val))
6006             t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
6007           else
6008             t = op;
6009
6010           GIMPLE_STMT_OPERAND (stmt, 1) = t;
6011           update_stmt (stmt);
6012         }
6013     }
6014 }
6015
6016 /* We are comparing trees OP0 and OP1 using COND_CODE.  OP0 has
6017    a known value range VR.
6018
6019    If there is one and only one value which will satisfy the
6020    conditional, then return that value.  Else return NULL.  */
6021
6022 static tree
6023 test_for_singularity (enum tree_code cond_code, tree op0,
6024                       tree op1, value_range_t *vr)
6025 {
6026   tree min = NULL;
6027   tree max = NULL;
6028
6029   /* Extract minimum/maximum values which satisfy the
6030      the conditional as it was written.  */
6031   if (cond_code == LE_EXPR || cond_code == LT_EXPR)
6032     {
6033       /* This should not be negative infinity; there is no overflow
6034          here.  */
6035       min = TYPE_MIN_VALUE (TREE_TYPE (op0));
6036
6037       max = op1;
6038       if (cond_code == LT_EXPR && !is_overflow_infinity (max))
6039         {
6040           tree one = build_int_cst (TREE_TYPE (op0), 1);
6041           max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
6042           if (EXPR_P (max))
6043             TREE_NO_WARNING (max) = 1;
6044         }
6045     }
6046   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
6047     {
6048       /* This should not be positive infinity; there is no overflow
6049          here.  */
6050       max = TYPE_MAX_VALUE (TREE_TYPE (op0));
6051
6052       min = op1;
6053       if (cond_code == GT_EXPR && !is_overflow_infinity (min))
6054         {
6055           tree one = build_int_cst (TREE_TYPE (op0), 1);
6056           min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
6057           if (EXPR_P (min))
6058             TREE_NO_WARNING (min) = 1;
6059         }
6060     }
6061
6062   /* Now refine the minimum and maximum values using any
6063      value range information we have for op0.  */
6064   if (min && max)
6065     {
6066       if (compare_values (vr->min, min) == -1)
6067         min = min;
6068       else
6069         min = vr->min;
6070       if (compare_values (vr->max, max) == 1)
6071         max = max;
6072       else
6073         max = vr->max;
6074
6075       /* If the new min/max values have converged to a single value,
6076          then there is only one value which can satisfy the condition,
6077          return that value.  */
6078       if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
6079         return min;
6080     }
6081   return NULL;
6082 }
6083
6084 /* Simplify a conditional using a relational operator to an equality
6085    test if the range information indicates only one value can satisfy
6086    the original conditional.  */
6087
6088 static void
6089 simplify_cond_using_ranges (tree stmt)
6090 {
6091   tree cond = COND_EXPR_COND (stmt);
6092   tree op0 = TREE_OPERAND (cond, 0);
6093   tree op1 = TREE_OPERAND (cond, 1);
6094   enum tree_code cond_code = TREE_CODE (cond);
6095
6096   if (cond_code != NE_EXPR
6097       && cond_code != EQ_EXPR
6098       && TREE_CODE (op0) == SSA_NAME
6099       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
6100       && is_gimple_min_invariant (op1))
6101     {
6102       value_range_t *vr = get_value_range (op0);
6103
6104       /* If we have range information for OP0, then we might be
6105          able to simplify this conditional. */
6106       if (vr->type == VR_RANGE)
6107         {
6108           tree new = test_for_singularity (cond_code, op0, op1, vr);
6109
6110           if (new)
6111             {
6112               if (dump_file)
6113                 {
6114                   fprintf (dump_file, "Simplified relational ");
6115                   print_generic_expr (dump_file, cond, 0);
6116                   fprintf (dump_file, " into ");
6117                 }
6118
6119               COND_EXPR_COND (stmt)
6120                 = build2 (EQ_EXPR, boolean_type_node, op0, new);
6121               update_stmt (stmt);
6122
6123               if (dump_file)
6124                 {
6125                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
6126                   fprintf (dump_file, "\n");
6127                 }
6128               return;
6129
6130             }
6131
6132           /* Try again after inverting the condition.  We only deal
6133              with integral types here, so no need to worry about
6134              issues with inverting FP comparisons.  */
6135           cond_code = invert_tree_comparison (cond_code, false);
6136           new = test_for_singularity (cond_code, op0, op1, vr);
6137
6138           if (new)
6139             {
6140               if (dump_file)
6141                 {
6142                   fprintf (dump_file, "Simplified relational ");
6143                   print_generic_expr (dump_file, cond, 0);
6144                   fprintf (dump_file, " into ");
6145                 }
6146
6147               COND_EXPR_COND (stmt)
6148                 = build2 (NE_EXPR, boolean_type_node, op0, new);
6149               update_stmt (stmt);
6150
6151               if (dump_file)
6152                 {
6153                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
6154                   fprintf (dump_file, "\n");
6155                 }
6156               return;
6157
6158             }
6159         }
6160     }
6161 }
6162
6163 /* Simplify STMT using ranges if possible.  */
6164
6165 void
6166 simplify_stmt_using_ranges (tree stmt)
6167 {
6168   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
6169     {
6170       tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
6171       enum tree_code rhs_code = TREE_CODE (rhs);
6172
6173       /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
6174          and BIT_AND_EXPR respectively if the first operand is greater
6175          than zero and the second operand is an exact power of two.  */
6176       if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
6177           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
6178           && integer_pow2p (TREE_OPERAND (rhs, 1)))
6179         simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
6180
6181       /* Transform ABS (X) into X or -X as appropriate.  */
6182       if (rhs_code == ABS_EXPR
6183           && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
6184           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
6185         simplify_abs_using_ranges (stmt, rhs);
6186     }
6187   else if (TREE_CODE (stmt) == COND_EXPR
6188            && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
6189     {
6190       simplify_cond_using_ranges (stmt);
6191     }
6192 }
6193
6194 /* Stack of dest,src equivalency pairs that need to be restored after
6195    each attempt to thread a block's incoming edge to an outgoing edge.
6196
6197    A NULL entry is used to mark the end of pairs which need to be
6198    restored.  */
6199 static VEC(tree,heap) *stack;
6200
6201 /* A trivial wrapper so that we can present the generic jump threading
6202    code with a simple API for simplifying statements.  STMT is the
6203    statement we want to simplify, WITHIN_STMT provides the location
6204    for any overflow warnings.  */
6205
6206 static tree
6207 simplify_stmt_for_jump_threading (tree stmt, tree within_stmt)
6208 {
6209   /* We only use VRP information to simplify conditionals.  This is
6210      overly conservative, but it's unclear if doing more would be
6211      worth the compile time cost.  */
6212   if (TREE_CODE (stmt) != COND_EXPR)
6213     return NULL;
6214
6215   return vrp_evaluate_conditional (COND_EXPR_COND (stmt), within_stmt);
6216 }
6217
6218 /* Blocks which have more than one predecessor and more than
6219    one successor present jump threading opportunities.  ie,
6220    when the block is reached from a specific predecessor, we
6221    may be able to determine which of the outgoing edges will
6222    be traversed.  When this optimization applies, we are able
6223    to avoid conditionals at runtime and we may expose secondary
6224    optimization opportunities.
6225
6226    This routine is effectively a driver for the generic jump
6227    threading code.  It basically just presents the generic code
6228    with edges that may be suitable for jump threading.
6229
6230    Unlike DOM, we do not iterate VRP if jump threading was successful.
6231    While iterating may expose new opportunities for VRP, it is expected
6232    those opportunities would be very limited and the compile time cost
6233    to expose those opportunities would be significant.
6234
6235    As jump threading opportunities are discovered, they are registered
6236    for later realization.  */
6237
6238 static void
6239 identify_jump_threads (void)
6240 {
6241   basic_block bb;
6242   tree dummy;
6243
6244   /* Ugh.  When substituting values earlier in this pass we can
6245      wipe the dominance information.  So rebuild the dominator
6246      information as we need it within the jump threading code.  */
6247   calculate_dominance_info (CDI_DOMINATORS);
6248
6249   /* We do not allow VRP information to be used for jump threading
6250      across a back edge in the CFG.  Otherwise it becomes too
6251      difficult to avoid eliminating loop exit tests.  Of course
6252      EDGE_DFS_BACK is not accurate at this time so we have to
6253      recompute it.  */
6254   mark_dfs_back_edges ();
6255
6256   /* Allocate our unwinder stack to unwind any temporary equivalences
6257      that might be recorded.  */
6258   stack = VEC_alloc (tree, heap, 20);
6259
6260   /* To avoid lots of silly node creation, we create a single
6261      conditional and just modify it in-place when attempting to
6262      thread jumps.  */
6263   dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
6264   dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
6265
6266   /* Walk through all the blocks finding those which present a
6267      potential jump threading opportunity.  We could set this up
6268      as a dominator walker and record data during the walk, but
6269      I doubt it's worth the effort for the classes of jump
6270      threading opportunities we are trying to identify at this
6271      point in compilation.  */
6272   FOR_EACH_BB (bb)
6273     {
6274       tree last, cond;
6275
6276       /* If the generic jump threading code does not find this block
6277          interesting, then there is nothing to do.  */
6278       if (! potentially_threadable_block (bb))
6279         continue;
6280
6281       /* We only care about blocks ending in a COND_EXPR.  While there
6282          may be some value in handling SWITCH_EXPR here, I doubt it's
6283          terribly important.  */
6284       last = bsi_stmt (bsi_last (bb));
6285       if (TREE_CODE (last) != COND_EXPR)
6286         continue;
6287
6288       /* We're basically looking for any kind of conditional with
6289          integral type arguments.  */
6290       cond = COND_EXPR_COND (last);
6291       if ((TREE_CODE (cond) == SSA_NAME
6292            && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
6293           || (COMPARISON_CLASS_P (cond)
6294               && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
6295               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
6296               && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
6297                   || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
6298               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
6299         {
6300           edge_iterator ei;
6301           edge e;
6302
6303           /* We've got a block with multiple predecessors and multiple
6304              successors which also ends in a suitable conditional.  For
6305              each predecessor, see if we can thread it to a specific
6306              successor.  */
6307           FOR_EACH_EDGE (e, ei, bb->preds)
6308             {
6309               /* Do not thread across back edges or abnormal edges
6310                  in the CFG.  */
6311               if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
6312                 continue;
6313
6314               thread_across_edge (dummy, e, true,
6315                                   &stack,
6316                                   simplify_stmt_for_jump_threading);
6317             }
6318         }
6319     }
6320
6321   /* We do not actually update the CFG or SSA graphs at this point as
6322      ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
6323      handle ASSERT_EXPRs gracefully.  */
6324 }
6325
6326 /* We identified all the jump threading opportunities earlier, but could
6327    not transform the CFG at that time.  This routine transforms the
6328    CFG and arranges for the dominator tree to be rebuilt if necessary.
6329
6330    Note the SSA graph update will occur during the normal TODO
6331    processing by the pass manager.  */
6332 static void
6333 finalize_jump_threads (void)
6334 {
6335   thread_through_all_blocks (false);
6336   VEC_free (tree, heap, stack);
6337 }
6338
6339
6340 /* Traverse all the blocks folding conditionals with known ranges.  */
6341
6342 static void
6343 vrp_finalize (void)
6344 {
6345   size_t i;
6346   prop_value_t *single_val_range;
6347   bool do_value_subst_p;
6348
6349   if (dump_file)
6350     {
6351       fprintf (dump_file, "\nValue ranges after VRP:\n\n");
6352       dump_all_value_ranges (dump_file);
6353       fprintf (dump_file, "\n");
6354     }
6355
6356   /* We may have ended with ranges that have exactly one value.  Those
6357      values can be substituted as any other copy/const propagated
6358      value using substitute_and_fold.  */
6359   single_val_range = XCNEWVEC (prop_value_t, num_ssa_names);
6360
6361   do_value_subst_p = false;
6362   for (i = 0; i < num_ssa_names; i++)
6363     if (vr_value[i]
6364         && vr_value[i]->type == VR_RANGE
6365         && vr_value[i]->min == vr_value[i]->max)
6366       {
6367         single_val_range[i].value = vr_value[i]->min;
6368         do_value_subst_p = true;
6369       }
6370
6371   if (!do_value_subst_p)
6372     {
6373       /* We found no single-valued ranges, don't waste time trying to
6374          do single value substitution in substitute_and_fold.  */
6375       free (single_val_range);
6376       single_val_range = NULL;
6377     }
6378
6379   substitute_and_fold (single_val_range, true);
6380
6381   if (warn_array_bounds)
6382       check_all_array_refs ();
6383
6384   /* We must identify jump threading opportunities before we release
6385      the datastructures built by VRP.  */
6386   identify_jump_threads ();
6387
6388   /* Free allocated memory.  */
6389   for (i = 0; i < num_ssa_names; i++)
6390     if (vr_value[i])
6391       {
6392         BITMAP_FREE (vr_value[i]->equiv);
6393         free (vr_value[i]);
6394       }
6395
6396   free (single_val_range);
6397   free (vr_value);
6398   free (vr_phi_edge_counts);
6399
6400   /* So that we can distinguish between VRP data being available
6401      and not available.  */
6402   vr_value = NULL;
6403   vr_phi_edge_counts = NULL;
6404 }
6405
6406 /* Calculates number of iterations for all loops, to ensure that they are
6407    cached.  */
6408
6409 static void
6410 record_numbers_of_iterations (void)
6411 {
6412   loop_iterator li;
6413   struct loop *loop;
6414
6415   FOR_EACH_LOOP (li, loop, 0)
6416     {
6417       number_of_latch_executions (loop);
6418     }
6419 }
6420
6421 /* Main entry point to VRP (Value Range Propagation).  This pass is
6422    loosely based on J. R. C. Patterson, ``Accurate Static Branch
6423    Prediction by Value Range Propagation,'' in SIGPLAN Conference on
6424    Programming Language Design and Implementation, pp. 67-78, 1995.
6425    Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
6426
6427    This is essentially an SSA-CCP pass modified to deal with ranges
6428    instead of constants.
6429
6430    While propagating ranges, we may find that two or more SSA name
6431    have equivalent, though distinct ranges.  For instance,
6432
6433      1  x_9 = p_3->a;
6434      2  p_4 = ASSERT_EXPR <p_3, p_3 != 0>
6435      3  if (p_4 == q_2)
6436      4    p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
6437      5  endif
6438      6  if (q_2)
6439
6440    In the code above, pointer p_5 has range [q_2, q_2], but from the
6441    code we can also determine that p_5 cannot be NULL and, if q_2 had
6442    a non-varying range, p_5's range should also be compatible with it.
6443
6444    These equivalences are created by two expressions: ASSERT_EXPR and
6445    copy operations.  Since p_5 is an assertion on p_4, and p_4 was the
6446    result of another assertion, then we can use the fact that p_5 and
6447    p_4 are equivalent when evaluating p_5's range.
6448
6449    Together with value ranges, we also propagate these equivalences
6450    between names so that we can take advantage of information from
6451    multiple ranges when doing final replacement.  Note that this
6452    equivalency relation is transitive but not symmetric.
6453
6454    In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
6455    cannot assert that q_2 is equivalent to p_5 because q_2 may be used
6456    in contexts where that assertion does not hold (e.g., in line 6).
6457
6458    TODO, the main difference between this pass and Patterson's is that
6459    we do not propagate edge probabilities.  We only compute whether
6460    edges can be taken or not.  That is, instead of having a spectrum
6461    of jump probabilities between 0 and 1, we only deal with 0, 1 and
6462    DON'T KNOW.  In the future, it may be worthwhile to propagate
6463    probabilities to aid branch prediction.  */
6464
6465 static unsigned int
6466 execute_vrp (void)
6467 {
6468   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
6469   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
6470   scev_initialize ();
6471
6472   insert_range_assertions ();
6473
6474   /* Compute the # of iterations for each loop before we start the VRP
6475      analysis.  The value ranges determined by VRP are used in expression
6476      simplification, that is also used by the # of iterations analysis.
6477      However, in the middle of the VRP analysis, the value ranges do not take
6478      all the possible paths in CFG into account, so they do not have to be
6479      correct, and the # of iterations analysis can obtain wrong results.
6480      This is a problem, since the results of the # of iterations analysis
6481      are cached, so these mistakes would not be corrected when the value
6482      ranges are corrected.  */
6483   record_numbers_of_iterations ();
6484
6485   vrp_initialize ();
6486   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
6487   vrp_finalize ();
6488
6489   /* ASSERT_EXPRs must be removed before finalizing jump threads
6490      as finalizing jump threads calls the CFG cleanup code which
6491      does not properly handle ASSERT_EXPRs.  */
6492   remove_range_assertions ();
6493
6494   /* If we exposed any new variables, go ahead and put them into
6495      SSA form now, before we handle jump threading.  This simplifies
6496      interactions between rewriting of _DECL nodes into SSA form
6497      and rewriting SSA_NAME nodes into SSA form after block
6498      duplication and CFG manipulation.  */
6499   update_ssa (TODO_update_ssa);
6500
6501   finalize_jump_threads ();
6502   scev_finalize ();
6503   loop_optimizer_finalize ();
6504
6505   return 0;
6506 }
6507
6508 static bool
6509 gate_vrp (void)
6510 {
6511   return flag_tree_vrp != 0;
6512 }
6513
6514 struct gimple_opt_pass pass_vrp =
6515 {
6516  {
6517   GIMPLE_PASS,
6518   "vrp",                                /* name */
6519   gate_vrp,                             /* gate */
6520   execute_vrp,                          /* execute */
6521   NULL,                                 /* sub */
6522   NULL,                                 /* next */
6523   0,                                    /* static_pass_number */
6524   TV_TREE_VRP,                          /* tv_id */
6525   PROP_ssa | PROP_alias,                /* properties_required */
6526   0,                                    /* properties_provided */
6527   0,                                    /* properties_destroyed */
6528   0,                                    /* todo_flags_start */
6529   TODO_cleanup_cfg
6530     | TODO_ggc_collect
6531     | TODO_verify_ssa
6532     | TODO_dump_func
6533     | TODO_update_ssa                   /* todo_flags_finish */
6534  }
6535 };