1//===-- SerialSnippetGenerator.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 "SerialSnippetGenerator.h"
10
11#include "CodeTemplate.h"
12#include "MCInstrDescView.h"
13#include "Target.h"
14#include <numeric>
15#include <vector>
16
17namespace llvm {
18namespace exegesis {
19
20struct ExecutionClass {
21 ExecutionMode Mask;
22 const char *Description;
23} static const kExecutionClasses[] = {
24 {.Mask: ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS |
25 ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS,
26 .Description: "Repeating a single implicitly serial instruction"},
27 {.Mask: ExecutionMode::SERIAL_VIA_EXPLICIT_REGS,
28 .Description: "Repeating a single explicitly serial instruction"},
29 {.Mask: ExecutionMode::SERIAL_VIA_MEMORY_INSTR |
30 ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR,
31 .Description: "Repeating two instructions"},
32};
33
34static constexpr size_t kMaxAliasingInstructions = 10;
35
36static std::vector<const Instruction *>
37computeAliasingInstructions(const LLVMState &State, const Instruction *Instr,
38 size_t MaxAliasingInstructions,
39 const BitVector &ForbiddenRegisters) {
40 const auto &ET = State.getExegesisTarget();
41 const auto AvailableFeatures = State.getSubtargetInfo().getFeatureBits();
42 // Randomly iterate the set of instructions.
43 std::vector<unsigned> Opcodes;
44 Opcodes.resize(new_size: State.getInstrInfo().getNumOpcodes());
45 std::iota(first: Opcodes.begin(), last: Opcodes.end(), value: 0U);
46 llvm::shuffle(first: Opcodes.begin(), last: Opcodes.end(), g&: randomGenerator());
47
48 std::vector<const Instruction *> AliasingInstructions;
49 for (const unsigned OtherOpcode : Opcodes) {
50 if (!ET.isOpcodeAvailable(Opcode: OtherOpcode, Features: AvailableFeatures))
51 continue;
52 if (OtherOpcode == Instr->Description.getOpcode())
53 continue;
54 const Instruction &OtherInstr = State.getIC().getInstr(Opcode: OtherOpcode);
55 if (ET.getIgnoredOpcodeReasonOrNull(State, Opcode: OtherInstr.getOpcode()))
56 continue;
57 if (OtherInstr.hasMemoryOperands())
58 continue;
59 // Filtering out loads/stores might belong in hasMemoryOperands(), but that
60 // complicates things as there are instructions with may load/store that
61 // don't have operands (e.g. X86's CLUI instruction). So, it's easier to
62 // filter them out here.
63 if (OtherInstr.Description.mayLoad() || OtherInstr.Description.mayStore())
64 continue;
65 if (!ET.allowAsBackToBack(Instr: OtherInstr))
66 continue;
67 if (Instr->hasAliasingRegistersThrough(OtherInstr, ForbiddenRegisters))
68 AliasingInstructions.push_back(x: &OtherInstr);
69 if (AliasingInstructions.size() >= MaxAliasingInstructions)
70 break;
71 }
72 return AliasingInstructions;
73}
74
75static ExecutionMode getExecutionModes(const Instruction &Instr,
76 const BitVector &ForbiddenRegisters) {
77 ExecutionMode EM = ExecutionMode::UNKNOWN;
78 if (Instr.hasAliasingImplicitRegisters())
79 EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS;
80 if (Instr.hasTiedRegisters())
81 EM |= ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS;
82 if (Instr.hasMemoryOperands())
83 EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR;
84 if (Instr.hasAliasingNotMemoryRegisters(ForbiddenRegisters))
85 EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
86 if (Instr.hasOneUseOrOneDef())
87 EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
88 return EM;
89}
90
91static void appendCodeTemplates(const LLVMState &State,
92 InstructionTemplate Variant,
93 const BitVector &ForbiddenRegisters,
94 ExecutionMode ExecutionModeBit,
95 StringRef ExecutionClassDescription,
96 std::vector<CodeTemplate> &CodeTemplates) {
97 assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
98 switch (ExecutionModeBit) {
99 case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
100 // Nothing to do, the instruction is always serial.
101 [[fallthrough]];
102 case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
103 // Picking whatever value for the tied variable will make the instruction
104 // serial.
105 CodeTemplate CT;
106 CT.Execution = ExecutionModeBit;
107 CT.Info = std::string(ExecutionClassDescription);
108 CT.Instructions.push_back(x: std::move(Variant));
109 CodeTemplates.push_back(x: std::move(CT));
110 return;
111 }
112 case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
113 // Select back-to-back memory instruction.
114
115 auto &I = Variant.getInstr();
116 if (I.Description.mayLoad()) {
117 // If instruction is load, we can self-alias it in case when instruction
118 // overrides whole address register. For that we use provided scratch
119 // memory.
120
121 // TODO: now it is not checked if load writes the whole register.
122
123 auto DefOpIt = find_if(Range: I.Operands, P: [](Operand const &Op) {
124 return Op.isDef() && Op.isReg();
125 });
126
127 if (DefOpIt == I.Operands.end())
128 return;
129
130 const Operand &DefOp = *DefOpIt;
131 const ExegesisTarget &ET = State.getExegesisTarget();
132 unsigned ScratchMemoryRegister = ET.getScratchMemoryRegister(
133 State.getTargetMachine().getTargetTriple());
134 const llvm::MCRegisterClass &RegClass =
135 State.getTargetMachine().getMCRegisterInfo().getRegClass(
136 i: DefOp.getExplicitOperandInfo().RegClass);
137
138 // Register classes of def operand and memory operand must be the same
139 // to perform aliasing.
140 if (!RegClass.contains(Reg: ScratchMemoryRegister))
141 return;
142
143 ET.fillMemoryOperands(IT&: Variant, Reg: ScratchMemoryRegister, Offset: 0);
144
145 // Only force the def register to ScratchMemoryRegister if the target
146 // hasn't assigned a value yet.
147 MCOperand &DefVal = Variant.getValueFor(Op: DefOp);
148 if (!DefVal.isValid())
149 DefVal = MCOperand::createReg(Reg: ScratchMemoryRegister);
150
151 CodeTemplate CT;
152 CT.Execution = ExecutionModeBit;
153 CT.ScratchSpacePointerInReg = ScratchMemoryRegister;
154
155 CT.Info = std::string(ExecutionClassDescription);
156 CT.Instructions.push_back(x: std::move(Variant));
157 CodeTemplates.push_back(x: std::move(CT));
158 }
159
160 // TODO: implement more cases
161 return;
162 }
163 case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
164 // Making the execution of this instruction serial by selecting one def
165 // register to alias with one use register.
166 const AliasingConfigurations SelfAliasing(
167 Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
168 assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
169 "Instr must alias itself explicitly");
170 // This is a self aliasing instruction so defs and uses are from the same
171 // instance, hence twice Variant in the following call.
172 setRandomAliasing(AliasingConfigurations: SelfAliasing, DefIB&: Variant, UseIB&: Variant);
173 CodeTemplate CT;
174 CT.Execution = ExecutionModeBit;
175 CT.Info = std::string(ExecutionClassDescription);
176 CT.Instructions.push_back(x: std::move(Variant));
177 CodeTemplates.push_back(x: std::move(CT));
178 return;
179 }
180 case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
181 const Instruction &Instr = Variant.getInstr();
182 // Select back-to-back non-memory instruction.
183 for (const auto *OtherInstr : computeAliasingInstructions(
184 State, Instr: &Instr, MaxAliasingInstructions: kMaxAliasingInstructions, ForbiddenRegisters)) {
185 const AliasingConfigurations Forward(Instr, *OtherInstr,
186 ForbiddenRegisters);
187 const AliasingConfigurations Back(*OtherInstr, Instr, ForbiddenRegisters);
188 InstructionTemplate ThisIT(Variant);
189 InstructionTemplate OtherIT(OtherInstr);
190 if (!Forward.hasImplicitAliasing())
191 setRandomAliasing(AliasingConfigurations: Forward, DefIB&: ThisIT, UseIB&: OtherIT);
192 else if (!Back.hasImplicitAliasing())
193 setRandomAliasing(AliasingConfigurations: Back, DefIB&: OtherIT, UseIB&: ThisIT);
194 CodeTemplate CT;
195 CT.Execution = ExecutionModeBit;
196 CT.Info = std::string(ExecutionClassDescription);
197 CT.Instructions.push_back(x: std::move(ThisIT));
198 CT.Instructions.push_back(x: std::move(OtherIT));
199 CodeTemplates.push_back(x: std::move(CT));
200 }
201 return;
202 }
203 default:
204 llvm_unreachable("Unhandled enum value");
205 }
206}
207
208SerialSnippetGenerator::~SerialSnippetGenerator() = default;
209
210Expected<std::vector<CodeTemplate>>
211SerialSnippetGenerator::generateCodeTemplates(
212 InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
213 std::vector<CodeTemplate> Results;
214 const ExecutionMode EM =
215 getExecutionModes(Instr: Variant.getInstr(), ForbiddenRegisters);
216 for (const auto EC : kExecutionClasses) {
217 for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
218 appendCodeTemplates(State, Variant, ForbiddenRegisters, ExecutionModeBit,
219 ExecutionClassDescription: EC.Description, CodeTemplates&: Results);
220 if (!Results.empty())
221 break;
222 }
223 if (Results.empty())
224 return make_error<Failure>(
225 Args: "No strategy found to make the execution serial");
226 return std::move(Results);
227}
228
229} // namespace exegesis
230} // namespace llvm
231