X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FSupport%2FAPInt.cpp;h=a034fd1e797076b69a121fcfcee5a77f33861b52;hb=3a4a884c1618d94202ee714ea5c899cd80d1c536;hp=ae9b066684cfb93335a69b6c07264ce64a780053;hpb=bf5836b075a7fdd680e7c43134237bdef65643cf;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index ae9b066684c..a034fd1e797 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/SmallString.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include @@ -675,12 +676,11 @@ static inline uint32_t hashword(const uint64_t *k64, size_t length) } /*------------------------------------------- handle the last 3 uint32_t's */ - switch(length) /* all the case statements fall through */ - { - case 3 : c+=k[2]; - case 2 : b+=k[1]; - case 1 : a+=k[0]; - final(a,b,c); + switch (length) { /* all the case statements fall through */ + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); case 0: /* case 0: nothing left to add */ break; } @@ -1387,7 +1387,7 @@ APInt APInt::sqrt() const { else return x_old + 1; } else - assert(0 && "Error in APInt::sqrt computation"); + llvm_unreachable("Error in APInt::sqrt computation"); return x_old + 1; } @@ -1435,6 +1435,98 @@ APInt APInt::multiplicativeInverse(const APInt& modulo) const { return t[i].isNegative() ? t[i] + modulo : t[i]; } +/// Calculate the magic numbers required to implement a signed integer division +/// by a constant as a sequence of multiplies, adds and shifts. Requires that +/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. +/// Warren, Jr., chapter 10. +APInt::ms APInt::magic() const { + const APInt& d = *this; + unsigned p; + APInt ad, anc, delta, q1, r1, q2, r2, t; + APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()); + APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); + APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); + struct ms mag; + + ad = d.abs(); + t = signedMin + (d.lshr(d.getBitWidth() - 1)); + anc = t - 1 - t.urem(ad); // absolute value of nc + p = d.getBitWidth() - 1; // initialize p + q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) + r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) + q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) + r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) + do { + p = p + 1; + q1 = q1<<1; // update q1 = 2p/abs(nc) + r1 = r1<<1; // update r1 = rem(2p/abs(nc)) + if (r1.uge(anc)) { // must be unsigned comparison + q1 = q1 + 1; + r1 = r1 - anc; + } + q2 = q2<<1; // update q2 = 2p/abs(d) + r2 = r2<<1; // update r2 = rem(2p/abs(d)) + if (r2.uge(ad)) { // must be unsigned comparison + q2 = q2 + 1; + r2 = r2 - ad; + } + delta = ad - r2; + } while (q1.ule(delta) || (q1 == delta && r1 == 0)); + + mag.m = q2 + 1; + if (d.isNegative()) mag.m = -mag.m; // resulting magic number + mag.s = p - d.getBitWidth(); // resulting shift + return mag; +} + +/// Calculate the magic numbers required to implement an unsigned integer +/// division by a constant as a sequence of multiplies, adds and shifts. +/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry +/// S. Warren, Jr., chapter 10. +APInt::mu APInt::magicu() const { + const APInt& d = *this; + unsigned p; + APInt nc, delta, q1, r1, q2, r2; + struct mu magu; + magu.a = 0; // initialize "add" indicator + APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()); + APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); + APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); + + nc = allOnes - (-d).urem(d); + p = d.getBitWidth() - 1; // initialize p + q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc + r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) + q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d + r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) + do { + p = p + 1; + if (r1.uge(nc - r1)) { + q1 = q1 + q1 + 1; // update q1 + r1 = r1 + r1 - nc; // update r1 + } + else { + q1 = q1+q1; // update q1 + r1 = r1+r1; // update r1 + } + if ((r2 + 1).uge(d - r2)) { + if (q2.uge(signedMax)) magu.a = 1; + q2 = q2+q2 + 1; // update q2 + r2 = r2+r2 + 1 - d; // update r2 + } + else { + if (q2.uge(signedMin)) magu.a = 1; + q2 = q2+q2; // update q2 + r2 = r2+r2 + 1; // update r2 + } + delta = d - 1 - r2; + } while (p < d.getBitWidth()*2 && + (q1.ult(delta) || (q1 == delta && r1 == 0))); + magu.m = q2 + 1; // resulting magic number + magu.s = p - d.getBitWidth(); // resulting shift + return magu; +} + /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The /// variables here have the same names as in the algorithm. Comments explain @@ -1452,12 +1544,12 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, uint64_t b = uint64_t(1) << 32; #if 0 - DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n'); - DEBUG(cerr << "KnuthDiv: original:"); - DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); - DEBUG(cerr << " by"); - DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); - DEBUG(cerr << '\n'); + DEBUG(errs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); + DEBUG(errs() << "KnuthDiv: original:"); + DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); + DEBUG(errs() << " by"); + DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]); + DEBUG(errs() << '\n'); #endif // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of // u and v by d. Note that we have taken Knuth's advice here to use a power @@ -1484,17 +1576,17 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, } u[m+n] = u_carry; #if 0 - DEBUG(cerr << "KnuthDiv: normal:"); - DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); - DEBUG(cerr << " by"); - DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); - DEBUG(cerr << '\n'); + DEBUG(errs() << "KnuthDiv: normal:"); + DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); + DEBUG(errs() << " by"); + DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]); + DEBUG(errs() << '\n'); #endif // D2. [Initialize j.] Set j to m. This is the loop counter over the places. int j = m; do { - DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n'); + DEBUG(errs() << "KnuthDiv: quotient digit #" << j << '\n'); // D3. [Calculate q'.]. // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') @@ -1504,7 +1596,7 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, // value qp is one too large, and it eliminates all cases where qp is two // too large. uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); - DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n'); + DEBUG(errs() << "KnuthDiv: dividend == " << dividend << '\n'); uint64_t qp = dividend / v[n-1]; uint64_t rp = dividend % v[n-1]; if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { @@ -1513,7 +1605,7 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) qp--; } - DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); + DEBUG(errs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation @@ -1524,9 +1616,9 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); bool borrow = subtrahend > u_tmp; - DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp - << ", subtrahend == " << subtrahend - << ", borrow = " << borrow << '\n'); + DEBUG(errs() << "KnuthDiv: u_tmp == " << u_tmp + << ", subtrahend == " << subtrahend + << ", borrow = " << borrow << '\n'); uint64_t result = u_tmp - subtrahend; unsigned k = j + i; @@ -1538,12 +1630,12 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, k++; } isNeg |= borrow; - DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << + DEBUG(errs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << u[j+i+1] << '\n'); } - DEBUG(cerr << "KnuthDiv: after subtraction:"); - DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]); - DEBUG(cerr << '\n'); + DEBUG(errs() << "KnuthDiv: after subtraction:"); + DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); + DEBUG(errs() << '\n'); // The digits (u[j+n]...u[j]) should be kept positive; if the result of // this step is actually negative, (u[j+n]...u[j]) should be left as the // true value plus b**(n+1), namely as the b's complement of @@ -1556,9 +1648,9 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, carry = carry && u[i] == 0; } } - DEBUG(cerr << "KnuthDiv: after complement:"); - DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]); - DEBUG(cerr << '\n'); + DEBUG(errs() << "KnuthDiv: after complement:"); + DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); + DEBUG(errs() << '\n'); // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was // negative, go to step D6; otherwise go on to step D7. @@ -1579,16 +1671,16 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, } u[j+n] += carry; } - DEBUG(cerr << "KnuthDiv: after correction:"); - DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]); - DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n'); + DEBUG(errs() << "KnuthDiv: after correction:"); + DEBUG(for (int i = m+n; i >=0; i--) errs() <<" " << u[i]); + DEBUG(errs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. } while (--j >= 0); - DEBUG(cerr << "KnuthDiv: quotient:"); - DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]); - DEBUG(cerr << '\n'); + DEBUG(errs() << "KnuthDiv: quotient:"); + DEBUG(for (int i = m; i >=0; i--) errs() <<" " << q[i]); + DEBUG(errs() << '\n'); // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired // remainder may be obtained by dividing u[...] by d. If r is non-null we @@ -1599,22 +1691,22 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, // shift right here. In order to mak if (shift) { unsigned carry = 0; - DEBUG(cerr << "KnuthDiv: remainder:"); + DEBUG(errs() << "KnuthDiv: remainder:"); for (int i = n-1; i >= 0; i--) { r[i] = (u[i] >> shift) | carry; carry = u[i] << (32 - shift); - DEBUG(cerr << " " << r[i]); + DEBUG(errs() << " " << r[i]); } } else { for (int i = n-1; i >= 0; i--) { r[i] = u[i]; - DEBUG(cerr << " " << r[i]); + DEBUG(errs() << " " << r[i]); } } - DEBUG(cerr << '\n'); + DEBUG(errs() << '\n'); } #if 0 - DEBUG(cerr << std::setbase(10) << '\n'); + DEBUG(errs() << '\n'); #endif } @@ -1631,7 +1723,7 @@ void APInt::divide(const APInt LHS, unsigned lhsWords, // can't use 64-bit operands here because we don't have native results of // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't // work on large-endian machines. - uint64_t mask = ~0ull >> (sizeof(unsigned)*8); + uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT); unsigned n = rhsWords * 2; unsigned m = (lhsWords * 2) - n; @@ -1661,7 +1753,7 @@ void APInt::divide(const APInt LHS, unsigned lhsWords, for (unsigned i = 0; i < lhsWords; ++i) { uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); U[i * 2] = (unsigned)(tmp & mask); - U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8)); + U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); } U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. @@ -1670,7 +1762,7 @@ void APInt::divide(const APInt LHS, unsigned lhsWords, for (unsigned i = 0; i < rhsWords; ++i) { uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); V[i * 2] = (unsigned)(tmp & mask); - V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8)); + V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); } // initialize the quotient and remainder @@ -1918,9 +2010,9 @@ void APInt::fromString(unsigned numbits, const char *str, unsigned slen, if (isNeg) str++, slen--; assert((slen <= numbits || radix != 2) && "Insufficient bit width"); - assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width"); - assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width"); - assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width"); + assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width"); + assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width"); + assert((((slen-1)*64)/22 <= numbits || radix != 10) && "Insufficient bit width"); // Allocate memory if (!isSingleWord()) @@ -1941,7 +2033,7 @@ void APInt::fromString(unsigned numbits, const char *str, unsigned slen, char cdigit = str[i]; if (radix == 16) { if (!isxdigit(cdigit)) - assert(0 && "Invalid hex digit in string"); + llvm_unreachable("Invalid hex digit in string"); if (isdigit(cdigit)) digit = cdigit - '0'; else if (cdigit >= 'a') @@ -1949,7 +2041,7 @@ void APInt::fromString(unsigned numbits, const char *str, unsigned slen, else if (cdigit >= 'A') digit = cdigit - 'A' + 10; else - assert(0 && "huh? we shouldn't get here"); + llvm_unreachable("huh? we shouldn't get here"); } else if (isdigit(cdigit)) { digit = cdigit - '0'; assert((radix == 10 || @@ -1957,14 +2049,16 @@ void APInt::fromString(unsigned numbits, const char *str, unsigned slen, (radix == 2 && (digit == 0 || digit == 1))) && "Invalid digit in string for given radix"); } else { - assert(0 && "Invalid character in digit string"); + llvm_unreachable("Invalid character in digit string"); } // Shift or multiply the value by the radix - if (shift) - *this <<= shift; - else - *this *= apradix; + if (slen > 1) { + if (shift) + *this <<= shift; + else + *this *= apradix; + } // Add in the digit we just interpreted if (apdigit.isSingleWord()) @@ -2085,6 +2179,12 @@ void APInt::print(raw_ostream &OS, bool isSigned) const { OS << S.c_str(); } +std::ostream &llvm::operator<<(std::ostream &o, const APInt &I) { + raw_os_ostream OS(o); + OS << I; + return o; +} + // This implements a variety of operations on a representation of // arbitrary precision, two's-complement, bignum integer values. @@ -2266,7 +2366,7 @@ APInt::tcMSB(const integerPart *parts, unsigned int n) the least significant bit of DST. All high bits above srcBITS in DST are zero-filled. */ void -APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src, +APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src, unsigned int srcBits, unsigned int srcLSB) { unsigned int firstSrcPart, dstParts, shift, n;