Create type IDs based on reference counts.

lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp

 //===-- NaClValueEnumerator.cpp ------------------------------------------===//
 //     Number values and types for bitcode writer
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the NaClValueEnumerator class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "NaClValueEnumerator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueSymbolTable.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
+#include <set>
+
 using namespace llvm;
 
 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
   return V.first->getType()->isIntOrIntVectorTy();
 }
 
 /// NaClValueEnumerator - Enumerate module-level information.
 NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
+  // Create map for counting frequency of types, and set field
+  // TypeCountMap accordingly.  Note: Pointer field TypeCountMap is
+  // used to deal with the fact that types are added through various
+  // method calls in this routine. Rather than pass it as an argument,
+  // we use a field. The field is a pointer so that the memory
+  // footprint of count_map can be garbage collected when this
+  // constructor completes.
+  TypeCountMapType count_map;
+  TypeCountMap = &count_map;
   // Enumerate the global variables.
   for (Module::const_global_iterator I = M->global_begin(),
          E = M->global_end(); I != E; ++I)
     EnumerateValue(I);
 
   // Enumerate the functions.
   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
     EnumerateValue(I);
     EnumerateAttributes(cast<Function>(I)->getAttributes());
   }
@@ skipping 10 matching lines @@
   for (Module::const_global_iterator I = M->global_begin(),
          E = M->global_end(); I != E; ++I)
     if (I->hasInitializer())
       EnumerateValue(I->getInitializer());
 
   // Enumerate the aliasees.
   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
        I != E; ++I)
     EnumerateValue(I->getAliasee());
 
-  // Insert constants and metadata that are named at module level into the slot 
+  // Insert constants and metadata that are named at module level into the slot
   // pool so that the module symbol table can refer to them...
   EnumerateValueSymbolTable(M->getValueSymbolTable());
   EnumerateNamedMetadata(M);
 
   SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
 
   // Enumerate types used by function bodies and argument lists.
   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
 
     for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
@@ skipping 24 matching lines @@
 
         if (!I->getDebugLoc().isUnknown()) {
           MDNode *Scope, *IA;
           I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext());
           if (Scope) EnumerateMetadata(Scope);
           if (IA) EnumerateMetadata(IA);
         }
       }
   }
 
+  // Optimized type indicies to put "common" expected types in with small
+  // indices.
+  OptimizeTypes(M);
+  TypeCountMap = NULL;
+
   // Optimize constant ordering.
   OptimizeConstants(FirstConstant, Values.size());
 }
 
+void NaClValueEnumerator::OptimizeTypes(const Module *M) {
+
+  // Sort types by count, so that we can index them based on
+  // frequency. Use indices of built TypeMap, so that order of
+  // construction is repeatable.

[Karl, 2013/05/20 21:48:51]

Changed the type of TypeSetType to be on unsigned, and stored the generated
index for each type. Did this so that type order is repeatable.

+  std::set<unsigned> type_counts;
+  typedef std::set<unsigned> TypeSetType;
+  std::map<unsigned, TypeSetType> usage_count_map;
+  TypeList IdType(Types);

[Karl, 2013/05/20 21:48:51]

Also added this so that we can look up types from  type ids.

+
+  for (TypeCountMapType::iterator iter = TypeCountMap->begin();
+       iter != TypeCountMap->end(); ++ iter) {
+    type_counts.insert(iter->second);
+    usage_count_map[iter->second].insert(TypeMap[iter->first]-1);
+  }
+
+  // Reset type tracking maps, so that we can re-enter based
+  // on fequency ordering.
+  TypeCountMap = NULL;
+  Types.clear();
+  TypeMap.clear();
+
+  // Reinsert types, based on frequency.
+  for (std::set<unsigned>::reverse_iterator count_iter = type_counts.rbegin();
+       count_iter != type_counts.rend(); ++count_iter) {
+    TypeSetType& count_types = usage_count_map[*count_iter];
+    for (TypeSetType::iterator type_iter = count_types.begin();
+         type_iter != count_types.end(); ++type_iter)
+      EnumerateType((IdType[*type_iter]), true);
+  }
+}
+
 unsigned NaClValueEnumerator::getInstructionID(const Instruction *Inst) const {
   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
   assert(I != InstructionMap.end() && "Instruction is not mapped!");
   return I->second;
 }
 
 void NaClValueEnumerator::setInstructionID(const Instruction *I) {
   InstructionMap[I] = InstructionCount++;
 }
 
@@ skipping 221 matching lines @@
       return;
     }
   }
 
   // Add the value.
   Values.push_back(std::make_pair(V, 1U));
   ValueID = Values.size();
 }
 
 
-void NaClValueEnumerator::EnumerateType(Type *Ty) {
+void NaClValueEnumerator::EnumerateType(Type *Ty, bool InsideOptimizeTypes) {
+  // This function is used to enumerate types referenced by the given
+  // module. This function is called in two phases, based on the value
+  // of TypeCountMap. These phases are:
+  //
+  // (1) In this phase, InsideOptimizeTypes=false. We are collecting types
+  // and all corresponding (implicitly) referenced types. In addition,
+  // we are keeping track of the number of references to each type in
+  // TypeCountMap. These reference counts will be used by method
+  // OptimizeTypes to associate the smallest type ID's with the most
+  // referenced types.
+  //
+  // (2) In this phase, InsideOptimizeTypes=true. We are registering types
+  // based on frequency. To minimize type IDs for frequently used
+  // types, (unlike the other context) we are inserting the minimal
+  // (implicitly) referenced types needed for each type.
   unsigned *TypeID = &TypeMap[Ty];
 
+  if (TypeCountMap) ++((*TypeCountMap)[Ty]);
+
   // We've already seen this type.
   if (*TypeID)
     return;
 
   // If it is a non-anonymous struct, mark the type as being visited so that we
   // don't recursively visit it.  This is safe because we allow forward
   // references of these in the bitcode reader.
   if (StructType *STy = dyn_cast<StructType>(Ty))
     if (!STy->isLiteral())
       *TypeID = ~0U;
 
+  // If in the second phase (i.e. inside optimize types), don't expand
+  // pointers to structures, since we can just generate a forward
+  // reference to it. This way, we don't use up unnecessary (small) ID
+  // values just to define the pointer.
+  bool EnumerateSubtypes = true;
+  if (InsideOptimizeTypes)
+    if (PointerType *PTy = dyn_cast<PointerType>(Ty))
+      if (StructType *STy = dyn_cast<StructType>(PTy->getElementType()))
+        if (!STy->isLiteral())
+          EnumerateSubtypes = false;
+
   // Enumerate all of the subtypes before we enumerate this type.  This ensures
   // that the type will be enumerated in an order that can be directly built.
-  for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
-       I != E; ++I)
-    EnumerateType(*I);
+  if (EnumerateSubtypes) {
+    for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
+         I != E; ++I)
+      EnumerateType(*I, InsideOptimizeTypes);
+  }
 
   // Refresh the TypeID pointer in case the table rehashed.
   TypeID = &TypeMap[Ty];
 
   // Check to see if we got the pointer another way.  This can happen when
   // enumerating recursive types that hit the base case deeper than they start.
   //
   // If this is actually a struct that we are treating as forward ref'able,
   // then emit the definition now that all of its contents are available.
   if (*TypeID && *TypeID != ~0U)
@@ skipping 148 matching lines @@
 /// specified basic block.  This is relatively expensive information, so it
 /// should only be used by rare constructs such as address-of-label.
 unsigned NaClValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
   unsigned &Idx = GlobalBasicBlockIDs[BB];
   if (Idx != 0)
     return Idx-1;
 
   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
   return getGlobalBasicBlockID(BB);
 }
-