1 files changed, 89 insertions, 0 deletions
diff --git a/llvm/tools/llvm-exegesis/lib/OperandGraph.h b/llvm/tools/llvm-exegesis/lib/OperandGraph.h
new file mode 100644
index 00000000000..3db1a2a578b
--- /dev/null
+++ b/llvm/tools/llvm-exegesis/lib/OperandGraph.h
@@ -0,0 +1,89 @@
+//===-- OperandGraph.h ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// A collection of tools to model register aliasing and instruction operand.
+/// This is used to find an aliasing between the input and output registers of
+/// an instruction. It allows us to repeat an instruction and make sure that
+/// successive instances are executed sequentially.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H
+
+#include "llvm/MC/MCRegisterInfo.h"
+#include <map>
+#include <set>
+#include <tuple>
+#include <vector>
+
+namespace exegesis {
+namespace graph {
+
+enum class NodeType {
+  VARIABLE, // An set of "tied together operands" to resolve.
+  REG,      // A particular register.
+  IN,       // The input node.
+  OUT       // The output node.
+};
+
+// A Node in the graph, it has a type and an int value.
+struct Node : public std::pair<NodeType, int> {
+  using std::pair<NodeType, int>::pair;
+
+  static Node Reg(int Value) { return {NodeType::REG, Value}; }
+  static Node Var(int Value) { return {NodeType::VARIABLE, Value}; }
+  static Node In() { return {NodeType::IN, 0}; }
+  static Node Out() { return {NodeType::OUT, 0}; }
+
+  NodeType type() const;
+  int regValue() const; // checks that type==REG and returns value.
+  int varValue() const; // checks that type==VARIABLE and returns value.
+
+  void dump(const llvm::MCRegisterInfo &RegInfo) const;
+};
+
+// Graph represents the connectivity of registers for a particular instruction.
+// This object is used to select registers that would create a dependency chain
+// between instruction's input and output.
+struct Graph {
+public:
+  void connect(const Node From, const Node To);
+  void disconnect(const Node From, const Node To);
+
+  // Tries to find a path between 'From' and 'To' nodes.
+  // Returns empty if no path is found.
+  std::vector<Node> getPathFrom(const Node From, const Node To) const;
+
+private:
+  // We use std::set to keep the implementation simple, using an unordered_set
+  // requires the definition of a hasher.
+  using NodeSet = std::set<Node>;
+
+  // Performs a Depth First Search from 'current' node up until 'sentinel' node
+  // is found. 'path' is the recording of the traversed nodes, 'seen' is the
+  // collection of nodes seen so far.
+  bool dfs(const Node Current, const Node Sentinel, std::vector<Node> &Path,
+           NodeSet &Seen) const;
+
+  // We use std::map to keep the implementation simple, using an unordered_map
+  // requires the definition of a hasher.
+  std::map<Node, NodeSet> AdjacencyLists;
+};
+
+// Add register nodes to graph and connect them when they alias. Connection is
+// both ways.
+void setupRegisterAliasing(const llvm::MCRegisterInfo &RegInfo,
+                           Graph &TheGraph);
+
+} // namespace graph
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_OPERANDGRAPH_H