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