gcc/tree-vrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005, 2006 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 "cfgloop.h"
  36 #include "tree-scalar-evolution.h"
  37 #include "tree-ssa-propagate.h"
  38 #include "tree-chrec.h"
  39
  40 /* Set of SSA names found during the dominator traversal of a
  41    sub-graph in find_assert_locations.  */
  42 static sbitmap found_in_subgraph;
  43
  44 /* Local functions.  */
  45 static int compare_values (tree val1, tree val2);
  46
  47 /* Location information for ASSERT_EXPRs.  Each instance of this
  48    structure describes an ASSERT_EXPR for an SSA name.  Since a single
  49    SSA name may have more than one assertion associated with it, these
  50    locations are kept in a linked list attached to the corresponding
  51    SSA name.  */
  52 struct assert_locus_d
  53 {
  54   /* Basic block where the assertion would be inserted.  */
  55   basic_block bb;
  56
  57   /* Some assertions need to be inserted on an edge (e.g., assertions
  58      generated by COND_EXPRs).  In those cases, BB will be NULL.  */
  59   edge e;
  60
  61   /* Pointer to the statement that generated this assertion.  */
  62   block_stmt_iterator si;
  63
  64   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
  65   enum tree_code comp_code;
  66
  67   /* Value being compared against.  */
  68   tree val;
  69
  70   /* Next node in the linked list.  */
  71   struct assert_locus_d *next;
  72 };
  73
  74 typedef struct assert_locus_d *assert_locus_t;
  75
  76 /* If bit I is present, it means that SSA name N_i has a list of
  77    assertions that should be inserted in the IL.  */
  78 static bitmap need_assert_for;
  79
  80 /* Array of locations lists where to insert assertions.  ASSERTS_FOR[I]
  81    holds a list of ASSERT_LOCUS_T nodes that describe where
  82    ASSERT_EXPRs for SSA name N_I should be inserted.  */
  83 static assert_locus_t *asserts_for;
  84
  85 /* Set of blocks visited in find_assert_locations.  Used to avoid
  86    visiting the same block more than once.  */
  87 static sbitmap blocks_visited;
  88
  89 /* Value range array.  After propagation, VR_VALUE[I] holds the range
  90    of values that SSA name N_I may take.  */
  91 static value_range_t **vr_value;
  92
  93
  94 /* Return true if ARG is marked with the nonnull attribute in the
  95    current function signature.  */
  96
  97 static bool
  98 nonnull_arg_p (tree arg)
  99 {
 100   tree t, attrs, fntype;
 101   unsigned HOST_WIDE_INT arg_num;
 102
 103   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
 104
 105   fntype = TREE_TYPE (current_function_decl);
 106   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
 107
 108   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
 109   if (attrs == NULL_TREE)
 110     return false;
 111
 112   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
 113   if (TREE_VALUE (attrs) == NULL_TREE)
 114     return true;
 115
 116   /* Get the position number for ARG in the function signature.  */
 117   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
 118        t;
 119        t = TREE_CHAIN (t), arg_num++)
 120     {
 121       if (t == arg)
 122         break;
 123     }
 124
 125   gcc_assert (t == arg);
 126
 127   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
 128   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
 129     {
 130       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
 131         return true;
 132     }
 133
 134   return false;
 135 }
 136
 137
 138 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
 139
 140 static void
 141 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 142                  tree max, bitmap equiv)
 143 {
 144 #if defined ENABLE_CHECKING
 145   /* Check the validity of the range.  */
 146   if (t == VR_RANGE || t == VR_ANTI_RANGE)
 147     {
 148       int cmp;
 149
 150       gcc_assert (min && max);
 151
 152       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
 153         gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
 154                     || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
 155
 156       cmp = compare_values (min, max);
 157       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
 158     }
 159
 160   if (t == VR_UNDEFINED || t == VR_VARYING)
 161     gcc_assert (min == NULL_TREE && max == NULL_TREE);
 162
 163   if (t == VR_UNDEFINED || t == VR_VARYING)
 164     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
 165 #endif
 166
 167   vr->type = t;
 168   vr->min = min;
 169   vr->max = max;
 170
 171   /* Since updating the equivalence set involves deep copying the
 172      bitmaps, only do it if absolutely necessary.  */
 173   if (vr->equiv == NULL)
 174     vr->equiv = BITMAP_ALLOC (NULL);
 175
 176   if (equiv != vr->equiv)
 177     {
 178       if (equiv && !bitmap_empty_p (equiv))
 179         bitmap_copy (vr->equiv, equiv);
 180       else
 181         bitmap_clear (vr->equiv);
 182     }
 183 }
 184
 185
 186 /* Copy value range FROM into value range TO.  */
 187
 188 static inline void
 189 copy_value_range (value_range_t *to, value_range_t *from)
 190 {
 191   set_value_range (to, from->type, from->min, from->max, from->equiv);
 192 }
 193
 194 /* Set value range VR to a non-negative range of type TYPE.  */
 195
 196 static inline void
 197 set_value_range_to_nonnegative (value_range_t *vr, tree type)
 198 {
 199   tree zero = build_int_cst (type, 0);
 200   set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
 201 }
 202
 203 /* Set value range VR to a non-NULL range of type TYPE.  */
 204
 205 static inline void
 206 set_value_range_to_nonnull (value_range_t *vr, tree type)
 207 {
 208   tree zero = build_int_cst (type, 0);
 209   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
 210 }
 211
 212
 213 /* Set value range VR to a NULL range of type TYPE.  */
 214
 215 static inline void
 216 set_value_range_to_null (value_range_t *vr, tree type)
 217 {
 218   tree zero = build_int_cst (type, 0);
 219   set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
 220 }
 221
 222
 223 /* Set value range VR to VR_VARYING.  */
 224
 225 static inline void
 226 set_value_range_to_varying (value_range_t *vr)
 227 {
 228   vr->type = VR_VARYING;
 229   vr->min = vr->max = NULL_TREE;
 230   if (vr->equiv)
 231     bitmap_clear (vr->equiv);
 232 }
 233
 234
 235 /* Set value range VR to VR_UNDEFINED.  */
 236
 237 static inline void
 238 set_value_range_to_undefined (value_range_t *vr)
 239 {
 240   vr->type = VR_UNDEFINED;
 241   vr->min = vr->max = NULL_TREE;
 242   if (vr->equiv)
 243     bitmap_clear (vr->equiv);
 244 }
 245
 246
 247 /* Return value range information for VAR.
 248
 249    If we have no values ranges recorded (ie, VRP is not running), then
 250    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 251
 252 static value_range_t *
 253 get_value_range (tree var)
 254 {
 255   value_range_t *vr;
 256   tree sym;
 257   unsigned ver = SSA_NAME_VERSION (var);
 258
 259   /* If we have no recorded ranges, then return NULL.  */
 260   if (! vr_value)
 261     return NULL;
 262
 263   vr = vr_value[ver];
 264   if (vr)
 265     return vr;
 266
 267   /* Create a default value range.  */
 268   vr_value[ver] = vr = XNEW (value_range_t);
 269   memset (vr, 0, sizeof (*vr));
 270
 271   /* Allocate an equivalence set.  */
 272   vr->equiv = BITMAP_ALLOC (NULL);
 273
 274   /* If VAR is a default definition, the variable can take any value
 275      in VAR's type.  */
 276   sym = SSA_NAME_VAR (var);
 277   if (var == default_def (sym))
 278     {
 279       /* Try to use the "nonnull" attribute to create ~[0, 0]
 280          anti-ranges for pointers.  Note that this is only valid with
 281          default definitions of PARM_DECLs.  */
 282       if (TREE_CODE (sym) == PARM_DECL
 283           && POINTER_TYPE_P (TREE_TYPE (sym))
 284           && nonnull_arg_p (sym))
 285         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
 286       else
 287         set_value_range_to_varying (vr);
 288     }
 289
 290   return vr;
 291 }
 292
 293 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
 294
 295 static inline bool
 296 vrp_operand_equal_p (tree val1, tree val2)
 297 {
 298   return (val1 == val2
 299           || (val1 && val2
 300               && operand_equal_p (val1, val2, 0)));
 301 }
 302
 303 /* Return true, if the bitmaps B1 and B2 are equal.  */
 304
 305 static inline bool
 306 vrp_bitmap_equal_p (bitmap b1, bitmap b2)
 307 {
 308   return (b1 == b2
 309           || (b1 && b2
 310               && bitmap_equal_p (b1, b2)));
 311 }
 312
 313 /* Update the value range and equivalence set for variable VAR to
 314    NEW_VR.  Return true if NEW_VR is different from VAR's previous
 315    value.
 316
 317    NOTE: This function assumes that NEW_VR is a temporary value range
 318    object created for the sole purpose of updating VAR's range.  The
 319    storage used by the equivalence set from NEW_VR will be freed by
 320    this function.  Do not call update_value_range when NEW_VR
 321    is the range object associated with another SSA name.  */
 322
 323 static inline bool
 324 update_value_range (tree var, value_range_t *new_vr)
 325 {
 326   value_range_t *old_vr;
 327   bool is_new;
 328
 329   /* Update the value range, if necessary.  */
 330   old_vr = get_value_range (var);
 331   is_new = old_vr->type != new_vr->type
 332            || !vrp_operand_equal_p (old_vr->min, new_vr->min)
 333            || !vrp_operand_equal_p (old_vr->max, new_vr->max)
 334            || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv);
 335
 336   if (is_new)
 337     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
 338                      new_vr->equiv);
 339
 340   BITMAP_FREE (new_vr->equiv);
 341   new_vr->equiv = NULL;
 342
 343   return is_new;
 344 }
 345
 346
 347 /* Add VAR and VAR's equivalence set to EQUIV.  */
 348
 349 static void
 350 add_equivalence (bitmap equiv, tree var)
 351 {
 352   unsigned ver = SSA_NAME_VERSION (var);
 353   value_range_t *vr = vr_value[ver];
 354
 355   bitmap_set_bit (equiv, ver);
 356   if (vr && vr->equiv)
 357     bitmap_ior_into (equiv, vr->equiv);
 358 }
 359
 360
 361 /* Return true if VR is ~[0, 0].  */
 362
 363 static inline bool
 364 range_is_nonnull (value_range_t *vr)
 365 {
 366   return vr->type == VR_ANTI_RANGE
 367          && integer_zerop (vr->min)
 368          && integer_zerop (vr->max);
 369 }
 370
 371
 372 /* Return true if VR is [0, 0].  */
 373
 374 static inline bool
 375 range_is_null (value_range_t *vr)
 376 {
 377   return vr->type == VR_RANGE
 378          && integer_zerop (vr->min)
 379          && integer_zerop (vr->max);
 380 }
 381
 382
 383 /* Return true if value range VR involves at least one symbol.  */
 384
 385 static inline bool
 386 symbolic_range_p (value_range_t *vr)
 387 {
 388   return (!is_gimple_min_invariant (vr->min)
 389           || !is_gimple_min_invariant (vr->max));
 390 }
 391
 392 /* Like tree_expr_nonnegative_p, but this function uses value ranges
 393    obtained so far.  */
 394
 395 static bool
 396 vrp_expr_computes_nonnegative (tree expr)
 397 {
 398   return tree_expr_nonnegative_p (expr);
 399 }
 400
 401 /* Like tree_expr_nonzero_p, but this function uses value ranges
 402    obtained so far.  */
 403
 404 static bool
 405 vrp_expr_computes_nonzero (tree expr)
 406 {
 407   if (tree_expr_nonzero_p (expr))
 408     return true;
 409
 410   /* If we have an expression of the form &X->a, then the expression
 411      is nonnull if X is nonnull.  */
 412   if (TREE_CODE (expr) == ADDR_EXPR)
 413     {
 414       tree base = get_base_address (TREE_OPERAND (expr, 0));
 415
 416       if (base != NULL_TREE
 417           && TREE_CODE (base) == INDIRECT_REF
 418           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
 419         {
 420           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
 421           if (range_is_nonnull (vr))
 422             return true;
 423         }
 424     }
 425
 426   return false;
 427 }
 428
 429 /* Returns true if EXPR is a valid value (as expected by compare_values) --
 430    a gimple invariant, or SSA_NAME +- CST.  */
 431
 432 static bool
 433 valid_value_p (tree expr)
 434 {
 435   if (TREE_CODE (expr) == SSA_NAME)
 436     return true;
 437
 438   if (TREE_CODE (expr) == PLUS_EXPR
 439       || TREE_CODE (expr) == MINUS_EXPR)
 440     return (TREE_CODE (TREE_OPERAND (expr, 0)) == SSA_NAME
 441             && TREE_CODE (TREE_OPERAND (expr, 1)) == INTEGER_CST);
 442
 443   return is_gimple_min_invariant (expr);
 444 }
 445
 446 /* Compare two values VAL1 and VAL2.  Return
 447
 448         -2 if VAL1 and VAL2 cannot be compared at compile-time,
 449         -1 if VAL1 < VAL2,
 450          0 if VAL1 == VAL2,
 451         +1 if VAL1 > VAL2, and
 452         +2 if VAL1 != VAL2
 453
 454    This is similar to tree_int_cst_compare but supports pointer values
 455    and values that cannot be compared at compile time.  */
 456
 457 static int
 458 compare_values (tree val1, tree val2)
 459 {
 460   if (val1 == val2)
 461     return 0;
 462
 463   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
 464      both integers.  */
 465   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
 466               == POINTER_TYPE_P (TREE_TYPE (val2)));
 467
 468   if ((TREE_CODE (val1) == SSA_NAME
 469        || TREE_CODE (val1) == PLUS_EXPR
 470        || TREE_CODE (val1) == MINUS_EXPR)
 471       && (TREE_CODE (val2) == SSA_NAME
 472           || TREE_CODE (val2) == PLUS_EXPR
 473           || TREE_CODE (val2) == MINUS_EXPR))
 474     {
 475       tree n1, c1, n2, c2;
 476       enum tree_code code1, code2;
 477
 478       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
 479          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
 480          same name, return -2.  */
 481       if (TREE_CODE (val1) == SSA_NAME)
 482         {
 483           code1 = SSA_NAME;
 484           n1 = val1;
 485           c1 = NULL_TREE;
 486         }
 487       else
 488         {
 489           code1 = TREE_CODE (val1);
 490           n1 = TREE_OPERAND (val1, 0);
 491           c1 = TREE_OPERAND (val1, 1);
 492           if (tree_int_cst_sgn (c1) == -1)
 493             {
 494               c1 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c1), c1);
 495               if (!c1)
 496                 return -2;
 497               code1 = code1 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 498             }
 499         }
 500
 501       if (TREE_CODE (val2) == SSA_NAME)
 502         {
 503           code2 = SSA_NAME;
 504           n2 = val2;
 505           c2 = NULL_TREE;
 506         }
 507       else
 508         {
 509           code2 = TREE_CODE (val2);
 510           n2 = TREE_OPERAND (val2, 0);
 511           c2 = TREE_OPERAND (val2, 1);
 512           if (tree_int_cst_sgn (c2) == -1)
 513             {
 514               c2 = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (c2), c2);
 515               if (!c2)
 516                 return -2;
 517               code2 = code2 == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR;
 518             }
 519         }
 520
 521       /* Both values must use the same name.  */
 522       if (n1 != n2)
 523         return -2;
 524
 525       if (code1 == SSA_NAME
 526           && code2 == SSA_NAME)
 527         /* NAME == NAME  */
 528         return 0;
 529
 530       /* If overflow is defined we cannot simplify more.  */
 531       if (TYPE_UNSIGNED (TREE_TYPE (val1))
 532           || flag_wrapv)
 533         return -2;
 534
 535       if (code1 == SSA_NAME)
 536         {
 537           if (code2 == PLUS_EXPR)
 538             /* NAME < NAME + CST  */
 539             return -1;
 540           else if (code2 == MINUS_EXPR)
 541             /* NAME > NAME - CST  */
 542             return 1;
 543         }
 544       else if (code1 == PLUS_EXPR)
 545         {
 546           if (code2 == SSA_NAME)
 547             /* NAME + CST > NAME  */
 548             return 1;
 549           else if (code2 == PLUS_EXPR)
 550             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
 551             return compare_values (c1, c2);
 552           else if (code2 == MINUS_EXPR)
 553             /* NAME + CST1 > NAME - CST2  */
 554             return 1;
 555         }
 556       else if (code1 == MINUS_EXPR)
 557         {
 558           if (code2 == SSA_NAME)
 559             /* NAME - CST < NAME  */
 560             return -1;
 561           else if (code2 == PLUS_EXPR)
 562             /* NAME - CST1 < NAME + CST2  */
 563             return -1;
 564           else if (code2 == MINUS_EXPR)
 565             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
 566                C1 and C2 are swapped in the call to compare_values.  */
 567             return compare_values (c2, c1);
 568         }
 569
 570       gcc_unreachable ();
 571     }
 572
 573   /* We cannot compare non-constants.  */
 574   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
 575     return -2;
 576
 577   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
 578     {
 579       /* We cannot compare overflowed values.  */
 580       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
 581         return -2;
 582
 583       return tree_int_cst_compare (val1, val2);
 584     }
 585   else
 586     {
 587       tree t;
 588
 589       /* First see if VAL1 and VAL2 are not the same.  */
 590       if (val1 == val2 || operand_equal_p (val1, val2, 0))
 591         return 0;
 592
 593       /* If VAL1 is a lower address than VAL2, return -1.  */
 594       t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
 595       if (t == boolean_true_node)
 596         return -1;
 597
 598       /* If VAL1 is a higher address than VAL2, return +1.  */
 599       t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
 600       if (t == boolean_true_node)
 601         return 1;
 602
 603       /* If VAL1 is different than VAL2, return +2.  */
 604       t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
 605       if (t == boolean_true_node)
 606         return 2;
 607
 608       return -2;
 609     }
 610 }
 611
 612
 613 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
 614           0 if VAL is not inside VR,
 615          -2 if we cannot tell either way.
 616
 617    FIXME, the current semantics of this functions are a bit quirky
 618           when taken in the context of VRP.  In here we do not care
 619           about VR's type.  If VR is the anti-range ~[3, 5] the call
 620           value_inside_range (4, VR) will return 1.
 621
 622           This is counter-intuitive in a strict sense, but the callers
 623           currently expect this.  They are calling the function
 624           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
 625           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
 626           themselves.
 627
 628           This also applies to value_ranges_intersect_p and
 629           range_includes_zero_p.  The semantics of VR_RANGE and
 630           VR_ANTI_RANGE should be encoded here, but that also means
 631           adapting the users of these functions to the new semantics.  */
 632
 633 static inline int
 634 value_inside_range (tree val, value_range_t *vr)
 635 {
 636   tree cmp1, cmp2;
 637
 638   cmp1 = fold_binary_to_constant (GE_EXPR, boolean_type_node, val, vr->min);
 639   if (!cmp1)
 640     return -2;
 641
 642   cmp2 = fold_binary_to_constant (LE_EXPR, boolean_type_node, val, vr->max);
 643   if (!cmp2)
 644     return -2;
 645
 646   return cmp1 == boolean_true_node && cmp2 == boolean_true_node;
 647 }
 648
 649
 650 /* Return true if value ranges VR0 and VR1 have a non-empty
 651    intersection.  */
 652
 653 static inline bool
 654 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
 655 {
 656   return (value_inside_range (vr1->min, vr0) == 1
 657           || value_inside_range (vr1->max, vr0) == 1
 658           || value_inside_range (vr0->min, vr1) == 1
 659           || value_inside_range (vr0->max, vr1) == 1);
 660 }
 661
 662
 663 /* Return true if VR includes the value zero, false otherwise.  FIXME,
 664    currently this will return false for an anti-range like ~[-4, 3].
 665    This will be wrong when the semantics of value_inside_range are
 666    modified (currently the users of this function expect these
 667    semantics).  */
 668
 669 static inline bool
 670 range_includes_zero_p (value_range_t *vr)
 671 {
 672   tree zero;
 673
 674   gcc_assert (vr->type != VR_UNDEFINED
 675               && vr->type != VR_VARYING
 676               && !symbolic_range_p (vr));
 677
 678   zero = build_int_cst (TREE_TYPE (vr->min), 0);
 679   return (value_inside_range (zero, vr) == 1);
 680 }
 681
 682 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
 683    false otherwise or if no value range information is available.  */
 684
 685 bool
 686 ssa_name_nonnegative_p (tree t)
 687 {
 688   value_range_t *vr = get_value_range (t);
 689
 690   if (!vr)
 691     return false;
 692
 693   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
 694      which would return a useful value should be encoded as a VR_RANGE.  */
 695   if (vr->type == VR_RANGE)
 696     {
 697       int result = compare_values (vr->min, integer_zero_node);
 698
 699       return (result == 0 || result == 1);
 700     }
 701   return false;
 702 }
 703
 704 /* Return true if T, an SSA_NAME, is known to be nonzero.  Return
 705    false otherwise or if no value range information is available.  */
 706
 707 bool
 708 ssa_name_nonzero_p (tree t)
 709 {
 710   value_range_t *vr = get_value_range (t);
 711
 712   if (!vr)
 713     return false;
 714
 715   /* A VR_RANGE which does not include zero is a nonzero value.  */
 716   if (vr->type == VR_RANGE && !symbolic_range_p (vr))
 717     return ! range_includes_zero_p (vr);
 718
 719   /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
 720   if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
 721     return range_includes_zero_p (vr);
 722
 723   return false;
 724 }
 725
 726
 727 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
 728    initially consider X_i and Y_j equivalent, so the equivalence set
 729    of Y_j is added to the equivalence set of X_i.  However, it is
 730    possible to have a chain of ASSERT_EXPRs whose predicates are
 731    actually incompatible.  This is usually the result of nesting of
 732    contradictory if-then-else statements.  For instance, in PR 24670:
 733
 734         count_4 has range [-INF, 63]
 735
 736         if (count_4 != 0)
 737           {
 738             count_19 = ASSERT_EXPR <count_4, count_4 != 0>
 739             if (count_19 > 63)
 740               {
 741                 count_18 = ASSERT_EXPR <count_19, count_19 > 63>
 742                 if (count_18 <= 63)
 743                   ...
 744               }
 745           }
 746
 747    Notice that 'if (count_19 > 63)' is trivially false and will be
 748    folded out at the end.  However, during propagation, the flowgraph
 749    is not cleaned up and so, VRP will evaluate predicates more
 750    predicates than necessary, so it must support these
 751    inconsistencies.  The problem here is that because of the chaining
 752    of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
 753    Since count_4 has an incompatible range, we ICE when evaluating the
 754    ranges in the equivalency set.  So, we need to remove count_4 from
 755    it.  */
 756
 757 static void
 758 fix_equivalence_set (value_range_t *vr_p)
 759 {
 760   bitmap_iterator bi;
 761   unsigned i;
 762   bitmap e = vr_p->equiv;
 763   bitmap to_remove;
 764
 765   /* Only detect inconsistencies on numeric ranges.  */
 766   if (vr_p->type == VR_VARYING
 767       || vr_p->type == VR_UNDEFINED
 768       || symbolic_range_p (vr_p))
 769     return;
 770
 771   to_remove = BITMAP_ALLOC (NULL);
 772   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
 773     {
 774       value_range_t *equiv_vr = vr_value[i];
 775
 776       if (equiv_vr->type == VR_VARYING
 777           || equiv_vr->type == VR_UNDEFINED)
 778         continue;
 779
 780       if (vr_p->type == VR_RANGE
 781           && equiv_vr->type == VR_RANGE)
 782         {
 783           /* Two ranges have an empty intersection if their end points
 784              are outside of the other range.  */
 785           if (compare_values (equiv_vr->min, vr_p->max) == 1
 786               || compare_values (equiv_vr->max, vr_p->min) == -1)
 787             bitmap_set_bit (to_remove, i);
 788         }
 789       else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
 790                || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
 791         {
 792           /* A range and an anti-range have an empty intersection if
 793              their end points are the same.  FIXME,
 794              value_ranges_intersect_p should handle this
 795              automatically.  */
 796           if (compare_values (equiv_vr->min, vr_p->min) == 0
 797               && compare_values (equiv_vr->max, vr_p->max) == 0)
 798             bitmap_set_bit (to_remove, i);
 799         }
 800     }
 801
 802   bitmap_and_compl_into (vr_p->equiv, to_remove);
 803   BITMAP_FREE (to_remove);
 804 }
 805
 806
 807 /* Extract value range information from an ASSERT_EXPR EXPR and store
 808    it in *VR_P.  */
 809
 810 static void
 811 extract_range_from_assert (value_range_t *vr_p, tree expr)
 812 {
 813   tree var, cond, limit, min, max, type;
 814   value_range_t *var_vr, *limit_vr;
 815   enum tree_code cond_code;
 816
 817   var = ASSERT_EXPR_VAR (expr);
 818   cond = ASSERT_EXPR_COND (expr);
 819
 820   gcc_assert (COMPARISON_CLASS_P (cond));
 821
 822   /* Find VAR in the ASSERT_EXPR conditional.  */
 823   if (var == TREE_OPERAND (cond, 0))
 824     {
 825       /* If the predicate is of the form VAR COMP LIMIT, then we just
 826          take LIMIT from the RHS and use the same comparison code.  */
 827       limit = TREE_OPERAND (cond, 1);
 828       cond_code = TREE_CODE (cond);
 829     }
 830   else
 831     {
 832       /* If the predicate is of the form LIMIT COMP VAR, then we need
 833          to flip around the comparison code to create the proper range
 834          for VAR.  */
 835       limit = TREE_OPERAND (cond, 0);
 836       cond_code = swap_tree_comparison (TREE_CODE (cond));
 837     }
 838
 839   type = TREE_TYPE (limit);
 840   gcc_assert (limit != var);
 841
 842   /* For pointer arithmetic, we only keep track of pointer equality
 843      and inequality.  */
 844   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
 845     {
 846       set_value_range_to_varying (vr_p);
 847       return;
 848     }
 849
 850   /* If LIMIT is another SSA name and LIMIT has a range of its own,
 851      try to use LIMIT's range to avoid creating symbolic ranges
 852      unnecessarily. */
 853   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
 854
 855   /* LIMIT's range is only interesting if it has any useful information.  */
 856   if (limit_vr
 857       && (limit_vr->type == VR_UNDEFINED
 858           || limit_vr->type == VR_VARYING
 859           || symbolic_range_p (limit_vr)))
 860     limit_vr = NULL;
 861
 862   /* Initially, the new range has the same set of equivalences of
 863      VAR's range.  This will be revised before returning the final
 864      value.  Since assertions may be chained via mutually exclusive
 865      predicates, we will need to trim the set of equivalences before
 866      we are done.  */
 867   gcc_assert (vr_p->equiv == NULL);
 868   vr_p->equiv = BITMAP_ALLOC (NULL);
 869   add_equivalence (vr_p->equiv, var);
 870
 871   /* Extract a new range based on the asserted comparison for VAR and
 872      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
 873      will only use it for equality comparisons (EQ_EXPR).  For any
 874      other kind of assertion, we cannot derive a range from LIMIT's
 875      anti-range that can be used to describe the new range.  For
 876      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
 877      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
 878      no single range for x_2 that could describe LE_EXPR, so we might
 879      as well build the range [b_4, +INF] for it.  */
 880   if (cond_code == EQ_EXPR)
 881     {
 882       enum value_range_type range_type;
 883
 884       if (limit_vr)
 885         {
 886           range_type = limit_vr->type;
 887           min = limit_vr->min;
 888           max = limit_vr->max;
 889         }
 890       else
 891         {
 892           range_type = VR_RANGE;
 893           min = limit;
 894           max = limit;
 895         }
 896
 897       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
 898
 899       /* When asserting the equality VAR == LIMIT and LIMIT is another
 900          SSA name, the new range will also inherit the equivalence set
 901          from LIMIT.  */
 902       if (TREE_CODE (limit) == SSA_NAME)
 903         add_equivalence (vr_p->equiv, limit);
 904     }
 905   else if (cond_code == NE_EXPR)
 906     {
 907       /* As described above, when LIMIT's range is an anti-range and
 908          this assertion is an inequality (NE_EXPR), then we cannot
 909          derive anything from the anti-range.  For instance, if
 910          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
 911          not imply that VAR's range is [0, 0].  So, in the case of
 912          anti-ranges, we just assert the inequality using LIMIT and
 913          not its anti-range.
 914
 915          If LIMIT_VR is a range, we can only use it to build a new
 916          anti-range if LIMIT_VR is a single-valued range.  For
 917          instance, if LIMIT_VR is [0, 1], the predicate
 918          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
 919          Rather, it means that for value 0 VAR should be ~[0, 0]
 920          and for value 1, VAR should be ~[1, 1].  We cannot
 921          represent these ranges.
 922
 923          The only situation in which we can build a valid
 924          anti-range is when LIMIT_VR is a single-valued range
 925          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case,
 926          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
 927       if (limit_vr
 928           && limit_vr->type == VR_RANGE
 929           && compare_values (limit_vr->min, limit_vr->max) == 0)
 930         {
 931           min = limit_vr->min;
 932           max = limit_vr->max;
 933         }
 934       else
 935         {
 936           /* In any other case, we cannot use LIMIT's range to build a
 937              valid anti-range.  */
 938           min = max = limit;
 939         }
 940
 941       /* If MIN and MAX cover the whole range for their type, then
 942          just use the original LIMIT.  */
 943       if (INTEGRAL_TYPE_P (type)
 944           && min == TYPE_MIN_VALUE (type)
 945           && max == TYPE_MAX_VALUE (type))
 946         min = max = limit;
 947
 948       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
 949     }
 950   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
 951     {
 952       min = TYPE_MIN_VALUE (type);
 953
 954       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 955         max = limit;
 956       else
 957         {
 958           /* If LIMIT_VR is of the form [N1, N2], we need to build the
 959              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
 960              LT_EXPR.  */
 961           max = limit_vr->max;
 962         }
 963
 964       /* If the maximum value forces us to be out of bounds, simply punt.
 965          It would be pointless to try and do anything more since this
 966          all should be optimized away above us.  */
 967       if (cond_code == LT_EXPR && compare_values (max, min) == 0)
 968         set_value_range_to_varying (vr_p);
 969       else
 970         {
 971           /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
 972           if (cond_code == LT_EXPR)
 973             {
 974               tree one = build_int_cst (type, 1);
 975               max = fold_build2 (MINUS_EXPR, type, max, one);
 976             }
 977
 978           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
 979         }
 980     }
 981   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
 982     {
 983       max = TYPE_MAX_VALUE (type);
 984
 985       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 986         min = limit;
 987       else
 988         {
 989           /* If LIMIT_VR is of the form [N1, N2], we need to build the
 990              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
 991              GT_EXPR.  */
 992           min = limit_vr->min;
 993         }
 994
 995       /* If the minimum value forces us to be out of bounds, simply punt.
 996          It would be pointless to try and do anything more since this
 997          all should be optimized away above us.  */
 998       if (cond_code == GT_EXPR && compare_values (min, max) == 0)
 999         set_value_range_to_varying (vr_p);
1000       else
1001         {
1002           /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
1003           if (cond_code == GT_EXPR)
1004             {
1005               tree one = build_int_cst (type, 1);
1006               min = fold_build2 (PLUS_EXPR, type, min, one);
1007             }
1008
1009           set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1010         }
1011     }
1012   else
1013     gcc_unreachable ();
1014
1015   /* If VAR already had a known range, it may happen that the new
1016      range we have computed and VAR's range are not compatible.  For
1017      instance,
1018
1019         if (p_5 == NULL)
1020           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
1021           x_7 = p_6->fld;
1022           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
1023
1024      While the above comes from a faulty program, it will cause an ICE
1025      later because p_8 and p_6 will have incompatible ranges and at
1026      the same time will be considered equivalent.  A similar situation
1027      would arise from
1028
1029         if (i_5 > 10)
1030           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
1031           if (i_5 < 5)
1032             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
1033
1034      Again i_6 and i_7 will have incompatible ranges.  It would be
1035      pointless to try and do anything with i_7's range because
1036      anything dominated by 'if (i_5 < 5)' will be optimized away.
1037      Note, due to the wa in which simulation proceeds, the statement
1038      i_7 = ASSERT_EXPR <...> we would never be visited because the
1039      conditional 'if (i_5 < 5)' always evaluates to false.  However,
1040      this extra check does not hurt and may protect against future
1041      changes to VRP that may get into a situation similar to the
1042      NULL pointer dereference example.
1043
1044      Note that these compatibility tests are only needed when dealing
1045      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
1046      are both anti-ranges, they will always be compatible, because two
1047      anti-ranges will always have a non-empty intersection.  */
1048
1049   var_vr = get_value_range (var);
1050
1051   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1052      ranges or anti-ranges.  */
1053   if (vr_p->type == VR_VARYING
1054       || vr_p->type == VR_UNDEFINED
1055       || var_vr->type == VR_VARYING
1056       || var_vr->type == VR_UNDEFINED
1057       || symbolic_range_p (vr_p)
1058       || symbolic_range_p (var_vr))
1059     goto done;
1060
1061   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1062     {
1063       /* If the two ranges have a non-empty intersection, we can
1064          refine the resulting range.  Since the assert expression
1065          creates an equivalency and at the same time it asserts a
1066          predicate, we can take the intersection of the two ranges to
1067          get better precision.  */
1068       if (value_ranges_intersect_p (var_vr, vr_p))
1069         {
1070           /* Use the larger of the two minimums.  */
1071           if (compare_values (vr_p->min, var_vr->min) == -1)
1072             min = var_vr->min;
1073           else
1074             min = vr_p->min;
1075
1076           /* Use the smaller of the two maximums.  */
1077           if (compare_values (vr_p->max, var_vr->max) == 1)
1078             max = var_vr->max;
1079           else
1080             max = vr_p->max;
1081
1082           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1083         }
1084       else
1085         {
1086           /* The two ranges do not intersect, set the new range to
1087              VARYING, because we will not be able to do anything
1088              meaningful with it.  */
1089           set_value_range_to_varying (vr_p);
1090         }
1091     }
1092   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1093            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1094     {
1095       /* A range and an anti-range will cancel each other only if
1096          their ends are the same.  For instance, in the example above,
1097          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1098          so VR_P should be set to VR_VARYING.  */
1099       if (compare_values (var_vr->min, vr_p->min) == 0
1100           && compare_values (var_vr->max, vr_p->max) == 0)
1101         set_value_range_to_varying (vr_p);
1102       else
1103         {
1104           tree min, max, anti_min, anti_max, real_min, real_max;
1105
1106           /* We want to compute the logical AND of the two ranges;
1107              there are three cases to consider.
1108
1109
1110              1. The VR_ANTI_RANGE range is completely within the
1111                 VR_RANGE and the endpoints of the ranges are
1112                 different.  In that case the resulting range
1113                 should be whichever range is more precise.
1114                 Typically that will be the VR_RANGE.
1115
1116              2. The VR_ANTI_RANGE is completely disjoint from
1117                 the VR_RANGE.  In this case the resulting range
1118                 should be the VR_RANGE.
1119
1120              3. There is some overlap between the VR_ANTI_RANGE
1121                 and the VR_RANGE.
1122
1123                 3a. If the high limit of the VR_ANTI_RANGE resides
1124                     within the VR_RANGE, then the result is a new
1125                     VR_RANGE starting at the high limit of the
1126                     the VR_ANTI_RANGE + 1 and extending to the
1127                     high limit of the original VR_RANGE.
1128
1129                 3b. If the low limit of the VR_ANTI_RANGE resides
1130                     within the VR_RANGE, then the result is a new
1131                     VR_RANGE starting at the low limit of the original
1132                     VR_RANGE and extending to the low limit of the
1133                     VR_ANTI_RANGE - 1.  */
1134           if (vr_p->type == VR_ANTI_RANGE)
1135             {
1136               anti_min = vr_p->min;
1137               anti_max = vr_p->max;
1138               real_min = var_vr->min;
1139               real_max = var_vr->max;
1140             }
1141           else
1142             {
1143               anti_min = var_vr->min;
1144               anti_max = var_vr->max;
1145               real_min = vr_p->min;
1146               real_max = vr_p->max;
1147             }
1148
1149
1150           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1151              not including any endpoints.  */
1152           if (compare_values (anti_max, real_max) == -1
1153               && compare_values (anti_min, real_min) == 1)
1154             {
1155               set_value_range (vr_p, VR_RANGE, real_min,
1156                                real_max, vr_p->equiv);
1157             }
1158           /* Case 2, VR_ANTI_RANGE completely disjoint from
1159              VR_RANGE.  */
1160           else if (compare_values (anti_min, real_max) == 1
1161                    || compare_values (anti_max, real_min) == -1)
1162             {
1163               set_value_range (vr_p, VR_RANGE, real_min,
1164                                real_max, vr_p->equiv);
1165             }
1166           /* Case 3a, the anti-range extends into the low
1167              part of the real range.  Thus creating a new
1168              low for the real range.  */
1169           else if ((compare_values (anti_max, real_min) == 1
1170                     || compare_values (anti_max, real_min) == 0)
1171                    && compare_values (anti_max, real_max) == -1)
1172             {
1173               min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1174                                  anti_max,
1175                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1176               max = real_max;
1177               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1178             }
1179           /* Case 3b, the anti-range extends into the high
1180              part of the real range.  Thus creating a new
1181              higher for the real range.  */
1182           else if (compare_values (anti_min, real_min) == 1
1183                    && (compare_values (anti_min, real_max) == -1
1184                        || compare_values (anti_min, real_max) == 0))
1185             {
1186               max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1187                                  anti_min,
1188                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1189               min = real_min;
1190               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1191             }
1192         }
1193     }
1194
1195   /* Remove names from the equivalence set that have ranges
1196      incompatible with VR_P.  */
1197 done:
1198   fix_equivalence_set (vr_p);
1199 }
1200
1201
1202 /* Extract range information from SSA name VAR and store it in VR.  If
1203    VAR has an interesting range, use it.  Otherwise, create the
1204    range [VAR, VAR] and return it.  This is useful in situations where
1205    we may have conditionals testing values of VARYING names.  For
1206    instance,
1207
1208         x_3 = y_5;
1209         if (x_3 > y_5)
1210           ...
1211
1212     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1213     always false.  */
1214
1215 static void
1216 extract_range_from_ssa_name (value_range_t *vr, tree var)
1217 {
1218   value_range_t *var_vr = get_value_range (var);
1219
1220   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1221     copy_value_range (vr, var_vr);
1222   else
1223     set_value_range (vr, VR_RANGE, var, var, NULL);
1224
1225   add_equivalence (vr->equiv, var);
1226 }
1227
1228
1229 /* Wrapper around int_const_binop.  If the operation overflows and we
1230    are not using wrapping arithmetic, then adjust the result to be
1231    -INF or +INF depending on CODE, VAL1 and VAL2.  */
1232
1233 static inline tree
1234 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1235 {
1236   tree res;
1237
1238   if (flag_wrapv)
1239     return int_const_binop (code, val1, val2, 0);
1240
1241   /* If we are not using wrapping arithmetic, operate symbolically
1242      on -INF and +INF.  */
1243   res = int_const_binop (code, val1, val2, 0);
1244
1245   if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1246     {
1247       int checkz = compare_values (res, val1);
1248       bool overflow = false;
1249
1250       /* Ensure that res = val1 [+*] val2 >= val1
1251          or that res = val1 - val2 <= val1.  */
1252       if ((code == PLUS_EXPR
1253            && !(checkz == 1 || checkz == 0))
1254           || (code == MINUS_EXPR
1255               && !(checkz == 0 || checkz == -1)))
1256         {
1257           overflow = true;
1258         }
1259       /* Checking for multiplication overflow is done by dividing the
1260          output of the multiplication by the first input of the
1261          multiplication.  If the result of that division operation is
1262          not equal to the second input of the multiplication, then the
1263          multiplication overflowed.  */
1264       else if (code == MULT_EXPR && !integer_zerop (val1))
1265         {
1266           tree tmp = int_const_binop (TRUNC_DIV_EXPR,
1267                                       TYPE_MAX_VALUE (TREE_TYPE (val1)),
1268                                       val1, 0);
1269           int check = compare_values (tmp, val2);
1270
1271           if (check != 0)
1272             overflow = true;
1273         }
1274
1275       if (overflow)
1276         {
1277           res = copy_node (res);
1278           TREE_OVERFLOW (res) = 1;
1279         }
1280
1281     }
1282   else if (TREE_OVERFLOW (res)
1283            && !TREE_OVERFLOW (val1)
1284            && !TREE_OVERFLOW (val2))
1285     {
1286       /* If the operation overflowed but neither VAL1 nor VAL2 are
1287          overflown, return -INF or +INF depending on the operation
1288          and the combination of signs of the operands.  */
1289       int sgn1 = tree_int_cst_sgn (val1);
1290       int sgn2 = tree_int_cst_sgn (val2);
1291
1292       /* Notice that we only need to handle the restricted set of
1293          operations handled by extract_range_from_binary_expr.
1294          Among them, only multiplication, addition and subtraction
1295          can yield overflow without overflown operands because we
1296          are working with integral types only... except in the
1297          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1298          for division too.  */
1299
1300       /* For multiplication, the sign of the overflow is given
1301          by the comparison of the signs of the operands.  */
1302       if ((code == MULT_EXPR && sgn1 == sgn2)
1303           /* For addition, the operands must be of the same sign
1304              to yield an overflow.  Its sign is therefore that
1305              of one of the operands, for example the first.  */
1306           || (code == PLUS_EXPR && sgn1 > 0)
1307           /* For subtraction, the operands must be of different
1308              signs to yield an overflow.  Its sign is therefore
1309              that of the first operand or the opposite of that
1310              of the second operand.  A first operand of 0 counts
1311              as positive here, for the corner case 0 - (-INF),
1312              which overflows, but must yield +INF.  */
1313           || (code == MINUS_EXPR && sgn1 >= 0)
1314           /* For division, the only case is -INF / -1 = +INF.  */
1315           || code == TRUNC_DIV_EXPR
1316           || code == FLOOR_DIV_EXPR
1317           || code == CEIL_DIV_EXPR
1318           || code == EXACT_DIV_EXPR
1319           || code == ROUND_DIV_EXPR)
1320         return TYPE_MAX_VALUE (TREE_TYPE (res));
1321       else
1322         return TYPE_MIN_VALUE (TREE_TYPE (res));
1323     }
1324
1325   return res;
1326 }
1327
1328
1329 /* Extract range information from a binary expression EXPR based on
1330    the ranges of each of its operands and the expression code.  */
1331
1332 static void
1333 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1334 {
1335   enum tree_code code = TREE_CODE (expr);
1336   enum value_range_type type;
1337   tree op0, op1, min, max;
1338   int cmp;
1339   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1340   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1341
1342   /* Not all binary expressions can be applied to ranges in a
1343      meaningful way.  Handle only arithmetic operations.  */
1344   if (code != PLUS_EXPR
1345       && code != MINUS_EXPR
1346       && code != MULT_EXPR
1347       && code != TRUNC_DIV_EXPR
1348       && code != FLOOR_DIV_EXPR
1349       && code != CEIL_DIV_EXPR
1350       && code != EXACT_DIV_EXPR
1351       && code != ROUND_DIV_EXPR
1352       && code != MIN_EXPR
1353       && code != MAX_EXPR
1354       && code != BIT_AND_EXPR
1355       && code != TRUTH_ANDIF_EXPR
1356       && code != TRUTH_ORIF_EXPR
1357       && code != TRUTH_AND_EXPR
1358       && code != TRUTH_OR_EXPR)
1359     {
1360       set_value_range_to_varying (vr);
1361       return;
1362     }
1363
1364   /* Get value ranges for each operand.  For constant operands, create
1365      a new value range with the operand to simplify processing.  */
1366   op0 = TREE_OPERAND (expr, 0);
1367   if (TREE_CODE (op0) == SSA_NAME)
1368     vr0 = *(get_value_range (op0));
1369   else if (is_gimple_min_invariant (op0))
1370     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1371   else
1372     set_value_range_to_varying (&vr0);
1373
1374   op1 = TREE_OPERAND (expr, 1);
1375   if (TREE_CODE (op1) == SSA_NAME)
1376     vr1 = *(get_value_range (op1));
1377   else if (is_gimple_min_invariant (op1))
1378     set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1379   else
1380     set_value_range_to_varying (&vr1);
1381
1382   /* If either range is UNDEFINED, so is the result.  */
1383   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1384     {
1385       set_value_range_to_undefined (vr);
1386       return;
1387     }
1388
1389   /* The type of the resulting value range defaults to VR0.TYPE.  */
1390   type = vr0.type;
1391
1392   /* Refuse to operate on VARYING ranges, ranges of different kinds
1393      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
1394      because we may be able to derive a useful range even if one of
1395      the operands is VR_VARYING or symbolic range.  TODO, we may be
1396      able to derive anti-ranges in some cases.  */
1397   if (code != BIT_AND_EXPR
1398       && code != TRUTH_AND_EXPR
1399       && code != TRUTH_OR_EXPR
1400       && (vr0.type == VR_VARYING
1401           || vr1.type == VR_VARYING
1402           || vr0.type != vr1.type
1403           || symbolic_range_p (&vr0)
1404           || symbolic_range_p (&vr1)))
1405     {
1406       set_value_range_to_varying (vr);
1407       return;
1408     }
1409
1410   /* Now evaluate the expression to determine the new range.  */
1411   if (POINTER_TYPE_P (TREE_TYPE (expr))
1412       || POINTER_TYPE_P (TREE_TYPE (op0))
1413       || POINTER_TYPE_P (TREE_TYPE (op1)))
1414     {
1415       /* For pointer types, we are really only interested in asserting
1416          whether the expression evaluates to non-NULL.  FIXME, we used
1417          to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1418          ivopts is generating expressions with pointer multiplication
1419          in them.  */
1420       if (code == PLUS_EXPR)
1421         {
1422           if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1423             set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1424           else if (range_is_null (&vr0) && range_is_null (&vr1))
1425             set_value_range_to_null (vr, TREE_TYPE (expr));
1426           else
1427             set_value_range_to_varying (vr);
1428         }
1429       else
1430         {
1431           /* Subtracting from a pointer, may yield 0, so just drop the
1432              resulting range to varying.  */
1433           set_value_range_to_varying (vr);
1434         }
1435
1436       return;
1437     }
1438
1439   /* For integer ranges, apply the operation to each end of the
1440      range and see what we end up with.  */
1441   if (code == TRUTH_ANDIF_EXPR
1442       || code == TRUTH_ORIF_EXPR
1443       || code == TRUTH_AND_EXPR
1444       || code == TRUTH_OR_EXPR)
1445     {
1446       /* If one of the operands is zero, we know that the whole
1447          expression evaluates zero.  */
1448       if (code == TRUTH_AND_EXPR
1449           && ((vr0.type == VR_RANGE
1450                && integer_zerop (vr0.min)
1451                && integer_zerop (vr0.max))
1452               || (vr1.type == VR_RANGE
1453                   && integer_zerop (vr1.min)
1454                   && integer_zerop (vr1.max))))
1455         {
1456           type = VR_RANGE;
1457           min = max = build_int_cst (TREE_TYPE (expr), 0);
1458         }
1459       /* If one of the operands is one, we know that the whole
1460          expression evaluates one.  */
1461       else if (code == TRUTH_OR_EXPR
1462                && ((vr0.type == VR_RANGE
1463                     && integer_onep (vr0.min)
1464                     && integer_onep (vr0.max))
1465                    || (vr1.type == VR_RANGE
1466                        && integer_onep (vr1.min)
1467                        && integer_onep (vr1.max))))
1468         {
1469           type = VR_RANGE;
1470           min = max = build_int_cst (TREE_TYPE (expr), 1);
1471         }
1472       else if (vr0.type != VR_VARYING
1473                && vr1.type != VR_VARYING
1474                && vr0.type == vr1.type
1475                && !symbolic_range_p (&vr0)
1476                && !symbolic_range_p (&vr1))
1477         {
1478           /* Boolean expressions cannot be folded with int_const_binop.  */
1479           min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1480           max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1481         }
1482       else
1483         {
1484           set_value_range_to_varying (vr);
1485           return;
1486         }
1487     }
1488   else if (code == PLUS_EXPR
1489            || code == MIN_EXPR
1490            || code == MAX_EXPR)
1491     {
1492       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
1493          VR_VARYING.  It would take more effort to compute a precise
1494          range for such a case.  For example, if we have op0 == 1 and
1495          op1 == -1 with their ranges both being ~[0,0], we would have
1496          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
1497          Note that we are guaranteed to have vr0.type == vr1.type at
1498          this point.  */
1499       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
1500         {
1501           set_value_range_to_varying (vr);
1502           return;
1503         }
1504
1505       /* For operations that make the resulting range directly
1506          proportional to the original ranges, apply the operation to
1507          the same end of each range.  */
1508       min = vrp_int_const_binop (code, vr0.min, vr1.min);
1509       max = vrp_int_const_binop (code, vr0.max, vr1.max);
1510     }
1511   else if (code == MULT_EXPR
1512            || code == TRUNC_DIV_EXPR
1513            || code == FLOOR_DIV_EXPR
1514            || code == CEIL_DIV_EXPR
1515            || code == EXACT_DIV_EXPR
1516            || code == ROUND_DIV_EXPR)
1517     {
1518       tree val[4];
1519       size_t i;
1520
1521       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
1522          drop to VR_VARYING.  It would take more effort to compute a
1523          precise range for such a case.  For example, if we have
1524          op0 == 65536 and op1 == 65536 with their ranges both being
1525          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
1526          we cannot claim that the product is in ~[0,0].  Note that we
1527          are guaranteed to have vr0.type == vr1.type at this
1528          point.  */
1529       if (code == MULT_EXPR
1530           && vr0.type == VR_ANTI_RANGE
1531           && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
1532         {
1533           set_value_range_to_varying (vr);
1534           return;
1535         }
1536
1537       /* Multiplications and divisions are a bit tricky to handle,
1538          depending on the mix of signs we have in the two ranges, we
1539          need to operate on different values to get the minimum and
1540          maximum values for the new range.  One approach is to figure
1541          out all the variations of range combinations and do the
1542          operations.
1543
1544          However, this involves several calls to compare_values and it
1545          is pretty convoluted.  It's simpler to do the 4 operations
1546          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1547          MAX1) and then figure the smallest and largest values to form
1548          the new range.  */
1549
1550       /* Divisions by zero result in a VARYING value.  */
1551       if (code != MULT_EXPR
1552           && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
1553         {
1554           set_value_range_to_varying (vr);
1555           return;
1556         }
1557
1558       /* Compute the 4 cross operations.  */
1559       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1560
1561       val[1] = (vr1.max != vr1.min)
1562                ? vrp_int_const_binop (code, vr0.min, vr1.max)
1563                : NULL_TREE;
1564
1565       val[2] = (vr0.max != vr0.min)
1566                ? vrp_int_const_binop (code, vr0.max, vr1.min)
1567                : NULL_TREE;
1568
1569       val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
1570                ? vrp_int_const_binop (code, vr0.max, vr1.max)
1571                : NULL_TREE;
1572
1573       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1574          of VAL[i].  */
1575       min = val[0];
1576       max = val[0];
1577       for (i = 1; i < 4; i++)
1578         {
1579           if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1580               || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1581             break;
1582
1583           if (val[i])
1584             {
1585               if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
1586                 {
1587                   /* If we found an overflowed value, set MIN and MAX
1588                      to it so that we set the resulting range to
1589                      VARYING.  */
1590                   min = max = val[i];
1591                   break;
1592                 }
1593
1594               if (compare_values (val[i], min) == -1)
1595                 min = val[i];
1596
1597               if (compare_values (val[i], max) == 1)
1598                 max = val[i];
1599             }
1600         }
1601     }
1602   else if (code == MINUS_EXPR)
1603     {
1604       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
1605          VR_VARYING.  It would take more effort to compute a precise
1606          range for such a case.  For example, if we have op0 == 1 and
1607          op1 == 1 with their ranges both being ~[0,0], we would have
1608          op0 - op1 == 0, so we cannot claim that the difference is in
1609          ~[0,0].  Note that we are guaranteed to have
1610          vr0.type == vr1.type at this point.  */
1611       if (vr0.type == VR_ANTI_RANGE)
1612         {
1613           set_value_range_to_varying (vr);
1614           return;
1615         }
1616
1617       /* For MINUS_EXPR, apply the operation to the opposite ends of
1618          each range.  */
1619       min = vrp_int_const_binop (code, vr0.min, vr1.max);
1620       max = vrp_int_const_binop (code, vr0.max, vr1.min);
1621     }
1622   else if (code == BIT_AND_EXPR)
1623     {
1624       if (vr0.type == VR_RANGE
1625           && vr0.min == vr0.max
1626           && tree_expr_nonnegative_p (vr0.max)
1627           && TREE_CODE (vr0.max) == INTEGER_CST)
1628         {
1629           min = build_int_cst (TREE_TYPE (expr), 0);
1630           max = vr0.max;
1631         }
1632       else if (vr1.type == VR_RANGE
1633           && vr1.min == vr1.max
1634           && tree_expr_nonnegative_p (vr1.max)
1635           && TREE_CODE (vr1.max) == INTEGER_CST)
1636         {
1637           type = VR_RANGE;
1638           min = build_int_cst (TREE_TYPE (expr), 0);
1639           max = vr1.max;
1640         }
1641       else
1642         {
1643           set_value_range_to_varying (vr);
1644           return;
1645         }
1646     }
1647   else
1648     gcc_unreachable ();
1649
1650   /* If either MIN or MAX overflowed, then set the resulting range to
1651      VARYING.  */
1652   if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1653       || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1654     {
1655       set_value_range_to_varying (vr);
1656       return;
1657     }
1658
1659   cmp = compare_values (min, max);
1660   if (cmp == -2 || cmp == 1)
1661     {
1662       /* If the new range has its limits swapped around (MIN > MAX),
1663          then the operation caused one of them to wrap around, mark
1664          the new range VARYING.  */
1665       set_value_range_to_varying (vr);
1666     }
1667   else
1668     set_value_range (vr, type, min, max, NULL);
1669 }
1670
1671
1672 /* Extract range information from a unary expression EXPR based on
1673    the range of its operand and the expression code.  */
1674
1675 static void
1676 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1677 {
1678   enum tree_code code = TREE_CODE (expr);
1679   tree min, max, op0;
1680   int cmp;
1681   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1682
1683   /* Refuse to operate on certain unary expressions for which we
1684      cannot easily determine a resulting range.  */
1685   if (code == FIX_TRUNC_EXPR
1686       || code == FIX_CEIL_EXPR
1687       || code == FIX_FLOOR_EXPR
1688       || code == FIX_ROUND_EXPR
1689       || code == FLOAT_EXPR
1690       || code == BIT_NOT_EXPR
1691       || code == NON_LVALUE_EXPR
1692       || code == CONJ_EXPR)
1693     {
1694       set_value_range_to_varying (vr);
1695       return;
1696     }
1697
1698   /* Get value ranges for the operand.  For constant operands, create
1699      a new value range with the operand to simplify processing.  */
1700   op0 = TREE_OPERAND (expr, 0);
1701   if (TREE_CODE (op0) == SSA_NAME)
1702     vr0 = *(get_value_range (op0));
1703   else if (is_gimple_min_invariant (op0))
1704     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1705   else
1706     set_value_range_to_varying (&vr0);
1707
1708   /* If VR0 is UNDEFINED, so is the result.  */
1709   if (vr0.type == VR_UNDEFINED)
1710     {
1711       set_value_range_to_undefined (vr);
1712       return;
1713     }
1714
1715   /* Refuse to operate on symbolic ranges, or if neither operand is
1716      a pointer or integral type.  */
1717   if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1718        && !POINTER_TYPE_P (TREE_TYPE (op0)))
1719       || (vr0.type != VR_VARYING
1720           && symbolic_range_p (&vr0)))
1721     {
1722       set_value_range_to_varying (vr);
1723       return;
1724     }
1725
1726   /* If the expression involves pointers, we are only interested in
1727      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
1728   if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1729     {
1730       if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
1731         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1732       else if (range_is_null (&vr0))
1733         set_value_range_to_null (vr, TREE_TYPE (expr));
1734       else
1735         set_value_range_to_varying (vr);
1736
1737       return;
1738     }
1739
1740   /* Handle unary expressions on integer ranges.  */
1741   if (code == NOP_EXPR || code == CONVERT_EXPR)
1742     {
1743       tree inner_type = TREE_TYPE (op0);
1744       tree outer_type = TREE_TYPE (expr);
1745
1746       /* If VR0 represents a simple range, then try to convert
1747          the min and max values for the range to the same type
1748          as OUTER_TYPE.  If the results compare equal to VR0's
1749          min and max values and the new min is still less than
1750          or equal to the new max, then we can safely use the newly
1751          computed range for EXPR.  This allows us to compute
1752          accurate ranges through many casts.  */
1753       if (vr0.type == VR_RANGE
1754           || (vr0.type == VR_VARYING
1755               && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
1756         {
1757           tree new_min, new_max, orig_min, orig_max;
1758
1759           /* Convert the input operand min/max to OUTER_TYPE.   If
1760              the input has no range information, then use the min/max
1761              for the input's type.  */
1762           if (vr0.type == VR_RANGE)
1763             {
1764               orig_min = vr0.min;
1765               orig_max = vr0.max;
1766             }
1767           else
1768             {
1769               orig_min = TYPE_MIN_VALUE (inner_type);
1770               orig_max = TYPE_MAX_VALUE (inner_type);
1771             }
1772
1773           new_min = fold_convert (outer_type, orig_min);
1774           new_max = fold_convert (outer_type, orig_max);
1775
1776           /* Verify the new min/max values are gimple values and
1777              that they compare equal to the original input's
1778              min/max values.  */
1779           if (is_gimple_val (new_min)
1780               && is_gimple_val (new_max)
1781               && tree_int_cst_equal (new_min, orig_min)
1782               && tree_int_cst_equal (new_max, orig_max)
1783               && compare_values (new_min, new_max) <= 0
1784               && compare_values (new_min, new_max) >= -1)
1785             {
1786               set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
1787               return;
1788             }
1789         }
1790
1791       /* When converting types of different sizes, set the result to
1792          VARYING.  Things like sign extensions and precision loss may
1793          change the range.  For instance, if x_3 is of type 'long long
1794          int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1795          is impossible to know at compile time whether y_5 will be
1796          ~[0, 0].  */
1797       if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1798           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1799         {
1800           set_value_range_to_varying (vr);
1801           return;
1802         }
1803     }
1804
1805   /* Conversion of a VR_VARYING value to a wider type can result
1806      in a usable range.  So wait until after we've handled conversions
1807      before dropping the result to VR_VARYING if we had a source
1808      operand that is VR_VARYING.  */
1809   if (vr0.type == VR_VARYING)
1810     {
1811       set_value_range_to_varying (vr);
1812       return;
1813     }
1814
1815   /* Apply the operation to each end of the range and see what we end
1816      up with.  */
1817   if (code == NEGATE_EXPR
1818       && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1819     {
1820       /* NEGATE_EXPR flips the range around.  We need to treat
1821          TYPE_MIN_VALUE specially dependent on wrapping, range type
1822          and if it was used as minimum or maximum value:
1823           -~[MIN, MIN] == ~[MIN, MIN]
1824           -[MIN, 0] == [0, MAX]  for -fno-wrapv
1825           -[MIN, 0] == [0, MIN]  for -fwrapv (will be set to varying later)  */
1826       min = vr0.max == TYPE_MIN_VALUE (TREE_TYPE (expr))
1827             ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1828             : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1829
1830       max = vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr))
1831             ? (vr0.type == VR_ANTI_RANGE || flag_wrapv
1832                ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1833                : TYPE_MAX_VALUE (TREE_TYPE (expr)))
1834             : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1835
1836     }
1837   else if (code == NEGATE_EXPR
1838            && TYPE_UNSIGNED (TREE_TYPE (expr)))
1839     {
1840       if (!range_includes_zero_p (&vr0))
1841         {
1842           max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1843           min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1844         }
1845       else
1846         {
1847           if (range_is_null (&vr0))
1848             set_value_range_to_null (vr, TREE_TYPE (expr));
1849           else
1850             set_value_range_to_varying (vr);
1851           return;
1852         }
1853     }
1854   else if (code == ABS_EXPR
1855            && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1856     {
1857       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
1858          useful range.  */
1859       if (flag_wrapv
1860           && ((vr0.type == VR_RANGE
1861                && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1862               || (vr0.type == VR_ANTI_RANGE
1863                   && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
1864                   && !range_includes_zero_p (&vr0))))
1865         {
1866           set_value_range_to_varying (vr);
1867           return;
1868         }
1869
1870       /* ABS_EXPR may flip the range around, if the original range
1871          included negative values.  */
1872       min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1873             ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1874             : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1875
1876       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1877
1878       cmp = compare_values (min, max);
1879
1880       /* If a VR_ANTI_RANGEs contains zero, then we have
1881          ~[-INF, min(MIN, MAX)].  */
1882       if (vr0.type == VR_ANTI_RANGE)
1883         {
1884           if (range_includes_zero_p (&vr0))
1885             {
1886               tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
1887
1888               /* Take the lower of the two values.  */
1889               if (cmp != 1)
1890                 max = min;
1891
1892               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
1893                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
1894                  flag_wrapv is set and the original anti-range doesn't include
1895                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
1896               min = (flag_wrapv && vr0.min != type_min_value
1897                      ? int_const_binop (PLUS_EXPR,
1898                                         type_min_value,
1899                                         integer_one_node, 0)
1900                      : type_min_value);
1901             }
1902           else
1903             {
1904               /* All else has failed, so create the range [0, INF], even for
1905                  flag_wrapv since TYPE_MIN_VALUE is in the original
1906                  anti-range.  */
1907               vr0.type = VR_RANGE;
1908               min = build_int_cst (TREE_TYPE (expr), 0);
1909               max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1910             }
1911         }
1912
1913       /* If the range contains zero then we know that the minimum value in the
1914          range will be zero.  */
1915       else if (range_includes_zero_p (&vr0))
1916         {
1917           if (cmp == 1)
1918             max = min;
1919           min = build_int_cst (TREE_TYPE (expr), 0);
1920         }
1921       else
1922         {
1923           /* If the range was reversed, swap MIN and MAX.  */
1924           if (cmp == 1)
1925             {
1926               tree t = min;
1927               min = max;
1928               max = t;
1929             }
1930         }
1931     }
1932   else
1933     {
1934       /* Otherwise, operate on each end of the range.  */
1935       min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1936       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1937     }
1938
1939   cmp = compare_values (min, max);
1940   if (cmp == -2 || cmp == 1)
1941     {
1942       /* If the new range has its limits swapped around (MIN > MAX),
1943          then the operation caused one of them to wrap around, mark
1944          the new range VARYING.  */
1945       set_value_range_to_varying (vr);
1946     }
1947   else
1948     set_value_range (vr, vr0.type, min, max, NULL);
1949 }
1950
1951
1952 /* Extract range information from a comparison expression EXPR based
1953    on the range of its operand and the expression code.  */
1954
1955 static void
1956 extract_range_from_comparison (value_range_t *vr, tree expr)
1957 {
1958   tree val = vrp_evaluate_conditional (expr, false);
1959   if (val)
1960     {
1961       /* Since this expression was found on the RHS of an assignment,
1962          its type may be different from _Bool.  Convert VAL to EXPR's
1963          type.  */
1964       val = fold_convert (TREE_TYPE (expr), val);
1965       set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1966     }
1967   else
1968     set_value_range_to_varying (vr);
1969 }
1970
1971
1972 /* Try to compute a useful range out of expression EXPR and store it
1973    in *VR.  */
1974
1975 static void
1976 extract_range_from_expr (value_range_t *vr, tree expr)
1977 {
1978   enum tree_code code = TREE_CODE (expr);
1979
1980   if (code == ASSERT_EXPR)
1981     extract_range_from_assert (vr, expr);
1982   else if (code == SSA_NAME)
1983     extract_range_from_ssa_name (vr, expr);
1984   else if (TREE_CODE_CLASS (code) == tcc_binary
1985            || code == TRUTH_ANDIF_EXPR
1986            || code == TRUTH_ORIF_EXPR
1987            || code == TRUTH_AND_EXPR
1988            || code == TRUTH_OR_EXPR
1989            || code == TRUTH_XOR_EXPR)
1990     extract_range_from_binary_expr (vr, expr);
1991   else if (TREE_CODE_CLASS (code) == tcc_unary)
1992     extract_range_from_unary_expr (vr, expr);
1993   else if (TREE_CODE_CLASS (code) == tcc_comparison)
1994     extract_range_from_comparison (vr, expr);
1995   else if (is_gimple_min_invariant (expr))
1996     set_value_range (vr, VR_RANGE, expr, expr, NULL);
1997   else
1998     set_value_range_to_varying (vr);
1999
2000   /* If we got a varying range from the tests above, try a final
2001      time to derive a nonnegative or nonzero range.  This time
2002      relying primarily on generic routines in fold in conjunction
2003      with range data.  */
2004   if (vr->type == VR_VARYING)
2005     {
2006       if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
2007           && vrp_expr_computes_nonnegative (expr))
2008         set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
2009       else if (vrp_expr_computes_nonzero (expr))
2010         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
2011     }
2012 }
2013
2014 /* Given a range VR, a LOOP and a variable VAR, determine whether it
2015    would be profitable to adjust VR using scalar evolution information
2016    for VAR.  If so, update VR with the new limits.  */
2017
2018 static void
2019 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
2020                         tree var)
2021 {
2022   tree init, step, chrec, tmin, tmax, min, max, type;
2023   enum ev_direction dir;
2024
2025   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
2026      better opportunities than a regular range, but I'm not sure.  */
2027   if (vr->type == VR_ANTI_RANGE)
2028     return;
2029
2030   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
2031   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2032     return;
2033
2034   init = initial_condition_in_loop_num (chrec, loop->num);
2035   step = evolution_part_in_loop_num (chrec, loop->num);
2036
2037   /* If STEP is symbolic, we can't know whether INIT will be the
2038      minimum or maximum value in the range.  Also, unless INIT is
2039      a simple expression, compare_values and possibly other functions
2040      in tree-vrp won't be able to handle it.  */
2041   if (step == NULL_TREE
2042       || !is_gimple_min_invariant (step)
2043       || !valid_value_p (init))
2044     return;
2045
2046   dir = scev_direction (chrec);
2047   if (/* Do not adjust ranges if we do not know whether the iv increases
2048          or decreases,  ... */
2049       dir == EV_DIR_UNKNOWN
2050       /* ... or if it may wrap.  */
2051       || scev_probably_wraps_p (init, step, stmt,
2052                                 current_loops->parray[CHREC_VARIABLE (chrec)],
2053                                 true))
2054     return;
2055
2056   type = TREE_TYPE (var);
2057   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
2058     tmin = lower_bound_in_type (type, type);
2059   else
2060     tmin = TYPE_MIN_VALUE (type);
2061   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
2062     tmax = upper_bound_in_type (type, type);
2063   else
2064     tmax = TYPE_MAX_VALUE (type);
2065
2066   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2067     {
2068       min = tmin;
2069       max = tmax;
2070
2071       /* For VARYING or UNDEFINED ranges, just about anything we get
2072          from scalar evolutions should be better.  */
2073
2074       if (dir == EV_DIR_DECREASES)
2075         max = init;
2076       else
2077         min = init;
2078
2079       /* If we would create an invalid range, then just assume we
2080          know absolutely nothing.  This may be over-conservative,
2081          but it's clearly safe, and should happen only in unreachable
2082          parts of code, or for invalid programs.  */
2083       if (compare_values (min, max) == 1)
2084         return;
2085
2086       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2087     }
2088   else if (vr->type == VR_RANGE)
2089     {
2090       min = vr->min;
2091       max = vr->max;
2092
2093       if (dir == EV_DIR_DECREASES)
2094         {
2095           /* INIT is the maximum value.  If INIT is lower than VR->MAX
2096              but no smaller than VR->MIN, set VR->MAX to INIT.  */
2097           if (compare_values (init, max) == -1)
2098             {
2099               max = init;
2100
2101               /* If we just created an invalid range with the minimum
2102                  greater than the maximum, we fail conservatively.
2103                  This should happen only in unreachable
2104                  parts of code, or for invalid programs.  */
2105               if (compare_values (min, max) == 1)
2106                 return;
2107             }
2108         }
2109       else
2110         {
2111           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
2112           if (compare_values (init, min) == 1)
2113             {
2114               min = init;
2115
2116               /* Again, avoid creating invalid range by failing.  */
2117               if (compare_values (min, max) == 1)
2118                 return;
2119             }
2120         }
2121
2122       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2123     }
2124 }
2125
2126
2127 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2128
2129    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2130      all the values in the ranges.
2131
2132    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2133
2134    - Return NULL_TREE if it is not always possible to determine the
2135      value of the comparison.  */
2136
2137
2138 static tree
2139 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
2140 {
2141   /* VARYING or UNDEFINED ranges cannot be compared.  */
2142   if (vr0->type == VR_VARYING
2143       || vr0->type == VR_UNDEFINED
2144       || vr1->type == VR_VARYING
2145       || vr1->type == VR_UNDEFINED)
2146     return NULL_TREE;
2147
2148   /* Anti-ranges need to be handled separately.  */
2149   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2150     {
2151       /* If both are anti-ranges, then we cannot compute any
2152          comparison.  */
2153       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2154         return NULL_TREE;
2155
2156       /* These comparisons are never statically computable.  */
2157       if (comp == GT_EXPR
2158           || comp == GE_EXPR
2159           || comp == LT_EXPR
2160           || comp == LE_EXPR)
2161         return NULL_TREE;
2162
2163       /* Equality can be computed only between a range and an
2164          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
2165       if (vr0->type == VR_RANGE)
2166         {
2167           /* To simplify processing, make VR0 the anti-range.  */
2168           value_range_t *tmp = vr0;
2169           vr0 = vr1;
2170           vr1 = tmp;
2171         }
2172
2173       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
2174
2175       if (compare_values (vr0->min, vr1->min) == 0
2176           && compare_values (vr0->max, vr1->max) == 0)
2177         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2178
2179       return NULL_TREE;
2180     }
2181
2182   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
2183      operands around and change the comparison code.  */
2184   if (comp == GT_EXPR || comp == GE_EXPR)
2185     {
2186       value_range_t *tmp;
2187       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
2188       tmp = vr0;
2189       vr0 = vr1;
2190       vr1 = tmp;
2191     }
2192
2193   if (comp == EQ_EXPR)
2194     {
2195       /* Equality may only be computed if both ranges represent
2196          exactly one value.  */
2197       if (compare_values (vr0->min, vr0->max) == 0
2198           && compare_values (vr1->min, vr1->max) == 0)
2199         {
2200           int cmp_min = compare_values (vr0->min, vr1->min);
2201           int cmp_max = compare_values (vr0->max, vr1->max);
2202           if (cmp_min == 0 && cmp_max == 0)
2203             return boolean_true_node;
2204           else if (cmp_min != -2 && cmp_max != -2)
2205             return boolean_false_node;
2206         }
2207       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
2208       else if (compare_values (vr0->min, vr1->max) == 1
2209                || compare_values (vr1->min, vr0->max) == 1)
2210         return boolean_false_node;
2211
2212       return NULL_TREE;
2213     }
2214   else if (comp == NE_EXPR)
2215     {
2216       int cmp1, cmp2;
2217
2218       /* If VR0 is completely to the left or completely to the right
2219          of VR1, they are always different.  Notice that we need to
2220          make sure that both comparisons yield similar results to
2221          avoid comparing values that cannot be compared at
2222          compile-time.  */
2223       cmp1 = compare_values (vr0->max, vr1->min);
2224       cmp2 = compare_values (vr0->min, vr1->max);
2225       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
2226         return boolean_true_node;
2227
2228       /* If VR0 and VR1 represent a single value and are identical,
2229          return false.  */
2230       else if (compare_values (vr0->min, vr0->max) == 0
2231                && compare_values (vr1->min, vr1->max) == 0
2232                && compare_values (vr0->min, vr1->min) == 0
2233                && compare_values (vr0->max, vr1->max) == 0)
2234         return boolean_false_node;
2235
2236       /* Otherwise, they may or may not be different.  */
2237       else
2238         return NULL_TREE;
2239     }
2240   else if (comp == LT_EXPR || comp == LE_EXPR)
2241     {
2242       int tst;
2243
2244       /* If VR0 is to the left of VR1, return true.  */
2245       tst = compare_values (vr0->max, vr1->min);
2246       if ((comp == LT_EXPR && tst == -1)
2247           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2248         return boolean_true_node;
2249
2250       /* If VR0 is to the right of VR1, return false.  */
2251       tst = compare_values (vr0->min, vr1->max);
2252       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2253           || (comp == LE_EXPR && tst == 1))
2254         return boolean_false_node;
2255
2256       /* Otherwise, we don't know.  */
2257       return NULL_TREE;
2258     }
2259
2260   gcc_unreachable ();
2261 }
2262
2263
2264 /* Given a value range VR, a value VAL and a comparison code COMP, return
2265    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
2266    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
2267    always returns false.  Return NULL_TREE if it is not always
2268    possible to determine the value of the comparison.  */
2269
2270 static tree
2271 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
2272 {
2273   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2274     return NULL_TREE;
2275
2276   /* Anti-ranges need to be handled separately.  */
2277   if (vr->type == VR_ANTI_RANGE)
2278     {
2279       /* For anti-ranges, the only predicates that we can compute at
2280          compile time are equality and inequality.  */
2281       if (comp == GT_EXPR
2282           || comp == GE_EXPR
2283           || comp == LT_EXPR
2284           || comp == LE_EXPR)
2285         return NULL_TREE;
2286
2287       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
2288       if (value_inside_range (val, vr) == 1)
2289         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2290
2291       return NULL_TREE;
2292     }
2293
2294   if (comp == EQ_EXPR)
2295     {
2296       /* EQ_EXPR may only be computed if VR represents exactly
2297          one value.  */
2298       if (compare_values (vr->min, vr->max) == 0)
2299         {
2300           int cmp = compare_values (vr->min, val);
2301           if (cmp == 0)
2302             return boolean_true_node;
2303           else if (cmp == -1 || cmp == 1 || cmp == 2)
2304             return boolean_false_node;
2305         }
2306       else if (compare_values (val, vr->min) == -1
2307                || compare_values (vr->max, val) == -1)
2308         return boolean_false_node;
2309
2310       return NULL_TREE;
2311     }
2312   else if (comp == NE_EXPR)
2313     {
2314       /* If VAL is not inside VR, then they are always different.  */
2315       if (compare_values (vr->max, val) == -1
2316           || compare_values (vr->min, val) == 1)
2317         return boolean_true_node;
2318
2319       /* If VR represents exactly one value equal to VAL, then return
2320          false.  */
2321       if (compare_values (vr->min, vr->max) == 0
2322           && compare_values (vr->min, val) == 0)
2323         return boolean_false_node;
2324
2325       /* Otherwise, they may or may not be different.  */
2326       return NULL_TREE;
2327     }
2328   else if (comp == LT_EXPR || comp == LE_EXPR)
2329     {
2330       int tst;
2331
2332       /* If VR is to the left of VAL, return true.  */
2333       tst = compare_values (vr->max, val);
2334       if ((comp == LT_EXPR && tst == -1)
2335           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2336         return boolean_true_node;
2337
2338       /* If VR is to the right of VAL, return false.  */
2339       tst = compare_values (vr->min, val);
2340       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2341           || (comp == LE_EXPR && tst == 1))
2342         return boolean_false_node;
2343
2344       /* Otherwise, we don't know.  */
2345       return NULL_TREE;
2346     }
2347   else if (comp == GT_EXPR || comp == GE_EXPR)
2348     {
2349       int tst;
2350
2351       /* If VR is to the right of VAL, return true.  */
2352       tst = compare_values (vr->min, val);
2353       if ((comp == GT_EXPR && tst == 1)
2354           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
2355         return boolean_true_node;
2356
2357       /* If VR is to the left of VAL, return false.  */
2358       tst = compare_values (vr->max, val);
2359       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
2360           || (comp == GE_EXPR && tst == -1))
2361         return boolean_false_node;
2362
2363       /* Otherwise, we don't know.  */
2364       return NULL_TREE;
2365     }
2366
2367   gcc_unreachable ();
2368 }
2369
2370
2371 /* Debugging dumps.  */
2372
2373 void dump_value_range (FILE *, value_range_t *);
2374 void debug_value_range (value_range_t *);
2375 void dump_all_value_ranges (FILE *);
2376 void debug_all_value_ranges (void);
2377 void dump_vr_equiv (FILE *, bitmap);
2378 void debug_vr_equiv (bitmap);
2379
2380
2381 /* Dump value range VR to FILE.  */
2382
2383 void
2384 dump_value_range (FILE *file, value_range_t *vr)
2385 {
2386   if (vr == NULL)
2387     fprintf (file, "[]");
2388   else if (vr->type == VR_UNDEFINED)
2389     fprintf (file, "UNDEFINED");
2390   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
2391     {
2392       tree type = TREE_TYPE (vr->min);
2393
2394       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
2395
2396       if (INTEGRAL_TYPE_P (type)
2397           && !TYPE_UNSIGNED (type)
2398           && vr->min == TYPE_MIN_VALUE (type))
2399         fprintf (file, "-INF");
2400       else
2401         print_generic_expr (file, vr->min, 0);
2402
2403       fprintf (file, ", ");
2404
2405       if (INTEGRAL_TYPE_P (type)
2406           && vr->max == TYPE_MAX_VALUE (type))
2407         fprintf (file, "+INF");
2408       else
2409         print_generic_expr (file, vr->max, 0);
2410
2411       fprintf (file, "]");
2412
2413       if (vr->equiv)
2414         {
2415           bitmap_iterator bi;
2416           unsigned i, c = 0;
2417
2418           fprintf (file, "  EQUIVALENCES: { ");
2419
2420           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
2421             {
2422               print_generic_expr (file, ssa_name (i), 0);
2423               fprintf (file, " ");
2424               c++;
2425             }
2426
2427           fprintf (file, "} (%u elements)", c);
2428         }
2429     }
2430   else if (vr->type == VR_VARYING)
2431     fprintf (file, "VARYING");
2432   else
2433     fprintf (file, "INVALID RANGE");
2434 }
2435
2436
2437 /* Dump value range VR to stderr.  */
2438
2439 void
2440 debug_value_range (value_range_t *vr)
2441 {
2442   dump_value_range (stderr, vr);
2443 }
2444
2445
2446 /* Dump value ranges of all SSA_NAMEs to FILE.  */
2447
2448 void
2449 dump_all_value_ranges (FILE *file)
2450 {
2451   size_t i;
2452
2453   for (i = 0; i < num_ssa_names; i++)
2454     {
2455       if (vr_value[i])
2456         {
2457           print_generic_expr (file, ssa_name (i), 0);
2458           fprintf (file, ": ");
2459           dump_value_range (file, vr_value[i]);
2460           fprintf (file, "\n");
2461         }
2462     }
2463
2464   fprintf (file, "\n");
2465 }
2466
2467
2468 /* Dump all value ranges to stderr.  */
2469
2470 void
2471 debug_all_value_ranges (void)
2472 {
2473   dump_all_value_ranges (stderr);
2474 }
2475
2476
2477 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
2478    create a new SSA name N and return the assertion assignment
2479    'V = ASSERT_EXPR <V, V OP W>'.  */
2480
2481 static tree
2482 build_assert_expr_for (tree cond, tree v)
2483 {
2484   tree n, assertion;
2485
2486   gcc_assert (TREE_CODE (v) == SSA_NAME);
2487   n = duplicate_ssa_name (v, NULL_TREE);
2488
2489   if (COMPARISON_CLASS_P (cond))
2490     {
2491       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
2492       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
2493     }
2494   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2495     {
2496       /* Given !V, build the assignment N = false.  */
2497       tree op0 = TREE_OPERAND (cond, 0);
2498       gcc_assert (op0 == v);
2499       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
2500     }
2501   else if (TREE_CODE (cond) == SSA_NAME)
2502     {
2503       /* Given V, build the assignment N = true.  */
2504       gcc_assert (v == cond);
2505       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
2506     }
2507   else
2508     gcc_unreachable ();
2509
2510   SSA_NAME_DEF_STMT (n) = assertion;
2511
2512   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
2513      operand of the ASSERT_EXPR. Register the new name and the old one
2514      in the replacement table so that we can fix the SSA web after
2515      adding all the ASSERT_EXPRs.  */
2516   register_new_name_mapping (n, v);
2517
2518   return assertion;
2519 }
2520
2521
2522 /* Return false if EXPR is a predicate expression involving floating
2523    point values.  */
2524
2525 static inline bool
2526 fp_predicate (tree expr)
2527 {
2528   return (COMPARISON_CLASS_P (expr)
2529           && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
2530 }
2531
2532
2533 /* If the range of values taken by OP can be inferred after STMT executes,
2534    return the comparison code (COMP_CODE_P) and value (VAL_P) that
2535    describes the inferred range.  Return true if a range could be
2536    inferred.  */
2537
2538 static bool
2539 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
2540 {
2541   *val_p = NULL_TREE;
2542   *comp_code_p = ERROR_MARK;
2543
2544   /* Do not attempt to infer anything in names that flow through
2545      abnormal edges.  */
2546   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2547     return false;
2548
2549   /* Similarly, don't infer anything from statements that may throw
2550      exceptions.  */
2551   if (tree_could_throw_p (stmt))
2552     return false;
2553
2554   /* If STMT is the last statement of a basic block with no
2555      successors, there is no point inferring anything about any of its
2556      operands.  We would not be able to find a proper insertion point
2557      for the assertion, anyway.  */
2558   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
2559     return false;
2560
2561   /* We can only assume that a pointer dereference will yield
2562      non-NULL if -fdelete-null-pointer-checks is enabled.  */
2563   if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
2564     {
2565       bool is_store;
2566       unsigned num_uses, num_derefs;
2567
2568       count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2569       if (num_derefs > 0)
2570         {
2571           *val_p = build_int_cst (TREE_TYPE (op), 0);
2572           *comp_code_p = NE_EXPR;
2573           return true;
2574         }
2575     }
2576
2577   return false;
2578 }
2579
2580
2581 void dump_asserts_for (FILE *, tree);
2582 void debug_asserts_for (tree);
2583 void dump_all_asserts (FILE *);
2584 void debug_all_asserts (void);
2585
2586 /* Dump all the registered assertions for NAME to FILE.  */
2587
2588 void
2589 dump_asserts_for (FILE *file, tree name)
2590 {
2591   assert_locus_t loc;
2592
2593   fprintf (file, "Assertions to be inserted for ");
2594   print_generic_expr (file, name, 0);
2595   fprintf (file, "\n");
2596
2597   loc = asserts_for[SSA_NAME_VERSION (name)];
2598   while (loc)
2599     {
2600       fprintf (file, "\t");
2601       print_generic_expr (file, bsi_stmt (loc->si), 0);
2602       fprintf (file, "\n\tBB #%d", loc->bb->index);
2603       if (loc->e)
2604         {
2605           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2606                    loc->e->dest->index);
2607           dump_edge_info (file, loc->e, 0);
2608         }
2609       fprintf (file, "\n\tPREDICATE: ");
2610       print_generic_expr (file, name, 0);
2611       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2612       print_generic_expr (file, loc->val, 0);
2613       fprintf (file, "\n\n");
2614       loc = loc->next;
2615     }
2616
2617   fprintf (file, "\n");
2618 }
2619
2620
2621 /* Dump all the registered assertions for NAME to stderr.  */
2622
2623 void
2624 debug_asserts_for (tree name)
2625 {
2626   dump_asserts_for (stderr, name);
2627 }
2628
2629
2630 /* Dump all the registered assertions for all the names to FILE.  */
2631
2632 void
2633 dump_all_asserts (FILE *file)
2634 {
2635   unsigned i;
2636   bitmap_iterator bi;
2637
2638   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2639   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2640     dump_asserts_for (file, ssa_name (i));
2641   fprintf (file, "\n");
2642 }
2643
2644
2645 /* Dump all the registered assertions for all the names to stderr.  */
2646
2647 void
2648 debug_all_asserts (void)
2649 {
2650   dump_all_asserts (stderr);
2651 }
2652
2653
2654 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2655    'NAME COMP_CODE VAL' at a location that dominates block BB or
2656    E->DEST, then register this location as a possible insertion point
2657    for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2658
2659    BB, E and SI provide the exact insertion point for the new
2660    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
2661    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2662    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2663    must not be NULL.  */
2664
2665 static void
2666 register_new_assert_for (tree name,
2667                          enum tree_code comp_code,
2668                          tree val,
2669                          basic_block bb,
2670                          edge e,
2671                          block_stmt_iterator si)
2672 {
2673   assert_locus_t n, loc, last_loc;
2674   bool found;
2675   basic_block dest_bb;
2676
2677 #if defined ENABLE_CHECKING
2678   gcc_assert (bb == NULL || e == NULL);
2679
2680   if (e == NULL)
2681     gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2682                 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2683 #endif
2684
2685   /* The new assertion A will be inserted at BB or E.  We need to
2686      determine if the new location is dominated by a previously
2687      registered location for A.  If we are doing an edge insertion,
2688      assume that A will be inserted at E->DEST.  Note that this is not
2689      necessarily true.
2690
2691      If E is a critical edge, it will be split.  But even if E is
2692      split, the new block will dominate the same set of blocks that
2693      E->DEST dominates.
2694
2695      The reverse, however, is not true, blocks dominated by E->DEST
2696      will not be dominated by the new block created to split E.  So,
2697      if the insertion location is on a critical edge, we will not use
2698      the new location to move another assertion previously registered
2699      at a block dominated by E->DEST.  */
2700   dest_bb = (bb) ? bb : e->dest;
2701
2702   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2703      VAL at a block dominating DEST_BB, then we don't need to insert a new
2704      one.  Similarly, if the same assertion already exists at a block
2705      dominated by DEST_BB and the new location is not on a critical
2706      edge, then update the existing location for the assertion (i.e.,
2707      move the assertion up in the dominance tree).
2708
2709      Note, this is implemented as a simple linked list because there
2710      should not be more than a handful of assertions registered per
2711      name.  If this becomes a performance problem, a table hashed by
2712      COMP_CODE and VAL could be implemented.  */
2713   loc = asserts_for[SSA_NAME_VERSION (name)];
2714   last_loc = loc;
2715   found = false;
2716   while (loc)
2717     {
2718       if (loc->comp_code == comp_code
2719           && (loc->val == val
2720               || operand_equal_p (loc->val, val, 0)))
2721         {
2722           /* If the assertion NAME COMP_CODE VAL has already been
2723              registered at a basic block that dominates DEST_BB, then
2724              we don't need to insert the same assertion again.  Note
2725              that we don't check strict dominance here to avoid
2726              replicating the same assertion inside the same basic
2727              block more than once (e.g., when a pointer is
2728              dereferenced several times inside a block).
2729
2730              An exception to this rule are edge insertions.  If the
2731              new assertion is to be inserted on edge E, then it will
2732              dominate all the other insertions that we may want to
2733              insert in DEST_BB.  So, if we are doing an edge
2734              insertion, don't do this dominance check.  */
2735           if (e == NULL
2736               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2737             return;
2738
2739           /* Otherwise, if E is not a critical edge and DEST_BB
2740              dominates the existing location for the assertion, move
2741              the assertion up in the dominance tree by updating its
2742              location information.  */
2743           if ((e == NULL || !EDGE_CRITICAL_P (e))
2744               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2745             {
2746               loc->bb = dest_bb;
2747               loc->e = e;
2748               loc->si = si;
2749               return;
2750             }
2751         }
2752
2753       /* Update the last node of the list and move to the next one.  */
2754       last_loc = loc;
2755       loc = loc->next;
2756     }
2757
2758   /* If we didn't find an assertion already registered for
2759      NAME COMP_CODE VAL, add a new one at the end of the list of
2760      assertions associated with NAME.  */
2761   n = XNEW (struct assert_locus_d);
2762   n->bb = dest_bb;
2763   n->e = e;
2764   n->si = si;
2765   n->comp_code = comp_code;
2766   n->val = val;
2767   n->next = NULL;
2768
2769   if (last_loc)
2770     last_loc->next = n;
2771   else
2772     asserts_for[SSA_NAME_VERSION (name)] = n;
2773
2774   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2775 }
2776
2777
2778 /* Try to register an edge assertion for SSA name NAME on edge E for
2779    the conditional jump pointed to by SI.  Return true if an assertion
2780    for NAME could be registered.  */
2781
2782 static bool
2783 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2784 {
2785   tree val, stmt;
2786   enum tree_code comp_code;
2787
2788   stmt = bsi_stmt (si);
2789
2790   /* Do not attempt to infer anything in names that flow through
2791      abnormal edges.  */
2792   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2793     return false;
2794
2795   /* If NAME was not found in the sub-graph reachable from E, then
2796      there's nothing to do.  */
2797   if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2798     return false;
2799
2800   /* We found a use of NAME in the sub-graph rooted at E->DEST.
2801      Register an assertion for NAME according to the value that NAME
2802      takes on edge E.  */
2803   if (TREE_CODE (stmt) == COND_EXPR)
2804     {
2805       /* If BB ends in a COND_EXPR then NAME then we should insert
2806          the original predicate on EDGE_TRUE_VALUE and the
2807          opposite predicate on EDGE_FALSE_VALUE.  */
2808       tree cond = COND_EXPR_COND (stmt);
2809       bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2810
2811       /* Predicates may be a single SSA name or NAME OP VAL.  */
2812       if (cond == name)
2813         {
2814           /* If the predicate is a name, it must be NAME, in which
2815              case we create the predicate NAME == true or
2816              NAME == false accordingly.  */
2817           comp_code = EQ_EXPR;
2818           val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2819         }
2820       else
2821         {
2822           /* Otherwise, we have a comparison of the form NAME COMP VAL
2823              or VAL COMP NAME.  */
2824           if (name == TREE_OPERAND (cond, 1))
2825             {
2826               /* If the predicate is of the form VAL COMP NAME, flip
2827                  COMP around because we need to register NAME as the
2828                  first operand in the predicate.  */
2829               comp_code = swap_tree_comparison (TREE_CODE (cond));
2830               val = TREE_OPERAND (cond, 0);
2831             }
2832           else
2833             {
2834               /* The comparison is of the form NAME COMP VAL, so the
2835                  comparison code remains unchanged.  */
2836               comp_code = TREE_CODE (cond);
2837               val = TREE_OPERAND (cond, 1);
2838             }
2839
2840           /* If we are inserting the assertion on the ELSE edge, we
2841              need to invert the sign comparison.  */
2842           if (is_else_edge)
2843             comp_code = invert_tree_comparison (comp_code, 0);
2844
2845           /* Do not register always-false predicates.  FIXME, this
2846              works around a limitation in fold() when dealing with
2847              enumerations.  Given 'enum { N1, N2 } x;', fold will not
2848              fold 'if (x > N2)' to 'if (0)'.  */
2849           if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
2850               && (INTEGRAL_TYPE_P (TREE_TYPE (val))
2851                   || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
2852             {
2853               tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
2854               tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
2855
2856               if (comp_code == GT_EXPR && compare_values (val, max) == 0)
2857                 return false;
2858
2859               if (comp_code == LT_EXPR && compare_values (val, min) == 0)
2860                 return false;
2861             }
2862         }
2863     }
2864   else
2865     {
2866       /* FIXME.  Handle SWITCH_EXPR.  */
2867       gcc_unreachable ();
2868     }
2869
2870   register_new_assert_for (name, comp_code, val, NULL, e, si);
2871   return true;
2872 }
2873
2874
2875 static bool find_assert_locations (basic_block bb);
2876
2877 /* Determine whether the outgoing edges of BB should receive an
2878    ASSERT_EXPR for each of the operands of BB's last statement.  The
2879    last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2880
2881    If any of the sub-graphs rooted at BB have an interesting use of
2882    the predicate operands, an assert location node is added to the
2883    list of assertions for the corresponding operands.  */
2884
2885 static bool
2886 find_conditional_asserts (basic_block bb)
2887 {
2888   bool need_assert;
2889   block_stmt_iterator last_si;
2890   tree op, last;
2891   edge_iterator ei;
2892   edge e;
2893   ssa_op_iter iter;
2894
2895   need_assert = false;
2896   last_si = bsi_last (bb);
2897   last = bsi_stmt (last_si);
2898
2899   /* Look for uses of the operands in each of the sub-graphs
2900      rooted at BB.  We need to check each of the outgoing edges
2901      separately, so that we know what kind of ASSERT_EXPR to
2902      insert.  */
2903   FOR_EACH_EDGE (e, ei, bb->succs)
2904     {
2905       if (e->dest == bb)
2906         continue;
2907
2908       /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2909          Otherwise, when we finish traversing each of the sub-graphs, we
2910          won't know whether the variables were found in the sub-graphs or
2911          if they had been found in a block upstream from BB.
2912
2913          This is actually a bad idea is some cases, particularly jump
2914          threading.  Consider a CFG like the following:
2915
2916                     0
2917                    /|
2918                   1 |
2919                    \|
2920                     2
2921                    / \
2922                   3   4
2923
2924          Assume that one or more operands in the conditional at the
2925          end of block 0 are used in a conditional in block 2, but not
2926          anywhere in block 1.  In this case we will not insert any
2927          assert statements in block 1, which may cause us to miss
2928          opportunities to optimize, particularly for jump threading.  */
2929       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2930         RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2931
2932       /* Traverse the strictly dominated sub-graph rooted at E->DEST
2933          to determine if any of the operands in the conditional
2934          predicate are used.  */
2935       if (e->dest != bb)
2936         need_assert |= find_assert_locations (e->dest);
2937
2938       /* Register the necessary assertions for each operand in the
2939          conditional predicate.  */
2940       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2941         need_assert |= register_edge_assert_for (op, e, last_si);
2942     }
2943
2944   /* Finally, indicate that we have found the operands in the
2945      conditional.  */
2946   FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2947     SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2948
2949   return need_assert;
2950 }
2951
2952
2953 /* Traverse all the statements in block BB looking for statements that
2954    may generate useful assertions for the SSA names in their operand.
2955    If a statement produces a useful assertion A for name N_i, then the
2956    list of assertions already generated for N_i is scanned to
2957    determine if A is actually needed.
2958
2959    If N_i already had the assertion A at a location dominating the
2960    current location, then nothing needs to be done.  Otherwise, the
2961    new location for A is recorded instead.
2962
2963    1- For every statement S in BB, all the variables used by S are
2964       added to bitmap FOUND_IN_SUBGRAPH.
2965
2966    2- If statement S uses an operand N in a way that exposes a known
2967       value range for N, then if N was not already generated by an
2968       ASSERT_EXPR, create a new assert location for N.  For instance,
2969       if N is a pointer and the statement dereferences it, we can
2970       assume that N is not NULL.
2971
2972    3- COND_EXPRs are a special case of #2.  We can derive range
2973       information from the predicate but need to insert different
2974       ASSERT_EXPRs for each of the sub-graphs rooted at the
2975       conditional block.  If the last statement of BB is a conditional
2976       expression of the form 'X op Y', then
2977
2978       a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2979
2980       b) If the conditional is the only entry point to the sub-graph
2981          corresponding to the THEN_CLAUSE, recurse into it.  On
2982          return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2983          an ASSERT_EXPR is added for the corresponding variable.
2984
2985       c) Repeat step (b) on the ELSE_CLAUSE.
2986
2987       d) Mark X and Y in FOUND_IN_SUBGRAPH.
2988
2989       For instance,
2990
2991             if (a == 9)
2992               b = a;
2993             else
2994               b = c + 1;
2995
2996       In this case, an assertion on the THEN clause is useful to
2997       determine that 'a' is always 9 on that edge.  However, an assertion
2998       on the ELSE clause would be unnecessary.
2999
3000    4- If BB does not end in a conditional expression, then we recurse
3001       into BB's dominator children.
3002
3003    At the end of the recursive traversal, every SSA name will have a
3004    list of locations where ASSERT_EXPRs should be added.  When a new
3005    location for name N is found, it is registered by calling
3006    register_new_assert_for.  That function keeps track of all the
3007    registered assertions to prevent adding unnecessary assertions.
3008    For instance, if a pointer P_4 is dereferenced more than once in a
3009    dominator tree, only the location dominating all the dereference of
3010    P_4 will receive an ASSERT_EXPR.
3011
3012    If this function returns true, then it means that there are names
3013    for which we need to generate ASSERT_EXPRs.  Those assertions are
3014    inserted by process_assert_insertions.
3015
3016    TODO.  Handle SWITCH_EXPR.  */
3017
3018 static bool
3019 find_assert_locations (basic_block bb)
3020 {
3021   block_stmt_iterator si;
3022   tree last, phi;
3023   bool need_assert;
3024   basic_block son;
3025
3026   if (TEST_BIT (blocks_visited, bb->index))
3027     return false;
3028
3029   SET_BIT (blocks_visited, bb->index);
3030
3031   need_assert = false;
3032
3033   /* Traverse all PHI nodes in BB marking used operands.  */
3034   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3035     {
3036       use_operand_p arg_p;
3037       ssa_op_iter i;
3038
3039       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
3040         {
3041           tree arg = USE_FROM_PTR (arg_p);
3042           if (TREE_CODE (arg) == SSA_NAME)
3043             {
3044               gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
3045               SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
3046             }
3047         }
3048     }
3049
3050   /* Traverse all the statements in BB marking used names and looking
3051      for statements that may infer assertions for their used operands.  */
3052   last = NULL_TREE;
3053   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3054     {
3055       tree stmt, op;
3056       ssa_op_iter i;
3057
3058       stmt = bsi_stmt (si);
3059
3060       /* See if we can derive an assertion for any of STMT's operands.  */
3061       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
3062         {
3063           tree value;
3064           enum tree_code comp_code;
3065
3066           /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
3067              the sub-graph of a conditional block, when we return from
3068              this recursive walk, our parent will use the
3069              FOUND_IN_SUBGRAPH bitset to determine if one of the
3070              operands it was looking for was present in the sub-graph.  */
3071           SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
3072
3073           /* If OP is used in such a way that we can infer a value
3074              range for it, and we don't find a previous assertion for
3075              it, create a new assertion location node for OP.  */
3076           if (infer_value_range (stmt, op, &comp_code, &value))
3077             {
3078               /* If we are able to infer a nonzero value range for OP,
3079                  then walk backwards through the use-def chain to see if OP
3080                  was set via a typecast.
3081
3082                  If so, then we can also infer a nonzero value range
3083                  for the operand of the NOP_EXPR.  */
3084               if (comp_code == NE_EXPR && integer_zerop (value))
3085                 {
3086                   tree t = op;
3087                   tree def_stmt = SSA_NAME_DEF_STMT (t);
3088
3089                   while (TREE_CODE (def_stmt) == MODIFY_EXPR
3090                          && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR
3091                          && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME
3092                          && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))))
3093                     {
3094                       t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
3095                       def_stmt = SSA_NAME_DEF_STMT (t);
3096
3097                       /* Note we want to register the assert for the
3098                          operand of the NOP_EXPR after SI, not after the
3099                          conversion.  */
3100                       if (! has_single_use (t))
3101                         {
3102                           register_new_assert_for (t, comp_code, value,
3103                                                    bb, NULL, si);
3104                           need_assert = true;
3105                         }
3106                     }
3107                 }
3108
3109               /* If OP is used only once, namely in this STMT, don't
3110                  bother creating an ASSERT_EXPR for it.  Such an
3111                  ASSERT_EXPR would do nothing but increase compile time.  */
3112               if (!has_single_use (op))
3113                 {
3114                   register_new_assert_for (op, comp_code, value, bb, NULL, si);
3115                   need_assert = true;
3116                 }
3117             }
3118         }
3119
3120       /* Remember the last statement of the block.  */
3121       last = stmt;
3122     }
3123
3124   /* If BB's last statement is a conditional expression
3125      involving integer operands, recurse into each of the sub-graphs
3126      rooted at BB to determine if we need to add ASSERT_EXPRs.  */
3127   if (last
3128       && TREE_CODE (last) == COND_EXPR
3129       && !fp_predicate (COND_EXPR_COND (last))
3130       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
3131     need_assert |= find_conditional_asserts (bb);
3132
3133   /* Recurse into the dominator children of BB.  */
3134   for (son = first_dom_son (CDI_DOMINATORS, bb);
3135        son;
3136        son = next_dom_son (CDI_DOMINATORS, son))
3137     need_assert |= find_assert_locations (son);
3138
3139   return need_assert;
3140 }
3141
3142
3143 /* Create an ASSERT_EXPR for NAME and insert it in the location
3144    indicated by LOC.  Return true if we made any edge insertions.  */
3145
3146 static bool
3147 process_assert_insertions_for (tree name, assert_locus_t loc)
3148 {
3149   /* Build the comparison expression NAME_i COMP_CODE VAL.  */
3150   tree stmt, cond, assert_expr;
3151   edge_iterator ei;
3152   edge e;
3153
3154   cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
3155   assert_expr = build_assert_expr_for (cond, name);
3156
3157   if (loc->e)
3158     {
3159       /* We have been asked to insert the assertion on an edge.  This
3160          is used only by COND_EXPR and SWITCH_EXPR assertions.  */
3161 #if defined ENABLE_CHECKING
3162       gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
3163           || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
3164 #endif
3165
3166       bsi_insert_on_edge (loc->e, assert_expr);
3167       return true;
3168     }
3169
3170   /* Otherwise, we can insert right after LOC->SI iff the
3171      statement must not be the last statement in the block.  */
3172   stmt = bsi_stmt (loc->si);
3173   if (!stmt_ends_bb_p (stmt))
3174     {
3175       bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
3176       return false;
3177     }
3178
3179   /* If STMT must be the last statement in BB, we can only insert new
3180      assertions on the non-abnormal edge out of BB.  Note that since
3181      STMT is not control flow, there may only be one non-abnormal edge
3182      out of BB.  */
3183   FOR_EACH_EDGE (e, ei, loc->bb->succs)
3184     if (!(e->flags & EDGE_ABNORMAL))
3185       {
3186         bsi_insert_on_edge (e, assert_expr);
3187         return true;
3188       }
3189
3190   gcc_unreachable ();
3191 }
3192
3193
3194 /* Process all the insertions registered for every name N_i registered
3195    in NEED_ASSERT_FOR.  The list of assertions to be inserted are
3196    found in ASSERTS_FOR[i].  */
3197
3198 static void
3199 process_assert_insertions (void)
3200 {
3201   unsigned i;
3202   bitmap_iterator bi;
3203   bool update_edges_p = false;
3204   int num_asserts = 0;
3205
3206   if (dump_file && (dump_flags & TDF_DETAILS))
3207     dump_all_asserts (dump_file);
3208
3209   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3210     {
3211       assert_locus_t loc = asserts_for[i];
3212       gcc_assert (loc);
3213
3214       while (loc)
3215         {
3216           assert_locus_t next = loc->next;
3217           update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
3218           free (loc);
3219           loc = next;
3220           num_asserts++;
3221         }
3222     }
3223
3224   if (update_edges_p)
3225     bsi_commit_edge_inserts ();
3226
3227   if (dump_file && (dump_flags & TDF_STATS))
3228     fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
3229              num_asserts);
3230 }
3231
3232
3233 /* Traverse the flowgraph looking for conditional jumps to insert range
3234    expressions.  These range expressions are meant to provide information
3235    to optimizations that need to reason in terms of value ranges.  They
3236    will not be expanded into RTL.  For instance, given:
3237
3238    x = ...
3239    y = ...
3240    if (x < y)
3241      y = x - 2;
3242    else
3243      x = y + 3;
3244
3245    this pass will transform the code into:
3246
3247    x = ...
3248    y = ...
3249    if (x < y)
3250     {
3251       x = ASSERT_EXPR <x, x < y>
3252       y = x - 2
3253     }
3254    else
3255     {
3256       y = ASSERT_EXPR <y, x <= y>
3257       x = y + 3
3258     }
3259
3260    The idea is that once copy and constant propagation have run, other
3261    optimizations will be able to determine what ranges of values can 'x'
3262    take in different paths of the code, simply by checking the reaching
3263    definition of 'x'.  */
3264
3265 static void
3266 insert_range_assertions (void)
3267 {
3268   edge e;
3269   edge_iterator ei;
3270   bool update_ssa_p;
3271
3272   found_in_subgraph = sbitmap_alloc (num_ssa_names);
3273   sbitmap_zero (found_in_subgraph);
3274
3275   blocks_visited = sbitmap_alloc (last_basic_block);
3276   sbitmap_zero (blocks_visited);
3277
3278   need_assert_for = BITMAP_ALLOC (NULL);
3279   asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
3280   memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
3281
3282   calculate_dominance_info (CDI_DOMINATORS);
3283
3284   update_ssa_p = false;
3285   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3286     if (find_assert_locations (e->dest))
3287       update_ssa_p = true;
3288
3289   if (update_ssa_p)
3290     {
3291       process_assert_insertions ();
3292       update_ssa (TODO_update_ssa_no_phi);
3293     }
3294
3295   if (dump_file && (dump_flags & TDF_DETAILS))
3296     {
3297       fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
3298       dump_function_to_file (current_function_decl, dump_file, dump_flags);
3299     }
3300
3301   sbitmap_free (found_in_subgraph);
3302   free (asserts_for);
3303   BITMAP_FREE (need_assert_for);
3304 }
3305
3306
3307 /* Convert range assertion expressions into the implied copies and
3308    copy propagate away the copies.  Doing the trivial copy propagation
3309    here avoids the need to run the full copy propagation pass after
3310    VRP.
3311
3312    FIXME, this will eventually lead to copy propagation removing the
3313    names that had useful range information attached to them.  For
3314    instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
3315    then N_i will have the range [3, +INF].
3316
3317    However, by converting the assertion into the implied copy
3318    operation N_i = N_j, we will then copy-propagate N_j into the uses
3319    of N_i and lose the range information.  We may want to hold on to
3320    ASSERT_EXPRs a little while longer as the ranges could be used in
3321    things like jump threading.
3322
3323    The problem with keeping ASSERT_EXPRs around is that passes after
3324    VRP need to handle them appropriately.
3325
3326    Another approach would be to make the range information a first
3327    class property of the SSA_NAME so that it can be queried from
3328    any pass.  This is made somewhat more complex by the need for
3329    multiple ranges to be associated with one SSA_NAME.  */
3330
3331 static void
3332 remove_range_assertions (void)
3333 {
3334   basic_block bb;
3335   block_stmt_iterator si;
3336
3337   /* Note that the BSI iterator bump happens at the bottom of the
3338      loop and no bump is necessary if we're removing the statement
3339      referenced by the current BSI.  */
3340   FOR_EACH_BB (bb)
3341     for (si = bsi_start (bb); !bsi_end_p (si);)
3342       {
3343         tree stmt = bsi_stmt (si);
3344         tree use_stmt;
3345
3346         if (TREE_CODE (stmt) == MODIFY_EXPR
3347             && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
3348           {
3349             tree rhs = TREE_OPERAND (stmt, 1), var;
3350             tree cond = fold (ASSERT_EXPR_COND (rhs));
3351             use_operand_p use_p;
3352             imm_use_iterator iter;
3353
3354             gcc_assert (cond != boolean_false_node);
3355
3356             /* Propagate the RHS into every use of the LHS.  */
3357             var = ASSERT_EXPR_VAR (rhs);
3358             FOR_EACH_IMM_USE_STMT (use_stmt, iter, TREE_OPERAND (stmt, 0))
3359               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3360                 {
3361                   SET_USE (use_p, var);
3362                   gcc_assert (TREE_CODE (var) == SSA_NAME);
3363                 }
3364
3365             /* And finally, remove the copy, it is not needed.  */
3366             bsi_remove (&si, true);
3367           }
3368         else
3369           bsi_next (&si);
3370       }
3371
3372   sbitmap_free (blocks_visited);
3373 }
3374
3375
3376 /* Return true if STMT is interesting for VRP.  */
3377
3378 static bool
3379 stmt_interesting_for_vrp (tree stmt)
3380 {
3381   if (TREE_CODE (stmt) == PHI_NODE
3382       && is_gimple_reg (PHI_RESULT (stmt))
3383       && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
3384           || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
3385     return true;
3386   else if (TREE_CODE (stmt) == MODIFY_EXPR)
3387     {
3388       tree lhs = TREE_OPERAND (stmt, 0);
3389       tree rhs = TREE_OPERAND (stmt, 1);
3390
3391       /* In general, assignments with virtual operands are not useful
3392          for deriving ranges, with the obvious exception of calls to
3393          builtin functions.  */
3394       if (TREE_CODE (lhs) == SSA_NAME
3395           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3396               || POINTER_TYPE_P (TREE_TYPE (lhs)))
3397           && ((TREE_CODE (rhs) == CALL_EXPR
3398                && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
3399                && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
3400                && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
3401               || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
3402         return true;
3403     }
3404   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3405     return true;
3406
3407   return false;
3408 }
3409
3410
3411 /* Initialize local data structures for VRP.  */
3412
3413 static void
3414 vrp_initialize (void)
3415 {
3416   basic_block bb;
3417
3418   vr_value = XNEWVEC (value_range_t *, num_ssa_names);
3419   memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
3420
3421   FOR_EACH_BB (bb)
3422     {
3423       block_stmt_iterator si;
3424       tree phi;
3425
3426       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3427         {
3428           if (!stmt_interesting_for_vrp (phi))
3429             {
3430               tree lhs = PHI_RESULT (phi);
3431               set_value_range_to_varying (get_value_range (lhs));
3432               DONT_SIMULATE_AGAIN (phi) = true;
3433             }
3434           else
3435             DONT_SIMULATE_AGAIN (phi) = false;
3436         }
3437
3438       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3439         {
3440           tree stmt = bsi_stmt (si);
3441
3442           if (!stmt_interesting_for_vrp (stmt))
3443             {
3444               ssa_op_iter i;
3445               tree def;
3446               FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
3447                 set_value_range_to_varying (get_value_range (def));
3448               DONT_SIMULATE_AGAIN (stmt) = true;
3449             }
3450           else
3451             {
3452               DONT_SIMULATE_AGAIN (stmt) = false;
3453             }
3454         }
3455     }
3456 }
3457
3458
3459 /* Visit assignment STMT.  If it produces an interesting range, record
3460    the SSA name in *OUTPUT_P.  */
3461
3462 static enum ssa_prop_result
3463 vrp_visit_assignment (tree stmt, tree *output_p)
3464 {
3465   tree lhs, rhs, def;
3466   ssa_op_iter iter;
3467
3468   lhs = TREE_OPERAND (stmt, 0);
3469   rhs = TREE_OPERAND (stmt, 1);
3470
3471   /* We only keep track of ranges in integral and pointer types.  */
3472   if (TREE_CODE (lhs) == SSA_NAME
3473       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3474            /* It is valid to have NULL MIN/MAX values on a type.  See
3475               build_range_type.  */
3476            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
3477            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
3478           || POINTER_TYPE_P (TREE_TYPE (lhs))))
3479     {
3480       struct loop *l;
3481       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3482
3483       extract_range_from_expr (&new_vr, rhs);
3484
3485       /* If STMT is inside a loop, we may be able to know something
3486          else about the range of LHS by examining scalar evolution
3487          information.  */
3488       if (current_loops && (l = loop_containing_stmt (stmt)))
3489         adjust_range_with_scev (&new_vr, l, stmt, lhs);
3490
3491       if (update_value_range (lhs, &new_vr))
3492         {
3493           *output_p = lhs;
3494
3495           if (dump_file && (dump_flags & TDF_DETAILS))
3496             {
3497               fprintf (dump_file, "Found new range for ");
3498               print_generic_expr (dump_file, lhs, 0);
3499               fprintf (dump_file, ": ");
3500               dump_value_range (dump_file, &new_vr);
3501               fprintf (dump_file, "\n\n");
3502             }
3503
3504           if (new_vr.type == VR_VARYING)
3505             return SSA_PROP_VARYING;
3506
3507           return SSA_PROP_INTERESTING;
3508         }
3509
3510       return SSA_PROP_NOT_INTERESTING;
3511     }
3512
3513   /* Every other statement produces no useful ranges.  */
3514   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3515     set_value_range_to_varying (get_value_range (def));
3516
3517   return SSA_PROP_VARYING;
3518 }
3519
3520
3521 /* Compare all the value ranges for names equivalent to VAR with VAL
3522    using comparison code COMP.  Return the same value returned by
3523    compare_range_with_value.  */
3524
3525 static tree
3526 compare_name_with_value (enum tree_code comp, tree var, tree val)
3527 {
3528   bitmap_iterator bi;
3529   unsigned i;
3530   bitmap e;
3531   tree retval, t;
3532
3533   t = retval = NULL_TREE;
3534
3535   /* Get the set of equivalences for VAR.  */
3536   e = get_value_range (var)->equiv;
3537
3538   /* Add VAR to its own set of equivalences so that VAR's value range
3539      is processed by this loop (otherwise, we would have to replicate
3540      the body of the loop just to check VAR's value range).  */
3541   bitmap_set_bit (e, SSA_NAME_VERSION (var));
3542
3543   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3544     {
3545       value_range_t equiv_vr = *(vr_value[i]);
3546
3547       /* If name N_i does not have a valid range, use N_i as its own
3548          range.  This allows us to compare against names that may
3549          have N_i in their ranges.  */
3550       if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3551         {
3552           equiv_vr.type = VR_RANGE;
3553           equiv_vr.min = ssa_name (i);
3554           equiv_vr.max = ssa_name (i);
3555         }
3556
3557       t = compare_range_with_value (comp, &equiv_vr, val);
3558       if (t)
3559         {
3560           /* All the ranges should compare the same against VAL.  */
3561           gcc_assert (retval == NULL || t == retval);
3562           retval = t;
3563         }
3564     }
3565
3566   /* Remove VAR from its own equivalence set.  */
3567   bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3568
3569   if (retval)
3570     return retval;
3571
3572   /* We couldn't find a non-NULL value for the predicate.  */
3573   return NULL_TREE;
3574 }
3575
3576
3577 /* Given a comparison code COMP and names N1 and N2, compare all the
3578    ranges equivalent to N1 against all the ranges equivalent to N2
3579    to determine the value of N1 COMP N2.  Return the same value
3580    returned by compare_ranges.  */
3581
3582 static tree
3583 compare_names (enum tree_code comp, tree n1, tree n2)
3584 {
3585   tree t, retval;
3586   bitmap e1, e2;
3587   bitmap_iterator bi1, bi2;
3588   unsigned i1, i2;
3589
3590   /* Compare the ranges of every name equivalent to N1 against the
3591      ranges of every name equivalent to N2.  */
3592   e1 = get_value_range (n1)->equiv;
3593   e2 = get_value_range (n2)->equiv;
3594
3595   /* Add N1 and N2 to their own set of equivalences to avoid
3596      duplicating the body of the loop just to check N1 and N2
3597      ranges.  */
3598   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3599   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3600
3601   /* If the equivalence sets have a common intersection, then the two
3602      names can be compared without checking their ranges.  */
3603   if (bitmap_intersect_p (e1, e2))
3604     {
3605       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3606       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3607
3608       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3609              ? boolean_true_node
3610              : boolean_false_node;
3611     }
3612
3613   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
3614      N2 to their own set of equivalences to avoid duplicating the body
3615      of the loop just to check N1 and N2 ranges.  */
3616   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3617     {
3618       value_range_t vr1 = *(vr_value[i1]);
3619
3620       /* If the range is VARYING or UNDEFINED, use the name itself.  */
3621       if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3622         {
3623           vr1.type = VR_RANGE;
3624           vr1.min = ssa_name (i1);
3625           vr1.max = ssa_name (i1);
3626         }
3627
3628       t = retval = NULL_TREE;
3629       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3630         {
3631           value_range_t vr2 = *(vr_value[i2]);
3632
3633           if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3634             {
3635               vr2.type = VR_RANGE;
3636               vr2.min = ssa_name (i2);
3637               vr2.max = ssa_name (i2);
3638             }
3639
3640           t = compare_ranges (comp, &vr1, &vr2);
3641           if (t)
3642             {
3643               /* All the ranges in the equivalent sets should compare
3644                  the same.  */
3645               gcc_assert (retval == NULL || t == retval);
3646               retval = t;
3647             }
3648         }
3649
3650       if (retval)
3651         {
3652           bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3653           bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3654           return retval;
3655         }
3656     }
3657
3658   /* None of the equivalent ranges are useful in computing this
3659      comparison.  */
3660   bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3661   bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3662   return NULL_TREE;
3663 }
3664
3665
3666 /* Given a conditional predicate COND, try to determine if COND yields
3667    true or false based on the value ranges of its operands.  Return
3668    BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
3669    BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
3670    NULL if the conditional cannot be evaluated at compile time.
3671
3672    If USE_EQUIV_P is true, the ranges of all the names equivalent with
3673    the operands in COND are used when trying to compute its value.
3674    This is only used during final substitution.  During propagation,
3675    we only check the range of each variable and not its equivalents.  */
3676
3677 tree
3678 vrp_evaluate_conditional (tree cond, bool use_equiv_p)
3679 {
3680   gcc_assert (TREE_CODE (cond) == SSA_NAME
3681               || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
3682
3683   if (TREE_CODE (cond) == SSA_NAME)
3684     {
3685       value_range_t *vr;
3686       tree retval;
3687
3688       if (use_equiv_p)
3689         retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node);
3690       else
3691         {
3692           value_range_t *vr = get_value_range (cond);
3693           retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node);
3694         }
3695
3696       /* If COND has a known boolean range, return it.  */
3697       if (retval)
3698         return retval;
3699
3700       /* Otherwise, if COND has a symbolic range of exactly one value,
3701          return it.  */
3702       vr = get_value_range (cond);
3703       if (vr->type == VR_RANGE && vr->min == vr->max)
3704         return vr->min;
3705     }
3706   else
3707     {
3708       tree op0 = TREE_OPERAND (cond, 0);
3709       tree op1 = TREE_OPERAND (cond, 1);
3710
3711       /* We only deal with integral and pointer types.  */
3712       if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3713           && !POINTER_TYPE_P (TREE_TYPE (op0)))
3714         return NULL_TREE;
3715
3716       if (use_equiv_p)
3717         {
3718           if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
3719             return compare_names (TREE_CODE (cond), op0, op1);
3720           else if (TREE_CODE (op0) == SSA_NAME)
3721             return compare_name_with_value (TREE_CODE (cond), op0, op1);
3722           else if (TREE_CODE (op1) == SSA_NAME)
3723             return compare_name_with_value (
3724                     swap_tree_comparison (TREE_CODE (cond)), op1, op0);
3725         }
3726       else
3727         {
3728           value_range_t *vr0, *vr1;
3729
3730           vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
3731           vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
3732
3733           if (vr0 && vr1)
3734             return compare_ranges (TREE_CODE (cond), vr0, vr1);
3735           else if (vr0 && vr1 == NULL)
3736             return compare_range_with_value (TREE_CODE (cond), vr0, op1);
3737           else if (vr0 == NULL && vr1)
3738             return compare_range_with_value (
3739                     swap_tree_comparison (TREE_CODE (cond)), vr1, op0);
3740         }
3741     }
3742
3743   /* Anything else cannot be computed statically.  */
3744   return NULL_TREE;
3745 }
3746
3747
3748 /* Visit conditional statement STMT.  If we can determine which edge
3749    will be taken out of STMT's basic block, record it in
3750    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
3751    SSA_PROP_VARYING.  */
3752
3753 static enum ssa_prop_result
3754 vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
3755 {
3756   tree cond, val;
3757
3758   *taken_edge_p = NULL;
3759
3760   /* FIXME.  Handle SWITCH_EXPRs.  But first, the assert pass needs to
3761      add ASSERT_EXPRs for them.  */
3762   if (TREE_CODE (stmt) == SWITCH_EXPR)
3763     return SSA_PROP_VARYING;
3764
3765   cond = COND_EXPR_COND (stmt);
3766
3767   if (dump_file && (dump_flags & TDF_DETAILS))
3768     {
3769       tree use;
3770       ssa_op_iter i;
3771
3772       fprintf (dump_file, "\nVisiting conditional with predicate: ");
3773       print_generic_expr (dump_file, cond, 0);
3774       fprintf (dump_file, "\nWith known ranges\n");
3775
3776       FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
3777         {
3778           fprintf (dump_file, "\t");
3779           print_generic_expr (dump_file, use, 0);
3780           fprintf (dump_file, ": ");
3781           dump_value_range (dump_file, vr_value[SSA_NAME_VERSION (use)]);
3782         }
3783
3784       fprintf (dump_file, "\n");
3785     }
3786
3787   /* Compute the value of the predicate COND by checking the known
3788      ranges of each of its operands.
3789
3790      Note that we cannot evaluate all the equivalent ranges here
3791      because those ranges may not yet be final and with the current
3792      propagation strategy, we cannot determine when the value ranges
3793      of the names in the equivalence set have changed.
3794
3795      For instance, given the following code fragment
3796
3797         i_5 = PHI <8, i_13>
3798         ...
3799         i_14 = ASSERT_EXPR <i_5, i_5 != 0>
3800         if (i_14 == 1)
3801           ...
3802
3803      Assume that on the first visit to i_14, i_5 has the temporary
3804      range [8, 8] because the second argument to the PHI function is
3805      not yet executable.  We derive the range ~[0, 0] for i_14 and the
3806      equivalence set { i_5 }.  So, when we visit 'if (i_14 == 1)' for
3807      the first time, since i_14 is equivalent to the range [8, 8], we
3808      determine that the predicate is always false.
3809
3810      On the next round of propagation, i_13 is determined to be
3811      VARYING, which causes i_5 to drop down to VARYING.  So, another
3812      visit to i_14 is scheduled.  In this second visit, we compute the
3813      exact same range and equivalence set for i_14, namely ~[0, 0] and
3814      { i_5 }.  But we did not have the previous range for i_5
3815      registered, so vrp_visit_assignment thinks that the range for
3816      i_14 has not changed.  Therefore, the predicate 'if (i_14 == 1)'
3817      is not visited again, which stops propagation from visiting
3818      statements in the THEN clause of that if().
3819
3820      To properly fix this we would need to keep the previous range
3821      value for the names in the equivalence set.  This way we would've
3822      discovered that from one visit to the other i_5 changed from
3823      range [8, 8] to VR_VARYING.
3824
3825      However, fixing this apparent limitation may not be worth the
3826      additional checking.  Testing on several code bases (GCC, DLV,
3827      MICO, TRAMP3D and SPEC2000) showed that doing this results in
3828      4 more predicates folded in SPEC.  */
3829   val = vrp_evaluate_conditional (cond, false);
3830   if (val)
3831     *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
3832
3833   if (dump_file && (dump_flags & TDF_DETAILS))
3834     {
3835       fprintf (dump_file, "\nPredicate evaluates to: ");
3836       if (val == NULL_TREE)
3837         fprintf (dump_file, "DON'T KNOW\n");
3838       else
3839         print_generic_stmt (dump_file, val, 0);
3840     }
3841
3842   return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
3843 }
3844
3845
3846 /* Evaluate statement STMT.  If the statement produces a useful range,
3847    return SSA_PROP_INTERESTING and record the SSA name with the
3848    interesting range into *OUTPUT_P.
3849
3850    If STMT is a conditional branch and we can determine its truth
3851    value, the taken edge is recorded in *TAKEN_EDGE_P.
3852
3853    If STMT produces a varying value, return SSA_PROP_VARYING.  */
3854
3855 static enum ssa_prop_result
3856 vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
3857 {
3858   tree def;
3859   ssa_op_iter iter;
3860   stmt_ann_t ann;
3861
3862   if (dump_file && (dump_flags & TDF_DETAILS))
3863     {
3864       fprintf (dump_file, "\nVisiting statement:\n");
3865       print_generic_stmt (dump_file, stmt, dump_flags);
3866       fprintf (dump_file, "\n");
3867     }
3868
3869   ann = stmt_ann (stmt);
3870   if (TREE_CODE (stmt) == MODIFY_EXPR)
3871     {
3872       tree rhs = TREE_OPERAND (stmt, 1);
3873
3874       /* In general, assignments with virtual operands are not useful
3875          for deriving ranges, with the obvious exception of calls to
3876          builtin functions.  */
3877       if ((TREE_CODE (rhs) == CALL_EXPR
3878            && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
3879            && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
3880            && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
3881           || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3882         return vrp_visit_assignment (stmt, output_p);
3883     }
3884   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3885     return vrp_visit_cond_stmt (stmt, taken_edge_p);
3886
3887   /* All other statements produce nothing of interest for VRP, so mark
3888      their outputs varying and prevent further simulation.  */
3889   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3890     set_value_range_to_varying (get_value_range (def));
3891
3892   return SSA_PROP_VARYING;
3893 }
3894
3895
3896 /* Meet operation for value ranges.  Given two value ranges VR0 and
3897    VR1, store in VR0 the result of meeting VR0 and VR1.
3898
3899    The meeting rules are as follows:
3900
3901    1- If VR0 and VR1 have an empty intersection, set VR0 to VR_VARYING.
3902
3903    2- If VR0 and VR1 have a non-empty intersection, set VR0 to the
3904       union of VR0 and VR1.  */
3905
3906 static void
3907 vrp_meet (value_range_t *vr0, value_range_t *vr1)
3908 {
3909   if (vr0->type == VR_UNDEFINED)
3910     {
3911       copy_value_range (vr0, vr1);
3912       return;
3913     }
3914
3915   if (vr1->type == VR_UNDEFINED)
3916     {
3917       /* Nothing to do.  VR0 already has the resulting range.  */
3918       return;
3919     }
3920
3921   if (vr0->type == VR_VARYING)
3922     {
3923       /* Nothing to do.  VR0 already has the resulting range.  */
3924       return;
3925     }
3926
3927   if (vr1->type == VR_VARYING)
3928     {
3929       set_value_range_to_varying (vr0);
3930       return;
3931     }
3932
3933   if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
3934     {
3935       /* If VR0 and VR1 have a non-empty intersection, compute the
3936          union of both ranges.  */
3937       if (value_ranges_intersect_p (vr0, vr1))
3938         {
3939           int cmp;
3940           tree min, max;
3941
3942           /* The lower limit of the new range is the minimum of the
3943              two ranges.  If they cannot be compared, the result is
3944              VARYING.  */
3945           cmp = compare_values (vr0->min, vr1->min);
3946           if (cmp == 0 || cmp == 1)
3947             min = vr1->min;
3948           else if (cmp == -1)
3949             min = vr0->min;
3950           else
3951             {
3952               set_value_range_to_varying (vr0);
3953               return;
3954             }
3955
3956           /* Similarly, the upper limit of the new range is the
3957              maximum of the two ranges.  If they cannot be compared,
3958              the result is VARYING.  */
3959           cmp = compare_values (vr0->max, vr1->max);
3960           if (cmp == 0 || cmp == -1)
3961             max = vr1->max;
3962           else if (cmp == 1)
3963             max = vr0->max;
3964           else
3965             {
3966               set_value_range_to_varying (vr0);
3967               return;
3968             }
3969
3970           /* The resulting set of equivalences is the intersection of
3971              the two sets.  */
3972           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3973             bitmap_and_into (vr0->equiv, vr1->equiv);
3974           else if (vr0->equiv && !vr1->equiv)
3975             bitmap_clear (vr0->equiv);
3976
3977           set_value_range (vr0, vr0->type, min, max, vr0->equiv);
3978         }
3979       else
3980         goto no_meet;
3981     }
3982   else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
3983     {
3984       /* Two anti-ranges meet only if they are both identical.  */
3985       if (compare_values (vr0->min, vr1->min) == 0
3986           && compare_values (vr0->max, vr1->max) == 0
3987           && compare_values (vr0->min, vr0->max) == 0)
3988         {
3989           /* The resulting set of equivalences is the intersection of
3990              the two sets.  */
3991           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
3992             bitmap_and_into (vr0->equiv, vr1->equiv);
3993           else if (vr0->equiv && !vr1->equiv)
3994             bitmap_clear (vr0->equiv);
3995         }
3996       else
3997         goto no_meet;
3998     }
3999   else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
4000     {
4001       /* A numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4]
4002          meet only if the ranges have an empty intersection.  The
4003          result of the meet operation is the anti-range.  */
4004       if (!symbolic_range_p (vr0)
4005           && !symbolic_range_p (vr1)
4006           && !value_ranges_intersect_p (vr0, vr1))
4007         {
4008           /* Copy most of VR1 into VR0.  Don't copy VR1's equivalence
4009              set.  We need to compute the intersection of the two
4010              equivalence sets.  */
4011           if (vr1->type == VR_ANTI_RANGE)
4012             set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
4013
4014           /* The resulting set of equivalences is the intersection of
4015              the two sets.  */
4016           if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
4017             bitmap_and_into (vr0->equiv, vr1->equiv);
4018           else if (vr0->equiv && !vr1->equiv)
4019             bitmap_clear (vr0->equiv);
4020         }
4021       else
4022         goto no_meet;
4023     }
4024   else
4025     gcc_unreachable ();
4026
4027   return;
4028
4029 no_meet:
4030   /* The two range VR0 and VR1 do not meet.  Before giving up and
4031      setting the result to VARYING, see if we can at least derive a
4032      useful anti-range.  FIXME, all this nonsense about distinguishing
4033      anti-ranges from ranges is necessary because of the odd
4034      semantics of range_includes_zero_p and friends.  */
4035   if (!symbolic_range_p (vr0)
4036       && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
4037           || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
4038       && !symbolic_range_p (vr1)
4039       && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
4040           || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
4041     {
4042       set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
4043
4044       /* Since this meet operation did not result from the meeting of
4045          two equivalent names, VR0 cannot have any equivalences.  */
4046       if (vr0->equiv)
4047         bitmap_clear (vr0->equiv);
4048     }
4049   else
4050     set_value_range_to_varying (vr0);
4051 }
4052
4053
4054 /* Visit all arguments for PHI node PHI that flow through executable
4055    edges.  If a valid value range can be derived from all the incoming
4056    value ranges, set a new range for the LHS of PHI.  */
4057
4058 static enum ssa_prop_result
4059 vrp_visit_phi_node (tree phi)
4060 {
4061   int i;
4062   tree lhs = PHI_RESULT (phi);
4063   value_range_t *lhs_vr = get_value_range (lhs);
4064   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
4065
4066   copy_value_range (&vr_result, lhs_vr);
4067
4068   if (dump_file && (dump_flags & TDF_DETAILS))
4069     {
4070       fprintf (dump_file, "\nVisiting PHI node: ");
4071       print_generic_expr (dump_file, phi, dump_flags);
4072     }
4073
4074   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
4075     {
4076       edge e = PHI_ARG_EDGE (phi, i);
4077
4078       if (dump_file && (dump_flags & TDF_DETAILS))
4079         {
4080           fprintf (dump_file,
4081               "\n    Argument #%d (%d -> %d %sexecutable)\n",
4082               i, e->src->index, e->dest->index,
4083               (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
4084         }
4085
4086       if (e->flags & EDGE_EXECUTABLE)
4087         {
4088           tree arg = PHI_ARG_DEF (phi, i);
4089           value_range_t vr_arg;
4090
4091           if (TREE_CODE (arg) == SSA_NAME)
4092             vr_arg = *(get_value_range (arg));
4093           else
4094             {
4095               vr_arg.type = VR_RANGE;
4096               vr_arg.min = arg;
4097               vr_arg.max = arg;
4098               vr_arg.equiv = NULL;
4099             }
4100
4101           if (dump_file && (dump_flags & TDF_DETAILS))
4102             {
4103               fprintf (dump_file, "\t");
4104               print_generic_expr (dump_file, arg, dump_flags);
4105               fprintf (dump_file, "\n\tValue: ");
4106               dump_value_range (dump_file, &vr_arg);
4107               fprintf (dump_file, "\n");
4108             }
4109
4110           vrp_meet (&vr_result, &vr_arg);
4111
4112           if (vr_result.type == VR_VARYING)
4113             break;
4114         }
4115     }
4116
4117   if (vr_result.type == VR_VARYING)
4118     goto varying;
4119
4120   /* To prevent infinite iterations in the algorithm, derive ranges
4121      when the new value is slightly bigger or smaller than the
4122      previous one.  */
4123   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
4124     {
4125       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
4126         {
4127           int cmp_min = compare_values (lhs_vr->min, vr_result.min);
4128           int cmp_max = compare_values (lhs_vr->max, vr_result.max);
4129
4130           /* If the new minimum is smaller or larger than the previous
4131              one, go all the way to -INF.  In the first case, to avoid
4132              iterating millions of times to reach -INF, and in the
4133              other case to avoid infinite bouncing between different
4134              minimums.  */
4135           if (cmp_min > 0 || cmp_min < 0)
4136             vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
4137
4138           /* Similarly, if the new maximum is smaller or larger than
4139              the previous one, go all the way to +INF.  */
4140           if (cmp_max < 0 || cmp_max > 0)
4141             vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
4142
4143           /* If we ended up with a (-INF, +INF) range, set it to
4144              VARYING.  */
4145           if (vr_result.min == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))
4146               && vr_result.max == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)))
4147             goto varying;
4148         }
4149     }
4150
4151   /* If the new range is different than the previous value, keep
4152      iterating.  */
4153   if (update_value_range (lhs, &vr_result))
4154     return SSA_PROP_INTERESTING;
4155
4156   /* Nothing changed, don't add outgoing edges.  */
4157   return SSA_PROP_NOT_INTERESTING;
4158
4159   /* No match found.  Set the LHS to VARYING.  */
4160 varying:
4161   set_value_range_to_varying (lhs_vr);
4162   return SSA_PROP_VARYING;
4163 }
4164
4165 /* Simplify a division or modulo operator to a right shift or
4166    bitwise and if the first operand is unsigned or is greater
4167    than zero and the second operand is an exact power of two.  */
4168
4169 static void
4170 simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
4171 {
4172   tree val = NULL;
4173   tree op = TREE_OPERAND (rhs, 0);
4174   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
4175
4176   if (TYPE_UNSIGNED (TREE_TYPE (op)))
4177     {
4178       val = integer_one_node;
4179     }
4180   else
4181     {
4182       val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
4183     }
4184
4185   if (val && integer_onep (val))
4186     {
4187       tree t;
4188       tree op0 = TREE_OPERAND (rhs, 0);
4189       tree op1 = TREE_OPERAND (rhs, 1);
4190
4191       if (rhs_code == TRUNC_DIV_EXPR)
4192         {
4193           t = build_int_cst (NULL_TREE, tree_log2 (op1));
4194           t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
4195         }
4196       else
4197         {
4198           t = build_int_cst (TREE_TYPE (op1), 1);
4199           t = int_const_binop (MINUS_EXPR, op1, t, 0);
4200           t = fold_convert (TREE_TYPE (op0), t);
4201           t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
4202         }
4203
4204       TREE_OPERAND (stmt, 1) = t;
4205       update_stmt (stmt);
4206     }
4207 }
4208
4209 /* If the operand to an ABS_EXPR is >= 0, then eliminate the
4210    ABS_EXPR.  If the operand is <= 0, then simplify the
4211    ABS_EXPR into a NEGATE_EXPR.  */
4212
4213 static void
4214 simplify_abs_using_ranges (tree stmt, tree rhs)
4215 {
4216   tree val = NULL;
4217   tree op = TREE_OPERAND (rhs, 0);
4218   tree type = TREE_TYPE (op);
4219   value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
4220
4221   if (TYPE_UNSIGNED (type))
4222     {
4223       val = integer_zero_node;
4224     }
4225   else if (vr)
4226     {
4227       val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
4228       if (!val)
4229         {
4230           val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
4231
4232           if (val)
4233             {
4234               if (integer_zerop (val))
4235                 val = integer_one_node;
4236               else if (integer_onep (val))
4237                 val = integer_zero_node;
4238             }
4239         }
4240
4241       if (val
4242           && (integer_onep (val) || integer_zerop (val)))
4243         {
4244           tree t;
4245
4246           if (integer_onep (val))
4247             t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
4248           else
4249             t = op;
4250
4251           TREE_OPERAND (stmt, 1) = t;
4252           update_stmt (stmt);
4253         }
4254     }
4255 }
4256
4257 /* We are comparing trees OP0 and OP1 using COND_CODE.  OP0 has
4258    a known value range VR.
4259
4260    If there is one and only one value which will satisfy the
4261    conditional, then return that value.  Else return NULL.  */
4262
4263 static tree
4264 test_for_singularity (enum tree_code cond_code, tree op0,
4265                       tree op1, value_range_t *vr)
4266 {
4267   tree min = NULL;
4268   tree max = NULL;
4269
4270   /* Extract minimum/maximum values which satisfy the
4271      the conditional as it was written.  */
4272   if (cond_code == LE_EXPR || cond_code == LT_EXPR)
4273     {
4274       min = TYPE_MIN_VALUE (TREE_TYPE (op0));
4275
4276       max = op1;
4277       if (cond_code == LT_EXPR)
4278         {
4279           tree one = build_int_cst (TREE_TYPE (op0), 1);
4280           max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
4281         }
4282     }
4283   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
4284     {
4285       max = TYPE_MAX_VALUE (TREE_TYPE (op0));
4286
4287       min = op1;
4288       if (cond_code == GT_EXPR)
4289         {
4290           tree one = build_int_cst (TREE_TYPE (op0), 1);
4291           min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
4292         }
4293     }
4294
4295   /* Now refine the minimum and maximum values using any
4296      value range information we have for op0.  */
4297   if (min && max)
4298     {
4299       if (compare_values (vr->min, min) == -1)
4300         min = min;
4301       else
4302         min = vr->min;
4303       if (compare_values (vr->max, max) == 1)
4304         max = max;
4305       else
4306         max = vr->max;
4307
4308       /* If the new min/max values have converged to a single value,
4309          then there is only one value which can satisfy the condition,
4310          return that value.  */
4311       if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
4312         return min;
4313     }
4314   return NULL;
4315 }
4316
4317 /* Simplify a conditional using a relational operator to an equality
4318    test if the range information indicates only one value can satisfy
4319    the original conditional.  */
4320
4321 static void
4322 simplify_cond_using_ranges (tree stmt)
4323 {
4324   tree cond = COND_EXPR_COND (stmt);
4325   tree op0 = TREE_OPERAND (cond, 0);
4326   tree op1 = TREE_OPERAND (cond, 1);
4327   enum tree_code cond_code = TREE_CODE (cond);
4328
4329   if (cond_code != NE_EXPR
4330       && cond_code != EQ_EXPR
4331       && TREE_CODE (op0) == SSA_NAME
4332       && INTEGRAL_TYPE_P (TREE_TYPE (op0))
4333       && is_gimple_min_invariant (op1))
4334     {
4335       value_range_t *vr = get_value_range (op0);
4336
4337       /* If we have range information for OP0, then we might be
4338          able to simplify this conditional. */
4339       if (vr->type == VR_RANGE)
4340         {
4341           tree new = test_for_singularity (cond_code, op0, op1, vr);
4342
4343           if (new)
4344             {
4345               if (dump_file)
4346                 {
4347                   fprintf (dump_file, "Simplified relational ");
4348                   print_generic_expr (dump_file, cond, 0);
4349                   fprintf (dump_file, " into ");
4350                 }
4351
4352               COND_EXPR_COND (stmt)
4353                 = build2 (EQ_EXPR, boolean_type_node, op0, new);
4354               update_stmt (stmt);
4355
4356               if (dump_file)
4357                 {
4358                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4359                   fprintf (dump_file, "\n");
4360                 }
4361               return;
4362
4363             }
4364
4365           /* Try again after inverting the condition.  We only deal
4366              with integral types here, so no need to worry about
4367              issues with inverting FP comparisons.  */
4368           cond_code = invert_tree_comparison (cond_code, false);
4369           new = test_for_singularity (cond_code, op0, op1, vr);
4370
4371           if (new)
4372             {
4373               if (dump_file)
4374                 {
4375                   fprintf (dump_file, "Simplified relational ");
4376                   print_generic_expr (dump_file, cond, 0);
4377                   fprintf (dump_file, " into ");
4378                 }
4379
4380               COND_EXPR_COND (stmt)
4381                 = build2 (NE_EXPR, boolean_type_node, op0, new);
4382               update_stmt (stmt);
4383
4384               if (dump_file)
4385                 {
4386                   print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
4387                   fprintf (dump_file, "\n");
4388                 }
4389               return;
4390
4391             }
4392         }
4393     }
4394 }
4395
4396 /* Simplify STMT using ranges if possible.  */
4397
4398 void
4399 simplify_stmt_using_ranges (tree stmt)
4400 {
4401   if (TREE_CODE (stmt) == MODIFY_EXPR)
4402     {
4403       tree rhs = TREE_OPERAND (stmt, 1);
4404       enum tree_code rhs_code = TREE_CODE (rhs);
4405
4406       /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
4407          and BIT_AND_EXPR respectively if the first operand is greater
4408          than zero and the second operand is an exact power of two.  */
4409       if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
4410           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
4411           && integer_pow2p (TREE_OPERAND (rhs, 1)))
4412         simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
4413
4414       /* Transform ABS (X) into X or -X as appropriate.  */
4415       if (rhs_code == ABS_EXPR
4416           && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
4417           && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
4418         simplify_abs_using_ranges (stmt, rhs);
4419     }
4420   else if (TREE_CODE (stmt) == COND_EXPR
4421            && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
4422     {
4423       simplify_cond_using_ranges (stmt);
4424     }
4425 }
4426
4427 /* Stack of dest,src equivalency pairs that need to be restored after
4428    each attempt to thread a block's incoming edge to an outgoing edge.
4429
4430    A NULL entry is used to mark the end of pairs which need to be
4431    restored.  */
4432 static VEC(tree,heap) *stack;
4433
4434 /* A trivial wrapper so that we can present the generic jump
4435    threading code with a simple API for simplifying statements.  */
4436 static tree
4437 simplify_stmt_for_jump_threading (tree stmt)
4438 {
4439   /* We only use VRP information to simplify conditionals.  This is
4440      overly conservative, but it's unclear if doing more would be
4441      worth the compile time cost.  */
4442   if (TREE_CODE (stmt) != COND_EXPR)
4443     return NULL;
4444
4445   return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true);
4446 }
4447
4448 /* Blocks which have more than one predecessor and more than
4449    one successor present jump threading opportunities.  ie,
4450    when the block is reached from a specific predecessor, we
4451    may be able to determine which of the outgoing edges will
4452    be traversed.  When this optimization applies, we are able
4453    to avoid conditionals at runtime and we may expose secondary
4454    optimization opportunities.
4455
4456    This routine is effectively a driver for the generic jump
4457    threading code.  It basically just presents the generic code
4458    with edges that may be suitable for jump threading.
4459
4460    Unlike DOM, we do not iterate VRP if jump threading was successful.
4461    While iterating may expose new opportunities for VRP, it is expected
4462    those opportunities would be very limited and the compile time cost
4463    to expose those opportunities would be significant.
4464
4465    As jump threading opportunities are discovered, they are registered
4466    for later realization.  */
4467
4468 static void
4469 identify_jump_threads (void)
4470 {
4471   basic_block bb;
4472   tree dummy;
4473
4474   /* Ugh.  When substituting values earlier in this pass we can
4475      wipe the dominance information.  So rebuild the dominator
4476      information as we need it within the jump threading code.  */
4477   calculate_dominance_info (CDI_DOMINATORS);
4478
4479   /* We do not allow VRP information to be used for jump threading
4480      across a back edge in the CFG.  Otherwise it becomes too
4481      difficult to avoid eliminating loop exit tests.  Of course
4482      EDGE_DFS_BACK is not accurate at this time so we have to
4483      recompute it.  */
4484   mark_dfs_back_edges ();
4485
4486   /* Allocate our unwinder stack to unwind any temporary equivalences
4487      that might be recorded.  */
4488   stack = VEC_alloc (tree, heap, 20);
4489
4490   /* To avoid lots of silly node creation, we create a single
4491      conditional and just modify it in-place when attempting to
4492      thread jumps.  */
4493   dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
4494   dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
4495
4496   /* Walk through all the blocks finding those which present a
4497      potential jump threading opportunity.  We could set this up
4498      as a dominator walker and record data during the walk, but
4499      I doubt it's worth the effort for the classes of jump
4500      threading opportunities we are trying to identify at this
4501      point in compilation.  */
4502   FOR_EACH_BB (bb)
4503     {
4504       tree last, cond;
4505
4506       /* If the generic jump threading code does not find this block
4507          interesting, then there is nothing to do.  */
4508       if (! potentially_threadable_block (bb))
4509         continue;
4510
4511       /* We only care about blocks ending in a COND_EXPR.  While there
4512          may be some value in handling SWITCH_EXPR here, I doubt it's
4513          terribly important.  */
4514       last = bsi_stmt (bsi_last (bb));
4515       if (TREE_CODE (last) != COND_EXPR)
4516         continue;
4517
4518       /* We're basically looking for any kind of conditional with
4519          integral type arguments.  */
4520       cond = COND_EXPR_COND (last);
4521       if ((TREE_CODE (cond) == SSA_NAME
4522            && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
4523           || (COMPARISON_CLASS_P (cond)
4524               && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
4525               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
4526               && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
4527                   || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
4528               && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
4529         {
4530           edge_iterator ei;
4531           edge e;
4532
4533           /* We've got a block with multiple predecessors and multiple
4534              successors which also ends in a suitable conditional.  For
4535              each predecessor, see if we can thread it to a specific
4536              successor.  */
4537           FOR_EACH_EDGE (e, ei, bb->preds)
4538             {
4539               /* Do not thread across back edges or abnormal edges
4540                  in the CFG.  */
4541               if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
4542                 continue;
4543
4544               thread_across_edge (dummy, e, true,
4545                                   &stack,
4546                                   simplify_stmt_for_jump_threading);
4547             }
4548         }
4549     }
4550
4551   /* We do not actually update the CFG or SSA graphs at this point as
4552      ASSERT_EXPRs are still in the IL and cfg cleanup code does not yet
4553      handle ASSERT_EXPRs gracefully.  */
4554 }
4555
4556 /* We identified all the jump threading opportunities earlier, but could
4557    not transform the CFG at that time.  This routine transforms the
4558    CFG and arranges for the dominator tree to be rebuilt if necessary.
4559
4560    Note the SSA graph update will occur during the normal TODO
4561    processing by the pass manager.  */
4562 static void
4563 finalize_jump_threads (void)
4564 {
4565   bool cfg_altered = false;
4566   cfg_altered = thread_through_all_blocks ();
4567
4568   /* If we threaded jumps, then we need to recompute the dominance
4569      information, to safely do that we must clean up the CFG first.  */
4570   if (cfg_altered)
4571     {
4572       free_dominance_info (CDI_DOMINATORS);
4573       cleanup_tree_cfg ();
4574       calculate_dominance_info (CDI_DOMINATORS);
4575     }
4576   VEC_free (tree, heap, stack);
4577 }
4578
4579
4580 /* Traverse all the blocks folding conditionals with known ranges.  */
4581
4582 static void
4583 vrp_finalize (void)
4584 {
4585   size_t i;
4586   prop_value_t *single_val_range;
4587   bool do_value_subst_p;
4588
4589   if (dump_file)
4590     {
4591       fprintf (dump_file, "\nValue ranges after VRP:\n\n");
4592       dump_all_value_ranges (dump_file);
4593       fprintf (dump_file, "\n");
4594     }
4595
4596   /* We may have ended with ranges that have exactly one value.  Those
4597      values can be substituted as any other copy/const propagated
4598      value using substitute_and_fold.  */
4599   single_val_range = XNEWVEC (prop_value_t, num_ssa_names);
4600   memset (single_val_range, 0, num_ssa_names * sizeof (*single_val_range));
4601
4602   do_value_subst_p = false;
4603   for (i = 0; i < num_ssa_names; i++)
4604     if (vr_value[i]
4605         && vr_value[i]->type == VR_RANGE
4606         && vr_value[i]->min == vr_value[i]->max)
4607       {
4608         single_val_range[i].value = vr_value[i]->min;
4609         do_value_subst_p = true;
4610       }
4611
4612   if (!do_value_subst_p)
4613     {
4614       /* We found no single-valued ranges, don't waste time trying to
4615          do single value substitution in substitute_and_fold.  */
4616       free (single_val_range);
4617       single_val_range = NULL;
4618     }
4619
4620   substitute_and_fold (single_val_range, true);
4621
4622   /* We must identify jump threading opportunities before we release
4623      the datastructures built by VRP.  */
4624   identify_jump_threads ();
4625
4626   /* Free allocated memory.  */
4627   for (i = 0; i < num_ssa_names; i++)
4628     if (vr_value[i])
4629       {
4630         BITMAP_FREE (vr_value[i]->equiv);
4631         free (vr_value[i]);
4632       }
4633
4634   free (single_val_range);
4635   free (vr_value);
4636
4637   /* So that we can distinguish between VRP data being available
4638      and not available.  */
4639   vr_value = NULL;
4640 }
4641
4642
4643 /* Main entry point to VRP (Value Range Propagation).  This pass is
4644    loosely based on J. R. C. Patterson, ``Accurate Static Branch
4645    Prediction by Value Range Propagation,'' in SIGPLAN Conference on
4646    Programming Language Design and Implementation, pp. 67-78, 1995.
4647    Also available at http://citeseer.ist.psu.edu/patterson95accurate.html
4648
4649    This is essentially an SSA-CCP pass modified to deal with ranges
4650    instead of constants.
4651
4652    While propagating ranges, we may find that two or more SSA name
4653    have equivalent, though distinct ranges.  For instance,
4654
4655      1  x_9 = p_3->a;
4656      2  p_4 = ASSERT_EXPR <p_3, p_3 != 0>
4657      3  if (p_4 == q_2)
4658      4    p_5 = ASSERT_EXPR <p_4, p_4 == q_2>;
4659      5  endif
4660      6  if (q_2)
4661
4662    In the code above, pointer p_5 has range [q_2, q_2], but from the
4663    code we can also determine that p_5 cannot be NULL and, if q_2 had
4664    a non-varying range, p_5's range should also be compatible with it.
4665
4666    These equivalences are created by two expressions: ASSERT_EXPR and
4667    copy operations.  Since p_5 is an assertion on p_4, and p_4 was the
4668    result of another assertion, then we can use the fact that p_5 and
4669    p_4 are equivalent when evaluating p_5's range.
4670
4671    Together with value ranges, we also propagate these equivalences
4672    between names so that we can take advantage of information from
4673    multiple ranges when doing final replacement.  Note that this
4674    equivalency relation is transitive but not symmetric.
4675
4676    In the example above, p_5 is equivalent to p_4, q_2 and p_3, but we
4677    cannot assert that q_2 is equivalent to p_5 because q_2 may be used
4678    in contexts where that assertion does not hold (e.g., in line 6).
4679
4680    TODO, the main difference between this pass and Patterson's is that
4681    we do not propagate edge probabilities.  We only compute whether
4682    edges can be taken or not.  That is, instead of having a spectrum
4683    of jump probabilities between 0 and 1, we only deal with 0, 1 and
4684    DON'T KNOW.  In the future, it may be worthwhile to propagate
4685    probabilities to aid branch prediction.  */
4686
4687 static unsigned int
4688 execute_vrp (void)
4689 {
4690   insert_range_assertions ();
4691
4692   current_loops = loop_optimizer_init (LOOPS_NORMAL);
4693   if (current_loops)
4694     scev_initialize (current_loops);
4695
4696   vrp_initialize ();
4697   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
4698   vrp_finalize ();
4699
4700   if (current_loops)
4701     {
4702       scev_finalize ();
4703       loop_optimizer_finalize (current_loops);
4704       current_loops = NULL;
4705     }
4706
4707   /* ASSERT_EXPRs must be removed before finalizing jump threads
4708      as finalizing jump threads calls the CFG cleanup code which
4709      does not properly handle ASSERT_EXPRs.  */
4710   remove_range_assertions ();
4711
4712   /* If we exposed any new variables, go ahead and put them into
4713      SSA form now, before we handle jump threading.  This simplifies
4714      interactions between rewriting of _DECL nodes into SSA form
4715      and rewriting SSA_NAME nodes into SSA form after block
4716      duplication and CFG manipulation.  */
4717   update_ssa (TODO_update_ssa);
4718
4719   finalize_jump_threads ();
4720   return 0;
4721 }
4722
4723 static bool
4724 gate_vrp (void)
4725 {
4726   return flag_tree_vrp != 0;
4727 }
4728
4729 struct tree_opt_pass pass_vrp =
4730 {
4731   "vrp",                                /* name */
4732   gate_vrp,                             /* gate */
4733   execute_vrp,                          /* execute */
4734   NULL,                                 /* sub */
4735   NULL,                                 /* next */
4736   0,                                    /* static_pass_number */
4737   TV_TREE_VRP,                          /* tv_id */
4738   PROP_ssa | PROP_alias,                /* properties_required */
4739   0,                                    /* properties_provided */
4740   PROP_smt_usage,                       /* properties_destroyed */
4741   0,                                    /* todo_flags_start */
4742   TODO_cleanup_cfg
4743     | TODO_ggc_collect
4744     | TODO_verify_ssa
4745     | TODO_dump_func
4746     | TODO_update_ssa
4747     | TODO_update_smt_usage,                    /* todo_flags_finish */
4748   0                                     /* letter */
4749 };