Index: tools/llvm-exegesis/lib/Assembler.h
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/Assembler.h
@@ -0,0 +1,78 @@
+//===-- 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 TM.
+// 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
Index: tools/llvm-exegesis/lib/Assembler.cpp
===================================================================
--- tools/llvm-exegesis/lib/Assembler.cpp
+++ tools/llvm-exegesis/lib/Assembler.cpp
@@ -1,4 +1,4 @@
-//===-- InMemoryAssembler.cpp -----------------------------------*- C++ -*-===//
+//===-- Assembler.cpp -------------------------------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
@@ -7,9 +7,8 @@
//
//===----------------------------------------------------------------------===//
-#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"
@@ -17,20 +16,11 @@
#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 {
@@ -73,47 +63,6 @@
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();
@@ -152,6 +101,97 @@
}
}
+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
@@ -175,57 +215,31 @@
} // 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)),
Index: tools/llvm-exegesis/lib/BenchmarkResult.h
===================================================================
--- tools/llvm-exegesis/lib/BenchmarkResult.h
+++ tools/llvm-exegesis/lib/BenchmarkResult.h
@@ -43,9 +43,14 @@
std::string Error;
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);
};
Index: tools/llvm-exegesis/lib/BenchmarkResult.cpp
===================================================================
--- tools/llvm-exegesis/lib/BenchmarkResult.cpp
+++ tools/llvm-exegesis/lib/BenchmarkResult.cpp
@@ -58,10 +58,8 @@
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);
@@ -70,8 +68,6 @@
return Benchmark;
}
-} // namespace
-
InstructionBenchmark
InstructionBenchmark::readYamlOrDie(llvm::StringRef Filename) {
return readYamlOrDieCommon<InstructionBenchmark>(Filename);
@@ -82,19 +78,26 @@
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);
}
}
Index: tools/llvm-exegesis/lib/BenchmarkRunner.h
===================================================================
--- tools/llvm-exegesis/lib/BenchmarkRunner.h
+++ tools/llvm-exegesis/lib/BenchmarkRunner.h
@@ -16,9 +16,10 @@
#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>
@@ -28,6 +29,8 @@
// 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 {
@@ -42,21 +45,29 @@
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(AliasingTrackerCache &ATC, 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;
+
+ AliasingTrackerCache ATC;
};
} // namespace exegesis
Index: tools/llvm-exegesis/lib/BenchmarkRunner.cpp
===================================================================
--- tools/llvm-exegesis/lib/BenchmarkRunner.cpp
+++ tools/llvm-exegesis/lib/BenchmarkRunner.cpp
@@ -7,23 +7,33 @@
//
//===----------------------------------------------------------------------===//
+#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()),
+ ATC(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.AsmTmpl.Name =
@@ -44,36 +54,49 @@
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::Expected<std::vector<llvm::MCInst>> SnippetOrError =
+ createSnippet(ATC, Opcode, llvm::outs());
+ 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::vector<llvm::MCInst> Code;
+ for (int I = 0; I < InstrBenchmark.NumRepetitions; ++I)
+ Code.push_back(Snippet[I % Snippet.size()]);
- 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));
+ auto ExpectedObjectPath = writeObjectFile(Code);
+ if (llvm::Error E = ExpectedObjectPath.takeError()) {
+ InstrBenchmark.Error = llvm::toString(std::move(E));
+ return InstrBenchmark;
}
- llvm::outs() << "# Asm excerpt: " << AsmExcerpt << "\n";
- llvm::outs().flush(); // In case we crash.
- InstrBenchmark.Measurements =
- runMeasurements(State, Function, NumRepetitions);
+ // 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
Index: tools/llvm-exegesis/lib/CMakeLists.txt
===================================================================
--- tools/llvm-exegesis/lib/CMakeLists.txt
+++ tools/llvm-exegesis/lib/CMakeLists.txt
@@ -1,14 +1,14 @@
add_library(LLVMExegesis
STATIC
+ 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
)
Index: tools/llvm-exegesis/lib/InMemoryAssembler.h
===================================================================
--- tools/llvm-exegesis/lib/InMemoryAssembler.h
+++ /dev/null
@@ -1,82 +0,0 @@
-//===-- 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
Index: tools/llvm-exegesis/lib/InstructionSnippetGenerator.h
===================================================================
--- tools/llvm-exegesis/lib/InstructionSnippetGenerator.h
+++ /dev/null
@@ -1,119 +0,0 @@
-//===-- 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
Index: tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp
===================================================================
--- tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp
+++ /dev/null
@@ -1,355 +0,0 @@
-//===-- 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
Index: tools/llvm-exegesis/lib/Latency.h
===================================================================
--- tools/llvm-exegesis/lib/Latency.h
+++ tools/llvm-exegesis/lib/Latency.h
@@ -21,19 +21,19 @@
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(AliasingTrackerCache &ATC, unsigned OpcodeIndex,
+ llvm::raw_ostream &Debug) 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
Index: tools/llvm-exegesis/lib/Latency.cpp
===================================================================
--- tools/llvm-exegesis/lib/Latency.cpp
+++ tools/llvm-exegesis/lib/Latency.cpp
@@ -8,25 +8,41 @@
//===----------------------------------------------------------------------===//
#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;
+ }
+ if (llvm::any_of(MCInstrDesc.operands(), HasUnknownOperand)) {
+ Error = "has unknown operands";
return true;
- case llvm::MCOI::OPERAND_IMMEDIATE:
- case llvm::MCOI::OPERAND_REGISTER:
- return false;
}
+ if (llvm::any_of(MCInstrDesc.operands(), HasMemoryOperand)) {
+ Error = "has memory operands";
+ return true;
+ }
+ return false;
}
static llvm::Error makeError(llvm::Twine Msg) {
@@ -38,39 +54,63 @@
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");
+llvm::Expected<std::vector<llvm::MCInst>>
+LatencyBenchmarkRunner::createSnippet(AliasingTrackerCache &ATC,
+ unsigned Opcode,
+ llvm::raw_ostream &Debug) const {
+ std::vector<llvm::MCInst> Snippet;
+ const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode);
+ const Instruction ThisInstruction(MCInstrDesc, ATC);
+ Debug << "Operands " << ThisInstruction.Operands.size() << "\n";
+ Debug << "Variables " << ThisInstruction.Variables.size() << "\n";
+
+ std::string Error;
+ if (IsInfeasible(ThisInstruction, Error))
+ return makeError(llvm::Twine("Infeasible : ").concat(Error));
+
+ const AliasingConfigurations SelfAliasing(ThisInstruction, ThisInstruction);
+ Debug << "hasImplicitAliasing " << SelfAliasing.hasImplicitAliasing() << "\n";
+ if (!SelfAliasing.empty()) {
+ if (!SelfAliasing.hasImplicitAliasing()) {
+ Debug << "Explicit Self cycles\n";
+ setRandomAliasing(SelfAliasing);
+ } else {
+ Debug << "Implicit Self cycles\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), ATC);
+ 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);
+ Debug << "Cycle through " << MCInstrInfo.getName(OtherOpcode) << "\n";
+ Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction));
+ Snippet.push_back(randomizeUnsetVariablesAndBuild(OtherInstruction));
+ return Snippet;
}
- 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);
+ 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.
Index: tools/llvm-exegesis/lib/LlvmState.h
===================================================================
--- tools/llvm-exegesis/lib/LlvmState.h
+++ tools/llvm-exegesis/lib/LlvmState.h
@@ -6,6 +6,11 @@
// 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
Index: tools/llvm-exegesis/lib/MCInstrDescView.h
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/MCInstrDescView.h
@@ -0,0 +1,145 @@
+//===-- 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 AliasingTracker *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> Variable; // 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, AliasingTrackerCache &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)
+ : Operand(Operand), Reg(Reg) {}
+
+ const Operand *Operand; // 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.
+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.
+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
Index: tools/llvm-exegesis/lib/MCInstrDescView.cpp
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/MCInstrDescView.cpp
@@ -0,0 +1,266 @@
+#include "MCInstrDescView.h"
+
+#include <iterator>
+#include <map>
+#include <tuple>
+
+#include "llvm/ADT/STLExtras.h"
+
+namespace exegesis {
+
+namespace {
+
+void Tie(const Operand *FromOperand, llvm::Optional<Variable> &Variable) {
+ if (!Variable)
+ Variable.emplace();
+ Variable->TiedOperands.push_back(FromOperand);
+}
+
+} // namespace
+
+Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc,
+ AliasingTrackerCache &ATC)
+ : 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 = &ATC.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 = &ATC.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 = &ATC.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].Variable);
+ } else {
+ Tie(&Op, Op.Variable);
+ }
+ }
+ }
+ for (auto &Op : Operands) {
+ if (Op.Variable) {
+ Variables.push_back(&*Op.Variable);
+ }
+ }
+ // Processing Aliasing.
+ DefRegisters = ATC.emptyRegisters();
+ UseRegisters = ATC.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(Operand, Reg) == std::tie(Other.Operand, Other.Reg);
+}
+
+bool AliasingRegisterOperands::
+operator==(const AliasingRegisterOperands &Other) const {
+ return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses);
+}
+
+namespace {
+
+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);
+ }
+ }
+}
+
+} // namespace
+
+bool AliasingRegisterOperands::hasImplicitAliasing() const {
+ const auto HasImplicit = [](const RegisterOperandAssignment &ROV) {
+ return !ROV.Operand->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 &Variable) {
+ assert(!Variable.TiedOperands.empty());
+ assert(Variable.TiedOperands.front() != nullptr);
+ const Operand &Op = *Variable.TiedOperands.front();
+ assert(Op.Info != nullptr);
+ const auto &OpInfo = *Op.Info;
+ switch (OpInfo.OperandType) {
+ case llvm::MCOI::OperandType::OPERAND_IMMEDIATE:
+ Variable.AssignedValue = llvm::MCOperand::createImm(1);
+ break;
+ case llvm::MCOI::OperandType::OPERAND_REGISTER: {
+ assert(Op.Tracker);
+ const auto &Registers = Op.Tracker->sourceBits();
+ Variable.AssignedValue = llvm::MCOperand::createReg(randomBit(Registers));
+ break;
+ }
+ default:
+ break;
+ }
+}
+
+static void setRegisterOperandValue(const RegisterOperandAssignment &ROV) {
+ const Operand *Op = ROV.Operand->TiedTo ? ROV.Operand->TiedTo : ROV.Operand;
+ assert(Op->Variable);
+ auto &AssignedValue = Op->Variable->AssignedValue;
+ if (AssignedValue.isValid()) {
+ assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
+ return;
+ }
+ Op->Variable->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 *Variable : Instruction.Variables)
+ if (!Variable->AssignedValue.isValid())
+ randomize(*Variable);
+}
+
+void clearVariableAssignments(const Instruction &Instruction) {
+ for (auto *Variable : Instruction.Variables)
+ Variable->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 &Variable = Op.TiedTo ? Op.TiedTo->Variable : Op.Variable;
+ assert(Variable);
+ Result.addOperand(Variable->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
Index: tools/llvm-exegesis/lib/OperandGraph.h
===================================================================
--- tools/llvm-exegesis/lib/OperandGraph.h
+++ /dev/null
@@ -1,89 +0,0 @@
-//===-- 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
Index: tools/llvm-exegesis/lib/OperandGraph.cpp
===================================================================
--- tools/llvm-exegesis/lib/OperandGraph.cpp
+++ /dev/null
@@ -1,115 +0,0 @@
-//===-- 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
Index: tools/llvm-exegesis/lib/RegisterAliasing.h
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/RegisterAliasing.h
@@ -0,0 +1,106 @@
+//===-- AliasingTracker.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.
+// AliasingTracker 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 AliasingTracker {
+ // Construct a tracker from an MCRegisterClass.
+ AliasingTracker(const llvm::MCRegisterInfo &RegInfo,
+ const llvm::BitVector &ReservedReg,
+ const llvm::MCRegisterClass &RegClass);
+
+ // Construct a tracker from an MCPhysReg.
+ AliasingTracker(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:
+ AliasingTracker(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 AliasingTrackerCache {
+ // RegInfo must outlive the cache.
+ AliasingTrackerCache(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 ®Info() const { return RegInfo; }
+
+ // Retrieves the AliasingTracker for this particular register.
+ const AliasingTracker &getRegister(llvm::MCPhysReg Reg);
+
+ // Retrieves the AliasingTracker for this particular register class.
+ const AliasingTracker &getRegisterClass(unsigned RegClassIndex);
+
+private:
+ const llvm::MCRegisterInfo &RegInfo;
+ const llvm::BitVector ReservedReg;
+ const llvm::BitVector EmptyRegisters;
+ std::unordered_map<unsigned, std::unique_ptr<AliasingTracker>> Registers;
+ std::unordered_map<unsigned, std::unique_ptr<AliasingTracker>>
+ RegisterClasses;
+};
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
Index: tools/llvm-exegesis/lib/RegisterAliasing.cpp
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/RegisterAliasing.cpp
@@ -0,0 +1,73 @@
+#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;
+}
+
+AliasingTracker::AliasingTracker(const llvm::MCRegisterInfo &RegInfo)
+ : SourceBits(RegInfo.getNumRegs()), AliasedBits(RegInfo.getNumRegs()),
+ Origins(RegInfo.getNumRegs()) {}
+
+AliasingTracker::AliasingTracker(const llvm::MCRegisterInfo &RegInfo,
+ const llvm::BitVector &ReservedReg,
+ const llvm::MCRegisterClass &RegClass)
+ : AliasingTracker(RegInfo) {
+ for (llvm::MCPhysReg PhysReg : RegClass)
+ if (!ReservedReg[PhysReg]) // Removing reserved registers.
+ SourceBits.set(PhysReg);
+ FillOriginAndAliasedBits(RegInfo, SourceBits);
+}
+
+AliasingTracker::AliasingTracker(const llvm::MCRegisterInfo &RegInfo,
+ const llvm::MCPhysReg PhysReg)
+ : AliasingTracker(RegInfo) {
+ SourceBits.set(PhysReg);
+ FillOriginAndAliasedBits(RegInfo, SourceBits);
+}
+
+void AliasingTracker::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;
+ }
+ }
+}
+
+AliasingTrackerCache::AliasingTrackerCache(const llvm::MCRegisterInfo &RegInfo,
+ const llvm::BitVector &ReservedReg)
+ : RegInfo(RegInfo), ReservedReg(ReservedReg),
+ EmptyRegisters(RegInfo.getNumRegs()) {}
+
+const AliasingTracker &
+AliasingTrackerCache::getRegister(llvm::MCPhysReg PhysReg) {
+ auto &Found = Registers[PhysReg];
+ if (!Found)
+ Found.reset(new AliasingTracker(RegInfo, PhysReg));
+ return *Found;
+}
+
+const AliasingTracker &
+AliasingTrackerCache::getRegisterClass(unsigned RegClassIndex) {
+ auto &Found = RegisterClasses[RegClassIndex];
+ const auto &RegClass = RegInfo.getRegClass(RegClassIndex);
+ if (!Found)
+ Found.reset(new AliasingTracker(RegInfo, ReservedReg, RegClass));
+ return *Found;
+}
+
+} // namespace exegesis
Index: tools/llvm-exegesis/lib/Uops.h
===================================================================
--- tools/llvm-exegesis/lib/Uops.h
+++ tools/llvm-exegesis/lib/Uops.h
@@ -21,19 +21,19 @@
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(AliasingTrackerCache &ATC, unsigned Opcode,
+ llvm::raw_ostream &Debug) 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
Index: tools/llvm-exegesis/lib/Uops.cpp
===================================================================
--- tools/llvm-exegesis/lib/Uops.cpp
+++ tools/llvm-exegesis/lib/Uops.cpp
@@ -8,183 +8,215 @@
//===----------------------------------------------------------------------===//
#include "Uops.h"
-#include "BenchmarkResult.h"
-#include "InstructionSnippetGenerator.h"
+
+#include "Assembler.h"
+#include "BenchmarkRunner.h"
+#include "MCInstrDescView.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>
+
+// 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.
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;
- }
+namespace {
+
+bool HasUnknownOperand(const llvm::MCOperandInfo &OpInfo) {
+ return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN;
}
-static llvm::Error makeError(llvm::Twine Msg) {
- return llvm::make_error<llvm::StringError>(Msg,
- llvm::inconvertibleErrorCode());
+// FIXME: Handle memory, see PR36905.
+bool HasMemoryOperand(const llvm::MCOperandInfo &OpInfo) {
+ return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY;
}
-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());
- }
+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;
+}
- 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));
+// Returns whether this Variable ties Use and Def operands together.
+bool HasTiedOperands(const Variable *Variable) {
+ bool HasUse = false;
+ bool HasDef = false;
+ for (const Operand *Op : Variable->TiedOperands) {
+ if (Op->IsDef)
+ HasDef = true;
+ else
+ HasUse = true;
}
- return Pattern;
+ return HasUse && HasDef;
}
+llvm::SmallVector<Variable *, 8>
+GetTiedVariables(const Instruction &Instruction) {
+ llvm::SmallVector<Variable *, 8> Result;
+ for (auto *Variable : Instruction.Variables)
+ if (HasTiedOperands(Variable))
+ Result.push_back(Variable);
+ return Result;
+}
+
+void Remove(llvm::BitVector &a, const llvm::BitVector &b) {
+ assert(a.size() == b.size());
+ for (auto I : b.set_bits())
+ a.reset(I);
+}
+
+} // namespace
+
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");
+llvm::Expected<std::vector<llvm::MCInst>>
+UopsBenchmarkRunner::createSnippet(AliasingTrackerCache &ATC, unsigned Opcode,
+ llvm::raw_ostream &Debug) const {
+ std::vector<llvm::MCInst> Snippet;
+ const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode);
+ const Instruction Instruction(MCInstrDesc, ATC);
+ Debug << "Operands " << Instruction.Operands.size() << "\n";
+ Debug << "Variables " << Instruction.Variables.size() << "\n";
+
+ std::string Error;
+ if (IsInfeasible(Instruction, Error)) {
+ llvm::report_fatal_error(llvm::Twine("Infeasible : ").concat(Error));
}
- // 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.
-
- const auto Vars = getVariables(RegInfo, InstrDesc, Context.getReservedRegs());
-
- // 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));
+ const AliasingConfigurations SelfAliasing(Instruction, Instruction);
+ if (SelfAliasing.empty()) {
+ Debug << "Instruction is parallel :)\n";
+ Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+ return Snippet;
}
-
- // 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()]);
- return Result;
+ if (SelfAliasing.hasImplicitAliasing()) {
+ Debug << "Instruction is serial :(\n";
+ Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction));
+ return Snippet;
+ }
+ const auto TiedVariables = GetTiedVariables(Instruction);
+ if (!TiedVariables.empty()) {
+ assert(TiedVariables.size() == 1 &&
+ "Don't know how to handle several tied variables");
+ Debug << "Static renaming\n";
+ Variable *Variable = TiedVariables.front();
+ assert(Variable);
+ assert(!Variable->TiedOperands.empty());
+ const Operand &Operand = *Variable->TiedOperands.front();
+ assert(Operand.Tracker);
+ for (const llvm::MCPhysReg Reg : Operand.Tracker->sourceBits().set_bits()) {
+ clearVariableAssignments(Instruction);
+ Variable->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.Variable);
+ auto PossibleRegisters = Op.Tracker->sourceBits();
+ Remove(PossibleRegisters, ATC.reservedRegisters());
+ assert(PossibleRegisters.any() && "No register left to choose from");
+ const auto RandomReg = randomBit(PossibleRegisters);
+ Defs.set(RandomReg);
+ Op.Variable->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.Variable);
+ auto PossibleRegisters = Op.Tracker->sourceBits();
+ Remove(PossibleRegisters, ATC.reservedRegisters());
+ Remove(PossibleRegisters, DefAliases);
+ assert(PossibleRegisters.any() && "No register left to choose from");
+ const auto RandomReg = randomBit(PossibleRegisters);
+ Op.Variable->AssignedValue = llvm::MCOperand::createReg(RandomReg);
+ }
+ }
+ Debug << "Pick Use different than def\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();
@@ -195,9 +227,14 @@
.PfmCounters.IssueCounters[ProcResIdx];
if (!PfmCounters)
continue;
- // FIXME: Sum results when there are several counters for a single ProcRes
+ // 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();
Index: tools/llvm-exegesis/llvm-exegesis.cpp
===================================================================
--- tools/llvm-exegesis/llvm-exegesis.cpp
+++ tools/llvm-exegesis/llvm-exegesis.cpp
@@ -54,11 +54,24 @@
namespace exegesis {
-void main() {
- if (OpcodeName.empty() == (OpcodeIndex == 0)) {
+namespace {
+
+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));
+}
+
+} // namespace
+
+void main() {
llvm::InitializeNativeTarget();
llvm::InitializeNativeTargetAsmPrinter();
@@ -68,35 +81,24 @@
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;
}
- 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("-");
}
Index: unittests/tools/llvm-exegesis/CMakeLists.txt
===================================================================
--- unittests/tools/llvm-exegesis/CMakeLists.txt
+++ unittests/tools/llvm-exegesis/CMakeLists.txt
@@ -13,7 +13,6 @@
add_llvm_unittest(LLVMExegesisTests
BenchmarkResultTest.cpp
ClusteringTest.cpp
- OperandGraphTest.cpp
PerfHelperTest.cpp
)
target_link_libraries(LLVMExegesisTests PRIVATE LLVMExegesis)
Index: unittests/tools/llvm-exegesis/OperandGraphTest.cpp
===================================================================
--- unittests/tools/llvm-exegesis/OperandGraphTest.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-//===-- 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
Index: unittests/tools/llvm-exegesis/X86/CMakeLists.txt
===================================================================
--- unittests/tools/llvm-exegesis/X86/CMakeLists.txt
+++ unittests/tools/llvm-exegesis/X86/CMakeLists.txt
@@ -14,8 +14,7 @@
)
add_llvm_unittest(LLVMExegesisX86Tests
+ RegisterAliasingTest.cpp
InMemoryAssemblerTest.cpp
- InstructionSnippetGeneratorTest.cpp
)
target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis)
-
Index: unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp
===================================================================
--- unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp
+++ unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp
@@ -7,7 +7,7 @@
//
//===----------------------------------------------------------------------===//
-#include "InMemoryAssembler.h"
+#include "Assembler.h"
#include "X86InstrInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -51,8 +51,8 @@
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(
+ TT, CpuName, "", Options, llvm::Reloc::Model::Static);
EXPECT_TRUE(TM) << TT << " " << CpuName;
return std::unique_ptr<llvm::LLVMTargetMachine>(
static_cast<llvm::LLVMTargetMachine *>(TM));
@@ -62,58 +62,66 @@
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
Index: unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp
===================================================================
--- unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp
+++ /dev/null
@@ -1,309 +0,0 @@
-//===-- 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
Index: unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp
===================================================================
--- /dev/null
+++ unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp
@@ -0,0 +1,82 @@
+#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 AliasingTracker 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 AliasingTracker RegClassTracker(
+ RegInfo, NoReservedReg,
+ RegInfo.getRegClass(llvm::X86::GR8_ABCD_LRegClassID));
+
+ llvm::BitVector sum(RegInfo.getNumRegs());
+ sum |= AliasingTracker(RegInfo, llvm::X86::AL).aliasedBits();
+ sum |= AliasingTracker(RegInfo, llvm::X86::BL).aliasedBits();
+ sum |= AliasingTracker(RegInfo, llvm::X86::CL).aliasedBits();
+ sum |= AliasingTracker(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());
+ AliasingTrackerCache 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