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 
27 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) {
28   std::vector<CodeTemplate> Result;
29   Result.push_back(std::move(CT));
30   return Result;
31 }
32 
33 SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S)
34     : StringError(S, inconvertibleErrorCode()) {}
35 
36 SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts)
37     : State(State), Opts(Opts) {}
38 
39 SnippetGenerator::~SnippetGenerator() = default;
40 
41 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 
100 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>>
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>>
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 
175 std::mt19937 &randomGenerator() {
176   static std::random_device RandomDevice;
177   static std::mt19937 RandomGenerator(RandomDevice());
178   return RandomGenerator;
179 }
180 
181 size_t randomIndex(size_t Max) {
182   std::uniform_int_distribution<> Distribution(0, Max);
183   return Distribution(randomGenerator());
184 }
185 
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 
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 
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 
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 
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 
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