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 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)
     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);
+
   // 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!");
   return I->second;
 }
 
 void NaClValueEnumerator::setInstructionID(const Instruction *I) {
   InstructionMap[I] = InstructionCount++;
 }
 
@@ skipping 222 matching lines @@
     }
   }
 
   // Add the value.
   Values.push_back(std::make_pair(V, 1U));
   ValueID = Values.size();
 }
 
 
 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;
 
   // 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, 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];
 
   // 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);
 }
-