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