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