gcc/tree-vrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "flags.h"
  28 #include "tree.h"
  29 #include "basic-block.h"
  30 #include "tree-flow.h"
  31 #include "tree-pass.h"
  32 #include "tree-dump.h"
  33 #include "timevar.h"
  34 #include "diagnostic.h"
  35 #include "cfgloop.h"
  36 #include "tree-scalar-evolution.h"
  37 #include "tree-ssa-propagate.h"
  38 #include "tree-chrec.h"
  39
  40 /* Set of SSA names found during the dominator traversal of a
  41    sub-graph in find_assert_locations.  */
  42 static sbitmap found_in_subgraph;
  43
  44 /* Local functions.  */
  45 static int compare_values (tree val1, tree val2);
  46
  47 /* Location information for ASSERT_EXPRs.  Each instance of this
  48    structure describes an ASSERT_EXPR for an SSA name.  Since a single
  49    SSA name may have more than one assertion associated with it, these
  50    locations are kept in a linked list attached to the corresponding
  51    SSA name.  */
  52 struct assert_locus_d
  53 {
  54   /* Basic block where the assertion would be inserted.  */
  55   basic_block bb;
  56
  57   /* Some assertions need to be inserted on an edge (e.g., assertions
  58      generated by COND_EXPRs).  In those cases, BB will be NULL.  */
  59   edge e;
  60
  61   /* Pointer to the statement that generated this assertion.  */
  62   block_stmt_iterator si;
  63
  64   /* Predicate code for the ASSERT_EXPR.  Must be COMPARISON_CLASS_P.  */
  65   enum tree_code comp_code;
  66
  67   /* Value being compared against.  */
  68   tree val;
  69
  70   /* Next node in the linked list.  */
  71   struct assert_locus_d *next;
  72 };
  73
  74 typedef struct assert_locus_d *assert_locus_t;
  75
  76 /* If bit I is present, it means that SSA name N_i has a list of
  77    assertions that should be inserted in the IL.  */
  78 static bitmap need_assert_for;
  79
  80 /* Array of locations lists where to insert assertions.  ASSERTS_FOR[I]
  81    holds a list of ASSERT_LOCUS_T nodes that describe where
  82    ASSERT_EXPRs for SSA name N_I should be inserted.  */
  83 static assert_locus_t *asserts_for;
  84
  85 /* Set of blocks visited in find_assert_locations.  Used to avoid
  86    visiting the same block more than once.  */
  87 static sbitmap blocks_visited;
  88
  89 /* Value range array.  After propagation, VR_VALUE[I] holds the range
  90    of values that SSA name N_I may take.  */
  91 static value_range_t **vr_value;
  92
  93
  94 /* Return true if ARG is marked with the nonnull attribute in the
  95    current function signature.  */
  96
  97 static bool
  98 nonnull_arg_p (tree arg)
  99 {
 100   tree t, attrs, fntype;
 101   unsigned HOST_WIDE_INT arg_num;
 102
 103   gcc_assert (TREE_CODE (arg) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (arg)));
 104
 105   fntype = TREE_TYPE (current_function_decl);
 106   attrs = lookup_attribute ("nonnull", TYPE_ATTRIBUTES (fntype));
 107
 108   /* If "nonnull" wasn't specified, we know nothing about the argument.  */
 109   if (attrs == NULL_TREE)
 110     return false;
 111
 112   /* If "nonnull" applies to all the arguments, then ARG is non-null.  */
 113   if (TREE_VALUE (attrs) == NULL_TREE)
 114     return true;
 115
 116   /* Get the position number for ARG in the function signature.  */
 117   for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
 118        t;
 119        t = TREE_CHAIN (t), arg_num++)
 120     {
 121       if (t == arg)
 122         break;
 123     }
 124
 125   gcc_assert (t == arg);
 126
 127   /* Now see if ARG_NUM is mentioned in the nonnull list.  */
 128   for (t = TREE_VALUE (attrs); t; t = TREE_CHAIN (t))
 129     {
 130       if (compare_tree_int (TREE_VALUE (t), arg_num) == 0)
 131         return true;
 132     }
 133
 134   return false;
 135 }
 136
 137
 138 /* Set value range VR to {T, MIN, MAX, EQUIV}.  */
 139
 140 static void
 141 set_value_range (value_range_t *vr, enum value_range_type t, tree min,
 142                  tree max, bitmap equiv)
 143 {
 144 #if defined ENABLE_CHECKING
 145   /* Check the validity of the range.  */
 146   if (t == VR_RANGE || t == VR_ANTI_RANGE)
 147     {
 148       int cmp;
 149
 150       gcc_assert (min && max);
 151
 152       if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
 153         gcc_assert (min != TYPE_MIN_VALUE (TREE_TYPE (min))
 154                     || max != TYPE_MAX_VALUE (TREE_TYPE (max)));
 155
 156       cmp = compare_values (min, max);
 157       gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
 158     }
 159
 160   if (t == VR_UNDEFINED || t == VR_VARYING)
 161     gcc_assert (min == NULL_TREE && max == NULL_TREE);
 162
 163   if (t == VR_UNDEFINED || t == VR_VARYING)
 164     gcc_assert (equiv == NULL || bitmap_empty_p (equiv));
 165 #endif
 166
 167   vr->type = t;
 168   vr->min = min;
 169   vr->max = max;
 170
 171   /* Since updating the equivalence set involves deep copying the
 172      bitmaps, only do it if absolutely necessary.  */
 173   if (vr->equiv == NULL)
 174     vr->equiv = BITMAP_ALLOC (NULL);
 175
 176   if (equiv != vr->equiv)
 177     {
 178       if (equiv && !bitmap_empty_p (equiv))
 179         bitmap_copy (vr->equiv, equiv);
 180       else
 181         bitmap_clear (vr->equiv);
 182     }
 183 }
 184
 185
 186 /* Copy value range FROM into value range TO.  */
 187
 188 static inline void
 189 copy_value_range (value_range_t *to, value_range_t *from)
 190 {
 191   set_value_range (to, from->type, from->min, from->max, from->equiv);
 192 }
 193
 194 /* Set value range VR to a non-negative range of type TYPE.  */
 195
 196 static inline void
 197 set_value_range_to_nonnegative (value_range_t *vr, tree type)
 198 {
 199   tree zero = build_int_cst (type, 0);
 200   set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
 201 }
 202
 203 /* Set value range VR to a non-NULL range of type TYPE.  */
 204
 205 static inline void
 206 set_value_range_to_nonnull (value_range_t *vr, tree type)
 207 {
 208   tree zero = build_int_cst (type, 0);
 209   set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv);
 210 }
 211
 212
 213 /* Set value range VR to a NULL range of type TYPE.  */
 214
 215 static inline void
 216 set_value_range_to_null (value_range_t *vr, tree type)
 217 {
 218   tree zero = build_int_cst (type, 0);
 219   set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
 220 }
 221
 222
 223 /* Set value range VR to VR_VARYING.  */
 224
 225 static inline void
 226 set_value_range_to_varying (value_range_t *vr)
 227 {
 228   vr->type = VR_VARYING;
 229   vr->min = vr->max = NULL_TREE;
 230   if (vr->equiv)
 231     bitmap_clear (vr->equiv);
 232 }
 233
 234
 235 /* Set value range VR to VR_UNDEFINED.  */
 236
 237 static inline void
 238 set_value_range_to_undefined (value_range_t *vr)
 239 {
 240   vr->type = VR_UNDEFINED;
 241   vr->min = vr->max = NULL_TREE;
 242   if (vr->equiv)
 243     bitmap_clear (vr->equiv);
 244 }
 245
 246
 247 /* Return value range information for VAR.
 248
 249    If we have no values ranges recorded (ie, VRP is not running), then
 250    return NULL.  Otherwise create an empty range if none existed for VAR.  */
 251
 252 static value_range_t *
 253 get_value_range (tree var)
 254 {
 255   value_range_t *vr;
 256   tree sym;
 257   unsigned ver = SSA_NAME_VERSION (var);
 258
 259   /* If we have no recorded ranges, then return NULL.  */
 260   if (! vr_value)
 261     return NULL;
 262
 263   vr = vr_value[ver];
 264   if (vr)
 265     return vr;
 266
 267   /* Create a default value range.  */
 268   vr_value[ver] = vr = XNEW (value_range_t);
 269   memset (vr, 0, sizeof (*vr));
 270
 271   /* Allocate an equivalence set.  */
 272   vr->equiv = BITMAP_ALLOC (NULL);
 273
 274   /* If VAR is a default definition, the variable can take any value
 275      in VAR's type.  */
 276   sym = SSA_NAME_VAR (var);
 277   if (var == default_def (sym))
 278     {
 279       /* Try to use the "nonnull" attribute to create ~[0, 0]
 280          anti-ranges for pointers.  Note that this is only valid with
 281          default definitions of PARM_DECLs.  */
 282       if (TREE_CODE (sym) == PARM_DECL
 283           && POINTER_TYPE_P (TREE_TYPE (sym))
 284           && nonnull_arg_p (sym))
 285         set_value_range_to_nonnull (vr, TREE_TYPE (sym));
 286       else
 287         set_value_range_to_varying (vr);
 288     }
 289
 290   return vr;
 291 }
 292
 293
 294 /* Update the value range and equivalence set for variable VAR to
 295    NEW_VR.  Return true if NEW_VR is different from VAR's previous
 296    value.
 297
 298    NOTE: This function assumes that NEW_VR is a temporary value range
 299    object created for the sole purpose of updating VAR's range.  The
 300    storage used by the equivalence set from NEW_VR will be freed by
 301    this function.  Do not call update_value_range when NEW_VR
 302    is the range object associated with another SSA name.  */
 303
 304 static inline bool
 305 update_value_range (tree var, value_range_t *new_vr)
 306 {
 307   value_range_t *old_vr;
 308   bool is_new;
 309
 310   /* Update the value range, if necessary.  */
 311   old_vr = get_value_range (var);
 312   is_new = old_vr->type != new_vr->type
 313            || old_vr->min != new_vr->min
 314            || old_vr->max != new_vr->max
 315            || (old_vr->equiv == NULL && new_vr->equiv)
 316            || (old_vr->equiv && new_vr->equiv == NULL)
 317            || (!bitmap_equal_p (old_vr->equiv, new_vr->equiv));
 318
 319   if (is_new)
 320     set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
 321                      new_vr->equiv);
 322
 323   BITMAP_FREE (new_vr->equiv);
 324   new_vr->equiv = NULL;
 325
 326   return is_new;
 327 }
 328
 329
 330 /* Add VAR and VAR's equivalence set to EQUIV.  */
 331
 332 static void
 333 add_equivalence (bitmap equiv, tree var)
 334 {
 335   unsigned ver = SSA_NAME_VERSION (var);
 336   value_range_t *vr = vr_value[ver];
 337
 338   bitmap_set_bit (equiv, ver);
 339   if (vr && vr->equiv)
 340     bitmap_ior_into (equiv, vr->equiv);
 341 }
 342
 343
 344 /* Return true if VR is ~[0, 0].  */
 345
 346 static inline bool
 347 range_is_nonnull (value_range_t *vr)
 348 {
 349   return vr->type == VR_ANTI_RANGE
 350          && integer_zerop (vr->min)
 351          && integer_zerop (vr->max);
 352 }
 353
 354
 355 /* Return true if VR is [0, 0].  */
 356
 357 static inline bool
 358 range_is_null (value_range_t *vr)
 359 {
 360   return vr->type == VR_RANGE
 361          && integer_zerop (vr->min)
 362          && integer_zerop (vr->max);
 363 }
 364
 365
 366 /* Return true if value range VR involves at least one symbol.  */
 367
 368 static inline bool
 369 symbolic_range_p (value_range_t *vr)
 370 {
 371   return (!is_gimple_min_invariant (vr->min)
 372           || !is_gimple_min_invariant (vr->max));
 373 }
 374
 375 /* Like tree_expr_nonnegative_p, but this function uses value ranges
 376    obtained so far.  */
 377
 378 static bool
 379 vrp_expr_computes_nonnegative (tree expr)
 380 {
 381   return tree_expr_nonnegative_p (expr);
 382 }
 383
 384 /* Like tree_expr_nonzero_p, but this function uses value ranges
 385    obtained so far.  */
 386
 387 static bool
 388 vrp_expr_computes_nonzero (tree expr)
 389 {
 390   if (tree_expr_nonzero_p (expr))
 391     return true;
 392
 393   /* If we have an expression of the form &X->a, then the expression
 394      is nonnull if X is nonnull.  */
 395   if (TREE_CODE (expr) == ADDR_EXPR)
 396     {
 397       tree base = get_base_address (TREE_OPERAND (expr, 0));
 398
 399       if (base != NULL_TREE
 400           && TREE_CODE (base) == INDIRECT_REF
 401           && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
 402         {
 403           value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
 404           if (range_is_nonnull (vr))
 405             return true;
 406         }
 407     }
 408
 409   return false;
 410 }
 411
 412
 413 /* Compare two values VAL1 and VAL2.  Return
 414
 415         -2 if VAL1 and VAL2 cannot be compared at compile-time,
 416         -1 if VAL1 < VAL2,
 417          0 if VAL1 == VAL2,
 418         +1 if VAL1 > VAL2, and
 419         +2 if VAL1 != VAL2
 420
 421    This is similar to tree_int_cst_compare but supports pointer values
 422    and values that cannot be compared at compile time.  */
 423
 424 static int
 425 compare_values (tree val1, tree val2)
 426 {
 427   if (val1 == val2)
 428     return 0;
 429
 430   /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
 431      both integers.  */
 432   gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
 433               == POINTER_TYPE_P (TREE_TYPE (val2)));
 434
 435   /* Do some limited symbolic comparisons.  */
 436   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
 437     {
 438       /* We can determine some comparisons against +INF and -INF even
 439          if the other value is an expression.  */
 440       if (val1 == TYPE_MAX_VALUE (TREE_TYPE (val1))
 441           && TREE_CODE (val2) == MINUS_EXPR)
 442         {
 443           /* +INF > NAME - CST.  */
 444           return 1;
 445         }
 446       else if (val1 == TYPE_MIN_VALUE (TREE_TYPE (val1))
 447                && TREE_CODE (val2) == PLUS_EXPR)
 448         {
 449           /* -INF < NAME + CST.  */
 450           return -1;
 451         }
 452       else if (TREE_CODE (val1) == MINUS_EXPR
 453                && val2 == TYPE_MAX_VALUE (TREE_TYPE (val2)))
 454         {
 455           /* NAME - CST < +INF.  */
 456           return -1;
 457         }
 458       else if (TREE_CODE (val1) == PLUS_EXPR
 459                && val2 == TYPE_MIN_VALUE (TREE_TYPE (val2)))
 460         {
 461           /* NAME + CST > -INF.  */
 462           return 1;
 463         }
 464     }
 465
 466   if ((TREE_CODE (val1) == SSA_NAME
 467        || TREE_CODE (val1) == PLUS_EXPR
 468        || TREE_CODE (val1) == MINUS_EXPR)
 469       && (TREE_CODE (val2) == SSA_NAME
 470           || TREE_CODE (val2) == PLUS_EXPR
 471           || TREE_CODE (val2) == MINUS_EXPR))
 472     {
 473       tree n1, c1, n2, c2;
 474
 475       /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
 476          return -1 or +1 accordingly.  If VAL1 and VAL2 don't use the
 477          same name, return -2.  */
 478       if (TREE_CODE (val1) == SSA_NAME)
 479         {
 480           n1 = val1;
 481           c1 = NULL_TREE;
 482         }
 483       else
 484         {
 485           n1 = TREE_OPERAND (val1, 0);
 486           c1 = TREE_OPERAND (val1, 1);
 487         }
 488
 489       if (TREE_CODE (val2) == SSA_NAME)
 490         {
 491           n2 = val2;
 492           c2 = NULL_TREE;
 493         }
 494       else
 495         {
 496           n2 = TREE_OPERAND (val2, 0);
 497           c2 = TREE_OPERAND (val2, 1);
 498         }
 499
 500       /* Both values must use the same name.  */
 501       if (n1 != n2)
 502         return -2;
 503
 504       if (TREE_CODE (val1) == SSA_NAME)
 505         {
 506           if (TREE_CODE (val2) == SSA_NAME)
 507             /* NAME == NAME  */
 508             return 0;
 509           else if (TREE_CODE (val2) == PLUS_EXPR)
 510             /* NAME < NAME + CST  */
 511             return -1;
 512           else if (TREE_CODE (val2) == MINUS_EXPR)
 513             /* NAME > NAME - CST  */
 514             return 1;
 515         }
 516       else if (TREE_CODE (val1) == PLUS_EXPR)
 517         {
 518           if (TREE_CODE (val2) == SSA_NAME)
 519             /* NAME + CST > NAME  */
 520             return 1;
 521           else if (TREE_CODE (val2) == PLUS_EXPR)
 522             /* NAME + CST1 > NAME + CST2, if CST1 > CST2  */
 523             return compare_values (c1, c2);
 524           else if (TREE_CODE (val2) == MINUS_EXPR)
 525             /* NAME + CST1 > NAME - CST2  */
 526             return 1;
 527         }
 528       else if (TREE_CODE (val1) == MINUS_EXPR)
 529         {
 530           if (TREE_CODE (val2) == SSA_NAME)
 531             /* NAME - CST < NAME  */
 532             return -1;
 533           else if (TREE_CODE (val2) == PLUS_EXPR)
 534             /* NAME - CST1 < NAME + CST2  */
 535             return -1;
 536           else if (TREE_CODE (val2) == MINUS_EXPR)
 537             /* NAME - CST1 > NAME - CST2, if CST1 < CST2.  Notice that
 538                C1 and C2 are swapped in the call to compare_values.  */
 539             return compare_values (c2, c1);
 540         }
 541
 542       gcc_unreachable ();
 543     }
 544
 545   /* We cannot compare non-constants.  */
 546   if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
 547     return -2;
 548
 549   if (!POINTER_TYPE_P (TREE_TYPE (val1)))
 550     {
 551       /* We cannot compare overflowed values.  */
 552       if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
 553         return -2;
 554
 555       return tree_int_cst_compare (val1, val2);
 556     }
 557   else
 558     {
 559       tree t;
 560
 561       /* First see if VAL1 and VAL2 are not the same.  */
 562       if (val1 == val2 || operand_equal_p (val1, val2, 0))
 563         return 0;
 564
 565       /* If VAL1 is a lower address than VAL2, return -1.  */
 566       t = fold_binary (LT_EXPR, boolean_type_node, val1, val2);
 567       if (t == boolean_true_node)
 568         return -1;
 569
 570       /* If VAL1 is a higher address than VAL2, return +1.  */
 571       t = fold_binary (GT_EXPR, boolean_type_node, val1, val2);
 572       if (t == boolean_true_node)
 573         return 1;
 574
 575       /* If VAL1 is different than VAL2, return +2.  */
 576       t = fold_binary (NE_EXPR, boolean_type_node, val1, val2);
 577       if (t == boolean_true_node)
 578         return 2;
 579
 580       return -2;
 581     }
 582 }
 583
 584
 585 /* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
 586           0 if VAL is not inside VR,
 587          -2 if we cannot tell either way.
 588
 589    FIXME, the current semantics of this functions are a bit quirky
 590           when taken in the context of VRP.  In here we do not care
 591           about VR's type.  If VR is the anti-range ~[3, 5] the call
 592           value_inside_range (4, VR) will return 1.
 593
 594           This is counter-intuitive in a strict sense, but the callers
 595           currently expect this.  They are calling the function
 596           merely to determine whether VR->MIN <= VAL <= VR->MAX.  The
 597           callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
 598           themselves.
 599
 600           This also applies to value_ranges_intersect_p and
 601           range_includes_zero_p.  The semantics of VR_RANGE and
 602           VR_ANTI_RANGE should be encoded here, but that also means
 603           adapting the users of these functions to the new semantics.  */
 604
 605 static inline int
 606 value_inside_range (tree val, value_range_t *vr)
 607 {
 608   int cmp1, cmp2;
 609
 610   cmp1 = compare_values (val, vr->min);
 611   if (cmp1 == -2 || cmp1 == 2)
 612     return -2;
 613
 614   cmp2 = compare_values (val, vr->max);
 615   if (cmp2 == -2 || cmp2 == 2)
 616     return -2;
 617
 618   return (cmp1 == 0 || cmp1 == 1) && (cmp2 == -1 || cmp2 == 0);
 619 }
 620
 621
 622 /* Return true if value ranges VR0 and VR1 have a non-empty
 623    intersection.  */
 624
 625 static inline bool
 626 value_ranges_intersect_p (value_range_t *vr0, value_range_t *vr1)
 627 {
 628   return (value_inside_range (vr1->min, vr0) == 1
 629           || value_inside_range (vr1->max, vr0) == 1
 630           || value_inside_range (vr0->min, vr1) == 1
 631           || value_inside_range (vr0->max, vr1) == 1);
 632 }
 633
 634
 635 /* Return true if VR includes the value zero, false otherwise.  FIXME,
 636    currently this will return false for an anti-range like ~[-4, 3].
 637    This will be wrong when the semantics of value_inside_range are
 638    modified (currently the users of this function expect these
 639    semantics).  */
 640
 641 static inline bool
 642 range_includes_zero_p (value_range_t *vr)
 643 {
 644   tree zero;
 645
 646   gcc_assert (vr->type != VR_UNDEFINED
 647               && vr->type != VR_VARYING
 648               && !symbolic_range_p (vr));
 649
 650   zero = build_int_cst (TREE_TYPE (vr->min), 0);
 651   return (value_inside_range (zero, vr) == 1);
 652 }
 653
 654 /* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
 655    false otherwise or if no value range information is available.  */
 656
 657 bool
 658 ssa_name_nonnegative_p (tree t)
 659 {
 660   value_range_t *vr = get_value_range (t);
 661
 662   if (!vr)
 663     return false;
 664
 665   /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
 666      which would return a useful value should be encoded as a VR_RANGE.  */
 667   if (vr->type == VR_RANGE)
 668     {
 669       int result = compare_values (vr->min, integer_zero_node);
 670
 671       return (result == 0 || result == 1);
 672     }
 673   return false;
 674 }
 675
 676 /* Return true if T, an SSA_NAME, is known to be nonzero.  Return
 677    false otherwise or if no value range information is available.  */
 678
 679 bool
 680 ssa_name_nonzero_p (tree t)
 681 {
 682   value_range_t *vr = get_value_range (t);
 683
 684   if (!vr)
 685     return false;
 686
 687   /* A VR_RANGE which does not include zero is a nonzero value.  */
 688   if (vr->type == VR_RANGE && !symbolic_range_p (vr))
 689     return ! range_includes_zero_p (vr);
 690
 691   /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
 692   if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
 693     return range_includes_zero_p (vr);
 694
 695   return false;
 696 }
 697
 698
 699 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
 700    initially consider X_i and Y_j equivalent, so the equivalence set
 701    of Y_j is added to the equivalence set of X_i.  However, it is
 702    possible to have a chain of ASSERT_EXPRs whose predicates are
 703    actually incompatible.  This is usually the result of nesting of
 704    contradictory if-then-else statements.  For instance, in PR 24670:
 705
 706         count_4 has range [-INF, 63]
 707
 708         if (count_4 != 0)
 709           {
 710             count_19 = ASSERT_EXPR <count_4, count_4 != 0>
 711             if (count_19 > 63)
 712               {
 713                 count_18 = ASSERT_EXPR <count_19, count_19 > 63>
 714                 if (count_18 <= 63)
 715                   ...
 716               }
 717           }
 718
 719    Notice that 'if (count_19 > 63)' is trivially false and will be
 720    folded out at the end.  However, during propagation, the flowgraph
 721    is not cleaned up and so, VRP will evaluate predicates more
 722    predicates than necessary, so it must support these
 723    inconsistencies.  The problem here is that because of the chaining
 724    of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
 725    Since count_4 has an incompatible range, we ICE when evaluating the
 726    ranges in the equivalency set.  So, we need to remove count_4 from
 727    it.  */
 728
 729 static void
 730 fix_equivalence_set (value_range_t *vr_p)
 731 {
 732   bitmap_iterator bi;
 733   unsigned i;
 734   bitmap e = vr_p->equiv;
 735   bitmap to_remove = BITMAP_ALLOC (NULL);
 736
 737   /* Only detect inconsistencies on numeric ranges.  */
 738   if (vr_p->type == VR_VARYING
 739       || vr_p->type == VR_UNDEFINED
 740       || symbolic_range_p (vr_p))
 741     return;
 742
 743   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
 744     {
 745       value_range_t *equiv_vr = vr_value[i];
 746
 747       if (equiv_vr->type == VR_VARYING
 748           || equiv_vr->type == VR_UNDEFINED
 749           || symbolic_range_p (equiv_vr))
 750         continue;
 751
 752       if (equiv_vr->type == VR_RANGE
 753           && vr_p->type == VR_RANGE
 754           && !value_ranges_intersect_p (vr_p, equiv_vr))
 755         bitmap_set_bit (to_remove, i);
 756       else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
 757                || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
 758         {
 759           /* A range and an anti-range have an empty intersection if
 760              their end points are the same.  FIXME,
 761              value_ranges_intersect_p should handle this
 762              automatically.  */
 763           if (compare_values (equiv_vr->min, vr_p->min) == 0
 764               && compare_values (equiv_vr->max, vr_p->max) == 0)
 765             bitmap_set_bit (to_remove, i);
 766         }
 767     }
 768
 769   bitmap_and_compl_into (vr_p->equiv, to_remove);
 770   BITMAP_FREE (to_remove);
 771 }
 772
 773
 774 /* Extract value range information from an ASSERT_EXPR EXPR and store
 775    it in *VR_P.  */
 776
 777 static void
 778 extract_range_from_assert (value_range_t *vr_p, tree expr)
 779 {
 780   tree var, cond, limit, min, max, type;
 781   value_range_t *var_vr, *limit_vr;
 782   enum tree_code cond_code;
 783
 784   var = ASSERT_EXPR_VAR (expr);
 785   cond = ASSERT_EXPR_COND (expr);
 786
 787   gcc_assert (COMPARISON_CLASS_P (cond));
 788
 789   /* Find VAR in the ASSERT_EXPR conditional.  */
 790   if (var == TREE_OPERAND (cond, 0))
 791     {
 792       /* If the predicate is of the form VAR COMP LIMIT, then we just
 793          take LIMIT from the RHS and use the same comparison code.  */
 794       limit = TREE_OPERAND (cond, 1);
 795       cond_code = TREE_CODE (cond);
 796     }
 797   else
 798     {
 799       /* If the predicate is of the form LIMIT COMP VAR, then we need
 800          to flip around the comparison code to create the proper range
 801          for VAR.  */
 802       limit = TREE_OPERAND (cond, 0);
 803       cond_code = swap_tree_comparison (TREE_CODE (cond));
 804     }
 805
 806   type = TREE_TYPE (limit);
 807   gcc_assert (limit != var);
 808
 809   /* For pointer arithmetic, we only keep track of pointer equality
 810      and inequality.  */
 811   if (POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
 812     {
 813       set_value_range_to_varying (vr_p);
 814       return;
 815     }
 816
 817   /* If LIMIT is another SSA name and LIMIT has a range of its own,
 818      try to use LIMIT's range to avoid creating symbolic ranges
 819      unnecessarily. */
 820   limit_vr = (TREE_CODE (limit) == SSA_NAME) ? get_value_range (limit) : NULL;
 821
 822   /* LIMIT's range is only interesting if it has any useful information.  */
 823   if (limit_vr
 824       && (limit_vr->type == VR_UNDEFINED
 825           || limit_vr->type == VR_VARYING
 826           || symbolic_range_p (limit_vr)))
 827     limit_vr = NULL;
 828
 829   /* Initially, the new range has the same set of equivalences of
 830      VAR's range.  This will be revised before returning the final
 831      value.  Since assertions may be chained via mutually exclusive
 832      predicates, we will need to trim the set of equivalences before
 833      we are done.  */
 834   gcc_assert (vr_p->equiv == NULL);
 835   vr_p->equiv = BITMAP_ALLOC (NULL);
 836   add_equivalence (vr_p->equiv, var);
 837
 838   /* Extract a new range based on the asserted comparison for VAR and
 839      LIMIT's value range.  Notice that if LIMIT has an anti-range, we
 840      will only use it for equality comparisons (EQ_EXPR).  For any
 841      other kind of assertion, we cannot derive a range from LIMIT's
 842      anti-range that can be used to describe the new range.  For
 843      instance, ASSERT_EXPR <x_2, x_2 <= b_4>.  If b_4 is ~[2, 10],
 844      then b_4 takes on the ranges [-INF, 1] and [11, +INF].  There is
 845      no single range for x_2 that could describe LE_EXPR, so we might
 846      as well build the range [b_4, +INF] for it.  */
 847   if (cond_code == EQ_EXPR)
 848     {
 849       enum value_range_type range_type;
 850
 851       if (limit_vr)
 852         {
 853           range_type = limit_vr->type;
 854           min = limit_vr->min;
 855           max = limit_vr->max;
 856         }
 857       else
 858         {
 859           range_type = VR_RANGE;
 860           min = limit;
 861           max = limit;
 862         }
 863
 864       set_value_range (vr_p, range_type, min, max, vr_p->equiv);
 865
 866       /* When asserting the equality VAR == LIMIT and LIMIT is another
 867          SSA name, the new range will also inherit the equivalence set
 868          from LIMIT.  */
 869       if (TREE_CODE (limit) == SSA_NAME)
 870         add_equivalence (vr_p->equiv, limit);
 871     }
 872   else if (cond_code == NE_EXPR)
 873     {
 874       /* As described above, when LIMIT's range is an anti-range and
 875          this assertion is an inequality (NE_EXPR), then we cannot
 876          derive anything from the anti-range.  For instance, if
 877          LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
 878          not imply that VAR's range is [0, 0].  So, in the case of
 879          anti-ranges, we just assert the inequality using LIMIT and
 880          not its anti-range.
 881
 882          If LIMIT_VR is a range, we can only use it to build a new
 883          anti-range if LIMIT_VR is a single-valued range.  For
 884          instance, if LIMIT_VR is [0, 1], the predicate
 885          VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
 886          Rather, it means that for value 0 VAR should be ~[0, 0]
 887          and for value 1, VAR should be ~[1, 1].  We cannot
 888          represent these ranges.
 889
 890          The only situation in which we can build a valid
 891          anti-range is when LIMIT_VR is a single-valued range
 892          (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX).  In that case,
 893          build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX].  */
 894       if (limit_vr
 895           && limit_vr->type == VR_RANGE
 896           && compare_values (limit_vr->min, limit_vr->max) == 0)
 897         {
 898           min = limit_vr->min;
 899           max = limit_vr->max;
 900         }
 901       else
 902         {
 903           /* In any other case, we cannot use LIMIT's range to build a
 904              valid anti-range.  */
 905           min = max = limit;
 906         }
 907
 908       /* If MIN and MAX cover the whole range for their type, then
 909          just use the original LIMIT.  */
 910       if (INTEGRAL_TYPE_P (type)
 911           && min == TYPE_MIN_VALUE (type)
 912           && max == TYPE_MAX_VALUE (type))
 913         min = max = limit;
 914
 915       set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
 916     }
 917   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
 918     {
 919       min = TYPE_MIN_VALUE (type);
 920
 921       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 922         max = limit;
 923       else
 924         {
 925           /* If LIMIT_VR is of the form [N1, N2], we need to build the
 926              range [MIN, N2] for LE_EXPR and [MIN, N2 - 1] for
 927              LT_EXPR.  */
 928           max = limit_vr->max;
 929         }
 930
 931       /* For LT_EXPR, we create the range [MIN, MAX - 1].  */
 932       if (cond_code == LT_EXPR)
 933         {
 934           tree one = build_int_cst (type, 1);
 935           max = fold_build2 (MINUS_EXPR, type, max, one);
 936         }
 937
 938       set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
 939     }
 940   else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
 941     {
 942       max = TYPE_MAX_VALUE (type);
 943
 944       if (limit_vr == NULL || limit_vr->type == VR_ANTI_RANGE)
 945         min = limit;
 946       else
 947         {
 948           /* If LIMIT_VR is of the form [N1, N2], we need to build the
 949              range [N1, MAX] for GE_EXPR and [N1 + 1, MAX] for
 950              GT_EXPR.  */
 951           min = limit_vr->min;
 952         }
 953
 954       /* For GT_EXPR, we create the range [MIN + 1, MAX].  */
 955       if (cond_code == GT_EXPR)
 956         {
 957           tree one = build_int_cst (type, 1);
 958           min = fold_build2 (PLUS_EXPR, type, min, one);
 959         }
 960
 961       set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
 962     }
 963   else
 964     gcc_unreachable ();
 965
 966   /* If VAR already had a known range, it may happen that the new
 967      range we have computed and VAR's range are not compatible.  For
 968      instance,
 969
 970         if (p_5 == NULL)
 971           p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
 972           x_7 = p_6->fld;
 973           p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
 974
 975      While the above comes from a faulty program, it will cause an ICE
 976      later because p_8 and p_6 will have incompatible ranges and at
 977      the same time will be considered equivalent.  A similar situation
 978      would arise from
 979
 980         if (i_5 > 10)
 981           i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
 982           if (i_5 < 5)
 983             i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
 984
 985      Again i_6 and i_7 will have incompatible ranges.  It would be
 986      pointless to try and do anything with i_7's range because
 987      anything dominated by 'if (i_5 < 5)' will be optimized away.
 988      Note, due to the wa in which simulation proceeds, the statement
 989      i_7 = ASSERT_EXPR <...> we would never be visited because the
 990      conditional 'if (i_5 < 5)' always evaluates to false.  However,
 991      this extra check does not hurt and may protect against future
 992      changes to VRP that may get into a situation similar to the
 993      NULL pointer dereference example.
 994
 995      Note that these compatibility tests are only needed when dealing
 996      with ranges or a mix of range and anti-range.  If VAR_VR and VR_P
 997      are both anti-ranges, they will always be compatible, because two
 998      anti-ranges will always have a non-empty intersection.  */
 999
1000   var_vr = get_value_range (var);
1001
1002   /* We may need to make adjustments when VR_P and VAR_VR are numeric
1003      ranges or anti-ranges.  */
1004   if (vr_p->type == VR_VARYING
1005       || vr_p->type == VR_UNDEFINED
1006       || var_vr->type == VR_VARYING
1007       || var_vr->type == VR_UNDEFINED
1008       || symbolic_range_p (vr_p)
1009       || symbolic_range_p (var_vr))
1010     goto done;
1011
1012   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
1013     {
1014       /* If the two ranges have a non-empty intersection, we can
1015          refine the resulting range.  Since the assert expression
1016          creates an equivalency and at the same time it asserts a
1017          predicate, we can take the intersection of the two ranges to
1018          get better precision.  */
1019       if (value_ranges_intersect_p (var_vr, vr_p))
1020         {
1021           /* Use the larger of the two minimums.  */
1022           if (compare_values (vr_p->min, var_vr->min) == -1)
1023             min = var_vr->min;
1024           else
1025             min = vr_p->min;
1026
1027           /* Use the smaller of the two maximums.  */
1028           if (compare_values (vr_p->max, var_vr->max) == 1)
1029             max = var_vr->max;
1030           else
1031             max = vr_p->max;
1032
1033           set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
1034         }
1035       else
1036         {
1037           /* The two ranges do not intersect, set the new range to
1038              VARYING, because we will not be able to do anything
1039              meaningful with it.  */
1040           set_value_range_to_varying (vr_p);
1041         }
1042     }
1043   else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
1044            || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
1045     {
1046       /* A range and an anti-range will cancel each other only if
1047          their ends are the same.  For instance, in the example above,
1048          p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
1049          so VR_P should be set to VR_VARYING.  */
1050       if (compare_values (var_vr->min, vr_p->min) == 0
1051           && compare_values (var_vr->max, vr_p->max) == 0)
1052         set_value_range_to_varying (vr_p);
1053       else
1054         {
1055           tree min, max, anti_min, anti_max, real_min, real_max;
1056
1057           /* We want to compute the logical AND of the two ranges;
1058              there are three cases to consider.
1059
1060
1061              1. The VR_ANTI_RANGE range is completely within the
1062                 VR_RANGE and the endpoints of the ranges are
1063                 different.  In that case the resulting range
1064                 should be whichever range is more precise.
1065                 Typically that will be the VR_RANGE.
1066
1067              2. The VR_ANTI_RANGE is completely disjoint from
1068                 the VR_RANGE.  In this case the resulting range
1069                 should be the VR_RANGE.
1070
1071              3. There is some overlap between the VR_ANTI_RANGE
1072                 and the VR_RANGE.
1073
1074                 3a. If the high limit of the VR_ANTI_RANGE resides
1075                     within the VR_RANGE, then the result is a new
1076                     VR_RANGE starting at the high limit of the
1077                     the VR_ANTI_RANGE + 1 and extending to the
1078                     high limit of the original VR_RANGE.
1079
1080                 3b. If the low limit of the VR_ANTI_RANGE resides
1081                     within the VR_RANGE, then the result is a new
1082                     VR_RANGE starting at the low limit of the original
1083                     VR_RANGE and extending to the low limit of the
1084                     VR_ANTI_RANGE - 1.  */
1085           if (vr_p->type == VR_ANTI_RANGE)
1086             {
1087               anti_min = vr_p->min;
1088               anti_max = vr_p->max;
1089               real_min = var_vr->min;
1090               real_max = var_vr->max;
1091             }
1092           else
1093             {
1094               anti_min = var_vr->min;
1095               anti_max = var_vr->max;
1096               real_min = vr_p->min;
1097               real_max = vr_p->max;
1098             }
1099
1100
1101           /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
1102              not including any endpoints.  */
1103           if (compare_values (anti_max, real_max) == -1
1104               && compare_values (anti_min, real_min) == 1)
1105             {
1106               set_value_range (vr_p, VR_RANGE, real_min,
1107                                real_max, vr_p->equiv);
1108             }
1109           /* Case 2, VR_ANTI_RANGE completely disjoint from
1110              VR_RANGE.  */
1111           else if (compare_values (anti_min, real_max) == 1
1112                    || compare_values (anti_max, real_min) == -1)
1113             {
1114               set_value_range (vr_p, VR_RANGE, real_min,
1115                                real_max, vr_p->equiv);
1116             }
1117           /* Case 3a, the anti-range extends into the low
1118              part of the real range.  Thus creating a new
1119              low for the real reange.  */
1120           else if ((compare_values (anti_max, real_min) == 1
1121                     || compare_values (anti_max, real_min) == 0)
1122                    && compare_values (anti_max, real_max) == -1)
1123             {
1124               min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
1125                                  anti_max,
1126                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1127               max = real_max;
1128               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1129             }
1130           /* Case 3b, the anti-range extends into the high
1131              part of the real range.  Thus creating a new
1132              higher for the real reange.  */
1133           else if (compare_values (anti_min, real_min) == 1
1134                    && (compare_values (anti_min, real_max) == -1
1135                        || compare_values (anti_min, real_max) == 0))
1136             {
1137               max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
1138                                  anti_min,
1139                                  build_int_cst (TREE_TYPE (var_vr->min), 1));
1140               min = real_min;
1141               set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
1142             }
1143         }
1144     }
1145
1146   /* Remove names from the equivalence set that have ranges
1147      incompatible with VR_P.  */
1148 done:
1149   fix_equivalence_set (vr_p);
1150 }
1151
1152
1153 /* Extract range information from SSA name VAR and store it in VR.  If
1154    VAR has an interesting range, use it.  Otherwise, create the
1155    range [VAR, VAR] and return it.  This is useful in situations where
1156    we may have conditionals testing values of VARYING names.  For
1157    instance,
1158
1159         x_3 = y_5;
1160         if (x_3 > y_5)
1161           ...
1162
1163     Even if y_5 is deemed VARYING, we can determine that x_3 > y_5 is
1164     always false.  */
1165
1166 static void
1167 extract_range_from_ssa_name (value_range_t *vr, tree var)
1168 {
1169   value_range_t *var_vr = get_value_range (var);
1170
1171   if (var_vr->type != VR_UNDEFINED && var_vr->type != VR_VARYING)
1172     copy_value_range (vr, var_vr);
1173   else
1174     set_value_range (vr, VR_RANGE, var, var, NULL);
1175
1176   add_equivalence (vr->equiv, var);
1177 }
1178
1179
1180 /* Wrapper around int_const_binop.  If the operation overflows and we
1181    are not using wrapping arithmetic, then adjust the result to be
1182    -INF or +INF depending on CODE, VAL1 and VAL2.  */
1183
1184 static inline tree
1185 vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
1186 {
1187   tree res;
1188
1189   if (flag_wrapv)
1190     return int_const_binop (code, val1, val2, 0);
1191
1192   /* If we are not using wrapping arithmetic, operate symbolically
1193      on -INF and +INF.  */
1194   res = int_const_binop (code, val1, val2, 0);
1195
1196   if (TYPE_UNSIGNED (TREE_TYPE (val1)))
1197     {
1198       int checkz = compare_values (res, val1);
1199
1200       /* Ensure that res = val1 [+*] val2 >= val1
1201          or that res = val1 - val2 <= val1.  */
1202       if (((code == PLUS_EXPR || code == MULT_EXPR)
1203            && !(checkz == 1 || checkz == 0))
1204           || (code == MINUS_EXPR
1205               && !(checkz == 0 || checkz == -1)))
1206         {
1207           res = copy_node (res);
1208           TREE_OVERFLOW (res) = 1;
1209         }
1210     }
1211   else if (TREE_OVERFLOW (res)
1212            && !TREE_OVERFLOW (val1)
1213            && !TREE_OVERFLOW (val2))
1214     {
1215       /* If the operation overflowed but neither VAL1 nor VAL2 are
1216          overflown, return -INF or +INF depending on the operation
1217          and the combination of signs of the operands.  */
1218       int sgn1 = tree_int_cst_sgn (val1);
1219       int sgn2 = tree_int_cst_sgn (val2);
1220
1221       /* Notice that we only need to handle the restricted set of
1222          operations handled by extract_range_from_binary_expr.
1223          Among them, only multiplication, addition and subtraction
1224          can yield overflow without overflown operands because we
1225          are working with integral types only... except in the
1226          case VAL1 = -INF and VAL2 = -1 which overflows to +INF
1227          for division too.  */
1228
1229       /* For multiplication, the sign of the overflow is given
1230          by the comparison of the signs of the operands.  */
1231       if ((code == MULT_EXPR && sgn1 == sgn2)
1232           /* For addition, the operands must be of the same sign
1233              to yield an overflow.  Its sign is therefore that
1234              of one of the operands, for example the first.  */
1235           || (code == PLUS_EXPR && sgn1 > 0)
1236           /* For subtraction, the operands must be of different
1237              signs to yield an overflow.  Its sign is therefore
1238              that of the first operand or the opposite of that
1239              of the second operand.  A first operand of 0 counts
1240              as positive here, for the corner case 0 - (-INF),
1241              which overflows, but must yield +INF.  */
1242           || (code == MINUS_EXPR && sgn1 >= 0)
1243           /* For division, the only case is -INF / -1 = +INF.  */
1244           || code == TRUNC_DIV_EXPR
1245           || code == FLOOR_DIV_EXPR
1246           || code == CEIL_DIV_EXPR
1247           || code == EXACT_DIV_EXPR
1248           || code == ROUND_DIV_EXPR)
1249         return TYPE_MAX_VALUE (TREE_TYPE (res));
1250       else
1251         return TYPE_MIN_VALUE (TREE_TYPE (res));
1252     }
1253
1254   return res;
1255 }
1256
1257
1258 /* Extract range information from a binary expression EXPR based on
1259    the ranges of each of its operands and the expression code.  */
1260
1261 static void
1262 extract_range_from_binary_expr (value_range_t *vr, tree expr)
1263 {
1264   enum tree_code code = TREE_CODE (expr);
1265   enum value_range_type type;
1266   tree op0, op1, min, max;
1267   int cmp;
1268   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1269   value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1270
1271   /* Not all binary expressions can be applied to ranges in a
1272      meaningful way.  Handle only arithmetic operations.  */
1273   if (code != PLUS_EXPR
1274       && code != MINUS_EXPR
1275       && code != MULT_EXPR
1276       && code != TRUNC_DIV_EXPR
1277       && code != FLOOR_DIV_EXPR
1278       && code != CEIL_DIV_EXPR
1279       && code != EXACT_DIV_EXPR
1280       && code != ROUND_DIV_EXPR
1281       && code != MIN_EXPR
1282       && code != MAX_EXPR
1283       && code != BIT_AND_EXPR
1284       && code != TRUTH_ANDIF_EXPR
1285       && code != TRUTH_ORIF_EXPR
1286       && code != TRUTH_AND_EXPR
1287       && code != TRUTH_OR_EXPR)
1288     {
1289       set_value_range_to_varying (vr);
1290       return;
1291     }
1292
1293   /* Get value ranges for each operand.  For constant operands, create
1294      a new value range with the operand to simplify processing.  */
1295   op0 = TREE_OPERAND (expr, 0);
1296   if (TREE_CODE (op0) == SSA_NAME)
1297     vr0 = *(get_value_range (op0));
1298   else if (is_gimple_min_invariant (op0))
1299     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1300   else
1301     set_value_range_to_varying (&vr0);
1302
1303   op1 = TREE_OPERAND (expr, 1);
1304   if (TREE_CODE (op1) == SSA_NAME)
1305     vr1 = *(get_value_range (op1));
1306   else if (is_gimple_min_invariant (op1))
1307     set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
1308   else
1309     set_value_range_to_varying (&vr1);
1310
1311   /* If either range is UNDEFINED, so is the result.  */
1312   if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
1313     {
1314       set_value_range_to_undefined (vr);
1315       return;
1316     }
1317
1318   /* The type of the resulting value range defaults to VR0.TYPE.  */
1319   type = vr0.type;
1320
1321   /* Refuse to operate on VARYING ranges, ranges of different kinds
1322      and symbolic ranges.  As an exception, we allow BIT_AND_EXPR
1323      because we may be able to derive a useful range even if one of
1324      the operands is VR_VARYING or symbolic range.  TODO, we may be
1325      able to derive anti-ranges in some cases.  */
1326   if (code != BIT_AND_EXPR
1327       && code != TRUTH_AND_EXPR
1328       && code != TRUTH_OR_EXPR
1329       && (vr0.type == VR_VARYING
1330           || vr1.type == VR_VARYING
1331           || vr0.type != vr1.type
1332           || symbolic_range_p (&vr0)
1333           || symbolic_range_p (&vr1)))
1334     {
1335       set_value_range_to_varying (vr);
1336       return;
1337     }
1338
1339   /* Now evaluate the expression to determine the new range.  */
1340   if (POINTER_TYPE_P (TREE_TYPE (expr))
1341       || POINTER_TYPE_P (TREE_TYPE (op0))
1342       || POINTER_TYPE_P (TREE_TYPE (op1)))
1343     {
1344       /* For pointer types, we are really only interested in asserting
1345          whether the expression evaluates to non-NULL.  FIXME, we used
1346          to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
1347          ivopts is generating expressions with pointer multiplication
1348          in them.  */
1349       if (code == PLUS_EXPR)
1350         {
1351           if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
1352             set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1353           else if (range_is_null (&vr0) && range_is_null (&vr1))
1354             set_value_range_to_null (vr, TREE_TYPE (expr));
1355           else
1356             set_value_range_to_varying (vr);
1357         }
1358       else
1359         {
1360           /* Subtracting from a pointer, may yield 0, so just drop the
1361              resulting range to varying.  */
1362           set_value_range_to_varying (vr);
1363         }
1364
1365       return;
1366     }
1367
1368   /* For integer ranges, apply the operation to each end of the
1369      range and see what we end up with.  */
1370   if (code == TRUTH_ANDIF_EXPR
1371       || code == TRUTH_ORIF_EXPR
1372       || code == TRUTH_AND_EXPR
1373       || code == TRUTH_OR_EXPR)
1374     {
1375       /* If one of the operands is zero, we know that the whole
1376          expression evaluates zero.  */
1377       if (code == TRUTH_AND_EXPR
1378           && ((vr0.type == VR_RANGE
1379                && integer_zerop (vr0.min)
1380                && integer_zerop (vr0.max))
1381               || (vr1.type == VR_RANGE
1382                   && integer_zerop (vr1.min)
1383                   && integer_zerop (vr1.max))))
1384         {
1385           type = VR_RANGE;
1386           min = max = build_int_cst (TREE_TYPE (expr), 0);
1387         }
1388       /* If one of the operands is one, we know that the whole
1389          expression evaluates one.  */
1390       else if (code == TRUTH_OR_EXPR
1391                && ((vr0.type == VR_RANGE
1392                     && integer_onep (vr0.min)
1393                     && integer_onep (vr0.max))
1394                    || (vr1.type == VR_RANGE
1395                        && integer_onep (vr1.min)
1396                        && integer_onep (vr1.max))))
1397         {
1398           type = VR_RANGE;
1399           min = max = build_int_cst (TREE_TYPE (expr), 1);
1400         }
1401       else if (vr0.type != VR_VARYING
1402                && vr1.type != VR_VARYING
1403                && vr0.type == vr1.type
1404                && !symbolic_range_p (&vr0)
1405                && !symbolic_range_p (&vr1))
1406         {
1407           /* Boolean expressions cannot be folded with int_const_binop.  */
1408           min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
1409           max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
1410         }
1411       else
1412         {
1413           set_value_range_to_varying (vr);
1414           return;
1415         }
1416     }
1417   else if (code == PLUS_EXPR
1418            || code == MIN_EXPR
1419            || code == MAX_EXPR)
1420     {
1421       /* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
1422          VR_VARYING.  It would take more effort to compute a precise
1423          range for such a case.  For example, if we have op0 == 1 and
1424          op1 == -1 with their ranges both being ~[0,0], we would have
1425          op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
1426          Note that we are guaranteed to have vr0.type == vr1.type at
1427          this point.  */
1428       if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
1429         {
1430           set_value_range_to_varying (vr);
1431           return;
1432         }
1433
1434       /* For operations that make the resulting range directly
1435          proportional to the original ranges, apply the operation to
1436          the same end of each range.  */
1437       min = vrp_int_const_binop (code, vr0.min, vr1.min);
1438       max = vrp_int_const_binop (code, vr0.max, vr1.max);
1439     }
1440   else if (code == MULT_EXPR
1441            || code == TRUNC_DIV_EXPR
1442            || code == FLOOR_DIV_EXPR
1443            || code == CEIL_DIV_EXPR
1444            || code == EXACT_DIV_EXPR
1445            || code == ROUND_DIV_EXPR)
1446     {
1447       tree val[4];
1448       size_t i;
1449
1450       /* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
1451          drop to VR_VARYING.  It would take more effort to compute a
1452          precise range for such a case.  For example, if we have
1453          op0 == 65536 and op1 == 65536 with their ranges both being
1454          ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
1455          we cannot claim that the product is in ~[0,0].  Note that we
1456          are guaranteed to have vr0.type == vr1.type at this
1457          point.  */
1458       if (code == MULT_EXPR
1459           && vr0.type == VR_ANTI_RANGE
1460           && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
1461         {
1462           set_value_range_to_varying (vr);
1463           return;
1464         }
1465
1466       /* Multiplications and divisions are a bit tricky to handle,
1467          depending on the mix of signs we have in the two ranges, we
1468          need to operate on different values to get the minimum and
1469          maximum values for the new range.  One approach is to figure
1470          out all the variations of range combinations and do the
1471          operations.
1472
1473          However, this involves several calls to compare_values and it
1474          is pretty convoluted.  It's simpler to do the 4 operations
1475          (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
1476          MAX1) and then figure the smallest and largest values to form
1477          the new range.  */
1478
1479       /* Divisions by zero result in a VARYING value.  */
1480       if (code != MULT_EXPR
1481           && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
1482         {
1483           set_value_range_to_varying (vr);
1484           return;
1485         }
1486
1487       /* Compute the 4 cross operations.  */
1488       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
1489
1490       val[1] = (vr1.max != vr1.min)
1491                ? vrp_int_const_binop (code, vr0.min, vr1.max)
1492                : NULL_TREE;
1493
1494       val[2] = (vr0.max != vr0.min)
1495                ? vrp_int_const_binop (code, vr0.max, vr1.min)
1496                : NULL_TREE;
1497
1498       val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
1499                ? vrp_int_const_binop (code, vr0.max, vr1.max)
1500                : NULL_TREE;
1501
1502       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
1503          of VAL[i].  */
1504       min = val[0];
1505       max = val[0];
1506       for (i = 1; i < 4; i++)
1507         {
1508           if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1509               || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1510             break;
1511
1512           if (val[i])
1513             {
1514               if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (val[i]))
1515                 {
1516                   /* If we found an overflowed value, set MIN and MAX
1517                      to it so that we set the resulting range to
1518                      VARYING.  */
1519                   min = max = val[i];
1520                   break;
1521                 }
1522
1523               if (compare_values (val[i], min) == -1)
1524                 min = val[i];
1525
1526               if (compare_values (val[i], max) == 1)
1527                 max = val[i];
1528             }
1529         }
1530     }
1531   else if (code == MINUS_EXPR)
1532     {
1533       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
1534          VR_VARYING.  It would take more effort to compute a precise
1535          range for such a case.  For example, if we have op0 == 1 and
1536          op1 == 1 with their ranges both being ~[0,0], we would have
1537          op0 - op1 == 0, so we cannot claim that the difference is in
1538          ~[0,0].  Note that we are guaranteed to have
1539          vr0.type == vr1.type at this point.  */
1540       if (vr0.type == VR_ANTI_RANGE)
1541         {
1542           set_value_range_to_varying (vr);
1543           return;
1544         }
1545
1546       /* For MINUS_EXPR, apply the operation to the opposite ends of
1547          each range.  */
1548       min = vrp_int_const_binop (code, vr0.min, vr1.max);
1549       max = vrp_int_const_binop (code, vr0.max, vr1.min);
1550     }
1551   else if (code == BIT_AND_EXPR)
1552     {
1553       if (vr0.type == VR_RANGE
1554           && vr0.min == vr0.max
1555           && tree_expr_nonnegative_p (vr0.max)
1556           && TREE_CODE (vr0.max) == INTEGER_CST)
1557         {
1558           min = build_int_cst (TREE_TYPE (expr), 0);
1559           max = vr0.max;
1560         }
1561       else if (vr1.type == VR_RANGE
1562           && vr1.min == vr1.max
1563           && tree_expr_nonnegative_p (vr1.max)
1564           && TREE_CODE (vr1.max) == INTEGER_CST)
1565         {
1566           type = VR_RANGE;
1567           min = build_int_cst (TREE_TYPE (expr), 0);
1568           max = vr1.max;
1569         }
1570       else
1571         {
1572           set_value_range_to_varying (vr);
1573           return;
1574         }
1575     }
1576   else
1577     gcc_unreachable ();
1578
1579   /* If either MIN or MAX overflowed, then set the resulting range to
1580      VARYING.  */
1581   if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
1582       || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
1583     {
1584       set_value_range_to_varying (vr);
1585       return;
1586     }
1587
1588   cmp = compare_values (min, max);
1589   if (cmp == -2 || cmp == 1)
1590     {
1591       /* If the new range has its limits swapped around (MIN > MAX),
1592          then the operation caused one of them to wrap around, mark
1593          the new range VARYING.  */
1594       set_value_range_to_varying (vr);
1595     }
1596   else
1597     set_value_range (vr, type, min, max, NULL);
1598 }
1599
1600
1601 /* Extract range information from a unary expression EXPR based on
1602    the range of its operand and the expression code.  */
1603
1604 static void
1605 extract_range_from_unary_expr (value_range_t *vr, tree expr)
1606 {
1607   enum tree_code code = TREE_CODE (expr);
1608   tree min, max, op0;
1609   int cmp;
1610   value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
1611
1612   /* Refuse to operate on certain unary expressions for which we
1613      cannot easily determine a resulting range.  */
1614   if (code == FIX_TRUNC_EXPR
1615       || code == FIX_CEIL_EXPR
1616       || code == FIX_FLOOR_EXPR
1617       || code == FIX_ROUND_EXPR
1618       || code == FLOAT_EXPR
1619       || code == BIT_NOT_EXPR
1620       || code == NON_LVALUE_EXPR
1621       || code == CONJ_EXPR)
1622     {
1623       set_value_range_to_varying (vr);
1624       return;
1625     }
1626
1627   /* Get value ranges for the operand.  For constant operands, create
1628      a new value range with the operand to simplify processing.  */
1629   op0 = TREE_OPERAND (expr, 0);
1630   if (TREE_CODE (op0) == SSA_NAME)
1631     vr0 = *(get_value_range (op0));
1632   else if (is_gimple_min_invariant (op0))
1633     set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
1634   else
1635     set_value_range_to_varying (&vr0);
1636
1637   /* If VR0 is UNDEFINED, so is the result.  */
1638   if (vr0.type == VR_UNDEFINED)
1639     {
1640       set_value_range_to_undefined (vr);
1641       return;
1642     }
1643
1644   /* Refuse to operate on varying and symbolic ranges.  Also, if the
1645      operand is neither a pointer nor an integral type, set the
1646      resulting range to VARYING.  TODO, in some cases we may be able
1647      to derive anti-ranges (like nonzero values).  */
1648   if (vr0.type == VR_VARYING
1649       || (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
1650           && !POINTER_TYPE_P (TREE_TYPE (op0)))
1651       || symbolic_range_p (&vr0))
1652     {
1653       set_value_range_to_varying (vr);
1654       return;
1655     }
1656
1657   /* If the expression involves pointers, we are only interested in
1658      determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]).  */
1659   if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
1660     {
1661       if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
1662         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1663       else if (range_is_null (&vr0))
1664         set_value_range_to_null (vr, TREE_TYPE (expr));
1665       else
1666         set_value_range_to_varying (vr);
1667
1668       return;
1669     }
1670
1671   /* Handle unary expressions on integer ranges.  */
1672   if (code == NOP_EXPR || code == CONVERT_EXPR)
1673     {
1674       tree inner_type = TREE_TYPE (op0);
1675       tree outer_type = TREE_TYPE (expr);
1676
1677       /* If VR0 represents a simple range, then try to convert
1678          the min and max values for the range to the same type
1679          as OUTER_TYPE.  If the results compare equal to VR0's
1680          min and max values and the new min is still less than
1681          or equal to the new max, then we can safely use the newly
1682          computed range for EXPR.  This allows us to compute
1683          accurate ranges through many casts.  */
1684       if (vr0.type == VR_RANGE)
1685         {
1686           tree new_min, new_max;
1687
1688           /* Convert VR0's min/max to OUTER_TYPE.  */
1689           new_min = fold_convert (outer_type, vr0.min);
1690           new_max = fold_convert (outer_type, vr0.max);
1691
1692           /* Verify the new min/max values are gimple values and
1693              that they compare equal to VR0's min/max values.  */
1694           if (is_gimple_val (new_min)
1695               && is_gimple_val (new_max)
1696               && tree_int_cst_equal (new_min, vr0.min)
1697               && tree_int_cst_equal (new_max, vr0.max)
1698               && compare_values (new_min, new_max) <= 0
1699               && compare_values (new_min, new_max) >= -1)
1700             {
1701               set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
1702               return;
1703             }
1704         }
1705
1706       /* When converting types of different sizes, set the result to
1707          VARYING.  Things like sign extensions and precision loss may
1708          change the range.  For instance, if x_3 is of type 'long long
1709          int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
1710          is impossible to know at compile time whether y_5 will be
1711          ~[0, 0].  */
1712       if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
1713           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1714         {
1715           set_value_range_to_varying (vr);
1716           return;
1717         }
1718     }
1719
1720   /* Apply the operation to each end of the range and see what we end
1721      up with.  */
1722   if (code == NEGATE_EXPR
1723       && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1724     {
1725       /* NEGATE_EXPR flips the range around.  */
1726       min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1727              ? TYPE_MIN_VALUE (TREE_TYPE (expr))
1728              : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1729
1730       max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
1731              ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1732              : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1733
1734     }
1735   else if (code == NEGATE_EXPR
1736            && TYPE_UNSIGNED (TREE_TYPE (expr)))
1737     {
1738       if (!range_includes_zero_p (&vr0))
1739         {
1740           max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1741           min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1742         }
1743       else
1744         {
1745           if (range_is_null (&vr0))
1746             set_value_range_to_null (vr, TREE_TYPE (expr));
1747           else
1748             set_value_range_to_varying (vr);
1749           return;
1750         }
1751     }
1752   else if (code == ABS_EXPR
1753            && !TYPE_UNSIGNED (TREE_TYPE (expr)))
1754     {
1755       /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
1756          useful range.  */
1757       if (flag_wrapv
1758           && ((vr0.type == VR_RANGE
1759                && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1760               || (vr0.type == VR_ANTI_RANGE
1761                   && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
1762                   && !range_includes_zero_p (&vr0))))
1763         {
1764           set_value_range_to_varying (vr);
1765           return;
1766         }
1767
1768       /* ABS_EXPR may flip the range around, if the original range
1769          included negative values.  */
1770       min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
1771             ? TYPE_MAX_VALUE (TREE_TYPE (expr))
1772             : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1773
1774       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1775
1776       cmp = compare_values (min, max);
1777
1778       /* If a VR_ANTI_RANGEs contains zero, then we have
1779          ~[-INF, min(MIN, MAX)].  */
1780       if (vr0.type == VR_ANTI_RANGE)
1781         {
1782           if (range_includes_zero_p (&vr0))
1783             {
1784               tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
1785
1786               /* Take the lower of the two values.  */
1787               if (cmp != 1)
1788                 max = min;
1789
1790               /* Create ~[-INF, min (abs(MIN), abs(MAX))]
1791                  or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
1792                  flag_wrapv is set and the original anti-range doesn't include
1793                  TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE.  */
1794               min = (flag_wrapv && vr0.min != type_min_value
1795                      ? int_const_binop (PLUS_EXPR,
1796                                         type_min_value,
1797                                         integer_one_node, 0)
1798                      : type_min_value);
1799             }
1800           else
1801             {
1802               /* All else has failed, so create the range [0, INF], even for
1803                  flag_wrapv since TYPE_MIN_VALUE is in the original
1804                  anti-range.  */
1805               vr0.type = VR_RANGE;
1806               min = build_int_cst (TREE_TYPE (expr), 0);
1807               max = TYPE_MAX_VALUE (TREE_TYPE (expr));
1808             }
1809         }
1810
1811       /* If the range contains zero then we know that the minimum value in the
1812          range will be zero.  */
1813       else if (range_includes_zero_p (&vr0))
1814         {
1815           if (cmp == 1)
1816             max = min;
1817           min = build_int_cst (TREE_TYPE (expr), 0);
1818         }
1819       else
1820         {
1821           /* If the range was reversed, swap MIN and MAX.  */
1822           if (cmp == 1)
1823             {
1824               tree t = min;
1825               min = max;
1826               max = t;
1827             }
1828         }
1829     }
1830   else
1831     {
1832       /* Otherwise, operate on each end of the range.  */
1833       min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
1834       max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
1835     }
1836
1837   cmp = compare_values (min, max);
1838   if (cmp == -2 || cmp == 1)
1839     {
1840       /* If the new range has its limits swapped around (MIN > MAX),
1841          then the operation caused one of them to wrap around, mark
1842          the new range VARYING.  */
1843       set_value_range_to_varying (vr);
1844     }
1845   else
1846     set_value_range (vr, vr0.type, min, max, NULL);
1847 }
1848
1849
1850 /* Extract range information from a comparison expression EXPR based
1851    on the range of its operand and the expression code.  */
1852
1853 static void
1854 extract_range_from_comparison (value_range_t *vr, tree expr)
1855 {
1856   tree val = vrp_evaluate_conditional (expr, false);
1857   if (val)
1858     {
1859       /* Since this expression was found on the RHS of an assignment,
1860          its type may be different from _Bool.  Convert VAL to EXPR's
1861          type.  */
1862       val = fold_convert (TREE_TYPE (expr), val);
1863       set_value_range (vr, VR_RANGE, val, val, vr->equiv);
1864     }
1865   else
1866     set_value_range_to_varying (vr);
1867 }
1868
1869
1870 /* Try to compute a useful range out of expression EXPR and store it
1871    in *VR.  */
1872
1873 static void
1874 extract_range_from_expr (value_range_t *vr, tree expr)
1875 {
1876   enum tree_code code = TREE_CODE (expr);
1877
1878   if (code == ASSERT_EXPR)
1879     extract_range_from_assert (vr, expr);
1880   else if (code == SSA_NAME)
1881     extract_range_from_ssa_name (vr, expr);
1882   else if (TREE_CODE_CLASS (code) == tcc_binary
1883            || code == TRUTH_ANDIF_EXPR
1884            || code == TRUTH_ORIF_EXPR
1885            || code == TRUTH_AND_EXPR
1886            || code == TRUTH_OR_EXPR
1887            || code == TRUTH_XOR_EXPR)
1888     extract_range_from_binary_expr (vr, expr);
1889   else if (TREE_CODE_CLASS (code) == tcc_unary)
1890     extract_range_from_unary_expr (vr, expr);
1891   else if (TREE_CODE_CLASS (code) == tcc_comparison)
1892     extract_range_from_comparison (vr, expr);
1893   else if (is_gimple_min_invariant (expr))
1894     set_value_range (vr, VR_RANGE, expr, expr, NULL);
1895   else
1896     set_value_range_to_varying (vr);
1897
1898   /* If we got a varying range from the tests above, try a final
1899      time to derive a nonnegative or nonzero range.  This time
1900      relying primarily on generic routines in fold in conjunction
1901      with range data.  */
1902   if (vr->type == VR_VARYING)
1903     {
1904       if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
1905           && vrp_expr_computes_nonnegative (expr))
1906         set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
1907       else if (vrp_expr_computes_nonzero (expr))
1908         set_value_range_to_nonnull (vr, TREE_TYPE (expr));
1909     }
1910 }
1911
1912 /* Given a range VR, a LOOP and a variable VAR, determine whether it
1913    would be profitable to adjust VR using scalar evolution information
1914    for VAR.  If so, update VR with the new limits.  */
1915
1916 static void
1917 adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
1918                         tree var)
1919 {
1920   tree init, step, chrec;
1921   bool init_is_max, unknown_max;
1922
1923   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
1924      better opportunities than a regular range, but I'm not sure.  */
1925   if (vr->type == VR_ANTI_RANGE)
1926     return;
1927
1928   chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
1929   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1930     return;
1931
1932   init = initial_condition_in_loop_num (chrec, loop->num);
1933   step = evolution_part_in_loop_num (chrec, loop->num);
1934
1935   /* If STEP is symbolic, we can't know whether INIT will be the
1936      minimum or maximum value in the range.  */
1937   if (step == NULL_TREE
1938       || !is_gimple_min_invariant (step))
1939     return;
1940
1941   /* Do not adjust ranges when chrec may wrap.  */
1942   if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
1943                              current_loops->parray[CHREC_VARIABLE (chrec)],
1944                              &init_is_max, &unknown_max)
1945       || unknown_max)
1946     return;
1947
1948   if (!POINTER_TYPE_P (TREE_TYPE (init))
1949       && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
1950     {
1951       /* For VARYING or UNDEFINED ranges, just about anything we get
1952          from scalar evolutions should be better.  */
1953       tree min = TYPE_MIN_VALUE (TREE_TYPE (init));
1954       tree max = TYPE_MAX_VALUE (TREE_TYPE (init));
1955
1956       if (init_is_max)
1957         max = init;
1958       else
1959         min = init;
1960
1961       /* If we would create an invalid range, then just assume we
1962          know absolutely nothing.  This may be over-conservative,
1963          but it's clearly safe.  */
1964       if (compare_values (min, max) == 1)
1965         return;
1966
1967       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
1968     }
1969   else if (vr->type == VR_RANGE)
1970     {
1971       tree min = vr->min;
1972       tree max = vr->max;
1973
1974       if (init_is_max)
1975         {
1976           /* INIT is the maximum value.  If INIT is lower than VR->MAX
1977              but no smaller than VR->MIN, set VR->MAX to INIT.  */
1978           if (compare_values (init, max) == -1)
1979             {
1980               max = init;
1981
1982               /* If we just created an invalid range with the minimum
1983                  greater than the maximum, take the minimum all the
1984                  way to -INF.  */
1985               if (compare_values (min, max) == 1)
1986                 min = TYPE_MIN_VALUE (TREE_TYPE (min));
1987             }
1988         }
1989       else
1990         {
1991           /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
1992           if (compare_values (init, min) == 1)
1993             {
1994               min = init;
1995
1996               /* If we just created an invalid range with the minimum
1997                  greater than the maximum, take the maximum all the
1998                  way to +INF.  */
1999               if (compare_values (min, max) == 1)
2000                 max = TYPE_MAX_VALUE (TREE_TYPE (max));
2001             }
2002         }
2003
2004       set_value_range (vr, VR_RANGE, min, max, vr->equiv);
2005     }
2006 }
2007
2008
2009 /* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
2010
2011    - Return BOOLEAN_TRUE_NODE if VR0 COMP VR1 always returns true for
2012      all the values in the ranges.
2013
2014    - Return BOOLEAN_FALSE_NODE if the comparison always returns false.
2015
2016    - Return NULL_TREE if it is not always possible to determine the
2017      value of the comparison.  */
2018
2019
2020 static tree
2021 compare_ranges (enum tree_code comp, value_range_t *vr0, value_range_t *vr1)
2022 {
2023   /* VARYING or UNDEFINED ranges cannot be compared.  */
2024   if (vr0->type == VR_VARYING
2025       || vr0->type == VR_UNDEFINED
2026       || vr1->type == VR_VARYING
2027       || vr1->type == VR_UNDEFINED)
2028     return NULL_TREE;
2029
2030   /* Anti-ranges need to be handled separately.  */
2031   if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
2032     {
2033       /* If both are anti-ranges, then we cannot compute any
2034          comparison.  */
2035       if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
2036         return NULL_TREE;
2037
2038       /* These comparisons are never statically computable.  */
2039       if (comp == GT_EXPR
2040           || comp == GE_EXPR
2041           || comp == LT_EXPR
2042           || comp == LE_EXPR)
2043         return NULL_TREE;
2044
2045       /* Equality can be computed only between a range and an
2046          anti-range.  ~[VAL1, VAL2] == [VAL1, VAL2] is always false.  */
2047       if (vr0->type == VR_RANGE)
2048         {
2049           /* To simplify processing, make VR0 the anti-range.  */
2050           value_range_t *tmp = vr0;
2051           vr0 = vr1;
2052           vr1 = tmp;
2053         }
2054
2055       gcc_assert (comp == NE_EXPR || comp == EQ_EXPR);
2056
2057       if (compare_values (vr0->min, vr1->min) == 0
2058           && compare_values (vr0->max, vr1->max) == 0)
2059         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2060
2061       return NULL_TREE;
2062     }
2063
2064   /* Simplify processing.  If COMP is GT_EXPR or GE_EXPR, switch the
2065      operands around and change the comparison code.  */
2066   if (comp == GT_EXPR || comp == GE_EXPR)
2067     {
2068       value_range_t *tmp;
2069       comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
2070       tmp = vr0;
2071       vr0 = vr1;
2072       vr1 = tmp;
2073     }
2074
2075   if (comp == EQ_EXPR)
2076     {
2077       /* Equality may only be computed if both ranges represent
2078          exactly one value.  */
2079       if (compare_values (vr0->min, vr0->max) == 0
2080           && compare_values (vr1->min, vr1->max) == 0)
2081         {
2082           int cmp_min = compare_values (vr0->min, vr1->min);
2083           int cmp_max = compare_values (vr0->max, vr1->max);
2084           if (cmp_min == 0 && cmp_max == 0)
2085             return boolean_true_node;
2086           else if (cmp_min != -2 && cmp_max != -2)
2087             return boolean_false_node;
2088         }
2089       /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1.  */
2090       else if (compare_values (vr0->min, vr1->max) == 1
2091                || compare_values (vr1->min, vr0->max) == 1)
2092         return boolean_false_node;
2093
2094       return NULL_TREE;
2095     }
2096   else if (comp == NE_EXPR)
2097     {
2098       int cmp1, cmp2;
2099
2100       /* If VR0 is completely to the left or completely to the right
2101          of VR1, they are always different.  Notice that we need to
2102          make sure that both comparisons yield similar results to
2103          avoid comparing values that cannot be compared at
2104          compile-time.  */
2105       cmp1 = compare_values (vr0->max, vr1->min);
2106       cmp2 = compare_values (vr0->min, vr1->max);
2107       if ((cmp1 == -1 && cmp2 == -1) || (cmp1 == 1 && cmp2 == 1))
2108         return boolean_true_node;
2109
2110       /* If VR0 and VR1 represent a single value and are identical,
2111          return false.  */
2112       else if (compare_values (vr0->min, vr0->max) == 0
2113                && compare_values (vr1->min, vr1->max) == 0
2114                && compare_values (vr0->min, vr1->min) == 0
2115                && compare_values (vr0->max, vr1->max) == 0)
2116         return boolean_false_node;
2117
2118       /* Otherwise, they may or may not be different.  */
2119       else
2120         return NULL_TREE;
2121     }
2122   else if (comp == LT_EXPR || comp == LE_EXPR)
2123     {
2124       int tst;
2125
2126       /* If VR0 is to the left of VR1, return true.  */
2127       tst = compare_values (vr0->max, vr1->min);
2128       if ((comp == LT_EXPR && tst == -1)
2129           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2130         return boolean_true_node;
2131
2132       /* If VR0 is to the right of VR1, return false.  */
2133       tst = compare_values (vr0->min, vr1->max);
2134       if ((comp == LT_EXPR && (tst == 0 || tst == 1))
2135           || (comp == LE_EXPR && tst == 1))
2136         return boolean_false_node;
2137
2138       /* Otherwise, we don't know.  */
2139       return NULL_TREE;
2140     }
2141
2142   gcc_unreachable ();
2143 }
2144
2145
2146 /* Given a value range VR, a value VAL and a comparison code COMP, return
2147    BOOLEAN_TRUE_NODE if VR COMP VAL always returns true for all the
2148    values in VR.  Return BOOLEAN_FALSE_NODE if the comparison
2149    always returns false.  Return NULL_TREE if it is not always
2150    possible to determine the value of the comparison.  */
2151
2152 static tree
2153 compare_range_with_value (enum tree_code comp, value_range_t *vr, tree val)
2154 {
2155   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
2156     return NULL_TREE;
2157
2158   /* Anti-ranges need to be handled separately.  */
2159   if (vr->type == VR_ANTI_RANGE)
2160     {
2161       /* For anti-ranges, the only predicates that we can compute at
2162          compile time are equality and inequality.  */
2163       if (comp == GT_EXPR
2164           || comp == GE_EXPR
2165           || comp == LT_EXPR
2166           || comp == LE_EXPR)
2167         return NULL_TREE;
2168
2169       /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2.  */
2170       if (value_inside_range (val, vr) == 1)
2171         return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
2172
2173       return NULL_TREE;
2174     }
2175
2176   if (comp == EQ_EXPR)
2177     {
2178       /* EQ_EXPR may only be computed if VR represents exactly
2179          one value.  */
2180       if (compare_values (vr->min, vr->max) == 0)
2181         {
2182           int cmp = compare_values (vr->min, val);
2183           if (cmp == 0)
2184             return boolean_true_node;
2185           else if (cmp == -1 || cmp == 1 || cmp == 2)
2186             return boolean_false_node;
2187         }
2188       else if (compare_values (val, vr->min) == -1
2189                || compare_values (vr->max, val) == -1)
2190         return boolean_false_node;
2191
2192       return NULL_TREE;
2193     }
2194   else if (comp == NE_EXPR)
2195     {
2196       /* If VAL is not inside VR, then they are always different.  */
2197       if (compare_values (vr->max, val) == -1
2198           || compare_values (vr->min, val) == 1)
2199         return boolean_true_node;
2200
2201       /* If VR represents exactly one value equal to VAL, then return
2202          false.  */
2203       if (compare_values (vr->min, vr->max) == 0
2204           && compare_values (vr->min, val) == 0)
2205         return boolean_false_node;
2206
2207       /* Otherwise, they may or may not be different.  */
2208       return NULL_TREE;
2209     }
2210   else if (comp == LT_EXPR || comp == LE_EXPR)
2211     {
2212       int tst;
2213
2214       /* If VR is to the left of VAL, return true.  */
2215       tst = compare_values (vr->max, val);
2216       if ((comp == LT_EXPR && tst == -1)
2217           || (comp == LE_EXPR && (tst == -1 || tst == 0)))
2218         return boolean_true_node;
2219
2220       /* If VR is to the right of VAL, return false.  */
2221       tst = compare_values (vr->min, val);
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   else if (comp == GT_EXPR || comp == GE_EXPR)
2230     {
2231       int tst;
2232
2233       /* If VR is to the right of VAL, return true.  */
2234       tst = compare_values (vr->min, val);
2235       if ((comp == GT_EXPR && tst == 1)
2236           || (comp == GE_EXPR && (tst == 0 || tst == 1)))
2237         return boolean_true_node;
2238
2239       /* If VR is to the left of VAL, return false.  */
2240       tst = compare_values (vr->max, val);
2241       if ((comp == GT_EXPR && (tst == -1 || tst == 0))
2242           || (comp == GE_EXPR && tst == -1))
2243         return boolean_false_node;
2244
2245       /* Otherwise, we don't know.  */
2246       return NULL_TREE;
2247     }
2248
2249   gcc_unreachable ();
2250 }
2251
2252
2253 /* Debugging dumps.  */
2254
2255 void dump_value_range (FILE *, value_range_t *);
2256 void debug_value_range (value_range_t *);
2257 void dump_all_value_ranges (FILE *);
2258 void debug_all_value_ranges (void);
2259 void dump_vr_equiv (FILE *, bitmap);
2260 void debug_vr_equiv (bitmap);
2261
2262
2263 /* Dump value range VR to FILE.  */
2264
2265 void
2266 dump_value_range (FILE *file, value_range_t *vr)
2267 {
2268   if (vr == NULL)
2269     fprintf (file, "[]");
2270   else if (vr->type == VR_UNDEFINED)
2271     fprintf (file, "UNDEFINED");
2272   else if (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
2273     {
2274       tree type = TREE_TYPE (vr->min);
2275
2276       fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
2277
2278       if (INTEGRAL_TYPE_P (type)
2279           && !TYPE_UNSIGNED (type)
2280           && vr->min == TYPE_MIN_VALUE (type))
2281         fprintf (file, "-INF");
2282       else
2283         print_generic_expr (file, vr->min, 0);
2284
2285       fprintf (file, ", ");
2286
2287       if (INTEGRAL_TYPE_P (type)
2288           && vr->max == TYPE_MAX_VALUE (type))
2289         fprintf (file, "+INF");
2290       else
2291         print_generic_expr (file, vr->max, 0);
2292
2293       fprintf (file, "]");
2294
2295       if (vr->equiv)
2296         {
2297           bitmap_iterator bi;
2298           unsigned i, c = 0;
2299
2300           fprintf (file, "  EQUIVALENCES: { ");
2301
2302           EXECUTE_IF_SET_IN_BITMAP (vr->equiv, 0, i, bi)
2303             {
2304               print_generic_expr (file, ssa_name (i), 0);
2305               fprintf (file, " ");
2306               c++;
2307             }
2308
2309           fprintf (file, "} (%u elements)", c);
2310         }
2311     }
2312   else if (vr->type == VR_VARYING)
2313     fprintf (file, "VARYING");
2314   else
2315     fprintf (file, "INVALID RANGE");
2316 }
2317
2318
2319 /* Dump value range VR to stderr.  */
2320
2321 void
2322 debug_value_range (value_range_t *vr)
2323 {
2324   dump_value_range (stderr, vr);
2325 }
2326
2327
2328 /* Dump value ranges of all SSA_NAMEs to FILE.  */
2329
2330 void
2331 dump_all_value_ranges (FILE *file)
2332 {
2333   size_t i;
2334
2335   for (i = 0; i < num_ssa_names; i++)
2336     {
2337       if (vr_value[i])
2338         {
2339           print_generic_expr (file, ssa_name (i), 0);
2340           fprintf (file, ": ");
2341           dump_value_range (file, vr_value[i]);
2342           fprintf (file, "\n");
2343         }
2344     }
2345
2346   fprintf (file, "\n");
2347 }
2348
2349
2350 /* Dump all value ranges to stderr.  */
2351
2352 void
2353 debug_all_value_ranges (void)
2354 {
2355   dump_all_value_ranges (stderr);
2356 }
2357
2358
2359 /* Given a COND_EXPR COND of the form 'V OP W', and an SSA name V,
2360    create a new SSA name N and return the assertion assignment
2361    'V = ASSERT_EXPR <V, V OP W>'.  */
2362
2363 static tree
2364 build_assert_expr_for (tree cond, tree v)
2365 {
2366   tree n, assertion;
2367
2368   gcc_assert (TREE_CODE (v) == SSA_NAME);
2369   n = duplicate_ssa_name (v, NULL_TREE);
2370
2371   if (COMPARISON_CLASS_P (cond))
2372     {
2373       tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
2374       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, a);
2375     }
2376   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2377     {
2378       /* Given !V, build the assignment N = false.  */
2379       tree op0 = TREE_OPERAND (cond, 0);
2380       gcc_assert (op0 == v);
2381       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
2382     }
2383   else if (TREE_CODE (cond) == SSA_NAME)
2384     {
2385       /* Given V, build the assignment N = true.  */
2386       gcc_assert (v == cond);
2387       assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
2388     }
2389   else
2390     gcc_unreachable ();
2391
2392   SSA_NAME_DEF_STMT (n) = assertion;
2393
2394   /* The new ASSERT_EXPR, creates a new SSA name that replaces the
2395      operand of the ASSERT_EXPR. Register the new name and the old one
2396      in the replacement table so that we can fix the SSA web after
2397      adding all the ASSERT_EXPRs.  */
2398   register_new_name_mapping (n, v);
2399
2400   return assertion;
2401 }
2402
2403
2404 /* Return false if EXPR is a predicate expression involving floating
2405    point values.  */
2406
2407 static inline bool
2408 fp_predicate (tree expr)
2409 {
2410   return (COMPARISON_CLASS_P (expr)
2411           && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
2412 }
2413
2414
2415 /* If the range of values taken by OP can be inferred after STMT executes,
2416    return the comparison code (COMP_CODE_P) and value (VAL_P) that
2417    describes the inferred range.  Return true if a range could be
2418    inferred.  */
2419
2420 static bool
2421 infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
2422 {
2423   *val_p = NULL_TREE;
2424   *comp_code_p = ERROR_MARK;
2425
2426   /* Do not attempt to infer anything in names that flow through
2427      abnormal edges.  */
2428   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
2429     return false;
2430
2431   /* Similarly, don't infer anything from statements that may throw
2432      exceptions.  */
2433   if (tree_could_throw_p (stmt))
2434     return false;
2435
2436   /* If STMT is the last statement of a basic block with no
2437      successors, there is no point inferring anything about any of its
2438      operands.  We would not be able to find a proper insertion point
2439      for the assertion, anyway.  */
2440   if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
2441     return false;
2442
2443   /* We can only assume that a pointer dereference will yield
2444      non-NULL if -fdelete-null-pointer-checks is enabled.  */
2445   if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
2446     {
2447       bool is_store;
2448       unsigned num_uses, num_derefs;
2449
2450       count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
2451       if (num_derefs > 0)
2452         {
2453           *val_p = build_int_cst (TREE_TYPE (op), 0);
2454           *comp_code_p = NE_EXPR;
2455           return true;
2456         }
2457     }
2458
2459   return false;
2460 }
2461
2462
2463 void dump_asserts_for (FILE *, tree);
2464 void debug_asserts_for (tree);
2465 void dump_all_asserts (FILE *);
2466 void debug_all_asserts (void);
2467
2468 /* Dump all the registered assertions for NAME to FILE.  */
2469
2470 void
2471 dump_asserts_for (FILE *file, tree name)
2472 {
2473   assert_locus_t loc;
2474
2475   fprintf (file, "Assertions to be inserted for ");
2476   print_generic_expr (file, name, 0);
2477   fprintf (file, "\n");
2478
2479   loc = asserts_for[SSA_NAME_VERSION (name)];
2480   while (loc)
2481     {
2482       fprintf (file, "\t");
2483       print_generic_expr (file, bsi_stmt (loc->si), 0);
2484       fprintf (file, "\n\tBB #%d", loc->bb->index);
2485       if (loc->e)
2486         {
2487           fprintf (file, "\n\tEDGE %d->%d", loc->e->src->index,
2488                    loc->e->dest->index);
2489           dump_edge_info (file, loc->e, 0);
2490         }
2491       fprintf (file, "\n\tPREDICATE: ");
2492       print_generic_expr (file, name, 0);
2493       fprintf (file, " %s ", tree_code_name[(int)loc->comp_code]);
2494       print_generic_expr (file, loc->val, 0);
2495       fprintf (file, "\n\n");
2496       loc = loc->next;
2497     }
2498
2499   fprintf (file, "\n");
2500 }
2501
2502
2503 /* Dump all the registered assertions for NAME to stderr.  */
2504
2505 void
2506 debug_asserts_for (tree name)
2507 {
2508   dump_asserts_for (stderr, name);
2509 }
2510
2511
2512 /* Dump all the registered assertions for all the names to FILE.  */
2513
2514 void
2515 dump_all_asserts (FILE *file)
2516 {
2517   unsigned i;
2518   bitmap_iterator bi;
2519
2520   fprintf (file, "\nASSERT_EXPRs to be inserted\n\n");
2521   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
2522     dump_asserts_for (file, ssa_name (i));
2523   fprintf (file, "\n");
2524 }
2525
2526
2527 /* Dump all the registered assertions for all the names to stderr.  */
2528
2529 void
2530 debug_all_asserts (void)
2531 {
2532   dump_all_asserts (stderr);
2533 }
2534
2535
2536 /* If NAME doesn't have an ASSERT_EXPR registered for asserting
2537    'NAME COMP_CODE VAL' at a location that dominates block BB or
2538    E->DEST, then register this location as a possible insertion point
2539    for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
2540
2541    BB, E and SI provide the exact insertion point for the new
2542    ASSERT_EXPR.  If BB is NULL, then the ASSERT_EXPR is to be inserted
2543    on edge E.  Otherwise, if E is NULL, the ASSERT_EXPR is inserted on
2544    BB.  If SI points to a COND_EXPR or a SWITCH_EXPR statement, then E
2545    must not be NULL.  */
2546
2547 static void
2548 register_new_assert_for (tree name,
2549                          enum tree_code comp_code,
2550                          tree val,
2551                          basic_block bb,
2552                          edge e,
2553                          block_stmt_iterator si)
2554 {
2555   assert_locus_t n, loc, last_loc;
2556   bool found;
2557   basic_block dest_bb;
2558
2559 #if defined ENABLE_CHECKING
2560   gcc_assert (bb == NULL || e == NULL);
2561
2562   if (e == NULL)
2563     gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
2564                 && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
2565 #endif
2566
2567   /* The new assertion A will be inserted at BB or E.  We need to
2568      determine if the new location is dominated by a previously
2569      registered location for A.  If we are doing an edge insertion,
2570      assume that A will be inserted at E->DEST.  Note that this is not
2571      necessarily true.
2572
2573      If E is a critical edge, it will be split.  But even if E is
2574      split, the new block will dominate the same set of blocks that
2575      E->DEST dominates.
2576
2577      The reverse, however, is not true, blocks dominated by E->DEST
2578      will not be dominated by the new block created to split E.  So,
2579      if the insertion location is on a critical edge, we will not use
2580      the new location to move another assertion previously registered
2581      at a block dominated by E->DEST.  */
2582   dest_bb = (bb) ? bb : e->dest;
2583
2584   /* If NAME already has an ASSERT_EXPR registered for COMP_CODE and
2585      VAL at a block dominating DEST_BB, then we don't need to insert a new
2586      one.  Similarly, if the same assertion already exists at a block
2587      dominated by DEST_BB and the new location is not on a critical
2588      edge, then update the existing location for the assertion (i.e.,
2589      move the assertion up in the dominance tree).
2590
2591      Note, this is implemented as a simple linked list because there
2592      should not be more than a handful of assertions registered per
2593      name.  If this becomes a performance problem, a table hashed by
2594      COMP_CODE and VAL could be implemented.  */
2595   loc = asserts_for[SSA_NAME_VERSION (name)];
2596   last_loc = loc;
2597   found = false;
2598   while (loc)
2599     {
2600       if (loc->comp_code == comp_code
2601           && (loc->val == val
2602               || operand_equal_p (loc->val, val, 0)))
2603         {
2604           /* If the assertion NAME COMP_CODE VAL has already been
2605              registered at a basic block that dominates DEST_BB, then
2606              we don't need to insert the same assertion again.  Note
2607              that we don't check strict dominance here to avoid
2608              replicating the same assertion inside the same basic
2609              block more than once (e.g., when a pointer is
2610              dereferenced several times inside a block).
2611
2612              An exception to this rule are edge insertions.  If the
2613              new assertion is to be inserted on edge E, then it will
2614              dominate all the other insertions that we may want to
2615              insert in DEST_BB.  So, if we are doing an edge
2616              insertion, don't do this dominance check.  */
2617           if (e == NULL
2618               && dominated_by_p (CDI_DOMINATORS, dest_bb, loc->bb))
2619             return;
2620
2621           /* Otherwise, if E is not a critical edge and DEST_BB
2622              dominates the existing location for the assertion, move
2623              the assertion up in the dominance tree by updating its
2624              location information.  */
2625           if ((e == NULL || !EDGE_CRITICAL_P (e))
2626               && dominated_by_p (CDI_DOMINATORS, loc->bb, dest_bb))
2627             {
2628               loc->bb = dest_bb;
2629               loc->e = e;
2630               loc->si = si;
2631               return;
2632             }
2633         }
2634
2635       /* Update the last node of the list and move to the next one.  */
2636       last_loc = loc;
2637       loc = loc->next;
2638     }
2639
2640   /* If we didn't find an assertion already registered for
2641      NAME COMP_CODE VAL, add a new one at the end of the list of
2642      assertions associated with NAME.  */
2643   n = XNEW (struct assert_locus_d);
2644   n->bb = dest_bb;
2645   n->e = e;
2646   n->si = si;
2647   n->comp_code = comp_code;
2648   n->val = val;
2649   n->next = NULL;
2650
2651   if (last_loc)
2652     last_loc->next = n;
2653   else
2654     asserts_for[SSA_NAME_VERSION (name)] = n;
2655
2656   bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
2657 }
2658
2659
2660 /* Try to register an edge assertion for SSA name NAME on edge E for
2661    the conditional jump pointed to by SI.  Return true if an assertion
2662    for NAME could be registered.  */
2663
2664 static bool
2665 register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
2666 {
2667   tree val, stmt;
2668   enum tree_code comp_code;
2669
2670   stmt = bsi_stmt (si);
2671
2672   /* Do not attempt to infer anything in names that flow through
2673      abnormal edges.  */
2674   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
2675     return false;
2676
2677   /* If NAME was not found in the sub-graph reachable from E, then
2678      there's nothing to do.  */
2679   if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
2680     return false;
2681
2682   /* We found a use of NAME in the sub-graph rooted at E->DEST.
2683      Register an assertion for NAME according to the value that NAME
2684      takes on edge E.  */
2685   if (TREE_CODE (stmt) == COND_EXPR)
2686     {
2687       /* If BB ends in a COND_EXPR then NAME then we should insert
2688          the original predicate on EDGE_TRUE_VALUE and the
2689          opposite predicate on EDGE_FALSE_VALUE.  */
2690       tree cond = COND_EXPR_COND (stmt);
2691       bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
2692
2693       /* Predicates may be a single SSA name or NAME OP VAL.  */
2694       if (cond == name)
2695         {
2696           /* If the predicate is a name, it must be NAME, in which
2697              case we create the predicate NAME == true or
2698              NAME == false accordingly.  */
2699           comp_code = EQ_EXPR;
2700           val = (is_else_edge) ? boolean_false_node : boolean_true_node;
2701         }
2702       else
2703         {
2704           /* Otherwise, we have a comparison of the form NAME COMP VAL
2705              or VAL COMP NAME.  */
2706           if (name == TREE_OPERAND (cond, 1))
2707             {
2708               /* If the predicate is of the form VAL COMP NAME, flip
2709                  COMP around because we need to register NAME as the
2710                  first operand in the predicate.  */
2711               comp_code = swap_tree_comparison (TREE_CODE (cond));
2712               val = TREE_OPERAND (cond, 0);
2713             }
2714           else
2715             {
2716               /* The comparison is of the form NAME COMP VAL, so the
2717                  comparison code remains unchanged.  */
2718               comp_code = TREE_CODE (cond);
2719               val = TREE_OPERAND (cond, 1);
2720             }
2721
2722           /* If we are inserting the assertion on the ELSE edge, we
2723              need to invert the sign comparison.  */
2724           if (is_else_edge)
2725             comp_code = invert_tree_comparison (comp_code, 0);
2726
2727           /* Do not register always-false predicates.  FIXME, this
2728              works around a limitation in fold() when dealing with
2729              enumerations.  Given 'enum { N1, N2 } x;', fold will not
2730              fold 'if (x > N2)' to 'if (0)'.  */
2731           if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
2732               && (INTEGRAL_TYPE_P (TREE_TYPE (val))
2733                   || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
2734             {
2735               tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
2736               tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
2737
2738               if (comp_code == GT_EXPR && compare_values (val, max) == 0)
2739                 return false;
2740
2741               if (comp_code == LT_EXPR && compare_values (val, min) == 0)
2742                 return false;
2743             }
2744         }
2745     }
2746   else
2747     {
2748       /* FIXME.  Handle SWITCH_EXPR.  */
2749       gcc_unreachable ();
2750     }
2751
2752   register_new_assert_for (name, comp_code, val, NULL, e, si);
2753   return true;
2754 }
2755
2756
2757 static bool find_assert_locations (basic_block bb);
2758
2759 /* Determine whether the outgoing edges of BB should receive an
2760    ASSERT_EXPR for each of the operands of BB's last statement.  The
2761    last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
2762
2763    If any of the sub-graphs rooted at BB have an interesting use of
2764    the predicate operands, an assert location node is added to the
2765    list of assertions for the corresponding operands.  */
2766
2767 static bool
2768 find_conditional_asserts (basic_block bb)
2769 {
2770   bool need_assert;
2771   block_stmt_iterator last_si;
2772   tree op, last;
2773   edge_iterator ei;
2774   edge e;
2775   ssa_op_iter iter;
2776
2777   need_assert = false;
2778   last_si = bsi_last (bb);
2779   last = bsi_stmt (last_si);
2780
2781   /* Look for uses of the operands in each of the sub-graphs
2782      rooted at BB.  We need to check each of the outgoing edges
2783      separately, so that we know what kind of ASSERT_EXPR to
2784      insert.  */
2785   FOR_EACH_EDGE (e, ei, bb->succs)
2786     {
2787       if (e->dest == bb)
2788         continue;
2789
2790       /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
2791          Otherwise, when we finish traversing each of the sub-graphs, we
2792          won't know whether the variables were found in the sub-graphs or
2793          if they had been found in a block upstream from BB.
2794
2795          This is actually a bad idea is some cases, particularly jump
2796          threading.  Consider a CFG like the following:
2797
2798                     0
2799                    /|
2800                   1 |
2801                    \|
2802                     2
2803                    / \
2804                   3   4
2805
2806          Assume that one or more operands in the conditional at the
2807          end of block 0 are used in a conditional in block 2, but not
2808          anywhere in block 1.  In this case we will not insert any
2809          assert statements in block 1, which may cause us to miss
2810          opportunities to optimize, particularly for jump threading.  */
2811       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2812         RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2813
2814       /* Traverse the strictly dominated sub-graph rooted at E->DEST
2815          to determine if any of the operands in the conditional
2816          predicate are used.  */
2817       if (e->dest != bb)
2818         need_assert |= find_assert_locations (e->dest);
2819
2820       /* Register the necessary assertions for each operand in the
2821          conditional predicate.  */
2822       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2823         need_assert |= register_edge_assert_for (op, e, last_si);
2824     }
2825
2826   /* Finally, indicate that we have found the operands in the
2827      conditional.  */
2828   FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
2829     SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2830
2831   return need_assert;
2832 }
2833
2834
2835 /* Traverse all the statements in block BB looking for statements that
2836    may generate useful assertions for the SSA names in their operand.
2837    If a statement produces a useful assertion A for name N_i, then the
2838    list of assertions already generated for N_i is scanned to
2839    determine if A is actually needed.
2840
2841    If N_i already had the assertion A at a location dominating the
2842    current location, then nothing needs to be done.  Otherwise, the
2843    new location for A is recorded instead.
2844
2845    1- For every statement S in BB, all the variables used by S are
2846       added to bitmap FOUND_IN_SUBGRAPH.
2847
2848    2- If statement S uses an operand N in a way that exposes a known
2849       value range for N, then if N was not already generated by an
2850       ASSERT_EXPR, create a new assert location for N.  For instance,
2851       if N is a pointer and the statement dereferences it, we can
2852       assume that N is not NULL.
2853
2854    3- COND_EXPRs are a special case of #2.  We can derive range
2855       information from the predicate but need to insert different
2856       ASSERT_EXPRs for each of the sub-graphs rooted at the
2857       conditional block.  If the last statement of BB is a conditional
2858       expression of the form 'X op Y', then
2859
2860       a) Remove X and Y from the set FOUND_IN_SUBGRAPH.
2861
2862       b) If the conditional is the only entry point to the sub-graph
2863          corresponding to the THEN_CLAUSE, recurse into it.  On
2864          return, if X and/or Y are marked in FOUND_IN_SUBGRAPH, then
2865          an ASSERT_EXPR is added for the corresponding variable.
2866
2867       c) Repeat step (b) on the ELSE_CLAUSE.
2868
2869       d) Mark X and Y in FOUND_IN_SUBGRAPH.
2870
2871       For instance,
2872
2873             if (a == 9)
2874               b = a;
2875             else
2876               b = c + 1;
2877
2878       In this case, an assertion on the THEN clause is useful to
2879       determine that 'a' is always 9 on that edge.  However, an assertion
2880       on the ELSE clause would be unnecessary.
2881
2882    4- If BB does not end in a conditional expression, then we recurse
2883       into BB's dominator children.
2884
2885    At the end of the recursive traversal, every SSA name will have a
2886    list of locations where ASSERT_EXPRs should be added.  When a new
2887    location for name N is found, it is registered by calling
2888    register_new_assert_for.  That function keeps track of all the
2889    registered assertions to prevent adding unnecessary assertions.
2890    For instance, if a pointer P_4 is dereferenced more than once in a
2891    dominator tree, only the location dominating all the dereference of
2892    P_4 will receive an ASSERT_EXPR.
2893
2894    If this function returns true, then it means that there are names
2895    for which we need to generate ASSERT_EXPRs.  Those assertions are
2896    inserted by process_assert_insertions.
2897
2898    TODO.  Handle SWITCH_EXPR.  */
2899
2900 static bool
2901 find_assert_locations (basic_block bb)
2902 {
2903   block_stmt_iterator si;
2904   tree last, phi;
2905   bool need_assert;
2906   basic_block son;
2907
2908   if (TEST_BIT (blocks_visited, bb->index))
2909     return false;
2910
2911   SET_BIT (blocks_visited, bb->index);
2912
2913   need_assert = false;
2914
2915   /* Traverse all PHI nodes in BB marking used operands.  */
2916   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2917     {
2918       use_operand_p arg_p;
2919       ssa_op_iter i;
2920
2921       FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
2922         {
2923           tree arg = USE_FROM_PTR (arg_p);
2924           if (TREE_CODE (arg) == SSA_NAME)
2925             {
2926               gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
2927               SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
2928             }
2929         }
2930     }
2931
2932   /* Traverse all the statements in BB marking used names and looking
2933      for statements that may infer assertions for their used operands.  */
2934   last = NULL_TREE;
2935   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2936     {
2937       tree stmt, op;
2938       ssa_op_iter i;
2939
2940       stmt = bsi_stmt (si);
2941
2942       /* See if we can derive an assertion for any of STMT's operands.  */
2943       FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
2944         {
2945           tree value;
2946           enum tree_code comp_code;
2947
2948           /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
2949              the sub-graph of a conditional block, when we return from
2950              this recursive walk, our parent will use the
2951              FOUND_IN_SUBGRAPH bitset to determine if one of the
2952              operands it was looking for was present in the sub-graph.  */
2953           SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
2954
2955           /* If OP is used in such a way that we can infer a value
2956              range for it, and we don't find a previous assertion for
2957              it, create a new assertion location node for OP.  */
2958           if (infer_value_range (stmt, op, &comp_code, &value))
2959             {
2960               /* If we are able to infer a non-zero value range for OP,
2961                  then walk backwards through the use-def chain to see if OP
2962                  was set via a typecast.
2963
2964                  If so, then we can also infer a nonzero value range
2965                  for the operand of the NOP_EXPR.  */
2966               if (comp_code == NE_EXPR && integer_zerop (value))
2967                 {
2968                   tree t = op;
2969                   tree def_stmt = SSA_NAME_DEF_STMT (t);
2970
2971                   while (TREE_CODE (def_stmt) == MODIFY_EXPR
2972                          && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR
2973                          && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME
2974                          && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))))
2975                     {
2976                       t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
2977                       def_stmt = SSA_NAME_DEF_STMT (t);
2978
2979                       /* Note we want to register the assert for the
2980                          operand of the NOP_EXPR after SI, not after the
2981                          conversion.  */
2982                       if (! has_single_use (t))
2983                         {
2984                           register_new_assert_for (t, comp_code, value,
2985                                                    bb, NULL, si);
2986                           need_assert = true;
2987                         }
2988                     }
2989                 }
2990
2991               /* If OP is used only once, namely in this STMT, don't
2992                  bother creating an ASSERT_EXPR for it.  Such an
2993                  ASSERT_EXPR would do nothing but increase compile time.  */
2994               if (!has_single_use (op))
2995                 {
2996                   register_new_assert_for (op, comp_code, value, bb, NULL, si);
2997                   need_assert = true;
2998                 }
2999             }
3000         }
3001
3002       /* Remember the last statement of the block.  */
3003       last = stmt;
3004     }
3005
3006   /* If BB's last statement is a conditional expression
3007      involving integer operands, recurse into each of the sub-graphs
3008      rooted at BB to determine if we need to add ASSERT_EXPRs.  */
3009   if (last
3010       && TREE_CODE (last) == COND_EXPR
3011       && !fp_predicate (COND_EXPR_COND (last))
3012       && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
3013     need_assert |= find_conditional_asserts (bb);
3014
3015   /* Recurse into the dominator children of BB.  */
3016   for (son = first_dom_son (CDI_DOMINATORS, bb);
3017        son;
3018        son = next_dom_son (CDI_DOMINATORS, son))
3019     need_assert |= find_assert_locations (son);
3020
3021   return need_assert;
3022 }
3023
3024
3025 /* Create an ASSERT_EXPR for NAME and insert it in the location
3026    indicated by LOC.  Return true if we made any edge insertions.  */
3027
3028 static bool
3029 process_assert_insertions_for (tree name, assert_locus_t loc)
3030 {
3031   /* Build the comparison expression NAME_i COMP_CODE VAL.  */
3032   tree stmt, cond, assert_expr;
3033   edge_iterator ei;
3034   edge e;
3035
3036   cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
3037   assert_expr = build_assert_expr_for (cond, name);
3038
3039   if (loc->e)
3040     {
3041       /* We have been asked to insert the assertion on an edge.  This
3042          is used only by COND_EXPR and SWITCH_EXPR assertions.  */
3043 #if defined ENABLE_CHECKING
3044       gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
3045           || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
3046 #endif
3047
3048       bsi_insert_on_edge (loc->e, assert_expr);
3049       return true;
3050     }
3051
3052   /* Otherwise, we can insert right after LOC->SI iff the
3053      statement must not be the last statement in the block.  */
3054   stmt = bsi_stmt (loc->si);
3055   if (!stmt_ends_bb_p (stmt))
3056     {
3057       bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
3058       return false;
3059     }
3060
3061   /* If STMT must be the last statement in BB, we can only insert new
3062      assertions on the non-abnormal edge out of BB.  Note that since
3063      STMT is not control flow, there may only be one non-abnormal edge
3064      out of BB.  */
3065   FOR_EACH_EDGE (e, ei, loc->bb->succs)
3066     if (!(e->flags & EDGE_ABNORMAL))
3067       {
3068         bsi_insert_on_edge (e, assert_expr);
3069         return true;
3070       }
3071
3072   gcc_unreachable ();
3073 }
3074
3075
3076 /* Process all the insertions registered for every name N_i registered
3077    in NEED_ASSERT_FOR.  The list of assertions to be inserted are
3078    found in ASSERTS_FOR[i].  */
3079
3080 static void
3081 process_assert_insertions (void)
3082 {
3083   unsigned i;
3084   bitmap_iterator bi;
3085   bool update_edges_p = false;
3086   int num_asserts = 0;
3087
3088   if (dump_file && (dump_flags & TDF_DETAILS))
3089     dump_all_asserts (dump_file);
3090
3091   EXECUTE_IF_SET_IN_BITMAP (need_assert_for, 0, i, bi)
3092     {
3093       assert_locus_t loc = asserts_for[i];
3094       gcc_assert (loc);
3095
3096       while (loc)
3097         {
3098           assert_locus_t next = loc->next;
3099           update_edges_p |= process_assert_insertions_for (ssa_name (i), loc);
3100           free (loc);
3101           loc = next;
3102           num_asserts++;
3103         }
3104     }
3105
3106   if (update_edges_p)
3107     bsi_commit_edge_inserts ();
3108
3109   if (dump_file && (dump_flags & TDF_STATS))
3110     fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
3111              num_asserts);
3112 }
3113
3114
3115 /* Traverse the flowgraph looking for conditional jumps to insert range
3116    expressions.  These range expressions are meant to provide information
3117    to optimizations that need to reason in terms of value ranges.  They
3118    will not be expanded into RTL.  For instance, given:
3119
3120    x = ...
3121    y = ...
3122    if (x < y)
3123      y = x - 2;
3124    else
3125      x = y + 3;
3126
3127    this pass will transform the code into:
3128
3129    x = ...
3130    y = ...
3131    if (x < y)
3132     {
3133       x = ASSERT_EXPR <x, x < y>
3134       y = x - 2
3135     }
3136    else
3137     {
3138       y = ASSERT_EXPR <y, x <= y>
3139       x = y + 3
3140     }
3141
3142    The idea is that once copy and constant propagation have run, other
3143    optimizations will be able to determine what ranges of values can 'x'
3144    take in different paths of the code, simply by checking the reaching
3145    definition of 'x'.  */
3146
3147 static void
3148 insert_range_assertions (void)
3149 {
3150   edge e;
3151   edge_iterator ei;
3152   bool update_ssa_p;
3153
3154   found_in_subgraph = sbitmap_alloc (num_ssa_names);
3155   sbitmap_zero (found_in_subgraph);
3156
3157   blocks_visited = sbitmap_alloc (last_basic_block);
3158   sbitmap_zero (blocks_visited);
3159
3160   need_assert_for = BITMAP_ALLOC (NULL);
3161   asserts_for = XNEWVEC (assert_locus_t, num_ssa_names);
3162   memset (asserts_for, 0, num_ssa_names * sizeof (assert_locus_t));
3163
3164   calculate_dominance_info (CDI_DOMINATORS);
3165
3166   update_ssa_p = false;
3167   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3168     if (find_assert_locations (e->dest))
3169       update_ssa_p = true;
3170
3171   if (update_ssa_p)
3172     {
3173       process_assert_insertions ();
3174       update_ssa (TODO_update_ssa_no_phi);
3175     }
3176
3177   if (dump_file && (dump_flags & TDF_DETAILS))
3178     {
3179       fprintf (dump_file, "\nSSA form after inserting ASSERT_EXPRs\n");
3180       dump_function_to_file (current_function_decl, dump_file, dump_flags);
3181     }
3182
3183   sbitmap_free (found_in_subgraph);
3184   free (asserts_for);
3185   BITMAP_FREE (need_assert_for);
3186 }
3187
3188
3189 /* Convert range assertion expressions into the implied copies and
3190    copy propagate away the copies.  Doing the trivial copy propagation
3191    here avoids the need to run the full copy propagation pass after
3192    VRP.
3193
3194    FIXME, this will eventually lead to copy propagation removing the
3195    names that had useful range information attached to them.  For
3196    instance, if we had the assertion N_i = ASSERT_EXPR <N_j, N_j > 3>,
3197    then N_i will have the range [3, +INF].
3198
3199    However, by converting the assertion into the implied copy
3200    operation N_i = N_j, we will then copy-propagate N_j into the uses
3201    of N_i and lose the range information.  We may want to hold on to
3202    ASSERT_EXPRs a little while longer as the ranges could be used in
3203    things like jump threading.
3204
3205    The problem with keeping ASSERT_EXPRs around is that passes after
3206    VRP need to handle them appropriately.
3207
3208    Another approach would be to make the range information a first
3209    class property of the SSA_NAME so that it can be queried from
3210    any pass.  This is made somewhat more complex by the need for
3211    multiple ranges to be associated with one SSA_NAME.  */
3212
3213 static void
3214 remove_range_assertions (void)
3215 {
3216   basic_block bb;
3217   block_stmt_iterator si;
3218
3219   /* Note that the BSI iterator bump happens at the bottom of the
3220      loop and no bump is necessary if we're removing the statement
3221      referenced by the current BSI.  */
3222   FOR_EACH_BB (bb)
3223     for (si = bsi_start (bb); !bsi_end_p (si);)
3224       {
3225         tree stmt = bsi_stmt (si);
3226
3227         if (TREE_CODE (stmt) == MODIFY_EXPR
3228             && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
3229           {
3230             tree rhs = TREE_OPERAND (stmt, 1), var;
3231             tree cond = fold (ASSERT_EXPR_COND (rhs));
3232             use_operand_p use_p;
3233             imm_use_iterator iter;
3234
3235             gcc_assert (cond != boolean_false_node);
3236
3237             /* Propagate the RHS into every use of the LHS.  */
3238             var = ASSERT_EXPR_VAR (rhs);
3239             FOR_EACH_IMM_USE_SAFE (use_p, iter, TREE_OPERAND (stmt, 0))
3240               {
3241                 SET_USE (use_p, var);
3242                 gcc_assert (TREE_CODE (var) == SSA_NAME);
3243               }
3244
3245             /* And finally, remove the copy, it is not needed.  */
3246             bsi_remove (&si, true);
3247           }
3248         else
3249           bsi_next (&si);
3250       }
3251
3252   sbitmap_free (blocks_visited);
3253 }
3254
3255
3256 /* Return true if STMT is interesting for VRP.  */
3257
3258 static bool
3259 stmt_interesting_for_vrp (tree stmt)
3260 {
3261   if (TREE_CODE (stmt) == PHI_NODE
3262       && is_gimple_reg (PHI_RESULT (stmt))
3263       && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
3264           || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
3265     return true;
3266   else if (TREE_CODE (stmt) == MODIFY_EXPR)
3267     {
3268       tree lhs = TREE_OPERAND (stmt, 0);
3269       tree rhs = TREE_OPERAND (stmt, 1);
3270
3271       /* In general, assignments with virtual operands are not useful
3272          for deriving ranges, with the obvious exception of calls to
3273          builtin functions.  */
3274       if (TREE_CODE (lhs) == SSA_NAME
3275           && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3276               || POINTER_TYPE_P (TREE_TYPE (lhs)))
3277           && ((TREE_CODE (rhs) == CALL_EXPR
3278                && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
3279                && DECL_P (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
3280                && DECL_IS_BUILTIN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
3281               || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
3282         return true;
3283     }
3284   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
3285     return true;
3286
3287   return false;
3288 }
3289
3290
3291 /* Initialize local data structures for VRP.  */
3292
3293 static void
3294 vrp_initialize (void)
3295 {
3296   basic_block bb;
3297
3298   vr_value = XNEWVEC (value_range_t *, num_ssa_names);
3299   memset (vr_value, 0, num_ssa_names * sizeof (value_range_t *));
3300
3301   FOR_EACH_BB (bb)
3302     {
3303       block_stmt_iterator si;
3304       tree phi;
3305
3306       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3307         {
3308           if (!stmt_interesting_for_vrp (phi))
3309             {
3310               tree lhs = PHI_RESULT (phi);
3311               set_value_range_to_varying (get_value_range (lhs));
3312               DONT_SIMULATE_AGAIN (phi) = true;
3313             }
3314           else
3315             DONT_SIMULATE_AGAIN (phi) = false;
3316         }
3317
3318       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3319         {
3320           tree stmt = bsi_stmt (si);
3321
3322           if (!stmt_interesting_for_vrp (stmt))
3323             {
3324               ssa_op_iter i;
3325               tree def;
3326               FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
3327                 set_value_range_to_varying (get_value_range (def));
3328               DONT_SIMULATE_AGAIN (stmt) = true;
3329             }
3330           else
3331             {
3332               DONT_SIMULATE_AGAIN (stmt) = false;
3333             }
3334         }
3335     }
3336 }
3337
3338
3339 /* Visit assignment STMT.  If it produces an interesting range, record
3340    the SSA name in *OUTPUT_P.  */
3341
3342 static enum ssa_prop_result
3343 vrp_visit_assignment (tree stmt, tree *output_p)
3344 {
3345   tree lhs, rhs, def;
3346   ssa_op_iter iter;
3347
3348   lhs = TREE_OPERAND (stmt, 0);
3349   rhs = TREE_OPERAND (stmt, 1);
3350
3351   /* We only keep track of ranges in integral and pointer types.  */
3352   if (TREE_CODE (lhs) == SSA_NAME
3353       && ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
3354            /* It is valid to have NULL MIN/MAX values on a type.  See
3355               build_range_type.  */
3356            && TYPE_MIN_VALUE (TREE_TYPE (lhs))
3357            && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
3358           || POINTER_TYPE_P (TREE_TYPE (lhs))))
3359     {
3360       struct loop *l;
3361       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
3362
3363       extract_range_from_expr (&new_vr, rhs);
3364
3365       /* If STMT is inside a loop, we may be able to know something
3366          else about the range of LHS by examining scalar evolution
3367          information.  */
3368       if (current_loops && (l = loop_containing_stmt (stmt)))
3369         adjust_range_with_scev (&new_vr, l, stmt, lhs);
3370
3371       if (update_value_range (lhs, &new_vr))
3372         {
3373           *output_p = lhs;
3374
3375           if (dump_file && (dump_flags & TDF_DETAILS))
3376             {
3377               fprintf (dump_file, "Found new range for ");
3378               print_generic_expr (dump_file, lhs, 0);
3379               fprintf (dump_file, ": ");
3380               dump_value_range (dump_file, &new_vr);
3381               fprintf (dump_file, "\n\n");
3382             }
3383
3384           if (new_vr.type == VR_VARYING)
3385             return SSA_PROP_VARYING;
3386
3387           return SSA_PROP_INTERESTING;
3388         }
3389
3390       return SSA_PROP_NOT_INTERESTING;
3391     }
3392
3393   /* Every other statement produces no useful ranges.  */
3394   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3395     set_value_range_to_varying (get_value_range (def));
3396
3397   return SSA_PROP_VARYING;
3398 }
3399
3400
3401 /* Compare all the value ranges for names equivalent to VAR with VAL
3402    using comparison code COMP.  Return the same value returned by
3403    compare_range_with_value.  */
3404
3405 static tree
3406 compare_name_with_value (enum tree_code comp, tree var, tree val)
3407 {
3408   bitmap_iterator bi;
3409   unsigned i;
3410   bitmap e;
3411   tree retval, t;
3412
3413   t = retval = NULL_TREE;
3414
3415   /* Get the set of equivalences for VAR.  */
3416   e = get_value_range (var)->equiv;
3417
3418   /* Add VAR to its own set of equivalences so that VAR's value range
3419      is processed by this loop (otherwise, we would have to replicate
3420      the body of the loop just to check VAR's value range).  */
3421   bitmap_set_bit (e, SSA_NAME_VERSION (var));
3422
3423   EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
3424     {
3425       value_range_t equiv_vr = *(vr_value[i]);
3426
3427       /* If name N_i does not have a valid range, use N_i as its own
3428          range.  This allows us to compare against names that may
3429          have N_i in their ranges.  */
3430       if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
3431         {
3432           equiv_vr.type = VR_RANGE;
3433           equiv_vr.min = ssa_name (i);
3434           equiv_vr.max = ssa_name (i);
3435         }
3436
3437       t = compare_range_with_value (comp, &equiv_vr, val);
3438       if (t)
3439         {
3440           /* All the ranges should compare the same against VAL.  */
3441           gcc_assert (retval == NULL || t == retval);
3442           retval = t;
3443         }
3444     }
3445
3446   /* Remove VAR from its own equivalence set.  */
3447   bitmap_clear_bit (e, SSA_NAME_VERSION (var));
3448
3449   if (retval)
3450     return retval;
3451
3452   /* We couldn't find a non-NULL value for the predicate.  */
3453   return NULL_TREE;
3454 }
3455
3456
3457 /* Given a comparison code COMP and names N1 and N2, compare all the
3458    ranges equivalent to N1 against all the ranges equivalent to N2
3459    to determine the value of N1 COMP N2.  Return the same value
3460    returned by compare_ranges.  */
3461
3462 static tree
3463 compare_names (enum tree_code comp, tree n1, tree n2)
3464 {
3465   tree t, retval;
3466   bitmap e1, e2;
3467   bitmap_iterator bi1, bi2;
3468   unsigned i1, i2;
3469
3470   /* Compare the ranges of every name equivalent to N1 against the
3471      ranges of every name equivalent to N2.  */
3472   e1 = get_value_range (n1)->equiv;
3473   e2 = get_value_range (n2)->equiv;
3474
3475   /* Add N1 and N2 to their own set of equivalences to avoid
3476      duplicating the body of the loop just to check N1 and N2
3477      ranges.  */
3478   bitmap_set_bit (e1, SSA_NAME_VERSION (n1));
3479   bitmap_set_bit (e2, SSA_NAME_VERSION (n2));
3480
3481   /* If the equivalence sets have a common intersection, then the two
3482      names can be compared without checking their ranges.  */
3483   if (bitmap_intersect_p (e1, e2))
3484     {
3485       bitmap_clear_bit (e1, SSA_NAME_VERSION (n1));
3486       bitmap_clear_bit (e2, SSA_NAME_VERSION (n2));
3487
3488       return (comp == EQ_EXPR || comp == GE_EXPR || comp == LE_EXPR)
3489              ? boolean_true_node
3490              : boolean_false_node;
3491     }
3492
3493   /* Otherwise, compare all the equivalent ranges.  First, add N1 and
3494      N2 to their own set of equivalences to avoid duplicating the body
3495      of the loop just to check N1 and N2 ranges.  */
3496   EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
3497     {
3498       value_range_t vr1 = *(vr_value[i1]);
3499
3500       /* If the range is VARYING or UNDEFINED, use the name itself.  */
3501       if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
3502         {
3503           vr1.type = VR_RANGE;
3504           vr1.min = ssa_name (i1);
3505           vr1.max = ssa_name (i1);
3506         }
3507
3508       t = retval = NULL_TREE;
3509       EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
3510         {
3511           value_range_t vr2 = *(vr_value[i2]);
3512
3513           if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
3514             {
3515               vr2.type = VR_RANGE;
3516               vr2.min = ssa_name (i2);
3517               vr2.max = ssa_name (i2);
3518             }
3519
3520           t = compare_ranges (comp, &vr1, &vr2);
3521           if (t)
3522             {