xref: /llvm-project/llvm/tools/llvm-exegesis/lib/SnippetGenerator.cpp (revision 4919534ae4d4029982d5a5ad7ea18f4a681cb602) 
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 llvm::Twine &S)
34     : llvm::StringError(S, llvm::inconvertibleErrorCode()) {}
35 
36 SnippetGenerator::SnippetGenerator(const LLVMState &State) : State(State) {}
37 
38 SnippetGenerator::~SnippetGenerator() = default;
39 
40 llvm::Expected<std::vector<BenchmarkCode>>
41 SnippetGenerator::generateConfigurations(
42     const Instruction &Instr, const llvm::BitVector &ExtraForbiddenRegs) const {
43   llvm::BitVector ForbiddenRegs = State.getRATC().reservedRegisters();
44   ForbiddenRegs |= ExtraForbiddenRegs;
45   // If the instruction has memory registers, prevent the generator from
46   // using the scratch register and its aliasing registers.
47   if (Instr.hasMemoryOperands()) {
48     const auto &ET = State.getExegesisTarget();
49     unsigned ScratchSpacePointerInReg =
50         ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple());
51     if (ScratchSpacePointerInReg == 0)
52       return make_error<Failure>(
53           "Infeasible : target does not support memory instructions");
54     const auto &ScratchRegAliases =
55         State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits();
56     // If the instruction implicitly writes to ScratchSpacePointerInReg , abort.
57     // FIXME: We could make a copy of the scratch register.
58     for (const auto &Op : Instr.Operands) {
59       if (Op.isDef() && Op.isImplicitReg() &&
60           ScratchRegAliases.test(Op.getImplicitReg()))
61         return make_error<Failure>(
62             "Infeasible : memory instruction uses scratch memory register");
63     }
64     ForbiddenRegs |= ScratchRegAliases;
65   }
66 
67   if (auto E = generateCodeTemplates(Instr, ForbiddenRegs)) {
68     std::vector<BenchmarkCode> Output;
69     for (CodeTemplate &CT : E.get()) {
70       // TODO: Generate as many BenchmarkCode as needed.
71       {
72         BenchmarkCode BC;
73         BC.Info = CT.Info;
74         for (InstructionTemplate &IT : CT.Instructions) {
75           randomizeUnsetVariables(State.getExegesisTarget(), ForbiddenRegs, IT);
76           BC.Key.Instructions.push_back(IT.build());
77         }
78         if (CT.ScratchSpacePointerInReg)
79           BC.LiveIns.push_back(CT.ScratchSpacePointerInReg);
80         BC.Key.RegisterInitialValues =
81             computeRegisterInitialValues(CT.Instructions);
82         BC.Key.Config = CT.Config;
83         Output.push_back(std::move(BC));
84       }
85     }
86     return Output;
87   } else
88     return E.takeError();
89 }
90 
91 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues(
92     const std::vector<InstructionTemplate> &Instructions) const {
93   // Collect all register uses and create an assignment for each of them.
94   // Ignore memory operands which are handled separately.
95   // Loop invariant: DefinedRegs[i] is true iif it has been set at least once
96   // before the current instruction.
97   llvm::BitVector DefinedRegs = State.getRATC().emptyRegisters();
98   std::vector<RegisterValue> RIV;
99   for (const InstructionTemplate &IT : Instructions) {
100     // Returns the register that this Operand sets or uses, or 0 if this is not
101     // a register.
102     const auto GetOpReg = [&IT](const Operand &Op) -> unsigned {
103       if (Op.isMemory())
104         return 0;
105       if (Op.isImplicitReg())
106         return Op.getImplicitReg();
107       if (Op.isExplicit() && IT.getValueFor(Op).isReg())
108         return IT.getValueFor(Op).getReg();
109       return 0;
110     };
111     // Collect used registers that have never been def'ed.
112     for (const Operand &Op : IT.Instr.Operands) {
113       if (Op.isUse()) {
114         const unsigned Reg = GetOpReg(Op);
115         if (Reg > 0 && !DefinedRegs.test(Reg)) {
116           RIV.push_back(RegisterValue::zero(Reg));
117           DefinedRegs.set(Reg);
118         }
119       }
120     }
121     // Mark defs as having been def'ed.
122     for (const Operand &Op : IT.Instr.Operands) {
123       if (Op.isDef()) {
124         const unsigned Reg = GetOpReg(Op);
125         if (Reg > 0)
126           DefinedRegs.set(Reg);
127       }
128     }
129   }
130   return RIV;
131 }
132 
133 llvm::Expected<std::vector<CodeTemplate>>
134 generateSelfAliasingCodeTemplates(const Instruction &Instr) {
135   const AliasingConfigurations SelfAliasing(Instr, Instr);
136   if (SelfAliasing.empty())
137     return llvm::make_error<SnippetGeneratorFailure>("empty self aliasing");
138   std::vector<CodeTemplate> Result;
139   Result.emplace_back();
140   CodeTemplate &CT = Result.back();
141   InstructionTemplate IT(Instr);
142   if (SelfAliasing.hasImplicitAliasing()) {
143     CT.Info = "implicit Self cycles, picking random values.";
144   } else {
145     CT.Info = "explicit self cycles, selecting one aliasing Conf.";
146     // This is a self aliasing instruction so defs and uses are from the same
147     // instance, hence twice IT in the following call.
148     setRandomAliasing(SelfAliasing, IT, IT);
149   }
150   CT.Instructions.push_back(std::move(IT));
151   return std::move(Result);
152 }
153 
154 llvm::Expected<std::vector<CodeTemplate>>
155 generateUnconstrainedCodeTemplates(const Instruction &Instr,
156                                    llvm::StringRef Msg) {
157   std::vector<CodeTemplate> Result;
158   Result.emplace_back();
159   CodeTemplate &CT = Result.back();
160   CT.Info = llvm::formatv("{0}, repeating an unconstrained assignment", Msg);
161   CT.Instructions.emplace_back(Instr);
162   return std::move(Result);
163 }
164 
165 std::mt19937 &randomGenerator() {
166   static std::random_device RandomDevice;
167   static std::mt19937 RandomGenerator(RandomDevice());
168   return RandomGenerator;
169 }
170 
171 size_t randomIndex(size_t Max) {
172   std::uniform_int_distribution<> Distribution(0, Max);
173   return Distribution(randomGenerator());
174 }
175 
176 template <typename C>
177 static auto randomElement(const C &Container) -> decltype(Container[0]) {
178   assert(!Container.empty() &&
179          "Can't pick a random element from an empty container)");
180   return Container[randomIndex(Container.size() - 1)];
181 }
182 
183 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV,
184                                     InstructionTemplate &IB) {
185   assert(ROV.Op);
186   if (ROV.Op->isExplicit()) {
187     auto &AssignedValue = IB.getValueFor(*ROV.Op);
188     if (AssignedValue.isValid()) {
189       assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg);
190       return;
191     }
192     AssignedValue = llvm::MCOperand::createReg(ROV.Reg);
193   } else {
194     assert(ROV.Op->isImplicitReg());
195     assert(ROV.Reg == ROV.Op->getImplicitReg());
196   }
197 }
198 
199 size_t randomBit(const llvm::BitVector &Vector) {
200   assert(Vector.any());
201   auto Itr = Vector.set_bits_begin();
202   for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I)
203     ++Itr;
204   return *Itr;
205 }
206 
207 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
208                        InstructionTemplate &DefIB, InstructionTemplate &UseIB) {
209   assert(!AliasingConfigurations.empty());
210   assert(!AliasingConfigurations.hasImplicitAliasing());
211   const auto &RandomConf = randomElement(AliasingConfigurations.Configurations);
212   setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB);
213   setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB);
214 }
215 
216 void randomizeUnsetVariables(const ExegesisTarget &Target,
217                              const llvm::BitVector &ForbiddenRegs,
218                              InstructionTemplate &IT) {
219   for (const Variable &Var : IT.Instr.Variables) {
220     llvm::MCOperand &AssignedValue = IT.getValueFor(Var);
221     if (!AssignedValue.isValid())
222       Target.randomizeMCOperand(IT.Instr, Var, AssignedValue, ForbiddenRegs);
223   }
224 }
225 
226 } // namespace exegesis
227 } // namespace llvm
228