gcc/d/dmd/intrange.d

   1 /**
   2  * Implement $(LINK2 https://digitalmars.com/articles/b62.html, Value Range Propagation).
   3  *
   4  * Copyright:   Copyright (C) 1999-2024 by The D Language Foundation, All Rights Reserved
   5  * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
   6  * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
   7  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/intrange.d, _intrange.d)
   8  * Documentation:  https://dlang.org/phobos/dmd_intrange.html
   9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/intrange.d
  10  */
  11
  12 module dmd.intrange;
  13
  14 import core.stdc.stdio;
  15
  16 import dmd.astenums;
  17 import dmd.mtype;
  18 import dmd.expression;
  19 import dmd.globals;
  20
  21 private uinteger_t copySign(uinteger_t x, bool sign) @safe
  22 {
  23     // return sign ? -x : x;
  24     return (x - cast(uinteger_t)sign) ^ -cast(uinteger_t)sign;
  25 }
  26
  27 struct SignExtendedNumber
  28 {
  29     uinteger_t value;
  30     bool negative;
  31
  32     static SignExtendedNumber fromInteger(uinteger_t value_) @safe
  33     {
  34         return SignExtendedNumber(value_, value_ >> 63);
  35     }
  36
  37     static SignExtendedNumber extreme(bool minimum) @safe
  38     {
  39         return SignExtendedNumber(minimum - 1, minimum);
  40     }
  41
  42     static SignExtendedNumber max() @safe
  43     {
  44         return SignExtendedNumber(ulong.max, false);
  45     }
  46
  47     static SignExtendedNumber min() @safe
  48     {
  49         return SignExtendedNumber(0, true);
  50     }
  51
  52     bool isMinimum() const @safe
  53     {
  54         return negative && value == 0;
  55     }
  56
  57     bool opEquals(const ref SignExtendedNumber a) const @safe
  58     {
  59         return value == a.value && negative == a.negative;
  60     }
  61
  62     int opCmp(const ref SignExtendedNumber a) const @safe
  63     {
  64         if (negative != a.negative)
  65         {
  66             if (negative)
  67                 return -1;
  68             else
  69                 return 1;
  70         }
  71         if (value < a.value)
  72             return -1;
  73         else if (value > a.value)
  74             return 1;
  75         else
  76             return 0;
  77     }
  78
  79     SignExtendedNumber opUnary(string op : "++")()
  80     {
  81         if (value != ulong.max)
  82             ++value;
  83         else if (negative)
  84         {
  85             value = 0;
  86             negative = false;
  87         }
  88         return this;
  89     }
  90
  91     SignExtendedNumber opUnary(string op : "~")() const
  92     {
  93         if (~value == 0)
  94             return SignExtendedNumber(~value);
  95         else
  96             return SignExtendedNumber(~value, !negative);
  97     }
  98
  99     SignExtendedNumber opUnary(string op : "-")() const
 100     {
 101         if (value == 0)
 102             return SignExtendedNumber(-cast(ulong)negative);
 103         else
 104             return SignExtendedNumber(-value, !negative);
 105     }
 106
 107     SignExtendedNumber opBinary(string op : "&")(SignExtendedNumber rhs) const
 108     {
 109         return SignExtendedNumber(value & rhs.value);
 110     }
 111
 112     SignExtendedNumber opBinary(string op : "|")(SignExtendedNumber rhs)
 113     {
 114         return SignExtendedNumber(value | rhs.value);
 115     }
 116
 117     SignExtendedNumber opBinary(string op : "^")(SignExtendedNumber rhs)
 118     {
 119         return SignExtendedNumber(value ^ rhs.value);
 120     }
 121
 122     SignExtendedNumber opBinary(string op : "+")(SignExtendedNumber rhs)
 123     {
 124         uinteger_t sum = value + rhs.value;
 125         bool carry = sum < value && sum < rhs.value;
 126         if (negative != rhs.negative)
 127             return SignExtendedNumber(sum, !carry);
 128         else if (negative)
 129             return SignExtendedNumber(carry ? sum : 0, true);
 130         else
 131             return SignExtendedNumber(carry ? ulong.max : sum, false);
 132     }
 133
 134
 135     SignExtendedNumber opBinary(string op : "-")(SignExtendedNumber rhs)
 136     {
 137         if (rhs.isMinimum())
 138             return negative ? SignExtendedNumber(value, false) : max();
 139         else
 140             return this + (-rhs);
 141     }
 142
 143     SignExtendedNumber opBinary(string op : "*")(SignExtendedNumber rhs)
 144     {
 145         // perform *saturated* multiplication, otherwise we may get bogus ranges
 146         //  like 0x10 * 0x10 == 0x100 == 0.
 147
 148         /* Special handling for zeros:
 149             INT65_MIN * 0 = 0
 150             INT65_MIN * + = INT65_MIN
 151             INT65_MIN * - = INT65_MAX
 152             0 * anything = 0
 153         */
 154         if (value == 0)
 155         {
 156             if (!negative)
 157                 return this;
 158             else if (rhs.negative)
 159                 return max();
 160             else
 161                 return rhs.value == 0 ? rhs : this;
 162         }
 163         else if (rhs.value == 0)
 164             return rhs * this; // don't duplicate the symmetric case.
 165
 166         SignExtendedNumber rv;
 167         // these are != 0 now surely.
 168         uinteger_t tAbs = copySign(value, negative);
 169         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
 170         rv.negative = negative != rhs.negative;
 171         if (ulong.max / tAbs < aAbs)
 172             rv.value = rv.negative - 1;
 173         else
 174             rv.value = copySign(tAbs * aAbs, rv.negative);
 175         return rv;
 176     }
 177
 178     SignExtendedNumber opBinary(string op : "/")(SignExtendedNumber rhs)
 179     {
 180         /* special handling for zeros:
 181             INT65_MIN / INT65_MIN = 1
 182             anything / INT65_MIN = 0
 183             + / 0 = INT65_MAX  (eh?)
 184             - / 0 = INT65_MIN  (eh?)
 185         */
 186         if (rhs.value == 0)
 187         {
 188             if (rhs.negative)
 189                 return SignExtendedNumber(value == 0 && negative);
 190             else
 191                 return extreme(negative);
 192         }
 193
 194         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
 195         uinteger_t rvVal;
 196
 197         if (!isMinimum())
 198             rvVal = copySign(value, negative) / aAbs;
 199         // Special handling for INT65_MIN
 200         //  if the denominator is not a power of 2, it is same as ulong.max / x.
 201         else if (aAbs & (aAbs - 1))
 202             rvVal = ulong.max / aAbs;
 203         // otherwise, it's the same as reversing the bits of x.
 204         else
 205         {
 206             if (aAbs == 1)
 207                 return extreme(!rhs.negative);
 208             rvVal = 1UL << 63;
 209             aAbs >>= 1;
 210             if (aAbs & 0xAAAAAAAAAAAAAAAAUL) rvVal >>= 1;
 211             if (aAbs & 0xCCCCCCCCCCCCCCCCUL) rvVal >>= 2;
 212             if (aAbs & 0xF0F0F0F0F0F0F0F0UL) rvVal >>= 4;
 213             if (aAbs & 0xFF00FF00FF00FF00UL) rvVal >>= 8;
 214             if (aAbs & 0xFFFF0000FFFF0000UL) rvVal >>= 16;
 215             if (aAbs & 0xFFFFFFFF00000000UL) rvVal >>= 32;
 216         }
 217         bool rvNeg = negative != rhs.negative;
 218         rvVal = copySign(rvVal, rvNeg);
 219
 220         return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg);
 221     }
 222
 223     SignExtendedNumber opBinary(string op : "%")(SignExtendedNumber rhs)
 224     {
 225         if (rhs.value == 0)
 226             return !rhs.negative ? rhs : isMinimum() ? SignExtendedNumber(0) : this;
 227
 228         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
 229         uinteger_t rvVal;
 230
 231         // a % b == sgn(a) * abs(a) % abs(b).
 232         if (!isMinimum())
 233             rvVal = copySign(value, negative) % aAbs;
 234         // Special handling for INT65_MIN
 235         //  if the denominator is not a power of 2, it is same as ulong.max % x + 1.
 236         else if (aAbs & (aAbs - 1))
 237             rvVal = ulong.max % aAbs + 1;
 238         //  otherwise, the modulus is trivially zero.
 239         else
 240             rvVal = 0;
 241
 242         rvVal = copySign(rvVal, negative);
 243         return SignExtendedNumber(rvVal, rvVal != 0 && negative);
 244     }
 245
 246     SignExtendedNumber opBinary(string op : "<<")(SignExtendedNumber rhs)
 247     {
 248         // assume left-shift the shift-amount is always unsigned. Thus negative
 249         //  shifts will give huge result.
 250         if (value == 0)
 251             return this;
 252         else if (rhs.negative)
 253             return extreme(negative);
 254
 255         uinteger_t v = copySign(value, negative);
 256
 257         // compute base-2 log of 'v' to determine the maximum allowed bits to shift.
 258         // Ref: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
 259
 260         // Why is this a size_t? Looks like a bug.
 261         size_t r, s;
 262
 263         r = (v > 0xFFFFFFFFUL) << 5; v >>= r;
 264         s = (v > 0xFFFFUL    ) << 4; v >>= s; r |= s;
 265         s = (v > 0xFFUL      ) << 3; v >>= s; r |= s;
 266         s = (v > 0xFUL       ) << 2; v >>= s; r |= s;
 267         s = (v > 0x3UL       ) << 1; v >>= s; r |= s;
 268                                                r |= (v >> 1);
 269
 270         uinteger_t allowableShift = 63 - r;
 271         if (rhs.value > allowableShift)
 272             return extreme(negative);
 273         else
 274             return SignExtendedNumber(value << rhs.value, negative);
 275     }
 276
 277     SignExtendedNumber opBinary(string op : ">>")(SignExtendedNumber rhs)
 278     {
 279         if (rhs.negative || rhs.value > 63)
 280             return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0);
 281         else if (isMinimum())
 282             return rhs.value == 0 ? this : SignExtendedNumber(-1UL << (64 - rhs.value), true);
 283
 284         uinteger_t x = value ^ -cast(int)negative;
 285         x >>= rhs.value;
 286         return SignExtendedNumber(x ^ -cast(int)negative, negative);
 287     }
 288
 289     SignExtendedNumber opBinary(string op : "^^")(SignExtendedNumber rhs)
 290     {
 291         // Not yet implemented
 292         assert(0);
 293     }
 294 }
 295
 296 struct IntRange
 297 {
 298     SignExtendedNumber imin, imax;
 299
 300     this(IntRange another) @safe
 301     {
 302         imin = another.imin;
 303         imax = another.imax;
 304     }
 305
 306     this(SignExtendedNumber a) @safe
 307     {
 308         imin = a;
 309         imax = a;
 310     }
 311
 312     this(SignExtendedNumber lower, SignExtendedNumber upper) @safe
 313     {
 314         imin = lower;
 315         imax = upper;
 316     }
 317
 318     static IntRange fromType(Type type)
 319     {
 320         return fromType(type, type.isunsigned());
 321     }
 322
 323     static IntRange fromType(Type type, bool isUnsigned)
 324     {
 325         if (!type.isintegral() || type.toBasetype().ty == Tvector)
 326             return widest();
 327
 328         uinteger_t mask = type.sizemask();
 329         auto lower = SignExtendedNumber(0);
 330         auto upper = SignExtendedNumber(mask);
 331         if (type.toBasetype().ty == Tdchar)
 332             upper.value = 0x10FFFFUL;
 333         else if (!isUnsigned)
 334         {
 335             lower.value = ~(mask >> 1);
 336             lower.negative = true;
 337             upper.value = (mask >> 1);
 338         }
 339         return IntRange(lower, upper);
 340     }
 341
 342     static IntRange fromNumbers2(SignExtendedNumber* numbers)
 343     {
 344         if (numbers[0] < numbers[1])
 345             return IntRange(numbers[0], numbers[1]);
 346         else
 347             return IntRange(numbers[1], numbers[0]);
 348     }
 349
 350     static IntRange fromNumbers4(SignExtendedNumber* numbers)
 351     {
 352         IntRange ab = fromNumbers2(numbers);
 353         IntRange cd = fromNumbers2(numbers + 2);
 354         if (cd.imin < ab.imin)
 355             ab.imin = cd.imin;
 356         if (cd.imax > ab.imax)
 357             ab.imax = cd.imax;
 358         return ab;
 359     }
 360
 361     static IntRange widest() @safe
 362     {
 363         return IntRange(SignExtendedNumber.min(), SignExtendedNumber.max());
 364     }
 365
 366     IntRange castSigned(uinteger_t mask) @safe
 367     {
 368         // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
 369         //
 370         // regular signed type. We use a technique similar to the unsigned version,
 371         //  but the chunk has to be offset by 1/2 of the range.
 372         uinteger_t halfChunkMask = mask >> 1;
 373         uinteger_t minHalfChunk = imin.value & ~halfChunkMask;
 374         uinteger_t maxHalfChunk = imax.value & ~halfChunkMask;
 375         int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
 376         int maxHalfChunkNegativity = imax.negative;
 377         if (minHalfChunk & mask)
 378         {
 379             minHalfChunk += halfChunkMask + 1;
 380             if (minHalfChunk == 0)
 381                 --minHalfChunkNegativity;
 382         }
 383         if (maxHalfChunk & mask)
 384         {
 385             maxHalfChunk += halfChunkMask + 1;
 386             if (maxHalfChunk == 0)
 387                 --maxHalfChunkNegativity;
 388         }
 389         if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity)
 390         {
 391             imin.value &= mask;
 392             imax.value &= mask;
 393             // sign extend if necessary.
 394             imin.negative = (imin.value & ~halfChunkMask) != 0;
 395             imax.negative = (imax.value & ~halfChunkMask) != 0;
 396             halfChunkMask += 1;
 397             imin.value = (imin.value ^ halfChunkMask) - halfChunkMask;
 398             imax.value = (imax.value ^ halfChunkMask) - halfChunkMask;
 399         }
 400         else
 401         {
 402             imin = SignExtendedNumber(~halfChunkMask, true);
 403             imax = SignExtendedNumber(halfChunkMask, false);
 404         }
 405         return this;
 406     }
 407
 408     IntRange castUnsigned(uinteger_t mask) @safe
 409     {
 410         // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
 411         //
 412         // regular unsigned type. We just need to see if ir steps across the
 413         //  boundary of validRange. If yes, ir will represent the whole validRange,
 414         //  otherwise, we just take the modulus.
 415         // e.g. [0x105, 0x107] & 0xff == [5, 7]
 416         //      [0x105, 0x207] & 0xff == [0, 0xff]
 417         uinteger_t minChunk = imin.value & ~mask;
 418         uinteger_t maxChunk = imax.value & ~mask;
 419         if (minChunk == maxChunk && imin.negative == imax.negative)
 420         {
 421             imin.value &= mask;
 422             imax.value &= mask;
 423         }
 424         else
 425         {
 426             imin.value = 0;
 427             imax.value = mask;
 428         }
 429         imin.negative = imax.negative = false;
 430         return this;
 431     }
 432
 433     IntRange castDchar() @safe
 434     {
 435         // special case for dchar. Casting to dchar means "I'll ignore all
 436         //  invalid characters."
 437         castUnsigned(0xFFFFFFFFUL);
 438         if (imin.value > 0x10FFFFUL) // ??
 439             imin.value = 0x10FFFFUL; // ??
 440         if (imax.value > 0x10FFFFUL)
 441             imax.value = 0x10FFFFUL;
 442         return this;
 443     }
 444
 445     IntRange _cast(Type type)
 446     {
 447         if (!type.isintegral() || type.toBasetype().ty == Tvector)
 448             return this;
 449         else if (!type.isunsigned())
 450             return castSigned(type.sizemask());
 451         else if (type.toBasetype().ty == Tdchar)
 452             return castDchar();
 453         else
 454             return castUnsigned(type.sizemask());
 455     }
 456
 457     IntRange castUnsigned(Type type)
 458     {
 459         if (!type.isintegral() || type.toBasetype().ty == Tvector)
 460             return castUnsigned(ulong.max);
 461         else if (type.toBasetype().ty == Tdchar)
 462             return castDchar();
 463         else
 464             return castUnsigned(type.sizemask());
 465     }
 466
 467     bool contains(IntRange a) @safe
 468     {
 469         return imin <= a.imin && imax >= a.imax;
 470     }
 471
 472     bool containsZero() const @safe
 473     {
 474         return (imin.negative && !imax.negative)
 475             || (!imin.negative && imin.value == 0);
 476     }
 477
 478     IntRange absNeg() const @safe
 479     {
 480         if (imax.negative)
 481             return this;
 482         else if (!imin.negative)
 483             return IntRange(-imax, -imin);
 484         else
 485         {
 486             SignExtendedNumber imaxAbsNeg = -imax;
 487             return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin,
 488                             SignExtendedNumber(0));
 489         }
 490     }
 491
 492     IntRange unionWith(const ref IntRange other) const @safe
 493     {
 494         return IntRange(imin < other.imin ? imin : other.imin,
 495                         imax > other.imax ? imax : other.imax);
 496     }
 497
 498     void unionOrAssign(IntRange other, ref bool union_) @safe
 499     {
 500         if (!union_ || imin > other.imin)
 501             imin = other.imin;
 502         if (!union_ || imax < other.imax)
 503             imax = other.imax;
 504         union_ = true;
 505     }
 506
 507     ref const(IntRange) dump(const(char)* funcName, Expression e) const return
 508     {
 509         printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n",
 510                imin.negative?'-':'+', cast(ulong)imin.value,
 511                imax.negative?'-':'+', cast(ulong)imax.value,
 512                funcName, e.toChars());
 513         return this;
 514     }
 515
 516     void splitBySign(ref IntRange negRange, ref bool hasNegRange, ref IntRange nonNegRange, ref bool hasNonNegRange) const @safe
 517     {
 518         hasNegRange = imin.negative;
 519         if (hasNegRange)
 520         {
 521             negRange.imin = imin;
 522             negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true);
 523         }
 524         hasNonNegRange = !imax.negative;
 525         if (hasNonNegRange)
 526         {
 527             nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin;
 528             nonNegRange.imax = imax;
 529         }
 530     }
 531
 532     IntRange opUnary(string op:"~")() const
 533     {
 534         return IntRange(~imax, ~imin);
 535     }
 536
 537     IntRange opUnary(string op : "-")()
 538     {
 539         return IntRange(-imax, -imin);
 540     }
 541
 542     // Credits to Timon Gehr for the algorithms for &, |
 543     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 544     IntRange opBinary(string op : "&")(IntRange rhs) const
 545     {
 546         // unsigned or identical sign bits
 547         if ((imin.negative ^ imax.negative) != 1 && (rhs.imin.negative ^ rhs.imax.negative) != 1)
 548         {
 549             return IntRange(minAnd(this, rhs), maxAnd(this, rhs));
 550         }
 551
 552         IntRange l = IntRange(this);
 553         IntRange r = IntRange(rhs);
 554
 555         // both intervals span [-1,0]
 556         if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
 557         {
 558             // cannot be larger than either l.max or r.max, set the other one to -1
 559             SignExtendedNumber max = l.imax.value > r.imax.value ? l.imax : r.imax;
 560
 561             // only negative numbers for minimum
 562             l.imax.value = -1;
 563             l.imax.negative = true;
 564             r.imax.value = -1;
 565             r.imax.negative = true;
 566
 567             return IntRange(minAnd(l, r), max);
 568         }
 569         else
 570         {
 571             // only one interval spans [-1,0]
 572             if ((l.imin.negative ^ l.imax.negative) == 1)
 573             {
 574                 swap(l, r); // r spans [-1,0]
 575             }
 576
 577             auto minAndNeg = minAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
 578             auto minAndPos = minAnd(l, IntRange(SignExtendedNumber(0), r.imax));
 579             auto maxAndNeg = maxAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
 580             auto maxAndPos = maxAnd(l, IntRange(SignExtendedNumber(0), r.imax));
 581
 582             auto min = minAndNeg < minAndPos ? minAndNeg : minAndPos;
 583             auto max = maxAndNeg > maxAndPos ? maxAndNeg : maxAndPos;
 584
 585             auto range = IntRange(min, max);
 586             return range;
 587         }
 588     }
 589
 590     // Credits to Timon Gehr for the algorithms for &, |
 591     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 592     IntRange opBinary(string op : "|")(IntRange rhs) const
 593     {
 594         // unsigned or identical sign bits:
 595         if ((imin.negative ^ imax.negative) == 0 && (rhs.imin.negative ^ rhs.imax.negative) == 0)
 596         {
 597             return IntRange(minOr(this, rhs), maxOr(this, rhs));
 598         }
 599
 600         IntRange l = IntRange(this);
 601         IntRange r = IntRange(rhs);
 602
 603         // both intervals span [-1,0]
 604         if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
 605         {
 606             // cannot be smaller than either l.min or r.min, set the other one to 0
 607             SignExtendedNumber min = l.imin.value < r.imin.value ? l.imin : r.imin;
 608
 609             // only negative numbers for minimum
 610             l.imin.value = 0;
 611             l.imin.negative = false;
 612             r.imin.value = 0;
 613             r.imin.negative = false;
 614
 615             return IntRange(min, maxOr(l, r));
 616         }
 617         else
 618         {
 619             // only one interval spans [-1,0]
 620             if ((imin.negative ^ imax.negative) == 1)
 621             {
 622                 swap(l, r); // r spans [-1,0]
 623             }
 624
 625             auto minOrNeg = minOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
 626             auto minOrPos = minOr(l, IntRange(SignExtendedNumber(0), r.imax));
 627             auto maxOrNeg = maxOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
 628             auto maxOrPos = maxOr(l, IntRange(SignExtendedNumber(0), r.imax));
 629
 630             auto min = minOrNeg < minOrPos ? minOrNeg : minOrPos;
 631             auto max = maxOrNeg > maxOrPos ? maxOrNeg : maxOrPos;
 632
 633             auto range = IntRange(min, max);
 634             return range;
 635         }
 636     }
 637
 638     IntRange opBinary(string op : "^")(IntRange rhs) const
 639     {
 640         return this & ~rhs | ~this & rhs;
 641     }
 642
 643     IntRange opBinary(string op : "+")(IntRange rhs)
 644     {
 645         return IntRange(imin + rhs.imin, imax + rhs.imax);
 646     }
 647
 648     IntRange opBinary(string op : "-")(IntRange rhs)
 649     {
 650         return IntRange(imin - rhs.imax, imax - rhs.imin);
 651     }
 652
 653     IntRange opBinary(string op : "*")(IntRange rhs)
 654     {
 655         // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
 656         SignExtendedNumber[4] bdy;
 657         bdy[0] = imin * rhs.imin;
 658         bdy[1] = imin * rhs.imax;
 659         bdy[2] = imax * rhs.imin;
 660         bdy[3] = imax * rhs.imax;
 661         return IntRange.fromNumbers4(bdy.ptr);
 662     }
 663
 664     IntRange opBinary(string op : "/")(IntRange rhs)
 665     {
 666         // Handle divide by 0
 667         if (rhs.imax.value == 0 && rhs.imin.value == 0)
 668             return widest();
 669
 670         // Don't treat the whole range as divide by 0 if only one end of a range is 0.
 671         // Issue 15289
 672         if (rhs.imax.value == 0)
 673         {
 674             rhs.imax.value--;
 675         }
 676         else if(rhs.imin.value == 0)
 677         {
 678             rhs.imin.value++;
 679         }
 680
 681         if (!imin.negative && !imax.negative && !rhs.imin.negative && !rhs.imax.negative)
 682         {
 683             return IntRange(imin / rhs.imax, imax / rhs.imin);
 684         }
 685         else
 686         {
 687             // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
 688             SignExtendedNumber[4] bdy;
 689             bdy[0] = imin / rhs.imin;
 690             bdy[1] = imin / rhs.imax;
 691             bdy[2] = imax / rhs.imin;
 692             bdy[3] = imax / rhs.imax;
 693
 694             return IntRange.fromNumbers4(bdy.ptr);
 695         }
 696     }
 697
 698     IntRange opBinary(string op : "%")(IntRange rhs)
 699     {
 700         IntRange irNum = this;
 701         IntRange irDen = rhs.absNeg();
 702
 703         /*
 704          due to the rules of D (C)'s % operator, we need to consider the cases
 705          separately in different range of signs.
 706
 707              case 1. [500, 1700] % [7, 23] (numerator is always positive)
 708                  = [0, 22]
 709              case 2. [-500, 1700] % [7, 23] (numerator can be negative)
 710                  = [-22, 22]
 711              case 3. [-1700, -500] % [7, 23] (numerator is always negative)
 712                  = [-22, 0]
 713
 714          the number 22 is the maximum absolute value in the denomator's range. We
 715          don't care about divide by zero.
 716          */
 717
 718         irDen.imin = irDen.imin + SignExtendedNumber(1);
 719         irDen.imax = -irDen.imin;
 720
 721         if (!irNum.imin.negative)
 722         {
 723             irNum.imin.value = 0;
 724         }
 725         else if (irNum.imin < irDen.imin)
 726         {
 727             irNum.imin = irDen.imin;
 728         }
 729
 730         if (irNum.imax.negative)
 731         {
 732             irNum.imax.negative = false;
 733             irNum.imax.value = 0;
 734         }
 735         else if (irNum.imax > irDen.imax)
 736         {
 737             irNum.imax = irDen.imax;
 738         }
 739
 740         return irNum;
 741     }
 742
 743     IntRange opBinary(string op : "<<")(IntRange rhs)
 744     {
 745         if (rhs.imin.negative)
 746         {
 747             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
 748         }
 749
 750         SignExtendedNumber lower = imin << (imin.negative ? rhs.imax : rhs.imin);
 751         SignExtendedNumber upper = imax << (imax.negative ? rhs.imin : rhs.imax);
 752
 753         return IntRange(lower, upper);
 754     }
 755
 756     IntRange opBinary(string op : ">>")(IntRange rhs)
 757     {
 758         if (rhs.imin.negative)
 759         {
 760             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
 761         }
 762
 763         SignExtendedNumber lower = imin >> (imin.negative ? rhs.imin : rhs.imax);
 764         SignExtendedNumber upper = imax >> (imax.negative ? rhs.imax : rhs.imin);
 765
 766         return IntRange(lower, upper);
 767     }
 768
 769     IntRange opBinary(string op : ">>>")(IntRange rhs)
 770     {
 771         if (rhs.imin.negative)
 772         {
 773             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
 774         }
 775
 776         return IntRange(imin >> rhs.imax, imax >> rhs.imin);
 777     }
 778
 779     IntRange opBinary(string op : "^^")(IntRange rhs)
 780     {
 781         // Not yet implemented
 782         assert(0);
 783     }
 784
 785 private:
 786     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
 787     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 788     static SignExtendedNumber maxOr(const IntRange lhs, const IntRange rhs) @safe
 789     {
 790         uinteger_t x = 0;
 791         auto sign = false;
 792         auto xor = lhs.imax.value ^ rhs.imax.value;
 793         auto and = lhs.imax.value & rhs.imax.value;
 794         auto lhsc = IntRange(lhs);
 795         auto rhsc = IntRange(rhs);
 796
 797         // Sign bit not part of the .value so we need an extra iteration
 798         if (lhsc.imax.negative ^ rhsc.imax.negative)
 799         {
 800             sign = true;
 801             if (lhsc.imax.negative)
 802             {
 803                 if (!lhsc.imin.negative)
 804                 {
 805                     lhsc.imin.value = 0;
 806                 }
 807                 if (!rhsc.imin.negative)
 808                 {
 809                     rhsc.imin.value = 0;
 810                 }
 811             }
 812         }
 813         else if (lhsc.imin.negative & rhsc.imin.negative)
 814         {
 815             sign = true;
 816         }
 817         else if (lhsc.imax.negative & rhsc.imax.negative)
 818         {
 819             return SignExtendedNumber(-1, false);
 820         }
 821
 822         for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
 823         {
 824             if (xor & d)
 825             {
 826                 x |= d;
 827                 if (lhsc.imax.value & d)
 828                 {
 829                     if (~lhsc.imin.value & d)
 830                     {
 831                         lhsc.imin.value = 0;
 832                     }
 833                 }
 834                 else
 835                 {
 836                     if (~rhsc.imin.value & d)
 837                     {
 838                         rhsc.imin.value = 0;
 839                     }
 840                 }
 841             }
 842             else if (lhsc.imin.value & rhsc.imin.value & d)
 843             {
 844                 x |= d;
 845             }
 846             else if (and & d)
 847             {
 848                 x |= (d << 1) - 1;
 849                 break;
 850             }
 851         }
 852
 853         auto range = SignExtendedNumber(x, sign);
 854         return range;
 855     }
 856
 857     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
 858     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 859     static SignExtendedNumber minOr(const IntRange lhs, const IntRange rhs) @safe
 860     {
 861         return ~maxAnd(~lhs, ~rhs);
 862     }
 863
 864     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
 865     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 866     static SignExtendedNumber maxAnd(const IntRange lhs, const IntRange rhs) @safe
 867     {
 868         uinteger_t x = 0;
 869         bool sign = false;
 870         auto lhsc = IntRange(lhs);
 871         auto rhsc = IntRange(rhs);
 872
 873         if (lhsc.imax.negative & rhsc.imax.negative)
 874         {
 875             sign = true;
 876         }
 877
 878         for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
 879         {
 880             if (lhsc.imax.value & rhsc.imax.value & d)
 881             {
 882                 x |= d;
 883                 if (~lhsc.imin.value & d)
 884                 {
 885                     lhsc.imin.value = 0;
 886                 }
 887                 if (~rhsc.imin.value & d)
 888                 {
 889                     rhsc.imin.value = 0;
 890                 }
 891             }
 892             else if (~lhsc.imin.value & d && lhsc.imax.value & d)
 893             {
 894                 lhsc.imax.value |= d - 1;
 895             }
 896             else if (~rhsc.imin.value & d && rhsc.imax.value & d)
 897             {
 898                 rhsc.imax.value |= d - 1;
 899             }
 900         }
 901
 902         auto range = SignExtendedNumber(x, sign);
 903         return range;
 904     }
 905
 906     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
 907     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
 908     static SignExtendedNumber minAnd(const IntRange lhs, const IntRange rhs) @safe
 909     {
 910         return ~maxOr(~lhs, ~rhs);
 911     }
 912
 913     static swap(ref IntRange a, ref IntRange b)
 914     {
 915         auto aux = a;
 916         a = b;
 917         b = aux;
 918     }
 919 }