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 "fold-const.h"
  25 #include "wide-int-range.h"
  26
  27 /* Wrapper around wide_int_binop that adjusts for overflow.
  28
  29    Return true if we can compute the result; i.e. if the operation
  30    doesn't overflow or if the overflow is undefined.  In the latter
  31    case (if the operation overflows and overflow is undefined), then
  32    adjust the result to be -INF or +INF depending on CODE, VAL1 and
  33    VAL2.  Return the value in *RES.
  34
  35    Return false for division by zero, for which the result is
  36    indeterminate.  */
  37
  38 static bool
  39 wide_int_binop_overflow (wide_int &res,
  40                          enum tree_code code,
  41                          const wide_int &w0, const wide_int &w1,
  42                          signop sign, bool overflow_undefined)
  43 {
  44   wi::overflow_type overflow;
  45   if (!wide_int_binop (res, code, w0, w1, sign, &overflow))
  46     return false;
  47
  48   /* If the operation overflowed return -INF or +INF depending on the
  49      operation and the combination of signs of the operands.  */
  50   if (overflow && overflow_undefined)
  51     {
  52       switch (code)
  53         {
  54         case MULT_EXPR:
  55           /* For multiplication, the sign of the overflow is given
  56              by the comparison of the signs of the operands.  */
  57           if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
  58             res = wi::max_value (w0.get_precision (), sign);
  59           else
  60             res = wi::min_value (w0.get_precision (), sign);
  61           return true;
  62
  63         case TRUNC_DIV_EXPR:
  64         case FLOOR_DIV_EXPR:
  65         case CEIL_DIV_EXPR:
  66         case EXACT_DIV_EXPR:
  67         case ROUND_DIV_EXPR:
  68           /* For division, the only case is -INF / -1 = +INF.  */
  69           res = wi::max_value (w0.get_precision (), sign);
  70           return true;
  71
  72         default:
  73           gcc_unreachable ();
  74         }
  75     }
  76   return !overflow;
  77 }
  78
  79 /* For range [LB, UB] compute two wide_int bit masks.
  80
  81    In the MAY_BE_NONZERO bit mask, if some bit is unset, it means that
  82    for all numbers in the range the bit is 0, otherwise it might be 0
  83    or 1.
  84
  85    In the MUST_BE_NONZERO bit mask, if some bit is set, it means that
  86    for all numbers in the range the bit is 1, otherwise it might be 0
  87    or 1.  */
  88
  89 void
  90 wide_int_range_set_zero_nonzero_bits (signop sign,
  91                                       const wide_int &lb, const wide_int &ub,
  92                                       wide_int &may_be_nonzero,
  93                                       wide_int &must_be_nonzero)
  94 {
  95   may_be_nonzero = wi::minus_one (lb.get_precision ());
  96   must_be_nonzero = wi::zero (lb.get_precision ());
  97
  98   if (wi::eq_p (lb, ub))
  99     {
 100       may_be_nonzero = lb;
 101       must_be_nonzero = may_be_nonzero;
 102     }
 103   else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
 104     {
 105       wide_int xor_mask = lb ^ ub;
 106       may_be_nonzero = lb | ub;
 107       must_be_nonzero = lb & ub;
 108       if (xor_mask != 0)
 109         {
 110           wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
 111                                     may_be_nonzero.get_precision ());
 112           may_be_nonzero = may_be_nonzero | mask;
 113           must_be_nonzero = wi::bit_and_not (must_be_nonzero, mask);
 114         }
 115     }
 116 }
 117
 118 /* Order 2 sets of wide int ranges (w0/w1, w2/w3) and set MIN/MAX
 119    accordingly.  */
 120
 121 static void
 122 wide_int_range_min_max (wide_int &min, wide_int &max,
 123                         wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3,
 124                         signop sign)
 125 {
 126   /* Order pairs w0,w1 and w2,w3.  */
 127   if (wi::gt_p (w0, w1, sign))
 128     std::swap (w0, w1);
 129   if (wi::gt_p (w2, w3, sign))
 130     std::swap (w2, w3);
 131
 132   /* Choose min and max from the ordered pairs.  */
 133   min = wi::min (w0, w2, sign);
 134   max = wi::max (w1, w3, sign);
 135 }
 136
 137 /* Calculate the cross product of two sets of ranges (VR0 and VR1) and
 138    store the result in [RES_LB, RES_UB].
 139
 140    CODE is the operation to perform with sign SIGN.
 141
 142    OVERFLOW_UNDEFINED is set if overflow is undefined for the operation type.
 143
 144    Return TRUE if we were able to calculate the cross product.  */
 145
 146 bool
 147 wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub,
 148                               enum tree_code code, signop sign,
 149                               const wide_int &vr0_lb, const wide_int &vr0_ub,
 150                               const wide_int &vr1_lb, const wide_int &vr1_ub,
 151                               bool overflow_undefined)
 152 {
 153   wide_int cp1, cp2, cp3, cp4;
 154
 155   /* Compute the 4 cross operations, bailing if we get an overflow we
 156      can't handle.  */
 157
 158   if (!wide_int_binop_overflow (cp1, code, vr0_lb, vr1_lb, sign,
 159                                 overflow_undefined))
 160     return false;
 161
 162   if (wi::eq_p (vr0_lb, vr0_ub))
 163     cp3 = cp1;
 164   else if (!wide_int_binop_overflow (cp3, code, vr0_ub, vr1_lb, sign,
 165                                      overflow_undefined))
 166     return false;
 167
 168   if (wi::eq_p (vr1_lb, vr1_ub))
 169     cp2 = cp1;
 170   else if (!wide_int_binop_overflow (cp2, code, vr0_lb, vr1_ub, sign,
 171                                      overflow_undefined))
 172     return false;
 173
 174   if (wi::eq_p (vr0_lb, vr0_ub))
 175     cp4 = cp2;
 176   else if (!wide_int_binop_overflow (cp4, code, vr0_ub, vr1_ub, sign,
 177                                      overflow_undefined))
 178     return false;
 179
 180   wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign);
 181   return true;
 182 }
 183
 184 /* Multiply two ranges when TYPE_OVERFLOW_WRAPS:
 185
 186      [RES_LB, RES_UB] = [MIN0, MAX0] * [MIN1, MAX1]
 187
 188    This is basically fancy code so we don't drop to varying with an
 189    unsigned [-3,-1]*[-3,-1].
 190
 191    Return TRUE if we were able to perform the operation.  */
 192
 193 bool
 194 wide_int_range_mult_wrapping (wide_int &res_lb,
 195                               wide_int &res_ub,
 196                               signop sign,
 197                               unsigned prec,
 198                               const wide_int &min0_,
 199                               const wide_int &max0_,
 200                               const wide_int &min1_,
 201                               const wide_int &max1_)
 202 {
 203   /* This test requires 2*prec bits if both operands are signed and
 204      2*prec + 2 bits if either is not.  Therefore, extend the values
 205      using the sign of the result to PREC2.  From here on out,
 206      everthing is just signed math no matter what the input types
 207      were.  */
 208   widest2_int min0 = widest2_int::from (min0_, sign);
 209   widest2_int max0 = widest2_int::from (max0_, sign);
 210   widest2_int min1 = widest2_int::from (min1_, sign);
 211   widest2_int max1 = widest2_int::from (max1_, sign);
 212   widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
 213   widest2_int size = sizem1 + 1;
 214
 215   /* Canonicalize the intervals.  */
 216   if (sign == UNSIGNED)
 217     {
 218       if (wi::ltu_p (size, min0 + max0))
 219         {
 220           min0 -= size;
 221           max0 -= size;
 222         }
 223
 224       if (wi::ltu_p (size, min1 + max1))
 225         {
 226           min1 -= size;
 227           max1 -= size;
 228         }
 229     }
 230
 231   widest2_int prod0 = min0 * min1;
 232   widest2_int prod1 = min0 * max1;
 233   widest2_int prod2 = max0 * min1;
 234   widest2_int prod3 = max0 * max1;
 235
 236   /* Sort the 4 products so that min is in prod0 and max is in
 237      prod3.  */
 238   /* min0min1 > max0max1 */
 239   if (prod0 > prod3)
 240     std::swap (prod0, prod3);
 241
 242   /* min0max1 > max0min1 */
 243   if (prod1 > prod2)
 244     std::swap (prod1, prod2);
 245
 246   if (prod0 > prod1)
 247     std::swap (prod0, prod1);
 248
 249   if (prod2 > prod3)
 250     std::swap (prod2, prod3);
 251
 252   /* diff = max - min.  */
 253   prod2 = prod3 - prod0;
 254   if (wi::geu_p (prod2, sizem1))
 255     /* The range covers all values.  */
 256     return false;
 257
 258   res_lb = wide_int::from (prod0, prec, sign);
 259   res_ub = wide_int::from (prod3, prec, sign);
 260   return true;
 261 }
 262
 263 /* Perform multiplicative operation CODE on two ranges:
 264
 265      [RES_LB, RES_UB] = [VR0_LB, VR0_UB] .CODE. [VR1_LB, VR1_LB]
 266
 267    Return TRUE if we were able to perform the operation.
 268
 269    NOTE: If code is MULT_EXPR and TYPE_OVERFLOW_WRAPS, the resulting
 270    range must be canonicalized by the caller because its components
 271    may be swapped.  */
 272
 273 bool
 274 wide_int_range_multiplicative_op (wide_int &res_lb, wide_int &res_ub,
 275                                   enum tree_code code,
 276                                   signop sign,
 277                                   unsigned prec,
 278                                   const wide_int &vr0_lb,
 279                                   const wide_int &vr0_ub,
 280                                   const wide_int &vr1_lb,
 281                                   const wide_int &vr1_ub,
 282                                   bool overflow_undefined,
 283                                   bool overflow_wraps)
 284 {
 285   /* Multiplications, divisions and shifts are a bit tricky to handle,
 286      depending on the mix of signs we have in the two ranges, we
 287      need to operate on different values to get the minimum and
 288      maximum values for the new range.  One approach is to figure
 289      out all the variations of range combinations and do the
 290      operations.
 291
 292      However, this involves several calls to compare_values and it
 293      is pretty convoluted.  It's simpler to do the 4 operations
 294      (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
 295      MAX1) and then figure the smallest and largest values to form
 296      the new range.  */
 297   if (code == MULT_EXPR && overflow_wraps)
 298     return wide_int_range_mult_wrapping (res_lb, res_ub,
 299                                          sign, prec,
 300                                          vr0_lb, vr0_ub, vr1_lb, vr1_ub);
 301   return wide_int_range_cross_product (res_lb, res_ub,
 302                                        code, sign,
 303                                        vr0_lb, vr0_ub, vr1_lb, vr1_ub,
 304                                        overflow_undefined);
 305 }
 306
 307 /* Perform a left shift operation on two ranges:
 308
 309      [RES_LB, RES_UB] = [VR0_LB, VR0_UB] << [VR1_LB, VR1_LB]
 310
 311    Return TRUE if we were able to perform the operation.
 312
 313    NOTE: The resulting range must be canonicalized by the caller
 314    because its contents components may be swapped.  */
 315
 316 bool
 317 wide_int_range_lshift (wide_int &res_lb, wide_int &res_ub,
 318                        signop sign, unsigned prec,
 319                        const wide_int &vr0_lb, const wide_int &vr0_ub,
 320                        const wide_int &vr1_lb, const wide_int &vr1_ub,
 321                        bool overflow_undefined, bool overflow_wraps)
 322 {
 323   /* Transform left shifts by constants into multiplies.  */
 324   if (wi::eq_p (vr1_lb, vr1_ub))
 325     {
 326       int shift = wi::extract_uhwi (vr1_ub, 0, vr1_ub.get_precision ());
 327       wide_int tmp = wi::set_bit_in_zero (shift, prec);
 328       return wide_int_range_multiplicative_op (res_lb, res_ub,
 329                                                MULT_EXPR, sign, prec,
 330                                                vr0_lb, vr0_ub, tmp, tmp,
 331                                                overflow_undefined,
 332                                                /*overflow_wraps=*/true);
 333     }
 334
 335   int overflow_pos = prec;
 336   if (sign == SIGNED)
 337     overflow_pos -= 1;
 338   int bound_shift = overflow_pos - vr1_ub.to_shwi ();
 339   /* If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
 340      overflow.  However, for that to happen, vr1.max needs to be
 341      zero, which means vr1 is a singleton range of zero, which
 342      means it should be handled by the previous LSHIFT_EXPR
 343      if-clause.  */
 344   wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
 345   wide_int complement = ~(bound - 1);
 346   wide_int low_bound, high_bound;
 347   bool in_bounds = false;
 348   if (sign == UNSIGNED)
 349     {
 350       low_bound = bound;
 351       high_bound = complement;
 352       if (wi::ltu_p (vr0_ub, low_bound))
 353         {
 354           /* [5, 6] << [1, 2] == [10, 24].  */
 355           /* We're shifting out only zeroes, the value increases
 356              monotonically.  */
 357           in_bounds = true;
 358         }
 359       else if (wi::ltu_p (high_bound, vr0_lb))
 360         {
 361           /* [0xffffff00, 0xffffffff] << [1, 2]
 362              == [0xfffffc00, 0xfffffffe].  */
 363           /* We're shifting out only ones, the value decreases
 364              monotonically.  */
 365           in_bounds = true;
 366         }
 367     }
 368   else
 369     {
 370       /* [-1, 1] << [1, 2] == [-4, 4].  */
 371       low_bound = complement;
 372       high_bound = bound;
 373       if (wi::lts_p (vr0_ub, high_bound)
 374           && wi::lts_p (low_bound, vr0_lb))
 375         {
 376           /* For non-negative numbers, we're shifting out only
 377              zeroes, the value increases monotonically.
 378              For negative numbers, we're shifting out only ones, the
 379              value decreases monotomically.  */
 380           in_bounds = true;
 381         }
 382     }
 383   if (in_bounds)
 384     return wide_int_range_multiplicative_op (res_lb, res_ub,
 385                                              LSHIFT_EXPR, sign, prec,
 386                                              vr0_lb, vr0_ub,
 387                                              vr1_lb, vr1_ub,
 388                                              overflow_undefined,
 389                                              overflow_wraps);
 390   return false;
 391 }
 392
 393 /* Return TRUE if a bit operation on two ranges can be easily
 394    optimized in terms of a mask.
 395
 396    Basically, for BIT_AND_EXPR or BIT_IOR_EXPR see if we can optimize:
 397
 398         [LB, UB] op Z
 399    into:
 400         [LB op Z, UB op Z]
 401
 402    It is up to the caller to perform the actual folding above.  */
 403
 404 bool
 405 wide_int_range_can_optimize_bit_op (tree_code code,
 406                                     const wide_int &lb, const wide_int &ub,
 407                                     const wide_int &mask)
 408
 409 {
 410   if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR)
 411     return false;
 412   /* If Z is a constant which (for op | its bitwise not) has n
 413      consecutive least significant bits cleared followed by m 1
 414      consecutive bits set immediately above it and either
 415      m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
 416
 417      The least significant n bits of all the values in the range are
 418      cleared or set, the m bits above it are preserved and any bits
 419      above these are required to be the same for all values in the
 420      range.  */
 421
 422   wide_int w = mask;
 423   int m = 0, n = 0;
 424   if (code == BIT_IOR_EXPR)
 425     w = ~w;
 426   if (wi::eq_p (w, 0))
 427     n = w.get_precision ();
 428   else
 429     {
 430       n = wi::ctz (w);
 431       w = ~(w | wi::mask (n, false, w.get_precision ()));
 432       if (wi::eq_p (w, 0))
 433         m = w.get_precision () - n;
 434       else
 435         m = wi::ctz (w) - n;
 436     }
 437   wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
 438   if ((new_mask & lb) == (new_mask & ub))
 439     return true;
 440
 441   return false;
 442 }
 443
 444 /* Calculate the XOR of two ranges and store the result in [WMIN,WMAX].
 445    The two input ranges are described by their MUST_BE_NONZERO and
 446    MAY_BE_NONZERO bit masks.
 447
 448    Return TRUE if we were able to successfully calculate the new range.  */
 449
 450 bool
 451 wide_int_range_bit_xor (wide_int &wmin, wide_int &wmax,
 452                         signop sign,
 453                         unsigned prec,
 454                         const wide_int &must_be_nonzero0,
 455                         const wide_int &may_be_nonzero0,
 456                         const wide_int &must_be_nonzero1,
 457                         const wide_int &may_be_nonzero1)
 458 {
 459   wide_int result_zero_bits = ((must_be_nonzero0 & must_be_nonzero1)
 460                                | ~(may_be_nonzero0 | may_be_nonzero1));
 461   wide_int result_one_bits
 462     = (wi::bit_and_not (must_be_nonzero0, may_be_nonzero1)
 463        | wi::bit_and_not (must_be_nonzero1, may_be_nonzero0));
 464   wmax = ~result_zero_bits;
 465   wmin = result_one_bits;
 466   /* If the range has all positive or all negative values, the result
 467      is better than VARYING.  */
 468   if (wi::lt_p (wmin, 0, sign) || wi::ge_p (wmax, 0, sign))
 469     return true;
 470   wmin = wi::min_value (prec, sign);
 471   wmax = wi::max_value (prec, sign);
 472   return false;
 473 }
 474
 475 /* Calculate the IOR of two ranges and store the result in [WMIN,WMAX].
 476    Return TRUE if we were able to successfully calculate the new range.  */
 477
 478 bool
 479 wide_int_range_bit_ior (wide_int &wmin, wide_int &wmax,
 480                         signop sign,
 481                         const wide_int &vr0_min,
 482                         const wide_int &vr0_max,
 483                         const wide_int &vr1_min,
 484                         const wide_int &vr1_max,
 485                         const wide_int &must_be_nonzero0,
 486                         const wide_int &may_be_nonzero0,
 487                         const wide_int &must_be_nonzero1,
 488                         const wide_int &may_be_nonzero1)
 489 {
 490   wmin = must_be_nonzero0 | must_be_nonzero1;
 491   wmax = may_be_nonzero0 | may_be_nonzero1;
 492   /* If the input ranges contain only positive values we can
 493      truncate the minimum of the result range to the maximum
 494      of the input range minima.  */
 495   if (wi::ge_p (vr0_min, 0, sign)
 496       && wi::ge_p (vr1_min, 0, sign))
 497     {
 498       wmin = wi::max (wmin, vr0_min, sign);
 499       wmin = wi::max (wmin, vr1_min, sign);
 500     }
 501   /* If either input range contains only negative values
 502      we can truncate the minimum of the result range to the
 503      respective minimum range.  */
 504   if (wi::lt_p (vr0_max, 0, sign))
 505     wmin = wi::max (wmin, vr0_min, sign);
 506   if (wi::lt_p (vr1_max, 0, sign))
 507     wmin = wi::max (wmin, vr1_min, sign);
 508   /* If the limits got swapped around, indicate error so we can adjust
 509      the range to VARYING.  */
 510   if (wi::gt_p (wmin, wmax,sign))
 511     return false;
 512   return true;
 513 }
 514
 515 /* Calculate the bitwise AND of two ranges and store the result in [WMIN,WMAX].
 516    Return TRUE if we were able to successfully calculate the new range.  */
 517
 518 bool
 519 wide_int_range_bit_and (wide_int &wmin, wide_int &wmax,
 520                         signop sign,
 521                         unsigned prec,
 522                         const wide_int &vr0_min,
 523                         const wide_int &vr0_max,
 524                         const wide_int &vr1_min,
 525                         const wide_int &vr1_max,
 526                         const wide_int &must_be_nonzero0,
 527                         const wide_int &may_be_nonzero0,
 528                         const wide_int &must_be_nonzero1,
 529                         const wide_int &may_be_nonzero1)
 530 {
 531   wmin = must_be_nonzero0 & must_be_nonzero1;
 532   wmax = may_be_nonzero0 & may_be_nonzero1;
 533   /* If both input ranges contain only negative values we can
 534      truncate the result range maximum to the minimum of the
 535      input range maxima.  */
 536   if (wi::lt_p (vr0_max, 0, sign) && wi::lt_p (vr1_max, 0, sign))
 537     {
 538       wmax = wi::min (wmax, vr0_max, sign);
 539       wmax = wi::min (wmax, vr1_max, sign);
 540     }
 541   /* If either input range contains only non-negative values
 542      we can truncate the result range maximum to the respective
 543      maximum of the input range.  */
 544   if (wi::ge_p (vr0_min, 0, sign))
 545     wmax = wi::min (wmax, vr0_max, sign);
 546   if (wi::ge_p (vr1_min, 0, sign))
 547     wmax = wi::min (wmax, vr1_max, sign);
 548   /* PR68217: In case of signed & sign-bit-CST should
 549      result in [-INF, 0] instead of [-INF, INF].  */
 550   if (wi::gt_p (wmin, wmax, sign))
 551     {
 552       wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
 553       if (sign == SIGNED
 554           && ((wi::eq_p (vr0_min, vr0_max)
 555                && !wi::cmps (vr0_min, sign_bit))
 556               || (wi::eq_p (vr1_min, vr1_max)
 557                   && !wi::cmps (vr1_min, sign_bit))))
 558         {
 559           wmin = wi::min_value (prec, sign);
 560           wmax = wi::zero (prec);
 561         }
 562     }
 563   /* If the limits got swapped around, indicate error so we can adjust
 564      the range to VARYING.  */
 565   if (wi::gt_p (wmin, wmax,sign))
 566     return false;
 567   return true;
 568 }
 569
 570 /* Calculate TRUNC_MOD_EXPR on two ranges and store the result in
 571    [WMIN,WMAX].  */
 572
 573 void
 574 wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax,
 575                           signop sign,
 576                           unsigned prec,
 577                           const wide_int &vr0_min,
 578                           const wide_int &vr0_max,
 579                           const wide_int &vr1_min,
 580                           const wide_int &vr1_max)
 581 {
 582   wide_int tmp;
 583
 584   /* ABS (A % B) < ABS (B) and either
 585      0 <= A % B <= A or A <= A % B <= 0.  */
 586   wmax = vr1_max - 1;
 587   if (sign == SIGNED)
 588     {
 589       tmp = -1 - vr1_min;
 590       wmax = wi::smax (wmax, tmp);
 591     }
 592
 593   if (sign == UNSIGNED)
 594     wmin = wi::zero (prec);
 595   else
 596     {
 597       wmin = -wmax;
 598       tmp = vr0_min;
 599       if (wi::gts_p (tmp, 0))
 600         tmp = wi::zero (prec);
 601       wmin = wi::smax (wmin, tmp);
 602     }
 603   tmp = vr0_max;
 604   if (sign == SIGNED && wi::neg_p (tmp))
 605     tmp = wi::zero (prec);
 606   wmax = wi::min (wmax, tmp, sign);
 607 }