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