gcc/d/dmd/intrange.c

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