Introduce StructuredData

[nhaehnle]

Summary

StructuredData is a fairly general mechanism for representing extensible
data in textual IR and in bitcode.

It is intended primarily as an abstraction layer used during IR printing,
parsing and (bitcode de-)serialization.

However, it can also be used to preserve structured data as-is for
extension points in tools where a particular extension isn't understood.

Possible use cases range over:

• Encoding TargetTypeInfo -- this is the use case that initially triggered this development
• Extensible human-readable and compile-time efficient metadata a la debug info metadata
• Human-readable and compile-time efficient modifiers on extended instructions / intrinsics

This change already includes rudimentary printing and parsing support.
Bitcode reading and writing will follow in a subsequent change.

[Flakebi]

Why does the symbol map need to be global, shouldn’t it by per LLVMContext (which would also get rid of the locking)?

Needs tests.

llvm/docs/LangRef.rst

3527–3531

Can constants follow the way metadata (and most other things in LLVM) is encoded and prefix the type?
I.e. i32 <integer> and i1 true/false

[nhaehnle]

Thanks for taking a look!

In D150370#4349276, @Flakebi wrote:

Why does the symbol map need to be global, shouldn’t it by per LLVMContext (which would also get rid of the locking)?

It's global so that we can cheaply compare an sdata::Symbol against an sdata::RegisterSymbol. This is used e.g. here: https://github.com/nhaehnle/llvm-project/blob/6bb5923a059c1120e006cb0d0cd63c5ef0806c0e/llvm/lib/IR/Type.cpp#L844

Needs tests.

What kind of tests do you have in mind? This change doesn't really expose anything, and there are tests in the followup change in the stack.

llvm/docs/LangRef.rst

3527–3531

Good question. I've been going back and forth on this, and the current version is as-is mostly because the various !DIxyz metadata doesn't have those prefixes. But that may not be the best example to follow.

I'd be happy to change it to be more in line with metadata. Any other opinions?

[Flakebi]

What kind of tests do you have in mind?

I thought about tests for the parsing and printing code. I missed that the code is not yet used here, so please ignore my comment from before :)

Having global state makes things easy at the start (and efficient in the case here), but I fear we will run into problems later, for example when unloading and reloading libLLVM. There is a precedent for globals, command line arguments are global state and it is problematic.

The TargetTypeInfoDeserialize::registerSymbols() call is in the LLVMContext constructor, so it does not seem far-fetched to me to make symbols part of the context.

llvm/docs/LangRef.rst

3527–3531

But that may not be the best example to follow.

I once tried to write a parser for !DI metadata (tree-sitter, for syntax highlighting) and gave up because there were more and more edge-cases, so I’d be happy to see a more structured format ;)

[nhaehnle]

llvm/docs/LangRef.rst

3527–3531

I'm going ahead and changing it to have the iN prefix. As a reasonable (I believe) consequence, the bit width is now actually part of the value, so if a user wants to distinguish between i7 0 and i9 0, they can.

[nhaehnle]

Add iN prefix to integers (and bool) in structured data values

[nikic]

I am very concerned about making this a global structure, rather than something bound to the context.

More generally, I'm not happy that this new concept is being introduced as part of the target type implementation. This doesn't really seem helpful for this specific use case (it makes the implementation substantially more complex rather than simpler). It may well make sense as part of some larger context, but I think this larger context deserves a wider discussion (probably on discourse) to clarify what the goals of this abstraction are and make sure we have a good design for it.

[nhaehnle]

More generally, I'm not happy that this new concept is being introduced as part of the target type implementation. This doesn't really seem helpful for this specific use case (it makes the implementation substantially more complex rather than simpler). It may well make sense as part of some larger context, but I think this larger context deserves a wider discussion (probably on discourse) to clarify what the goals of this abstraction are and make sure we have a good design for it.

Sure. It's a bit of a chicken-and-egg thing. I do think this approach is better than the piecemeal addition of things to bitcode reader/writer, which is rather subtle code that I don't think too many people understand, but at the same time, working on big changes is frustrating unless you have clear line-of-sight to actually getting something useful upstream. So I started with this small thing quite consciously on purpose.

I have a WIP change locally that leverages the same infrastructure for "extended metadata", and at least an early minimal version that does something interesting is something that I think I can put up reasonably soon so that the discussion doesn't end up overly abstract. I would also like to do the same thing for "extended instructions", but that's still a bit further out.

[nhaehnle]

I am very concerned about making this a global structure, rather than something bound to the context.

You mean the symbol registration? That's ultimately a performance tradeoff. I wanted to avoid having too many string comparisons in potential hot paths, which requires interning, which requires some way to get at the intern'd ID that isn't too horrible. It would be good to understand what the actual concerns are with it; the intention is that the size of this structure is bounded by the number of static variables, so there isn't an urgent need (or even ability) to reclaim anything. But I would be happier about it if I had a way to enforce that.

[nikic]

In D150370#4435746, @nhaehnle wrote:

More generally, I'm not happy that this new concept is being introduced as part of the target type implementation. This doesn't really seem helpful for this specific use case (it makes the implementation substantially more complex rather than simpler). It may well make sense as part of some larger context, but I think this larger context deserves a wider discussion (probably on discourse) to clarify what the goals of this abstraction are and make sure we have a good design for it.

Sure. It's a bit of a chicken-and-egg thing. I do think this approach is better than the piecemeal addition of things to bitcode reader/writer, which is rather subtle code that I don't think too many people understand, but at the same time, working on big changes is frustrating unless you have clear line-of-sight to actually getting something useful upstream. So I started with this small thing quite consciously on purpose.

I have a WIP change locally that leverages the same infrastructure for "extended metadata", and at least an early minimal version that does something interesting is something that I think I can put up reasonably soon so that the discussion doesn't end up overly abstract. I would also like to do the same thing for "extended instructions", but that's still a bit further out.

FWIW, I do think this is pretty reasonable when seen as a pure IR/bitcode abstraction. I wouldn't have concerns if this were (initially at least) represented as std::pair<StringRef, sdata::Value> and only used as part of reading/writing. That use case doesn't really need any of the Symbol machinery -- we get these as strings in IR/bitcode anyway, and I don't think there is a substantial performance difference between interning the strings and then comparing IDs compared to directly comparing to a small handful of strings, during parsing only.

The design you have makes a lot more sense if the sdata is supposed to be used as part of the in-memory IR as well, in which case the Symbols are important for more efficient access -- but I'm not sure if they are ideal in that context either. That would still require that we have Symbols and Values (std::variant, ugh) in the representation. Ideally we'd just have a C++ struct with properly typed members, and sdata only being used for the purposes of serializing/deserializing those structs using a general mechanism, without requiring new asm/bitcode support each time.

llvm/include/llvm/IR/StructuredData.h

26

Unused

177

Not used in this patch -- move to the last one?

[nhaehnle]

Drop symbols-as-values for now

[nhaehnle]

In D150370#4435919, @nikic wrote:

In D150370#4435746, @nhaehnle wrote:

More generally, I'm not happy that this new concept is being introduced as part of the target type implementation. This doesn't really seem helpful for this specific use case (it makes the implementation substantially more complex rather than simpler). It may well make sense as part of some larger context, but I think this larger context deserves a wider discussion (probably on discourse) to clarify what the goals of this abstraction are and make sure we have a good design for it.

Sure. It's a bit of a chicken-and-egg thing. I do think this approach is better than the piecemeal addition of things to bitcode reader/writer, which is rather subtle code that I don't think too many people understand, but at the same time, working on big changes is frustrating unless you have clear line-of-sight to actually getting something useful upstream. So I started with this small thing quite consciously on purpose.

I have a WIP change locally that leverages the same infrastructure for "extended metadata", and at least an early minimal version that does something interesting is something that I think I can put up reasonably soon so that the discussion doesn't end up overly abstract. I would also like to do the same thing for "extended instructions", but that's still a bit further out.

FWIW, I do think this is pretty reasonable when seen as a pure IR/bitcode abstraction. I wouldn't have concerns if this were (initially at least) represented as std::pair<StringRef, sdata::Value> and only used as part of reading/writing. That use case doesn't really need any of the Symbol machinery -- we get these as strings in IR/bitcode anyway, and I don't think there is a substantial performance difference between interning the strings and then comparing IDs compared to directly comparing to a small handful of strings, during parsing only.

The design you have makes a lot more sense if the sdata is supposed to be used as part of the in-memory IR as well, in which case the Symbols are important for more efficient access -- but I'm not sure if they are ideal in that context either. That would still require that we have Symbols and Values (std::variant, ugh) in the representation. Ideally we'd just have a C++ struct with properly typed members, and sdata only being used for the purposes of serializing/deserializing those structs using a general mechanism, without requiring new asm/bitcode support each time.

Hmm, perhaps that has been a case of premature optimization.

Indeed my intention is that "known" extended structures (in the general sense) are represented as C++ structs with properly typed members in live IR. The only exception are "generic" extended structures which are used as a fallback in-memory representation to preserve as a black-box any extension structures that are unknown. That is, in our graphics compiler my current thinking is for us to have extended metadata objects along the lines of:

!lgc.rasterizer.state { discardEnable: i1 true, perSampleShading: i1 false, ... }

In our compiler, these would be represented as an instance of an lgc::RasterizerStateMetadata class which is derived from an llvm::ExtMetadata base class and contains these fields as plain data. But when we write out intermediate IR with something like -stop-after and then run it through generic tools like opt, llvm-dis, etc., the same metadata object is represented by a llvm::GenericExtMetadata which just holds an array of std::pair<sdata::Symbol, sdata::Value>. But perhaps that could just be a std::pair<std::string, sdata::Value> instead because nobody really accesses these fields anyway.

I'll think about this some more but removing the Symbol stuff and just replacing by StringRef is starting to sound reasonable to me.

llvm/include/llvm/IR/StructuredData.h

26

(only MDNode is truly unused, removing that)

177

Sure

[nhaehnle]

Move SchemaField out of this patch

[nhaehnle]

Main change is removal of sdata::Symbol in favor of plain StringRef

[nhaehnle]

I think this larger context deserves a wider discussion

I started a thread on Discourse: https://discourse.llvm.org/t/rfc-structured-data-for-extensibility-in-llvm-ir/71527

[arsenm]

Missing all the assembler tests (but I guess they come with the bitcode parts?)

llvm/include/llvm/IR/StructuredData.h

70

Does std::get on variant not do this for you?

llvm/lib/IR/AsmWriter.cpp

1345

seems more like a report_fatal_error kind of case

[nhaehnle]

In D150370#4440349, @arsenm wrote:

Missing all the assembler tests (but I guess they come with the bitcode parts?)

Yeah, the assembler tests are with the actual use cases of this infrastructure in the next patch.

llvm/include/llvm/IR/StructuredData.h

70

std::get throws on error and we disable exceptions in LLVM. I'm not sure what that means in practice so thought it safest to add the assertion.

llvm/lib/IR/AsmWriter.cpp

1345

Really? I thought report_fatal_error was primarily for states that can be reached by bad input. This state here cannot be reached by bad input, but only by somebody extending sdata::Value and then forgetting to change this code.

[nikic]

Thanks for providing the context for this functionality. The updated patch looks good to me. I think even if we never end up introducing more uses for this, this is not going to be an undue burden, so I think it's okay to move forward with the target type use case.

llvm/include/llvm/IR/StructuredData.h

18

DenseMap is not used.

36

Why do we need this class to be default-constructible? (I presume this is also why there is a monostate in the storage?)

llvm/lib/AsmParser/LLParser.cpp

4213

Okay, I guess this is where the default initialization is used. Possibly this should be std::optional instead -- or parse the sdata value in a separate function and return it?

llvm/lib/IR/StructuredData.cpp

23

Structured

llvm/docs/LangRef.rst

 source file name to the local function name.
 
 The syntax for the source file name is simply:
 
 .. code-block:: text
 
     source_filename = "/path/to/source.c"
 
+.. _structured_data:
+
+Structured Data
+---------------
+
+Dictionaries of key-value pairs are used in some cases to represent data in an
+easily extendable, human-readable manner.
+
+The labels used in key-value pairs are identifiers followed immediately by a
+colon (':'), like the label of a named basic block.
+
+:Syntax:
+
+::
+
+    sdata       ::= '{' (sdata_field ',')* sdata_field? '}'
+    sdata_field ::= label sdata_value
+    sdata_value ::= 'type' type
+                ::= 'iN' integer
+                ::= 'i1' 'true' | 'i1' 'false'
+
+:Examples:
+
+::
+
+    {}
+    { layout: type float, }
+    { foo: i1 true, bar: i32 10 }
+
 .. _typesystem:
 
 Type System
 ===========
 
 The LLVM type system is one of the most important features of the
 intermediate representation. Being typed enables a number of
 optimizations to be performed on the intermediate representation

llvm/include/llvm/AsmParser/LLParser.h

 
 #include "LLLexer.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/FMF.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
+#include "llvm/IR/StructuredData.h"
 #include <map>
 #include <optional>
 
 namespace llvm {
   class Module;
   class ConstantRange;
   class FunctionType;
   class GlobalObject;
private:
     bool parseMDNode(MDNode *&N);
     bool parseMDNodeTail(MDNode *&N);
     bool parseMDNodeVector(SmallVectorImpl<Metadata *> &Elts);
     bool parseMetadataAttachment(unsigned &Kind, MDNode *&MD);
     bool parseInstructionMetadata(Instruction &Inst);
     bool parseGlobalObjectMetadataAttachment(GlobalObject &GO);
     bool parseOptionalFunctionMetadata(Function &F);
 
+    bool parseStructuredData(
+        function_ref<bool(LocTy, StringRef, LocTy, sdata::Value)>
+            ParseField);
+
     template <class FieldTy>
     bool parseMDField(LocTy Loc, StringRef Name, FieldTy &Result);
     template <class FieldTy> bool parseMDField(StringRef Name, FieldTy &Result);
     template <class ParserTy> bool parseMDFieldsImplBody(ParserTy ParseField);
     template <class ParserTy>
     bool parseMDFieldsImpl(ParserTy ParseField, LocTy &ClosingLoc);
     bool parseSpecializedMDNode(MDNode *&N, bool IsDistinct = false);
 

llvm/include/llvm/IR/StructuredData.h

+//===- llvm/IR/StructuredData.h ---------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides structured data objects that are used as an intermediate
+// abstraction for (de)serializing extensible IR objects.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_STRUCTUREDDATA_H
+#define LLVM_IR_STRUCTUREDDATA_H
+
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+
+class Type;
+
+namespace sdata {
+
+/// A value of structured data.
+class Value {
+private:
+  using Storage = std::variant<std::monostate, APInt, Type *>;
+
+  Storage S;
+
+public:
+  Value() = default;
+  explicit Value(Type *T) : S(T) {}
+  explicit Value(bool B) : S(APInt(1, B ? 1 : 0)) {}
+  explicit Value(APInt I) : S(I) {}
+
+  Value &operator=(Type *T) {
+    assert(T);
+    S = T;
+    return *this;
+  }
+  Value &operator=(bool B) {
+    S = APInt(1, B ? 1 : 0);
+    return *this;
+  }
+  Value &operator=(APInt I) {
+    S = I;
+    return *this;
+  }
+
+  bool isAPInt() const { return std::holds_alternative<APInt>(S); }
+  bool isBool() const {
+    return isAPInt() && std::get<APInt>(S).getBitWidth() == 1;
+  }
+  bool isType() const { return std::holds_alternative<Type *>(S); }
+
+  const APInt &getAPInt() const {
+    assert(isAPInt());
+    return std::get<APInt>(S);
+  }
+  bool getBool() const {
+    assert(isBool());
+    return std::get<APInt>(S).getZExtValue();
+  }
+  Type *getType() const {
+    assert(isType());
+    return std::get<Type *>(S);
+  }
+};
+
+// Convenience function to create an Error object when an error is encountered
+// while deserializing structured data.
+Error makeDeserializeError(const Twine &Msg);
+
+} // end namespace sdata
+
+} // end namespace llvm
+
+#endif

llvm/lib/AsmParser/LLParser.cpp

do {
     if (parseGlobalTypeAndValue(C))
       return true;
     Elts.push_back(C);
   } while (EatIfPresent(lltok::comma));
 
   return false;
 }
 
+/// parseStructuredData
+///   ::= '{' (key value (',' key value))? ','? '}'
+///
+/// value ::= 'type' type
+///       ::= 'i1' 'true' | 'i1' 'false'
+///       ::= 'iN' integer
+bool LLParser::parseStructuredData(
+    function_ref<bool(LocTy, StringRef, LocTy, sdata::Value)> ParseField) {
+  if (parseToken(lltok::lbrace, "expected '{' here"))
+    return true;
+
+  while (Lex.getKind() != lltok::rbrace) {
+    if (Lex.getKind() != lltok::LabelStr)
+      return tokError("expected '}' or field label here");
+
+    LocTy KeyLoc = Lex.getLoc();
+    std::string Key = Lex.getStrVal();
+    Lex.Lex();
+
+    LocTy ValueLoc = Lex.getLoc();
+    sdata::Value V;
+    switch (Lex.getKind()) {
+    case lltok::kw_type: {
+      Lex.Lex(); // eat 'type'
+
+      Type *T;
+      if (parseType(T, /*AllowVoid=*/true))
+        return true;
+
+      V = sdata::Value(T);
+      break;
+    }
+    case lltok::Type: {
+      Type *Ty = Lex.getTyVal();
+      if (auto *IntTy = dyn_cast<IntegerType>(Ty)) {
+        Lex.Lex();
+
+        switch (Lex.getKind()) {
+        case lltok::APSInt:
+          V = sdata::Value(Lex.getAPSIntVal().extOrTrunc(IntTy->getBitWidth()));
+          Lex.Lex();
+          break;
+        case lltok::kw_true:
+        case lltok::kw_false:
+          if (IntTy->getBitWidth() != 1)
+            return tokError("true/false can only be used with i1");
+          V = sdata::Value(Lex.getKind() == lltok::kw_true);
+          Lex.Lex();
+          break;
+        default:
+          return tokError("expected an integer value");
+        }
+
+        break;
+      }
+
+      return tokError("only integer types are supported in structured data");
+    }
+
+    default:
+      return tokError("expected structured data value");
+    }
+
+    if (ParseField(KeyLoc, Key, ValueLoc, V))
+      return true;
+
+    if (Lex.getKind() == lltok::rbrace)
+      break;
+    if (parseToken(lltok::comma, "expected ',' or '}' here"))
+      return true;
+  }
+
+  Lex.Lex(); // eat the '}'
+  return false;
+}
+
 bool LLParser::parseMDTuple(MDNode *&MD, bool IsDistinct) {
   SmallVector<Metadata *, 16> Elts;
   if (parseMDNodeVector(Elts))
     return true;
 
   MD = (IsDistinct ? MDTuple::getDistinct : MDTuple::get)(Context, Elts);
   return false;
 }

llvm/lib/IR/AsmWriter.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/StructuredData.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/TypeFinder.h"
 #include "llvm/IR/TypedPointerType.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
struct AsmWriterContext {
   virtual ~AsmWriterContext() = default;
 };
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // AsmWriter Implementation
 //===----------------------------------------------------------------------===//
 
+static void printStructuredData(
+    raw_ostream &Out, ArrayRef<std::pair<StringRef, sdata::Value>> Fields,
+    AsmWriterContext &Ctx) {
+  Out << "{\n";
+  for (const auto &Field : Fields) {
+    Out << "  " << Field.first << ": ";
+    if (Field.second.isBool()) {
+      if (Field.second.getBool())
+        Out << "i1 true";
+      else
+        Out << "i1 false";
+    } else if (Field.second.isAPInt()) {
+      const APInt &I = Field.second.getAPInt();
+      Out << 'i' << I.getBitWidth() << ' ' << I;
+    } else if (Field.second.isType()) {
+      Out << "type ";
+      Ctx.TypePrinter->print(Field.second.getType(), Out);
+    } else {
+      llvm_unreachable("unhandled sdata::Value type");
+    }
+    Out << ",\n";
+  }
+  Out << '}';
+}
+
 static void WriteAsOperandInternal(raw_ostream &Out, const Value *V,
                                    AsmWriterContext &WriterCtx);
 
 static void WriteAsOperandInternal(raw_ostream &Out, const Metadata *MD,
                                    AsmWriterContext &WriterCtx,
                                    bool FromValue = false);
 
 static void WriteOptimizationInfo(raw_ostream &Out, const User *U) {

llvm/lib/IR/CMakeLists.txt

add_llvm_component_library(LLVMCore
   PrintPasses.cpp
   ProfDataUtils.cpp
   SafepointIRVerifier.cpp
   ProfileSummary.cpp
   PseudoProbe.cpp
   ReplaceConstant.cpp
   Statepoint.cpp
   StructuralHash.cpp
+  StructuredData.cpp
   Type.cpp
   TypedPointerType.cpp
   TypeFinder.cpp
   Use.cpp
   User.cpp
   Value.cpp
   ValueSymbolTable.cpp
   VectorBuilder.cpp

llvm/lib/IR/StructuredData.cpp

+//===- StructuredData.cpp -------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/StructuredData.h"
+
+using namespace llvm;
+using namespace sdata;
+
+namespace {
+
+enum class DeserializeErrorCode : int {
+  Generic = 1,
+};
+
+class DeserializeErrorCategory : public std::error_category {
+public:
+  const char *name() const noexcept override {
+    return "Structure Data Deserialize Error";
+  }
+
+  std::string message(int condition) const override {
+    return "Error while deserializing structured data";
+  }
+
+  static DeserializeErrorCategory &get() {
+    static DeserializeErrorCategory TheCategory;
+    return TheCategory;
+  }
+};
+
+} // anonymous namespace
+
+Error llvm::sdata::makeDeserializeError(const Twine &Msg) {
+  return createStringError(
+      std::error_code(static_cast<int>(DeserializeErrorCode::Generic),
+                      DeserializeErrorCategory::get()),
+      Msg);
+}