IR: Module summary representation for type identifiers; summary test scaffolding for lowertypetests.

[pcc]

Summary

Set up basic YAML I/O support for module summaries, plumb the summary into
the pass and add a few command line flags to test YAML I/O support. Bitcode
support to come separately, as will the code in LowerTypeTests that actually
uses the summary. Also add a couple of tests that pass by virtue of the pass
doing nothing with the summary (which happens to be the correct thing to do
for those tests).

Depends on D28014

[mehdi_amini]

I don't have any strong feeling against YAML, but we should take this decision for the full summary and not just for the "type test", so I'd like to hear from Teresa about that (in the past we were considering a LLVM "metadata" serialization instead, or similar, so that it can round-trip in the IR itself).

(I'm tired of the llvm-bcanalyzer tests for the summary, so any kind of textual serialization of the summaries for testing and debugging purpose will be welcome at this point)

llvm/include/llvm/IR/ModuleSummaryIndex.h

401 ↗

(On Diff #82293)

Is this supposed to be "per module" or should it end up global to the index? (My understanding was the latter but you implemented the former AFAICT).

646 ↗

(On Diff #82293)

Could these all go in an implementation file with proper forward declaration here?

llvm/test/Transforms/LowerTypeTests/import-unsat.ll

23 ↗

(On Diff #82293)

Can you add a one line comment about that this test is checking?

[mehdi_amini]

llvm/include/llvm/IR/ModuleSummaryIndex.h

646 ↗

(On Diff #82293)

Alternatively, what about extracting this into a separate header llvm/include/llvm/IR/ModuleSummaryIndexSerialization.h that would include llvm/include/llvm/IR/ModuleSummaryIndex.h (if necessary).

[tejohnson]

In D28041#629442, @mehdi_amini wrote:

I don't have any strong feeling against YAML, but we should take this decision for the full summary and not just for the "type test", so I'd like to hear from Teresa about that (in the past we were considering a LLVM "metadata" serialization instead, or similar, so that it can round-trip in the IR itself).

It would be optimal to have a serialization in the LLVM assembly format (I started to look into doing that some time ago but got side tracked - I was thinking not as metadata since we don't carry it internally as metadata, but a new format e.g. similar to the way attributes are emitted as a separate format not metadata). Rather than taking the trouble to emit as YAML, why not emit into the LLVM assembly from the start?

(I'm tired of the llvm-bcanalyzer tests for the summary, so any kind of textual serialization of the summaries for testing and debugging purpose will be welcome at this point)

llvm/include/llvm/IR/ModuleSummaryIndex.h

401 ↗

(On Diff #82293)

Mehdi: What makes this per-module vs global? The same ModuleSummaryIndex data structure is used for both the permodule index and the combined index.

pcc: Why no accessors for this map?

[mehdi_amini]

llvm/include/llvm/IR/ModuleSummaryIndex.h

401 ↗

(On Diff #82293)

Oh forget my comment, I mis-identified the enclosing class.

[pcc]

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

I don't have any strong feeling against YAML, but we should take this decision for the full summary and not just for the "type test", so I'd like to hear from Teresa about that (in the past we were considering a LLVM "metadata" serialization instead, or similar, so that it can round-trip in the IR itself).

It would be optimal to have a serialization in the LLVM assembly format (I started to look into doing that some time ago but got side tracked - I was thinking not as metadata since we don't carry it internally as metadata, but a new format e.g. similar to the way attributes are emitted as a separate format not metadata). Rather than taking the trouble to emit as YAML, why not emit into the LLVM assembly from the start?

It's far from clear to me that in assembly is the right way to go. It might be for the individual summaries but not necessarily for the combined summary as it isn't really a property of any specific module.

Given that, and also given that this format is for debugging/testing purposes only, we might as well do the easiest thing we can while still making our tests readable. For me that meant leveraging the existing YAML support in LLVM. If we ultimately decide that some other format is better, I would imagine that converting the tests to the new format would be easier if we start from YAML rather than bcanalyzer output.

[mehdi_amini]

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

I was thinking not as metadata since we don't carry it internally as metadata, but a new format e.g. similar to the way attributes are emitted as a separate format not metadata). Rather than taking the trouble to emit as YAML, why not emit into the LLVM assembly from the start?

(I'm tired of the llvm-bcanalyzer tests for the summary, so any kind of textual serialization of the summaries for testing and debugging purpose will be welcome at this point)

In D28041#629835, @pcc wrote:

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

It's far from clear to me that in assembly is the right way to go. It might be for the individual summaries but not necessarily for the combined summary as it isn't really a property of any specific module.

I agree, but we wouldn't want two different serializations for each of the cases (knowing that the in-memory datastructure is shared).

Given that, and also given that this format is for debugging/testing purposes only,

Isn't it true of the textual IR as well?

[tejohnson]

In D28041#629835, @pcc wrote:

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

It's far from clear to me that in assembly is the right way to go. It might be for the individual summaries but not necessarily for the combined summary as it isn't really a property of any specific module.

I agree, but we wouldn't want two different serializations for each of the cases (knowing that the in-memory datastructure is shared).

I was envisioning that in the combined index case it would be serialized to a separate file (similar to how we can save the combined index to a distinct bitcode file in bitcode format now), as LLVM assembly just containing the combined index (aka textual IR as Mehdi calls it below, I think we are talking about the same thing).

Given that, and also given that this format is for debugging/testing purposes only,

Isn't it true of the textual IR as well?

[pcc]

In D28041#629836, @mehdi_amini wrote:

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

I was thinking not as metadata since we don't carry it internally as metadata, but a new format e.g. similar to the way attributes are emitted as a separate format not metadata). Rather than taking the trouble to emit as YAML, why not emit into the LLVM assembly from the start?

(I'm tired of the llvm-bcanalyzer tests for the summary, so any kind of textual serialization of the summaries for testing and debugging purpose will be welcome at this point)

In D28041#629835, @pcc wrote:

In D28041#629749, @tejohnson wrote:

In D28041#629442, @mehdi_amini wrote:

It's far from clear to me that in assembly is the right way to go. It might be for the individual summaries but not necessarily for the combined summary as it isn't really a property of any specific module.

I agree, but we wouldn't want two different serializations for each of the cases (knowing that the in-memory datastructure is shared).

We could just have some way to embed a YAML "blob" in the asm. Yes it would be a little ugly, but it wouldn't really matter because debugging/testing. And again: this is all predicated on assembly being the "right" format.

Given that, and also given that this format is for debugging/testing purposes only,

Isn't it true of the textual IR as well?

Yes, but IR in YAML format would likely be unreadable, so if you follow my point to its conclusion, YAML would be a bad choice for the IR. On the other hand, summaries are more straightforwardly representable as YAML.

[pcc]

• Address review comments

llvm/include/llvm/IR/ModuleSummaryIndex.h

401 ↗

(On Diff #82293)

pcc: Why no accessors for this map?

I don't need them yet. That will come in a later change.

646 ↗

(On Diff #82293)

Separate header sounds better; done.

[mehdi_amini]

LGTM.

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/IR/Module.h"
 
 #include <array>
 
 namespace llvm {
 
+namespace yaml {
+template <typename T> struct MappingTraits;
+}
+
 /// \brief Class to accumulate and hold information about a callee.
 struct CalleeInfo {
   enum class HotnessType : uint8_t { Unknown = 0, Cold = 1, None = 2, Hot = 3 };
   HotnessType Hotness = HotnessType::Unknown;
 
   CalleeInfo() = default;
   explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
 
GlobalVarSummary(GVFlags Flags, std::vector<ValueInfo> Refs)
       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)) {}
 
   /// Check if this is a global variable summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == GlobalVarKind;
   }
 };
 
+struct TypeTestResolution {
+  /// Specifies which kind of type check we should emit for this byte array.
+  /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
+  /// details on each kind of check; the enumerators are described with
+  /// reference to that document.
+  enum Kind {
+    Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
+    ByteArray, ///< Test a byte array (first example)
+    Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
+    Single,    ///< Single element (last example in "Short Inline Bit Vectors")
+    AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
+               ///  All-Ones Bit Vectors")
+  } TheKind = Unsat;
+
+  /// Range of the size expressed as a bit width. For example, if the size is in
+  /// range [0,256), this number will be 8. This helps generate the most compact
+  /// instruction sequences.
+  unsigned SizeBitWidth = 0;
+};
+
+struct TypeIdSummary {
+  TypeTestResolution TTRes;
+};
+
 /// 160 bits SHA1
 typedef std::array<uint32_t, 5> ModuleHash;
 
 /// List of global value summary structures for a particular value held
 /// in the GlobalValueMap. Requires a vector in the case of multiple
 /// COMDAT values of the same name.
 typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
 

 private:
   /// Map from value name to list of summary instances for values of that
   /// name (may be duplicates in the COMDAT case, e.g.).
   GlobalValueSummaryMapTy GlobalValueMap;
 
   /// Holds strings for combined index, mapping to the corresponding module ID.
   ModulePathStringTableTy ModulePathStringTable;
 
+  /// Mapping from type identifiers to summary information for that type
+  /// identifier.
+  // FIXME: Add bitcode read/write support for this field.
+  std::map<std::string, TypeIdSummary> TypeIdMap;
+
+  // YAML I/O support.
+  friend yaml::MappingTraits<ModuleSummaryIndex>;
+
 public:
   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
   gvsummary_iterator end() { return GlobalValueMap.end(); }
   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
 
   /// Get the list of global value summary objects for a given value name.
   const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {

llvm/trunk/include/llvm/IR/ModuleSummaryIndexYAML.h

+//===-- llvm/ModuleSummaryIndexYAML.h - YAML I/O for summary ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_MODULESUMMARYINDEXYAML_H
+#define LLVM_IR_MODULESUMMARYINDEXYAML_H
+
+#include "llvm/IR/ModuleSummaryIndex.h"
+#include "llvm/Support/YAMLTraits.h"
+
+namespace llvm {
+namespace yaml {
+
+template <> struct ScalarEnumerationTraits<TypeTestResolution::Kind> {
+  static void enumeration(IO &io, TypeTestResolution::Kind &value) {
+    io.enumCase(value, "Unsat", TypeTestResolution::Unsat);
+    io.enumCase(value, "ByteArray", TypeTestResolution::ByteArray);
+    io.enumCase(value, "Inline", TypeTestResolution::Inline);
+    io.enumCase(value, "Single", TypeTestResolution::Single);
+    io.enumCase(value, "AllOnes", TypeTestResolution::AllOnes);
+  }
+};
+
+template <> struct MappingTraits<TypeTestResolution> {
+  static void mapping(IO &io, TypeTestResolution &res) {
+    io.mapRequired("Kind", res.TheKind);
+    io.mapRequired("SizeBitWidth", res.SizeBitWidth);
+  }
+};
+
+template <> struct MappingTraits<TypeIdSummary> {
+  static void mapping(IO &io, TypeIdSummary& summary) {
+    io.mapRequired("TTRes", summary.TTRes);
+  }
+};
+
+struct FunctionSummaryYaml {
+  std::vector<uint64_t> TypeTests;
+};
+
+} // End yaml namespace
+} // End llvm namespace
+
+LLVM_YAML_IS_SEQUENCE_VECTOR(uint64_t)
+
+namespace llvm {
+namespace yaml {
+
+template <> struct MappingTraits<FunctionSummaryYaml> {
+  static void mapping(IO &io, FunctionSummaryYaml& summary) {
+    io.mapRequired("TypeTests", summary.TypeTests);
+  }
+};
+
+} // End yaml namespace
+} // End llvm namespace
+
+LLVM_YAML_IS_STRING_MAP(TypeIdSummary)
+LLVM_YAML_IS_SEQUENCE_VECTOR(FunctionSummaryYaml)
+
+namespace llvm {
+namespace yaml {
+
+// FIXME: Add YAML mappings for the rest of the module summary.
+template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> {
+  static void inputOne(IO &io, StringRef Key, GlobalValueSummaryMapTy &V) {
+    std::vector<FunctionSummaryYaml> FSums;
+    io.mapRequired(Key.str().c_str(), FSums);
+    uint64_t KeyInt;
+    if (Key.getAsInteger(0, KeyInt)) {
+      io.setError("key not an integer");
+      return;
+    }
+    auto &Elem = V[KeyInt];
+    for (auto &FSum : FSums) {
+      GlobalValueSummary::GVFlags GVFlags(GlobalValue::ExternalLinkage, false,
+                                          false, false);
+      Elem.push_back(make_unique<FunctionSummary>(
+          GVFlags, 0, ArrayRef<ValueInfo>{},
+          ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests)));
+    }
+  }
+  static void output(IO &io, GlobalValueSummaryMapTy &V) {
+    for (auto &P : V) {
+      std::vector<FunctionSummaryYaml> FSums;
+      for (auto &Sum : P.second) {
+        if (auto *FSum = dyn_cast<FunctionSummary>(Sum.get()))
+          FSums.push_back(FunctionSummaryYaml{FSum->type_tests()});
+      }
+      if (!FSums.empty())
+        io.mapRequired(std::to_string(P.first).c_str(), FSums);
+    }
+  }
+};
+
+template <> struct MappingTraits<ModuleSummaryIndex> {
+  static void mapping(IO &io, ModuleSummaryIndex& index) {
+    io.mapRequired("GlobalValueMap", index.GlobalValueMap);
+    io.mapRequired("TypeIdMap", index.TypeIdMap);
+  }
+};
+
+} // End yaml namespace
+} // End llvm namespace
+
+#endif

llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/ModuleSummaryIndexYAML.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
 #include "llvm/Support/TrailingObjects.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 
 using namespace llvm;
 using namespace lowertypetests;
 
 #define DEBUG_TYPE "lowertypetests"
 
 STATISTIC(ByteArraySizeBits, "Byte array size in bits");
 STATISTIC(ByteArraySizeBytes, "Byte array size in bytes");
 STATISTIC(NumByteArraysCreated, "Number of byte arrays created");
 STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered");
 STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers");
 
 static cl::opt<bool> AvoidReuse(
     "lowertypetests-avoid-reuse",
     cl::desc("Try to avoid reuse of byte array addresses using aliases"),
     cl::Hidden, cl::init(true));
 
+static cl::opt<std::string> ClSummaryAction(
+    "lowertypetests-summary-action",
+    cl::desc("What to do with the summary when running this pass"), cl::Hidden);
+
+static cl::opt<std::string> ClReadSummary(
+    "lowertypetests-read-summary",
+    cl::desc("Read summary from given YAML file before running pass"),
+    cl::Hidden);
+
+static cl::opt<std::string> ClWriteSummary(
+    "lowertypetests-write-summary",
+    cl::desc("Write summary to given YAML file after running pass"),
+    cl::Hidden);
+
 bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const {
   if (Offset < ByteOffset)
     return false;
 
   if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0)
     return false;
 
   uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2;
public:
   ArrayRef<MDNode *> types() const {
     return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
   }
 };
 
 class LowerTypeTestsModule {
   Module &M;
 
+  // This is for testing purposes only.
+  std::unique_ptr<ModuleSummaryIndex> OwnedSummary;
+
   bool LinkerSubsectionsViaSymbols;
   Triple::ArchType Arch;
   Triple::OSType OS;
   Triple::ObjectFormatType ObjectFormat;
 
   IntegerType *Int1Ty = Type::getInt1Ty(M.getContext());
   IntegerType *Int8Ty = Type::getInt8Ty(M.getContext());
   IntegerType *Int32Ty = Type::getInt32Ty(M.getContext());
class LowerTypeTestsModule {
   void moveInitializerToModuleConstructor(GlobalVariable *GV);
   void findGlobalVariableUsersOf(Constant *C,
                                  SmallSetVector<GlobalVariable *, 8> &Out);
 
   void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
 
 public:
   LowerTypeTestsModule(Module &M);
+  ~LowerTypeTestsModule();
   bool lower();
 };
 
 struct LowerTypeTests : public ModulePass {
   static char ID;
   LowerTypeTests() : ModulePass(ID) {
     initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry());
   }
if (Globals.empty() || isa<GlobalVariable>(Globals[0]->getGlobal())) {
     }
 
     buildBitSetsFromFunctions(TypeIds, OrderedFns);
   }
 }
 
 /// Lower all type tests in this module.
 LowerTypeTestsModule::LowerTypeTestsModule(Module &M) : M(M) {
+  // Handle the command-line summary arguments. This code is for testing
+  // purposes only, so we handle errors directly.
+  if (!ClSummaryAction.empty()) {
+    OwnedSummary = make_unique<ModuleSummaryIndex>();
+    if (!ClReadSummary.empty()) {
+      ExitOnError ExitOnErr("-lowertypetests-read-summary: " + ClReadSummary +
+                            ": ");
+      auto ReadSummaryFile =
+          ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary)));
+
+      yaml::Input In(ReadSummaryFile->getBuffer());
+      In >> *OwnedSummary;
+      ExitOnErr(errorCodeToError(In.error()));
+    }
+  }
+
   Triple TargetTriple(M.getTargetTriple());
   LinkerSubsectionsViaSymbols = TargetTriple.isMacOSX();
   Arch = TargetTriple.getArch();
   OS = TargetTriple.getOS();
   ObjectFormat = TargetTriple.getObjectFormat();
 }
 
+LowerTypeTestsModule::~LowerTypeTestsModule() {
+  if (ClSummaryAction.empty() || ClWriteSummary.empty())
+    return;
+
+  ExitOnError ExitOnErr("-lowertypetests-write-summary: " + ClWriteSummary +
+                        ": ");
+  std::error_code EC;
+  raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text);
+  ExitOnErr(errorCodeToError(EC));
+
+  yaml::Output Out(OS);
+  Out << *OwnedSummary;
+}
+
 bool LowerTypeTestsModule::lower() {
   Function *TypeTestFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
   if (!TypeTestFunc || TypeTestFunc->use_empty())
     return false;
 
   // Equivalence class set containing type identifiers and the globals that
   // reference them. This is used to partition the set of type identifiers in

llvm/trunk/test/Transforms/LowerTypeTests/Inputs/import-unsat.yaml

+---
+GlobalValueMap:
+  42:
+    - TypeTests: [123]
+TypeIdMap:
+  typeid1:
+    TTRes:
+      Kind: Unsat
+      SizeBitWidth: 0
+...

llvm/trunk/test/Transforms/LowerTypeTests/export-nothing.ll

+; RUN: opt -lowertypetests -lowertypetests-summary-action=export -lowertypetests-write-summary=%t -o /dev/null %s
+; RUN: FileCheck %s < %t
+
+; CHECK: ---
+; CHECK-NEXT: GlobalValueMap:
+; CHECK-NEXT: TypeIdMap:
+; CHECK-NEXT: ...

llvm/trunk/test/Transforms/LowerTypeTests/import-unsat.ll

+; Test that we correctly import an unsat resolution for type identifier "typeid1".
+; FIXME: We should not require -O2 to simplify this to return false.
+; RUN: opt -S -lowertypetests -lowertypetests-summary-action=import -lowertypetests-read-summary=%S/Inputs/import-unsat.yaml -lowertypetests-write-summary=%t -O2 < %s | FileCheck %s
+; RUN: FileCheck --check-prefix=SUMMARY %s < %t
+
+; SUMMARY:      GlobalValueMap:
+; SUMMARY-NEXT:   42:
+; SUMMARY-NEXT:     - TypeTests:
+; SUMMARY-NEXT:         - 123
+; SUMMARY-NEXT: TypeIdMap:
+; SUMMARY-NEXT:   typeid1:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeBitWidth:    0
+
+target datalayout = "e-p:32:32"
+
+declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
+
+define i1 @foo(i8* %p) {
+  %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
+  ; CHECK: ret i1 false
+  ret i1 %x
+}