332 lines · cpp
1//===-- SnippetGenerator.cpp ------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include <string>10 11#include "Assembler.h"12#include "Error.h"13#include "MCInstrDescView.h"14#include "SnippetGenerator.h"15#include "Target.h"16#include "llvm/ADT/StringExtras.h"17#include "llvm/ADT/StringRef.h"18#include "llvm/ADT/Twine.h"19#include "llvm/Support/Error.h"20#include "llvm/Support/FileSystem.h"21#include "llvm/Support/FormatVariadic.h"22#include "llvm/Support/Program.h"23 24#define DEBUG_TYPE "snippet-generator"25 26namespace llvm {27namespace exegesis {28 29static cl::opt<unsigned>30 RandomGeneratorSeed("random-generator-seed",31 cl::desc("The seed value to use for the random number "32 "generator when generating snippets."),33 cl::init(0));34 35std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {36 std::vector<CodeTemplate> Result;37 Result.push_back(std::move(CT));38 return Result;39}40 41SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)42 : StringError(S, inconvertibleErrorCode()) {}43 44SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)45 : State(State), Opts(Opts) {}46 47SnippetGenerator::~SnippetGenerator() = default;48 49Error SnippetGenerator::generateConfigurations(50 const InstructionTemplate &Variant, std::vector<BenchmarkCode> &Benchmarks,51 const BitVector &ExtraForbiddenRegs) const {52 BitVector ForbiddenRegs = State.getRATC().reservedRegisters();53 ForbiddenRegs |= ExtraForbiddenRegs;54 // If the instruction has memory registers, prevent the generator from55 // using the scratch register and its aliasing registers.56 if (Variant.getInstr().hasMemoryOperands()) {57 const auto &ET = State.getExegesisTarget();58 MCRegister ScratchSpacePointerInReg =59 ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());60 if (!ScratchSpacePointerInReg.isValid())61 return make_error<Failure>(62 "Infeasible : target does not support memory instructions");63 const auto &ScratchRegAliases =64 State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();65 // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.66 // FIXME: We could make a copy of the scratch register.67 for (const auto &Op : Variant.getInstr().Operands) {68 if (Op.isDef() && Op.isImplicitReg() &&69 ScratchRegAliases.test(Op.getImplicitReg().id()))70 return make_error<Failure>(71 "Infeasible : memory instruction uses scratch memory register");72 }73 ForbiddenRegs |= ScratchRegAliases;74 }75 76 if (auto E = generateCodeTemplates(Variant, ForbiddenRegs)) {77 MutableArrayRef<CodeTemplate> Templates = E.get();78 79 // Avoid reallocations in the loop.80 Benchmarks.reserve(Benchmarks.size() + Templates.size());81 for (CodeTemplate &CT : Templates) {82 // TODO: Generate as many BenchmarkCode as needed.83 {84 CT.ScratchSpacePointerInReg =85 State.getExegesisTarget().getScratchMemoryRegister(86 State.getTargetMachine().getTargetTriple());87 BenchmarkCode BC;88 BC.Info = CT.Info;89 BC.Key.Instructions.reserve(CT.Instructions.size());90 for (InstructionTemplate &IT : CT.Instructions) {91 if (auto Error = randomizeUnsetVariables(State, ForbiddenRegs, IT))92 return Error;93 MCInst Inst = IT.build();94 if (auto Error = validateGeneratedInstruction(State, Inst))95 return Error;96 BC.Key.Instructions.push_back(Inst);97 }98 if (CT.ScratchSpacePointerInReg)99 BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);100 BC.Key.RegisterInitialValues =101 computeRegisterInitialValues(CT.Instructions);102 BC.Key.Config = CT.Config;103 Benchmarks.emplace_back(std::move(BC));104 if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {105 // We reached the number of allowed configs and return early.106 return Error::success();107 }108 }109 }110 return Error::success();111 } else112 return E.takeError();113}114 115std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(116 const std::vector<InstructionTemplate> &Instructions) const {117 // Collect all register uses and create an assignment for each of them.118 // Ignore memory operands which are handled separately.119 // Loop invariant: DefinedRegs[i] is true iif it has been set at least once120 // before the current instruction.121 BitVector DefinedRegs = State.getRATC().emptyRegisters();122 // If target always expects a scratch memory register as live input,123 // mark it as defined.124 const ExegesisTarget &Target = State.getExegesisTarget();125 MCRegister ScratchMemoryReg = Target.getScratchMemoryRegister(126 State.getTargetMachine().getTargetTriple());127 DefinedRegs.set(ScratchMemoryReg.id());128 std::vector<RegisterValue> RIV;129 for (const InstructionTemplate &IT : Instructions) {130 // Returns the register that this Operand sets or uses, or 0 if this is not131 // a register.132 const auto GetOpReg = [&IT](const Operand &Op) -> MCRegister {133 if (Op.isMemory())134 return MCRegister();135 if (Op.isImplicitReg())136 return Op.getImplicitReg();137 if (Op.isExplicit() && IT.getValueFor(Op).isReg())138 return IT.getValueFor(Op).getReg();139 return MCRegister();140 };141 // Collect used registers that have never been def'ed.142 for (const Operand &Op : IT.getInstr().Operands) {143 if (Op.isUse()) {144 const MCRegister Reg = GetOpReg(Op);145 if (Reg && !DefinedRegs.test(Reg.id())) {146 RIV.push_back(RegisterValue::zero(Reg));147 DefinedRegs.set(Reg.id());148 }149 }150 }151 // Mark defs as having been def'ed.152 for (const Operand &Op : IT.getInstr().Operands) {153 if (Op.isDef()) {154 const MCRegister Reg = GetOpReg(Op);155 if (Reg)156 DefinedRegs.set(Reg.id());157 }158 }159 }160 return RIV;161}162 163Expected<std::vector<CodeTemplate>>164generateSelfAliasingCodeTemplates(InstructionTemplate Variant,165 const BitVector &ForbiddenRegisters) {166 const AliasingConfigurations SelfAliasing(167 Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);168 if (SelfAliasing.empty())169 return make_error<SnippetGeneratorFailure>("empty self aliasing");170 std::vector<CodeTemplate> Result;171 Result.emplace_back();172 CodeTemplate &CT = Result.back();173 if (SelfAliasing.hasImplicitAliasing()) {174 CT.Info = "implicit Self cycles, picking random values.";175 } else {176 CT.Info = "explicit self cycles, selecting one aliasing Conf.";177 // This is a self aliasing instruction so defs and uses are from the same178 // instance, hence twice Variant in the following call.179 setRandomAliasing(SelfAliasing, Variant, Variant);180 }181 CT.Instructions.push_back(std::move(Variant));182 return std::move(Result);183}184 185Expected<std::vector<CodeTemplate>>186generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,187 StringRef Msg) {188 std::vector<CodeTemplate> Result;189 Result.emplace_back();190 CodeTemplate &CT = Result.back();191 CT.Info =192 std::string(formatv("{0}, repeating an unconstrained assignment", Msg));193 CT.Instructions.push_back(std::move(Variant));194 return std::move(Result);195}196 197std::mt19937 &randomGenerator() {198 static std::random_device RandomDevice;199 unsigned RandomSeed = RandomGeneratorSeed.getNumOccurrences()200 ? RandomGeneratorSeed201 : RandomDevice();202 LLVM_DEBUG(dbgs() << "Using random seed " << RandomSeed << ".\n");203 static std::mt19937 RandomGenerator(RandomSeed);204 return RandomGenerator;205}206 207size_t randomIndex(size_t Max) {208 std::uniform_int_distribution<> Distribution(0, Max);209 return Distribution(randomGenerator());210}211 212template <typename C> static decltype(auto) randomElement(const C &Container) {213 assert(!Container.empty() &&214 "Can't pick a random element from an empty container)");215 return Container[randomIndex(Container.size() - 1)];216}217 218static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,219 InstructionTemplate &IB) {220 assert(ROV.Op);221 if (ROV.Op->isExplicit()) {222 auto &AssignedValue = IB.getValueFor(*ROV.Op);223 if (AssignedValue.isValid()) {224 // TODO don't re-assign register operands which are already "locked"225 // by Target in corresponding InstructionTemplate226 return;227 }228 AssignedValue = MCOperand::createReg(ROV.Reg);229 } else {230 assert(ROV.Op->isImplicitReg());231 assert(ROV.Reg == ROV.Op->getImplicitReg());232 }233}234 235size_t randomBit(const BitVector &Vector) {236 assert(Vector.any());237 auto Itr = Vector.set_bits_begin();238 for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)239 ++Itr;240 return *Itr;241}242 243std::optional<int> getFirstCommonBit(const BitVector &A, const BitVector &B) {244 BitVector Intersect = A;245 Intersect &= B;246 int idx = Intersect.find_first();247 if (idx != -1)248 return idx;249 return {};250}251 252void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,253 InstructionTemplate &DefIB, InstructionTemplate &UseIB) {254 assert(!AliasingConfigurations.empty());255 assert(!AliasingConfigurations.hasImplicitAliasing());256 const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);257 setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);258 setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);259}260 261static Error randomizeMCOperand(const LLVMState &State,262 const Instruction &Instr, const Variable &Var,263 MCOperand &AssignedValue,264 const BitVector &ForbiddenRegs) {265 const Operand &Op = Instr.getPrimaryOperand(Var);266 if (Op.getExplicitOperandInfo().OperandType >=267 MCOI::OperandType::OPERAND_FIRST_TARGET)268 return State.getExegesisTarget().randomizeTargetMCOperand(269 Instr, Var, AssignedValue, ForbiddenRegs);270 switch (Op.getExplicitOperandInfo().OperandType) {271 case MCOI::OperandType::OPERAND_IMMEDIATE:272 // FIXME: explore immediate values too.273 AssignedValue = MCOperand::createImm(1);274 break;275 case MCOI::OperandType::OPERAND_REGISTER: {276 assert(Op.isReg());277 auto AllowedRegs = Op.getRegisterAliasing().sourceBits();278 assert(AllowedRegs.size() == ForbiddenRegs.size());279 for (auto I : ForbiddenRegs.set_bits())280 AllowedRegs.reset(I);281 if (!AllowedRegs.any())282 return make_error<Failure>(283 Twine("no available registers:\ncandidates:\n")284 .concat(debugString(State.getRegInfo(),285 Op.getRegisterAliasing().sourceBits()))286 .concat("\nforbidden:\n")287 .concat(debugString(State.getRegInfo(), ForbiddenRegs)));288 AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));289 break;290 }291 /// Omit pc-relative operands to imm value based on the instruction292 case MCOI::OperandType::OPERAND_PCREL:293 return State.getExegesisTarget().randomizeTargetMCOperand(294 Instr, Var, AssignedValue, ForbiddenRegs);295 default:296 break;297 }298 return Error::success();299}300 301Error randomizeUnsetVariables(const LLVMState &State,302 const BitVector &ForbiddenRegs,303 InstructionTemplate &IT) {304 for (const Variable &Var : IT.getInstr().Variables) {305 MCOperand &AssignedValue = IT.getValueFor(Var);306 if (!AssignedValue.isValid())307 if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,308 AssignedValue, ForbiddenRegs))309 return Err;310 }311 return Error::success();312}313 314Error validateGeneratedInstruction(const LLVMState &State, const MCInst &Inst) {315 for (const auto &Operand : Inst) {316 if (!Operand.isValid()) {317 // Mention the particular opcode - it is not necessarily the "main"318 // opcode being benchmarked by this snippet. For example, serial snippet319 // generator uses one more opcode when in SERIAL_VIA_NON_MEMORY_INSTR320 // execution mode.321 const auto OpcodeName = State.getInstrInfo().getName(Inst.getOpcode());322 return make_error<Failure>("Not all operands were initialized by the "323 "snippet generator for " +324 OpcodeName + " opcode.");325 }326 }327 return Error::success();328}329 330} // namespace exegesis331} // namespace llvm332