gcc/tree-vrp.c

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