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