[turbofan] First version of loop analysis: loop finder on the soup of nodes.

src/compiler/loop-analysis.cc

+// Copyright 2013 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/graph.h"
+#include "src/compiler/loop-analysis.h"
+#include "src/compiler/node.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/zone.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+typedef uint32_t LoopMarks;
+
+
+// TODO(titzer): don't assume entry edges have a particular index.
+// TODO(titzer): use a BitMatrix to generalize this algorithm.
+static const size_t kMaxLoops = 31;
+static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.
+static const LoopMarks kVisited = 1;          // loop #0 is reserved.
+
+
+// Temporary information for each node during marking.
+struct NodeInfo {
+  Node* node;
+  NodeInfo* next;       // link in chaining loop members
+  LoopMarks forward;    // accumulated marks in the forward direction
+  LoopMarks backward;   // accumulated marks in the backward direction
+  LoopMarks loop_mark;  // loop mark for header nodes; encodes loop_num
+
+  bool MarkBackward(LoopMarks bw) {
+    LoopMarks prev = backward;
+    LoopMarks next = backward | bw;
+    backward = next;
+    return prev != next;
+  }
+
+  bool MarkForward(LoopMarks fw) {
+    LoopMarks prev = forward;
+    LoopMarks next = forward | fw;
+    forward = next;
+    return prev != next;
+  }
+
+  bool IsInLoop(size_t loop_num) {
+    DCHECK(loop_num > 0 && loop_num <= 31);
+    return forward & backward & (1 << loop_num);
+  }
+
+  bool IsLoopHeader() { return loop_mark != 0; }
+  bool IsInAnyLoop() { return (forward & backward) > kVisited; }
+
+  bool IsInHeaderForLoop(size_t loop_num) {
+    DCHECK(loop_num > 0);
+    return loop_mark == (kVisited | (1 << loop_num));
+  }
+};
+
+
+// Temporary loop info needed during traversal and building the loop tree.
+struct LoopInfo {
+  Node* header;
+  NodeInfo* header_list;
+  NodeInfo* body_list;
+  LoopTree::Loop* loop;
+};
+
+
+static const NodeInfo kEmptyNodeInfo = {nullptr, nullptr, 0, 0, 0};
+
+
+// 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
+// aren't sufficient. However, in valid TurboFan graphs, all cycles involve
+// either a {Loop} node or a phi. The {Loop} node itself and its accompanying
+// phis are treated together as a set referred to here as the loop header.
+// This loop finding algorithm works by traversing the graph in two directions,
+// first from nodes to their inputs, starting at {end}, then in the reverse
+// direction, from nodes to their uses, starting at loop headers.
+// 1 bit per loop per node per direction are required during the marking phase.
+// To handle nested loops correctly, the algorithm must filter some reachability
+// marks on edges into/out-of the loop header nodes.
+class LoopFinderImpl {
+ public:
+  LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone)
+      : end_(graph->end()),
+        queue_(zone),
+        queued_(graph, 2),
+        info_(graph->NodeCount(), kEmptyNodeInfo, zone),
+        loops_(zone),
+        loop_tree_(loop_tree),
+        loops_found_(0) {}
+
+  void Run() {
+    PropagateBackward();
+    PropagateForward();
+    FinishLoopTree();
+  }
+
+  void Print() {
+    // Print out the results.
+    for (NodeInfo& ni : info_) {
+      if (ni.node == nullptr) continue;
+      for (size_t i = 1; i <= loops_.size(); i++) {
+        if (ni.IsInLoop(i)) {
+          PrintF("X");
+        } else if (ni.forward & (1 << i)) {
+          PrintF("/");
+        } else if (ni.backward & (1 << i)) {
+          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());
+      i++;
+    }
+
+    for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
+      PrintLoop(loop);
+    }
+  }
+
+ private:
+  Node* end_;
+  NodeDeque queue_;
+  NodeMarker<bool> queued_;
+  ZoneVector<NodeInfo> info_;
+  ZoneVector<LoopInfo> loops_;
+  LoopTree* loop_tree_;
+  size_t loops_found_;
+
+  // Propagate marks backward from loop headers.
+  void PropagateBackward() {
+    PropagateBackward(end_, kVisited);
+
+    while (!queue_.empty()) {
+      Node* node = queue_.front();
+      queue_.pop_front();
+      queued_.Set(node, false);
+
+      // Setup loop headers first.
+      if (node->opcode() == IrOpcode::kLoop) {
+        // found the loop node first.
+        CreateLoopInfo(node);
+      } else if (node->opcode() == IrOpcode::kPhi ||
+                 node->opcode() == IrOpcode::kEffectPhi) {
+        // found a phi first.
+        Node* merge = node->InputAt(node->InputCount() - 1);
+        if (merge->opcode() == IrOpcode::kLoop) CreateLoopInfo(merge);
+      }
+
+      // Propagate reachability marks backwards from this node.
+      NodeInfo& ni = info(node);
+      if (ni.IsLoopHeader()) {
+        // Handle edges from loop header nodes specially.
+        for (int i = 0; i < node->InputCount(); i++) {
+          if (i == kAssumedLoopEntryIndex) {
+            // Don't propagate the loop mark backwards on the entry edge.
+            PropagateBackward(node->InputAt(0),
+                              kVisited | (ni.backward & ~ni.loop_mark));
+          } else {
+            // Only propagate the loop mark on backedges.
+            PropagateBackward(node->InputAt(i), ni.loop_mark);
+          }
+        }
+      } else {
+        // Propagate all loop marks backwards for a normal node.
+        for (Node* const input : node->inputs()) {
+          PropagateBackward(input, ni.backward);
+        }
+      }
+    }
+  }
+
+  // Make a new loop header for the given node.
+  void CreateLoopInfo(Node* node) {
+    NodeInfo& ni = info(node);
+    if (ni.IsLoopHeader()) return;  // loop already set up.
+
+    loops_found_++;
+    size_t loop_num = loops_.size() + 1;
+    CHECK(loops_found_ <= kMaxLoops);  // TODO(titzer): don't crash.
+    // Create a new loop.
+    loops_.push_back({node, nullptr, nullptr, nullptr});
+    loop_tree_->NewLoop();
+    LoopMarks loop_mark = kVisited | (1 << loop_num);
+    ni.node = node;
+    ni.loop_mark = loop_mark;
+
+    // Setup loop mark for phis attached to loop header.
+    for (Node* use : node->uses()) {
+      if (use->opcode() == IrOpcode::kPhi ||
+          use->opcode() == IrOpcode::kEffectPhi) {
+        info(use).loop_mark = loop_mark;
+      }
+    }
+  }
+
+  // Propagate marks forward from loops.
+  void PropagateForward() {
+    for (LoopInfo& li : loops_) {
+      queued_.Set(li.header, true);
+      queue_.push_back(li.header);
+      NodeInfo& ni = info(li.header);
+      ni.forward = ni.loop_mark;
+    }
+    // Propagate forward on paths that were backward reachable from backedges.
+    while (!queue_.empty()) {
+      Node* node = queue_.front();
+      queue_.pop_front();
+      queued_.Set(node, false);
+      NodeInfo& ni = info(node);
+      for (Edge edge : node->use_edges()) {
+        Node* use = edge.from();
+        NodeInfo& ui = info(use);
+        if (IsBackedge(use, ui, edge)) continue;  // skip backedges.
+        LoopMarks both = ni.forward & ui.backward;
+        if (ui.MarkForward(both) && !queued_.Get(use)) {
+          queued_.Set(use, true);
+          queue_.push_back(use);
+        }
+      }
+    }
+  }
+
+  bool IsBackedge(Node* use, NodeInfo& ui, Edge& edge) {
+    // TODO(titzer): checking for backedges here is ugly.
+    if (!ui.IsLoopHeader()) return false;
+    if (edge.index() == kAssumedLoopEntryIndex) return false;
+    if (use->opcode() == IrOpcode::kPhi ||
+        use->opcode() == IrOpcode::kEffectPhi) {
+      return !NodeProperties::IsControlEdge(edge);
+    }
+    return true;
+  }
+
+  NodeInfo& info(Node* node) {
+    NodeInfo& i = info_[node->id()];
+    if (i.node == nullptr) i.node = node;
+    return i;
+  }
+
+  void PropagateBackward(Node* node, LoopMarks marks) {
+    if (info(node).MarkBackward(marks) && !queued_.Get(node)) {
+      queue_.push_back(node);
+      queued_.Set(node, true);
+    }
+  }
+
+  void FinishLoopTree() {
+    // Degenerate cases.
+    if (loops_.size() == 0) return;
+    if (loops_.size() == 1) return FinishSingleLoop();
+
+    for (size_t i = 1; i <= loops_.size(); i++) ConnectLoopTree(i);
+
+    size_t count = 0;
+    // Place the node into the innermost nested loop of which it is a member.
+    for (NodeInfo& ni : info_) {
+      if (ni.node == nullptr || !ni.IsInAnyLoop()) continue;
+
+      LoopInfo* innermost = nullptr;
+      size_t index = 0;
+      for (size_t i = 1; i <= loops_.size(); i++) {
+        if (ni.IsInLoop(i)) {
+          LoopInfo* loop = &loops_[i - 1];
+          if (innermost == nullptr ||
+              loop->loop->depth_ > innermost->loop->depth_) {
+            innermost = loop;
+            index = i;
+          }
+        }
+      }
+      if (ni.IsInHeaderForLoop(index)) {
+        ni.next = innermost->header_list;
+        innermost->header_list = &ni;
+      } else {
+        ni.next = innermost->body_list;
+        innermost->body_list = &ni;
+      }
+      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() {
+    DCHECK(loops_.size() == 1);
+    DCHECK(loop_tree_->all_loops_.size() == 1);
+
+    // 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 || !ni.IsInAnyLoop()) continue;
+      DCHECK(ni.IsInLoop(1));
+      if (ni.IsInHeaderForLoop(1)) {
+        ni.next = li->header_list;
+        li->header_list = &ni;
+      } else {
+        ni.next = li->body_list;
+        li->body_list = &ni;
+      }
+      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.
+  void SerializeLoop(LoopTree::Loop* loop) {
+    size_t loop_num = loop_tree_->LoopNum(loop);
+    LoopInfo& li = loops_[loop_num - 1];
+
+    // Serialize the header.
+    loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
+    for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
+      loop_tree_->loop_nodes_.push_back(ni->node);
+      // TODO(titzer): lift loop count restriction.
+      loop_tree_->node_to_loop_num_[ni->node->id()] =
+          static_cast<uint8_t>(loop_num);
+    }
+
+    // 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);
+      // TODO(titzer): lift loop count restriction.
+      loop_tree_->node_to_loop_num_[ni->node->id()] =
+          static_cast<uint8_t>(loop_num);
+    }
+
+    // Serialize nested loops.
+    for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
+
+    loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
+  }
+
+  // Connect the LoopTree loops to their parents recursively.
+  LoopTree::Loop* ConnectLoopTree(size_t 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 (size_t i = 1; i <= loops_.size(); i++) {
+      if (i == loop_num) continue;
+      if (ni.IsInLoop(i)) {
+        // recursively create potential parent loops first.
+        LoopTree::Loop* upper = ConnectLoopTree(i);
+        if (parent == nullptr || upper->depth_ > parent->depth_) {
+          parent = upper;
+        }
+      }
+    }
+    li.loop = &loop_tree_->all_loops_[loop_num - 1];
+    loop_tree_->SetParent(parent, li.loop);
+    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_) {
+      PrintF(" B#%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);
+  finder.Run();
+  if (FLAG_trace_turbo_graph) {
+    finder.Print();
+  }
+  return loop_tree;
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8