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 18 namespace llvm { 19 namespace exegesis { 20 21 struct ExecutionClass { 22 ExecutionMode Mask; 23 const char *Description; 24 } static const kExecutionClasses[] = { 25 {ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS | 26 ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS, 27 "Repeating a single implicitly serial instruction"}, 28 {ExecutionMode::SERIAL_VIA_EXPLICIT_REGS, 29 "Repeating a single explicitly serial instruction"}, 30 {ExecutionMode::SERIAL_VIA_MEMORY_INSTR | 31 ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR, 32 "Repeating two instructions"}, 33 }; 34 35 static constexpr size_t kMaxAliasingInstructions = 10; 36 37 static std::vector<const Instruction *> 38 computeAliasingInstructions(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(State.getInstrInfo().getNumOpcodes()); 46 std::iota(Opcodes.begin(), Opcodes.end(), 0U); 47 llvm::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator()); 48 49 std::vector<const Instruction *> AliasingInstructions; 50 for (const unsigned OtherOpcode : Opcodes) { 51 if (!ET.isOpcodeAvailable(OtherOpcode, AvailableFeatures)) 52 continue; 53 if (OtherOpcode == Instr->Description.getOpcode()) 54 continue; 55 const Instruction &OtherInstr = State.getIC().getInstr(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(OtherInstr)) 66 continue; 67 if (Instr->hasAliasingRegistersThrough(OtherInstr, ForbiddenRegisters)) 68 AliasingInstructions.push_back(&OtherInstr); 69 if (AliasingInstructions.size() >= MaxAliasingInstructions) 70 break; 71 } 72 return AliasingInstructions; 73 } 74 75 static 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 93 static 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(std::move(Variant)); 111 CodeTemplates.push_back(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(SelfAliasing, Variant, Variant); 129 CodeTemplate CT; 130 CT.Execution = ExecutionModeBit; 131 CT.Info = std::string(ExecutionClassDescription); 132 CT.Instructions.push_back(std::move(Variant)); 133 CodeTemplates.push_back(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, 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(Forward, ThisIT, OtherIT); 148 else if (!Back.hasImplicitAliasing()) 149 setRandomAliasing(Back, OtherIT, ThisIT); 150 CodeTemplate CT; 151 CT.Execution = ExecutionModeBit; 152 CT.Info = std::string(ExecutionClassDescription); 153 CT.Instructions.push_back(std::move(ThisIT)); 154 CT.Instructions.push_back(std::move(OtherIT)); 155 CodeTemplates.push_back(std::move(CT)); 156 } 157 return; 158 } 159 default: 160 llvm_unreachable("Unhandled enum value"); 161 } 162 } 163 164 SerialSnippetGenerator::~SerialSnippetGenerator() = default; 165 166 Expected<std::vector<CodeTemplate>> 167 SerialSnippetGenerator::generateCodeTemplates( 168 InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const { 169 std::vector<CodeTemplate> Results; 170 const ExecutionMode EM = 171 getExecutionModes(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 EC.Description, Results); 176 if (!Results.empty()) 177 break; 178 } 179 if (Results.empty()) 180 return make_error<Failure>( 181 "No strategy found to make the execution serial"); 182 return std::move(Results); 183 } 184 185 } // namespace exegesis 186 } // namespace llvm 187