Index: tools/llvm-exegesis/lib/BenchmarkRunner.h =================================================================== --- tools/llvm-exegesis/lib/BenchmarkRunner.h +++ tools/llvm-exegesis/lib/BenchmarkRunner.h @@ -26,6 +26,13 @@ namespace exegesis { +// A class representing failures that happened during Benchmark, they are used +// to report informations to the user. +class BenchmarkFailure : public llvm::StringError { +public: + BenchmarkFailure(const llvm::Twine &S); +}; + // A collection of instructions that are to be assembled, executed and measured. struct BenchmarkConfiguration { // This code is run before the Snippet is iterated. Since it is part of the @@ -67,6 +74,7 @@ const LLVMState &State; const llvm::MCInstrInfo &MCInstrInfo; const llvm::MCRegisterInfo &MCRegisterInfo; + const RegisterAliasingTrackerCache RATC; private: InstructionBenchmark runOne(const BenchmarkConfiguration &Configuration, @@ -75,8 +83,7 @@ virtual InstructionBenchmark::ModeE getMode() const = 0; virtual llvm::Expected> - createConfigurations(RegisterAliasingTrackerCache &RATC, - unsigned Opcode) const = 0; + createConfigurations(unsigned Opcode) const = 0; virtual std::vector runMeasurements(const ExecutableFunction &EF, @@ -84,8 +91,6 @@ 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 @@ -23,6 +23,9 @@ namespace exegesis { +BenchmarkFailure::BenchmarkFailure(const llvm::Twine &S) + : llvm::StringError(S, llvm::inconvertibleErrorCode()) {} + BenchmarkRunner::InstructionFilter::~InstructionFilter() = default; BenchmarkRunner::BenchmarkRunner(const LLVMState &State) @@ -38,14 +41,13 @@ unsigned NumRepetitions) { // Ignore instructions that we cannot run. if (State.getInstrInfo().get(Opcode).isPseudo()) - return llvm::make_error("Unsupported opcode: isPseudo", - llvm::inconvertibleErrorCode()); + return llvm::make_error("Unsupported opcode: isPseudo"); if (llvm::Error E = Filter.shouldRun(State, Opcode)) return std::move(E); llvm::Expected> ConfigurationOrError = - createConfigurations(RATC, Opcode); + createConfigurations(Opcode); if (llvm::Error E = ConfigurationOrError.takeError()) return std::move(E); Index: tools/llvm-exegesis/lib/Latency.h =================================================================== --- tools/llvm-exegesis/lib/Latency.h +++ tools/llvm-exegesis/lib/Latency.h @@ -16,6 +16,7 @@ #define LLVM_TOOLS_LLVM_EXEGESIS_LATENCY_H #include "BenchmarkRunner.h" +#include "MCInstrDescView.h" namespace exegesis { @@ -24,12 +25,24 @@ using BenchmarkRunner::BenchmarkRunner; ~LatencyBenchmarkRunner() override; + llvm::Expected + generateConfiguration(unsigned Opcode) const; + private: + llvm::Error isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const; + + llvm::Expected generateSelfAliasingConfiguration( + const Instruction &Instr, + const AliasingConfigurations &SelfAliasing) const; + + llvm::Expected generateTwoInstructionConfiguration( + const Instruction &Instr, + const AliasingConfigurations &SelfAliasing) const; + InstructionBenchmark::ModeE getMode() const override; llvm::Expected> - createConfigurations(RegisterAliasingTrackerCache &RATC, - unsigned OpcodeIndex) const override; + createConfigurations(unsigned OpcodeIndex) const override; std::vector runMeasurements(const ExecutableFunction &EF, Index: tools/llvm-exegesis/lib/Latency.cpp =================================================================== --- tools/llvm-exegesis/lib/Latency.cpp +++ tools/llvm-exegesis/lib/Latency.cpp @@ -19,93 +19,113 @@ namespace exegesis { -static bool HasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { +static bool hasUnknownOperand(const llvm::MCOperandInfo &OpInfo) { return OpInfo.OperandType == llvm::MCOI::OPERAND_UNKNOWN; } // FIXME: Handle memory, see PR36905. -static bool HasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { +static bool hasMemoryOperand(const llvm::MCOperandInfo &OpInfo) { return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; } -static bool IsInfeasible(const Instruction &Instruction, std::string &Error) { - const auto &MCInstrDesc = Instruction.Description; - if (MCInstrDesc.isPseudo()) { - Error = "is pseudo"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), HasUnknownOperand)) { - Error = "has unknown operands"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), HasMemoryOperand)) { - Error = "has memory operands"; - return true; - } - return false; -} - LatencyBenchmarkRunner::~LatencyBenchmarkRunner() = default; InstructionBenchmark::ModeE LatencyBenchmarkRunner::getMode() const { return InstructionBenchmark::Latency; } -llvm::Expected> -LatencyBenchmarkRunner::createConfigurations(RegisterAliasingTrackerCache &RATC, - unsigned Opcode) const { - const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode); - const Instruction ThisInstruction(MCInstrDesc, RATC); - - std::string Error; - if (IsInfeasible(ThisInstruction, Error)) - return llvm::make_error( - llvm::Twine("Infeasible : ").concat(Error), - llvm::inconvertibleErrorCode()); +llvm::Error LatencyBenchmarkRunner::isInfeasible( + const llvm::MCInstrDesc &MCInstrDesc) const { + if (MCInstrDesc.isPseudo()) + return llvm::make_error("Infeasible : is pseudo"); + if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) + return llvm::make_error( + "Infeasible : has unknown operands"); + if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) + return llvm::make_error( + "Infeasible : has memory operands"); + return llvm::Error::success(); +} +llvm::Expected +LatencyBenchmarkRunner::generateSelfAliasingConfiguration( + const Instruction &Instr, + const AliasingConfigurations &SelfAliasing) const { BenchmarkConfiguration Conf; - const AliasingConfigurations SelfAliasing(ThisInstruction, ThisInstruction); - if (!SelfAliasing.empty()) { - if (!SelfAliasing.hasImplicitAliasing()) { - Conf.Info = "explicit self cycles, selecting one aliasing Conf."; - setRandomAliasing(SelfAliasing); - } else { - Conf.Info = "implicit Self cycles, picking random values."; - } - Conf.Snippet = {randomizeUnsetVariablesAndBuild(ThisInstruction)}; - return std::vector{Conf}; + InstructionInstance II(Instr); + if (SelfAliasing.hasImplicitAliasing()) { + Conf.Info = "implicit Self cycles, picking random values."; + } else { + Conf.Info = "explicit self cycles, selecting one aliasing Conf."; + // This is a self aliasing instruction so defs and uses are from the same + // instance, hence twice II in the following call. + setRandomAliasing(SelfAliasing, II, II); } + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; + return Conf; +} - // Let's try to create a dependency through another opcode. +llvm::Expected +LatencyBenchmarkRunner::generateTwoInstructionConfiguration( + const Instruction &Instr, + const AliasingConfigurations &SelfAliasing) const { 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) + if (OtherOpcode == Instr.Description.Opcode) continue; - const Instruction OtherInstruction(MCInstrInfo.get(OtherOpcode), RATC); - if (IsInfeasible(OtherInstruction, Error)) + const auto &OtherInstrDesc = MCInstrInfo.get(OtherOpcode); + if (auto E = isInfeasible(OtherInstrDesc)) { + llvm::consumeError(std::move(E)); continue; - const AliasingConfigurations Forward(ThisInstruction, OtherInstruction); - const AliasingConfigurations Back(OtherInstruction, ThisInstruction); + } + const Instruction OtherInstr(OtherInstrDesc, RATC); + const AliasingConfigurations Forward(Instr, OtherInstr); + const AliasingConfigurations Back(OtherInstr, Instr); if (Forward.empty() || Back.empty()) continue; - setRandomAliasing(Forward); - setRandomAliasing(Back); + InstructionInstance ThisII(Instr); + InstructionInstance OtherII(OtherInstr); + if (!Forward.hasImplicitAliasing()) + setRandomAliasing(Forward, ThisII, OtherII); + if (!Back.hasImplicitAliasing()) + setRandomAliasing(Back, OtherII, ThisII); + BenchmarkConfiguration Conf; Conf.Info = llvm::Twine("creating cycle through ") .concat(MCInstrInfo.getName(OtherOpcode)) .concat(".") .str(); - Conf.Snippet.push_back(randomizeUnsetVariablesAndBuild(ThisInstruction)); - Conf.Snippet.push_back(randomizeUnsetVariablesAndBuild(OtherInstruction)); - return std::vector{Conf}; + Conf.Snippet.push_back(ThisII.randomizeUnsetVariablesAndBuild()); + Conf.Snippet.push_back(OtherII.randomizeUnsetVariablesAndBuild()); + return Conf; + } + return llvm::make_error( + "Infeasible : Didn't find any scheme to make the instruction serial"); +} + +llvm::Expected +LatencyBenchmarkRunner::generateConfiguration(unsigned Opcode) const { + const auto &InstrDesc = MCInstrInfo.get(Opcode); + if (auto E = isInfeasible(InstrDesc)) + return std::move(E); + const Instruction Instr(InstrDesc, RATC); + const AliasingConfigurations SelfAliasing(Instr, Instr); + if (SelfAliasing.empty()) { + // No self aliasing, trying to create a dependency through another opcode. + return generateTwoInstructionConfiguration(Instr, SelfAliasing); + } else { + return generateSelfAliasingConfiguration(Instr, SelfAliasing); } +} - return llvm::make_error( - "Infeasible : Didn't find any scheme to make the instruction serial", - llvm::inconvertibleErrorCode()); +llvm::Expected> +LatencyBenchmarkRunner::createConfigurations(unsigned Opcode) const { + if (auto E = generateConfiguration(Opcode)) + return std::vector{E.get()}; + else + return E.takeError(); } std::vector Index: tools/llvm-exegesis/lib/MCInstrDescView.h =================================================================== --- tools/llvm-exegesis/lib/MCInstrDescView.h +++ tools/llvm-exegesis/lib/MCInstrDescView.h @@ -32,11 +32,14 @@ struct Operand; // forward declaration. -// A variable represents the value of an Operand or a set of Operands if they ar -// tied together. +// A variable represents the value associated to an Operand or a set of Operands +// if they are tied together. struct Variable { llvm::SmallVector TiedOperands; llvm::MCOperand AssignedValue; + // The index of this Variable in Instruction.Variables and its associated + // Value in InstructionInstance.VariableValues. + unsigned Index = -1; }; // MCOperandInfo can only represents Explicit operands. This object gives a @@ -46,35 +49,50 @@ // - 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. +// - TiedToIndex: the index of the Operand holding the value or -1. // - 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. +// - VariableIndex: the index of the Variable holding the value for this Operand +// or -1 if this operand is implicit. struct Operand { - uint8_t Index = 0; + unsigned 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. + int TiedToIndex = -1; // Set for Reg/Explicit Op. const llvm::MCPhysReg *ImplicitReg = nullptr; // Set for Implicit Op. - mutable llvm::Optional Var; // Set for Explicit Op. + int VariableIndex = -1; // Set for Reg/Explicit Op. }; // A view over an MCInstrDesc offering a convenient interface to compute -// Register aliasing and assign values to Operands. +// Register aliasing. struct Instruction { Instruction(const llvm::MCInstrDesc &MCInstrDesc, - RegisterAliasingTrackerCache &ATC); + const RegisterAliasingTrackerCache &ATC); const llvm::MCInstrDesc &Description; llvm::SmallVector Operands; - llvm::SmallVector Variables; + llvm::SmallVector Variables; llvm::BitVector DefRegisters; // The union of the aliased def registers. llvm::BitVector UseRegisters; // The union of the aliased use registers. }; +// An instance of an Instruction holding values for each of its Variables. +struct InstructionInstance { + InstructionInstance(const Instruction &Instr); + + llvm::MCOperand &getValueFor(const Variable &Var); + llvm::MCOperand &getValueFor(const Operand &Op); + + // Assigns a Random Value to all Variables that are still Invalid and returns + // the instance as an llvm::MCInst. + llvm::MCInst randomizeUnsetVariablesAndBuild(); + + const Instruction &Instr; + llvm::SmallVector VariableValues; +}; + // Represents the assignment of a Register to an Operand. struct RegisterOperandAssignment { RegisterOperandAssignment(const Operand *Operand, llvm::MCPhysReg Reg) @@ -126,17 +144,10 @@ // 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); +// Picks a random configuration, then selects a random def and a random use from +// it and finally set the selected values in the provided InstructionInstances. +void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations, + InstructionInstance &DefII, InstructionInstance &UseII); // Writes MCInst to OS. // This is not assembly but the internal LLVM's name for instructions and Index: tools/llvm-exegesis/lib/MCInstrDescView.cpp =================================================================== --- tools/llvm-exegesis/lib/MCInstrDescView.cpp +++ tools/llvm-exegesis/lib/MCInstrDescView.cpp @@ -17,14 +17,8 @@ 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) + const RegisterAliasingTrackerCache &RATC) : Description(MCInstrDesc) { unsigned OpIndex = 0; for (; OpIndex < MCInstrDesc.getNumOperands(); ++OpIndex) { @@ -36,6 +30,8 @@ // TODO(gchatelet): Handle isLookupPtrRegClass. if (OpInfo.RegClass >= 0) Operand.Tracker = &RATC.getRegisterClass(OpInfo.RegClass); + Operand.TiedToIndex = + MCInstrDesc.getOperandConstraint(OpIndex, llvm::MCOI::TIED_TO); Operand.Info = &OpInfo; Operands.push_back(Operand); } @@ -59,24 +55,23 @@ 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); + // Assigning Variables to non tied explicit operands. + Variables.reserve(Operands.size()); // Variables.size() <= Operands.size() + for (auto &Op : Operands) + if (Op.IsExplicit && Op.TiedToIndex < 0) { + const size_t VariableIndex = Variables.size(); + Op.VariableIndex = VariableIndex; + Variables.emplace_back(); + Variables.back().Index = VariableIndex; } - } + // Assigning Variables to tied operands. + for (auto &Op : Operands) + if (Op.TiedToIndex >= 0) + Op.VariableIndex = Operands[Op.TiedToIndex].VariableIndex; + // Assigning Operands to Variables. + for (auto &Op : Operands) + if (Op.VariableIndex >= 0) + Variables[Op.VariableIndex].TiedOperands.push_back(&Op); // Processing Aliasing. DefRegisters = RATC.emptyRegisters(); UseRegisters = RATC.emptyRegisters(); @@ -88,6 +83,35 @@ } } +InstructionInstance::InstructionInstance(const Instruction &Instr) + : Instr(Instr), VariableValues(Instr.Variables.size()) {} + +llvm::MCOperand &InstructionInstance::getValueFor(const Variable &Var) { + return VariableValues[Var.Index]; +} + +llvm::MCOperand &InstructionInstance::getValueFor(const Operand &Op) { + assert(Op.VariableIndex >= 0); + return getValueFor(Instr.Variables[Op.VariableIndex]); +} + +// forward declaration. +static void randomize(const Variable &Var, llvm::MCOperand &AssignedValue); + +llvm::MCInst InstructionInstance::randomizeUnsetVariablesAndBuild() { + for (const Variable &Var : Instr.Variables) { + llvm::MCOperand &AssignedValue = getValueFor(Var); + if (!AssignedValue.isValid()) + randomize(Var, AssignedValue); + } + llvm::MCInst Result; + Result.setOpcode(Instr.Description.Opcode); + for (const auto &Op : Instr.Operands) + if (Op.IsExplicit) + Result.addOperand(getValueFor(Op)); + return Result; +} + bool RegisterOperandAssignment:: operator==(const RegisterOperandAssignment &Other) const { return std::tie(Op, Reg) == std::tie(Other.Op, Other.Reg); @@ -159,7 +183,7 @@ return Container[randomIndex(Container.size())]; } -static void randomize(Variable &Var) { +static void randomize(const Variable &Var, llvm::MCOperand &AssignedValue) { assert(!Var.TiedOperands.empty()); assert(Var.TiedOperands.front() != nullptr); const Operand &Op = *Var.TiedOperands.front(); @@ -168,12 +192,12 @@ switch (OpInfo.OperandType) { case llvm::MCOI::OperandType::OPERAND_IMMEDIATE: // FIXME: explore immediate values too. - Var.AssignedValue = llvm::MCOperand::createImm(1); + 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)); + AssignedValue = llvm::MCOperand::createReg(randomBit(Registers)); break; } default: @@ -181,15 +205,16 @@ } } -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; +static void setRegisterOperandValue(const RegisterOperandAssignment &ROV, + InstructionInstance &II) { + assert(ROV.Op); + assert(ROV.Op->IsExplicit); + auto &AssignedValue = II.getValueFor(*ROV.Op); if (AssignedValue.isValid()) { assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg); return; } - Op->Var->AssignedValue = llvm::MCOperand::createReg(ROV.Reg); + AssignedValue = llvm::MCOperand::createReg(ROV.Reg); } size_t randomBit(const llvm::BitVector &Vector) { @@ -200,41 +225,13 @@ return *Itr; } -void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations) { +void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations, + InstructionInstance &DefII, InstructionInstance &UseII) { 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); + setRegisterOperandValue(randomElement(RandomConf.Defs), DefII); + setRegisterOperandValue(randomElement(RandomConf.Uses), UseII); } void DumpMCOperand(const llvm::MCRegisterInfo &MCRegisterInfo, Index: tools/llvm-exegesis/lib/RegisterAliasing.h =================================================================== --- tools/llvm-exegesis/lib/RegisterAliasing.h +++ tools/llvm-exegesis/lib/RegisterAliasing.h @@ -87,18 +87,18 @@ const llvm::MCRegisterInfo ®Info() const { return RegInfo; } // Retrieves the RegisterAliasingTracker for this particular register. - const RegisterAliasingTracker &getRegister(llvm::MCPhysReg Reg); + const RegisterAliasingTracker &getRegister(llvm::MCPhysReg Reg) const; // Retrieves the RegisterAliasingTracker for this particular register class. - const RegisterAliasingTracker &getRegisterClass(unsigned RegClassIndex); + const RegisterAliasingTracker &getRegisterClass(unsigned RegClassIndex) const; private: const llvm::MCRegisterInfo &RegInfo; const llvm::BitVector ReservedReg; const llvm::BitVector EmptyRegisters; - std::unordered_map> + mutable std::unordered_map> Registers; - std::unordered_map> + mutable std::unordered_map> RegisterClasses; }; Index: tools/llvm-exegesis/lib/RegisterAliasing.cpp =================================================================== --- tools/llvm-exegesis/lib/RegisterAliasing.cpp +++ tools/llvm-exegesis/lib/RegisterAliasing.cpp @@ -64,7 +64,7 @@ EmptyRegisters(RegInfo.getNumRegs()) {} const RegisterAliasingTracker & -RegisterAliasingTrackerCache::getRegister(llvm::MCPhysReg PhysReg) { +RegisterAliasingTrackerCache::getRegister(llvm::MCPhysReg PhysReg) const { auto &Found = Registers[PhysReg]; if (!Found) Found.reset(new RegisterAliasingTracker(RegInfo, PhysReg)); @@ -72,7 +72,7 @@ } const RegisterAliasingTracker & -RegisterAliasingTrackerCache::getRegisterClass(unsigned RegClassIndex) { +RegisterAliasingTrackerCache::getRegisterClass(unsigned RegClassIndex) const { auto &Found = RegisterClasses[RegClassIndex]; const auto &RegClass = RegInfo.getRegClass(RegClassIndex); if (!Found) Index: tools/llvm-exegesis/lib/Uops.h =================================================================== --- tools/llvm-exegesis/lib/Uops.h +++ tools/llvm-exegesis/lib/Uops.h @@ -24,12 +24,16 @@ using BenchmarkRunner::BenchmarkRunner; ~UopsBenchmarkRunner() override; + llvm::Expected + generateConfiguration(unsigned Opcode) const; + private: + llvm::Error isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const; + InstructionBenchmark::ModeE getMode() const override; llvm::Expected> - createConfigurations(RegisterAliasingTrackerCache &RATC, - unsigned Opcode) const override; + createConfigurations(unsigned Opcode) const override; std::vector runMeasurements(const ExecutableFunction &EF, Index: tools/llvm-exegesis/lib/Uops.cpp =================================================================== --- tools/llvm-exegesis/lib/Uops.cpp +++ tools/llvm-exegesis/lib/Uops.cpp @@ -89,28 +89,24 @@ return OpInfo.OperandType == llvm::MCOI::OPERAND_MEMORY; } -static bool isInfeasible(const Instruction &Instruction, std::string &Error) { - const auto &MCInstrDesc = Instruction.Description; - if (MCInstrDesc.isPseudo()) { - Error = "is pseudo"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) { - Error = "has unknown operands"; - return true; - } - if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) { - Error = "has memory operands"; - return true; - } - return false; +llvm::Error +UopsBenchmarkRunner::isInfeasible(const llvm::MCInstrDesc &MCInstrDesc) const { + if (MCInstrDesc.isPseudo()) + return llvm::make_error("Infeasible : is pseudo"); + if (llvm::any_of(MCInstrDesc.operands(), hasUnknownOperand)) + return llvm::make_error( + "Infeasible : has unknown operands"); + if (llvm::any_of(MCInstrDesc.operands(), hasMemoryOperand)) + return llvm::make_error( + "Infeasible : has memory operands"); + return llvm::Error::success(); } // Returns whether this Variable ties Use and Def operands together. -static bool hasTiedOperands(const Variable *Var) { +static bool hasTiedOperands(const Variable &Var) { bool HasUse = false; bool HasDef = false; - for (const Operand *Op : Var->TiedOperands) { + for (const Operand *Op : Var.TiedOperands) { if (Op->IsDef) HasDef = true; else @@ -119,12 +115,12 @@ return HasUse && HasDef; } -static llvm::SmallVector -getTiedVariables(const Instruction &Instruction) { - llvm::SmallVector Result; - for (auto *Var : Instruction.Variables) +static llvm::SmallVector +getTiedVariables(const Instruction &Instr) { + llvm::SmallVector Result; + for (const auto &Var : Instr.Variables) if (hasTiedOperands(Var)) - Result.push_back(Var); + Result.push_back(&Var); return Result; } @@ -140,79 +136,85 @@ return InstructionBenchmark::Uops; } -llvm::Expected> -UopsBenchmarkRunner::createConfigurations(RegisterAliasingTrackerCache &RATC, - unsigned Opcode) const { - const llvm::MCInstrDesc &MCInstrDesc = MCInstrInfo.get(Opcode); - const Instruction Instruction(MCInstrDesc, RATC); - - std::string Error; - if (isInfeasible(Instruction, Error)) - return llvm::make_error( - llvm::Twine("Infeasible : ").concat(Error), - llvm::inconvertibleErrorCode()); - - BenchmarkConfiguration Conf; - const AliasingConfigurations SelfAliasing(Instruction, Instruction); +llvm::Expected +UopsBenchmarkRunner::generateConfiguration(unsigned Opcode) const { + const auto &InstrDesc = MCInstrInfo.get(Opcode); + if (auto E = isInfeasible(InstrDesc)) + return std::move(E); + const Instruction Instr(InstrDesc, RATC); + const AliasingConfigurations SelfAliasing(Instr, Instr); if (SelfAliasing.empty()) { + InstructionInstance II(Instr); + BenchmarkConfiguration Conf; Conf.Info = "instruction is parallel, repeating a random one."; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; - return std::vector{Conf}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; + return Conf; } if (SelfAliasing.hasImplicitAliasing()) { + InstructionInstance II(Instr); + BenchmarkConfiguration Conf; Conf.Info = "instruction is serial, repeating a random one."; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; - return std::vector{Conf}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; + return Conf; } - const auto TiedVariables = getTiedVariables(Instruction); + const auto TiedVariables = getTiedVariables(Instr); if (!TiedVariables.empty()) { if (TiedVariables.size() > 1) return llvm::make_error( "Infeasible : don't know how to handle several tied variables", llvm::inconvertibleErrorCode()); + BenchmarkConfiguration Conf; Conf.Info = "instruction has tied variables using static renaming."; - Variable *Var = TiedVariables.front(); + const 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); - Conf.Snippet.push_back(randomizeUnsetVariablesAndBuild(Instruction)); + InstructionInstance II(Instr); + II.getValueFor(*Var) = llvm::MCOperand::createReg(Reg); + Conf.Snippet.push_back(II.randomizeUnsetVariablesAndBuild()); } - return std::vector{Conf}; + return Conf; } + InstructionInstance II(Instr); // No tied variables, we pick random values for defs. llvm::BitVector Defs(MCRegisterInfo.getNumRegs()); - for (const auto &Op : Instruction.Operands) { + for (const auto &Op : Instr.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); + II.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg); } } // And pick random use values that are not reserved and don't alias with defs. const auto DefAliases = getAliasedBits(MCRegisterInfo, Defs); - for (const auto &Op : Instruction.Operands) { + for (const auto &Op : Instr.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); + II.getValueFor(Op) = llvm::MCOperand::createReg(RandomReg); } } + BenchmarkConfiguration Conf; Conf.Info = "instruction has no tied variables picking Uses different from defs"; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; - return std::vector{Conf}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; + return Conf; +} + +llvm::Expected> +UopsBenchmarkRunner::createConfigurations(unsigned Opcode) const { + if (auto E = generateConfiguration(Opcode)) + return std::vector{E.get()}; + else + return E.takeError(); } std::vector @@ -232,7 +234,7 @@ int64_t CounterValue = 0; llvm::SmallVector CounterNames; llvm::StringRef(PfmCounters).split(CounterNames, ','); - for (const auto& CounterName : CounterNames) { + for (const auto &CounterName : CounterNames) { pfm::PerfEvent UopPerfEvent(CounterName); if (!UopPerfEvent.valid()) llvm::report_fatal_error( 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,9 @@ ) add_llvm_unittest(LLVMExegesisX86Tests - RegisterAliasingTest.cpp AssemblerTest.cpp AnalysisTest.cpp + SnippetGeneratorTest.cpp + RegisterAliasingTest.cpp ) target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis) Index: unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp =================================================================== --- /dev/null +++ unittests/tools/llvm-exegesis/X86/SnippetGeneratorTest.cpp @@ -0,0 +1,199 @@ +//===-- SnippetGeneratorTest.cpp --------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "../Common/AssemblerUtils.h" +#include "Latency.h" +#include "LlvmState.h" +#include "MCInstrDescView.h" +#include "RegisterAliasing.h" +#include "Uops.h" +#include "X86InstrInfo.h" + +#include + +namespace exegesis { +namespace { + +class X86SnippetGeneratorTest : public ::testing::Test { +protected: + X86SnippetGeneratorTest() + : MCInstrInfo(State.getInstrInfo()), MCRegisterInfo(State.getRegInfo()) {} + + static void SetUpTestCase() { + LLVMInitializeX86TargetInfo(); + LLVMInitializeX86TargetMC(); + LLVMInitializeX86Target(); + LLVMInitializeX86AsmPrinter(); + } + + const LLVMState State; + const llvm::MCInstrInfo &MCInstrInfo; + const llvm::MCRegisterInfo &MCRegisterInfo; +}; + +class LatencySnippetGeneratorTest : public X86SnippetGeneratorTest { +protected: + LatencySnippetGeneratorTest() : Runner(State) {} + + BenchmarkConfiguration checkAndGetConfiguration(unsigned Opcode) { + randomGenerator().seed(0); // Initialize seed. + auto ConfOrError = Runner.generateConfiguration(Opcode); + EXPECT_FALSE(ConfOrError.takeError()); // Valid configuration. + return ConfOrError.get(); + } + + LatencyBenchmarkRunner Runner; +}; + +TEST_F(LatencySnippetGeneratorTest, ImplicitSelfDependency) { + // ADC16i16 self alias because of implicit use and def. + + // explicit use 0 : imm + // implicit def : AX + // implicit def : EFLAGS + // implicit use : AX + // implicit use : EFLAGS + const unsigned Opcode = llvm::X86::ADC16i16; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("implicit")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(1)); + const llvm::MCInst Instr = Conf.Snippet[0]; + EXPECT_THAT(Instr.getOpcode(), Opcode); + EXPECT_THAT(Instr.getNumOperands(), 1); + EXPECT_TRUE(Instr.getOperand(0).isImm()); // Use + EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[0], llvm::X86::AX); + EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[1], llvm::X86::EFLAGS); + EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitUses()[0], llvm::X86::AX); + EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitUses()[1], llvm::X86::EFLAGS); +} + +TEST_F(LatencySnippetGeneratorTest, ExplicitSelfDependency) { + // ADD16ri self alias because Op0 and Op1 are tied together. + + // explicit def 0 : reg RegClass=GR16 + // explicit use 1 : reg RegClass=GR16 | TIED_TO:0 + // explicit use 2 : imm + // implicit def : EFLAGS + const unsigned Opcode = llvm::X86::ADD16ri; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("explicit")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(1)); + const llvm::MCInst Instr = Conf.Snippet[0]; + EXPECT_THAT(Instr.getOpcode(), Opcode); + EXPECT_THAT(Instr.getNumOperands(), 3); + EXPECT_TRUE(Instr.getOperand(0).isReg()); + EXPECT_TRUE(Instr.getOperand(1).isReg()); + EXPECT_THAT(Instr.getOperand(0).getReg(), Instr.getOperand(1).getReg()) + << "Op0 and Op1 should have the same value"; + EXPECT_TRUE(Instr.getOperand(2).isImm()); + EXPECT_THAT(MCInstrInfo.get(Opcode).getImplicitDefs()[0], llvm::X86::EFLAGS); +} + +TEST_F(LatencySnippetGeneratorTest, DependencyThroughOtherOpcode) { + // CMP64rr + // explicit use 0 : reg RegClass=GR64 + // explicit use 1 : reg RegClass=GR64 + // implicit def : EFLAGS + + const unsigned Opcode = llvm::X86::CMP64rr; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("cycle through CMOVLE16rr")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(2)); + // TODO: check that the two instructions alias each other. +} + +class UopsSnippetGeneratorTest : public X86SnippetGeneratorTest { +protected: + UopsSnippetGeneratorTest() : Runner(State) {} + + BenchmarkConfiguration checkAndGetConfiguration(unsigned Opcode) { + randomGenerator().seed(0); // Initialize seed. + auto ConfOrError = Runner.generateConfiguration(Opcode); + EXPECT_FALSE(ConfOrError.takeError()); // Valid configuration. + return ConfOrError.get(); + } + + UopsBenchmarkRunner Runner; +}; + +TEST_F(UopsSnippetGeneratorTest, ParallelInstruction) { + // BNDCL32rr is parallelno matter what. + + // explicit use 0 : reg RegClass=BNDR + // explicit use 1 : reg RegClass=GR32 + + const unsigned Opcode = llvm::X86::BNDCL32rr; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("parallel")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(1)); + const llvm::MCInst Instr = Conf.Snippet[0]; + EXPECT_THAT(Instr.getOpcode(), Opcode); +} + +TEST_F(UopsSnippetGeneratorTest, SerialInstruction) { + // CDQ is serial no matter what. + + // implicit def : EAX + // implicit def : EDX + // implicit use : EAX + const unsigned Opcode = llvm::X86::CDQ; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("serial")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(1)); + const llvm::MCInst Instr = Conf.Snippet[0]; + EXPECT_THAT(Instr.getOpcode(), Opcode); +} + +TEST_F(UopsSnippetGeneratorTest, StaticRenaming) { + // CMOVA32rr has tied variables, we enumarate the possible values to execute + // as many in parallel as possible. + + // explicit def 0 : reg RegClass=GR32 + // explicit use 1 : reg RegClass=GR32 | TIED_TO:0 + // explicit use 2 : reg RegClass=GR32 + // implicit use : EFLAGS + const unsigned Opcode = llvm::X86::CMOVA32rr; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("static renaming")); + constexpr const unsigned kInstructionCount = 15; + ASSERT_THAT(Conf.Snippet, testing::SizeIs(kInstructionCount)); + std::unordered_set AllDefRegisters; + for (const auto &Inst : Conf.Snippet) + AllDefRegisters.insert(Inst.getOperand(0).getReg()); + EXPECT_THAT(AllDefRegisters, testing::SizeIs(kInstructionCount)) + << "Each instruction writes to a different register"; +} + +TEST_F(UopsSnippetGeneratorTest, NoTiedVariables) { + // CMOV_GR32 has no tied variables, we make sure def and use are different + // from each other. + + // explicit def 0 : reg RegClass=GR32 + // explicit use 1 : reg RegClass=GR32 + // explicit use 2 : reg RegClass=GR32 + // explicit use 3 : imm + // implicit use : EFLAGS + const unsigned Opcode = llvm::X86::CMOV_GR32; + auto Conf = checkAndGetConfiguration(Opcode); + EXPECT_THAT(Conf.Info, testing::HasSubstr("no tied variables")); + ASSERT_THAT(Conf.Snippet, testing::SizeIs(1)); + const llvm::MCInst Instr = Conf.Snippet[0]; + EXPECT_THAT(Instr.getOpcode(), Opcode); + EXPECT_THAT(Instr.getNumOperands(), 4); + EXPECT_THAT(Instr.getOperand(0).getReg(), + testing::Not(Instr.getOperand(1).getReg())) + << "Def is different from first Use"; + EXPECT_THAT(Instr.getOperand(0).getReg(), + testing::Not(Instr.getOperand(2).getReg())) + << "Def is different from second Use"; + EXPECT_THAT(Instr.getOperand(3).getImm(), 1); +} + +} // namespace +} // namespace exegesis