Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(358)

Side by Side Diff: src/compiler/control-equivalence.cc

Issue 1056093005: [turbofan] Split ControlEquivalence implementation and add trace flag. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/control-equivalence.h ('k') | src/flag-definitions.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2015 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 #include "src/compiler/control-equivalence.h"
6 #include "src/compiler/node-properties.h"
7
8 #define TRACE(...) \
9 do { \
10 if (FLAG_trace_turbo_ceq) PrintF(__VA_ARGS__); \
11 } while (false)
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
17 void ControlEquivalence::Run(Node* exit) {
18 if (GetClass(exit) == kInvalidClass) {
19 DetermineParticipation(exit);
20 RunUndirectedDFS(exit);
21 }
22 }
23
24
25 // static
26 STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27
28
29 void ControlEquivalence::VisitPre(Node* node) {
30 TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31
32 // Dispense a new pre-order number.
33 SetNumber(node, NewDFSNumber());
34 TRACE(" Assigned DFS number is %zu\n", GetNumber(node));
35 }
36
37
38 void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
39 TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
40 BracketList& blist = GetBracketList(node);
41
42 // Remove brackets pointing to this node [line:19].
43 BracketListDelete(blist, node, direction);
44
45 // Potentially introduce artificial dependency from start to end.
46 if (blist.empty()) {
47 DCHECK_EQ(kInputDirection, direction);
48 VisitBackedge(node, graph_->end(), kInputDirection);
49 }
50
51 // Potentially start a new equivalence class [line:37].
52 BracketListTRACE(blist);
53 Bracket* recent = &blist.back();
54 if (recent->recent_size != blist.size()) {
55 recent->recent_size = blist.size();
56 recent->recent_class = NewClassNumber();
57 }
58
59 // Assign equivalence class to node.
60 SetClass(node, recent->recent_class);
61 TRACE(" Assigned class number is %zu\n", GetClass(node));
62 }
63
64
65 void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
66 DFSDirection direction) {
67 TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
68 BracketList& blist = GetBracketList(node);
69
70 // Remove brackets pointing to this node [line:19].
71 BracketListDelete(blist, node, direction);
72
73 // Propagate bracket list up the DFS tree [line:13].
74 if (parent_node != NULL) {
75 BracketList& parent_blist = GetBracketList(parent_node);
76 parent_blist.splice(parent_blist.end(), blist);
77 }
78 }
79
80
81 void ControlEquivalence::VisitBackedge(Node* from, Node* to,
82 DFSDirection direction) {
83 TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
84 from->op()->mnemonic(), to->id(), to->op()->mnemonic());
85
86 // Push backedge onto the bracket list [line:25].
87 Bracket bracket = {direction, kInvalidClass, 0, from, to};
88 GetBracketList(from).push_back(bracket);
89 }
90
91
92 void ControlEquivalence::RunUndirectedDFS(Node* exit) {
93 ZoneStack<DFSStackEntry> stack(zone_);
94 DFSPush(stack, exit, NULL, kInputDirection);
95 VisitPre(exit);
96
97 while (!stack.empty()) { // Undirected depth-first backwards traversal.
98 DFSStackEntry& entry = stack.top();
99 Node* node = entry.node;
100
101 if (entry.direction == kInputDirection) {
102 if (entry.input != node->input_edges().end()) {
103 Edge edge = *entry.input;
104 Node* input = edge.to();
105 ++(entry.input);
106 if (NodeProperties::IsControlEdge(edge)) {
107 // Visit next control input.
108 if (!GetData(input)->participates) continue;
109 if (GetData(input)->visited) continue;
110 if (GetData(input)->on_stack) {
111 // Found backedge if input is on stack.
112 if (input != entry.parent_node) {
113 VisitBackedge(node, input, kInputDirection);
114 }
115 } else {
116 // Push input onto stack.
117 DFSPush(stack, input, node, kInputDirection);
118 VisitPre(input);
119 }
120 }
121 continue;
122 }
123 if (entry.use != node->use_edges().end()) {
124 // Switch direction to uses.
125 entry.direction = kUseDirection;
126 VisitMid(node, kInputDirection);
127 continue;
128 }
129 }
130
131 if (entry.direction == kUseDirection) {
132 if (entry.use != node->use_edges().end()) {
133 Edge edge = *entry.use;
134 Node* use = edge.from();
135 ++(entry.use);
136 if (NodeProperties::IsControlEdge(edge)) {
137 // Visit next control use.
138 if (!GetData(use)->participates) continue;
139 if (GetData(use)->visited) continue;
140 if (GetData(use)->on_stack) {
141 // Found backedge if use is on stack.
142 if (use != entry.parent_node) {
143 VisitBackedge(node, use, kUseDirection);
144 }
145 } else {
146 // Push use onto stack.
147 DFSPush(stack, use, node, kUseDirection);
148 VisitPre(use);
149 }
150 }
151 continue;
152 }
153 if (entry.input != node->input_edges().end()) {
154 // Switch direction to inputs.
155 entry.direction = kInputDirection;
156 VisitMid(node, kUseDirection);
157 continue;
158 }
159 }
160
161 // Pop node from stack when done with all inputs and uses.
162 DCHECK(entry.input == node->input_edges().end());
163 DCHECK(entry.use == node->use_edges().end());
164 DFSPop(stack, node);
165 VisitPost(node, entry.parent_node, entry.direction);
166 }
167 }
168
169 void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
170 Node* node) {
171 if (!GetData(node)->participates) {
172 GetData(node)->participates = true;
173 queue.push(node);
174 }
175 }
176
177
178 void ControlEquivalence::DetermineParticipation(Node* exit) {
179 ZoneQueue<Node*> queue(zone_);
180 DetermineParticipationEnqueue(queue, exit);
181 while (!queue.empty()) { // Breadth-first backwards traversal.
182 Node* node = queue.front();
183 queue.pop();
184 int max = NodeProperties::PastControlIndex(node);
185 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
186 DetermineParticipationEnqueue(queue, node->InputAt(i));
187 }
188 }
189 }
190
191
192 void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
193 DFSDirection dir) {
194 DCHECK(GetData(node)->participates);
195 DCHECK(!GetData(node)->visited);
196 GetData(node)->on_stack = true;
197 Node::InputEdges::iterator input = node->input_edges().begin();
198 Node::UseEdges::iterator use = node->use_edges().begin();
199 stack.push({dir, input, use, from, node});
200 }
201
202
203 void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
204 DCHECK_EQ(stack.top().node, node);
205 GetData(node)->on_stack = false;
206 GetData(node)->visited = true;
207 stack.pop();
208 }
209
210
211 void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
212 DFSDirection direction) {
213 // TODO(mstarzinger): Optimize this to avoid linear search.
214 for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
215 if (i->to == to && i->direction != direction) {
216 TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
217 i = blist.erase(i);
218 } else {
219 ++i;
220 }
221 }
222 }
223
224
225 void ControlEquivalence::BracketListTRACE(BracketList& blist) {
226 if (FLAG_trace_turbo_ceq) {
227 TRACE(" BList: ");
228 for (Bracket bracket : blist) {
229 TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
230 }
231 TRACE("\n");
232 }
233 }
234
235 } // namespace compiler
236 } // namespace internal
237 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/control-equivalence.h ('k') | src/flag-definitions.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698