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