dmd.intrange source code

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