1 //===-- SnippetGenerator.h --------------------------------------*- 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 /// \file 10 /// Defines the abstract SnippetGenerator class for generating code that allows 11 /// measuring a certain property of instructions (e.g. latency). 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H 16 #define LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H 17 18 #include "Assembler.h" 19 #include "BenchmarkCode.h" 20 #include "CodeTemplate.h" 21 #include "LlvmState.h" 22 #include "MCInstrDescView.h" 23 #include "RegisterAliasing.h" 24 #include "llvm/MC/MCInst.h" 25 #include "llvm/Support/Error.h" 26 #include <cstdlib> 27 #include <memory> 28 #include <vector> 29 30 namespace llvm { 31 namespace exegesis { 32 33 std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT); 34 35 // Generates code templates that has a self-dependency. 36 Expected<std::vector<CodeTemplate>> 37 generateSelfAliasingCodeTemplates(InstructionTemplate Variant); 38 39 // Generates code templates without assignment constraints. 40 Expected<std::vector<CodeTemplate>> 41 generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant, 42 StringRef Msg); 43 44 // A class representing failures that happened during Benchmark, they are used 45 // to report informations to the user. 46 class SnippetGeneratorFailure : public StringError { 47 public: 48 SnippetGeneratorFailure(const Twine &S); 49 }; 50 51 // Common code for all benchmark modes. 52 class SnippetGenerator { 53 public: 54 struct Options { 55 unsigned MaxConfigsPerOpcode = 1; 56 }; 57 58 explicit SnippetGenerator(const LLVMState &State, const Options &Opts); 59 60 virtual ~SnippetGenerator(); 61 62 // Calls generateCodeTemplate and expands it into one or more BenchmarkCode. 63 Error generateConfigurations(const InstructionTemplate &Variant, 64 std::vector<BenchmarkCode> &Benchmarks, 65 const BitVector &ExtraForbiddenRegs) const; 66 67 // Given a snippet, computes which registers the setup code needs to define. 68 std::vector<RegisterValue> computeRegisterInitialValues( 69 const std::vector<InstructionTemplate> &Snippet) const; 70 71 protected: 72 const LLVMState &State; 73 const Options Opts; 74 75 private: 76 // API to be implemented by subclasses. 77 virtual Expected<std::vector<CodeTemplate>> 78 generateCodeTemplates(InstructionTemplate Variant, 79 const BitVector &ForbiddenRegisters) const = 0; 80 }; 81 82 // A global Random Number Generator to randomize configurations. 83 // FIXME: Move random number generation into an object and make it seedable for 84 // unit tests. 85 std::mt19937 &randomGenerator(); 86 87 // Picks a random unsigned integer from 0 to Max (inclusive). 88 size_t randomIndex(size_t Max); 89 90 // Picks a random bit among the bits set in Vector and returns its index. 91 // Precondition: Vector must have at least one bit set. 92 size_t randomBit(const BitVector &Vector); 93 94 // Picks a random configuration, then selects a random def and a random use from 95 // it and finally set the selected values in the provided InstructionInstances. 96 void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations, 97 InstructionTemplate &DefIB, InstructionTemplate &UseIB); 98 99 // Assigns a Random Value to all Variables in IT that are still Invalid. 100 // Do not use any of the registers in `ForbiddenRegs`. 101 Error randomizeUnsetVariables(const LLVMState &State, 102 const BitVector &ForbiddenRegs, 103 InstructionTemplate &IT); 104 105 // Combination generator. 106 // 107 // Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following 108 // combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}. 109 // 110 // It is important to think of input as vector-of-vectors, where the 111 // outer vector is the variable space, and inner vector is choice space. 112 // The number of choices for each variable can be different. 113 // 114 // As for implementation, it is useful to think of this as a weird number, 115 // where each digit (==variable) may have different base (==number of choices). 116 // Thus modelling of 'produce next combination' is exactly analogous to the 117 // incrementing of an number - increment lowest digit (pick next choice for the 118 // variable), and if it wrapped to the beginning then increment next digit. 119 template <typename choice_type, typename choices_storage_type, 120 int variable_smallsize> 121 class CombinationGenerator { 122 template <typename T> struct WrappingIterator { 123 using value_type = T; 124 125 const ArrayRef<value_type> Range; 126 typename decltype(Range)::const_iterator Position; 127 128 // Rewind the tape, placing the position to again point at the beginning. rewindWrappingIterator129 void rewind() { Position = Range.begin(); } 130 131 // Advance position forward, possibly wrapping to the beginning. 132 // Returns whether the wrap happened. 133 bool operator++() { 134 ++Position; 135 bool Wrapped = Position == Range.end(); 136 if (Wrapped) 137 rewind(); 138 return Wrapped; 139 } 140 141 // Get the value at which we are currently pointing. 142 operator const value_type &() const { return *Position; } 143 WrappingIteratorWrappingIterator144 WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) { 145 assert(!Range.empty() && "The range must not be empty."); 146 rewind(); 147 } 148 }; 149 150 const ArrayRef<choices_storage_type> VariablesChoices; 151 performGeneration(const function_ref<bool (ArrayRef<choice_type>)> Callback)152 void performGeneration( 153 const function_ref<bool(ArrayRef<choice_type>)> Callback) const { 154 SmallVector<WrappingIterator<choice_type>, variable_smallsize> 155 VariablesState; 156 157 // 'increment' of the the whole VariablesState is defined identically to the 158 // increment of a number: starting from the least significant element, 159 // increment it, and if it wrapped, then propagate that carry by also 160 // incrementing next (more significant) element. 161 auto IncrementState = 162 [](MutableArrayRef<WrappingIterator<choice_type>> VariablesState) 163 -> bool { 164 for (WrappingIterator<choice_type> &Variable : 165 llvm::reverse(VariablesState)) { 166 bool Wrapped = ++Variable; 167 if (!Wrapped) 168 return false; // There you go, next combination is ready. 169 // We have carry - increment more significant variable next.. 170 } 171 return true; // MSB variable wrapped, no more unique combinations. 172 }; 173 174 // Initialize the per-variable state to refer to the possible choices for 175 // that variable. 176 VariablesState.reserve(VariablesChoices.size()); 177 for (ArrayRef<choice_type> VC : VariablesChoices) 178 VariablesState.emplace_back(VC); 179 180 // Temporary buffer to store each combination before performing Callback. 181 SmallVector<choice_type, variable_smallsize> CurrentCombination; 182 CurrentCombination.resize(VariablesState.size()); 183 184 while (true) { 185 // Gather the currently-selected variable choices into a vector. 186 for (auto I : llvm::zip(VariablesState, CurrentCombination)) 187 std::get<1>(I) = std::get<0>(I); 188 // And pass the new combination into callback, as intended. 189 if (/*Abort=*/Callback(CurrentCombination)) 190 return; 191 // And tick the state to next combination, which will be unique. 192 if (IncrementState(VariablesState)) 193 return; // All combinations produced. 194 } 195 }; 196 197 public: CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_)198 CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_) 199 : VariablesChoices(VariablesChoices_) { 200 #ifndef NDEBUG 201 assert(!VariablesChoices.empty() && "There should be some variables."); 202 llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) { 203 assert(!VariableChoices.empty() && 204 "There must always be some choice, at least a placeholder one."); 205 }); 206 #endif 207 } 208 209 // How many combinations can we produce, max? 210 // This is at most how many times the callback will be called. numCombinations()211 size_t numCombinations() const { 212 size_t NumVariants = 1; 213 for (ArrayRef<choice_type> VariableChoices : VariablesChoices) 214 NumVariants *= VariableChoices.size(); 215 assert(NumVariants >= 1 && 216 "We should always end up producing at least one combination"); 217 return NumVariants; 218 } 219 220 // Actually perform exhaustive combination generation. 221 // Each result will be passed into the callback. generate(const function_ref<bool (ArrayRef<choice_type>)> Callback)222 void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) { 223 performGeneration(Callback); 224 } 225 }; 226 227 } // namespace exegesis 228 } // namespace llvm 229 230 #endif // LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H 231