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.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36742 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 48 insertions, 5 deletions

diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp
index c903485b1a..6b753b2386 100644
--- a/lib/Bitcode/Writer/ValueEnumerator.cpp
+++ b/lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -24,6 +24,10 @@ static bool isFirstClassType(const std::pair<const llvm::Type*,
   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 @@ ValueEnumerator::ValueEnumerator(const Module *M) {
        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 @@ 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);
@@ -95,15 +105,43 @@ ValueEnumerator::ValueEnumerator(const Module *M) {
   // 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 @@ void ValueEnumerator::incorporateFunction(const Function &F) {
     ValueMap[BB] = BasicBlocks.size();
   }
   
+  // Optimize the constant layout.
+  OptimizeConstants(FirstFuncConstantID, Values.size());
+  
   FirstInstID = Values.size();
   
   // Add all of the instructions.
diff --git a/lib/Bitcode/Writer/ValueEnumerator.h b/lib/Bitcode/Writer/ValueEnumerator.h
index 3d3cbff8d0..1e8e8e81e1 100644
--- a/lib/Bitcode/Writer/ValueEnumerator.h
+++ b/lib/Bitcode/Writer/ValueEnumerator.h
@@ -110,6 +110,8 @@ public:
   void purgeFunction();
 
 private:
+  void OptimizeConstants(unsigned CstStart, unsigned CstEnd);
+    
   void EnumerateValue(const Value *V);
   void EnumerateType(const Type *T);
   void EnumerateParamAttrs(const ParamAttrsList *PAL);