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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
#define V8_COMPILER_CONTROL_EQUIVALENCE_H_
#include "src/base/compiler-specific.h"
#include "src/compiler/graph.h"
#include "src/compiler/node.h"
#include "src/globals.h"
#include "src/zone/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
// Determines control dependence equivalence classes for control nodes. Any two
// nodes having the same set of control dependences land in one class. These
// classes can in turn be used to:
// - Build a program structure tree (PST) for controls in the graph.
// - Determine single-entry single-exit (SESE) regions within the graph.
//
// Note that this implementation actually uses cycle equivalence to establish
// class numbers. Any two nodes are cycle equivalent if they occur in the same
// set of cycles. It can be shown that control dependence equivalence reduces
// to undirected cycle equivalence for strongly connected control flow graphs.
//
// The algorithm is based on the paper, "The program structure tree: computing
// control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which
// also contains proofs for the aforementioned equivalence. References to line
// numbers in the algorithm from figure 4 have been added [line:x].
class V8_EXPORT_PRIVATE ControlEquivalence final
: public NON_EXPORTED_BASE(ZoneObject) {
public:
ControlEquivalence(Zone* zone, Graph* graph)
: zone_(zone),
graph_(graph),
dfs_number_(0),
class_number_(1),
node_data_(graph->NodeCount(), EmptyData(), zone) {}
// Run the main algorithm starting from the {exit} control node. This causes
// the following iterations over control edges of the graph:
// 1) A breadth-first backwards traversal to determine the set of nodes that
// participate in the next step. Takes O(E) time and O(N) space.
// 2) An undirected depth-first backwards traversal that determines class
// numbers for all participating nodes. Takes O(E) time and O(N) space.
void Run(Node* exit);
// Retrieves a previously computed class number.
size_t ClassOf(Node* node) {
DCHECK_NE(kInvalidClass, GetClass(node));
return GetClass(node);
}
private:
static const size_t kInvalidClass = static_cast<size_t>(-1);
typedef enum { kInputDirection, kUseDirection } DFSDirection;
struct Bracket {
DFSDirection direction; // Direction in which this bracket was added.
size_t recent_class; // Cached class when bracket was topmost.
size_t recent_size; // Cached set-size when bracket was topmost.
Node* from; // Node that this bracket originates from.
Node* to; // Node that this bracket points to.
};
// The set of brackets for each node during the DFS walk.
typedef ZoneLinkedList<Bracket> BracketList;
struct DFSStackEntry {
DFSDirection direction; // Direction currently used in DFS walk.
Node::InputEdges::iterator input; // Iterator used for "input" direction.
Node::UseEdges::iterator use; // Iterator used for "use" direction.
Node* parent_node; // Parent node of entry during DFS walk.
Node* node; // Node that this stack entry belongs to.
};
// The stack is used during the undirected DFS walk.
typedef ZoneStack<DFSStackEntry> DFSStack;
struct NodeData {
size_t class_number; // Equivalence class number assigned to node.
size_t dfs_number; // Pre-order DFS number assigned to node.
bool visited; // Indicates node has already been visited.
bool on_stack; // Indicates node is on DFS stack during walk.
bool participates; // Indicates node participates in DFS walk.
BracketList blist; // List of brackets per node.
};
// The per-node data computed during the DFS walk.
typedef ZoneVector<NodeData> Data;
// Called at pre-visit during DFS walk.
void VisitPre(Node* node);
// Called at mid-visit during DFS walk.
void VisitMid(Node* node, DFSDirection direction);
// Called at post-visit during DFS walk.
void VisitPost(Node* node, Node* parent_node, DFSDirection direction);
// Called when hitting a back edge in the DFS walk.
void VisitBackedge(Node* from, Node* to, DFSDirection direction);
// Performs and undirected DFS walk of the graph. Conceptually all nodes are
// expanded, splitting "input" and "use" out into separate nodes. During the
// traversal, edges towards the representative nodes are preferred.
//
// \ / - Pre-visit: When N1 is visited in direction D the preferred
// x N1 edge towards N is taken next, calling VisitPre(N).
// | - Mid-visit: After all edges out of N2 in direction D have
// | N been visited, we switch the direction and start considering
// | edges out of N1 now, and we call VisitMid(N).
// x N2 - Post-visit: After all edges out of N1 in direction opposite
// / \ to D have been visited, we pop N and call VisitPost(N).
//
// This will yield a true spanning tree (without cross or forward edges) and
// also discover proper back edges in both directions.
void RunUndirectedDFS(Node* exit);
void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node);
void DetermineParticipation(Node* exit);
private:
NodeData* GetData(Node* node) { return &node_data_[node->id()]; }
int NewClassNumber() { return class_number_++; }
int NewDFSNumber() { return dfs_number_++; }
// Template used to initialize per-node data.
NodeData EmptyData() {
return {kInvalidClass, 0, false, false, false, BracketList(zone_)};
}
// Accessors for the DFS number stored within the per-node data.
size_t GetNumber(Node* node) { return GetData(node)->dfs_number; }
void SetNumber(Node* node, size_t number) {
GetData(node)->dfs_number = number;
}
// Accessors for the equivalence class stored within the per-node data.
size_t GetClass(Node* node) { return GetData(node)->class_number; }
void SetClass(Node* node, size_t number) {
GetData(node)->class_number = number;
}
// Accessors for the bracket list stored within the per-node data.
BracketList& GetBracketList(Node* node) { return GetData(node)->blist; }
void SetBracketList(Node* node, BracketList& list) {
GetData(node)->blist = list;
}
// Mutates the DFS stack by pushing an entry.
void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir);
// Mutates the DFS stack by popping an entry.
void DFSPop(DFSStack& stack, Node* node);
void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction);
void BracketListTRACE(BracketList& blist);
Zone* const zone_;
Graph* const graph_;
int dfs_number_; // Generates new DFS pre-order numbers on demand.
int class_number_; // Generates new equivalence class numbers on demand.
Data node_data_; // Per-node data stored as a side-table.
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_
|
