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