[turbofan] Loop peeling with explicit loop exits.

src/compiler/loop-analysis.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/loop-analysis.h"
 
 #include "src/compiler/graph.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-marker.h"
 #include "src/compiler/node-properties.h"
@@ skipping 11 matching lines @@
 struct NodeInfo {
   Node* node;
   NodeInfo* next;       // link in chaining loop members
 };
 
 
 // Temporary loop info needed during traversal and building the loop tree.
 struct LoopInfo {
   Node* header;
   NodeInfo* header_list;
+  NodeInfo* exit_list;
   NodeInfo* body_list;
   LoopTree::Loop* loop;
 };
 
 
 // Encapsulation of the loop finding algorithm.
 // -----------------------------------------------------------------------------
 // Conceptually, the contents of a loop are those nodes that are "between" the
 // loop header and the backedges of the loop. Graphs in the soup of nodes can
 // form improper cycles, so standard loop finding algorithms that work on CFGs
@@ skipping 32 matching lines @@
     // Print out the results.
     for (NodeInfo& ni : info_) {
       if (ni.node == nullptr) continue;
       for (int i = 1; i <= loops_found_; i++) {
         int index = ni.node->id() * width_ + INDEX(i);
         bool marked_forward = forward_[index] & BIT(i);
         bool marked_backward = backward_[index] & BIT(i);
         if (marked_forward && marked_backward) {
           PrintF("X");
         } else if (marked_forward) {
-          PrintF("/");
+          PrintF(">");
         } else if (marked_backward) {
-          PrintF("\\");
+          PrintF("<");
         } else {
           PrintF(" ");
         }
       }
       PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
     }
 
     int i = 0;
     for (LoopInfo& li : loops_) {
       PrintF("Loop %d headed at #%d\n", i, li.header->id());
@@ skipping 94 matching lines @@
       // Setup loop headers first.
       if (node->opcode() == IrOpcode::kLoop) {
         // found the loop node first.
         loop_num = CreateLoopInfo(node);
       } else if (NodeProperties::IsPhi(node)) {
         // found a phi first.
         Node* merge = node->InputAt(node->InputCount() - 1);
         if (merge->opcode() == IrOpcode::kLoop) {
           loop_num = CreateLoopInfo(merge);
         }
+      } else if (node->opcode() == IrOpcode::kLoopExit) {
+        // Intentionally ignore return value. Loop exit node marks
+        // are propagated normally.
+        CreateLoopInfo(node->InputAt(1));
+      } else if (node->opcode() == IrOpcode::kLoopExitValue ||
+                 node->opcode() == IrOpcode::kLoopExitEffect) {
+        Node* loop_exit = NodeProperties::GetControlInput(node);
+        // Intentionally ignore return value. Loop exit node marks
+        // are propagated normally.
+        CreateLoopInfo(loop_exit->InputAt(1));
       }
 
       // Propagate marks backwards from this node.
       for (int i = 0; i < node->InputCount(); i++) {
         Node* input = node->InputAt(i);
-        if (loop_num > 0 && i != kAssumedLoopEntryIndex) {
+        if (IsBackedge(node, i)) {
           // Only propagate the loop mark on backedges.
           if (SetBackwardMark(input, loop_num)) Queue(input);
         } else {
           // Entry or normal edge. Propagate all marks except loop_num.
           if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
         }
       }
     }
   }
 
   // Make a new loop if necessary for the given node.
   int CreateLoopInfo(Node* node) {
+    DCHECK_EQ(IrOpcode::kLoop, node->opcode());
     int loop_num = LoopNum(node);
     if (loop_num > 0) return loop_num;
 
     loop_num = ++loops_found_;
     if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
 
     // Create a new loop.
-    loops_.push_back({node, nullptr, nullptr, nullptr});
+    loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
     loop_tree_->NewLoop();
-    SetBackwardMark(node, loop_num);
-    loop_tree_->node_to_loop_num_[node->id()] = loop_num;
-
-    // Setup loop mark for phis attached to loop header.
-    for (Node* use : node->uses()) {
-      if (NodeProperties::IsPhi(use)) {
-        info(use);  // create the NodeInfo
-        SetBackwardMark(use, loop_num);
-        loop_tree_->node_to_loop_num_[use->id()] = loop_num;
-      }
-    }
-
+    SetLoopMarkForLoopHeader(node, loop_num);
     return loop_num;
   }
 
+  void SetLoopMark(Node* node, int loop_num) {
+    info(node);  // create the NodeInfo
+    SetBackwardMark(node, loop_num);
+    loop_tree_->node_to_loop_num_[node->id()] = loop_num;
+  }
+
+  void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
+    DCHECK_EQ(IrOpcode::kLoop, node->opcode());
+    SetLoopMark(node, loop_num);
+    for (Node* use : node->uses()) {
+      if (NodeProperties::IsPhi(use)) {
+        SetLoopMark(use, loop_num);
+      }
+
+      // Do not keep the loop alive if it does not have any backedges.
+      if (node->InputCount() <= 1) continue;
+
+      if (use->opcode() == IrOpcode::kLoopExit) {
+        SetLoopMark(use, loop_num);
+        for (Node* exit_use : use->uses()) {
+          if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
+              exit_use->opcode() == IrOpcode::kLoopExitEffect) {
+            SetLoopMark(exit_use, loop_num);
+          }
+        }
+      }
+    }
+  }
+
   void ResizeBackwardMarks() {
     int new_width = width_ + 1;
     int max = num_nodes();
     uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
     memset(new_backward, 0, new_width * max * sizeof(uint32_t));
     if (width_ > 0) {  // copy old matrix data.
       for (int i = 0; i < max; i++) {
         uint32_t* np = &new_backward[i * new_width];
         uint32_t* op = &backward_[i * width_];
         for (int j = 0; j < width_; j++) np[j] = op[j];
@@ skipping 16 matching lines @@
       SetForwardMark(li.header, LoopNum(li.header));
       Queue(li.header);
     }
     // Propagate forward on paths that were backward reachable from backedges.
     while (!queue_.empty()) {
       Node* node = queue_.front();
       queue_.pop_front();
       queued_.Set(node, false);
       for (Edge edge : node->use_edges()) {
         Node* use = edge.from();
-        if (!IsBackedge(use, edge)) {
+        if (!IsBackedge(use, edge.index())) {
           if (PropagateForwardMarks(node, use)) Queue(use);
         }
       }
     }
   }
 
-  bool IsBackedge(Node* use, Edge& edge) {
+  bool IsLoopHeaderNode(Node* node) {
+    return node->opcode() == IrOpcode::kLoop || NodeProperties::IsPhi(node);
+  }
+
+  bool IsLoopExitNode(Node* node) {
+    return node->opcode() == IrOpcode::kLoopExit ||
+           node->opcode() == IrOpcode::kLoopExitValue ||
+           node->opcode() == IrOpcode::kLoopExitEffect;
+  }
+
+  bool IsBackedge(Node* use, int index) {
     if (LoopNum(use) <= 0) return false;
-    if (edge.index() == kAssumedLoopEntryIndex) return false;
     if (NodeProperties::IsPhi(use)) {
-      return !NodeProperties::IsControlEdge(edge);
+      return index != NodeProperties::FirstControlIndex(use) &&
+             index != kAssumedLoopEntryIndex;
+    } else if (use->opcode() == IrOpcode::kLoop) {
+      return index != kAssumedLoopEntryIndex;
     }
-    return true;
+    DCHECK(IsLoopExitNode(use));
+    return false;
   }
 
   int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
 
   NodeInfo& info(Node* node) {
     NodeInfo& i = info_[node->id()];
     if (i.node == nullptr) i.node = node;
     return i;
   }
 
   void Queue(Node* node) {
     if (!queued_.Get(node)) {
       queue_.push_back(node);
       queued_.Set(node, true);
     }
   }
 
+  void AddNodeToLoop(NodeInfo* node_info, LoopInfo* loop, int loop_num) {
+    if (LoopNum(node_info->node) == loop_num) {
+      if (IsLoopHeaderNode(node_info->node)) {
+        node_info->next = loop->header_list;
+        loop->header_list = node_info;
+      } else {
+        DCHECK(IsLoopExitNode(node_info->node));
+        node_info->next = loop->exit_list;
+        loop->exit_list = node_info;
+      }
+    } else {
+      node_info->next = loop->body_list;
+      loop->body_list = node_info;
+    }
+  }
+
   void FinishLoopTree() {
     DCHECK(loops_found_ == static_cast<int>(loops_.size()));
     DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));
 
     // Degenerate cases.
     if (loops_found_ == 0) return;
     if (loops_found_ == 1) return FinishSingleLoop();
 
     for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i);
 
@@ skipping 15 matching lines @@
             LoopInfo* loop = &loops_[loop_num - 1];
             if (innermost == nullptr ||
                 loop->loop->depth_ > innermost->loop->depth_) {
               innermost = loop;
               innermost_index = loop_num;
             }
           }
         }
       }
       if (innermost == nullptr) continue;
-      if (LoopNum(ni.node) == innermost_index) {
-        ni.next = innermost->header_list;
-        innermost->header_list = &ni;
-      } else {
-        ni.next = innermost->body_list;
-        innermost->body_list = &ni;
-      }
+      AddNodeToLoop(&ni, innermost, innermost_index);
       count++;
     }
 
     // Serialize the node lists for loops into the loop tree.
     loop_tree_->loop_nodes_.reserve(count);
     for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
       SerializeLoop(loop);
     }
   }
 
   // Handle the simpler case of a single loop (no checks for nesting necessary).
   void FinishSingleLoop() {
     // Place nodes into the loop header and body.
     LoopInfo* li = &loops_[0];
     li->loop = &loop_tree_->all_loops_[0];
     loop_tree_->SetParent(nullptr, li->loop);
     size_t count = 0;
     for (NodeInfo& ni : info_) {
       if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
-      if (LoopNum(ni.node) == 1) {
-        ni.next = li->header_list;
-        li->header_list = &ni;
-      } else {
-        ni.next = li->body_list;
-        li->body_list = &ni;
-      }
+      AddNodeToLoop(&ni, li, 1);
       count++;
     }
 
     // Serialize the node lists for the loop into the loop tree.
     loop_tree_->loop_nodes_.reserve(count);
     SerializeLoop(li->loop);
   }
 
   // Recursively serialize the list of header nodes and body nodes
   // so that nested loops occupy nested intervals.
@@ skipping 11 matching lines @@
     // Serialize the body.
     loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
     for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
       loop_tree_->loop_nodes_.push_back(ni->node);
       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
     }
 
     // Serialize nested loops.
     for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
 
-    loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
+    // Serialize the exits.
+    loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
+    for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
+      loop_tree_->loop_nodes_.push_back(ni->node);
+      loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
+    }
+
+    loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
   }
 
   // Connect the LoopTree loops to their parents recursively.
   LoopTree::Loop* ConnectLoopTree(int loop_num) {
     LoopInfo& li = loops_[loop_num - 1];
     if (li.loop != nullptr) return li.loop;
 
     NodeInfo& ni = info(li.header);
     LoopTree::Loop* parent = nullptr;
     for (int i = 1; i <= loops_found_; i++) {
@@ skipping 11 matching lines @@
     return li.loop;
   }
 
   void PrintLoop(LoopTree::Loop* loop) {
     for (int i = 0; i < loop->depth_; i++) PrintF("  ");
     PrintF("Loop depth = %d ", loop->depth_);
     int i = loop->header_start_;
     while (i < loop->body_start_) {
       PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
     }
-    while (i < loop->body_end_) {
+    while (i < loop->exits_start_) {
       PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
     }
+    while (i < loop->exits_end_) {
+      PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id());
+    }
     PrintF("\n");
     for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
   }
 };
 
 
 LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
   LoopTree* loop_tree =
       new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
   LoopFinderImpl finder(graph, loop_tree, zone);
@@ skipping 10 matching lines @@
   if (first->opcode() == IrOpcode::kLoop) return first;
   DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
   Node* header = NodeProperties::GetControlInput(first);
   DCHECK_EQ(IrOpcode::kLoop, header->opcode());
   return header;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8