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 LoopInfo {
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 2489516 : 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 1867137 : forward_(nullptr) {}
67 :
68 622379 : void Run() {
69 622379 : PropagateBackward();
70 622379 : PropagateForward();
71 622379 : FinishLoopTree();
72 622379 : }
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 (LoopInfo& 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<LoopInfo> 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 2489736 : return static_cast<int>(loop_tree_->node_to_loop_num_.size());
122 : }
123 :
124 : // Tb = Tb | (Fb - loop_filter)
125 325897748 : bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
126 108632876 : if (from == to) return false;
127 217264872 : uint32_t* fp = &backward_[from->id() * width_];
128 108632436 : uint32_t* tp = &backward_[to->id() * width_];
129 : bool change = false;
130 228467225 : for (int i = 0; i < width_; i++) {
131 119834789 : uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
132 119834789 : uint32_t prev = tp[i];
133 119834789 : uint32_t next = prev | (fp[i] & mask);
134 119834789 : tp[i] = next;
135 119834789 : if (!change && (prev != next)) change = true;
136 : }
137 : return change;
138 : }
139 :
140 : // Tb = Tb | B
141 3442751 : bool SetBackwardMark(Node* to, int loop_num) {
142 5567047 : uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
143 5567047 : uint32_t prev = tp[0];
144 5567047 : uint32_t next = prev | BIT(loop_num);
145 5567047 : tp[0] = next;
146 : return next != prev;
147 : }
148 :
149 : // Tf = Tf | B
150 : bool SetForwardMark(Node* to, int loop_num) {
151 742281 : uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
152 742281 : uint32_t prev = tp[0];
153 742281 : uint32_t next = prev | BIT(loop_num);
154 742281 : tp[0] = next;
155 : return next != prev;
156 : }
157 :
158 : // Tf = Tf | (Ff & Tb)
159 59723345 : bool PropagateForwardMarks(Node* from, Node* to) {
160 19908055 : if (from == to) return false;
161 : bool change = false;
162 19907645 : int findex = from->id() * width_;
163 19907645 : int tindex = to->id() * width_;
164 39984931 : for (int i = 0; i < width_; i++) {
165 20077286 : uint32_t marks = backward_[tindex + i] & forward_[findex + i];
166 20077286 : uint32_t prev = forward_[tindex + i];
167 20077286 : uint32_t next = prev | marks;
168 20077286 : forward_[tindex + i] = next;
169 20077286 : if (!change && (prev != next)) change = true;
170 : }
171 : return change;
172 : }
173 :
174 7762945 : bool IsInLoop(Node* node, int loop_num) {
175 7762945 : int offset = node->id() * width_ + INDEX(loop_num);
176 7762945 : return backward_[offset] & forward_[offset] & BIT(loop_num);
177 : }
178 :
179 : // Propagate marks backward from loop headers.
180 4065130 : void PropagateBackward() {
181 622379 : ResizeBackwardMarks();
182 622379 : SetBackwardMark(end_, 0);
183 622379 : Queue(end_);
184 :
185 43345575 : while (!queue_.empty()) {
186 84201729 : Node* node = queue_.front();
187 : info(node);
188 42100812 : queue_.pop_front();
189 : queued_.Set(node, false);
190 :
191 : int loop_num = -1;
192 : // Setup loop headers first.
193 42100917 : if (node->opcode() == IrOpcode::kLoop) {
194 : // found the loop node first.
195 1298285 : loop_num = CreateLoopInfo(node);
196 40802632 : } else if (NodeProperties::IsPhi(node)) {
197 : // found a phi first.
198 4624158 : Node* merge = node->InputAt(node->InputCount() - 1);
199 2312079 : if (merge->opcode() == IrOpcode::kLoop) {
200 1474839 : loop_num = CreateLoopInfo(merge);
201 : }
202 38490553 : } else if (node->opcode() == IrOpcode::kLoopExit) {
203 : // Intentionally ignore return value. Loop exit node marks
204 : // are propagated normally.
205 183646 : CreateLoopInfo(node->InputAt(1));
206 38306907 : } else if (node->opcode() == IrOpcode::kLoopExitValue ||
207 : node->opcode() == IrOpcode::kLoopExitEffect) {
208 399373 : Node* loop_exit = NodeProperties::GetControlInput(node);
209 : // Intentionally ignore return value. Loop exit node marks
210 : // are propagated normally.
211 399373 : CreateLoopInfo(loop_exit->InputAt(1));
212 : }
213 :
214 : // Propagate marks backwards from this node.
215 307107938 : for (int i = 0; i < node->InputCount(); i++) {
216 : Node* input = node->InputAt(i);
217 111453162 : if (IsBackedge(node, i)) {
218 : // Only propagate the loop mark on backedges.
219 2820372 : if (SetBackwardMark(input, loop_num)) Queue(input);
220 : } else {
221 : // Entry or normal edge. Propagate all marks except loop_num.
222 108632873 : if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
223 : }
224 : }
225 : }
226 622379 : }
227 :
228 : // Make a new loop if necessary for the given node.
229 3356139 : int CreateLoopInfo(Node* node) {
230 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
231 : int loop_num = LoopNum(node);
232 3356139 : if (loop_num > 0) return loop_num;
233 :
234 742281 : loop_num = ++loops_found_;
235 742281 : if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
236 :
237 : // Create a new loop.
238 1484562 : loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
239 742281 : loop_tree_->NewLoop();
240 742281 : SetLoopMarkForLoopHeader(node, loop_num);
241 742281 : return loop_num;
242 : }
243 :
244 6372888 : void SetLoopMark(Node* node, int loop_num) {
245 : info(node); // create the NodeInfo
246 : SetBackwardMark(node, loop_num);
247 4248592 : loop_tree_->node_to_loop_num_[node->id()] = loop_num;
248 2124296 : }
249 :
250 742281 : void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
251 : DCHECK_EQ(IrOpcode::kLoop, node->opcode());
252 742281 : SetLoopMark(node, loop_num);
253 4577903 : for (Node* use : node->uses()) {
254 1918252 : if (NodeProperties::IsPhi(use)) {
255 878693 : SetLoopMark(use, loop_num);
256 : }
257 :
258 : // Do not keep the loop alive if it does not have any backedges.
259 1918252 : if (node->InputCount() <= 1) continue;
260 :
261 1917370 : if (use->opcode() == IrOpcode::kLoopExit) {
262 156863 : SetLoopMark(use, loop_num);
263 1254085 : for (Node* exit_use : use->uses()) {
264 548611 : if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
265 : exit_use->opcode() == IrOpcode::kLoopExitEffect) {
266 346459 : SetLoopMark(exit_use, loop_num);
267 : }
268 : }
269 : }
270 : }
271 742281 : }
272 :
273 1244978 : void ResizeBackwardMarks() {
274 622489 : int new_width = width_ + 1;
275 : int max = num_nodes();
276 622489 : uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
277 : memset(new_backward, 0, new_width * max * sizeof(uint32_t));
278 622489 : if (width_ > 0) { // copy old matrix data.
279 209488 : for (int i = 0; i < max; i++) {
280 209488 : uint32_t* np = &new_backward[i * new_width];
281 209488 : uint32_t* op = &backward_[i * width_];
282 209488 : for (int j = 0; j < width_; j++) np[j] = op[j];
283 : }
284 : }
285 622489 : width_ = new_width;
286 622489 : backward_ = new_backward;
287 622489 : }
288 :
289 622379 : void ResizeForwardMarks() {
290 : int max = num_nodes();
291 1244758 : forward_ = zone_->NewArray<uint32_t>(width_ * max);
292 622379 : memset(forward_, 0, width_ * max * sizeof(uint32_t));
293 622379 : }
294 :
295 : // Propagate marks forward from loops.
296 2106941 : void PropagateForward() {
297 622379 : ResizeForwardMarks();
298 1987049 : for (LoopInfo& li : loops_) {
299 742281 : SetForwardMark(li.header, LoopNum(li.header));
300 742281 : Queue(li.header);
301 : }
302 : // Propagate forward on paths that were backward reachable from backedges.
303 11065147 : while (!queue_.empty()) {
304 10442768 : Node* node = queue_.front();
305 10442768 : queue_.pop_front();
306 : queued_.Set(node, false);
307 32182659 : for (Edge edge : node->use_edges()) {
308 : Node* use = edge.from();
309 21739896 : if (!IsBackedge(use, edge.index())) {
310 19908042 : if (PropagateForwardMarks(node, use)) Queue(use);
311 : }
312 : }
313 : }
314 622379 : }
315 :
316 2123648 : bool IsLoopHeaderNode(Node* node) {
317 3505015 : 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 133190802 : bool IsBackedge(Node* use, int index) {
327 133190802 : if (LoopNum(use) <= 0) return false;
328 13483844 : if (NodeProperties::IsPhi(use)) {
329 7341198 : return index != NodeProperties::FirstControlIndex(use) &&
330 7341198 : index != kAssumedLoopEntryIndex;
331 6142640 : } else if (use->opcode() == IrOpcode::kLoop) {
332 3817724 : return index != kAssumedLoopEntryIndex;
333 : }
334 : DCHECK(IsLoopExitNode(use));
335 : return false;
336 : }
337 :
338 437888118 : int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
339 :
340 44938692 : NodeInfo& info(Node* node) {
341 44938692 : NodeInfo& i = info_[node->id()];
342 44938692 : if (i.node == nullptr) i.node = node;
343 : return i;
344 : }
345 :
346 53513834 : void Queue(Node* node) {
347 107027609 : if (!queued_.Get(node)) {
348 52543022 : queue_.push_back(node);
349 52543003 : queued_.Set(node, true);
350 : }
351 53513771 : }
352 :
353 17346968 : void AddNodeToLoop(NodeInfo* node_info, LoopInfo* loop, int loop_num) {
354 17346968 : if (LoopNum(node_info->node) == loop_num) {
355 2123648 : if (IsLoopHeaderNode(node_info->node)) {
356 1620974 : node_info->next = loop->header_list;
357 1620974 : loop->header_list = node_info;
358 : } else {
359 : DCHECK(IsLoopExitNode(node_info->node));
360 502674 : node_info->next = loop->exit_list;
361 502674 : loop->exit_list = node_info;
362 : }
363 : } else {
364 6549836 : node_info->next = loop->body_list;
365 6549836 : loop->body_list = node_info;
366 : }
367 8673484 : }
368 :
369 622379 : 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 622379 : if (loops_found_ == 0) return;
375 265619 : if (loops_found_ == 1) return FinishSingleLoop();
376 :
377 713584 : 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 16321119 : for (NodeInfo& ni : info_) {
382 15847275 : if (ni.node == nullptr) continue;
383 :
384 : LoopInfo* innermost = nullptr;
385 : int innermost_index = 0;
386 8923393 : int pos = ni.node->id() * width_;
387 : // Search the marks word by word.
388 18013242 : for (int i = 0; i < width_; i++) {
389 9089849 : uint32_t marks = backward_[pos + i] & forward_[pos + i];
390 299965017 : for (int j = 0; j < 32; j++) {
391 290875168 : if (marks & (1u << j)) {
392 8563914 : int loop_num = i * 32 + j;
393 8563914 : if (loop_num == 0) continue;
394 8563914 : LoopInfo* loop = &loops_[loop_num - 1];
395 10937746 : if (innermost == nullptr ||
396 2373832 : loop->loop->depth_ > innermost->loop->depth_) {
397 : innermost = loop;
398 : innermost_index = loop_num;
399 : }
400 : }
401 : }
402 : }
403 8923393 : if (innermost == nullptr) continue;
404 6190082 : AddNodeToLoop(&ni, innermost, innermost_index);
405 6190082 : count++;
406 : }
407 :
408 : // Serialize the node lists for loops into the loop tree.
409 236922 : loop_tree_->loop_nodes_.reserve(count);
410 956586 : for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
411 245820 : SerializeLoop(loop);
412 : }
413 : }
414 :
415 : // Handle the simpler case of a single loop (no checks for nesting necessary).
416 28697 : void FinishSingleLoop() {
417 : // Place nodes into the loop header and body.
418 28697 : LoopInfo* li = &loops_[0];
419 28697 : li->loop = &loop_tree_->all_loops_[0];
420 28697 : loop_tree_->SetParent(nullptr, li->loop);
421 : size_t count = 0;
422 9363706 : for (NodeInfo& ni : info_) {
423 15343559 : if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
424 2483402 : AddNodeToLoop(&ni, li, 1);
425 2483402 : count++;
426 : }
427 :
428 : // Serialize the node lists for the loop into the loop tree.
429 28697 : loop_tree_->loop_nodes_.reserve(count);
430 28697 : SerializeLoop(li->loop);
431 28697 : }
432 :
433 : // Recursively serialize the list of header nodes and body nodes
434 : // so that nested loops occupy nested intervals.
435 742281 : void SerializeLoop(LoopTree::Loop* loop) {
436 742281 : int loop_num = loop_tree_->LoopNum(loop);
437 742281 : LoopInfo& li = loops_[loop_num - 1];
438 :
439 : // Serialize the header.
440 3711405 : loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
441 2363255 : for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
442 1620974 : loop_tree_->loop_nodes_.push_back(ni->node);
443 11915432 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
444 : }
445 :
446 : // Serialize the body.
447 1484562 : loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
448 7292117 : for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
449 6549836 : loop_tree_->loop_nodes_.push_back(ni->node);
450 19649508 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
451 : }
452 :
453 : // Serialize nested loops.
454 1952326 : for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
455 :
456 : // Serialize the exits.
457 1484562 : loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
458 1244955 : for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
459 502674 : loop_tree_->loop_nodes_.push_back(ni->node);
460 1508022 : loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
461 : }
462 :
463 1484562 : loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
464 742281 : }
465 :
466 : // Connect the LoopTree loops to their parents recursively.
467 1182291 : LoopTree::Loop* ConnectLoopTree(int loop_num) {
468 1182291 : LoopInfo& li = loops_[loop_num - 1];
469 1182291 : if (li.loop != nullptr) return li.loop;
470 :
471 713584 : NodeInfo& ni = info(li.header);
472 : LoopTree::Loop* parent = nullptr;
473 3152866 : for (int i = 1; i <= loops_found_; i++) {
474 2439282 : if (i == loop_num) continue;
475 3451396 : if (IsInLoop(ni.node, i)) {
476 : // recursively create potential parent loops first.
477 468707 : LoopTree::Loop* upper = ConnectLoopTree(i);
478 468707 : if (parent == nullptr || upper->depth_ > parent->depth_) {
479 : parent = upper;
480 : }
481 : }
482 : }
483 1427168 : li.loop = &loop_tree_->all_loops_[loop_num - 1];
484 713584 : loop_tree_->SetParent(parent, li.loop);
485 713584 : 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 1244758 : LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
508 : LoopTree* loop_tree =
509 622379 : new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
510 622379 : LoopFinderImpl finder(graph, loop_tree, zone);
511 622379 : finder.Run();
512 622379 : if (FLAG_trace_turbo_loop) {
513 0 : finder.Print();
514 : }
515 622379 : return loop_tree;
516 : }
517 :
518 :
519 2652 : Node* LoopTree::HeaderNode(Loop* loop) {
520 2652 : Node* first = *HeaderNodes(loop).begin();
521 2652 : if (first->opcode() == IrOpcode::kLoop) return first;
522 : DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
523 2652 : Node* header = NodeProperties::GetControlInput(first);
524 : DCHECK_EQ(IrOpcode::kLoop, header->opcode());
525 2652 : return header;
526 : }
527 :
528 : } // namespace compiler
529 : } // namespace internal
530 : } // namespace v8
|
