Index: tools/llvm-exegesis/lib/Latency.cpp =================================================================== --- tools/llvm-exegesis/lib/Latency.cpp +++ tools/llvm-exegesis/lib/Latency.cpp @@ -66,13 +66,14 @@ BenchmarkConfiguration Conf; const AliasingConfigurations SelfAliasing(ThisInstruction, ThisInstruction); if (!SelfAliasing.empty()) { + InstructionInstance II(ThisInstruction); if (!SelfAliasing.hasImplicitAliasing()) { Conf.Info = "explicit self cycles, selecting one aliasing Conf."; - setRandomAliasing(SelfAliasing); + setRandomAliasing(SelfAliasing, II, II); } else { Conf.Info = "implicit Self cycles, picking random values."; } - Conf.Snippet = {randomizeUnsetVariablesAndBuild(ThisInstruction)}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; return std::vector{Conf}; } @@ -82,7 +83,7 @@ std::iota(Opcodes.begin(), Opcodes.end(), 0U); std::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator()); for (const unsigned OtherOpcode : Opcodes) { - clearVariableAssignments(ThisInstruction); + InstructionInstance ThisII(ThisInstruction); if (OtherOpcode == Opcode) continue; const Instruction OtherInstruction(MCInstrInfo.get(OtherOpcode), RATC); @@ -92,14 +93,15 @@ const AliasingConfigurations Back(OtherInstruction, ThisInstruction); if (Forward.empty() || Back.empty()) continue; - setRandomAliasing(Forward); - setRandomAliasing(Back); + InstructionInstance OtherII(OtherInstruction); + setRandomAliasing(Forward, ThisII, OtherII); + setRandomAliasing(Back, OtherII, ThisII); 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)); + Conf.Snippet.push_back(ThisII.randomizeUnsetVariablesAndBuild()); + Conf.Snippet.push_back(OtherII.randomizeUnsetVariablesAndBuild()); return std::vector{Conf}; } 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,51 @@ // - 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 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. + 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) @@ -127,16 +146,9 @@ 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); +// 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,12 +17,6 @@ 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) { @@ -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,15 @@ } } -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); + 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,42 +224,28 @@ 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)); + setRegisterOperandValue(randomElement(RandomConf.Defs), DefII); + setRegisterOperandValue(randomElement(RandomConf.Uses), UseII); } -void randomizeUnsetVariable(const Instruction &Instruction) { - for (auto *Var : Instruction.Variables) - if (!Var->AssignedValue.isValid()) - randomize(*Var); -} +// void randomizeUnsetVariable(InstructionInstance &II) { +// for (const Variable &Var : II.Instruction.Variables) { +// llvm::MCOperand &AssignedValue = II.getValueFor(Var); +// if (!AssignedValue.isValid()) +// randomize(Var, AssignedValue); +// } +// } -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); -} +// 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) { Index: tools/llvm-exegesis/lib/Uops.cpp =================================================================== --- tools/llvm-exegesis/lib/Uops.cpp +++ tools/llvm-exegesis/lib/Uops.cpp @@ -107,10 +107,10 @@ } // 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 +119,12 @@ return HasUse && HasDef; } -static llvm::SmallVector +static llvm::SmallVector getTiedVariables(const Instruction &Instruction) { - llvm::SmallVector Result; - for (auto *Var : Instruction.Variables) + llvm::SmallVector Result; + for (const auto &Var : Instruction.Variables) if (hasTiedOperands(Var)) - Result.push_back(Var); + Result.push_back(&Var); return Result; } @@ -155,13 +155,15 @@ BenchmarkConfiguration Conf; const AliasingConfigurations SelfAliasing(Instruction, Instruction); if (SelfAliasing.empty()) { + InstructionInstance II(Instruction); Conf.Info = "instruction is parallel, repeating a random one."; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; return std::vector{Conf}; } if (SelfAliasing.hasImplicitAliasing()) { + InstructionInstance II(Instruction); Conf.Info = "instruction is serial, repeating a random one."; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; return std::vector{Conf}; } const auto TiedVariables = getTiedVariables(Instruction); @@ -171,47 +173,46 @@ "Infeasible : don't know how to handle several tied variables", llvm::inconvertibleErrorCode()); 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(Instruction); + II.getValueFor(*Var) = llvm::MCOperand::createReg(Reg); + Conf.Snippet.push_back(II.randomizeUnsetVariablesAndBuild()); } return std::vector{Conf}; } + InstructionInstance II(Instruction); // 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); + 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) { 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); } } Conf.Info = "instruction has no tied variables picking Uses different from defs"; - Conf.Snippet = {randomizeUnsetVariablesAndBuild(Instruction)}; + Conf.Snippet = {II.randomizeUnsetVariablesAndBuild()}; return std::vector{Conf}; }