Add parser for the stackmap section format

[reames]

Summary

Add an externally facing parser for the stackmap section generated for stackmaps, patchpoint, and statepoint. The intended users of the parser are consumers of LLVM - mainly users of MCJIT.

Our documented usage model for all of these intrinsics is to have users parse the stackmap format and generate whatever custom side tables they may require. We know have multiple active groups that need such a parser, so it's time to find a place to put it for code sharing. This code is base around code developed for our particular frontend. The LLILC group has expressed interest in getting access to the code and another unrelated user spoke up on llvm-dev today.

To be explicitly clear about support: the parser explicitly and intentionally only supports parsing the section generated by the exact same build of LLVM. There are NO compatibility guarantees provided even across major releases.

I would welcome suggestions on how to test this in tree. I didn't see any obvious places to add a stackmap section parser. Would it make sense to add a dedicated parser/printer tool? Or is there an existing one I can add to? I'm reasonable sure I've introduced at least one bug when migrating the code, but without backporting into my own tree, I don't have a way to flesh these out.

[swaroop.sridhar]

For StackMapSection::dump(), my suggestion is to follow the other dumper routines and send the output to dbgs(), instead of using printfs.

void StackMapSection::dump() const { print(dbgs()); }

void StackMapSection::print(raw_ostream &OS) const
{

OS << "Functions (" << static_cast<int>(FnSizeRecords.size()) << ") [\n";
for (uint16_t j = 0; j < FnSizeRecords.size(); j++) {
  OS << "  addr = " << static_cast<unsigned>(FnSizeRecords[j].FunctionAddr);
  OS << ", size = " << static_cast<unsigned>(FnSizeRecords[j].StackSize);
  OS << "\n";
}
OS << "]\n";

OS << "Constants (" << static_cast<int>(Constants.size()) << ") [\n";
for (uint16_t j = 0; j < Constants.size(); j++) {
  OS << "  value = " << static_cast<unsigned>(Constants[j]);
}
OS << "]\n";

OS << "Records (" << static_cast<int>(Records.size()) << ") [\n";
for (unsigned i = 0; i < Records.size(); i++) {
  const StackMapRecord& Rec = Records[i];
  OS << "  id = " << Rec.PatchPointID;
  OS << ", offset" << Rec.InstructionOffset;
  OS << ", flags=" << Rec.ReservedFlags;
  OS << "\n";

  OS << "  Locations (" << static_cast<int>(Rec.Locations.size()) << ") [\n";
  for (uint16_t j = 0; j < Rec.Locations.size(); j++) {
    const LocationRecord& Loc = Rec.Locations[j];
    OS << "    type = " << locationTypeToString(Loc.Type);
    OS << ", size = " << (size_t)Loc.SizeInBytes;
    OS << ", dwarfreg = " << Loc.DwarfRegNum;
    OS << ", offset = " << Loc.Offset;
    OS << "\n";
  }
  OS << "  ]\n";
}
OS << "]\n";

}

[swaroop.sridhar]

Looks good to me, other than the comment above.

[sanjoy]

This change mostly has stylistic issues -- I've commented on some; and whitespace needs to be fixed (I'd just run the change through clang-format).

As far as testing is concerned, does it make sense to run the parser over a binary blob in a test in unittests/?

lib/CodeGen/StackMaps.cpp

39

Should be ParsePrimitive.

43

So the machine generating the stackmap section and the machine parsing them should have the same endianness -- should this be documented explicitly?

49

LLVM style is uint8_t *Data etc.

114

foreach?

124

foreach?

[pgavlin]

+1 to Swaroop's suggestion to use an ostream rather than printf.

include/llvm/CodeGen/StackMaps.h

48

s/it's/its

lib/CodeGen/StackMaps.cpp

43

It would certainly be nice to have his were documented if it is intentional.

52

I don't see anything that guarantees that the layout of a LocationRecord value matches the layout of the fields in the input buffer w.r.t. padding. I think that either LocationRecord needs to have __attribute__((packed)) applied (or something similar that will work across MSVC, GCC, and clang) or each field will need to be set individually using the result of an appropriate call to parse_primitive.

149

Maybe mark these as TODOs to help them stand out a bit better.

[lhames]

This should definitely be ostream based, rather than printf based.

It also duplicates the contents of the stackmap section, which is unfortunate. The section will already be in memory, so ideally we should just have accessors for the fields. I'm writing up something along these lines at the moment and will post it shortly.

[lhames]

Hi all,

I couldn't figure out how to neatly attach an alternative patch to this review, so I've posted mine at http://reviews.llvm.org/D10434.

That review is only a sketch of the idea. Still on the to-do list are the location data structure, version check, and richer debug-dumps (i.e with named registers, fields).

I'm curious about how the data from the stackmap section is used by clients. If all clients are interested in all stackmap contents then it seems reasonable to provide an abstract StackMap data structure (like the one proposed here) and use my parser to parse it. If different clients use different portions of the stackmap sections, and are likely to want to parse the stackmap section into custom data structures, then maybe we're best of just providing stackmap parsers in-tree.

[swaroop.sridhar]

I like Lang Hames' idea of using copy-free accessors to read the data directly from the __llvm.stackmaps section loaded into memory.
In particular, if the client compiler needs to read the stackmap section and translate it to an alternate format specific to its runtime, its better to avoid creating an intermediate copy between the two versions.

[pgavlin]

I prefer Lang's approach as well--I certainly wouldn't mind having this checked in as an intermediate step, however.

[reames]

Unless anyone objects, I'm going to check in a cleaned up version of
this change with style comments addressed and a use in objdump. I agree
that the flyweight parser is probably a better long term approach, but
this a) works, and b) is incremental progress towards that goal. We can
adapt the parser once it's in and tested.

If anyone wants to take lead on the flyweight style parser, I'd welcome
that. It's probably not something I'll get to short term. I am very
happy to review patches.

Philip

[reames]

Lang landed his version of a stackmap parser a while back.

include/llvm/CodeGen/StackMaps.h

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/Debug.h"
 #include <map>
 #include <vector>
 
 namespace llvm {
+/// Represents a location associated with a given record in the generated
+/// stackmap section.   
+struct LocationRecord {
+  /// Can use StackMaps::Location::Type to interpret value of Type field.
+  uint8_t Type;
+  uint8_t SizeInBytes;
+  uint16_t DwarfRegNum;
+  int32_t Offset;
+
+  void parse(uint8_t* data, unsigned& offset, const unsigned len);
+};
+
+/// Represents a given record (of a single stackmap, patchpoint, or statepoint
+/// intrinsic) within the generated stackmap section.
+struct StackMapRecord {
+  uint64_t PatchPointID;
+  uint32_t InstructionOffset;
+  uint16_t ReservedFlags;
+  std::vector<LocationRecord> Locations;  //[NumLocations]
+  // LiveOuts omitted - could be added by interested users
+
+  void parse(uint8_t* data, unsigned& offset, const unsigned len);
+};
+
+/// Represents information recorded about a given function within the text
+/// section recorded in the stackmap section.  In particular, used to record
+/// the start of each function and it's stack size.
+struct StackMapSizeRecord {
+  StackMapSizeRecord(uint64_t offset, uint64_t size)
+    : FunctionAddr(offset), StackSize(size) {}
+  uint64_t FunctionAddr;
+  uint64_t StackSize;
+
+  /// Does this function have a fixed size frame?  If not, the StackSize field
+  /// is undefined and meaningless.
+  bool isFixedSizeFrame() const;
+};
+
+/// Represents the contents of a generated stackmap section.  Intended usage is
+/// to construct an instance of this class on the stack, parse the memory
+/// holding the stackmap section using the given API, and then access the data
+/// through the provided fields.  Note that this parser is intentionally and
+/// deliberately version locked with the version of LLVM which includes it.  No
+/// effort is made to parse stackmap sections generated by other revisions.
+/// Cross version parsing is explicitly and intentionally unsupported.
+/// Note: The parsed data contains offset into the associated text section
+/// before finalizeObject() is called.  Once relocations are applied, the
+/// offsets may not match the resulting code!
+struct StackMapSection {
+private:
+  void parse(uint8_t* data, unsigned& offset, const unsigned len);
+public:
+  uint8_t Version;     /* one expected */
+  uint8_t Reserved8;   /* zero expected */
+  uint16_t Reserved16; /* zero expected */
+  std::vector<StackMapSizeRecord> FnSizeRecords;
+  std::vector<int64_t> Constants;       //[NumConstants]
+  std::vector<StackMapRecord> Records;  //[NumRecord]
+
+  /// Parse the contents of a given region of memory.  Can only be called on a
+  /// default initialized instance of this class.  Attempting to parse multiple
+  /// sections using a single object is unsupported.
+  void parse(uint8_t* data, const unsigned len) {
+    unsigned offset = 0;
+    parse(data, offset, len);
+    assert(offset == len && "incomplete parsing of stack map section!");
+  }
+  /// Dump a human readable form of the stackmap section previously parsed.
+  /// This is intended for debugging only.  The format is not stable.
+  void dump() const;
+
+  /// Given a particular address, return the record associated with it from the
+  /// parsed stack map section.  Such a record must exist.
+  StackMapRecord& findRecordForRelPC(uint32_t RelPC);
+  
+  /// Check to see if a record exists for the given RelPC within the associated
+  /// text section.
+  bool hasRecordForRelPC(uint32_t RelPC);
+};
 
 class AsmPrinter;
 class MCExpr;
 class MCStreamer;
 
 /// \brief MI-level patchpoint operands.
 ///
 /// MI patchpoint operations take the form:

lib/CodeGen/StackMaps.cpp

 
 #define DEBUG_TYPE "stackmaps"
 
 static cl::opt<int> StackMapVersion("stackmap-version", cl::init(1),
   cl::desc("Specify the stackmap encoding version (default = 1)"));
 
 const char *StackMaps::WSMP = "Stack Maps: ";
 
+
+template <typename Primitive>
+static Primitive parse_primitive(uint8_t* data, unsigned& offset,
+                                 const unsigned len) {
+  assert(data && offset >= 0 && len >= 0);
+  assert(offset < len);
+  Primitive rval = *(Primitive*)(data + offset);
+  offset += sizeof(rval);
+  assert(offset <= len);
+  return rval;
+}
+
+void LocationRecord::parse(uint8_t* data, unsigned& offset,
+                           const unsigned len) {
+  assert(offset + sizeof(LocationRecord) <= len);
+  memcpy(this, data + offset, sizeof(LocationRecord));
+  offset += sizeof(LocationRecord);
+  assert(Type <= 5);
+}
+void StackMapRecord::parse(uint8_t* data, unsigned& offset,
+                           const unsigned len) {
+  PatchPointID = parse_primitive<uint64_t>(data, offset, len);
+  InstructionOffset = parse_primitive<uint32_t>(data, offset, len);
+  ReservedFlags = parse_primitive<uint16_t>(data, offset, len);
+  assert(0 == ReservedFlags);
+  uint16_t NumLocations = parse_primitive<uint16_t>(data, offset, len);
+  Locations.resize(NumLocations);
+  for (uint16_t i = 0; i < NumLocations; i++) {
+    Locations[i].parse(data, offset, len);
+  }
+  uint16_t Padding16 = parse_primitive<uint16_t>(data, offset, len);
+  assert(Padding16 == 0);
+  uint16_t NumLiveOuts = parse_primitive<uint16_t>(data, offset, len);
+  assert(NumLiveOuts == 0 && "need to implement live out parsing");
+
+  // If the offset is not 8-byte aligned, skip the padding inserted to align it.
+  if (offset % 8 != 0) {
+    offset += 8 - (offset % 8);
+  }
+}
+
+bool StackMapSizeRecord::isFixedSizeFrame() const {
+  return StackSize != std::numeric_limits<uint64_t>::max();
+}
+
+void StackMapSection::parse(uint8_t* data, unsigned& offset,
+                            const unsigned len) {
+  Version = parse_primitive<uint8_t>(data, offset, len);
+  Reserved8 = parse_primitive<uint8_t>(data, offset, len);
+  Reserved16 = parse_primitive<uint16_t>(data, offset, len);
+  assert(Version == 1);
+  assert(Reserved8 == 0);
+  assert(Reserved16 == 0);
+
+  uint32_t NumFuncs = parse_primitive<uint32_t>(data, offset, len);
+  uint32_t NumConstants = parse_primitive<uint32_t>(data, offset, len);
+  uint32_t NumRecords = parse_primitive<uint32_t>(data, offset, len);
+  for (uint32_t i = 0; i < NumFuncs; i++) {
+    uint64_t Addr = parse_primitive<uint64_t>(data, offset, len);
+    uint64_t Size = parse_primitive<uint64_t>(data, offset, len);
+    FnSizeRecords.push_back(StackMapSizeRecord(Addr, Size));
+  }
+  for (uint32_t i = 0; i < NumConstants; i++) {
+    Constants.push_back(parse_primitive<uint64_t>(data, offset, len));
+  }
+
+  Records.resize(NumRecords);
+  for (uint32_t i = 0; i < NumRecords; i++) {
+    Records[i].parse(data, offset, len);
+  }
+}
+
+void StackMapSection::dump() const {
+  if (FnSizeRecords.empty()) {
+    printf("Functions (%d) []\n", static_cast<int>(FnSizeRecords.size()));
+  } else {
+    printf("Functions (%d) [\n", static_cast<int>(FnSizeRecords.size()));
+    for (uint16_t j = 0; j < FnSizeRecords.size(); j++) {
+      printf("  addr=%u, size=%u", static_cast<unsigned>(FnSizeRecords[j].FunctionAddr),
+             static_cast<unsigned>(FnSizeRecords[j].StackSize));
+    }
+    puts("]");
+  }
+  if (Constants.empty()) {
+    printf("Constants (%d) []\n", static_cast<int>(Constants.size()));
+  } else {
+    printf("Constants (%d) [\n", static_cast<int>(Constants.size()));
+    for (uint16_t j = 0; j < Constants.size(); j++) {
+      printf("  value=%u", static_cast<unsigned>(Constants[j]));
+    }
+    puts("]");
+  }
+  printf("Records (%d) [\n", static_cast<int>(Records.size()));
+  for (unsigned i = 0; i < Records.size(); i++) {
+    const StackMapRecord& Rec = Records[i];
+    printf("  id=%lu, offset=%d, flags=%X\n", Rec.PatchPointID, Rec.InstructionOffset,
+           Rec.ReservedFlags);
+    if (Rec.Locations.empty()) {
+      printf("  Locations (%d) []\n", static_cast<int>(Rec.Locations.size()));
+    } else {
+      printf("  Locations (%d) [\n", static_cast<int>(Rec.Locations.size()));
+      for (uint16_t j = 0; j < Rec.Locations.size(); j++) {
+        const LocationRecord& Loc = Rec.Locations[j];
+        printf("    type=%u, size=%u, dwarfreg=%u, offset=%u\n", Loc.Type, Loc.SizeInBytes,
+               Loc.DwarfRegNum, Loc.Offset);
+      }
+      puts("  ]");
+    }
+  }
+  puts("]");
+}
+StackMapRecord& StackMapSection::findRecordForRelPC(uint32_t RelPC) {
+  // brute force search for the moment, could be improved
+  for (unsigned i = 0; i < Records.size(); i++) {
+    StackMapRecord& Rec = Records[i];
+    if (Rec.InstructionOffset == RelPC) {
+      return Rec;
+    }
+  }
+  report_fatal_error("no record for offset into text section");
+  return *((StackMapRecord*)nullptr);
+}
+bool StackMapSection::hasRecordForRelPC(uint32_t RelPC) {
+  // brute force search for the moment, could be improved
+  for (unsigned i = 0; i < Records.size(); i++) {
+    StackMapRecord& Rec = Records[i];
+    if (Rec.InstructionOffset == RelPC) {
+      return true;
+    }
+  }
+  return false;
+}
+
 PatchPointOpers::PatchPointOpers(const MachineInstr *MI)
   : MI(MI),
     HasDef(MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
            !MI->getOperand(0).isImplicit()),
     IsAnyReg(MI->getOperand(getMetaIdx(CCPos)).getImm() == CallingConv::AnyReg)
 {
 #ifndef NDEBUG
   unsigned CheckStartIdx = 0, e = MI->getNumOperands();