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 if (!ET.allowAsBackToBack(Instr: OtherInstr))
61 continue;
62 if (Instr->hasAliasingRegistersThrough(OtherInstr, ForbiddenRegisters))
63 AliasingInstructions.push_back(x: &OtherInstr);
64 if (AliasingInstructions.size() >= MaxAliasingInstructions)
65 break;
66 }
67 return AliasingInstructions;
68}
69
70static ExecutionMode getExecutionModes(const Instruction &Instr,
71 const BitVector &ForbiddenRegisters) {
72 ExecutionMode EM = ExecutionMode::UNKNOWN;
73 if (Instr.hasAliasingImplicitRegisters())
74 EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS;
75 if (Instr.hasTiedRegisters())
76 EM |= ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS;
77 if (Instr.hasMemoryOperands())
78 EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR;
79 if (Instr.hasAliasingNotMemoryRegisters(ForbiddenRegisters))
80 EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
81 if (Instr.hasOneUseOrOneDef())
82 EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
83 return EM;
84}
85
86static void appendCodeTemplates(const LLVMState &State,
87 InstructionTemplate Variant,
88 const BitVector &ForbiddenRegisters,
89 ExecutionMode ExecutionModeBit,
90 StringRef ExecutionClassDescription,
91 std::vector<CodeTemplate> &CodeTemplates) {
92 assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
93 switch (ExecutionModeBit) {
94 case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
95 // Nothing to do, the instruction is always serial.
96 [[fallthrough]];
97 case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
98 // Picking whatever value for the tied variable will make the instruction
99 // serial.
100 CodeTemplate CT;
101 CT.Execution = ExecutionModeBit;
102 CT.Info = std::string(ExecutionClassDescription);
103 CT.Instructions.push_back(x: std::move(Variant));
104 CodeTemplates.push_back(x: std::move(CT));
105 return;
106 }
107 case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
108 // Select back-to-back memory instruction.
109
110 auto &I = Variant.getInstr();
111 if (I.Description.mayLoad()) {
112 // If instruction is load, we can self-alias it in case when instruction
113 // overrides whole address register. For that we use provided scratch
114 // memory.
115
116 // TODO: now it is not checked if load writes the whole register.
117
118 auto DefOpIt = find_if(Range: I.Operands, P: [](Operand const &Op) {
119 return Op.isDef() && Op.isReg();
120 });
121
122 if (DefOpIt == I.Operands.end())
123 return;
124
125 const Operand &DefOp = *DefOpIt;
126 const ExegesisTarget &ET = State.getExegesisTarget();
127 unsigned ScratchMemoryRegister = ET.getScratchMemoryRegister(
128 State.getTargetMachine().getTargetTriple());
129 const llvm::MCRegisterClass &RegClass =
130 State.getTargetMachine().getMCRegisterInfo()->getRegClass(
131 i: DefOp.getExplicitOperandInfo().RegClass);
132
133 // Register classes of def operand and memory operand must be the same
134 // to perform aliasing.
135 if (!RegClass.contains(Reg: ScratchMemoryRegister))
136 return;
137
138 ET.fillMemoryOperands(IT&: Variant, Reg: ScratchMemoryRegister, Offset: 0);
139 Variant.getValueFor(Op: DefOp) = MCOperand::createReg(Reg: ScratchMemoryRegister);
140
141 CodeTemplate CT;
142 CT.Execution = ExecutionModeBit;
143 CT.ScratchSpacePointerInReg = ScratchMemoryRegister;
144
145 CT.Info = std::string(ExecutionClassDescription);
146 CT.Instructions.push_back(x: std::move(Variant));
147 CodeTemplates.push_back(x: std::move(CT));
148 }
149
150 // TODO: implement more cases
151 return;
152 }
153 case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
154 // Making the execution of this instruction serial by selecting one def
155 // register to alias with one use register.
156 const AliasingConfigurations SelfAliasing(
157 Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
158 assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
159 "Instr must alias itself explicitly");
160 // This is a self aliasing instruction so defs and uses are from the same
161 // instance, hence twice Variant in the following call.
162 setRandomAliasing(AliasingConfigurations: SelfAliasing, DefIB&: Variant, UseIB&: Variant);
163 CodeTemplate CT;
164 CT.Execution = ExecutionModeBit;
165 CT.Info = std::string(ExecutionClassDescription);
166 CT.Instructions.push_back(x: std::move(Variant));
167 CodeTemplates.push_back(x: std::move(CT));
168 return;
169 }
170 case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
171 const Instruction &Instr = Variant.getInstr();
172 // Select back-to-back non-memory instruction.
173 for (const auto *OtherInstr : computeAliasingInstructions(
174 State, Instr: &Instr, MaxAliasingInstructions: kMaxAliasingInstructions, ForbiddenRegisters)) {
175 const AliasingConfigurations Forward(Instr, *OtherInstr,
176 ForbiddenRegisters);
177 const AliasingConfigurations Back(*OtherInstr, Instr, ForbiddenRegisters);
178 InstructionTemplate ThisIT(Variant);
179 InstructionTemplate OtherIT(OtherInstr);
180 if (!Forward.hasImplicitAliasing())
181 setRandomAliasing(AliasingConfigurations: Forward, DefIB&: ThisIT, UseIB&: OtherIT);
182 else if (!Back.hasImplicitAliasing())
183 setRandomAliasing(AliasingConfigurations: Back, DefIB&: OtherIT, UseIB&: ThisIT);
184 CodeTemplate CT;
185 CT.Execution = ExecutionModeBit;
186 CT.Info = std::string(ExecutionClassDescription);
187 CT.Instructions.push_back(x: std::move(ThisIT));
188 CT.Instructions.push_back(x: std::move(OtherIT));
189 CodeTemplates.push_back(x: std::move(CT));
190 }
191 return;
192 }
193 default:
194 llvm_unreachable("Unhandled enum value");
195 }
196}
197
198SerialSnippetGenerator::~SerialSnippetGenerator() = default;
199
200Expected<std::vector<CodeTemplate>>
201SerialSnippetGenerator::generateCodeTemplates(
202 InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
203 std::vector<CodeTemplate> Results;
204 const ExecutionMode EM =
205 getExecutionModes(Instr: Variant.getInstr(), ForbiddenRegisters);
206 for (const auto EC : kExecutionClasses) {
207 for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
208 appendCodeTemplates(State, Variant, ForbiddenRegisters, ExecutionModeBit,
209 ExecutionClassDescription: EC.Description, CodeTemplates&: Results);
210 if (!Results.empty())
211 break;
212 }
213 if (Results.empty())
214 return make_error<Failure>(
215 Args: "No strategy found to make the execution serial");
216 return std::move(Results);
217}
218
219} // namespace exegesis
220} // namespace llvm
221