Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_
6 : #define V8_COMPILER_CONTROL_EQUIVALENCE_H_
7 :
8 : #include "src/base/compiler-specific.h"
9 : #include "src/compiler/graph.h"
10 : #include "src/compiler/node.h"
11 : #include "src/globals.h"
12 : #include "src/zone/zone-containers.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : // Determines control dependence equivalence classes for control nodes. Any two
19 : // nodes having the same set of control dependences land in one class. These
20 : // classes can in turn be used to:
21 : // - Build a program structure tree (PST) for controls in the graph.
22 : // - Determine single-entry single-exit (SESE) regions within the graph.
23 : //
24 : // Note that this implementation actually uses cycle equivalence to establish
25 : // class numbers. Any two nodes are cycle equivalent if they occur in the same
26 : // set of cycles. It can be shown that control dependence equivalence reduces
27 : // to undirected cycle equivalence for strongly connected control flow graphs.
28 : //
29 : // The algorithm is based on the paper, "The program structure tree: computing
30 : // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which
31 : // also contains proofs for the aforementioned equivalence. References to line
32 : // numbers in the algorithm from figure 4 have been added [line:x].
33 9 : class V8_EXPORT_PRIVATE ControlEquivalence final
34 : : public NON_EXPORTED_BASE(ZoneObject) {
35 : public:
36 : ControlEquivalence(Zone* zone, Graph* graph)
37 : : zone_(zone),
38 : graph_(graph),
39 : dfs_number_(0),
40 : class_number_(1),
41 2865728 : node_data_(graph->NodeCount(), zone) {}
42 :
43 : // Run the main algorithm starting from the {exit} control node. This causes
44 : // the following iterations over control edges of the graph:
45 : // 1) A breadth-first backwards traversal to determine the set of nodes that
46 : // participate in the next step. Takes O(E) time and O(N) space.
47 : // 2) An undirected depth-first backwards traversal that determines class
48 : // numbers for all participating nodes. Takes O(E) time and O(N) space.
49 : void Run(Node* exit);
50 :
51 : // Retrieves a previously computed class number.
52 : size_t ClassOf(Node* node) {
53 : DCHECK_NE(kInvalidClass, GetClass(node));
54 : return GetClass(node);
55 : }
56 :
57 : private:
58 : static const size_t kInvalidClass = static_cast<size_t>(-1);
59 : enum DFSDirection { kInputDirection, kUseDirection };
60 :
61 : struct Bracket {
62 : DFSDirection direction; // Direction in which this bracket was added.
63 : size_t recent_class; // Cached class when bracket was topmost.
64 : size_t recent_size; // Cached set-size when bracket was topmost.
65 : Node* from; // Node that this bracket originates from.
66 : Node* to; // Node that this bracket points to.
67 : };
68 :
69 : // The set of brackets for each node during the DFS walk.
70 : using BracketList = ZoneLinkedList<Bracket>;
71 :
72 : struct DFSStackEntry {
73 : DFSDirection direction; // Direction currently used in DFS walk.
74 : Node::InputEdges::iterator input; // Iterator used for "input" direction.
75 : Node::UseEdges::iterator use; // Iterator used for "use" direction.
76 : Node* parent_node; // Parent node of entry during DFS walk.
77 : Node* node; // Node that this stack entry belongs to.
78 : };
79 :
80 : // The stack is used during the undirected DFS walk.
81 : using DFSStack = ZoneStack<DFSStackEntry>;
82 :
83 : struct NodeData : ZoneObject {
84 : explicit NodeData(Zone* zone)
85 : : class_number(kInvalidClass),
86 : blist(BracketList(zone)),
87 : visited(false),
88 371502 : on_stack(false) {}
89 :
90 : size_t class_number; // Equivalence class number assigned to node.
91 : BracketList blist; // List of brackets per node.
92 : bool visited : 1; // Indicates node has already been visited.
93 : bool on_stack : 1; // Indicates node is on DFS stack during walk.
94 : };
95 :
96 : // The per-node data computed during the DFS walk.
97 : using Data = ZoneVector<NodeData*>;
98 :
99 : // Called at pre-visit during DFS walk.
100 : void VisitPre(Node* node);
101 :
102 : // Called at mid-visit during DFS walk.
103 : void VisitMid(Node* node, DFSDirection direction);
104 :
105 : // Called at post-visit during DFS walk.
106 : void VisitPost(Node* node, Node* parent_node, DFSDirection direction);
107 :
108 : // Called when hitting a back edge in the DFS walk.
109 : void VisitBackedge(Node* from, Node* to, DFSDirection direction);
110 :
111 : // Performs and undirected DFS walk of the graph. Conceptually all nodes are
112 : // expanded, splitting "input" and "use" out into separate nodes. During the
113 : // traversal, edges towards the representative nodes are preferred.
114 : //
115 : // \ / - Pre-visit: When N1 is visited in direction D the preferred
116 : // x N1 edge towards N is taken next, calling VisitPre(N).
117 : // | - Mid-visit: After all edges out of N2 in direction D have
118 : // | N been visited, we switch the direction and start considering
119 : // | edges out of N1 now, and we call VisitMid(N).
120 : // x N2 - Post-visit: After all edges out of N1 in direction opposite
121 : // / \ to D have been visited, we pop N and call VisitPost(N).
122 : //
123 : // This will yield a true spanning tree (without cross or forward edges) and
124 : // also discover proper back edges in both directions.
125 : void RunUndirectedDFS(Node* exit);
126 :
127 : void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node);
128 : void DetermineParticipation(Node* exit);
129 :
130 : private:
131 3192289 : NodeData* GetData(Node* node) {
132 3192289 : size_t const index = node->id();
133 3192289 : if (index >= node_data_.size()) node_data_.resize(index + 1);
134 3192289 : return node_data_[index];
135 : }
136 185749 : void AllocateData(Node* node) {
137 185749 : size_t const index = node->id();
138 185749 : if (index >= node_data_.size()) node_data_.resize(index + 1);
139 557251 : node_data_[index] = new (zone_) NodeData(zone_);
140 185751 : }
141 :
142 117898 : int NewClassNumber() { return class_number_++; }
143 : int NewDFSNumber() { return dfs_number_++; }
144 :
145 819133 : bool Participates(Node* node) { return GetData(node) != nullptr; }
146 :
147 : // Accessors for the equivalence class stored within the per-node data.
148 315113 : size_t GetClass(Node* node) { return GetData(node)->class_number; }
149 : void SetClass(Node* node, size_t number) {
150 : DCHECK(Participates(node));
151 185751 : GetData(node)->class_number = number;
152 : }
153 :
154 : // Accessors for the bracket list stored within the per-node data.
155 : BracketList& GetBracketList(Node* node) {
156 : DCHECK(Participates(node));
157 596721 : return GetData(node)->blist;
158 : }
159 : void SetBracketList(Node* node, BracketList& list) {
160 : DCHECK(Participates(node));
161 : GetData(node)->blist = list;
162 : }
163 :
164 : // Mutates the DFS stack by pushing an entry.
165 : void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir);
166 :
167 : // Mutates the DFS stack by popping an entry.
168 : void DFSPop(DFSStack& stack, Node* node);
169 :
170 : void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction);
171 : void BracketListTRACE(BracketList& blist);
172 :
173 : Zone* const zone_;
174 : Graph* const graph_;
175 : int dfs_number_; // Generates new DFS pre-order numbers on demand.
176 : int class_number_; // Generates new equivalence class numbers on demand.
177 : Data node_data_; // Per-node data stored as a side-table.
178 : };
179 :
180 : } // namespace compiler
181 : } // namespace internal
182 : } // namespace v8
183 :
184 : #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_
|
