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