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..c266d6010d49c05de7616d15222331feb889aa8a 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,11 @@ static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
 
 /// NaClValueEnumerator - Enumerate module-level information.
 NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
+  // Create map for counting frequency of types, and set feild
+  // TypeCountMap accordingly. Let OptimizeTypes call (below) reset
+  // TypeCountMap to NULL, once collected information has been used.
+  TypeCountMapType count_map;
+  TypeCountMap = &count_map;

[Derek Schuff, 2013/05/02 15:41:45]

it's weird having this extra pointer and having NULL be a special meaning, when
the structure itself is also local. Just use the local structure directly, and
instead of having a NULL pointer, just use a boolean with a more helpful name.

[Karl, 2013/05/15 20:12:20]

The point wasn't just that it is NULL, but that it is referenced nonlocally 
through method calls. As such, it needs to be a field. Added a comment to try
and explain this.

   // Enumerate the global variables.
   for (Module::const_global_iterator I = M->global_begin(),
          E = M->global_end(); I != E; ++I)
@@ -61,7 +68,7 @@ NaClValueEnumerator::NaClValueEnumerator(const Module *M) {
        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);
@@ -106,10 +113,58 @@ 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.
+  TypeCountMap = NULL;
+  Types.clear();
+  TypeMap.clear();
+
+  // Start by adding Common integer types.
+  EnumerateType(Type::getInt1Ty(M->getContext()));
+  EnumerateType(Type::getInt8Ty(M->getContext()));

[jvoung (off chromium), 2013/05/02 16:35:40]

So these primitive types weren't already part of the TypeCountMap?  It would be
nice if they were automatically tracked also, then we wouldn't have to worry
about remembering to add the "half" type or not.  It would just have a count of
0 if the program never had any "half" types.

[Karl, 2013/05/15 20:12:20]

Reasonable point. Restructured code to make sure we only add the type if it is
used.

[jvoung (off chromium), 2013/05/15 21:01:36]

Do they not get counted in the type_counts then?  If so, I don't see why they
need to be given put ahead of the other types.  The sorting would fall out
naturally from the type_counts map?

E.g., what if i16 is actually rare compared to i32, why should i16 come first
(even though, yes the order of the first N types probably doesn't matter so
much)?

It's more about having less special code.

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

The point of explicitly ordering was to (in the future) shrink the bit width
needed for integer/floating point operations. I may be presuming too much here.

Not to presume, I'll remove this until I'm actually ready to change binary
integer/floating operations. That way, I'll have a better feel for whether this
is a good assumption.

+  EnumerateType(Type::getInt16Ty(M->getContext()));
+  EnumerateType(Type::getInt32Ty(M->getContext()));
+  EnumerateType(Type::getInt64Ty(M->getContext()));
+
+  // Add common float types.
+  // Note: This list is specific to NaCL, and one may want to use a
+  // more complete list if adding to LLVM bitcode format.
+  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 +407,25 @@ void NaClValueEnumerator::EnumerateValue(const Value *V) {
 
 
 void NaClValueEnumerator::EnumerateType(Type *Ty) {
+  // 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, 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 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;
@@ -365,11 +437,23 @@ void NaClValueEnumerator::EnumerateType(Type *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.

[jvoung (off chromium), 2013/05/02 16:35:40]

Is there a test that would demonstrate this waste vs savings, to make sure that
this is working?

[Karl, 2013/05/15 20:12:20]

Ok. Done.

+  bool EnumerateSubtypes = true;
+  if (TypeCountMap == NULL)
+    if (PointerType *PTy = dyn_cast<PointerType>(Ty))
+      if (StructType *STy = dyn_cast<StructType>(PTy))

[jvoung (off chromium), 2013/05/02 16:35:40]

Unless I'm reading this wrong, it still seems like it isn't possible to enter
this branch and set EnumerateSubtypes to false.

You're just casting Ty -> PTy -> STy, and it's all the same value, right?  If
you wanted the pointed-to-value's Type, you would need to cast
PTy->getElementType(), instead of PTy?

[Karl, 2013/05/15 20:12:20]

Your right. I fixed it. It definitely wasn't firing (you can easily see the
savings with pnacl_translate.pexe).

+        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 +622,3 @@ unsigned NaClValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const
   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
   return getGlobalBasicBlockID(BB);
 }
-