Bye, Bye Compaction Tables. The benefit compaction tables provides doesn't

outweight its computational costs. This patch removes all compaction
table handling from the bcreader and bcwriter. For the record, here's the
difference betweeen having and not having compaction tables for some tests:

Test             With       Without   Size Chg
Olden/mst       5,602         5,598      +0.1%
viterbi        18,026        17,795      +1.3%
obsequi       162,133       166,663      -2.8%
burg          224,090       228,148      -1.8%
kimwitu++   4,933,263     5,121,159      -3.8%
176.gcc     8,470,424     9,141,539      -7.3%

It seems that it is more beneficial to larger files, but even on the largest
test case we have (176.gcc) it only amounts ot an I/O saving of 7.3%.


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

3 files changed, 19 insertions, 230 deletions

diff --git a/lib/Bytecode/Reader/Analyzer.cpp b/lib/Bytecode/Reader/Analyzer.cpp
index c86db26a92..64907a8e80 100644
--- a/lib/Bytecode/Reader/Analyzer.cpp
+++ b/lib/Bytecode/Reader/Analyzer.cpp
@@ -100,7 +100,6 @@ public:
     bca.BlockSizes[BytecodeFormat::ModuleGlobalInfoBlockID] = 0;
     bca.BlockSizes[BytecodeFormat::GlobalTypePlaneBlockID] = 0;
     bca.BlockSizes[BytecodeFormat::InstructionListBlockID] = 0;
-    bca.BlockSizes[BytecodeFormat::CompactionTableBlockID] = 0;
     bca.BlockSizes[BytecodeFormat::TypeSymbolTableBlockID] = 0;
   }
 
@@ -635,9 +634,6 @@ void PrintBytecodeAnalysis(BytecodeAnalysis& bca, std::ostream& Out )
   print(Out, "Instruction List Bytes",
         double(bca.BlockSizes[BytecodeFormat::InstructionListBlockID]),
         double(bca.byteSize));
-  print(Out, "Compaction Table Bytes",
-        double(bca.BlockSizes[BytecodeFormat::CompactionTableBlockID]),
-        double(bca.byteSize));
   print(Out, "Value Symbol Table Bytes",
         double(bca.BlockSizes[BytecodeFormat::ValueSymbolTableBlockID]),
         double(bca.byteSize));
diff --git a/lib/Bytecode/Reader/Reader.cpp b/lib/Bytecode/Reader/Reader.cpp
index b94139482c..718ba3e800 100644
--- a/lib/Bytecode/Reader/Reader.cpp
+++ b/lib/Bytecode/Reader/Reader.cpp
@@ -186,8 +186,8 @@ inline bool BytecodeReader::hasImplicitNull(unsigned TyID) {
   return TyID != Type::LabelTyID && TyID != Type::VoidTyID;
 }
 
-/// Obtain a type given a typeid and account for things like compaction tables,
-/// function level vs module level, and the offsetting for the primitive types.
+/// Obtain a type given a typeid and account for things like function level vs 
+/// module level, and the offsetting for the primitive types.
 const Type *BytecodeReader::getType(unsigned ID) {
   if (ID <= Type::LastPrimitiveTyID)
     if (const Type *T = Type::getPrimitiveType((Type::TypeID)ID))
@@ -196,12 +196,6 @@ const Type *BytecodeReader::getType(unsigned ID) {
   // Otherwise, derived types need offset...
   ID -= Type::FirstDerivedTyID;
 
-  if (!CompactionTypes.empty()) {
-    if (ID >= CompactionTypes.size())
-      error("Type ID out of range for compaction table!");
-    return CompactionTypes[ID].first;
-  }
-
   // Is it a module-level type?
   if (ID < ModuleTypes.size())
     return ModuleTypes[ID].get();
@@ -223,20 +217,11 @@ inline const Type* BytecodeReader::readType() {
 }
 
 /// Get the slot number associated with a type accounting for primitive
-/// types, compaction tables, and function level vs module level.
+/// types and function level vs module level.
 unsigned BytecodeReader::getTypeSlot(const Type *Ty) {
   if (Ty->isPrimitiveType())
     return Ty->getTypeID();
 
-  // Scan the compaction table for the type if needed.
-  if (!CompactionTypes.empty()) {
-    for (unsigned i = 0, e = CompactionTypes.size(); i != e; ++i)
-      if (CompactionTypes[i].first == Ty)
-        return Type::FirstDerivedTyID + i;
-
-    error("Couldn't find type specified in compaction table!");
-  }
-
   // Check the function level types first...
   TypeListTy::iterator I = std::find(FunctionTypes.begin(),
                                      FunctionTypes.end(), Ty);
@@ -266,86 +251,30 @@ unsigned BytecodeReader::getTypeSlot(const Type *Ty) {
   return Type::FirstDerivedTyID + IT->second;
 }
 
-/// This is just like getType, but when a compaction table is in use, it is
-/// ignored.  It also ignores function level types.
-/// @see getType
-const Type *BytecodeReader::getGlobalTableType(unsigned Slot) {
-  if (Slot < Type::FirstDerivedTyID) {
-    const Type *Ty = Type::getPrimitiveType((Type::TypeID)Slot);
-    if (!Ty)
-      error("Not a primitive type ID?");
-    return Ty;
-  }
-  Slot -= Type::FirstDerivedTyID;
-  if (Slot >= ModuleTypes.size())
-    error("Illegal compaction table type reference!");
-  return ModuleTypes[Slot];
-}
-
-/// This is just like getTypeSlot, but when a compaction table is in use, it
-/// is ignored. It also ignores function level types.
-unsigned BytecodeReader::getGlobalTableTypeSlot(const Type *Ty) {
-  if (Ty->isPrimitiveType())
-    return Ty->getTypeID();
-  
-  // If we don't have our cache yet, build it now.
-  if (ModuleTypeIDCache.empty()) {
-    unsigned N = 0;
-    ModuleTypeIDCache.reserve(ModuleTypes.size());
-    for (TypeListTy::iterator I = ModuleTypes.begin(), E = ModuleTypes.end();
-         I != E; ++I, ++N)
-      ModuleTypeIDCache.push_back(std::make_pair(*I, N));
-    
-    std::sort(ModuleTypeIDCache.begin(), ModuleTypeIDCache.end());
-  }
-  
-  // Binary search the cache for the entry.
-  std::vector<std::pair<const Type*, unsigned> >::iterator IT =
-    std::lower_bound(ModuleTypeIDCache.begin(), ModuleTypeIDCache.end(),
-                     std::make_pair(Ty, 0U));
-  if (IT == ModuleTypeIDCache.end() || IT->first != Ty)
-    error("Didn't find type in ModuleTypes.");
-  
-  return Type::FirstDerivedTyID + IT->second;
-}
-
 /// Retrieve a value of a given type and slot number, possibly creating
 /// it if it doesn't already exist.
 Value * BytecodeReader::getValue(unsigned type, unsigned oNum, bool Create) {
   assert(type != Type::LabelTyID && "getValue() cannot get blocks!");
   unsigned Num = oNum;
 
-  // If there is a compaction table active, it defines the low-level numbers.
-  // If not, the module values define the low-level numbers.
-  if (CompactionValues.size() > type && !CompactionValues[type].empty()) {
-    if (Num < CompactionValues[type].size())
-      return CompactionValues[type][Num];
-    Num -= CompactionValues[type].size();
-  } else {
-    // By default, the global type id is the type id passed in
-    unsigned GlobalTyID = type;
-
-    // If the type plane was compactified, figure out the global type ID by
-    // adding the derived type ids and the distance.
-    if (!CompactionTypes.empty() && type >= Type::FirstDerivedTyID)
-      GlobalTyID = CompactionTypes[type-Type::FirstDerivedTyID].second;
-
-    if (hasImplicitNull(GlobalTyID)) {
-      const Type *Ty = getType(type);
-      if (!isa<OpaqueType>(Ty)) {
-        if (Num == 0)
-          return Constant::getNullValue(Ty);
-        --Num;
-      }
-    }
+  // By default, the global type id is the type id passed in
+  unsigned GlobalTyID = type;
 
-    if (GlobalTyID < ModuleValues.size() && ModuleValues[GlobalTyID]) {
-      if (Num < ModuleValues[GlobalTyID]->size())
-        return ModuleValues[GlobalTyID]->getOperand(Num);
-      Num -= ModuleValues[GlobalTyID]->size();
+  if (hasImplicitNull(GlobalTyID)) {
+    const Type *Ty = getType(type);
+    if (!isa<OpaqueType>(Ty)) {
+      if (Num == 0)
+        return Constant::getNullValue(Ty);
+      --Num;
     }
   }
 
+  if (GlobalTyID < ModuleValues.size() && ModuleValues[GlobalTyID]) {
+    if (Num < ModuleValues[GlobalTyID]->size())
+      return ModuleValues[GlobalTyID]->getOperand(Num);
+    Num -= ModuleValues[GlobalTyID]->size();
+  }
+
   if (FunctionValues.size() > type &&
       FunctionValues[type] &&
       Num < FunctionValues[type]->size())
@@ -370,38 +299,6 @@ Value * BytecodeReader::getValue(unsigned type, unsigned oNum, bool Create) {
   return 0; // just silence warning, error calls longjmp
 }
 
-/// This is just like getValue, but when a compaction table is in use, it
-/// is ignored.  Also, no forward references or other fancy features are
-/// supported.
-Value* BytecodeReader::getGlobalTableValue(unsigned TyID, unsigned SlotNo) {
-  if (SlotNo == 0)
-    return Constant::getNullValue(getType(TyID));
-
-  if (!CompactionTypes.empty() && TyID >= Type::FirstDerivedTyID) {
-    TyID -= Type::FirstDerivedTyID;
-    if (TyID >= CompactionTypes.size())
-      error("Type ID out of range for compaction table!");
-    TyID = CompactionTypes[TyID].second;
-  }
-
-  --SlotNo;
-
-  if (TyID >= ModuleValues.size() || ModuleValues[TyID] == 0 ||
-      SlotNo >= ModuleValues[TyID]->size()) {
-    if (TyID >= ModuleValues.size() || ModuleValues[TyID] == 0)
-      error("Corrupt compaction table entry!"
-            + utostr(TyID) + ", " + utostr(SlotNo) + ": "
-            + utostr(ModuleValues.size()));
-    else
-      error("Corrupt compaction table entry!"
-            + utostr(TyID) + ", " + utostr(SlotNo) + ": "
-            + utostr(ModuleValues.size()) + ", "
-            + utohexstr(reinterpret_cast<uint64_t>(((void*)ModuleValues[TyID])))
-            + ", "
-            + utostr(ModuleValues[TyID]->size()));
-  }
-  return ModuleValues[TyID]->getOperand(SlotNo);
-}
 
 /// Just like getValue, except that it returns a null pointer
 /// only on error.  It always returns a constant (meaning that if the value is
@@ -1079,76 +976,6 @@ void BytecodeReader::ParseValueSymbolTable(Function *CurrentFunction,
   if (Handler) Handler->handleSymbolTableEnd();
 }
 
-/// Read in the types portion of a compaction table.
-void BytecodeReader::ParseCompactionTypes(unsigned NumEntries) {
-  for (unsigned i = 0; i != NumEntries; ++i) {
-    unsigned TypeSlot = read_vbr_uint();
-    const Type *Typ = getGlobalTableType(TypeSlot);
-    CompactionTypes.push_back(std::make_pair(Typ, TypeSlot));
-    if (Handler) Handler->handleCompactionTableType(i, TypeSlot, Typ);
-  }
-}
-
-/// Parse a compaction table.
-void BytecodeReader::ParseCompactionTable() {
-
-  // Notify handler that we're beginning a compaction table.
-  if (Handler) Handler->handleCompactionTableBegin();
-
-  // Get the types for the compaction table.
-  unsigned NumEntries = read_vbr_uint();
-  ParseCompactionTypes(NumEntries);
-
-  // Compaction tables live in separate blocks so we have to loop
-  // until we've read the whole thing.
-  while (moreInBlock()) {
-    // Read the number of Value* entries in the compaction table
-    unsigned NumEntries = read_vbr_uint();
-    unsigned Ty = 0;
-
-    // Decode the type from value read in. Most compaction table
-    // planes will have one or two entries in them. If that's the
-    // case then the length is encoded in the bottom two bits and
-    // the higher bits encode the type. This saves another VBR value.
-    if ((NumEntries & 3) == 3) {
-      // In this case, both low-order bits are set (value 3). This
-      // is a signal that the typeid follows.
-      NumEntries >>= 2;
-      Ty = read_vbr_uint();
-    } else {
-      // In this case, the low-order bits specify the number of entries
-      // and the high order bits specify the type.
-      Ty = NumEntries >> 2;
-      NumEntries &= 3;
-    }
-
-    // Make sure we have enough room for the plane.
-    if (Ty >= CompactionValues.size())
-      CompactionValues.resize(Ty+1);
-
-    // Make sure the plane is empty or we have some kind of error.
-    if (!CompactionValues[Ty].empty())
-      error("Compaction table plane contains multiple entries!");
-
-    // Notify handler about the plane.
-    if (Handler) Handler->handleCompactionTablePlane(Ty, NumEntries);
-
-    // Push the implicit zero.
-    CompactionValues[Ty].push_back(Constant::getNullValue(getType(Ty)));
-
-    // Read in each of the entries, put them in the compaction table
-    // and notify the handler that we have a new compaction table value.
-    for (unsigned i = 0; i != NumEntries; ++i) {
-      unsigned ValSlot = read_vbr_uint();
-      Value *V = getGlobalTableValue(Ty, ValSlot);
-      CompactionValues[Ty].push_back(V);
-      if (Handler) Handler->handleCompactionTableValue(i, Ty, ValSlot);
-    }
-  }
-  // Notify handler that the compaction table is done.
-  if (Handler) Handler->handleCompactionTableEnd();
-}
-
 // Parse a single type. The typeid is read in first. If its a primitive type
 // then nothing else needs to be read, we know how to instantiate it. If its
 // a derived type, then additional data is read to fill out the type
@@ -1667,8 +1494,7 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
     case BytecodeFormat::ConstantPoolBlockID:
       if (!InsertedArguments) {
         // Insert arguments into the value table before we parse the first basic
-        // block in the function, but after we potentially read in the
-        // compaction table.
+        // block in the function
         insertArguments(F);
         InsertedArguments = true;
       }
@@ -1676,14 +1502,9 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
       ParseConstantPool(FunctionValues, FunctionTypes, true);
       break;
 
-    case BytecodeFormat::CompactionTableBlockID:
-      ParseCompactionTable();
-      break;
-
     case BytecodeFormat::InstructionListBlockID: {
       // Insert arguments into the value table before we parse the instruction
-      // list for the function, but after we potentially read in the compaction
-      // table.
+      // list for the function
       if (!InsertedArguments) {
         insertArguments(F);
         InsertedArguments = true;
@@ -1732,8 +1553,6 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
 
   // Clear out function-level types...
   FunctionTypes.clear();
-  CompactionTypes.clear();
-  CompactionValues.clear();
   freeTable(FunctionValues);
 
   if (Handler) Handler->handleFunctionEnd(F);
diff --git a/lib/Bytecode/Reader/Reader.h b/lib/Bytecode/Reader/Reader.h
index 3e64f2d027..92c8fa0225 100644
--- a/lib/Bytecode/Reader/Reader.h
+++ b/lib/Bytecode/Reader/Reader.h
@@ -212,12 +212,6 @@ protected:
   ///  @brief Parse a function body
   void ParseFunctionBody(Function* Func);
 
-  /// @brief Parse the type list portion of a compaction table
-  void ParseCompactionTypes(unsigned NumEntries);
-
-  /// @brief Parse a compaction table
-  void ParseCompactionTable();
-
   /// @brief Parse global types
   void ParseGlobalTypes();
 
@@ -275,15 +269,6 @@ private:
   ///
   unsigned char RevisionNum;        // The rev # itself
 
-  /// CompactionTypes - If a compaction table is active in the current function,
-  /// this is the mapping that it contains.  We keep track of what resolved type
-  /// it is as well as what global type entry it is.
-  std::vector<std::pair<const Type*, unsigned> > CompactionTypes;
-
-  /// @brief If a compaction table is active in the current function,
-  /// this is the mapping that it contains.
-  std::vector<std::vector<Value*> > CompactionValues;
-
   /// @brief This vector is used to deal with forward references to types in
   /// a module.
   TypeListTy ModuleTypes;
@@ -363,23 +348,12 @@ private:
   /// @brief Converts a Type* to its type slot number
   unsigned getTypeSlot(const Type *Ty);
 
-  /// @brief Converts a normal type slot number to a compacted type slot num.
-  unsigned getCompactionTypeSlot(unsigned type);
-
   /// @brief Gets the global type corresponding to the TypeId
   const Type *getGlobalTableType(unsigned TypeId);
 
-  /// This is just like getTypeSlot, but when a compaction table is in use,
-  /// it is ignored.
-  unsigned getGlobalTableTypeSlot(const Type *Ty);
-
   /// @brief Get a value from its typeid and slot number
   Value* getValue(unsigned TypeID, unsigned num, bool Create = true);
 
-  /// @brief Get a value from its type and slot number, ignoring compaction
-  /// tables.
-  Value *getGlobalTableValue(unsigned TyID, unsigned SlotNo);
-
   /// @brief Get a basic block for current function
   BasicBlock *getBasicBlock(unsigned ID);