[WIP][llvm-exegesis] Add support for memory instructions in latency mode.

[courbet]

Summary

This only supports instructions that touch memory without being serial
*through* memory right now: ADD64rm is supported, ADD64mr is not.

Note tthat this doe snot take memory latency into account, e.g. latency for ADD64rm will be 1.

[lebedev.ri]

Is something like this still planned?
Looks like this 'kinda' stalled.

[courbet]

In D54318#1363448, @lebedev.ri wrote:

Is something like this still planned?
Looks like this 'kinda' stalled.

We have not had time to work on that recently, but it's something we want to have eventually. The reason why I did not submit this is that "this only supports instructions that touch memory without being serial": it's a bit restrictive, I'd like to do better than that to avoid giving misleading results when this assumption is not met (we should at least detect it).

tools/llvm-exegesis/lib/Latency.cpp

else {
     if (Instr.hasAliasingRegisters())
       EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
     if (Instr.hasOneUseOrOneDef())
       EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
   }
   return EM;
 }
 
+// Instanciates memory operands for instructions that happen to touch memory but
+// are not serial through memory. We just need to ensure that all instruction in
+// the serial sequence use non-overlapping memory spans.
+static void instantiateMemoryOperands(const LLVMState &State,
+                                      CodeTemplate &CT) {
+  if (CT.ScratchSpacePointerInReg == 0)
+    return; // no memory operands.
+  const auto &ET = State.getExegesisTarget();
+  const unsigned MemStep = ET.getMaxMemoryAccessSize();
+  size_t I = 0;
+  for (InstructionTemplate &IT : CT.Instructions) {
+    ET.fillMemoryOperands(IT, CT.ScratchSpacePointerInReg, I * MemStep);
+    ++I;
+  }
+}
+
 static void appendCodeTemplates(const LLVMState &State,
                                 const Instruction &Instr,
                                 ExecutionMode ExecutionModeBit,
                                 llvm::StringRef ExecutionClassDescription,
+                                const unsigned ScratchSpacePointerInReg,
                                 std::vector<CodeTemplate> &CodeTemplates) {
   assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
   switch (ExecutionModeBit) {
   case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
     // Nothing to do, the instruction is always serial.
     LLVM_FALLTHROUGH;
   case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
     // Picking whatever value for the tied variable will make the instruction
     // serial.
     CodeTemplate CT;
+    CT.ScratchSpacePointerInReg = ScratchSpacePointerInReg;
     CT.Execution = ExecutionModeBit;
     CT.Info = ExecutionClassDescription;
     CT.Instructions.push_back(Instr);
+    instantiateMemoryOperands(State, CT);
     CodeTemplates.push_back(std::move(CT));
     return;
   }
   case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
     // Select back-to-back memory instruction.
     // TODO: Implement me.
     return;
   }
   case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
     // Making the execution of this instruction serial by selecting one def
     // register to alias with one use register.
     const AliasingConfigurations SelfAliasing(Instr, Instr);
     assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
            "Instr must alias itself explicitly");
     InstructionTemplate IT(Instr);
     // This is a self aliasing instruction so defs and uses are from the same
     // instance, hence twice IT in the following call.
     setRandomAliasing(SelfAliasing, IT, IT);
     CodeTemplate CT;
+    CT.ScratchSpacePointerInReg = ScratchSpacePointerInReg;
     CT.Execution = ExecutionModeBit;
     CT.Info = ExecutionClassDescription;
     CT.Instructions.push_back(std::move(IT));
+    instantiateMemoryOperands(State, CT);
     CodeTemplates.push_back(std::move(CT));
     return;
   }
   case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
     // Select back-to-back non-memory instruction.
     for (const auto OtherInstr :
          computeAliasingInstructions(State, Instr, kMaxAliasingInstructions)) {
       const AliasingConfigurations Forward(Instr, OtherInstr);
       const AliasingConfigurations Back(OtherInstr, Instr);
       InstructionTemplate ThisIT(Instr);
       InstructionTemplate OtherIT(OtherInstr);
       if (!Forward.hasImplicitAliasing())
         setRandomAliasing(Forward, ThisIT, OtherIT);
       if (!Back.hasImplicitAliasing())
         setRandomAliasing(Back, OtherIT, ThisIT);
       CodeTemplate CT;
+      CT.ScratchSpacePointerInReg = ScratchSpacePointerInReg;
       CT.Execution = ExecutionModeBit;
       CT.Info = ExecutionClassDescription;
       CT.Instructions.push_back(std::move(ThisIT));
       CT.Instructions.push_back(std::move(OtherIT));
+      instantiateMemoryOperands(State, CT);
       CodeTemplates.push_back(std::move(CT));
     }
     return;
   }
   default:
     llvm_unreachable("Unhandled enum value");
   }
 }
 
 LatencySnippetGenerator::~LatencySnippetGenerator() = default;
 
 llvm::Expected<std::vector<CodeTemplate>>
 LatencySnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
   std::vector<CodeTemplate> Results;
+  const llvm::BitVector *ScratchSpaceAliasedRegs;
+  unsigned ScratchSpacePointerInReg;
+  if (auto E = handleInstrWithMemoryOperand(Instr, ScratchSpacePointerInReg, ScratchSpaceAliasedRegs)) {
+    return std::move(E);
+  }
+
   const ExecutionMode EM = getExecutionModes(Instr);
   for (const auto EC : kExecutionClasses) {
     for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
       appendCodeTemplates(State, Instr, ExecutionModeBit, EC.Description,
-                          Results);
+                          ScratchSpacePointerInReg, Results);
     if (!Results.empty())
       break;
   }
   if (Results.empty())
     return llvm::make_error<BenchmarkFailure>(
         "No strategy found to make the execution serial");
   return std::move(Results);
 }

tools/llvm-exegesis/lib/SnippetGenerator.h

public:
 
   // Given a snippet, computes which registers the setup code needs to define.
   std::vector<RegisterValue> computeRegisterInitialValues(
       const std::vector<InstructionTemplate> &Snippet) const;
 
 protected:
   const LLVMState &State;
 
+  // A helper that checks whether Instr is supported (or has no memory operand).
+  // On success, it sets `ScratchSpacePointerInReg` and
+  // `ScratchSpaceAliasedRegs`.
+  Error handleInstrWithMemoryOperand(
+      const Instruction &Instr, unsigned &ScratchSpacePointerInReg,
+      const llvm::BitVector *&ScratchSpaceAliasedRegs) const;
+
 private:
   // API to be implemented by subclasses.
   virtual llvm::Expected<std::vector<CodeTemplate>>
   generateCodeTemplates(const Instruction &Instr) const = 0;
 };
 
 // A global Random Number Generator to randomize configurations.
 // FIXME: Move random number generation into an object and make it seedable for

tools/llvm-exegesis/lib/SnippetGenerator.cpp

 //===-- SnippetGenerator.cpp ------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include <array>
 #include <string>
 
 #include "Assembler.h"
 #include "MCInstrDescView.h"
 #include "SnippetGenerator.h"
+#include "Target.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Program.h"
 
 namespace llvm {
for (const Operand &Op : IT.Instr.Operands) {
         if (Reg > 0)
           DefinedRegs.set(Reg);
       }
     }
   }
   return RIV;
 }
 
+Error SnippetGenerator::handleInstrWithMemoryOperand(
+    const Instruction &Instr, unsigned &ScratchSpacePointerInReg,
+    const llvm::BitVector *&ScratchSpaceAliasedRegs) const {
+  ScratchSpacePointerInReg = 0;
+  ScratchSpaceAliasedRegs = nullptr;
+  if (Instr.hasMemoryOperands()) {
+    const auto &ET = State.getExegesisTarget();
+    ScratchSpacePointerInReg =
+        ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
+    if (ScratchSpacePointerInReg == 0)
+      return llvm::make_error<BenchmarkFailure>(
+          "Infeasible : target does not support memory instructions");
+    ScratchSpaceAliasedRegs =
+        &State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
+    // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
+    // FIXME: We could make a copy of the scratch register.
+    for (const auto &Op : Instr.Operands) {
+      if (Op.isDef() && Op.isImplicitReg() &&
+          ScratchSpaceAliasedRegs->test(Op.getImplicitReg()))
+        return llvm::make_error<BenchmarkFailure>(
+            "Infeasible : memory instruction uses scratch memory register");
+    }
+  }
+  return Error::success();
+}
+
 llvm::Expected<std::vector<CodeTemplate>>
 generateSelfAliasingCodeTemplates(const Instruction &Instr) {
   const AliasingConfigurations SelfAliasing(Instr, Instr);
   if (SelfAliasing.empty())
     return llvm::make_error<SnippetGeneratorFailure>("empty self aliasing");
   std::vector<CodeTemplate> Result;
   Result.emplace_back();
   CodeTemplate &CT = Result.back();

tools/llvm-exegesis/lib/Uops.cpp

void UopsSnippetGenerator::instantiateMemoryOperands(
   }
   assert(I * MemStep < BenchmarkRunner::ScratchSpace::kSize &&
          "not enough scratch space");
 }
 
 llvm::Expected<std::vector<CodeTemplate>>
 UopsSnippetGenerator::generateCodeTemplates(const Instruction &Instr) const {
   CodeTemplate CT;
-  const llvm::BitVector *ScratchSpaceAliasedRegs = nullptr;
-  if (Instr.hasMemoryOperands()) {
-    const auto &ET = State.getExegesisTarget();
-    CT.ScratchSpacePointerInReg =
-        ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
-    if (CT.ScratchSpacePointerInReg == 0)
-      return llvm::make_error<BenchmarkFailure>(
-          "Infeasible : target does not support memory instructions");
-    ScratchSpaceAliasedRegs =
-        &State.getRATC().getRegister(CT.ScratchSpacePointerInReg).aliasedBits();
-    // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
-    // FIXME: We could make a copy of the scratch register.
-    for (const auto &Op : Instr.Operands) {
-      if (Op.isDef() && Op.isImplicitReg() &&
-          ScratchSpaceAliasedRegs->test(Op.getImplicitReg()))
-        return llvm::make_error<BenchmarkFailure>(
-            "Infeasible : memory instruction uses scratch memory register");
-    }
+  const llvm::BitVector *ScratchSpaceAliasedRegs;
+  if (auto E = handleInstrWithMemoryOperand(Instr, CT.ScratchSpacePointerInReg, ScratchSpaceAliasedRegs)) {
+    return std::move(E);
   }
 
   const AliasingConfigurations SelfAliasing(Instr, Instr);
   InstructionTemplate IT(Instr);
   if (SelfAliasing.empty()) {
     CT.Info = "instruction is parallel, repeating a random one.";
     CT.Instructions.push_back(std::move(IT));
     instantiateMemoryOperands(CT.ScratchSpacePointerInReg, CT.Instructions);