Create type IDs based on reference counts.

lib/Bitcode/NaCl/Writer/NaClValueEnumerator.h

 //===-- Bitcode/NaCl/Writer/NaClValueEnumerator.h - ----------*- C++ -*-===//
 //      Number values.
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ skipping 24 matching lines @@
 class MDSymbolTable;
 class raw_ostream;
 
 class NaClValueEnumerator {
 public:
   typedef std::vector<Type*> TypeList;
 
   // For each value, we remember its Value* and occurrence frequency.
   typedef std::vector<std::pair<const Value*, unsigned> > ValueList;
 private:
+  // Defines unique ID's for each type.
   typedef DenseMap<Type*, unsigned> TypeMapType;
   TypeMapType TypeMap;
+  // Defines the number of references to each type. If defined,
+  // we are in the first pass of collecting types, and reference counts
+  // should be added to the map. If undefined, we are in the second pass
+  // that actually assigns type IDs, based on frequency counts found in
+  // the first pass.
+  typedef TypeMapType TypeCountMapType;
+  TypeCountMapType* TypeCountMap;

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

Does this need to be a pointer, or could it be allocated as part of the
ValueEnumerator, like TypeMap, ValueMap, etc.?

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

I did it this way because it is only needed during the first pass of the
construction of the type ID map. Once built, this space is wasted and should be
collected.

+
   TypeList Types;
 
   typedef DenseMap<const Value*, unsigned> ValueMapType;
   ValueMapType ValueMap;
   ValueList Values;
   ValueList MDValues;
   SmallVector<const MDNode *, 8> FunctionLocalMDs;
   ValueMapType MDValueMap;
 
   typedef DenseMap<AttributeSet, unsigned> AttributeGroupMapType;
@@ skipping 19 matching lines @@
   /// When a function is incorporated, this is the size of the Values list
   /// before incorporation.
   unsigned NumModuleValues;
 
   /// When a function is incorporated, this is the size of the MDValues list
   /// before incorporation.
   unsigned NumModuleMDValues;
 
   unsigned FirstFuncConstantID;
   unsigned FirstInstID;
+  unsigned FirstFloatTypeID;

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

why are float types singled out?

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

I was looking ahead to "float" operations, which can subtract this value from
the type id. However, since I'm not adding that, I will remove it until it is
needed.

 
   NaClValueEnumerator(const NaClValueEnumerator &) LLVM_DELETED_FUNCTION;
   void operator=(const NaClValueEnumerator &) LLVM_DELETED_FUNCTION;
 public:
   NaClValueEnumerator(const Module *M);
 
   void dump() const;
   void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const;
 
   unsigned getValueID(const Value *V) const;
@@ skipping 49 matching lines @@
   /// should only be used by rare constructs such as address-of-label.
   unsigned getGlobalBasicBlockID(const BasicBlock *BB) const;
 
   /// incorporateFunction/purgeFunction - If you'd like to deal with a function,
   /// use these two methods to get its data into the NaClValueEnumerator!
   ///
   void incorporateFunction(const Function &F);
   void purgeFunction();
 
 private:
+  void OptimizeTypes(const Module *M);

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

This seems like a change that could be upstreamed.  It's not actually changing
the wireformat, just optimizing the choice of IDs?

I'll review this, but just saying that if we upstream, it could reduce the
number of differences.

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

I agree that it is worth considering upstreaming this change.

   void OptimizeConstants(unsigned CstStart, unsigned CstEnd);
 
   void EnumerateMDNodeOperands(const MDNode *N);
   void EnumerateMetadata(const Value *MD);
   void EnumerateFunctionLocalMetadata(const MDNode *N);
   void EnumerateNamedMDNode(const NamedMDNode *NMD);
   void EnumerateValue(const Value *V);
   void EnumerateType(Type *T);
   void EnumerateOperandType(const Value *V);
   void EnumerateAttributes(AttributeSet PAL);
 
   void EnumerateValueSymbolTable(const ValueSymbolTable &ST);
   void EnumerateNamedMetadata(const Module *M);
 };
 
 } // End llvm namespace
 
 #endif