Create type IDs based on reference counts.

lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp

Index: lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
diff --git a/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp b/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
index 1cadd02450d8eef08aee23855dcf0ff93f8e8f1f..d6a2205f26fbdcc0c2732ee0cb9c6045a8941627 100644
--- a/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
+++ b/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
@@ -231,12 +231,23 @@ static void WriteTypeTable(const NaClValueEnumerator &VE,
   Stream.EnterSubblock(bitc::TYPE_BLOCK_ID_NEW, 4 /*count from # abbrevs */);
   SmallVector<uint64_t, 64> TypeVals;
 
+  // Note: modify to use maximum number of bits if under cutoff. Otherwise,
+  // use VBR to take advantage that frequently referenced types have
+  // small IDs.
+  //
+  // Note: Cutoff chosen based on experiments of some bit code files with
+  // a large number of types.

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

What is a large number of types, and on which benchmarks?

There was one issue before where our var-args expansion pass was making up a
whole bunch of duplicate types for the var-args buffers, but that should be gone
after LLVM rev 1174111 (git hash).  Then there is the plan to get rid of a bunch
of struct types...

Still, I guess if it does happen to be that the # of types is large, then with
the sorting this should help...

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

I thought this is still worth adding, in that while we currently are trying to
get structure types out, this may change. Since the cost is minimal if there are
a small number of types, and certainly helps if there are a large number of
types, I didn't see why not to add this.

As far as benchmarks, I'll clarify this by relating it to the bitcode file size
for pnacl-translate.pexe. Changed comment to reflect this.

I also agree that this should be up-streamed.

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

Yeah, it would be more useful for upstream users.

   uint64_t NumBits = Log2_32_Ceil(VE.getTypes().size()+1);
+  static const uint64_t TypeVBRCutoff = 6;
+  uint64_t TypeIdNumBits = (NumBits <= TypeVBRCutoff ? NumBits : TypeVBRCutoff);
+  BitCodeAbbrevOp::Encoding TypeIdEncoding =
+      (NumBits <= TypeVBRCutoff
+       ? BitCodeAbbrevOp::Fixed : BitCodeAbbrevOp::VBR);
 
   // Abbrev for TYPE_CODE_POINTER.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_POINTER));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
+  Abbv->Add(BitCodeAbbrevOp(TypeIdEncoding, TypeIdNumBits));
   Abbv->Add(BitCodeAbbrevOp(0));  // Addrspace = 0
   unsigned PtrAbbrev = Stream.EmitAbbrev(Abbv);
 
@@ -245,8 +256,7 @@ static void WriteTypeTable(const NaClValueEnumerator &VE,
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_FUNCTION));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // isvararg
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
-
+  Abbv->Add(BitCodeAbbrevOp(TypeIdEncoding, TypeIdNumBits));
   unsigned FunctionAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Abbrev for TYPE_CODE_STRUCT_ANON.
@@ -254,8 +264,7 @@ static void WriteTypeTable(const NaClValueEnumerator &VE,
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_ANON));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
-
+  Abbv->Add(BitCodeAbbrevOp(TypeIdEncoding, TypeIdNumBits));
   unsigned StructAnonAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Abbrev for TYPE_CODE_STRUCT_NAME.
@@ -270,16 +279,14 @@ static void WriteTypeTable(const NaClValueEnumerator &VE,
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_NAMED));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
-
+  Abbv->Add(BitCodeAbbrevOp(TypeIdEncoding, TypeIdNumBits));
   unsigned StructNamedAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Abbrev for TYPE_CODE_ARRAY.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_ARRAY));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // size
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
-
+  Abbv->Add(BitCodeAbbrevOp(TypeIdEncoding, TypeIdNumBits));
   unsigned ArrayAbbrev = Stream.EmitAbbrev(Abbv);
 
   // Emit an entry count so the reader can reserve space.