Change encodeU/SLEB128 to pad to certain number of bytes

[sbc100]

Summary

Previously the 'Padding' argument was the number of padding
bytes to add. However most callers that use 'Padding' know
how many overall bytes they need to write. With the previous
code this would mean encoding the LEB once to find out how
many bytes it would occupy and then using this to calulate
the 'Padding' value.

See: https://reviews.llvm.org/D36595

[ruiu]

The new function may write more bytes than PadTo bytes, so it seems the only reliable way of using it is to pass 5 as PadTo. Is there any other use case than that?

include/llvm/Support/LEB128.h

22–24 ↗

(On Diff #113928)

It is perhaps a matter of personal taste, but it feels Len is a better name than PadTo. I'd also add a comment that if an encoded number of shorter than Len bytes, it is padded so that it becomes Len bytes in total.

[sbc100]

My understanding is that with LEB one can pad to any number of bytes. We use 5 when we write 32-bit values in wasm because 5 is the number of bytes required to encode any 32-bit number as an LEB. We likewise use 10 bytes when writing padded 64-values. One might conceivably use 2 and 3 when writing 8-bit and 16-bit values as well.

[ruiu]

Ah, that makes sense.

[sbc100]

@sunfish could you take a look?

[sunfish]

Looks good to me. This is certainly a simplification over computing PaddingFor5ByteULEB128 :-).

llvm/trunk/include/llvm/CodeGen/AsmPrinter.h

public:
   //===------------------------------------------------------------------===//
   // Dwarf Emission Helper Routines
   //===------------------------------------------------------------------===//
 
   /// Emit the specified signed leb128 value.
   void EmitSLEB128(int64_t Value, const char *Desc = nullptr) const;
 
   /// Emit the specified unsigned leb128 value.
-  void EmitULEB128(uint64_t Value, const char *Desc = nullptr,
-                   unsigned PadTo = 0) const;
+  void EmitULEB128(uint64_t Value, const char *Desc = nullptr) const;
+
+  /// Emit the specified unsigned leb128 value padded to a specific number
+  /// bytes
+  void EmitPaddedULEB128(uint64_t Value, unsigned PadTo,
+                         const char *Desc = nullptr) const;
 
   /// Emit a .byte 42 directive that corresponds to an encoding.  If verbose
   /// assembly output is enabled, we output comments describing the encoding.
   /// Desc is a string saying what the encoding is specifying (e.g. "LSDA").
   void EmitEncodingByte(unsigned Val, const char *Desc = nullptr) const;
 
   /// Return the size of the encoding in bytes.
   unsigned GetSizeOfEncodedValue(unsigned Encoding) const;

llvm/trunk/include/llvm/MC/MCStreamer.h

public:
   virtual void EmitIntValue(uint64_t Value, unsigned Size);
 
   virtual void EmitULEB128Value(const MCExpr *Value);
 
   virtual void EmitSLEB128Value(const MCExpr *Value);
 
   /// \brief Special case of EmitULEB128Value that avoids the client having to
   /// pass in a MCExpr for constant integers.
-  void EmitULEB128IntValue(uint64_t Value, unsigned Padding = 0);
+  void EmitULEB128IntValue(uint64_t Value);
+
+  /// \brief Like EmitULEB128Value but pads the output to specific number of
+  /// bytes.
+  void EmitPaddedULEB128IntValue(uint64_t Value, unsigned PadTo);
 
   /// \brief Special case of EmitSLEB128Value that avoids the client having to
   /// pass in a MCExpr for constant integers.
   void EmitSLEB128IntValue(int64_t Value);
 
   /// \brief Special case of EmitValue that avoids the client having to pass in
   /// a MCExpr for MCSymbols.
   void EmitSymbolValue(const MCSymbol *Sym, unsigned Size,

llvm/trunk/include/llvm/Support/LEB128.h

 #define LLVM_SUPPORT_LEB128_H
 
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 /// Utility function to encode a SLEB128 value to an output stream.
 inline void encodeSLEB128(int64_t Value, raw_ostream &OS,
-                          unsigned Padding = 0) {
+                          unsigned PadTo = 0) {
   bool More;
+  unsigned Count = 0;
   do {
     uint8_t Byte = Value & 0x7f;
     // NOTE: this assumes that this signed shift is an arithmetic right shift.
     Value >>= 7;
     More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
               ((Value == -1) && ((Byte & 0x40) != 0))));
-    if (More || Padding != 0)
+    Count++;
+    if (More || Count < PadTo)
       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
     OS << char(Byte);
   } while (More);
 
   // Pad with 0x80 and emit a terminating byte at the end.
-  if (Padding != 0) {
+  if (Count < PadTo) {
     uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
-    for (; Padding != 1; --Padding)
+    for (; Count < PadTo - 1; ++Count)
       OS << char(PadValue | 0x80);
     OS << char(PadValue);
   }
 }
 
 /// Utility function to encode a SLEB128 value to a buffer. Returns
 /// the length in bytes of the encoded value.
-inline unsigned encodeSLEB128(int64_t Value, uint8_t *p, unsigned Padding = 0) {
+inline unsigned encodeSLEB128(int64_t Value, uint8_t *p, unsigned PadTo = 0) {
   uint8_t *orig_p = p;
+  unsigned Count = 0;
   bool More;
   do {
     uint8_t Byte = Value & 0x7f;
     // NOTE: this assumes that this signed shift is an arithmetic right shift.
     Value >>= 7;
     More = !((((Value == 0 ) && ((Byte & 0x40) == 0)) ||
               ((Value == -1) && ((Byte & 0x40) != 0))));
-    if (More || Padding != 0)
+    Count++;
+    if (More || Count < PadTo)
       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
     *p++ = Byte;
   } while (More);
 
   // Pad with 0x80 and emit a terminating byte at the end.
-  if (Padding != 0) {
+  if (Count < PadTo) {
     uint8_t PadValue = Value < 0 ? 0x7f : 0x00;
-    for (; Padding != 1; --Padding)
+    for (; Count < PadTo - 1; ++Count)
       *p++ = (PadValue | 0x80);
     *p++ = PadValue;
   }
   return (unsigned)(p - orig_p);
 }
 
 /// Utility function to encode a ULEB128 value to an output stream.
 inline void encodeULEB128(uint64_t Value, raw_ostream &OS,
-                          unsigned Padding = 0) {
+                          unsigned PadTo = 0) {
+  unsigned Count = 0;
   do {
     uint8_t Byte = Value & 0x7f;
     Value >>= 7;
-    if (Value != 0 || Padding != 0)
+    Count++;
+    if (Value != 0 || Count < PadTo)
       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
     OS << char(Byte);
   } while (Value != 0);
 
   // Pad with 0x80 and emit a null byte at the end.
-  if (Padding != 0) {
-    for (; Padding != 1; --Padding)
+  if (Count < PadTo) {
+    for (; Count < PadTo - 1; ++Count)
       OS << '\x80';
     OS << '\x00';
+    Count++;
   }
 }
 
 /// Utility function to encode a ULEB128 value to a buffer. Returns
 /// the length in bytes of the encoded value.
 inline unsigned encodeULEB128(uint64_t Value, uint8_t *p,
-                              unsigned Padding = 0) {
+                              unsigned PadTo = 0) {
   uint8_t *orig_p = p;
+  unsigned Count = 0;
   do {
     uint8_t Byte = Value & 0x7f;
     Value >>= 7;
-    if (Value != 0 || Padding != 0)
+    Count++;
+    if (Value != 0 || Count < PadTo)
       Byte |= 0x80; // Mark this byte to show that more bytes will follow.
     *p++ = Byte;
   } while (Value != 0);
 
   // Pad with 0x80 and emit a null byte at the end.
-  if (Padding != 0) {
-    for (; Padding != 1; --Padding)
+  if (Count < PadTo) {
+    for (; Count < PadTo - 1; ++Count)
       *p++ = '\x80';
     *p++ = '\x00';
   }
+
   return (unsigned)(p - orig_p);
 }
 
 /// Utility function to decode a ULEB128 value.
 inline uint64_t decodeULEB128(const uint8_t *p, unsigned *n = nullptr,
                               const uint8_t *end = nullptr,
                               const char **error = nullptr) {
   const uint8_t *orig_p = p;

llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinterDwarf.cpp

 void AsmPrinter::EmitSLEB128(int64_t Value, const char *Desc) const {
   if (isVerbose() && Desc)
     OutStreamer->AddComment(Desc);
 
   OutStreamer->EmitSLEB128IntValue(Value);
 }
 
 /// EmitULEB128 - emit the specified unsigned leb128 value.
-void AsmPrinter::EmitULEB128(uint64_t Value, const char *Desc,
-                             unsigned PadTo) const {
+void AsmPrinter::EmitPaddedULEB128(uint64_t Value, unsigned PadTo,
+                                   const char *Desc) const {
   if (isVerbose() && Desc)
     OutStreamer->AddComment(Desc);
 
-  OutStreamer->EmitULEB128IntValue(Value, PadTo);
+  OutStreamer->EmitPaddedULEB128IntValue(Value, PadTo);
+}
+
+void AsmPrinter::EmitULEB128(uint64_t Value, const char *Desc) const {
+  if (isVerbose() && Desc)
+    OutStreamer->AddComment(Desc);
+
+  OutStreamer->EmitULEB128IntValue(Value);
 }
 
 static const char *DecodeDWARFEncoding(unsigned Encoding) {
   switch (Encoding) {
   case dwarf::DW_EH_PE_absptr:
     return "absptr";
   case dwarf::DW_EH_PE_omit:
     return "omit";

llvm/trunk/lib/CodeGen/AsmPrinter/EHStreamer.cpp

unsigned TTypeBaseOffset =
     SizeActions +                               // Actions size
     SizeTypes;
   unsigned TTypeBaseOffsetSize = getULEB128Size(TTypeBaseOffset);
   unsigned TotalSize =
     sizeof(int8_t) +                            // LPStart format
     sizeof(int8_t) +                            // TType format
     (HaveTTData ? TTypeBaseOffsetSize : 0) +    // TType base offset size
     TTypeBaseOffset;                            // TType base offset
-  unsigned SizeAlign = (4 - TotalSize) & 3;
+  unsigned PadBytes = (4 - TotalSize) & 3;
 
   if (HaveTTData) {
     // Account for any extra padding that will be added to the call site table
     // length.
-    Asm->EmitULEB128(TTypeBaseOffset, "@TType base offset", SizeAlign);
-    SizeAlign = 0;
+    Asm->EmitPaddedULEB128(TTypeBaseOffset, TTypeBaseOffsetSize + PadBytes,
+                           "@TType base offset");
+    PadBytes = 0;
   }
 
   bool VerboseAsm = Asm->OutStreamer->isVerboseAsm();
 
   // SjLj Exception handling
   if (IsSJLJ) {
     Asm->EmitEncodingByte(dwarf::DW_EH_PE_udata4, "Call site");
 
     // Add extra padding if it wasn't added to the TType base offset.
-    Asm->EmitULEB128(CallSiteTableLength, "Call site table length", SizeAlign);
+    Asm->EmitPaddedULEB128(CallSiteTableLength,
+                           CallSiteTableLengthSize + PadBytes,
+                           "Call site table length");
 
     // Emit the landing pad site information.
     unsigned idx = 0;
     for (SmallVectorImpl<CallSiteEntry>::const_iterator
          I = CallSites.begin(), E = CallSites.end(); I != E; ++I, ++idx) {
       const CallSiteEntry &S = *I;
 
       // Offset of the landing pad, counted in 16-byte bundles relative to the
if (IsSJLJ) {
     //
     // A missing entry in the call-site table indicates that a call is not
     // supposed to throw.
 
     // Emit the landing pad call site table.
     Asm->EmitEncodingByte(dwarf::DW_EH_PE_udata4, "Call site");
 
     // Add extra padding if it wasn't added to the TType base offset.
-    Asm->EmitULEB128(CallSiteTableLength, "Call site table length", SizeAlign);
+    Asm->EmitPaddedULEB128(CallSiteTableLength,
+                           CallSiteTableLengthSize + PadBytes,
+                           "Call site table length");
 
     unsigned Entry = 0;
     for (SmallVectorImpl<CallSiteEntry>::const_iterator
          I = CallSites.begin(), E = CallSites.end(); I != E; ++I) {
       const CallSiteEntry &S = *I;
 
       MCSymbol *EHFuncBeginSym = Asm->getFunctionBegin();
 

llvm/trunk/lib/MC/MCStreamer.cpp

for (unsigned i = 0; i != Size; ++i) {
     unsigned index = isLittleEndian ? i : (Size - i - 1);
     buf[i] = uint8_t(Value >> (index * 8));
   }
   EmitBytes(StringRef(buf, Size));
 }
 
 /// EmitULEB128Value - Special case of EmitULEB128Value that avoids the
 /// client having to pass in a MCExpr for constant integers.
-void MCStreamer::EmitULEB128IntValue(uint64_t Value, unsigned Padding) {
+void MCStreamer::EmitPaddedULEB128IntValue(uint64_t Value, unsigned PadTo) {
   SmallString<128> Tmp;
   raw_svector_ostream OSE(Tmp);
-  encodeULEB128(Value, OSE, Padding);
+  encodeULEB128(Value, OSE, PadTo);
   EmitBytes(OSE.str());
 }
 
+void MCStreamer::EmitULEB128IntValue(uint64_t Value) {
+  EmitPaddedULEB128IntValue(Value, 0);
+}
+
 /// EmitSLEB128Value - Special case of EmitSLEB128Value that avoids the
 /// client having to pass in a MCExpr for constant integers.
 void MCStreamer::EmitSLEB128IntValue(int64_t Value) {
   SmallString<128> Tmp;
   raw_svector_ostream OSE(Tmp);
   encodeSLEB128(Value, OSE);
   EmitBytes(OSE.str());
 }

llvm/trunk/lib/MC/WasmObjectWriter.cpp

private:
   uint32_t getFunctionType(const MCSymbolWasm& Symbol);
   uint32_t registerFunctionType(const MCSymbolWasm& Symbol);
 };
 
 } // end anonymous namespace
 
 WasmObjectWriter::~WasmObjectWriter() {}
 
-// Return the padding size to write a 32-bit value into a 5-byte ULEB128.
-static unsigned PaddingFor5ByteULEB128(uint32_t X) {
-  return X == 0 ? 4 : (4u - (31u - countLeadingZeros(X)) / 7u);
-}
-
-// Return the padding size to write a 32-bit value into a 5-byte SLEB128.
-static unsigned PaddingFor5ByteSLEB128(int32_t X) {
-  return 5 - getSLEB128Size(X);
-}
-
 // Write out a section header and a patchable section size field.
 void WasmObjectWriter::startSection(SectionBookkeeping &Section,
                                     unsigned SectionId,
                                     const char *Name) {
   assert((Name != nullptr) == (SectionId == wasm::WASM_SEC_CUSTOM) &&
          "Only custom sections can have names");
 
   DEBUG(dbgs() << "startSection " << SectionId << ": " << Name << "\n");

 // Now that the section is complete and we know how big it is, patch up the
 // section size field at the start of the section.
 void WasmObjectWriter::endSection(SectionBookkeeping &Section) {
   uint64_t Size = getStream().tell() - Section.ContentsOffset;
   if (uint32_t(Size) != Size)
     report_fatal_error("section size does not fit in a uint32_t");
 
   DEBUG(dbgs() << "endSection size=" << Size << "\n");
-  unsigned Padding = PaddingFor5ByteULEB128(Size);
 
   // Write the final section size to the payload_len field, which follows
   // the section id byte.
   uint8_t Buffer[16];
-  unsigned SizeLen = encodeULEB128(Size, Buffer, Padding);
+  unsigned SizeLen = encodeULEB128(Size, Buffer, 5);
   assert(SizeLen == 5);
   getStream().pwrite((char *)Buffer, SizeLen, Section.SizeOffset);
 }
 
 // Emit the Wasm header.
 void WasmObjectWriter::writeHeader(const MCAssembler &Asm) {
   writeBytes(StringRef(wasm::WasmMagic, sizeof(wasm::WasmMagic)));
   writeLE32(wasm::WasmVersion);
else
     DataRelocations.push_back(Rec);
 }
 
 // Write X as an (unsigned) LEB value at offset Offset in Stream, padded
 // to allow patching.
 static void
 WritePatchableLEB(raw_pwrite_stream &Stream, uint32_t X, uint64_t Offset) {
   uint8_t Buffer[5];
-  unsigned Padding = PaddingFor5ByteULEB128(X);
-  unsigned SizeLen = encodeULEB128(X, Buffer, Padding);
+  unsigned SizeLen = encodeULEB128(X, Buffer, 5);
   assert(SizeLen == 5);
   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 }
 
 // Write X as an signed LEB value at offset Offset in Stream, padded
 // to allow patching.
 static void
 WritePatchableSLEB(raw_pwrite_stream &Stream, int32_t X, uint64_t Offset) {
   uint8_t Buffer[5];
-  unsigned Padding = PaddingFor5ByteSLEB128(X);
-  unsigned SizeLen = encodeSLEB128(X, Buffer, Padding);
+  unsigned SizeLen = encodeSLEB128(X, Buffer, 5);
   assert(SizeLen == 5);
   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 }
 
 // Write X as a plain integer value at offset Offset in Stream.
 static void WriteI32(raw_pwrite_stream &Stream, uint32_t X, uint64_t Offset) {
   uint8_t Buffer[4];
   support::endian::write32le(Buffer, X);

llvm/trunk/lib/Target/WebAssembly/MCTargetDesc/WebAssemblyMCCodeEmitter.cpp

if (MO.isReg()) {
       } else {
         assert(Info.OperandType == WebAssembly::OPERAND_F64IMM);
         double d = MO.getFPImm();
         support::endian::Writer<support::little>(OS).write<double>(d);
       }
     } else if (MO.isExpr()) {
       const MCOperandInfo &Info = Desc.OpInfo[i];
       llvm::MCFixupKind FixupKind;
-      size_t PaddedSize;
+      size_t PaddedSize = 5;
       if (Info.OperandType == WebAssembly::OPERAND_I32IMM) {
         FixupKind = MCFixupKind(WebAssembly::fixup_code_sleb128_i32);
-        PaddedSize = 5;
       } else if (Info.OperandType == WebAssembly::OPERAND_I64IMM) {
         FixupKind = MCFixupKind(WebAssembly::fixup_code_sleb128_i64);
         PaddedSize = 10;
       } else if (Info.OperandType == WebAssembly::OPERAND_FUNCTION32 ||
                  Info.OperandType == WebAssembly::OPERAND_OFFSET32 ||
                  Info.OperandType == WebAssembly::OPERAND_TYPEINDEX) {
         FixupKind = MCFixupKind(WebAssembly::fixup_code_uleb128_i32);
-        PaddedSize = 5;
       } else if (Info.OperandType == WebAssembly::OPERAND_GLOBAL) {
         FixupKind = MCFixupKind(WebAssembly::fixup_code_global_index);
-        PaddedSize = 5;
       } else {
         llvm_unreachable("unexpected symbolic operand kind");
       }
       Fixups.push_back(MCFixup::create(
           OS.tell() - Start, MO.getExpr(),
           FixupKind, MI.getLoc()));
       ++MCNumFixups;
-      encodeULEB128(0, OS, PaddedSize - 1);
+      encodeULEB128(0, OS, PaddedSize);
     } else {
       llvm_unreachable("unexpected operand kind");
     }
   }
 
   ++MCNumEmitted; // Keep track of the # of mi's emitted.
 }
 
 #include "WebAssemblyGenMCCodeEmitter.inc"

llvm/trunk/unittests/Support/LEB128Test.cpp

#define EXPECT_SLEB128_EQ(EXPECTED, VALUE, PAD) \
   EXPECT_SLEB128_EQ("\x7f", -1, 0);
   EXPECT_SLEB128_EQ("\x3f", 63, 0);
   EXPECT_SLEB128_EQ("\x41", -63, 0);
   EXPECT_SLEB128_EQ("\x40", -64, 0);
   EXPECT_SLEB128_EQ("\xbf\x7f", -65, 0);
   EXPECT_SLEB128_EQ("\xc0\x00", 64, 0);
 
   // Encode SLEB128 with some extra padding bytes
-  EXPECT_SLEB128_EQ("\x80\x00", 0, 1);
-  EXPECT_SLEB128_EQ("\x80\x80\x00", 0, 2);
-  EXPECT_SLEB128_EQ("\xff\x80\x00", 0x7f, 1);
-  EXPECT_SLEB128_EQ("\xff\x80\x80\x00", 0x7f, 2);
-  EXPECT_SLEB128_EQ("\x80\x81\x00", 0x80, 1);
-  EXPECT_SLEB128_EQ("\x80\x81\x80\x00", 0x80, 2);
-  EXPECT_SLEB128_EQ("\xc0\x7f", -0x40, 1);
-  EXPECT_SLEB128_EQ("\xc0\xff\x7f", -0x40, 2);
-  EXPECT_SLEB128_EQ("\x80\xff\x7f", -0x80, 1);
-  EXPECT_SLEB128_EQ("\x80\xff\xff\x7f", -0x80, 2);
+  EXPECT_SLEB128_EQ("\x80\x00", 0, 2);
+  EXPECT_SLEB128_EQ("\x80\x80\x00", 0, 3);
+  EXPECT_SLEB128_EQ("\xff\x80\x00", 0x7f, 3);
+  EXPECT_SLEB128_EQ("\xff\x80\x80\x00", 0x7f, 4);
+  EXPECT_SLEB128_EQ("\x80\x81\x00", 0x80, 3);
+  EXPECT_SLEB128_EQ("\x80\x81\x80\x00", 0x80, 4);
+  EXPECT_SLEB128_EQ("\xc0\x7f", -0x40, 2);
+
+  EXPECT_SLEB128_EQ("\xc0\xff\x7f", -0x40, 3);
+  EXPECT_SLEB128_EQ("\x80\xff\x7f", -0x80, 3);
+  EXPECT_SLEB128_EQ("\x80\xff\xff\x7f", -0x80, 4);
 
 #undef EXPECT_SLEB128_EQ
 }
 
 TEST(LEB128Test, EncodeULEB128) {
 #define EXPECT_ULEB128_EQ(EXPECTED, VALUE, PAD) \
   do { \
     std::string Expected(EXPECTED, sizeof(EXPECTED) - 1); \
#define EXPECT_ULEB128_EQ(EXPECTED, VALUE, PAD) \
   EXPECT_ULEB128_EQ("\x80\x01", 0x80, 0);
   EXPECT_ULEB128_EQ("\x81\x01", 0x81, 0);
   EXPECT_ULEB128_EQ("\x90\x01", 0x90, 0);
   EXPECT_ULEB128_EQ("\xff\x01", 0xff, 0);
   EXPECT_ULEB128_EQ("\x80\x02", 0x100, 0);
   EXPECT_ULEB128_EQ("\x81\x02", 0x101, 0);
 
   // Encode ULEB128 with some extra padding bytes
-  EXPECT_ULEB128_EQ("\x80\x00", 0, 1);
-  EXPECT_ULEB128_EQ("\x80\x80\x00", 0, 2);
-  EXPECT_ULEB128_EQ("\xff\x00", 0x7f, 1);
-  EXPECT_ULEB128_EQ("\xff\x80\x00", 0x7f, 2);
-  EXPECT_ULEB128_EQ("\x80\x81\x00", 0x80, 1);
-  EXPECT_ULEB128_EQ("\x80\x81\x80\x00", 0x80, 2);
+  EXPECT_ULEB128_EQ("\x80\x00", 0, 2);
+  EXPECT_ULEB128_EQ("\x80\x80\x00", 0, 3);
+  EXPECT_ULEB128_EQ("\xff\x00", 0x7f, 2);
+  EXPECT_ULEB128_EQ("\xff\x80\x00", 0x7f, 3);
+  EXPECT_ULEB128_EQ("\x80\x81\x00", 0x80, 3);
+  EXPECT_ULEB128_EQ("\x80\x81\x80\x00", 0x80, 4);
 
 #undef EXPECT_ULEB128_EQ
 }
 
 TEST(LEB128Test, DecodeULEB128) {
 #define EXPECT_DECODE_ULEB128_EQ(EXPECTED, VALUE) \
   do { \
     unsigned ActualSize = 0; \