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 : #include "src/compiler/loop-analysis.h"
6 :
7 : #include "src/compiler/graph.h"
8 : #include "src/compiler/node-marker.h"
9 : #include "src/compiler/node-properties.h"
10 : #include "src/compiler/node.h"
11 : #include "src/zone/zone.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 : #define OFFSET(x) ((x)&0x1f)
18 : #define BIT(x) (1u << OFFSET(x))
19 : #define INDEX(x) ((x) >> 5)
20 :
21 : // Temporary information for each node during marking.
22 : struct NodeInfo {
23 : Node* node;
24 : NodeInfo* next; // link in chaining loop members
25 : };
26 :
27 :
28 : // Temporary loop info needed during traversal and building the loop tree.
29 : struct TempLoopInfo {
30 : Node* header;
31 : NodeInfo* header_list;
32 : NodeInfo* exit_list;
33 : NodeInfo* body_list;
34 : LoopTree::Loop* loop;
35 : };
36 :
37 :
38 : // Encapsulation of the loop finding algorithm.
39 : // -----------------------------------------------------------------------------
40 : // Conceptually, the contents of a loop are those nodes that are "between" the
41 : // loop header and the backedges of the loop. Graphs in the soup of nodes can
42 : // form improper cycles, so standard loop finding algorithms that work on CFGs
43 : // aren't sufficient. However, in valid TurboFan graphs, all cycles involve
44 : // either a {Loop} node or a phi. The {Loop} node itself and its accompanying
45 : // phis are treated together as a set referred to here as the loop header.
46 : // This loop finding algorithm works by traversing the graph in two directions,
47 : // first from nodes to their inputs, starting at {end}, then in the reverse
48 : // direction, from nodes to their uses, starting at loop headers.
49 : // 1 bit per loop per node per direction are required during the marking phase.
50 : // To handle nested loops correctly, the algorithm must filter some reachability
51 : // marks on edges into/out-of the loop header nodes.
52 : class LoopFinderImpl {
53 : public:
54 2538719 : LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone)
55 : : zone_(zone),
56 : end_(graph->end()),
57 : queue_(zone),
58 : queued_(graph, 2),
59 : info_(graph->NodeCount(), {nullptr, nullptr}, zone),
60 : loops_(zone),
61 : loop_num_(graph->NodeCount(), -1, zone),
62 : loop_tree_(loop_tree),
63 : loops_found_(0),
64 : width_(0),
65 : backward_(nullptr),
66 1904040 : forward_(nullptr) {}
67 :
68 634679 : void Run() {
69 634679 : PropagateBackward();
70 634678 : PropagateForward();
71 634680 : FinishLoopTree();
72 634678 : }
73 :
74 0 : void Print() {
75 : // Print out the results.
76 0 : for (NodeInfo& ni : info_) {
77 0 : if (ni.node == nullptr) continue;
78 0 : for (int i = 1; i <= loops_found_; i++) {
79 0 : int index = ni.node->id() * width_ + INDEX(i);
80 0 : bool marked_forward = forward_[index] & BIT(i);
81 0 : bool marked_backward = backward_[index] & BIT(i);
82 0 : if (marked_forward && marked_backward) {
83 0 : PrintF("X");
84 0 : } else if (marked_forward) {
85 0 : PrintF(">");
86 0 : } else if (marked_backward) {
87 0 : PrintF("<");
88 : } else {
89 0 : PrintF(" ");
90 : }
91 : }
92 0 : PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
93 : }
94 :
95 : int i = 0;
96 0 : for (TempLoopInfo& li : loops_) {
97 0 : PrintF("Loop %d headed at #%d\n", i, li.header->id());
98 0 : i++;
99 : }
100 :
101 0 : for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
102 0 : PrintLoop(loop);
103 : }
104 0 : }
105 :
106 : private:
107 : Zone* zone_;
108 : Node* end_;
109 : NodeDeque queue_;
110 : NodeMarker<bool> queued_;
111 : ZoneVector<NodeInfo> info_;
112 : ZoneVector<TempLoopInfo> loops_;
113 : ZoneVector<int> loop_num_;
114 : LoopTree* loop_tree_;
115 : int loops_found_;
116 : int width_;
117 : uint32_t* backward_;
118 : uint32_t* forward_;
119 :
120 : int num_nodes() {
121 2538900 : return static_cast<int>(loop_tree_->node_to_loop_num_.size());
122 : }
123 :
124 : // Tb = Tb | (Fb - loop_filter)
125 324662616 : bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
126 108221102 : if (from == to) return false;
127 216441514 : uint32_t* fp = &backward_[from->id() * width_];
128 108220757 : uint32_t* tp = &backward_[to->id() * width_];
129 : bool change = false;
130 221964242 : for (int i = 0; i < width_; i++) {
131 113743485 : uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
132 113743485 : uint32_t prev = tp[i];
133 113743485 : uint32_t next = prev | (fp[i] & mask);
134 113743485 : tp[i] = next;
135 113743485 : if (!change && (prev != next)) change = true;
136 : }
137 : return change;
138 : }
139 :
140 : // Tb = Tb | B
141 4588036 : bool SetBackwardMark(Node* to, int loop_num) {
142 4588036 : uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
143 4588036 : uint32_t prev = tp[0];
144 4588036 : uint32_t next = prev | BIT(loop_num);
145 4588036 : tp[0] = next;
146 : return next != prev;
147 : }
148 :
149 : // Tf = Tf | B
150 : bool SetForwardMark(Node* to, int loop_num) {
151 632174 : uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
152 632174 : uint32_t prev = tp[0];
153 632174 : uint32_t next = prev | BIT(loop_num);
154 632174 : tp[0] = next;
155 : return next != prev;
156 : }
157 :
158 : // Tf = Tf | (Ff & Tb)
159 42828976 : bool PropagateForwardMarks(Node* from, Node* to) {
160 14276562 : if (from == to) return false;
161 : bool change = false;
162 14276207 : int findex = from->id() * width_;
163 14276207 : int tindex = to->id() * width_;
164 28655534 : for (int i = 0; i < width_; i++) {
165 14379327 : uint32_t marks = backward_[tindex + i] & forward_[findex + i];
166 14379327 : uint32_t prev = forward_[tindex + i];
167 14379327 : uint32_t next = prev | marks;
168 14379327 : forward_[tindex + i] = next;
169 14379327 : if (!change && (prev != next)) change = true;
170 : }
171 : return change;
172 : }
173 :
174 5525644 : bool IsInLoop(Node* node, int loop_num) {
175 5525644 : int offset = node->id() * width_ + INDEX(loop_num);
176 5525644 : return backward_[offset] & forward_[offset] & BIT(loop_num);
177 : }
178 :
179 : // Propagate marks backward from loop headers.
180 3567466 : void PropagateBackward() {
181 634679 : ResizeBackwardMarks();
182 634680 : SetBackwardMark(end_, 0);
183 634680 : Queue(end_);
184 :
185 40362589 : while (!queue_.empty()) {
186 78186565 : Node* node = queue_.front();
187 : info(node);
188 39093210 : queue_.pop_front();
189 : queued_.Set(node, false);
190 :
191 : int loop_num = -1;
192 : // Setup loop headers first.
193 39093355 : if (node->opcode() == IrOpcode::kLoop) {
194 : // found the loop node first.
195 1103859 : loop_num = CreateLoopInfo(node);
196 37989496 : } else if (NodeProperties::IsPhi(node)) {
197 : // found a phi first.
198 3424462 : Node* merge = node->InputAt(node->InputCount() - 1);
199 1712231 : if (merge->opcode() == IrOpcode::kLoop) {
200 1194028 : loop_num = CreateLoopInfo(merge);
201 : }
202 36277265 : } else if (node->opcode() == IrOpcode::kLoopExit) {
203 : // Intentionally ignore return value. Loop exit node marks
204 : // are propagated normally.
205 121324 : CreateLoopInfo(node->InputAt(1));
206 36155941 : } else if (node->opcode() == IrOpcode::kLoopExitValue ||
207 : node->opcode() == IrOpcode::kLoopExitEffect) {
208 255871 : Node* loop_exit = NodeProperties::GetControlInput(node);
209 : // Intentionally ignore return value. Loop exit node marks
210 : // are propagated normally.
211 255871 : CreateLoopInfo(loop_exit->InputAt(1));
212 : }
213 :
214 : // Propagate marks backwards from this node.
215 299224306 : for (int i = 0; i < node->InputCount(); i++) {
216 : Node* input = node->InputAt(i);
217 110518962 : if (IsBackedge(node, i)) {
218 : // Only propagate the loop mark on backedges.
219 2298107 : if (SetBackwardMark(input, loop_num)) Queue(input);
220 : } else {
221 : // Entry or normal edge. Propagate all marks except loop_num.
222 108221108 : if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
223 : }
224 : }
225 : }
226 634680 : }
227 :
228 : // Make a new loop if necessary for the given node.
229 2675079 : int CreateLoopInfo(Node* node) {
230 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
231 : int loop_num = LoopNum(node);
232 2675079 : if (loop_num > 0) return loop_num;
233 :
234 632174 : loop_num = ++loops_found_;
235 632174 : if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
236 :
237 : // Create a new loop.
238 1264348 : loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
239 632174 : loop_tree_->NewLoop();
240 632174 : SetLoopMarkForLoopHeader(node, loop_num);
241 632174 : return loop_num;
242 : }
243 :
244 4965747 : void SetLoopMark(Node* node, int loop_num) {
245 : info(node); // create the NodeInfo
246 : SetBackwardMark(node, loop_num);
247 3310498 : loop_tree_->node_to_loop_num_[node->id()] = loop_num;
248 1655249 : }
249 :
250 632174 : void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
251 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
252 632174 : SetLoopMark(node, loop_num);
253 3719868 : for (Node* use : node->uses()) {
254 1543847 : if (NodeProperties::IsPhi(use)) {
255 705455 : SetLoopMark(use, loop_num);
256 : }
257 :
258 : // Do not keep the loop alive if it does not have any backedges.
259 1543847 : if (node->InputCount() <= 1) continue;
260 :
261 1543847 : if (use->opcode() == IrOpcode::kLoopExit) {
262 101137 : SetLoopMark(use, loop_num);
263 801059 : for (Node* exit_use : use->uses()) {
264 349961 : if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
265 : exit_use->opcode() == IrOpcode::kLoopExitEffect) {
266 216483 : SetLoopMark(exit_use, loop_num);
267 : }
268 : }
269 : }
270 : }
271 632174 : }
272 :
273 1269542 : void ResizeBackwardMarks() {
274 634771 : int new_width = width_ + 1;
275 : int max = num_nodes();
276 634771 : uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
277 : memset(new_backward, 0, new_width * max * sizeof(uint32_t));
278 634771 : if (width_ > 0) { // copy old matrix data.
279 114520 : for (int i = 0; i < max; i++) {
280 114520 : uint32_t* np = &new_backward[i * new_width];
281 114520 : uint32_t* op = &backward_[i * width_];
282 114520 : for (int j = 0; j < width_; j++) np[j] = op[j];
283 : }
284 : }
285 634771 : width_ = new_width;
286 634771 : backward_ = new_backward;
287 634771 : }
288 :
289 634679 : void ResizeForwardMarks() {
290 : int max = num_nodes();
291 1269358 : forward_ = zone_->NewArray<uint32_t>(width_ * max);
292 634679 : memset(forward_, 0, width_ * max * sizeof(uint32_t));
293 634679 : }
294 :
295 : // Propagate marks forward from loops.
296 1899026 : void PropagateForward() {
297 634678 : ResizeForwardMarks();
298 1901540 : for (TempLoopInfo& li : loops_) {
299 632174 : SetForwardMark(li.header, LoopNum(li.header));
300 632174 : Queue(li.header);
301 : }
302 : // Propagate forward on paths that were backward reachable from backedges.
303 8371229 : while (!queue_.empty()) {
304 7736549 : Node* node = queue_.front();
305 7736549 : queue_.pop_front();
306 : queued_.Set(node, false);
307 23533624 : for (Edge edge : node->use_edges()) {
308 : Node* use = edge.from();
309 15797078 : if (!IsBackedge(use, edge.index())) {
310 14276568 : if (PropagateForwardMarks(node, use)) Queue(use);
311 : }
312 : }
313 : }
314 634680 : }
315 :
316 1655073 : bool IsLoopHeaderNode(Node* node) {
317 2677972 : return node->opcode() == IrOpcode::kLoop || NodeProperties::IsPhi(node);
318 : }
319 :
320 : bool IsLoopExitNode(Node* node) {
321 : return node->opcode() == IrOpcode::kLoopExit ||
322 : node->opcode() == IrOpcode::kLoopExitValue ||
323 : node->opcode() == IrOpcode::kLoopExitEffect;
324 : }
325 :
326 126315672 : bool IsBackedge(Node* use, int index) {
327 126315672 : if (LoopNum(use) <= 0) return false;
328 10633921 : if (NodeProperties::IsPhi(use)) {
329 5917544 : return index != NodeProperties::FirstControlIndex(use) &&
330 5917544 : index != kAssumedLoopEntryIndex;
331 4716378 : } else if (use->opcode() == IrOpcode::kLoop) {
332 3241228 : return index != kAssumedLoopEntryIndex;
333 : }
334 : DCHECK(IsLoopExitNode(use));
335 : return false;
336 : }
337 :
338 408010833 : int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
339 :
340 41354922 : NodeInfo& info(Node* node) {
341 41354922 : NodeInfo& i = info_[node->id()];
342 41354922 : if (i.node == nullptr) i.node = node;
343 : return i;
344 : }
345 :
346 47575161 : void Queue(Node* node) {
347 95150317 : if (!queued_.Get(node)) {
348 46829673 : queue_.push_back(node);
349 46829651 : queued_.Set(node, true);
350 : }
351 47575141 : }
352 :
353 12761372 : void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num) {
354 12761372 : if (LoopNum(node_info->node) == loop_num) {
355 1655073 : if (IsLoopHeaderNode(node_info->node)) {
356 1337629 : node_info->next = loop->header_list;
357 1337629 : loop->header_list = node_info;
358 : } else {
359 : DCHECK(IsLoopExitNode(node_info->node));
360 317444 : node_info->next = loop->exit_list;
361 317444 : loop->exit_list = node_info;
362 : }
363 : } else {
364 4725613 : node_info->next = loop->body_list;
365 4725613 : loop->body_list = node_info;
366 : }
367 6380686 : }
368 :
369 634679 : void FinishLoopTree() {
370 : DCHECK(loops_found_ == static_cast<int>(loops_.size()));
371 : DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));
372 :
373 : // Degenerate cases.
374 634679 : if (loops_found_ == 0) return;
375 227134 : if (loops_found_ == 1) return FinishSingleLoop();
376 :
377 606463 : for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i);
378 :
379 : size_t count = 0;
380 : // Place the node into the innermost nested loop of which it is a member.
381 11891999 : for (NodeInfo& ni : info_) {
382 11489153 : if (ni.node == nullptr) continue;
383 :
384 : TempLoopInfo* innermost = nullptr;
385 : int innermost_index = 0;
386 7018729 : int pos = ni.node->id() * width_;
387 : // Search the marks word by word.
388 14132354 : for (int i = 0; i < width_; i++) {
389 7113625 : uint32_t marks = backward_[pos + i] & forward_[pos + i];
390 234749625 : for (int j = 0; j < 32; j++) {
391 227636000 : if (marks & (1u << j)) {
392 6412067 : int loop_num = i * 32 + j;
393 6412067 : if (loop_num == 0) continue;
394 6412067 : TempLoopInfo* loop = &loops_[loop_num - 1];
395 8189611 : if (innermost == nullptr ||
396 1777544 : loop->loop->depth_ > innermost->loop->depth_) {
397 : innermost = loop;
398 : innermost_index = loop_num;
399 : }
400 : }
401 : }
402 : }
403 7018729 : if (innermost == nullptr) continue;
404 4634523 : AddNodeToLoop(&ni, innermost, innermost_index);
405 4634523 : count++;
406 : }
407 :
408 : // Serialize the node lists for loops into the loop tree.
409 201423 : loop_tree_->loop_nodes_.reserve(count);
410 812621 : for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
411 208352 : SerializeLoop(loop);
412 : }
413 : }
414 :
415 : // Handle the simpler case of a single loop (no checks for nesting necessary).
416 25711 : void FinishSingleLoop() {
417 : // Place nodes into the loop header and body.
418 25711 : TempLoopInfo* li = &loops_[0];
419 25711 : li->loop = &loop_tree_->all_loops_[0];
420 25711 : loop_tree_->SetParent(nullptr, li->loop);
421 : size_t count = 0;
422 5854773 : for (NodeInfo& ni : info_) {
423 9876665 : if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
424 1746104 : AddNodeToLoop(&ni, li, 1);
425 1746104 : count++;
426 : }
427 :
428 : // Serialize the node lists for the loop into the loop tree.
429 25711 : loop_tree_->loop_nodes_.reserve(count);
430 25711 : SerializeLoop(li->loop);
431 25711 : }
432 :
433 : // Recursively serialize the list of header nodes and body nodes
434 : // so that nested loops occupy nested intervals.
435 632173 : void SerializeLoop(LoopTree::Loop* loop) {
436 632173 : int loop_num = loop_tree_->LoopNum(loop);
437 632173 : TempLoopInfo& li = loops_[loop_num - 1];
438 :
439 : // Serialize the header.
440 3160867 : loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
441 1969802 : for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
442 1337629 : loop_tree_->loop_nodes_.push_back(ni->node);
443 9056207 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
444 : }
445 :
446 : // Serialize the body.
447 1264346 : loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
448 5358049 : for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
449 4725875 : loop_tree_->loop_nodes_.push_back(ni->node);
450 14177628 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
451 : }
452 :
453 : // Serialize nested loops.
454 1662459 : for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
455 :
456 : // Serialize the exits.
457 1264348 : loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
458 949618 : for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
459 317444 : loop_tree_->loop_nodes_.push_back(ni->node);
460 952332 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
461 : }
462 :
463 1264348 : loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
464 632174 : }
465 :
466 : // Connect the LoopTree loops to their parents recursively.
467 1005075 : LoopTree::Loop* ConnectLoopTree(int loop_num) {
468 1005075 : TempLoopInfo& li = loops_[loop_num - 1];
469 1005075 : if (li.loop != nullptr) return li.loop;
470 :
471 606463 : NodeInfo& ni = info(li.header);
472 : LoopTree::Loop* parent = nullptr;
473 2665256 : for (int i = 1; i <= loops_found_; i++) {
474 2058793 : if (i == loop_num) continue;
475 2904660 : if (IsInLoop(ni.node, i)) {
476 : // recursively create potential parent loops first.
477 398612 : LoopTree::Loop* upper = ConnectLoopTree(i);
478 398612 : if (parent == nullptr || upper->depth_ > parent->depth_) {
479 : parent = upper;
480 : }
481 : }
482 : }
483 1212926 : li.loop = &loop_tree_->all_loops_[loop_num - 1];
484 606463 : loop_tree_->SetParent(parent, li.loop);
485 606463 : return li.loop;
486 : }
487 :
488 0 : void PrintLoop(LoopTree::Loop* loop) {
489 0 : for (int i = 0; i < loop->depth_; i++) PrintF(" ");
490 0 : PrintF("Loop depth = %d ", loop->depth_);
491 0 : int i = loop->header_start_;
492 0 : while (i < loop->body_start_) {
493 0 : PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
494 : }
495 0 : while (i < loop->exits_start_) {
496 0 : PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
497 : }
498 0 : while (i < loop->exits_end_) {
499 0 : PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id());
500 : }
501 0 : PrintF("\n");
502 0 : for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
503 0 : }
504 : };
505 :
506 :
507 1269356 : LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
508 : LoopTree* loop_tree =
509 634679 : new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
510 634680 : LoopFinderImpl finder(graph, loop_tree, zone);
511 634680 : finder.Run();
512 634678 : if (FLAG_trace_turbo_loop) {
513 0 : finder.Print();
514 : }
515 634680 : return loop_tree;
516 : }
517 :
518 :
519 0 : Node* LoopTree::HeaderNode(Loop* loop) {
520 0 : Node* first = *HeaderNodes(loop).begin();
521 0 : if (first->opcode() == IrOpcode::kLoop) return first;
522 : DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
523 0 : Node* header = NodeProperties::GetControlInput(first);
524 : DCHECK_EQ(IrOpcode::kLoop, header->opcode());
525 0 : return header;
526 : }
527 :
528 : } // namespace compiler
529 : } // namespace internal
530 : } // namespace v8
|
