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 // Randomly iterate the set of instructions. 42 std::vector<unsigned> Opcodes; 43 Opcodes.resize(State.getInstrInfo().getNumOpcodes()); 44 std::iota(Opcodes.begin(), Opcodes.end(), 0U); 45 llvm::shuffle(Opcodes.begin(), Opcodes.end(), randomGenerator()); 46 47 std::vector<const Instruction *> AliasingInstructions; 48 for (const unsigned OtherOpcode : Opcodes) { 49 if (OtherOpcode == Instr->Description.getOpcode()) 50 continue; 51 const Instruction &OtherInstr = State.getIC().getInstr(OtherOpcode); 52 const MCInstrDesc &OtherInstrDesc = OtherInstr.Description; 53 // Ignore instructions that we cannot run. 54 if (OtherInstrDesc.isPseudo() || OtherInstrDesc.usesCustomInsertionHook() || 55 OtherInstrDesc.isBranch() || OtherInstrDesc.isIndirectBranch() || 56 OtherInstrDesc.isCall() || OtherInstrDesc.isReturn()) { 57 continue; 58 } 59 if (OtherInstr.hasMemoryOperands()) 60 continue; 61 if (!State.getExegesisTarget().allowAsBackToBack(OtherInstr)) 62 continue; 63 if (Instr->hasAliasingRegistersThrough(OtherInstr, ForbiddenRegisters)) 64 AliasingInstructions.push_back(&OtherInstr); 65 if (AliasingInstructions.size() >= MaxAliasingInstructions) 66 break; 67 } 68 return AliasingInstructions; 69 } 70 71 static ExecutionMode getExecutionModes(const Instruction &Instr, 72 const BitVector &ForbiddenRegisters) { 73 ExecutionMode EM = ExecutionMode::UNKNOWN; 74 if (Instr.hasAliasingImplicitRegisters()) 75 EM |= ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS; 76 if (Instr.hasTiedRegisters()) 77 EM |= ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS; 78 if (Instr.hasMemoryOperands()) 79 EM |= ExecutionMode::SERIAL_VIA_MEMORY_INSTR; 80 else { 81 if (Instr.hasAliasingRegisters(ForbiddenRegisters)) 82 EM |= ExecutionMode::SERIAL_VIA_EXPLICIT_REGS; 83 if (Instr.hasOneUseOrOneDef()) 84 EM |= ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR; 85 } 86 return EM; 87 } 88 89 static void appendCodeTemplates(const LLVMState &State, 90 InstructionTemplate Variant, 91 const BitVector &ForbiddenRegisters, 92 ExecutionMode ExecutionModeBit, 93 StringRef ExecutionClassDescription, 94 std::vector<CodeTemplate> &CodeTemplates) { 95 assert(isEnumValue(ExecutionModeBit) && "Bit must be a power of two"); 96 switch (ExecutionModeBit) { 97 case ExecutionMode::ALWAYS_SERIAL_IMPLICIT_REGS_ALIAS: 98 // Nothing to do, the instruction is always serial. 99 LLVM_FALLTHROUGH; 100 case ExecutionMode::ALWAYS_SERIAL_TIED_REGS_ALIAS: { 101 // Picking whatever value for the tied variable will make the instruction 102 // serial. 103 CodeTemplate CT; 104 CT.Execution = ExecutionModeBit; 105 CT.Info = std::string(ExecutionClassDescription); 106 CT.Instructions.push_back(std::move(Variant)); 107 CodeTemplates.push_back(std::move(CT)); 108 return; 109 } 110 case ExecutionMode::SERIAL_VIA_MEMORY_INSTR: { 111 // Select back-to-back memory instruction. 112 // TODO: Implement me. 113 return; 114 } 115 case ExecutionMode::SERIAL_VIA_EXPLICIT_REGS: { 116 // Making the execution of this instruction serial by selecting one def 117 // register to alias with one use register. 118 const AliasingConfigurations SelfAliasing(Variant.getInstr(), 119 Variant.getInstr()); 120 assert(!SelfAliasing.empty() && !SelfAliasing.hasImplicitAliasing() && 121 "Instr must alias itself explicitly"); 122 // This is a self aliasing instruction so defs and uses are from the same 123 // instance, hence twice Variant in the following call. 124 setRandomAliasing(SelfAliasing, Variant, Variant); 125 CodeTemplate CT; 126 CT.Execution = ExecutionModeBit; 127 CT.Info = std::string(ExecutionClassDescription); 128 CT.Instructions.push_back(std::move(Variant)); 129 CodeTemplates.push_back(std::move(CT)); 130 return; 131 } 132 case ExecutionMode::SERIAL_VIA_NON_MEMORY_INSTR: { 133 const Instruction &Instr = Variant.getInstr(); 134 // Select back-to-back non-memory instruction. 135 for (const auto *OtherInstr : computeAliasingInstructions( 136 State, &Instr, kMaxAliasingInstructions, ForbiddenRegisters)) { 137 const AliasingConfigurations Forward(Instr, *OtherInstr); 138 const AliasingConfigurations Back(*OtherInstr, Instr); 139 InstructionTemplate ThisIT(Variant); 140 InstructionTemplate OtherIT(OtherInstr); 141 if (!Forward.hasImplicitAliasing()) 142 setRandomAliasing(Forward, ThisIT, OtherIT); 143 else if (!Back.hasImplicitAliasing()) 144 setRandomAliasing(Back, OtherIT, ThisIT); 145 CodeTemplate CT; 146 CT.Execution = ExecutionModeBit; 147 CT.Info = std::string(ExecutionClassDescription); 148 CT.Instructions.push_back(std::move(ThisIT)); 149 CT.Instructions.push_back(std::move(OtherIT)); 150 CodeTemplates.push_back(std::move(CT)); 151 } 152 return; 153 } 154 default: 155 llvm_unreachable("Unhandled enum value"); 156 } 157 } 158 159 SerialSnippetGenerator::~SerialSnippetGenerator() = default; 160 161 Expected<std::vector<CodeTemplate>> 162 SerialSnippetGenerator::generateCodeTemplates( 163 InstructionTemplate Variant, const BitVector &ForbiddenRegisters) const { 164 std::vector<CodeTemplate> Results; 165 const ExecutionMode EM = 166 getExecutionModes(Variant.getInstr(), ForbiddenRegisters); 167 for (const auto EC : kExecutionClasses) { 168 for (const auto ExecutionModeBit : getExecutionModeBits(EM & EC.Mask)) 169 appendCodeTemplates(State, Variant, ForbiddenRegisters, ExecutionModeBit, 170 EC.Description, Results); 171 if (!Results.empty()) 172 break; 173 } 174 if (Results.empty()) 175 return make_error<Failure>( 176 "No strategy found to make the execution serial"); 177 return std::move(Results); 178 } 179 180 } // namespace exegesis 181 } // namespace llvm 182