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