gcc/value-range.cc

   1 /* Support routines for value ranges.
   2    Copyright (C) 2019-2020 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "ssa.h"
  27 #include "tree-pretty-print.h"
  28 #include "fold-const.h"
  29
  30 value_range::value_range (tree min, tree max, value_range_kind kind)
  31 {
  32   set (min, max, kind);
  33 }
  34
  35 value_range::value_range (tree type)
  36 {
  37   set_varying (type);
  38 }
  39
  40 value_range::value_range (tree type,
  41                           const wide_int &wmin, const wide_int &wmax,
  42                           enum value_range_kind kind)
  43 {
  44   tree min = wide_int_to_tree (type, wmin);
  45   tree max = wide_int_to_tree (type, wmax);
  46   gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
  47   set (min, max, kind);
  48 }
  49
  50 void
  51 value_range::set_undefined ()
  52 {
  53   m_kind = VR_UNDEFINED;
  54   m_min = m_max = NULL;
  55 }
  56
  57 void
  58 value_range::set_varying (tree type)
  59 {
  60   m_kind = VR_VARYING;
  61   if (supports_type_p (type))
  62     {
  63       m_min = vrp_val_min (type);
  64       m_max = vrp_val_max (type);
  65     }
  66   else
  67     /* We can't do anything range-wise with these types.  */
  68     m_min = m_max = error_mark_node;
  69 }
  70
  71 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
  72    This means adjusting VRTYPE, MIN and MAX representing the case of a
  73    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
  74    as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
  75    In corner cases where MAX+1 or MIN-1 wraps this will fall back
  76    to varying.
  77    This routine exists to ease canonicalization in the case where we
  78    extract ranges from var + CST op limit.  */
  79
  80 void
  81 value_range::set (tree min, tree max, value_range_kind kind)
  82 {
  83   /* Use the canonical setters for VR_UNDEFINED and VR_VARYING.  */
  84   if (kind == VR_UNDEFINED)
  85     {
  86       set_undefined ();
  87       return;
  88     }
  89   else if (kind == VR_VARYING)
  90     {
  91       gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
  92       tree typ = TREE_TYPE (min);
  93       if (supports_type_p (typ))
  94         {
  95           gcc_assert (vrp_val_min (typ));
  96           gcc_assert (vrp_val_max (typ));
  97         }
  98       set_varying (typ);
  99       return;
 100     }
 101
 102   /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds.  */
 103   if (POLY_INT_CST_P (min))
 104     {
 105       tree type_min = vrp_val_min (TREE_TYPE (min));
 106       widest_int lb
 107         = constant_lower_bound_with_limit (wi::to_poly_widest (min),
 108                                            wi::to_widest (type_min));
 109       min = wide_int_to_tree (TREE_TYPE (min), lb);
 110     }
 111   if (POLY_INT_CST_P (max))
 112     {
 113       tree type_max = vrp_val_max (TREE_TYPE (max));
 114       widest_int ub
 115         = constant_upper_bound_with_limit (wi::to_poly_widest (max),
 116                                            wi::to_widest (type_max));
 117       max = wide_int_to_tree (TREE_TYPE (max), ub);
 118     }
 119
 120   /* Nothing to canonicalize for symbolic ranges.  */
 121   if (TREE_CODE (min) != INTEGER_CST
 122       || TREE_CODE (max) != INTEGER_CST)
 123     {
 124       m_kind = kind;
 125       m_min = min;
 126       m_max = max;
 127       return;
 128     }
 129
 130   /* Wrong order for min and max, to swap them and the VR type we need
 131      to adjust them.  */
 132   if (tree_int_cst_lt (max, min))
 133     {
 134       tree one, tmp;
 135
 136       /* For one bit precision if max < min, then the swapped
 137          range covers all values, so for VR_RANGE it is varying and
 138          for VR_ANTI_RANGE empty range, so drop to varying as well.  */
 139       if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
 140         {
 141           set_varying (TREE_TYPE (min));
 142           return;
 143         }
 144
 145       one = build_int_cst (TREE_TYPE (min), 1);
 146       tmp = int_const_binop (PLUS_EXPR, max, one);
 147       max = int_const_binop (MINUS_EXPR, min, one);
 148       min = tmp;
 149
 150       /* There's one corner case, if we had [C+1, C] before we now have
 151          that again.  But this represents an empty value range, so drop
 152          to varying in this case.  */
 153       if (tree_int_cst_lt (max, min))
 154         {
 155           set_varying (TREE_TYPE (min));
 156           return;
 157         }
 158
 159       kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
 160     }
 161
 162   tree type = TREE_TYPE (min);
 163
 164   /* Anti-ranges that can be represented as ranges should be so.  */
 165   if (kind == VR_ANTI_RANGE)
 166     {
 167       /* For -fstrict-enums we may receive out-of-range ranges so consider
 168          values < -INF and values > INF as -INF/INF as well.  */
 169       bool is_min = vrp_val_is_min (min);
 170       bool is_max = vrp_val_is_max (max);
 171
 172       if (is_min && is_max)
 173         {
 174           /* We cannot deal with empty ranges, drop to varying.
 175              ???  This could be VR_UNDEFINED instead.  */
 176           set_varying (type);
 177           return;
 178         }
 179       else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
 180                && (is_min || is_max))
 181         {
 182           /* Non-empty boolean ranges can always be represented
 183              as a singleton range.  */
 184           if (is_min)
 185             min = max = vrp_val_max (TREE_TYPE (min));
 186           else
 187             min = max = vrp_val_min (TREE_TYPE (min));
 188           kind = VR_RANGE;
 189         }
 190       else if (is_min)
 191         {
 192           tree one = build_int_cst (TREE_TYPE (max), 1);
 193           min = int_const_binop (PLUS_EXPR, max, one);
 194           max = vrp_val_max (TREE_TYPE (max));
 195           kind = VR_RANGE;
 196         }
 197       else if (is_max)
 198         {
 199           tree one = build_int_cst (TREE_TYPE (min), 1);
 200           max = int_const_binop (MINUS_EXPR, min, one);
 201           min = vrp_val_min (TREE_TYPE (min));
 202           kind = VR_RANGE;
 203         }
 204     }
 205
 206   /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
 207
 208      Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
 209      restrict those to a subset of what actually fits in the type.
 210      Instead use the extremes of the type precision which will allow
 211      compare_range_with_value() to check if a value is inside a range,
 212      whereas if we used TYPE_*_VAL, said function would just punt
 213      upon seeing a VARYING.  */
 214   unsigned prec = TYPE_PRECISION (type);
 215   signop sign = TYPE_SIGN (type);
 216   if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
 217       && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
 218     {
 219       if (kind == VR_RANGE)
 220         set_varying (type);
 221       else if (kind == VR_ANTI_RANGE)
 222         set_undefined ();
 223       else
 224         gcc_unreachable ();
 225       return;
 226     }
 227
 228   /* Do not drop [-INF(OVF), +INF(OVF)] to varying.  (OVF) has to be sticky
 229      to make sure VRP iteration terminates, otherwise we can get into
 230      oscillations.  */
 231
 232   m_kind = kind;
 233   m_min = min;
 234   m_max = max;
 235   if (flag_checking)
 236     check ();
 237 }
 238
 239 void
 240 value_range::set (tree val)
 241 {
 242   gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
 243   if (TREE_OVERFLOW_P (val))
 244     val = drop_tree_overflow (val);
 245   set (val, val);
 246 }
 247
 248 /* Set value range VR to a nonzero range of type TYPE.  */
 249
 250 void
 251 value_range::set_nonzero (tree type)
 252 {
 253   tree zero = build_int_cst (type, 0);
 254   set (zero, zero, VR_ANTI_RANGE);
 255 }
 256
 257 /* Set value range VR to a ZERO range of type TYPE.  */
 258
 259 void
 260 value_range::set_zero (tree type)
 261 {
 262   set (build_int_cst (type, 0));
 263 }
 264
 265 /* Check the validity of the range.  */
 266
 267 void
 268 value_range::check ()
 269 {
 270   switch (m_kind)
 271     {
 272     case VR_RANGE:
 273     case VR_ANTI_RANGE:
 274       {
 275         gcc_assert (m_min && m_max);
 276         gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
 277
 278         /* Creating ~[-MIN, +MAX] is stupid because that would be
 279            the empty set.  */
 280         if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
 281           gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
 282
 283         int cmp = compare_values (m_min, m_max);
 284         gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
 285         break;
 286       }
 287     case VR_UNDEFINED:
 288       gcc_assert (!min () && !max ());
 289       break;
 290     case VR_VARYING:
 291       gcc_assert (m_min && m_max);
 292       break;
 293     default:
 294       gcc_unreachable ();
 295     }
 296 }
 297
 298 /* Return the number of sub-ranges in a range.  */
 299
 300 unsigned
 301 value_range::num_pairs () const
 302 {
 303   if (undefined_p ())
 304     return 0;
 305   if (varying_p ())
 306     return 1;
 307   if (symbolic_p ())
 308     {
 309       value_range numeric_range (*this);
 310       numeric_range.normalize_symbolics ();
 311       return numeric_range.num_pairs ();
 312     }
 313   if (m_kind == VR_ANTI_RANGE)
 314     {
 315       // ~[MIN, X] has one sub-range of [X+1, MAX], and
 316       // ~[X, MAX] has one sub-range of [MIN, X-1].
 317       if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max))
 318         return 1;
 319       return 2;
 320     }
 321   return 1;
 322 }
 323
 324 /* Return the lower bound for a sub-range.  PAIR is the sub-range in
 325    question.  */
 326
 327 wide_int
 328 value_range::lower_bound (unsigned pair) const
 329 {
 330   if (symbolic_p ())
 331     {
 332       value_range numeric_range (*this);
 333       numeric_range.normalize_symbolics ();
 334       return numeric_range.lower_bound (pair);
 335     }
 336
 337   gcc_checking_assert (!undefined_p ());
 338   gcc_checking_assert (pair + 1 <= num_pairs ());
 339   tree t = NULL;
 340   if (m_kind == VR_ANTI_RANGE)
 341     {
 342       tree typ = type ();
 343       if (pair == 1 || vrp_val_is_min (m_min))
 344         t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
 345       else
 346         t = vrp_val_min (typ);
 347     }
 348   else
 349     t = m_min;
 350   return wi::to_wide (t);
 351 }
 352
 353 /* Return the upper bound for a sub-range.  PAIR is the sub-range in
 354    question.  */
 355
 356 wide_int
 357 value_range::upper_bound (unsigned pair) const
 358 {
 359   if (symbolic_p ())
 360     {
 361       value_range numeric_range (*this);
 362       numeric_range.normalize_symbolics ();
 363       return numeric_range.upper_bound (pair);
 364     }
 365
 366   gcc_checking_assert (!undefined_p ());
 367   gcc_checking_assert (pair + 1 <= num_pairs ());
 368   tree t = NULL;
 369   if (m_kind == VR_ANTI_RANGE)
 370     {
 371       tree typ = type ();
 372       if (pair == 1 || vrp_val_is_min (m_min))
 373         t = vrp_val_max (typ);
 374       else
 375         t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
 376     }
 377   else
 378     t = m_max;
 379   return wi::to_wide (t);
 380 }
 381
 382 /* Return the highest bound in a range.  */
 383
 384 wide_int
 385 value_range::upper_bound () const
 386 {
 387   unsigned pairs = num_pairs ();
 388   gcc_checking_assert (pairs > 0);
 389   return upper_bound (pairs - 1);
 390 }
 391
 392 bool
 393 value_range::equal_p (const value_range &other) const
 394 {
 395   /* Ignore types for undefined.  All undefines are equal.  */
 396   if (undefined_p ())
 397     return m_kind == other.m_kind;
 398
 399   return (m_kind == other.m_kind
 400           && vrp_operand_equal_p (m_min, other.m_min)
 401           && vrp_operand_equal_p (m_max, other.m_max));
 402 }
 403
 404 bool
 405 value_range::operator== (const value_range &r) const
 406 {
 407   return equal_p (r);
 408 }
 409
 410 /* If range is a singleton, place it in RESULT and return TRUE.
 411    Note: A singleton can be any gimple invariant, not just constants.
 412    So, [&x, &x] counts as a singleton.  */
 413 /* Return TRUE if this is a symbolic range.  */
 414
 415 bool
 416 value_range::symbolic_p () const
 417 {
 418   return (!varying_p ()
 419           && !undefined_p ()
 420           && (!is_gimple_min_invariant (m_min)
 421               || !is_gimple_min_invariant (m_max)));
 422 }
 423
 424 /* NOTE: This is not the inverse of symbolic_p because the range
 425    could also be varying or undefined.  Ideally they should be inverse
 426    of each other, with varying only applying to symbolics.  Varying of
 427    constants would be represented as [-MIN, +MAX].  */
 428
 429 bool
 430 value_range::constant_p () const
 431 {
 432   return (!varying_p ()
 433           && !undefined_p ()
 434           && TREE_CODE (m_min) == INTEGER_CST
 435           && TREE_CODE (m_max) == INTEGER_CST);
 436 }
 437
 438 bool
 439 value_range::singleton_p (tree *result) const
 440 {
 441   if (m_kind == VR_ANTI_RANGE)
 442     {
 443       if (nonzero_p ())
 444         {
 445           if (TYPE_PRECISION (type ()) == 1)
 446             {
 447               if (result)
 448                 *result = m_max;
 449               return true;
 450             }
 451           return false;
 452         }
 453       if (num_pairs () == 1)
 454         {
 455           value_range vr0, vr1;
 456           ranges_from_anti_range (this, &vr0, &vr1);
 457           return vr0.singleton_p (result);
 458         }
 459     }
 460   if (m_kind == VR_RANGE
 461       && vrp_operand_equal_p (min (), max ())
 462       && is_gimple_min_invariant (min ()))
 463     {
 464       if (result)
 465         *result = min ();
 466       return true;
 467     }
 468   return false;
 469 }
 470
 471 /* Return 1 if VAL is inside value range.
 472           0 if VAL is not inside value range.
 473          -2 if we cannot tell either way.
 474
 475    Benchmark compile/20001226-1.c compilation time after changing this
 476    function.  */
 477
 478 int
 479 value_range::value_inside_range (tree val) const
 480 {
 481   int cmp1, cmp2;
 482
 483   if (varying_p ())
 484     return 1;
 485
 486   if (undefined_p ())
 487     return 0;
 488
 489   cmp1 = operand_less_p (val, m_min);
 490   if (cmp1 == -2)
 491     return -2;
 492   if (cmp1 == 1)
 493     return m_kind != VR_RANGE;
 494
 495   cmp2 = operand_less_p (m_max, val);
 496   if (cmp2 == -2)
 497     return -2;
 498
 499   if (m_kind == VR_RANGE)
 500     return !cmp2;
 501   else
 502     return !!cmp2;
 503 }
 504
 505 /* Return TRUE if it is possible that range contains VAL.  */
 506
 507 bool
 508 value_range::may_contain_p (tree val) const
 509 {
 510   return value_inside_range (val) != 0;
 511 }
 512
 513 /* Return TRUE if range contains INTEGER_CST.  */
 514
 515 bool
 516 value_range::contains_p (tree cst) const
 517 {
 518   gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
 519   if (symbolic_p ())
 520     {
 521       value_range numeric_range (*this);
 522       numeric_range.normalize_symbolics ();
 523       return numeric_range.contains_p (cst);
 524     }
 525   return value_inside_range (cst) == 1;
 526 }
 527
 528 /* Normalize addresses into constants.  */
 529
 530 void
 531 value_range::normalize_addresses ()
 532 {
 533   if (undefined_p ())
 534     return;
 535
 536   if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
 537     return;
 538
 539   if (!range_includes_zero_p (this))
 540     {
 541       gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
 542                            || TREE_CODE (m_max) == ADDR_EXPR);
 543       set_nonzero (type ());
 544       return;
 545     }
 546   set_varying (type ());
 547 }
 548
 549 /* Normalize symbolics and addresses into constants.  */
 550
 551 void
 552 value_range::normalize_symbolics ()
 553 {
 554   if (varying_p () || undefined_p ())
 555     return;
 556
 557   tree ttype = type ();
 558   bool min_symbolic = !is_gimple_min_invariant (min ());
 559   bool max_symbolic = !is_gimple_min_invariant (max ());
 560   if (!min_symbolic && !max_symbolic)
 561     {
 562       normalize_addresses ();
 563       return;
 564     }
 565
 566   // [SYM, SYM] -> VARYING
 567   if (min_symbolic && max_symbolic)
 568     {
 569       set_varying (ttype);
 570       return;
 571     }
 572   if (kind () == VR_RANGE)
 573     {
 574       // [SYM, NUM] -> [-MIN, NUM]
 575       if (min_symbolic)
 576         {
 577           set (vrp_val_min (ttype), max ());
 578           return;
 579         }
 580       // [NUM, SYM] -> [NUM, +MAX]
 581       set (min (), vrp_val_max (ttype));
 582       return;
 583     }
 584   gcc_checking_assert (kind () == VR_ANTI_RANGE);
 585   // ~[SYM, NUM] -> [NUM + 1, +MAX]
 586   if (min_symbolic)
 587     {
 588       if (!vrp_val_is_max (max ()))
 589         {
 590           tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
 591           set (n, vrp_val_max (ttype));
 592           return;
 593         }
 594       set_varying (ttype);
 595       return;
 596     }
 597   // ~[NUM, SYM] -> [-MIN, NUM - 1]
 598   if (!vrp_val_is_min (min ()))
 599     {
 600       tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
 601       set (vrp_val_min (ttype), n);
 602       return;
 603     }
 604   set_varying (ttype);
 605 }
 606
 607 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
 608    { VR1TYPE, VR0MIN, VR0MAX } and store the result
 609    in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
 610    possible such range.  The resulting range is not canonicalized.  */
 611
 612 static void
 613 intersect_ranges (enum value_range_kind *vr0type,
 614                   tree *vr0min, tree *vr0max,
 615                   enum value_range_kind vr1type,
 616                   tree vr1min, tree vr1max)
 617 {
 618   bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
 619   bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
 620
 621   /* [] is vr0, () is vr1 in the following classification comments.  */
 622   if (mineq && maxeq)
 623     {
 624       /* [(  )] */
 625       if (*vr0type == vr1type)
 626         /* Nothing to do for equal ranges.  */
 627         ;
 628       else if ((*vr0type == VR_RANGE
 629                 && vr1type == VR_ANTI_RANGE)
 630                || (*vr0type == VR_ANTI_RANGE
 631                    && vr1type == VR_RANGE))
 632         {
 633           /* For anti-range with range intersection the result is empty.  */
 634           *vr0type = VR_UNDEFINED;
 635           *vr0min = NULL_TREE;
 636           *vr0max = NULL_TREE;
 637         }
 638       else
 639         gcc_unreachable ();
 640     }
 641   else if (operand_less_p (*vr0max, vr1min) == 1
 642            || operand_less_p (vr1max, *vr0min) == 1)
 643     {
 644       /* [ ] ( ) or ( ) [ ]
 645          If the ranges have an empty intersection, the result of the
 646          intersect operation is the range for intersecting an
 647          anti-range with a range or empty when intersecting two ranges.  */
 648       if (*vr0type == VR_RANGE
 649           && vr1type == VR_ANTI_RANGE)
 650         ;
 651       else if (*vr0type == VR_ANTI_RANGE
 652                && vr1type == VR_RANGE)
 653         {
 654           *vr0type = vr1type;
 655           *vr0min = vr1min;
 656           *vr0max = vr1max;
 657         }
 658       else if (*vr0type == VR_RANGE
 659                && vr1type == VR_RANGE)
 660         {
 661           *vr0type = VR_UNDEFINED;
 662           *vr0min = NULL_TREE;
 663           *vr0max = NULL_TREE;
 664         }
 665       else if (*vr0type == VR_ANTI_RANGE
 666                && vr1type == VR_ANTI_RANGE)
 667         {
 668           /* If the anti-ranges are adjacent to each other merge them.  */
 669           if (TREE_CODE (*vr0max) == INTEGER_CST
 670               && TREE_CODE (vr1min) == INTEGER_CST
 671               && operand_less_p (*vr0max, vr1min) == 1
 672               && integer_onep (int_const_binop (MINUS_EXPR,
 673                                                 vr1min, *vr0max)))
 674             *vr0max = vr1max;
 675           else if (TREE_CODE (vr1max) == INTEGER_CST
 676                    && TREE_CODE (*vr0min) == INTEGER_CST
 677                    && operand_less_p (vr1max, *vr0min) == 1
 678                    && integer_onep (int_const_binop (MINUS_EXPR,
 679                                                      *vr0min, vr1max)))
 680             *vr0min = vr1min;
 681           /* Else arbitrarily take VR0.  */
 682         }
 683     }
 684   else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
 685            && (mineq || operand_less_p (*vr0min, vr1min) == 1))
 686     {
 687       /* [ (  ) ] or [(  ) ] or [ (  )] */
 688       if (*vr0type == VR_RANGE
 689           && vr1type == VR_RANGE)
 690         {
 691           /* If both are ranges the result is the inner one.  */
 692           *vr0type = vr1type;
 693           *vr0min = vr1min;
 694           *vr0max = vr1max;
 695         }
 696       else if (*vr0type == VR_RANGE
 697                && vr1type == VR_ANTI_RANGE)
 698         {
 699           /* Choose the right gap if the left one is empty.  */
 700           if (mineq)
 701             {
 702               if (TREE_CODE (vr1max) != INTEGER_CST)
 703                 *vr0min = vr1max;
 704               else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
 705                        && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
 706                 *vr0min
 707                   = int_const_binop (MINUS_EXPR, vr1max,
 708                                      build_int_cst (TREE_TYPE (vr1max), -1));
 709               else
 710                 *vr0min
 711                   = int_const_binop (PLUS_EXPR, vr1max,
 712                                      build_int_cst (TREE_TYPE (vr1max), 1));
 713             }
 714           /* Choose the left gap if the right one is empty.  */
 715           else if (maxeq)
 716             {
 717               if (TREE_CODE (vr1min) != INTEGER_CST)
 718                 *vr0max = vr1min;
 719               else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
 720                        && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
 721                 *vr0max
 722                   = int_const_binop (PLUS_EXPR, vr1min,
 723                                      build_int_cst (TREE_TYPE (vr1min), -1));
 724               else
 725                 *vr0max
 726                   = int_const_binop (MINUS_EXPR, vr1min,
 727                                      build_int_cst (TREE_TYPE (vr1min), 1));
 728             }
 729           /* Choose the anti-range if the range is effectively varying.  */
 730           else if (vrp_val_is_min (*vr0min)
 731                    && vrp_val_is_max (*vr0max))
 732             {
 733               *vr0type = vr1type;
 734               *vr0min = vr1min;
 735               *vr0max = vr1max;
 736             }
 737           /* Else choose the range.  */
 738         }
 739       else if (*vr0type == VR_ANTI_RANGE
 740                && vr1type == VR_ANTI_RANGE)
 741         /* If both are anti-ranges the result is the outer one.  */
 742         ;
 743       else if (*vr0type == VR_ANTI_RANGE
 744                && vr1type == VR_RANGE)
 745         {
 746           /* The intersection is empty.  */
 747           *vr0type = VR_UNDEFINED;
 748           *vr0min = NULL_TREE;
 749           *vr0max = NULL_TREE;
 750         }
 751       else
 752         gcc_unreachable ();
 753     }
 754   else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
 755            && (mineq || operand_less_p (vr1min, *vr0min) == 1))
 756     {
 757       /* ( [  ] ) or ([  ] ) or ( [  ]) */
 758       if (*vr0type == VR_RANGE
 759           && vr1type == VR_RANGE)
 760         /* Choose the inner range.  */
 761         ;
 762       else if (*vr0type == VR_ANTI_RANGE
 763                && vr1type == VR_RANGE)
 764         {
 765           /* Choose the right gap if the left is empty.  */
 766           if (mineq)
 767             {
 768               *vr0type = VR_RANGE;
 769               if (TREE_CODE (*vr0max) != INTEGER_CST)
 770                 *vr0min = *vr0max;
 771               else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
 772                        && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
 773                 *vr0min
 774                   = int_const_binop (MINUS_EXPR, *vr0max,
 775                                      build_int_cst (TREE_TYPE (*vr0max), -1));
 776               else
 777                 *vr0min
 778                   = int_const_binop (PLUS_EXPR, *vr0max,
 779                                      build_int_cst (TREE_TYPE (*vr0max), 1));
 780               *vr0max = vr1max;
 781             }
 782           /* Choose the left gap if the right is empty.  */
 783           else if (maxeq)
 784             {
 785               *vr0type = VR_RANGE;
 786               if (TREE_CODE (*vr0min) != INTEGER_CST)
 787                 *vr0max = *vr0min;
 788               else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
 789                        && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
 790                 *vr0max
 791                   = int_const_binop (PLUS_EXPR, *vr0min,
 792                                      build_int_cst (TREE_TYPE (*vr0min), -1));
 793               else
 794                 *vr0max
 795                   = int_const_binop (MINUS_EXPR, *vr0min,
 796                                      build_int_cst (TREE_TYPE (*vr0min), 1));
 797               *vr0min = vr1min;
 798             }
 799           /* Choose the anti-range if the range is effectively varying.  */
 800           else if (vrp_val_is_min (vr1min)
 801                    && vrp_val_is_max (vr1max))
 802             ;
 803           /* Choose the anti-range if it is ~[0,0], that range is special
 804              enough to special case when vr1's range is relatively wide.
 805              At least for types bigger than int - this covers pointers
 806              and arguments to functions like ctz.  */
 807           else if (*vr0min == *vr0max
 808                    && integer_zerop (*vr0min)
 809                    && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
 810                         >= TYPE_PRECISION (integer_type_node))
 811                        || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
 812                    && TREE_CODE (vr1max) == INTEGER_CST
 813                    && TREE_CODE (vr1min) == INTEGER_CST
 814                    && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
 815                        < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
 816             ;
 817           /* Else choose the range.  */
 818           else
 819             {
 820               *vr0type = vr1type;
 821               *vr0min = vr1min;
 822               *vr0max = vr1max;
 823             }
 824         }
 825       else if (*vr0type == VR_ANTI_RANGE
 826                && vr1type == VR_ANTI_RANGE)
 827         {
 828           /* If both are anti-ranges the result is the outer one.  */
 829           *vr0type = vr1type;
 830           *vr0min = vr1min;
 831           *vr0max = vr1max;
 832         }
 833       else if (vr1type == VR_ANTI_RANGE
 834                && *vr0type == VR_RANGE)
 835         {
 836           /* The intersection is empty.  */
 837           *vr0type = VR_UNDEFINED;
 838           *vr0min = NULL_TREE;
 839           *vr0max = NULL_TREE;
 840         }
 841       else
 842         gcc_unreachable ();
 843     }
 844   else if ((operand_less_p (vr1min, *vr0max) == 1
 845             || operand_equal_p (vr1min, *vr0max, 0))
 846            && operand_less_p (*vr0min, vr1min) == 1)
 847     {
 848       /* [  (  ]  ) or [  ](  ) */
 849       if (*vr0type == VR_ANTI_RANGE
 850           && vr1type == VR_ANTI_RANGE)
 851         *vr0max = vr1max;
 852       else if (*vr0type == VR_RANGE
 853                && vr1type == VR_RANGE)
 854         *vr0min = vr1min;
 855       else if (*vr0type == VR_RANGE
 856                && vr1type == VR_ANTI_RANGE)
 857         {
 858           if (TREE_CODE (vr1min) == INTEGER_CST)
 859             *vr0max = int_const_binop (MINUS_EXPR, vr1min,
 860                                        build_int_cst (TREE_TYPE (vr1min), 1));
 861           else
 862             *vr0max = vr1min;
 863         }
 864       else if (*vr0type == VR_ANTI_RANGE
 865                && vr1type == VR_RANGE)
 866         {
 867           *vr0type = VR_RANGE;
 868           if (TREE_CODE (*vr0max) == INTEGER_CST)
 869             *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
 870                                        build_int_cst (TREE_TYPE (*vr0max), 1));
 871           else
 872             *vr0min = *vr0max;
 873           *vr0max = vr1max;
 874         }
 875       else
 876         gcc_unreachable ();
 877     }
 878   else if ((operand_less_p (*vr0min, vr1max) == 1
 879             || operand_equal_p (*vr0min, vr1max, 0))
 880            && operand_less_p (vr1min, *vr0min) == 1)
 881     {
 882       /* (  [  )  ] or (  )[  ] */
 883       if (*vr0type == VR_ANTI_RANGE
 884           && vr1type == VR_ANTI_RANGE)
 885         *vr0min = vr1min;
 886       else if (*vr0type == VR_RANGE
 887                && vr1type == VR_RANGE)
 888         *vr0max = vr1max;
 889       else if (*vr0type == VR_RANGE
 890                && vr1type == VR_ANTI_RANGE)
 891         {
 892           if (TREE_CODE (vr1max) == INTEGER_CST)
 893             *vr0min = int_const_binop (PLUS_EXPR, vr1max,
 894                                        build_int_cst (TREE_TYPE (vr1max), 1));
 895           else
 896             *vr0min = vr1max;
 897         }
 898       else if (*vr0type == VR_ANTI_RANGE
 899                && vr1type == VR_RANGE)
 900         {
 901           *vr0type = VR_RANGE;
 902           if (TREE_CODE (*vr0min) == INTEGER_CST)
 903             *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
 904                                        build_int_cst (TREE_TYPE (*vr0min), 1));
 905           else
 906             *vr0max = *vr0min;
 907           *vr0min = vr1min;
 908         }
 909       else
 910         gcc_unreachable ();
 911     }
 912
 913   /* If we know the intersection is empty, there's no need to
 914      conservatively add anything else to the set.  */
 915   if (*vr0type == VR_UNDEFINED)
 916     return;
 917
 918   /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
 919      result for the intersection.  That's always a conservative
 920      correct estimate unless VR1 is a constant singleton range
 921      in which case we choose that.  */
 922   if (vr1type == VR_RANGE
 923       && is_gimple_min_invariant (vr1min)
 924       && vrp_operand_equal_p (vr1min, vr1max))
 925     {
 926       *vr0type = vr1type;
 927       *vr0min = vr1min;
 928       *vr0max = vr1max;
 929     }
 930 }
 931
 932 /* Helper for the intersection operation for value ranges.  Given two
 933    value ranges VR0 and VR1, return the intersection of the two
 934    ranges.  This may not be the smallest possible such range.  */
 935
 936 value_range
 937 value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
 938 {
 939   /* If either range is VR_VARYING the other one wins.  */
 940   if (vr1->varying_p ())
 941     return *vr0;
 942   if (vr0->varying_p ())
 943     return *vr1;
 944
 945   /* When either range is VR_UNDEFINED the resulting range is
 946      VR_UNDEFINED, too.  */
 947   if (vr0->undefined_p ())
 948     return *vr0;
 949   if (vr1->undefined_p ())
 950     return *vr1;
 951
 952   value_range_kind vr0kind = vr0->kind ();
 953   tree vr0min = vr0->min ();
 954   tree vr0max = vr0->max ();
 955   intersect_ranges (&vr0kind, &vr0min, &vr0max,
 956                     vr1->kind (), vr1->min (), vr1->max ());
 957   /* Make sure to canonicalize the result though as the inversion of a
 958      VR_RANGE can still be a VR_RANGE.  Work on a temporary so we can
 959      fall back to vr0 when this turns things to varying.  */
 960   value_range tem;
 961   if (vr0kind == VR_UNDEFINED)
 962     tem.set_undefined ();
 963   else if (vr0kind == VR_VARYING)
 964     tem.set_varying (vr0->type ());
 965   else
 966     tem.set (vr0min, vr0max, vr0kind);
 967   /* If that failed, use the saved original VR0.  */
 968   if (tem.varying_p ())
 969     return *vr0;
 970
 971   return tem;
 972 }
 973
 974 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
 975    { VR1TYPE, VR0MIN, VR0MAX } and store the result
 976    in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
 977    possible such range.  The resulting range is not canonicalized.  */
 978
 979 static void
 980 union_ranges (enum value_range_kind *vr0type,
 981               tree *vr0min, tree *vr0max,
 982               enum value_range_kind vr1type,
 983               tree vr1min, tree vr1max)
 984 {
 985   int cmpmin = compare_values (*vr0min, vr1min);
 986   int cmpmax = compare_values (*vr0max, vr1max);
 987   bool mineq = cmpmin == 0;
 988   bool maxeq = cmpmax == 0;
 989
 990   /* [] is vr0, () is vr1 in the following classification comments.  */
 991   if (mineq && maxeq)
 992     {
 993       /* [(  )] */
 994       if (*vr0type == vr1type)
 995         /* Nothing to do for equal ranges.  */
 996         ;
 997       else if ((*vr0type == VR_RANGE
 998                 && vr1type == VR_ANTI_RANGE)
 999                || (*vr0type == VR_ANTI_RANGE
1000                    && vr1type == VR_RANGE))
1001         {
1002           /* For anti-range with range union the result is varying.  */
1003           goto give_up;
1004         }
1005       else
1006         gcc_unreachable ();
1007     }
1008   else if (operand_less_p (*vr0max, vr1min) == 1
1009            || operand_less_p (vr1max, *vr0min) == 1)
1010     {
1011       /* [ ] ( ) or ( ) [ ]
1012          If the ranges have an empty intersection, result of the union
1013          operation is the anti-range or if both are anti-ranges
1014          it covers all.  */
1015       if (*vr0type == VR_ANTI_RANGE
1016           && vr1type == VR_ANTI_RANGE)
1017         goto give_up;
1018       else if (*vr0type == VR_ANTI_RANGE
1019                && vr1type == VR_RANGE)
1020         ;
1021       else if (*vr0type == VR_RANGE
1022                && vr1type == VR_ANTI_RANGE)
1023         {
1024           *vr0type = vr1type;
1025           *vr0min = vr1min;
1026           *vr0max = vr1max;
1027         }
1028       else if (*vr0type == VR_RANGE
1029                && vr1type == VR_RANGE)
1030         {
1031           /* The result is the convex hull of both ranges.  */
1032           if (operand_less_p (*vr0max, vr1min) == 1)
1033             {
1034               /* If the result can be an anti-range, create one.  */
1035               if (TREE_CODE (*vr0max) == INTEGER_CST
1036                   && TREE_CODE (vr1min) == INTEGER_CST
1037                   && vrp_val_is_min (*vr0min)
1038                   && vrp_val_is_max (vr1max))
1039                 {
1040                   tree min = int_const_binop (PLUS_EXPR,
1041                                               *vr0max,
1042                                               build_int_cst (TREE_TYPE (*vr0max), 1));
1043                   tree max = int_const_binop (MINUS_EXPR,
1044                                               vr1min,
1045                                               build_int_cst (TREE_TYPE (vr1min), 1));
1046                   if (!operand_less_p (max, min))
1047                     {
1048                       *vr0type = VR_ANTI_RANGE;
1049                       *vr0min = min;
1050                       *vr0max = max;
1051                     }
1052                   else
1053                     *vr0max = vr1max;
1054                 }
1055               else
1056                 *vr0max = vr1max;
1057             }
1058           else
1059             {
1060               /* If the result can be an anti-range, create one.  */
1061               if (TREE_CODE (vr1max) == INTEGER_CST
1062                   && TREE_CODE (*vr0min) == INTEGER_CST
1063                   && vrp_val_is_min (vr1min)
1064                   && vrp_val_is_max (*vr0max))
1065                 {
1066                   tree min = int_const_binop (PLUS_EXPR,
1067                                               vr1max,
1068                                               build_int_cst (TREE_TYPE (vr1max), 1));
1069                   tree max = int_const_binop (MINUS_EXPR,
1070                                               *vr0min,
1071                                               build_int_cst (TREE_TYPE (*vr0min), 1));
1072                   if (!operand_less_p (max, min))
1073                     {
1074                       *vr0type = VR_ANTI_RANGE;
1075                       *vr0min = min;
1076                       *vr0max = max;
1077                     }
1078                   else
1079                     *vr0min = vr1min;
1080                 }
1081               else
1082                 *vr0min = vr1min;
1083             }
1084         }
1085       else
1086         gcc_unreachable ();
1087     }
1088   else if ((maxeq || cmpmax == 1)
1089            && (mineq || cmpmin == -1))
1090     {
1091       /* [ (  ) ] or [(  ) ] or [ (  )] */
1092       if (*vr0type == VR_RANGE
1093           && vr1type == VR_RANGE)
1094         ;
1095       else if (*vr0type == VR_ANTI_RANGE
1096                && vr1type == VR_ANTI_RANGE)
1097         {
1098           *vr0type = vr1type;
1099           *vr0min = vr1min;
1100           *vr0max = vr1max;
1101         }
1102       else if (*vr0type == VR_ANTI_RANGE
1103                && vr1type == VR_RANGE)
1104         {
1105           /* Arbitrarily choose the right or left gap.  */
1106           if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
1107             *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1108                                        build_int_cst (TREE_TYPE (vr1min), 1));
1109           else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
1110             *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1111                                        build_int_cst (TREE_TYPE (vr1max), 1));
1112           else
1113             goto give_up;
1114         }
1115       else if (*vr0type == VR_RANGE
1116                && vr1type == VR_ANTI_RANGE)
1117         /* The result covers everything.  */
1118         goto give_up;
1119       else
1120         gcc_unreachable ();
1121     }
1122   else if ((maxeq || cmpmax == -1)
1123            && (mineq || cmpmin == 1))
1124     {
1125       /* ( [  ] ) or ([  ] ) or ( [  ]) */
1126       if (*vr0type == VR_RANGE
1127           && vr1type == VR_RANGE)
1128         {
1129           *vr0type = vr1type;
1130           *vr0min = vr1min;
1131           *vr0max = vr1max;
1132         }
1133       else if (*vr0type == VR_ANTI_RANGE
1134                && vr1type == VR_ANTI_RANGE)
1135         ;
1136       else if (*vr0type == VR_RANGE
1137                && vr1type == VR_ANTI_RANGE)
1138         {
1139           *vr0type = VR_ANTI_RANGE;
1140           if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
1141             {
1142               *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1143                                          build_int_cst (TREE_TYPE (*vr0min), 1));
1144               *vr0min = vr1min;
1145             }
1146           else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
1147             {
1148               *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1149                                          build_int_cst (TREE_TYPE (*vr0max), 1));
1150               *vr0max = vr1max;
1151             }
1152           else
1153             goto give_up;
1154         }
1155       else if (*vr0type == VR_ANTI_RANGE
1156                && vr1type == VR_RANGE)
1157         /* The result covers everything.  */
1158         goto give_up;
1159       else
1160         gcc_unreachable ();
1161     }
1162   else if (cmpmin == -1
1163            && cmpmax == -1
1164            && (operand_less_p (vr1min, *vr0max) == 1
1165                || operand_equal_p (vr1min, *vr0max, 0)))
1166     {
1167       /* [  (  ]  ) or [   ](   ) */
1168       if (*vr0type == VR_RANGE
1169           && vr1type == VR_RANGE)
1170         *vr0max = vr1max;
1171       else if (*vr0type == VR_ANTI_RANGE
1172                && vr1type == VR_ANTI_RANGE)
1173         *vr0min = vr1min;
1174       else if (*vr0type == VR_ANTI_RANGE
1175                && vr1type == VR_RANGE)
1176         {
1177           if (TREE_CODE (vr1min) == INTEGER_CST)
1178             *vr0max = int_const_binop (MINUS_EXPR, vr1min,
1179                                        build_int_cst (TREE_TYPE (vr1min), 1));
1180           else
1181             goto give_up;
1182         }
1183       else if (*vr0type == VR_RANGE
1184                && vr1type == VR_ANTI_RANGE)
1185         {
1186           if (TREE_CODE (*vr0max) == INTEGER_CST)
1187             {
1188               *vr0type = vr1type;
1189               *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
1190                                          build_int_cst (TREE_TYPE (*vr0max), 1));
1191               *vr0max = vr1max;
1192             }
1193           else
1194             goto give_up;
1195         }
1196       else
1197         gcc_unreachable ();
1198     }
1199   else if (cmpmin == 1
1200            && cmpmax == 1
1201            && (operand_less_p (*vr0min, vr1max) == 1
1202                || operand_equal_p (*vr0min, vr1max, 0)))
1203     {
1204       /* (  [  )  ] or (   )[   ] */
1205       if (*vr0type == VR_RANGE
1206           && vr1type == VR_RANGE)
1207         *vr0min = vr1min;
1208       else if (*vr0type == VR_ANTI_RANGE
1209                && vr1type == VR_ANTI_RANGE)
1210         *vr0max = vr1max;
1211       else if (*vr0type == VR_ANTI_RANGE
1212                && vr1type == VR_RANGE)
1213         {
1214           if (TREE_CODE (vr1max) == INTEGER_CST)
1215             *vr0min = int_const_binop (PLUS_EXPR, vr1max,
1216                                        build_int_cst (TREE_TYPE (vr1max), 1));
1217           else
1218             goto give_up;
1219         }
1220       else if (*vr0type == VR_RANGE
1221                && vr1type == VR_ANTI_RANGE)
1222         {
1223           if (TREE_CODE (*vr0min) == INTEGER_CST)
1224             {
1225               *vr0type = vr1type;
1226               *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
1227                                          build_int_cst (TREE_TYPE (*vr0min), 1));
1228               *vr0min = vr1min;
1229             }
1230           else
1231             goto give_up;
1232         }
1233       else
1234         gcc_unreachable ();
1235     }
1236   else
1237     goto give_up;
1238
1239   return;
1240
1241 give_up:
1242   *vr0type = VR_VARYING;
1243   *vr0min = NULL_TREE;
1244   *vr0max = NULL_TREE;
1245 }
1246
1247 /* Helper for meet operation for value ranges.  Given two value ranges VR0 and
1248    VR1, return a range that contains both VR0 and VR1.  This may not be the
1249    smallest possible such range.  */
1250
1251 value_range
1252 value_range::union_helper (const value_range *vr0, const value_range *vr1)
1253 {
1254   /* VR0 has the resulting range if VR1 is undefined or VR0 is varying.  */
1255   if (vr1->undefined_p ()
1256       || vr0->varying_p ())
1257     return *vr0;
1258
1259   /* VR1 has the resulting range if VR0 is undefined or VR1 is varying.  */
1260   if (vr0->undefined_p ()
1261       || vr1->varying_p ())
1262     return *vr1;
1263
1264   value_range_kind vr0kind = vr0->kind ();
1265   tree vr0min = vr0->min ();
1266   tree vr0max = vr0->max ();
1267   union_ranges (&vr0kind, &vr0min, &vr0max,
1268                 vr1->kind (), vr1->min (), vr1->max ());
1269
1270   /* Work on a temporary so we can still use vr0 when union returns varying.  */
1271   value_range tem;
1272   if (vr0kind == VR_UNDEFINED)
1273     tem.set_undefined ();
1274   else if (vr0kind == VR_VARYING)
1275     tem.set_varying (vr0->type ());
1276   else
1277     tem.set (vr0min, vr0max, vr0kind);
1278
1279   /* Failed to find an efficient meet.  Before giving up and setting
1280      the result to VARYING, see if we can at least derive a useful
1281      anti-range.  */
1282   if (tem.varying_p ()
1283       && range_includes_zero_p (vr0) == 0
1284       && range_includes_zero_p (vr1) == 0)
1285     {
1286       tem.set_nonzero (vr0->type ());
1287       return tem;
1288     }
1289
1290   return tem;
1291 }
1292
1293 /* Meet operation for value ranges.  Given two value ranges VR0 and
1294    VR1, store in VR0 a range that contains both VR0 and VR1.  This
1295    may not be the smallest possible such range.  */
1296
1297 void
1298 value_range::union_ (const value_range *other)
1299 {
1300   if (dump_file && (dump_flags & TDF_DETAILS))
1301     {
1302       fprintf (dump_file, "Meeting\n  ");
1303       dump_value_range (dump_file, this);
1304       fprintf (dump_file, "\nand\n  ");
1305       dump_value_range (dump_file, other);
1306       fprintf (dump_file, "\n");
1307     }
1308
1309   *this = union_helper (this, other);
1310
1311   if (dump_file && (dump_flags & TDF_DETAILS))
1312     {
1313       fprintf (dump_file, "to\n  ");
1314       dump_value_range (dump_file, this);
1315       fprintf (dump_file, "\n");
1316     }
1317 }
1318
1319 /* Range union, but for references.  */
1320
1321 void
1322 value_range::union_ (const value_range &r)
1323 {
1324   /* Disable details for now, because it makes the ranger dump
1325      unnecessarily verbose.  */
1326   bool details = dump_flags & TDF_DETAILS;
1327   if (details)
1328     dump_flags &= ~TDF_DETAILS;
1329   union_ (&r);
1330   if (details)
1331     dump_flags |= TDF_DETAILS;
1332 }
1333
1334 void
1335 value_range::intersect (const value_range *other)
1336 {
1337   if (dump_file && (dump_flags & TDF_DETAILS))
1338     {
1339       fprintf (dump_file, "Intersecting\n  ");
1340       dump_value_range (dump_file, this);
1341       fprintf (dump_file, "\nand\n  ");
1342       dump_value_range (dump_file, other);
1343       fprintf (dump_file, "\n");
1344     }
1345
1346   *this = intersect_helper (this, other);
1347
1348   if (dump_file && (dump_flags & TDF_DETAILS))
1349     {
1350       fprintf (dump_file, "to\n  ");
1351       dump_value_range (dump_file, this);
1352       fprintf (dump_file, "\n");
1353     }
1354 }
1355
1356 /* Range intersect, but for references.  */
1357
1358 void
1359 value_range::intersect (const value_range &r)
1360 {
1361   /* Disable details for now, because it makes the ranger dump
1362      unnecessarily verbose.  */
1363   bool details = dump_flags & TDF_DETAILS;
1364   if (details)
1365     dump_flags &= ~TDF_DETAILS;
1366   intersect (&r);
1367   if (details)
1368     dump_flags |= TDF_DETAILS;
1369 }
1370
1371 /* Return the inverse of a range.  */
1372
1373 void
1374 value_range::invert ()
1375 {
1376   /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
1377      create non-canonical ranges.  Use the constructors instead.  */
1378   if (m_kind == VR_RANGE)
1379     *this = value_range (m_min, m_max, VR_ANTI_RANGE);
1380   else if (m_kind == VR_ANTI_RANGE)
1381     *this = value_range (m_min, m_max);
1382   else
1383     gcc_unreachable ();
1384 }
1385
1386 void
1387 value_range::dump (FILE *file) const
1388 {
1389   if (undefined_p ())
1390     fprintf (file, "UNDEFINED");
1391   else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
1392     {
1393       tree ttype = type ();
1394
1395       print_generic_expr (file, ttype);
1396       fprintf (file, " ");
1397
1398       fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
1399
1400       if (INTEGRAL_TYPE_P (ttype)
1401           && !TYPE_UNSIGNED (ttype)
1402           && vrp_val_is_min (min ())
1403           && TYPE_PRECISION (ttype) != 1)
1404         fprintf (file, "-INF");
1405       else
1406         print_generic_expr (file, min ());
1407
1408       fprintf (file, ", ");
1409
1410       if (supports_type_p (ttype)
1411           && vrp_val_is_max (max ())
1412           && TYPE_PRECISION (ttype) != 1)
1413         fprintf (file, "+INF");
1414       else
1415         print_generic_expr (file, max ());
1416
1417       fprintf (file, "]");
1418     }
1419   else if (varying_p ())
1420     {
1421       print_generic_expr (file, type ());
1422       fprintf (file, " VARYING");
1423     }
1424   else
1425     gcc_unreachable ();
1426 }
1427
1428 void
1429 value_range::dump () const
1430 {
1431   dump (stderr);
1432 }
1433
1434 void
1435 dump_value_range (FILE *file, const value_range *vr)
1436 {
1437   if (!vr)
1438     fprintf (file, "[]");
1439   else
1440     vr->dump (file);
1441 }
1442
1443 DEBUG_FUNCTION void
1444 debug (const value_range *vr)
1445 {
1446   dump_value_range (stderr, vr);
1447 }
1448
1449 DEBUG_FUNCTION void
1450 debug (const value_range &vr)
1451 {
1452   dump_value_range (stderr, &vr);
1453 }
1454
1455 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
1456    so that *VR0 U *VR1 == *AR.  Returns true if that is possible,
1457    false otherwise.  If *AR can be represented with a single range
1458    *VR1 will be VR_UNDEFINED.  */
1459
1460 bool
1461 ranges_from_anti_range (const value_range *ar,
1462                         value_range *vr0, value_range *vr1)
1463 {
1464   tree type = ar->type ();
1465
1466   vr0->set_undefined ();
1467   vr1->set_undefined ();
1468
1469   /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
1470      [A+1, +INF].  Not sure if this helps in practice, though.  */
1471
1472   if (ar->kind () != VR_ANTI_RANGE
1473       || TREE_CODE (ar->min ()) != INTEGER_CST
1474       || TREE_CODE (ar->max ()) != INTEGER_CST
1475       || !vrp_val_min (type)
1476       || !vrp_val_max (type))
1477     return false;
1478
1479   if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
1480     vr0->set (vrp_val_min (type),
1481               wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
1482   if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
1483     vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
1484               vrp_val_max (type));
1485   if (vr0->undefined_p ())
1486     {
1487       *vr0 = *vr1;
1488       vr1->set_undefined ();
1489     }
1490
1491   return !vr0->undefined_p ();
1492 }
1493
1494 bool
1495 range_has_numeric_bounds_p (const value_range *vr)
1496 {
1497   return (vr->min ()
1498           && TREE_CODE (vr->min ()) == INTEGER_CST
1499           && TREE_CODE (vr->max ()) == INTEGER_CST);
1500 }
1501
1502 /* Return the maximum value for TYPE.  */
1503
1504 tree
1505 vrp_val_max (const_tree type)
1506 {
1507   if (INTEGRAL_TYPE_P (type))
1508     return TYPE_MAX_VALUE (type);
1509   if (POINTER_TYPE_P (type))
1510     {
1511       wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
1512       return wide_int_to_tree (const_cast<tree> (type), max);
1513     }
1514   return NULL_TREE;
1515 }
1516
1517 /* Return the minimum value for TYPE.  */
1518
1519 tree
1520 vrp_val_min (const_tree type)
1521 {
1522   if (INTEGRAL_TYPE_P (type))
1523     return TYPE_MIN_VALUE (type);
1524   if (POINTER_TYPE_P (type))
1525     return build_zero_cst (const_cast<tree> (type));
1526   return NULL_TREE;
1527 }
1528
1529 /* Return whether VAL is equal to the maximum value of its type.
1530    We can't do a simple equality comparison with TYPE_MAX_VALUE because
1531    C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
1532    is not == to the integer constant with the same value in the type.  */
1533
1534 bool
1535 vrp_val_is_max (const_tree val)
1536 {
1537   tree type_max = vrp_val_max (TREE_TYPE (val));
1538   return (val == type_max
1539           || (type_max != NULL_TREE
1540               && operand_equal_p (val, type_max, 0)));
1541 }
1542
1543 /* Return whether VAL is equal to the minimum value of its type.  */
1544
1545 bool
1546 vrp_val_is_min (const_tree val)
1547 {
1548   tree type_min = vrp_val_min (TREE_TYPE (val));
1549   return (val == type_min
1550           || (type_min != NULL_TREE
1551               && operand_equal_p (val, type_min, 0)));
1552 }
1553
1554 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
1555
1556 bool
1557 vrp_operand_equal_p (const_tree val1, const_tree val2)
1558 {
1559   if (val1 == val2)
1560     return true;
1561   if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
1562     return false;
1563   return true;
1564 }