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