Line data Source code
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 64448 : void ControlEquivalence::Run(Node* exit) {
18 64451 : if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
19 64446 : DetermineParticipation(exit);
20 64447 : RunUndirectedDFS(exit);
21 : }
22 64450 : }
23 :
24 :
25 : // static
26 : STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27 :
28 :
29 317851 : void ControlEquivalence::VisitPre(Node* node) {
30 317851 : TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31 317851 : }
32 :
33 :
34 317851 : void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
35 317851 : TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
36 317851 : BracketList& blist = GetBracketList(node);
37 :
38 : // Remove brackets pointing to this node [line:19].
39 317851 : BracketListDelete(blist, node, direction);
40 :
41 : // Potentially introduce artificial dependency from start to end.
42 317850 : if (blist.empty()) {
43 : DCHECK_EQ(kInputDirection, direction);
44 64533 : VisitBackedge(node, graph_->end(), kInputDirection);
45 : }
46 :
47 : // Potentially start a new equivalence class [line:37].
48 317851 : BracketListTRACE(blist);
49 : Bracket* recent = &blist.back();
50 635702 : if (recent->recent_size != blist.size()) {
51 196265 : recent->recent_size = blist.size();
52 196265 : recent->recent_class = NewClassNumber();
53 : }
54 :
55 : // Assign equivalence class to node.
56 317851 : SetClass(node, recent->recent_class);
57 317851 : TRACE(" Assigned class number is %zu\n", GetClass(node));
58 317851 : }
59 :
60 :
61 317851 : void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
62 : DFSDirection direction) {
63 317851 : TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
64 317851 : BracketList& blist = GetBracketList(node);
65 :
66 : // Remove brackets pointing to this node [line:19].
67 317851 : BracketListDelete(blist, node, direction);
68 :
69 : // Propagate bracket list up the DFS tree [line:13].
70 317851 : if (parent_node != nullptr) {
71 : BracketList& parent_blist = GetBracketList(parent_node);
72 506806 : parent_blist.splice(parent_blist.end(), blist);
73 : }
74 317850 : }
75 :
76 :
77 130454 : void ControlEquivalence::VisitBackedge(Node* from, Node* to,
78 : DFSDirection direction) {
79 130454 : TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
80 : from->op()->mnemonic(), to->id(), to->op()->mnemonic());
81 :
82 : // Push backedge onto the bracket list [line:25].
83 130454 : Bracket bracket = {direction, kInvalidClass, 0, from, to};
84 130454 : GetBracketList(from).push_back(bracket);
85 130455 : }
86 :
87 :
88 64446 : void ControlEquivalence::RunUndirectedDFS(Node* exit) {
89 64446 : ZoneStack<DFSStackEntry> stack(zone_);
90 64446 : DFSPush(stack, exit, nullptr, kInputDirection);
91 64447 : VisitPre(exit);
92 :
93 2153424 : while (!stack.empty()) { // Undirected depth-first backwards traversal.
94 : DFSStackEntry& entry = stack.top();
95 2024528 : Node* node = entry.node;
96 :
97 2024528 : if (entry.direction == kInputDirection) {
98 738257 : if (entry.input != node->input_edges().end()) {
99 420406 : Edge edge = *entry.input;
100 : Node* input = edge.to();
101 : ++(entry.input);
102 420406 : if (NodeProperties::IsControlEdge(edge)) {
103 : // Visit next control input.
104 336057 : if (!Participates(input)) continue;
105 336057 : if (GetData(input)->visited) continue;
106 254031 : if (GetData(input)->on_stack) {
107 : // Found backedge if input is on stack.
108 67292 : if (input != entry.parent_node) {
109 627 : VisitBackedge(node, input, kInputDirection);
110 : }
111 : } else {
112 : // Push input onto stack.
113 186739 : DFSPush(stack, input, node, kInputDirection);
114 186739 : VisitPre(input);
115 : }
116 : }
117 : continue;
118 : }
119 317851 : if (entry.use != node->use_edges().end()) {
120 : // Switch direction to uses.
121 251186 : entry.direction = kUseDirection;
122 251186 : VisitMid(node, kInputDirection);
123 251186 : continue;
124 : }
125 : }
126 :
127 1352936 : if (entry.direction == kUseDirection) {
128 1286271 : if (entry.use != node->use_edges().end()) {
129 968420 : Edge edge = *entry.use;
130 : Node* use = edge.from();
131 : ++(entry.use);
132 968420 : if (NodeProperties::IsControlEdge(edge)) {
133 : // Visit next control use.
134 631461 : if (!Participates(use)) continue;
135 319324 : if (GetData(use)->visited) continue;
136 318698 : if (GetData(use)->on_stack) {
137 : // Found backedge if use is on stack.
138 252033 : if (use != entry.parent_node) {
139 65294 : VisitBackedge(node, use, kUseDirection);
140 : }
141 : } else {
142 : // Push use onto stack.
143 66665 : DFSPush(stack, use, node, kUseDirection);
144 66665 : VisitPre(use);
145 : }
146 : }
147 : continue;
148 : }
149 317851 : if (entry.input != node->input_edges().end()) {
150 : // Switch direction to inputs.
151 66665 : entry.direction = kInputDirection;
152 66665 : VisitMid(node, kUseDirection);
153 66665 : continue;
154 : }
155 : }
156 :
157 : // Pop node from stack when done with all inputs and uses.
158 : DCHECK(entry.input == node->input_edges().end());
159 : DCHECK(entry.use == node->use_edges().end());
160 317851 : DFSPop(stack, node);
161 317851 : VisitPost(node, entry.parent_node, entry.direction);
162 : }
163 64447 : }
164 :
165 400504 : void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
166 : Node* node) {
167 801007 : if (!Participates(node)) {
168 317851 : AllocateData(node);
169 : queue.push(node);
170 : }
171 400503 : }
172 :
173 :
174 64446 : void ControlEquivalence::DetermineParticipation(Node* exit) {
175 64446 : ZoneQueue<Node*> queue(zone_);
176 64447 : DetermineParticipationEnqueue(queue, exit);
177 446743 : while (!queue.empty()) { // Breadth-first backwards traversal.
178 317850 : Node* node = queue.front();
179 : queue.pop();
180 317850 : int max = NodeProperties::PastControlIndex(node);
181 653908 : for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
182 336057 : DetermineParticipationEnqueue(queue, node->InputAt(i));
183 : }
184 : }
185 64447 : }
186 :
187 :
188 317850 : void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
189 : DFSDirection dir) {
190 : DCHECK(Participates(node));
191 : DCHECK(!GetData(node)->visited);
192 317850 : GetData(node)->on_stack = true;
193 : Node::InputEdges::iterator input = node->input_edges().begin();
194 : Node::UseEdges::iterator use = node->use_edges().begin();
195 635701 : stack.push({dir, input, use, from, node});
196 317851 : }
197 :
198 :
199 317851 : void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
200 : DCHECK_EQ(stack.top().node, node);
201 317851 : GetData(node)->on_stack = false;
202 317851 : GetData(node)->visited = true;
203 : stack.pop();
204 317851 : }
205 :
206 :
207 635701 : void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
208 : DFSDirection direction) {
209 : // TODO(mstarzinger): Optimize this to avoid linear search.
210 2110199 : for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
211 838797 : if (i->to == to && i->direction != direction) {
212 65920 : TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
213 : i = blist.erase(i);
214 : } else {
215 : ++i;
216 : }
217 : }
218 635701 : }
219 :
220 :
221 317851 : void ControlEquivalence::BracketListTRACE(BracketList& blist) {
222 317851 : if (FLAG_trace_turbo_ceq) {
223 0 : TRACE(" BList: ");
224 0 : for (Bracket bracket : blist) {
225 0 : TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
226 : }
227 0 : TRACE("\n");
228 : }
229 317851 : }
230 :
231 : #undef TRACE
232 :
233 : } // namespace compiler
234 : } // namespace internal
235 183867 : } // namespace v8
|
