diff options
28 files changed, 1526 insertions, 1328 deletions
diff --git a/llvm/tools/llvm-exegesis/lib/Assembler.h b/llvm/tools/llvm-exegesis/lib/Assembler.h deleted file mode 100644 index 932542ca504..00000000000 --- a/llvm/tools/llvm-exegesis/lib/Assembler.h +++ /dev/null @@ -1,78 +0,0 @@ -//===-- Assembler.h ---------------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// Defines classes to assemble functions composed of a single basic block of -/// MCInsts. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H -#define LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H - -#include <memory> - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineModuleInfo.h" -#include "llvm/ExecutionEngine/ExecutionEngine.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/MC/MCInst.h" -#include "llvm/Object/Binary.h" -#include "llvm/Object/ObjectFile.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetMachine.h" - -namespace exegesis { - -// Gather the set of reserved registers (depends on function's calling -// convention and target machine). -llvm::BitVector getFunctionReservedRegs(const llvm::TargetMachine &TM); - -// Creates a temporary `void foo()` function containing the provided -// Instructions. Runs a set of llvm Passes to provide correct prologue and -// epilogue. Once the MachineFunction is ready, it is assembled for TM to -// AsmStream, the temporary function is eventually discarded. -void assembleToStream(std::unique_ptr<llvm::LLVMTargetMachine> TM, - llvm::ArrayRef<llvm::MCInst> Instructions, - llvm::raw_pwrite_stream &AsmStream); - -// Creates an ObjectFile in the format understood by the host. -// Note: the resulting object keeps a copy of Buffer so it can be discarded once -// this function returns. -llvm::object::OwningBinary<llvm::object::ObjectFile> -getObjectFromBuffer(llvm::StringRef Buffer); - -// Loads the content of Filename as on ObjectFile and returns it. -llvm::object::OwningBinary<llvm::object::ObjectFile> -getObjectFromFile(llvm::StringRef Filename); - -// Consumes an ObjectFile containing a `void foo()` function and make it -// executable. -struct ExecutableFunction { - explicit ExecutableFunction( - std::unique_ptr<llvm::LLVMTargetMachine> TM, - llvm::object::OwningBinary<llvm::object::ObjectFile> &&ObjectFileHolder); - - // Retrieves the function as an array of bytes. - llvm::StringRef getFunctionBytes() const { return FunctionBytes; } - - // Executes the function. - void operator()() const { ((void (*)())(intptr_t)FunctionBytes.data())(); } - - std::unique_ptr<llvm::LLVMContext> Context; - std::unique_ptr<llvm::ExecutionEngine> ExecEngine; - llvm::StringRef FunctionBytes; -}; - -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H diff --git a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.cpp b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.cpp index b1083f4ed0a..a043ea40c27 100644 --- a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.cpp +++ b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.cpp @@ -61,8 +61,10 @@ LLVM_YAML_IS_DOCUMENT_LIST_VECTOR(exegesis::InstructionBenchmark) namespace exegesis { +namespace { + template <typename ObjectOrList> -static ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) { +ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) { std::unique_ptr<llvm::MemoryBuffer> MemBuffer = llvm::cantFail( llvm::errorOrToExpected(llvm::MemoryBuffer::getFile(Filename))); llvm::yaml::Input Yin(*MemBuffer); @@ -71,6 +73,8 @@ static ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) { return Benchmark; } +} // namespace + InstructionBenchmark InstructionBenchmark::readYamlOrDie(llvm::StringRef Filename) { return readYamlOrDieCommon<InstructionBenchmark>(Filename); @@ -81,26 +85,19 @@ InstructionBenchmark::readYamlsOrDie(llvm::StringRef Filename) { return readYamlOrDieCommon<std::vector<InstructionBenchmark>>(Filename); } -void InstructionBenchmark::writeYamlTo(llvm::raw_ostream &S) { - llvm::yaml::Output Yout(S); - Yout << *this; -} - -void InstructionBenchmark::readYamlFrom(llvm::StringRef InputContent) { - llvm::yaml::Input Yin(InputContent); - Yin >> *this; -} - -// FIXME: Change the API to let the caller handle errors. void InstructionBenchmark::writeYamlOrDie(const llvm::StringRef Filename) { if (Filename == "-") { - writeYamlTo(llvm::outs()); + llvm::yaml::Output Yout(llvm::outs()); + Yout << *this; } else { - 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); + 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()); } } diff --git a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h index 3a7d241dbd0..cf9bcece99a 100644 --- a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h +++ b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h @@ -50,14 +50,9 @@ struct InstructionBenchmark { std::string Info; static InstructionBenchmark readYamlOrDie(llvm::StringRef Filename); - static std::vector<InstructionBenchmark> + static std::vector<InstructionBenchmark> readYamlsOrDie(llvm::StringRef Filename); - // 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); + // Unfortunately this function is non const because of YAML traits. void writeYamlOrDie(const llvm::StringRef Filename); }; diff --git a/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp b/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp index 0e2052f82cc..2615a829902 100644 --- a/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp +++ b/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.cpp @@ -7,33 +7,23 @@ // //===----------------------------------------------------------------------===// -#include <array> -#include <string> - -#include "Assembler.h" #include "BenchmarkRunner.h" -#include "MCInstrDescView.h" +#include "InMemoryAssembler.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" -#include "llvm/Support/FileSystem.h" -#include "llvm/Support/FormatVariadic.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/Support/Program.h" +#include <string> namespace exegesis { BenchmarkRunner::InstructionFilter::~InstructionFilter() = default; -BenchmarkRunner::BenchmarkRunner(const LLVMState &State) - : State(State), MCInstrInfo(State.getInstrInfo()), - MCRegisterInfo(State.getRegInfo()), - RATC(MCRegisterInfo, - getFunctionReservedRegs(*State.createTargetMachine())) {} + BenchmarkRunner::~BenchmarkRunner() = default; -InstructionBenchmark BenchmarkRunner::run(unsigned Opcode, - const InstructionFilter &Filter, - unsigned NumRepetitions) { +InstructionBenchmark +BenchmarkRunner::run(const LLVMState &State, const unsigned Opcode, + unsigned NumRepetitions, + const InstructionFilter &Filter) const { InstructionBenchmark InstrBenchmark; InstrBenchmark.Key.OpcodeName = State.getInstrInfo().getName(Opcode); @@ -51,56 +41,36 @@ InstructionBenchmark BenchmarkRunner::run(unsigned Opcode, InstrBenchmark.Error = llvm::toString(std::move(E)); return InstrBenchmark; } - llvm::raw_string_ostream InfoStream(InstrBenchmark.Info); - llvm::Expected<std::vector<llvm::MCInst>> SnippetOrError = - createSnippet(RATC, Opcode, InfoStream); - if (llvm::Error E = SnippetOrError.takeError()) { + + JitFunctionContext Context(State.createTargetMachine()); + auto ExpectedInstructions = + createCode(State, Opcode, NumRepetitions, Context); + if (llvm::Error E = ExpectedInstructions.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; - } - InfoStream << "Snippet:\n"; - for (const auto &MCInst : Snippet) { - DumpMCInst(MCRegisterInfo, MCInstrInfo, MCInst, InfoStream); - InfoStream << "\n"; - } - - std::vector<llvm::MCInst> Code; - for (int I = 0; I < InstrBenchmark.NumRepetitions; ++I) - Code.push_back(Snippet[I % Snippet.size()]); + const std::vector<llvm::MCInst> Instructions = *ExpectedInstructions; + const JitFunction Function(std::move(Context), Instructions); + const llvm::StringRef CodeBytes = Function.getFunctionBytes(); - auto ExpectedObjectPath = writeObjectFile(Code); - if (llvm::Error E = ExpectedObjectPath.takeError()) { - InstrBenchmark.Error = llvm::toString(std::move(E)); - return InstrBenchmark; + 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)); } + llvm::outs() << "# Asm excerpt: " << AsmExcerpt << "\n"; + llvm::outs().flush(); // In case we crash. - // 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); - + InstrBenchmark.Measurements = + runMeasurements(State, Function, 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 diff --git a/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h b/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h index 679436a2cf7..715ad5884c1 100644 --- a/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h +++ b/llvm/tools/llvm-exegesis/lib/BenchmarkRunner.h @@ -16,10 +16,9 @@ #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> @@ -29,8 +28,6 @@ namespace exegesis { // Common code for all benchmark modes. class BenchmarkRunner { public: - explicit BenchmarkRunner(const LLVMState &State); - // Subtargets can disable running benchmarks for some instructions by // returning an error here. class InstructionFilter { @@ -45,29 +42,21 @@ public: virtual ~BenchmarkRunner(); - InstructionBenchmark run(unsigned Opcode, const InstructionFilter &Filter, - unsigned NumRepetitions); - -protected: - const LLVMState &State; - const llvm::MCInstrInfo &MCInstrInfo; - const llvm::MCRegisterInfo &MCRegisterInfo; + InstructionBenchmark run(const LLVMState &State, unsigned Opcode, + unsigned NumRepetitions, + const InstructionFilter &Filter) const; private: virtual const char *getDisplayName() const = 0; virtual llvm::Expected<std::vector<llvm::MCInst>> - createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode, - llvm::raw_ostream &Debug) const = 0; + createCode(const LLVMState &State, unsigned OpcodeIndex, + unsigned NumRepetitions, + const JitFunctionContext &Context) const = 0; virtual std::vector<BenchmarkMeasure> - runMeasurements(const ExecutableFunction &EF, - const unsigned NumRepetitions) const = 0; - - llvm::Expected<std::string> - writeObjectFile(llvm::ArrayRef<llvm::MCInst> Code) const; - - RegisterAliasingTrackerCache RATC; + runMeasurements(const LLVMState &State, const JitFunction &Function, + unsigned NumRepetitions) const = 0; }; } // namespace exegesis diff --git a/llvm/tools/llvm-exegesis/lib/CMakeLists.txt b/llvm/tools/llvm-exegesis/lib/CMakeLists.txt index b326757fb6b..fae0bcda953 100644 --- a/llvm/tools/llvm-exegesis/lib/CMakeLists.txt +++ b/llvm/tools/llvm-exegesis/lib/CMakeLists.txt @@ -1,15 +1,15 @@ add_library(LLVMExegesis STATIC Analysis.cpp - Assembler.cpp BenchmarkResult.cpp BenchmarkRunner.cpp Clustering.cpp + InMemoryAssembler.cpp + InstructionSnippetGenerator.cpp Latency.cpp LlvmState.cpp - MCInstrDescView.cpp + OperandGraph.cpp PerfHelper.cpp - RegisterAliasing.cpp Uops.cpp X86.cpp ) diff --git a/llvm/tools/llvm-exegesis/lib/Assembler.cpp b/llvm/tools/llvm-exegesis/lib/InMemoryAssembler.cpp index 81185064eef..317a59d6e96 100644 --- a/llvm/tools/llvm-exegesis/lib/Assembler.cpp +++ b/llvm/tools/llvm-exegesis/lib/InMemoryAssembler.cpp @@ -1,4 +1,4 @@ -//===-- Assembler.cpp -------------------------------------------*- C++ -*-===// +//===-- InMemoryAssembler.cpp -----------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -7,8 +7,9 @@ // //===----------------------------------------------------------------------===// -#include "Assembler.h" - +#include "InMemoryAssembler.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" #include "llvm/CodeGen/GlobalISel/CallLowering.h" #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -16,11 +17,20 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetPassConfig.h" -#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/ExecutionEngine/ExecutionEngine.h" +#include "llvm/ExecutionEngine/MCJIT.h" #include "llvm/ExecutionEngine/SectionMemoryManager.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LegacyPassManager.h" -#include "llvm/MC/MCInstrInfo.h" -#include "llvm/Support/MemoryBuffer.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" namespace exegesis { @@ -63,6 +73,47 @@ createVoidVoidMachineFunction(llvm::StringRef FunctionID, llvm::Module *Module, 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(); @@ -101,97 +152,6 @@ static void fillMachineFunction(llvm::MachineFunction &MF, } } -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 @@ -215,31 +175,57 @@ private: } // namespace -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"); +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"); // 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(createModule(Context, TM->createDataLayout())) + llvm::EngineBuilder(std::move(FunctionContext.Module)) .setErrorStr(&Error) .setMCPU(TM->getTargetCPU()) .setEngineKind(llvm::EngineKind::JIT) .setMCJITMemoryManager( llvm::make_unique<TrackingSectionMemoryManager>(&CodeSize)) - .create(TM.release())); + .create(TM)); 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(ObjectFileHolder)); - // Fetching function bytes. + ExecEngine->addObjectFile(std::move(ObjHolder)); + // Setting function FunctionBytes = llvm::StringRef(reinterpret_cast<const char *>( ExecEngine->getFunctionAddress(FunctionID)), diff --git a/llvm/tools/llvm-exegesis/lib/InMemoryAssembler.h b/llvm/tools/llvm-exegesis/lib/InMemoryAssembler.h new file mode 100644 index 00000000000..51b555f5453 --- /dev/null +++ b/llvm/tools/llvm-exegesis/lib/InMemoryAssembler.h @@ -0,0 +1,82 @@ +//===-- 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 diff --git a/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp new file mode 100644 index 00000000000..2ab3379faed --- /dev/null +++ b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp @@ -0,0 +1,355 @@ +//===-- 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 diff --git a/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h new file mode 100644 index 00000000000..be21f8725ad --- /dev/null +++ b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h @@ -0,0 +1,119 @@ +//===-- 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 diff --git a/llvm/tools/llvm-exegesis/lib/Latency.cpp b/llvm/tools/llvm-exegesis/lib/Latency.cpp index 4233345aba0..4a2632c7b5c 100644 --- a/llvm/tools/llvm-exegesis/lib/Latency.cpp +++ b/llvm/tools/llvm-exegesis/lib/Latency.cpp @@ -8,41 +8,25 @@ //===----------------------------------------------------------------------===// #include "Latency.h" - -#include "Assembler.h" -#include "BenchmarkRunner.h" -#include "MCInstrDescView.h" +#include "BenchmarkResult.h" +#include "InstructionSnippetGenerator.h" #include "PerfHelper.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/MC/MCInst.h" -#include "llvm/MC/MCInstBuilder.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/Support/Error.h" +#include <algorithm> +#include <random> namespace exegesis { -static bool HasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { - return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN; -} - // FIXME: Handle memory, see PR36905. -static bool HasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { - return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; -} - -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"; +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; } - if (llvm::any_of(MCInstrDesc.operands(), HasMemoryOperand)) { - Error = "has memory operands"; - return true; - } - return false; } static llvm::Error makeError(llvm::Twine Msg) { @@ -54,61 +38,39 @@ LatencyBenchmarkRunner::~LatencyBenchmarkRunner() = default; const char *LatencyBenchmarkRunner::getDisplayName() const { return "latency"; } -llvm::Expected<std::vector<llvm::MCInst>> -LatencyBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC, - unsigned Opcode, - llvm::raw_ostream &Info) const { - std::vector<llvm::MCInst> Snippet; - const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode); - const Instruction ThisInstruction(MCInstrDesc, RATC); - - std::string Error; - if (IsInfeasible(ThisInstruction, Error)) - return makeError(llvm::Twine("Infeasible : ").concat(Error)); - - const AliasingConfigurations SelfAliasing(ThisInstruction, ThisInstruction); - if (!SelfAliasing.empty()) { - if (!SelfAliasing.hasImplicitAliasing()) { - Info << "explicit self cycles, selecting one aliasing configuration.\n"; - setRandomAliasing(SelfAliasing); - } else { - Info << "implicit Self cycles, picking random values.\n"; - } - Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction)); - return Snippet; - } - - // Let's try to create a dependency through another opcode. - std::vector<unsigned> Opcodes; - Opcodes.resize(MCInstrInfo.getNumOpcodes()); - std::iota(Opcodes.begin(), Opcodes.end(), 0U); - std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator()); - for (const unsigned OtherOpcode : Opcodes) { - clearVariableAssignments(ThisInstruction); - if (OtherOpcode == Opcode) - continue; - const Instruction OtherInstruction(MCInstrInfo.get(OtherOpcode), RATC); - if (IsInfeasible(OtherInstruction, Error)) - continue; - const AliasingConfigurations Forward(ThisInstruction, OtherInstruction); - const AliasingConfigurations Back(OtherInstruction, ThisInstruction); - if (Forward.empty() || Back.empty()) - continue; - setRandomAliasing(Forward); - setRandomAliasing(Back); - Info << "creating cycle through " << MCInstrInfo.getName(OtherOpcode) - << ".\n"; - Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction)); - Snippet.push_back(randomizeUnsetVariablesAndBuild(OtherInstruction)); - return Snippet; +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"); } - return makeError( - "Infeasible : Didn't find any scheme to make the instruction serial\n"); + 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); } std::vector<BenchmarkMeasure> -LatencyBenchmarkRunner::runMeasurements(const ExecutableFunction &Function, +LatencyBenchmarkRunner::runMeasurements(const LLVMState &State, + const JitFunction &Function, const unsigned NumRepetitions) const { // Cycle measurements include some overhead from the kernel. Repeat the // measure several times and take the minimum value. diff --git a/llvm/tools/llvm-exegesis/lib/Latency.h b/llvm/tools/llvm-exegesis/lib/Latency.h index f3963f0f1f9..65a1b33af50 100644 --- a/llvm/tools/llvm-exegesis/lib/Latency.h +++ b/llvm/tools/llvm-exegesis/lib/Latency.h @@ -21,19 +21,19 @@ namespace exegesis { class LatencyBenchmarkRunner : public BenchmarkRunner { public: - using BenchmarkRunner::BenchmarkRunner; ~LatencyBenchmarkRunner() override; private: const char *getDisplayName() const override; llvm::Expected<std::vector<llvm::MCInst>> - createSnippet(RegisterAliasingTrackerCache &RATC, unsigned OpcodeIndex, - llvm::raw_ostream &Info) const override; + createCode(const LLVMState &State, unsigned OpcodeIndex, + unsigned NumRepetitions, + const JitFunctionContext &Context) const override; std::vector<BenchmarkMeasure> - runMeasurements(const ExecutableFunction &EF, - const unsigned NumRepetitions) const override; + runMeasurements(const LLVMState &State, const JitFunction &Function, + unsigned NumRepetitions) const override; }; } // namespace exegesis diff --git a/llvm/tools/llvm-exegesis/lib/LlvmState.h b/llvm/tools/llvm-exegesis/lib/LlvmState.h index 6bde4f681c1..c0a9bb29d8c 100644 --- a/llvm/tools/llvm-exegesis/lib/LlvmState.h +++ b/llvm/tools/llvm-exegesis/lib/LlvmState.h @@ -6,11 +6,6 @@ // 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 diff --git a/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp b/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp deleted file mode 100644 index 268136e9e6a..00000000000 --- a/llvm/tools/llvm-exegesis/lib/MCInstrDescView.cpp +++ /dev/null @@ -1,268 +0,0 @@ -//===-- MCInstrDescView.cpp -------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "MCInstrDescView.h" - -#include <iterator> -#include <map> -#include <tuple> - -#include "llvm/ADT/STLExtras.h" - -namespace exegesis { - -static void tie(const Operand *FromOperand, llvm::Optional<Variable> &Var) { - if (!Var) - Var.emplace(); - Var->TiedOperands.push_back(FromOperand); -} - -Instruction::Instruction(const llvm::MCInstrDesc &MCInstrDesc, - RegisterAliasingTrackerCache &RATC) - : Description(MCInstrDesc) { - unsigned OpIndex = 0; - for (; OpIndex < MCInstrDesc.getNumOperands(); ++OpIndex) { - const auto &OpInfo = MCInstrDesc.opInfo_begin()[OpIndex]; - Operand Operand; - Operand.Index = OpIndex; - Operand.IsDef = (OpIndex < MCInstrDesc.getNumDefs()); - Operand.IsExplicit = true; - // TODO(gchatelet): Handle isLookupPtrRegClass. - if (OpInfo.RegClass >= 0) - Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass); - Operand.Info = &OpInfo; - Operands.push_back(Operand); - } - for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitDefs(); - MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) { - Operand Operand; - Operand.Index = OpIndex; - Operand.IsDef = true; - Operand.IsExplicit = false; - Operand.Tracker = &RATC.getRegister(*MCPhysReg); - Operand.ImplicitReg = MCPhysReg; - Operands.push_back(Operand); - } - for (const llvm::MCPhysReg *MCPhysReg = MCInstrDesc.getImplicitUses(); - MCPhysReg && *MCPhysReg; ++MCPhysReg, ++OpIndex) { - Operand Operand; - Operand.Index = OpIndex; - Operand.IsDef = false; - Operand.IsExplicit = false; - Operand.Tracker = &RATC.getRegister(*MCPhysReg); - Operand.ImplicitReg = MCPhysReg; - Operands.push_back(Operand); - } - // Set TiedTo for operands. - for (auto &Op : Operands) { - if (Op.IsExplicit) { - const int TiedTo = - MCInstrDesc.getOperandConstraint(Op.Index, llvm::MCOI::TIED_TO); - if (TiedTo >= 0) { - Op.TiedTo = &Operands[TiedTo]; - tie(&Op, Operands[TiedTo].Var); - } else { - tie(&Op, Op.Var); - } - } - } - for (auto &Op : Operands) { - if (Op.Var) { - Variables.push_back(&*Op.Var); - } - } - // Processing Aliasing. - DefRegisters = RATC.emptyRegisters(); - UseRegisters = RATC.emptyRegisters(); - for (const auto &Op : Operands) { - if (Op.Tracker) { - auto &Registers = Op.IsDef ? DefRegisters : UseRegisters; - Registers |= Op.Tracker->aliasedBits(); - } - } -} - -bool RegisterOperandAssignment:: -operator==(const RegisterOperandAssignment &Other) const { - return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg); -} - -bool AliasingRegisterOperands:: -operator==(const AliasingRegisterOperands &Other) const { - return std::tie(Defs, Uses) == std::tie(Other.Defs, Other.Uses); -} - -static void addOperandIfAlias( - const llvm::MCPhysReg Reg, bool SelectDef, llvm::ArrayRef<Operand> Operands, - llvm::SmallVectorImpl<RegisterOperandAssignment> &OperandValues) { - for (const auto &Op : Operands) { - if (Op.Tracker && Op.IsDef == SelectDef) { - const int SourceReg = Op.Tracker->getOrigin(Reg); - if (SourceReg >= 0) - OperandValues.emplace_back(&Op, SourceReg); - } - } -} - -bool AliasingRegisterOperands::hasImplicitAliasing() const { - const auto HasImplicit = [](const RegisterOperandAssignment &ROV) { - return !ROV.Op->IsExplicit; - }; - return llvm::any_of(Defs, HasImplicit) && llvm::any_of(Uses, HasImplicit); -} - -bool AliasingConfigurations::empty() const { return Configurations.empty(); } - -bool AliasingConfigurations::hasImplicitAliasing() const { - return llvm::any_of(Configurations, [](const AliasingRegisterOperands &ARO) { - return ARO.hasImplicitAliasing(); - }); -} - -AliasingConfigurations::AliasingConfigurations( - const Instruction &DefInstruction, const Instruction &UseInstruction) - : DefInstruction(DefInstruction), UseInstruction(UseInstruction) { - if (UseInstruction.UseRegisters.anyCommon(DefInstruction.DefRegisters)) { - auto CommonRegisters = UseInstruction.UseRegisters; - CommonRegisters &= DefInstruction.DefRegisters; - for (const llvm::MCPhysReg Reg : CommonRegisters.set_bits()) { - AliasingRegisterOperands ARO; - addOperandIfAlias(Reg, true, DefInstruction.Operands, ARO.Defs); - addOperandIfAlias(Reg, false, UseInstruction.Operands, ARO.Uses); - if (!ARO.Defs.empty() && !ARO.Uses.empty() && - !llvm::is_contained(Configurations, ARO)) - Configurations.push_back(std::move(ARO)); - } - } -} - -std::mt19937 &randomGenerator() { - static std::random_device RandomDevice; - static std::mt19937 RandomGenerator(RandomDevice()); - return RandomGenerator; -} - -static size_t randomIndex(size_t Size) { - assert(Size > 0); - std::uniform_int_distribution<> Distribution(0, Size - 1); - return Distribution(randomGenerator()); -} - -template <typename C> -static auto randomElement(const C &Container) -> decltype(Container[0]) { - return Container[randomIndex(Container.size())]; -} - -static void randomize(Variable &Var) { - assert(!Var.TiedOperands.empty()); - assert(Var.TiedOperands.front() != nullptr); - const Operand &Op = *Var.TiedOperands.front(); - assert(Op.Info != nullptr); - const auto &OpInfo = *Op.Info; - switch (OpInfo.OperandType) { - case llvm::MCOI::OperandType::OPERAND_IMMEDIATE: - // FIXME: explore immediate values too. - Var.AssignedValue = llvm::MCOperand::createImm(1); - break; - case llvm::MCOI::OperandType::OPERAND_REGISTER: { - assert(Op.Tracker); - const auto &Registers = Op.Tracker->sourceBits(); - Var.AssignedValue = llvm::MCOperand::createReg(randomBit(Registers)); - break; - } - default: - break; - } -} - -static void setRegisterOperandValue(const RegisterOperandAssignment &ROV) { - const Operand *Op = ROV.Op->TiedTo ? ROV.Op->TiedTo : ROV.Op; - assert(Op->Var); - auto &AssignedValue = Op->Var->AssignedValue; - if (AssignedValue.isValid()) { - assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg); - return; - } - Op->Var->AssignedValue = llvm::MCOperand::createReg(ROV.Reg); -} - -size_t randomBit(const llvm::BitVector &Vector) { - assert(Vector.any()); - auto Itr = Vector.set_bits_begin(); - for (size_t I = randomIndex(Vector.count()); I != 0; --I) - ++Itr; - return *Itr; -} - -void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations) { - assert(!AliasingConfigurations.empty()); - assert(!AliasingConfigurations.hasImplicitAliasing()); - const auto &RandomConf = randomElement(AliasingConfigurations.Configurations); - setRegisterOperandValue(randomElement(RandomConf.Defs)); - setRegisterOperandValue(randomElement(RandomConf.Uses)); -} - -void randomizeUnsetVariable(const Instruction &Instruction) { - for (auto *Var : Instruction.Variables) - if (!Var->AssignedValue.isValid()) - randomize(*Var); -} - -void clearVariableAssignments(const Instruction &Instruction) { - for (auto *Var : Instruction.Variables) - Var->AssignedValue = llvm::MCOperand(); -} - -llvm::MCInst build(const Instruction &Instruction) { - llvm::MCInst Result; - Result.setOpcode(Instruction.Description.Opcode); - for (const auto &Op : Instruction.Operands) { - if (Op.IsExplicit) { - auto &Var = Op.TiedTo ? Op.TiedTo->Var : Op.Var; - assert(Var); - Result.addOperand(Var->AssignedValue); - } - } - return Result; -} - -llvm::MCInst randomizeUnsetVariablesAndBuild(const Instruction &Instruction) { - randomizeUnsetVariable(Instruction); - return build(Instruction); -} - -void DumpMCOperand(const llvm::MCRegisterInfo &MCRegisterInfo, - const llvm::MCOperand &Op, llvm::raw_ostream &OS) { - if (!Op.isValid()) - OS << "Invalid"; - else if (Op.isReg()) - OS << MCRegisterInfo.getName(Op.getReg()); - else if (Op.isImm()) - OS << Op.getImm(); - else if (Op.isFPImm()) - OS << Op.getFPImm(); - else if (Op.isExpr()) - OS << "Expr"; - else if (Op.isInst()) - OS << "SubInst"; -} - -void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo, - const llvm::MCInstrInfo &MCInstrInfo, - const llvm::MCInst &MCInst, llvm::raw_ostream &OS) { - OS << MCInstrInfo.getName(MCInst.getOpcode()); - for (unsigned I = 0, E = MCInst.getNumOperands(); I < E; ++I) { - if (I > 0) - OS << ','; - OS << ' '; - DumpMCOperand(MCRegisterInfo, MCInst.getOperand(I), OS); - } -} - -} // namespace exegesis diff --git a/llvm/tools/llvm-exegesis/lib/MCInstrDescView.h b/llvm/tools/llvm-exegesis/lib/MCInstrDescView.h deleted file mode 100644 index 386a32cebf4..00000000000 --- a/llvm/tools/llvm-exegesis/lib/MCInstrDescView.h +++ /dev/null @@ -1,150 +0,0 @@ -//===-- MCInstrDescView.h ---------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// Provide views around LLVM structures to represents an instruction instance, -/// as well as its implicit and explicit arguments in a uniform way. -/// Arguments that are explicit and independant (non tied) also have a Variable -/// associated to them so the instruction can be fully defined by reading its -/// Variables. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H -#define LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H - -#include <random> - -#include "RegisterAliasing.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/Optional.h" -#include "llvm/MC/MCInst.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCInstrInfo.h" - -namespace exegesis { - -struct Operand; // forward declaration. - -// A variable represents the value of an Operand or a set of Operands if they ar -// tied together. -struct Variable { - llvm::SmallVector<const Operand *, 2> TiedOperands; - llvm::MCOperand AssignedValue; -}; - -// MCOperandInfo can only represents Explicit operands. This object gives a -// uniform view of Implicit and Explicit Operands. -// -// - Index: can be used to refer to MCInstrDesc::operands for Explicit operands. -// - Tracker: is set for Register Operands and is used to keep track of possible -// registers and the registers reachable from them (aliasing registers). -// - Info: a shortcut for MCInstrDesc::operands()[Index]. -// - TiedTo: a pointer to the Operand holding the value or nullptr. -// - ImplicitReg: a pointer to the register value when Operand is Implicit, -// nullptr otherwise. -// - Variable: The value associated with this Operand. It is only set for -// explicit operands that are not TiedTo. -struct Operand { - uint8_t Index = 0; - bool IsDef = false; - bool IsExplicit = false; - const RegisterAliasingTracker *Tracker = nullptr; // Set for Register Op. - const llvm::MCOperandInfo *Info = nullptr; // Set for Explicit Op. - const Operand *TiedTo = nullptr; // Set for Reg/Explicit Op. - const llvm::MCPhysReg *ImplicitReg = nullptr; // Set for Implicit Op. - mutable llvm::Optional<Variable> Var; // Set for Explicit Op. -}; - -// A view over an MCInstrDesc offering a convenient interface to compute -// Register aliasing and assign values to Operands. -struct Instruction { - Instruction(const llvm::MCInstrDesc &MCInstrDesc, - RegisterAliasingTrackerCache &ATC); - - const llvm::MCInstrDesc &Description; - llvm::SmallVector<Operand, 8> Operands; - llvm::SmallVector<Variable *, 8> Variables; - llvm::BitVector DefRegisters; // The union of the aliased def registers. - llvm::BitVector UseRegisters; // The union of the aliased use registers. -}; - -// Represents the assignment of a Register to an Operand. -struct RegisterOperandAssignment { - RegisterOperandAssignment(const Operand *Operand, llvm::MCPhysReg Reg) - : Op(Operand), Reg(Reg) {} - - const Operand *Op; // Pointer to an Explicit Register Operand. - llvm::MCPhysReg Reg; - - bool operator==(const RegisterOperandAssignment &other) const; -}; - -// Represents a set of Operands that would alias through the use of some -// Registers. -// There are two reasons why operands would alias: -// - The registers assigned to each of the operands are the same or alias each -// other (e.g. AX/AL) -// - The operands are tied. -struct AliasingRegisterOperands { - llvm::SmallVector<RegisterOperandAssignment, 1> Defs; // Unlikely size() > 1. - llvm::SmallVector<RegisterOperandAssignment, 2> Uses; - - // True is Defs and Use contain an Implicit Operand. - bool hasImplicitAliasing() const; - - bool operator==(const AliasingRegisterOperands &other) const; -}; - -// Returns all possible configurations leading Def registers of DefInstruction -// to alias with Use registers of UseInstruction. -struct AliasingConfigurations { - AliasingConfigurations(const Instruction &DefInstruction, - const Instruction &UseInstruction); - - bool empty() const; // True if no aliasing configuration is found. - bool hasImplicitAliasing() const; - void setExplicitAliasing() const; - - const Instruction &DefInstruction; - const Instruction &UseInstruction; - llvm::SmallVector<AliasingRegisterOperands, 32> Configurations; -}; - -// A global Random Number Generator to randomize configurations. -// FIXME: Move random number generation into an object and make it seedable for -// unit tests. -std::mt19937 &randomGenerator(); - -// Picks a random bit among the bits set in Vector and returns its index. -// Precondition: Vector must have at least one bit set. -size_t randomBit(const llvm::BitVector &Vector); - -// Picks a random configuration, then select a random def and a random use from -// it and set the target Variables to the selected values. -// FIXME: This function mutates some nested variables in a const object, please -// fix ASAP. -void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations); - -// Set all Instruction's Variables AssignedValue to Invalid. -void clearVariableAssignments(const Instruction &Instruction); - -// Assigns a Random Value to all Instruction's Variables that are still Invalid. -llvm::MCInst randomizeUnsetVariablesAndBuild(const Instruction &Instruction); - -// Writes MCInst to OS. -// This is not assembly but the internal LLVM's name for instructions and -// registers. -void DumpMCInst(const llvm::MCRegisterInfo &MCRegisterInfo, - const llvm::MCInstrInfo &MCInstrInfo, - const llvm::MCInst &MCInst, llvm::raw_ostream &OS); - -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_MCINSTRDESCVIEW_H diff --git a/llvm/tools/llvm-exegesis/lib/OperandGraph.cpp b/llvm/tools/llvm-exegesis/lib/OperandGraph.cpp new file mode 100644 index 00000000000..f6bdc9d73ee --- /dev/null +++ b/llvm/tools/llvm-exegesis/lib/OperandGraph.cpp @@ -0,0 +1,115 @@ +//===-- 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 diff --git a/llvm/tools/llvm-exegesis/lib/OperandGraph.h b/llvm/tools/llvm-exegesis/lib/OperandGraph.h new file mode 100644 index 00000000000..3db1a2a578b --- /dev/null +++ b/llvm/tools/llvm-exegesis/lib/OperandGraph.h @@ -0,0 +1,89 @@ +//===-- 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 diff --git a/llvm/tools/llvm-exegesis/lib/RegisterAliasing.cpp b/llvm/tools/llvm-exegesis/lib/RegisterAliasing.cpp deleted file mode 100644 index fb5547bb603..00000000000 --- a/llvm/tools/llvm-exegesis/lib/RegisterAliasing.cpp +++ /dev/null @@ -1,83 +0,0 @@ -//===-- RegisterAliasingTracker.cpp -----------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "RegisterAliasing.h" - -namespace exegesis { - -llvm::BitVector getAliasedBits(const llvm::MCRegisterInfo &RegInfo, - const llvm::BitVector &SourceBits) { - llvm::BitVector AliasedBits(RegInfo.getNumRegs()); - for (const size_t PhysReg : SourceBits.set_bits()) { - using RegAliasItr = llvm::MCRegAliasIterator; - for (auto Itr = RegAliasItr(PhysReg, &RegInfo, true); Itr.isValid(); - ++Itr) { - AliasedBits.set(*Itr); - } - } - return AliasedBits; -} - -RegisterAliasingTracker::RegisterAliasingTracker( - const llvm::MCRegisterInfo &RegInfo) - : SourceBits(RegInfo.getNumRegs()), AliasedBits(RegInfo.getNumRegs()), - Origins(RegInfo.getNumRegs()) {} - -RegisterAliasingTracker::RegisterAliasingTracker( - const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &ReservedReg, - const llvm::MCRegisterClass &RegClass) - : RegisterAliasingTracker(RegInfo) { - for (llvm::MCPhysReg PhysReg : RegClass) - if (!ReservedReg[PhysReg]) // Removing reserved registers. - SourceBits.set(PhysReg); - FillOriginAndAliasedBits(RegInfo, SourceBits); -} - -RegisterAliasingTracker::RegisterAliasingTracker( - const llvm::MCRegisterInfo &RegInfo, const llvm::MCPhysReg PhysReg) - : RegisterAliasingTracker(RegInfo) { - SourceBits.set(PhysReg); - FillOriginAndAliasedBits(RegInfo, SourceBits); -} - -void RegisterAliasingTracker::FillOriginAndAliasedBits( - const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &SourceBits) { - using RegAliasItr = llvm::MCRegAliasIterator; - for (const size_t PhysReg : SourceBits.set_bits()) { - for (auto Itr = RegAliasItr(PhysReg, &RegInfo, true); Itr.isValid(); - ++Itr) { - AliasedBits.set(*Itr); - Origins[*Itr] = PhysReg; - } - } -} - -RegisterAliasingTrackerCache::RegisterAliasingTrackerCache( - const llvm::MCRegisterInfo &RegInfo, const llvm::BitVector &ReservedReg) - : RegInfo(RegInfo), ReservedReg(ReservedReg), - EmptyRegisters(RegInfo.getNumRegs()) {} - -const RegisterAliasingTracker & -RegisterAliasingTrackerCache::getRegister(llvm::MCPhysReg PhysReg) { - auto &Found = Registers[PhysReg]; - if (!Found) - Found.reset(new RegisterAliasingTracker(RegInfo, PhysReg)); - return *Found; -} - -const RegisterAliasingTracker & -RegisterAliasingTrackerCache::getRegisterClass(unsigned RegClassIndex) { - auto &Found = RegisterClasses[RegClassIndex]; - const auto &RegClass = RegInfo.getRegClass(RegClassIndex); - if (!Found) - Found.reset(new RegisterAliasingTracker(RegInfo, ReservedReg, RegClass)); - return *Found; -} - -} // namespace exegesis diff --git a/llvm/tools/llvm-exegesis/lib/RegisterAliasing.h b/llvm/tools/llvm-exegesis/lib/RegisterAliasing.h deleted file mode 100644 index 3387adf01b7..00000000000 --- a/llvm/tools/llvm-exegesis/lib/RegisterAliasing.h +++ /dev/null @@ -1,107 +0,0 @@ -//===-- RegisterAliasingTracker.h -------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// Defines classes to keep track of register aliasing. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H -#define LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H - -#include <memory> -#include <unordered_map> - -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/PackedVector.h" -#include "llvm/MC/MCRegisterInfo.h" - -namespace exegesis { - -// Returns the registers that are aliased by the ones set in SourceBits. -llvm::BitVector getAliasedBits(const llvm::MCRegisterInfo &RegInfo, - const llvm::BitVector &SourceBits); - -// Keeps track of a mapping from one register (or a register class) to its -// aliased registers. -// -// e.g. -// RegisterAliasingTracker Tracker(RegInfo, llvm::X86::EAX); -// Tracker.sourceBits() == { llvm::X86::EAX } -// Tracker.aliasedBits() == { llvm::X86::AL, llvm::X86::AH, llvm::X86::AX, -// llvm::X86::EAX,llvm::X86::HAX, llvm::X86::RAX } -// Tracker.getOrigin(llvm::X86::AL) == llvm::X86::EAX; -// Tracker.getOrigin(llvm::X86::BX) == -1; -struct RegisterAliasingTracker { - // Construct a tracker from an MCRegisterClass. - RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo, - const llvm::BitVector &ReservedReg, - const llvm::MCRegisterClass &RegClass); - - // Construct a tracker from an MCPhysReg. - RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo, - const llvm::MCPhysReg Register); - - const llvm::BitVector &sourceBits() const { return SourceBits; } - - // Retrieves all the touched registers as a BitVector. - const llvm::BitVector &aliasedBits() const { return AliasedBits; } - - // Returns the origin of this register or -1. - int getOrigin(llvm::MCPhysReg Aliased) const { - if (!AliasedBits[Aliased]) - return -1; - return Origins[Aliased]; - } - -private: - RegisterAliasingTracker(const llvm::MCRegisterInfo &RegInfo); - - void FillOriginAndAliasedBits(const llvm::MCRegisterInfo &RegInfo, - const llvm::BitVector &OriginalBits); - - llvm::BitVector SourceBits; - llvm::BitVector AliasedBits; - llvm::PackedVector<size_t, 10> Origins; // Max 1024 physical registers. -}; - -// A cache of existing trackers. -struct RegisterAliasingTrackerCache { - // RegInfo must outlive the cache. - RegisterAliasingTrackerCache(const llvm::MCRegisterInfo &RegInfo, - const llvm::BitVector &ReservedReg); - - // Convenient function to retrieve a BitVector of the right size. - const llvm::BitVector &emptyRegisters() const { return EmptyRegisters; } - - // Convenient function to retrieve the registers the function body can't use. - const llvm::BitVector &reservedRegisters() const { return ReservedReg; } - - // Convenient function to retrieve the underlying MCRegInfo. - const llvm::MCRegisterInfo ®Info() const { return RegInfo; } - - // Retrieves the RegisterAliasingTracker for this particular register. - const RegisterAliasingTracker &getRegister(llvm::MCPhysReg Reg); - - // Retrieves the RegisterAliasingTracker for this particular register class. - const RegisterAliasingTracker &getRegisterClass(unsigned RegClassIndex); - -private: - const llvm::MCRegisterInfo &RegInfo; - const llvm::BitVector ReservedReg; - const llvm::BitVector EmptyRegisters; - std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>> - Registers; - std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>> - RegisterClasses; -}; - -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H diff --git a/llvm/tools/llvm-exegesis/lib/Uops.cpp b/llvm/tools/llvm-exegesis/lib/Uops.cpp index 94282862989..59d2fc408fb 100644 --- a/llvm/tools/llvm-exegesis/lib/Uops.cpp +++ b/llvm/tools/llvm-exegesis/lib/Uops.cpp @@ -8,130 +8,29 @@ //===----------------------------------------------------------------------===// #include "Uops.h" - -#include "Assembler.h" -#include "BenchmarkRunner.h" -#include "MCInstrDescView.h" +#include "BenchmarkResult.h" +#include "InstructionSnippetGenerator.h" #include "PerfHelper.h" - -// FIXME: Load constants into registers (e.g. with fld1) to not break -// instructions like x87. - -// Ideally we would like the only limitation on executing uops to be the issue -// ports. Maximizing port pressure increases the likelihood that the load is -// distributed evenly across possible ports. - -// To achieve that, one approach is to generate instructions that do not have -// data dependencies between them. -// -// For some instructions, this is trivial: -// mov rax, qword ptr [rsi] -// mov rax, qword ptr [rsi] -// mov rax, qword ptr [rsi] -// mov rax, qword ptr [rsi] -// For the above snippet, haswell just renames rax four times and executes the -// four instructions two at a time on P23 and P0126. -// -// For some instructions, we just need to make sure that the source is -// different from the destination. For example, IDIV8r reads from GPR and -// writes to AX. We just need to ensure that the Var 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. +#include "llvm/ADT/StringExtras.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCSchedule.h" +#include "llvm/Support/Error.h" +#include <algorithm> +#include <random> +#include <unordered_map> +#include <unordered_set> namespace exegesis { -static bool hasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { - return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN; -} - -// FIXME: Handle memory, see PR36905. -static bool hasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { - return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; -} - -static bool isInfeasible(const Instruction &Instruction, std::string &Error) { - const auto &MCInstrDesc = Instruction.Description; - if (MCInstrDesc.isPseudo()) { - Error = "is pseudo"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) { - Error = "has unknown operands"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) { - Error = "has memory operands"; +// 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; } - return false; -} - -// Returns whether this Variable ties Use and Def operands together. -static bool hasTiedOperands(const Variable *Var) { - bool HasUse = false; - bool HasDef = false; - for (const Operand *Op : Var->TiedOperands) { - if (Op->IsDef) - HasDef = true; - else - HasUse = true; - } - return HasUse && HasDef; -} - -static llvm::SmallVector<Variable *, 8> -getTiedVariables(const Instruction &Instruction) { - llvm::SmallVector<Variable *, 8> Result; - for (auto *Var : Instruction.Variables) - if (hasTiedOperands(Var)) - Result.push_back(Var); - return Result; -} - -static void remove(llvm::BitVector &a, const llvm::BitVector &b) { - assert(a.size() == b.size()); - for (auto I : b.set_bits()) - a.reset(I); } static llvm::Error makeError(llvm::Twine Msg) { @@ -139,89 +38,153 @@ static llvm::Error makeError(llvm::Twine Msg) { llvm::inconvertibleErrorCode()); } +static std::vector<llvm::MCInst> generateIndependentAssignments( + const LLVMState &State, const llvm::MCInstrDesc &InstrDesc, + llvm::SmallVector<Variable, 8> Vars, int MaxAssignments) { + std::unordered_set<llvm::MCPhysReg> IsUsedByAnyVar; + for (const Variable &Var : Vars) { + if (Var.IsUse) { + IsUsedByAnyVar.insert(Var.PossibleRegisters.begin(), + Var.PossibleRegisters.end()); + } + } + + std::vector<llvm::MCInst> Pattern; + for (int A = 0; A < MaxAssignments; ++A) { + // FIXME: This is a bit pessimistic. We should get away with an + // assignment that ensures that the set of assigned registers for uses and + // the set of assigned registers for defs do not intersect (registers + // for uses (resp defs) do not have to be all distinct). + const std::vector<llvm::MCPhysReg> Regs = getExclusiveAssignment(Vars); + if (Regs.empty()) + break; + // Remove all assigned registers defs that are used by at least one other + // variable from the list of possible variable registers. This ensures that + // we never create a RAW hazard that would lead to serialization. + for (size_t I = 0, E = Vars.size(); I < E; ++I) { + llvm::MCPhysReg Reg = Regs[I]; + if (Vars[I].IsDef && IsUsedByAnyVar.count(Reg)) { + Vars[I].PossibleRegisters.remove(Reg); + } + } + // Create an MCInst and check assembly. + llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs); + if (!State.canAssemble(Inst)) + continue; + Pattern.push_back(std::move(Inst)); + } + return Pattern; +} + UopsBenchmarkRunner::~UopsBenchmarkRunner() = default; const char *UopsBenchmarkRunner::getDisplayName() const { return "uops"; } -llvm::Expected<std::vector<llvm::MCInst>> -UopsBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC, - unsigned Opcode, - llvm::raw_ostream &Info) const { - std::vector<llvm::MCInst> Snippet; - const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode); - const Instruction Instruction(MCInstrDesc, RATC); - - std::string Error; - if (isInfeasible(Instruction, Error)) { - llvm::report_fatal_error(llvm::Twine("Infeasible : ").concat(Error)); +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"); } - const AliasingConfigurations SelfAliasing(Instruction, Instruction); - if (SelfAliasing.empty()) { - Info << "instruction is parallel, repeating a random one.\n"; - Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); - return Snippet; + // 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)); } - if (SelfAliasing.hasImplicitAliasing()) { - Info << "instruction is serial, repeating a random one.\n"; - Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); - return Snippet; - } - const auto TiedVariables = getTiedVariables(Instruction); - if (!TiedVariables.empty()) { - if (TiedVariables.size() > 1) { - Info << "Not yet implemented, don't know how to handle several tied " - "variables\n"; - return makeError("Infeasible : don't know how to handle several tied " - "variables"); - } - Info << "instruction has tied variables using static renaming.\n"; - Variable *Var = TiedVariables.front(); - assert(Var); - assert(!Var->TiedOperands.empty()); - const Operand &Operand = *Var->TiedOperands.front(); - assert(Operand.Tracker); - for (const llvm::MCPhysReg Reg : Operand.Tracker->sourceBits().set_bits()) { - clearVariableAssignments(Instruction); - Var->AssignedValue = llvm::MCOperand::createReg(Reg); - Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); - } - return Snippet; - } - // No tied variables, we pick random values for defs. - llvm::BitVector Defs(MCRegisterInfo.getNumRegs()); - for (const auto &Op : Instruction.Operands) { - if (Op.Tracker && Op.IsExplicit && Op.IsDef) { - assert(Op.Var); - auto PossibleRegisters = Op.Tracker->sourceBits(); - remove(PossibleRegisters, RATC.reservedRegisters()); - assert(PossibleRegisters.any() && "No register left to choose from"); - const auto RandomReg = randomBit(PossibleRegisters); - Defs.set(RandomReg); - Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg); - } - } - // And pick random use values that are not reserved and don't alias with defs. - const auto DefAliases = getAliasedBits(MCRegisterInfo, Defs); - for (const auto &Op : Instruction.Operands) { - if (Op.Tracker && Op.IsExplicit && !Op.IsDef) { - assert(Op.Var); - auto PossibleRegisters = Op.Tracker->sourceBits(); - remove(PossibleRegisters, RATC.reservedRegisters()); - remove(PossibleRegisters, DefAliases); - assert(PossibleRegisters.any() && "No register left to choose from"); - const auto RandomReg = randomBit(PossibleRegisters); - Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg); - } - } - Info - << "instruction has no tied variables picking Uses different from defs\n"; - Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); - return Snippet; + + // 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; } std::vector<BenchmarkMeasure> -UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function, +UopsBenchmarkRunner::runMeasurements(const LLVMState &State, + const JitFunction &Function, const unsigned NumRepetitions) const { const auto &SchedModel = State.getSubtargetInfo().getSchedModel(); @@ -234,11 +197,7 @@ UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function, continue; // FIXME: Sum results when there are several counters for a single ProcRes // (e.g. P23 on SandyBridge). - pfm::PerfEvent UopPerfEvent(PfmCounters); - if (!UopPerfEvent.valid()) - llvm::report_fatal_error( - llvm::Twine("invalid perf event ").concat(PfmCounters)); - pfm::Counter Counter(UopPerfEvent); + pfm::Counter Counter{pfm::PerfEvent(PfmCounters)}; Counter.start(); Function(); Counter.stop(); diff --git a/llvm/tools/llvm-exegesis/lib/Uops.h b/llvm/tools/llvm-exegesis/lib/Uops.h index d305d0124f8..e9dc181061d 100644 --- a/llvm/tools/llvm-exegesis/lib/Uops.h +++ b/llvm/tools/llvm-exegesis/lib/Uops.h @@ -21,19 +21,19 @@ namespace exegesis { class UopsBenchmarkRunner : public BenchmarkRunner { public: - using BenchmarkRunner::BenchmarkRunner; ~UopsBenchmarkRunner() override; private: const char *getDisplayName() const override; llvm::Expected<std::vector<llvm::MCInst>> - createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode, - llvm::raw_ostream &Info) const override; + createCode(const LLVMState &State, unsigned OpcodeIndex, + unsigned NumRepetitions, + const JitFunctionContext &Context) const override; std::vector<BenchmarkMeasure> - runMeasurements(const ExecutableFunction &EF, - const unsigned NumRepetitions) const override; + runMeasurements(const LLVMState &State, const JitFunction &Function, + unsigned NumRepetitions) const override; }; } // namespace exegesis diff --git a/llvm/tools/llvm-exegesis/llvm-exegesis.cpp b/llvm/tools/llvm-exegesis/llvm-exegesis.cpp index 2b77288d288..a872c759093 100644 --- a/llvm/tools/llvm-exegesis/llvm-exegesis.cpp +++ b/llvm/tools/llvm-exegesis/llvm-exegesis.cpp @@ -76,23 +76,14 @@ static llvm::cl::opt<std::string> AnalysisClustersFile("analysis-clusters-file", namespace exegesis { -static unsigned GetOpcodeOrDie(const llvm::MCInstrInfo &MCInstrInfo) { - if (OpcodeName.empty() && (OpcodeIndex == 0)) - llvm::report_fatal_error( - "please provide one and only one of 'opcode-index' or 'opcode-name'"); - if (OpcodeIndex > 0) - return OpcodeIndex; - // Resolve opcode name -> opcode. - for (unsigned I = 0, E = MCInstrInfo.getNumOpcodes(); I < E; ++I) - if (MCInstrInfo.getName(I) == OpcodeName) - return I; - llvm::report_fatal_error(llvm::Twine("unknown opcode ").concat(OpcodeName)); -} - void benchmarkMain() { if (exegesis::pfm::pfmInitialize()) llvm::report_fatal_error("cannot initialize libpfm"); + if (OpcodeName.empty() == (OpcodeIndex == 0)) + llvm::report_fatal_error( + "please provide one and only one of 'opcode-index' or 'opcode-name'"); + llvm::InitializeNativeTarget(); llvm::InitializeNativeTargetAsmPrinter(); @@ -101,26 +92,37 @@ void benchmarkMain() { 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>(State); + Runner = llvm::make_unique<LatencyBenchmarkRunner>(); break; case BenchmarkModeE::Uops: - Runner = llvm::make_unique<UopsBenchmarkRunner>(State); + Runner = llvm::make_unique<UopsBenchmarkRunner>(); break; case BenchmarkModeE::Analysis: llvm_unreachable("not a benchmark"); } - if (NumRepetitions == 0) - llvm::report_fatal_error("--num-repetitions must be greater than zero"); - - Runner->run(GetOpcodeOrDie(State.getInstrInfo()), Filter, NumRepetitions) + Runner->run(State, Opcode, NumRepetitions > 0 ? NumRepetitions : 1, Filter) .writeYamlOrDie(BenchmarkFile); exegesis::pfm::pfmTerminate(); } diff --git a/llvm/unittests/tools/llvm-exegesis/CMakeLists.txt b/llvm/unittests/tools/llvm-exegesis/CMakeLists.txt index 95426aa1564..22b5f1d79c3 100644 --- a/llvm/unittests/tools/llvm-exegesis/CMakeLists.txt +++ b/llvm/unittests/tools/llvm-exegesis/CMakeLists.txt @@ -13,6 +13,7 @@ set(LLVM_LINK_COMPONENTS add_llvm_unittest(LLVMExegesisTests BenchmarkResultTest.cpp ClusteringTest.cpp + OperandGraphTest.cpp PerfHelperTest.cpp ) target_link_libraries(LLVMExegesisTests PRIVATE LLVMExegesis) diff --git a/llvm/unittests/tools/llvm-exegesis/OperandGraphTest.cpp b/llvm/unittests/tools/llvm-exegesis/OperandGraphTest.cpp new file mode 100644 index 00000000000..a29813b03ef --- /dev/null +++ b/llvm/unittests/tools/llvm-exegesis/OperandGraphTest.cpp @@ -0,0 +1,48 @@ +//===-- 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 diff --git a/llvm/unittests/tools/llvm-exegesis/X86/CMakeLists.txt b/llvm/unittests/tools/llvm-exegesis/X86/CMakeLists.txt index d1e2ed192b1..4d76f1a18c0 100644 --- a/llvm/unittests/tools/llvm-exegesis/X86/CMakeLists.txt +++ b/llvm/unittests/tools/llvm-exegesis/X86/CMakeLists.txt @@ -14,7 +14,8 @@ set(LLVM_LINK_COMPONENTS ) add_llvm_unittest(LLVMExegesisX86Tests - RegisterAliasingTest.cpp InMemoryAssemblerTest.cpp + InstructionSnippetGeneratorTest.cpp ) target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis) + diff --git a/llvm/unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp b/llvm/unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp index 24b55c8f109..d00b223393f 100644 --- a/llvm/unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp +++ b/llvm/unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// -#include "Assembler.h" +#include "InMemoryAssembler.h" #include "X86InstrInfo.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -51,8 +51,8 @@ protected: 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,66 +62,58 @@ protected: 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, JitFunction) { +TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunction) { SKIP_UNSUPPORTED_PLATFORM; - const ExecutableFunction Function = assembleEmptyFunction(); + JitFunctionContext Context(createTargetMachine()); + JitFunction Function(std::move(Context), {}); 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, JitFunctionXOR32rr) { +TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr) { SKIP_UNSUPPORTED_PLATFORM; - const ExecutableFunction Function = assembleFunction( - MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX)); + JitFunctionContext Context(createTargetMachine()); + JitFunction Function( + std::move(Context), + {MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX)}); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0x31, 0xc0, 0xc3)); - Function(); + // Function(); } -TEST_F(MachineFunctionGeneratorTest, JitFunctionMOV64ri) { +TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV64ri) { SKIP_UNSUPPORTED_PLATFORM; - const ExecutableFunction Function = - assembleFunction(MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42)); + JitFunctionContext Context(createTargetMachine()); + JitFunction Function(std::move(Context), + {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, JitFunctionMOV32ri) { +TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV32ri) { SKIP_UNSUPPORTED_PLATFORM; - const ExecutableFunction Function = - assembleFunction(MCInstBuilder(MOV32ri).addReg(EAX).addImm(42)); + JitFunctionContext Context(createTargetMachine()); + JitFunction Function(std::move(Context), + {MCInstBuilder(MOV32ri).addReg(EAX).addImm(42)}); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0xb8, 0x2a, 0x00, 0x00, 0x00, 0xc3)); - Function(); + // Function(); } } // namespace diff --git a/llvm/unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp b/llvm/unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp new file mode 100644 index 00000000000..f4136561a11 --- /dev/null +++ b/llvm/unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp @@ -0,0 +1,309 @@ +//===-- 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 diff --git a/llvm/unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp b/llvm/unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp deleted file mode 100644 index eb6f294dc13..00000000000 --- a/llvm/unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include "RegisterAliasing.h" - -#include <cassert> -#include <memory> - -#include "X86InstrInfo.h" -#include "llvm/Support/Host.h" -#include "llvm/Support/TargetRegistry.h" -#include "llvm/Support/TargetSelect.h" -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -namespace exegesis { -namespace { - -class RegisterAliasingTest : public ::testing::Test { -protected: - RegisterAliasingTest() { - const std::string TT = llvm::sys::getProcessTriple(); - std::string error; - const llvm::Target *const TheTarget = - llvm::TargetRegistry::lookupTarget(TT, error); - assert(TheTarget); - MCRegInfo.reset(TheTarget->createMCRegInfo(TT)); - } - - static void SetUpTestCase() { llvm::InitializeNativeTarget(); } - - const llvm::MCRegisterInfo &getMCRegInfo() { return *MCRegInfo; } - -private: - std::unique_ptr<const llvm::MCRegisterInfo> MCRegInfo; -}; - -TEST_F(RegisterAliasingTest, TrackSimpleRegister) { - const auto &RegInfo = getMCRegInfo(); - const RegisterAliasingTracker tracker(RegInfo, llvm::X86::EAX); - const std::set<llvm::MCPhysReg> ActualAliasedRegisters( - tracker.aliasedBits().set_bits().begin(), - tracker.aliasedBits().set_bits().end()); - const std::set<llvm::MCPhysReg> ExpectedAliasedRegisters = { - llvm::X86::AL, llvm::X86::AH, llvm::X86::AX, - llvm::X86::EAX, llvm::X86::HAX, llvm::X86::RAX}; - ASSERT_THAT(ActualAliasedRegisters, ExpectedAliasedRegisters); - for (llvm::MCPhysReg aliased : ExpectedAliasedRegisters) { - ASSERT_THAT(tracker.getOrigin(aliased), llvm::X86::EAX); - } -} - -TEST_F(RegisterAliasingTest, TrackRegisterClass) { - // The alias bits for GR8_ABCD_LRegClassID are the union of the alias bits for - // AL, BL, CL and DL. - const auto &RegInfo = getMCRegInfo(); - const llvm::BitVector NoReservedReg(RegInfo.getNumRegs()); - - const RegisterAliasingTracker RegClassTracker( - RegInfo, NoReservedReg, - RegInfo.getRegClass(llvm::X86::GR8_ABCD_LRegClassID)); - - llvm::BitVector sum(RegInfo.getNumRegs()); - sum |= RegisterAliasingTracker(RegInfo, llvm::X86::AL).aliasedBits(); - sum |= RegisterAliasingTracker(RegInfo, llvm::X86::BL).aliasedBits(); - sum |= RegisterAliasingTracker(RegInfo, llvm::X86::CL).aliasedBits(); - sum |= RegisterAliasingTracker(RegInfo, llvm::X86::DL).aliasedBits(); - - ASSERT_THAT(RegClassTracker.aliasedBits(), sum); -} - -TEST_F(RegisterAliasingTest, TrackRegisterClassCache) { - // Fetching twice the same tracker yields the same pointers. - const auto &RegInfo = getMCRegInfo(); - const llvm::BitVector NoReservedReg(RegInfo.getNumRegs()); - RegisterAliasingTrackerCache Cache(RegInfo, NoReservedReg); - ASSERT_THAT(&Cache.getRegister(llvm::X86::AX), - &Cache.getRegister(llvm::X86::AX)); - - ASSERT_THAT(&Cache.getRegisterClass(llvm::X86::GR8_ABCD_LRegClassID), - &Cache.getRegisterClass(llvm::X86::GR8_ABCD_LRegClassID)); -} - -} // namespace -} // namespace exegesis |
