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