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