Index: tools/llvm-exegesis/lib/Assembler.h =================================================================== --- /dev/null +++ tools/llvm-exegesis/lib/Assembler.h @@ -0,0 +1,78 @@ +//===-- Assembler.h ---------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// Defines classes to assemble functions composed of a single basic block of +/// MCInsts. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H +#define LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H + +#include + +#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 TM, + llvm::ArrayRef 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 +getObjectFromBuffer(llvm::StringRef Buffer); + +// Loads the content of Filename as on ObjectFile and returns it. +llvm::object::OwningBinary +getObjectFromFile(llvm::StringRef Filename); + +// Consumes an ObjectFile containing a `void foo()` function and make it +// executable. +struct ExecutableFunction { + explicit ExecutableFunction( + std::unique_ptr TM, + llvm::object::OwningBinary &&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 Context; + std::unique_ptr ExecEngine; + llvm::StringRef FunctionBytes; +}; + +} // namespace exegesis + +#endif // LLVM_TOOLS_LLVM_EXEGESIS_ASSEMBLER_H Index: tools/llvm-exegesis/lib/Assembler.cpp =================================================================== --- tools/llvm-exegesis/lib/Assembler.cpp +++ tools/llvm-exegesis/lib/Assembler.cpp @@ -1,4 +1,4 @@ -//===-- InMemoryAssembler.cpp -----------------------------------*- C++ -*-===// +//===-- Assembler.cpp -------------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -7,9 +7,8 @@ // //===----------------------------------------------------------------------===// -#include "InMemoryAssembler.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" +#include "Assembler.h" + #include "llvm/CodeGen/GlobalISel/CallLowering.h" #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -17,20 +16,11 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetPassConfig.h" -#include "llvm/ExecutionEngine/ExecutionEngine.h" -#include "llvm/ExecutionEngine/MCJIT.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/ExecutionEngine/SectionMemoryManager.h" -#include "llvm/IR/LLVMContext.h" #include "llvm/IR/LegacyPassManager.h" -#include "llvm/MC/MCFixup.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/Object/Binary.h" -#include "llvm/Object/ObjectFile.h" -#include "llvm/PassInfo.h" -#include "llvm/PassRegistry.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetOptions.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/Support/MemoryBuffer.h" namespace exegesis { @@ -73,47 +63,6 @@ return MMI->getOrCreateMachineFunction(*F); } -static llvm::object::OwningBinary -assemble(llvm::Module *Module, std::unique_ptr 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 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 Buffer = - llvm::MemoryBuffer::getMemBufferCopy(AsmStream.str()); - // Create the ObjectFile from the MemoryBuffer. - std::unique_ptr Obj = llvm::cantFail( - llvm::object::ObjectFile::createObjectFile(Buffer->getMemBufferRef())); - // Returning both the MemoryBuffer and the ObjectFile. - return llvm::object::OwningBinary( - std::move(Obj), std::move(Buffer)); -} - static void fillMachineFunction(llvm::MachineFunction &MF, llvm::ArrayRef Instructions) { llvm::MachineBasicBlock *MBB = MF.CreateMachineBasicBlock(); @@ -152,6 +101,97 @@ } } +static std::unique_ptr +createModule(const std::unique_ptr &Context, + const llvm::DataLayout DL) { + auto Module = llvm::make_unique(ModuleID, *Context); + Module->setDataLayout(DL); + return Module; +} + +llvm::BitVector getFunctionReservedRegs(const llvm::TargetMachine &TM) { + std::unique_ptr Context = + llvm::make_unique(); + std::unique_ptr Module = + createModule(Context, TM.createDataLayout()); + std::unique_ptr MMI = + llvm::make_unique(&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 TM, + llvm::ArrayRef Instructions, + llvm::raw_pwrite_stream &AsmStream) { + std::unique_ptr Context = + llvm::make_unique(); + std::unique_ptr Module = + createModule(Context, TM->createDataLayout()); + std::unique_ptr MMI = + llvm::make_unique(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 +getObjectFromBuffer(llvm::StringRef InputData) { + // Storing the generated assembly into a MemoryBuffer that owns the memory. + std::unique_ptr Buffer = + llvm::MemoryBuffer::getMemBufferCopy(InputData); + // Create the ObjectFile from the MemoryBuffer. + std::unique_ptr Obj = llvm::cantFail( + llvm::object::ObjectFile::createObjectFile(Buffer->getMemBufferRef())); + // Returning both the MemoryBuffer and the ObjectFile. + return llvm::object::OwningBinary( + std::move(Obj), std::move(Buffer)); +} + +llvm::object::OwningBinary +getObjectFromFile(llvm::StringRef Filename) { + return llvm::cantFail(llvm::object::ObjectFile::createObjectFile(Filename)); +} + namespace { // Implementation of this class relies on the fact that a single object with a @@ -175,57 +215,31 @@ } // namespace -JitFunctionContext::JitFunctionContext( - std::unique_ptr TheTM) - : Context(llvm::make_unique()), TM(std::move(TheTM)), - MMI(llvm::make_unique(TM.get())), - Module(llvm::make_unique(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 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 ObjHolder = - assemble(FunctionContext.Module.get(), std::move(FunctionContext.MMI), - FunctionContext.TM.get()); - assert(ObjHolder.getBinary() && "cannot create object file"); +ExecutableFunction::ExecutableFunction( + std::unique_ptr TM, + llvm::object::OwningBinary &&ObjectFileHolder) + : Context(llvm::make_unique()) { + assert(ObjectFileHolder.getBinary() && "cannot create object file"); // Initializing the execution engine. // We need to use the JIT EngineKind to be able to add an object file. LLVMLinkInMCJIT(); uintptr_t CodeSize = 0; std::string Error; - llvm::LLVMTargetMachine *TM = FunctionContext.TM.release(); ExecEngine.reset( - llvm::EngineBuilder(std::move(FunctionContext.Module)) + llvm::EngineBuilder(createModule(Context, TM->createDataLayout())) .setErrorStr(&Error) .setMCPU(TM->getTargetCPU()) .setEngineKind(llvm::EngineKind::JIT) .setMCJITMemoryManager( llvm::make_unique(&CodeSize)) - .create(TM)); + .create(TM.release())); if (!ExecEngine) llvm::report_fatal_error(Error); // Adding the generated object file containing the assembled function. // The ExecutionEngine makes sure the object file is copied into an // executable page. - ExecEngine->addObjectFile(std::move(ObjHolder)); - // Setting function + ExecEngine->addObjectFile(std::move(ObjectFileHolder)); + // Fetching function bytes. FunctionBytes = llvm::StringRef(reinterpret_cast( ExecEngine->getFunctionAddress(FunctionID)), Index: tools/llvm-exegesis/lib/BenchmarkResult.h =================================================================== --- tools/llvm-exegesis/lib/BenchmarkResult.h +++ tools/llvm-exegesis/lib/BenchmarkResult.h @@ -50,9 +50,14 @@ std::string Info; static InstructionBenchmark readYamlOrDie(llvm::StringRef Filename); - static std::vector readYamlsOrDie(llvm::StringRef Filename); + static std::vector - // Unfortunately this function is non const because of YAML traits. + // Read functions. + readYamlsOrDie(llvm::StringRef Filename); + void readYamlFrom(llvm::StringRef InputContent); + + // Write functions, non-const because of YAML traits. + void writeYamlTo(llvm::raw_ostream &S); void writeYamlOrDie(const llvm::StringRef Filename); }; Index: tools/llvm-exegesis/lib/BenchmarkResult.cpp =================================================================== --- tools/llvm-exegesis/lib/BenchmarkResult.cpp +++ tools/llvm-exegesis/lib/BenchmarkResult.cpp @@ -61,10 +61,8 @@ namespace exegesis { -namespace { - template -ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) { +static ObjectOrList readYamlOrDieCommon(llvm::StringRef Filename) { std::unique_ptr MemBuffer = llvm::cantFail( llvm::errorOrToExpected(llvm::MemoryBuffer::getFile(Filename))); llvm::yaml::Input Yin(*MemBuffer); @@ -73,8 +71,6 @@ return Benchmark; } -} // namespace - InstructionBenchmark InstructionBenchmark::readYamlOrDie(llvm::StringRef Filename) { return readYamlOrDieCommon(Filename); @@ -85,19 +81,26 @@ return readYamlOrDieCommon>(Filename); } +void InstructionBenchmark::writeYamlTo(llvm::raw_ostream &S) { + llvm::yaml::Output Yout(S); + Yout << *this; +} + +void InstructionBenchmark::readYamlFrom(llvm::StringRef InputContent) { + llvm::yaml::Input Yin(InputContent); + Yin >> *this; +} + +// FIXME: Change the API to let the caller handle errors. void InstructionBenchmark::writeYamlOrDie(const llvm::StringRef Filename) { if (Filename == "-") { - llvm::yaml::Output Yout(llvm::outs()); - Yout << *this; + writeYamlTo(llvm::outs()); } else { - llvm::SmallString<1024> Buffer; - llvm::raw_svector_ostream Ostr(Buffer); - llvm::yaml::Output Yout(Ostr); - Yout << *this; - std::unique_ptr File = - llvm::cantFail(llvm::FileOutputBuffer::create(Filename, Buffer.size())); - memcpy(File->getBufferStart(), Buffer.data(), Buffer.size()); - llvm::cantFail(File->commit()); + int ResultFD = 0; + llvm::cantFail(llvm::errorCodeToError( + openFileForWrite(Filename, ResultFD, llvm::sys::fs::F_Text))); + llvm::raw_fd_ostream Ostr(ResultFD, true /*shouldClose*/); + writeYamlTo(Ostr); } } Index: tools/llvm-exegesis/lib/BenchmarkRunner.h =================================================================== --- tools/llvm-exegesis/lib/BenchmarkRunner.h +++ tools/llvm-exegesis/lib/BenchmarkRunner.h @@ -16,9 +16,10 @@ #ifndef LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H #define LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRUNNER_H +#include "Assembler.h" #include "BenchmarkResult.h" -#include "InMemoryAssembler.h" #include "LlvmState.h" +#include "RegisterAliasing.h" #include "llvm/MC/MCInst.h" #include "llvm/Support/Error.h" #include @@ -28,6 +29,8 @@ // Common code for all benchmark modes. class BenchmarkRunner { public: + explicit BenchmarkRunner(const LLVMState &State); + // Subtargets can disable running benchmarks for some instructions by // returning an error here. class InstructionFilter { @@ -42,21 +45,29 @@ virtual ~BenchmarkRunner(); - InstructionBenchmark run(const LLVMState &State, unsigned Opcode, - unsigned NumRepetitions, - const InstructionFilter &Filter) const; + InstructionBenchmark run(unsigned Opcode, const InstructionFilter &Filter, + unsigned NumRepetitions); + +protected: + const LLVMState &State; + const llvm::MCInstrInfo &MCInstrInfo; + const llvm::MCRegisterInfo &MCRegisterInfo; private: virtual const char *getDisplayName() const = 0; virtual llvm::Expected> - createCode(const LLVMState &State, unsigned OpcodeIndex, - unsigned NumRepetitions, - const JitFunctionContext &Context) const = 0; + createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode, + llvm::raw_ostream &Debug) const = 0; virtual std::vector - runMeasurements(const LLVMState &State, const JitFunction &Function, - unsigned NumRepetitions) const = 0; + runMeasurements(const ExecutableFunction &EF, + const unsigned NumRepetitions) const = 0; + + llvm::Expected + writeObjectFile(llvm::ArrayRef Code) const; + + RegisterAliasingTrackerCache RATC; }; } // namespace exegesis Index: tools/llvm-exegesis/lib/BenchmarkRunner.cpp =================================================================== --- tools/llvm-exegesis/lib/BenchmarkRunner.cpp +++ tools/llvm-exegesis/lib/BenchmarkRunner.cpp @@ -7,23 +7,33 @@ // //===----------------------------------------------------------------------===// +#include +#include + +#include "Assembler.h" #include "BenchmarkRunner.h" -#include "InMemoryAssembler.h" +#include "MCInstrDescView.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" -#include +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/Program.h" namespace exegesis { BenchmarkRunner::InstructionFilter::~InstructionFilter() = default; - +BenchmarkRunner::BenchmarkRunner(const LLVMState &State) + : State(State), MCInstrInfo(State.getInstrInfo()), + MCRegisterInfo(State.getRegInfo()), + RATC(MCRegisterInfo, + getFunctionReservedRegs(*State.createTargetMachine())) {} BenchmarkRunner::~BenchmarkRunner() = default; -InstructionBenchmark -BenchmarkRunner::run(const LLVMState &State, const unsigned Opcode, - unsigned NumRepetitions, - const InstructionFilter &Filter) const { +InstructionBenchmark BenchmarkRunner::run(unsigned Opcode, + const InstructionFilter &Filter, + unsigned NumRepetitions) { InstructionBenchmark InstrBenchmark; InstrBenchmark.Key.OpcodeName = State.getInstrInfo().getName(Opcode); @@ -41,36 +51,56 @@ InstrBenchmark.Error = llvm::toString(std::move(E)); return InstrBenchmark; } - - JitFunctionContext Context(State.createTargetMachine()); - auto ExpectedInstructions = - createCode(State, Opcode, NumRepetitions, Context); - if (llvm::Error E = ExpectedInstructions.takeError()) { + llvm::raw_string_ostream InfoStream(InstrBenchmark.Info); + llvm::Expected> SnippetOrError = + createSnippet(RATC, Opcode, InfoStream); + if (llvm::Error E = SnippetOrError.takeError()) { InstrBenchmark.Error = llvm::toString(std::move(E)); return InstrBenchmark; } + std::vector &Snippet = SnippetOrError.get(); + if (Snippet.empty()) { + InstrBenchmark.Error = "Empty snippet"; + return InstrBenchmark; + } - const std::vector Instructions = *ExpectedInstructions; - const JitFunction Function(std::move(Context), Instructions); - const llvm::StringRef CodeBytes = Function.getFunctionBytes(); + InfoStream << "Snippet:\n"; + for (const auto &MCInst : Snippet) { + DumpMCInst(MCRegisterInfo, MCInstrInfo, MCInst, InfoStream); + InfoStream << "\n"; + } + + std::vector Code; + for (int I = 0; I < InstrBenchmark.NumRepetitions; ++I) + Code.push_back(Snippet[I % Snippet.size()]); - std::string AsmExcerpt; - constexpr const int ExcerptSize = 100; - constexpr const int ExcerptTailSize = 10; - if (CodeBytes.size() <= ExcerptSize) { - AsmExcerpt = llvm::toHex(CodeBytes); - } else { - AsmExcerpt = - llvm::toHex(CodeBytes.take_front(ExcerptSize - ExcerptTailSize + 3)); - AsmExcerpt += "..."; - AsmExcerpt += llvm::toHex(CodeBytes.take_back(ExcerptTailSize)); + auto ExpectedObjectPath = writeObjectFile(Code); + if (llvm::Error E = ExpectedObjectPath.takeError()) { + InstrBenchmark.Error = llvm::toString(std::move(E)); + return InstrBenchmark; } - llvm::outs() << "# Asm excerpt: " << AsmExcerpt << "\n"; - llvm::outs().flush(); // In case we crash. - InstrBenchmark.Measurements = - runMeasurements(State, Function, NumRepetitions); + // FIXME: Check if TargetMachine or ExecutionEngine can be reused instead of + // creating one everytime. + const ExecutableFunction EF(State.createTargetMachine(), + getObjectFromFile(*ExpectedObjectPath)); + InstrBenchmark.Measurements = runMeasurements(EF, NumRepetitions); + return InstrBenchmark; } +llvm::Expected +BenchmarkRunner::writeObjectFile(llvm::ArrayRef Code) const { + int ResultFD = 0; + llvm::SmallString<256> ResultPath; + if (llvm::Error E = llvm::errorCodeToError(llvm::sys::fs::createTemporaryFile( + "snippet", "o", ResultFD, ResultPath))) + return std::move(E); + llvm::raw_fd_ostream OFS(ResultFD, true /*ShouldClose*/); + assembleToStream(State.createTargetMachine(), Code, OFS); + llvm::outs() << "Check generated assembly with: /usr/bin/objdump -d " + << ResultPath << "\n"; + return ResultPath.str(); +} + } // namespace exegesis Index: tools/llvm-exegesis/lib/CMakeLists.txt =================================================================== --- tools/llvm-exegesis/lib/CMakeLists.txt +++ tools/llvm-exegesis/lib/CMakeLists.txt @@ -1,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 - OperandGraph.cpp + MCInstrDescView.cpp PerfHelper.cpp + RegisterAliasing.cpp Uops.cpp X86.cpp ) Index: tools/llvm-exegesis/lib/InMemoryAssembler.h =================================================================== --- tools/llvm-exegesis/lib/InMemoryAssembler.h +++ /dev/null @@ -1,82 +0,0 @@ -//===-- InMemoryAssembler.h -------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// Defines classes to assemble functions composed of a single basic block of -/// MCInsts. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H -#define LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H - -#include "llvm/ADT/BitVector.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineModuleInfo.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" -#include "llvm/ExecutionEngine/ExecutionEngine.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/MC/MCInst.h" -#include -#include -#include - -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 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 Context; - std::unique_ptr TM; - std::unique_ptr MMI; - std::unique_ptr 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 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(FunctionBytes.data()); - ((void (*)())(intptr_t)FnData)(); - } - -private: - JitFunctionContext FunctionContext; - std::unique_ptr ExecEngine; - llvm::StringRef FunctionBytes; -}; - -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_INMEMORYASSEMBLER_H Index: tools/llvm-exegesis/lib/InstructionSnippetGenerator.h =================================================================== --- tools/llvm-exegesis/lib/InstructionSnippetGenerator.h +++ /dev/null @@ -1,119 +0,0 @@ -//===-- InstructionSnippetGenerator.h ---------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// Defines helper classes to generate code snippets, in particular register -/// assignment. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H -#define LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H - -#include "OperandGraph.h" -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/MC/MCInst.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCRegisterInfo.h" -#include - -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 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 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 -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; - -// 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 -computeSequentialAssignmentChains(const llvm::MCRegisterInfo &RegInfo, - llvm::ArrayRef 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 -getRandomAssignment(llvm::ArrayRef Vars, - llvm::ArrayRef Chains, - const std::function &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 -getExclusiveAssignment(llvm::ArrayRef 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 -getGreedyAssignment(llvm::ArrayRef 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 Vars, - llvm::ArrayRef VarRegs); - -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H Index: tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp =================================================================== --- tools/llvm-exegesis/lib/InstructionSnippetGenerator.cpp +++ /dev/null @@ -1,355 +0,0 @@ -//===-- InstructionSnippetGenerator.cpp -------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "InstructionSnippetGenerator.h" -#include "llvm/ADT/MapVector.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/MC/MCInstBuilder.h" -#include -#include -#include - -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 &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 -getVariables(const llvm::MCRegisterInfo &RegInfo, - const llvm::MCInstrDesc &InstrInfo, - const llvm::BitVector &ReservedRegs) { - llvm::SmallVector Vars; - // For each operand, its "tied to" operand or -1. - llvm::SmallVector 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 -computeSequentialAssignmentChains(const llvm::MCRegisterInfo &RegInfo, - llvm::ArrayRef 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 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 -getRandomAssignment(llvm::ArrayRef Vars, - llvm::ArrayRef Chains, - const std::function &RandomIndexForSize) { - // Registers are initialized with 0 (aka NoRegister). - std::vector 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 Vars, const size_t VarIdx, - std::unordered_set &Seen, - std::unordered_map &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 -getExclusiveAssignment(llvm::ArrayRef Vars) { - // `RegAssignments[r]` is the variable id that was assigned register `Reg`. - std::unordered_map RegAssignments; - - for (size_t VarIdx = 0, E = Vars.size(); VarIdx < E; ++VarIdx) { - if (!Vars[VarIdx].IsReg) - continue; - std::unordered_set Seen; - if (!findMatchingRegister(Vars, VarIdx, Seen, RegAssignments)) - return {}; // Infeasible. - } - - std::vector Registers(Vars.size(), 0); - for (const auto &RegVarIdx : RegAssignments) - Registers[RegVarIdx.second] = RegVarIdx.first; - return Registers; -} - -std::vector -getGreedyAssignment(llvm::ArrayRef Vars) { - std::vector Registers(Vars.size(), 0); - llvm::SmallSet 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 Vars, - llvm::ArrayRef VarRegs) { - const size_t NumOperands = InstrInfo.getNumOperands(); - llvm::SmallVector OperandToRegister(NumOperands, 0); - - // We browse the variable and for each explicit operands we set the selected - // register in the OperandToRegister array. - for (size_t I = 0, E = Vars.size(); I < E; ++I) { - for (const size_t OpIndex : Vars[I].ExplicitOperands) { - OperandToRegister[OpIndex] = VarRegs[I]; - } - } - - // Building the instruction. - llvm::MCInstBuilder Builder(InstrInfo.getOpcode()); - for (size_t I = 0, E = InstrInfo.getNumOperands(); I < E; ++I) { - const llvm::MCOperandInfo &OpInfo = InstrInfo.opInfo_begin()[I]; - switch (OpInfo.OperandType) { - case llvm::MCOI::OperandType::OPERAND_REGISTER: - Builder.addReg(OperandToRegister[I]); - break; - case llvm::MCOI::OperandType::OPERAND_IMMEDIATE: - Builder.addImm(1); - break; - default: - Builder.addOperand(llvm::MCOperand()); - } - } - - return Builder; -} - -} // namespace exegesis Index: tools/llvm-exegesis/lib/Latency.h =================================================================== --- tools/llvm-exegesis/lib/Latency.h +++ tools/llvm-exegesis/lib/Latency.h @@ -21,19 +21,19 @@ class LatencyBenchmarkRunner : public BenchmarkRunner { public: + using BenchmarkRunner::BenchmarkRunner; ~LatencyBenchmarkRunner() override; private: const char *getDisplayName() const override; llvm::Expected> - createCode(const LLVMState &State, unsigned OpcodeIndex, - unsigned NumRepetitions, - const JitFunctionContext &Context) const override; + createSnippet(RegisterAliasingTrackerCache &RATC, unsigned OpcodeIndex, + llvm::raw_ostream &Info) const override; std::vector - runMeasurements(const LLVMState &State, const JitFunction &Function, - unsigned NumRepetitions) const override; + runMeasurements(const ExecutableFunction &EF, + const unsigned NumRepetitions) const override; }; } // namespace exegesis Index: tools/llvm-exegesis/lib/Latency.cpp =================================================================== --- tools/llvm-exegesis/lib/Latency.cpp +++ tools/llvm-exegesis/lib/Latency.cpp @@ -8,25 +8,41 @@ //===----------------------------------------------------------------------===// #include "Latency.h" -#include "BenchmarkResult.h" -#include "InstructionSnippetGenerator.h" + +#include "Assembler.h" +#include "BenchmarkRunner.h" +#include "MCInstrDescView.h" #include "PerfHelper.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/Support/Error.h" -#include -#include +#include "llvm/ADT/STLExtras.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstBuilder.h" namespace exegesis { +static bool HasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { + return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN; +} + // FIXME: Handle memory, see PR36905. -static bool isInvalidOperand(const llvm::MCOperandInfo &OpInfo) { - switch (OpInfo.OperandType) { - default: +static bool HasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { + return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; +} + +static bool IsInfeasible(const Instruction &Instruction, std::string &Error) { + const auto &MCInstrDesc = Instruction.Description; + if (MCInstrDesc.isPseudo()) { + Error = "is pseudo"; + return true; + } + if (llvm::any_of(MCInstrDesc.operands(), HasUnknownOperand)) { + Error = "has unknown operands"; return true; - case llvm::MCOI::OPERAND_IMMEDIATE: - case llvm::MCOI::OPERAND_REGISTER: - return false; } + if (llvm::any_of(MCInstrDesc.operands(), HasMemoryOperand)) { + Error = "has memory operands"; + return true; + } + return false; } static llvm::Error makeError(llvm::Twine Msg) { @@ -38,39 +54,61 @@ const char *LatencyBenchmarkRunner::getDisplayName() const { return "latency"; } -llvm::Expected> LatencyBenchmarkRunner::createCode( - const LLVMState &State, const unsigned OpcodeIndex, - const unsigned NumRepetitions, const JitFunctionContext &Context) const { - std::default_random_engine RandomEngine; - const auto GetRandomIndex = [&RandomEngine](size_t Size) { - assert(Size > 0 && "trying to get select a random element of an empty set"); - return std::uniform_int_distribution<>(0, Size - 1)(RandomEngine); - }; - - const auto &InstrInfo = State.getInstrInfo(); - const auto &RegInfo = State.getRegInfo(); - const llvm::MCInstrDesc &InstrDesc = InstrInfo.get(OpcodeIndex); - for (const llvm::MCOperandInfo &OpInfo : InstrDesc.operands()) { - if (isInvalidOperand(OpInfo)) - return makeError("Only registers and immediates are supported"); +llvm::Expected> +LatencyBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC, + unsigned Opcode, + llvm::raw_ostream &Info) const { + std::vector 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 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; } - const auto Vars = getVariables(RegInfo, InstrDesc, Context.getReservedRegs()); - const std::vector AssignmentChains = - computeSequentialAssignmentChains(RegInfo, Vars); - if (AssignmentChains.empty()) - return makeError("Unable to find a dependency chain."); - const std::vector 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(NumRepetitions, Inst); + return makeError( + "Infeasible : Didn't find any scheme to make the instruction serial\n"); } std::vector -LatencyBenchmarkRunner::runMeasurements(const LLVMState &State, - const JitFunction &Function, +LatencyBenchmarkRunner::runMeasurements(const ExecutableFunction &Function, const unsigned NumRepetitions) const { // Cycle measurements include some overhead from the kernel. Repeat the // measure several times and take the minimum value. Index: tools/llvm-exegesis/lib/LlvmState.h =================================================================== --- tools/llvm-exegesis/lib/LlvmState.h +++ tools/llvm-exegesis/lib/LlvmState.h @@ -6,6 +6,11 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +/// +/// \file +/// A class to set up and access common LLVM objects. +/// +//===----------------------------------------------------------------------===// #ifndef LLVM_TOOLS_LLVM_EXEGESIS_LLVMSTATE_H #define LLVM_TOOLS_LLVM_EXEGESIS_LLVMSTATE_H Index: tools/llvm-exegesis/lib/MCInstrDescView.h =================================================================== --- /dev/null +++ tools/llvm-exegesis/lib/MCInstrDescView.h @@ -0,0 +1,150 @@ +//===-- 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 + +#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 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 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 Operands; + llvm::SmallVector 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 Defs; // Unlikely size() > 1. + llvm::SmallVector 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 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 Index: tools/llvm-exegesis/lib/MCInstrDescView.cpp =================================================================== --- /dev/null +++ tools/llvm-exegesis/lib/MCInstrDescView.cpp @@ -0,0 +1,268 @@ +//===-- 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 +#include +#include + +#include "llvm/ADT/STLExtras.h" + +namespace exegesis { + +static void tie(const Operand *FromOperand, llvm::Optional &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 Operands, + llvm::SmallVectorImpl &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 +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 Index: tools/llvm-exegesis/lib/OperandGraph.h =================================================================== --- tools/llvm-exegesis/lib/OperandGraph.h +++ /dev/null @@ -1,89 +0,0 @@ -//===-- OperandGraph.h ------------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// A collection of tools to model register aliasing and instruction operand. -/// This is used to find an aliasing between the input and output registers of -/// an instruction. It allows us to repeat an instruction and make sure that -/// successive instances are executed sequentially. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H -#define LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H - -#include "llvm/MC/MCRegisterInfo.h" -#include -#include -#include -#include - -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 { - using std::pair::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 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; - - // 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 &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 AdjacencyLists; -}; - -// Add register nodes to graph and connect them when they alias. Connection is -// both ways. -void setupRegisterAliasing(const llvm::MCRegisterInfo &RegInfo, - Graph &TheGraph); - -} // namespace graph -} // namespace exegesis - -#endif // LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H Index: tools/llvm-exegesis/lib/OperandGraph.cpp =================================================================== --- tools/llvm-exegesis/lib/OperandGraph.cpp +++ /dev/null @@ -1,115 +0,0 @@ -//===-- OperandGraph.cpp ----------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "OperandGraph.h" -#include "llvm/MC/MCRegisterInfo.h" - -namespace exegesis { -namespace graph { - -void Node::dump(const llvm::MCRegisterInfo &RegInfo) const { - switch (type()) { - case NodeType::VARIABLE: - printf(" %d", varValue()); - break; - case NodeType::REG: - printf(" %s", RegInfo.getName(regValue())); - break; - case NodeType::IN: - printf(" IN"); - break; - case NodeType::OUT: - printf(" OUT"); - break; - } -} - -NodeType Node::type() const { return first; } - -int Node::regValue() const { - assert(first == NodeType::REG && "regValue() called on non-reg"); - return second; -} - -int Node::varValue() const { - assert(first == NodeType::VARIABLE && "varValue() called on non-var"); - return second; -} - -void Graph::connect(const Node From, const Node To) { - AdjacencyLists[From].insert(To); -} - -void Graph::disconnect(const Node From, const Node To) { - AdjacencyLists[From].erase(To); -} - -std::vector Graph::getPathFrom(const Node From, const Node To) const { - std::vector 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 &Path, NodeSet &Seen) const { - Path.push_back(Current); - Seen.insert(Current); - if (Current == Sentinel) - return true; - if (AdjacencyLists.count(Current)) { - for (const Node Next : AdjacencyLists.find(Current)->second) { - if (Seen.count(Next)) - continue; - if (dfs(Next, Sentinel, Path, Seen)) - return true; - } - } - Path.pop_back(); - return false; -} - -// For each Register Units we walk up their parents. -// Let's take the case of the A register family: -// -// RAX -// ^ -// EAX -// ^ -// AX -// ^ ^ -// AH AL -// -// Register Units are AH and AL. -// Walking them up gives the following lists: -// AH->AX->EAX->RAX and AL->AX->EAX->RAX -// When walking the lists we add connect current to parent both ways leading to -// the following connections: -// -// AL<->AX, AH<->AX, AX<->EAX, EAX<->RAX -// We repeat this process for all Unit Registers to cover all connections. -void setupRegisterAliasing(const llvm::MCRegisterInfo &RegInfo, - Graph &TheGraph) { - using SuperItr = llvm::MCSuperRegIterator; - for (size_t Reg = 0, E = RegInfo.getNumRegUnits(); Reg < E; ++Reg) { - size_t Current = Reg; - for (SuperItr Super(Reg, &RegInfo); Super.isValid(); ++Super) { - const Node A = Node::Reg(Current); - const Node B = Node::Reg(*Super); - TheGraph.connect(A, B); - TheGraph.connect(B, A); - Current = *Super; - } - } -} - -} // namespace graph -} // namespace exegesis Index: tools/llvm-exegesis/lib/RegisterAliasing.h =================================================================== --- /dev/null +++ tools/llvm-exegesis/lib/RegisterAliasing.h @@ -0,0 +1,107 @@ +//===-- 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 +#include + +#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 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> + Registers; + std::unordered_map> + RegisterClasses; +}; + +} // namespace exegesis + +#endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H Index: tools/llvm-exegesis/lib/RegisterAliasing.cpp =================================================================== --- /dev/null +++ tools/llvm-exegesis/lib/RegisterAliasing.cpp @@ -0,0 +1,83 @@ +//===-- 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 Index: tools/llvm-exegesis/lib/Uops.h =================================================================== --- tools/llvm-exegesis/lib/Uops.h +++ tools/llvm-exegesis/lib/Uops.h @@ -21,19 +21,19 @@ class UopsBenchmarkRunner : public BenchmarkRunner { public: + using BenchmarkRunner::BenchmarkRunner; ~UopsBenchmarkRunner() override; private: const char *getDisplayName() const override; llvm::Expected> - createCode(const LLVMState &State, unsigned OpcodeIndex, - unsigned NumRepetitions, - const JitFunctionContext &Context) const override; + createSnippet(RegisterAliasingTrackerCache &RATC, unsigned Opcode, + llvm::raw_ostream &Info) const override; std::vector - runMeasurements(const LLVMState &State, const JitFunction &Function, - unsigned NumRepetitions) const override; + runMeasurements(const ExecutableFunction &EF, + const unsigned NumRepetitions) const override; }; } // namespace exegesis Index: tools/llvm-exegesis/lib/Uops.cpp =================================================================== --- tools/llvm-exegesis/lib/Uops.cpp +++ tools/llvm-exegesis/lib/Uops.cpp @@ -8,183 +8,220 @@ //===----------------------------------------------------------------------===// #include "Uops.h" -#include "BenchmarkResult.h" -#include "InstructionSnippetGenerator.h" + +#include "Assembler.h" +#include "BenchmarkRunner.h" +#include "MCInstrDescView.h" #include "PerfHelper.h" -#include "llvm/ADT/StringExtras.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCSchedule.h" -#include "llvm/Support/Error.h" -#include -#include -#include -#include + +// 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. namespace exegesis { -// FIXME: Handle memory (see PR36906) -static bool isInvalidOperand(const llvm::MCOperandInfo &OpInfo) { - switch (OpInfo.OperandType) { - default: - return true; - case llvm::MCOI::OPERAND_IMMEDIATE: - case llvm::MCOI::OPERAND_REGISTER: - return false; - } +static bool hasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { + return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN; } -static llvm::Error makeError(llvm::Twine Msg) { - return llvm::make_error(Msg, - llvm::inconvertibleErrorCode()); +// FIXME: Handle memory, see PR36905. +static bool hasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { + return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; } -static std::vector generateIndependentAssignments( - const LLVMState &State, const llvm::MCInstrDesc &InstrDesc, - llvm::SmallVector Vars, int MaxAssignments) { - std::unordered_set IsUsedByAnyVar; - for (const Variable &Var : Vars) { - if (Var.IsUse) { - IsUsedByAnyVar.insert(Var.PossibleRegisters.begin(), - Var.PossibleRegisters.end()); - } +static bool isInfeasible(const Instruction &Instruction, std::string &Error) { + const auto &MCInstrDesc = Instruction.Description; + if (MCInstrDesc.isPseudo()) { + Error = "is pseudo"; + return true; } + if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) { + Error = "has unknown operands"; + return true; + } + if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) { + Error = "has memory operands"; + return true; + } + return false; +} - std::vector 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 Regs = getExclusiveAssignment(Vars); - if (Regs.empty()) - break; - // Remove all assigned registers defs that are used by at least one other - // variable from the list of possible variable registers. This ensures that - // we never create a RAW hazard that would lead to serialization. - for (size_t I = 0, E = Vars.size(); I < E; ++I) { - llvm::MCPhysReg Reg = Regs[I]; - if (Vars[I].IsDef && IsUsedByAnyVar.count(Reg)) { - Vars[I].PossibleRegisters.remove(Reg); - } - } - // Create an MCInst and check assembly. - llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs); - if (!State.canAssemble(Inst)) - continue; - Pattern.push_back(std::move(Inst)); +// Returns whether this Variable ties Use and Def operands together. +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 Pattern; + return HasUse && HasDef; +} + +static llvm::SmallVector +getTiedVariables(const Instruction &Instruction) { + llvm::SmallVector Result; + for (auto *Var : Instruction.Variables) + if (hasTiedOperands(Var)) + Result.push_back(Var); + return Result; +} + +static void remove(llvm::BitVector &a, const llvm::BitVector &b) { + assert(a.size() == b.size()); + for (auto I : b.set_bits()) + a.reset(I); +} + +static llvm::Error makeError(llvm::Twine Msg) { + return llvm::make_error(Msg, + llvm::inconvertibleErrorCode()); } UopsBenchmarkRunner::~UopsBenchmarkRunner() = default; const char *UopsBenchmarkRunner::getDisplayName() const { return "uops"; } -llvm::Expected> UopsBenchmarkRunner::createCode( - const LLVMState &State, const unsigned OpcodeIndex, - const unsigned NumRepetitions, const JitFunctionContext &Context) const { - const auto &InstrInfo = State.getInstrInfo(); - const auto &RegInfo = State.getRegInfo(); - const llvm::MCInstrDesc &InstrDesc = InstrInfo.get(OpcodeIndex); - for (const llvm::MCOperandInfo &OpInfo : InstrDesc.operands()) { - if (isInvalidOperand(OpInfo)) - return makeError("Only registers and immediates are supported"); +llvm::Expected> +UopsBenchmarkRunner::createSnippet(RegisterAliasingTrackerCache &RATC, + unsigned Opcode, + llvm::raw_ostream &Info) const { + std::vector 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)); } - // 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 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 Regs = getGreedyAssignment(Vars); - if (!Vars.empty() && Regs.empty()) - return makeError("No feasible greedy assignment"); - llvm::MCInst Inst = generateMCInst(InstrDesc, Vars, Regs); - if (!State.canAssemble(Inst)) - return makeError("Cannot assemble greedy assignment"); - Pattern.push_back(std::move(Inst)); + const AliasingConfigurations SelfAliasing(Instruction, Instruction); + if (SelfAliasing.empty()) { + Info << "instruction is parallel, repeating a random one.\n"; + Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); + return Snippet; } - - // Generate repetitions of the pattern until benchmark_iterations is reached. - std::vector Result; - Result.reserve(NumRepetitions); - for (unsigned I = 0; I < NumRepetitions; ++I) - Result.push_back(Pattern[I % Pattern.size()]); - return Result; + if (SelfAliasing.hasImplicitAliasing()) { + Info << "instruction is serial, repeating a random one.\n"; + Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); + return Snippet; + } + const auto TiedVariables = getTiedVariables(Instruction); + if (!TiedVariables.empty()) { + if (TiedVariables.size() > 1) { + Info << "Not yet implemented, don't know how to handle several tied " + "variables\n"; + return makeError("Infeasible : don't know how to handle several tied " + "variables"); + } + Info << "instruction has tied variables using static renaming.\n"; + Variable *Var = TiedVariables.front(); + assert(Var); + assert(!Var->TiedOperands.empty()); + const Operand &Operand = *Var->TiedOperands.front(); + assert(Operand.Tracker); + for (const llvm::MCPhysReg Reg : Operand.Tracker->sourceBits().set_bits()) { + clearVariableAssignments(Instruction); + Var->AssignedValue = llvm::MCOperand::createReg(Reg); + Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); + } + return Snippet; + } + // No tied variables, we pick random values for defs. + llvm::BitVector Defs(MCRegisterInfo.getNumRegs()); + for (const auto &Op : Instruction.Operands) { + if (Op.Tracker && Op.IsExplicit && Op.IsDef) { + assert(Op.Var); + auto PossibleRegisters = Op.Tracker->sourceBits(); + remove(PossibleRegisters, RATC.reservedRegisters()); + assert(PossibleRegisters.any() && "No register left to choose from"); + const auto RandomReg = randomBit(PossibleRegisters); + Defs.set(RandomReg); + Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg); + } + } + // And pick random use values that are not reserved and don't alias with defs. + const auto DefAliases = getAliasedBits(MCRegisterInfo, Defs); + for (const auto &Op : Instruction.Operands) { + if (Op.Tracker && Op.IsExplicit && !Op.IsDef) { + assert(Op.Var); + auto PossibleRegisters = Op.Tracker->sourceBits(); + remove(PossibleRegisters, RATC.reservedRegisters()); + remove(PossibleRegisters, DefAliases); + assert(PossibleRegisters.any() && "No register left to choose from"); + const auto RandomReg = randomBit(PossibleRegisters); + Op.Var->AssignedValue = llvm::MCOperand::createReg(RandomReg); + } + } + Info + << "instruction has no tied variables picking Uses different from defs\n"; + Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); + return Snippet; } std::vector -UopsBenchmarkRunner::runMeasurements(const LLVMState &State, - const JitFunction &Function, +UopsBenchmarkRunner::runMeasurements(const ExecutableFunction &Function, const unsigned NumRepetitions) const { const auto &SchedModel = State.getSubtargetInfo().getSchedModel(); @@ -197,7 +234,11 @@ continue; // FIXME: Sum results when there are several counters for a single ProcRes // (e.g. P23 on SandyBridge). - pfm::Counter Counter{pfm::PerfEvent(PfmCounters)}; + pfm::PerfEvent UopPerfEvent(PfmCounters); + if (!UopPerfEvent.valid()) + llvm::report_fatal_error( + llvm::Twine("invalid perf event ").concat(PfmCounters)); + pfm::Counter Counter(UopPerfEvent); Counter.start(); Function(); Counter.stop(); Index: tools/llvm-exegesis/llvm-exegesis.cpp =================================================================== --- tools/llvm-exegesis/llvm-exegesis.cpp +++ tools/llvm-exegesis/llvm-exegesis.cpp @@ -76,14 +76,23 @@ 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(); @@ -92,37 +101,26 @@ 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 Runner; switch (BenchmarkMode) { case BenchmarkModeE::Latency: - Runner = llvm::make_unique(); + Runner = llvm::make_unique(State); break; case BenchmarkModeE::Uops: - Runner = llvm::make_unique(); + Runner = llvm::make_unique(State); break; case BenchmarkModeE::Analysis: llvm_unreachable("not a benchmark"); } - Runner->run(State, Opcode, NumRepetitions > 0 ? NumRepetitions : 1, Filter) + if (NumRepetitions == 0) + llvm::report_fatal_error("--num-repetitions must be greater than zero"); + + Runner->run(GetOpcodeOrDie(State.getInstrInfo()), Filter, NumRepetitions) .writeYamlOrDie(BenchmarkFile); exegesis::pfm::pfmTerminate(); } Index: unittests/tools/llvm-exegesis/CMakeLists.txt =================================================================== --- unittests/tools/llvm-exegesis/CMakeLists.txt +++ unittests/tools/llvm-exegesis/CMakeLists.txt @@ -13,7 +13,6 @@ add_llvm_unittest(LLVMExegesisTests BenchmarkResultTest.cpp ClusteringTest.cpp - OperandGraphTest.cpp PerfHelperTest.cpp ) target_link_libraries(LLVMExegesisTests PRIVATE LLVMExegesis) Index: unittests/tools/llvm-exegesis/OperandGraphTest.cpp =================================================================== --- unittests/tools/llvm-exegesis/OperandGraphTest.cpp +++ /dev/null @@ -1,48 +0,0 @@ -//===-- OperandGraphTest.cpp ------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "OperandGraph.h" -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -using testing::ElementsAre; -using testing::IsEmpty; -using testing::Not; - -namespace exegesis { -namespace graph { -namespace { - -static const auto In = Node::In(); -static const auto Out = Node::Out(); - -TEST(OperandGraphTest, NoPath) { - Graph TheGraph; - EXPECT_THAT(TheGraph.getPathFrom(In, Out), IsEmpty()); -} - -TEST(OperandGraphTest, Connecting) { - Graph TheGraph; - TheGraph.connect(In, Out); - EXPECT_THAT(TheGraph.getPathFrom(In, Out), Not(IsEmpty())); - EXPECT_THAT(TheGraph.getPathFrom(In, Out), ElementsAre(In, Out)); -} - -TEST(OperandGraphTest, ConnectingThroughVariable) { - const Node Var = Node::Var(1); - Graph TheGraph; - TheGraph.connect(In, Var); - TheGraph.connect(Var, Out); - EXPECT_THAT(TheGraph.getPathFrom(In, Out), Not(IsEmpty())); - EXPECT_THAT(TheGraph.getPathFrom(In, Out), ElementsAre(In, Var, Out)); -} - -} // namespace -} // namespace graph -} // namespace exegesis Index: unittests/tools/llvm-exegesis/X86/CMakeLists.txt =================================================================== --- unittests/tools/llvm-exegesis/X86/CMakeLists.txt +++ unittests/tools/llvm-exegesis/X86/CMakeLists.txt @@ -14,8 +14,7 @@ ) add_llvm_unittest(LLVMExegesisX86Tests + RegisterAliasingTest.cpp InMemoryAssemblerTest.cpp - InstructionSnippetGeneratorTest.cpp ) target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis) - Index: unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp =================================================================== --- unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp +++ unittests/tools/llvm-exegesis/X86/InMemoryAssemblerTest.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// -#include "InMemoryAssembler.h" +#include "Assembler.h" #include "X86InstrInfo.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -51,8 +51,8 @@ llvm::TargetRegistry::lookupTarget(TT, Error); EXPECT_TRUE(TheTarget) << Error << " " << TT; const llvm::TargetOptions Options; - llvm::TargetMachine* TM = TheTarget->createTargetMachine( - TT, CpuName, "", Options, llvm::Reloc::Model::Static); + llvm::TargetMachine *TM = TheTarget->createTargetMachine( + TT, CpuName, "", Options, llvm::Reloc::Model::Static); EXPECT_TRUE(TM) << TT << " " << CpuName; return std::unique_ptr( static_cast(TM)); @@ -62,58 +62,66 @@ return llvm::StringRef(TT).startswith_lower("x86_64"); } + ExecutableFunction assembleFunction(llvm::MCInst MCInst) { + return assembleToFunction({MCInst}); + } + + ExecutableFunction assembleEmptyFunction() { return assembleToFunction({}); } + private: + ExecutableFunction + assembleToFunction(llvm::ArrayRef Instructions) { + llvm::SmallString<256> Buffer; + llvm::raw_svector_ostream AsmStream(Buffer); + assembleToStream(createTargetMachine(), Instructions, AsmStream); + return ExecutableFunction(createTargetMachine(), + getObjectFromBuffer(AsmStream.str())); + } const std::string TT; const std::string CpuName; }; // Used to skip tests on unsupported architectures and operating systems. // To skip a test, add this macro at the top of a test-case. -#define SKIP_UNSUPPORTED_PLATFORM \ - do \ - if (!IsSupportedTarget()) \ - return; \ - while(0) - +#define SKIP_UNSUPPORTED_PLATFORM \ + do \ + if (!IsSupportedTarget()) \ + return; \ + while (0) -TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunction) { +TEST_F(MachineFunctionGeneratorTest, JitFunction) { SKIP_UNSUPPORTED_PLATFORM; - JitFunctionContext Context(createTargetMachine()); - JitFunction Function(std::move(Context), {}); + const ExecutableFunction Function = assembleEmptyFunction(); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0xc3)); // FIXME: Check that the function runs without errors. Right now this is // disabled because it fails on some bots. - // Function(); + Function(); } -TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionXOR32rr) { +TEST_F(MachineFunctionGeneratorTest, JitFunctionXOR32rr) { SKIP_UNSUPPORTED_PLATFORM; - JitFunctionContext Context(createTargetMachine()); - JitFunction Function( - std::move(Context), - {MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX)}); + const ExecutableFunction Function = assembleFunction( + MCInstBuilder(XOR32rr).addReg(EAX).addReg(EAX).addReg(EAX)); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0x31, 0xc0, 0xc3)); - // Function(); + Function(); } -TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV64ri) { +TEST_F(MachineFunctionGeneratorTest, JitFunctionMOV64ri) { SKIP_UNSUPPORTED_PLATFORM; - JitFunctionContext Context(createTargetMachine()); - JitFunction Function(std::move(Context), - {MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42)}); + const ExecutableFunction Function = + assembleFunction(MCInstBuilder(MOV64ri32).addReg(RAX).addImm(42)); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0x48, 0xc7, 0xc0, 0x2a, 0x00, 0x00, 0x00, 0xc3)); - // Function(); + Function(); } -TEST_F(MachineFunctionGeneratorTest, DISABLED_JitFunctionMOV32ri) { +TEST_F(MachineFunctionGeneratorTest, JitFunctionMOV32ri) { SKIP_UNSUPPORTED_PLATFORM; - JitFunctionContext Context(createTargetMachine()); - JitFunction Function(std::move(Context), - {MCInstBuilder(MOV32ri).addReg(EAX).addImm(42)}); + const ExecutableFunction Function = + assembleFunction(MCInstBuilder(MOV32ri).addReg(EAX).addImm(42)); ASSERT_THAT(Function.getFunctionBytes().str(), ElementsAre(0xb8, 0x2a, 0x00, 0x00, 0x00, 0xc3)); - // Function(); + Function(); } } // namespace Index: unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp =================================================================== --- unittests/tools/llvm-exegesis/X86/InstructionSnippetGeneratorTest.cpp +++ /dev/null @@ -1,309 +0,0 @@ -//===-- InstructionSnippetGeneratorTest.cpp ---------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "InstructionSnippetGenerator.h" -#include "X86InstrInfo.h" -#include "llvm/MC/MCInstBuilder.h" -#include "llvm/Support/Host.h" -#include "llvm/Support/TargetRegistry.h" -#include "llvm/Support/TargetSelect.h" -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include -#include - -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 InstrInfo; - std::unique_ptr 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 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 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 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 Vars = { - makeVariableWithRegisters(true, {4}), - makeVariableWithRegisters(true, {4}), - }; - const auto Regs = getExclusiveAssignment(Vars); - EXPECT_THAT(Regs, ElementsAre()); -} - -TEST(getExclusiveAssignment, Feasible1) { - const std::vector 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 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 Vars = { - makeVariableWithRegisters(true, {}), - makeVariableWithRegisters(true, {1, 2}), - }; - const auto Regs = getGreedyAssignment(Vars); - ASSERT_THAT(Regs, ElementsAre()); -} - -TEST(getGreedyAssignment, FeasibleNoFallback) { - const std::vector 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 Vars = { - makeVariableWithRegisters(false, {}), - makeVariableWithRegisters(true, {1, 2}), - makeVariableWithRegisters(true, {2, 3}), - makeVariableWithRegisters(true, {2, 3}), - makeVariableWithRegisters(true, {2, 3}), - }; - const auto Regs = getGreedyAssignment(Vars); - ASSERT_THAT(Regs, ElementsAre(0, 1, 2, 3, 2)); -} - -} // namespace -} // namespace exegesis Index: unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp =================================================================== --- /dev/null +++ unittests/tools/llvm-exegesis/X86/RegisterAliasingTest.cpp @@ -0,0 +1,82 @@ +#include "RegisterAliasing.h" + +#include +#include + +#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 MCRegInfo; +}; + +TEST_F(RegisterAliasingTest, TrackSimpleRegister) { + const auto &RegInfo = getMCRegInfo(); + const RegisterAliasingTracker tracker(RegInfo, llvm::X86::EAX); + const std::set ActualAliasedRegisters( + tracker.aliasedBits().set_bits().begin(), + tracker.aliasedBits().set_bits().end()); + const std::set 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