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 38966 : void ControlEquivalence::Run(Node* exit) {
18 38969 : if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
19 38964 : DetermineParticipation(exit);
20 38965 : RunUndirectedDFS(exit);
21 : }
22 38969 : }
23 :
24 :
25 : // static
26 : STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
27 :
28 :
29 0 : void ControlEquivalence::VisitPre(Node* node) {
30 185753 : TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
31 0 : }
32 :
33 :
34 185753 : void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
35 185753 : 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 185755 : BracketListDelete(blist, node, direction);
40 :
41 : // Potentially introduce artificial dependency from start to end.
42 185753 : if (blist.empty()) {
43 : DCHECK_EQ(kInputDirection, direction);
44 38965 : VisitBackedge(node, graph_->end(), kInputDirection);
45 : }
46 :
47 : // Potentially start a new equivalence class [line:37].
48 185753 : BracketListTRACE(blist);
49 : Bracket* recent = &blist.back();
50 185751 : if (recent->recent_size != blist.size()) {
51 117898 : recent->recent_size = blist.size();
52 117898 : recent->recent_class = NewClassNumber();
53 : }
54 :
55 : // Assign equivalence class to node.
56 185751 : SetClass(node, recent->recent_class);
57 185752 : TRACE(" Assigned class number is %zu\n", GetClass(node));
58 185752 : }
59 :
60 :
61 185750 : void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
62 : DFSDirection direction) {
63 185750 : 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 185751 : BracketListDelete(blist, node, direction);
68 :
69 : // Propagate bracket list up the DFS tree [line:13].
70 185749 : if (parent_node != nullptr) {
71 : BracketList& parent_blist = GetBracketList(parent_node);
72 293572 : parent_blist.splice(parent_blist.end(), blist);
73 : }
74 185750 : }
75 :
76 :
77 78432 : void ControlEquivalence::VisitBackedge(Node* from, Node* to,
78 : DFSDirection direction) {
79 78432 : 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 78432 : Bracket bracket = {direction, kInvalidClass, 0, from, to};
84 78432 : GetBracketList(from).push_back(bracket);
85 78432 : }
86 :
87 :
88 38964 : void ControlEquivalence::RunUndirectedDFS(Node* exit) {
89 38964 : ZoneStack<DFSStackEntry> stack(zone_);
90 38965 : DFSPush(stack, exit, nullptr, kInputDirection);
91 : VisitPre(exit);
92 :
93 1293405 : while (!stack.empty()) { // Undirected depth-first backwards traversal.
94 : DFSStackEntry& entry = stack.top();
95 1254440 : Node* node = entry.node;
96 :
97 1254440 : if (entry.direction == kInputDirection) {
98 428121 : if (entry.input != node->input_edges().end()) {
99 242365 : Edge edge = *entry.input;
100 : Node* input = edge.to();
101 : ++(entry.input);
102 242365 : if (NodeProperties::IsControlEdge(edge)) {
103 : // Visit next control input.
104 199184 : if (!Participates(input)) continue;
105 199184 : if (GetData(input)->visited) continue;
106 147078 : if (GetData(input)->on_stack) {
107 : // Found backedge if input is on stack.
108 40335 : if (input != entry.parent_node) {
109 289 : VisitBackedge(node, input, kInputDirection);
110 : }
111 : } else {
112 : // Push input onto stack.
113 106743 : DFSPush(stack, input, node, kInputDirection);
114 : VisitPre(input);
115 : }
116 : }
117 : continue;
118 : }
119 185756 : if (entry.use != node->use_edges().end()) {
120 : // Switch direction to uses.
121 145710 : entry.direction = kUseDirection;
122 145710 : VisitMid(node, kInputDirection);
123 145707 : continue;
124 : }
125 : }
126 :
127 866365 : if (entry.direction == kUseDirection) {
128 826363 : if (entry.use != node->use_edges().end()) {
129 640609 : Edge edge = *entry.use;
130 : Node* use = edge.from();
131 : ++(entry.use);
132 640609 : if (NodeProperties::IsControlEdge(edge)) {
133 : // Visit next control use.
134 342844 : if (!Participates(use)) continue;
135 186255 : if (GetData(use)->visited) continue;
136 185967 : if (GetData(use)->on_stack) {
137 : // Found backedge if use is on stack.
138 145921 : if (use != entry.parent_node) {
139 39178 : VisitBackedge(node, use, kUseDirection);
140 : }
141 : } else {
142 : // Push use onto stack.
143 40045 : DFSPush(stack, use, node, kUseDirection);
144 : VisitPre(use);
145 : }
146 : }
147 : continue;
148 : }
149 185754 : if (entry.input != node->input_edges().end()) {
150 : // Switch direction to inputs.
151 40046 : entry.direction = kInputDirection;
152 40046 : VisitMid(node, kUseDirection);
153 40046 : 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 185710 : DFSPop(stack, node);
161 185751 : VisitPost(node, entry.parent_node, entry.direction);
162 : }
163 38966 : }
164 :
165 238141 : void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
166 : Node* node) {
167 476284 : if (!Participates(node)) {
168 185749 : AllocateData(node);
169 : queue.push(node);
170 : }
171 238145 : }
172 :
173 :
174 38964 : void ControlEquivalence::DetermineParticipation(Node* exit) {
175 38964 : ZoneQueue<Node*> queue(zone_);
176 38966 : DetermineParticipationEnqueue(queue, exit);
177 224717 : while (!queue.empty()) { // Breadth-first backwards traversal.
178 185751 : Node* node = queue.front();
179 : queue.pop();
180 185749 : int max = NodeProperties::PastControlIndex(node);
181 584110 : for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
182 199178 : DetermineParticipationEnqueue(queue, node->InputAt(i));
183 : }
184 : }
185 38966 : }
186 :
187 :
188 185753 : void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
189 : DFSDirection dir) {
190 : DCHECK(Participates(node));
191 : DCHECK(!GetData(node)->visited);
192 185753 : GetData(node)->on_stack = true;
193 : Node::InputEdges::iterator input = node->input_edges().begin();
194 : Node::UseEdges::iterator use = node->use_edges().begin();
195 371508 : stack.push({dir, input, use, from, node});
196 185753 : }
197 :
198 :
199 185751 : void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
200 : DCHECK_EQ(stack.top().node, node);
201 185751 : GetData(node)->on_stack = false;
202 185751 : GetData(node)->visited = true;
203 : stack.pop();
204 185751 : }
205 :
206 :
207 371504 : void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
208 : DFSDirection direction) {
209 : // TODO(mstarzinger): Optimize this to avoid linear search.
210 862959 : for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
211 491457 : if (i->to == to && i->direction != direction) {
212 39465 : TRACE(" BList erased: {%d->%d}\n", i->from->id(), i->to->id());
213 : i = blist.erase(i);
214 : } else {
215 : ++i;
216 : }
217 : }
218 371502 : }
219 :
220 :
221 185751 : void ControlEquivalence::BracketListTRACE(BracketList& blist) {
222 185751 : 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 185751 : }
230 :
231 : #undef TRACE
232 :
233 : } // namespace compiler
234 : } // namespace internal
235 121996 : } // namespace v8
|
