[Bitstream] Define VBRZ encoding, and use VBRZ6 for unabbreviated values

[sammccall]

Summary

When we don't know what we're encoding, chances are it's zero often
enough that providing a 1-bit encoding of zero is a win.

This seems to be roughly size-neutral on LLVM bitcode, and reduces Clang
PCH files by ~9%.

[MaskRay]

llvm/lib/Bitstream/Reader/BitstreamReader.cpp

110

Why is this unconditionally true?

llvm/include/llvm/Bitstream/BitCodes.h

class BitCodeAbbrevOp {
   bool IsLiteral : 1;     // Indicate whether this is a literal value or not.
   unsigned Enc   : 3;     // The encoding to use.
 public:
   enum Encoding {
     Fixed = 1,  // A fixed width field, Val specifies number of bits.
     VBR   = 2,  // A VBR field where Val specifies the width of each chunk.
     Array = 3,  // A sequence of fields, next field species elt encoding.
     Char6 = 4,  // A 6-bit fixed field which maps to [a-zA-Z0-9._].
-    Blob  = 5   // 32-bit aligned array of 8-bit characters.
+    Blob  = 5,  // 32-bit aligned array of 8-bit characters.
+    VBRZ  = 6,  // A nullable VBR field, Val specifies the width of each chunk.
   };
 
   static bool isValidEncoding(uint64_t E) {
-    return E >= 1 && E <= 5;
+    return E >= 1 && E <= 6;
   }
 
   explicit BitCodeAbbrevOp(uint64_t V) :  Val(V), IsLiteral(true) {}
   explicit BitCodeAbbrevOp(Encoding E, uint64_t Data = 0)
     : Val(Data), IsLiteral(false), Enc(E) {}
 
   bool isLiteral() const  { return IsLiteral; }
   bool isEncoding() const { return !IsLiteral; }
 
   // Accessors for literals.
   uint64_t getLiteralValue() const { assert(isLiteral()); return Val; }
 
   // Accessors for encoding info.
   Encoding getEncoding() const { assert(isEncoding()); return (Encoding)Enc; }
   uint64_t getEncodingData() const {
     assert(isEncoding() && hasEncodingData());
     return Val;
   }
 
   bool hasEncodingData() const { return hasEncodingData(getEncoding()); }
   static bool hasEncodingData(Encoding E) {
     switch (E) {
     case Fixed:
     case VBR:
+    case VBRZ:
       return true;
     case Array:
     case Char6:
     case Blob:
       return false;
     }
     report_fatal_error("Invalid encoding");
   }

llvm/include/llvm/Bitstream/BitstreamReader.h

Expected<word_t> Read(unsigned NumBits) {
 
     BitsInCurWord -= BitsLeft;
 
     R |= R2 << (NumBits - BitsLeft);
 
     return R;
   }
 
-  Expected<uint32_t> ReadVBR(const unsigned NumBits) {
+  Expected<uint32_t> ReadVBR(const unsigned NumBits, bool ZeroBit = false) {
+    if (ZeroBit) {
+      Expected<unsigned> MaybeRead = Read(1);
+      if (!MaybeRead)
+        return MaybeRead;
+      if (*MaybeRead == 0)
+        return 0;
+    }
+
     Expected<unsigned> MaybeRead = Read(NumBits);
     if (!MaybeRead)
       return MaybeRead;
     uint32_t Piece = MaybeRead.get();
 
     assert(NumBits <= 32 && NumBits >= 1 && "Invalid NumBits value");
     const uint32_t MaskBitOrder = (NumBits - 1);
     const uint32_t Mask = 1UL << MaskBitOrder;
while (true) {
       if (!MaybeRead)
         return MaybeRead;
       Piece = MaybeRead.get();
     }
   }
 
   // Read a VBR that may have a value up to 64-bits in size. The chunk size of
   // the VBR must still be <= 32 bits though.
-  Expected<uint64_t> ReadVBR64(const unsigned NumBits) {
-    Expected<uint64_t> MaybeRead = Read(NumBits);
+  Expected<uint64_t> ReadVBR64(const unsigned NumBits, bool ZeroBit = false) {
+    if (ZeroBit) {
+      Expected<unsigned> MaybeRead = Read(1);
+      if (!MaybeRead)
+        return MaybeRead;
+      if (*MaybeRead == 0)
+        return 0;
+    }
+
+    Expected<unsigned> MaybeRead = Read(NumBits);
     if (!MaybeRead)
       return MaybeRead;
     uint32_t Piece = MaybeRead.get();
     assert(NumBits <= 32 && NumBits >= 1 && "Invalid NumBits value");
     const uint32_t MaskBitOrder = (NumBits - 1);
     const uint32_t Mask = 1UL << MaskBitOrder;
 
     if ((Piece & Mask) == 0)

llvm/include/llvm/Bitstream/BitstreamWriter.h

#endif
   void FlushToWord() {
     if (CurBit) {
       WriteWord(CurValue);
       CurBit = 0;
       CurValue = 0;
     }
   }
 
-  void EmitVBR(uint32_t Val, unsigned NumBits) {
+  void EmitVBR(uint32_t Val, unsigned NumBits, bool ZeroBit = false) {
+    if (ZeroBit) {
+      Emit(Val != 0, 1);
+      if (Val == 0)
+        return;
+    }
+
     assert(NumBits <= 32 && "Too many bits to emit!");
     uint32_t Threshold = 1U << (NumBits-1);
 
     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
     while (Val >= Threshold) {
       Emit((Val & ((1 << (NumBits-1))-1)) | (1 << (NumBits-1)), NumBits);
       Val >>= NumBits-1;
     }
 
     Emit(Val, NumBits);
   }
 
-  void EmitVBR64(uint64_t Val, unsigned NumBits) {
+  void EmitVBR64(uint64_t Val, unsigned NumBits, bool ZeroBit = false) {
     assert(NumBits <= 32 && "Too many bits to emit!");
     if ((uint32_t)Val == Val)
-      return EmitVBR((uint32_t)Val, NumBits);
+      return EmitVBR((uint32_t)Val, NumBits, ZeroBit);
+
+    if (ZeroBit) {
+      Emit(Val != 0, 1);
+      if (Val == 0)
+        return;
+    }
 
     uint32_t Threshold = 1U << (NumBits-1);
 
     // Emit the bits with VBR encoding, NumBits-1 bits at a time.
     while (Val >= Threshold) {
       Emit(((uint32_t)Val & ((1 << (NumBits - 1)) - 1)) | (1 << (NumBits - 1)),
            NumBits);
       Val >>= NumBits-1;
void EmitAbbreviatedField(const BitCodeAbbrevOp &Op, uintty V) {
     case BitCodeAbbrevOp::Fixed:
       if (Op.getEncodingData())
         Emit((unsigned)V, (unsigned)Op.getEncodingData());
       break;
     case BitCodeAbbrevOp::VBR:
       if (Op.getEncodingData())
         EmitVBR64(V, (unsigned)Op.getEncodingData());
       break;
+    case BitCodeAbbrevOp::VBRZ:
+      if (Op.getEncodingData())
+        EmitVBR64(V, (unsigned)Op.getEncodingData(), /*ZeroBit=*/true);
+      break;
     case BitCodeAbbrevOp::Char6:
       Emit(BitCodeAbbrevOp::EncodeChar6((char)V), 6);
       break;
     }
   }
 
   /// EmitRecordWithAbbrevImpl - This is the core implementation of the record
   /// emission code.  If BlobData is non-null, then it specifies an array of
void EmitRecord(unsigned Code, const Container &Vals, unsigned Abbrev = 0) {
     if (!Abbrev) {
       // If we don't have an abbrev to use, emit this in its fully unabbreviated
       // form.
       auto Count = static_cast<uint32_t>(makeArrayRef(Vals).size());
       EmitCode(bitc::UNABBREV_RECORD);
       EmitVBR(Code, 6);
       EmitVBR(Count, 6);
       for (unsigned i = 0, e = Count; i != e; ++i)
-        EmitVBR64(Vals[i], 6);
+        EmitVBR64(Vals[i], 6, /*ZeroBit=*/true);
       return;
     }
 
     EmitRecordWithAbbrevImpl(Abbrev, makeArrayRef(Vals), StringRef(), Code);
   }
 
   /// EmitRecordWithAbbrev - Emit a record with the specified abbreviation.
   /// Unlike EmitRecord, the code for the record should be included in Vals as

llvm/lib/Bitstream/Reader/BitstreamReader.cpp

static Expected<uint64_t> readAbbreviatedField(BitstreamCursor &Cursor,
   case BitCodeAbbrevOp::Blob:
     llvm_unreachable("Should not reach here");
   case BitCodeAbbrevOp::Fixed:
     assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
     return Cursor.Read((unsigned)Op.getEncodingData());
   case BitCodeAbbrevOp::VBR:
     assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
     return Cursor.ReadVBR64((unsigned)Op.getEncodingData());
+  case BitCodeAbbrevOp::VBRZ:
+    assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
+    return Cursor.ReadVBR64((unsigned)Op.getEncodingData(), /*ZeroBit=*/true);
   case BitCodeAbbrevOp::Char6:
     if (Expected<unsigned> Res = Cursor.Read(6))
       return BitCodeAbbrevOp::DecodeChar6(Res.get());
     else
       return Res.takeError();
   }
   llvm_unreachable("invalid abbreviation encoding");
 }
 
 /// skipRecord - Read the current record and discard it.
 Expected<unsigned> BitstreamCursor::skipRecord(unsigned AbbrevID) {
   // Skip unabbreviated records by reading past their entries.
   if (AbbrevID == bitc::UNABBREV_RECORD) {
     Expected<uint32_t> MaybeCode = ReadVBR(6);
     if (!MaybeCode)
       return MaybeCode.takeError();
     unsigned Code = MaybeCode.get();
     Expected<uint32_t> MaybeVBR = ReadVBR(6);
     if (!MaybeVBR)
       return MaybeVBR.takeError();
     unsigned NumElts = MaybeVBR.get();
     for (unsigned i = 0; i != NumElts; ++i)
-      if (Expected<uint64_t> Res = ReadVBR64(6))
+      if (Expected<uint64_t> Res = ReadVBR64(6, /*ZeroBit=*/true))
         ; // Skip!
       else
         return Res.takeError();
     return Code;
   }
 
   Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
   if (!MaybeAbbv)
if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
       case BitCodeAbbrevOp::Fixed:
         assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
         if (Error Err =
                 JumpToBit(GetCurrentBitNo() + static_cast<uint64_t>(NumElts) *
                                                   EltEnc.getEncodingData()))
           return std::move(Err);
         break;
       case BitCodeAbbrevOp::VBR:
+      case BitCodeAbbrevOp::VBRZ:
         assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
         for (; NumElts; --NumElts)
-          if (Expected<uint64_t> Res =
-                  ReadVBR64((unsigned)EltEnc.getEncodingData()))
+          if (Expected<uint64_t> Res = ReadVBR64(
+                  (unsigned)EltEnc.getEncodingData(),
+                  /*ZeroBit=*/EltEnc.getEncoding() == BitCodeAbbrevOp::VBRZ))
             ; // Skip!
           else
             return Res.takeError();
         break;
       case BitCodeAbbrevOp::Char6:
         if (Error Err = JumpToBit(GetCurrentBitNo() + NumElts * 6))
           return std::move(Err);
         break;
if (!MaybeNumElts)
           ("Failed to read size: " + toString(MaybeNumElts.takeError()))
               .c_str());
     uint32_t NumElts = MaybeNumElts.get();
     if (!isSizePlausible(NumElts))
       return error("Size is not plausible");
     Vals.reserve(Vals.size() + NumElts);
 
     for (unsigned i = 0; i != NumElts; ++i)
-      if (Expected<uint64_t> MaybeVal = ReadVBR64(6))
+      if (Expected<uint64_t> MaybeVal = ReadVBR64(6, /*ZeroBit=*/true))
         Vals.push_back(MaybeVal.get());
       else
         return MaybeVal.takeError();
     return Code;
   }
 
   Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
   if (!MaybeAbbv)
if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
         for (; NumElts; --NumElts)
           if (Expected<SimpleBitstreamCursor::word_t> MaybeVal =
                   Read((unsigned)EltEnc.getEncodingData()))
             Vals.push_back(MaybeVal.get());
           else
             return MaybeVal.takeError();
         break;
       case BitCodeAbbrevOp::VBR:
+      case BitCodeAbbrevOp::VBRZ:
         for (; NumElts; --NumElts)
-          if (Expected<uint64_t> MaybeVal =
-                  ReadVBR64((unsigned)EltEnc.getEncodingData()))
+          if (Expected<uint64_t> MaybeVal = ReadVBR64(
+                  (unsigned)EltEnc.getEncodingData(),
+                  /*ZeroBit=*/EltEnc.getEncoding() == BitCodeAbbrevOp::VBRZ))
             Vals.push_back(MaybeVal.get());
           else
             return MaybeVal.takeError();
         break;
       case BitCodeAbbrevOp::Char6:
         for (; NumElts; --NumElts)
           if (Expected<SimpleBitstreamCursor::word_t> MaybeVal = Read(6))
             Vals.push_back(BitCodeAbbrevOp::DecodeChar6(MaybeVal.get()));