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 <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(Val: 0));
34
35std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
36 std::vector<CodeTemplate> Result;
37 Result.push_back(x: 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 from
55 // 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 Args: "Infeasible : target does not support memory instructions");
63 const auto &ScratchRegAliases =
64 State.getRATC().getRegister(Reg: 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(Idx: Op.getImplicitReg().id()))
70 return make_error<Failure>(
71 Args: "Infeasible : memory instruction uses scratch memory register");
72 }
73 ForbiddenRegs |= ScratchRegAliases;
74 }
75
76 if (auto E = generateCodeTemplates(Variant, ForbiddenRegisters: ForbiddenRegs)) {
77 MutableArrayRef<CodeTemplate> Templates = E.get();
78
79 // Avoid reallocations in the loop.
80 Benchmarks.reserve(n: 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(n: 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(x: Inst);
97 }
98 if (CT.ScratchSpacePointerInReg)
99 BC.LiveIns.push_back(x: CT.ScratchSpacePointerInReg);
100 BC.Key.RegisterInitialValues =
101 computeRegisterInitialValues(Snippet: CT.Instructions);
102 BC.Key.Config = CT.Config;
103 Benchmarks.emplace_back(args: 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 } else
112 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 once
120 // 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 not
131 // 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(Idx: Reg.id())) {
146 RIV.push_back(x: 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>(Args: "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 same
178 // instance, hence twice Variant in the following call.
179 setRandomAliasing(AliasingConfigurations: SelfAliasing, DefIB&: Variant, UseIB&: Variant);
180 }
181 CT.Instructions.push_back(x: 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(Fmt: "{0}, repeating an unconstrained assignment", Vals&: Msg));
193 CT.Instructions.push_back(x: 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 ? RandomGeneratorSeed
201 : 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(Op: *ROV.Op);
223 if (AssignedValue.isValid()) {
224 // TODO don't re-assign register operands which are already "locked"
225 // by Target in corresponding InstructionTemplate
226 return;
227 }
228 AssignedValue = MCOperand::createReg(Reg: 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(Max: 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(Container: AliasingConfigurations.Configurations);
257 setRegisterOperandValue(ROV: randomElement(Container: RandomConf.Defs), IB&: DefIB);
258 setRegisterOperandValue(ROV: randomElement(Container: RandomConf.Uses), IB&: 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(Val: 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(Idx: I);
281 if (!AllowedRegs.any())
282 return make_error<Failure>(
283 Args: Twine("no available registers:\ncandidates:\n")
284 .concat(Suffix: debugString(RegInfo: State.getRegInfo(),
285 Regs: Op.getRegisterAliasing().sourceBits()))
286 .concat(Suffix: "\nforbidden:\n")
287 .concat(Suffix: debugString(RegInfo: State.getRegInfo(), Regs: ForbiddenRegs)));
288 AssignedValue = MCOperand::createReg(Reg: randomBit(Vector: AllowedRegs));
289 break;
290 }
291 /// Omit pc-relative operands to imm value based on the instruction
292 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, Instr: 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 snippet
319 // generator uses one more opcode when in SERIAL_VIA_NON_MEMORY_INSTR
320 // execution mode.
321 const auto OpcodeName = State.getInstrInfo().getName(Opcode: Inst.getOpcode());
322 return make_error<Failure>(Args: "Not all operands were initialized by the "
323 "snippet generator for " +
324 OpcodeName + " opcode.");
325 }
326 }
327 return Error::success();
328}
329
330} // namespace exegesis
331} // namespace llvm
332