Create type IDs based on reference counts.

lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp

Index: lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
diff --git a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
index 4ac34daa9620d91a1f288cf92b02fb72e70c349a..bded4742800457a97f9fde06cdd9089ebd55a64e 100644
--- a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
+++ b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
@@ -23,6 +23,8 @@
 #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) {
@@ -31,6 +33,7 @@ static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
 
 /// NaClValueEnumerator - Enumerate module-level information.
 NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
+  TypeCountMap = new TypeCountMapType();

[jvoung (off chromium), 2013/04/29 18:35:42]

see question about whether this really needs to be a pointer?

[Karl, 2013/04/29 22:19:16]

As mentioned in the header file, this is only needed during initial collection,
and therefore can be removed once the initial assignment to type ID's is done.

I didn't see an easy way to pass this local collector through method calls, and
guarantee that they are right. So I didn't make it a method argument, but a
field on the enumerator class.

However, since the scope of this is within this routine, I'm changing it to use
a local instead of a new. 

   // Enumerate the global variables.
   for (Module::const_global_iterator I = M->global_begin(),
          E = M->global_end(); I != E; ++I)
@@ -106,10 +109,60 @@ NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
       }
   }
 
+  // Optimized type indicies to put "common" expected types in with small
+  // indices.
+  OptimizeTypes(M);
+
   // 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.
+  std::set<unsigned> type_counts;
+  typedef std::set<Type*> TypeSetType;
+  std::map<unsigned, TypeSetType> usage_count_map;
+
+  for (TypeCountMapType::iterator iter = TypeCountMap->begin();
+       iter != TypeCountMap->end(); ++ iter) {
+    type_counts.insert(iter->second);
+    usage_count_map[iter->second].insert(iter->first);
+  }
+
+  // Reset type tracking maps, so that we can re-enter based
+  // on fequency ordering.
+  delete TypeCountMap;
+  TypeCountMap = NULL;
+  Types.clear();
+  TypeMap.clear();
+
+  // Start by adding Common integer types.
+  EnumerateType(Type::getInt1Ty(M->getContext()));
+  EnumerateType(Type::getInt8Ty(M->getContext()));
+  EnumerateType(Type::getInt16Ty(M->getContext()));
+  EnumerateType(Type::getInt32Ty(M->getContext()));
+  EnumerateType(Type::getInt64Ty(M->getContext()));
+
+  // Add common float types.
+  FirstFloatTypeID = TypeMap.size();

[jvoung (off chromium), 2013/04/29 18:35:42]

why can't FirstFloatTypeID just be a local variable?

[Karl, 2013/04/29 22:19:16]

Removed, since we don't use value yet.

+  assert(FirstFloatTypeID == 5 && "Float first type id wrong!");
+  EnumerateType(Type::getHalfTy(M->getContext()));

[Derek Schuff, 2013/04/29 19:38:42]

half types are not allowed in the pnacl ABI. so if we go upstream this should
probably stay, but otherwise it can go.

[Karl, 2013/04/29 22:19:16]

Note: Since these types are specific to NaCl, I will drop half type.

+  EnumerateType(Type::getFloatTy(M->getContext()));
+  EnumerateType(Type::getDoubleTy(M->getContext()));
+
+  // Insert remaining 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(*type_iter);
+    }
+  }
+}
+
 unsigned NaClValueEnumerator::getInstructionID(const Instruction *Inst) const {
   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
   assert(I != InstructionMap.end() && "Instruction is not mapped!");
@@ -352,8 +405,25 @@ void NaClValueEnumerator::EnumerateValue(const Value *V) {
 
 
 void NaClValueEnumerator::EnumerateType(Type *Ty) {
+  // This function is used to enumerate types referenced by the given
+  // type. This function is called in two phases, based on the value
+  // of TypeCountMap. These phases are:
+  //
+  // (1) In this phase, TypeCountMap!=NULL. 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, TypeCountMap==NUll. We are registering types based on

[jvoung (off chromium), 2013/04/29 18:35:42]

NUll -> NULL

[Karl, 2013/04/29 22:19:16]

Done.

+  // frequency. To miniize type IDs for frequently used types, (unlike

[Derek Schuff, 2013/04/29 19:38:42]

miniize->minimize

[Karl, 2013/04/29 22:19:16]

Done.

+  // the other two contextx) we are inserting the minimal (implicitly)

[jvoung (off chromium), 2013/04/29 18:35:42]

contextx -> contexts

[Karl, 2013/04/29 22:19:16]

Done.

+  // referenced types needed for each type.
   unsigned *TypeID = &TypeMap[Ty];
 
+  if (TypeCountMap) ++((*TypeCountMap)[Ty]);
+
   // We've already seen this type.
   if (*TypeID)
     return;
@@ -361,15 +431,27 @@ void NaClValueEnumerator::EnumerateType(Type *Ty) {
   // 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.
+  bool EnumerateSubtypes = true;

[jvoung (off chromium), 2013/04/29 18:35:42]

move variable decl to under the comment about "If in the second phase... " ?

[Karl, 2013/04/29 22:19:16]

Done.

   if (StructType *STy = dyn_cast<StructType>(Ty))
     if (!STy->isLiteral())
       *TypeID = ~0U;
 
+  // If in the second phase, 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.
+  if (TypeCountMap == NULL)
+    if (PointerType *PTy = dyn_cast<PointerType>(Ty))
+      if (StructType *STy = dyn_cast<StructType>(Ty))

[jvoung (off chromium), 2013/04/29 18:35:42]

Is this really supposed to be "Ty" in both casts?  How can "Ty" be both a
PointerType and a StructType?  Don't you need to get the pointed-to-type from
PTy?

[Karl, 2013/04/29 22:19:16]

Good point. Fixing.

+        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);
+  }
 
   // Refresh the TypeID pointer in case the table rehashed.
   TypeID = &TypeMap[Ty];
@@ -538,4 +620,3 @@ unsigned NaClValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const
   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
   return getGlobalBasicBlockID(BB);
 }
-