[llvm-exegesis] Insert IACA markers

[oontvoo]

Summary

LLVM-EXEgesis - IACA analysis

About the project

IACA is a static performance analysis tool that Intel provides to developers for analysing low-level performance problems with their code. It contains specialized models for several high-end Intel CPUs, including instruction latencies. The goal of the project is to be able to compare these latencies with the data that are currently in LLVM, and with other simulators and benchmarks.
IACA is distributed only in binary form, neither the CPU models it contains have been open-sourced, and we can observe them only by running the models on certain pieces of code.

Project plan
The simplest way to analyse the data from IACA would be to get them into llvm-exegesis, as it already has functions for generating the benchmarked code, and also for analysing the output. It could be done as another BenchmarkRunner for llvm-exegesis, that:

• Produces an object file in the right format that can be processed by IACA. Llvm-exegesis already produces an object file that contains the benchmarked code, but this file does not have the IACA start/end markers. We would need to modify this function to be able to add the markers
• Runs IACA on that file: Implement a BenchmarkRunner that runs the IACA code. This could be as simple as launching the IACA binary, the path to which will be specified via command-line flag. (Because we cannot include/distribute the IACA binary)
• Parses the outputs and extracts the information needed by llvm-exegesis (the latency and the port pressure) and uses the llvm-exegesis analysis tools to process that information.

[oontvoo]

Updated the diff (got rid of the "third_party/..." in paths.

[RKSimon]

Please add context to the diff

[lebedev.ri]

Please add description to differential.
What is the goal? What is this solving?

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

10

Use "llvm/Support/raw_ostream.h"

17

This can't go here, it needs to go into x86-specific file

[oontvoo]

In D60851#1471981, @lebedev.ri wrote:

Please add description to differential.
What is the goal? What is this solving?

I've added additional details on the project. PTAL. Thanks!

[lebedev.ri]

The goal of the project is to be able to compare these latencies with the data that are currently in LLVM, and with other simulators and benchmarks.

Okay, that is the goal of the changes.
But what's the actual real endgoal?
Generating llvm schedule data from IACA data, not measurements?
I'm sorry if that question makes no sense, i may be unaware of some previous discussions about this.

Relevant: https://bugs.llvm.org/show_bug.cgi?id=38437

In D60851#1475928, @oontvoo wrote:

In D60851#1471981, @lebedev.ri wrote:

Please add description to differential.
What is the goal? What is this solving?

I've added additional details on the project. PTAL. Thanks!

Other comments weren't addressed though.
Also, please always upload all patches with full context (-U99999)

llvm/tools/llvm-exegesis/lib/InlineAsmMCExpr.h

2

Missing starting comment, wrong header guard

llvm/unittests/tools/llvm-exegesis/BenchmarkRunnerTest.cpp

13–20

All these look wrong

59

This is x86-specific, needs to go into x86/ dir

[courbet]

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

202

Please remove the debugging code.

llvm/tools/llvm-exegesis/lib/InlineAsmMCExpr.h

2

More specifically, every llvm file needs a header: https://llvm.org/docs/CodingStandards.html#file-headers.

12

I would ditch this intermediate class and only have IacaMarkerBytesMCExpr.

30

I don't think the namespace is really useful here.

45

I can see that :) Please remove the comment.

49

Ditto

llvm/unittests/tools/llvm-exegesis/BenchmarkRunnerTest.cpp

10

The file header is missing.

13

Did you build and run the tests ? This should not be compiling on your local checkout.

13

Hm, actually I see you're missing and entry in CMakeLists for this, so this is never built & run.

26

TestIacaBenchmarkRunner ?

51

I think you can remove these.

78

I think testing form string equality is a bit brittle. What about:

const auto IsImmOperand = [](int64_t Imm) {
  return AllOf(Property(&MCOperand::isImm, Eq(true)), Property(&MCOperand::getImm, Eq(Imm)));
};

const auto IsIacaMarkerOperand = ...;

EXPECT_THAT(Inst, ElementsAre(IsIacaMarkerOperand, IsImmOperand(1)))

88

why not call the real thing directly ?

122

s/maker/marker/ (same below)

127

Same remark as above: let's use matchers.

[RKSimon]

It looks like IACA has now reached EOL: https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

[oontvoo]

Withdrawing review request since IACA is going away. Thanks, all for the comments!

llvm/tools/llvm-exegesis/lib/Assembler.cpp

 
 #include "Assembler.h"
 
+#include "InlineAsmMCExpr.h"
 #include "Target.h"
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"

         Builder.addReg(Op.getReg(), Flags);
       } else if (Op.isImm()) {
         Builder.addImm(Op.getImm());
+      } else if (Op.isExpr() && Opcode == TargetOpcode::INLINEASM) {
+        Builder.addExternalSymbol(
+            cast<InlineAsmMCExpr>(Op.getExpr())->getAsmString());
       } else if (!Op.isValid()) {
         llvm_unreachable("Operand is not set");
       } else {

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h

   BenchmarkFailure(const llvm::Twine &S);
 };
 
+// Function to dump an MCInst to string.
+std::string DumpToString(const llvm::MCInst &inst);
+
 // Common code for all benchmark modes.
 class BenchmarkRunner {
 public:

   const LLVMState &State;
   const InstructionBenchmark::ModeE Mode;
 
+  static std::vector<llvm::MCInst>
+  GenerateInstructions(const BenchmarkCode &BC, const size_t MinInstructions,
+                       bool IncludeIacaMakers);
+
 private:
   virtual llvm::Expected<std::vector<BenchmarkMeasure>>
   runMeasurements(const FunctionExecutor &Executor) const = 0;

llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp

 //===----------------------------------------------------------------------===//
 
 #include <array>
+#include <iostream>
 #include <string>
 
 #include "Assembler.h"
 #include "BenchmarkRunner.h"
+#include "InlineAsmMCExpr.h"
 #include "MCInstrDescView.h"
+#include "MCTargetDesc/X86MCTargetDesc.h"
 #include "PerfHelper.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstBuilder.h"
 #include "llvm/Support/CrashRecoveryContext.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Program.h"
 
 namespace llvm {
 namespace exegesis {
+namespace {
+
+// Inserts IACA-start marker at the end of the given vector.
+void InsertStartMarker(std::vector<llvm::MCInst> &Instructions) {
+  // mov ebx, 111         ; IACA Start marker bytes
+  // db 0x64, 0x67, 0x90  ; IACA Start marker bytes
+  Instructions.push_back(
+      MCInstBuilder(llvm::X86::MOV32ri).addReg(llvm::X86::EBX).addImm(111));
+  Instructions.push_back(MCInstBuilder(TargetOpcode::INLINEASM)
+                             .addExpr(new iaca::IacaMarkerBytesMCExpr())
+                             // Because our IACA markers trap:
+                             .addImm(InlineAsm::Extra_HasSideEffects));
+}
+
+// Inserts IACA-end marker at the end of the given vector.
+void InsertEndMarker(std::vector<llvm::MCInst> &Instructions) {
+  // mov ebx, 222         ; IACA End marker bytes
+  // db 0x64, 0x67, 0x90  ; IACA End marker bytes
+  Instructions.push_back(
+      MCInstBuilder(llvm::X86::MOV32ri).addReg(llvm::X86::EBX).addImm(222));
+  Instructions.push_back(MCInstBuilder(TargetOpcode::INLINEASM)
+                             .addExpr(new iaca::IacaMarkerBytesMCExpr())
+                             // Because our IACA markers trap:
+                             .addImm(InlineAsm::Extra_HasSideEffects));
+}
+
+} // end of anonymous namespace
 
 BenchmarkFailure::BenchmarkFailure(const llvm::Twine &S)
     : llvm::StringError(S, llvm::inconvertibleErrorCode()) {}

 
 // Repeat the snippet until there are at least MinInstructions in the resulting
 // code.
-static std::vector<llvm::MCInst>
-GenerateInstructions(const BenchmarkCode &BC, const size_t MinInstructions) {
-  if (BC.Instructions.empty())
+std::vector<llvm::MCInst>
+BenchmarkRunner::GenerateInstructions(const BenchmarkCode &BC,
+                                      const size_t MinInstructions,
+                                      const bool IncludeIacaMakers) {
+  if (BC.Instructions.empty()) {
     return {};
-  std::vector<llvm::MCInst> Code = BC.Instructions;
-  for (int I = 0; Code.size() < MinInstructions; ++I)
+  }
+
+  std::vector<llvm::MCInst> Code;
+  Code.reserve(MinInstructions + (IncludeIacaMakers ? 4 : 0));
+
+  if (IncludeIacaMakers) {
+    InsertStartMarker(Code);
+  }
+
+  // Do not count the IACA markers when checking the size because these
+  // instructions are not executable.
+  const int AdjustedSize = MinInstructions + (IncludeIacaMakers ? 2 : 0);
+  for (int I = 0; Code.size() < AdjustedSize; ++I) {
     Code.push_back(BC.Instructions[I % BC.Instructions.size()]);
+  }
+
+  if (IncludeIacaMakers) {
+    InsertEndMarker(Code);
+  }
+
   return Code;
 }
 

 };
 } // namespace
 
+std::string DumpToString(const llvm::MCInst &inst) {
+  std::string buffer;
+  llvm::raw_string_ostream stream(buffer);
+  inst.print(stream);
+  stream.flush();
+  return buffer;
+}
+
 InstructionBenchmark
 BenchmarkRunner::runConfiguration(const BenchmarkCode &BC,
                                   unsigned NumRepetitions,

   // that the inside instructions are repeated.
   constexpr const int kMinInstructionsForSnippet = 16;
   {
-    auto ObjectFilePath = writeObjectFile(
-        BC, GenerateInstructions(BC, kMinInstructionsForSnippet));
+    // NOTE(vyng): "IncludeIacaMarkers" must be false, regardless of the mode
+    // because we don't want to insert the markers around single snippet.
+    auto ObjectFilePath =
+        writeObjectFile(BC, GenerateInstructions(BC, kMinInstructionsForSnippet,
+                                                 /*IncludeIacaMakers=*/false));
     if (llvm::Error E = ObjectFilePath.takeError()) {
       InstrBenchmark.Error = llvm::toString(std::move(E));
       return InstrBenchmark;

 
   // Assemble NumRepetitions instructions repetitions of the snippet for
   // measurements.
-  const auto Code = GenerateInstructions(BC, InstrBenchmark.NumRepetitions);
+  // TODO(vyng): Change the IncludeIacaMarkers to the right value based on mode.
+  const auto Code = GenerateInstructions(BC, InstrBenchmark.NumRepetitions,
+                                         /*IncludeIacaMakers=*/false);
 
   llvm::object::OwningBinary<llvm::object::ObjectFile> ObjectFile;
+  // For debugging.
+  {
+    int i = 0;
+    llvm::outs() << "*** START genereated instructions: \n";
+    for (const auto &line : Code) {
+      llvm::outs() << i++ << ": " << DumpToString(line) << "\n";
+    }
+    llvm::outs() << "*** END genereated instructions \n";
+  }
+
   if (DumpObjectToDisk) {
     auto ObjectFilePath = writeObjectFile(BC, Code);
     if (llvm::Error E = ObjectFilePath.takeError()) {

llvm/tools/llvm-exegesis/lib/InlineAsmMCExpr.h

+#ifndef THIRD_PARTY_LLVM_LLVM_TOOLS_LLVM_EXEGESIS_INLINEASMMCEXPR_H_
+#define THIRD_PARTY_LLVM_LLVM_TOOLS_LLVM_EXEGESIS_INLINEASMMCEXPR_H_
+
+#include "llvm/MC/MCExpr.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace exegesis {
+
+// Class for emitting arbitrary inline-asm.
+class InlineAsmMCExpr : public MCTargetExpr {
+public:
+  virtual const char *getAsmString() const = 0;
+
+  void printImpl(raw_ostream &OS, const MCAsmInfo *MAI) const override {
+    OS << getAsmString();
+  }
+
+  bool evaluateAsRelocatableImpl(MCValue &Res, const MCAsmLayout *Layout,
+                                 const MCFixup *Fixup) const override {
+    return false;
+  }
+
+  bool inlineAssignedExpr() const override { return true; }
+
+  MCFragment *findAssociatedFragment() const override { return nullptr; }
+};
+
+namespace iaca {
+
+// Class for emitting IACA magic-bytes in start/end markers.
+class IacaMarkerBytesMCExpr : public InlineAsmMCExpr {
+public:
+  const char *getAsmString() const override { return ".byte 0x64, 0x67, 0x90"; }
+
+  bool isEqualTo(const MCExpr *X) const override {
+    if (dyn_cast<IacaMarkerBytesMCExpr>(X)) {
+      return true;
+    }
+    return false;
+  }
+
+  void visitUsedExpr(MCStreamer &Streamer) const override {
+    /* Does nothing. */
+  }
+
+  void fixELFSymbolsInTLSFixups(MCAssembler &Asm) const override {
+    /* Does nothing. */
+  }
+};
+
+} // namespace iaca
+} // namespace exegesis
+} // namespace llvm
+#endif // THIRD_PARTY_LLVM_LLVM_TOOLS_LLVM_EXEGESIS_INLINEASMMCEXPR_H_

llvm/unittests/tools/llvm-exegesis/BenchmarkRunnerTest.cpp

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
+#include "third_party/absl/flags/flag.h"
+#include "third_party/llvm/llvm/include/llvm/MC/MCExpr.h"
+#include "third_party/llvm/llvm/include/llvm/MC/MCInst.h"
+#include "third_party/llvm/llvm/include/llvm/MC/MCInstBuilder.h"
+#include "third_party/llvm/llvm/lib/Target/X86/MCTargetDesc/X86MCTargetDesc.h"
+#include "third_party/llvm/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h"
+#include "third_party/llvm/llvm/tools/llvm-exegesis/lib/InlineAsmMCExpr.h"
+#include "third_party/llvm/llvm/tools/llvm-exegesis/lib/RegisterValue.h"
+
 namespace llvm {
 namespace exegesis {
-
 namespace {
 
+class IacaBenchmarkRunnerTester : public BenchmarkRunner {
+public:
+  IacaBenchmarkRunnerTester()
+      : BenchmarkRunner(LLVMState(""), InstructionBenchmark::ModeE::Latency) {}
+  ~IacaBenchmarkRunnerTester() = default;
+
+protected:
+  // Exposed for testing.
+  using BenchmarkRunner::GenerateInstructions;
+
+  llvm::Expected<std::vector<BenchmarkMeasure>>
+  runMeasurements(const FunctionExecutor &Executor) const override {
+    // This does nothing because we're only testing the generation of IACA
+    // start/end markers.
+    // TODO: Change this once we've plugged in the iaca backend.
+    return std::vector<BenchmarkMeasure>();
+  }
+
+  friend class IacaBenchmarkRunnerTest;
+};
+
+class IacaBenchmarkRunnerTest : public ::testing::Test {
+public:
+  IacaBenchmarkRunnerTest() : iaca_runner_(IacaBenchmarkRunnerTester()) {}
+
+  static void SetUpTestCase() {}
+  static void TearDownTestCase() {}
+
+  // Creates a piece of BenchmarkCode.
+  static BenchmarkCode MakeBenchmarkCode() {
+    BenchmarkCode Code;
+    Code.Info = "Random code.";
+
+    Code.LiveIns.push_back(llvm::X86::EAX);
+    Code.LiveIns.push_back(llvm::X86::EBX);
+    Code.LiveIns.push_back(llvm::X86::ECX);
+
+    Code.RegisterInitialValues.push_back(RegisterValue::zero(llvm::X86::EAX));
+    Code.RegisterInitialValues.push_back(RegisterValue::zero(llvm::X86::EBX));
+    Code.RegisterInitialValues.push_back(RegisterValue::zero(llvm::X86::ECX));
+
+    Code.Instructions.push_back(
+        MCInstBuilder(llvm::X86::MOV32ri).addReg(llvm::X86::EAX).addImm(10));
+    Code.Instructions.push_back(
+        MCInstBuilder(llvm::X86::ADD32ri).addReg(llvm::X86::EAX).addImm(220));
+
+    return Code;
+  }
+
+  // Checks that the argument is the IACA magic bytes.
+  // .byte 0x64, 0x67, 0x90
+  static void AssertIacaMagicBytesInstruction(const llvm::MCInst &Inst) {
+    const std::string InstructionDump = DumpToString(Inst);
+    EXPECT_EQ(TargetOpcode::INLINEASM, Inst.getOpcode())
+        << "Instruction dump: " << InstructionDump;
+    EXPECT_EQ(2, Inst.getNumOperands())
+        << "Instruction dump: " << InstructionDump;
+    EXPECT_EQ(
+        "<MCInst 1 <MCOperand Expr:(.byte 0x64, 0x67, 0x90)> <MCOperand Imm:1>>",
+        InstructionDump);
+  }
+
+  // Wrapper function that simply passes through the arguments to the real
+  // function.
+  std::vector<llvm::MCInst> GenerateInstructions(const BenchmarkCode &BC,
+                                                 const size_t MinInstructions,
+                                                 bool IncludeIacaMakers) {
+    return iaca_runner_.GenerateInstructions(BC, MinInstructions,
+                                             IncludeIacaMakers);
+  }
+
+protected:
+  IacaBenchmarkRunnerTester iaca_runner_;
+};
+
 TEST(ScratchSpaceTest, Works) {
   BenchmarkRunner::ScratchSpace Space;
   EXPECT_EQ(reinterpret_cast<intptr_t>(Space.ptr()) %

   EXPECT_EQ(Space.ptr()[BenchmarkRunner::ScratchSpace::kSize - 1], 0);
 }
 
+TEST_F(IacaBenchmarkRunnerTest, IacaMarkers) {
+  const BenchmarkCode Code = MakeBenchmarkCode();
+  const std::vector<llvm::MCInst> GeneratedInstructions =
+      GenerateInstructions(Code, Code.Instructions.size(),
+                           /*IncludeIacaMakers=*/true);
+
+  EXPECT_EQ(/*two 2-instruction markers + original size*/
+            Code.Instructions.size() + 4, GeneratedInstructions.size());
+
+  // Start-maker
+  {
+    const llvm::MCInst &FirstInst = GeneratedInstructions.at(0);
+    const std::string FirstInstDump = DumpToString(FirstInst);
+
+    EXPECT_EQ(llvm::X86::MOV32ri, FirstInst.getOpcode())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(2, FirstInst.getNumOperands())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(llvm::X86::EBX, FirstInst.getOperand(0).getReg())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(111, FirstInst.getOperand(1).getImm())
+        << "Instruction dump: " << FirstInstDump;
+
+    AssertIacaMagicBytesInstruction(GeneratedInstructions.at(1));
+  }
+
+  // End-maker
+  {
+    const llvm::MCInst &FirstInst =
+        GeneratedInstructions.at(GeneratedInstructions.size() - 2);
+    std::string FirstInstDump = DumpToString(FirstInst);
+    EXPECT_EQ(llvm::X86::MOV32ri, FirstInst.getOpcode())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(2, FirstInst.getNumOperands())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(llvm::X86::EBX, FirstInst.getOperand(0).getReg())
+        << "Instruction dump: " << FirstInstDump;
+    EXPECT_EQ(222, FirstInst.getOperand(1).getImm())
+        << "Instruction dump: " << FirstInstDump;
+
+    AssertIacaMagicBytesInstruction(
+        GeneratedInstructions.at(GeneratedInstructions.size() - 1));
+  }
+}
+
 } // namespace
 } // namespace exegesis
 } // namespace llvm