Lines Matching refs:Loop
5 #include "src/compiler/loop-analysis.h"
24 NodeInfo* next; // link in chaining loop members
28 // Temporary loop info needed during traversal and building the loop tree.
33 LoopTree::Loop* loop;
37 // Encapsulation of the loop finding algorithm.
39 // Conceptually, the contents of a loop are those nodes that are "between" the
40 // loop header and the backedges of the loop. Graphs in the soup of nodes can
41 // form improper cycles, so standard loop finding algorithms that work on CFGs
43 // either a {Loop} node or a phi. The {Loop} node itself and its accompanying
44 // phis are treated together as a set referred to here as the loop header.
45 // This loop finding algorithm works by traversing the graph in two directions,
47 // direction, from nodes to their uses, starting at loop headers.
48 // 1 bit per loop per node per direction are required during the marking phase.
50 // marks on edges into/out-of the loop header nodes.
96 PrintF("Loop %d headed at #%d\n", i, li.header->id());
100 for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
101 PrintLoop(loop);
178 // Propagate marks backward from loop headers.
191 // Setup loop headers first.
193 // found the loop node first.
207 // Only propagate the loop mark on backedges.
217 // Make a new loop if necessary for the given node.
225 // Create a new loop.
231 // Setup loop mark for phis attached to loop header.
321 // Place the node into the innermost nested loop of which it is a member.
335 LoopInfo* loop = &loops_[loop_num - 1];
337 loop->loop->depth_ > innermost->loop->depth_) {
338 innermost = loop;
355 // Serialize the node lists for loops into the loop tree.
357 for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
358 SerializeLoop(loop);
362 // Handle the simpler case of a single loop (no checks for nesting necessary).
364 // Place nodes into the loop header and body.
366 li->loop = &loop_tree_->all_loops_[0];
367 loop_tree_->SetParent(nullptr, li->loop);
381 // Serialize the node lists for the loop into the loop tree.
383 SerializeLoop(li->loop);
388 void SerializeLoop(LoopTree::Loop* loop) {
389 int loop_num = loop_tree_->LoopNum(loop);
393 loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
400 loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
407 for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
409 loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
413 LoopTree::Loop* ConnectLoopTree(int loop_num) {
415 if (li.loop != nullptr) return li.loop;
418 LoopTree::Loop* parent = nullptr;
423 LoopTree::Loop* upper = ConnectLoopTree(i);
429 li.loop = &loop_tree_->all_loops_[loop_num - 1];
430 loop_tree_->SetParent(parent, li.loop);
431 return li.loop;
434 void PrintLoop(LoopTree::Loop* loop) {
435 for (int i = 0; i < loop->depth_; i++) PrintF(" ");
436 PrintF("Loop depth = %d ", loop->depth_);
437 int i = loop->header_start_;
438 while (i < loop->body_start_) {
441 while (i < loop->body_end_) {
445 for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
462 Node* LoopTree::HeaderNode(Loop* loop) {
463 Node* first = *HeaderNodes(loop).begin();
