gcc/tree-vrp.c

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