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) {
+  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)
     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 55 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.
+  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!");
   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
+  // 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;
 
   // 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];
 
   // 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);
 }
-