gcc/wide-int-range.cc

   1 /* Support routines for range operations on wide ints.
   2    Copyright (C) 2018 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 "tree.h"
  24 #include "function.h"
  25 #include "fold-const.h"
  26 #include "wide-int-range.h"
  27
  28 /* Wrapper around wide_int_binop that adjusts for overflow.
  29
  30    Return true if we can compute the result; i.e. if the operation
  31    doesn't overflow or if the overflow is undefined.  In the latter
  32    case (if the operation overflows and overflow is undefined), then
  33    adjust the result to be -INF or +INF depending on CODE, VAL1 and
  34    VAL2.  Return the value in *RES.
  35
  36    Return false for division by zero, for which the result is
  37    indeterminate.  */
  38
  39 static bool
  40 wide_int_binop_overflow (wide_int &res,
  41                          enum tree_code code,
  42                          const wide_int &w0, const wide_int &w1,
  43                          signop sign, bool overflow_undefined)
  44 {
  45   wi::overflow_type overflow;
  46   if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
  47     return false;
  48
  49   /* If the operation overflowed return -INF or +INF depending on the
  50      operation and the combination of signs of the operands.  */
  51   if (overflow && overflow_undefined)
  52     {
  53       switch (code)
  54         {
  55         case MULT_EXPR:
  56           /* For multiplication, the sign of the overflow is given
  57              by the comparison of the signs of the operands.  */
  58           if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
  59             res = wi::max_value (w0.get_precision (), sign);
  60           else
  61             res = wi::min_value (w0.get_precision (), sign);
  62           return true;
  63
  64         case TRUNC_DIV_EXPR:
  65         case FLOOR_DIV_EXPR:
  66         case CEIL_DIV_EXPR:
  67         case EXACT_DIV_EXPR:
  68         case ROUND_DIV_EXPR:
  69           /* For division, the only case is -INF / -1 = +INF.  */
  70           res = wi::max_value (w0.get_precision (), sign);
  71           return true;
  72
  73         default:
  74           gcc_unreachable ();
  75         }
  76     }
  77   return !overflow;
  78 }
  79
  80 /* For range [LB, UB] compute two wide_int bit masks.
  81
  82    In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
  83    for all numbers in the range the bit is 0, otherwise it might be 0
  84    or 1.
  85
  86    In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
  87    for all numbers in the range the bit is 1, otherwise it might be 0
  88    or 1.  */
  89
  90 void
  91 wide_int_range_set_zero_nonzero_bits (signop sign,
  92                                       const wide_int &lb, const wide_int &ub,
  93                                       wide_int &may_be_nonzero,
  94                                       wide_int &must_be_nonzero)
  95 {
  96   may_be_nonzero = wi::minus_one (lb.get_precision ());
  97   must_be_nonzero = wi::zero (lb.get_precision ());
  98
  99   if (wi::eq_p (lb, ub))
 100     {
 101       may_be_nonzero = lb;
 102       must_be_nonzero = may_be_nonzero;
 103     }
 104   else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
 105     {
 106       wide_int xor_mask = lb ^ ub;
 107       may_be_nonzero = lb | ub;
 108       must_be_nonzero = lb & ub;
 109       if (xor_mask != 0)
 110         {
 111           wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
 112                                     may_be_nonzero.get_precision ());
 113           may_be_nonzero = may_be_nonzero | mask;
 114           must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
 115         }
 116     }
 117 }
 118
 119 /* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
 120    accordingly.  */
 121
 122 static void
 123 wide_int_range_order_set (wide_int &min, wide_int &max,
 124                           wide_int &w0, wide_int &w1,
 125                           wide_int &w2, wide_int &w3,
 126                           signop sign)
 127 {
 128   /* Order pairs w0,w1 and w2,w3.  */
 129   if (wi::gt_p (w0, w1, sign))
 130     std::swap (w0, w1);
 131   if (wi::gt_p (w2, w3, sign))
 132     std::swap (w2, w3);
 133
 134   /* Choose min and max from the ordered pairs.  */
 135   min = wi::min (w0, w2, sign);
 136   max = wi::max (w1, w3, sign);
 137 }
 138
 139 /* Calculate the cross product of two sets of ranges (VR0 and VR1) and
 140    store the result in [RES_LB, RES_UB].
 141
 142    CODE is the operation to perform with sign SIGN.
 143
 144    OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
 145
 146    Return TRUE if we were able to calculate the cross product.  */
 147
 148 bool
 149 wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
 150                               enum tree_code code, signop sign,
 151                               const wide_int &vr0_lb, const wide_int &vr0_ub,
 152                               const wide_int &vr1_lb, const wide_int &vr1_ub,
 153                               bool overflow_undefined)
 154 {
 155   wide_int cp1, cp2, cp3, cp4;
 156
 157   /* Compute the 4 cross operations, bailing if we get an overflow we
 158      can't handle.  */
 159
 160   if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
 161                                 overflow_undefined))
 162     return false;
 163
 164   if (wi::eq_p (vr0_lb, vr0_ub))
 165     cp3 = cp1;
 166   else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
 167                                      overflow_undefined))
 168     return false;
 169
 170   if (wi::eq_p (vr1_lb, vr1_ub))
 171     cp2 = cp1;
 172   else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
 173                                      overflow_undefined))
 174     return false;
 175
 176   if (wi::eq_p (vr0_lb, vr0_ub))
 177     cp4 = cp2;
 178   else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
 179                                      overflow_undefined))
 180     return false;
 181
 182   wide_int_range_order_set (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
 183   return true;
 184 }
 185
 186 /* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
 187
 188      [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
 189
 190    This is basically fancy code so we don't drop to varying with an
 191    unsigned [-3,-1]*[-3,-1].
 192
 193    Return TRUE if we were able to perform the operation.  */
 194
 195 bool
 196 wide_int_range_mult_wrapping (wide_int &res_lb,
 197                               wide_int &res_ub,
 198                               signop sign,
 199                               unsigned prec,
 200                               const wide_int &min0_,
 201                               const wide_int &max0_,
 202                               const wide_int &min1_,
 203                               const wide_int &max1_)
 204 {
 205   /* This test requires 2*prec bits if both operands are signed and
 206      2*prec + 2 bits if either is not.  Therefore, extend the values
 207      using the sign of the result to PREC2.  From here on out,
 208      everthing is just signed math no matter what the input types
 209      were.  */
 210   widest2_int min0 = widest2_int::from (min0_, sign);
 211   widest2_int max0 = widest2_int::from (max0_, sign);
 212   widest2_int min1 = widest2_int::from (min1_, sign);
 213   widest2_int max1 = widest2_int::from (max1_, sign);
 214   widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
 215   widest2_int size = sizem1 + 1;
 216
 217   /* Canonicalize the intervals.  */
 218   if (sign == UNSIGNED)
 219     {
 220       if (wi::ltu_p (size, min0 + max0))
 221         {
 222           min0 -= size;
 223           max0 -= size;
 224         }
 225
 226       if (wi::ltu_p (size, min1 + max1))
 227         {
 228           min1 -= size;
 229           max1 -= size;
 230         }
 231     }
 232
 233   widest2_int prod0 = min0 * min1;
 234   widest2_int prod1 = min0 * max1;
 235   widest2_int prod2 = max0 * min1;
 236   widest2_int prod3 = max0 * max1;
 237
 238   /* Sort the 4 products so that min is in prod0 and max is in
 239      prod3.  */
 240   /* min0min1 > max0max1 */
 241   if (prod0 > prod3)
 242     std::swap (prod0, prod3);
 243
 244   /* min0max1 > max0min1 */
 245   if (prod1 > prod2)
 246     std::swap (prod1, prod2);
 247
 248   if (prod0 > prod1)
 249     std::swap (prod0, prod1);
 250
 251   if (prod2 > prod3)
 252     std::swap (prod2, prod3);
 253
 254   /* diff = max - min.  */
 255   prod2 = prod3 - prod0;
 256   if (wi::geu_p (prod2, sizem1))
 257     /* The range covers all values.  */
 258     return false;
 259
 260   res_lb = wide_int::from (prod0, prec, sign);
 261   res_ub = wide_int::from (prod3, prec, sign);
 262   return true;
 263 }
 264
 265 /* Perform multiplicative operation CODE on two ranges:
 266
 267      [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
 268
 269    Return TRUE if we were able to perform the operation.
 270
 271    NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
 272    range must be canonicalized by the caller because its components
 273    may be swapped.  */
 274
 275 bool
 276 wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
 277                                   enum tree_code code,
 278                                   signop sign,
 279                                   unsigned prec,
 280                                   const wide_int &vr0_lb,
 281                                   const wide_int &vr0_ub,
 282                                   const wide_int &vr1_lb,
 283                                   const wide_int &vr1_ub,
 284                                   bool overflow_undefined,
 285                                   bool overflow_wraps)
 286 {
 287   /* Multiplications, divisions and shifts are a bit tricky to handle,
 288      depending on the mix of signs we have in the two ranges, we
 289      need to operate on different values to get the minimum and
 290      maximum values for the new range.  One approach is to figure
 291      out all the variations of range combinations and do the
 292      operations.
 293
 294      However, this involves several calls to compare_values and it
 295      is pretty convoluted.  It's simpler to do the 4 operations
 296      (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
 297      MAX1) and then figure the smallest and largest values to form
 298      the new range.  */
 299   if (code == MULT_EXPR && overflow_wraps)
 300     return wide_int_range_mult_wrapping (res_lb, res_ub,
 301                                          sign, prec,
 302                                          vr0_lb, vr0_ub, vr1_lb, vr1_ub);
 303   return wide_int_range_cross_product (res_lb, res_ub,
 304                                        code, sign,
 305                                        vr0_lb, vr0_ub, vr1_lb, vr1_ub,
 306                                        overflow_undefined);
 307 }
 308
 309 /* Perform a left shift operation on two ranges:
 310
 311      [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
 312
 313    Return TRUE if we were able to perform the operation.
 314
 315    NOTE: The resulting range must be canonicalized by the caller
 316    because its contents components may be swapped.  */
 317
 318 bool
 319 wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
 320                        signop sign, unsigned prec,
 321                        const wide_int &vr0_lb, const wide_int &vr0_ub,
 322                        const wide_int &vr1_lb, const wide_int &vr1_ub,
 323                        bool overflow_undefined, bool overflow_wraps)
 324 {
 325   /* Transform left shifts by constants into multiplies.  */
 326   if (wi::eq_p (vr1_lb, vr1_ub))
 327     {
 328       unsigned shift = vr1_ub.to_uhwi ();
 329       wide_int tmp = wi::set_bit_in_zero (shift, prec);
 330       return wide_int_range_multiplicative_op (res_lb, res_ub,
 331                                                MULT_EXPR, sign, prec,
 332                                                vr0_lb, vr0_ub, tmp, tmp,
 333                                                overflow_undefined,
 334                                                /*overflow_wraps=*/true);
 335     }
 336
 337   int overflow_pos = prec;
 338   if (sign == SIGNED)
 339     overflow_pos -= 1;
 340   int bound_shift = overflow_pos - vr1_ub.to_shwi ();
 341   /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
 342      overflow.  However, for that to happen, vr1.max needs to be
 343      zero, which means vr1 is a singleton range of zero, which
 344      means it should be handled by the previous LSHIFT_EXPR
 345      if-clause.  */
 346   wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
 347   wide_int complement = ~(bound - 1);
 348   wide_int low_bound, high_bound;
 349   bool in_bounds = false;
 350   if (sign == UNSIGNED)
 351     {
 352       low_bound = bound;
 353       high_bound = complement;
 354       if (wi::ltu_p (vr0_ub, low_bound))
 355         {
 356           /* [5, 6] << [1, 2] == [10, 24].  */
 357           /* We're shifting out only zeroes, the value increases
 358              monotonically.  */
 359           in_bounds = true;
 360         }
 361       else if (wi::ltu_p (high_bound, vr0_lb))
 362         {
 363           /* [0xffffff00, 0xffffffff] << [1, 2]
 364              == [0xfffffc00, 0xfffffffe].  */
 365           /* We're shifting out only ones, the value decreases
 366              monotonically.  */
 367           in_bounds = true;
 368         }
 369     }
 370   else
 371     {
 372       /* [-1, 1] << [1, 2] == [-4, 4].  */
 373       low_bound = complement;
 374       high_bound = bound;
 375       if (wi::lts_p (vr0_ub, high_bound)
 376           && wi::lts_p (low_bound, vr0_lb))
 377         {
 378           /* For non-negative numbers, we're shifting out only
 379              zeroes, the value increases monotonically.
 380              For negative numbers, we're shifting out only ones, the
 381              value decreases monotomically.  */
 382           in_bounds = true;
 383         }
 384     }
 385   if (in_bounds)
 386     return wide_int_range_multiplicative_op (res_lb, res_ub,
 387                                              LSHIFT_EXPR, sign, prec,
 388                                              vr0_lb, vr0_ub,
 389                                              vr1_lb, vr1_ub,
 390                                              overflow_undefined,
 391                                              overflow_wraps);
 392   return false;
 393 }
 394
 395 /* Return TRUE if a bit operation on two ranges can be easily
 396    optimized in terms of a mask.
 397
 398    Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
 399
 400         [LB, UB] op Z
 401    into:
 402         [LB op Z, UB op Z]
 403
 404    It is up to the caller to perform the actual folding above.  */
 405
 406 static bool
 407 wide_int_range_can_optimize_bit_op (tree_code code,
 408                                     const wide_int &lb, const wide_int &ub,
 409                                     const wide_int &mask)
 410
 411 {
 412   if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
 413     return false;
 414   /* If Z is a constant which (for op | its bitwise not) has n
 415      consecutive least significant bits cleared followed by m 1
 416      consecutive bits set immediately above it and either
 417      m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
 418
 419      The least significant n bits of all the values in the range are
 420      cleared or set, the m bits above it are preserved and any bits
 421      above these are required to be the same for all values in the
 422      range.  */
 423
 424   wide_int w = mask;
 425   int m = 0, n = 0;
 426   if (code == BIT_IOR_EXPR)
 427     w = ~w;
 428   if (wi::eq_p (w, 0))
 429     n = w.get_precision ();
 430   else
 431     {
 432       n = wi::ctz (w);
 433       w = ~(w | wi::mask (n, false, w.get_precision ()));
 434       if (wi::eq_p (w, 0))
 435         m = w.get_precision () - n;
 436       else
 437         m = wi::ctz (w) - n;
 438     }
 439   wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
 440   if ((new_mask & lb) == (new_mask & ub))
 441     return true;
 442
 443   return false;
 444 }
 445
 446 /* Helper function for wide_int_range_optimize_bit_op.
 447
 448    Calculates bounds and mask for a pair of ranges.  The mask is the
 449    singleton range among the ranges, if any.  The bounds are the
 450    bounds for the remaining range.  */
 451
 452 bool
 453 wide_int_range_get_mask_and_bounds (wide_int &mask,
 454                                     wide_int &lower_bound,
 455                                     wide_int &upper_bound,
 456                                     const wide_int &vr0_min,
 457                                     const wide_int &vr0_max,
 458                                     const wide_int &vr1_min,
 459                                     const wide_int &vr1_max)
 460 {
 461   if (wi::eq_p (vr1_min, vr1_max))
 462     {
 463       mask = vr1_min;
 464       lower_bound = vr0_min;
 465       upper_bound = vr0_max;
 466       return true;
 467     }
 468   else if (wi::eq_p (vr0_min, vr0_max))
 469     {
 470       mask = vr0_min;
 471       lower_bound = vr1_min;
 472       upper_bound = vr1_max;
 473       return true;
 474     }
 475   return false;
 476 }
 477
 478 /* Optimize a bit operation (BIT_AND_EXPR or BIT_IOR_EXPR) if
 479    possible.  If so, return TRUE and store the result in
 480    [RES_LB, RES_UB].  */
 481
 482 bool
 483 wide_int_range_optimize_bit_op (wide_int &res_lb, wide_int &res_ub,
 484                                 enum tree_code code,
 485                                 signop sign,
 486                                 const wide_int &vr0_min,
 487                                 const wide_int &vr0_max,
 488                                 const wide_int &vr1_min,
 489                                 const wide_int &vr1_max)
 490 {
 491   gcc_assert (code == BIT_AND_EXPR || code == BIT_IOR_EXPR);
 492
 493   wide_int lower_bound, upper_bound, mask;
 494   if (!wide_int_range_get_mask_and_bounds (mask, lower_bound, upper_bound,
 495                                            vr0_min, vr0_max, vr1_min, vr1_max))
 496     return false;
 497   if (wide_int_range_can_optimize_bit_op (code,
 498                                           lower_bound, upper_bound, mask))
 499     {
 500       wi::overflow_type ovf;
 501       wide_int_binop (res_lb, code, lower_bound, mask, sign, &ovf);
 502       wide_int_binop (res_ub, code, upper_bound, mask, sign, &ovf);
 503       return true;
 504     }
 505   return false;
 506 }
 507
 508 /* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
 509    The two input ranges are described by their MUST_BE_NONZERO and
 510    MAY_BE_NONZERO bit masks.
 511
 512    Return TRUE if we were able to successfully calculate the new range.  */
 513
 514 bool
 515 wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
 516                         signop sign,
 517                         unsigned prec,
 518                         const wide_int &must_be_nonzero0,
 519                         const wide_int &may_be_nonzero0,
 520                         const wide_int &must_be_nonzero1,
 521                         const wide_int &may_be_nonzero1)
 522 {
 523   wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
 524                                | ~(may_be_nonzero0 | may_be_nonzero1));
 525   wide_int result_one_bits
 526     = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
 527        | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
 528   wmax = ~result_zero_bits;
 529   wmin = result_one_bits;
 530   /* If the range has all positive or all negative values, the result
 531      is better than VARYING.  */
 532   if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
 533     return true;
 534   wmin = wi::min_value (prec, sign);
 535   wmax = wi::max_value (prec, sign);
 536   return false;
 537 }
 538
 539 /* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
 540    Return TRUE if we were able to successfully calculate the new range.  */
 541
 542 bool
 543 wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
 544                         signop sign,
 545                         const wide_int &vr0_min,
 546                         const wide_int &vr0_max,
 547                         const wide_int &vr1_min,
 548                         const wide_int &vr1_max,
 549                         const wide_int &must_be_nonzero0,
 550                         const wide_int &may_be_nonzero0,
 551                         const wide_int &must_be_nonzero1,
 552                         const wide_int &may_be_nonzero1)
 553 {
 554   if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_IOR_EXPR, sign,
 555                                       vr0_min, vr0_max,
 556                                       vr1_min, vr1_max))
 557     return true;
 558   wmin = must_be_nonzero0 | must_be_nonzero1;
 559   wmax = may_be_nonzero0 | may_be_nonzero1;
 560   /* If the input ranges contain only positive values we can
 561      truncate the minimum of the result range to the maximum
 562      of the input range minima.  */
 563   if (wi::ge_p (vr0_min, 0, sign)
 564       && wi::ge_p (vr1_min, 0, sign))
 565     {
 566       wmin = wi::max (wmin, vr0_min, sign);
 567       wmin = wi::max (wmin, vr1_min, sign);
 568     }
 569   /* If either input range contains only negative values
 570      we can truncate the minimum of the result range to the
 571      respective minimum range.  */
 572   if (wi::lt_p (vr0_max, 0, sign))
 573     wmin = wi::max (wmin, vr0_min, sign);
 574   if (wi::lt_p (vr1_max, 0, sign))
 575     wmin = wi::max (wmin, vr1_min, sign);
 576   /* If the limits got swapped around, indicate error so we can adjust
 577      the range to VARYING.  */
 578   if (wi::gt_p (wmin, wmax,sign))
 579     return false;
 580   return true;
 581 }
 582
 583 /* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
 584    Return TRUE if we were able to successfully calculate the new range.  */
 585
 586 bool
 587 wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
 588                         signop sign,
 589                         unsigned prec,
 590                         const wide_int &vr0_min,
 591                         const wide_int &vr0_max,
 592                         const wide_int &vr1_min,
 593                         const wide_int &vr1_max,
 594                         const wide_int &must_be_nonzero0,
 595                         const wide_int &may_be_nonzero0,
 596                         const wide_int &must_be_nonzero1,
 597                         const wide_int &may_be_nonzero1)
 598 {
 599   if (wide_int_range_optimize_bit_op (wmin, wmax, BIT_AND_EXPR, sign,
 600                                       vr0_min, vr0_max,
 601                                       vr1_min, vr1_max))
 602     return true;
 603   wmin = must_be_nonzero0 & must_be_nonzero1;
 604   wmax = may_be_nonzero0 & may_be_nonzero1;
 605   /* If both input ranges contain only negative values we can
 606      truncate the result range maximum to the minimum of the
 607      input range maxima.  */
 608   if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
 609     {
 610       wmax = wi::min (wmax, vr0_max, sign);
 611       wmax = wi::min (wmax, vr1_max, sign);
 612     }
 613   /* If either input range contains only non-negative values
 614      we can truncate the result range maximum to the respective
 615      maximum of the input range.  */
 616   if (wi::ge_p (vr0_min, 0, sign))
 617     wmax = wi::min (wmax, vr0_max, sign);
 618   if (wi::ge_p (vr1_min, 0, sign))
 619     wmax = wi::min (wmax, vr1_max, sign);
 620   /* PR68217: In case of signed & sign-bit-CST should
 621      result in [-INF, 0] instead of [-INF, INF].  */
 622   if (wi::gt_p (wmin, wmax, sign))
 623     {
 624       wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
 625       if (sign == SIGNED
 626           && ((wi::eq_p (vr0_min, vr0_max)
 627                && !wi::cmps (vr0_min, sign_bit))
 628               || (wi::eq_p (vr1_min, vr1_max)
 629                   && !wi::cmps (vr1_min, sign_bit))))
 630         {
 631           wmin = wi::min_value (prec, sign);
 632           wmax = wi::zero (prec);
 633         }
 634     }
 635   /* If the limits got swapped around, indicate error so we can adjust
 636      the range to VARYING.  */
 637   if (wi::gt_p (wmin, wmax,sign))
 638     return false;
 639   return true;
 640 }
 641
 642 /* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
 643    [WMIN,WMAX].  */
 644
 645 void
 646 wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
 647                           signop sign,
 648                           unsigned prec,
 649                           const wide_int &vr0_min,
 650                           const wide_int &vr0_max,
 651                           const wide_int &vr1_min,
 652                           const wide_int &vr1_max)
 653 {
 654   wide_int tmp;
 655
 656   /* ABS (A % B) < ABS (B) and either
 657      0 <= A % B <= A or A <= A % B <= 0.  */
 658   wmax = vr1_max - 1;
 659   if (sign == SIGNED)
 660     {
 661       tmp = -1 - vr1_min;
 662       wmax = wi::smax (wmax, tmp);
 663     }
 664
 665   if (sign == UNSIGNED)
 666     wmin = wi::zero (prec);
 667   else
 668     {
 669       wmin = -wmax;
 670       tmp = vr0_min;
 671       if (wi::gts_p (tmp, 0))
 672         tmp = wi::zero (prec);
 673       wmin = wi::smax (wmin, tmp);
 674     }
 675   tmp = vr0_max;
 676   if (sign == SIGNED && wi::neg_p (tmp))
 677     tmp = wi::zero (prec);
 678   wmax = wi::min (wmax, tmp, sign);
 679 }
 680
 681 /* Calculate ABS_EXPR on a range and store the result in [MIN, MAX].  */
 682
 683 bool
 684 wide_int_range_abs (wide_int &min, wide_int &max,
 685                     signop sign, unsigned prec,
 686                     const wide_int &vr0_min, const wide_int &vr0_max,
 687                     bool overflow_undefined)
 688 {
 689   /* Pass through VR0 the easy cases.  */
 690   if (sign == UNSIGNED || wi::ge_p (vr0_min, 0, sign))
 691     {
 692       min = vr0_min;
 693       max = vr0_max;
 694       return true;
 695     }
 696
 697   /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
 698      useful range.  */
 699   wide_int min_value = wi::min_value (prec, sign);
 700   wide_int max_value = wi::max_value (prec, sign);
 701   if (!overflow_undefined && wi::eq_p (vr0_min, min_value))
 702     return false;
 703
 704   /* ABS_EXPR may flip the range around, if the original range
 705      included negative values.  */
 706   if (wi::eq_p (vr0_min, min_value))
 707     min = max_value;
 708   else
 709     min = wi::abs (vr0_min);
 710   if (wi::eq_p (vr0_max, min_value))
 711     max = max_value;
 712   else
 713     max = wi::abs (vr0_max);
 714
 715   /* If the range contains zero then we know that the minimum value in the
 716      range will be zero.  */
 717   if (wi::le_p (vr0_min, 0, sign) && wi::ge_p (vr0_max, 0, sign))
 718     {
 719       if (wi::gt_p (min, max, sign))
 720         max = min;
 721       min = wi::zero (prec);
 722     }
 723   else
 724     {
 725       /* If the range was reversed, swap MIN and MAX.  */
 726       if (wi::gt_p (min, max, sign))
 727         std::swap (min, max);
 728     }
 729
 730   /* If the new range has its limits swapped around (MIN > MAX), then
 731      the operation caused one of them to wrap around.  The only thing
 732      we know is that the result is positive.  */
 733   if (wi::gt_p (min, max, sign))
 734     {
 735       min = wi::zero (prec);
 736       max = max_value;
 737     }
 738   return true;
 739 }
 740
 741 /* Convert range in [VR0_MIN, VR0_MAX] with INNER_SIGN and INNER_PREC,
 742    to a range in [MIN, MAX] with OUTER_SIGN and OUTER_PREC.
 743
 744    Return TRUE if we were able to successfully calculate the new range.
 745
 746    Caller is responsible for canonicalizing the resulting range.  */
 747
 748 bool
 749 wide_int_range_convert (wide_int &min, wide_int &max,
 750                         signop inner_sign,
 751                         unsigned inner_prec,
 752                         signop outer_sign,
 753                         unsigned outer_prec,
 754                         const wide_int &vr0_min,
 755                         const wide_int &vr0_max)
 756 {
 757   /* If the conversion is not truncating we can convert the min and
 758      max values and canonicalize the resulting range.  Otherwise we
 759      can do the conversion if the size of the range is less than what
 760      the precision of the target type can represent.  */
 761   if (outer_prec >= inner_prec
 762       || wi::rshift (wi::sub (vr0_max, vr0_min),
 763                      wi::uhwi (outer_prec, inner_prec),
 764                      inner_sign) == 0)
 765     {
 766       min = wide_int::from (vr0_min, outer_prec, inner_sign);
 767       max = wide_int::from (vr0_max, outer_prec, inner_sign);
 768       return (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign))
 769               || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign)));
 770     }
 771   return false;
 772 }
 773
 774 /* Calculate a division operation on two ranges and store the result in
 775    [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX].
 776
 777    If EXTRA_RANGE_P is set upon return, EXTRA_MIN/EXTRA_MAX hold
 778    meaningful information, otherwise they should be ignored.
 779
 780    Return TRUE if we were able to successfully calculate the new range.  */
 781
 782 bool
 783 wide_int_range_div (wide_int &wmin, wide_int &wmax,
 784                     tree_code code, signop sign, unsigned prec,
 785                     const wide_int &dividend_min, const wide_int &dividend_max,
 786                     const wide_int &divisor_min, const wide_int &divisor_max,
 787                     bool overflow_undefined,
 788                     bool overflow_wraps,
 789                     bool &extra_range_p,
 790                     wide_int &extra_min, wide_int &extra_max)
 791 {
 792   extra_range_p = false;
 793
 794   /* If we know we won't divide by zero, just do the division.  */
 795   if (!wide_int_range_includes_zero_p (divisor_min, divisor_max, sign))
 796     return wide_int_range_multiplicative_op (wmin, wmax, code, sign, prec,
 797                                              dividend_min, dividend_max,
 798                                              divisor_min, divisor_max,
 799                                              overflow_undefined,
 800                                              overflow_wraps);
 801
 802   /* If flag_non_call_exceptions, we must not eliminate a division
 803      by zero.  */
 804   if (cfun->can_throw_non_call_exceptions)
 805     return false;
 806
 807   /* If we're definitely dividing by zero, there's nothing to do.  */
 808   if (wide_int_range_zero_p (divisor_min, divisor_max, prec))
 809     return false;
 810
 811   /* Perform the division in 2 parts, [LB, -1] and [1, UB],
 812      which will skip any division by zero.
 813
 814      First divide by the negative numbers, if any.  */
 815   if (wi::neg_p (divisor_min, sign))
 816     {
 817       if (!wide_int_range_multiplicative_op (wmin, wmax,
 818                                              code, sign, prec,
 819                                              dividend_min, dividend_max,
 820                                              divisor_min, wi::minus_one (prec),
 821                                              overflow_undefined,
 822                                              overflow_wraps))
 823         return false;
 824       extra_range_p = true;
 825     }
 826   /* Then divide by the non-zero positive numbers, if any.  */
 827   if (wi::gt_p (divisor_max, wi::zero (prec), sign))
 828     {
 829       if (!wide_int_range_multiplicative_op (extra_range_p ? extra_min : wmin,
 830                                              extra_range_p ? extra_max : wmax,
 831                                              code, sign, prec,
 832                                              dividend_min, dividend_max,
 833                                              wi::one (prec), divisor_max,
 834                                              overflow_undefined,
 835                                              overflow_wraps))
 836         return false;
 837     }
 838   else
 839     extra_range_p = false;
 840   return true;
 841 }