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