[llvm-exegesis] Provide a way to handle memory instructions.

[courbet]

Summary

And implement memory instructions on X86.

This fixes PR36906.

[RKSimon]

unittests/tools/llvm-exegesis/Common/AssemblerUtils.h

49 ↗

(On Diff #154104)

How should these numbers relate to the ScratchSpace values?

[courbet]

Use ScratchSpace instead of alinged_storage.

[courbet]

unittests/tools/llvm-exegesis/Common/AssemblerUtils.h

49 ↗

(On Diff #154104)

This was a leftover from a previous implementation. Fixed.

[filcab]

tools/llvm-exegesis/lib/Assembler.h

42 ↗

(On Diff #154104)

s/void*/char*/

tools/llvm-exegesis/lib/BenchmarkRunner.h

84 ↗

(On Diff #154104)

unique_ptr here. AlignedPtr is ok, though.

93 ↗

(On Diff #154104)

Can you split the formatting changes to another diff?

tools/llvm-exegesis/lib/Target.cpp

33 ↗

(On Diff #154104)

Why is the assert being removed? It seemed to be asserting that we don't call this function twice. Are we now possibly calling it twice, or would it still be a programmer problem (as in: we should try to guarantee that the function is only called once).

[courbet]

address review comments

[courbet]

Thanks for the comments !

tools/llvm-exegesis/lib/Target.cpp

33 ↗

(On Diff #154104)

Unit tests are actually calling it twice unfortunately. It allows having a single binary for all tests rathen than one binary per test and reduces link time quite importantly.

[gchatelet]

tools/llvm-exegesis/lib/Assembler.cpp

92 ↗

(On Diff #154208)

Remove parenthesis.

171 ↗

(On Diff #154208)

Remove parenthesis.

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

141 ↗

(On Diff #154208)

Remove parenthesis.

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

Why not aligned_alloc ?

tools/llvm-exegesis/lib/MCInstrDescView.h

130 ↗

(On Diff #154110)

"the pointer to" this memory is passed

tools/llvm-exegesis/lib/Target.h

59 ↗

(On Diff #154208)

I don't understand the comment :-/

How about this :

// Returns the maximum number of bytes a load/store instruction can access at once.
// This is typically the size of the largest register available on the processor.
virtual unsigned getLoadStoreMaxSize() const;

Also I think there's mismatch between the documentation and the implementation since you say return a value that is *larger* than ... but the implementation returns 64.

tools/llvm-exegesis/lib/Uops.cpp

182 ↗

(On Diff #154208)

This is not ideal because if (HasMemOperands) instantiateMemoryOperands(...) is repeated before each return.
How about a PrototypeBuilder struct that encapsulate the memory logic ?

206 ↗

(On Diff #154208)

?

tools/llvm-exegesis/lib/Uops.h

45 ↗

(On Diff #154208)

Not sure to understand what you mean by

// If there are less
// than kMinNumDifferentAddresses in the original snippet, we duplicate
// instructions until there are this number of instructions.

unittests/tools/llvm-exegesis/Common/AssemblerUtils.h

75 ↗

(On Diff #154208)

Can you introduce a variable for readability?

unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp

242 ↗

(On Diff #154208)

Do you need the (bool) cast?

[courbet]

address review comments

[courbet]

Thanks, PTAL.

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

the alignment of aligned_alloc has to be an alignment for a valid object. Some X86 instructions require 512 byte alignment, wich is not the alignment of any valid object.

tools/llvm-exegesis/lib/Uops.cpp

182 ↗

(On Diff #154208)

I originally had a lambda called MaybeInstanciateMemoryOperands, but TBH I think the repeated if makes it clearer.

unittests/tools/llvm-exegesis/Common/AssemblerUtils.h

75 ↗

(On Diff #154208)

For the {} ? I've added a comment.

unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp

242 ↗

(On Diff #154208)

Yes, because the macro tries to capture Error as an llvm::Error and barfs.

[gchatelet]

tools/llvm-exegesis/lib/Uops.cpp

182 ↗

(On Diff #154208)

I originally had a lambda called MaybeInstanciateMemoryOperands, but TBH I think the repeated if makes it clearer.

The if statement might be clearer than the Lambda but it is as error prone (you can omit the lambda and it compiles but it's broken).
My point was, if you use a Builder it is correct by design (and it removes visual clutter), true that it adds a struct to the file though.

tools/llvm-exegesis/lib/Uops.h

45 ↗

(On Diff #155352)

"assuming kMinNumDifferentAddresses=5 and getMaxMemoryAccessSize()=64"

[courbet]

remove the HasMemOperands bool and ifs.

[courbet]

tools/llvm-exegesis/lib/Uops.cpp

182 ↗

(On Diff #154208)

Here's a proposal with no lambda and no builder, tell me what you think.

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

I don't understand why you can't use aligned_alloc(1024, 1<<20);?

[courbet]

Thanks.

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

aligned_alloc is c++17...

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

I read C++11 on the link I provided.
https://en.cppreference.com/w/c/memory/aligned_alloc

[lebedev.ri]

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

C11, not C++11.

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkRunner.h

77 ↗

(On Diff #154110)

I misread then :) Thx for correcting me.

[gchatelet]

FYI I'll submit this patch for Clement.

llvm/trunk/tools/llvm-exegesis/lib/Assembler.h

 namespace exegesis {
 
 class ExegesisTarget;
 
 // Gather the set of reserved registers (depends on function's calling
 // convention and target machine).
 llvm::BitVector getFunctionReservedRegs(const llvm::TargetMachine &TM);
 
-// Creates a temporary `void foo()` function containing the provided
+// Creates a temporary `void foo(char*)` function containing the provided
 // Instructions. Runs a set of llvm Passes to provide correct prologue and
 // epilogue. Once the MachineFunction is ready, it is assembled for TM to
 // AsmStream, the temporary function is eventually discarded.
 void assembleToStream(const ExegesisTarget &ET,
                       std::unique_ptr<llvm::LLVMTargetMachine> TM,
+                      llvm::ArrayRef<unsigned> LiveIns,
                       llvm::ArrayRef<unsigned> RegsToDef,
                       llvm::ArrayRef<llvm::MCInst> Instructions,
                       llvm::raw_pwrite_stream &AsmStream);
 
 // Creates an ObjectFile in the format understood by the host.
 // Note: the resulting object keeps a copy of Buffer so it can be discarded once
 // this function returns.
 llvm::object::OwningBinary<llvm::object::ObjectFile>
 getObjectFromBuffer(llvm::StringRef Buffer);
 
 // Loads the content of Filename as on ObjectFile and returns it.
 llvm::object::OwningBinary<llvm::object::ObjectFile>
 getObjectFromFile(llvm::StringRef Filename);
 
-// Consumes an ObjectFile containing a `void foo()` function and make it
+// Consumes an ObjectFile containing a `void foo(char*)` function and make it
 // executable.
 struct ExecutableFunction {
   explicit ExecutableFunction(
       std::unique_ptr<llvm::LLVMTargetMachine> TM,
       llvm::object::OwningBinary<llvm::object::ObjectFile> &&ObjectFileHolder);
 
   // Retrieves the function as an array of bytes.
   llvm::StringRef getFunctionBytes() const { return FunctionBytes; }
 
   // Executes the function.
-  void operator()() const { ((void (*)())(intptr_t)FunctionBytes.data())(); }
+  void operator()(char *Memory) const {
+    ((void (*)(char *))(intptr_t)FunctionBytes.data())(Memory);
+  }
 
   std::unique_ptr<llvm::LLVMContext> Context;
   std::unique_ptr<llvm::ExecutionEngine> ExecEngine;
   llvm::StringRef FunctionBytes;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H

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

static bool addPass(llvm::PassManagerBase &PM, llvm::StringRef PassName,
   llvm::Pass *P = PI->getNormalCtor()();
   std::string Banner = std::string("After ") + std::string(P->getPassName());
   PM.add(P);
   TPC.printAndVerify(Banner);
 
   return false;
 }
 
-// Creates a void MachineFunction with no argument.
+// Creates a void(int8*) MachineFunction.
 static llvm::MachineFunction &
-createVoidVoidMachineFunction(llvm::StringRef FunctionID, llvm::Module *Module,
+createVoidVoidPtrMachineFunction(llvm::StringRef FunctionID,
+                                 llvm::Module *Module,
                                  llvm::MachineModuleInfo *MMI) {
   llvm::Type *const ReturnType = llvm::Type::getInt32Ty(Module->getContext());
-  llvm::FunctionType *FunctionType = llvm::FunctionType::get(ReturnType, false);
+  llvm::Type *const MemParamType = llvm::PointerType::get(
+      llvm::Type::getInt8Ty(Module->getContext()), 0 /*default address space*/);
+  llvm::FunctionType *FunctionType =
+      llvm::FunctionType::get(ReturnType, {MemParamType}, false);
   llvm::Function *const F = llvm::Function::Create(
       FunctionType, llvm::GlobalValue::InternalLinkage, FunctionID, Module);
   // Making sure we can create a MachineFunction out of this Function even if it
   // contains no IR.
   F->setIsMaterializable(true);
   return MMI->getOrCreateMachineFunction(*F);
 }
 
 static void fillMachineFunction(llvm::MachineFunction &MF,
+                                llvm::ArrayRef<unsigned> LiveIns,
                                 llvm::ArrayRef<llvm::MCInst> Instructions) {
   llvm::MachineBasicBlock *MBB = MF.CreateMachineBasicBlock();
   MF.push_back(MBB);
+  for (const unsigned Reg : LiveIns)
+    MBB->addLiveIn(Reg);
   const llvm::MCInstrInfo *MCII = MF.getTarget().getMCInstrInfo();
   llvm::DebugLoc DL;
   for (const llvm::MCInst &Inst : Instructions) {
     const unsigned Opcode = Inst.getOpcode();
     const llvm::MCInstrDesc &MCID = MCII->get(Opcode);
     llvm::MachineInstrBuilder Builder = llvm::BuildMI(MBB, DL, MCID);
     for (unsigned OpIndex = 0, E = Inst.getNumOperands(); OpIndex < E;
          ++OpIndex) {

 llvm::BitVector getFunctionReservedRegs(const llvm::TargetMachine &TM) {
   std::unique_ptr<llvm::LLVMContext> Context =
       llvm::make_unique<llvm::LLVMContext>();
   std::unique_ptr<llvm::Module> Module =
       createModule(Context, TM.createDataLayout());
   std::unique_ptr<llvm::MachineModuleInfo> MMI =
       llvm::make_unique<llvm::MachineModuleInfo>(&TM);
   llvm::MachineFunction &MF =
-      createVoidVoidMachineFunction(FunctionID, Module.get(), MMI.get());
+      createVoidVoidPtrMachineFunction(FunctionID, Module.get(), MMI.get());
   // Saving reserved registers for client.
   return MF.getSubtarget().getRegisterInfo()->getReservedRegs(MF);
 }
 
 void assembleToStream(const ExegesisTarget &ET,
                       std::unique_ptr<llvm::LLVMTargetMachine> TM,
+                      llvm::ArrayRef<unsigned> LiveIns,
                       llvm::ArrayRef<unsigned> RegsToDef,
                       llvm::ArrayRef<llvm::MCInst> Instructions,
                       llvm::raw_pwrite_stream &AsmStream) {
   std::unique_ptr<llvm::LLVMContext> Context =
       llvm::make_unique<llvm::LLVMContext>();
   std::unique_ptr<llvm::Module> Module =
       createModule(Context, TM->createDataLayout());
   std::unique_ptr<llvm::MachineModuleInfo> MMI =
       llvm::make_unique<llvm::MachineModuleInfo>(TM.get());
   llvm::MachineFunction &MF =
-      createVoidVoidMachineFunction(FunctionID, Module.get(), MMI.get());
+      createVoidVoidPtrMachineFunction(FunctionID, Module.get(), MMI.get());
 
   // We need to instruct the passes that we're done with SSA and virtual
   // registers.
   auto &Properties = MF.getProperties();
   Properties.set(llvm::MachineFunctionProperties::Property::NoVRegs);
   Properties.reset(llvm::MachineFunctionProperties::Property::IsSSA);
+
+  for (const unsigned Reg : LiveIns)
+    MF.getRegInfo().addLiveIn(Reg);
+
   bool IsSnippetSetupComplete = false;
   std::vector<llvm::MCInst> SnippetWithSetup =
       generateSnippetSetupCode(RegsToDef, ET, *TM, IsSnippetSetupComplete);
   if (!SnippetWithSetup.empty()) {
     SnippetWithSetup.insert(SnippetWithSetup.end(), Instructions.begin(),
                             Instructions.end());
     Instructions = SnippetWithSetup;
   }
   // If the snippet setup is not complete, we disable liveliness tracking. This
   // means that we won't know what values are in the registers.
   if (!IsSnippetSetupComplete)
     Properties.reset(llvm::MachineFunctionProperties::Property::TracksLiveness);
 
   // prologue/epilogue pass needs the reserved registers to be frozen, this
   // is usually done by the SelectionDAGISel pass.
   MF.getRegInfo().freezeReservedRegs(MF);
 
   // Fill the MachineFunction from the instructions.
-  fillMachineFunction(MF, Instructions);
+  fillMachineFunction(MF, LiveIns, Instructions);
 
   // We create the pass manager, run the passes to populate AsmBuffer.
   llvm::MCContext &MCContext = MMI->getContext();
   llvm::legacy::PassManager PM;
 
   llvm::TargetLibraryInfoImpl TLII(llvm::Triple(Module->getTargetTriple()));
   PM.add(new llvm::TargetLibraryInfoWrapperPass(TLII));
 

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

 
 #include "Assembler.h"
 #include "BenchmarkResult.h"
 #include "LlvmState.h"
 #include "MCInstrDescView.h"
 #include "RegisterAliasing.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Error.h"
+#include <cstdlib>
+#include <memory>
 #include <vector>
 
 namespace exegesis {
 
 // A class representing failures that happened during Benchmark, they are used
 // to report informations to the user.
 class BenchmarkFailure : public llvm::StringError {
 public:
   BenchmarkFailure(const llvm::Twine &S);
 };
 
 // A collection of instructions that are to be assembled, executed and measured.
 struct BenchmarkConfiguration {
   // This code is run before the Snippet is iterated. Since it is part of the
   // measurement it should be as short as possible. It is usually used to setup
   // the content of the Registers.
   struct Setup {
+    std::vector<unsigned> LiveIns; // The registers that are live on entry.
     std::vector<unsigned> RegsToDef;
   };
   Setup SnippetSetup;
 
   // The sequence of instructions that are to be repeated.
   std::vector<llvm::MCInst> Snippet;
 
   // Informations about how this configuration was built.
public:
 
   llvm::Expected<std::vector<InstructionBenchmark>>
   run(unsigned Opcode, unsigned NumRepetitions);
 
   // Given a snippet, computes which registers the setup code needs to define.
   std::vector<unsigned>
   computeRegsToDef(const std::vector<InstructionInstance> &Snippet) const;
 
+  // Scratch space to run instructions that touch memory.
+  struct ScratchSpace {
+    static constexpr const size_t kAlignment = 1024;
+    static constexpr const size_t kSize = 1 << 20; // 1MB.
+    ScratchSpace()
+        : UnalignedPtr(llvm::make_unique<char[]>(kSize + kAlignment)),
+          AlignedPtr(
+              UnalignedPtr.get() + kAlignment -
+              (reinterpret_cast<intptr_t>(UnalignedPtr.get()) % kAlignment)) {}
+    char *ptr() const { return AlignedPtr; }
+    void clear() { std::memset(ptr(), 0, kSize); }
+
+  private:
+    const std::unique_ptr<char[]> UnalignedPtr;
+    char *const AlignedPtr;
+  };
+
 protected:
   const LLVMState &State;
   const RegisterAliasingTrackerCache RATC;
 
   // Generates a single instruction prototype that has a self-dependency.
   llvm::Expected<SnippetPrototype>
   generateSelfAliasingPrototype(const Instruction &Instr) const;
   // Generates a single instruction prototype without assignment constraints.
   llvm::Expected<SnippetPrototype>
   generateUnconstrainedPrototype(const Instruction &Instr,
                                  llvm::StringRef Msg) const;
 
 private:
   // API to be implemented by subclasses.
   virtual llvm::Expected<SnippetPrototype>
   generatePrototype(unsigned Opcode) const = 0;
 
   virtual std::vector<BenchmarkMeasure>
-  runMeasurements(const ExecutableFunction &EF,
+  runMeasurements(const ExecutableFunction &EF, ScratchSpace &Scratch,
                   const unsigned NumRepetitions) const = 0;
 
   // Internal helpers.
   InstructionBenchmark runOne(const BenchmarkConfiguration &Configuration,
                               unsigned Opcode, unsigned NumRepetitions) const;
 
   // Calls generatePrototype and expands the SnippetPrototype into one or more
   // BenchmarkConfiguration.
   llvm::Expected<std::vector<BenchmarkConfiguration>>
   generateConfigurations(unsigned Opcode) const;
 
   llvm::Expected<std::string>
   writeObjectFile(const BenchmarkConfiguration::Setup &Setup,
                   llvm::ArrayRef<llvm::MCInst> Code) const;
 
   const InstructionBenchmark::ModeE Mode;
+
+  const std::unique_ptr<ScratchSpace> Scratch;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H

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

 
 BenchmarkFailure::BenchmarkFailure(const llvm::Twine &S)
     : llvm::StringError(S, llvm::inconvertibleErrorCode()) {}
 
 BenchmarkRunner::BenchmarkRunner(const LLVMState &State,
                                  InstructionBenchmark::ModeE Mode)
     : State(State), RATC(State.getRegInfo(),
                          getFunctionReservedRegs(State.getTargetMachine())),
-      Mode(Mode) {}
+      Mode(Mode), Scratch(llvm::make_unique<ScratchSpace>()) {}
 
 BenchmarkRunner::~BenchmarkRunner() = default;
 
 llvm::Expected<std::vector<InstructionBenchmark>>
 BenchmarkRunner::run(unsigned Opcode, unsigned NumRepetitions) {
   const llvm::MCInstrDesc &InstrDesc = State.getInstrInfo().get(Opcode);
   // Ignore instructions that we cannot run.
   if (InstrDesc.isPseudo())
BenchmarkRunner::runOne(const BenchmarkConfiguration &Configuration,
   if (llvm::Error E = ObjectFilePath.takeError()) {
     InstrBenchmark.Error = llvm::toString(std::move(E));
     return InstrBenchmark;
   }
   llvm::outs() << "Check generated assembly with: /usr/bin/objdump -d "
                << *ObjectFilePath << "\n";
   const ExecutableFunction EF(State.createTargetMachine(),
                               getObjectFromFile(*ObjectFilePath));
-  InstrBenchmark.Measurements = runMeasurements(EF, NumRepetitions);
+  InstrBenchmark.Measurements = runMeasurements(EF, *Scratch, NumRepetitions);
 
   return InstrBenchmark;
 }
 
 llvm::Expected<std::vector<BenchmarkConfiguration>>
 BenchmarkRunner::generateConfigurations(unsigned Opcode) const {
   if (auto E = generatePrototype(Opcode)) {
     SnippetPrototype &Prototype = E.get();
     // TODO: Generate as many configurations as needed here.
     BenchmarkConfiguration Configuration;
     Configuration.Info = Prototype.Explanation;
     for (InstructionInstance &II : Prototype.Snippet) {
-      II.randomizeUnsetVariables();
+      II.randomizeUnsetVariables(
+          Prototype.ScratchSpaceReg
+              ? RATC.getRegister(Prototype.ScratchSpaceReg).aliasedBits()
+              : RATC.emptyRegisters());
       Configuration.Snippet.push_back(II.build());
     }
+    if (Prototype.ScratchSpaceReg)
+      Configuration.SnippetSetup.LiveIns.push_back(Prototype.ScratchSpaceReg);
     Configuration.SnippetSetup.RegsToDef = computeRegsToDef(Prototype.Snippet);
     return std::vector<BenchmarkConfiguration>{Configuration};
   } else
     return E.takeError();
 }
 
 std::vector<unsigned> BenchmarkRunner::computeRegsToDef(
     const std::vector<InstructionInstance> &Snippet) const {
   // Collect all register uses and create an assignment for each of them.
+  // Ignore memory operands which are handled separately.
   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
   // before the current instruction.
   llvm::BitVector DefinedRegs = RATC.emptyRegisters();
   std::vector<unsigned> RegsToDef;
   for (const InstructionInstance &II : Snippet) {
     // Returns the register that this Operand sets or uses, or 0 if this is not
     // a register.
     const auto GetOpReg = [&II](const Operand &Op) -> unsigned {
-      if (Op.ImplicitReg) {
+      if (Op.IsMem)
+        return 0;
+      if (Op.ImplicitReg)
         return *Op.ImplicitReg;
-      } else if (Op.IsExplicit && II.getValueFor(Op).isReg()) {
+      if (Op.IsExplicit && II.getValueFor(Op).isReg())
         return II.getValueFor(Op).getReg();
-      }
       return 0;
     };
     // Collect used registers that have never been def'ed.
     for (const Operand &Op : II.Instr.Operands) {
       if (!Op.IsDef) {
         const unsigned Reg = GetOpReg(Op);
         if (Reg > 0 && !DefinedRegs.test(Reg)) {
           RegsToDef.push_back(Reg);
           DefinedRegs.set(Reg);
         }
       }
     }
     // Mark defs as having been def'ed.
     for (const Operand &Op : II.Instr.Operands) {
       if (Op.IsDef) {
         const unsigned Reg = GetOpReg(Op);
-        if (Reg > 0) {
+        if (Reg > 0)
           DefinedRegs.set(Reg);
-        }
-      }
-    }
-  }
   return RegsToDef;
 }
 
 llvm::Expected<std::string>
 BenchmarkRunner::writeObjectFile(const BenchmarkConfiguration::Setup &Setup,
                                  llvm::ArrayRef<llvm::MCInst> Code) const {
   int ResultFD = 0;
   llvm::SmallString<256> ResultPath;
   if (llvm::Error E = llvm::errorCodeToError(llvm::sys::fs::createTemporaryFile(
           "snippet", "o", ResultFD, ResultPath)))
     return std::move(E);
   llvm::raw_fd_ostream OFS(ResultFD, true /*ShouldClose*/);
   assembleToStream(State.getExegesisTarget(), State.createTargetMachine(),
-                   Setup.RegsToDef, Code, OFS);
+                   Setup.LiveIns, Setup.RegsToDef, Code, OFS);
   return ResultPath.str();
 }
 
 llvm::Expected<SnippetPrototype>
 BenchmarkRunner::generateSelfAliasingPrototype(const Instruction &Instr) const {
   const AliasingConfigurations SelfAliasing(Instr, Instr);
   if (SelfAliasing.empty()) {
     return llvm::make_error<BenchmarkFailure>("empty self aliasing");

llvm/trunk/tools/llvm-exegesis/lib/Latency.h

 
 private:
   llvm::Error isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const;
 
   llvm::Expected<SnippetPrototype> generateTwoInstructionPrototype(
       const Instruction &Instr) const;
 
   std::vector<BenchmarkMeasure>
-  runMeasurements(const ExecutableFunction &EF,
+  runMeasurements(const ExecutableFunction &EF, ScratchSpace &Scratch,
                   const unsigned NumRepetitions) const override;
 
   virtual const char *getCounterName() const;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_LATENCY_H

llvm/trunk/tools/llvm-exegesis/lib/Latency.cpp

const char *CounterName = State.getSubtargetInfo()
                                 .PfmCounters.CycleCounter;
   if (!CounterName)
     llvm::report_fatal_error("sched model does not define a cycle counter");
   return CounterName;
 }
 
 std::vector<BenchmarkMeasure>
 LatencyBenchmarkRunner::runMeasurements(const ExecutableFunction &Function,
+                                        ScratchSpace &Scratch,
                                         const unsigned NumRepetitions) const {
   // Cycle measurements include some overhead from the kernel. Repeat the
   // measure several times and take the minimum value.
   constexpr const int NumMeasurements = 30;
   int64_t MinLatency = std::numeric_limits<int64_t>::max();
   const char *CounterName = getCounterName();
   if (!CounterName)
     llvm::report_fatal_error("could not determine cycle counter name");
   const pfm::PerfEvent CyclesPerfEvent(CounterName);
   if (!CyclesPerfEvent.valid())
     llvm::report_fatal_error("invalid perf event");
   for (size_t I = 0; I < NumMeasurements; ++I) {
     pfm::Counter Counter(CyclesPerfEvent);
+    Scratch.clear();
     Counter.start();
-    Function();
+    Function(Scratch.ptr());
     Counter.stop();
     const int64_t Value = Counter.read();
     if (Value < MinLatency)
       MinLatency = Value;
   }
   return {{"latency", static_cast<double>(MinLatency) / NumRepetitions, ""}};
 }
 
 } // namespace exegesis

llvm/trunk/tools/llvm-exegesis/lib/MCInstrDescView.h

 // - TiedToIndex: the index of the Operand holding the value or -1.
 // - ImplicitReg: a pointer to the register value when Operand is Implicit,
 // nullptr otherwise.
 // - VariableIndex: the index of the Variable holding the value for this Operand
 // or -1 if this operand is implicit.
 struct Operand {
   unsigned Index = 0;
   bool IsDef = false;
+  bool IsMem = false;
   bool IsExplicit = false;
   const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op.
   const llvm::MCOperandInfo *Info = nullptr;        // Set for Explicit Op.
   int TiedToIndex = -1;                             // Set for Reg&Explicit Op.
   const llvm::MCPhysReg *ImplicitReg = nullptr;     // Set for Implicit Op.
   int VariableIndex = -1;                           // Set for Explicit Op.
 };
 
 // A view over an MCInstrDesc offering a convenient interface to compute
 // Register aliasing.
 struct Instruction {
   Instruction(const llvm::MCInstrDesc &MCInstrDesc,
               const RegisterAliasingTrackerCache &ATC);
 
+  bool hasMemoryOperands() const;
+
   const llvm::MCInstrDesc *Description; // Never nullptr.
   llvm::SmallVector<Operand, 8> Operands;
   llvm::SmallVector<Variable, 4> Variables;
   llvm::BitVector DefRegisters; // The union of the aliased def registers.
   llvm::BitVector UseRegisters; // The union of the aliased use registers.
 };
 
 // An instance of an Instruction holding values for each of its Variables.
 struct InstructionInstance {
   InstructionInstance(const Instruction &Instr);
 
-  // No copy.
-  InstructionInstance(const InstructionInstance &) = delete;
-  InstructionInstance &operator=(const InstructionInstance &) = delete;
-
-  // Moving is OK.
+  InstructionInstance(const InstructionInstance &);
+  InstructionInstance &operator=(const InstructionInstance &);
   InstructionInstance(InstructionInstance &&);
   InstructionInstance &operator=(InstructionInstance &&);
 
   unsigned getOpcode() const;
   llvm::MCOperand &getValueFor(const Variable &Var);
   const llvm::MCOperand &getValueFor(const Variable &Var) const;
   llvm::MCOperand &getValueFor(const Operand &Op);
   const llvm::MCOperand &getValueFor(const Operand &Op) const;
   bool hasImmediateVariables() const;
 
   // Assigns a Random Value to all Variables that are still Invalid.
-  void randomizeUnsetVariables();
+  // Do not use any of the registers in `ForbiddenRegs`.
+  void randomizeUnsetVariables(const llvm::BitVector &ForbiddenRegs);
 
   // Returns the instance as an llvm::MCInst. The InstructionInstance must be
   // fully allocated (no invalid variables).
   llvm::MCInst build() const;
 
   Instruction Instr;
   llvm::SmallVector<llvm::MCOperand, 4> VariableValues;
 };
struct SnippetPrototype {
   SnippetPrototype(const SnippetPrototype &) = delete;
   SnippetPrototype &operator=(const SnippetPrototype &) = delete;
 
   // Moving is OK.
   SnippetPrototype(SnippetPrototype &&);
   SnippetPrototype &operator=(SnippetPrototype &&);
 
   std::string Explanation;
+  // If the prototype uses the provided scratch memory, the register in which
+  // the pointer to this memory is passed in to the function.
+  unsigned ScratchSpaceReg = 0;
   std::vector<InstructionInstance> Snippet;
 };
 
 // Represents the assignment of a Register to an Operand.
 struct RegisterOperandAssignment {
   RegisterOperandAssignment(const Operand *Operand, llvm::MCPhysReg Reg)
       : Op(Operand), Reg(Reg) {}
 

llvm/trunk/tools/llvm-exegesis/lib/MCInstrDescView.cpp

Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
                          const RegisterAliasingTrackerCache &RATC)
     : Description(&MCInstrDesc) {
   unsigned OpIndex = 0;
   for (; OpIndex < MCInstrDesc.getNumOperands(); ++OpIndex) {
     const auto &OpInfo = MCInstrDesc.opInfo_begin()[OpIndex];
     Operand Operand;
     Operand.Index = OpIndex;
     Operand.IsDef = (OpIndex < MCInstrDesc.getNumDefs());
+    Operand.IsMem = OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY;
     Operand.IsExplicit = true;
     // TODO(gchatelet): Handle isLookupPtrRegClass.
     if (OpInfo.RegClass >= 0)
       Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
     Operand.TiedToIndex =
         MCInstrDesc.getOperandConstraint(OpIndex, llvm::MCOI::TIED_TO);
     Operand.Info = &OpInfo;
     Operands.push_back(Operand);
Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
   for (const auto &Op : Operands) {
     if (Op.Tracker) {
       auto &Registers = Op.IsDef ? DefRegisters : UseRegisters;
       Registers |= Op.Tracker->aliasedBits();
     }
   }
 }
 
+bool Instruction::hasMemoryOperands() const {
+  return std::any_of(Operands.begin(), Operands.end(),
+                     [](const Operand &Op) { return Op.IsMem; });
+}
+
 InstructionInstance::InstructionInstance(const Instruction &Instr)
     : Instr(Instr), VariableValues(Instr.Variables.size()) {}
 
 InstructionInstance::InstructionInstance(InstructionInstance &&) = default;
 
 InstructionInstance &InstructionInstance::
 operator=(InstructionInstance &&) = default;
 
+InstructionInstance::InstructionInstance(const InstructionInstance &) = default;
+
+InstructionInstance &InstructionInstance::
+operator=(const InstructionInstance &) = default;
+
 unsigned InstructionInstance::getOpcode() const {
   return Instr.Description->getOpcode();
 }
 
 llvm::MCOperand &InstructionInstance::getValueFor(const Variable &Var) {
   return VariableValues[Var.Index];
 }
 

 const llvm::MCOperand &
 InstructionInstance::getValueFor(const Operand &Op) const {
   assert(Op.VariableIndex >= 0);
   return getValueFor(Instr.Variables[Op.VariableIndex]);
 }
 
 // forward declaration.
 static void randomize(const Instruction &Instr, const Variable &Var,
-                      llvm::MCOperand &AssignedValue);
+                      llvm::MCOperand &AssignedValue,
+                      const llvm::BitVector &ForbiddenRegs);
 
 bool InstructionInstance::hasImmediateVariables() const {
   return llvm::any_of(Instr.Variables, [this](const Variable &Var) {
     assert(!Var.TiedOperands.empty());
     const unsigned OpIndex = Var.TiedOperands[0];
     const Operand &Op = Instr.Operands[OpIndex];
     assert(Op.Info);
     return Op.Info->OperandType == llvm::MCOI::OPERAND_IMMEDIATE;
   });
 }
 
-void InstructionInstance::randomizeUnsetVariables() {
+void InstructionInstance::randomizeUnsetVariables(
+    const llvm::BitVector &ForbiddenRegs) {
   for (const Variable &Var : Instr.Variables) {
     llvm::MCOperand &AssignedValue = getValueFor(Var);
     if (!AssignedValue.isValid())
-      randomize(Instr, Var, AssignedValue);
+      randomize(Instr, Var, AssignedValue, ForbiddenRegs);
   }
 }
 
 llvm::MCInst InstructionInstance::build() const {
   llvm::MCInst Result;
   Result.setOpcode(Instr.Description->Opcode);
   for (const auto &Op : Instr.Operands)
     if (Op.IsExplicit)

 }
 
 template <typename C>
 static auto randomElement(const C &Container) -> decltype(Container[0]) {
   return Container[randomIndex(Container.size())];
 }
 
 static void randomize(const Instruction &Instr, const Variable &Var,
-                      llvm::MCOperand &AssignedValue) {
+                      llvm::MCOperand &AssignedValue,
+                      const llvm::BitVector &ForbiddenRegs) {
   assert(!Var.TiedOperands.empty());
   const Operand &Op = Instr.Operands[Var.TiedOperands.front()];
   assert(Op.Info != nullptr);
   const auto &OpInfo = *Op.Info;
   switch (OpInfo.OperandType) {
   case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
     // FIXME: explore immediate values too.
     AssignedValue = llvm::MCOperand::createImm(1);
     break;
   case llvm::MCOI::OperandType::OPERAND_REGISTER: {
     assert(Op.Tracker);
-    const auto &Registers = Op.Tracker->sourceBits();
-    AssignedValue = llvm::MCOperand::createReg(randomBit(Registers));
+    auto AllowedRegs = Op.Tracker->sourceBits();
+    assert(AllowedRegs.size() == ForbiddenRegs.size());
+    for (auto I : ForbiddenRegs.set_bits())
+      AllowedRegs.reset(I);
+    AssignedValue = llvm::MCOperand::createReg(randomBit(AllowedRegs));
     break;
   }
   default:
     break;
   }
 }
 
 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,

llvm/trunk/tools/llvm-exegesis/lib/RegisterAliasing.h

struct RegisterAliasingTracker {
   int getOrigin(llvm::MCPhysReg Aliased) const {
     if (!AliasedBits[Aliased])
       return -1;
     return Origins[Aliased];
   }
 
 private:
   RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo);
+  RegisterAliasingTracker(const RegisterAliasingTracker &) = delete;
 
   void FillOriginAndAliasedBits(const llvm::MCRegisterInfo &RegInfo,
                                 const llvm::BitVector &OriginalBits);
 
   llvm::BitVector SourceBits;
   llvm::BitVector AliasedBits;
   llvm::PackedVector<size_t, 10> Origins; // Max 1024 physical registers.
 };

llvm/trunk/tools/llvm-exegesis/lib/Target.h

 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_TARGET_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_TARGET_H
 
 #include "BenchmarkResult.h"
 #include "BenchmarkRunner.h"
 #include "LlvmState.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/IR/CallingConv.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCRegisterInfo.h"
 
 namespace exegesis {
 
 class ExegesisTarget {
 public:
   // Targets can use this to add target-specific passes in assembleToStream();
   virtual void addTargetSpecificPasses(llvm::PassManagerBase &PM) const {}
 
   // Generates code to move a constant into a the given register.
   virtual std::vector<llvm::MCInst>
   setRegToConstant(const llvm::MCSubtargetInfo &STI, unsigned Reg) const {
     return {};
   }
 
+  // Returns the register pointing to scratch memory, or 0 if this target does
+  // not support memory operands. The benchmark function uses the default
+  // calling convention.
+  virtual unsigned getScratchMemoryRegister(const llvm::Triple &) const {
+    return 0;
+  }
+
+  // Fills memory operands with references to the address at [Reg] + Offset.
+  virtual void fillMemoryOperands(InstructionInstance &II, unsigned Reg,
+                                  unsigned Offset) const {
+    llvm_unreachable(
+        "fillMemoryOperands() requires getScratchMemoryRegister() > 0");
+  }
+
+  // Returns the maximum number of bytes a load/store instruction can access at
+  // once. This is typically the size of the largest register available on the
+  // processor. Note that this only used as a hint to generate independant
+  // load/stores to/from memory, so the exact returned value does not really
+  // matter as long as it's large enough.
+  virtual unsigned getMaxMemoryAccessSize() const { return 0; }
+
   // Creates a benchmark runner for the given mode.
   std::unique_ptr<BenchmarkRunner>
   createBenchmarkRunner(InstructionBenchmark::ModeE Mode,
                         const LLVMState &State) const;
 
   // Returns the ExegesisTarget for the given triple or nullptr if the target
   // does not exist.
   static const ExegesisTarget *lookup(llvm::Triple TT);

llvm/trunk/tools/llvm-exegesis/lib/Target.cpp

const ExegesisTarget *ExegesisTarget::lookup(llvm::Triple TT) {
   return nullptr;
 }
 
 void ExegesisTarget::registerTarget(ExegesisTarget *Target) {
   if (FirstTarget == nullptr) {
     FirstTarget = Target;
     return;
   }
-  assert(Target->Next == nullptr && "target has already been registered");
   if (Target->Next != nullptr)
-    return;
+    return; // Already registered.
   Target->Next = FirstTarget;
   FirstTarget = Target;
 }
 
 std::unique_ptr<BenchmarkRunner>
 ExegesisTarget::createBenchmarkRunner(InstructionBenchmark::ModeE Mode,
                                       const LLVMState &State) const {
   switch (Mode) {

llvm/trunk/tools/llvm-exegesis/lib/Uops.h

 public:
   UopsBenchmarkRunner(const LLVMState &State)
       : BenchmarkRunner(State, InstructionBenchmark::Uops) {}
   ~UopsBenchmarkRunner() override;
 
   llvm::Expected<SnippetPrototype>
   generatePrototype(unsigned Opcode) const override;
 
+  static constexpr const size_t kMinNumDifferentAddresses = 6;
+
 private:
   llvm::Error isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const;
 
   std::vector<BenchmarkMeasure>
-  runMeasurements(const ExecutableFunction &EF,
+  runMeasurements(const ExecutableFunction &EF, ScratchSpace &Scratch,
                   const unsigned NumRepetitions) const override;
+
+  // Instantiates memory operands within a snippet.
+  // To make computations as parallel as possible, we generate independant
+  // memory locations for instructions that load and store. If there are less
+  // than kMinNumDifferentAddresses in the original snippet, we duplicate
+  // instructions until there are this number of instructions.
+  // For example, assuming kMinNumDifferentAddresses=5 and
+  // getMaxMemoryAccessSize()=64, if the original snippet is:
+  //   mov eax, [memory]
+  // we might generate:
+  //   mov eax, [rdi]
+  //   mov eax, [rdi + 64]
+  //   mov eax, [rdi + 128]
+  //   mov eax, [rdi + 192]
+  //   mov eax, [rdi + 256]
+  // If the original snippet is:
+  //   mov eax, [memory]
+  //   add eax, [memory]
+  // we might generate:
+  //   mov eax, [rdi]
+  //   add eax, [rdi + 64]
+  //   mov eax, [rdi + 128]
+  //   add eax, [rdi + 192]
+  //   mov eax, [rdi + 256]
+  void
+  instantiateMemoryOperands(unsigned ScratchSpaceReg,
+                            std::vector<InstructionInstance> &Snippet) const;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_UOPS_H

llvm/trunk/tools/llvm-exegesis/lib/Uops.cpp

 //===-- Uops.cpp ------------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Uops.h"
 
 #include "Assembler.h"
 #include "BenchmarkRunner.h"
 #include "MCInstrDescView.h"
 #include "PerfHelper.h"
+#include "Target.h"
 
 // FIXME: Load constants into registers (e.g. with fld1) to not break
 // instructions like x87.
 
 // Ideally we would like the only limitation on executing uops to be the issue
 // ports. Maximizing port pressure increases the likelihood that the load is
 // distributed evenly across possible ports.
 

 // best.
 
 namespace exegesis {
 
 static bool hasUnknownOperand(const llvm::MCOperandInfo &OpInfo) {
   return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN;
 }
 
-// FIXME: Handle memory, see PR36905.
-static bool hasMemoryOperand(const llvm::MCOperandInfo &OpInfo) {
-  return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY;
-}
-
 llvm::Error
 UopsBenchmarkRunner::isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const {
   if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand))
     return llvm::make_error<BenchmarkFailure>(
         "Infeasible : has unknown operands");
-  if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand))
-    return llvm::make_error<BenchmarkFailure>(
-        "Infeasible : has memory operands");
   return llvm::Error::success();
 }
 
 // Returns whether this Variable ties Use and Def operands together.
 static bool hasTiedOperands(const Instruction &Instr, const Variable &Var) {
   bool HasUse = false;
   bool HasDef = false;
   for (const unsigned OpIndex : Var.TiedOperands) {

 static void remove(llvm::BitVector &a, const llvm::BitVector &b) {
   assert(a.size() == b.size());
   for (auto I : b.set_bits())
     a.reset(I);
 }
 
 UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
 
+void UopsBenchmarkRunner::instantiateMemoryOperands(
+    const unsigned ScratchSpaceReg,
+    std::vector<InstructionInstance> &Snippet) const {
+  if (ScratchSpaceReg == 0)
+    return;  // no memory operands.
+  const auto &ET = State.getExegesisTarget();
+  const unsigned MemStep = ET.getMaxMemoryAccessSize();
+  const size_t OriginalSnippetSize = Snippet.size();
+  size_t I = 0;
+  for (InstructionInstance &II : Snippet) {
+    ET.fillMemoryOperands(II, ScratchSpaceReg, I * MemStep);
+    ++I;
+  }
+
+  while (Snippet.size() < kMinNumDifferentAddresses) {
+    InstructionInstance II = Snippet[I % OriginalSnippetSize];
+    ET.fillMemoryOperands(II, ScratchSpaceReg, I * MemStep);
+    ++I;
+    Snippet.push_back(std::move(II));
+  }
+  assert(I * MemStep < ScratchSpace::kSize && "not enough scratch space");
+}
+
 llvm::Expected<SnippetPrototype>
 UopsBenchmarkRunner::generatePrototype(unsigned Opcode) const {
   const auto &InstrDesc = State.getInstrInfo().get(Opcode);
   if (auto E = isInfeasible(InstrDesc))
     return std::move(E);
   const Instruction Instr(InstrDesc, RATC);
+  const auto &ET = State.getExegesisTarget();
+  SnippetPrototype Prototype;
+
+  const llvm::BitVector *ScratchSpaceAliasedRegs = nullptr;
+  if (Instr.hasMemoryOperands()) {
+    Prototype.ScratchSpaceReg =
+        ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
+    if (Prototype.ScratchSpaceReg == 0)
+      return llvm::make_error<BenchmarkFailure>(
+          "Infeasible : target does not support memory instructions");
+    ScratchSpaceAliasedRegs =
+        &RATC.getRegister(Prototype.ScratchSpaceReg).aliasedBits();
+    // If the instruction implicitly writes to ScratchSpaceReg , abort.
+    // FIXME: We could make a copy of the scratch register.
+    for (const auto &Op : Instr.Operands) {
+      if (Op.IsDef && Op.ImplicitReg &&
+          ScratchSpaceAliasedRegs->test(*Op.ImplicitReg))
+        return llvm::make_error<BenchmarkFailure>(
+            "Infeasible : memory instruction uses scratch memory register");
+    }
+  }
+
   const AliasingConfigurations SelfAliasing(Instr, Instr);
+  InstructionInstance II(Instr);
   if (SelfAliasing.empty()) {
-    return generateUnconstrainedPrototype(Instr, "instruction is parallel");
+    Prototype.Explanation = "instruction is parallel, repeating a random one.";
+    Prototype.Snippet.push_back(std::move(II));
+    instantiateMemoryOperands(Prototype.ScratchSpaceReg, Prototype.Snippet);
+    return std::move(Prototype);
   }
   if (SelfAliasing.hasImplicitAliasing()) {
-    return generateUnconstrainedPrototype(Instr, "instruction is serial");
+    Prototype.Explanation = "instruction is serial, repeating a random one.";
+    Prototype.Snippet.push_back(std::move(II));
+    instantiateMemoryOperands(Prototype.ScratchSpaceReg, Prototype.Snippet);
+    return std::move(Prototype);
   }
   const auto TiedVariables = getTiedVariables(Instr);
   if (!TiedVariables.empty()) {
     if (TiedVariables.size() > 1)
       return llvm::make_error<llvm::StringError>(
           "Infeasible : don't know how to handle several tied variables",
           llvm::inconvertibleErrorCode());
     const Variable *Var = TiedVariables.front();
     assert(Var);
     assert(!Var->TiedOperands.empty());
     const Operand &Op = Instr.Operands[Var->TiedOperands.front()];
     assert(Op.Tracker);
-    SnippetPrototype Prototype;
     Prototype.Explanation =
         "instruction has tied variables using static renaming.";
     for (const llvm::MCPhysReg Reg : Op.Tracker->sourceBits().set_bits()) {
-      Prototype.Snippet.emplace_back(Instr);
-      Prototype.Snippet.back().getValueFor(*Var) =
-          llvm::MCOperand::createReg(Reg);
+      if (ScratchSpaceAliasedRegs && ScratchSpaceAliasedRegs->test(Reg))
+        continue; // Do not use the scratch memory address register.
+      InstructionInstance TmpII = II;
+      TmpII.getValueFor(*Var) = llvm::MCOperand::createReg(Reg);
+      Prototype.Snippet.push_back(std::move(TmpII));
     }
+    instantiateMemoryOperands(Prototype.ScratchSpaceReg, Prototype.Snippet);
     return std::move(Prototype);
   }
-  InstructionInstance II(Instr);
   // No tied variables, we pick random values for defs.
   llvm::BitVector Defs(State.getRegInfo().getNumRegs());
   for (const auto &Op : Instr.Operands) {
-    if (Op.Tracker && Op.IsExplicit && Op.IsDef) {
+    if (Op.Tracker && Op.IsExplicit && Op.IsDef && !Op.IsMem) {
       auto PossibleRegisters = Op.Tracker->sourceBits();
       remove(PossibleRegisters, RATC.reservedRegisters());
+      // Do not use the scratch memory address register.
+      if (ScratchSpaceAliasedRegs)
+        remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
       assert(PossibleRegisters.any() && "No register left to choose from");
       const auto RandomReg = randomBit(PossibleRegisters);
       Defs.set(RandomReg);
       II.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
     }
   }
   // And pick random use values that are not reserved and don't alias with defs.
   const auto DefAliases = getAliasedBits(State.getRegInfo(), Defs);
   for (const auto &Op : Instr.Operands) {
-    if (Op.Tracker && Op.IsExplicit && !Op.IsDef) {
+    if (Op.Tracker && Op.IsExplicit && !Op.IsDef && !Op.IsMem) {
       auto PossibleRegisters = Op.Tracker->sourceBits();
       remove(PossibleRegisters, RATC.reservedRegisters());
+      // Do not use the scratch memory address register.
+      if (ScratchSpaceAliasedRegs)
+        remove(PossibleRegisters, *ScratchSpaceAliasedRegs);
       remove(PossibleRegisters, DefAliases);
       assert(PossibleRegisters.any() && "No register left to choose from");
       const auto RandomReg = randomBit(PossibleRegisters);
       II.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg);
     }
   }
-  SnippetPrototype Prototype;
   Prototype.Explanation =
       "instruction has no tied variables picking Uses different from defs";
   Prototype.Snippet.push_back(std::move(II));
+  instantiateMemoryOperands(Prototype.ScratchSpaceReg, Prototype.Snippet);
   return std::move(Prototype);
 }
 
 std::vector<BenchmarkMeasure>
 UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function,
+                                     ScratchSpace &Scratch,
                                      const unsigned NumRepetitions) const {
   const auto &SchedModel = State.getSubtargetInfo().getSchedModel();
 
   std::vector<BenchmarkMeasure> Result;
   for (unsigned ProcResIdx = 1;
        ProcResIdx < SchedModel.getNumProcResourceKinds(); ++ProcResIdx) {
     const char *const PfmCounters = SchedModel.getExtraProcessorInfo()
                                         .PfmCounters.IssueCounters[ProcResIdx];
     if (!PfmCounters)
       continue;
     // We sum counts when there are several counters for a single ProcRes
     // (e.g. P23 on SandyBridge).
     int64_t CounterValue = 0;
     llvm::SmallVector<llvm::StringRef, 2> CounterNames;
     llvm::StringRef(PfmCounters).split(CounterNames, ',');
     for (const auto &CounterName : CounterNames) {
       pfm::PerfEvent UopPerfEvent(CounterName);
       if (!UopPerfEvent.valid())
         llvm::report_fatal_error(
             llvm::Twine("invalid perf event ").concat(PfmCounters));
       pfm::Counter Counter(UopPerfEvent);
+      Scratch.clear();
       Counter.start();
-      Function();
+      Function(Scratch.ptr());
       Counter.stop();
       CounterValue += Counter.read();
     }
     Result.push_back({llvm::itostr(ProcResIdx),
                       static_cast<double>(CounterValue) / NumRepetitions,
                       SchedModel.getProcResource(ProcResIdx)->Name});
   }
   return Result;
 }
 
+constexpr const size_t UopsBenchmarkRunner::kMinNumDifferentAddresses;
+
 } // namespace exegesis

llvm/trunk/tools/llvm-exegesis/lib/X86/Target.cpp

 };
 
 class ExegesisX86Target : public ExegesisTarget {
   void addTargetSpecificPasses(llvm::PassManagerBase &PM) const override {
     // Lowers FP pseudo-instructions, e.g. ABS_Fp32 -> ABS_F.
     PM.add(llvm::createX86FloatingPointStackifierPass());
   }
 
+  unsigned getScratchMemoryRegister(const llvm::Triple &TT) const override {
+    if (!TT.isArch64Bit()) {
+      // FIXME: This would require popping from the stack, so we would have to
+      // add some additional setup code.
+      return 0;
+    }
+    return TT.isOSWindows() ? llvm::X86::RCX : llvm::X86::RDI;
+  }
+
+  unsigned getMaxMemoryAccessSize() const override { return 64; }
+
+  void fillMemoryOperands(InstructionInstance &II, unsigned Reg,
+                          unsigned Offset) const override {
+    // FIXME: For instructions that read AND write to memory, we use the same
+    // value for input and output.
+    for (size_t I = 0, E = II.Instr.Operands.size(); I < E; ++I) {
+      const Operand *Op = &II.Instr.Operands[I];
+      if (Op->IsExplicit && Op->IsMem) {
+        // Case 1: 5-op memory.
+        assert((I + 5 <= E) && "x86 memory references are always 5 ops");
+        II.getValueFor(*Op) = llvm::MCOperand::createReg(Reg); // BaseReg
+        Op = &II.Instr.Operands[++I];
+        assert(Op->IsMem);
+        assert(Op->IsExplicit);
+        II.getValueFor(*Op) = llvm::MCOperand::createImm(1); // ScaleAmt
+        Op = &II.Instr.Operands[++I];
+        assert(Op->IsMem);
+        assert(Op->IsExplicit);
+        II.getValueFor(*Op) = llvm::MCOperand::createReg(0); // IndexReg
+        Op = &II.Instr.Operands[++I];
+        assert(Op->IsMem);
+        assert(Op->IsExplicit);
+        II.getValueFor(*Op) = llvm::MCOperand::createImm(Offset); // Disp
+        Op = &II.Instr.Operands[++I];
+        assert(Op->IsMem);
+        assert(Op->IsExplicit);
+        II.getValueFor(*Op) = llvm::MCOperand::createReg(0); // Segment
+        // Case2: segment:index addressing. We assume that ES is 0.
+      }
+    }
+  }
+
   std::vector<llvm::MCInst> setRegToConstant(const llvm::MCSubtargetInfo &STI,
                                              unsigned Reg) const override {
     // GPR.
     if (llvm::X86::GR8RegClass.contains(Reg))
       return {llvm::MCInstBuilder(llvm::X86::MOV8ri).addReg(Reg).addImm(1)};
     if (llvm::X86::GR16RegClass.contains(Reg))
       return {llvm::MCInstBuilder(llvm::X86::MOV16ri).addReg(Reg).addImm(1)};
     if (llvm::X86::GR32RegClass.contains(Reg))

llvm/trunk/unittests/tools/llvm-exegesis/ARM/AssemblerTest.cpp

static void SetUpTestCase() {
     LLVMInitializeARMTargetInfo();
     LLVMInitializeARMTargetMC();
     LLVMInitializeARMTarget();
     LLVMInitializeARMAsmPrinter();
   }
 };
 
 TEST_F(ARMMachineFunctionGeneratorTest, DISABLED_JitFunction) {
-  Check(llvm::MCInst(), 0x1e, 0xff, 0x2f, 0xe1);
+  Check(ExegesisTarget::getDefault(), {}, llvm::MCInst(), 0x1e, 0xff, 0x2f,
+        0xe1);
 }
 
 TEST_F(ARMMachineFunctionGeneratorTest, DISABLED_JitFunctionADDrr) {
-  Check(MCInstBuilder(llvm::ARM::ADDrr)
+  Check(ExegesisTarget::getDefault(), {llvm::ARM::R0},
+        MCInstBuilder(llvm::ARM::ADDrr)
             .addReg(llvm::ARM::R0)
             .addReg(llvm::ARM::R0)
             .addReg(llvm::ARM::R0)
             .addImm(llvm::ARMCC::AL)
             .addReg(0)
             .addReg(0),
         0x00, 0x00, 0x80, 0xe0, 0x1e, 0xff, 0x2f, 0xe1);
 }
 
 } // namespace
 } // namespace exegesis

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

+//===-- BenchmarkRunnerTest.cpp ---------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BenchmarkRunner.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace exegesis {
+
+namespace {
+
+TEST(ScratchSpaceTest, Works) {
+  BenchmarkRunner::ScratchSpace Space;
+  EXPECT_EQ(reinterpret_cast<intptr_t>(Space.ptr()) %
+                BenchmarkRunner::ScratchSpace::kAlignment,
+            0u);
+  Space.ptr()[0] = 42;
+  Space.ptr()[BenchmarkRunner::ScratchSpace::kSize - 1] = 43;
+  Space.clear();
+  EXPECT_EQ(Space.ptr()[0], 0);
+  EXPECT_EQ(Space.ptr()[BenchmarkRunner::ScratchSpace::kSize - 1], 0);
+}
+
+} // namespace
+} // namespace exegesis

llvm/trunk/unittests/tools/llvm-exegesis/CMakeLists.txt

 include_directories(
   ${LLVM_MAIN_SRC_DIR}/tools/llvm-exegesis/lib
   )
 
 set(LLVM_LINK_COMPONENTS
   MC
   MCParser
   Object
   Support
   Symbolize
   )
 
 add_llvm_unittest(LLVMExegesisTests
   BenchmarkResultTest.cpp
+  BenchmarkRunnerTest.cpp
   ClusteringTest.cpp
   PerfHelperTest.cpp
   )
 target_link_libraries(LLVMExegesisTests PRIVATE LLVMExegesis)
 
 if(LLVM_TARGETS_TO_BUILD MATCHES "X86")
   add_subdirectory(X86)
 endif()
 if(LLVM_TARGETS_TO_BUILD MATCHES "ARM")
   add_subdirectory(ARM)
 endif()
 if(LLVM_TARGETS_TO_BUILD MATCHES "AArch64")
   add_subdirectory(AArch64)
 endif()

llvm/trunk/unittests/tools/llvm-exegesis/Common/AssemblerUtils.h

 //===-- AssemblerUtils.h ----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Assembler.h"
+#include "BenchmarkRunner.h"
 #include "Target.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/MC/MCInstBuilder.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/TargetRegistry.h"
MachineFunctionGeneratorBaseTest(const std::string &TT,
                    llvm::Triple(llvm::sys::getProcessTriple()).getArch()) {
     if (!CanExecute) {
       llvm::outs() << "Skipping execution, host:"
                    << llvm::sys::getProcessTriple() << ", target:" << TT
                    << "\n";
     }
   }
 
-  template <class... Bs> inline void Check(llvm::MCInst MCInst, Bs... Bytes) {
-    CheckWithSetup(ExegesisTarget::getDefault(), {}, MCInst, Bytes...);
-  }
-
   template <class... Bs>
-  inline void CheckWithSetup(const ExegesisTarget &ET,
-                             llvm::ArrayRef<unsigned> RegsToDef,
-                             llvm::MCInst MCInst, Bs... Bytes) {
+  inline void Check(const ExegesisTarget &ET,
+                    llvm::ArrayRef<unsigned> RegsToDef, llvm::MCInst MCInst,
+                    Bs... Bytes) {
     ExecutableFunction Function =
         (MCInst.getOpcode() == 0) ? assembleToFunction(ET, RegsToDef, {})
                                   : assembleToFunction(ET, RegsToDef, {MCInst});
     ASSERT_THAT(Function.getFunctionBytes().str(),
                 testing::ElementsAre(Bytes...));
-    if (CanExecute)
-      Function();
+    if (CanExecute) {
+      BenchmarkRunner::ScratchSpace Scratch;
+      Function(Scratch.ptr());
+    }
   }
 
 private:
   std::unique_ptr<llvm::LLVMTargetMachine> createTargetMachine() {
     std::string Error;
     const llvm::Target *TheTarget =
         llvm::TargetRegistry::lookupTarget(TT, Error);
     EXPECT_TRUE(TheTarget) << Error << " " << TT;
     const llvm::TargetOptions Options;
     llvm::TargetMachine *TM = TheTarget->createTargetMachine(
         TT, CpuName, "", Options, llvm::Reloc::Model::Static);
     EXPECT_TRUE(TM) << TT << " " << CpuName;
     return std::unique_ptr<llvm::LLVMTargetMachine>(
         static_cast<llvm::LLVMTargetMachine *>(TM));
   }
 
   ExecutableFunction
   assembleToFunction(const ExegesisTarget &ET,
                      llvm::ArrayRef<unsigned> RegsToDef,
                      llvm::ArrayRef<llvm::MCInst> Instructions) {
     llvm::SmallString<256> Buffer;
     llvm::raw_svector_ostream AsmStream(Buffer);
-    assembleToStream(ET, createTargetMachine(), RegsToDef, Instructions,
+    assembleToStream(ET, createTargetMachine(), /*LiveIns=*/{},
+                     RegsToDef, Instructions,
                      AsmStream);
     return ExecutableFunction(createTargetMachine(),
                               getObjectFromBuffer(AsmStream.str()));
   }
 
   const std::string TT;
   const std::string CpuName;
   const bool CanExecute;
 };
 
 } // namespace exegesis

llvm/trunk/unittests/tools/llvm-exegesis/X86/AssemblerTest.cpp

 //===-- AssemblerTest.cpp ---------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../Common/AssemblerUtils.h"
 #include "X86InstrInfo.h"
 
 namespace exegesis {
+
+void InitializeX86ExegesisTarget();
+
 namespace {
 
 using llvm::MCInstBuilder;
 using llvm::X86::EAX;
 using llvm::X86::MOV32ri;
 using llvm::X86::MOV64ri32;
 using llvm::X86::RAX;
 using llvm::X86::XOR32rr;
 
 class X86MachineFunctionGeneratorTest
     : public MachineFunctionGeneratorBaseTest {
 protected:
   X86MachineFunctionGeneratorTest()
       : MachineFunctionGeneratorBaseTest("x86_64-unknown-linux", "haswell") {}
 
   static void SetUpTestCase() {
     LLVMInitializeX86TargetInfo();
     LLVMInitializeX86TargetMC();
     LLVMInitializeX86Target();
     LLVMInitializeX86AsmPrinter();
+    InitializeX86ExegesisTarget();
   }
 };
 
 TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunction) {
-  Check(llvm::MCInst(), 0xc3);
+  Check(ExegesisTarget::getDefault(), {}, llvm::MCInst(), 0xc3);
 }
 
-TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr) {
-  Check(MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX), 0x31, 0xc0,
+TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr_Default) {
+  Check(ExegesisTarget::getDefault(), {EAX},
+        MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX), 0x31, 0xc0,
         0xc3);
 }
 
+TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr_X86) {
+  const auto *ET = ExegesisTarget::lookup(llvm::Triple("x86_64-unknown-linux"));
+  ASSERT_NE(ET, nullptr);
+  Check(*ET, {EAX}, MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX),
+        // mov eax, 1
+        0xb8, 0x01, 0x00, 0x00, 0x00,
+        // xor eax, eax
+        0x31, 0xc0, 0xc3);
+}
+
 TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV64ri) {
-  Check(MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42), 0x48, 0xc7, 0xc0, 0x2a,
+  Check(ExegesisTarget::getDefault(), {},
+        MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42), 0x48, 0xc7, 0xc0, 0x2a,
         0x00, 0x00, 0x00, 0xc3);
 }
 
 TEST_F(X86MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV32ri) {
-  Check(MCInstBuilder(MOV32ri).addReg(EAX).addImm(42), 0xb8, 0x2a, 0x00, 0x00,
+  Check(ExegesisTarget::getDefault(), {},
+        MCInstBuilder(MOV32ri).addReg(EAX).addImm(42), 0xb8, 0x2a, 0x00, 0x00,
         0x00, 0xc3);
 }
 
 } // namespace
 } // namespace exegesis

llvm/trunk/unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp

 #include "MCInstrDescView.h"
 #include "RegisterAliasing.h"
 #include "Uops.h"
 #include "X86InstrInfo.h"
 
 #include <unordered_set>
 
 namespace exegesis {
+
+void InitializeX86ExegesisTarget();
+
 namespace {
 
 using testing::AnyOf;
 using testing::ElementsAre;
 using testing::HasSubstr;
 using testing::Not;
 using testing::SizeIs;
 using testing::UnorderedElementsAre;
 
 MATCHER(IsInvalid, "") { return !arg.isValid(); }
 MATCHER(IsReg, "") { return arg.isReg(); }
 
 class X86SnippetGeneratorTest : public ::testing::Test {
 protected:
   X86SnippetGeneratorTest()
       : State("x86_64-unknown-linux", "haswell"),
         MCInstrInfo(State.getInstrInfo()), MCRegisterInfo(State.getRegInfo()) {}
 
   static void SetUpTestCase() {
     LLVMInitializeX86TargetInfo();
     LLVMInitializeX86TargetMC();
     LLVMInitializeX86Target();
     LLVMInitializeX86AsmPrinter();
+    InitializeX86ExegesisTarget();
   }
 
   const LLVMState State;
   const llvm::MCInstrInfo &MCInstrInfo;
   const llvm::MCRegisterInfo &MCRegisterInfo;
 };
 
 template <typename BenchmarkRunner>
TEST_F(UopsSnippetGeneratorTest, NoTiedVariables) {
   ASSERT_THAT(II.VariableValues, SizeIs(4));
   EXPECT_THAT(II.VariableValues[0].getReg(), Not(II.VariableValues[1].getReg()))
       << "Def is different from first Use";
   EXPECT_THAT(II.VariableValues[0].getReg(), Not(II.VariableValues[2].getReg()))
       << "Def is different from second Use";
   EXPECT_THAT(II.VariableValues[3], IsInvalid());
 }
 
+TEST_F(UopsSnippetGeneratorTest, MemoryUse) {
+  // Mov32rm reads from memory.
+  const unsigned Opcode = llvm::X86::MOV32rm;
+  const SnippetPrototype Proto = checkAndGetConfigurations(Opcode);
+  EXPECT_THAT(Proto.Explanation, HasSubstr("no tied variables"));
+  ASSERT_THAT(Proto.Snippet,
+              SizeIs(UopsBenchmarkRunner::kMinNumDifferentAddresses));
+  const InstructionInstance &II = Proto.Snippet[0];
+  EXPECT_THAT(II.getOpcode(), Opcode);
+  ASSERT_THAT(II.VariableValues, SizeIs(6));
+  EXPECT_EQ(II.VariableValues[2].getImm(), 1);
+  EXPECT_EQ(II.VariableValues[3].getReg(), 0u);
+  EXPECT_EQ(II.VariableValues[4].getImm(), 0);
+  EXPECT_EQ(II.VariableValues[5].getReg(), 0u);
+}
+
+TEST_F(UopsSnippetGeneratorTest, MemoryUse_Movsb) {
+  // MOVSB writes to scratch memory register.
+  const unsigned Opcode = llvm::X86::MOVSB;
+  auto Error = Runner.generatePrototype(Opcode).takeError();
+  EXPECT_TRUE((bool)Error);
+  llvm::consumeError(std::move(Error));
+}
+
 class FakeBenchmarkRunner : public BenchmarkRunner {
 public:
   FakeBenchmarkRunner(const LLVMState &State)
       : BenchmarkRunner(State, InstructionBenchmark::Unknown) {}
 
   Instruction createInstruction(unsigned Opcode) {
     return Instruction(State.getInstrInfo().get(Opcode), RATC);
   }
 
 private:
   llvm::Expected<SnippetPrototype>
   generatePrototype(unsigned Opcode) const override {
     return llvm::make_error<llvm::StringError>("not implemented",
                                                llvm::inconvertibleErrorCode());
   }
 
   std::vector<BenchmarkMeasure>
-  runMeasurements(const ExecutableFunction &EF,
+  runMeasurements(const ExecutableFunction &EF, ScratchSpace &Scratch,
                   const unsigned NumRepetitions) const override {
     return {};
   }
 };
 
 using FakeSnippetGeneratorTest = SnippetGeneratorTest<FakeBenchmarkRunner>;
 
 TEST_F(FakeSnippetGeneratorTest, ComputeRegsToDefAdd16ri) {