aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Support
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Support')
-rw-r--r--lib/Support/APInt.cpp2014
-rw-r--r--lib/Support/Allocator.cpp111
-rw-r--r--lib/Support/Annotation.cpp105
-rw-r--r--lib/Support/CommandLine.cpp1072
-rw-r--r--lib/Support/ConstantRange.cpp474
-rw-r--r--lib/Support/Debug.cpp77
-rw-r--r--lib/Support/Dwarf.cpp586
-rw-r--r--lib/Support/FileUtilities.cpp266
-rw-r--r--lib/Support/FoldingSet.cpp307
-rw-r--r--lib/Support/GraphWriter.cpp88
-rw-r--r--lib/Support/IsInf.cpp49
-rw-r--r--lib/Support/IsNAN.cpp33
-rw-r--r--lib/Support/Makefile14
-rw-r--r--lib/Support/ManagedStatic.cpp53
-rw-r--r--lib/Support/MemoryBuffer.cpp259
-rw-r--r--lib/Support/PluginLoader.cpp44
-rw-r--r--lib/Support/SlowOperationInformer.cpp66
-rw-r--r--lib/Support/SmallPtrSet.cpp209
-rw-r--r--lib/Support/Statistic.cpp121
-rw-r--r--lib/Support/Streams.cpp21
-rw-r--r--lib/Support/StringExtras.cpp108
-rw-r--r--lib/Support/StringMap.cpp234
-rw-r--r--lib/Support/SystemUtils.cpp58
-rw-r--r--lib/Support/Timer.cpp355
24 files changed, 6724 insertions, 0 deletions
diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp
new file mode 100644
index 0000000..267aaf8
--- /dev/null
+++ b/lib/Support/APInt.cpp
@@ -0,0 +1,2014 @@
+//===-- APInt.cpp - Implement APInt class ---------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Sheng Zhou and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a class to represent arbitrary precision integer
+// constant values and provide a variety of arithmetic operations on them.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "apint"
+#include "llvm/ADT/APInt.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
+#include <math.h>
+#include <limits>
+#include <cstring>
+#include <cstdlib>
+#ifndef NDEBUG
+#include <iomanip>
+#endif
+
+using namespace llvm;
+
+/// A utility function for allocating memory, checking for allocation failures,
+/// and ensuring the contents are zeroed.
+inline static uint64_t* getClearedMemory(uint32_t numWords) {
+ uint64_t * result = new uint64_t[numWords];
+ assert(result && "APInt memory allocation fails!");
+ memset(result, 0, numWords * sizeof(uint64_t));
+ return result;
+}
+
+/// A utility function for allocating memory and checking for allocation
+/// failure. The content is not zeroed.
+inline static uint64_t* getMemory(uint32_t numWords) {
+ uint64_t * result = new uint64_t[numWords];
+ assert(result && "APInt memory allocation fails!");
+ return result;
+}
+
+APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned)
+ : BitWidth(numBits), VAL(0) {
+ assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
+ assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
+ if (isSingleWord())
+ VAL = val;
+ else {
+ pVal = getClearedMemory(getNumWords());
+ pVal[0] = val;
+ if (isSigned && int64_t(val) < 0)
+ for (unsigned i = 1; i < getNumWords(); ++i)
+ pVal[i] = -1ULL;
+ }
+ clearUnusedBits();
+}
+
+APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[])
+ : BitWidth(numBits), VAL(0) {
+ assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
+ assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
+ assert(bigVal && "Null pointer detected!");
+ if (isSingleWord())
+ VAL = bigVal[0];
+ else {
+ // Get memory, cleared to 0
+ pVal = getClearedMemory(getNumWords());
+ // Calculate the number of words to copy
+ uint32_t words = std::min<uint32_t>(numWords, getNumWords());
+ // Copy the words from bigVal to pVal
+ memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
+ }
+ // Make sure unused high bits are cleared
+ clearUnusedBits();
+}
+
+APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
+ uint8_t radix)
+ : BitWidth(numbits), VAL(0) {
+ assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
+ assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
+ fromString(numbits, StrStart, slen, radix);
+}
+
+APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix)
+ : BitWidth(numbits), VAL(0) {
+ assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
+ assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
+ assert(!Val.empty() && "String empty?");
+ fromString(numbits, Val.c_str(), Val.size(), radix);
+}
+
+APInt::APInt(const APInt& that)
+ : BitWidth(that.BitWidth), VAL(0) {
+ assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
+ assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
+ if (isSingleWord())
+ VAL = that.VAL;
+ else {
+ pVal = getMemory(getNumWords());
+ memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
+ }
+}
+
+APInt::~APInt() {
+ if (!isSingleWord() && pVal)
+ delete [] pVal;
+}
+
+APInt& APInt::operator=(const APInt& RHS) {
+ // Don't do anything for X = X
+ if (this == &RHS)
+ return *this;
+
+ // If the bitwidths are the same, we can avoid mucking with memory
+ if (BitWidth == RHS.getBitWidth()) {
+ if (isSingleWord())
+ VAL = RHS.VAL;
+ else
+ memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
+ return *this;
+ }
+
+ if (isSingleWord())
+ if (RHS.isSingleWord())
+ VAL = RHS.VAL;
+ else {
+ VAL = 0;
+ pVal = getMemory(RHS.getNumWords());
+ memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
+ }
+ else if (getNumWords() == RHS.getNumWords())
+ memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
+ else if (RHS.isSingleWord()) {
+ delete [] pVal;
+ VAL = RHS.VAL;
+ } else {
+ delete [] pVal;
+ pVal = getMemory(RHS.getNumWords());
+ memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
+ }
+ BitWidth = RHS.BitWidth;
+ return clearUnusedBits();
+}
+
+APInt& APInt::operator=(uint64_t RHS) {
+ if (isSingleWord())
+ VAL = RHS;
+ else {
+ pVal[0] = RHS;
+ memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
+ }
+ return clearUnusedBits();
+}
+
+/// add_1 - This function adds a single "digit" integer, y, to the multiple
+/// "digit" integer array, x[]. x[] is modified to reflect the addition and
+/// 1 is returned if there is a carry out, otherwise 0 is returned.
+/// @returns the carry of the addition.
+static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
+ for (uint32_t i = 0; i < len; ++i) {
+ dest[i] = y + x[i];
+ if (dest[i] < y)
+ y = 1; // Carry one to next digit.
+ else {
+ y = 0; // No need to carry so exit early
+ break;
+ }
+ }
+ return y;
+}
+
+/// @brief Prefix increment operator. Increments the APInt by one.
+APInt& APInt::operator++() {
+ if (isSingleWord())
+ ++VAL;
+ else
+ add_1(pVal, pVal, getNumWords(), 1);
+ return clearUnusedBits();
+}
+
+/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
+/// the multi-digit integer array, x[], propagating the borrowed 1 value until
+/// no further borrowing is neeeded or it runs out of "digits" in x. The result
+/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
+/// In other words, if y > x then this function returns 1, otherwise 0.
+/// @returns the borrow out of the subtraction
+static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
+ for (uint32_t i = 0; i < len; ++i) {
+ uint64_t X = x[i];
+ x[i] -= y;
+ if (y > X)
+ y = 1; // We have to "borrow 1" from next "digit"
+ else {
+ y = 0; // No need to borrow
+ break; // Remaining digits are unchanged so exit early
+ }
+ }
+ return bool(y);
+}
+
+/// @brief Prefix decrement operator. Decrements the APInt by one.
+APInt& APInt::operator--() {
+ if (isSingleWord())
+ --VAL;
+ else
+ sub_1(pVal, getNumWords(), 1);
+ return clearUnusedBits();
+}
+
+/// add - This function adds the integer array x to the integer array Y and
+/// places the result in dest.
+/// @returns the carry out from the addition
+/// @brief General addition of 64-bit integer arrays
+static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
+ uint32_t len) {
+ bool carry = false;
+ for (uint32_t i = 0; i< len; ++i) {
+ uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
+ dest[i] = x[i] + y[i] + carry;
+ carry = dest[i] < limit || (carry && dest[i] == limit);
+ }
+ return carry;
+}
+
+/// Adds the RHS APint to this APInt.
+/// @returns this, after addition of RHS.
+/// @brief Addition assignment operator.
+APInt& APInt::operator+=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ VAL += RHS.VAL;
+ else {
+ add(pVal, pVal, RHS.pVal, getNumWords());
+ }
+ return clearUnusedBits();
+}
+
+/// Subtracts the integer array y from the integer array x
+/// @returns returns the borrow out.
+/// @brief Generalized subtraction of 64-bit integer arrays.
+static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
+ uint32_t len) {
+ bool borrow = false;
+ for (uint32_t i = 0; i < len; ++i) {
+ uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
+ borrow = y[i] > x_tmp || (borrow && x[i] == 0);
+ dest[i] = x_tmp - y[i];
+ }
+ return borrow;
+}
+
+/// Subtracts the RHS APInt from this APInt
+/// @returns this, after subtraction
+/// @brief Subtraction assignment operator.
+APInt& APInt::operator-=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ VAL -= RHS.VAL;
+ else
+ sub(pVal, pVal, RHS.pVal, getNumWords());
+ return clearUnusedBits();
+}
+
+/// Multiplies an integer array, x by a a uint64_t integer and places the result
+/// into dest.
+/// @returns the carry out of the multiplication.
+/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
+static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
+ // Split y into high 32-bit part (hy) and low 32-bit part (ly)
+ uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
+ uint64_t carry = 0;
+
+ // For each digit of x.
+ for (uint32_t i = 0; i < len; ++i) {
+ // Split x into high and low words
+ uint64_t lx = x[i] & 0xffffffffULL;
+ uint64_t hx = x[i] >> 32;
+ // hasCarry - A flag to indicate if there is a carry to the next digit.
+ // hasCarry == 0, no carry
+ // hasCarry == 1, has carry
+ // hasCarry == 2, no carry and the calculation result == 0.
+ uint8_t hasCarry = 0;
+ dest[i] = carry + lx * ly;
+ // Determine if the add above introduces carry.
+ hasCarry = (dest[i] < carry) ? 1 : 0;
+ carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
+ // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
+ // (2^32 - 1) + 2^32 = 2^64.
+ hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
+
+ carry += (lx * hy) & 0xffffffffULL;
+ dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
+ carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
+ (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
+ }
+ return carry;
+}
+
+/// Multiplies integer array x by integer array y and stores the result into
+/// the integer array dest. Note that dest's size must be >= xlen + ylen.
+/// @brief Generalized multiplicate of integer arrays.
+static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
+ uint32_t ylen) {
+ dest[xlen] = mul_1(dest, x, xlen, y[0]);
+ for (uint32_t i = 1; i < ylen; ++i) {
+ uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
+ uint64_t carry = 0, lx = 0, hx = 0;
+ for (uint32_t j = 0; j < xlen; ++j) {
+ lx = x[j] & 0xffffffffULL;
+ hx = x[j] >> 32;
+ // hasCarry - A flag to indicate if has carry.
+ // hasCarry == 0, no carry
+ // hasCarry == 1, has carry
+ // hasCarry == 2, no carry and the calculation result == 0.
+ uint8_t hasCarry = 0;
+ uint64_t resul = carry + lx * ly;
+ hasCarry = (resul < carry) ? 1 : 0;
+ carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
+ hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
+
+ carry += (lx * hy) & 0xffffffffULL;
+ resul = (carry << 32) | (resul & 0xffffffffULL);
+ dest[i+j] += resul;
+ carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
+ (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
+ ((lx * hy) >> 32) + hx * hy;
+ }
+ dest[i+xlen] = carry;
+ }
+}
+
+APInt& APInt::operator*=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord()) {
+ VAL *= RHS.VAL;
+ clearUnusedBits();
+ return *this;
+ }
+
+ // Get some bit facts about LHS and check for zero
+ uint32_t lhsBits = getActiveBits();
+ uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
+ if (!lhsWords)
+ // 0 * X ===> 0
+ return *this;
+
+ // Get some bit facts about RHS and check for zero
+ uint32_t rhsBits = RHS.getActiveBits();
+ uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
+ if (!rhsWords) {
+ // X * 0 ===> 0
+ clear();
+ return *this;
+ }
+
+ // Allocate space for the result
+ uint32_t destWords = rhsWords + lhsWords;
+ uint64_t *dest = getMemory(destWords);
+
+ // Perform the long multiply
+ mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
+
+ // Copy result back into *this
+ clear();
+ uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
+ memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
+
+ // delete dest array and return
+ delete[] dest;
+ return *this;
+}
+
+APInt& APInt::operator&=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord()) {
+ VAL &= RHS.VAL;
+ return *this;
+ }
+ uint32_t numWords = getNumWords();
+ for (uint32_t i = 0; i < numWords; ++i)
+ pVal[i] &= RHS.pVal[i];
+ return *this;
+}
+
+APInt& APInt::operator|=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord()) {
+ VAL |= RHS.VAL;
+ return *this;
+ }
+ uint32_t numWords = getNumWords();
+ for (uint32_t i = 0; i < numWords; ++i)
+ pVal[i] |= RHS.pVal[i];
+ return *this;
+}
+
+APInt& APInt::operator^=(const APInt& RHS) {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord()) {
+ VAL ^= RHS.VAL;
+ this->clearUnusedBits();
+ return *this;
+ }
+ uint32_t numWords = getNumWords();
+ for (uint32_t i = 0; i < numWords; ++i)
+ pVal[i] ^= RHS.pVal[i];
+ return clearUnusedBits();
+}
+
+APInt APInt::operator&(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(getBitWidth(), VAL & RHS.VAL);
+
+ uint32_t numWords = getNumWords();
+ uint64_t* val = getMemory(numWords);
+ for (uint32_t i = 0; i < numWords; ++i)
+ val[i] = pVal[i] & RHS.pVal[i];
+ return APInt(val, getBitWidth());
+}
+
+APInt APInt::operator|(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(getBitWidth(), VAL | RHS.VAL);
+
+ uint32_t numWords = getNumWords();
+ uint64_t *val = getMemory(numWords);
+ for (uint32_t i = 0; i < numWords; ++i)
+ val[i] = pVal[i] | RHS.pVal[i];
+ return APInt(val, getBitWidth());
+}
+
+APInt APInt::operator^(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(BitWidth, VAL ^ RHS.VAL);
+
+ uint32_t numWords = getNumWords();
+ uint64_t *val = getMemory(numWords);
+ for (uint32_t i = 0; i < numWords; ++i)
+ val[i] = pVal[i] ^ RHS.pVal[i];
+
+ // 0^0==1 so clear the high bits in case they got set.
+ return APInt(val, getBitWidth()).clearUnusedBits();
+}
+
+bool APInt::operator !() const {
+ if (isSingleWord())
+ return !VAL;
+
+ for (uint32_t i = 0; i < getNumWords(); ++i)
+ if (pVal[i])
+ return false;
+ return true;
+}
+
+APInt APInt::operator*(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(BitWidth, VAL * RHS.VAL);
+ APInt Result(*this);
+ Result *= RHS;
+ return Result.clearUnusedBits();
+}
+
+APInt APInt::operator+(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(BitWidth, VAL + RHS.VAL);
+ APInt Result(BitWidth, 0);
+ add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
+ return Result.clearUnusedBits();
+}
+
+APInt APInt::operator-(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return APInt(BitWidth, VAL - RHS.VAL);
+ APInt Result(BitWidth, 0);
+ sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
+ return Result.clearUnusedBits();
+}
+
+bool APInt::operator[](uint32_t bitPosition) const {
+ return (maskBit(bitPosition) &
+ (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
+}
+
+bool APInt::operator==(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
+ if (isSingleWord())
+ return VAL == RHS.VAL;
+
+ // Get some facts about the number of bits used in the two operands.
+ uint32_t n1 = getActiveBits();
+ uint32_t n2 = RHS.getActiveBits();
+
+ // If the number of bits isn't the same, they aren't equal
+ if (n1 != n2)
+ return false;
+
+ // If the number of bits fits in a word, we only need to compare the low word.
+ if (n1 <= APINT_BITS_PER_WORD)
+ return pVal[0] == RHS.pVal[0];
+
+ // Otherwise, compare everything
+ for (int i = whichWord(n1 - 1); i >= 0; --i)
+ if (pVal[i] != RHS.pVal[i])
+ return false;
+ return true;
+}
+
+bool APInt::operator==(uint64_t Val) const {
+ if (isSingleWord())
+ return VAL == Val;
+
+ uint32_t n = getActiveBits();
+ if (n <= APINT_BITS_PER_WORD)
+ return pVal[0] == Val;
+ else
+ return false;
+}
+
+bool APInt::ult(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
+ if (isSingleWord())
+ return VAL < RHS.VAL;
+
+ // Get active bit length of both operands
+ uint32_t n1 = getActiveBits();
+ uint32_t n2 = RHS.getActiveBits();
+
+ // If magnitude of LHS is less than RHS, return true.
+ if (n1 < n2)
+ return true;
+
+ // If magnitude of RHS is greather than LHS, return false.
+ if (n2 < n1)
+ return false;
+
+ // If they bot fit in a word, just compare the low order word
+ if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
+ return pVal[0] < RHS.pVal[0];
+
+ // Otherwise, compare all words
+ uint32_t topWord = whichWord(std::max(n1,n2)-1);
+ for (int i = topWord; i >= 0; --i) {
+ if (pVal[i] > RHS.pVal[i])
+ return false;
+ if (pVal[i] < RHS.pVal[i])
+ return true;
+ }
+ return false;
+}
+
+bool APInt::slt(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
+ if (isSingleWord()) {
+ int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
+ int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
+ return lhsSext < rhsSext;
+ }
+
+ APInt lhs(*this);
+ APInt rhs(RHS);
+ bool lhsNeg = isNegative();
+ bool rhsNeg = rhs.isNegative();
+ if (lhsNeg) {
+ // Sign bit is set so perform two's complement to make it positive
+ lhs.flip();
+ lhs++;
+ }
+ if (rhsNeg) {
+ // Sign bit is set so perform two's complement to make it positive
+ rhs.flip();
+ rhs++;
+ }
+
+ // Now we have unsigned values to compare so do the comparison if necessary
+ // based on the negativeness of the values.
+ if (lhsNeg)
+ if (rhsNeg)
+ return lhs.ugt(rhs);
+ else
+ return true;
+ else if (rhsNeg)
+ return false;
+ else
+ return lhs.ult(rhs);
+}
+
+APInt& APInt::set(uint32_t bitPosition) {
+ if (isSingleWord())
+ VAL |= maskBit(bitPosition);
+ else
+ pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
+ return *this;
+}
+
+APInt& APInt::set() {
+ if (isSingleWord()) {
+ VAL = -1ULL;
+ return clearUnusedBits();
+ }
+
+ // Set all the bits in all the words.
+ for (uint32_t i = 0; i < getNumWords(); ++i)
+ pVal[i] = -1ULL;
+ // Clear the unused ones
+ return clearUnusedBits();
+}
+
+/// Set the given bit to 0 whose position is given as "bitPosition".
+/// @brief Set a given bit to 0.
+APInt& APInt::clear(uint32_t bitPosition) {
+ if (isSingleWord())
+ VAL &= ~maskBit(bitPosition);
+ else
+ pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
+ return *this;
+}
+
+/// @brief Set every bit to 0.
+APInt& APInt::clear() {
+ if (isSingleWord())
+ VAL = 0;
+ else
+ memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
+ return *this;
+}
+
+/// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
+/// this APInt.
+APInt APInt::operator~() const {
+ APInt Result(*this);
+ Result.flip();
+ return Result;
+}
+
+/// @brief Toggle every bit to its opposite value.
+APInt& APInt::flip() {
+ if (isSingleWord()) {
+ VAL ^= -1ULL;
+ return clearUnusedBits();
+ }
+ for (uint32_t i = 0; i < getNumWords(); ++i)
+ pVal[i] ^= -1ULL;
+ return clearUnusedBits();
+}
+
+/// Toggle a given bit to its opposite value whose position is given
+/// as "bitPosition".
+/// @brief Toggles a given bit to its opposite value.
+APInt& APInt::flip(uint32_t bitPosition) {
+ assert(bitPosition < BitWidth && "Out of the bit-width range!");
+ if ((*this)[bitPosition]) clear(bitPosition);
+ else set(bitPosition);
+ return *this;
+}
+
+uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
+ assert(str != 0 && "Invalid value string");
+ assert(slen > 0 && "Invalid string length");
+
+ // Each computation below needs to know if its negative
+ uint32_t isNegative = str[0] == '-';
+ if (isNegative) {
+ slen--;
+ str++;
+ }
+ // For radixes of power-of-two values, the bits required is accurately and
+ // easily computed
+ if (radix == 2)
+ return slen + isNegative;
+ if (radix == 8)
+ return slen * 3 + isNegative;
+ if (radix == 16)
+ return slen * 4 + isNegative;
+
+ // Otherwise it must be radix == 10, the hard case
+ assert(radix == 10 && "Invalid radix");
+
+ // This is grossly inefficient but accurate. We could probably do something
+ // with a computation of roughly slen*64/20 and then adjust by the value of
+ // the first few digits. But, I'm not sure how accurate that could be.
+
+ // Compute a sufficient number of bits that is always large enough but might
+ // be too large. This avoids the assertion in the constructor.
+ uint32_t sufficient = slen*64/18;
+
+ // Convert to the actual binary value.
+ APInt tmp(sufficient, str, slen, radix);
+
+ // Compute how many bits are required.
+ return isNegative + tmp.logBase2() + 1;
+}
+
+uint64_t APInt::getHashValue() const {
+ // Put the bit width into the low order bits.
+ uint64_t hash = BitWidth;
+
+ // Add the sum of the words to the hash.
+ if (isSingleWord())
+ hash += VAL << 6; // clear separation of up to 64 bits
+ else
+ for (uint32_t i = 0; i < getNumWords(); ++i)
+ hash += pVal[i] << 6; // clear sepration of up to 64 bits
+ return hash;
+}
+
+/// HiBits - This function returns the high "numBits" bits of this APInt.
+APInt APInt::getHiBits(uint32_t numBits) const {
+ return APIntOps::lshr(*this, BitWidth - numBits);
+}
+
+/// LoBits - This function returns the low "numBits" bits of this APInt.
+APInt APInt::getLoBits(uint32_t numBits) const {
+ return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
+ BitWidth - numBits);
+}
+
+bool APInt::isPowerOf2() const {
+ return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
+}
+
+uint32_t APInt::countLeadingZeros() const {
+ uint32_t Count = 0;
+ if (isSingleWord())
+ Count = CountLeadingZeros_64(VAL);
+ else {
+ for (uint32_t i = getNumWords(); i > 0u; --i) {
+ if (pVal[i-1] == 0)
+ Count += APINT_BITS_PER_WORD;
+ else {
+ Count += CountLeadingZeros_64(pVal[i-1]);
+ break;
+ }
+ }
+ }
+ uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
+ if (remainder)
+ Count -= APINT_BITS_PER_WORD - remainder;
+ return Count;
+}
+
+static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
+ uint32_t Count = 0;
+ if (skip)
+ V <<= skip;
+ while (V && (V & (1ULL << 63))) {
+ Count++;
+ V <<= 1;
+ }
+ return Count;
+}
+
+uint32_t APInt::countLeadingOnes() const {
+ if (isSingleWord())
+ return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
+
+ uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
+ uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
+ int i = getNumWords() - 1;
+ uint32_t Count = countLeadingOnes_64(pVal[i], shift);
+ if (Count == highWordBits) {
+ for (i--; i >= 0; --i) {
+ if (pVal[i] == -1ULL)
+ Count += APINT_BITS_PER_WORD;
+ else {
+ Count += countLeadingOnes_64(pVal[i], 0);
+ break;
+ }
+ }
+ }
+ return Count;
+}
+
+uint32_t APInt::countTrailingZeros() const {
+ if (isSingleWord())
+ return CountTrailingZeros_64(VAL);
+ uint32_t Count = 0;
+ uint32_t i = 0;
+ for (; i < getNumWords() && pVal[i] == 0; ++i)
+ Count += APINT_BITS_PER_WORD;
+ if (i < getNumWords())
+ Count += CountTrailingZeros_64(pVal[i]);
+ return Count;
+}
+
+uint32_t APInt::countPopulation() const {
+ if (isSingleWord())
+ return CountPopulation_64(VAL);
+ uint32_t Count = 0;
+ for (uint32_t i = 0; i < getNumWords(); ++i)
+ Count += CountPopulation_64(pVal[i]);
+ return Count;
+}
+
+APInt APInt::byteSwap() const {
+ assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
+ if (BitWidth == 16)
+ return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
+ else if (BitWidth == 32)
+ return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
+ else if (BitWidth == 48) {
+ uint32_t Tmp1 = uint32_t(VAL >> 16);
+ Tmp1 = ByteSwap_32(Tmp1);
+ uint16_t Tmp2 = uint16_t(VAL);
+ Tmp2 = ByteSwap_16(Tmp2);
+ return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
+ } else if (BitWidth == 64)
+ return APInt(BitWidth, ByteSwap_64(VAL));
+ else {
+ APInt Result(BitWidth, 0);
+ char *pByte = (char*)Result.pVal;
+ for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
+ char Tmp = pByte[i];
+ pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
+ pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
+ }
+ return Result;
+ }
+}
+
+APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
+ const APInt& API2) {
+ APInt A = API1, B = API2;
+ while (!!B) {
+ APInt T = B;
+ B = APIntOps::urem(A, B);
+ A = T;
+ }
+ return A;
+}
+
+APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
+ union {
+ double D;
+ uint64_t I;
+ } T;
+ T.D = Double;
+
+ // Get the sign bit from the highest order bit
+ bool isNeg = T.I >> 63;
+
+ // Get the 11-bit exponent and adjust for the 1023 bit bias
+ int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
+
+ // If the exponent is negative, the value is < 0 so just return 0.
+ if (exp < 0)
+ return APInt(width, 0u);
+
+ // Extract the mantissa by clearing the top 12 bits (sign + exponent).
+ uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
+
+ // If the exponent doesn't shift all bits out of the mantissa
+ if (exp < 52)
+ return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
+ APInt(width, mantissa >> (52 - exp));
+
+ // If the client didn't provide enough bits for us to shift the mantissa into
+ // then the result is undefined, just return 0
+ if (width <= exp - 52)
+ return APInt(width, 0);
+
+ // Otherwise, we have to shift the mantissa bits up to the right location
+ APInt Tmp(width, mantissa);
+ Tmp = Tmp.shl(exp - 52);
+ return isNeg ? -Tmp : Tmp;
+}
+
+/// RoundToDouble - This function convert this APInt to a double.
+/// The layout for double is as following (IEEE Standard 754):
+/// --------------------------------------
+/// | Sign Exponent Fraction Bias |
+/// |-------------------------------------- |
+/// | 1[63] 11[62-52] 52[51-00] 1023 |
+/// --------------------------------------
+double APInt::roundToDouble(bool isSigned) const {
+
+ // Handle the simple case where the value is contained in one uint64_t.
+ if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
+ if (isSigned) {
+ int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
+ return double(sext);
+ } else
+ return double(VAL);
+ }
+
+ // Determine if the value is negative.
+ bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
+
+ // Construct the absolute value if we're negative.
+ APInt Tmp(isNeg ? -(*this) : (*this));
+
+ // Figure out how many bits we're using.
+ uint32_t n = Tmp.getActiveBits();
+
+ // The exponent (without bias normalization) is just the number of bits
+ // we are using. Note that the sign bit is gone since we constructed the
+ // absolute value.
+ uint64_t exp = n;
+
+ // Return infinity for exponent overflow
+ if (exp > 1023) {
+ if (!isSigned || !isNeg)
+ return std::numeric_limits<double>::infinity();
+ else
+ return -std::numeric_limits<double>::infinity();
+ }
+ exp += 1023; // Increment for 1023 bias
+
+ // Number of bits in mantissa is 52. To obtain the mantissa value, we must
+ // extract the high 52 bits from the correct words in pVal.
+ uint64_t mantissa;
+ unsigned hiWord = whichWord(n-1);
+ if (hiWord == 0) {
+ mantissa = Tmp.pVal[0];
+ if (n > 52)
+ mantissa >>= n - 52; // shift down, we want the top 52 bits.
+ } else {
+ assert(hiWord > 0 && "huh?");
+ uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
+ uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
+ mantissa = hibits | lobits;
+ }
+
+ // The leading bit of mantissa is implicit, so get rid of it.
+ uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
+ union {
+ double D;
+ uint64_t I;
+ } T;
+ T.I = sign | (exp << 52) | mantissa;
+ return T.D;
+}
+
+// Truncate to new width.
+APInt &APInt::trunc(uint32_t width) {
+ assert(width < BitWidth && "Invalid APInt Truncate request");
+ assert(width >= IntegerType::MIN_INT_BITS && "Can't truncate to 0 bits");
+ uint32_t wordsBefore = getNumWords();
+ BitWidth = width;
+ uint32_t wordsAfter = getNumWords();
+ if (wordsBefore != wordsAfter) {
+ if (wordsAfter == 1) {
+ uint64_t *tmp = pVal;
+ VAL = pVal[0];
+ delete [] tmp;
+ } else {
+ uint64_t *newVal = getClearedMemory(wordsAfter);
+ for (uint32_t i = 0; i < wordsAfter; ++i)
+ newVal[i] = pVal[i];
+ delete [] pVal;
+ pVal = newVal;
+ }
+ }
+ return clearUnusedBits();
+}
+
+// Sign extend to a new width.
+APInt &APInt::sext(uint32_t width) {
+ assert(width > BitWidth && "Invalid APInt SignExtend request");
+ assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
+ // If the sign bit isn't set, this is the same as zext.
+ if (!isNegative()) {
+ zext(width);
+ return *this;
+ }
+
+ // The sign bit is set. First, get some facts
+ uint32_t wordsBefore = getNumWords();
+ uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
+ BitWidth = width;
+ uint32_t wordsAfter = getNumWords();
+
+ // Mask the high order word appropriately
+ if (wordsBefore == wordsAfter) {
+ uint32_t newWordBits = width % APINT_BITS_PER_WORD;
+ // The extension is contained to the wordsBefore-1th word.
+ uint64_t mask = ~0ULL;
+ if (newWordBits)
+ mask >>= APINT_BITS_PER_WORD - newWordBits;
+ mask <<= wordBits;
+ if (wordsBefore == 1)
+ VAL |= mask;
+ else
+ pVal[wordsBefore-1] |= mask;
+ return clearUnusedBits();
+ }
+
+ uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
+ uint64_t *newVal = getMemory(wordsAfter);
+ if (wordsBefore == 1)
+ newVal[0] = VAL | mask;
+ else {
+ for (uint32_t i = 0; i < wordsBefore; ++i)
+ newVal[i] = pVal[i];
+ newVal[wordsBefore-1] |= mask;
+ }
+ for (uint32_t i = wordsBefore; i < wordsAfter; i++)
+ newVal[i] = -1ULL;
+ if (wordsBefore != 1)
+ delete [] pVal;
+ pVal = newVal;
+ return clearUnusedBits();
+}
+
+// Zero extend to a new width.
+APInt &APInt::zext(uint32_t width) {
+ assert(width > BitWidth && "Invalid APInt ZeroExtend request");
+ assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
+ uint32_t wordsBefore = getNumWords();
+ BitWidth = width;
+ uint32_t wordsAfter = getNumWords();
+ if (wordsBefore != wordsAfter) {
+ uint64_t *newVal = getClearedMemory(wordsAfter);
+ if (wordsBefore == 1)
+ newVal[0] = VAL;
+ else
+ for (uint32_t i = 0; i < wordsBefore; ++i)
+ newVal[i] = pVal[i];
+ if (wordsBefore != 1)
+ delete [] pVal;
+ pVal = newVal;
+ }
+ return *this;
+}
+
+APInt &APInt::zextOrTrunc(uint32_t width) {
+ if (BitWidth < width)
+ return zext(width);
+ if (BitWidth > width)
+ return trunc(width);
+ return *this;
+}
+
+APInt &APInt::sextOrTrunc(uint32_t width) {
+ if (BitWidth < width)
+ return sext(width);
+ if (BitWidth > width)
+ return trunc(width);
+ return *this;
+}
+
+/// Arithmetic right-shift this APInt by shiftAmt.
+/// @brief Arithmetic right-shift function.
+APInt APInt::ashr(uint32_t shiftAmt) const {
+ assert(shiftAmt <= BitWidth && "Invalid shift amount");
+ // Handle a degenerate case
+ if (shiftAmt == 0)
+ return *this;
+
+ // Handle single word shifts with built-in ashr
+ if (isSingleWord()) {
+ if (shiftAmt == BitWidth)
+ return APInt(BitWidth, 0); // undefined
+ else {
+ uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
+ return APInt(BitWidth,
+ (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
+ }
+ }
+
+ // If all the bits were shifted out, the result is, technically, undefined.
+ // We return -1 if it was negative, 0 otherwise. We check this early to avoid
+ // issues in the algorithm below.
+ if (shiftAmt == BitWidth) {
+ if (isNegative())
+ return APInt(BitWidth, -1ULL);
+ else
+ return APInt(BitWidth, 0);
+ }
+
+ // Create some space for the result.
+ uint64_t * val = new uint64_t[getNumWords()];
+
+ // Compute some values needed by the following shift algorithms
+ uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
+ uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
+ uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
+ uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
+ if (bitsInWord == 0)
+ bitsInWord = APINT_BITS_PER_WORD;
+
+ // If we are shifting whole words, just move whole words
+ if (wordShift == 0) {
+ // Move the words containing significant bits
+ for (uint32_t i = 0; i <= breakWord; ++i)
+ val[i] = pVal[i+offset]; // move whole word
+
+ // Adjust the top significant word for sign bit fill, if negative
+ if (isNegative())
+ if (bitsInWord < APINT_BITS_PER_WORD)
+ val[breakWord] |= ~0ULL << bitsInWord; // set high bits
+ } else {
+ // Shift the low order words
+ for (uint32_t i = 0; i < breakWord; ++i) {
+ // This combines the shifted corresponding word with the low bits from
+ // the next word (shifted into this word's high bits).
+ val[i] = (pVal[i+offset] >> wordShift) |
+ (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
+ }
+
+ // Shift the break word. In this case there are no bits from the next word
+ // to include in this word.
+ val[breakWord] = pVal[breakWord+offset] >> wordShift;
+
+ // Deal with sign extenstion in the break word, and possibly the word before
+ // it.
+ if (isNegative()) {
+ if (wordShift > bitsInWord) {
+ if (breakWord > 0)
+ val[breakWord-1] |=
+ ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
+ val[breakWord] |= ~0ULL;
+ } else
+ val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
+ }
+ }
+
+ // Remaining words are 0 or -1, just assign them.
+ uint64_t fillValue = (isNegative() ? -1ULL : 0);
+ for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
+ val[i] = fillValue;
+ return APInt(val, BitWidth).clearUnusedBits();
+}
+
+/// Logical right-shift this APInt by shiftAmt.
+/// @brief Logical right-shift function.
+APInt APInt::lshr(uint32_t shiftAmt) const {
+ if (isSingleWord()) {
+ if (shiftAmt == BitWidth)
+ return APInt(BitWidth, 0);
+ else
+ return APInt(BitWidth, this->VAL >> shiftAmt);
+ }
+
+ // If all the bits were shifted out, the result is 0. This avoids issues
+ // with shifting by the size of the integer type, which produces undefined
+ // results. We define these "undefined results" to always be 0.
+ if (shiftAmt == BitWidth)
+ return APInt(BitWidth, 0);
+
+ // If none of the bits are shifted out, the result is *this. This avoids
+ // issues with shifting byt he size of the integer type, which produces
+ // undefined results in the code below. This is also an optimization.
+ if (shiftAmt == 0)
+ return *this;
+
+ // Create some space for the result.
+ uint64_t * val = new uint64_t[getNumWords()];
+
+ // If we are shifting less than a word, compute the shift with a simple carry
+ if (shiftAmt < APINT_BITS_PER_WORD) {
+ uint64_t carry = 0;
+ for (int i = getNumWords()-1; i >= 0; --i) {
+ val[i] = (pVal[i] >> shiftAmt) | carry;
+ carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
+ }
+ return APInt(val, BitWidth).clearUnusedBits();
+ }
+
+ // Compute some values needed by the remaining shift algorithms
+ uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
+ uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
+
+ // If we are shifting whole words, just move whole words
+ if (wordShift == 0) {
+ for (uint32_t i = 0; i < getNumWords() - offset; ++i)
+ val[i] = pVal[i+offset];
+ for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
+ val[i] = 0;
+ return APInt(val,BitWidth).clearUnusedBits();
+ }
+
+ // Shift the low order words
+ uint32_t breakWord = getNumWords() - offset -1;
+ for (uint32_t i = 0; i < breakWord; ++i)
+ val[i] = (pVal[i+offset] >> wordShift) |
+ (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
+ // Shift the break word.
+ val[breakWord] = pVal[breakWord+offset] >> wordShift;
+
+ // Remaining words are 0
+ for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
+ val[i] = 0;
+ return APInt(val, BitWidth).clearUnusedBits();
+}
+
+/// Left-shift this APInt by shiftAmt.
+/// @brief Left-shift function.
+APInt APInt::shl(uint32_t shiftAmt) const {
+ assert(shiftAmt <= BitWidth && "Invalid shift amount");
+ if (isSingleWord()) {
+ if (shiftAmt == BitWidth)
+ return APInt(BitWidth, 0); // avoid undefined shift results
+ return APInt(BitWidth, VAL << shiftAmt);
+ }
+
+ // If all the bits were shifted out, the result is 0. This avoids issues
+ // with shifting by the size of the integer type, which produces undefined
+ // results. We define these "undefined results" to always be 0.
+ if (shiftAmt == BitWidth)
+ return APInt(BitWidth, 0);
+
+ // If none of the bits are shifted out, the result is *this. This avoids a
+ // lshr by the words size in the loop below which can produce incorrect
+ // results. It also avoids the expensive computation below for a common case.
+ if (shiftAmt == 0)
+ return *this;
+
+ // Create some space for the result.
+ uint64_t * val = new uint64_t[getNumWords()];
+
+ // If we are shifting less than a word, do it the easy way
+ if (shiftAmt < APINT_BITS_PER_WORD) {
+ uint64_t carry = 0;
+ for (uint32_t i = 0; i < getNumWords(); i++) {
+ val[i] = pVal[i] << shiftAmt | carry;
+ carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
+ }
+ return APInt(val, BitWidth).clearUnusedBits();
+ }
+
+ // Compute some values needed by the remaining shift algorithms
+ uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
+ uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
+
+ // If we are shifting whole words, just move whole words
+ if (wordShift == 0) {
+ for (uint32_t i = 0; i < offset; i++)
+ val[i] = 0;
+ for (uint32_t i = offset; i < getNumWords(); i++)
+ val[i] = pVal[i-offset];
+ return APInt(val,BitWidth).clearUnusedBits();
+ }
+
+ // Copy whole words from this to Result.
+ uint32_t i = getNumWords() - 1;
+ for (; i > offset; --i)
+ val[i] = pVal[i-offset] << wordShift |
+ pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
+ val[offset] = pVal[0] << wordShift;
+ for (i = 0; i < offset; ++i)
+ val[i] = 0;
+ return APInt(val, BitWidth).clearUnusedBits();
+}
+
+APInt APInt::rotl(uint32_t rotateAmt) const {
+ if (rotateAmt == 0)
+ return *this;
+ // Don't get too fancy, just use existing shift/or facilities
+ APInt hi(*this);
+ APInt lo(*this);
+ hi.shl(rotateAmt);
+ lo.lshr(BitWidth - rotateAmt);
+ return hi | lo;
+}
+
+APInt APInt::rotr(uint32_t rotateAmt) const {
+ if (rotateAmt == 0)
+ return *this;
+ // Don't get too fancy, just use existing shift/or facilities
+ APInt hi(*this);
+ APInt lo(*this);
+ lo.lshr(rotateAmt);
+ hi.shl(BitWidth - rotateAmt);
+ return hi | lo;
+}
+
+// Square Root - this method computes and returns the square root of "this".
+// Three mechanisms are used for computation. For small values (<= 5 bits),
+// a table lookup is done. This gets some performance for common cases. For
+// values using less than 52 bits, the value is converted to double and then
+// the libc sqrt function is called. The result is rounded and then converted
+// back to a uint64_t which is then used to construct the result. Finally,
+// the Babylonian method for computing square roots is used.
+APInt APInt::sqrt() const {
+
+ // Determine the magnitude of the value.
+ uint32_t magnitude = getActiveBits();
+
+ // Use a fast table for some small values. This also gets rid of some
+ // rounding errors in libc sqrt for small values.
+ if (magnitude <= 5) {
+ static const uint8_t results[32] = {
+ /* 0 */ 0,
+ /* 1- 2 */ 1, 1,
+ /* 3- 6 */ 2, 2, 2, 2,
+ /* 7-12 */ 3, 3, 3, 3, 3, 3,
+ /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
+ /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ /* 31 */ 6
+ };
+ return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
+ }
+
+ // If the magnitude of the value fits in less than 52 bits (the precision of
+ // an IEEE double precision floating point value), then we can use the
+ // libc sqrt function which will probably use a hardware sqrt computation.
+ // This should be faster than the algorithm below.
+ if (magnitude < 52) {
+#ifdef _MSC_VER
+ // Amazingly, VC++ doesn't have round().
+ return APInt(BitWidth,
+ uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
+#else
+ return APInt(BitWidth,
+ uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
+#endif
+ }
+
+ // Okay, all the short cuts are exhausted. We must compute it. The following
+ // is a classical Babylonian method for computing the square root. This code
+ // was adapted to APINt from a wikipedia article on such computations.
+ // See http://www.wikipedia.org/ and go to the page named
+ // Calculate_an_integer_square_root.
+ uint32_t nbits = BitWidth, i = 4;
+ APInt testy(BitWidth, 16);
+ APInt x_old(BitWidth, 1);
+ APInt x_new(BitWidth, 0);
+ APInt two(BitWidth, 2);
+
+ // Select a good starting value using binary logarithms.
+ for (;; i += 2, testy = testy.shl(2))
+ if (i >= nbits || this->ule(testy)) {
+ x_old = x_old.shl(i / 2);
+ break;
+ }
+
+ // Use the Babylonian method to arrive at the integer square root:
+ for (;;) {
+ x_new = (this->udiv(x_old) + x_old).udiv(two);
+ if (x_old.ule(x_new))
+ break;
+ x_old = x_new;
+ }
+
+ // Make sure we return the closest approximation
+ // NOTE: The rounding calculation below is correct. It will produce an
+ // off-by-one discrepancy with results from pari/gp. That discrepancy has been
+ // determined to be a rounding issue with pari/gp as it begins to use a
+ // floating point representation after 192 bits. There are no discrepancies
+ // between this algorithm and pari/gp for bit widths < 192 bits.
+ APInt square(x_old * x_old);
+ APInt nextSquare((x_old + 1) * (x_old +1));
+ if (this->ult(square))
+ return x_old;
+ else if (this->ule(nextSquare)) {
+ APInt midpoint((nextSquare - square).udiv(two));
+ APInt offset(*this - square);
+ if (offset.ult(midpoint))
+ return x_old;
+ else
+ return x_old + 1;
+ } else
+ assert(0 && "Error in APInt::sqrt computation");
+ return x_old + 1;
+}
+
+/// 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
+/// the algorithm and any deviation from it.
+static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
+ uint32_t m, uint32_t n) {
+ assert(u && "Must provide dividend");
+ assert(v && "Must provide divisor");
+ assert(q && "Must provide quotient");
+ assert(u != v && u != q && v != q && "Must us different memory");
+ assert(n>1 && "n must be > 1");
+
+ // Knuth uses the value b as the base of the number system. In our case b
+ // is 2^31 so we just set it to -1u.
+ uint64_t b = uint64_t(1) << 32;
+
+ 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');
+ // 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
+ // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
+ // 2 allows us to shift instead of multiply and it is easy to determine the
+ // shift amount from the leading zeros. We are basically normalizing the u
+ // and v so that its high bits are shifted to the top of v's range without
+ // overflow. Note that this can require an extra word in u so that u must
+ // be of length m+n+1.
+ uint32_t shift = CountLeadingZeros_32(v[n-1]);
+ uint32_t v_carry = 0;
+ uint32_t u_carry = 0;
+ if (shift) {
+ for (uint32_t i = 0; i < m+n; ++i) {
+ uint32_t u_tmp = u[i] >> (32 - shift);
+ u[i] = (u[i] << shift) | u_carry;
+ u_carry = u_tmp;
+ }
+ for (uint32_t i = 0; i < n; ++i) {
+ uint32_t v_tmp = v[i] >> (32 - shift);
+ v[i] = (v[i] << shift) | v_carry;
+ v_carry = v_tmp;
+ }
+ }
+ u[m+n] = u_carry;
+ 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');
+
+ // 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');
+ // 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')
+ // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
+ // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
+ // on v[n-2] determines at high speed most of the cases in which the trial
+ // 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');
+ 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]) {
+ qp--;
+ rp += v[n-1];
+ if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
+ qp--;
+ }
+ DEBUG(cerr << "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
+ // consists of a simple multiplication by a one-place number, combined with
+ // a subtraction.
+ bool isNeg = false;
+ for (uint32_t i = 0; i < n; ++i) {
+ 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');
+
+ uint64_t result = u_tmp - subtrahend;
+ uint32_t k = j + i;
+ u[k++] = result & (b-1); // subtract low word
+ u[k++] = result >> 32; // subtract high word
+ while (borrow && k <= m+n) { // deal with borrow to the left
+ borrow = u[k] == 0;
+ u[k]--;
+ k++;
+ }
+ isNeg |= borrow;
+ DEBUG(cerr << "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');
+ // 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
+ // the true value, and a "borrow" to the left should be remembered.
+ //
+ if (isNeg) {
+ bool carry = true; // true because b's complement is "complement + 1"
+ for (uint32_t i = 0; i <= m+n; ++i) {
+ u[i] = ~u[i] + carry; // b's complement
+ 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');
+
+ // 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.
+ q[j] = qp;
+ if (isNeg) {
+ // D6. [Add back]. The probability that this step is necessary is very
+ // small, on the order of only 2/b. Make sure that test data accounts for
+ // this possibility. Decrease q[j] by 1
+ q[j]--;
+ // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
+ // A carry will occur to the left of u[j+n], and it should be ignored
+ // since it cancels with the borrow that occurred in D4.
+ bool carry = false;
+ for (uint32_t i = 0; i < n; i++) {
+ uint32_t limit = std::min(u[j+i],v[i]);
+ u[j+i] += v[i] + carry;
+ carry = u[j+i] < limit || (carry && u[j+i] == limit);
+ }
+ 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');
+
+ // 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');
+
+ // 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
+ // compute the remainder (urem uses this).
+ if (r) {
+ // The value d is expressed by the "shift" value above since we avoided
+ // multiplication by d by using a shift left. So, all we have to do is
+ // shift right here. In order to mak
+ if (shift) {
+ uint32_t carry = 0;
+ DEBUG(cerr << "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]);
+ }
+ } else {
+ for (int i = n-1; i >= 0; i--) {
+ r[i] = u[i];
+ DEBUG(cerr << " " << r[i]);
+ }
+ }
+ DEBUG(cerr << '\n');
+ }
+ DEBUG(cerr << std::setbase(10) << '\n');
+}
+
+void APInt::divide(const APInt LHS, uint32_t lhsWords,
+ const APInt &RHS, uint32_t rhsWords,
+ APInt *Quotient, APInt *Remainder)
+{
+ assert(lhsWords >= rhsWords && "Fractional result");
+
+ // First, compose the values into an array of 32-bit words instead of
+ // 64-bit words. This is a necessity of both the "short division" algorithm
+ // and the the Knuth "classical algorithm" which requires there to be native
+ // operations for +, -, and * on an m bit value with an m*2 bit result. We
+ // can't use 64-bit operands here because we don't have native results of
+ // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
+ // work on large-endian machines.
+ uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
+ uint32_t n = rhsWords * 2;
+ uint32_t m = (lhsWords * 2) - n;
+
+ // Allocate space for the temporary values we need either on the stack, if
+ // it will fit, or on the heap if it won't.
+ uint32_t SPACE[128];
+ uint32_t *U = 0;
+ uint32_t *V = 0;
+ uint32_t *Q = 0;
+ uint32_t *R = 0;
+ if ((Remainder?4:3)*n+2*m+1 <= 128) {
+ U = &SPACE[0];
+ V = &SPACE[m+n+1];
+ Q = &SPACE[(m+n+1) + n];
+ if (Remainder)
+ R = &SPACE[(m+n+1) + n + (m+n)];
+ } else {
+ U = new uint32_t[m + n + 1];
+ V = new uint32_t[n];
+ Q = new uint32_t[m+n];
+ if (Remainder)
+ R = new uint32_t[n];
+ }
+
+ // Initialize the dividend
+ memset(U, 0, (m+n+1)*sizeof(uint32_t));
+ for (unsigned i = 0; i < lhsWords; ++i) {
+ uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
+ U[i * 2] = tmp & mask;
+ U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
+ }
+ U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
+
+ // Initialize the divisor
+ memset(V, 0, (n)*sizeof(uint32_t));
+ for (unsigned i = 0; i < rhsWords; ++i) {
+ uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
+ V[i * 2] = tmp & mask;
+ V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
+ }
+
+ // initialize the quotient and remainder
+ memset(Q, 0, (m+n) * sizeof(uint32_t));
+ if (Remainder)
+ memset(R, 0, n * sizeof(uint32_t));
+
+ // Now, adjust m and n for the Knuth division. n is the number of words in
+ // the divisor. m is the number of words by which the dividend exceeds the
+ // divisor (i.e. m+n is the length of the dividend). These sizes must not
+ // contain any zero words or the Knuth algorithm fails.
+ for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
+ n--;
+ m++;
+ }
+ for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
+ m--;
+
+ // If we're left with only a single word for the divisor, Knuth doesn't work
+ // so we implement the short division algorithm here. This is much simpler
+ // and faster because we are certain that we can divide a 64-bit quantity
+ // by a 32-bit quantity at hardware speed and short division is simply a
+ // series of such operations. This is just like doing short division but we
+ // are using base 2^32 instead of base 10.
+ assert(n != 0 && "Divide by zero?");
+ if (n == 1) {
+ uint32_t divisor = V[0];
+ uint32_t remainder = 0;
+ for (int i = m+n-1; i >= 0; i--) {
+ uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
+ if (partial_dividend == 0) {
+ Q[i] = 0;
+ remainder = 0;
+ } else if (partial_dividend < divisor) {
+ Q[i] = 0;
+ remainder = partial_dividend;
+ } else if (partial_dividend == divisor) {
+ Q[i] = 1;
+ remainder = 0;
+ } else {
+ Q[i] = partial_dividend / divisor;
+ remainder = partial_dividend - (Q[i] * divisor);
+ }
+ }
+ if (R)
+ R[0] = remainder;
+ } else {
+ // Now we're ready to invoke the Knuth classical divide algorithm. In this
+ // case n > 1.
+ KnuthDiv(U, V, Q, R, m, n);
+ }
+
+ // If the caller wants the quotient
+ if (Quotient) {
+ // Set up the Quotient value's memory.
+ if (Quotient->BitWidth != LHS.BitWidth) {
+ if (Quotient->isSingleWord())
+ Quotient->VAL = 0;
+ else
+ delete [] Quotient->pVal;
+ Quotient->BitWidth = LHS.BitWidth;
+ if (!Quotient->isSingleWord())
+ Quotient->pVal = getClearedMemory(Quotient->getNumWords());
+ } else
+ Quotient->clear();
+
+ // The quotient is in Q. Reconstitute the quotient into Quotient's low
+ // order words.
+ if (lhsWords == 1) {
+ uint64_t tmp =
+ uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
+ if (Quotient->isSingleWord())
+ Quotient->VAL = tmp;
+ else
+ Quotient->pVal[0] = tmp;
+ } else {
+ assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
+ for (unsigned i = 0; i < lhsWords; ++i)
+ Quotient->pVal[i] =
+ uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
+ }
+ }
+
+ // If the caller wants the remainder
+ if (Remainder) {
+ // Set up the Remainder value's memory.
+ if (Remainder->BitWidth != RHS.BitWidth) {
+ if (Remainder->isSingleWord())
+ Remainder->VAL = 0;
+ else
+ delete [] Remainder->pVal;
+ Remainder->BitWidth = RHS.BitWidth;
+ if (!Remainder->isSingleWord())
+ Remainder->pVal = getClearedMemory(Remainder->getNumWords());
+ } else
+ Remainder->clear();
+
+ // The remainder is in R. Reconstitute the remainder into Remainder's low
+ // order words.
+ if (rhsWords == 1) {
+ uint64_t tmp =
+ uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
+ if (Remainder->isSingleWord())
+ Remainder->VAL = tmp;
+ else
+ Remainder->pVal[0] = tmp;
+ } else {
+ assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
+ for (unsigned i = 0; i < rhsWords; ++i)
+ Remainder->pVal[i] =
+ uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
+ }
+ }
+
+ // Clean up the memory we allocated.
+ if (U != &SPACE[0]) {
+ delete [] U;
+ delete [] V;
+ delete [] Q;
+ delete [] R;
+ }
+}
+
+APInt APInt::udiv(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+
+ // First, deal with the easy case
+ if (isSingleWord()) {
+ assert(RHS.VAL != 0 && "Divide by zero?");
+ return APInt(BitWidth, VAL / RHS.VAL);
+ }
+
+ // Get some facts about the LHS and RHS number of bits and words
+ uint32_t rhsBits = RHS.getActiveBits();
+ uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
+ assert(rhsWords && "Divided by zero???");
+ uint32_t lhsBits = this->getActiveBits();
+ uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
+
+ // Deal with some degenerate cases
+ if (!lhsWords)
+ // 0 / X ===> 0
+ return APInt(BitWidth, 0);
+ else if (lhsWords < rhsWords || this->ult(RHS)) {
+ // X / Y ===> 0, iff X < Y
+ return APInt(BitWidth, 0);
+ } else if (*this == RHS) {
+ // X / X ===> 1
+ return APInt(BitWidth, 1);
+ } else if (lhsWords == 1 && rhsWords == 1) {
+ // All high words are zero, just use native divide
+ return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
+ }
+
+ // We have to compute it the hard way. Invoke the Knuth divide algorithm.
+ APInt Quotient(1,0); // to hold result.
+ divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
+ return Quotient;
+}
+
+APInt APInt::urem(const APInt& RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord()) {
+ assert(RHS.VAL != 0 && "Remainder by zero?");
+ return APInt(BitWidth, VAL % RHS.VAL);
+ }
+
+ // Get some facts about the LHS
+ uint32_t lhsBits = getActiveBits();
+ uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
+
+ // Get some facts about the RHS
+ uint32_t rhsBits = RHS.getActiveBits();
+ uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
+ assert(rhsWords && "Performing remainder operation by zero ???");
+
+ // Check the degenerate cases
+ if (lhsWords == 0) {
+ // 0 % Y ===> 0
+ return APInt(BitWidth, 0);
+ } else if (lhsWords < rhsWords || this->ult(RHS)) {
+ // X % Y ===> X, iff X < Y
+ return *this;
+ } else if (*this == RHS) {
+ // X % X == 0;
+ return APInt(BitWidth, 0);
+ } else if (lhsWords == 1) {
+ // All high words are zero, just use native remainder
+ return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
+ }
+
+ // We have to compute it the hard way. Invoke the Knuth divide algorithm.
+ APInt Remainder(1,0);
+ divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
+ return Remainder;
+}
+
+void APInt::udivrem(const APInt &LHS, const APInt &RHS,
+ APInt &Quotient, APInt &Remainder) {
+ // Get some size facts about the dividend and divisor
+ uint32_t lhsBits = LHS.getActiveBits();
+ uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
+ uint32_t rhsBits = RHS.getActiveBits();
+ uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
+
+ // Check the degenerate cases
+ if (lhsWords == 0) {
+ Quotient = 0; // 0 / Y ===> 0
+ Remainder = 0; // 0 % Y ===> 0
+ return;
+ }
+
+ if (lhsWords < rhsWords || LHS.ult(RHS)) {
+ Quotient = 0; // X / Y ===> 0, iff X < Y
+ Remainder = LHS; // X % Y ===> X, iff X < Y
+ return;
+ }
+
+ if (LHS == RHS) {
+ Quotient = 1; // X / X ===> 1
+ Remainder = 0; // X % X ===> 0;
+ return;
+ }
+
+ if (lhsWords == 1 && rhsWords == 1) {
+ // There is only one word to consider so use the native versions.
+ if (LHS.isSingleWord()) {
+ Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
+ Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
+ } else {
+ Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
+ Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
+ }
+ return;
+ }
+
+ // Okay, lets do it the long way
+ divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
+}
+
+void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
+ uint8_t radix) {
+ // Check our assumptions here
+ assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
+ "Radix should be 2, 8, 10, or 16!");
+ assert(str && "String is null?");
+ bool isNeg = str[0] == '-';
+ 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");
+
+ // Allocate memory
+ if (!isSingleWord())
+ pVal = getClearedMemory(getNumWords());
+
+ // Figure out if we can shift instead of multiply
+ uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
+
+ // Set up an APInt for the digit to add outside the loop so we don't
+ // constantly construct/destruct it.
+ APInt apdigit(getBitWidth(), 0);
+ APInt apradix(getBitWidth(), radix);
+
+ // Enter digit traversal loop
+ for (unsigned i = 0; i < slen; i++) {
+ // Get a digit
+ uint32_t digit = 0;
+ char cdigit = str[i];
+ if (radix == 16) {
+ if (!isxdigit(cdigit))
+ assert(0 && "Invalid hex digit in string");
+ if (isdigit(cdigit))
+ digit = cdigit - '0';
+ else if (cdigit >= 'a')
+ digit = cdigit - 'a' + 10;
+ else if (cdigit >= 'A')
+ digit = cdigit - 'A' + 10;
+ else
+ assert(0 && "huh? we shouldn't get here");
+ } else if (isdigit(cdigit)) {
+ digit = cdigit - '0';
+ } else {
+ assert(0 && "Invalid character in digit string");
+ }
+
+ // Shift or multiply the value by the radix
+ if (shift)
+ *this <<= shift;
+ else
+ *this *= apradix;
+
+ // Add in the digit we just interpreted
+ if (apdigit.isSingleWord())
+ apdigit.VAL = digit;
+ else
+ apdigit.pVal[0] = digit;
+ *this += apdigit;
+ }
+ // If its negative, put it in two's complement form
+ if (isNeg) {
+ (*this)--;
+ this->flip();
+ }
+}
+
+std::string APInt::toString(uint8_t radix, bool wantSigned) const {
+ assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
+ "Radix should be 2, 8, 10, or 16!");
+ static const char *digits[] = {
+ "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
+ };
+ std::string result;
+ uint32_t bits_used = getActiveBits();
+ if (isSingleWord()) {
+ char buf[65];
+ const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
+ (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
+ if (format) {
+ if (wantSigned) {
+ int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
+ (APINT_BITS_PER_WORD-BitWidth);
+ sprintf(buf, format, sextVal);
+ } else
+ sprintf(buf, format, VAL);
+ } else {
+ memset(buf, 0, 65);
+ uint64_t v = VAL;
+ while (bits_used) {
+ uint32_t bit = v & 1;
+ bits_used--;
+ buf[bits_used] = digits[bit][0];
+ v >>=1;
+ }
+ }
+ result = buf;
+ return result;
+ }
+
+ if (radix != 10) {
+ // For the 2, 8 and 16 bit cases, we can just shift instead of divide
+ // because the number of bits per digit (1,3 and 4 respectively) divides
+ // equaly. We just shift until there value is zero.
+
+ // First, check for a zero value and just short circuit the logic below.
+ if (*this == 0)
+ result = "0";
+ else {
+ APInt tmp(*this);
+ size_t insert_at = 0;
+ if (wantSigned && this->isNegative()) {
+ // They want to print the signed version and it is a negative value
+ // Flip the bits and add one to turn it into the equivalent positive
+ // value and put a '-' in the result.
+ tmp.flip();
+ tmp++;
+ result = "-";
+ insert_at = 1;
+ }
+ // Just shift tmp right for each digit width until it becomes zero
+ uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
+ uint64_t mask = radix - 1;
+ APInt zero(tmp.getBitWidth(), 0);
+ while (tmp.ne(zero)) {
+ unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
+ result.insert(insert_at, digits[digit]);
+ tmp = tmp.lshr(shift);
+ }
+ }
+ return result;
+ }
+
+ APInt tmp(*this);
+ APInt divisor(4, radix);
+ APInt zero(tmp.getBitWidth(), 0);
+ size_t insert_at = 0;
+ if (wantSigned && tmp[BitWidth-1]) {
+ // They want to print the signed version and it is a negative value
+ // Flip the bits and add one to turn it into the equivalent positive
+ // value and put a '-' in the result.
+ tmp.flip();
+ tmp++;
+ result = "-";
+ insert_at = 1;
+ }
+ if (tmp == APInt(tmp.getBitWidth(), 0))
+ result = "0";
+ else while (tmp.ne(zero)) {
+ APInt APdigit(1,0);
+ APInt tmp2(tmp.getBitWidth(), 0);
+ divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
+ &APdigit);
+ uint32_t digit = APdigit.getZExtValue();
+ assert(digit < radix && "divide failed");
+ result.insert(insert_at,digits[digit]);
+ tmp = tmp2;
+ }
+
+ return result;
+}
+
+#ifndef NDEBUG
+void APInt::dump() const
+{
+ cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
+ if (isSingleWord())
+ cerr << VAL;
+ else for (unsigned i = getNumWords(); i > 0; i--) {
+ cerr << pVal[i-1] << " ";
+ }
+ cerr << " U(" << this->toString(10) << ") S(" << this->toStringSigned(10)
+ << ")\n" << std::setbase(10);
+}
+#endif
diff --git a/lib/Support/Allocator.cpp b/lib/Support/Allocator.cpp
new file mode 100644
index 0000000..234fd41
--- /dev/null
+++ b/lib/Support/Allocator.cpp
@@ -0,0 +1,111 @@
+//===--- Allocator.cpp - Simple memory allocation abstraction -------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the BumpPtrAllocator interface.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Streams.h"
+#include <ostream>
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// MemRegion class implementation
+//===----------------------------------------------------------------------===//
+
+namespace {
+/// MemRegion - This is one chunk of the BumpPtrAllocator.
+class MemRegion {
+ unsigned RegionSize;
+ MemRegion *Next;
+ char *NextPtr;
+public:
+ void Init(unsigned size, unsigned Alignment, MemRegion *next) {
+ RegionSize = size;
+ Next = next;
+ NextPtr = (char*)(this+1);
+
+ // Align NextPtr.
+ NextPtr = (char*)((intptr_t)(NextPtr+Alignment-1) &
+ ~(intptr_t)(Alignment-1));
+ }
+
+ const MemRegion *getNext() const { return Next; }
+ unsigned getNumBytesAllocated() const {
+ return NextPtr-(const char*)this;
+ }
+
+ /// Allocate - Allocate and return at least the specified number of bytes.
+ ///
+ void *Allocate(unsigned AllocSize, unsigned Alignment, MemRegion **RegPtr) {
+ // Round size up to an even multiple of the alignment.
+ AllocSize = (AllocSize+Alignment-1) & ~(Alignment-1);
+
+ // If there is space in this region, return it.
+ if (unsigned(NextPtr+AllocSize-(char*)this) <= RegionSize) {
+ void *Result = NextPtr;
+ NextPtr += AllocSize;
+ return Result;
+ }
+
+ // Otherwise, we have to allocate a new chunk. Create one twice as big as
+ // this one.
+ MemRegion *NewRegion = (MemRegion *)malloc(RegionSize*2);
+ NewRegion->Init(RegionSize*2, Alignment, this);
+
+ // Update the current "first region" pointer to point to the new region.
+ *RegPtr = NewRegion;
+
+ // Try allocating from it now.
+ return NewRegion->Allocate(AllocSize, Alignment, RegPtr);
+ }
+
+ /// Deallocate - Release all memory for this region to the system.
+ ///
+ void Deallocate() {
+ MemRegion *next = Next;
+ free(this);
+ if (next)
+ next->Deallocate();
+ }
+};
+}
+
+//===----------------------------------------------------------------------===//
+// BumpPtrAllocator class implementation
+//===----------------------------------------------------------------------===//
+
+BumpPtrAllocator::BumpPtrAllocator() {
+ TheMemory = malloc(4096);
+ ((MemRegion*)TheMemory)->Init(4096, 1, 0);
+}
+
+BumpPtrAllocator::~BumpPtrAllocator() {
+ ((MemRegion*)TheMemory)->Deallocate();
+}
+
+void *BumpPtrAllocator::Allocate(unsigned Size, unsigned Align) {
+ MemRegion *MRP = (MemRegion*)TheMemory;
+ void *Ptr = MRP->Allocate(Size, Align, &MRP);
+ TheMemory = MRP;
+ return Ptr;
+}
+
+void BumpPtrAllocator::PrintStats() const {
+ unsigned BytesUsed = 0;
+ unsigned NumRegions = 0;
+ const MemRegion *R = (MemRegion*)TheMemory;
+ for (; R; R = R->getNext(), ++NumRegions)
+ BytesUsed += R->getNumBytesAllocated();
+
+ cerr << "\nNumber of memory regions: " << NumRegions << "\n";
+ cerr << "Bytes allocated: " << BytesUsed << "\n";
+}
diff --git a/lib/Support/Annotation.cpp b/lib/Support/Annotation.cpp
new file mode 100644
index 0000000..cfc9c2a
--- /dev/null
+++ b/lib/Support/Annotation.cpp
@@ -0,0 +1,105 @@
+//===-- Annotation.cpp - Implement the Annotation Classes -----------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the AnnotationManager class.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Annotation.h"
+#include "llvm/Support/ManagedStatic.h"
+#include <map>
+using namespace llvm;
+
+Annotation::~Annotation() {} // Designed to be subclassed
+
+Annotable::~Annotable() { // Virtual because it's designed to be subclassed...
+ Annotation *A = AnnotationList;
+ while (A) {
+ Annotation *Next = A->getNext();
+ delete A;
+ A = Next;
+ }
+}
+
+typedef std::map<const std::string, unsigned> IDMapType;
+static unsigned IDCounter = 0; // Unique ID counter
+
+// Static member to ensure initialiation on demand.
+static ManagedStatic<IDMapType> IDMap;
+
+// On demand annotation creation support...
+typedef Annotation *(*AnnFactory)(AnnotationID, const Annotable *, void *);
+typedef std::map<unsigned, std::pair<AnnFactory,void*> > FactMapType;
+
+static FactMapType *TheFactMap = 0;
+static FactMapType &getFactMap() {
+ if (TheFactMap == 0)
+ TheFactMap = new FactMapType();
+ return *TheFactMap;
+}
+
+static void eraseFromFactMap(unsigned ID) {
+ assert(TheFactMap && "No entries found!");
+ TheFactMap->erase(ID);
+ if (TheFactMap->empty()) { // Delete when empty
+ delete TheFactMap;
+ TheFactMap = 0;
+ }
+}
+
+AnnotationID AnnotationManager::getID(const std::string &Name) { // Name -> ID
+ IDMapType::iterator I = IDMap->find(Name);
+ if (I == IDMap->end()) {
+ (*IDMap)[Name] = IDCounter++; // Add a new element
+ return IDCounter-1;
+ }
+ return I->second;
+}
+
+// getID - Name -> ID + registration of a factory function for demand driven
+// annotation support.
+AnnotationID AnnotationManager::getID(const std::string &Name, Factory Fact,
+ void *Data) {
+ AnnotationID Result(getID(Name));
+ registerAnnotationFactory(Result, Fact, Data);
+ return Result;
+}
+
+// getName - This function is especially slow, but that's okay because it should
+// only be used for debugging.
+//
+const std::string &AnnotationManager::getName(AnnotationID ID) { // ID -> Name
+ IDMapType &TheMap = *IDMap;
+ for (IDMapType::iterator I = TheMap.begin(); ; ++I) {
+ assert(I != TheMap.end() && "Annotation ID is unknown!");
+ if (I->second == ID.ID) return I->first;
+ }
+}
+
+// registerAnnotationFactory - This method is used to register a callback
+// function used to create an annotation on demand if it is needed by the
+// Annotable::findOrCreateAnnotation method.
+//
+void AnnotationManager::registerAnnotationFactory(AnnotationID ID, AnnFactory F,
+ void *ExtraData) {
+ if (F)
+ getFactMap()[ID.ID] = std::make_pair(F, ExtraData);
+ else
+ eraseFromFactMap(ID.ID);
+}
+
+// createAnnotation - Create an annotation of the specified ID for the
+// specified object, using a register annotation creation function.
+//
+Annotation *AnnotationManager::createAnnotation(AnnotationID ID,
+ const Annotable *Obj) {
+ FactMapType::iterator I = getFactMap().find(ID.ID);
+ if (I == getFactMap().end()) return 0;
+ return I->second.first(ID, Obj, I->second.second);
+}
diff --git a/lib/Support/CommandLine.cpp b/lib/Support/CommandLine.cpp
new file mode 100644
index 0000000..1f5008a
--- /dev/null
+++ b/lib/Support/CommandLine.cpp
@@ -0,0 +1,1072 @@
+//===-- CommandLine.cpp - Command line parser implementation --------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class implements a command line argument processor that is useful when
+// creating a tool. It provides a simple, minimalistic interface that is easily
+// extensible and supports nonlocal (library) command line options.
+//
+// Note that rather than trying to figure out what this code does, you could try
+// reading the library documentation located in docs/CommandLine.html
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Config/config.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/System/Path.h"
+#include <algorithm>
+#include <functional>
+#include <map>
+#include <ostream>
+#include <set>
+#include <cstdlib>
+#include <cerrno>
+#include <cstring>
+using namespace llvm;
+using namespace cl;
+
+//===----------------------------------------------------------------------===//
+// Template instantiations and anchors.
+//
+TEMPLATE_INSTANTIATION(class basic_parser<bool>);
+TEMPLATE_INSTANTIATION(class basic_parser<boolOrDefault>);
+TEMPLATE_INSTANTIATION(class basic_parser<int>);
+TEMPLATE_INSTANTIATION(class basic_parser<unsigned>);
+TEMPLATE_INSTANTIATION(class basic_parser<double>);
+TEMPLATE_INSTANTIATION(class basic_parser<float>);
+TEMPLATE_INSTANTIATION(class basic_parser<std::string>);
+
+TEMPLATE_INSTANTIATION(class opt<unsigned>);
+TEMPLATE_INSTANTIATION(class opt<int>);
+TEMPLATE_INSTANTIATION(class opt<std::string>);
+TEMPLATE_INSTANTIATION(class opt<bool>);
+
+void Option::anchor() {}
+void basic_parser_impl::anchor() {}
+void parser<bool>::anchor() {}
+void parser<boolOrDefault>::anchor() {}
+void parser<int>::anchor() {}
+void parser<unsigned>::anchor() {}
+void parser<double>::anchor() {}
+void parser<float>::anchor() {}
+void parser<std::string>::anchor() {}
+
+//===----------------------------------------------------------------------===//
+
+// Globals for name and overview of program. Program name is not a string to
+// avoid static ctor/dtor issues.
+static char ProgramName[80] = "<premain>";
+static const char *ProgramOverview = 0;
+
+// This collects additional help to be printed.
+static ManagedStatic<std::vector<const char*> > MoreHelp;
+
+extrahelp::extrahelp(const char *Help)
+ : morehelp(Help) {
+ MoreHelp->push_back(Help);
+}
+
+static bool OptionListChanged = false;
+
+// MarkOptionsChanged - Internal helper function.
+void cl::MarkOptionsChanged() {
+ OptionListChanged = true;
+}
+
+/// RegisteredOptionList - This is the list of the command line options that
+/// have statically constructed themselves.
+static Option *RegisteredOptionList = 0;
+
+void Option::addArgument() {
+ assert(NextRegistered == 0 && "argument multiply registered!");
+
+ NextRegistered = RegisteredOptionList;
+ RegisteredOptionList = this;
+ MarkOptionsChanged();
+}
+
+
+//===----------------------------------------------------------------------===//
+// Basic, shared command line option processing machinery.
+//
+
+/// GetOptionInfo - Scan the list of registered options, turning them into data
+/// structures that are easier to handle.
+static void GetOptionInfo(std::vector<Option*> &PositionalOpts,
+ std::map<std::string, Option*> &OptionsMap) {
+ std::vector<const char*> OptionNames;
+ Option *CAOpt = 0; // The ConsumeAfter option if it exists.
+ for (Option *O = RegisteredOptionList; O; O = O->getNextRegisteredOption()) {
+ // If this option wants to handle multiple option names, get the full set.
+ // This handles enum options like "-O1 -O2" etc.
+ O->getExtraOptionNames(OptionNames);
+ if (O->ArgStr[0])
+ OptionNames.push_back(O->ArgStr);
+
+ // Handle named options.
+ for (unsigned i = 0, e = OptionNames.size(); i != e; ++i) {
+ // Add argument to the argument map!
+ if (!OptionsMap.insert(std::pair<std::string,Option*>(OptionNames[i],
+ O)).second) {
+ cerr << ProgramName << ": CommandLine Error: Argument '"
+ << OptionNames[0] << "' defined more than once!\n";
+ }
+ }
+
+ OptionNames.clear();
+
+ // Remember information about positional options.
+ if (O->getFormattingFlag() == cl::Positional)
+ PositionalOpts.push_back(O);
+ else if (O->getNumOccurrencesFlag() == cl::ConsumeAfter) {
+ if (CAOpt)
+ O->error("Cannot specify more than one option with cl::ConsumeAfter!");
+ CAOpt = O;
+ }
+ }
+
+ if (CAOpt)
+ PositionalOpts.push_back(CAOpt);
+
+ // Make sure that they are in order of registration not backwards.
+ std::reverse(PositionalOpts.begin(), PositionalOpts.end());
+}
+
+
+/// LookupOption - Lookup the option specified by the specified option on the
+/// command line. If there is a value specified (after an equal sign) return
+/// that as well.
+static Option *LookupOption(const char *&Arg, const char *&Value,
+ std::map<std::string, Option*> &OptionsMap) {
+ while (*Arg == '-') ++Arg; // Eat leading dashes
+
+ const char *ArgEnd = Arg;
+ while (*ArgEnd && *ArgEnd != '=')
+ ++ArgEnd; // Scan till end of argument name.
+
+ if (*ArgEnd == '=') // If we have an equals sign...
+ Value = ArgEnd+1; // Get the value, not the equals
+
+
+ if (*Arg == 0) return 0;
+
+ // Look up the option.
+ std::map<std::string, Option*>::iterator I =
+ OptionsMap.find(std::string(Arg, ArgEnd));
+ return I != OptionsMap.end() ? I->second : 0;
+}
+
+static inline bool ProvideOption(Option *Handler, const char *ArgName,
+ const char *Value, int argc, char **argv,
+ int &i) {
+ // Enforce value requirements
+ switch (Handler->getValueExpectedFlag()) {
+ case ValueRequired:
+ if (Value == 0) { // No value specified?
+ if (i+1 < argc) { // Steal the next argument, like for '-o filename'
+ Value = argv[++i];
+ } else {
+ return Handler->error(" requires a value!");
+ }
+ }
+ break;
+ case ValueDisallowed:
+ if (Value)
+ return Handler->error(" does not allow a value! '" +
+ std::string(Value) + "' specified.");
+ break;
+ case ValueOptional:
+ break;
+ default:
+ cerr << ProgramName
+ << ": Bad ValueMask flag! CommandLine usage error:"
+ << Handler->getValueExpectedFlag() << "\n";
+ abort();
+ break;
+ }
+
+ // Run the handler now!
+ return Handler->addOccurrence(i, ArgName, Value ? Value : "");
+}
+
+static bool ProvidePositionalOption(Option *Handler, const std::string &Arg,
+ int i) {
+ int Dummy = i;
+ return ProvideOption(Handler, Handler->ArgStr, Arg.c_str(), 0, 0, Dummy);
+}
+
+
+// Option predicates...
+static inline bool isGrouping(const Option *O) {
+ return O->getFormattingFlag() == cl::Grouping;
+}
+static inline bool isPrefixedOrGrouping(const Option *O) {
+ return isGrouping(O) || O->getFormattingFlag() == cl::Prefix;
+}
+
+// getOptionPred - Check to see if there are any options that satisfy the
+// specified predicate with names that are the prefixes in Name. This is
+// checked by progressively stripping characters off of the name, checking to
+// see if there options that satisfy the predicate. If we find one, return it,
+// otherwise return null.
+//
+static Option *getOptionPred(std::string Name, unsigned &Length,
+ bool (*Pred)(const Option*),
+ std::map<std::string, Option*> &OptionsMap) {
+
+ std::map<std::string, Option*>::iterator OMI = OptionsMap.find(Name);
+ if (OMI != OptionsMap.end() && Pred(OMI->second)) {
+ Length = Name.length();
+ return OMI->second;
+ }
+
+ if (Name.size() == 1) return 0;
+ do {
+ Name.erase(Name.end()-1, Name.end()); // Chop off the last character...
+ OMI = OptionsMap.find(Name);
+
+ // Loop while we haven't found an option and Name still has at least two
+ // characters in it (so that the next iteration will not be the empty
+ // string...
+ } while ((OMI == OptionsMap.end() || !Pred(OMI->second)) && Name.size() > 1);
+
+ if (OMI != OptionsMap.end() && Pred(OMI->second)) {
+ Length = Name.length();
+ return OMI->second; // Found one!
+ }
+ return 0; // No option found!
+}
+
+static bool RequiresValue(const Option *O) {
+ return O->getNumOccurrencesFlag() == cl::Required ||
+ O->getNumOccurrencesFlag() == cl::OneOrMore;
+}
+
+static bool EatsUnboundedNumberOfValues(const Option *O) {
+ return O->getNumOccurrencesFlag() == cl::ZeroOrMore ||
+ O->getNumOccurrencesFlag() == cl::OneOrMore;
+}
+
+/// ParseCStringVector - Break INPUT up wherever one or more
+/// whitespace characters are found, and store the resulting tokens in
+/// OUTPUT. The tokens stored in OUTPUT are dynamically allocated
+/// using strdup (), so it is the caller's responsibility to free ()
+/// them later.
+///
+static void ParseCStringVector(std::vector<char *> &output,
+ const char *input) {
+ // Characters which will be treated as token separators:
+ static const char *delims = " \v\f\t\r\n";
+
+ std::string work (input);
+ // Skip past any delims at head of input string.
+ size_t pos = work.find_first_not_of (delims);
+ // If the string consists entirely of delims, then exit early.
+ if (pos == std::string::npos) return;
+ // Otherwise, jump forward to beginning of first word.
+ work = work.substr (pos);
+ // Find position of first delimiter.
+ pos = work.find_first_of (delims);
+
+ while (!work.empty() && pos != std::string::npos) {
+ // Everything from 0 to POS is the next word to copy.
+ output.push_back (strdup (work.substr (0,pos).c_str ()));
+ // Is there another word in the string?
+ size_t nextpos = work.find_first_not_of (delims, pos + 1);
+ if (nextpos != std::string::npos) {
+ // Yes? Then remove delims from beginning ...
+ work = work.substr (work.find_first_not_of (delims, pos + 1));
+ // and find the end of the word.
+ pos = work.find_first_of (delims);
+ } else {
+ // No? (Remainder of string is delims.) End the loop.
+ work = "";
+ pos = std::string::npos;
+ }
+ }
+
+ // If `input' ended with non-delim char, then we'll get here with
+ // the last word of `input' in `work'; copy it now.
+ if (!work.empty ()) {
+ output.push_back (strdup (work.c_str ()));
+ }
+}
+
+/// ParseEnvironmentOptions - An alternative entry point to the
+/// CommandLine library, which allows you to read the program's name
+/// from the caller (as PROGNAME) and its command-line arguments from
+/// an environment variable (whose name is given in ENVVAR).
+///
+void cl::ParseEnvironmentOptions(const char *progName, const char *envVar,
+ const char *Overview) {
+ // Check args.
+ assert(progName && "Program name not specified");
+ assert(envVar && "Environment variable name missing");
+
+ // Get the environment variable they want us to parse options out of.
+ const char *envValue = getenv(envVar);
+ if (!envValue)
+ return;
+
+ // Get program's "name", which we wouldn't know without the caller
+ // telling us.
+ std::vector<char*> newArgv;
+ newArgv.push_back(strdup(progName));
+
+ // Parse the value of the environment variable into a "command line"
+ // and hand it off to ParseCommandLineOptions().
+ ParseCStringVector(newArgv, envValue);
+ int newArgc = newArgv.size();
+ ParseCommandLineOptions(newArgc, &newArgv[0], Overview);
+
+ // Free all the strdup()ed strings.
+ for (std::vector<char*>::iterator i = newArgv.begin(), e = newArgv.end();
+ i != e; ++i)
+ free (*i);
+}
+
+void cl::ParseCommandLineOptions(int &argc, char **argv,
+ const char *Overview) {
+ // Process all registered options.
+ std::vector<Option*> PositionalOpts;
+ std::map<std::string, Option*> Opts;
+ GetOptionInfo(PositionalOpts, Opts);
+
+ assert((!Opts.empty() || !PositionalOpts.empty()) &&
+ "No options specified!");
+ sys::Path progname(argv[0]);
+
+ // Copy the program name into ProgName, making sure not to overflow it.
+ std::string ProgName = sys::Path(argv[0]).getLast();
+ if (ProgName.size() > 79) ProgName.resize(79);
+ strcpy(ProgramName, ProgName.c_str());
+
+ ProgramOverview = Overview;
+ bool ErrorParsing = false;
+
+ // Check out the positional arguments to collect information about them.
+ unsigned NumPositionalRequired = 0;
+
+ // Determine whether or not there are an unlimited number of positionals
+ bool HasUnlimitedPositionals = false;
+
+ Option *ConsumeAfterOpt = 0;
+ if (!PositionalOpts.empty()) {
+ if (PositionalOpts[0]->getNumOccurrencesFlag() == cl::ConsumeAfter) {
+ assert(PositionalOpts.size() > 1 &&
+ "Cannot specify cl::ConsumeAfter without a positional argument!");
+ ConsumeAfterOpt = PositionalOpts[0];
+ }
+
+ // Calculate how many positional values are _required_.
+ bool UnboundedFound = false;
+ for (unsigned i = ConsumeAfterOpt != 0, e = PositionalOpts.size();
+ i != e; ++i) {
+ Option *Opt = PositionalOpts[i];
+ if (RequiresValue(Opt))
+ ++NumPositionalRequired;
+ else if (ConsumeAfterOpt) {
+ // ConsumeAfter cannot be combined with "optional" positional options
+ // unless there is only one positional argument...
+ if (PositionalOpts.size() > 2)
+ ErrorParsing |=
+ Opt->error(" error - this positional option will never be matched, "
+ "because it does not Require a value, and a "
+ "cl::ConsumeAfter option is active!");
+ } else if (UnboundedFound && !Opt->ArgStr[0]) {
+ // This option does not "require" a value... Make sure this option is
+ // not specified after an option that eats all extra arguments, or this
+ // one will never get any!
+ //
+ ErrorParsing |= Opt->error(" error - option can never match, because "
+ "another positional argument will match an "
+ "unbounded number of values, and this option"
+ " does not require a value!");
+ }
+ UnboundedFound |= EatsUnboundedNumberOfValues(Opt);
+ }
+ HasUnlimitedPositionals = UnboundedFound || ConsumeAfterOpt;
+ }
+
+ // PositionalVals - A vector of "positional" arguments we accumulate into
+ // the process at the end...
+ //
+ std::vector<std::pair<std::string,unsigned> > PositionalVals;
+
+ // If the program has named positional arguments, and the name has been run
+ // across, keep track of which positional argument was named. Otherwise put
+ // the positional args into the PositionalVals list...
+ Option *ActivePositionalArg = 0;
+
+ // Loop over all of the arguments... processing them.
+ bool DashDashFound = false; // Have we read '--'?
+ for (int i = 1; i < argc; ++i) {
+ Option *Handler = 0;
+ const char *Value = 0;
+ const char *ArgName = "";
+
+ // If the option list changed, this means that some command line
+ // option has just been registered or deregistered. This can occur in
+ // response to things like -load, etc. If this happens, rescan the options.
+ if (OptionListChanged) {
+ PositionalOpts.clear();
+ Opts.clear();
+ GetOptionInfo(PositionalOpts, Opts);
+ OptionListChanged = false;
+ }
+
+ // Check to see if this is a positional argument. This argument is
+ // considered to be positional if it doesn't start with '-', if it is "-"
+ // itself, or if we have seen "--" already.
+ //
+ if (argv[i][0] != '-' || argv[i][1] == 0 || DashDashFound) {
+ // Positional argument!
+ if (ActivePositionalArg) {
+ ProvidePositionalOption(ActivePositionalArg, argv[i], i);
+ continue; // We are done!
+ } else if (!PositionalOpts.empty()) {
+ PositionalVals.push_back(std::make_pair(argv[i],i));
+
+ // All of the positional arguments have been fulfulled, give the rest to
+ // the consume after option... if it's specified...
+ //
+ if (PositionalVals.size() >= NumPositionalRequired &&
+ ConsumeAfterOpt != 0) {
+ for (++i; i < argc; ++i)
+ PositionalVals.push_back(std::make_pair(argv[i],i));
+ break; // Handle outside of the argument processing loop...
+ }
+
+ // Delay processing positional arguments until the end...
+ continue;
+ }
+ } else if (argv[i][0] == '-' && argv[i][1] == '-' && argv[i][2] == 0 &&
+ !DashDashFound) {
+ DashDashFound = true; // This is the mythical "--"?
+ continue; // Don't try to process it as an argument itself.
+ } else if (ActivePositionalArg &&
+ (ActivePositionalArg->getMiscFlags() & PositionalEatsArgs)) {
+ // If there is a positional argument eating options, check to see if this
+ // option is another positional argument. If so, treat it as an argument,
+ // otherwise feed it to the eating positional.
+ ArgName = argv[i]+1;
+ Handler = LookupOption(ArgName, Value, Opts);
+ if (!Handler || Handler->getFormattingFlag() != cl::Positional) {
+ ProvidePositionalOption(ActivePositionalArg, argv[i], i);
+ continue; // We are done!
+ }
+
+ } else { // We start with a '-', must be an argument...
+ ArgName = argv[i]+1;
+ Handler = LookupOption(ArgName, Value, Opts);
+
+ // Check to see if this "option" is really a prefixed or grouped argument.
+ if (Handler == 0) {
+ std::string RealName(ArgName);
+ if (RealName.size() > 1) {
+ unsigned Length = 0;
+ Option *PGOpt = getOptionPred(RealName, Length, isPrefixedOrGrouping,
+ Opts);
+
+ // If the option is a prefixed option, then the value is simply the
+ // rest of the name... so fall through to later processing, by
+ // setting up the argument name flags and value fields.
+ //
+ if (PGOpt && PGOpt->getFormattingFlag() == cl::Prefix) {
+ Value = ArgName+Length;
+ assert(Opts.find(std::string(ArgName, Value)) != Opts.end() &&
+ Opts.find(std::string(ArgName, Value))->second == PGOpt);
+ Handler = PGOpt;
+ } else if (PGOpt) {
+ // This must be a grouped option... handle them now.
+ assert(isGrouping(PGOpt) && "Broken getOptionPred!");
+
+ do {
+ // Move current arg name out of RealName into RealArgName...
+ std::string RealArgName(RealName.begin(),
+ RealName.begin() + Length);
+ RealName.erase(RealName.begin(), RealName.begin() + Length);
+
+ // Because ValueRequired is an invalid flag for grouped arguments,
+ // we don't need to pass argc/argv in...
+ //
+ assert(PGOpt->getValueExpectedFlag() != cl::ValueRequired &&
+ "Option can not be cl::Grouping AND cl::ValueRequired!");
+ int Dummy;
+ ErrorParsing |= ProvideOption(PGOpt, RealArgName.c_str(),
+ 0, 0, 0, Dummy);
+
+ // Get the next grouping option...
+ PGOpt = getOptionPred(RealName, Length, isGrouping, Opts);
+ } while (PGOpt && Length != RealName.size());
+
+ Handler = PGOpt; // Ate all of the options.
+ }
+ }
+ }
+ }
+
+ if (Handler == 0) {
+ cerr << ProgramName << ": Unknown command line argument '"
+ << argv[i] << "'. Try: '" << argv[0] << " --help'\n";
+ ErrorParsing = true;
+ continue;
+ }
+
+ // Check to see if this option accepts a comma separated list of values. If
+ // it does, we have to split up the value into multiple values...
+ if (Value && Handler->getMiscFlags() & CommaSeparated) {
+ std::string Val(Value);
+ std::string::size_type Pos = Val.find(',');
+
+ while (Pos != std::string::npos) {
+ // Process the portion before the comma...
+ ErrorParsing |= ProvideOption(Handler, ArgName,
+ std::string(Val.begin(),
+ Val.begin()+Pos).c_str(),
+ argc, argv, i);
+ // Erase the portion before the comma, AND the comma...
+ Val.erase(Val.begin(), Val.begin()+Pos+1);
+ Value += Pos+1; // Increment the original value pointer as well...
+
+ // Check for another comma...
+ Pos = Val.find(',');
+ }
+ }
+
+ // If this is a named positional argument, just remember that it is the
+ // active one...
+ if (Handler->getFormattingFlag() == cl::Positional)
+ ActivePositionalArg = Handler;
+ else
+ ErrorParsing |= ProvideOption(Handler, ArgName, Value, argc, argv, i);
+ }
+
+ // Check and handle positional arguments now...
+ if (NumPositionalRequired > PositionalVals.size()) {
+ cerr << ProgramName
+ << ": Not enough positional command line arguments specified!\n"
+ << "Must specify at least " << NumPositionalRequired
+ << " positional arguments: See: " << argv[0] << " --help\n";
+
+ ErrorParsing = true;
+ } else if (!HasUnlimitedPositionals
+ && PositionalVals.size() > PositionalOpts.size()) {
+ cerr << ProgramName
+ << ": Too many positional arguments specified!\n"
+ << "Can specify at most " << PositionalOpts.size()
+ << " positional arguments: See: " << argv[0] << " --help\n";
+ ErrorParsing = true;
+
+ } else if (ConsumeAfterOpt == 0) {
+ // Positional args have already been handled if ConsumeAfter is specified...
+ unsigned ValNo = 0, NumVals = PositionalVals.size();
+ for (unsigned i = 0, e = PositionalOpts.size(); i != e; ++i) {
+ if (RequiresValue(PositionalOpts[i])) {
+ ProvidePositionalOption(PositionalOpts[i], PositionalVals[ValNo].first,
+ PositionalVals[ValNo].second);
+ ValNo++;
+ --NumPositionalRequired; // We fulfilled our duty...
+ }
+
+ // If we _can_ give this option more arguments, do so now, as long as we
+ // do not give it values that others need. 'Done' controls whether the
+ // option even _WANTS_ any more.
+ //
+ bool Done = PositionalOpts[i]->getNumOccurrencesFlag() == cl::Required;
+ while (NumVals-ValNo > NumPositionalRequired && !Done) {
+ switch (PositionalOpts[i]->getNumOccurrencesFlag()) {
+ case cl::Optional:
+ Done = true; // Optional arguments want _at most_ one value
+ // FALL THROUGH
+ case cl::ZeroOrMore: // Zero or more will take all they can get...
+ case cl::OneOrMore: // One or more will take all they can get...
+ ProvidePositionalOption(PositionalOpts[i],
+ PositionalVals[ValNo].first,
+ PositionalVals[ValNo].second);
+ ValNo++;
+ break;
+ default:
+ assert(0 && "Internal error, unexpected NumOccurrences flag in "
+ "positional argument processing!");
+ }
+ }
+ }
+ } else {
+ assert(ConsumeAfterOpt && NumPositionalRequired <= PositionalVals.size());
+ unsigned ValNo = 0;
+ for (unsigned j = 1, e = PositionalOpts.size(); j != e; ++j)
+ if (RequiresValue(PositionalOpts[j])) {
+ ErrorParsing |= ProvidePositionalOption(PositionalOpts[j],
+ PositionalVals[ValNo].first,
+ PositionalVals[ValNo].second);
+ ValNo++;
+ }
+
+ // Handle the case where there is just one positional option, and it's
+ // optional. In this case, we want to give JUST THE FIRST option to the
+ // positional option and keep the rest for the consume after. The above
+ // loop would have assigned no values to positional options in this case.
+ //
+ if (PositionalOpts.size() == 2 && ValNo == 0 && !PositionalVals.empty()) {
+ ErrorParsing |= ProvidePositionalOption(PositionalOpts[1],
+ PositionalVals[ValNo].first,
+ PositionalVals[ValNo].second);
+ ValNo++;
+ }
+
+ // Handle over all of the rest of the arguments to the
+ // cl::ConsumeAfter command line option...
+ for (; ValNo != PositionalVals.size(); ++ValNo)
+ ErrorParsing |= ProvidePositionalOption(ConsumeAfterOpt,
+ PositionalVals[ValNo].first,
+ PositionalVals[ValNo].second);
+ }
+
+ // Loop over args and make sure all required args are specified!
+ for (std::map<std::string, Option*>::iterator I = Opts.begin(),
+ E = Opts.end(); I != E; ++I) {
+ switch (I->second->getNumOccurrencesFlag()) {
+ case Required:
+ case OneOrMore:
+ if (I->second->getNumOccurrences() == 0) {
+ I->second->error(" must be specified at least once!");
+ ErrorParsing = true;
+ }
+ // Fall through
+ default:
+ break;
+ }
+ }
+
+ // Free all of the memory allocated to the map. Command line options may only
+ // be processed once!
+ Opts.clear();
+ PositionalOpts.clear();
+ MoreHelp->clear();
+
+ // If we had an error processing our arguments, don't let the program execute
+ if (ErrorParsing) exit(1);
+}
+
+//===----------------------------------------------------------------------===//
+// Option Base class implementation
+//
+
+bool Option::error(std::string Message, const char *ArgName) {
+ if (ArgName == 0) ArgName = ArgStr;
+ if (ArgName[0] == 0)
+ cerr << HelpStr; // Be nice for positional arguments
+ else
+ cerr << ProgramName << ": for the -" << ArgName;
+
+ cerr << " option: " << Message << "\n";
+ return true;
+}
+
+bool Option::addOccurrence(unsigned pos, const char *ArgName,
+ const std::string &Value) {
+ NumOccurrences++; // Increment the number of times we have been seen
+
+ switch (getNumOccurrencesFlag()) {
+ case Optional:
+ if (NumOccurrences > 1)
+ return error(": may only occur zero or one times!", ArgName);
+ break;
+ case Required:
+ if (NumOccurrences > 1)
+ return error(": must occur exactly one time!", ArgName);
+ // Fall through
+ case OneOrMore:
+ case ZeroOrMore:
+ case ConsumeAfter: break;
+ default: return error(": bad num occurrences flag value!");
+ }
+
+ return handleOccurrence(pos, ArgName, Value);
+}
+
+
+// getValueStr - Get the value description string, using "DefaultMsg" if nothing
+// has been specified yet.
+//
+static const char *getValueStr(const Option &O, const char *DefaultMsg) {
+ if (O.ValueStr[0] == 0) return DefaultMsg;
+ return O.ValueStr;
+}
+
+//===----------------------------------------------------------------------===//
+// cl::alias class implementation
+//
+
+// Return the width of the option tag for printing...
+unsigned alias::getOptionWidth() const {
+ return std::strlen(ArgStr)+6;
+}
+
+// Print out the option for the alias.
+void alias::printOptionInfo(unsigned GlobalWidth) const {
+ unsigned L = std::strlen(ArgStr);
+ cout << " -" << ArgStr << std::string(GlobalWidth-L-6, ' ') << " - "
+ << HelpStr << "\n";
+}
+
+
+
+//===----------------------------------------------------------------------===//
+// Parser Implementation code...
+//
+
+// basic_parser implementation
+//
+
+// Return the width of the option tag for printing...
+unsigned basic_parser_impl::getOptionWidth(const Option &O) const {
+ unsigned Len = std::strlen(O.ArgStr);
+ if (const char *ValName = getValueName())
+ Len += std::strlen(getValueStr(O, ValName))+3;
+
+ return Len + 6;
+}
+
+// printOptionInfo - Print out information about this option. The
+// to-be-maintained width is specified.
+//
+void basic_parser_impl::printOptionInfo(const Option &O,
+ unsigned GlobalWidth) const {
+ cout << " -" << O.ArgStr;
+
+ if (const char *ValName = getValueName())
+ cout << "=<" << getValueStr(O, ValName) << ">";
+
+ cout << std::string(GlobalWidth-getOptionWidth(O), ' ') << " - "
+ << O.HelpStr << "\n";
+}
+
+
+
+
+// parser<bool> implementation
+//
+bool parser<bool>::parse(Option &O, const char *ArgName,
+ const std::string &Arg, bool &Value) {
+ if (Arg == "" || Arg == "true" || Arg == "TRUE" || Arg == "True" ||
+ Arg == "1") {
+ Value = true;
+ } else if (Arg == "false" || Arg == "FALSE" || Arg == "False" || Arg == "0") {
+ Value = false;
+ } else {
+ return O.error(": '" + Arg +
+ "' is invalid value for boolean argument! Try 0 or 1");
+ }
+ return false;
+}
+
+// parser<boolOrDefault> implementation
+//
+bool parser<boolOrDefault>::parse(Option &O, const char *ArgName,
+ const std::string &Arg, boolOrDefault &Value) {
+ if (Arg == "" || Arg == "true" || Arg == "TRUE" || Arg == "True" ||
+ Arg == "1") {
+ Value = BOU_TRUE;
+ } else if (Arg == "false" || Arg == "FALSE" || Arg == "False" || Arg == "0") {
+ Value = BOU_FALSE;
+ } else {
+ return O.error(": '" + Arg +
+ "' is invalid value for boolean argument! Try 0 or 1");
+ }
+ return false;
+}
+
+// parser<int> implementation
+//
+bool parser<int>::parse(Option &O, const char *ArgName,
+ const std::string &Arg, int &Value) {
+ char *End;
+ Value = (int)strtol(Arg.c_str(), &End, 0);
+ if (*End != 0)
+ return O.error(": '" + Arg + "' value invalid for integer argument!");
+ return false;
+}
+
+// parser<unsigned> implementation
+//
+bool parser<unsigned>::parse(Option &O, const char *ArgName,
+ const std::string &Arg, unsigned &Value) {
+ char *End;
+ errno = 0;
+ unsigned long V = strtoul(Arg.c_str(), &End, 0);
+ Value = (unsigned)V;
+ if (((V == ULONG_MAX) && (errno == ERANGE))
+ || (*End != 0)
+ || (Value != V))
+ return O.error(": '" + Arg + "' value invalid for uint argument!");
+ return false;
+}
+
+// parser<double>/parser<float> implementation
+//
+static bool parseDouble(Option &O, const std::string &Arg, double &Value) {
+ const char *ArgStart = Arg.c_str();
+ char *End;
+ Value = strtod(ArgStart, &End);
+ if (*End != 0)
+ return O.error(": '" +Arg+ "' value invalid for floating point argument!");
+ return false;
+}
+
+bool parser<double>::parse(Option &O, const char *AN,
+ const std::string &Arg, double &Val) {
+ return parseDouble(O, Arg, Val);
+}
+
+bool parser<float>::parse(Option &O, const char *AN,
+ const std::string &Arg, float &Val) {
+ double dVal;
+ if (parseDouble(O, Arg, dVal))
+ return true;
+ Val = (float)dVal;
+ return false;
+}
+
+
+
+// generic_parser_base implementation
+//
+
+// findOption - Return the option number corresponding to the specified
+// argument string. If the option is not found, getNumOptions() is returned.
+//
+unsigned generic_parser_base::findOption(const char *Name) {
+ unsigned i = 0, e = getNumOptions();
+ std::string N(Name);
+
+ while (i != e)
+ if (getOption(i) == N)
+ return i;
+ else
+ ++i;
+ return e;
+}
+
+
+// Return the width of the option tag for printing...
+unsigned generic_parser_base::getOptionWidth(const Option &O) const {
+ if (O.hasArgStr()) {
+ unsigned Size = std::strlen(O.ArgStr)+6;
+ for (unsigned i = 0, e = getNumOptions(); i != e; ++i)
+ Size = std::max(Size, (unsigned)std::strlen(getOption(i))+8);
+ return Size;
+ } else {
+ unsigned BaseSize = 0;
+ for (unsigned i = 0, e = getNumOptions(); i != e; ++i)
+ BaseSize = std::max(BaseSize, (unsigned)std::strlen(getOption(i))+8);
+ return BaseSize;
+ }
+}
+
+// printOptionInfo - Print out information about this option. The
+// to-be-maintained width is specified.
+//
+void generic_parser_base::printOptionInfo(const Option &O,
+ unsigned GlobalWidth) const {
+ if (O.hasArgStr()) {
+ unsigned L = std::strlen(O.ArgStr);
+ cout << " -" << O.ArgStr << std::string(GlobalWidth-L-6, ' ')
+ << " - " << O.HelpStr << "\n";
+
+ for (unsigned i = 0, e = getNumOptions(); i != e; ++i) {
+ unsigned NumSpaces = GlobalWidth-strlen(getOption(i))-8;
+ cout << " =" << getOption(i) << std::string(NumSpaces, ' ')
+ << " - " << getDescription(i) << "\n";
+ }
+ } else {
+ if (O.HelpStr[0])
+ cout << " " << O.HelpStr << "\n";
+ for (unsigned i = 0, e = getNumOptions(); i != e; ++i) {
+ unsigned L = std::strlen(getOption(i));
+ cout << " -" << getOption(i) << std::string(GlobalWidth-L-8, ' ')
+ << " - " << getDescription(i) << "\n";
+ }
+ }
+}
+
+
+//===----------------------------------------------------------------------===//
+// --help and --help-hidden option implementation
+//
+
+namespace {
+
+class HelpPrinter {
+ unsigned MaxArgLen;
+ const Option *EmptyArg;
+ const bool ShowHidden;
+
+ // isHidden/isReallyHidden - Predicates to be used to filter down arg lists.
+ inline static bool isHidden(std::pair<std::string, Option *> &OptPair) {
+ return OptPair.second->getOptionHiddenFlag() >= Hidden;
+ }
+ inline static bool isReallyHidden(std::pair<std::string, Option *> &OptPair) {
+ return OptPair.second->getOptionHiddenFlag() == ReallyHidden;
+ }
+
+public:
+ HelpPrinter(bool showHidden) : ShowHidden(showHidden) {
+ EmptyArg = 0;
+ }
+
+ void operator=(bool Value) {
+ if (Value == false) return;
+
+ // Get all the options.
+ std::vector<Option*> PositionalOpts;
+ std::map<std::string, Option*> OptMap;
+ GetOptionInfo(PositionalOpts, OptMap);
+
+ // Copy Options into a vector so we can sort them as we like...
+ std::vector<std::pair<std::string, Option*> > Opts;
+ copy(OptMap.begin(), OptMap.end(), std::back_inserter(Opts));
+
+ // Eliminate Hidden or ReallyHidden arguments, depending on ShowHidden
+ Opts.erase(std::remove_if(Opts.begin(), Opts.end(),
+ std::ptr_fun(ShowHidden ? isReallyHidden : isHidden)),
+ Opts.end());
+
+ // Eliminate duplicate entries in table (from enum flags options, f.e.)
+ { // Give OptionSet a scope
+ std::set<Option*> OptionSet;
+ for (unsigned i = 0; i != Opts.size(); ++i)
+ if (OptionSet.count(Opts[i].second) == 0)
+ OptionSet.insert(Opts[i].second); // Add new entry to set
+ else
+ Opts.erase(Opts.begin()+i--); // Erase duplicate
+ }
+
+ if (ProgramOverview)
+ cout << "OVERVIEW:" << ProgramOverview << "\n";
+
+ cout << "USAGE: " << ProgramName << " [options]";
+
+ // Print out the positional options.
+ Option *CAOpt = 0; // The cl::ConsumeAfter option, if it exists...
+ if (!PositionalOpts.empty() &&
+ PositionalOpts[0]->getNumOccurrencesFlag() == ConsumeAfter)
+ CAOpt = PositionalOpts[0];
+
+ for (unsigned i = CAOpt != 0, e = PositionalOpts.size(); i != e; ++i) {
+ if (PositionalOpts[i]->ArgStr[0])
+ cout << " --" << PositionalOpts[i]->ArgStr;
+ cout << " " << PositionalOpts[i]->HelpStr;
+ }
+
+ // Print the consume after option info if it exists...
+ if (CAOpt) cout << " " << CAOpt->HelpStr;
+
+ cout << "\n\n";
+
+ // Compute the maximum argument length...
+ MaxArgLen = 0;
+ for (unsigned i = 0, e = Opts.size(); i != e; ++i)
+ MaxArgLen = std::max(MaxArgLen, Opts[i].second->getOptionWidth());
+
+ cout << "OPTIONS:\n";
+ for (unsigned i = 0, e = Opts.size(); i != e; ++i)
+ Opts[i].second->printOptionInfo(MaxArgLen);
+
+ // Print any extra help the user has declared.
+ for (std::vector<const char *>::iterator I = MoreHelp->begin(),
+ E = MoreHelp->end(); I != E; ++I)
+ cout << *I;
+ MoreHelp->clear();
+
+ // Halt the program since help information was printed
+ exit(1);
+ }
+};
+} // End anonymous namespace
+
+// Define the two HelpPrinter instances that are used to print out help, or
+// help-hidden...
+//
+static HelpPrinter NormalPrinter(false);
+static HelpPrinter HiddenPrinter(true);
+
+static cl::opt<HelpPrinter, true, parser<bool> >
+HOp("help", cl::desc("Display available options (--help-hidden for more)"),
+ cl::location(NormalPrinter), cl::ValueDisallowed);
+
+static cl::opt<HelpPrinter, true, parser<bool> >
+HHOp("help-hidden", cl::desc("Display all available options"),
+ cl::location(HiddenPrinter), cl::Hidden, cl::ValueDisallowed);
+
+static void (*OverrideVersionPrinter)() = 0;
+
+namespace {
+class VersionPrinter {
+public:
+ void print() {
+ cout << "Low Level Virtual Machine (http://llvm.org/):\n";
+ cout << " " << PACKAGE_NAME << " version " << PACKAGE_VERSION;
+#ifdef LLVM_VERSION_INFO
+ cout << LLVM_VERSION_INFO;
+#endif
+ cout << "\n ";
+#ifndef __OPTIMIZE__
+ cout << "DEBUG build";
+#else
+ cout << "Optimized build";
+#endif
+#ifndef NDEBUG
+ cout << " with assertions";
+#endif
+ cout << ".\n";
+ }
+ void operator=(bool OptionWasSpecified) {
+ if (OptionWasSpecified) {
+ if (OverrideVersionPrinter == 0) {
+ print();
+ exit(1);
+ } else {
+ (*OverrideVersionPrinter)();
+ exit(1);
+ }
+ }
+ }
+};
+} // End anonymous namespace
+
+
+// Define the --version option that prints out the LLVM version for the tool
+static VersionPrinter VersionPrinterInstance;
+
+static cl::opt<VersionPrinter, true, parser<bool> >
+VersOp("version", cl::desc("Display the version of this program"),
+ cl::location(VersionPrinterInstance), cl::ValueDisallowed);
+
+// Utility function for printing the help message.
+void cl::PrintHelpMessage() {
+ // This looks weird, but it actually prints the help message. The
+ // NormalPrinter variable is a HelpPrinter and the help gets printed when
+ // its operator= is invoked. That's because the "normal" usages of the
+ // help printer is to be assigned true/false depending on whether the
+ // --help option was given or not. Since we're circumventing that we have
+ // to make it look like --help was given, so we assign true.
+ NormalPrinter = true;
+}
+
+/// Utility function for printing version number.
+void cl::PrintVersionMessage() {
+ VersionPrinterInstance.print();
+}
+
+void cl::SetVersionPrinter(void (*func)()) {
+ OverrideVersionPrinter = func;
+}
diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
new file mode 100644
index 0000000..fdfe28a
--- /dev/null
+++ b/lib/Support/ConstantRange.cpp
@@ -0,0 +1,474 @@
+//===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Represent a range of possible values that may occur when the program is run
+// for an integral value. This keeps track of a lower and upper bound for the
+// constant, which MAY wrap around the end of the numeric range. To do this, it
+// keeps track of a [lower, upper) bound, which specifies an interval just like
+// STL iterators. When used with boolean values, the following are important
+// ranges (other integral ranges use min/max values for special range values):
+//
+// [F, F) = {} = Empty set
+// [T, F) = {T}
+// [F, T) = {F}
+// [T, T) = {F, T} = Full set
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/ConstantRange.h"
+#include "llvm/Support/Streams.h"
+#include <ostream>
+using namespace llvm;
+
+/// Initialize a full (the default) or empty set for the specified type.
+///
+ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) :
+ Lower(BitWidth, 0), Upper(BitWidth, 0) {
+ if (Full)
+ Lower = Upper = APInt::getMaxValue(BitWidth);
+ else
+ Lower = Upper = APInt::getMinValue(BitWidth);
+}
+
+/// Initialize a range to hold the single specified value.
+///
+ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) { }
+
+ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
+ Lower(L), Upper(U) {
+ assert(L.getBitWidth() == U.getBitWidth() &&
+ "ConstantRange with unequal bit widths");
+ assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
+ "Lower == Upper, but they aren't min or max value!");
+}
+
+/// isFullSet - Return true if this set contains all of the elements possible
+/// for this data-type
+bool ConstantRange::isFullSet() const {
+ return Lower == Upper && Lower.isMaxValue();
+}
+
+/// isEmptySet - Return true if this set contains no members.
+///
+bool ConstantRange::isEmptySet() const {
+ return Lower == Upper && Lower.isMinValue();
+}
+
+/// isWrappedSet - Return true if this set wraps around the top of the range,
+/// for example: [100, 8)
+///
+bool ConstantRange::isWrappedSet() const {
+ return Lower.ugt(Upper);
+}
+
+/// getSetSize - Return the number of elements in this set.
+///
+APInt ConstantRange::getSetSize() const {
+ if (isEmptySet())
+ return APInt(getBitWidth(), 0);
+ if (getBitWidth() == 1) {
+ if (Lower != Upper) // One of T or F in the set...
+ return APInt(2, 1);
+ return APInt(2, 2); // Must be full set...
+ }
+
+ // Simply subtract the bounds...
+ return Upper - Lower;
+}
+
+/// getUnsignedMax - Return the largest unsigned value contained in the
+/// ConstantRange.
+///
+APInt ConstantRange::getUnsignedMax() const {
+ if (isFullSet() || isWrappedSet())
+ return APInt::getMaxValue(getBitWidth());
+ else
+ return getUpper() - 1;
+}
+
+/// getUnsignedMin - Return the smallest unsigned value contained in the
+/// ConstantRange.
+///
+APInt ConstantRange::getUnsignedMin() const {
+ if (isFullSet() || (isWrappedSet() && getUpper() != 0))
+ return APInt::getMinValue(getBitWidth());
+ else
+ return getLower();
+}
+
+/// getSignedMax - Return the largest signed value contained in the
+/// ConstantRange.
+///
+APInt ConstantRange::getSignedMax() const {
+ APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
+ if (!isWrappedSet()) {
+ if (getLower().sle(getUpper() - 1))
+ return getUpper() - 1;
+ else
+ return SignedMax;
+ } else {
+ if ((getUpper() - 1).slt(getLower())) {
+ if (getLower() != SignedMax)
+ return SignedMax;
+ else
+ return getUpper() - 1;
+ } else {
+ return getUpper() - 1;
+ }
+ }
+}
+
+/// getSignedMin - Return the smallest signed value contained in the
+/// ConstantRange.
+///
+APInt ConstantRange::getSignedMin() const {
+ APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
+ if (!isWrappedSet()) {
+ if (getLower().sle(getUpper() - 1))
+ return getLower();
+ else
+ return SignedMin;
+ } else {
+ if ((getUpper() - 1).slt(getLower())) {
+ if (getUpper() != SignedMin)
+ return SignedMin;
+ else
+ return getLower();
+ } else {
+ return getLower();
+ }
+ }
+}
+
+/// contains - Return true if the specified value is in the set.
+///
+bool ConstantRange::contains(const APInt &V) const {
+ if (Lower == Upper)
+ return isFullSet();
+
+ if (!isWrappedSet())
+ return Lower.ule(V) && V.ult(Upper);
+ else
+ return Lower.ule(V) || V.ult(Upper);
+}
+
+/// subtract - Subtract the specified constant from the endpoints of this
+/// constant range.
+ConstantRange ConstantRange::subtract(const APInt &Val) const {
+ assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
+ // If the set is empty or full, don't modify the endpoints.
+ if (Lower == Upper)
+ return *this;
+ return ConstantRange(Lower - Val, Upper - Val);
+}
+
+
+// intersect1Wrapped - This helper function is used to intersect two ranges when
+// it is known that LHS is wrapped and RHS isn't.
+//
+ConstantRange
+ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
+ const ConstantRange &RHS) {
+ assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
+
+ // Check to see if we overlap on the Left side of RHS...
+ //
+ if (RHS.Lower.ult(LHS.Upper)) {
+ // We do overlap on the left side of RHS, see if we overlap on the right of
+ // RHS...
+ if (RHS.Upper.ugt(LHS.Lower)) {
+ // Ok, the result overlaps on both the left and right sides. See if the
+ // resultant interval will be smaller if we wrap or not...
+ //
+ if (LHS.getSetSize().ult(RHS.getSetSize()))
+ return LHS;
+ else
+ return RHS;
+
+ } else {
+ // No overlap on the right, just on the left.
+ return ConstantRange(RHS.Lower, LHS.Upper);
+ }
+ } else {
+ // We don't overlap on the left side of RHS, see if we overlap on the right
+ // of RHS...
+ if (RHS.Upper.ugt(LHS.Lower)) {
+ // Simple overlap...
+ return ConstantRange(LHS.Lower, RHS.Upper);
+ } else {
+ // No overlap...
+ return ConstantRange(LHS.getBitWidth(), false);
+ }
+ }
+}
+
+/// intersectWith - Return the range that results from the intersection of this
+/// range with another range.
+///
+ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
+ assert(getBitWidth() == CR.getBitWidth() &&
+ "ConstantRange types don't agree!");
+ // Handle common special cases
+ if (isEmptySet() || CR.isFullSet())
+ return *this;
+ if (isFullSet() || CR.isEmptySet())
+ return CR;
+
+ if (!isWrappedSet()) {
+ if (!CR.isWrappedSet()) {
+ using namespace APIntOps;
+ APInt L = umax(Lower, CR.Lower);
+ APInt U = umin(Upper, CR.Upper);
+
+ if (L.ult(U)) // If range isn't empty...
+ return ConstantRange(L, U);
+ else
+ return ConstantRange(getBitWidth(), false);// Otherwise, empty set
+ } else
+ return intersect1Wrapped(CR, *this);
+ } else { // We know "this" is wrapped...
+ if (!CR.isWrappedSet())
+ return intersect1Wrapped(*this, CR);
+ else {
+ // Both ranges are wrapped...
+ using namespace APIntOps;
+ APInt L = umax(Lower, CR.Lower);
+ APInt U = umin(Upper, CR.Upper);
+ return ConstantRange(L, U);
+ }
+ }
+ return *this;
+}
+
+/// maximalIntersectWith - Return the range that results from the intersection
+/// of this range with another range. The resultant range is guaranteed to
+/// include all elements contained in both input ranges, and to have the
+/// smallest possible set size that does so. Because there may be two
+/// intersections with the same set size, A.maximalIntersectWith(B) might not
+/// be equal to B.maximalIntersect(A).
+ConstantRange ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
+ assert(getBitWidth() == CR.getBitWidth() &&
+ "ConstantRange types don't agree!");
+
+ // Handle common cases.
+ if ( isEmptySet() || CR.isFullSet()) return *this;
+ if (CR.isEmptySet() || isFullSet()) return CR;
+
+ if (!isWrappedSet() && CR.isWrappedSet())
+ return CR.maximalIntersectWith(*this);
+
+ if (!isWrappedSet() && !CR.isWrappedSet()) {
+ if (Lower.ult(CR.Lower)) {
+ if (Upper.ule(CR.Lower))
+ return ConstantRange(getBitWidth(), false);
+
+ if (Upper.ult(CR.Upper))
+ return ConstantRange(CR.Lower, Upper);
+
+ return CR;
+ } else {
+ if (Upper.ult(CR.Upper))
+ return *this;
+
+ if (Lower.ult(CR.Upper))
+ return ConstantRange(Lower, CR.Upper);
+
+ return ConstantRange(getBitWidth(), false);
+ }
+ }
+
+ if (isWrappedSet() && !CR.isWrappedSet()) {
+ if (CR.Lower.ult(Upper)) {
+ if (CR.Upper.ult(Upper))
+ return CR;
+
+ if (CR.Upper.ult(Lower))
+ return ConstantRange(CR.Lower, Upper);
+
+ if (getSetSize().ult(CR.getSetSize()))
+ return *this;
+ else
+ return CR;
+ } else if (CR.Lower.ult(Lower)) {
+ if (CR.Upper.ule(Lower))
+ return ConstantRange(getBitWidth(), false);
+
+ return ConstantRange(Lower, CR.Upper);
+ }
+ return CR;
+ }
+
+ if (CR.Upper.ult(Upper)) {
+ if (CR.Lower.ult(Upper)) {
+ if (getSetSize().ult(CR.getSetSize()))
+ return *this;
+ else
+ return CR;
+ }
+
+ if (CR.Lower.ult(Lower))
+ return ConstantRange(Lower, CR.Upper);
+
+ return CR;
+ } else if (CR.Upper.ult(Lower)) {
+ if (CR.Lower.ult(Lower))
+ return *this;
+
+ return ConstantRange(CR.Lower, Upper);
+ }
+ if (getSetSize().ult(CR.getSetSize()))
+ return *this;
+ else
+ return CR;
+}
+
+
+/// unionWith - Return the range that results from the union of this range with
+/// another range. The resultant range is guaranteed to include the elements of
+/// both sets, but may contain more. For example, [3, 9) union [12,15) is
+/// [3, 15), which includes 9, 10, and 11, which were not included in either
+/// set before.
+///
+ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
+ assert(getBitWidth() == CR.getBitWidth() &&
+ "ConstantRange types don't agree!");
+
+ if ( isFullSet() || CR.isEmptySet()) return *this;
+ if (CR.isFullSet() || isEmptySet()) return CR;
+
+ if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
+
+ APInt L = Lower, U = Upper;
+
+ if (!isWrappedSet() && !CR.isWrappedSet()) {
+ if (CR.Lower.ult(L))
+ L = CR.Lower;
+
+ if (CR.Upper.ugt(U))
+ U = CR.Upper;
+ }
+
+ if (isWrappedSet() && !CR.isWrappedSet()) {
+ if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) ||
+ (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) {
+ return *this;
+ }
+
+ if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
+ return ConstantRange(getBitWidth());
+ }
+
+ if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) {
+ APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
+ if (d1.ult(d2)) {
+ U = CR.Upper;
+ } else {
+ L = CR.Upper;
+ }
+ }
+
+ if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) {
+ APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
+ if (d1.ult(d2)) {
+ U = CR.Lower + 1;
+ } else {
+ L = CR.Upper - 1;
+ }
+ }
+
+ if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) {
+ APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
+
+ if (d1.ult(d2)) {
+ U = CR.Lower + 1;
+ } else {
+ L = CR.Lower;
+ }
+ }
+ }
+
+ if (isWrappedSet() && CR.isWrappedSet()) {
+ if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper))
+ return ConstantRange(getBitWidth());
+
+ if (CR.Upper.ugt(U)) {
+ U = CR.Upper;
+ }
+
+ if (CR.Lower.ult(L)) {
+ L = CR.Lower;
+ }
+
+ if (L == U) return ConstantRange(getBitWidth());
+ }
+
+ return ConstantRange(L, U);
+}
+
+/// zeroExtend - Return a new range in the specified integer type, which must
+/// be strictly larger than the current type. The returned range will
+/// correspond to the possible range of values as if the source range had been
+/// zero extended.
+ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
+ unsigned SrcTySize = getBitWidth();
+ assert(SrcTySize < DstTySize && "Not a value extension");
+ if (isFullSet())
+ // Change a source full set into [0, 1 << 8*numbytes)
+ return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
+
+ APInt L = Lower; L.zext(DstTySize);
+ APInt U = Upper; U.zext(DstTySize);
+ return ConstantRange(L, U);
+}
+
+/// signExtend - Return a new range in the specified integer type, which must
+/// be strictly larger than the current type. The returned range will
+/// correspond to the possible range of values as if the source range had been
+/// sign extended.
+ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
+ unsigned SrcTySize = getBitWidth();
+ assert(SrcTySize < DstTySize && "Not a value extension");
+ if (isFullSet()) {
+ return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
+ APInt::getLowBitsSet(DstTySize, SrcTySize-1));
+ }
+
+ APInt L = Lower; L.sext(DstTySize);
+ APInt U = Upper; U.sext(DstTySize);
+ return ConstantRange(L, U);
+}
+
+/// truncate - Return a new range in the specified integer type, which must be
+/// strictly smaller than the current type. The returned range will
+/// correspond to the possible range of values as if the source range had been
+/// truncated to the specified type.
+ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
+ unsigned SrcTySize = getBitWidth();
+ assert(SrcTySize > DstTySize && "Not a value truncation");
+ APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
+ if (isFullSet() || getSetSize().ugt(Size))
+ return ConstantRange(DstTySize);
+
+ APInt L = Lower; L.trunc(DstTySize);
+ APInt U = Upper; U.trunc(DstTySize);
+ return ConstantRange(L, U);
+}
+
+/// print - Print out the bounds to a stream...
+///
+void ConstantRange::print(std::ostream &OS) const {
+ OS << "[" << Lower.toStringSigned(10) << ","
+ << Upper.toStringSigned(10) << " )";
+}
+
+/// dump - Allow printing from a debugger easily...
+///
+void ConstantRange::dump() const {
+ print(cerr);
+}
diff --git a/lib/Support/Debug.cpp b/lib/Support/Debug.cpp
new file mode 100644
index 0000000..c5b6fa2
--- /dev/null
+++ b/lib/Support/Debug.cpp
@@ -0,0 +1,77 @@
+//===-- Debug.cpp - An easy way to add debug output to your code ----------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a handle way of adding debugging information to your
+// code, without it being enabled all of the time, and without having to add
+// command line options to enable it.
+//
+// In particular, just wrap your code with the DEBUG() macro, and it will be
+// enabled automatically if you specify '-debug' on the command-line.
+// Alternatively, you can also use the SET_DEBUG_TYPE("foo") macro to specify
+// that your debug code belongs to class "foo". Then, on the command line, you
+// can specify '-debug-only=foo' to enable JUST the debug information for the
+// foo class.
+//
+// When compiling in release mode, the -debug-* options and all code in DEBUG()
+// statements disappears, so it does not effect the runtime of the code.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+using namespace llvm;
+
+bool llvm::DebugFlag; // DebugFlag - Exported boolean set by the -debug option
+
+namespace {
+#ifndef NDEBUG
+ // -debug - Command line option to enable the DEBUG statements in the passes.
+ // This flag may only be enabled in debug builds.
+ cl::opt<bool, true>
+ Debug("debug", cl::desc("Enable debug output"), cl::Hidden,
+ cl::location(DebugFlag));
+
+ std::string CurrentDebugType;
+ struct DebugOnlyOpt {
+ void operator=(const std::string &Val) const {
+ DebugFlag |= !Val.empty();
+ CurrentDebugType = Val;
+ }
+ } DebugOnlyOptLoc;
+
+ cl::opt<DebugOnlyOpt, true, cl::parser<std::string> >
+ DebugOnly("debug-only", cl::desc("Enable a specific type of debug output"),
+ cl::Hidden, cl::value_desc("debug string"),
+ cl::location(DebugOnlyOptLoc), cl::ValueRequired);
+#endif
+}
+
+// isCurrentDebugType - Return true if the specified string is the debug type
+// specified on the command line, or if none was specified on the command line
+// with the -debug-only=X option.
+//
+bool llvm::isCurrentDebugType(const char *DebugType) {
+#ifndef NDEBUG
+ return CurrentDebugType.empty() || DebugType == CurrentDebugType;
+#else
+ return false;
+#endif
+}
+
+// getErrorOutputStream - Returns the error output stream (std::cerr). This
+// places the std::c* I/O streams into one .cpp file and relieves the whole
+// program from having to have hundreds of static c'tor/d'tors for them.
+//
+OStream &llvm::getErrorOutputStream(const char *DebugType) {
+ static OStream cnoout(0);
+ if (DebugFlag && isCurrentDebugType(DebugType))
+ return cerr;
+ else
+ return cnoout;
+}
diff --git a/lib/Support/Dwarf.cpp b/lib/Support/Dwarf.cpp
new file mode 100644
index 0000000..572ba19
--- /dev/null
+++ b/lib/Support/Dwarf.cpp
@@ -0,0 +1,586 @@
+//===-- llvm/Support/Dwarf.cpp - Dwarf Framework ----------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by James M. Laskey and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for generic dwarf information.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Dwarf.h"
+#include "llvm/System/IncludeFile.h"
+
+#include <cassert>
+
+namespace llvm {
+
+namespace dwarf {
+
+/// TagString - Return the string for the specified tag.
+///
+const char *TagString(unsigned Tag) {
+ switch(Tag) {
+ case DW_TAG_array_type: return "TAG_array_type";
+ case DW_TAG_class_type: return "TAG_class_type";
+ case DW_TAG_entry_point: return "TAG_entry_point";
+ case DW_TAG_enumeration_type: return "TAG_enumeration_type";
+ case DW_TAG_formal_parameter: return "TAG_formal_parameter";
+ case DW_TAG_imported_declaration: return "TAG_imported_declaration";
+ case DW_TAG_label: return "TAG_label";
+ case DW_TAG_lexical_block: return "TAG_lexical_block";
+ case DW_TAG_member: return "TAG_member";
+ case DW_TAG_pointer_type: return "TAG_pointer_type";
+ case DW_TAG_reference_type: return "TAG_reference_type";
+ case DW_TAG_compile_unit: return "TAG_compile_unit";
+ case DW_TAG_string_type: return "TAG_string_type";
+ case DW_TAG_structure_type: return "TAG_structure_type";
+ case DW_TAG_subroutine_type: return "TAG_subroutine_type";
+ case DW_TAG_typedef: return "TAG_typedef";
+ case DW_TAG_union_type: return "TAG_union_type";
+ case DW_TAG_unspecified_parameters: return "TAG_unspecified_parameters";
+ case DW_TAG_variant: return "TAG_variant";
+ case DW_TAG_common_block: return "TAG_common_block";
+ case DW_TAG_common_inclusion: return "TAG_common_inclusion";
+ case DW_TAG_inheritance: return "TAG_inheritance";
+ case DW_TAG_inlined_subroutine: return "TAG_inlined_subroutine";
+ case DW_TAG_module: return "TAG_module";
+ case DW_TAG_ptr_to_member_type: return "TAG_ptr_to_member_type";
+ case DW_TAG_set_type: return "TAG_set_type";
+ case DW_TAG_subrange_type: return "TAG_subrange_type";
+ case DW_TAG_with_stmt: return "TAG_with_stmt";
+ case DW_TAG_access_declaration: return "TAG_access_declaration";
+ case DW_TAG_base_type: return "TAG_base_type";
+ case DW_TAG_catch_block: return "TAG_catch_block";
+ case DW_TAG_const_type: return "TAG_const_type";
+ case DW_TAG_constant: return "TAG_constant";
+ case DW_TAG_enumerator: return "TAG_enumerator";
+ case DW_TAG_file_type: return "TAG_file_type";
+ case DW_TAG_friend: return "TAG_friend";
+ case DW_TAG_namelist: return "TAG_namelist";
+ case DW_TAG_namelist_item: return "TAG_namelist_item";
+ case DW_TAG_packed_type: return "TAG_packed_type";
+ case DW_TAG_subprogram: return "TAG_subprogram";
+ case DW_TAG_template_type_parameter: return "TAG_template_type_parameter";
+ case DW_TAG_template_value_parameter: return "TAG_template_value_parameter";
+ case DW_TAG_thrown_type: return "TAG_thrown_type";
+ case DW_TAG_try_block: return "TAG_try_block";
+ case DW_TAG_variant_part: return "TAG_variant_part";
+ case DW_TAG_variable: return "TAG_variable";
+ case DW_TAG_volatile_type: return "TAG_volatile_type";
+ case DW_TAG_dwarf_procedure: return "TAG_dwarf_procedure";
+ case DW_TAG_restrict_type: return "TAG_restrict_type";
+ case DW_TAG_interface_type: return "TAG_interface_type";
+ case DW_TAG_namespace: return "TAG_namespace";
+ case DW_TAG_imported_module: return "TAG_imported_module";
+ case DW_TAG_unspecified_type: return "TAG_unspecified_type";
+ case DW_TAG_partial_unit: return "TAG_partial_unit";
+ case DW_TAG_imported_unit: return "TAG_imported_unit";
+ case DW_TAG_condition: return "TAG_condition";
+ case DW_TAG_shared_type: return "TAG_shared_type";
+ case DW_TAG_lo_user: return "TAG_lo_user";
+ case DW_TAG_hi_user: return "TAG_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Tag");
+ return "";
+}
+
+/// ChildrenString - Return the string for the specified children flag.
+///
+const char *ChildrenString(unsigned Children) {
+ switch(Children) {
+ case DW_CHILDREN_no: return "CHILDREN_no";
+ case DW_CHILDREN_yes: return "CHILDREN_yes";
+ }
+ assert(0 && "Unknown Dwarf ChildrenFlag");
+ return "";
+}
+
+/// AttributeString - Return the string for the specified attribute.
+///
+const char *AttributeString(unsigned Attribute) {
+ switch(Attribute) {
+ case DW_AT_sibling: return "AT_sibling";
+ case DW_AT_location: return "AT_location";
+ case DW_AT_name: return "AT_name";
+ case DW_AT_ordering: return "AT_ordering";
+ case DW_AT_byte_size: return "AT_byte_size";
+ case DW_AT_bit_offset: return "AT_bit_offset";
+ case DW_AT_bit_size: return "AT_bit_size";
+ case DW_AT_stmt_list: return "AT_stmt_list";
+ case DW_AT_low_pc: return "AT_low_pc";
+ case DW_AT_high_pc: return "AT_high_pc";
+ case DW_AT_language: return "AT_language";
+ case DW_AT_discr: return "AT_discr";
+ case DW_AT_discr_value: return "AT_discr_value";
+ case DW_AT_visibility: return "AT_visibility";
+ case DW_AT_import: return "AT_import";
+ case DW_AT_string_length: return "AT_string_length";
+ case DW_AT_common_reference: return "AT_common_reference";
+ case DW_AT_comp_dir: return "AT_comp_dir";
+ case DW_AT_const_value: return "AT_const_value";
+ case DW_AT_containing_type: return "AT_containing_type";
+ case DW_AT_default_value: return "AT_default_value";
+ case DW_AT_inline: return "AT_inline";
+ case DW_AT_is_optional: return "AT_is_optional";
+ case DW_AT_lower_bound: return "AT_lower_bound";
+ case DW_AT_producer: return "AT_producer";
+ case DW_AT_prototyped: return "AT_prototyped";
+ case DW_AT_return_addr: return "AT_return_addr";
+ case DW_AT_start_scope: return "AT_start_scope";
+ case DW_AT_bit_stride: return "AT_bit_stride";
+ case DW_AT_upper_bound: return "AT_upper_bound";
+ case DW_AT_abstract_origin: return "AT_abstract_origin";
+ case DW_AT_accessibility: return "AT_accessibility";
+ case DW_AT_address_class: return "AT_address_class";
+ case DW_AT_artificial: return "AT_artificial";
+ case DW_AT_base_types: return "AT_base_types";
+ case DW_AT_calling_convention: return "AT_calling_convention";
+ case DW_AT_count: return "AT_count";
+ case DW_AT_data_member_location: return "AT_data_member_location";
+ case DW_AT_decl_column: return "AT_decl_column";
+ case DW_AT_decl_file: return "AT_decl_file";
+ case DW_AT_decl_line: return "AT_decl_line";
+ case DW_AT_declaration: return "AT_declaration";
+ case DW_AT_discr_list: return "AT_discr_list";
+ case DW_AT_encoding: return "AT_encoding";
+ case DW_AT_external: return "AT_external";
+ case DW_AT_frame_base: return "AT_frame_base";
+ case DW_AT_friend: return "AT_friend";
+ case DW_AT_identifier_case: return "AT_identifier_case";
+ case DW_AT_macro_info: return "AT_macro_info";
+ case DW_AT_namelist_item: return "AT_namelist_item";
+ case DW_AT_priority: return "AT_priority";
+ case DW_AT_segment: return "AT_segment";
+ case DW_AT_specification: return "AT_specification";
+ case DW_AT_static_link: return "AT_static_link";
+ case DW_AT_type: return "AT_type";
+ case DW_AT_use_location: return "AT_use_location";
+ case DW_AT_variable_parameter: return "AT_variable_parameter";
+ case DW_AT_virtuality: return "AT_virtuality";
+ case DW_AT_vtable_elem_location: return "AT_vtable_elem_location";
+ case DW_AT_allocated: return "AT_allocated";
+ case DW_AT_associated: return "AT_associated";
+ case DW_AT_data_location: return "AT_data_location";
+ case DW_AT_byte_stride: return "AT_byte_stride";
+ case DW_AT_entry_pc: return "AT_entry_pc";
+ case DW_AT_use_UTF8: return "AT_use_UTF8";
+ case DW_AT_extension: return "AT_extension";
+ case DW_AT_ranges: return "AT_ranges";
+ case DW_AT_trampoline: return "AT_trampoline";
+ case DW_AT_call_column: return "AT_call_column";
+ case DW_AT_call_file: return "AT_call_file";
+ case DW_AT_call_line: return "AT_call_line";
+ case DW_AT_description: return "AT_description";
+ case DW_AT_binary_scale: return "AT_binary_scale";
+ case DW_AT_decimal_scale: return "AT_decimal_scale";
+ case DW_AT_small: return "AT_small";
+ case DW_AT_decimal_sign: return "AT_decimal_sign";
+ case DW_AT_digit_count: return "AT_digit_count";
+ case DW_AT_picture_string: return "AT_picture_string";
+ case DW_AT_mutable: return "AT_mutable";
+ case DW_AT_threads_scaled: return "AT_threads_scaled";
+ case DW_AT_explicit: return "AT_explicit";
+ case DW_AT_object_pointer: return "AT_object_pointer";
+ case DW_AT_endianity: return "AT_endianity";
+ case DW_AT_elemental: return "AT_elemental";
+ case DW_AT_pure: return "AT_pure";
+ case DW_AT_recursive: return "AT_recursive";
+ case DW_AT_MIPS_linkage_name: return "AT_MIPS_linkage_name";
+ case DW_AT_sf_names: return "AT_sf_names";
+ case DW_AT_src_info: return "AT_src_info";
+ case DW_AT_mac_info: return "AT_mac_info";
+ case DW_AT_src_coords: return "AT_src_coords";
+ case DW_AT_body_begin: return "AT_body_begin";
+ case DW_AT_body_end: return "AT_body_end";
+ case DW_AT_GNU_vector: return "AT_GNU_vector";
+ case DW_AT_lo_user: return "AT_lo_user";
+ case DW_AT_hi_user: return "AT_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Attribute");
+ return "";
+}
+
+/// FormEncodingString - Return the string for the specified form encoding.
+///
+const char *FormEncodingString(unsigned Encoding) {
+ switch(Encoding) {
+ case DW_FORM_addr: return "FORM_addr";
+ case DW_FORM_block2: return "FORM_block2";
+ case DW_FORM_block4: return "FORM_block4";
+ case DW_FORM_data2: return "FORM_data2";
+ case DW_FORM_data4: return "FORM_data4";
+ case DW_FORM_data8: return "FORM_data8";
+ case DW_FORM_string: return "FORM_string";
+ case DW_FORM_block: return "FORM_block";
+ case DW_FORM_block1: return "FORM_block1";
+ case DW_FORM_data1: return "FORM_data1";
+ case DW_FORM_flag: return "FORM_flag";
+ case DW_FORM_sdata: return "FORM_sdata";
+ case DW_FORM_strp: return "FORM_strp";
+ case DW_FORM_udata: return "FORM_udata";
+ case DW_FORM_ref_addr: return "FORM_ref_addr";
+ case DW_FORM_ref1: return "FORM_ref1";
+ case DW_FORM_ref2: return "FORM_ref2";
+ case DW_FORM_ref4: return "FORM_ref4";
+ case DW_FORM_ref8: return "FORM_ref8";
+ case DW_FORM_ref_udata: return "FORM_ref_udata";
+ case DW_FORM_indirect: return "FORM_indirect";
+ }
+ assert(0 && "Unknown Dwarf Form Encoding");
+ return "";
+}
+
+/// OperationEncodingString - Return the string for the specified operation
+/// encoding.
+const char *OperationEncodingString(unsigned Encoding) {
+ switch(Encoding) {
+ case DW_OP_addr: return "OP_addr";
+ case DW_OP_deref: return "OP_deref";
+ case DW_OP_const1u: return "OP_const1u";
+ case DW_OP_const1s: return "OP_const1s";
+ case DW_OP_const2u: return "OP_const2u";
+ case DW_OP_const2s: return "OP_const2s";
+ case DW_OP_const4u: return "OP_const4u";
+ case DW_OP_const4s: return "OP_const4s";
+ case DW_OP_const8u: return "OP_const8u";
+ case DW_OP_const8s: return "OP_const8s";
+ case DW_OP_constu: return "OP_constu";
+ case DW_OP_consts: return "OP_consts";
+ case DW_OP_dup: return "OP_dup";
+ case DW_OP_drop: return "OP_drop";
+ case DW_OP_over: return "OP_over";
+ case DW_OP_pick: return "OP_pick";
+ case DW_OP_swap: return "OP_swap";
+ case DW_OP_rot: return "OP_rot";
+ case DW_OP_xderef: return "OP_xderef";
+ case DW_OP_abs: return "OP_abs";
+ case DW_OP_and: return "OP_and";
+ case DW_OP_div: return "OP_div";
+ case DW_OP_minus: return "OP_minus";
+ case DW_OP_mod: return "OP_mod";
+ case DW_OP_mul: return "OP_mul";
+ case DW_OP_neg: return "OP_neg";
+ case DW_OP_not: return "OP_not";
+ case DW_OP_or: return "OP_or";
+ case DW_OP_plus: return "OP_plus";
+ case DW_OP_plus_uconst: return "OP_plus_uconst";
+ case DW_OP_shl: return "OP_shl";
+ case DW_OP_shr: return "OP_shr";
+ case DW_OP_shra: return "OP_shra";
+ case DW_OP_xor: return "OP_xor";
+ case DW_OP_skip: return "OP_skip";
+ case DW_OP_bra: return "OP_bra";
+ case DW_OP_eq: return "OP_eq";
+ case DW_OP_ge: return "OP_ge";
+ case DW_OP_gt: return "OP_gt";
+ case DW_OP_le: return "OP_le";
+ case DW_OP_lt: return "OP_lt";
+ case DW_OP_ne: return "OP_ne";
+ case DW_OP_lit0: return "OP_lit0";
+ case DW_OP_lit1: return "OP_lit1";
+ case DW_OP_lit31: return "OP_lit31";
+ case DW_OP_reg0: return "OP_reg0";
+ case DW_OP_reg1: return "OP_reg1";
+ case DW_OP_reg31: return "OP_reg31";
+ case DW_OP_breg0: return "OP_breg0";
+ case DW_OP_breg1: return "OP_breg1";
+ case DW_OP_breg31: return "OP_breg31";
+ case DW_OP_regx: return "OP_regx";
+ case DW_OP_fbreg: return "OP_fbreg";
+ case DW_OP_bregx: return "OP_bregx";
+ case DW_OP_piece: return "OP_piece";
+ case DW_OP_deref_size: return "OP_deref_size";
+ case DW_OP_xderef_size: return "OP_xderef_size";
+ case DW_OP_nop: return "OP_nop";
+ case DW_OP_push_object_address: return "OP_push_object_address";
+ case DW_OP_call2: return "OP_call2";
+ case DW_OP_call4: return "OP_call4";
+ case DW_OP_call_ref: return "OP_call_ref";
+ case DW_OP_form_tls_address: return "OP_form_tls_address";
+ case DW_OP_call_frame_cfa: return "OP_call_frame_cfa";
+ case DW_OP_lo_user: return "OP_lo_user";
+ case DW_OP_hi_user: return "OP_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Operation Encoding");
+ return "";
+}
+
+/// AttributeEncodingString - Return the string for the specified attribute
+/// encoding.
+const char *AttributeEncodingString(unsigned Encoding) {
+ switch(Encoding) {
+ case DW_ATE_address: return "ATE_address";
+ case DW_ATE_boolean: return "ATE_boolean";
+ case DW_ATE_complex_float: return "ATE_complex_float";
+ case DW_ATE_float: return "ATE_float";
+ case DW_ATE_signed: return "ATE_signed";
+ case DW_ATE_signed_char: return "ATE_signed_char";
+ case DW_ATE_unsigned: return "ATE_unsigned";
+ case DW_ATE_unsigned_char: return "ATE_unsigned_char";
+ case DW_ATE_imaginary_float: return "ATE_imaginary_float";
+ case DW_ATE_packed_decimal: return "ATE_packed_decimal";
+ case DW_ATE_numeric_string: return "ATE_numeric_string";
+ case DW_ATE_edited: return "ATE_edited";
+ case DW_ATE_signed_fixed: return "ATE_signed_fixed";
+ case DW_ATE_unsigned_fixed: return "ATE_unsigned_fixed";
+ case DW_ATE_decimal_float: return "ATE_decimal_float";
+ case DW_ATE_lo_user: return "ATE_lo_user";
+ case DW_ATE_hi_user: return "ATE_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Attribute Encoding");
+ return "";
+}
+
+/// DecimalSignString - Return the string for the specified decimal sign
+/// attribute.
+const char *DecimalSignString(unsigned Sign) {
+ switch(Sign) {
+ case DW_DS_unsigned: return "DS_unsigned";
+ case DW_DS_leading_overpunch: return "DS_leading_overpunch";
+ case DW_DS_trailing_overpunch: return "DS_trailing_overpunch";
+ case DW_DS_leading_separate: return "DS_leading_separate";
+ case DW_DS_trailing_separate: return "DS_trailing_separate";
+ }
+ assert(0 && "Unknown Dwarf Decimal Sign Attribute");
+ return "";
+}
+
+/// EndianityString - Return the string for the specified endianity.
+///
+const char *EndianityString(unsigned Endian) {
+ switch(Endian) {
+ case DW_END_default: return "END_default";
+ case DW_END_big: return "END_big";
+ case DW_END_little: return "END_little";
+ case DW_END_lo_user: return "END_lo_user";
+ case DW_END_hi_user: return "END_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Endianity");
+ return "";
+}
+
+/// AccessibilityString - Return the string for the specified accessibility.
+///
+const char *AccessibilityString(unsigned Access) {
+ switch(Access) {
+ // Accessibility codes
+ case DW_ACCESS_public: return "ACCESS_public";
+ case DW_ACCESS_protected: return "ACCESS_protected";
+ case DW_ACCESS_private: return "ACCESS_private";
+ }
+ assert(0 && "Unknown Dwarf Accessibility");
+ return "";
+}
+
+/// VisibilityString - Return the string for the specified visibility.
+///
+const char *VisibilityString(unsigned Visibility) {
+ switch(Visibility) {
+ case DW_VIS_local: return "VIS_local";
+ case DW_VIS_exported: return "VIS_exported";
+ case DW_VIS_qualified: return "VIS_qualified";
+ }
+ assert(0 && "Unknown Dwarf Visibility");
+ return "";
+}
+
+/// VirtualityString - Return the string for the specified virtuality.
+///
+const char *VirtualityString(unsigned Virtuality) {
+ switch(Virtuality) {
+ case DW_VIRTUALITY_none: return "VIRTUALITY_none";
+ case DW_VIRTUALITY_virtual: return "VIRTUALITY_virtual";
+ case DW_VIRTUALITY_pure_virtual: return "VIRTUALITY_pure_virtual";
+ }
+ assert(0 && "Unknown Dwarf Virtuality");
+ return "";
+}
+
+/// LanguageString - Return the string for the specified language.
+///
+const char *LanguageString(unsigned Language) {
+ switch(Language) {
+ case DW_LANG_C89: return "LANG_C89";
+ case DW_LANG_C: return "LANG_C";
+ case DW_LANG_Ada83: return "LANG_Ada83";
+ case DW_LANG_C_plus_plus: return "LANG_C_plus_plus";
+ case DW_LANG_Cobol74: return "LANG_Cobol74";
+ case DW_LANG_Cobol85: return "LANG_Cobol85";
+ case DW_LANG_Fortran77: return "LANG_Fortran77";
+ case DW_LANG_Fortran90: return "LANG_Fortran90";
+ case DW_LANG_Pascal83: return "LANG_Pascal83";
+ case DW_LANG_Modula2: return "LANG_Modula2";
+ case DW_LANG_Java: return "LANG_Java";
+ case DW_LANG_C99: return "LANG_C99";
+ case DW_LANG_Ada95: return "LANG_Ada95";
+ case DW_LANG_Fortran95: return "LANG_Fortran95";
+ case DW_LANG_PLI: return "LANG_PLI";
+ case DW_LANG_ObjC: return "LANG_ObjC";
+ case DW_LANG_ObjC_plus_plus: return "LANG_ObjC_plus_plus";
+ case DW_LANG_UPC: return "LANG_UPC";
+ case DW_LANG_D: return "LANG_D";
+ case DW_LANG_lo_user: return "LANG_lo_user";
+ case DW_LANG_hi_user: return "LANG_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Language");
+ return "";
+}
+
+/// CaseString - Return the string for the specified identifier case.
+///
+const char *CaseString(unsigned Case) {
+ switch(Case) {
+ case DW_ID_case_sensitive: return "ID_case_sensitive";
+ case DW_ID_up_case: return "ID_up_case";
+ case DW_ID_down_case: return "ID_down_case";
+ case DW_ID_case_insensitive: return "ID_case_insensitive";
+ }
+ assert(0 && "Unknown Dwarf Identifier Case");
+ return "";
+}
+
+/// ConventionString - Return the string for the specified calling convention.
+///
+const char *ConventionString(unsigned Convention) {
+ switch(Convention) {
+ case DW_CC_normal: return "CC_normal";
+ case DW_CC_program: return "CC_program";
+ case DW_CC_nocall: return "CC_nocall";
+ case DW_CC_lo_user: return "CC_lo_user";
+ case DW_CC_hi_user: return "CC_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Calling Convention");
+ return "";
+}
+
+/// InlineCodeString - Return the string for the specified inline code.
+///
+const char *InlineCodeString(unsigned Code) {
+ switch(Code) {
+ case DW_INL_not_inlined: return "INL_not_inlined";
+ case DW_INL_inlined: return "INL_inlined";
+ case DW_INL_declared_not_inlined: return "INL_declared_not_inlined";
+ case DW_INL_declared_inlined: return "INL_declared_inlined";
+ }
+ assert(0 && "Unknown Dwarf Inline Code");
+ return "";
+}
+
+/// ArrayOrderString - Return the string for the specified array order.
+///
+const char *ArrayOrderString(unsigned Order) {
+ switch(Order) {
+ case DW_ORD_row_major: return "ORD_row_major";
+ case DW_ORD_col_major: return "ORD_col_major";
+ }
+ assert(0 && "Unknown Dwarf Array Order");
+ return "";
+}
+
+/// DiscriminantString - Return the string for the specified discriminant
+/// descriptor.
+const char *DiscriminantString(unsigned Discriminant) {
+ switch(Discriminant) {
+ case DW_DSC_label: return "DSC_label";
+ case DW_DSC_range: return "DSC_range";
+ }
+ assert(0 && "Unknown Dwarf Discriminant Descriptor");
+ return "";
+}
+
+/// LNStandardString - Return the string for the specified line number standard.
+///
+const char *LNStandardString(unsigned Standard) {
+ switch(Standard) {
+ case DW_LNS_copy: return "LNS_copy";
+ case DW_LNS_advance_pc: return "LNS_advance_pc";
+ case DW_LNS_advance_line: return "LNS_advance_line";
+ case DW_LNS_set_file: return "LNS_set_file";
+ case DW_LNS_set_column: return "LNS_set_column";
+ case DW_LNS_negate_stmt: return "LNS_negate_stmt";
+ case DW_LNS_set_basic_block: return "LNS_set_basic_block";
+ case DW_LNS_const_add_pc: return "LNS_const_add_pc";
+ case DW_LNS_fixed_advance_pc: return "LNS_fixed_advance_pc";
+ case DW_LNS_set_prologue_end: return "LNS_set_prologue_end";
+ case DW_LNS_set_epilogue_begin: return "LNS_set_epilogue_begin";
+ case DW_LNS_set_isa: return "LNS_set_isa";
+ }
+ assert(0 && "Unknown Dwarf Line Number Standard");
+ return "";
+}
+
+/// LNExtendedString - Return the string for the specified line number extended
+/// opcode encodings.
+const char *LNExtendedString(unsigned Encoding) {
+ switch(Encoding) {
+ // Line Number Extended Opcode Encodings
+ case DW_LNE_end_sequence: return "LNE_end_sequence";
+ case DW_LNE_set_address: return "LNE_set_address";
+ case DW_LNE_define_file: return "LNE_define_file";
+ case DW_LNE_lo_user: return "LNE_lo_user";
+ case DW_LNE_hi_user: return "LNE_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Line Number Extended Opcode Encoding");
+ return "";
+}
+
+/// MacinfoString - Return the string for the specified macinfo type encodings.
+///
+const char *MacinfoString(unsigned Encoding) {
+ switch(Encoding) {
+ // Macinfo Type Encodings
+ case DW_MACINFO_define: return "MACINFO_define";
+ case DW_MACINFO_undef: return "MACINFO_undef";
+ case DW_MACINFO_start_file: return "MACINFO_start_file";
+ case DW_MACINFO_end_file: return "MACINFO_end_file";
+ case DW_MACINFO_vendor_ext: return "MACINFO_vendor_ext";
+ }
+ assert(0 && "Unknown Dwarf Macinfo Type Encodings");
+ return "";
+}
+
+/// CallFrameString - Return the string for the specified call frame instruction
+/// encodings.
+const char *CallFrameString(unsigned Encoding) {
+ switch(Encoding) {
+ case DW_CFA_advance_loc: return "CFA_advance_loc";
+ case DW_CFA_offset: return "CFA_offset";
+ case DW_CFA_restore: return "CFA_restore";
+ case DW_CFA_set_loc: return "CFA_set_loc";
+ case DW_CFA_advance_loc1: return "CFA_advance_loc1";
+ case DW_CFA_advance_loc2: return "CFA_advance_loc2";
+ case DW_CFA_advance_loc4: return "CFA_advance_loc4";
+ case DW_CFA_offset_extended: return "CFA_offset_extended";
+ case DW_CFA_restore_extended: return "CFA_restore_extended";
+ case DW_CFA_undefined: return "CFA_undefined";
+ case DW_CFA_same_value: return "CFA_same_value";
+ case DW_CFA_register: return "CFA_register";
+ case DW_CFA_remember_state: return "CFA_remember_state";
+ case DW_CFA_restore_state: return "CFA_restore_state";
+ case DW_CFA_def_cfa: return "CFA_def_cfa";
+ case DW_CFA_def_cfa_register: return "CFA_def_cfa_register";
+ case DW_CFA_def_cfa_offset: return "CFA_def_cfa_offset";
+ case DW_CFA_def_cfa_expression: return "CFA_def_cfa_expression";
+ case DW_CFA_expression: return "CFA_expression";
+ case DW_CFA_offset_extended_sf: return "CFA_offset_extended_sf";
+ case DW_CFA_def_cfa_sf: return "CFA_def_cfa_sf";
+ case DW_CFA_def_cfa_offset_sf: return "CFA_def_cfa_offset_sf";
+ case DW_CFA_val_offset: return "CFA_val_offset";
+ case DW_CFA_val_offset_sf: return "CFA_val_offset_sf";
+ case DW_CFA_val_expression: return "CFA_val_expression";
+ case DW_CFA_lo_user: return "CFA_lo_user";
+ case DW_CFA_hi_user: return "CFA_hi_user";
+ }
+ assert(0 && "Unknown Dwarf Call Frame Instruction Encodings");
+ return "";
+}
+
+} // End of namespace dwarf.
+
+} // End of namespace llvm.
+
+DEFINING_FILE_FOR(SupportDwarf)
diff --git a/lib/Support/FileUtilities.cpp b/lib/Support/FileUtilities.cpp
new file mode 100644
index 0000000..1736b0d
--- /dev/null
+++ b/lib/Support/FileUtilities.cpp
@@ -0,0 +1,266 @@
+//===- Support/FileUtilities.cpp - File System Utilities ------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a family of utility functions which are useful for doing
+// various things with files.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/FileUtilities.h"
+#include "llvm/System/Path.h"
+#include "llvm/System/MappedFile.h"
+#include "llvm/ADT/StringExtras.h"
+#include <cstring>
+#include <cctype>
+using namespace llvm;
+
+static bool isNumberChar(char C) {
+ switch (C) {
+ case '0': case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ case '.': case '+': case '-':
+ case 'D': // Strange exponential notation.
+ case 'd': // Strange exponential notation.
+ case 'e':
+ case 'E': return true;
+ default: return false;
+ }
+}
+
+static char *BackupNumber(char *Pos, char *FirstChar) {
+ // If we didn't stop in the middle of a number, don't backup.
+ if (!isNumberChar(*Pos)) return Pos;
+
+ // Otherwise, return to the start of the number.
+ while (Pos > FirstChar && isNumberChar(Pos[-1]))
+ --Pos;
+ return Pos;
+}
+
+/// CompareNumbers - compare two numbers, returning true if they are different.
+static bool CompareNumbers(char *&F1P, char *&F2P, char *F1End, char *F2End,
+ double AbsTolerance, double RelTolerance,
+ std::string *ErrorMsg) {
+ char *F1NumEnd, *F2NumEnd;
+ double V1 = 0.0, V2 = 0.0;
+
+ // If one of the positions is at a space and the other isn't, chomp up 'til
+ // the end of the space.
+ while (isspace(*F1P) && F1P != F1End)
+ ++F1P;
+ while (isspace(*F2P) && F2P != F2End)
+ ++F2P;
+
+ // If we stop on numbers, compare their difference. Note that some ugliness
+ // is built into this to permit support for numbers that use "D" or "d" as
+ // their exponential marker, e.g. "1.234D45". This occurs in 200.sixtrack in
+ // spec2k.
+ if (isNumberChar(*F1P) && isNumberChar(*F2P)) {
+ bool isDNotation;
+ do {
+ isDNotation = false;
+ V1 = strtod(F1P, &F1NumEnd);
+ V2 = strtod(F2P, &F2NumEnd);
+
+ if (*F1NumEnd == 'D' || *F1NumEnd == 'd') {
+ *F1NumEnd = 'e'; // Strange exponential notation!
+ isDNotation = true;
+ }
+ if (*F2NumEnd == 'D' || *F2NumEnd == 'd') {
+ *F2NumEnd = 'e'; // Strange exponential notation!
+ isDNotation = true;
+ }
+ } while (isDNotation);
+ } else {
+ // Otherwise, the diff failed.
+ F1NumEnd = F1P;
+ F2NumEnd = F2P;
+ }
+
+ if (F1NumEnd == F1P || F2NumEnd == F2P) {
+ if (ErrorMsg) {
+ *ErrorMsg = "FP Comparison failed, not a numeric difference between '";
+ *ErrorMsg += F1P[0];
+ *ErrorMsg += "' and '";
+ *ErrorMsg += F2P[0];
+ *ErrorMsg += "'";
+ }
+ return true;
+ }
+
+ // Check to see if these are inside the absolute tolerance
+ if (AbsTolerance < std::abs(V1-V2)) {
+ // Nope, check the relative tolerance...
+ double Diff;
+ if (V2)
+ Diff = std::abs(V1/V2 - 1.0);
+ else if (V1)
+ Diff = std::abs(V2/V1 - 1.0);
+ else
+ Diff = 0; // Both zero.
+ if (Diff > RelTolerance) {
+ if (ErrorMsg) {
+ *ErrorMsg = "Compared: " + ftostr(V1) + " and " + ftostr(V2) + "\n";
+ *ErrorMsg += "abs. diff = " + ftostr(std::abs(V1-V2)) +
+ " rel.diff = " + ftostr(Diff) + "\n";
+ *ErrorMsg += "Out of tolerance: rel/abs: " + ftostr(RelTolerance) +
+ "/" + ftostr(AbsTolerance);
+ }
+ return true;
+ }
+ }
+
+ // Otherwise, advance our read pointers to the end of the numbers.
+ F1P = F1NumEnd; F2P = F2NumEnd;
+ return false;
+}
+
+// PadFileIfNeeded - If the files are not identical, we will have to be doing
+// numeric comparisons in here. There are bad cases involved where we (i.e.,
+// strtod) might run off the beginning or end of the file if it starts or ends
+// with a number. Because of this, if needed, we pad the file so that it starts
+// and ends with a null character.
+static void PadFileIfNeeded(char *&FileStart, char *&FileEnd, char *&FP) {
+ if (FileStart-FileEnd < 2 ||
+ isNumberChar(FileStart[0]) || isNumberChar(FileEnd[-1])) {
+ unsigned FileLen = FileEnd-FileStart;
+ char *NewFile = new char[FileLen+2];
+ NewFile[0] = 0; // Add null padding
+ NewFile[FileLen+1] = 0; // Add null padding
+ memcpy(NewFile+1, FileStart, FileLen);
+ FP = NewFile+(FP-FileStart)+1;
+ FileStart = NewFile+1;
+ FileEnd = FileStart+FileLen;
+ }
+}
+
+/// DiffFilesWithTolerance - Compare the two files specified, returning 0 if the
+/// files match, 1 if they are different, and 2 if there is a file error. This
+/// function differs from DiffFiles in that you can specify an absolete and
+/// relative FP error that is allowed to exist. If you specify a string to fill
+/// in for the error option, it will set the string to an error message if an
+/// error occurs, allowing the caller to distinguish between a failed diff and a
+/// file system error.
+///
+int llvm::DiffFilesWithTolerance(const sys::PathWithStatus &FileA,
+ const sys::PathWithStatus &FileB,
+ double AbsTol, double RelTol,
+ std::string *Error) {
+ const sys::FileStatus *FileAStat = FileA.getFileStatus(false, Error);
+ if (!FileAStat)
+ return 2;
+ const sys::FileStatus *FileBStat = FileB.getFileStatus(false, Error);
+ if (!FileBStat)
+ return 2;
+
+ // Check for zero length files because some systems croak when you try to
+ // mmap an empty file.
+ size_t A_size = FileAStat->getSize();
+ size_t B_size = FileBStat->getSize();
+
+ // If they are both zero sized then they're the same
+ if (A_size == 0 && B_size == 0)
+ return 0;
+
+ // If only one of them is zero sized then they can't be the same
+ if ((A_size == 0 || B_size == 0)) {
+ if (Error)
+ *Error = "Files differ: one is zero-sized, the other isn't";
+ return 1;
+ }
+
+ // Now its safe to mmap the files into memory becasue both files
+ // have a non-zero size.
+ sys::MappedFile F1;
+ if (F1.open(FileA, sys::MappedFile::READ_ACCESS, Error))
+ return 2;
+ sys::MappedFile F2;
+ if (F2.open(FileB, sys::MappedFile::READ_ACCESS, Error))
+ return 2;
+ if (!F1.map(Error))
+ return 2;
+ if (!F2.map(Error))
+ return 2;
+
+ // Okay, now that we opened the files, scan them for the first difference.
+ char *File1Start = F1.charBase();
+ char *File2Start = F2.charBase();
+ char *File1End = File1Start+A_size;
+ char *File2End = File2Start+B_size;
+ char *F1P = File1Start;
+ char *F2P = File2Start;
+
+ if (A_size == B_size) {
+ // Are the buffers identical?
+ if (std::memcmp(File1Start, File2Start, A_size) == 0)
+ return 0;
+
+ if (AbsTol == 0 && RelTol == 0) {
+ if (Error)
+ *Error = "Files differ without tolerance allowance";
+ return 1; // Files different!
+ }
+ }
+
+ char *OrigFile1Start = File1Start;
+ char *OrigFile2Start = File2Start;
+
+ // If the files need padding, do so now.
+ PadFileIfNeeded(File1Start, File1End, F1P);
+ PadFileIfNeeded(File2Start, File2End, F2P);
+
+ bool CompareFailed = false;
+ while (1) {
+ // Scan for the end of file or next difference.
+ while (F1P < File1End && F2P < File2End && *F1P == *F2P)
+ ++F1P, ++F2P;
+
+ if (F1P >= File1End || F2P >= File2End) break;
+
+ // Okay, we must have found a difference. Backup to the start of the
+ // current number each stream is at so that we can compare from the
+ // beginning.
+ F1P = BackupNumber(F1P, File1Start);
+ F2P = BackupNumber(F2P, File2Start);
+
+ // Now that we are at the start of the numbers, compare them, exiting if
+ // they don't match.
+ if (CompareNumbers(F1P, F2P, File1End, File2End, AbsTol, RelTol, Error)) {
+ CompareFailed = true;
+ break;
+ }
+ }
+
+ // Okay, we reached the end of file. If both files are at the end, we
+ // succeeded.
+ bool F1AtEnd = F1P >= File1End;
+ bool F2AtEnd = F2P >= File2End;
+ if (!CompareFailed && (!F1AtEnd || !F2AtEnd)) {
+ // Else, we might have run off the end due to a number: backup and retry.
+ if (F1AtEnd && isNumberChar(F1P[-1])) --F1P;
+ if (F2AtEnd && isNumberChar(F2P[-1])) --F2P;
+ F1P = BackupNumber(F1P, File1Start);
+ F2P = BackupNumber(F2P, File2Start);
+
+ // Now that we are at the start of the numbers, compare them, exiting if
+ // they don't match.
+ if (CompareNumbers(F1P, F2P, File1End, File2End, AbsTol, RelTol, Error))
+ CompareFailed = true;
+
+ // If we found the end, we succeeded.
+ if (F1P < File1End || F2P < File2End)
+ CompareFailed = true;
+ }
+
+ if (OrigFile1Start != File1Start)
+ delete[] (File1Start-1); // Back up past null byte
+ if (OrigFile2Start != File2Start)
+ delete[] (File2Start-1); // Back up past null byte
+ return CompareFailed;
+}
diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp
new file mode 100644
index 0000000..6f7f5ea
--- /dev/null
+++ b/lib/Support/FoldingSet.cpp
@@ -0,0 +1,307 @@
+//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by James M. Laskey and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a hash set that can be used to remove duplication of
+// nodes in a graph. This code was originally created by Chris Lattner for use
+// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code
+// set.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/MathExtras.h"
+#include <cassert>
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// FoldingSetImpl::NodeID Implementation
+
+/// Add* - Add various data types to Bit data.
+///
+void FoldingSetImpl::NodeID::AddPointer(const void *Ptr) {
+ // Note: this adds pointers to the hash using sizes and endianness that
+ // depend on the host. It doesn't matter however, because hashing on
+ // pointer values in inherently unstable. Nothing should depend on the
+ // ordering of nodes in the folding set.
+ intptr_t PtrI = (intptr_t)Ptr;
+ Bits.push_back(unsigned(PtrI));
+ if (sizeof(intptr_t) > sizeof(unsigned))
+ Bits.push_back(unsigned(uint64_t(PtrI) >> 32));
+}
+void FoldingSetImpl::NodeID::AddInteger(signed I) {
+ Bits.push_back(I);
+}
+void FoldingSetImpl::NodeID::AddInteger(unsigned I) {
+ Bits.push_back(I);
+}
+void FoldingSetImpl::NodeID::AddInteger(uint64_t I) {
+ Bits.push_back(unsigned(I));
+
+ // If the integer is small, encode it just as 32-bits.
+ if ((uint64_t)(int)I != I)
+ Bits.push_back(unsigned(I >> 32));
+}
+void FoldingSetImpl::NodeID::AddFloat(float F) {
+ Bits.push_back(FloatToBits(F));
+}
+void FoldingSetImpl::NodeID::AddDouble(double D) {
+ AddInteger(DoubleToBits(D));
+}
+void FoldingSetImpl::NodeID::AddString(const std::string &String) {
+ unsigned Size = String.size();
+ Bits.push_back(Size);
+ if (!Size) return;
+
+ unsigned Units = Size / 4;
+ unsigned Pos = 0;
+ const unsigned *Base = (const unsigned *)String.data();
+
+ // If the string is aligned do a bulk transfer.
+ if (!((intptr_t)Base & 3)) {
+ Bits.append(Base, Base + Units);
+ Pos = (Units + 1) * 4;
+ } else {
+ // Otherwise do it the hard way.
+ for ( Pos += 4; Pos <= Size; Pos += 4) {
+ unsigned V = ((unsigned char)String[Pos - 4] << 24) |
+ ((unsigned char)String[Pos - 3] << 16) |
+ ((unsigned char)String[Pos - 2] << 8) |
+ (unsigned char)String[Pos - 1];
+ Bits.push_back(V);
+ }
+ }
+
+ // With the leftover bits.
+ unsigned V = 0;
+ // Pos will have overshot size by 4 - #bytes left over.
+ switch (Pos - Size) {
+ case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru.
+ case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru.
+ case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
+ default: return; // Nothing left.
+ }
+
+ Bits.push_back(V);
+}
+
+/// ComputeHash - Compute a strong hash value for this NodeID, used to
+/// lookup the node in the FoldingSetImpl.
+unsigned FoldingSetImpl::NodeID::ComputeHash() const {
+ // This is adapted from SuperFastHash by Paul Hsieh.
+ unsigned Hash = Bits.size();
+ for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) {
+ unsigned Data = *BP;
+ Hash += Data & 0xFFFF;
+ unsigned Tmp = ((Data >> 16) << 11) ^ Hash;
+ Hash = (Hash << 16) ^ Tmp;
+ Hash += Hash >> 11;
+ }
+
+ // Force "avalanching" of final 127 bits.
+ Hash ^= Hash << 3;
+ Hash += Hash >> 5;
+ Hash ^= Hash << 4;
+ Hash += Hash >> 17;
+ Hash ^= Hash << 25;
+ Hash += Hash >> 6;
+ return Hash;
+}
+
+/// operator== - Used to compare two nodes to each other.
+///
+bool FoldingSetImpl::NodeID::operator==(const FoldingSetImpl::NodeID &RHS)const{
+ if (Bits.size() != RHS.Bits.size()) return false;
+ return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0;
+}
+
+
+//===----------------------------------------------------------------------===//
+/// Helper functions for FoldingSetImpl.
+
+/// GetNextPtr - In order to save space, each bucket is a
+/// singly-linked-list. In order to make deletion more efficient, we make
+/// the list circular, so we can delete a node without computing its hash.
+/// The problem with this is that the start of the hash buckets are not
+/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null:
+/// use GetBucketPtr when this happens.
+static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr,
+ void **Buckets, unsigned NumBuckets) {
+ if (NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets + NumBuckets)
+ return 0;
+ return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
+}
+
+/// GetBucketPtr - Provides a casting of a bucket pointer for isNode
+/// testing.
+static void **GetBucketPtr(void *NextInBucketPtr) {
+ return static_cast<void**>(NextInBucketPtr);
+}
+
+/// GetBucketFor - Hash the specified node ID and return the hash bucket for
+/// the specified ID.
+static void **GetBucketFor(const FoldingSetImpl::NodeID &ID,
+ void **Buckets, unsigned NumBuckets) {
+ // NumBuckets is always a power of 2.
+ unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
+ return Buckets + BucketNum;
+}
+
+//===----------------------------------------------------------------------===//
+// FoldingSetImpl Implementation
+
+FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) : NumNodes(0) {
+ assert(5 < Log2InitSize && Log2InitSize < 32 &&
+ "Initial hash table size out of range");
+ NumBuckets = 1 << Log2InitSize;
+ Buckets = new void*[NumBuckets];
+ memset(Buckets, 0, NumBuckets*sizeof(void*));
+}
+FoldingSetImpl::~FoldingSetImpl() {
+ delete [] Buckets;
+}
+
+/// GrowHashTable - Double the size of the hash table and rehash everything.
+///
+void FoldingSetImpl::GrowHashTable() {
+ void **OldBuckets = Buckets;
+ unsigned OldNumBuckets = NumBuckets;
+ NumBuckets <<= 1;
+
+ // Reset the node count to zero: we're going to reinsert everything.
+ NumNodes = 0;
+
+ // Clear out new buckets.
+ Buckets = new void*[NumBuckets];
+ memset(Buckets, 0, NumBuckets*sizeof(void*));
+
+ // Walk the old buckets, rehashing nodes into their new place.
+ for (unsigned i = 0; i != OldNumBuckets; ++i) {
+ void *Probe = OldBuckets[i];
+ if (!Probe) continue;
+ while (Node *NodeInBucket = GetNextPtr(Probe, OldBuckets, OldNumBuckets)) {
+ // Figure out the next link, remove NodeInBucket from the old link.
+ Probe = NodeInBucket->getNextInBucket();
+ NodeInBucket->SetNextInBucket(0);
+
+ // Insert the node into the new bucket, after recomputing the hash.
+ NodeID ID;
+ GetNodeProfile(ID, NodeInBucket);
+ InsertNode(NodeInBucket, GetBucketFor(ID, Buckets, NumBuckets));
+ }
+ }
+
+ delete[] OldBuckets;
+}
+
+/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
+/// return it. If not, return the insertion token that will make insertion
+/// faster.
+FoldingSetImpl::Node *FoldingSetImpl::FindNodeOrInsertPos(const NodeID &ID,
+ void *&InsertPos) {
+ void **Bucket = GetBucketFor(ID, Buckets, NumBuckets);
+ void *Probe = *Bucket;
+
+ InsertPos = 0;
+
+ while (Node *NodeInBucket = GetNextPtr(Probe, Buckets, NumBuckets)) {
+ NodeID OtherID;
+ GetNodeProfile(OtherID, NodeInBucket);
+ if (OtherID == ID)
+ return NodeInBucket;
+
+ Probe = NodeInBucket->getNextInBucket();
+ }
+
+ // Didn't find the node, return null with the bucket as the InsertPos.
+ InsertPos = Bucket;
+ return 0;
+}
+
+/// InsertNode - Insert the specified node into the folding set, knowing that it
+/// is not already in the map. InsertPos must be obtained from
+/// FindNodeOrInsertPos.
+void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
+ assert(N->getNextInBucket() == 0);
+ // Do we need to grow the hashtable?
+ if (NumNodes+1 > NumBuckets*2) {
+ GrowHashTable();
+ NodeID ID;
+ GetNodeProfile(ID, N);
+ InsertPos = GetBucketFor(ID, Buckets, NumBuckets);
+ }
+
+ ++NumNodes;
+
+ /// The insert position is actually a bucket pointer.
+ void **Bucket = static_cast<void**>(InsertPos);
+
+ void *Next = *Bucket;
+
+ // If this is the first insertion into this bucket, its next pointer will be
+ // null. Pretend as if it pointed to itself.
+ if (Next == 0)
+ Next = Bucket;
+
+ // Set the node's next pointer, and make the bucket point to the node.
+ N->SetNextInBucket(Next);
+ *Bucket = N;
+}
+
+/// RemoveNode - Remove a node from the folding set, returning true if one was
+/// removed or false if the node was not in the folding set.
+bool FoldingSetImpl::RemoveNode(Node *N) {
+ // Because each bucket is a circular list, we don't need to compute N's hash
+ // to remove it.
+ void *Ptr = N->getNextInBucket();
+ if (Ptr == 0) return false; // Not in folding set.
+
+ --NumNodes;
+ N->SetNextInBucket(0);
+
+ // Remember what N originally pointed to, either a bucket or another node.
+ void *NodeNextPtr = Ptr;
+
+ // Chase around the list until we find the node (or bucket) which points to N.
+ while (true) {
+ if (Node *NodeInBucket = GetNextPtr(Ptr, Buckets, NumBuckets)) {
+ // Advance pointer.
+ Ptr = NodeInBucket->getNextInBucket();
+
+ // We found a node that points to N, change it to point to N's next node,
+ // removing N from the list.
+ if (Ptr == N) {
+ NodeInBucket->SetNextInBucket(NodeNextPtr);
+ return true;
+ }
+ } else {
+ void **Bucket = GetBucketPtr(Ptr);
+ Ptr = *Bucket;
+
+ // If we found that the bucket points to N, update the bucket to point to
+ // whatever is next.
+ if (Ptr == N) {
+ *Bucket = NodeNextPtr;
+ return true;
+ }
+ }
+ }
+}
+
+/// GetOrInsertNode - If there is an existing simple Node exactly
+/// equal to the specified node, return it. Otherwise, insert 'N' and it
+/// instead.
+FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
+ NodeID ID;
+ GetNodeProfile(ID, N);
+ void *IP;
+ if (Node *E = FindNodeOrInsertPos(ID, IP))
+ return E;
+ InsertNode(N, IP);
+ return N;
+}
diff --git a/lib/Support/GraphWriter.cpp b/lib/Support/GraphWriter.cpp
new file mode 100644
index 0000000..eab76df
--- /dev/null
+++ b/lib/Support/GraphWriter.cpp
@@ -0,0 +1,88 @@
+//===-- GraphWriter.cpp - Implements GraphWriter support routines ---------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements misc. GraphWriter support routines.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/System/Path.h"
+#include "llvm/System/Program.h"
+#include "llvm/Config/config.h"
+using namespace llvm;
+
+void llvm::DisplayGraph(const sys::Path &Filename) {
+ std::string ErrMsg;
+#if HAVE_GRAPHVIZ
+ sys::Path Graphviz(LLVM_PATH_GRAPHVIZ);
+
+ std::vector<const char*> args;
+ args.push_back(Graphviz.c_str());
+ args.push_back(Filename.c_str());
+ args.push_back(0);
+
+ cerr << "Running 'Graphviz' program... " << std::flush;
+ if (sys::Program::ExecuteAndWait(Graphviz, &args[0],0,0,0,0,&ErrMsg)) {
+ cerr << "Error viewing graph: " << ErrMsg << "\n";
+ }
+#elif (HAVE_GV && HAVE_DOT)
+ sys::Path PSFilename = Filename;
+ PSFilename.appendSuffix("ps");
+
+ sys::Path dot(LLVM_PATH_DOT);
+
+ std::vector<const char*> args;
+ args.push_back(dot.c_str());
+ args.push_back("-Tps");
+ args.push_back("-Nfontname=Courier");
+ args.push_back("-Gsize=7.5,10");
+ args.push_back(Filename.c_str());
+ args.push_back("-o");
+ args.push_back(PSFilename.c_str());
+ args.push_back(0);
+
+ cerr << "Running 'dot' program... " << std::flush;
+ if (sys::Program::ExecuteAndWait(dot, &args[0],0,0,0,0,&ErrMsg)) {
+ cerr << "Error viewing graph: '" << ErrMsg << "\n";
+ } else {
+ cerr << " done. \n";
+
+ sys::Path gv(LLVM_PATH_GV);
+ args.clear();
+ args.push_back(gv.c_str());
+ args.push_back(PSFilename.c_str());
+ args.push_back(0);
+
+ ErrMsg.clear();
+ if (sys::Program::ExecuteAndWait(gv, &args[0],0,0,0,0,&ErrMsg)) {
+ cerr << "Error viewing graph: " << ErrMsg << "\n";
+ }
+ }
+ PSFilename.eraseFromDisk();
+#elif HAVE_DOTTY
+ sys::Path dotty(LLVM_PATH_DOTTY);
+
+ std::vector<const char*> args;
+ args.push_back(dotty.c_str());
+ args.push_back(Filename.c_str());
+ args.push_back(0);
+
+ cerr << "Running 'dotty' program... " << std::flush;
+ if (sys::Program::ExecuteAndWait(dotty, &args[0],0,0,0,0,&ErrMsg)) {
+ cerr << "Error viewing graph: " << ErrMsg << "\n";
+ } else {
+#ifdef __MINGW32__ // Dotty spawns another app and doesn't wait until it returns
+ return;
+#endif
+ }
+#endif
+
+ Filename.eraseFromDisk();
+}
diff --git a/lib/Support/IsInf.cpp b/lib/Support/IsInf.cpp
new file mode 100644
index 0000000..52c7d42
--- /dev/null
+++ b/lib/Support/IsInf.cpp
@@ -0,0 +1,49 @@
+//===-- IsInf.cpp - Platform-independent wrapper around C99 isinf() -------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Platform-independent wrapper around C99 isinf()
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Config/config.h"
+
+#if HAVE_ISINF_IN_MATH_H
+# include <math.h>
+#elif HAVE_ISINF_IN_CMATH
+# include <cmath>
+#elif HAVE_STD_ISINF_IN_CMATH
+# include <cmath>
+using std::isinf;
+#elif HAVE_FINITE_IN_IEEEFP_H
+// A handy workaround I found at http://www.unixguide.net/sun/faq ...
+// apparently this has been a problem with Solaris for years.
+# include <ieeefp.h>
+static int isinf(double x) { return !finite(x) && x==x; }
+#elif defined(_MSC_VER)
+#include <float.h>
+#define isinf(X) (!_finite(X))
+#elif defined(_AIX) && defined(__GNUC__)
+// GCC's fixincludes seems to be removing the isinf() declaration from the
+// system header /usr/include/math.h
+# include <math.h>
+static int isinf(double x) { return !finite(x) && x==x; }
+#elif defined(__hpux)
+// HP-UX is "special"
+#include <math.h>
+static int isinf(double x) { return ((x) == INFINITY) || ((x) == -INFINITY); }
+#else
+# error "Don't know how to get isinf()"
+#endif
+
+namespace llvm {
+
+int IsInf(float f) { return isinf(f); }
+int IsInf(double d) { return isinf(d); }
+
+} // end namespace llvm;
diff --git a/lib/Support/IsNAN.cpp b/lib/Support/IsNAN.cpp
new file mode 100644
index 0000000..4e6c849
--- /dev/null
+++ b/lib/Support/IsNAN.cpp
@@ -0,0 +1,33 @@
+//===-- IsNAN.cpp ---------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Platform-independent wrapper around C99 isnan().
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Config/config.h"
+
+#if HAVE_ISNAN_IN_MATH_H
+# include <math.h>
+#elif HAVE_ISNAN_IN_CMATH
+# include <cmath>
+#elif HAVE_STD_ISNAN_IN_CMATH
+# include <cmath>
+using std::isnan;
+#elif defined(_MSC_VER)
+#include <float.h>
+#define isnan _isnan
+#else
+# error "Don't know how to get isnan()"
+#endif
+
+namespace llvm {
+ int IsNAN(float f) { return isnan(f); }
+ int IsNAN(double d) { return isnan(d); }
+} // end namespace llvm;
diff --git a/lib/Support/Makefile b/lib/Support/Makefile
new file mode 100644
index 0000000..af2776c
--- /dev/null
+++ b/lib/Support/Makefile
@@ -0,0 +1,14 @@
+##===- lib/Support/Makefile ------------------------------*- Makefile -*-===##
+#
+# The LLVM Compiler Infrastructure
+#
+# This file was developed by the LLVM research group and is distributed under
+# the University of Illinois Open Source License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+LIBRARYNAME = LLVMSupport
+BUILD_ARCHIVE = 1
+
+include $(LEVEL)/Makefile.common
diff --git a/lib/Support/ManagedStatic.cpp b/lib/Support/ManagedStatic.cpp
new file mode 100644
index 0000000..8de8ecd
--- /dev/null
+++ b/lib/Support/ManagedStatic.cpp
@@ -0,0 +1,53 @@
+//===-- ManagedStatic.cpp - Static Global wrapper -------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the ManagedStatic class and llvm_shutdown().
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/ManagedStatic.h"
+#include <cassert>
+using namespace llvm;
+
+static const ManagedStaticBase *StaticList = 0;
+
+void ManagedStaticBase::RegisterManagedStatic(void *ObjPtr,
+ void (*Deleter)(void*)) const {
+ assert(Ptr == 0 && DeleterFn == 0 && Next == 0 &&
+ "Partially init static?");
+ Ptr = ObjPtr;
+ DeleterFn = Deleter;
+
+ // Add to list of managed statics.
+ Next = StaticList;
+ StaticList = this;
+}
+
+void ManagedStaticBase::destroy() const {
+ assert(DeleterFn && "ManagedStatic not initialized correctly!");
+ assert(StaticList == this &&
+ "Not destroyed in reverse order of construction?");
+ // Unlink from list.
+ StaticList = Next;
+ Next = 0;
+
+ // Destroy memory.
+ DeleterFn(Ptr);
+
+ // Cleanup.
+ Ptr = 0;
+ DeleterFn = 0;
+}
+
+/// llvm_shutdown - Deallocate and destroy all ManagedStatic variables.
+void llvm::llvm_shutdown() {
+ while (StaticList)
+ StaticList->destroy();
+}
+
diff --git a/lib/Support/MemoryBuffer.cpp b/lib/Support/MemoryBuffer.cpp
new file mode 100644
index 0000000..43eb181
--- /dev/null
+++ b/lib/Support/MemoryBuffer.cpp
@@ -0,0 +1,259 @@
+//===--- MemoryBuffer.cpp - Memory Buffer implementation ------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the MemoryBuffer interface.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/System/MappedFile.h"
+#include "llvm/System/Process.h"
+#include "llvm/System/Program.h"
+#include <cassert>
+#include <cstdio>
+#include <cstring>
+#include <cerrno>
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// MemoryBuffer implementation itself.
+//===----------------------------------------------------------------------===//
+
+MemoryBuffer::~MemoryBuffer() {
+ if (MustDeleteBuffer)
+ delete [] BufferStart;
+}
+
+/// initCopyOf - Initialize this source buffer with a copy of the specified
+/// memory range. We make the copy so that we can null terminate it
+/// successfully.
+void MemoryBuffer::initCopyOf(const char *BufStart, const char *BufEnd) {
+ size_t Size = BufEnd-BufStart;
+ BufferStart = new char[Size+1];
+ BufferEnd = BufferStart+Size;
+ memcpy(const_cast<char*>(BufferStart), BufStart, Size);
+ *const_cast<char*>(BufferEnd) = 0; // Null terminate buffer.
+ MustDeleteBuffer = true;
+}
+
+/// init - Initialize this MemoryBuffer as a reference to externally allocated
+/// memory, memory that we know is already null terminated.
+void MemoryBuffer::init(const char *BufStart, const char *BufEnd) {
+ assert(BufEnd[0] == 0 && "Buffer is not null terminated!");
+ BufferStart = BufStart;
+ BufferEnd = BufEnd;
+ MustDeleteBuffer = false;
+}
+
+//===----------------------------------------------------------------------===//
+// MemoryBufferMem implementation.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class MemoryBufferMem : public MemoryBuffer {
+ std::string FileID;
+public:
+ MemoryBufferMem(const char *Start, const char *End, const char *FID)
+ : FileID(FID) {
+ init(Start, End);
+ }
+
+ virtual const char *getBufferIdentifier() const {
+ return FileID.c_str();
+ }
+};
+}
+
+/// getMemBuffer - Open the specified memory range as a MemoryBuffer. Note
+/// that EndPtr[0] must be a null byte and be accessible!
+MemoryBuffer *MemoryBuffer::getMemBuffer(const char *StartPtr,
+ const char *EndPtr,
+ const char *BufferName) {
+ return new MemoryBufferMem(StartPtr, EndPtr, BufferName);
+}
+
+/// getNewUninitMemBuffer - Allocate a new MemoryBuffer of the specified size
+/// that is completely initialized to zeros. Note that the caller should
+/// initialize the memory allocated by this method. The memory is owned by
+/// the MemoryBuffer object.
+MemoryBuffer *MemoryBuffer::getNewUninitMemBuffer(unsigned Size,
+ const char *BufferName) {
+ char *Buf = new char[Size+1];
+ Buf[Size] = 0;
+ MemoryBufferMem *SB = new MemoryBufferMem(Buf, Buf+Size, BufferName);
+ // The memory for this buffer is owned by the MemoryBuffer.
+ SB->MustDeleteBuffer = true;
+ return SB;
+}
+
+/// getNewMemBuffer - Allocate a new MemoryBuffer of the specified size that
+/// is completely initialized to zeros. Note that the caller should
+/// initialize the memory allocated by this method. The memory is owned by
+/// the MemoryBuffer object.
+MemoryBuffer *MemoryBuffer::getNewMemBuffer(unsigned Size,
+ const char *BufferName) {
+ MemoryBuffer *SB = getNewUninitMemBuffer(Size, BufferName);
+ memset(const_cast<char*>(SB->getBufferStart()), 0, Size+1);
+ return SB;
+}
+
+
+//===----------------------------------------------------------------------===//
+// MemoryBufferMMapFile implementation.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class MemoryBufferMMapFile : public MemoryBuffer {
+ sys::MappedFile File;
+public:
+ MemoryBufferMMapFile() {}
+
+ bool open(const sys::Path &Filename, std::string *ErrStr);
+
+ virtual const char *getBufferIdentifier() const {
+ return File.path().c_str();
+ }
+
+ ~MemoryBufferMMapFile();
+};
+}
+
+bool MemoryBufferMMapFile::open(const sys::Path &Filename,
+ std::string *ErrStr) {
+ // FIXME: This does an extra stat syscall to figure out the size, but we
+ // already know the size!
+ bool Failure = File.open(Filename, sys::MappedFile::READ_ACCESS, ErrStr);
+ if (Failure) return true;
+
+ if (!File.map(ErrStr))
+ return true;
+
+ size_t Size = File.size();
+
+ static unsigned PageSize = sys::Process::GetPageSize();
+ assert(((PageSize & (PageSize-1)) == 0) && PageSize &&
+ "Page size is not a power of 2!");
+
+ // If this file is not an exact multiple of the system page size (common
+ // case), then the OS has zero terminated the buffer for us.
+ if ((Size & (PageSize-1))) {
+ init(File.charBase(), File.charBase()+Size);
+ } else {
+ // Otherwise, we allocate a new memory buffer and copy the data over
+ initCopyOf(File.charBase(), File.charBase()+Size);
+
+ // No need to keep the file mapped any longer.
+ File.unmap();
+ }
+ return false;
+}
+
+MemoryBufferMMapFile::~MemoryBufferMMapFile() {
+ if (File.isMapped())
+ File.unmap();
+}
+
+//===----------------------------------------------------------------------===//
+// MemoryBuffer::getFile implementation.
+//===----------------------------------------------------------------------===//
+
+MemoryBuffer *MemoryBuffer::getFile(const char *FilenameStart, unsigned FnSize,
+ std::string *ErrStr, int64_t FileSize){
+ // FIXME: it would be nice if PathWithStatus didn't copy the filename into a
+ // temporary string. :(
+ sys::PathWithStatus P(FilenameStart, FnSize);
+#if 1
+ MemoryBufferMMapFile *M = new MemoryBufferMMapFile();
+ if (!M->open(P, ErrStr))
+ return M;
+ delete M;
+ return 0;
+#else
+ // FIXME: We need an efficient and portable method to open a file and then use
+ // 'read' to copy the bits out. The unix implementation is below. This is
+ // an important optimization for clients that want to open large numbers of
+ // small files (using mmap on everything can easily exhaust address space!).
+
+ // If the user didn't specify a filesize, do a stat to find it.
+ if (FileSize == -1) {
+ const sys::FileStatus *FS = P.getFileStatus();
+ if (FS == 0) return 0; // Error stat'ing file.
+
+ FileSize = FS->fileSize;
+ }
+
+ // If the file is larger than some threshold, use mmap, otherwise use 'read'.
+ if (FileSize >= 4096*4) {
+ MemoryBufferMMapFile *M = new MemoryBufferMMapFile();
+ if (!M->open(P, ErrStr))
+ return M;
+ delete M;
+ return 0;
+ }
+
+ MemoryBuffer *SB = getNewUninitMemBuffer(FileSize, FilenameStart);
+ char *BufPtr = const_cast<char*>(SB->getBufferStart());
+
+ int FD = ::open(FilenameStart, O_RDONLY);
+ if (FD == -1) {
+ delete SB;
+ return 0;
+ }
+
+ unsigned BytesLeft = FileSize;
+ while (BytesLeft) {
+ ssize_t NumRead = ::read(FD, BufPtr, BytesLeft);
+ if (NumRead != -1) {
+ BytesLeft -= NumRead;
+ BufPtr += NumRead;
+ } else if (errno == EINTR) {
+ // try again
+ } else {
+ // error reading.
+ close(FD);
+ delete SB;
+ return 0;
+ }
+ }
+ close(FD);
+
+ return SB;
+#endif
+}
+
+
+//===----------------------------------------------------------------------===//
+// MemoryBuffer::getSTDIN implementation.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class STDINBufferFile : public MemoryBuffer {
+public:
+ virtual const char *getBufferIdentifier() const {
+ return "<stdin>";
+ }
+};
+}
+
+MemoryBuffer *MemoryBuffer::getSTDIN() {
+ char Buffer[4096*4];
+
+ std::vector<char> FileData;
+
+ // Read in all of the data from stdin, we cannot mmap stdin.
+ sys::Program::ChangeStdinToBinary();
+ while (size_t ReadBytes = fread(Buffer, 1, 4096*4, stdin))
+ FileData.insert(FileData.end(), Buffer, Buffer+ReadBytes);
+
+ FileData.push_back(0); // &FileData[Size] is invalid. So is &*FileData.end().
+ size_t Size = FileData.size();
+ MemoryBuffer *B = new STDINBufferFile();
+ B->initCopyOf(&FileData[0], &FileData[Size-1]);
+ return B;
+}
diff --git a/lib/Support/PluginLoader.cpp b/lib/Support/PluginLoader.cpp
new file mode 100644
index 0000000..3c9de89
--- /dev/null
+++ b/lib/Support/PluginLoader.cpp
@@ -0,0 +1,44 @@
+//===-- PluginLoader.cpp - Implement -load command line option ------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the -load <plugin> command line option handler.
+//
+//===----------------------------------------------------------------------===//
+
+#define DONT_GET_PLUGIN_LOADER_OPTION
+#include "llvm/Support/PluginLoader.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/System/DynamicLibrary.h"
+#include <ostream>
+#include <vector>
+using namespace llvm;
+
+static std::vector<std::string> *Plugins;
+
+void PluginLoader::operator=(const std::string &Filename) {
+ if (!Plugins)
+ Plugins = new std::vector<std::string>();
+
+ std::string Error;
+ if (sys::DynamicLibrary::LoadLibraryPermanently(Filename.c_str(), &Error)) {
+ cerr << "Error opening '" << Filename << "': " << Error
+ << "\n -load request ignored.\n";
+ } else {
+ Plugins->push_back(Filename);
+ }
+}
+
+unsigned PluginLoader::getNumPlugins() {
+ return Plugins ? Plugins->size() : 0;
+}
+
+std::string &PluginLoader::getPlugin(unsigned num) {
+ assert(Plugins && num < Plugins->size() && "Asking for an out of bounds plugin");
+ return (*Plugins)[num];
+}
diff --git a/lib/Support/SlowOperationInformer.cpp b/lib/Support/SlowOperationInformer.cpp
new file mode 100644
index 0000000..a7bdf12
--- /dev/null
+++ b/lib/Support/SlowOperationInformer.cpp
@@ -0,0 +1,66 @@
+//===-- SlowOperationInformer.cpp - Keep the user informed ----------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the SlowOperationInformer class for the LLVM debugger.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/SlowOperationInformer.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/System/Alarm.h"
+#include <sstream>
+#include <cassert>
+using namespace llvm;
+
+SlowOperationInformer::SlowOperationInformer(const std::string &Name)
+ : OperationName(Name), LastPrintAmount(0) {
+ sys::SetupAlarm(1);
+}
+
+SlowOperationInformer::~SlowOperationInformer() {
+ sys::TerminateAlarm();
+ if (LastPrintAmount) {
+ // If we have printed something, make _sure_ we print the 100% amount, and
+ // also print a newline.
+ cout << std::string(LastPrintAmount, '\b') << "Progress "
+ << OperationName << ": 100% \n";
+ }
+}
+
+/// progress - Clients should periodically call this method when they are in
+/// an exception-safe state. The Amount variable should indicate how far
+/// along the operation is, given in 1/10ths of a percent (in other words,
+/// Amount should range from 0 to 1000).
+bool SlowOperationInformer::progress(unsigned Amount) {
+ int status = sys::AlarmStatus();
+ if (status == -1) {
+ cout << "\n";
+ LastPrintAmount = 0;
+ return true;
+ }
+
+ // If we haven't spent enough time in this operation to warrant displaying the
+ // progress bar, don't do so yet.
+ if (status == 0)
+ return false;
+
+ // Delete whatever we printed last time.
+ std::string ToPrint = std::string(LastPrintAmount, '\b');
+
+ std::ostringstream OS;
+ OS << "Progress " << OperationName << ": " << Amount/10;
+ if (unsigned Rem = Amount % 10)
+ OS << "." << Rem << "%";
+ else
+ OS << "% ";
+
+ LastPrintAmount = OS.str().size();
+ cout << ToPrint+OS.str() << std::flush;
+ return false;
+}
diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp
new file mode 100644
index 0000000..eb33c15
--- /dev/null
+++ b/lib/Support/SmallPtrSet.cpp
@@ -0,0 +1,209 @@
+//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the SmallPtrSet class. See SmallPtrSet.h for an
+// overview of the algorithm.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/MathExtras.h"
+#include <cstdlib>
+
+using namespace llvm;
+
+bool SmallPtrSetImpl::insert(void *Ptr) {
+ if (isSmall()) {
+ // Check to see if it is already in the set.
+ for (void **APtr = SmallArray, **E = SmallArray+NumElements;
+ APtr != E; ++APtr)
+ if (*APtr == Ptr)
+ return false;
+
+ // Nope, there isn't. If we stay small, just 'pushback' now.
+ if (NumElements < CurArraySize-1) {
+ SmallArray[NumElements++] = Ptr;
+ return true;
+ }
+ // Otherwise, hit the big set case, which will call grow.
+ }
+
+ // If more than 3/4 of the array is full, grow.
+ if (NumElements*4 >= CurArraySize*3 ||
+ CurArraySize-(NumElements+NumTombstones) < CurArraySize/8)
+ Grow();
+
+ // Okay, we know we have space. Find a hash bucket.
+ void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
+ if (*Bucket == Ptr) return false; // Already inserted, good.
+
+ // Otherwise, insert it!
+ if (*Bucket == getTombstoneMarker())
+ --NumTombstones;
+ *Bucket = Ptr;
+ ++NumElements; // Track density.
+ return true;
+}
+
+bool SmallPtrSetImpl::erase(void *Ptr) {
+ if (isSmall()) {
+ // Check to see if it is in the set.
+ for (void **APtr = SmallArray, **E = SmallArray+NumElements;
+ APtr != E; ++APtr)
+ if (*APtr == Ptr) {
+ // If it is in the set, replace this element.
+ *APtr = E[-1];
+ E[-1] = getEmptyMarker();
+ --NumElements;
+ return true;
+ }
+
+ return false;
+ }
+
+ // Okay, we know we have space. Find a hash bucket.
+ void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
+ if (*Bucket != Ptr) return false; // Not in the set?
+
+ // Set this as a tombstone.
+ *Bucket = getTombstoneMarker();
+ --NumElements;
+ ++NumTombstones;
+ return true;
+}
+
+void * const *SmallPtrSetImpl::FindBucketFor(void *Ptr) const {
+ unsigned Bucket = Hash(Ptr);
+ unsigned ArraySize = CurArraySize;
+ unsigned ProbeAmt = 1;
+ void *const *Array = CurArray;
+ void *const *Tombstone = 0;
+ while (1) {
+ // Found Ptr's bucket?
+ if (Array[Bucket] == Ptr)
+ return Array+Bucket;
+
+ // If we found an empty bucket, the pointer doesn't exist in the set.
+ // Return a tombstone if we've seen one so far, or the empty bucket if
+ // not.
+ if (Array[Bucket] == getEmptyMarker())
+ return Tombstone ? Tombstone : Array+Bucket;
+
+ // If this is a tombstone, remember it. If Ptr ends up not in the set, we
+ // prefer to return it than something that would require more probing.
+ if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
+ Tombstone = Array+Bucket; // Remember the first tombstone found.
+
+ // It's a hash collision or a tombstone. Reprobe.
+ Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
+ }
+}
+
+/// Grow - Allocate a larger backing store for the buckets and move it over.
+///
+void SmallPtrSetImpl::Grow() {
+ // Allocate at twice as many buckets, but at least 128.
+ unsigned OldSize = CurArraySize;
+ unsigned NewSize = OldSize < 64 ? 128 : OldSize*2;
+
+ void **OldBuckets = CurArray;
+ bool WasSmall = isSmall();
+
+ // Install the new array. Clear all the buckets to empty.
+ CurArray = (void**)malloc(sizeof(void*) * (NewSize+1));
+ assert(CurArray && "Failed to allocate memory?");
+ CurArraySize = NewSize;
+ memset(CurArray, -1, NewSize*sizeof(void*));
+
+ // The end pointer, always valid, is set to a valid element to help the
+ // iterator.
+ CurArray[NewSize] = 0;
+
+ // Copy over all the elements.
+ if (WasSmall) {
+ // Small sets store their elements in order.
+ for (void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
+ BucketPtr != E; ++BucketPtr) {
+ void *Elt = *BucketPtr;
+ *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ }
+ } else {
+ // Copy over all valid entries.
+ for (void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
+ BucketPtr != E; ++BucketPtr) {
+ // Copy over the element if it is valid.
+ void *Elt = *BucketPtr;
+ if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
+ *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ }
+
+ free(OldBuckets);
+ NumTombstones = 0;
+ }
+}
+
+SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) {
+ NumElements = that.NumElements;
+ NumTombstones = 0;
+ if (that.isSmall()) {
+ CurArraySize = that.CurArraySize;
+ CurArray = &SmallArray[0];
+ // Copy the entire contents of the array, including the -1's and the null
+ // terminator.
+ memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
+ } else {
+ CurArraySize = that.NumElements < 64 ? 128 : that.CurArraySize*2;
+ CurArray = (void**)malloc(sizeof(void*) * (CurArraySize+1));
+ assert(CurArray && "Failed to allocate memory?");
+ memset(CurArray, -1, CurArraySize*sizeof(void*));
+
+ // The end pointer, always valid, is set to a valid element to help the
+ // iterator.
+ CurArray[CurArraySize] = 0;
+
+ // Copy over all valid entries.
+ for (void **BucketPtr = that.CurArray, **E = that.CurArray+that.CurArraySize;
+ BucketPtr != E; ++BucketPtr) {
+ // Copy over the element if it is valid.
+ void *Elt = *BucketPtr;
+ if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
+ *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ }
+ }
+}
+
+/// CopyFrom - implement operator= from a smallptrset that has the same pointer
+/// type, but may have a different small size.
+void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
+ if (isSmall() && RHS.isSmall())
+ assert(CurArraySize == RHS.CurArraySize &&
+ "Cannot assign sets with different small sizes");
+ NumElements = RHS.NumElements;
+ NumTombstones = RHS.NumTombstones;
+
+ // If we're becoming small, prepare to insert into our stack space
+ if (RHS.isSmall())
+ CurArray = &SmallArray[0];
+ // Otherwise, allocate new heap space (unless we were the same size)
+ else if (CurArraySize != RHS.CurArraySize) {
+ CurArray = (void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1));
+ assert(CurArray && "Failed to allocate memory?");
+ }
+
+ // Copy over the new array size
+ CurArraySize = RHS.CurArraySize;
+
+ // Copy over the contents from the other set
+ memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1));
+}
+
+SmallPtrSetImpl::~SmallPtrSetImpl() {
+ if (!isSmall())
+ free(CurArray);
+}
diff --git a/lib/Support/Statistic.cpp b/lib/Support/Statistic.cpp
new file mode 100644
index 0000000..a698a00
--- /dev/null
+++ b/lib/Support/Statistic.cpp
@@ -0,0 +1,121 @@
+//===-- Statistic.cpp - Easy way to expose stats information --------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the 'Statistic' class, which is designed to be an easy
+// way to expose various success metrics from passes. These statistics are
+// printed at the end of a run, when the -stats command line option is enabled
+// on the command line.
+//
+// This is useful for reporting information like the number of instructions
+// simplified, optimized or removed by various transformations, like this:
+//
+// static Statistic NumInstEliminated("GCSE", "Number of instructions killed");
+//
+// Later, in the code: ++NumInstEliminated;
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/ADT/StringExtras.h"
+#include <algorithm>
+#include <ostream>
+using namespace llvm;
+
+// GetLibSupportInfoOutputFile - Return a file stream to print our output on.
+namespace llvm { extern std::ostream *GetLibSupportInfoOutputFile(); }
+
+/// -stats - Command line option to cause transformations to emit stats about
+/// what they did.
+///
+static cl::opt<bool>
+Enabled("stats", cl::desc("Enable statistics output from program"));
+
+
+namespace {
+/// StatisticInfo - This class is used in a ManagedStatic so that it is created
+/// on demand (when the first statistic is bumped) and destroyed only when
+/// llvm_shutdown is called. We print statistics from the destructor.
+class StatisticInfo {
+ std::vector<const Statistic*> Stats;
+public:
+ ~StatisticInfo();
+
+ void addStatistic(const Statistic *S) {
+ Stats.push_back(S);
+ }
+};
+}
+
+static ManagedStatic<StatisticInfo> StatInfo;
+
+
+/// RegisterStatistic - The first time a statistic is bumped, this method is
+/// called.
+void Statistic::RegisterStatistic() {
+ // If stats are enabled, inform StatInfo that this statistic should be
+ // printed.
+ if (Enabled)
+ StatInfo->addStatistic(this);
+ // Remember we have been registered.
+ Initialized = true;
+}
+
+struct NameCompare {
+ bool operator()(const Statistic *LHS, const Statistic *RHS) const {
+ int Cmp = std::strcmp(LHS->getName(), RHS->getName());
+ if (Cmp != 0) return Cmp < 0;
+
+ // Secondary key is the description.
+ return std::strcmp(LHS->getDesc(), RHS->getDesc()) < 0;
+ }
+};
+
+// Print information when destroyed, iff command line option is specified.
+StatisticInfo::~StatisticInfo() {
+ // Statistics not enabled?
+ if (Stats.empty()) return;
+
+ // Get the stream to write to.
+ std::ostream &OutStream = *GetLibSupportInfoOutputFile();
+
+ // Figure out how long the biggest Value and Name fields are.
+ unsigned MaxNameLen = 0, MaxValLen = 0;
+ for (unsigned i = 0, e = Stats.size(); i != e; ++i) {
+ MaxValLen = std::max(MaxValLen,
+ (unsigned)utostr(Stats[i]->getValue()).size());
+ MaxNameLen = std::max(MaxNameLen,
+ (unsigned)std::strlen(Stats[i]->getName()));
+ }
+
+ // Sort the fields by name.
+ std::stable_sort(Stats.begin(), Stats.end(), NameCompare());
+
+ // Print out the statistics header...
+ OutStream << "===" << std::string(73, '-') << "===\n"
+ << " ... Statistics Collected ...\n"
+ << "===" << std::string(73, '-') << "===\n\n";
+
+ // Print all of the statistics.
+ for (unsigned i = 0, e = Stats.size(); i != e; ++i) {
+ std::string CountStr = utostr(Stats[i]->getValue());
+ OutStream << std::string(MaxValLen-CountStr.size(), ' ')
+ << CountStr << " " << Stats[i]->getName()
+ << std::string(MaxNameLen-std::strlen(Stats[i]->getName()), ' ')
+ << " - " << Stats[i]->getDesc() << "\n";
+
+ }
+
+ OutStream << std::endl; // Flush the output stream...
+
+ if (&OutStream != cerr.stream() && &OutStream != cout.stream())
+ delete &OutStream; // Close the file.
+}
diff --git a/lib/Support/Streams.cpp b/lib/Support/Streams.cpp
new file mode 100644
index 0000000..433f6b4
--- /dev/null
+++ b/lib/Support/Streams.cpp
@@ -0,0 +1,21 @@
+//===-- Streams.cpp - Wrappers for iostreams ------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Bill Wendling and is distributed under the
+// University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a wrapper for the std::cout and std::cerr I/O streams.
+// It prevents the need to include <iostream> to each file just to get I/O.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Streams.h"
+#include <iostream>
+using namespace llvm;
+
+OStream llvm::cout(std::cout);
+OStream llvm::cerr(std::cerr);
+IStream llvm::cin(std::cin);
diff --git a/lib/Support/StringExtras.cpp b/lib/Support/StringExtras.cpp
new file mode 100644
index 0000000..2ce2349
--- /dev/null
+++ b/lib/Support/StringExtras.cpp
@@ -0,0 +1,108 @@
+//===-- StringExtras.cpp - Implement the StringExtras header --------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the StringExtras.h header
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringExtras.h"
+using namespace llvm;
+
+/// getToken - This function extracts one token from source, ignoring any
+/// leading characters that appear in the Delimiters string, and ending the
+/// token at any of the characters that appear in the Delimiters string. If
+/// there are no tokens in the source string, an empty string is returned.
+/// The Source source string is updated in place to remove the returned string
+/// and any delimiter prefix from it.
+std::string llvm::getToken(std::string &Source, const char *Delimiters) {
+ unsigned NumDelimiters = std::strlen(Delimiters);
+
+ // Figure out where the token starts.
+ std::string::size_type Start =
+ Source.find_first_not_of(Delimiters, 0, NumDelimiters);
+ if (Start == std::string::npos) Start = Source.size();
+
+ // Find the next occurance of the delimiter.
+ std::string::size_type End =
+ Source.find_first_of(Delimiters, Start, NumDelimiters);
+ if (End == std::string::npos) End = Source.size();
+
+ // Create the return token.
+ std::string Result = std::string(Source.begin()+Start, Source.begin()+End);
+
+ // Erase the token that we read in.
+ Source.erase(Source.begin(), Source.begin()+End);
+
+ return Result;
+}
+
+/// SplitString - Split up the specified string according to the specified
+/// delimiters, appending the result fragments to the output list.
+void llvm::SplitString(const std::string &Source,
+ std::vector<std::string> &OutFragments,
+ const char *Delimiters) {
+ std::string S = Source;
+
+ std::string S2 = getToken(S, Delimiters);
+ while (!S2.empty()) {
+ OutFragments.push_back(S2);
+ S2 = getToken(S, Delimiters);
+ }
+}
+
+
+
+/// UnescapeString - Modify the argument string, turning two character sequences
+/// like '\\' 'n' into '\n'. This handles: \e \a \b \f \n \r \t \v \' \\ and
+/// \num (where num is a 1-3 byte octal value).
+void llvm::UnescapeString(std::string &Str) {
+ for (unsigned i = 0; i != Str.size(); ++i) {
+ if (Str[i] == '\\' && i != Str.size()-1) {
+ switch (Str[i+1]) {
+ default: continue; // Don't execute the code after the switch.
+ case 'a': Str[i] = '\a'; break;
+ case 'b': Str[i] = '\b'; break;
+ case 'e': Str[i] = 27; break;
+ case 'f': Str[i] = '\f'; break;
+ case 'n': Str[i] = '\n'; break;
+ case 'r': Str[i] = '\r'; break;
+ case 't': Str[i] = '\t'; break;
+ case 'v': Str[i] = '\v'; break;
+ case '\'': Str[i] = '\''; break;
+ case '\\': Str[i] = '\\'; break;
+ }
+ // Nuke the second character.
+ Str.erase(Str.begin()+i+1);
+ }
+ }
+}
+
+/// EscapeString - Modify the argument string, turning '\\' and anything that
+/// doesn't satisfy std::isprint into an escape sequence.
+void llvm::EscapeString(std::string &Str) {
+ for (unsigned i = 0; i != Str.size(); ++i) {
+ if (Str[i] == '\\') {
+ ++i;
+ Str.insert(Str.begin()+i, '\\');
+ } else if (Str[i] == '\t') {
+ Str[i++] = '\\';
+ Str.insert(Str.begin()+i, 't');
+ } else if (Str[i] == '\n') {
+ Str[i++] = '\\';
+ Str.insert(Str.begin()+i, 'n');
+ } else if (!std::isprint(Str[i])) {
+ // Always expand to a 3-digit octal escape.
+ unsigned Char = Str[i];
+ Str[i++] = '\\';
+ Str.insert(Str.begin()+i++, '0'+((Char/64) & 7));
+ Str.insert(Str.begin()+i++, '0'+((Char/8) & 7));
+ Str.insert(Str.begin()+i , '0'+( Char & 7));
+ }
+ }
+}
diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp
new file mode 100644
index 0000000..ae0dca7
--- /dev/null
+++ b/lib/Support/StringMap.cpp
@@ -0,0 +1,234 @@
+//===--- StringMap.cpp - String Hash table map implementation -------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by Chris Lattner and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the StringMap class.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringMap.h"
+#include <cassert>
+using namespace llvm;
+
+StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
+ ItemSize = itemSize;
+
+ // If a size is specified, initialize the table with that many buckets.
+ if (InitSize) {
+ init(InitSize);
+ return;
+ }
+
+ // Otherwise, initialize it with zero buckets to avoid the allocation.
+ TheTable = 0;
+ NumBuckets = 0;
+ NumItems = 0;
+ NumTombstones = 0;
+}
+
+void StringMapImpl::init(unsigned InitSize) {
+ assert((InitSize & (InitSize-1)) == 0 &&
+ "Init Size must be a power of 2 or zero!");
+ NumBuckets = InitSize ? InitSize : 16;
+ NumItems = 0;
+ NumTombstones = 0;
+
+ TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
+
+ // Allocate one extra bucket, set it to look filled so the iterators stop at
+ // end.
+ TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
+}
+
+
+/// HashString - Compute a hash code for the specified string.
+///
+static unsigned HashString(const char *Start, const char *End) {
+ // Bernstein hash function.
+ unsigned int Result = 0;
+ // TODO: investigate whether a modified bernstein hash function performs
+ // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
+ // X*33+c -> X*33^c
+ while (Start != End)
+ Result = Result * 33 + *Start++;
+ Result = Result + (Result >> 5);
+ return Result;
+}
+
+/// LookupBucketFor - Look up the bucket that the specified string should end
+/// up in. If it already exists as a key in the map, the Item pointer for the
+/// specified bucket will be non-null. Otherwise, it will be null. In either
+/// case, the FullHashValue field of the bucket will be set to the hash value
+/// of the string.
+unsigned StringMapImpl::LookupBucketFor(const char *NameStart,
+ const char *NameEnd) {
+ unsigned HTSize = NumBuckets;
+ if (HTSize == 0) { // Hash table unallocated so far?
+ init(16);
+ HTSize = NumBuckets;
+ }
+ unsigned FullHashValue = HashString(NameStart, NameEnd);
+ unsigned BucketNo = FullHashValue & (HTSize-1);
+
+ unsigned ProbeAmt = 1;
+ int FirstTombstone = -1;
+ while (1) {
+ ItemBucket &Bucket = TheTable[BucketNo];
+ StringMapEntryBase *BucketItem = Bucket.Item;
+ // If we found an empty bucket, this key isn't in the table yet, return it.
+ if (BucketItem == 0) {
+ // If we found a tombstone, we want to reuse the tombstone instead of an
+ // empty bucket. This reduces probing.
+ if (FirstTombstone != -1) {
+ TheTable[FirstTombstone].FullHashValue = FullHashValue;
+ return FirstTombstone;
+ }
+
+ Bucket.FullHashValue = FullHashValue;
+ return BucketNo;
+ }
+
+ if (BucketItem == getTombstoneVal()) {
+ // Skip over tombstones. However, remember the first one we see.
+ if (FirstTombstone == -1) FirstTombstone = BucketNo;
+ } else if (Bucket.FullHashValue == FullHashValue) {
+ // If the full hash value matches, check deeply for a match. The common
+ // case here is that we are only looking at the buckets (for item info
+ // being non-null and for the full hash value) not at the items. This
+ // is important for cache locality.
+
+ // Do the comparison like this because NameStart isn't necessarily
+ // null-terminated!
+ char *ItemStr = (char*)BucketItem+ItemSize;
+ unsigned ItemStrLen = BucketItem->getKeyLength();
+ if (unsigned(NameEnd-NameStart) == ItemStrLen &&
+ memcmp(ItemStr, NameStart, ItemStrLen) == 0) {
+ // We found a match!
+ return BucketNo;
+ }
+ }
+
+ // Okay, we didn't find the item. Probe to the next bucket.
+ BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
+
+ // Use quadratic probing, it has fewer clumping artifacts than linear
+ // probing and has good cache behavior in the common case.
+ ++ProbeAmt;
+ }
+}
+
+
+/// FindKey - Look up the bucket that contains the specified key. If it exists
+/// in the map, return the bucket number of the key. Otherwise return -1.
+/// This does not modify the map.
+int StringMapImpl::FindKey(const char *KeyStart, const char *KeyEnd) const {
+ unsigned HTSize = NumBuckets;
+ if (HTSize == 0) return -1; // Really empty table?
+ unsigned FullHashValue = HashString(KeyStart, KeyEnd);
+ unsigned BucketNo = FullHashValue & (HTSize-1);
+
+ unsigned ProbeAmt = 1;
+ while (1) {
+ ItemBucket &Bucket = TheTable[BucketNo];
+ StringMapEntryBase *BucketItem = Bucket.Item;
+ // If we found an empty bucket, this key isn't in the table yet, return.
+ if (BucketItem == 0)
+ return -1;
+
+ if (BucketItem == getTombstoneVal()) {
+ // Ignore tombstones.
+ } else if (Bucket.FullHashValue == FullHashValue) {
+ // If the full hash value matches, check deeply for a match. The common
+ // case here is that we are only looking at the buckets (for item info
+ // being non-null and for the full hash value) not at the items. This
+ // is important for cache locality.
+
+ // Do the comparison like this because NameStart isn't necessarily
+ // null-terminated!
+ char *ItemStr = (char*)BucketItem+ItemSize;
+ unsigned ItemStrLen = BucketItem->getKeyLength();
+ if (unsigned(KeyEnd-KeyStart) == ItemStrLen &&
+ memcmp(ItemStr, KeyStart, ItemStrLen) == 0) {
+ // We found a match!
+ return BucketNo;
+ }
+ }
+
+ // Okay, we didn't find the item. Probe to the next bucket.
+ BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
+
+ // Use quadratic probing, it has fewer clumping artifacts than linear
+ // probing and has good cache behavior in the common case.
+ ++ProbeAmt;
+ }
+}
+
+/// RemoveKey - Remove the specified StringMapEntry from the table, but do not
+/// delete it. This aborts if the value isn't in the table.
+void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
+ const char *VStr = (char*)V + ItemSize;
+ StringMapEntryBase *V2 = RemoveKey(VStr, VStr+V->getKeyLength());
+ V2 = V2;
+ assert(V == V2 && "Didn't find key?");
+}
+
+/// RemoveKey - Remove the StringMapEntry for the specified key from the
+/// table, returning it. If the key is not in the table, this returns null.
+StringMapEntryBase *StringMapImpl::RemoveKey(const char *KeyStart,
+ const char *KeyEnd) {
+ int Bucket = FindKey(KeyStart, KeyEnd);
+ if (Bucket == -1) return 0;
+
+ StringMapEntryBase *Result = TheTable[Bucket].Item;
+ TheTable[Bucket].Item = getTombstoneVal();
+ --NumItems;
+ ++NumTombstones;
+ return Result;
+}
+
+
+
+/// RehashTable - Grow the table, redistributing values into the buckets with
+/// the appropriate mod-of-hashtable-size.
+void StringMapImpl::RehashTable() {
+ unsigned NewSize = NumBuckets*2;
+ // Allocate one extra bucket which will always be non-empty. This allows the
+ // iterators to stop at end.
+ ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
+ NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
+
+ // Rehash all the items into their new buckets. Luckily :) we already have
+ // the hash values available, so we don't have to rehash any strings.
+ for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
+ if (IB->Item && IB->Item != getTombstoneVal()) {
+ // Fast case, bucket available.
+ unsigned FullHash = IB->FullHashValue;
+ unsigned NewBucket = FullHash & (NewSize-1);
+ if (NewTableArray[NewBucket].Item == 0) {
+ NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
+ NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
+ continue;
+ }
+
+ // Otherwise probe for a spot.
+ unsigned ProbeSize = 1;
+ do {
+ NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
+ } while (NewTableArray[NewBucket].Item);
+
+ // Finally found a slot. Fill it in.
+ NewTableArray[NewBucket].Item = IB->Item;
+ NewTableArray[NewBucket].FullHashValue = FullHash;
+ }
+ }
+
+ free(TheTable);
+
+ TheTable = NewTableArray;
+ NumBuckets = NewSize;
+}
diff --git a/lib/Support/SystemUtils.cpp b/lib/Support/SystemUtils.cpp
new file mode 100644
index 0000000..afa0d7e
--- /dev/null
+++ b/lib/Support/SystemUtils.cpp
@@ -0,0 +1,58 @@
+//===- SystemUtils.cpp - Utilities for low-level system tasks -------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains functions used to do a variety of low-level, often
+// system-specific, tasks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Streams.h"
+#include "llvm/Support/SystemUtils.h"
+#include "llvm/System/Process.h"
+#include "llvm/System/Program.h"
+#include <ostream>
+using namespace llvm;
+
+bool llvm::CheckBitcodeOutputToConsole(std::ostream* stream_to_check,
+ bool print_warning) {
+ if (stream_to_check == cout.stream() &&
+ sys::Process::StandardOutIsDisplayed()) {
+ if (print_warning) {
+ cerr << "WARNING: You're attempting to print out a bitcode file.\n"
+ << "This is inadvisable as it may cause display problems. If\n"
+ << "you REALLY want to taste LLVM bitcode first-hand, you\n"
+ << "can force output with the `-f' option.\n\n";
+ }
+ return true;
+ }
+ return false;
+}
+
+/// FindExecutable - Find a named executable, giving the argv[0] of program
+/// being executed. This allows us to find another LLVM tool if it is built
+/// into the same directory, but that directory is neither the current
+/// directory, nor in the PATH. If the executable cannot be found, return an
+/// empty string.
+///
+#undef FindExecutable // needed on windows :(
+sys::Path llvm::FindExecutable(const std::string &ExeName,
+ const std::string &ProgramPath) {
+ // First check the directory that the calling program is in. We can do this
+ // if ProgramPath contains at least one / character, indicating that it is a
+ // relative path to bugpoint itself.
+ sys::Path Result ( ProgramPath );
+ Result.eraseComponent();
+ if (!Result.isEmpty()) {
+ Result.appendComponent(ExeName);
+ if (Result.canExecute())
+ return Result;
+ }
+
+ return sys::Program::FindProgramByName(ExeName);
+}
diff --git a/lib/Support/Timer.cpp b/lib/Support/Timer.cpp
new file mode 100644
index 0000000..077995d
--- /dev/null
+++ b/lib/Support/Timer.cpp
@@ -0,0 +1,355 @@
+//===-- Timer.cpp - Interval Timing Support -------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Interval Timing implementation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/Timer.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/System/Process.h"
+#include <algorithm>
+#include <fstream>
+#include <functional>
+#include <map>
+using namespace llvm;
+
+// GetLibSupportInfoOutputFile - Return a file stream to print our output on.
+namespace llvm { extern std::ostream *GetLibSupportInfoOutputFile(); }
+
+// getLibSupportInfoOutputFilename - This ugly hack is brought to you courtesy
+// of constructor/destructor ordering being unspecified by C++. Basically the
+// problem is that a Statistic object gets destroyed, which ends up calling
+// 'GetLibSupportInfoOutputFile()' (below), which calls this function.
+// LibSupportInfoOutputFilename used to be a global variable, but sometimes it
+// would get destroyed before the Statistic, causing havoc to ensue. We "fix"
+// this by creating the string the first time it is needed and never destroying
+// it.
+static ManagedStatic<std::string> LibSupportInfoOutputFilename;
+static std::string &getLibSupportInfoOutputFilename() {
+ return *LibSupportInfoOutputFilename;
+}
+
+namespace {
+ cl::opt<bool>
+ TrackSpace("track-memory", cl::desc("Enable -time-passes memory "
+ "tracking (this may be slow)"),
+ cl::Hidden);
+
+ cl::opt<std::string, true>
+ InfoOutputFilename("info-output-file", cl::value_desc("filename"),
+ cl::desc("File to append -stats and -timer output to"),
+ cl::Hidden, cl::location(getLibSupportInfoOutputFilename()));
+}
+
+static TimerGroup *DefaultTimerGroup = 0;
+static TimerGroup *getDefaultTimerGroup() {
+ if (DefaultTimerGroup) return DefaultTimerGroup;
+ return DefaultTimerGroup = new TimerGroup("Miscellaneous Ungrouped Timers");
+}
+
+Timer::Timer(const std::string &N)
+ : Elapsed(0), UserTime(0), SystemTime(0), MemUsed(0), PeakMem(0), Name(N),
+ Started(false), TG(getDefaultTimerGroup()) {
+ TG->addTimer();
+}
+
+Timer::Timer(const std::string &N, TimerGroup &tg)
+ : Elapsed(0), UserTime(0), SystemTime(0), MemUsed(0), PeakMem(0), Name(N),
+ Started(false), TG(&tg) {
+ TG->addTimer();
+}
+
+Timer::Timer(const Timer &T) {
+ TG = T.TG;
+ if (TG) TG->addTimer();
+ operator=(T);
+}
+
+
+// Copy ctor, initialize with no TG member.
+Timer::Timer(bool, const Timer &T) {
+ TG = T.TG; // Avoid assertion in operator=
+ operator=(T); // Copy contents
+ TG = 0;
+}
+
+
+Timer::~Timer() {
+ if (TG) {
+ if (Started) {
+ Started = false;
+ TG->addTimerToPrint(*this);
+ }
+ TG->removeTimer();
+ }
+}
+
+static inline size_t getMemUsage() {
+ if (TrackSpace)
+ return sys::Process::GetMallocUsage();
+ return 0;
+}
+
+struct TimeRecord {
+ double Elapsed, UserTime, SystemTime;
+ ssize_t MemUsed;
+};
+
+static TimeRecord getTimeRecord(bool Start) {
+ TimeRecord Result;
+
+ sys::TimeValue now(0,0);
+ sys::TimeValue user(0,0);
+ sys::TimeValue sys(0,0);
+
+ ssize_t MemUsed = 0;
+ if (Start) {
+ MemUsed = getMemUsage();
+ sys::Process::GetTimeUsage(now,user,sys);
+ } else {
+ sys::Process::GetTimeUsage(now,user,sys);
+ MemUsed = getMemUsage();
+ }
+
+ Result.Elapsed = now.seconds() + now.microseconds() / 1000000.0;
+ Result.UserTime = user.seconds() + user.microseconds() / 1000000.0;
+ Result.SystemTime = sys.seconds() + sys.microseconds() / 1000000.0;
+ Result.MemUsed = MemUsed;
+
+ return Result;
+}
+
+static ManagedStatic<std::vector<Timer*> > ActiveTimers;
+
+void Timer::startTimer() {
+ Started = true;
+ TimeRecord TR = getTimeRecord(true);
+ Elapsed -= TR.Elapsed;
+ UserTime -= TR.UserTime;
+ SystemTime -= TR.SystemTime;
+ MemUsed -= TR.MemUsed;
+ PeakMemBase = TR.MemUsed;
+ ActiveTimers->push_back(this);
+}
+
+void Timer::stopTimer() {
+ TimeRecord TR = getTimeRecord(false);
+ Elapsed += TR.Elapsed;
+ UserTime += TR.UserTime;
+ SystemTime += TR.SystemTime;
+ MemUsed += TR.MemUsed;
+
+ if (ActiveTimers->back() == this) {
+ ActiveTimers->pop_back();
+ } else {
+ std::vector<Timer*>::iterator I =
+ std::find(ActiveTimers->begin(), ActiveTimers->end(), this);
+ assert(I != ActiveTimers->end() && "stop but no startTimer?");
+ ActiveTimers->erase(I);
+ }
+}
+
+void Timer::sum(const Timer &T) {
+ Elapsed += T.Elapsed;
+ UserTime += T.UserTime;
+ SystemTime += T.SystemTime;
+ MemUsed += T.MemUsed;
+ PeakMem += T.PeakMem;
+}
+
+/// addPeakMemoryMeasurement - This method should be called whenever memory
+/// usage needs to be checked. It adds a peak memory measurement to the
+/// currently active timers, which will be printed when the timer group prints
+///
+void Timer::addPeakMemoryMeasurement() {
+ size_t MemUsed = getMemUsage();
+
+ for (std::vector<Timer*>::iterator I = ActiveTimers->begin(),
+ E = ActiveTimers->end(); I != E; ++I)
+ (*I)->PeakMem = std::max((*I)->PeakMem, MemUsed-(*I)->PeakMemBase);
+}
+
+//===----------------------------------------------------------------------===//
+// NamedRegionTimer Implementation
+//===----------------------------------------------------------------------===//
+
+static ManagedStatic<std::map<std::string, Timer> > NamedTimers;
+
+static Timer &getNamedRegionTimer(const std::string &Name) {
+ std::map<std::string, Timer>::iterator I = NamedTimers->lower_bound(Name);
+ if (I != NamedTimers->end() && I->first == Name)
+ return I->second;
+
+ return NamedTimers->insert(I, std::make_pair(Name, Timer(Name)))->second;
+}
+
+NamedRegionTimer::NamedRegionTimer(const std::string &Name)
+ : TimeRegion(getNamedRegionTimer(Name)) {}
+
+
+//===----------------------------------------------------------------------===//
+// TimerGroup Implementation
+//===----------------------------------------------------------------------===//
+
+// printAlignedFP - Simulate the printf "%A.Bf" format, where A is the
+// TotalWidth size, and B is the AfterDec size.
+//
+static void printAlignedFP(double Val, unsigned AfterDec, unsigned TotalWidth,
+ std::ostream &OS) {
+ assert(TotalWidth >= AfterDec+1 && "Bad FP Format!");
+ OS.width(TotalWidth-AfterDec-1);
+ char OldFill = OS.fill();
+ OS.fill(' ');
+ OS << (int)Val; // Integer part;
+ OS << ".";
+ OS.width(AfterDec);
+ OS.fill('0');
+ unsigned ResultFieldSize = 1;
+ while (AfterDec--) ResultFieldSize *= 10;
+ OS << (int)(Val*ResultFieldSize) % ResultFieldSize;
+ OS.fill(OldFill);
+}
+
+static void printVal(double Val, double Total, std::ostream &OS) {
+ if (Total < 1e-7) // Avoid dividing by zero...
+ OS << " ----- ";
+ else {
+ OS << " ";
+ printAlignedFP(Val, 4, 7, OS);
+ OS << " (";
+ printAlignedFP(Val*100/Total, 1, 5, OS);
+ OS << "%)";
+ }
+}
+
+void Timer::print(const Timer &Total, std::ostream &OS) {
+ if (Total.UserTime)
+ printVal(UserTime, Total.UserTime, OS);
+ if (Total.SystemTime)
+ printVal(SystemTime, Total.SystemTime, OS);
+ if (Total.getProcessTime())
+ printVal(getProcessTime(), Total.getProcessTime(), OS);
+ printVal(Elapsed, Total.Elapsed, OS);
+
+ OS << " ";
+
+ if (Total.MemUsed) {
+ OS.width(9);
+ OS << MemUsed << " ";
+ }
+ if (Total.PeakMem) {
+ if (PeakMem) {
+ OS.width(9);
+ OS << PeakMem << " ";
+ } else
+ OS << " ";
+ }
+ OS << Name << "\n";
+
+ Started = false; // Once printed, don't print again
+}
+
+// GetLibSupportInfoOutputFile - Return a file stream to print our output on...
+std::ostream *
+llvm::GetLibSupportInfoOutputFile() {
+ std::string &LibSupportInfoOutputFilename = getLibSupportInfoOutputFilename();
+ if (LibSupportInfoOutputFilename.empty())
+ return cerr.stream();
+ if (LibSupportInfoOutputFilename == "-")
+ return cout.stream();
+
+ std::ostream *Result = new std::ofstream(LibSupportInfoOutputFilename.c_str(),
+ std::ios::app);
+ if (!Result->good()) {
+ cerr << "Error opening info-output-file '"
+ << LibSupportInfoOutputFilename << " for appending!\n";
+ delete Result;
+ return cerr.stream();
+ }
+ return Result;
+}
+
+
+void TimerGroup::removeTimer() {
+ if (--NumTimers == 0 && !TimersToPrint.empty()) { // Print timing report...
+ // Sort the timers in descending order by amount of time taken...
+ std::sort(TimersToPrint.begin(), TimersToPrint.end(),
+ std::greater<Timer>());
+
+ // Figure out how many spaces to indent TimerGroup name...
+ unsigned Padding = (80-Name.length())/2;
+ if (Padding > 80) Padding = 0; // Don't allow "negative" numbers
+
+ std::ostream *OutStream = GetLibSupportInfoOutputFile();
+
+ ++NumTimers;
+ { // Scope to contain Total timer... don't allow total timer to drop us to
+ // zero timers...
+ Timer Total("TOTAL");
+
+ for (unsigned i = 0, e = TimersToPrint.size(); i != e; ++i)
+ Total.sum(TimersToPrint[i]);
+
+ // Print out timing header...
+ *OutStream << "===" << std::string(73, '-') << "===\n"
+ << std::string(Padding, ' ') << Name << "\n"
+ << "===" << std::string(73, '-')
+ << "===\n";
+
+ // If this is not an collection of ungrouped times, print the total time.
+ // Ungrouped timers don't really make sense to add up. We still print the
+ // TOTAL line to make the percentages make sense.
+ if (this != DefaultTimerGroup) {
+ *OutStream << " Total Execution Time: ";
+
+ printAlignedFP(Total.getProcessTime(), 4, 5, *OutStream);
+ *OutStream << " seconds (";
+ printAlignedFP(Total.getWallTime(), 4, 5, *OutStream);
+ *OutStream << " wall clock)\n";
+ }
+ *OutStream << "\n";
+
+ if (Total.UserTime)
+ *OutStream << " ---User Time---";
+ if (Total.SystemTime)
+ *OutStream << " --System Time--";
+ if (Total.getProcessTime())
+ *OutStream << " --User+System--";
+ *OutStream << " ---Wall Time---";
+ if (Total.getMemUsed())
+ *OutStream << " ---Mem---";
+ if (Total.getPeakMem())
+ *OutStream << " -PeakMem-";
+ *OutStream << " --- Name ---\n";
+
+ // Loop through all of the timing data, printing it out...
+ for (unsigned i = 0, e = TimersToPrint.size(); i != e; ++i)
+ TimersToPrint[i].print(Total, *OutStream);
+
+ Total.print(Total, *OutStream);
+ *OutStream << std::endl; // Flush output
+ }
+ --NumTimers;
+
+ TimersToPrint.clear();
+
+ if (OutStream != cerr.stream() && OutStream != cout.stream())
+ delete OutStream; // Close the file...
+ }
+
+ // Delete default timer group!
+ if (NumTimers == 0 && this == DefaultTimerGroup) {
+ delete DefaultTimerGroup;
+ DefaultTimerGroup = 0;
+ }
+}
+