1 //===-- SnippetGenerator.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 <array> 10 #include <string> 11 12 #include "Assembler.h" 13 #include "Error.h" 14 #include "MCInstrDescView.h" 15 #include "SnippetGenerator.h" 16 #include "Target.h" 17 #include "llvm/ADT/StringExtras.h" 18 #include "llvm/ADT/StringRef.h" 19 #include "llvm/ADT/Twine.h" 20 #include "llvm/Support/FileSystem.h" 21 #include "llvm/Support/FormatVariadic.h" 22 #include "llvm/Support/Program.h" 23 24 namespace llvm { 25 namespace exegesis { 26 27 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT) { 28 std::vector<CodeTemplate> Result; 29 Result.push_back(std::move(CT)); 30 return Result; 31 } 32 33 SnippetGeneratorFailure::SnippetGeneratorFailure(const Twine &S) 34 : StringError(S, inconvertibleErrorCode()) {} 35 36 SnippetGenerator::SnippetGenerator(const LLVMState &State, const Options &Opts) 37 : State(State), Opts(Opts) {} 38 39 SnippetGenerator::~SnippetGenerator() = default; 40 41 Expected<std::vector<BenchmarkCode>> SnippetGenerator::generateConfigurations( 42 const Instruction &Instr, const BitVector &ExtraForbiddenRegs) const { 43 BitVector ForbiddenRegs = State.getRATC().reservedRegisters(); 44 ForbiddenRegs |= ExtraForbiddenRegs; 45 // If the instruction has memory registers, prevent the generator from 46 // using the scratch register and its aliasing registers. 47 if (Instr.hasMemoryOperands()) { 48 const auto &ET = State.getExegesisTarget(); 49 unsigned ScratchSpacePointerInReg = 50 ET.getScratchMemoryRegister(State.getTargetMachine().getTargetTriple()); 51 if (ScratchSpacePointerInReg == 0) 52 return make_error<Failure>( 53 "Infeasible : target does not support memory instructions"); 54 const auto &ScratchRegAliases = 55 State.getRATC().getRegister(ScratchSpacePointerInReg).aliasedBits(); 56 // If the instruction implicitly writes to ScratchSpacePointerInReg , abort. 57 // FIXME: We could make a copy of the scratch register. 58 for (const auto &Op : Instr.Operands) { 59 if (Op.isDef() && Op.isImplicitReg() && 60 ScratchRegAliases.test(Op.getImplicitReg())) 61 return make_error<Failure>( 62 "Infeasible : memory instruction uses scratch memory register"); 63 } 64 ForbiddenRegs |= ScratchRegAliases; 65 } 66 67 if (auto E = generateCodeTemplates(Instr, ForbiddenRegs)) { 68 std::vector<BenchmarkCode> Output; 69 for (CodeTemplate &CT : E.get()) { 70 // TODO: Generate as many BenchmarkCode as needed. 71 { 72 BenchmarkCode BC; 73 BC.Info = CT.Info; 74 for (InstructionTemplate &IT : CT.Instructions) { 75 if (auto error = randomizeUnsetVariables(State, ForbiddenRegs, IT)) 76 return error; 77 BC.Key.Instructions.push_back(IT.build()); 78 } 79 if (CT.ScratchSpacePointerInReg) 80 BC.LiveIns.push_back(CT.ScratchSpacePointerInReg); 81 BC.Key.RegisterInitialValues = 82 computeRegisterInitialValues(CT.Instructions); 83 BC.Key.Config = CT.Config; 84 Output.push_back(std::move(BC)); 85 if (Output.size() >= Opts.MaxConfigsPerOpcode) 86 return Output; // Early exit if we exceeded the number of allowed 87 // configs. 88 } 89 } 90 return Output; 91 } else 92 return E.takeError(); 93 } 94 95 std::vector<RegisterValue> SnippetGenerator::computeRegisterInitialValues( 96 const std::vector<InstructionTemplate> &Instructions) const { 97 // Collect all register uses and create an assignment for each of them. 98 // Ignore memory operands which are handled separately. 99 // Loop invariant: DefinedRegs[i] is true iif it has been set at least once 100 // before the current instruction. 101 BitVector DefinedRegs = State.getRATC().emptyRegisters(); 102 std::vector<RegisterValue> RIV; 103 for (const InstructionTemplate &IT : Instructions) { 104 // Returns the register that this Operand sets or uses, or 0 if this is not 105 // a register. 106 const auto GetOpReg = [&IT](const Operand &Op) -> unsigned { 107 if (Op.isMemory()) 108 return 0; 109 if (Op.isImplicitReg()) 110 return Op.getImplicitReg(); 111 if (Op.isExplicit() && IT.getValueFor(Op).isReg()) 112 return IT.getValueFor(Op).getReg(); 113 return 0; 114 }; 115 // Collect used registers that have never been def'ed. 116 for (const Operand &Op : IT.getInstr().Operands) { 117 if (Op.isUse()) { 118 const unsigned Reg = GetOpReg(Op); 119 if (Reg > 0 && !DefinedRegs.test(Reg)) { 120 RIV.push_back(RegisterValue::zero(Reg)); 121 DefinedRegs.set(Reg); 122 } 123 } 124 } 125 // Mark defs as having been def'ed. 126 for (const Operand &Op : IT.getInstr().Operands) { 127 if (Op.isDef()) { 128 const unsigned Reg = GetOpReg(Op); 129 if (Reg > 0) 130 DefinedRegs.set(Reg); 131 } 132 } 133 } 134 return RIV; 135 } 136 137 Expected<std::vector<CodeTemplate>> 138 generateSelfAliasingCodeTemplates(const Instruction &Instr) { 139 const AliasingConfigurations SelfAliasing(Instr, Instr); 140 if (SelfAliasing.empty()) 141 return make_error<SnippetGeneratorFailure>("empty self aliasing"); 142 std::vector<CodeTemplate> Result; 143 Result.emplace_back(); 144 CodeTemplate &CT = Result.back(); 145 InstructionTemplate IT(&Instr); 146 if (SelfAliasing.hasImplicitAliasing()) { 147 CT.Info = "implicit Self cycles, picking random values."; 148 } else { 149 CT.Info = "explicit self cycles, selecting one aliasing Conf."; 150 // This is a self aliasing instruction so defs and uses are from the same 151 // instance, hence twice IT in the following call. 152 setRandomAliasing(SelfAliasing, IT, IT); 153 } 154 CT.Instructions.push_back(std::move(IT)); 155 return Result; 156 } 157 158 Expected<std::vector<CodeTemplate>> 159 generateUnconstrainedCodeTemplates(const Instruction &Instr, StringRef Msg) { 160 std::vector<CodeTemplate> Result; 161 Result.emplace_back(); 162 CodeTemplate &CT = Result.back(); 163 CT.Info = 164 std::string(formatv("{0}, repeating an unconstrained assignment", Msg)); 165 CT.Instructions.emplace_back(&Instr); 166 return Result; 167 } 168 169 std::mt19937 &randomGenerator() { 170 static std::random_device RandomDevice; 171 static std::mt19937 RandomGenerator(RandomDevice()); 172 return RandomGenerator; 173 } 174 175 size_t randomIndex(size_t Max) { 176 std::uniform_int_distribution<> Distribution(0, Max); 177 return Distribution(randomGenerator()); 178 } 179 180 template <typename C> 181 static auto randomElement(const C &Container) -> decltype(Container[0]) { 182 assert(!Container.empty() && 183 "Can't pick a random element from an empty container)"); 184 return Container[randomIndex(Container.size() - 1)]; 185 } 186 187 static void setRegisterOperandValue(const RegisterOperandAssignment &ROV, 188 InstructionTemplate &IB) { 189 assert(ROV.Op); 190 if (ROV.Op->isExplicit()) { 191 auto &AssignedValue = IB.getValueFor(*ROV.Op); 192 if (AssignedValue.isValid()) { 193 assert(AssignedValue.isReg() && AssignedValue.getReg() == ROV.Reg); 194 return; 195 } 196 AssignedValue = MCOperand::createReg(ROV.Reg); 197 } else { 198 assert(ROV.Op->isImplicitReg()); 199 assert(ROV.Reg == ROV.Op->getImplicitReg()); 200 } 201 } 202 203 size_t randomBit(const BitVector &Vector) { 204 assert(Vector.any()); 205 auto Itr = Vector.set_bits_begin(); 206 for (size_t I = randomIndex(Vector.count() - 1); I != 0; --I) 207 ++Itr; 208 return *Itr; 209 } 210 211 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations, 212 InstructionTemplate &DefIB, InstructionTemplate &UseIB) { 213 assert(!AliasingConfigurations.empty()); 214 assert(!AliasingConfigurations.hasImplicitAliasing()); 215 const auto &RandomConf = randomElement(AliasingConfigurations.Configurations); 216 setRegisterOperandValue(randomElement(RandomConf.Defs), DefIB); 217 setRegisterOperandValue(randomElement(RandomConf.Uses), UseIB); 218 } 219 220 static Error randomizeMCOperand(const LLVMState &State, 221 const Instruction &Instr, const Variable &Var, 222 MCOperand &AssignedValue, 223 const BitVector &ForbiddenRegs) { 224 const Operand &Op = Instr.getPrimaryOperand(Var); 225 if (Op.getExplicitOperandInfo().OperandType >= 226 MCOI::OperandType::OPERAND_FIRST_TARGET) 227 return State.getExegesisTarget().randomizeTargetMCOperand( 228 Instr, Var, AssignedValue, ForbiddenRegs); 229 switch (Op.getExplicitOperandInfo().OperandType) { 230 case MCOI::OperandType::OPERAND_IMMEDIATE: 231 // FIXME: explore immediate values too. 232 AssignedValue = MCOperand::createImm(1); 233 break; 234 case MCOI::OperandType::OPERAND_REGISTER: { 235 assert(Op.isReg()); 236 auto AllowedRegs = Op.getRegisterAliasing().sourceBits(); 237 assert(AllowedRegs.size() == ForbiddenRegs.size()); 238 for (auto I : ForbiddenRegs.set_bits()) 239 AllowedRegs.reset(I); 240 if (!AllowedRegs.any()) 241 return make_error<Failure>( 242 Twine("no available registers:\ncandidates:\n") 243 .concat(debugString(State.getRegInfo(), 244 Op.getRegisterAliasing().sourceBits())) 245 .concat("\nforbidden:\n") 246 .concat(debugString(State.getRegInfo(), ForbiddenRegs))); 247 AssignedValue = MCOperand::createReg(randomBit(AllowedRegs)); 248 break; 249 } 250 default: 251 break; 252 } 253 return Error::success(); 254 } 255 256 Error randomizeUnsetVariables(const LLVMState &State, 257 const BitVector &ForbiddenRegs, 258 InstructionTemplate &IT) { 259 for (const Variable &Var : IT.getInstr().Variables) { 260 MCOperand &AssignedValue = IT.getValueFor(Var); 261 if (!AssignedValue.isValid()) 262 if (auto Err = randomizeMCOperand(State, IT.getInstr(), Var, 263 AssignedValue, ForbiddenRegs)) 264 return Err; 265 } 266 return Error::success(); 267 } 268 269 } // namespace exegesis 270 } // namespace llvm 271