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 623809 : class LoopFinderImpl {
53 : public:
54 623804 : 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 1247610 : forward_(nullptr) {}
67 :
68 623805 : void Run() {
69 623805 : PropagateBackward();
70 623809 : PropagateForward();
71 623806 : FinishLoopTree();
72 623806 : }
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 1247686 : return static_cast<int>(loop_tree_->node_to_loop_num_.size());
122 : }
123 :
124 : // Tb = Tb | (Fb - loop_filter)
125 123575076 : bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
126 123575076 : if (from == to) return false;
127 247149570 : uint32_t* fp = &backward_[from->id() * width_];
128 123574785 : uint32_t* tp = &backward_[to->id() * width_];
129 : bool change = false;
130 375240537 : for (int i = 0; i < width_; i++) {
131 125832876 : uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
132 125832876 : uint32_t prev = tp[i];
133 125832876 : uint32_t next = prev | (fp[i] & mask);
134 125832876 : tp[i] = next;
135 125832876 : if (!change && (prev != next)) change = true;
136 : }
137 : return change;
138 : }
139 :
140 : // Tb = Tb | B
141 : bool SetBackwardMark(Node* to, int loop_num) {
142 4227992 : uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
143 4227992 : uint32_t prev = tp[0];
144 4227992 : uint32_t next = prev | BIT(loop_num);
145 4227992 : tp[0] = next;
146 : return next != prev;
147 : }
148 :
149 : // Tf = Tf | B
150 : bool SetForwardMark(Node* to, int loop_num) {
151 532508 : uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
152 532508 : uint32_t prev = tp[0];
153 532508 : uint32_t next = prev | BIT(loop_num);
154 532508 : tp[0] = next;
155 : return next != prev;
156 : }
157 :
158 : // Tf = Tf | (Ff & Tb)
159 14625511 : bool PropagateForwardMarks(Node* from, Node* to) {
160 14625511 : if (from == to) return false;
161 : bool change = false;
162 14625240 : int findex = from->id() * width_;
163 14625240 : int tindex = to->id() * width_;
164 43977674 : for (int i = 0; i < width_; i++) {
165 14676217 : uint32_t marks = backward_[tindex + i] & forward_[findex + i];
166 14676217 : uint32_t prev = forward_[tindex + i];
167 14676217 : uint32_t next = prev | marks;
168 14676217 : forward_[tindex + i] = next;
169 14676217 : if (!change && (prev != next)) change = true;
170 : }
171 : return change;
172 : }
173 :
174 : bool IsInLoop(Node* node, int loop_num) {
175 5817851 : int offset = node->id() * width_ + INDEX(loop_num);
176 5817851 : return backward_[offset] & forward_[offset] & BIT(loop_num);
177 : }
178 :
179 : // Propagate marks backward from loop headers.
180 623804 : void PropagateBackward() {
181 623804 : ResizeBackwardMarks();
182 623805 : SetBackwardMark(end_, 0);
183 623805 : Queue(end_);
184 :
185 42916113 : while (!queue_.empty()) {
186 42292304 : Node* node = queue_.front();
187 : info(node);
188 42292304 : queue_.pop_front();
189 : queued_.Set(node, false);
190 :
191 : int loop_num = -1;
192 : // Setup loop headers first.
193 42292518 : if (node->opcode() == IrOpcode::kLoop) {
194 : // found the loop node first.
195 930657 : loop_num = CreateLoopInfo(node);
196 41361861 : } else if (NodeProperties::IsPhi(node)) {
197 : // found a phi first.
198 1535233 : Node* merge = node->InputAt(node->InputCount() - 1);
199 1535233 : if (merge->opcode() == IrOpcode::kLoop) {
200 1014822 : loop_num = CreateLoopInfo(merge);
201 : }
202 39826628 : } else if (node->opcode() == IrOpcode::kLoopExit) {
203 : // Intentionally ignore return value. Loop exit node marks
204 : // are propagated normally.
205 227155 : CreateLoopInfo(node->InputAt(1));
206 39599473 : } else if (node->opcode() == IrOpcode::kLoopExitValue ||
207 : node->opcode() == IrOpcode::kLoopExitEffect) {
208 536694 : Node* loop_exit = NodeProperties::GetControlInput(node);
209 : // Intentionally ignore return value. Loop exit node marks
210 : // are propagated normally.
211 536693 : CreateLoopInfo(loop_exit->InputAt(1));
212 : }
213 :
214 : // Propagate marks backwards from this node.
215 293334322 : for (int i = 0; i < node->InputCount(); i++) {
216 : Node* input = node->InputAt(i);
217 125521488 : if (IsBackedge(node, i)) {
218 : // Only propagate the loop mark on backedges.
219 1945663 : if (SetBackwardMark(input, loop_num)) Queue(input);
220 : } else {
221 : // Entry or normal edge. Propagate all marks except loop_num.
222 123575035 : if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
223 : }
224 : }
225 : }
226 623809 : }
227 :
228 : // Make a new loop if necessary for the given node.
229 2709325 : int CreateLoopInfo(Node* node) {
230 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
231 : int loop_num = LoopNum(node);
232 2709325 : if (loop_num > 0) return loop_num;
233 :
234 532506 : loop_num = ++loops_found_;
235 532506 : if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
236 :
237 : // Create a new loop.
238 1065012 : loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
239 532506 : loop_tree_->NewLoop();
240 532508 : SetLoopMarkForLoopHeader(node, loop_num);
241 532506 : return loop_num;
242 : }
243 :
244 1658524 : void SetLoopMark(Node* node, int loop_num) {
245 : info(node); // create the NodeInfo
246 : SetBackwardMark(node, loop_num);
247 3317048 : loop_tree_->node_to_loop_num_[node->id()] = loop_num;
248 1658524 : }
249 :
250 532508 : void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
251 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
252 532508 : SetLoopMark(node, loop_num);
253 1930735 : for (Node* use : node->uses()) {
254 1398229 : if (NodeProperties::IsPhi(use)) {
255 598643 : SetLoopMark(use, loop_num);
256 : }
257 :
258 : // Do not keep the loop alive if it does not have any backedges.
259 1398229 : if (node->InputCount() <= 1) continue;
260 :
261 1398229 : if (use->opcode() == IrOpcode::kLoopExit) {
262 165770 : SetLoopMark(use, loop_num);
263 716829 : for (Node* exit_use : use->uses()) {
264 551059 : if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
265 : exit_use->opcode() == IrOpcode::kLoopExitEffect) {
266 361605 : SetLoopMark(exit_use, loop_num);
267 : }
268 : }
269 : }
270 : }
271 532506 : }
272 :
273 623877 : void ResizeBackwardMarks() {
274 623877 : int new_width = width_ + 1;
275 : int max = num_nodes();
276 623877 : uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
277 : memset(new_backward, 0, new_width * max * sizeof(uint32_t));
278 623880 : if (width_ > 0) { // copy old matrix data.
279 98633 : for (int i = 0; i < max; i++) {
280 49280 : uint32_t* np = &new_backward[i * new_width];
281 49280 : uint32_t* op = &backward_[i * width_];
282 132720 : for (int j = 0; j < width_; j++) np[j] = op[j];
283 : }
284 : }
285 623880 : width_ = new_width;
286 623880 : backward_ = new_backward;
287 623880 : }
288 :
289 623809 : void ResizeForwardMarks() {
290 : int max = num_nodes();
291 1247618 : forward_ = zone_->NewArray<uint32_t>(width_ * max);
292 623809 : memset(forward_, 0, width_ * max * sizeof(uint32_t));
293 623809 : }
294 :
295 : // Propagate marks forward from loops.
296 623809 : void PropagateForward() {
297 623809 : ResizeForwardMarks();
298 1156318 : for (TempLoopInfo& li : loops_) {
299 532508 : SetForwardMark(li.header, LoopNum(li.header));
300 532508 : Queue(li.header);
301 : }
302 : // Propagate forward on paths that were backward reachable from backedges.
303 15843100 : while (!queue_.empty()) {
304 7609649 : Node* node = queue_.front();
305 7609649 : queue_.pop_front();
306 : queued_.Set(node, false);
307 23519001 : for (Edge edge : node->use_edges()) {
308 : Node* use = edge.from();
309 15909356 : if (!IsBackedge(use, edge.index())) {
310 14625514 : if (PropagateForwardMarks(node, use)) Queue(use);
311 : }
312 : }
313 : }
314 623806 : }
315 :
316 : bool IsLoopHeaderNode(Node* node) {
317 2735811 : 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 141426584 : bool IsBackedge(Node* use, int index) {
327 141426584 : if (LoopNum(use) <= 0) return false;
328 10566083 : if (NodeProperties::IsPhi(use)) {
329 5010353 : return index != NodeProperties::FirstControlIndex(use) &&
330 : index != kAssumedLoopEntryIndex;
331 5555728 : } else if (use->opcode() == IrOpcode::kLoop) {
332 2728419 : return index != kAssumedLoopEntryIndex;
333 : }
334 : DCHECK(IsLoopExitNode(use));
335 : return false;
336 : }
337 :
338 301814904 : int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
339 :
340 : NodeInfo& info(Node* node) {
341 44457752 : NodeInfo& i = info_[node->id()];
342 44457752 : if (i.node == nullptr) i.node = node;
343 : return i;
344 : }
345 :
346 50614823 : void Queue(Node* node) {
347 101229646 : if (!queued_.Get(node)) {
348 49901639 : queue_.push_back(node);
349 49901619 : queued_.Set(node, true);
350 : }
351 50614803 : }
352 :
353 6239035 : void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num) {
354 12478070 : if (LoopNum(node_info->node) == loop_num) {
355 1634159 : if (IsLoopHeaderNode(node_info->node)) {
356 1131162 : node_info->next = loop->header_list;
357 1131162 : loop->header_list = node_info;
358 : } else {
359 : DCHECK(IsLoopExitNode(node_info->node));
360 502997 : node_info->next = loop->exit_list;
361 502997 : loop->exit_list = node_info;
362 : }
363 : } else {
364 4604876 : node_info->next = loop->body_list;
365 4604876 : loop->body_list = node_info;
366 : }
367 6239035 : }
368 :
369 623806 : 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 623806 : if (loops_found_ == 0) return;
375 193655 : if (loops_found_ == 1) return FinishSingleLoop();
376 :
377 674995 : 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 10400170 : for (NodeInfo& ni : info_) {
382 10232099 : if (ni.node == nullptr) continue;
383 :
384 : TempLoopInfo* innermost = nullptr;
385 : int innermost_index = 0;
386 6726950 : int pos = ni.node->id() * width_;
387 : // Search the marks word by word.
388 20275648 : for (int i = 0; i < width_; i++) {
389 6774349 : uint32_t marks = backward_[pos + i] & forward_[pos + i];
390 :
391 440332685 : for (int j = 0; j < 32; j++) {
392 216779168 : if (marks & (1u << j)) {
393 6145248 : int loop_num = i * 32 + j;
394 6145248 : if (loop_num == 0) continue;
395 6145248 : TempLoopInfo* loop = &loops_[loop_num - 1];
396 7933482 : if (innermost == nullptr ||
397 1788234 : loop->loop->depth_ > innermost->loop->depth_) {
398 : innermost = loop;
399 : innermost_index = loop_num;
400 : }
401 : }
402 : }
403 : }
404 6726950 : if (innermost == nullptr) continue;
405 :
406 : // Return statements should never be found by forward or backward walk.
407 4357014 : CHECK(ni.node->opcode() != IrOpcode::kReturn);
408 :
409 4357014 : AddNodeToLoop(&ni, innermost, innermost_index);
410 4357014 : count++;
411 : }
412 :
413 : // Serialize the node lists for loops into the loop tree.
414 168071 : loop_tree_->loop_nodes_.reserve(count);
415 511109 : for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
416 174967 : SerializeLoop(loop);
417 : }
418 : }
419 :
420 : // Handle the simpler case of a single loop (no checks for nesting necessary).
421 25583 : void FinishSingleLoop() {
422 : // Place nodes into the loop header and body.
423 : TempLoopInfo* li = &loops_[0];
424 25583 : li->loop = &loop_tree_->all_loops_[0];
425 25583 : loop_tree_->SetParent(nullptr, li->loop);
426 : size_t count = 0;
427 6421602 : for (NodeInfo& ni : info_) {
428 11000098 : if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
429 :
430 : // Return statements should never be found by forward or backward walk.
431 1882021 : CHECK(ni.node->opcode() != IrOpcode::kReturn);
432 :
433 1882021 : AddNodeToLoop(&ni, li, 1);
434 1882021 : count++;
435 : }
436 :
437 : // Serialize the node lists for the loop into the loop tree.
438 25583 : loop_tree_->loop_nodes_.reserve(count);
439 25583 : SerializeLoop(li->loop);
440 25583 : }
441 :
442 : // Recursively serialize the list of header nodes and body nodes
443 : // so that nested loops occupy nested intervals.
444 532489 : void SerializeLoop(LoopTree::Loop* loop) {
445 532489 : int loop_num = loop_tree_->LoopNum(loop);
446 532489 : TempLoopInfo& li = loops_[loop_num - 1];
447 :
448 : // Serialize the header.
449 532489 : loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
450 1663660 : for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
451 1131171 : loop_tree_->loop_nodes_.push_back(ni->node);
452 3393513 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
453 : }
454 :
455 : // Serialize the body.
456 1064978 : loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
457 5137502 : for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
458 4604991 : loop_tree_->loop_nodes_.push_back(ni->node);
459 13815039 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
460 : }
461 :
462 : // Serialize nested loops.
463 864468 : for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
464 :
465 : // Serialize the exits.
466 1065022 : loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
467 1035508 : for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
468 503001 : loop_tree_->loop_nodes_.push_back(ni->node);
469 1508991 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
470 : }
471 :
472 1065014 : loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
473 532507 : }
474 :
475 : // Connect the LoopTree loops to their parents recursively.
476 838968 : LoopTree::Loop* ConnectLoopTree(int loop_num) {
477 838968 : TempLoopInfo& li = loops_[loop_num - 1];
478 838968 : if (li.loop != nullptr) return li.loop;
479 :
480 506924 : NodeInfo& ni = info(li.header);
481 : LoopTree::Loop* parent = nullptr;
482 3948316 : for (int i = 1; i <= loops_found_; i++) {
483 1720696 : if (i == loop_num) continue;
484 2427544 : if (IsInLoop(ni.node, i)) {
485 : // recursively create potential parent loops first.
486 332044 : LoopTree::Loop* upper = ConnectLoopTree(i);
487 332044 : if (parent == nullptr || upper->depth_ > parent->depth_) {
488 : parent = upper;
489 : }
490 : }
491 : }
492 1013848 : li.loop = &loop_tree_->all_loops_[loop_num - 1];
493 506924 : loop_tree_->SetParent(parent, li.loop);
494 506924 : 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 623802 : LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
517 : LoopTree* loop_tree =
518 623802 : new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
519 623806 : LoopFinderImpl finder(graph, loop_tree, zone);
520 623806 : finder.Run();
521 623806 : if (FLAG_trace_turbo_loop) {
522 0 : finder.Print();
523 : }
524 623809 : 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 122004 : } // namespace v8
|
