Changes in directory llvm/lib/Bitcode/Writer:
ValueEnumerator.cpp updated: 1.10 -> 1.11 ValueEnumerator.h updated: 1.9 -> 1.10 --- Log message: optimize constant layout. This fixes encoding of 181.mcf (by ensuring integer structure idx's are emitted before constant expr geps) and shrinks files slightly. For example kc++ shrinks from 4326188 to 4240128 bytes. --- Diffs of the changes: (+48 -5) ValueEnumerator.cpp | 51 ++++++++++++++++++++++++++++++++++++++++++++++----- ValueEnumerator.h | 2 ++ 2 files changed, 48 insertions(+), 5 deletions(-) Index: llvm/lib/Bitcode/Writer/ValueEnumerator.cpp diff -u llvm/lib/Bitcode/Writer/ValueEnumerator.cpp:1.10 llvm/lib/Bitcode/Writer/ValueEnumerator.cpp:1.11 --- llvm/lib/Bitcode/Writer/ValueEnumerator.cpp:1.10 Fri May 4 00:05:48 2007 +++ llvm/lib/Bitcode/Writer/ValueEnumerator.cpp Fri May 4 00:21:47 2007 @@ -24,6 +24,10 @@ return P.first->isFirstClassType(); } +static bool isIntegerValue(const std::pair<const Value*, unsigned> &V) { + return isa<IntegerType>(V.first->getType()); +} + static bool CompareByFrequency(const std::pair<const llvm::Type*, unsigned int> &P1, const std::pair<const llvm::Type*, @@ -47,6 +51,9 @@ I != E; ++I) EnumerateValue(I); + // Remember what is the cutoff between globalvalue's and other constants. + unsigned FirstConstant = Values.size(); + // Enumerate the global variable initializers. for (Module::const_global_iterator I = M->global_begin(), E = M->global_end(); I != E; ++I) @@ -83,6 +90,9 @@ } } + // 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); @@ -95,15 +105,43 @@ // 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; - - // FIXME: Emit a marker into the module indicating which aggregates types can - // be dropped form the table. // FIXME: Sort value tables by frequency. - - // FIXME: Sort constants by type to reduce size. } +// Optimize constant ordering. +struct CstSortPredicate { + ValueEnumerator &VE; + CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} + bool operator()(const std::pair<const Value*, unsigned> &LHS, + const std::pair<const Value*, unsigned> &RHS) { + // Sort by plane. + if (LHS.first->getType() != RHS.first->getType()) + return VE.getTypeID(LHS.first->getType()) < + VE.getTypeID(RHS.first->getType()); + // Then by frequency. + return LHS.second > RHS.second; + } +}; + +/// OptimizeConstants - Reorder constant pool for denser encoding. +void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { + if (CstStart == CstEnd || CstStart+1 == CstEnd) return; + + CstSortPredicate P(*this); + std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); + + // Ensure that integer constants are at the start of the constant pool. This + // is important so that GEP structure indices come before gep constant exprs. + std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, + isIntegerValue); + + // Rebuild the modified portion of ValueMap. + for (; CstStart != CstEnd; ++CstStart) + ValueMap[Values[CstStart].first] = CstStart+1; +} + + /// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol /// table. void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) { @@ -225,6 +263,9 @@ ValueMap[BB] = BasicBlocks.size(); } + // Optimize the constant layout. + OptimizeConstants(FirstFuncConstantID, Values.size()); + FirstInstID = Values.size(); // Add all of the instructions. Index: llvm/lib/Bitcode/Writer/ValueEnumerator.h diff -u llvm/lib/Bitcode/Writer/ValueEnumerator.h:1.9 llvm/lib/Bitcode/Writer/ValueEnumerator.h:1.10 --- llvm/lib/Bitcode/Writer/ValueEnumerator.h:1.9 Thu May 3 19:45:24 2007 +++ llvm/lib/Bitcode/Writer/ValueEnumerator.h Fri May 4 00:21:47 2007 @@ -110,6 +110,8 @@ void purgeFunction(); private: + void OptimizeConstants(unsigned CstStart, unsigned CstEnd); + void EnumerateValue(const Value *V); void EnumerateType(const Type *T); void EnumerateParamAttrs(const ParamAttrsList *PAL); _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits