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 38987 : void ControlEquivalence::Run(Node* exit) {
18 38989 : if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
19 38985 : DetermineParticipation(exit);
20 38986 : RunUndirectedDFS(exit);
21 : }
22 38988 : }
23 :
24 :
25 : // static
26 : STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27 :
28 :
29 0 : void ControlEquivalence::VisitPre(Node* node) {
30 185843 : TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31 0 : }
32 :
33 :
34 185842 : void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
35 185842 : TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
36 : BracketList& blist = GetBracketList(node);
37 :
38 : // Remove brackets pointing to this node [line:19].
39 185841 : BracketListDelete(blist, node, direction);
40 :
41 : // Potentially introduce artificial dependency from start to end.
42 185841 : if (blist.empty()) {
43 : DCHECK_EQ(kInputDirection, direction);
44 38985 : VisitBackedge(node, graph_->end(), kInputDirection);
45 : }
46 :
47 : // Potentially start a new equivalence class [line:37].
48 185842 : BracketListTRACE(blist);
49 : Bracket* recent = &blist.back();
50 185841 : if (recent->recent_size != blist.size()) {
51 117956 : recent->recent_size = blist.size();
52 117956 : recent->recent_class = NewClassNumber();
53 : }
54 :
55 : // Assign equivalence class to node.
56 185841 : SetClass(node, recent->recent_class);
57 185840 : TRACE(" Assigned class number is %zu\n", GetClass(node));
58 185840 : }
59 :
60 :
61 185839 : void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
62 : DFSDirection direction) {
63 185839 : TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
64 : BracketList& blist = GetBracketList(node);
65 :
66 : // Remove brackets pointing to this node [line:19].
67 185839 : BracketListDelete(blist, node, direction);
68 :
69 : // Propagate bracket list up the DFS tree [line:13].
70 185842 : if (parent_node != nullptr) {
71 : BracketList& parent_blist = GetBracketList(parent_node);
72 293712 : parent_blist.splice(parent_blist.end(), blist);
73 : }
74 185840 : }
75 :
76 :
77 78472 : void ControlEquivalence::VisitBackedge(Node* from, Node* to,
78 : DFSDirection direction) {
79 78472 : 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 78472 : Bracket bracket = {direction, kInvalidClass, 0, from, to};
84 78471 : GetBracketList(from).push_back(bracket);
85 78472 : }
86 :
87 :
88 38985 : void ControlEquivalence::RunUndirectedDFS(Node* exit) {
89 38985 : ZoneStack<DFSStackEntry> stack(zone_);
90 38986 : DFSPush(stack, exit, nullptr, kInputDirection);
91 : VisitPre(exit);
92 :
93 1294800 : while (!stack.empty()) { // Undirected depth-first backwards traversal.
94 : DFSStackEntry& entry = stack.top();
95 1255814 : Node* node = entry.node;
96 :
97 1255814 : if (entry.direction == kInputDirection) {
98 428329 : if (entry.input != node->input_edges().end()) {
99 242488 : Edge edge = *entry.input;
100 : Node* input = edge.to();
101 : ++(entry.input);
102 242488 : if (NodeProperties::IsControlEdge(edge)) {
103 : // Visit next control input.
104 199284 : if (!Participates(input)) continue;
105 199285 : if (GetData(input)->visited) continue;
106 147145 : if (GetData(input)->on_stack) {
107 : // Found backedge if input is on stack.
108 40355 : if (input != entry.parent_node) {
109 289 : VisitBackedge(node, input, kInputDirection);
110 : }
111 : } else {
112 : // Push input onto stack.
113 106791 : DFSPush(stack, input, node, kInputDirection);
114 : VisitPre(input);
115 : }
116 : }
117 : continue;
118 : }
119 185841 : if (entry.use != node->use_edges().end()) {
120 : // Switch direction to uses.
121 145777 : entry.direction = kUseDirection;
122 145777 : VisitMid(node, kInputDirection);
123 145775 : continue;
124 : }
125 : }
126 :
127 867549 : if (entry.direction == kUseDirection) {
128 827511 : if (entry.use != node->use_edges().end()) {
129 641670 : Edge edge = *entry.use;
130 : Node* use = edge.from();
131 : ++(entry.use);
132 641670 : if (NodeProperties::IsControlEdge(edge)) {
133 : // Visit next control use.
134 342985 : if (!Participates(use)) continue;
135 186341 : if (GetData(use)->visited) continue;
136 186053 : if (GetData(use)->on_stack) {
137 : // Found backedge if use is on stack.
138 145988 : if (use != entry.parent_node) {
139 39198 : VisitBackedge(node, use, kUseDirection);
140 : }
141 : } else {
142 : // Push use onto stack.
143 40066 : DFSPush(stack, use, node, kUseDirection);
144 : VisitPre(use);
145 : }
146 : }
147 : continue;
148 : }
149 185841 : if (entry.input != node->input_edges().end()) {
150 : // Switch direction to inputs.
151 40065 : entry.direction = kInputDirection;
152 40065 : VisitMid(node, kUseDirection);
153 40066 : 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 185814 : DFSPop(stack, node);
161 185838 : VisitPost(node, entry.parent_node, entry.direction);
162 : }
163 38986 : }
164 :
165 238264 : void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
166 : Node* node) {
167 476529 : if (!Participates(node)) {
168 185838 : AllocateData(node);
169 : queue.push(node);
170 : }
171 238265 : }
172 :
173 :
174 38985 : void ControlEquivalence::DetermineParticipation(Node* exit) {
175 38985 : ZoneQueue<Node*> queue(zone_);
176 38985 : DetermineParticipationEnqueue(queue, exit);
177 224824 : while (!queue.empty()) { // Breadth-first backwards traversal.
178 185838 : Node* node = queue.front();
179 : queue.pop();
180 185837 : int max = NodeProperties::PastControlIndex(node);
181 584397 : for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
182 199280 : DetermineParticipationEnqueue(queue, node->InputAt(i));
183 : }
184 : }
185 38986 : }
186 :
187 :
188 185841 : void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
189 : DFSDirection dir) {
190 : DCHECK(Participates(node));
191 : DCHECK(!GetData(node)->visited);
192 185841 : GetData(node)->on_stack = true;
193 : Node::InputEdges::iterator input = node->input_edges().begin();
194 : Node::UseEdges::iterator use = node->use_edges().begin();
195 371685 : stack.push({dir, input, use, from, node});
196 185843 : }
197 :
198 :
199 185840 : void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
200 : DCHECK_EQ(stack.top().node, node);
201 185840 : GetData(node)->on_stack = false;
202 185838 : GetData(node)->visited = true;
203 : stack.pop();
204 185838 : }
205 :
206 :
207 371678 : void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
208 : DFSDirection direction) {
209 : // TODO(mstarzinger): Optimize this to avoid linear search.
210 863371 : for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
211 491694 : if (i->to == to && i->direction != direction) {
212 39486 : TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
213 : i = blist.erase(i);
214 : } else {
215 : ++i;
216 : }
217 : }
218 371677 : }
219 :
220 :
221 185842 : void ControlEquivalence::BracketListTRACE(BracketList& blist) {
222 185842 : 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 185842 : }
230 :
231 : #undef TRACE
232 :
233 : } // namespace compiler
234 : } // namespace internal
235 122004 : } // namespace v8
|
