[turbofan] Improve loop analysis to handle more than 32 loops.

test/cctest/compiler/test-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/v8.h"
 
 #include "src/compiler/access-builder.h"
 #include "src/compiler/common-operator.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/graph-visualizer.h"
@@ skipping 128 matching lines @@
     CHECK_NE(NULL, loop);
 
     CHECK(header_count == static_cast<int>(loop->HeaderSize()));
     for (int i = 0; i < header_count; i++) {
       // Each header node should be in the loop.
       CHECK_EQ(loop, tree->ContainingLoop(header[i]));
       CheckRangeContains(tree->HeaderNodes(loop), header[i]);
     }
 
     CHECK_EQ(body_count, static_cast<int>(loop->BodySize()));
+    // TODO(turbofan): O(n^2) set equivalence in this test.
     for (int i = 0; i < body_count; i++) {
       // Each body node should be contained in the loop.
       CHECK(tree->Contains(loop, body[i]));
       CheckRangeContains(tree->BodyNodes(loop), body[i]);
     }
   }
 
   void CheckRangeContains(NodeRange range, Node* node) {
-    // O(n) ftw.
     CHECK_NE(range.end(), std::find(range.begin(), range.end(), node));
   }
 
   void CheckNestedLoops(Node** chain, int chain_count) {
     LoopTree* tree = GetLoopTree();
     for (int i = 0; i < chain_count; i++) {
       Node* header = chain[i];
       // Each header should be in a loop.
       LoopTree::Loop* loop = tree->ContainingLoop(header);
       CHECK_NE(NULL, loop);
       // Check parentage.
       LoopTree::Loop* parent =
           i == 0 ? NULL : tree->ContainingLoop(chain[i - 1]);
       CHECK_EQ(parent, loop->parent());
       for (int j = i - 1; j >= 0; j--) {
         // This loop should be nested inside all the outer loops.
         Node* outer_header = chain[j];
         LoopTree::Loop* outer = tree->ContainingLoop(outer_header);
         CHECK(tree->Contains(outer, header));
         CHECK(!tree->Contains(loop, outer_header));
       }
     }
   }
+
+  Zone* zone() { return main_zone(); }
 };
 
 
 struct While {
   LoopFinderTester& t;
   Node* branch;
   Node* if_true;
   Node* exit;
   Node* loop;
 
@@ skipping 641 matching lines @@
                    phi3,  cond3,   branch3,  if_true3};
   t.CheckLoop(header2, 2, body2, 9);
 
   Node* header3[] = {loop3, phi3};
   Node* body3[] = {cond3, branch3, if_true3};
   t.CheckLoop(header3, 2, body3, 3);
 }
 
 
 // Runs all combinations with a fixed {i}.
-void RunEdgeMatrix3_i(int i) {
+static void RunEdgeMatrix3_i(int i) {
   for (int a = 0; a < 1; a++) {
     for (int b = 0; b < 1; b++) {
       for (int c = 0; c < 4; c++) {
         for (int d = 0; d < 3; d++) {
           for (int e = 0; e < 3; e++) {
             for (int f = 0; f < 6; f++) {
               for (int g = 0; g < 5; g++) {
                 for (int h = 0; h < 5; h++) {
                   RunEdgeMatrix3(a, b, c, d, e, f, g, h, i);
                 }
@@ skipping 17 matching lines @@
 TEST(LaEdgeMatrix3_2) { RunEdgeMatrix3_i(2); }
 
 
 TEST(LaEdgeMatrix3_3) { RunEdgeMatrix3_i(3); }
 
 
 TEST(LaEdgeMatrix3_4) { RunEdgeMatrix3_i(4); }
 
 
 TEST(LaEdgeMatrix3_5) { RunEdgeMatrix3_i(5); }
+
+
+static void RunManyChainedLoops_i(int count) {
+  LoopFinderTester t;
+  Node** nodes = t.zone()->NewArray<Node*>(count * 4);
+  Node* k11 = t.jsgraph.Int32Constant(11);
+  Node* k12 = t.jsgraph.Int32Constant(12);
+  Node* last = t.start;
+
+  // Build loops.
+  for (int i = 0; i < count; i++) {
+    Node* loop = t.graph.NewNode(t.common.Loop(2), last, t.start);
+    Node* phi = t.graph.NewNode(t.common.Phi(kMachInt32, 2), k11, k12, loop);
+    Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop);
+    Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
+    Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
+    loop->ReplaceInput(1, if_true);
+
+    nodes[i * 4 + 0] = loop;
+    nodes[i * 4 + 1] = phi;
+    nodes[i * 4 + 2] = branch;
+    nodes[i * 4 + 3] = if_true;
+
+    last = exit;
+  }
+
+  Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, last);
+  t.graph.SetEnd(ret);
+
+  // Verify loops.
+  for (int i = 0; i < count; i++) {
+    t.CheckLoop(nodes + i * 4, 2, nodes + i * 4 + 2, 2);
+  }
+}
+
+
+static void RunManyNestedLoops_i(int count) {
+  LoopFinderTester t;
+  Node** nodes = t.zone()->NewArray<Node*>(count * 5);
+  Node* k11 = t.jsgraph.Int32Constant(11);
+  Node* k12 = t.jsgraph.Int32Constant(12);
+  Node* outer = nullptr;
+  Node* entry = t.start;
+
+  // Build loops.
+  for (int i = 0; i < count; i++) {
+    Node* loop = t.graph.NewNode(t.common.Loop(2), entry, t.start);
+    Node* phi = t.graph.NewNode(t.common.Phi(kMachInt32, 2), k11, k12, loop);
+    Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop);
+    Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
+    Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
+
+    nodes[i * 5 + 0] = exit;     // outside
+    nodes[i * 5 + 1] = loop;     // header
+    nodes[i * 5 + 2] = phi;      // header
+    nodes[i * 5 + 3] = branch;   // body
+    nodes[i * 5 + 4] = if_true;  // body
+
+    if (outer != nullptr) {
+      // inner loop.
+      outer->ReplaceInput(1, exit);
+    } else {
+      // outer loop.
+      Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, exit);
+      t.graph.SetEnd(ret);
+    }
+    outer = loop;
+    entry = if_true;
+  }
+  outer->ReplaceInput(1, entry);  // innermost loop.
+
+  // Verify loops.
+  for (int i = 0; i < count; i++) {
+    int k = i * 5;
+    t.CheckLoop(nodes + k + 1, 2, nodes + k + 3, count * 5 - k - 3);
+  }
+}
+
+
+TEST(LaManyChained_30) { RunManyChainedLoops_i(30); }
+TEST(LaManyChained_31) { RunManyChainedLoops_i(30); }

[Michael Starzinger, 2015/01/19 12:51:20]

nit: s/30/31/ here.

[titzer, 2015/01/19 12:54:49]

Done.

+TEST(LaManyChained_32) { RunManyChainedLoops_i(32); }
+TEST(LaManyChained_33) { RunManyChainedLoops_i(33); }
+TEST(LaManyChained_34) { RunManyChainedLoops_i(34); }
+TEST(LaManyChained_62) { RunManyChainedLoops_i(62); }
+TEST(LaManyChained_63) { RunManyChainedLoops_i(63); }
+TEST(LaManyChained_64) { RunManyChainedLoops_i(64); }
+
+TEST(LaManyNested_30) { RunManyNestedLoops_i(30); }
+TEST(LaManyNested_31) { RunManyNestedLoops_i(30); }

[Michael Starzinger, 2015/01/19 12:51:20]

nit: s/30/31/ here.

[titzer, 2015/01/19 12:54:49]

Done.

+TEST(LaManyNested_32) { RunManyNestedLoops_i(32); }
+TEST(LaManyNested_33) { RunManyNestedLoops_i(33); }
+TEST(LaManyNested_34) { RunManyNestedLoops_i(34); }
+TEST(LaManyNested_62) { RunManyNestedLoops_i(62); }
+TEST(LaManyNested_63) { RunManyNestedLoops_i(63); }
+TEST(LaManyNested_64) { RunManyNestedLoops_i(64); }