Update llvm-exegesis to cover latency through another opcode.

[gchatelet]

Summary

Restructuring the code to measure latency and uops.
The end goal is to have this program spawn another process to deal with SIGILL and other malformed programs. It is not yet the case in this redesign, it is still the main program that runs the code (and may crash).
It now uses BitVector instead of Graph for performance reasons.

[courbet]

tools/llvm-exegesis/lib/Assembler.cpp

28

Please keep the statics: https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

tools/llvm-exegesis/lib/Assembler.h

44

doc ?

58

doc ?

62

doc ?

64

doc ?

[courbet]

tools/llvm-exegesis/lib/Assembler.cpp

229

Given that you're moving from AC, I don't think it makes sense to have AC be a member variable here. AC should not be accessible outside of this function.

255

it'd be better if the error was handled by the caller. BTW I don't see who's calling that.

tools/llvm-exegesis/lib/BenchmarkResult.cpp

63–67

Please rebase.

95

what about letting the caller handle the error ?

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

28

static + remove namespace

29

It does not really make sense to create a function to get the reserved registers. Could you refactor this ?

83–88

let's avoid creating a target machine several times. It could be a State member.

tools/llvm-exegesis/lib/BenchmarkRunner.h

57

why not private ?

60–61

Let's keep llvm::Expected<std::vector<llvm::MCInst>> if you don't mind.

61

ditto

64–70

ditto

tools/llvm-exegesis/lib/Latency.cpp

22

static

60

let's take the OS as a parameter. This will allow disabling debug or dumping it to a field of the benchmark results.

tools/llvm-exegesis/lib/MCInstrDescView.h

2

header + file doc

[gchatelet]

tools/llvm-exegesis/lib/Assembler.cpp

229

Yes, that's part of the redesign I intend to do. I added some FIXME in the header file.

255

Nobody does for now, it's a leftover from the code I wrote earlier to deal with the process spawning. I'll just remove it for now.

[gchatelet]

• Add documentation to Assembler.h.

[gchatelet]

• Fix missing static in Assembler.cpp.

[gchatelet]

• Update documentation in BenchmarkResult.

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkResult.cpp

95

Let's do this in a separate Patch if you don't mind.

[gchatelet]

• Return an llvm::Expected instead of passing vector by ref.

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

29

It's part of the redesign of Assembler.{h/cpp}. I'll add a FIXME.

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.

[gchatelet]

• Added Description to MCInstrDescView.h.

[gchatelet]

• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.

[gchatelet]

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

83–88

Unfortunately the target machine is consumed by the ExecutableFunction to create the ExecutionEngine.
I'm not sure if I can reuse the ExecutionEngine, I'll try this in a following Patch to address the FIXMEs.

[courbet]

tools/llvm-exegesis/lib/AliasingTracker.cpp

1 ↗

(On Diff #146603)

Missing header. please check all other files.

tools/llvm-exegesis/lib/Assembler.cpp

10–13

file header.

229

My point is: where else is AC used ? If it's used outside of the ctor, it's probably wrong, because AC was moved from. If it's use donly in the ctor, why not make it local to the ctor now ?

tools/llvm-exegesis/lib/Assembler.h

67

s/TM/Instructions ?

69

"it is assembled (for TM) to AsmStream,..."

75

"Creates an ObjectFile in the format understood by TM"

tools/llvm-exegesis/lib/BenchmarkResult.h

53

Did you clang-format your patch ?

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

32

let's inline getReservedRegs() here.

[courbet]

tools/llvm-exegesis/lib/AliasingTracker.h

41 ↗

(On Diff #146603)

RegisterAliasingTracker because Aliasing has too many meanings.

tools/llvm-exegesis/lib/MCInstrDescView.cpp

153

[style]randomGenerator

155

let's seed with a flag or a constexpr (unittests will thank you).

161

[style] static

161

[style]randomIndex

163

[style]Dis

168

[style] static+randomElement

180

Add a FIXME to explore immediate values too.

206

[style] randomBit

tools/llvm-exegesis/lib/MCInstrDescView.h

80

RegisterOperandAssignment ?

85

Reg

92

// There are two reasons why operands would alias:
// - The registers assigned to each of the operands are the same or alias each other (e.g. AX/AL)
// - The operands are tied.

116

Let's get rid of SmallSet and use std::find

120

ideally this would come from the main (or tests). Possibly in a subsequent revision.

128

AliasingConfigurations AliasingConfigurations::createRandomAssignment(const AliasingConfigurations &AliasingConfigurations);

tools/llvm-exegesis/lib/PerfHelper.cpp

113 ↗

(On Diff #146603)

I submitted this independently for you as r332330, please rebase.

tools/llvm-exegesis/lib/Uops.cpp

83–84

static

[courbet]

tools/llvm-exegesis/lib/MCInstrDescView.h

131

clearVariableAssignments ?

tools/llvm-exegesis/lib/Uops.cpp

110

hasTiedOperands

143

getTiedVariables

151

remove

173

remove assert, add an if, say it in debug and return an error.

236

format

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.
• Add header in Assembler.cpp.
• Fix comments in Assembler.h.
• Simplify Assembler file and remove most of the clutter.

[gchatelet]

• Update comments and fix missing line feed.

[gchatelet]

• Get rid of SmallSet.

[gchatelet]

• rename clearVariable in clearVariableAssignments.

[gchatelet]

• Fix style for random generator functions.

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.
• Add header in Assembler.cpp.
• Fix comments in Assembler.h.
• Simplify Assembler file and remove most of the clutter.
• Update comments and fix missing line feed.
• Get rid of SmallSet.
• rename clearVariable in clearVariableAssignments.
• Fix style for random generator functions.
• Add a FIXME to explore immediate values.
• Fix private namespace and code style.
• Fix wrong rebase
• Turn an assert into a real error.

[gchatelet]

tools/llvm-exegesis/lib/MCInstrDescView.h

120

Yes let's do this in a subsequent version.

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.
• Add header in Assembler.cpp.
• Fix comments in Assembler.h.
• Simplify Assembler file and remove most of the clutter.
• Update comments and fix missing line feed.
• Get rid of SmallSet.
• rename clearVariable in clearVariableAssignments.
• Fix style for random generator functions.
• Add a FIXME to explore immediate values.
• Fix private namespace and code style.
• Fix wrong rebase
• Turn an assert into a real error.
• Added FIXME.

tools/llvm-exegesis/lib/MCInstrDescView.cpp

155

Added a FIXME, I'll do this in a follow up patch.

tools/llvm-exegesis/lib/MCInstrDescView.h

128

Added a FIXME, I'll do it in a follow up patch.

[gchatelet]

• Adding informations inside the YAML output (code snippet, strategy).

[courbet]

Only minor comments left.

tools/llvm-exegesis/lib/Assembler.h

49

s/TM/the host/ (there's no TM anymore).

tools/llvm-exegesis/lib/MCInstrDescView.cpp

2

file header.

12

static

97

static

tools/llvm-exegesis/lib/RegisterAliasing.cpp

2

file header.

tools/llvm-exegesis/lib/RegisterAliasing.h

42

Let's rename this to "RegisterAliasingTracker"

76

ditto

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.
• Add header in Assembler.cpp.
• Fix comments in Assembler.h.
• Simplify Assembler file and remove most of the clutter.
• Update comments and fix missing line feed.
• Get rid of SmallSet.
• rename clearVariable in clearVariableAssignments.
• Fix style for random generator functions.
• Add a FIXME to explore immediate values.
• Fix private namespace and code style.
• Fix wrong rebase
• Turn an assert into a real error.
• Added FIXME.
• Adding informations inside the YAML output (code snippet, strategy).
• Fix typo in documentation.
• Fix missing header and code style.
• Rename AliasingTracker and AliasingTrackerCache.

[gchatelet]

Rebase.

[courbet]

tools/llvm-exegesis/lib/MCInstrDescView.h

63

this breaks the build in -Wall mode. Use Var.

83

ditto

[gchatelet]

• Add documentation to Assembler.h.
• Fix missing static in Assembler.cpp.
• Update documentation in BenchmarkResult.
• Return an llvm::Expected instead of passing vector by ref.
• Removed private namespace and added FIXME.
• Remove private namespace.
• Added Description to MCInstrDescView.h.
• Added Fixme to BenchmarkRunner.
• Make create snippet debug information an argument of the function.
• Rename AliasingTracker files into RegisterAliasing.
• Add header in Assembler.cpp.
• Fix comments in Assembler.h.
• Simplify Assembler file and remove most of the clutter.
• Update comments and fix missing line feed.
• Get rid of SmallSet.
• rename clearVariable in clearVariableAssignments.
• Fix style for random generator functions.
• Add a FIXME to explore immediate values.
• Fix private namespace and code style.
• Fix wrong rebase
• Turn an assert into a real error.
• Added FIXME.
• Adding informations inside the YAML output (code snippet, strategy).
• Fix typo in documentation.
• Fix missing header and code style.
• Rename AliasingTracker and AliasingTrackerCache.
• Rename Variable to Var.
• Rename Operand variable into Op.

[gchatelet]

Done.

tools/llvm-exegesis/lib/Assembler.h

+//===-- Assembler.h ---------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Defines classes to assemble functions composed of a single basic block of
+/// MCInsts.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H
+
+#include <memory>
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/ExecutionEngine/ExecutionEngine.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetMachine.h"
+
+namespace exegesis {
+
+// 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
+// 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(std::unique_ptr<llvm::LLVMTargetMachine> TM,
+                      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
+// 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())(); }
+
+  std::unique_ptr<llvm::LLVMContext> Context;
+  std::unique_ptr<llvm::ExecutionEngine> ExecEngine;
+  llvm::StringRef FunctionBytes;
+};
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H

tools/llvm-exegesis/lib/Assembler.cpp

-//===-- InMemoryAssembler.cpp -----------------------------------*- C++ -*-===//
+//===-- Assembler.cpp -------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "InMemoryAssembler.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/StringRef.h"
+#include "Assembler.h"
+
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
-#include "llvm/ExecutionEngine/ExecutionEngine.h"
-#include "llvm/ExecutionEngine/MCJIT.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/ExecutionEngine/SectionMemoryManager.h"
-#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManager.h"
-#include "llvm/MC/MCFixup.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/Object/Binary.h"
-#include "llvm/Object/ObjectFile.h"
-#include "llvm/PassInfo.h"
-#include "llvm/PassRegistry.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetOptions.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/Support/MemoryBuffer.h"
 
 namespace exegesis {
 
 static constexpr const char ModuleID[] = "ExegesisInfoTest";
 static constexpr const char FunctionID[] = "foo";
 
 // Small utility function to add named passes.
 static bool addPass(llvm::PassManagerBase &PM, llvm::StringRef PassName,
                     llvm::TargetPassConfig &TPC) {
   const llvm::PassRegistry *PR = llvm::PassRegistry::getPassRegistry();
   const llvm::PassInfo *PI = PR->getPassInfo(PassName);
   if (!PI) {
     llvm::errs() << " run-pass " << PassName << " is not registered.\n";
createVoidVoidMachineFunction(llvm::StringRef FunctionID, llvm::Module *Module,
   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 llvm::object::OwningBinary<llvm::object::ObjectFile>
-assemble(llvm::Module *Module, std::unique_ptr<llvm::MachineModuleInfo> MMI,
-         llvm::LLVMTargetMachine *LLVMTM) {
-  llvm::legacy::PassManager PM;
-  llvm::MCContext &Context = MMI->getContext();
-
-  llvm::TargetLibraryInfoImpl TLII(llvm::Triple(Module->getTargetTriple()));
-  PM.add(new llvm::TargetLibraryInfoWrapperPass(TLII));
-
-  llvm::TargetPassConfig *TPC = LLVMTM->createPassConfig(PM);
-  PM.add(TPC);
-  PM.add(MMI.release());
-  TPC->printAndVerify("MachineFunctionGenerator::assemble");
-  // Adding the following passes:
-  // - machineverifier: checks that the MachineFunction is well formed.
-  // - prologepilog: saves and restore callee saved registers.
-  for (const char *PassName : {"machineverifier", "prologepilog"})
-    if (addPass(PM, PassName, *TPC))
-      llvm::report_fatal_error("Unable to add a mandatory pass");
-  TPC->setInitialized();
-
-  llvm::SmallVector<char, 4096> AsmBuffer;
-  llvm::raw_svector_ostream AsmStream(AsmBuffer);
-  // AsmPrinter is responsible for generating the assembly into AsmBuffer.
-  if (LLVMTM->addAsmPrinter(PM, AsmStream, llvm::TargetMachine::CGFT_ObjectFile,
-                            Context))
-    llvm::report_fatal_error("Cannot add AsmPrinter passes");
-
-  PM.run(*Module); // Run all the passes
-
-  // Storing the generated assembly into a MemoryBuffer that owns the memory.
-  std::unique_ptr<llvm::MemoryBuffer> Buffer =
-      llvm::MemoryBuffer::getMemBufferCopy(AsmStream.str());
-  // Create the ObjectFile from the MemoryBuffer.
-  std::unique_ptr<llvm::object::ObjectFile> Obj = llvm::cantFail(
-      llvm::object::ObjectFile::createObjectFile(Buffer->getMemBufferRef()));
-  // Returning both the MemoryBuffer and the ObjectFile.
-  return llvm::object::OwningBinary<llvm::object::ObjectFile>(
-      std::move(Obj), std::move(Buffer));
-}
-
 static void fillMachineFunction(llvm::MachineFunction &MF,
                                 llvm::ArrayRef<llvm::MCInst> Instructions) {
   llvm::MachineBasicBlock *MBB = MF.CreateMachineBasicBlock();
   MF.push_back(MBB);
   const llvm::MCInstrInfo *MCII = MF.getTarget().getMCInstrInfo();
   llvm::DebugLoc DL;
   for (const llvm::MCInst &Inst : Instructions) {
     const unsigned Opcode = Inst.getOpcode();
if (TII->getReturnOpcode() < TII->getNumOpcodes()) {
     llvm::BuildMI(MBB, DL, TII->get(TII->getReturnOpcode()));
   } else {
     llvm::MachineIRBuilder MIB(MF);
     MIB.setMBB(*MBB);
     MF.getSubtarget().getCallLowering()->lowerReturn(MIB, nullptr, 0);
   }
 }
 
+static std::unique_ptr<llvm::Module>
+createModule(const std::unique_ptr<llvm::LLVMContext> &Context,
+             const llvm::DataLayout DL) {
+  auto Module = llvm::make_unique<llvm::Module>(ModuleID, *Context);
+  Module->setDataLayout(DL);
+  return Module;
+}
+
+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());
+  // Saving reserved registers for client.
+  return MF.getSubtarget().getRegisterInfo()->getReservedRegs(MF);
+}
+
+void assembleToStream(std::unique_ptr<llvm::LLVMTargetMachine> TM,
+                      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());
+
+  // 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);
+  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);
+
+  // 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::TargetPassConfig *TPC = TM->createPassConfig(PM);
+  PM.add(TPC);
+  PM.add(MMI.release());
+  TPC->printAndVerify("MachineFunctionGenerator::assemble");
+  // Adding the following passes:
+  // - machineverifier: checks that the MachineFunction is well formed.
+  // - prologepilog: saves and restore callee saved registers.
+  for (const char *PassName : {"machineverifier", "prologepilog"})
+    if (addPass(PM, PassName, *TPC))
+      llvm::report_fatal_error("Unable to add a mandatory pass");
+  TPC->setInitialized();
+
+  // AsmPrinter is responsible for generating the assembly into AsmBuffer.
+  if (TM->addAsmPrinter(PM, AsmStream, llvm::TargetMachine::CGFT_ObjectFile,
+                        MCContext))
+    llvm::report_fatal_error("Cannot add AsmPrinter passes");
+
+  PM.run(*Module); // Run all the passes
+}
+
+llvm::object::OwningBinary<llvm::object::ObjectFile>
+getObjectFromBuffer(llvm::StringRef InputData) {
+  // Storing the generated assembly into a MemoryBuffer that owns the memory.
+  std::unique_ptr<llvm::MemoryBuffer> Buffer =
+      llvm::MemoryBuffer::getMemBufferCopy(InputData);
+  // Create the ObjectFile from the MemoryBuffer.
+  std::unique_ptr<llvm::object::ObjectFile> Obj = llvm::cantFail(
+      llvm::object::ObjectFile::createObjectFile(Buffer->getMemBufferRef()));
+  // Returning both the MemoryBuffer and the ObjectFile.
+  return llvm::object::OwningBinary<llvm::object::ObjectFile>(
+      std::move(Obj), std::move(Buffer));
+}
+
+llvm::object::OwningBinary<llvm::object::ObjectFile>
+getObjectFromFile(llvm::StringRef Filename) {
+  return llvm::cantFail(llvm::object::ObjectFile::createObjectFile(Filename));
+}
+
 namespace {
 
 // Implementation of this class relies on the fact that a single object with a
 // single function will be loaded into memory.
 class TrackingSectionMemoryManager : public llvm::SectionMemoryManager {
 public:
   explicit TrackingSectionMemoryManager(uintptr_t *CodeSize)
       : CodeSize(CodeSize) {}
 
   uint8_t *allocateCodeSection(uintptr_t Size, unsigned Alignment,
                                unsigned SectionID,
                                llvm::StringRef SectionName) override {
     *CodeSize = Size;
     return llvm::SectionMemoryManager::allocateCodeSection(
         Size, Alignment, SectionID, SectionName);
   }
 
 private:
   uintptr_t *const CodeSize = nullptr;
 };
 
 } // namespace
 
-JitFunctionContext::JitFunctionContext(
-    std::unique_ptr<llvm::LLVMTargetMachine> TheTM)
-    : Context(llvm::make_unique<llvm::LLVMContext>()), TM(std::move(TheTM)),
-      MMI(llvm::make_unique<llvm::MachineModuleInfo>(TM.get())),
-      Module(llvm::make_unique<llvm::Module>(ModuleID, *Context)) {
-  Module->setDataLayout(TM->createDataLayout());
-  MF = &createVoidVoidMachineFunction(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);
-  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);
-  // Saving reserved registers for client.
-  ReservedRegs = MF->getSubtarget().getRegisterInfo()->getReservedRegs(*MF);
-}
-
-JitFunction::JitFunction(JitFunctionContext &&Context,
-                         llvm::ArrayRef<llvm::MCInst> Instructions)
-    : FunctionContext(std::move(Context)) {
-  fillMachineFunction(*FunctionContext.MF, Instructions);
-  // We create the pass manager, run the passes and returns the produced
-  // ObjectFile.
-  llvm::object::OwningBinary<llvm::object::ObjectFile> ObjHolder =
-      assemble(FunctionContext.Module.get(), std::move(FunctionContext.MMI),
-               FunctionContext.TM.get());
-  assert(ObjHolder.getBinary() && "cannot create object file");
+ExecutableFunction::ExecutableFunction(
+    std::unique_ptr<llvm::LLVMTargetMachine> TM,
+    llvm::object::OwningBinary<llvm::object::ObjectFile> &&ObjectFileHolder)
+    : Context(llvm::make_unique<llvm::LLVMContext>()) {
+  assert(ObjectFileHolder.getBinary() && "cannot create object file");
   // Initializing the execution engine.
   // We need to use the JIT EngineKind to be able to add an object file.
   LLVMLinkInMCJIT();
   uintptr_t CodeSize = 0;
   std::string Error;
-  llvm::LLVMTargetMachine *TM = FunctionContext.TM.release();
   ExecEngine.reset(
-      llvm::EngineBuilder(std::move(FunctionContext.Module))
+      llvm::EngineBuilder(createModule(Context, TM->createDataLayout()))
           .setErrorStr(&Error)
           .setMCPU(TM->getTargetCPU())
           .setEngineKind(llvm::EngineKind::JIT)
           .setMCJITMemoryManager(
               llvm::make_unique<TrackingSectionMemoryManager>(&CodeSize))
-          .create(TM));
+          .create(TM.release()));
   if (!ExecEngine)
     llvm::report_fatal_error(Error);
   // Adding the generated object file containing the assembled function.
   // The ExecutionEngine makes sure the object file is copied into an
   // executable page.
-  ExecEngine->addObjectFile(std::move(ObjHolder));
-  // Setting function
+  ExecEngine->addObjectFile(std::move(ObjectFileHolder));
+  // Fetching function bytes.
   FunctionBytes =
       llvm::StringRef(reinterpret_cast<const char *>(
                           ExecEngine->getFunctionAddress(FunctionID)),
                       CodeSize);
 }
 
 } // namespace exegesis

tools/llvm-exegesis/lib/BenchmarkResult.h

struct InstructionBenchmark {
   std::string CpuName;
   std::string LLVMTriple;
   int NumRepetitions = 0;
   std::vector<BenchmarkMeasure> Measurements;
   std::string Error;
   std::string Info;
 
   static InstructionBenchmark readYamlOrDie(llvm::StringRef Filename);
-  static std::vector<InstructionBenchmark> readYamlsOrDie(llvm::StringRef Filename);
+  static std::vector<InstructionBenchmark>
 
-  // Unfortunately this function is non const because of YAML traits.
+  // Read functions.
+  readYamlsOrDie(llvm::StringRef Filename);
+  void readYamlFrom(llvm::StringRef InputContent);
+
+  // Write functions, non-const because of YAML traits.
+  void writeYamlTo(llvm::raw_ostream &S);
   void writeYamlOrDie(const llvm::StringRef Filename);
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRESULT_H

tools/llvm-exegesis/lib/BenchmarkResult.cpp

 };
 
 } // namespace yaml
 } // namespace llvm
 
 LLVM_YAML_IS_DOCUMENT_LIST_VECTOR(exegesis::InstructionBenchmark)
 
 namespace exegesis {
 
-namespace {
-
 template <typename ObjectOrList>
-ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) {
+static ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) {
   std::unique_ptr<llvm::MemoryBuffer> MemBuffer = llvm::cantFail(
       llvm::errorOrToExpected(llvm::MemoryBuffer::getFile(Filename)));
   llvm::yaml::Input Yin(*MemBuffer);
   ObjectOrList Benchmark;
   Yin >> Benchmark;
   return Benchmark;
 }
 
-} // namespace
-
 InstructionBenchmark
 InstructionBenchmark::readYamlOrDie(llvm::StringRef Filename) {
   return readYamlOrDieCommon<InstructionBenchmark>(Filename);
 }
 
 std::vector<InstructionBenchmark>
 InstructionBenchmark::readYamlsOrDie(llvm::StringRef Filename) {
   return readYamlOrDieCommon<std::vector<InstructionBenchmark>>(Filename);
 }
 
+void InstructionBenchmark::writeYamlTo(llvm::raw_ostream &S) {
+  llvm::yaml::Output Yout(S);
+  Yout << *this;
+}
+
+void InstructionBenchmark::readYamlFrom(llvm::StringRef InputContent) {
+  llvm::yaml::Input Yin(InputContent);
+  Yin >> *this;
+}
+
+// FIXME: Change the API to let the caller handle errors.
 void InstructionBenchmark::writeYamlOrDie(const llvm::StringRef Filename) {
   if (Filename == "-") {
-    llvm::yaml::Output Yout(llvm::outs());
-    Yout << *this;
+    writeYamlTo(llvm::outs());
   } else {
-    llvm::SmallString<1024> Buffer;
-    llvm::raw_svector_ostream Ostr(Buffer);
-    llvm::yaml::Output Yout(Ostr);
-    Yout << *this;
-    std::unique_ptr<llvm::FileOutputBuffer> File =
-        llvm::cantFail(llvm::FileOutputBuffer::create(Filename, Buffer.size()));
-    memcpy(File->getBufferStart(), Buffer.data(), Buffer.size());
-    llvm::cantFail(File->commit());
+    int ResultFD = 0;
+    llvm::cantFail(llvm::errorCodeToError(
+        openFileForWrite(Filename, ResultFD, llvm::sys::fs::F_Text)));
+    llvm::raw_fd_ostream Ostr(ResultFD, true /*shouldClose*/);
+    writeYamlTo(Ostr);
   }
 }
 
 } // namespace exegesis

tools/llvm-exegesis/lib/BenchmarkRunner.h

 /// Defines the abstract BenchmarkRunner class for measuring a certain execution
 /// property of instructions (e.g. latency).
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H
 
+#include "Assembler.h"
 #include "BenchmarkResult.h"
-#include "InMemoryAssembler.h"
 #include "LlvmState.h"
+#include "RegisterAliasing.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Error.h"
 #include <vector>
 
 namespace exegesis {
 
 // Common code for all benchmark modes.
 class BenchmarkRunner {
 public:
+  explicit BenchmarkRunner(const LLVMState &State);
+
   // Subtargets can disable running benchmarks for some instructions by
   // returning an error here.
   class InstructionFilter {
   public:
     virtual ~InstructionFilter();
 
     virtual llvm::Error shouldRun(const LLVMState &State,
                                   unsigned Opcode) const {
       return llvm::ErrorSuccess();
     }
   };
 
   virtual ~BenchmarkRunner();
 
-  InstructionBenchmark run(const LLVMState &State, unsigned Opcode,
-                           unsigned NumRepetitions,
-                           const InstructionFilter &Filter) const;
+  InstructionBenchmark run(unsigned Opcode, const InstructionFilter &Filter,
+                           unsigned NumRepetitions);
+
+protected:
+  const LLVMState &State;
+  const llvm::MCInstrInfo &MCInstrInfo;
+  const llvm::MCRegisterInfo &MCRegisterInfo;
 
 private:
   virtual const char *getDisplayName() const = 0;
 
   virtual llvm::Expected<std::vector<llvm::MCInst>>
-  createCode(const LLVMState &State, unsigned OpcodeIndex,
-             unsigned NumRepetitions,
-             const JitFunctionContext &Context) const = 0;
+  createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode,
+                llvm::raw_ostream &Debug) const = 0;
 
   virtual std::vector<BenchmarkMeasure>
-  runMeasurements(const LLVMState &State, const JitFunction &Function,
-                  unsigned NumRepetitions) const = 0;
+  runMeasurements(const ExecutableFunction &EF,
+                  const unsigned NumRepetitions) const = 0;
+
+  llvm::Expected<std::string>
+  writeObjectFile(llvm::ArrayRef<llvm::MCInst> Code) const;
+
+  RegisterAliasingTrackerCache RATC;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H

tools/llvm-exegesis/lib/BenchmarkRunner.cpp

 //===-- BenchmarkRunner.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 "BenchmarkRunner.h"
-#include "InMemoryAssembler.h"
+#include "MCInstrDescView.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
-#include <string>
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Program.h"
 
 namespace exegesis {
 
 BenchmarkRunner::InstructionFilter::~InstructionFilter() = default;
-
+BenchmarkRunner::BenchmarkRunner(const LLVMState &State)
+    : State(State), MCInstrInfo(State.getInstrInfo()),
+      MCRegisterInfo(State.getRegInfo()),
+      RATC(MCRegisterInfo,
+           getFunctionReservedRegs(*State.createTargetMachine())) {}
 BenchmarkRunner::~BenchmarkRunner() = default;
 
-InstructionBenchmark
-BenchmarkRunner::run(const LLVMState &State, const unsigned Opcode,
-                     unsigned NumRepetitions,
-                     const InstructionFilter &Filter) const {
+InstructionBenchmark BenchmarkRunner::run(unsigned Opcode,
+                                          const InstructionFilter &Filter,
+                                          unsigned NumRepetitions) {
   InstructionBenchmark InstrBenchmark;
 
   InstrBenchmark.Key.OpcodeName = State.getInstrInfo().getName(Opcode);
   InstrBenchmark.Key.Mode = getDisplayName();
   InstrBenchmark.CpuName = State.getCpuName();
   InstrBenchmark.LLVMTriple = State.getTriple();
   InstrBenchmark.NumRepetitions = NumRepetitions;
 
   // Ignore instructions that we cannot run.
   if (State.getInstrInfo().get(Opcode).isPseudo()) {
     InstrBenchmark.Error = "Unsupported opcode: isPseudo";
     return InstrBenchmark;
   }
   if (llvm::Error E = Filter.shouldRun(State, Opcode)) {
     InstrBenchmark.Error = llvm::toString(std::move(E));
     return InstrBenchmark;
   }
-
-  JitFunctionContext Context(State.createTargetMachine());
-  auto ExpectedInstructions =
-      createCode(State, Opcode, NumRepetitions, Context);
-  if (llvm::Error E = ExpectedInstructions.takeError()) {
+  llvm::raw_string_ostream InfoStream(InstrBenchmark.Info);
+  llvm::Expected<std::vector<llvm::MCInst>> SnippetOrError =
+      createSnippet(RATC, Opcode, InfoStream);
+  if (llvm::Error E = SnippetOrError.takeError()) {
     InstrBenchmark.Error = llvm::toString(std::move(E));
     return InstrBenchmark;
   }
+  std::vector<llvm::MCInst> &Snippet = SnippetOrError.get();
+  if (Snippet.empty()) {
+    InstrBenchmark.Error = "Empty snippet";
+    return InstrBenchmark;
+  }
 
-  const std::vector<llvm::MCInst> Instructions = *ExpectedInstructions;
-  const JitFunction Function(std::move(Context), Instructions);
-  const llvm::StringRef CodeBytes = Function.getFunctionBytes();
-
-  std::string AsmExcerpt;
-  constexpr const int ExcerptSize = 100;
-  constexpr const int ExcerptTailSize = 10;
-  if (CodeBytes.size() <= ExcerptSize) {
-    AsmExcerpt = llvm::toHex(CodeBytes);
-  } else {
-    AsmExcerpt =
-        llvm::toHex(CodeBytes.take_front(ExcerptSize - ExcerptTailSize + 3));
-    AsmExcerpt += "...";
-    AsmExcerpt += llvm::toHex(CodeBytes.take_back(ExcerptTailSize));
+  InfoStream << "Snippet:\n";
+  for (const auto &MCInst : Snippet) {
+    DumpMCInst(MCRegisterInfo, MCInstrInfo, MCInst, InfoStream);
+    InfoStream << "\n";
   }
-  llvm::outs() << "# Asm excerpt: " << AsmExcerpt << "\n";
-  llvm::outs().flush(); // In case we crash.
 
-  InstrBenchmark.Measurements =
-      runMeasurements(State, Function, NumRepetitions);
+  std::vector<llvm::MCInst> Code;
+  for (int I = 0; I < InstrBenchmark.NumRepetitions; ++I)
+    Code.push_back(Snippet[I % Snippet.size()]);
+
+  auto ExpectedObjectPath = writeObjectFile(Code);
+  if (llvm::Error E = ExpectedObjectPath.takeError()) {
+    InstrBenchmark.Error = llvm::toString(std::move(E));
     return InstrBenchmark;
   }
 
+  // FIXME: Check if TargetMachine or ExecutionEngine can be reused instead of
+  // creating one everytime.
+  const ExecutableFunction EF(State.createTargetMachine(),
+                              getObjectFromFile(*ExpectedObjectPath));
+  InstrBenchmark.Measurements = runMeasurements(EF, NumRepetitions);
+
+  return InstrBenchmark;
+}
+
+llvm::Expected<std::string>
+BenchmarkRunner::writeObjectFile(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.createTargetMachine(), Code, OFS);
+  llvm::outs() << "Check generated assembly with: /usr/bin/objdump -d "
+               << ResultPath << "\n";
+  return ResultPath.str();
+}
+
 } // namespace exegesis

tools/llvm-exegesis/lib/CMakeLists.txt

 add_library(LLVMExegesis
   STATIC
   Analysis.cpp
+  Assembler.cpp
   BenchmarkResult.cpp
   BenchmarkRunner.cpp
   Clustering.cpp
-  InMemoryAssembler.cpp
-  InstructionSnippetGenerator.cpp
   Latency.cpp
   LlvmState.cpp
-  OperandGraph.cpp
+  MCInstrDescView.cpp
   PerfHelper.cpp
+  RegisterAliasing.cpp
   Uops.cpp
   X86.cpp
   )
 
 llvm_update_compile_flags(LLVMExegesis)
 llvm_map_components_to_libnames(libs
   Analysis
   CodeGen

tools/llvm-exegesis/lib/InMemoryAssembler.h

-//===-- InMemoryAssembler.h -------------------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// Defines classes to assemble functions composed of a single basic block of
-/// MCInsts.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H
-#define LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H
-
-#include "llvm/ADT/BitVector.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/CodeGen/MachineModuleInfo.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/ExecutionEngine/ExecutionEngine.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/MC/MCInst.h"
-#include <cstdint>
-#include <memory>
-#include <vector>
-
-namespace exegesis {
-
-// Consumable context for JitFunction below.
-// This temporary object allows for retrieving MachineFunction properties before
-// assembling it.
-class JitFunctionContext {
-public:
-  explicit JitFunctionContext(std::unique_ptr<llvm::LLVMTargetMachine> TM);
-  // Movable
-  JitFunctionContext(JitFunctionContext &&) = default;
-  JitFunctionContext &operator=(JitFunctionContext &&) = default;
-  // Non copyable
-  JitFunctionContext(const JitFunctionContext &) = delete;
-  JitFunctionContext &operator=(const JitFunctionContext &) = delete;
-
-  const llvm::BitVector &getReservedRegs() const { return ReservedRegs; }
-
-private:
-  friend class JitFunction;
-
-  std::unique_ptr<llvm::LLVMContext> Context;
-  std::unique_ptr<llvm::LLVMTargetMachine> TM;
-  std::unique_ptr<llvm::MachineModuleInfo> MMI;
-  std::unique_ptr<llvm::Module> Module;
-  llvm::MachineFunction *MF = nullptr;
-  llvm::BitVector ReservedRegs;
-};
-
-// Creates a void() function from a sequence of llvm::MCInst.
-class JitFunction {
-public:
-  // Assembles Instructions into an executable function.
-  JitFunction(JitFunctionContext &&Context,
-              llvm::ArrayRef<llvm::MCInst> Instructions);
-
-  // Retrieves the function as an array of bytes.
-  llvm::StringRef getFunctionBytes() const { return FunctionBytes; }
-
-  // Retrieves the callable function.
-  void operator()() const {
-    char* const FnData = const_cast<char*>(FunctionBytes.data());
-    ((void (*)())(intptr_t)FnData)();
-  }
-
-private:
-  JitFunctionContext FunctionContext;
-  std::unique_ptr<llvm::ExecutionEngine> ExecEngine;
-  llvm::StringRef FunctionBytes;
-};
-
-} // namespace exegesis
-
-#endif // LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H

tools/llvm-exegesis/lib/InstructionSnippetGenerator.h

-//===-- InstructionSnippetGenerator.h ---------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// Defines helper classes to generate code snippets, in particular register
-/// assignment.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H
-#define LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H
-
-#include "OperandGraph.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/MC/MCInst.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include <vector>
-
-namespace exegesis {
-
-// A Variable represents a set of possible values that we need to choose from.
-// It may represent one or more explicit operands that are tied together, or one
-// implicit operand.
-class Variable final {
-public:
-  bool IsUse = false;
-  bool IsDef = false;
-  bool IsReg = false;
-
-  // Lists all the explicit operand indices that are tied to this variable.
-  // Empty if Variable represents an implicit operand.
-  llvm::SmallVector<size_t, 8> ExplicitOperands;
-
-  // - In case of explicit operands, PossibleRegisters is the expansion of the
-  // operands's RegClass registers. Please note that tied together explicit
-  // operands share the same RegClass.
-  // - In case of implicit operands, PossibleRegisters is a singleton MCPhysReg.
-  llvm::SmallSetVector<llvm::MCPhysReg, 16> PossibleRegisters;
-
-  // If RegInfo is null, register names won't get resolved.
-  void print(llvm::raw_ostream &OS, const llvm::MCRegisterInfo *RegInfo) const;
-};
-
-// Builds a model of implicit and explicit operands for InstrDesc into
-// Variables.
-llvm::SmallVector<Variable, 8>
-getVariables(const llvm::MCRegisterInfo &RegInfo,
-             const llvm::MCInstrDesc &InstrDesc,
-             const llvm::BitVector &ReservedRegs);
-
-// A simple object to represent a Variable assignement.
-struct VariableAssignment {
-  VariableAssignment(size_t VarIdx, llvm::MCPhysReg AssignedReg);
-
-  size_t VarIdx;
-  llvm::MCPhysReg AssignedReg;
-
-  bool operator==(const VariableAssignment &) const;
-  bool operator<(const VariableAssignment &) const;
-};
-
-// An AssignmentChain is a set of assignement realizing a dependency chain.
-// We inherit from std::set to leverage uniqueness of elements.
-using AssignmentChain = std::set<VariableAssignment>;
-
-// Debug function to print an assignment chain.
-void dumpAssignmentChain(const llvm::MCRegisterInfo &RegInfo,
-                         const AssignmentChain &Chain);
-
-// Inserts Variables into a graph representing register aliasing and finds all
-// the possible dependency chains for this instruction, i.e. all the possible
-// assignement of operands that would make execution of the instruction
-// sequential.
-std::vector<AssignmentChain>
-computeSequentialAssignmentChains(const llvm::MCRegisterInfo &RegInfo,
-                                  llvm::ArrayRef<Variable> Vars);
-
-// Selects a random configuration leading to a dependency chain.
-// The result is a vector of the same size as `Vars`.
-// `random_index_for_size` is a functor giving a random value in [0, arg[.
-std::vector<llvm::MCPhysReg>
-getRandomAssignment(llvm::ArrayRef<Variable> Vars,
-                    llvm::ArrayRef<AssignmentChain> Chains,
-                    const std::function<size_t(size_t)> &RandomIndexForSize);
-
-// Finds an assignment of registers to variables such that no two variables are
-// assigned the same register.
-// The result is a vector of the same size as `Vars`, or `{}` if the
-// assignment is not feasible.
-std::vector<llvm::MCPhysReg>
-getExclusiveAssignment(llvm::ArrayRef<Variable> Vars);
-
-// Finds a greedy assignment of registers to variables. Each variable gets
-// assigned the first possible register that is not already assigned to a
-// previous variable. If there is no such register, the variable gets assigned
-// the first possible register.
-// The result is a vector of the same size as `Vars`, or `{}` if the
-// assignment is not feasible.
-std::vector<llvm::MCPhysReg>
-getGreedyAssignment(llvm::ArrayRef<Variable> Vars);
-
-// Generates an LLVM MCInst with the previously computed variables.
-// Immediate values are set to 1.
-llvm::MCInst generateMCInst(const llvm::MCInstrDesc &InstrDesc,
-                            llvm::ArrayRef<Variable> Vars,
-                            llvm::ArrayRef<llvm::MCPhysReg> VarRegs);
-
-} // namespace exegesis
-
-#endif // LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H

tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp

-//===-- InstructionSnippetGenerator.cpp -------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "InstructionSnippetGenerator.h"
-#include "llvm/ADT/MapVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/MC/MCInstBuilder.h"
-#include <algorithm>
-#include <unordered_map>
-#include <unordered_set>
-
-namespace exegesis {
-
-void Variable::print(llvm::raw_ostream &OS,
-                     const llvm::MCRegisterInfo *RegInfo) const {
-  OS << "IsUse=" << IsUse << " IsDef=" << IsDef << " possible regs: {";
-  for (const size_t Reg : PossibleRegisters) {
-    if (RegInfo)
-      OS << RegInfo->getName(Reg);
-    else
-      OS << Reg;
-    OS << ",";
-  }
-  OS << "} ";
-  if (ExplicitOperands.empty()) {
-    OS << "implicit";
-  } else {
-    OS << "explicit ops: {";
-    for (const size_t Op : ExplicitOperands)
-      OS << Op << ",";
-    OS << "}";
-  }
-  OS << "\n";
-}
-
-// Update the state of a Variable with an explicit operand.
-static void updateExplicitOperandVariable(const llvm::MCRegisterInfo &RegInfo,
-                                          const llvm::MCInstrDesc &InstrInfo,
-                                          const size_t OpIndex,
-                                          const llvm::BitVector &ReservedRegs,
-                                          Variable &Var) {
-  const bool IsDef = OpIndex < InstrInfo.getNumDefs();
-  if (IsDef)
-    Var.IsDef = true;
-  if (!IsDef)
-    Var.IsUse = true;
-  Var.ExplicitOperands.push_back(OpIndex);
-  const llvm::MCOperandInfo &OpInfo = InstrInfo.opInfo_begin()[OpIndex];
-  if (OpInfo.RegClass >= 0) {
-    Var.IsReg = true;
-    for (const llvm::MCPhysReg &Reg : RegInfo.getRegClass(OpInfo.RegClass)) {
-      if (!ReservedRegs[Reg])
-        Var.PossibleRegisters.insert(Reg);
-    }
-  }
-}
-
-static Variable &findVariableWithOperand(llvm::SmallVector<Variable, 8> &Vars,
-                                         size_t OpIndex) {
-  // Vars.size() is small (<10) so a linear scan is good enough.
-  for (Variable &Var : Vars) {
-    if (llvm::is_contained(Var.ExplicitOperands, OpIndex))
-      return Var;
-  }
-  assert(false && "Illegal state");
-  static Variable *const EmptyVariable = new Variable();
-  return *EmptyVariable;
-}
-
-llvm::SmallVector<Variable, 8>
-getVariables(const llvm::MCRegisterInfo &RegInfo,
-             const llvm::MCInstrDesc &InstrInfo,
-             const llvm::BitVector &ReservedRegs) {
-  llvm::SmallVector<Variable, 8> Vars;
-  // For each operand, its "tied to" operand or -1.
-  llvm::SmallVector<int, 10> TiedToMap;
-  for (size_t I = 0, E = InstrInfo.getNumOperands(); I < E; ++I) {
-    TiedToMap.push_back(InstrInfo.getOperandConstraint(I, llvm::MCOI::TIED_TO));
-  }
-  // Adding non tied operands.
-  for (size_t I = 0, E = InstrInfo.getNumOperands(); I < E; ++I) {
-    if (TiedToMap[I] >= 0)
-      continue; // dropping tied ones.
-    Vars.emplace_back();
-    updateExplicitOperandVariable(RegInfo, InstrInfo, I, ReservedRegs,
-                                  Vars.back());
-  }
-  // Adding tied operands to existing variables.
-  for (size_t I = 0, E = InstrInfo.getNumOperands(); I < E; ++I) {
-    if (TiedToMap[I] < 0)
-      continue; // dropping non-tied ones.
-    updateExplicitOperandVariable(RegInfo, InstrInfo, I, ReservedRegs,
-                                  findVariableWithOperand(Vars, TiedToMap[I]));
-  }
-  // Adding implicit defs.
-  for (size_t I = 0, E = InstrInfo.getNumImplicitDefs(); I < E; ++I) {
-    Vars.emplace_back();
-    Variable &Var = Vars.back();
-    const llvm::MCPhysReg Reg = InstrInfo.getImplicitDefs()[I];
-    assert(!ReservedRegs[Reg] && "implicit def of reserved register");
-    Var.PossibleRegisters.insert(Reg);
-    Var.IsDef = true;
-    Var.IsReg = true;
-  }
-  // Adding implicit uses.
-  for (size_t I = 0, E = InstrInfo.getNumImplicitUses(); I < E; ++I) {
-    Vars.emplace_back();
-    Variable &Var = Vars.back();
-    const llvm::MCPhysReg Reg = InstrInfo.getImplicitUses()[I];
-    assert(!ReservedRegs[Reg] && "implicit use of reserved register");
-    Var.PossibleRegisters.insert(Reg);
-    Var.IsUse = true;
-    Var.IsReg = true;
-  }
-
-  return Vars;
-}
-
-VariableAssignment::VariableAssignment(size_t VarIdx,
-                                       llvm::MCPhysReg AssignedReg)
-    : VarIdx(VarIdx), AssignedReg(AssignedReg) {}
-
-bool VariableAssignment::operator==(const VariableAssignment &Other) const {
-  return std::tie(VarIdx, AssignedReg) ==
-         std::tie(Other.VarIdx, Other.AssignedReg);
-}
-
-bool VariableAssignment::operator<(const VariableAssignment &Other) const {
-  return std::tie(VarIdx, AssignedReg) <
-         std::tie(Other.VarIdx, Other.AssignedReg);
-}
-
-void dumpAssignmentChain(const llvm::MCRegisterInfo &RegInfo,
-                         const AssignmentChain &Chain) {
-  for (const VariableAssignment &Assignment : Chain) {
-    llvm::outs() << llvm::format("(%d %s) ", Assignment.VarIdx,
-                                 RegInfo.getName(Assignment.AssignedReg));
-  }
-  llvm::outs() << "\n";
-}
-
-std::vector<AssignmentChain>
-computeSequentialAssignmentChains(const llvm::MCRegisterInfo &RegInfo,
-                                  llvm::ArrayRef<Variable> Vars) {
-  using graph::Node;
-  graph::Graph Graph;
-
-  // Add register aliasing to the graph.
-  setupRegisterAliasing(RegInfo, Graph);
-
-  // Adding variables to the graph.
-  for (size_t I = 0, E = Vars.size(); I < E; ++I) {
-    const Variable &Var = Vars[I];
-    const Node N = Node::Var(I);
-    if (Var.IsDef) {
-      Graph.connect(Node::In(), N);
-      for (const size_t Reg : Var.PossibleRegisters)
-        Graph.connect(N, Node::Reg(Reg));
-    }
-    if (Var.IsUse) {
-      Graph.connect(N, Node::Out());
-      for (const size_t Reg : Var.PossibleRegisters)
-        Graph.connect(Node::Reg(Reg), N);
-    }
-  }
-
-  // Find all possible dependency chains (aka all possible paths from In to Out
-  // node).
-  std::vector<AssignmentChain> AllChains;
-  for (;;) {
-    const auto Path = Graph.getPathFrom(Node::In(), Node::Out());
-    if (Path.empty())
-      break;
-    switch (Path.size()) {
-    case 0:
-    case 1:
-    case 2:
-    case 4:
-      assert(false && "Illegal state");
-      break;
-    case 3: { // IN -> variable -> OUT
-      const size_t VarIdx = Path[1].varValue();
-      for (size_t Reg : Vars[VarIdx].PossibleRegisters) {
-        AllChains.emplace_back();
-        AllChains.back().emplace(VarIdx, Reg);
-      }
-      Graph.disconnect(Path[0], Path[1]); // IN -> variable
-      Graph.disconnect(Path[1], Path[2]); // variable -> OUT
-      break;
-    }
-    default: { // IN -> var1 -> Reg[...] -> var2 -> OUT
-      const size_t Last = Path.size() - 1;
-      const size_t Var1 = Path[1].varValue();
-      const llvm::MCPhysReg Reg1 = Path[2].regValue();
-      const llvm::MCPhysReg Reg2 = Path[Last - 2].regValue();
-      const size_t Var2 = Path[Last - 1].varValue();
-      AllChains.emplace_back();
-      AllChains.back().emplace(Var1, Reg1);
-      AllChains.back().emplace(Var2, Reg2);
-      Graph.disconnect(Path[1], Path[2]); // Var1 -> Reg[0]
-      break;
-    }
-    }
-  }
-
-  return AllChains;
-}
-
-std::vector<llvm::MCPhysReg>
-getRandomAssignment(llvm::ArrayRef<Variable> Vars,
-                    llvm::ArrayRef<AssignmentChain> Chains,
-                    const std::function<size_t(size_t)> &RandomIndexForSize) {
-  // Registers are initialized with 0 (aka NoRegister).
-  std::vector<llvm::MCPhysReg> Registers(Vars.size(), 0);
-  if (Chains.empty())
-    return Registers;
-  // Pick one of the chains and set Registers that are fully constrained (have
-  // no degrees of freedom).
-  const size_t ChainIndex = RandomIndexForSize(Chains.size());
-  for (const VariableAssignment Assignment : Chains[ChainIndex])
-    Registers[Assignment.VarIdx] = Assignment.AssignedReg;
-  // Registers with remaining degrees of freedom are assigned randomly.
-  for (size_t I = 0, E = Vars.size(); I < E; ++I) {
-    llvm::MCPhysReg &Reg = Registers[I];
-    const Variable &Var = Vars[I];
-    const auto &PossibleRegisters = Var.PossibleRegisters;
-    if (Reg > 0 || PossibleRegisters.empty())
-      continue;
-    Reg = PossibleRegisters[RandomIndexForSize(PossibleRegisters.size())];
-  }
-  return Registers;
-}
-
-// Finds a matching register `reg` for variable `VarIdx` and sets
-// `RegAssignments[r]` to `VarIdx`. Returns false if no matching can be found.
-// `seen.count(r)` is 1 if register `reg` has been processed.
-static bool findMatchingRegister(
-    llvm::ArrayRef<Variable> Vars, const size_t VarIdx,
-    std::unordered_set<llvm::MCPhysReg> &Seen,
-    std::unordered_map<llvm::MCPhysReg, size_t> &RegAssignments) {
-  for (const llvm::MCPhysReg Reg : Vars[VarIdx].PossibleRegisters) {
-    if (!Seen.count(Reg)) {
-      Seen.insert(Reg); // Mark `Reg` as seen.
-      // If `Reg` is not assigned to a variable, or if `Reg` was assigned to a
-      // variable which has an alternate possible register, assign `Reg` to
-      // variable `VarIdx`. Since `Reg` is marked as assigned in the above line,
-      // `RegAssignments[r]` in the following recursive call will not get
-      // assigned `Reg` again.
-      const auto AssignedVarIt = RegAssignments.find(Reg);
-      if (AssignedVarIt == RegAssignments.end() ||
-          findMatchingRegister(Vars, AssignedVarIt->second, Seen,
-                               RegAssignments)) {
-        RegAssignments[Reg] = VarIdx;
-        return true;
-      }
-    }
-  }
-  return false;
-}
-
-// This is actually a maximum bipartite matching problem:
-//   https://en.wikipedia.org/wiki/Matching_(graph_theory)#Bipartite_matching
-// The graph has variables on the left and registers on the right, with an edge
-// between variable `I` and register `Reg` iff
-// `Vars[I].PossibleRegisters.count(A)`.
-// Note that a greedy approach won't work for cases like:
-//   Vars[0] PossibleRegisters={C,B}
-//   Vars[1] PossibleRegisters={A,B}
-//   Vars[2] PossibleRegisters={A,C}
-// There is a feasible solution {0->B, 1->A, 2->C}, but the greedy solution is
-// {0->C, 1->A, oops}.
-std::vector<llvm::MCPhysReg>
-getExclusiveAssignment(llvm::ArrayRef<Variable> Vars) {
-  // `RegAssignments[r]` is the variable id that was assigned register `Reg`.
-  std::unordered_map<llvm::MCPhysReg, size_t> RegAssignments;
-
-  for (size_t VarIdx = 0, E = Vars.size(); VarIdx < E; ++VarIdx) {
-    if (!Vars[VarIdx].IsReg)
-      continue;
-    std::unordered_set<llvm::MCPhysReg> Seen;
-    if (!findMatchingRegister(Vars, VarIdx, Seen, RegAssignments))
-      return {}; // Infeasible.
-  }
-
-  std::vector<llvm::MCPhysReg> Registers(Vars.size(), 0);
-  for (const auto &RegVarIdx : RegAssignments)
-    Registers[RegVarIdx.second] = RegVarIdx.first;
-  return Registers;
-}
-
-std::vector<llvm::MCPhysReg>
-getGreedyAssignment(llvm::ArrayRef<Variable> Vars) {
-  std::vector<llvm::MCPhysReg> Registers(Vars.size(), 0);
-  llvm::SmallSet<llvm::MCPhysReg, 8> Assigned;
-  for (size_t VarIdx = 0, E = Vars.size(); VarIdx < E; ++VarIdx) {
-    const auto &Var = Vars[VarIdx];
-    if (!Var.IsReg)
-      continue;
-    if (Var.PossibleRegisters.empty())
-      return {};
-    // Try possible registers until an unassigned one is found.
-    for (const auto Reg : Var.PossibleRegisters) {
-      if (Assigned.insert(Reg).second) {
-        Registers[VarIdx] = Reg;
-        break;
-      }
-    }
-    // Fallback to first possible register.
-    if (Registers[VarIdx] == 0)
-      Registers[VarIdx] = Var.PossibleRegisters[0];
-  }
-  return Registers;
-}
-
-llvm::MCInst generateMCInst(const llvm::MCInstrDesc &InstrInfo,
-                            llvm::ArrayRef<Variable> Vars,
-                            llvm::ArrayRef<llvm::MCPhysReg> VarRegs) {
-  const size_t NumOperands = InstrInfo.getNumOperands();
-  llvm::SmallVector<llvm::MCPhysReg, 16> OperandToRegister(NumOperands, 0);
-
-  // We browse the variable and for each explicit operands we set the selected
-  // register in the OperandToRegister array.
-  for (size_t I = 0, E = Vars.size(); I < E; ++I) {
-    for (const size_t OpIndex : Vars[I].ExplicitOperands) {
-      OperandToRegister[OpIndex] = VarRegs[I];
-    }
-  }
-
-  // Building the instruction.
-  llvm::MCInstBuilder Builder(InstrInfo.getOpcode());
-  for (size_t I = 0, E = InstrInfo.getNumOperands(); I < E; ++I) {
-    const llvm::MCOperandInfo &OpInfo = InstrInfo.opInfo_begin()[I];
-    switch (OpInfo.OperandType) {
-    case llvm::MCOI::OperandType::OPERAND_REGISTER:
-      Builder.addReg(OperandToRegister[I]);
-      break;
-    case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
-      Builder.addImm(1);
-      break;
-    default:
-      Builder.addOperand(llvm::MCOperand());
-    }
-  }
-
-  return Builder;
-}
-
-} // namespace exegesis

tools/llvm-exegesis/lib/Latency.h

 #define LLVM_TOOLS_LLVM_EXEGESIS_LATENCY_H
 
 #include "BenchmarkRunner.h"
 
 namespace exegesis {
 
 class LatencyBenchmarkRunner : public BenchmarkRunner {
 public:
+  using BenchmarkRunner::BenchmarkRunner;
   ~LatencyBenchmarkRunner() override;
 
 private:
   const char *getDisplayName() const override;
 
   llvm::Expected<std::vector<llvm::MCInst>>
-  createCode(const LLVMState &State, unsigned OpcodeIndex,
-             unsigned NumRepetitions,
-             const JitFunctionContext &Context) const override;
+  createSnippet(RegisterAliasingTrackerCache &RATC, unsigned OpcodeIndex,
+                llvm::raw_ostream &Info) const override;
 
   std::vector<BenchmarkMeasure>
-  runMeasurements(const LLVMState &State, const JitFunction &Function,
-                  unsigned NumRepetitions) const override;
+  runMeasurements(const ExecutableFunction &EF,
+                  const unsigned NumRepetitions) const override;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_LATENCY_H

tools/llvm-exegesis/lib/Latency.cpp

 //===-- Latency.cpp ---------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Latency.h"
-#include "BenchmarkResult.h"
-#include "InstructionSnippetGenerator.h"
+
+#include "Assembler.h"
+#include "BenchmarkRunner.h"
+#include "MCInstrDescView.h"
 #include "PerfHelper.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/Support/Error.h"
-#include <algorithm>
-#include <random>
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstBuilder.h"
 
 namespace exegesis {
 
+static bool HasUnknownOperand(const llvm::MCOperandInfo &OpInfo) {
+  return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN;
+}
+
 // FIXME: Handle memory, see PR36905.
-static bool isInvalidOperand(const llvm::MCOperandInfo &OpInfo) {
-  switch (OpInfo.OperandType) {
-  default:
+static bool HasMemoryOperand(const llvm::MCOperandInfo &OpInfo) {
+  return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY;
+}
+
+static bool IsInfeasible(const Instruction &Instruction, std::string &Error) {
+  const auto &MCInstrDesc = Instruction.Description;
+  if (MCInstrDesc.isPseudo()) {
+    Error = "is pseudo";
     return true;
-  case llvm::MCOI::OPERAND_IMMEDIATE:
-  case llvm::MCOI::OPERAND_REGISTER:
-    return false;
   }
+  if (llvm::any_of(MCInstrDesc.operands(), HasUnknownOperand)) {
+    Error = "has unknown operands";
+    return true;
+  }
+  if (llvm::any_of(MCInstrDesc.operands(), HasMemoryOperand)) {
+    Error = "has memory operands";
+    return true;
+  }
+  return false;
 }
 
 static llvm::Error makeError(llvm::Twine Msg) {
   return llvm::make_error<llvm::StringError>(Msg,
                                              llvm::inconvertibleErrorCode());
 }
 
 LatencyBenchmarkRunner::~LatencyBenchmarkRunner() = default;
 
 const char *LatencyBenchmarkRunner::getDisplayName() const { return "latency"; }
 
-llvm::Expected<std::vector<llvm::MCInst>> LatencyBenchmarkRunner::createCode(
-    const LLVMState &State, const unsigned OpcodeIndex,
-    const unsigned NumRepetitions, const JitFunctionContext &Context) const {
-  std::default_random_engine RandomEngine;
-  const auto GetRandomIndex = [&RandomEngine](size_t Size) {
-    assert(Size > 0 && "trying to get select a random element of an empty set");
-    return std::uniform_int_distribution<>(0, Size - 1)(RandomEngine);
-  };
-
-  const auto &InstrInfo = State.getInstrInfo();
-  const auto &RegInfo = State.getRegInfo();
-  const llvm::MCInstrDesc &InstrDesc = InstrInfo.get(OpcodeIndex);
-  for (const llvm::MCOperandInfo &OpInfo : InstrDesc.operands()) {
-    if (isInvalidOperand(OpInfo))
-      return makeError("Only registers and immediates are supported");
-  }
-
-  const auto Vars = getVariables(RegInfo, InstrDesc, Context.getReservedRegs());
-  const std::vector<AssignmentChain> AssignmentChains =
-      computeSequentialAssignmentChains(RegInfo, Vars);
-  if (AssignmentChains.empty())
-    return makeError("Unable to find a dependency chain.");
-  const std::vector<llvm::MCPhysReg> Regs =
-      getRandomAssignment(Vars, AssignmentChains, GetRandomIndex);
-  const llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs);
-  if (!State.canAssemble(Inst))
-    return makeError("MCInst does not assemble.");
-  return std::vector<llvm::MCInst>(NumRepetitions, Inst);
+llvm::Expected<std::vector<llvm::MCInst>>
+LatencyBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC,
+                                      unsigned Opcode,
+                                      llvm::raw_ostream &Info) const {
+  std::vector<llvm::MCInst> Snippet;
+  const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode);
+  const Instruction ThisInstruction(MCInstrDesc, RATC);
+
+  std::string Error;
+  if (IsInfeasible(ThisInstruction, Error))
+    return makeError(llvm::Twine("Infeasible : ").concat(Error));
+
+  const AliasingConfigurations SelfAliasing(ThisInstruction, ThisInstruction);
+  if (!SelfAliasing.empty()) {
+    if (!SelfAliasing.hasImplicitAliasing()) {
+      Info << "explicit self cycles, selecting one aliasing configuration.\n";
+      setRandomAliasing(SelfAliasing);
+    } else {
+      Info << "implicit Self cycles, picking random values.\n";
+    }
+    Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction));
+    return Snippet;
+  }
+
+  // Let's try to create a dependency through another opcode.
+  std::vector<unsigned> Opcodes;
+  Opcodes.resize(MCInstrInfo.getNumOpcodes());
+  std::iota(Opcodes.begin(), Opcodes.end(), 0U);
+  std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator());
+  for (const unsigned OtherOpcode : Opcodes) {
+    clearVariableAssignments(ThisInstruction);
+    if (OtherOpcode == Opcode)
+      continue;
+    const Instruction OtherInstruction(MCInstrInfo.get(OtherOpcode), RATC);
+    if (IsInfeasible(OtherInstruction, Error))
+      continue;
+    const AliasingConfigurations Forward(ThisInstruction, OtherInstruction);
+    const AliasingConfigurations Back(OtherInstruction, ThisInstruction);
+    if (Forward.empty() || Back.empty())
+      continue;
+    setRandomAliasing(Forward);
+    setRandomAliasing(Back);
+    Info << "creating cycle through " << MCInstrInfo.getName(OtherOpcode)
+         << ".\n";
+    Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction));
+    Snippet.push_back(randomizeUnsetVariablesAndBuild(OtherInstruction));
+    return Snippet;
+  }
+
+  return makeError(
+      "Infeasible : Didn't find any scheme to make the instruction serial\n");
 }
 
 std::vector<BenchmarkMeasure>
-LatencyBenchmarkRunner::runMeasurements(const LLVMState &State,
-                                        const JitFunction &Function,
+LatencyBenchmarkRunner::runMeasurements(const ExecutableFunction &Function,
                                         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 = State.getSubtargetInfo()
                                 .getSchedModel()
                                 .getExtraProcessorInfo()

tools/llvm-exegesis/lib/LlvmState.h

 //===-- LlvmState.h ---------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+///
+/// \file
+/// A class to set up and access common LLVM objects.
+///
+//===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_LLVMSTATE_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_LLVMSTATE_H
 
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/MC/MCRegisterInfo.h"

tools/llvm-exegesis/lib/MCInstrDescView.h

+//===-- MCInstrDescView.h ---------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Provide views around LLVM structures to represents an instruction instance,
+/// as well as its implicit and explicit arguments in a uniform way.
+/// Arguments that are explicit and independant (non tied) also have a Variable
+/// associated to them so the instruction can be fully defined by reading its
+/// Variables.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H
+
+#include <random>
+
+#include "RegisterAliasing.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+
+namespace exegesis {
+
+struct Operand; // forward declaration.
+
+// A variable represents the value of an Operand or a set of Operands if they ar
+// tied together.
+struct Variable {
+  llvm::SmallVector<const Operand *, 2> TiedOperands;
+  llvm::MCOperand AssignedValue;
+};
+
+// MCOperandInfo can only represents Explicit operands. This object gives a
+// uniform view of Implicit and Explicit Operands.
+//
+// - Index: can be used to refer to MCInstrDesc::operands for Explicit operands.
+// - Tracker: is set for Register Operands and is used to keep track of possible
+// registers and the registers reachable from them (aliasing registers).
+// - Info: a shortcut for MCInstrDesc::operands()[Index].
+// - TiedTo: a pointer to the Operand holding the value or nullptr.
+// - ImplicitReg: a pointer to the register value when Operand is Implicit,
+// nullptr otherwise.
+// - Variable: The value associated with this Operand. It is only set for
+// explicit operands that are not TiedTo.
+struct Operand {
+  uint8_t Index = 0;
+  bool IsDef = false;
+  bool IsExplicit = false;
+  const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op.
+  const llvm::MCOperandInfo *Info = nullptr;        // Set for Explicit Op.
+  const Operand *TiedTo = nullptr;                  // Set for Reg/Explicit Op.
+  const llvm::MCPhysReg *ImplicitReg = nullptr;     // Set for Implicit Op.
+  mutable llvm::Optional<Variable> Var;             // Set for Explicit Op.
+};
+
+// A view over an MCInstrDesc offering a convenient interface to compute
+// Register aliasing and assign values to Operands.
+struct Instruction {
+  Instruction(const llvm::MCInstrDesc &MCInstrDesc,
+              RegisterAliasingTrackerCache &ATC);
+
+  const llvm::MCInstrDesc &Description;
+  llvm::SmallVector<Operand, 8> Operands;
+  llvm::SmallVector<Variable *, 8> Variables;
+  llvm::BitVector DefRegisters; // The union of the aliased def registers.
+  llvm::BitVector UseRegisters; // The union of the aliased use registers.
+};
+
+// Represents the assignment of a Register to an Operand.
+struct RegisterOperandAssignment {
+  RegisterOperandAssignment(const Operand *Operand, llvm::MCPhysReg Reg)
+      : Op(Operand), Reg(Reg) {}
+
+  const Operand *Op; // Pointer to an Explicit Register Operand.
+  llvm::MCPhysReg Reg;
+
+  bool operator==(const RegisterOperandAssignment &other) const;
+};
+
+// Represents a set of Operands that would alias through the use of some
+// Registers.
+// There are two reasons why operands would alias:
+// - The registers assigned to each of the operands are the same or alias each
+//   other (e.g. AX/AL)
+// - The operands are tied.
+struct AliasingRegisterOperands {
+  llvm::SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1.
+  llvm::SmallVector<RegisterOperandAssignment, 2> Uses;
+
+  // True is Defs and Use contain an Implicit Operand.
+  bool hasImplicitAliasing() const;
+
+  bool operator==(const AliasingRegisterOperands &other) const;
+};
+
+// Returns all possible configurations leading Def registers of DefInstruction
+// to alias with Use registers of UseInstruction.
+struct AliasingConfigurations {
+  AliasingConfigurations(const Instruction &DefInstruction,
+                         const Instruction &UseInstruction);
+
+  bool empty() const; // True if no aliasing configuration is found.
+  bool hasImplicitAliasing() const;
+  void setExplicitAliasing() const;
+
+  const Instruction &DefInstruction;
+  const Instruction &UseInstruction;
+  llvm::SmallVector<AliasingRegisterOperands, 32> Configurations;
+};
+
+// A global Random Number Generator to randomize configurations.
+// FIXME: Move random number generation into an object and make it seedable for
+// unit tests.
+std::mt19937 &randomGenerator();
+
+// Picks a random bit among the bits set in Vector and returns its index.
+// Precondition: Vector must have at least one bit set.
+size_t randomBit(const llvm::BitVector &Vector);
+
+// Picks a random configuration, then select a random def and a random use from
+// it and set the target Variables to the selected values.
+// FIXME: This function mutates some nested variables in a const object, please
+// fix ASAP.
+void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations);
+
+// Set all Instruction's Variables AssignedValue to Invalid.
+void clearVariableAssignments(const Instruction &Instruction);
+
+// Assigns a Random Value to all Instruction's Variables that are still Invalid.
+llvm::MCInst randomizeUnsetVariablesAndBuild(const Instruction &Instruction);
+
+// Writes MCInst to OS.
+// This is not assembly but the internal LLVM's name for instructions and
+// registers.
+void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo,
+                const llvm::MCInstrInfo &MCInstrInfo,
+                const llvm::MCInst &MCInst, llvm::raw_ostream &OS);
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H

tools/llvm-exegesis/lib/MCInstrDescView.cpp

+//===-- MCInstrDescView.cpp -------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MCInstrDescView.h"
+
+#include <iterator>
+#include <map>
+#include <tuple>
+
+#include "llvm/ADT/STLExtras.h"
+
+namespace exegesis {
+
+static void tie(const Operand *FromOperand, llvm::Optional<Variable> &Var) {
+  if (!Var)
+    Var.emplace();
+  Var->TiedOperands.push_back(FromOperand);
+}
+
+Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
+                         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.IsExplicit = true;
+    // TODO(gchatelet): Handle isLookupPtrRegClass.
+    if (OpInfo.RegClass >= 0)
+      Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass);
+    Operand.Info = &OpInfo;
+    Operands.push_back(Operand);
+  }
+  for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitDefs();
+       MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
+    Operand Operand;
+    Operand.Index = OpIndex;
+    Operand.IsDef = true;
+    Operand.IsExplicit = false;
+    Operand.Tracker = &RATC.getRegister(*MCPhysReg);
+    Operand.ImplicitReg = MCPhysReg;
+    Operands.push_back(Operand);
+  }
+  for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitUses();
+       MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) {
+    Operand Operand;
+    Operand.Index = OpIndex;
+    Operand.IsDef = false;
+    Operand.IsExplicit = false;
+    Operand.Tracker = &RATC.getRegister(*MCPhysReg);
+    Operand.ImplicitReg = MCPhysReg;
+    Operands.push_back(Operand);
+  }
+  // Set TiedTo for operands.
+  for (auto &Op : Operands) {
+    if (Op.IsExplicit) {
+      const int TiedTo =
+          MCInstrDesc.getOperandConstraint(Op.Index, llvm::MCOI::TIED_TO);
+      if (TiedTo >= 0) {
+        Op.TiedTo = &Operands[TiedTo];
+        tie(&Op, Operands[TiedTo].Var);
+      } else {
+        tie(&Op, Op.Var);
+      }
+    }
+  }
+  for (auto &Op : Operands) {
+    if (Op.Var) {
+      Variables.push_back(&*Op.Var);
+    }
+  }
+  // Processing Aliasing.
+  DefRegisters = RATC.emptyRegisters();
+  UseRegisters = RATC.emptyRegisters();
+  for (const auto &Op : Operands) {
+    if (Op.Tracker) {
+      auto &Registers = Op.IsDef ? DefRegisters : UseRegisters;
+      Registers |= Op.Tracker->aliasedBits();
+    }
+  }
+}
+
+bool RegisterOperandAssignment::
+operator==(const RegisterOperandAssignment &Other) const {
+  return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg);
+}
+
+bool AliasingRegisterOperands::
+operator==(const AliasingRegisterOperands &Other) const {
+  return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
+}
+
+static void addOperandIfAlias(
+    const llvm::MCPhysReg Reg, bool SelectDef, llvm::ArrayRef<Operand> Operands,
+    llvm::SmallVectorImpl<RegisterOperandAssignment> &OperandValues) {
+  for (const auto &Op : Operands) {
+    if (Op.Tracker && Op.IsDef == SelectDef) {
+      const int SourceReg = Op.Tracker->getOrigin(Reg);
+      if (SourceReg >= 0)
+        OperandValues.emplace_back(&Op, SourceReg);
+    }
+  }
+}
+
+bool AliasingRegisterOperands::hasImplicitAliasing() const {
+  const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
+    return !ROV.Op->IsExplicit;
+  };
+  return llvm::any_of(Defs, HasImplicit) && llvm::any_of(Uses, HasImplicit);
+}
+
+bool AliasingConfigurations::empty() const { return Configurations.empty(); }
+
+bool AliasingConfigurations::hasImplicitAliasing() const {
+  return llvm::any_of(Configurations, [](const AliasingRegisterOperands &ARO) {
+    return ARO.hasImplicitAliasing();
+  });
+}
+
+AliasingConfigurations::AliasingConfigurations(
+    const Instruction &DefInstruction, const Instruction &UseInstruction)
+    : DefInstruction(DefInstruction), UseInstruction(UseInstruction) {
+  if (UseInstruction.UseRegisters.anyCommon(DefInstruction.DefRegisters)) {
+    auto CommonRegisters = UseInstruction.UseRegisters;
+    CommonRegisters &= DefInstruction.DefRegisters;
+    for (const llvm::MCPhysReg Reg : CommonRegisters.set_bits()) {
+      AliasingRegisterOperands ARO;
+      addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs);
+      addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses);
+      if (!ARO.Defs.empty() && !ARO.Uses.empty() &&
+          !llvm::is_contained(Configurations, ARO))
+        Configurations.push_back(std::move(ARO));
+    }
+  }
+}
+
+std::mt19937 &randomGenerator() {
+  static std::random_device RandomDevice;
+  static std::mt19937 RandomGenerator(RandomDevice());
+  return RandomGenerator;
+}
+
+static size_t randomIndex(size_t Size) {
+  assert(Size > 0);
+  std::uniform_int_distribution<> Distribution(0, Size - 1);
+  return Distribution(randomGenerator());
+}
+
+template <typename C>
+static auto randomElement(const C &Container) -> decltype(Container[0]) {
+  return Container[randomIndex(Container.size())];
+}
+
+static void randomize(Variable &Var) {
+  assert(!Var.TiedOperands.empty());
+  assert(Var.TiedOperands.front() != nullptr);
+  const Operand &Op = *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.
+    Var.AssignedValue = llvm::MCOperand::createImm(1);
+    break;
+  case llvm::MCOI::OperandType::OPERAND_REGISTER: {
+    assert(Op.Tracker);
+    const auto &Registers = Op.Tracker->sourceBits();
+    Var.AssignedValue = llvm::MCOperand::createReg(randomBit(Registers));
+    break;
+  }
+  default:
+    break;
+  }
+}
+
+static void setRegisterOperandValue(const RegisterOperandAssignment &ROV) {
+  const Operand *Op = ROV.Op->TiedTo ? ROV.Op->TiedTo : ROV.Op;
+  assert(Op->Var);
+  auto &AssignedValue = Op->Var->AssignedValue;
+  if (AssignedValue.isValid()) {
+    assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
+    return;
+  }
+  Op->Var->AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
+}
+
+size_t randomBit(const llvm::BitVector &Vector) {
+  assert(Vector.any());
+  auto Itr = Vector.set_bits_begin();
+  for (size_t I = randomIndex(Vector.count()); I != 0; --I)
+    ++Itr;
+  return *Itr;
+}
+
+void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations) {
+  assert(!AliasingConfigurations.empty());
+  assert(!AliasingConfigurations.hasImplicitAliasing());
+  const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
+  setRegisterOperandValue(randomElement(RandomConf.Defs));
+  setRegisterOperandValue(randomElement(RandomConf.Uses));
+}
+
+void randomizeUnsetVariable(const Instruction &Instruction) {
+  for (auto *Var : Instruction.Variables)
+    if (!Var->AssignedValue.isValid())
+      randomize(*Var);
+}
+
+void clearVariableAssignments(const Instruction &Instruction) {
+  for (auto *Var : Instruction.Variables)
+    Var->AssignedValue = llvm::MCOperand();
+}
+
+llvm::MCInst build(const Instruction &Instruction) {
+  llvm::MCInst Result;
+  Result.setOpcode(Instruction.Description.Opcode);
+  for (const auto &Op : Instruction.Operands) {
+    if (Op.IsExplicit) {
+      auto &Var = Op.TiedTo ? Op.TiedTo->Var : Op.Var;
+      assert(Var);
+      Result.addOperand(Var->AssignedValue);
+    }
+  }
+  return Result;
+}
+
+llvm::MCInst randomizeUnsetVariablesAndBuild(const Instruction &Instruction) {
+  randomizeUnsetVariable(Instruction);
+  return build(Instruction);
+}
+
+void DumpMCOperand(const llvm::MCRegisterInfo &MCRegisterInfo,
+                   const llvm::MCOperand &Op, llvm::raw_ostream &OS) {
+  if (!Op.isValid())
+    OS << "Invalid";
+  else if (Op.isReg())
+    OS << MCRegisterInfo.getName(Op.getReg());
+  else if (Op.isImm())
+    OS << Op.getImm();
+  else if (Op.isFPImm())
+    OS << Op.getFPImm();
+  else if (Op.isExpr())
+    OS << "Expr";
+  else if (Op.isInst())
+    OS << "SubInst";
+}
+
+void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo,
+                const llvm::MCInstrInfo &MCInstrInfo,
+                const llvm::MCInst &MCInst, llvm::raw_ostream &OS) {
+  OS << MCInstrInfo.getName(MCInst.getOpcode());
+  for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) {
+    if (I > 0)
+      OS << ',';
+    OS << ' ';
+    DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS);
+  }
+}
+
+} // namespace exegesis

tools/llvm-exegesis/lib/OperandGraph.h

-//===-- OperandGraph.h ------------------------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-///
-/// \file
-/// A collection of tools to model register aliasing and instruction operand.
-/// This is used to find an aliasing between the input and output registers of
-/// an instruction. It allows us to repeat an instruction and make sure that
-/// successive instances are executed sequentially.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H
-#define LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H
-
-#include "llvm/MC/MCRegisterInfo.h"
-#include <map>
-#include <set>
-#include <tuple>
-#include <vector>
-
-namespace exegesis {
-namespace graph {
-
-enum class NodeType {
-  VARIABLE, // An set of "tied together operands" to resolve.
-  REG,      // A particular register.
-  IN,       // The input node.
-  OUT       // The output node.
-};
-
-// A Node in the graph, it has a type and an int value.
-struct Node : public std::pair<NodeType, int> {
-  using std::pair<NodeType, int>::pair;
-
-  static Node Reg(int Value) { return {NodeType::REG, Value}; }
-  static Node Var(int Value) { return {NodeType::VARIABLE, Value}; }
-  static Node In() { return {NodeType::IN, 0}; }
-  static Node Out() { return {NodeType::OUT, 0}; }
-
-  NodeType type() const;
-  int regValue() const; // checks that type==REG and returns value.
-  int varValue() const; // checks that type==VARIABLE and returns value.
-
-  void dump(const llvm::MCRegisterInfo &RegInfo) const;
-};
-
-// Graph represents the connectivity of registers for a particular instruction.
-// This object is used to select registers that would create a dependency chain
-// between instruction's input and output.
-struct Graph {
-public:
-  void connect(const Node From, const Node To);
-  void disconnect(const Node From, const Node To);
-
-  // Tries to find a path between 'From' and 'To' nodes.
-  // Returns empty if no path is found.
-  std::vector<Node> getPathFrom(const Node From, const Node To) const;
-
-private:
-  // We use std::set to keep the implementation simple, using an unordered_set
-  // requires the definition of a hasher.
-  using NodeSet = std::set<Node>;
-
-  // Performs a Depth First Search from 'current' node up until 'sentinel' node
-  // is found. 'path' is the recording of the traversed nodes, 'seen' is the
-  // collection of nodes seen so far.
-  bool dfs(const Node Current, const Node Sentinel, std::vector<Node> &Path,
-           NodeSet &Seen) const;
-
-  // We use std::map to keep the implementation simple, using an unordered_map
-  // requires the definition of a hasher.
-  std::map<Node, NodeSet> AdjacencyLists;
-};
-
-// Add register nodes to graph and connect them when they alias. Connection is
-// both ways.
-void setupRegisterAliasing(const llvm::MCRegisterInfo &RegInfo,
-                           Graph &TheGraph);
-
-} // namespace graph
-} // namespace exegesis
-
-#endif // LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H

tools/llvm-exegesis/lib/OperandGraph.cpp

-//===-- OperandGraph.cpp ----------------------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "OperandGraph.h"
-#include "llvm/MC/MCRegisterInfo.h"
-
-namespace exegesis {
-namespace graph {
-
-void Node::dump(const llvm::MCRegisterInfo &RegInfo) const {
-  switch (type()) {
-  case NodeType::VARIABLE:
-    printf(" %d", varValue());
-    break;
-  case NodeType::REG:
-    printf(" %s", RegInfo.getName(regValue()));
-    break;
-  case NodeType::IN:
-    printf(" IN");
-    break;
-  case NodeType::OUT:
-    printf(" OUT");
-    break;
-  }
-}
-
-NodeType Node::type() const { return first; }
-
-int Node::regValue() const {
-  assert(first == NodeType::REG && "regValue() called on non-reg");
-  return second;
-}
-
-int Node::varValue() const {
-  assert(first == NodeType::VARIABLE && "varValue() called on non-var");
-  return second;
-}
-
-void Graph::connect(const Node From, const Node To) {
-  AdjacencyLists[From].insert(To);
-}
-
-void Graph::disconnect(const Node From, const Node To) {
-  AdjacencyLists[From].erase(To);
-}
-
-std::vector<Node> Graph::getPathFrom(const Node From, const Node To) const {
-  std::vector<Node> Path;
-  NodeSet Seen;
-  dfs(From, To, Path, Seen);
-  return Path;
-}
-
-// DFS is implemented recursively, this is fine as graph size is small (~250
-// nodes, ~200 edges, longuest path depth < 10).
-bool Graph::dfs(const Node Current, const Node Sentinel,
-                std::vector<Node> &Path, NodeSet &Seen) const {
-  Path.push_back(Current);
-  Seen.insert(Current);
-  if (Current == Sentinel)
-    return true;
-  if (AdjacencyLists.count(Current)) {
-    for (const Node Next : AdjacencyLists.find(Current)->second) {
-      if (Seen.count(Next))
-        continue;
-      if (dfs(Next, Sentinel, Path, Seen))
-        return true;
-    }
-  }
-  Path.pop_back();
-  return false;
-}
-
-// For each Register Units we walk up their parents.
-// Let's take the case of the A register family:
-//
-//  RAX
-//   ^
-//   EAX
-//    ^
-//    AX
-//   ^  ^
-//  AH  AL
-//
-// Register Units are AH and AL.
-// Walking them up gives the following lists:
-// AH->AX->EAX->RAX and AL->AX->EAX->RAX
-// When walking the lists we add connect current to parent both ways leading to
-// the following connections:
-//
-// AL<->AX, AH<->AX, AX<->EAX, EAX<->RAX
-// We repeat this process for all Unit Registers to cover all connections.
-void setupRegisterAliasing(const llvm::MCRegisterInfo &RegInfo,
-                           Graph &TheGraph) {
-  using SuperItr = llvm::MCSuperRegIterator;
-  for (size_t Reg = 0, E = RegInfo.getNumRegUnits(); Reg < E; ++Reg) {
-    size_t Current = Reg;
-    for (SuperItr Super(Reg, &RegInfo); Super.isValid(); ++Super) {
-      const Node A = Node::Reg(Current);
-      const Node B = Node::Reg(*Super);
-      TheGraph.connect(A, B);
-      TheGraph.connect(B, A);
-      Current = *Super;
-    }
-  }
-}
-
-} // namespace graph
-} // namespace exegesis

tools/llvm-exegesis/lib/RegisterAliasing.h

+//===-- RegisterAliasingTracker.h -------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Defines classes to keep track of register aliasing.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
+
+#include <memory>
+#include <unordered_map>
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/PackedVector.h"
+#include "llvm/MC/MCRegisterInfo.h"
+
+namespace exegesis {
+
+// Returns the registers that are aliased by the ones set in SourceBits.
+llvm::BitVector getAliasedBits(const llvm::MCRegisterInfo &RegInfo,
+                               const llvm::BitVector &SourceBits);
+
+// Keeps track of a mapping from one register (or a register class) to its
+// aliased registers.
+//
+// e.g.
+// RegisterAliasingTracker Tracker(RegInfo, llvm::X86::EAX);
+// Tracker.sourceBits() == { llvm::X86::EAX }
+// Tracker.aliasedBits() == { llvm::X86::AL, llvm::X86::AH, llvm::X86::AX,
+//                            llvm::X86::EAX,llvm::X86::HAX, llvm::X86::RAX }
+// Tracker.getOrigin(llvm::X86::AL) == llvm::X86::EAX;
+// Tracker.getOrigin(llvm::X86::BX) == -1;
+struct RegisterAliasingTracker {
+  // Construct a tracker from an MCRegisterClass.
+  RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo,
+                          const llvm::BitVector &ReservedReg,
+                          const llvm::MCRegisterClass &RegClass);
+
+  // Construct a tracker from an MCPhysReg.
+  RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo,
+                          const llvm::MCPhysReg Register);
+
+  const llvm::BitVector &sourceBits() const { return SourceBits; }
+
+  // Retrieves all the touched registers as a BitVector.
+  const llvm::BitVector &aliasedBits() const { return AliasedBits; }
+
+  // Returns the origin of this register or -1.
+  int getOrigin(llvm::MCPhysReg Aliased) const {
+    if (!AliasedBits[Aliased])
+      return -1;
+    return Origins[Aliased];
+  }
+
+private:
+  RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo);
+
+  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.
+};
+
+// A cache of existing trackers.
+struct RegisterAliasingTrackerCache {
+  // RegInfo must outlive the cache.
+  RegisterAliasingTrackerCache(const llvm::MCRegisterInfo &RegInfo,
+                               const llvm::BitVector &ReservedReg);
+
+  // Convenient function to retrieve a BitVector of the right size.
+  const llvm::BitVector &emptyRegisters() const { return EmptyRegisters; }
+
+  // Convenient function to retrieve the registers the function body can't use.
+  const llvm::BitVector &reservedRegisters() const { return ReservedReg; }
+
+  // Convenient function to retrieve the underlying MCRegInfo.
+  const llvm::MCRegisterInfo &regInfo() const { return RegInfo; }
+
+  // Retrieves the RegisterAliasingTracker for this particular register.
+  const RegisterAliasingTracker &getRegister(llvm::MCPhysReg Reg);
+
+  // Retrieves the RegisterAliasingTracker for this particular register class.
+  const RegisterAliasingTracker &getRegisterClass(unsigned RegClassIndex);
+
+private:
+  const llvm::MCRegisterInfo &RegInfo;
+  const llvm::BitVector ReservedReg;
+  const llvm::BitVector EmptyRegisters;
+  std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
+      Registers;
+  std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
+      RegisterClasses;
+};
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H

tools/llvm-exegesis/lib/RegisterAliasing.cpp

+//===-- RegisterAliasingTracker.cpp -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RegisterAliasing.h"
+
+namespace exegesis {
+
+llvm::BitVector getAliasedBits(const llvm::MCRegisterInfo &RegInfo,
+                               const llvm::BitVector &SourceBits) {
+  llvm::BitVector AliasedBits(RegInfo.getNumRegs());
+  for (const size_t PhysReg : SourceBits.set_bits()) {
+    using RegAliasItr = llvm::MCRegAliasIterator;
+    for (auto Itr = RegAliasItr(PhysReg, &RegInfo, true); Itr.isValid();
+         ++Itr) {
+      AliasedBits.set(*Itr);
+    }
+  }
+  return AliasedBits;
+}
+
+RegisterAliasingTracker::RegisterAliasingTracker(
+    const llvm::MCRegisterInfo &RegInfo)
+    : SourceBits(RegInfo.getNumRegs()), AliasedBits(RegInfo.getNumRegs()),
+      Origins(RegInfo.getNumRegs()) {}
+
+RegisterAliasingTracker::RegisterAliasingTracker(
+    const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &ReservedReg,
+    const llvm::MCRegisterClass &RegClass)
+    : RegisterAliasingTracker(RegInfo) {
+  for (llvm::MCPhysReg PhysReg : RegClass)
+    if (!ReservedReg[PhysReg]) // Removing reserved registers.
+      SourceBits.set(PhysReg);
+  FillOriginAndAliasedBits(RegInfo, SourceBits);
+}
+
+RegisterAliasingTracker::RegisterAliasingTracker(
+    const llvm::MCRegisterInfo &RegInfo, const llvm::MCPhysReg PhysReg)
+    : RegisterAliasingTracker(RegInfo) {
+  SourceBits.set(PhysReg);
+  FillOriginAndAliasedBits(RegInfo, SourceBits);
+}
+
+void RegisterAliasingTracker::FillOriginAndAliasedBits(
+    const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &SourceBits) {
+  using RegAliasItr = llvm::MCRegAliasIterator;
+  for (const size_t PhysReg : SourceBits.set_bits()) {
+    for (auto Itr = RegAliasItr(PhysReg, &RegInfo, true); Itr.isValid();
+         ++Itr) {
+      AliasedBits.set(*Itr);
+      Origins[*Itr] = PhysReg;
+    }
+  }
+}
+
+RegisterAliasingTrackerCache::RegisterAliasingTrackerCache(
+    const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &ReservedReg)
+    : RegInfo(RegInfo), ReservedReg(ReservedReg),
+      EmptyRegisters(RegInfo.getNumRegs()) {}
+
+const RegisterAliasingTracker &
+RegisterAliasingTrackerCache::getRegister(llvm::MCPhysReg PhysReg) {
+  auto &Found = Registers[PhysReg];
+  if (!Found)
+    Found.reset(new RegisterAliasingTracker(RegInfo, PhysReg));
+  return *Found;
+}
+
+const RegisterAliasingTracker &
+RegisterAliasingTrackerCache::getRegisterClass(unsigned RegClassIndex) {
+  auto &Found = RegisterClasses[RegClassIndex];
+  const auto &RegClass = RegInfo.getRegClass(RegClassIndex);
+  if (!Found)
+    Found.reset(new RegisterAliasingTracker(RegInfo, ReservedReg, RegClass));
+  return *Found;
+}
+
+} // namespace exegesis

tools/llvm-exegesis/lib/Uops.h

 #define LLVM_TOOLS_LLVM_EXEGESIS_UOPS_H
 
 #include "BenchmarkRunner.h"
 
 namespace exegesis {
 
 class UopsBenchmarkRunner : public BenchmarkRunner {
 public:
+  using BenchmarkRunner::BenchmarkRunner;
   ~UopsBenchmarkRunner() override;
 
 private:
   const char *getDisplayName() const override;
 
   llvm::Expected<std::vector<llvm::MCInst>>
-  createCode(const LLVMState &State, unsigned OpcodeIndex,
-             unsigned NumRepetitions,
-             const JitFunctionContext &Context) const override;
+  createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode,
+                llvm::raw_ostream &Info) const override;
 
   std::vector<BenchmarkMeasure>
-  runMeasurements(const LLVMState &State, const JitFunction &Function,
-                  unsigned NumRepetitions) const override;
+  runMeasurements(const ExecutableFunction &EF,
+                  const unsigned NumRepetitions) const override;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_UOPS_H

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 "BenchmarkResult.h"
-#include "InstructionSnippetGenerator.h"
-#include "PerfHelper.h"
-#include "llvm/ADT/StringExtras.h"
-#include "llvm/MC/MCInstrDesc.h"
-#include "llvm/MC/MCSchedule.h"
-#include "llvm/Support/Error.h"
-#include <algorithm>
-#include <random>
-#include <unordered_map>
-#include <unordered_set>
-
-namespace exegesis {
-
-// FIXME: Handle memory (see PR36906)
-static bool isInvalidOperand(const llvm::MCOperandInfo &OpInfo) {
-  switch (OpInfo.OperandType) {
-  default:
-    return true;
-  case llvm::MCOI::OPERAND_IMMEDIATE:
-  case llvm::MCOI::OPERAND_REGISTER:
-    return false;
-  }
-}
 
-static llvm::Error makeError(llvm::Twine Msg) {
-  return llvm::make_error<llvm::StringError>(Msg,
-                                             llvm::inconvertibleErrorCode());
-}
-
-static std::vector<llvm::MCInst> generateIndependentAssignments(
-    const LLVMState &State, const llvm::MCInstrDesc &InstrDesc,
-    llvm::SmallVector<Variable, 8> Vars, int MaxAssignments) {
-  std::unordered_set<llvm::MCPhysReg> IsUsedByAnyVar;
-  for (const Variable &Var : Vars) {
-    if (Var.IsUse) {
-      IsUsedByAnyVar.insert(Var.PossibleRegisters.begin(),
-                            Var.PossibleRegisters.end());
-    }
-  }
-
-  std::vector<llvm::MCInst> Pattern;
-  for (int A = 0; A < MaxAssignments; ++A) {
-    // FIXME: This is a bit pessimistic. We should get away with an
-    // assignment that ensures that the set of assigned registers for uses and
-    // the set of assigned registers for defs do not intersect (registers
-    // for uses (resp defs) do not have to be all distinct).
-    const std::vector<llvm::MCPhysReg> Regs = getExclusiveAssignment(Vars);
-    if (Regs.empty())
-      break;
-    // Remove all assigned registers defs that are used by at least one other
-    // variable from the list of possible variable registers. This ensures that
-    // we never create a RAW hazard that would lead to serialization.
-    for (size_t I = 0, E = Vars.size(); I < E; ++I) {
-      llvm::MCPhysReg Reg = Regs[I];
-      if (Vars[I].IsDef && IsUsedByAnyVar.count(Reg)) {
-        Vars[I].PossibleRegisters.remove(Reg);
-      }
-    }
-    // Create an MCInst and check assembly.
-    llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs);
-    if (!State.canAssemble(Inst))
-      continue;
-    Pattern.push_back(std::move(Inst));
-  }
-  return Pattern;
-}
-
-UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
-
-const char *UopsBenchmarkRunner::getDisplayName() const { return "uops"; }
-
-llvm::Expected<std::vector<llvm::MCInst>> UopsBenchmarkRunner::createCode(
-    const LLVMState &State, const unsigned OpcodeIndex,
-    const unsigned NumRepetitions, const JitFunctionContext &Context) const {
-  const auto &InstrInfo = State.getInstrInfo();
-  const auto &RegInfo = State.getRegInfo();
-  const llvm::MCInstrDesc &InstrDesc = InstrInfo.get(OpcodeIndex);
-  for (const llvm::MCOperandInfo &OpInfo : InstrDesc.operands()) {
-    if (isInvalidOperand(OpInfo))
-      return makeError("Only registers and immediates are supported");
-  }
+#include "Assembler.h"
+#include "BenchmarkRunner.h"
+#include "MCInstrDescView.h"
+#include "PerfHelper.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.
 
-  // To achieve that, one approach is to generate instructions that do not have
-  // data dependencies between them.
-  //
-  // For some instructions, this is trivial:
-  //    mov rax, qword ptr [rsi]
-  //    mov rax, qword ptr [rsi]
-  //    mov rax, qword ptr [rsi]
-  //    mov rax, qword ptr [rsi]
-  // For the above snippet, haswell just renames rax four times and executes the
-  // four instructions two at a time on P23 and P0126.
-  //
-  // For some instructions, we just need to make sure that the source is
-  // different from the destination. For example, IDIV8r reads from GPR and
-  // writes to AX. We just need to ensure that the variable is assigned a
-  // register which is different from AX:
-  //    idiv bx
-  //    idiv bx
-  //    idiv bx
-  //    idiv bx
-  // The above snippet will be able to fully saturate the ports, while the same
-  // with ax would issue one uop every `latency(IDIV8r)` cycles.
-  //
-  // Some instructions make this harder because they both read and write from
-  // the same register:
-  //    inc rax
-  //    inc rax
-  //    inc rax
-  //    inc rax
-  // This has a data dependency from each instruction to the next, limit the
-  // number of instructions that can be issued in parallel.
-  // It turns out that this is not a big issue on recent Intel CPUs because they
-  // have heuristics to balance port pressure. In the snippet above, subsequent
-  // instructions will end up evenly distributed on {P0,P1,P5,P6}, but some CPUs
-  // might end up executing them all on P0 (just because they can), or try
-  // avoiding P5 because it's usually under high pressure from vector
-  // instructions.
-  // This issue is even more important for high-latency instructions because
-  // they increase the idle time of the CPU, e.g. :
-  //    imul rax, rbx
-  //    imul rax, rbx
-  //    imul rax, rbx
-  //    imul rax, rbx
-  //
-  // To avoid that, we do the renaming statically by generating as many
-  // independent exclusive assignments as possible (until all possible registers
-  // are exhausted) e.g.:
-  //    imul rax, rbx
-  //    imul rcx, rbx
-  //    imul rdx, rbx
-  //    imul r8,  rbx
-  //
-  // Some instruction even make the above static renaming impossible because
-  // they implicitly read and write from the same operand, e.g. ADC16rr reads
-  // and writes from EFLAGS.
-  // In that case we just use a greedy register assignment and hope for the
-  // best.
+// writes to AX. We just need to ensure that the Var is assigned a
 
-  const auto Vars = getVariables(RegInfo, InstrDesc, Context.getReservedRegs());
+namespace exegesis {
 
-  // Generate as many independent exclusive assignments as possible.
-  constexpr const int MaxStaticRenames = 20;
-  std::vector<llvm::MCInst> Pattern =
-      generateIndependentAssignments(State, InstrDesc, Vars, MaxStaticRenames);
-  if (Pattern.empty()) {
-    // We don't even have a single exclusive assignment, fallback to a greedy
-    // assignment.
-    // FIXME: Tell the user about this decision to help debugging.
-    const std::vector<llvm::MCPhysReg> Regs = getGreedyAssignment(Vars);
-    if (!Vars.empty() && Regs.empty())
-      return makeError("No feasible greedy assignment");
-    llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs);
-    if (!State.canAssemble(Inst))
-      return makeError("Cannot assemble greedy assignment");
-    Pattern.push_back(std::move(Inst));
-  }
-
-  // Generate repetitions of the pattern until benchmark_iterations is reached.
-  std::vector<llvm::MCInst> Result;
-  Result.reserve(NumRepetitions);
-  for (unsigned I = 0; I < NumRepetitions; ++I)
-    Result.push_back(Pattern[I % Pattern.size()]);
+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;
+}
+
+static bool isInfeasible(const Instruction &Instruction, std::string &Error) {
+  const auto &MCInstrDesc = Instruction.Description;
+  if (MCInstrDesc.isPseudo()) {
+    Error = "is pseudo";
+    return true;
+  }
+  if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) {
+    Error = "has unknown operands";
+    return true;
+  }
+  if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) {
+    Error = "has memory operands";
+    return true;
+  }
+  return false;
+}
+
+// Returns whether this Variable ties Use and Def operands together.
+static bool hasTiedOperands(const Variable *Var) {
+  bool HasUse = false;
+  bool HasDef = false;
+  for (const Operand *Op : Var->TiedOperands) {
+    if (Op->IsDef)
+      HasDef = true;
+    else
+      HasUse = true;
+  }
+  return HasUse && HasDef;
+}
+
+static llvm::SmallVector<Variable *, 8>
+getTiedVariables(const Instruction &Instruction) {
+  llvm::SmallVector<Variable *, 8> Result;
+  for (auto *Var : Instruction.Variables)
+    if (hasTiedOperands(Var))
+      Result.push_back(Var);
   return Result;
 }
 
+static void remove(llvm::BitVector &a, const llvm::BitVector &b) {
+  assert(a.size() == b.size());
+  for (auto I : b.set_bits())
+    a.reset(I);
+}
+
+static llvm::Error makeError(llvm::Twine Msg) {
+  return llvm::make_error<llvm::StringError>(Msg,
+                                             llvm::inconvertibleErrorCode());
+}
+
+UopsBenchmarkRunner::~UopsBenchmarkRunner() = default;
+
+const char *UopsBenchmarkRunner::getDisplayName() const { return "uops"; }
+
+llvm::Expected<std::vector<llvm::MCInst>>
+UopsBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC,
+                                   unsigned Opcode,
+                                   llvm::raw_ostream &Info) const {
+  std::vector<llvm::MCInst> Snippet;
+  const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode);
+  const Instruction Instruction(MCInstrDesc, RATC);
+
+  std::string Error;
+  if (isInfeasible(Instruction, Error)) {
+    llvm::report_fatal_error(llvm::Twine("Infeasible : ").concat(Error));
+  }
+
+  const AliasingConfigurations SelfAliasing(Instruction, Instruction);
+  if (SelfAliasing.empty()) {
+    Info << "instruction is parallel, repeating a random one.\n";
+    Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+    return Snippet;
+  }
+  if (SelfAliasing.hasImplicitAliasing()) {
+    Info << "instruction is serial, repeating a random one.\n";
+    Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+    return Snippet;
+  }
+  const auto TiedVariables = getTiedVariables(Instruction);
+  if (!TiedVariables.empty()) {
+    if (TiedVariables.size() > 1) {
+      Info << "Not yet implemented, don't know how to handle several tied "
+              "variables\n";
+      return makeError("Infeasible : don't know how to handle several tied "
+                       "variables");
+    }
+    Info << "instruction has tied variables using static renaming.\n";
+    Variable *Var = TiedVariables.front();
+    assert(Var);
+    assert(!Var->TiedOperands.empty());
+    const Operand &Operand = *Var->TiedOperands.front();
+    assert(Operand.Tracker);
+    for (const llvm::MCPhysReg Reg : Operand.Tracker->sourceBits().set_bits()) {
+      clearVariableAssignments(Instruction);
+      Var->AssignedValue = llvm::MCOperand::createReg(Reg);
+      Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+    }
+    return Snippet;
+  }
+  // No tied variables, we pick random values for defs.
+  llvm::BitVector Defs(MCRegisterInfo.getNumRegs());
+  for (const auto &Op : Instruction.Operands) {
+    if (Op.Tracker && Op.IsExplicit && Op.IsDef) {
+      assert(Op.Var);
+      auto PossibleRegisters = Op.Tracker->sourceBits();
+      remove(PossibleRegisters, RATC.reservedRegisters());
+      assert(PossibleRegisters.any() && "No register left to choose from");
+      const auto RandomReg = randomBit(PossibleRegisters);
+      Defs.set(RandomReg);
+      Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg);
+    }
+  }
+  // And pick random use values that are not reserved and don't alias with defs.
+  const auto DefAliases = getAliasedBits(MCRegisterInfo, Defs);
+  for (const auto &Op : Instruction.Operands) {
+    if (Op.Tracker && Op.IsExplicit && !Op.IsDef) {
+      assert(Op.Var);
+      auto PossibleRegisters = Op.Tracker->sourceBits();
+      remove(PossibleRegisters, RATC.reservedRegisters());
+      remove(PossibleRegisters, DefAliases);
+      assert(PossibleRegisters.any() && "No register left to choose from");
+      const auto RandomReg = randomBit(PossibleRegisters);
+      Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg);
+    }
+  }
+  Info
+      << "instruction has no tied variables picking Uses different from defs\n";
+  Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+  return Snippet;
+}
+
 std::vector<BenchmarkMeasure>
-UopsBenchmarkRunner::runMeasurements(const LLVMState &State,
-                                     const JitFunction &Function,
+UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function,
                                      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;
     // FIXME: Sum results when there are several counters for a single ProcRes
     // (e.g. P23 on SandyBridge).
-    pfm::Counter Counter{pfm::PerfEvent(PfmCounters)};
+    pfm::PerfEvent UopPerfEvent(PfmCounters);
+    if (!UopPerfEvent.valid())
+      llvm::report_fatal_error(
+          llvm::Twine("invalid perf event ").concat(PfmCounters));
+    pfm::Counter Counter(UopPerfEvent);
     Counter.start();
     Function();
     Counter.stop();
     Result.push_back({llvm::itostr(ProcResIdx),
                       static_cast<double>(Counter.read()) / NumRepetitions,
                       SchedModel.getProcResource(ProcResIdx)->Name});
   }
   return Result;
 }
 
 } // namespace exegesis

tools/llvm-exegesis/llvm-exegesis.cpp

AnalysisEpsilon("analysis-epsilon",
                     llvm::cl::init(0.1));
 
 static llvm::cl::opt<std::string> AnalysisClustersFile("analysis-clusters-file",
                                                        llvm::cl::desc(""),
                                                        llvm::cl::init("-"));
 
 namespace exegesis {
 
+static unsigned GetOpcodeOrDie(const llvm::MCInstrInfo &MCInstrInfo) {
+  if (OpcodeName.empty() && (OpcodeIndex == 0))
+    llvm::report_fatal_error(
+        "please provide one and only one of 'opcode-index' or 'opcode-name'");
+  if (OpcodeIndex > 0)
+    return OpcodeIndex;
+  // Resolve opcode name -> opcode.
+  for (unsigned I = 0, E = MCInstrInfo.getNumOpcodes(); I < E; ++I)
+    if (MCInstrInfo.getName(I) == OpcodeName)
+      return I;
+  llvm::report_fatal_error(llvm::Twine("unknown opcode ").concat(OpcodeName));
+}
+
 void benchmarkMain() {
   if (exegesis::pfm::pfmInitialize())
     llvm::report_fatal_error("cannot initialize libpfm");
 
-  if (OpcodeName.empty() == (OpcodeIndex == 0))
-    llvm::report_fatal_error(
-        "please provide one and only one of 'opcode-index' or 'opcode-name'");
-
   llvm::InitializeNativeTarget();
   llvm::InitializeNativeTargetAsmPrinter();
 
   // FIXME: Target-specific filter.
   X86Filter Filter;
 
   const LLVMState State;
 
+  // FIXME: Do not require SchedModel for latency.
   if (!State.getSubtargetInfo().getSchedModel().hasExtraProcessorInfo())
     llvm::report_fatal_error("sched model is missing extra processor info!");
 
-  unsigned Opcode = OpcodeIndex;
-  if (Opcode == 0) {
-    // Resolve opcode name -> opcode.
-    for (unsigned I = 0, E = State.getInstrInfo().getNumOpcodes(); I < E; ++I) {
-      if (State.getInstrInfo().getName(I) == OpcodeName) {
-        Opcode = I;
-        break;
-      }
-    }
-    if (Opcode == 0) {
-      llvm::report_fatal_error(
-          llvm::Twine("unknown opcode ").concat(OpcodeName));
-    }
-  }
-
   std::unique_ptr<BenchmarkRunner> Runner;
   switch (BenchmarkMode) {
   case BenchmarkModeE::Latency:
-    Runner = llvm::make_unique<LatencyBenchmarkRunner>();
+    Runner = llvm::make_unique<LatencyBenchmarkRunner>(State);
     break;
   case BenchmarkModeE::Uops:
-    Runner = llvm::make_unique<UopsBenchmarkRunner>();
+    Runner = llvm::make_unique<UopsBenchmarkRunner>(State);
     break;
   case BenchmarkModeE::Analysis:
     llvm_unreachable("not a benchmark");
   }
 
-  Runner->run(State, Opcode, NumRepetitions > 0 ? NumRepetitions : 1, Filter)
+  if (NumRepetitions == 0)
+    llvm::report_fatal_error("--num-repetitions must be greater than zero");
+
+  Runner->run(GetOpcodeOrDie(State.getInstrInfo()), Filter, NumRepetitions)
       .writeYamlOrDie(BenchmarkFile);
   exegesis::pfm::pfmTerminate();
 }
 
 void analysisMain() {
   // Read benchmarks.
   const std::vector<InstructionBenchmark> Points =
       InstructionBenchmark::readYamlsOrDie(BenchmarkFile);

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
   ClusteringTest.cpp
-  OperandGraphTest.cpp
   PerfHelperTest.cpp
   )
 target_link_libraries(LLVMExegesisTests PRIVATE LLVMExegesis)
 
 if(LLVM_ENABLE_LIBPFM AND HAVE_LIBPFM)
   target_link_libraries(LLVMExegesisTests PRIVATE pfm)
 endif()
 
 if(LLVM_TARGETS_TO_BUILD MATCHES "X86")
   add_subdirectory(X86)
 endif()
 if(LLVM_TARGETS_TO_BUILD MATCHES "ARM")
   add_subdirectory(ARM)
 endif()

unittests/tools/llvm-exegesis/OperandGraphTest.cpp

-//===-- OperandGraphTest.cpp ------------------------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "OperandGraph.h"
-#include "gmock/gmock.h"
-#include "gtest/gtest.h"
-
-using testing::ElementsAre;
-using testing::IsEmpty;
-using testing::Not;
-
-namespace exegesis {
-namespace graph {
-namespace {
-
-static const auto In = Node::In();
-static const auto Out = Node::Out();
-
-TEST(OperandGraphTest, NoPath) {
-  Graph TheGraph;
-  EXPECT_THAT(TheGraph.getPathFrom(In, Out), IsEmpty());
-}
-
-TEST(OperandGraphTest, Connecting) {
-  Graph TheGraph;
-  TheGraph.connect(In, Out);
-  EXPECT_THAT(TheGraph.getPathFrom(In, Out), Not(IsEmpty()));
-  EXPECT_THAT(TheGraph.getPathFrom(In, Out), ElementsAre(In, Out));
-}
-
-TEST(OperandGraphTest, ConnectingThroughVariable) {
-  const Node Var = Node::Var(1);
-  Graph TheGraph;
-  TheGraph.connect(In, Var);
-  TheGraph.connect(Var, Out);
-  EXPECT_THAT(TheGraph.getPathFrom(In, Out), Not(IsEmpty()));
-  EXPECT_THAT(TheGraph.getPathFrom(In, Out), ElementsAre(In, Var, Out));
-}
-
-} // namespace
-} // namespace graph
-} // namespace exegesis

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

 include_directories(
   ${LLVM_MAIN_SRC_DIR}/lib/Target/X86
   ${LLVM_BINARY_DIR}/lib/Target/X86
   ${LLVM_MAIN_SRC_DIR}/tools/llvm-exegesis/lib
   )
 
 set(LLVM_LINK_COMPONENTS
   MC
   MCParser
   Object
   Support
   Symbolize
   X86
   )
 
 add_llvm_unittest(LLVMExegesisX86Tests
+  RegisterAliasingTest.cpp
   InMemoryAssemblerTest.cpp
-  InstructionSnippetGeneratorTest.cpp
   )
 target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis)
-

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

 //===-- InMemoryAssemblerTest.cpp -------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "InMemoryAssembler.h"
+#include "Assembler.h"
 #include "X86InstrInfo.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"
protected:
   }
 
   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);
+    llvm::TargetMachine *TM = TheTarget->createTargetMachine(
     EXPECT_TRUE(TM) << TT << " " << CpuName;
     return std::unique_ptr<llvm::LLVMTargetMachine>(
         static_cast<llvm::LLVMTargetMachine *>(TM));
   }
 
   bool IsSupportedTarget() const {
     return llvm::StringRef(TT).startswith_lower("x86_64");
   }
 
+  ExecutableFunction assembleFunction(llvm::MCInst MCInst) {
+    return assembleToFunction({MCInst});
+  }
+
+  ExecutableFunction assembleEmptyFunction() { return assembleToFunction({}); }
+
 private:
+  ExecutableFunction
+  assembleToFunction(llvm::ArrayRef<llvm::MCInst> Instructions) {
+    llvm::SmallString<256> Buffer;
+    llvm::raw_svector_ostream AsmStream(Buffer);
+    assembleToStream(createTargetMachine(), Instructions, AsmStream);
+    return ExecutableFunction(createTargetMachine(),
+                              getObjectFromBuffer(AsmStream.str()));
+  }
   const std::string TT;
   const std::string CpuName;
 };
 
 // Used to skip tests on unsupported architectures and operating systems.
 // To skip a test, add this macro at the top of a test-case.
-#define SKIP_UNSUPPORTED_PLATFORM \
-  do \
-    if (!IsSupportedTarget()) \
-      return; \
-  while(0)
+#define SKIP_UNSUPPORTED_PLATFORM                                              \
+  do                                                                           \
+    if (!IsSupportedTarget())                                                  \
+      return;                                                                  \
+  while (0)
 
-
-TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunction) {
+TEST_F(MachineFunctionGeneratorTest, JitFunction) {
   SKIP_UNSUPPORTED_PLATFORM;
-  JitFunctionContext Context(createTargetMachine());
-  JitFunction Function(std::move(Context), {});
+  const ExecutableFunction Function = assembleEmptyFunction();
   ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0xc3));
   // FIXME: Check that the function runs without errors. Right now this is
   // disabled because it fails on some bots.
-  // Function();
+  Function();
 }
 
-TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr) {
+TEST_F(MachineFunctionGeneratorTest, JitFunctionXOR32rr) {
   SKIP_UNSUPPORTED_PLATFORM;
-  JitFunctionContext Context(createTargetMachine());
-  JitFunction Function(
-      std::move(Context),
-      {MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX)});
+  const ExecutableFunction Function = assembleFunction(
+      MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX));
   ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0x31, 0xc0, 0xc3));
-  // Function();
+  Function();
 }
 
-TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV64ri) {
+TEST_F(MachineFunctionGeneratorTest, JitFunctionMOV64ri) {
   SKIP_UNSUPPORTED_PLATFORM;
-  JitFunctionContext Context(createTargetMachine());
-  JitFunction Function(std::move(Context),
-                       {MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42)});
+  const ExecutableFunction Function =
+      assembleFunction(MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42));
   ASSERT_THAT(Function.getFunctionBytes().str(),
               ElementsAre(0x48, 0xc7, 0xc0, 0x2a, 0x00, 0x00, 0x00, 0xc3));
-  // Function();
+  Function();
 }
 
-TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV32ri) {
+TEST_F(MachineFunctionGeneratorTest, JitFunctionMOV32ri) {
   SKIP_UNSUPPORTED_PLATFORM;
-  JitFunctionContext Context(createTargetMachine());
-  JitFunction Function(std::move(Context),
-                       {MCInstBuilder(MOV32ri).addReg(EAX).addImm(42)});
+  const ExecutableFunction Function =
+      assembleFunction(MCInstBuilder(MOV32ri).addReg(EAX).addImm(42));
   ASSERT_THAT(Function.getFunctionBytes().str(),
               ElementsAre(0xb8, 0x2a, 0x00, 0x00, 0x00, 0xc3));
-  // Function();
+  Function();
 }
 
 } // namespace
 } // namespace exegesis

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

-//===-- InstructionSnippetGeneratorTest.cpp ---------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "InstructionSnippetGenerator.h"
-#include "X86InstrInfo.h"
-#include "llvm/MC/MCInstBuilder.h"
-#include "llvm/Support/Host.h"
-#include "llvm/Support/TargetRegistry.h"
-#include "llvm/Support/TargetSelect.h"
-#include "gmock/gmock.h"
-#include "gtest/gtest.h"
-#include <memory>
-#include <set>
-
-namespace llvm {
-
-bool operator==(const MCOperand &A, const MCOperand &B) {
-  if ((A.isValid() == false) && (B.isValid() == false))
-    return true;
-  if (A.isReg() && B.isReg())
-    return A.getReg() == B.getReg();
-  if (A.isImm() && B.isImm())
-    return A.getImm() == B.getImm();
-  return false;
-}
-
-} // namespace llvm
-
-namespace exegesis {
-namespace {
-
-using testing::_;
-using testing::AllOf;
-using testing::AnyOf;
-using testing::Contains;
-using testing::ElementsAre;
-using testing::Eq;
-using testing::Field;
-using testing::Not;
-using testing::SizeIs;
-using testing::UnorderedElementsAre;
-using testing::Value;
-
-using llvm::X86::AL;
-using llvm::X86::AX;
-using llvm::X86::EFLAGS;
-using llvm::X86::RAX;
-
-class MCInstrDescViewTest : public ::testing::Test {
-protected:
-  MCInstrDescViewTest()
-      : TheTriple("x86_64") {}
-
-  static void SetUpTestCase() {
-    LLVMInitializeX86TargetInfo();
-    LLVMInitializeX86TargetMC();
-    LLVMInitializeX86Target();
-  }
-
-  void SetUp() override {
-    std::string Error;
-    const auto *Target = llvm::TargetRegistry::lookupTarget(TheTriple, Error);
-    InstrInfo.reset(Target->createMCInstrInfo());
-    RegInfo.reset(Target->createMCRegInfo(TheTriple));
-  }
-
-  const std::string TheTriple;
-  std::unique_ptr<const llvm::MCInstrInfo> InstrInfo;
-  std::unique_ptr<const llvm::MCRegisterInfo> RegInfo;
-};
-
-MATCHER(IsDef, "") { return arg.IsDef; }
-MATCHER(IsUse, "") { return arg.IsUse; }
-MATCHER_P2(EqVarAssignement, VariableIndexMatcher, AssignedRegisterMatcher,
-           "") {
-  return Value(
-      arg,
-      AllOf(Field(&VariableAssignment::VarIdx, VariableIndexMatcher),
-            Field(&VariableAssignment::AssignedReg, AssignedRegisterMatcher)));
-}
-
-size_t returnIndexZero(const size_t UpperBound) { return 0; }
-
-TEST_F(MCInstrDescViewTest, DISABLED_XOR64rr) {
-  const llvm::MCInstrDesc &InstrDesc = InstrInfo->get(llvm::X86::XOR64rr);
-  const auto Vars =
-      getVariables(*RegInfo, InstrDesc, llvm::BitVector(RegInfo->getNumRegs()));
-
-  // XOR64rr has the following operands:
-  //  0. out register
-  //  1. in register (tied to out)
-  //  2. in register
-  //  3. out EFLAGS (implicit)
-  //
-  // This translates to 3 variables, one for 0 and 1, one for 2, one for 3.
-  ASSERT_THAT(Vars, SizeIs(3));
-
-  EXPECT_THAT(Vars[0].ExplicitOperands, ElementsAre(0, 1));
-  EXPECT_THAT(Vars[1].ExplicitOperands, ElementsAre(2));
-  EXPECT_THAT(Vars[2].ExplicitOperands, ElementsAre()); // implicit
-
-  EXPECT_THAT(Vars[0], AllOf(IsUse(), IsDef()));
-  EXPECT_THAT(Vars[1], AllOf(IsUse(), Not(IsDef())));
-  EXPECT_THAT(Vars[2], AllOf(Not(IsUse()), IsDef()));
-
-  EXPECT_THAT(Vars[0].PossibleRegisters, Contains(RAX));
-  EXPECT_THAT(Vars[1].PossibleRegisters, Contains(RAX));
-  EXPECT_THAT(Vars[2].PossibleRegisters, ElementsAre(EFLAGS));
-
-  // Computing chains.
-  const auto Chains = computeSequentialAssignmentChains(*RegInfo, Vars);
-
-  // Because operands 0 and 1 are tied together any possible value for variable
-  // 0 would do.
-  for (const auto &Reg : Vars[0].PossibleRegisters) {
-    EXPECT_THAT(Chains, Contains(ElementsAre(EqVarAssignement(0, Reg))));
-  }
-
-  // We also have chains going through operand 0 to 2 (i.e. Vars 0 and 1).
-  EXPECT_THAT(Vars[0].PossibleRegisters, Eq(Vars[1].PossibleRegisters))
-      << "Variables 0 and 1 are of the same class";
-  for (const auto &Reg : Vars[0].PossibleRegisters) {
-    EXPECT_THAT(Chains,
-                Contains(UnorderedElementsAre(EqVarAssignement(0, Reg),
-                                              EqVarAssignement(1, Reg))));
-  }
-
-  // EFLAGS does not appear as an input therefore no chain can contain EFLAGS.
-  EXPECT_THAT(Chains, Not(Contains(Contains(EqVarAssignement(_, EFLAGS)))));
-
-  // Computing assignment.
-  const auto Regs = getRandomAssignment(Vars, Chains, &returnIndexZero);
-  EXPECT_THAT(Regs, ElementsAre(RAX, RAX, EFLAGS));
-
-  // Generating assembler representation.
-  const llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs);
-  EXPECT_THAT(Inst.getOpcode(), llvm::X86::XOR64rr);
-  EXPECT_THAT(Inst.getNumOperands(), 3);
-  EXPECT_THAT(Inst.getOperand(0), llvm::MCOperand::createReg(RAX));
-  EXPECT_THAT(Inst.getOperand(1), llvm::MCOperand::createReg(RAX));
-  EXPECT_THAT(Inst.getOperand(2), llvm::MCOperand::createReg(RAX));
-}
-
-TEST_F(MCInstrDescViewTest, DISABLED_AAA) {
-  const llvm::MCInstrDesc &InstrDesc = InstrInfo->get(llvm::X86::AAA);
-  const auto Vars =
-      getVariables(*RegInfo, InstrDesc, llvm::BitVector(RegInfo->getNumRegs()));
-
-  // AAA has the following operands:
-  //  0. out AX      (implicit)
-  //  1. out EFLAGS  (implicit)
-  //  2. in AL       (implicit)
-  //  3. in EFLAGS   (implicit)
-  //
-  // This translates to 4 Vars (non are tied together).
-  ASSERT_THAT(Vars, SizeIs(4));
-
-  EXPECT_THAT(Vars[0].ExplicitOperands, ElementsAre()); // implicit
-  EXPECT_THAT(Vars[1].ExplicitOperands, ElementsAre()); // implicit
-  EXPECT_THAT(Vars[2].ExplicitOperands, ElementsAre()); // implicit
-  EXPECT_THAT(Vars[3].ExplicitOperands, ElementsAre()); // implicit
-
-  EXPECT_THAT(Vars[0], AllOf(Not(IsUse()), IsDef()));
-  EXPECT_THAT(Vars[1], AllOf(Not(IsUse()), IsDef()));
-  EXPECT_THAT(Vars[2], AllOf(IsUse(), Not(IsDef())));
-  EXPECT_THAT(Vars[3], AllOf(IsUse(), Not(IsDef())));
-
-  EXPECT_THAT(Vars[0].PossibleRegisters, ElementsAre(AX));
-  EXPECT_THAT(Vars[1].PossibleRegisters, ElementsAre(EFLAGS));
-  EXPECT_THAT(Vars[2].PossibleRegisters, ElementsAre(AL));
-  EXPECT_THAT(Vars[3].PossibleRegisters, ElementsAre(EFLAGS));
-
-  const auto Chains = computeSequentialAssignmentChains(*RegInfo, Vars);
-  EXPECT_THAT(Chains,
-              ElementsAre(UnorderedElementsAre(EqVarAssignement(0, AX),
-                                               EqVarAssignement(2, AL)),
-                          UnorderedElementsAre(EqVarAssignement(1, EFLAGS),
-                                               EqVarAssignement(3, EFLAGS))));
-
-  // Computing assignment.
-  const auto Regs = getRandomAssignment(Vars, Chains, &returnIndexZero);
-  EXPECT_THAT(Regs, ElementsAre(AX, EFLAGS, AL, EFLAGS));
-
-  // Generating assembler representation.
-  const llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs);
-  EXPECT_THAT(Inst.getOpcode(), llvm::X86::AAA);
-  EXPECT_THAT(Inst.getNumOperands(), 0) << "All operands are implicit";
-}
-
-TEST_F(MCInstrDescViewTest, DISABLED_ReservedRegisters) {
-  llvm::BitVector ReservedRegisters(RegInfo->getNumRegs());
-
-  const llvm::MCInstrDesc &InstrDesc = InstrInfo->get(llvm::X86::XOR64rr);
-  {
-    const auto Vars = getVariables(*RegInfo, InstrDesc, ReservedRegisters);
-    ASSERT_THAT(Vars, SizeIs(3));
-    EXPECT_THAT(Vars[0].PossibleRegisters, Contains(RAX));
-    EXPECT_THAT(Vars[1].PossibleRegisters, Contains(RAX));
-  }
-
-  // Disable RAX.
-  ReservedRegisters.set(RAX);
-  {
-    const auto Vars = getVariables(*RegInfo, InstrDesc, ReservedRegisters);
-    ASSERT_THAT(Vars, SizeIs(3));
-    EXPECT_THAT(Vars[0].PossibleRegisters, Not(Contains(RAX)));
-    EXPECT_THAT(Vars[1].PossibleRegisters, Not(Contains(RAX)));
-  }
-}
-
-Variable makeVariableWithRegisters(bool IsReg,
-                                   std::initializer_list<int> Regs) {
-  assert((IsReg || (Regs.size() == 0)) && "IsReg => !(Regs.size() == 0)");
-  Variable Var;
-  Var.IsReg = IsReg;
-  Var.PossibleRegisters.insert(Regs.begin(), Regs.end());
-  return Var;
-}
-
-TEST(getExclusiveAssignment, TriviallyFeasible) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {3}),
-      makeVariableWithRegisters(false, {}),
-      makeVariableWithRegisters(true, {4}),
-      makeVariableWithRegisters(true, {5}),
-  };
-  const auto Regs = getExclusiveAssignment(Vars);
-  EXPECT_THAT(Regs, ElementsAre(3, 0, 4, 5));
-}
-
-TEST(getExclusiveAssignment, TriviallyInfeasible1) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {3}),
-      makeVariableWithRegisters(true, {}),
-      makeVariableWithRegisters(true, {4}),
-      makeVariableWithRegisters(true, {5}),
-  };
-  const auto Regs = getExclusiveAssignment(Vars);
-  EXPECT_THAT(Regs, ElementsAre());
-}
-
-TEST(getExclusiveAssignment, TriviallyInfeasible) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {4}),
-      makeVariableWithRegisters(true, {4}),
-  };
-  const auto Regs = getExclusiveAssignment(Vars);
-  EXPECT_THAT(Regs, ElementsAre());
-}
-
-TEST(getExclusiveAssignment, Feasible1) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {4, 3}),
-      makeVariableWithRegisters(true, {6, 3}),
-      makeVariableWithRegisters(true, {6, 4}),
-  };
-  const auto Regs = getExclusiveAssignment(Vars);
-  ASSERT_THAT(Regs, AnyOf(ElementsAre(3, 6, 4), ElementsAre(4, 3, 6)));
-}
-
-TEST(getExclusiveAssignment, Feasible2) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {1, 2}),
-      makeVariableWithRegisters(true, {3, 4}),
-  };
-  const auto Regs = getExclusiveAssignment(Vars);
-  ASSERT_THAT(Regs, AnyOf(ElementsAre(1, 3), ElementsAre(1, 4),
-                          ElementsAre(2, 3), ElementsAre(2, 4)));
-}
-
-TEST(getGreedyAssignment, Infeasible) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {}),
-      makeVariableWithRegisters(true, {1, 2}),
-  };
-  const auto Regs = getGreedyAssignment(Vars);
-  ASSERT_THAT(Regs, ElementsAre());
-}
-
-TEST(getGreedyAssignment, FeasibleNoFallback) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(true, {1, 2}),
-      makeVariableWithRegisters(false, {}),
-      makeVariableWithRegisters(true, {2, 3}),
-  };
-  const auto Regs = getGreedyAssignment(Vars);
-  ASSERT_THAT(Regs, ElementsAre(1, 0, 2));
-}
-
-TEST(getGreedyAssignment, Feasible) {
-  const std::vector<Variable> Vars = {
-      makeVariableWithRegisters(false, {}),
-      makeVariableWithRegisters(true, {1, 2}),
-      makeVariableWithRegisters(true, {2, 3}),
-      makeVariableWithRegisters(true, {2, 3}),
-      makeVariableWithRegisters(true, {2, 3}),
-  };
-  const auto Regs = getGreedyAssignment(Vars);
-  ASSERT_THAT(Regs, ElementsAre(0, 1, 2, 3, 2));
-}
-
-} // namespace
-} // namespace exegesis

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

+#include "RegisterAliasing.h"
+
+#include <cassert>
+#include <memory>
+
+#include "X86InstrInfo.h"
+#include "llvm/Support/Host.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace exegesis {
+namespace {
+
+class RegisterAliasingTest : public ::testing::Test {
+protected:
+  RegisterAliasingTest() {
+    const std::string TT = llvm::sys::getProcessTriple();
+    std::string error;
+    const llvm::Target *const TheTarget =
+        llvm::TargetRegistry::lookupTarget(TT, error);
+    assert(TheTarget);
+    MCRegInfo.reset(TheTarget->createMCRegInfo(TT));
+  }
+
+  static void SetUpTestCase() { llvm::InitializeNativeTarget(); }
+
+  const llvm::MCRegisterInfo &getMCRegInfo() { return *MCRegInfo; }
+
+private:
+  std::unique_ptr<const llvm::MCRegisterInfo> MCRegInfo;
+};
+
+TEST_F(RegisterAliasingTest, TrackSimpleRegister) {
+  const auto &RegInfo = getMCRegInfo();
+  const RegisterAliasingTracker tracker(RegInfo, llvm::X86::EAX);
+  const std::set<llvm::MCPhysReg> ActualAliasedRegisters(
+      tracker.aliasedBits().set_bits().begin(),
+      tracker.aliasedBits().set_bits().end());
+  const std::set<llvm::MCPhysReg> ExpectedAliasedRegisters = {
+      llvm::X86::AL,  llvm::X86::AH,  llvm::X86::AX,
+      llvm::X86::EAX, llvm::X86::HAX, llvm::X86::RAX};
+  ASSERT_THAT(ActualAliasedRegisters, ExpectedAliasedRegisters);
+  for (llvm::MCPhysReg aliased : ExpectedAliasedRegisters) {
+    ASSERT_THAT(tracker.getOrigin(aliased), llvm::X86::EAX);
+  }
+}
+
+TEST_F(RegisterAliasingTest, TrackRegisterClass) {
+  // The alias bits for GR8_ABCD_LRegClassID are the union of the alias bits for
+  // AL, BL, CL and DL.
+  const auto &RegInfo = getMCRegInfo();
+  const llvm::BitVector NoReservedReg(RegInfo.getNumRegs());
+
+  const RegisterAliasingTracker RegClassTracker(
+      RegInfo, NoReservedReg,
+      RegInfo.getRegClass(llvm::X86::GR8_ABCD_LRegClassID));
+
+  llvm::BitVector sum(RegInfo.getNumRegs());
+  sum |= RegisterAliasingTracker(RegInfo, llvm::X86::AL).aliasedBits();
+  sum |= RegisterAliasingTracker(RegInfo, llvm::X86::BL).aliasedBits();
+  sum |= RegisterAliasingTracker(RegInfo, llvm::X86::CL).aliasedBits();
+  sum |= RegisterAliasingTracker(RegInfo, llvm::X86::DL).aliasedBits();
+
+  ASSERT_THAT(RegClassTracker.aliasedBits(), sum);
+}
+
+TEST_F(RegisterAliasingTest, TrackRegisterClassCache) {
+  // Fetching twice the same tracker yields the same pointers.
+  const auto &RegInfo = getMCRegInfo();
+  const llvm::BitVector NoReservedReg(RegInfo.getNumRegs());
+  RegisterAliasingTrackerCache Cache(RegInfo, NoReservedReg);
+  ASSERT_THAT(&Cache.getRegister(llvm::X86::AX),
+              &Cache.getRegister(llvm::X86::AX));
+
+  ASSERT_THAT(&Cache.getRegisterClass(llvm::X86::GR8_ABCD_LRegClassID),
+              &Cache.getRegisterClass(llvm::X86::GR8_ABCD_LRegClassID));
+}
+
+} // namespace
+} // namespace exegesis