gcc/tree-vrp.c

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