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 <array>
10 #include <string>
11
12 #include "Assembler.h"
13 #include "Error.h"
14 #include "MCInstrDescView.h"
15 #include "SnippetGenerator.h"
16 #include "Target.h"
17 #include "llvm/ADT/StringExtras.h"
18 #include "llvm/ADT/StringRef.h"
19 #include "llvm/ADT/Twine.h"
20 #include "llvm/Support/FileSystem.h"
21 #include "llvm/Support/FormatVariadic.h"
22 #include "llvm/Support/Program.h"
23
24 namespace llvm {
25 namespace exegesis {
26
getSingleton(CodeTemplate && CT)27 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
28 std::vector<CodeTemplate> Result;
29 Result.push_back(std::move(CT));
30 return Result;
31 }
32
SnippetGeneratorFailure(const Twine & S)33 SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)
34 : StringError(S, inconvertibleErrorCode()) {}
35
SnippetGenerator(const LLVMState & State,const Options & Opts)36 SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)
37 : State(State), Opts(Opts) {}
38
39 SnippetGenerator::~SnippetGenerator() = default;
40
generateConfigurations(const InstructionTemplate & Variant,std::vector<BenchmarkCode> & Benchmarks,const BitVector & ExtraForbiddenRegs) const41 Error 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 "Infeasible : target does not support memory instructions");
55 const auto &ScratchRegAliases =
56 State.getRATC().getRegister(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(Op.getImplicitReg()))
62 return make_error<Failure>(
63 "Infeasible : memory instruction uses scratch memory register");
64 }
65 ForbiddenRegs |= ScratchRegAliases;
66 }
67
68 if (auto E = generateCodeTemplates(Variant, ForbiddenRegs)) {
69 MutableArrayRef<CodeTemplate> Templates = E.get();
70
71 // Avoid reallocations in the loop.
72 Benchmarks.reserve(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 for (InstructionTemplate &IT : CT.Instructions) {
79 if (auto error = randomizeUnsetVariables(State, ForbiddenRegs, IT))
80 return error;
81 BC.Key.Instructions.push_back(IT.build());
82 }
83 if (CT.ScratchSpacePointerInReg)
84 BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
85 BC.Key.RegisterInitialValues =
86 computeRegisterInitialValues(CT.Instructions);
87 BC.Key.Config = CT.Config;
88 Benchmarks.emplace_back(std::move(BC));
89 if (Benchmarks.size() >= Opts.MaxConfigsPerOpcode) {
90 // We reached the number of allowed configs and return early.
91 return Error::success();
92 }
93 }
94 }
95 return Error::success();
96 } else
97 return E.takeError();
98 }
99
computeRegisterInitialValues(const std::vector<InstructionTemplate> & Instructions) const100 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
101 const std::vector<InstructionTemplate> &Instructions) const {
102 // Collect all register uses and create an assignment for each of them.
103 // Ignore memory operands which are handled separately.
104 // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
105 // before the current instruction.
106 BitVector DefinedRegs = State.getRATC().emptyRegisters();
107 std::vector<RegisterValue> RIV;
108 for (const InstructionTemplate &IT : Instructions) {
109 // Returns the register that this Operand sets or uses, or 0 if this is not
110 // a register.
111 const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
112 if (Op.isMemory())
113 return 0;
114 if (Op.isImplicitReg())
115 return Op.getImplicitReg();
116 if (Op.isExplicit() && IT.getValueFor(Op).isReg())
117 return IT.getValueFor(Op).getReg();
118 return 0;
119 };
120 // Collect used registers that have never been def'ed.
121 for (const Operand &Op : IT.getInstr().Operands) {
122 if (Op.isUse()) {
123 const unsigned Reg = GetOpReg(Op);
124 if (Reg > 0 && !DefinedRegs.test(Reg)) {
125 RIV.push_back(RegisterValue::zero(Reg));
126 DefinedRegs.set(Reg);
127 }
128 }
129 }
130 // Mark defs as having been def'ed.
131 for (const Operand &Op : IT.getInstr().Operands) {
132 if (Op.isDef()) {
133 const unsigned Reg = GetOpReg(Op);
134 if (Reg > 0)
135 DefinedRegs.set(Reg);
136 }
137 }
138 }
139 return RIV;
140 }
141
142 Expected<std::vector<CodeTemplate>>
generateSelfAliasingCodeTemplates(InstructionTemplate Variant)143 generateSelfAliasingCodeTemplates(InstructionTemplate Variant) {
144 const AliasingConfigurations SelfAliasing(Variant.getInstr(),
145 Variant.getInstr());
146 if (SelfAliasing.empty())
147 return make_error<SnippetGeneratorFailure>("empty self aliasing");
148 std::vector<CodeTemplate> Result;
149 Result.emplace_back();
150 CodeTemplate &CT = Result.back();
151 if (SelfAliasing.hasImplicitAliasing()) {
152 CT.Info = "implicit Self cycles, picking random values.";
153 } else {
154 CT.Info = "explicit self cycles, selecting one aliasing Conf.";
155 // This is a self aliasing instruction so defs and uses are from the same
156 // instance, hence twice Variant in the following call.
157 setRandomAliasing(SelfAliasing, Variant, Variant);
158 }
159 CT.Instructions.push_back(std::move(Variant));
160 return std::move(Result);
161 }
162
163 Expected<std::vector<CodeTemplate>>
generateUnconstrainedCodeTemplates(const InstructionTemplate & Variant,StringRef Msg)164 generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant,
165 StringRef Msg) {
166 std::vector<CodeTemplate> Result;
167 Result.emplace_back();
168 CodeTemplate &CT = Result.back();
169 CT.Info =
170 std::string(formatv("{0}, repeating an unconstrained assignment", Msg));
171 CT.Instructions.push_back(std::move(Variant));
172 return std::move(Result);
173 }
174
randomGenerator()175 std::mt19937 &randomGenerator() {
176 static std::random_device RandomDevice;
177 static std::mt19937 RandomGenerator(RandomDevice());
178 return RandomGenerator;
179 }
180
randomIndex(size_t Max)181 size_t randomIndex(size_t Max) {
182 std::uniform_int_distribution<> Distribution(0, Max);
183 return Distribution(randomGenerator());
184 }
185
randomElement(const C & Container)186 template <typename C> static decltype(auto) randomElement(const C &Container) {
187 assert(!Container.empty() &&
188 "Can't pick a random element from an empty container)");
189 return Container[randomIndex(Container.size() - 1)];
190 }
191
setRegisterOperandValue(const RegisterOperandAssignment & ROV,InstructionTemplate & IB)192 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
193 InstructionTemplate &IB) {
194 assert(ROV.Op);
195 if (ROV.Op->isExplicit()) {
196 auto &AssignedValue = IB.getValueFor(*ROV.Op);
197 if (AssignedValue.isValid()) {
198 assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
199 return;
200 }
201 AssignedValue = MCOperand::createReg(ROV.Reg);
202 } else {
203 assert(ROV.Op->isImplicitReg());
204 assert(ROV.Reg == ROV.Op->getImplicitReg());
205 }
206 }
207
randomBit(const BitVector & Vector)208 size_t randomBit(const BitVector &Vector) {
209 assert(Vector.any());
210 auto Itr = Vector.set_bits_begin();
211 for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
212 ++Itr;
213 return *Itr;
214 }
215
setRandomAliasing(const AliasingConfigurations & AliasingConfigurations,InstructionTemplate & DefIB,InstructionTemplate & UseIB)216 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
217 InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
218 assert(!AliasingConfigurations.empty());
219 assert(!AliasingConfigurations.hasImplicitAliasing());
220 const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
221 setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
222 setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
223 }
224
randomizeMCOperand(const LLVMState & State,const Instruction & Instr,const Variable & Var,MCOperand & AssignedValue,const BitVector & ForbiddenRegs)225 static Error randomizeMCOperand(const LLVMState &State,
226 const Instruction &Instr, const Variable &Var,
227 MCOperand &AssignedValue,
228 const BitVector &ForbiddenRegs) {
229 const Operand &Op = Instr.getPrimaryOperand(Var);
230 if (Op.getExplicitOperandInfo().OperandType >=
231 MCOI::OperandType::OPERAND_FIRST_TARGET)
232 return State.getExegesisTarget().randomizeTargetMCOperand(
233 Instr, Var, AssignedValue, ForbiddenRegs);
234 switch (Op.getExplicitOperandInfo().OperandType) {
235 case MCOI::OperandType::OPERAND_IMMEDIATE:
236 // FIXME: explore immediate values too.
237 AssignedValue = MCOperand::createImm(1);
238 break;
239 case MCOI::OperandType::OPERAND_REGISTER: {
240 assert(Op.isReg());
241 auto AllowedRegs = Op.getRegisterAliasing().sourceBits();
242 assert(AllowedRegs.size() == ForbiddenRegs.size());
243 for (auto I : ForbiddenRegs.set_bits())
244 AllowedRegs.reset(I);
245 if (!AllowedRegs.any())
246 return make_error<Failure>(
247 Twine("no available registers:\ncandidates:\n")
248 .concat(debugString(State.getRegInfo(),
249 Op.getRegisterAliasing().sourceBits()))
250 .concat("\nforbidden:\n")
251 .concat(debugString(State.getRegInfo(), ForbiddenRegs)));
252 AssignedValue = MCOperand::createReg(randomBit(AllowedRegs));
253 break;
254 }
255 default:
256 break;
257 }
258 return Error::success();
259 }
260
randomizeUnsetVariables(const LLVMState & State,const BitVector & ForbiddenRegs,InstructionTemplate & IT)261 Error randomizeUnsetVariables(const LLVMState &State,
262 const BitVector &ForbiddenRegs,
263 InstructionTemplate &IT) {
264 for (const Variable &Var : IT.getInstr().Variables) {
265 MCOperand &AssignedValue = IT.getValueFor(Var);
266 if (!AssignedValue.isValid())
267 if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var,
268 AssignedValue, ForbiddenRegs))
269 return Err;
270 }
271 return Error::success();
272 }
273
274 } // namespace exegesis
275 } // namespace llvm
276