summaryrefslogtreecommitdiffstats
path: root/lib/Bitcode/Writer
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Bitcode/Writer')
-rw-r--r--lib/Bitcode/Writer/BitcodeWriter.cpp2
-rw-r--r--lib/Bitcode/Writer/ValueEnumerator.cpp98
-rw-r--r--lib/Bitcode/Writer/ValueEnumerator.h4
3 files changed, 73 insertions, 31 deletions
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);
OpenPOWER on IntegriCloud