1 files changed, 119 insertions, 0 deletions
diff --git a/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h
new file mode 100644
index 00000000000..be21f8725ad
--- /dev/null
+++ b/llvm/tools/llvm-exegesis/lib/InstructionSnippetGenerator.h
@@ -0,0 +1,119 @@
+//===-- InstructionSnippetGenerator.h ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Defines helper classes to generate code snippets, in particular register
+/// assignment.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H
+
+#include "OperandGraph.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include <vector>
+
+namespace exegesis {
+
+// A Variable represents a set of possible values that we need to choose from.
+// It may represent one or more explicit operands that are tied together, or one
+// implicit operand.
+class Variable final {
+public:
+  bool IsUse = false;
+  bool IsDef = false;
+  bool IsReg = false;
+
+  // Lists all the explicit operand indices that are tied to this variable.
+  // Empty if Variable represents an implicit operand.
+  llvm::SmallVector<size_t, 8> ExplicitOperands;
+
+  // - In case of explicit operands, PossibleRegisters is the expansion of the
+  // operands's RegClass registers. Please note that tied together explicit
+  // operands share the same RegClass.
+  // - In case of implicit operands, PossibleRegisters is a singleton MCPhysReg.
+  llvm::SmallSetVector<llvm::MCPhysReg, 16> PossibleRegisters;
+
+  // If RegInfo is null, register names won't get resolved.
+  void print(llvm::raw_ostream &OS, const llvm::MCRegisterInfo *RegInfo) const;
+};
+
+// Builds a model of implicit and explicit operands for InstrDesc into
+// Variables.
+llvm::SmallVector<Variable, 8>
+getVariables(const llvm::MCRegisterInfo &RegInfo,
+             const llvm::MCInstrDesc &InstrDesc,
+             const llvm::BitVector &ReservedRegs);
+
+// A simple object to represent a Variable assignement.
+struct VariableAssignment {
+  VariableAssignment(size_t VarIdx, llvm::MCPhysReg AssignedReg);
+
+  size_t VarIdx;
+  llvm::MCPhysReg AssignedReg;
+
+  bool operator==(const VariableAssignment &) const;
+  bool operator<(const VariableAssignment &) const;
+};
+
+// An AssignmentChain is a set of assignement realizing a dependency chain.
+// We inherit from std::set to leverage uniqueness of elements.
+using AssignmentChain = std::set<VariableAssignment>;
+
+// Debug function to print an assignment chain.
+void dumpAssignmentChain(const llvm::MCRegisterInfo &RegInfo,
+                         const AssignmentChain &Chain);
+
+// Inserts Variables into a graph representing register aliasing and finds all
+// the possible dependency chains for this instruction, i.e. all the possible
+// assignement of operands that would make execution of the instruction
+// sequential.
+std::vector<AssignmentChain>
+computeSequentialAssignmentChains(const llvm::MCRegisterInfo &RegInfo,
+                                  llvm::ArrayRef<Variable> Vars);
+
+// Selects a random configuration leading to a dependency chain.
+// The result is a vector of the same size as `Vars`.
+// `random_index_for_size` is a functor giving a random value in [0, arg[.
+std::vector<llvm::MCPhysReg>
+getRandomAssignment(llvm::ArrayRef<Variable> Vars,
+                    llvm::ArrayRef<AssignmentChain> Chains,
+                    const std::function<size_t(size_t)> &RandomIndexForSize);
+
+// Finds an assignment of registers to variables such that no two variables are
+// assigned the same register.
+// The result is a vector of the same size as `Vars`, or `{}` if the
+// assignment is not feasible.
+std::vector<llvm::MCPhysReg>
+getExclusiveAssignment(llvm::ArrayRef<Variable> Vars);
+
+// Finds a greedy assignment of registers to variables. Each variable gets
+// assigned the first possible register that is not already assigned to a
+// previous variable. If there is no such register, the variable gets assigned
+// the first possible register.
+// The result is a vector of the same size as `Vars`, or `{}` if the
+// assignment is not feasible.
+std::vector<llvm::MCPhysReg>
+getGreedyAssignment(llvm::ArrayRef<Variable> Vars);
+
+// Generates an LLVM MCInst with the previously computed variables.
+// Immediate values are set to 1.
+llvm::MCInst generateMCInst(const llvm::MCInstrDesc &InstrDesc,
+                            llvm::ArrayRef<Variable> Vars,
+                            llvm::ArrayRef<llvm::MCPhysReg> VarRegs);
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_INSTRUCTIONSNIPPETGENERATOR_H