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

src/compiler/loop-analysis.h

Index: src/compiler/loop-analysis.h
diff --git a/src/compiler/loop-analysis.h b/src/compiler/loop-analysis.h
new file mode 100644
index 0000000000000000000000000000000000000000..66958f71f16ad9c7d4feaadbc2aa6c017207d1f0
--- /dev/null
+++ b/src/compiler/loop-analysis.h
@@ -0,0 +1,128 @@
+// 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.
+
+#ifndef V8_COMPILER_LOOP_ANALYSIS_H_
+#define V8_COMPILER_LOOP_ANALYSIS_H_
+
+#include "src/compiler/graph.h"
+#include "src/compiler/node.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class LoopFinderImpl;
+
+// Represents a tree of loops in a graph.
+class LoopTree : public ZoneObject {
+ public:
+  LoopTree(size_t num_nodes, Zone* zone)
+      : zone_(zone),
+        outer_loops_(zone),
+        all_loops_(zone),
+        node_to_loop_num_(num_nodes, 0, zone),
+        loop_nodes_(zone) {}
+
+  // Represents a loop in the tree of loops, including the header nodes,
+  // the body, and any nested loops.
+  class Loop {
+   public:
+    Loop* parent() { return parent_; }

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:09]

Done.

+    const ZoneVector<Loop*>& children() const { return children_; }
+    size_t HeaderSize() { return body_start_ - header_start_; }

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:09]

Done.

+    size_t BodySize() { return body_end_ - body_start_; }

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:09]

Done.

+    size_t TotalSize() { return body_end_ - header_start_; }

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:10]

Done.

+
+   private:
+    friend class LoopTree;
+    friend class LoopFinderImpl;
+
+    explicit Loop(Zone* zone)
+        : parent_(NULL),

[Benedikt Meurer, 2014/12/16 06:10:25]

Please use type-safe nullptr instead of NULL for newly written code, in line
with the Chromium/Google style guides.

[titzer, 2014/12/16 07:55:10]

Done.

+          depth_(0),
+          children_(zone),
+          header_start_(-1),
+          body_start_(-1),
+          body_end_(-1) {}
+    Loop* parent_;
+    int depth_;
+    ZoneVector<Loop*> children_;
+    int header_start_;
+    int body_start_;
+    int body_end_;
+  };
+
+  // Return the innermost nested loop, if any, that contains {node}.
+  Loop* ContainingLoop(Node* node) {

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:10]

Const starts to spread like a virus from this site, so I'll skip this one if you
don't mind.

+    if (node->id() >= static_cast<int>(node_to_loop_num_.size())) return NULL;
+    uint8_t num = node_to_loop_num_[node->id()];
+    return num > 0 ? &all_loops_[num - 1] : NULL;
+  }
+
+  // Check if the {loop} contains the {node}, either directly or by containing
+  // a nested loop that contains {node}.
+  bool Contains(Loop* loop, Node* node) {

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:10]

Same as above.

+    for (Loop* c = ContainingLoop(node); c != NULL; c = c->parent_) {
+      if (c == loop) return true;
+    }
+    return false;
+  }
+
+  // Return the list of outer loops.
+  const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }
+
+  // Return the unique loop number for a given loop. Loop numbers start at {1}.
+  int LoopNum(Loop* loop) {

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[Benedikt Meurer, 2014/12/16 06:10:25]

Nit: const.

[titzer, 2014/12/16 07:55:09]

Done.

[titzer, 2014/12/16 07:55:10]

Done.

+    return 1 + static_cast<int>(loop - &all_loops_[0]);
+  }
+
+  PtrRange<Node*> HeaderNodes(Loop* loop) {
+    return {&loop_nodes_[0] + loop->header_start_,
+            &loop_nodes_[0] + loop->body_start_};
+  }
+
+  PtrRange<Node*> BodyNodes(Loop* loop) {
+    return {&loop_nodes_[0] + loop->body_start_,
+            &loop_nodes_[0] + loop->body_end_};
+  }
+
+ private:
+  friend class LoopFinderImpl;
+
+  Loop* NewLoop() {
+    all_loops_.push_back(Loop(zone_));
+    Loop* result = &all_loops_.back();
+    return result;
+  }
+
+  void SetParent(Loop* parent, Loop* child) {
+    if (parent != NULL) {
+      parent->children_.push_back(child);
+      child->parent_ = parent;
+      child->depth_ = parent->depth_ + 1;
+    } else {
+      outer_loops_.push_back(child);
+    }
+  }
+
+  Zone* zone_;
+  ZoneVector<Loop*> outer_loops_;
+  ZoneVector<Loop> all_loops_;
+  ZoneVector<uint8_t> node_to_loop_num_;
+  ZoneVector<Node*> loop_nodes_;
+};
+
+
+class LoopFinder {
+ public:
+  // Build a loop tree for the entire graph.
+  static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone);
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_LOOP_ANALYSIS_H_