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 2460004 : 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 1844989 : forward_(nullptr) {}
67 :
68 615004 : void Run() {
69 615004 : PropagateBackward();
70 614999 : PropagateForward();
71 614989 : FinishLoopTree();
72 614994 : }
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 2460170 : return static_cast<int>(loop_tree_->node_to_loop_num_.size());
122 : }
123 :
124 : // Tb = Tb | (Fb - loop_filter)
125 335164928 : bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
126 111721660 : if (from == to) return false;
127 223443268 : uint32_t* fp = &backward_[from->id() * width_];
128 111721634 : uint32_t* tp = &backward_[to->id() * width_];
129 : bool change = false;
130 228621325 : for (int i = 0; i < width_; i++) {
131 116899691 : uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
132 116899691 : uint32_t prev = tp[i];
133 116899691 : uint32_t next = prev | (fp[i] & mask);
134 116899691 : tp[i] = next;
135 116899691 : if (!change && (prev != next)) change = true;
136 : }
137 : return change;
138 : }
139 :
140 : // Tb = Tb | B
141 4137246 : bool SetBackwardMark(Node* to, int loop_num) {
142 4137246 : uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
143 4137246 : uint32_t prev = tp[0];
144 4137246 : uint32_t next = prev | BIT(loop_num);
145 4137246 : tp[0] = next;
146 : return next != prev;
147 : }
148 :
149 : // Tf = Tf | B
150 : bool SetForwardMark(Node* to, int loop_num) {
151 533335 : uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
152 533335 : uint32_t prev = tp[0];
153 533335 : uint32_t next = prev | BIT(loop_num);
154 533335 : tp[0] = next;
155 : return next != prev;
156 : }
157 :
158 : // Tf = Tf | (Ff & Tb)
159 40362074 : bool PropagateForwardMarks(Node* from, Node* to) {
160 13454208 : if (from == to) return false;
161 : bool change = false;
162 13453933 : int findex = from->id() * width_;
163 13453933 : int tindex = to->id() * width_;
164 27118277 : for (int i = 0; i < width_; i++) {
165 13664344 : uint32_t marks = backward_[tindex + i] & forward_[findex + i];
166 13664344 : uint32_t prev = forward_[tindex + i];
167 13664344 : uint32_t next = prev | marks;
168 13664344 : forward_[tindex + i] = next;
169 13664344 : if (!change && (prev != next)) change = true;
170 : }
171 : return change;
172 : }
173 :
174 5546200 : bool IsInLoop(Node* node, int loop_num) {
175 5546200 : int offset = node->id() * width_ + INDEX(loop_num);
176 5546200 : return backward_[offset] & forward_[offset] & BIT(loop_num);
177 : }
178 :
179 : // Propagate marks backward from loop headers.
180 3200528 : void PropagateBackward() {
181 614993 : ResizeBackwardMarks();
182 614987 : SetBackwardMark(end_, 0);
183 614987 : Queue(end_);
184 :
185 40857958 : while (!queue_.empty()) {
186 79256021 : Node* node = queue_.front();
187 : info(node);
188 39627974 : queue_.pop_front();
189 : queued_.Set(node, false);
190 :
191 : int loop_num = -1;
192 : // Setup loop headers first.
193 39628047 : if (node->opcode() == IrOpcode::kLoop) {
194 : // found the loop node first.
195 940100 : loop_num = CreateLoopInfo(node);
196 38687947 : } else if (NodeProperties::IsPhi(node)) {
197 : // found a phi first.
198 3110628 : Node* merge = node->InputAt(node->InputCount() - 1);
199 1555314 : if (merge->opcode() == IrOpcode::kLoop) {
200 1030263 : loop_num = CreateLoopInfo(merge);
201 : }
202 37132633 : } else if (node->opcode() == IrOpcode::kLoopExit) {
203 : // Intentionally ignore return value. Loop exit node marks
204 : // are propagated normally.
205 202455 : CreateLoopInfo(node->InputAt(1));
206 36930178 : } else if (node->opcode() == IrOpcode::kLoopExitValue ||
207 : node->opcode() == IrOpcode::kLoopExitEffect) {
208 379651 : Node* loop_exit = NodeProperties::GetControlInput(node);
209 : // Intentionally ignore return value. Loop exit node marks
210 : // are propagated normally.
211 379651 : CreateLoopInfo(loop_exit->InputAt(1));
212 : }
213 :
214 : // Propagate marks backwards from this node.
215 306640234 : for (int i = 0; i < node->InputCount(); i++) {
216 : Node* input = node->InputAt(i);
217 113692135 : if (IsBackedge(node, i)) {
218 : // Only propagate the loop mark on backedges.
219 1970548 : if (SetBackwardMark(input, loop_num)) Queue(input);
220 : } else {
221 : // Entry or normal edge. Propagate all marks except loop_num.
222 111721737 : if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
223 : }
224 : }
225 : }
226 614996 : }
227 :
228 : // Make a new loop if necessary for the given node.
229 2552470 : int CreateLoopInfo(Node* node) {
230 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
231 : int loop_num = LoopNum(node);
232 2552470 : if (loop_num > 0) return loop_num;
233 :
234 533334 : loop_num = ++loops_found_;
235 533334 : if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
236 :
237 : // Create a new loop.
238 1066667 : loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
239 533333 : loop_tree_->NewLoop();
240 533334 : SetLoopMarkForLoopHeader(node, loop_num);
241 533335 : return loop_num;
242 : }
243 :
244 4655133 : void SetLoopMark(Node* node, int loop_num) {
245 : info(node); // create the NodeInfo
246 : SetBackwardMark(node, loop_num);
247 3103422 : loop_tree_->node_to_loop_num_[node->id()] = loop_num;
248 1551711 : }
249 :
250 533334 : void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
251 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
252 533334 : SetLoopMark(node, loop_num);
253 3822692 : for (Node* use : node->uses()) {
254 1378011 : if (NodeProperties::IsPhi(use)) {
255 599854 : SetLoopMark(use, loop_num);
256 : }
257 :
258 : // Do not keep the loop alive if it does not have any backedges.
259 1378012 : if (node->InputCount() <= 1) continue;
260 :
261 1378013 : if (use->opcode() == IrOpcode::kLoopExit) {
262 139127 : SetLoopMark(use, loop_num);
263 1168661 : for (Node* exit_use : use->uses()) {
264 445203 : if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
265 : exit_use->opcode() == IrOpcode::kLoopExitEffect) {
266 279397 : SetLoopMark(exit_use, loop_num);
267 : }
268 : }
269 : }
270 : }
271 533335 : }
272 :
273 1230172 : void ResizeBackwardMarks() {
274 615086 : int new_width = width_ + 1;
275 : int max = num_nodes();
276 615086 : uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
277 : memset(new_backward, 0, new_width * max * sizeof(uint32_t));
278 615100 : if (width_ > 0) { // copy old matrix data.
279 233872 : for (int i = 0; i < max; i++) {
280 233872 : uint32_t* np = &new_backward[i * new_width];
281 233872 : uint32_t* op = &backward_[i * width_];
282 233872 : for (int j = 0; j < width_; j++) np[j] = op[j];
283 : }
284 : }
285 615100 : width_ = new_width;
286 615100 : backward_ = new_backward;
287 615100 : }
288 :
289 614999 : void ResizeForwardMarks() {
290 : int max = num_nodes();
291 1229999 : forward_ = zone_->NewArray<uint32_t>(width_ * max);
292 615000 : memset(forward_, 0, width_ * max * sizeof(uint32_t));
293 615000 : }
294 :
295 : // Propagate marks forward from loops.
296 1681668 : void PropagateForward() {
297 614998 : ResizeForwardMarks();
298 1763319 : for (TempLoopInfo& li : loops_) {
299 533335 : SetForwardMark(li.header, LoopNum(li.header));
300 533335 : Queue(li.header);
301 : }
302 : // Propagate forward on paths that were backward reachable from backedges.
303 7779576 : while (!queue_.empty()) {
304 7164595 : Node* node = queue_.front();
305 7164595 : queue_.pop_front();
306 : queued_.Set(node, false);
307 29070027 : for (Edge edge : node->use_edges()) {
308 : Node* use = edge.from();
309 14740867 : if (!IsBackedge(use, edge.index())) {
310 13454233 : if (PropagateForwardMarks(node, use)) Queue(use);
311 : }
312 : }
313 : }
314 614981 : }
315 :
316 1551368 : bool IsLoopHeaderNode(Node* node) {
317 2569401 : 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 128432194 : bool IsBackedge(Node* use, int index) {
327 128432194 : if (LoopNum(use) <= 0) return false;
328 9969590 : if (NodeProperties::IsPhi(use)) {
329 5061048 : return index != NodeProperties::FirstControlIndex(use) &&
330 5061048 : index != kAssumedLoopEntryIndex;
331 4908545 : } else if (use->opcode() == IrOpcode::kLoop) {
332 2748815 : return index != kAssumedLoopEntryIndex;
333 : }
334 : DCHECK(IsLoopExitNode(use));
335 : return false;
336 : }
337 :
338 412287396 : int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
339 :
340 41687576 : NodeInfo& info(Node* node) {
341 41687576 : NodeInfo& i = info_[node->id()];
342 41687576 : if (i.node == nullptr) i.node = node;
343 : return i;
344 : }
345 :
346 47514185 : void Queue(Node* node) {
347 95028408 : if (!queued_.Get(node)) {
348 46792427 : queue_.push_back(node);
349 46792409 : queued_.Set(node, true);
350 : }
351 47514220 : }
352 :
353 11822266 : void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num) {
354 11822266 : if (LoopNum(node_info->node) == loop_num) {
355 1551368 : if (IsLoopHeaderNode(node_info->node)) {
356 1133189 : node_info->next = loop->header_list;
357 1133189 : loop->header_list = node_info;
358 : } else {
359 : DCHECK(IsLoopExitNode(node_info->node));
360 418179 : node_info->next = loop->exit_list;
361 418179 : loop->exit_list = node_info;
362 : }
363 : } else {
364 4359765 : node_info->next = loop->body_list;
365 4359765 : loop->body_list = node_info;
366 : }
367 5911133 : }
368 :
369 614986 : 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 614986 : if (loops_found_ == 0) return;
375 193747 : if (loops_found_ == 1) return FinishSingleLoop();
376 :
377 507891 : 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 10529589 : for (NodeInfo& ni : info_) {
382 14334148 : if (ni.node == nullptr) continue;
383 :
384 : TempLoopInfo* innermost = nullptr;
385 : int innermost_index = 0;
386 6418892 : int pos = ni.node->id() * width_;
387 : // Search the marks word by word.
388 12969447 : for (int i = 0; i < width_; i++) {
389 6550555 : uint32_t marks = backward_[pos + i] & forward_[pos + i];
390 :
391 216168315 : for (int j = 0; j < 32; j++) {
392 209617760 : if (marks & (1u << j)) {
393 5807382 : int loop_num = i * 32 + j;
394 5807382 : if (loop_num == 0) continue;
395 5807382 : TempLoopInfo* loop = &loops_[loop_num - 1];
396 7473599 : if (innermost == nullptr ||
397 1666217 : loop->loop->depth_ > innermost->loop->depth_) {
398 : innermost = loop;
399 : innermost_index = loop_num;
400 : }
401 : }
402 : }
403 : }
404 6418892 : if (innermost == nullptr) continue;
405 :
406 : // Return statements should never be found by forward or backward walk.
407 4141165 : CHECK(ni.node->opcode() != IrOpcode::kReturn);
408 :
409 4141165 : AddNodeToLoop(&ni, innermost, innermost_index);
410 4141165 : count++;
411 : }
412 :
413 : // Serialize the node lists for loops into the loop tree.
414 168303 : loop_tree_->loop_nodes_.reserve(count);
415 680678 : for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
416 175769 : SerializeLoop(loop);
417 : }
418 : }
419 :
420 : // Handle the simpler case of a single loop (no checks for nesting necessary).
421 25442 : void FinishSingleLoop() {
422 : // Place nodes into the loop header and body.
423 25442 : TempLoopInfo* li = &loops_[0];
424 25442 : li->loop = &loop_tree_->all_loops_[0];
425 25442 : loop_tree_->SetParent(nullptr, li->loop);
426 : size_t count = 0;
427 6342149 : for (NodeInfo& ni : info_) {
428 10583548 : if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
429 :
430 : // Return statements should never be found by forward or backward walk.
431 1770005 : CHECK(ni.node->opcode() != IrOpcode::kReturn);
432 :
433 1769967 : AddNodeToLoop(&ni, li, 1);
434 1769960 : count++;
435 : }
436 :
437 : // Serialize the node lists for the loop into the loop tree.
438 25443 : loop_tree_->loop_nodes_.reserve(count);
439 25441 : SerializeLoop(li->loop);
440 25444 : }
441 :
442 : // Recursively serialize the list of header nodes and body nodes
443 : // so that nested loops occupy nested intervals.
444 533358 : void SerializeLoop(LoopTree::Loop* loop) {
445 533358 : int loop_num = loop_tree_->LoopNum(loop);
446 533358 : TempLoopInfo& li = loops_[loop_num - 1];
447 :
448 : // Serialize the header.
449 2666743 : loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
450 1666539 : for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
451 1133183 : loop_tree_->loop_nodes_.push_back(ni->node);
452 8177431 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
453 : }
454 :
455 : // Serialize the body.
456 1066712 : loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
457 4893067 : for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
458 4359731 : loop_tree_->loop_nodes_.push_back(ni->node);
459 13079133 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
460 : }
461 :
462 : // Serialize nested loops.
463 1398794 : for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
464 :
465 : // Serialize the exits.
466 1066672 : loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
467 951513 : for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
468 418178 : loop_tree_->loop_nodes_.push_back(ni->node);
469 1254531 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
470 : }
471 :
472 1066670 : loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
473 533335 : }
474 :
475 : // Connect the LoopTree loops to their parents recursively.
476 840190 : LoopTree::Loop* ConnectLoopTree(int loop_num) {
477 840190 : TempLoopInfo& li = loops_[loop_num - 1];
478 840190 : if (li.loop != nullptr) return li.loop;
479 :
480 507891 : NodeInfo& ni = info(li.header);
481 : LoopTree::Loop* parent = nullptr;
482 2269652 : for (int i = 1; i <= loops_found_; i++) {
483 1761761 : if (i == loop_num) continue;
484 2507740 : if (IsInLoop(ni.node, i)) {
485 : // recursively create potential parent loops first.
486 332299 : LoopTree::Loop* upper = ConnectLoopTree(i);
487 332299 : if (parent == nullptr || upper->depth_ > parent->depth_) {
488 : parent = upper;
489 : }
490 : }
491 : }
492 1015782 : li.loop = &loop_tree_->all_loops_[loop_num - 1];
493 507891 : loop_tree_->SetParent(parent, li.loop);
494 507891 : return li.loop;
495 : }
496 :
497 0 : void PrintLoop(LoopTree::Loop* loop) {
498 0 : for (int i = 0; i < loop->depth_; i++) PrintF(" ");
499 0 : PrintF("Loop depth = %d ", loop->depth_);
500 0 : int i = loop->header_start_;
501 0 : while (i < loop->body_start_) {
502 0 : PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
503 : }
504 0 : while (i < loop->exits_start_) {
505 0 : PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
506 : }
507 0 : while (i < loop->exits_end_) {
508 0 : PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id());
509 : }
510 0 : PrintF("\n");
511 0 : for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
512 0 : }
513 : };
514 :
515 :
516 1229970 : LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
517 : LoopTree* loop_tree =
518 615001 : new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
519 614993 : LoopFinderImpl finder(graph, loop_tree, zone);
520 615005 : finder.Run();
521 614994 : if (FLAG_trace_turbo_loop) {
522 0 : finder.Print();
523 : }
524 614998 : return loop_tree;
525 : }
526 :
527 :
528 0 : Node* LoopTree::HeaderNode(Loop* loop) {
529 0 : Node* first = *HeaderNodes(loop).begin();
530 0 : if (first->opcode() == IrOpcode::kLoop) return first;
531 : DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
532 0 : Node* header = NodeProperties::GetControlInput(first);
533 : DCHECK_EQ(IrOpcode::kLoop, header->opcode());
534 0 : return header;
535 : }
536 :
537 : } // namespace compiler
538 : } // namespace internal
539 183867 : } // namespace v8
|
