1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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
|
