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