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 const MCInstrDesc &OtherInstrDesc = OtherInstr.Description;
57 // Ignore instructions that we cannot run.
58 if (OtherInstrDesc.isPseudo() || OtherInstrDesc.usesCustomInsertionHook() ||
59 OtherInstrDesc.isBranch() || OtherInstrDesc.isIndirectBranch() ||
60 OtherInstrDesc.isCall() || OtherInstrDesc.isReturn()) {
61 continue;
62 }
63 if (OtherInstr.hasMemoryOperands())
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 else {
85 if (Instr.hasAliasingRegisters(ForbiddenRegisters))
86 EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS;
87 if (Instr.hasOneUseOrOneDef())
88 EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR;
89 }
90 return EM;
91}
92
93static void appendCodeTemplates(const LLVMState &State,
94 InstructionTemplate Variant,
95 const BitVector &ForbiddenRegisters,
96 ExecutionMode ExecutionModeBit,
97 StringRef ExecutionClassDescription,
98 std::vector<CodeTemplate> &CodeTemplates) {
99 assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two");
100 switch (ExecutionModeBit) {
101 case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS:
102 // Nothing to do, the instruction is always serial.
103 [[fallthrough]];
104 case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: {
105 // Picking whatever value for the tied variable will make the instruction
106 // serial.
107 CodeTemplate CT;
108 CT.Execution = ExecutionModeBit;
109 CT.Info = std::string(ExecutionClassDescription);
110 CT.Instructions.push_back(x: std::move(Variant));
111 CodeTemplates.push_back(x: std::move(CT));
112 return;
113 }
114 case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: {
115 // Select back-to-back memory instruction.
116 // TODO: Implement me.
117 return;
118 }
119 case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: {
120 // Making the execution of this instruction serial by selecting one def
121 // register to alias with one use register.
122 const AliasingConfigurations SelfAliasing(
123 Variant.getInstr(), Variant.getInstr(), ForbiddenRegisters);
124 assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() &&
125 "Instr must alias itself explicitly");
126 // This is a self aliasing instruction so defs and uses are from the same
127 // instance, hence twice Variant in the following call.
128 setRandomAliasing(AliasingConfigurations: SelfAliasing, DefIB&: Variant, UseIB&: Variant);
129 CodeTemplate CT;
130 CT.Execution = ExecutionModeBit;
131 CT.Info = std::string(ExecutionClassDescription);
132 CT.Instructions.push_back(x: std::move(Variant));
133 CodeTemplates.push_back(x: std::move(CT));
134 return;
135 }
136 case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: {
137 const Instruction &Instr = Variant.getInstr();
138 // Select back-to-back non-memory instruction.
139 for (const auto *OtherInstr : computeAliasingInstructions(
140 State, Instr: &Instr, MaxAliasingInstructions: kMaxAliasingInstructions, ForbiddenRegisters)) {
141 const AliasingConfigurations Forward(Instr, *OtherInstr,
142 ForbiddenRegisters);
143 const AliasingConfigurations Back(*OtherInstr, Instr, ForbiddenRegisters);
144 InstructionTemplate ThisIT(Variant);
145 InstructionTemplate OtherIT(OtherInstr);
146 if (!Forward.hasImplicitAliasing())
147 setRandomAliasing(AliasingConfigurations: Forward, DefIB&: ThisIT, UseIB&: OtherIT);
148 else if (!Back.hasImplicitAliasing())
149 setRandomAliasing(AliasingConfigurations: Back, DefIB&: OtherIT, UseIB&: ThisIT);
150 CodeTemplate CT;
151 CT.Execution = ExecutionModeBit;
152 CT.Info = std::string(ExecutionClassDescription);
153 CT.Instructions.push_back(x: std::move(ThisIT));
154 CT.Instructions.push_back(x: std::move(OtherIT));
155 CodeTemplates.push_back(x: std::move(CT));
156 }
157 return;
158 }
159 default:
160 llvm_unreachable("Unhandled enum value");
161 }
162}
163
164SerialSnippetGenerator::~SerialSnippetGenerator() = default;
165
166Expected<std::vector<CodeTemplate>>
167SerialSnippetGenerator::generateCodeTemplates(
168 InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const {
169 std::vector<CodeTemplate> Results;
170 const ExecutionMode EM =
171 getExecutionModes(Instr: Variant.getInstr(), ForbiddenRegisters);
172 for (const auto EC : kExecutionClasses) {
173 for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask))
174 appendCodeTemplates(State, Variant, ForbiddenRegisters, ExecutionModeBit,
175 ExecutionClassDescription: EC.Description, CodeTemplates&: Results);
176 if (!Results.empty())
177 break;
178 }
179 if (Results.empty())
180 return make_error<Failure>(
181 Args: "No strategy found to make the execution serial");
182 return std::move(Results);
183}
184
185} // namespace exegesis
186} // namespace llvm
187