| //===-- SnippetGenerator.h --------------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// Defines the abstract SnippetGenerator class for generating code that allows |
| /// measuring a certain property of instructions (e.g. latency). |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H |
| #define LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H |
| |
| #include "Assembler.h" |
| #include "BenchmarkCode.h" |
| #include "CodeTemplate.h" |
| #include "LlvmState.h" |
| #include "MCInstrDescView.h" |
| #include "RegisterAliasing.h" |
| #include "llvm/MC/MCInst.h" |
| #include "llvm/Support/Error.h" |
| #include <cstdlib> |
| #include <memory> |
| #include <vector> |
| |
| namespace llvm { |
| namespace exegesis { |
| |
| std::vector<CodeTemplate> getSingleton(CodeTemplate &&CT); |
| |
| // Generates code templates that has a self-dependency. |
| Expected<std::vector<CodeTemplate>> |
| generateSelfAliasingCodeTemplates(InstructionTemplate Variant); |
| |
| // Generates code templates without assignment constraints. |
| Expected<std::vector<CodeTemplate>> |
| generateUnconstrainedCodeTemplates(const InstructionTemplate &Variant, |
| StringRef Msg); |
| |
| // A class representing failures that happened during Benchmark, they are used |
| // to report informations to the user. |
| class SnippetGeneratorFailure : public StringError { |
| public: |
| SnippetGeneratorFailure(const Twine &S); |
| }; |
| |
| // Common code for all benchmark modes. |
| class SnippetGenerator { |
| public: |
| struct Options { |
| unsigned MaxConfigsPerOpcode = 1; |
| }; |
| |
| explicit SnippetGenerator(const LLVMState &State, const Options &Opts); |
| |
| virtual ~SnippetGenerator(); |
| |
| // Calls generateCodeTemplate and expands it into one or more BenchmarkCode. |
| Error generateConfigurations(const InstructionTemplate &Variant, |
| std::vector<BenchmarkCode> &Benchmarks, |
| const BitVector &ExtraForbiddenRegs) const; |
| |
| // Given a snippet, computes which registers the setup code needs to define. |
| std::vector<RegisterValue> computeRegisterInitialValues( |
| const std::vector<InstructionTemplate> &Snippet) const; |
| |
| protected: |
| const LLVMState &State; |
| const Options Opts; |
| |
| private: |
| // API to be implemented by subclasses. |
| virtual Expected<std::vector<CodeTemplate>> |
| generateCodeTemplates(InstructionTemplate Variant, |
| const BitVector &ForbiddenRegisters) const = 0; |
| }; |
| |
| // A global Random Number Generator to randomize configurations. |
| // FIXME: Move random number generation into an object and make it seedable for |
| // unit tests. |
| std::mt19937 &randomGenerator(); |
| |
| // Picks a random unsigned integer from 0 to Max (inclusive). |
| size_t randomIndex(size_t Max); |
| |
| // Picks a random bit among the bits set in Vector and returns its index. |
| // Precondition: Vector must have at least one bit set. |
| size_t randomBit(const BitVector &Vector); |
| |
| // Picks a random configuration, then selects a random def and a random use from |
| // it and finally set the selected values in the provided InstructionInstances. |
| void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations, |
| InstructionTemplate &DefIB, InstructionTemplate &UseIB); |
| |
| // Assigns a Random Value to all Variables in IT that are still Invalid. |
| // Do not use any of the registers in `ForbiddenRegs`. |
| Error randomizeUnsetVariables(const LLVMState &State, |
| const BitVector &ForbiddenRegs, |
| InstructionTemplate &IT); |
| |
| // Combination generator. |
| // |
| // Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following |
| // combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}. |
| // |
| // It is important to think of input as vector-of-vectors, where the |
| // outer vector is the variable space, and inner vector is choice space. |
| // The number of choices for each variable can be different. |
| // |
| // As for implementation, it is useful to think of this as a weird number, |
| // where each digit (==variable) may have different base (==number of choices). |
| // Thus modelling of 'produce next combination' is exactly analogous to the |
| // incrementing of an number - increment lowest digit (pick next choice for the |
| // variable), and if it wrapped to the beginning then increment next digit. |
| template <typename choice_type, typename choices_storage_type, |
| int variable_smallsize> |
| class CombinationGenerator { |
| template <typename T> struct WrappingIterator { |
| using value_type = T; |
| |
| const ArrayRef<value_type> Range; |
| typename decltype(Range)::const_iterator Position; |
| |
| // Rewind the tape, placing the position to again point at the beginning. |
| void rewind() { Position = Range.begin(); } |
| |
| // Advance position forward, possibly wrapping to the beginning. |
| // Returns whether the wrap happened. |
| bool operator++() { |
| ++Position; |
| bool Wrapped = Position == Range.end(); |
| if (Wrapped) |
| rewind(); |
| return Wrapped; |
| } |
| |
| // Get the value at which we are currently pointing. |
| operator const value_type &() const { return *Position; } |
| |
| WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) { |
| assert(!Range.empty() && "The range must not be empty."); |
| rewind(); |
| } |
| }; |
| |
| const ArrayRef<choices_storage_type> VariablesChoices; |
| |
| void performGeneration( |
| const function_ref<bool(ArrayRef<choice_type>)> Callback) const { |
| SmallVector<WrappingIterator<choice_type>, variable_smallsize> |
| VariablesState; |
| |
| // 'increment' of the the whole VariablesState is defined identically to the |
| // increment of a number: starting from the least significant element, |
| // increment it, and if it wrapped, then propagate that carry by also |
| // incrementing next (more significant) element. |
| auto IncrementState = |
| [](MutableArrayRef<WrappingIterator<choice_type>> VariablesState) |
| -> bool { |
| for (WrappingIterator<choice_type> &Variable : |
| llvm::reverse(VariablesState)) { |
| bool Wrapped = ++Variable; |
| if (!Wrapped) |
| return false; // There you go, next combination is ready. |
| // We have carry - increment more significant variable next.. |
| } |
| return true; // MSB variable wrapped, no more unique combinations. |
| }; |
| |
| // Initialize the per-variable state to refer to the possible choices for |
| // that variable. |
| VariablesState.reserve(VariablesChoices.size()); |
| for (ArrayRef<choice_type> VC : VariablesChoices) |
| VariablesState.emplace_back(VC); |
| |
| // Temporary buffer to store each combination before performing Callback. |
| SmallVector<choice_type, variable_smallsize> CurrentCombination; |
| CurrentCombination.resize(VariablesState.size()); |
| |
| while (true) { |
| // Gather the currently-selected variable choices into a vector. |
| for (auto I : llvm::zip(VariablesState, CurrentCombination)) |
| std::get<1>(I) = std::get<0>(I); |
| // And pass the new combination into callback, as intended. |
| if (/*Abort=*/Callback(CurrentCombination)) |
| return; |
| // And tick the state to next combination, which will be unique. |
| if (IncrementState(VariablesState)) |
| return; // All combinations produced. |
| } |
| }; |
| |
| public: |
| CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_) |
| : VariablesChoices(VariablesChoices_) { |
| #ifndef NDEBUG |
| assert(!VariablesChoices.empty() && "There should be some variables."); |
| llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) { |
| assert(!VariableChoices.empty() && |
| "There must always be some choice, at least a placeholder one."); |
| }); |
| #endif |
| } |
| |
| // How many combinations can we produce, max? |
| // This is at most how many times the callback will be called. |
| size_t numCombinations() const { |
| size_t NumVariants = 1; |
| for (ArrayRef<choice_type> VariableChoices : VariablesChoices) |
| NumVariants *= VariableChoices.size(); |
| assert(NumVariants >= 1 && |
| "We should always end up producing at least one combination"); |
| return NumVariants; |
| } |
| |
| // Actually perform exhaustive combination generation. |
| // Each result will be passed into the callback. |
| void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) { |
| performGeneration(Callback); |
| } |
| }; |
| |
| } // namespace exegesis |
| } // namespace llvm |
| |
| #endif // LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H |