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