diff options
author | dim <dim@FreeBSD.org> | 2011-05-02 19:34:44 +0000 |
---|---|---|
committer | dim <dim@FreeBSD.org> | 2011-05-02 19:34:44 +0000 |
commit | 2b066988909948dc3d53d01760bc2d71d32f3feb (patch) | |
tree | fc5f365fb9035b2d0c622bbf06c9bbe8627d7279 /lib/Bitcode | |
parent | c80ac9d286b8fcc6d1ee5d76048134cf80aa9edc (diff) | |
download | FreeBSD-src-2b066988909948dc3d53d01760bc2d71d32f3feb.zip FreeBSD-src-2b066988909948dc3d53d01760bc2d71d32f3feb.tar.gz |
Vendor import of llvm trunk r130700:
http://llvm.org/svn/llvm-project/llvm/trunk@130700
Diffstat (limited to 'lib/Bitcode')
-rw-r--r-- | lib/Bitcode/Reader/BitcodeReader.cpp | 12 | ||||
-rw-r--r-- | lib/Bitcode/Writer/BitcodeWriter.cpp | 2 | ||||
-rw-r--r-- | lib/Bitcode/Writer/ValueEnumerator.cpp | 98 | ||||
-rw-r--r-- | lib/Bitcode/Writer/ValueEnumerator.h | 4 |
4 files changed, 77 insertions, 39 deletions
diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp index dbf8da0..19f57cf 100644 --- a/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/lib/Bitcode/Reader/BitcodeReader.cpp @@ -301,8 +301,7 @@ void BitcodeReaderValueList::ResolveConstantForwardRefs() { NewC = ConstantVector::get(NewOps); } else { assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr."); - NewC = cast<ConstantExpr>(UserC)->getWithOperands(&NewOps[0], - NewOps.size()); + NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps); } UserC->replaceAllUsesWith(NewC); @@ -350,7 +349,7 @@ Value *BitcodeReaderMDValueList::getValueFwdRef(unsigned Idx) { } // Create and return a placeholder, which will later be RAUW'd. - Value *V = MDNode::getTemporary(Context, 0, 0); + Value *V = MDNode::getTemporary(Context, ArrayRef<Value*>()); MDValuePtrs[Idx] = V; return V; } @@ -844,9 +843,7 @@ bool BitcodeReader::ParseMetadata() { else Elts.push_back(NULL); } - Value *V = MDNode::getWhenValsUnresolved(Context, - Elts.data(), Elts.size(), - IsFunctionLocal); + Value *V = MDNode::getWhenValsUnresolved(Context, Elts, IsFunctionLocal); IsFunctionLocal = false; MDValueList.AssignValue(V, NextMDValueNo++); break; @@ -2288,9 +2285,8 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { const Type *Ty = getTypeByID(Record[0]); if (!Ty) return Error("Invalid PHI record"); - PHINode *PN = PHINode::Create(Ty); + PHINode *PN = PHINode::Create(Ty, (Record.size()-1)/2); InstructionList.push_back(PN); - PN->reserveOperandSpace((Record.size()-1)/2); for (unsigned i = 0, e = Record.size()-1; i != e; i += 2) { Value *V = getFnValueByID(Record[1+i], Ty); diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp index f8ef8c6..e34137f 100644 --- a/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -197,7 +197,7 @@ static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) { // Loop over all of the types, emitting each in turn. for (unsigned i = 0, e = TypeList.size(); i != e; ++i) { - const Type *T = TypeList[i].first; + const Type *T = TypeList[i]; int AbbrevToUse = 0; unsigned Code = 0; diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp index 2f02262..21f004a 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -12,6 +12,8 @@ //===----------------------------------------------------------------------===// #include "ValueEnumerator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Module.h" @@ -21,22 +23,10 @@ #include <algorithm> using namespace llvm; -static bool isSingleValueType(const std::pair<const llvm::Type*, - unsigned int> &P) { - return P.first->isSingleValueType(); -} - static bool isIntegerValue(const std::pair<const Value*, unsigned> &V) { return V.first->getType()->isIntegerTy(); } -static bool CompareByFrequency(const std::pair<const llvm::Type*, - unsigned int> &P1, - const std::pair<const llvm::Type*, - unsigned int> &P2) { - return P1.second > P2.second; -} - /// ValueEnumerator - Enumerate module-level information. ValueEnumerator::ValueEnumerator(const Module *M) { // Enumerate the global variables. @@ -120,18 +110,72 @@ ValueEnumerator::ValueEnumerator(const Module *M) { // Optimize constant ordering. OptimizeConstants(FirstConstant, Values.size()); - // Sort the type table by frequency so that most commonly used types are early - // in the table (have low bit-width). - std::stable_sort(Types.begin(), Types.end(), CompareByFrequency); - - // Partition the Type ID's so that the single-value types occur before the - // aggregate types. This allows the aggregate types to be dropped from the - // type table after parsing the global variable initializers. - std::partition(Types.begin(), Types.end(), isSingleValueType); + OptimizeTypes(); // Now that we rearranged the type table, rebuild TypeMap. for (unsigned i = 0, e = Types.size(); i != e; ++i) - TypeMap[Types[i].first] = i+1; + TypeMap[Types[i]] = i+1; +} + +struct TypeAndDeps { + const Type *Ty; + unsigned NumDeps; +}; + +static int CompareByDeps(const void *a, const void *b) { + const TypeAndDeps &ta = *(const TypeAndDeps*) a; + const TypeAndDeps &tb = *(const TypeAndDeps*) b; + return ta.NumDeps - tb.NumDeps; +} + +static void VisitType(const Type *Ty, SmallPtrSet<const Type*, 16> &Visited, + std::vector<const Type*> &Out) { + if (Visited.count(Ty)) + return; + + Visited.insert(Ty); + + for (Type::subtype_iterator I2 = Ty->subtype_begin(), + E2 = Ty->subtype_end(); I2 != E2; ++I2) { + const Type *InnerType = I2->get(); + VisitType(InnerType, Visited, Out); + } + + Out.push_back(Ty); +} + +void ValueEnumerator::OptimizeTypes(void) { + // If the types form a DAG, this will compute a topological sort and + // no forward references will be needed when reading them in. + // If there are cycles, this is a simple but reasonable heuristic for + // the minimum feedback arc set problem. + const unsigned NumTypes = Types.size(); + std::vector<TypeAndDeps> TypeDeps; + TypeDeps.resize(NumTypes); + + for (unsigned I = 0; I < NumTypes; ++I) { + const Type *Ty = Types[I]; + TypeDeps[I].Ty = Ty; + TypeDeps[I].NumDeps = 0; + } + + for (unsigned I = 0; I < NumTypes; ++I) { + const Type *Ty = TypeDeps[I].Ty; + for (Type::subtype_iterator I2 = Ty->subtype_begin(), + E2 = Ty->subtype_end(); I2 != E2; ++I2) { + const Type *InnerType = I2->get(); + unsigned InnerIndex = TypeMap.lookup(InnerType) - 1; + TypeDeps[InnerIndex].NumDeps++; + } + } + array_pod_sort(TypeDeps.begin(), TypeDeps.end(), CompareByDeps); + + SmallPtrSet<const Type*, 16> Visited; + Types.clear(); + Types.reserve(NumTypes); + for (unsigned I = 0; I < NumTypes; ++I) { + VisitType(TypeDeps[I].Ty, Visited, Types); + } } unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { @@ -319,7 +363,7 @@ void ValueEnumerator::EnumerateValue(const Value *V) { // Initializers for globals are handled explicitly elsewhere. } else if (isa<ConstantArray>(C) && cast<ConstantArray>(C)->isString()) { // Do not enumerate the initializers for an array of simple characters. - // The initializers just polute the value table, and we emit the strings + // The initializers just pollute the value table, and we emit the strings // specially. } else if (C->getNumOperands()) { // If a constant has operands, enumerate them. This makes sure that if a @@ -352,14 +396,12 @@ void ValueEnumerator::EnumerateValue(const Value *V) { void ValueEnumerator::EnumerateType(const Type *Ty) { unsigned &TypeID = TypeMap[Ty]; - if (TypeID) { - // If we've already seen this type, just increase its occurrence count. - Types[TypeID-1].second++; + // We've already seen this type. + if (TypeID) return; - } // First time we saw this type, add it. - Types.push_back(std::make_pair(Ty, 1U)); + Types.push_back(Ty); TypeID = Types.size(); // Enumerate subtypes. @@ -381,7 +423,7 @@ void ValueEnumerator::EnumerateOperandType(const Value *V) { // This constant may have operands, make sure to enumerate the types in // them. for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { - const User *Op = C->getOperand(i); + const Value *Op = C->getOperand(i); // Don't enumerate basic blocks here, this happens as operands to // blockaddress. diff --git a/lib/Bitcode/Writer/ValueEnumerator.h b/lib/Bitcode/Writer/ValueEnumerator.h index cd1d237..1e42a26 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.h +++ b/lib/Bitcode/Writer/ValueEnumerator.h @@ -36,8 +36,7 @@ class MDSymbolTable; class ValueEnumerator { public: - // For each type, we remember its Type* and occurrence frequency. - typedef std::vector<std::pair<const Type*, unsigned> > TypeList; + typedef std::vector<const Type*> TypeList; // For each value, we remember its Value* and occurrence frequency. typedef std::vector<std::pair<const Value*, unsigned> > ValueList; @@ -136,6 +135,7 @@ public: private: void OptimizeConstants(unsigned CstStart, unsigned CstEnd); + void OptimizeTypes(); void EnumerateMDNodeOperands(const MDNode *N); void EnumerateMetadata(const Value *MD); |