1 2/* Compiler implementation of the D programming language 3 * Copyright (C) 1999-2019 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`. 19static 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 31SignExtendedNumber SignExtendedNumber::fromInteger(uinteger_t value_) 32{ 33 return SignExtendedNumber(value_, value_ >> 63); 34} 35 36bool SignExtendedNumber::operator==(const SignExtendedNumber& a) const 37{ 38 return value == a.value && negative == a.negative; 39} 40 41bool SignExtendedNumber::operator<(const SignExtendedNumber& a) const 42{ 43 return (negative && !a.negative) 44 || (negative == a.negative && value < a.value); 45} 46 47SignExtendedNumber SignExtendedNumber::extreme(bool minimum) 48{ 49 return SignExtendedNumber(minimum-1, minimum); 50} 51 52SignExtendedNumber SignExtendedNumber::max() 53{ 54 return SignExtendedNumber(UINT64_MAX, false); 55} 56 57SignExtendedNumber& 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 69SignExtendedNumber SignExtendedNumber::operator~() const 70{ 71 if (~value == 0) 72 return SignExtendedNumber(~value); 73 else 74 return SignExtendedNumber(~value, !negative); 75} 76 77SignExtendedNumber SignExtendedNumber::operator-() const 78{ 79 if (value == 0) 80 return SignExtendedNumber(-negative); 81 else 82 return SignExtendedNumber(-value, !negative); 83} 84 85SignExtendedNumber SignExtendedNumber::operator&(const SignExtendedNumber& rhs) const 86{ 87 return SignExtendedNumber(value & rhs.value); 88} 89 90SignExtendedNumber SignExtendedNumber::operator|(const SignExtendedNumber& rhs) const 91{ 92 return SignExtendedNumber(value | rhs.value); 93} 94 95SignExtendedNumber SignExtendedNumber::operator^(const SignExtendedNumber& rhs) const 96{ 97 return SignExtendedNumber(value ^ rhs.value); 98} 99 100SignExtendedNumber 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 112SignExtendedNumber 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 120SignExtendedNumber 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 155SignExtendedNumber 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 200SignExtendedNumber 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 223SignExtendedNumber 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 254SignExtendedNumber 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 269IntRange IntRange::widest() 270{ 271 return IntRange(SignExtendedNumber::min(), SignExtendedNumber::max()); 272} 273 274IntRange IntRange::fromType(Type *type) 275{ 276 return fromType(type, type->isunsigned()); 277} 278 279IntRange IntRange::fromType(Type *type, bool isUnsigned) 280{ 281 if (!type->isintegral() || type->toBasetype()->ty == Tvector) 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 297IntRange 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} 304IntRange 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 315bool IntRange::contains(const IntRange& a) const 316{ 317 return imin <= a.imin && imax >= a.imax; 318} 319 320bool IntRange::containsZero() const 321{ 322 return (imin.negative && !imax.negative) 323 || (!imin.negative && imin.value == 0); 324} 325 326IntRange& 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 351IntRange& 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 393IntRange& 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 405IntRange& IntRange::cast(Type *type) 406{ 407 if (!type->isintegral() || type->toBasetype()->ty == Tvector) 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 417IntRange& IntRange::castUnsigned(Type *type) 418{ 419 if (!type->isintegral() || type->toBasetype()->ty == Tvector) 420 return castUnsigned(UINT64_MAX); 421 else if (type->toBasetype()->ty == Tdchar) 422 return castDchar(); 423 else 424 return castUnsigned(type->sizemask()); 425} 426 427IntRange 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 441IntRange 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 447void 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 456void 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 473IntRange IntRange::operator~() const 474{ 475 return IntRange(~imax, ~imin); 476} 477 478IntRange IntRange::operator-() const 479{ 480 return IntRange(-imax, -imin); 481} 482 483IntRange 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 528IntRange 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 573IntRange IntRange::operator^(const IntRange& rhs) const 574{ 575 return (*this & (~rhs)) | (~(*this) & rhs); 576} 577 578IntRange IntRange::operator+(const IntRange& rhs) const 579{ 580 return IntRange(imin + rhs.imin, imax + rhs.imax); 581} 582 583IntRange IntRange::operator-(const IntRange& rhs) const 584{ 585 return IntRange(imin - rhs.imax, imax - rhs.imin); 586} 587 588IntRange 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 599IntRange 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 635IntRange 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 680IntRange 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 694IntRange 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 708SignExtendedNumber 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 776SignExtendedNumber IntRange::minOr(const IntRange& lhs, const IntRange& rhs) 777{ 778 return ~maxAnd(~lhs, ~rhs); 779} 780 781SignExtendedNumber 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 820SignExtendedNumber IntRange::minAnd(const IntRange& lhs, const IntRange& rhs) 821{ 822 return ~maxOr(~lhs, ~rhs); 823} 824 825void IntRange::swap(IntRange& a, IntRange& b) 826{ 827 IntRange aux = a; 828 a = b; 829 b = aux; 830} 831 832const 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} 840