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

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"
+#include "src/compiler/js-graph.h"
+#include "src/compiler/js-operator.h"
+#include "src/compiler/loop-analysis.h"
+#include "src/compiler/node.h"
+#include "src/compiler/opcodes.h"
+#include "src/compiler/operator.h"
+#include "src/compiler/schedule.h"
+#include "src/compiler/scheduler.h"
+#include "src/compiler/simplified-operator.h"
+#include "src/compiler/verifier.h"
+#include "test/cctest/cctest.h"
+
+using namespace v8::internal;
+using namespace v8::internal::compiler;
+
+static Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
+                        0, 1, 0, 0);
+static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure,
+                       "Int32LessThan", 2, 0, 0, 1, 0, 0);
+static Operator kStore(IrOpcode::kStore, Operator::kNoProperties, "Store", 0, 2,
+                       1, 0, 1, 0);
+
+static const int kNumLeafs = 4;
+
+// A helper for all tests dealing with LoopFinder.
+class LoopFinderTester : HandleAndZoneScope {
+ public:
+  LoopFinderTester()
+      : isolate(main_isolate()),
+        common(main_zone()),
+        graph(main_zone()),
+        jsgraph(&graph, &common, NULL, NULL),
+        start(graph.NewNode(common.Start(1))),
+        end(graph.NewNode(common.End(), start)),
+        p0(graph.NewNode(common.Parameter(0), start)),
+        zero(jsgraph.Int32Constant(0)),
+        one(jsgraph.OneConstant()),
+        half(jsgraph.Constant(0.5)),
+        self(graph.NewNode(common.Int32Constant(0xaabbccdd))),
+        dead(graph.NewNode(common.Dead())),
+        loop_tree(NULL) {
+    graph.SetEnd(end);
+    graph.SetStart(start);
+    leaf[0] = zero;
+    leaf[1] = one;
+    leaf[2] = half;
+    leaf[3] = p0;
+  }
+
+  Isolate* isolate;
+  CommonOperatorBuilder common;
+  Graph graph;
+  JSGraph jsgraph;
+  Node* start;
+  Node* end;
+  Node* p0;
+  Node* zero;
+  Node* one;
+  Node* half;
+  Node* self;
+  Node* dead;
+  Node* leaf[kNumLeafs];
+  LoopTree* loop_tree;
+
+  Node* Phi(Node* a) {
+    return SetSelfReferences(graph.NewNode(op(1, false), a, start));
+  }
+
+  Node* Phi(Node* a, Node* b) {
+    return SetSelfReferences(graph.NewNode(op(2, false), a, b, start));
+  }
+
+  Node* Phi(Node* a, Node* b, Node* c) {
+    return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start));
+  }
+
+  Node* Phi(Node* a, Node* b, Node* c, Node* d) {
+    return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start));
+  }
+
+  Node* EffectPhi(Node* a) {
+    return SetSelfReferences(graph.NewNode(op(1, true), a, start));
+  }
+
+  Node* EffectPhi(Node* a, Node* b) {
+    return SetSelfReferences(graph.NewNode(op(2, true), a, b, start));
+  }
+
+  Node* EffectPhi(Node* a, Node* b, Node* c) {
+    return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start));
+  }
+
+  Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) {
+    return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start));
+  }
+
+  Node* SetSelfReferences(Node* node) {
+    for (Edge edge : node->input_edges()) {
+      if (edge.to() == self) node->ReplaceInput(edge.index(), node);
+    }
+    return node;
+  }
+
+  const Operator* op(int count, bool effect) {
+    return effect ? common.EffectPhi(count) : common.Phi(kMachAnyTagged, count);
+  }
+
+  Node* Return(Node* val, Node* effect, Node* control) {
+    Node* ret = graph.NewNode(common.Return(), val, effect, control);
+    end->ReplaceInput(0, ret);
+    return ret;
+  }
+
+  LoopTree* GetLoopTree() {
+    if (loop_tree == NULL) {
+      if (FLAG_trace_turbo_graph) {
+        OFStream os(stdout);
+        os << AsRPO(graph);
+      }
+      Zone zone(isolate);
+      loop_tree = LoopFinder::BuildLoopTree(&graph, &zone);
+    }
+    return loop_tree;
+  }
+
+  void CheckLoop(Node** header, int header_count, Node** body, int body_count) {
+    LoopTree* tree = GetLoopTree();
+    LoopTree::Loop* loop = tree->ContainingLoop(header[0]);
+    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()));
+    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(PtrRange<Node*> range, Node* node) {

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

As Sven mentioned, this is just std::find().

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

Done.

+    // O(n) ftw.
+    bool found = false;
+    for (Node* n : range)
+      if (n == node) return;
+    CHECK(found);  // not found.
+  }
+
+  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));
+      }
+    }
+  }
+};
+
+
+struct While {
+  LoopFinderTester& t;
+  Node* branch;
+  Node* if_true;
+  Node* exit;
+  Node* loop;
+
+  While(LoopFinderTester& R, Node* cond) : t(R) {
+    loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
+    branch = t.graph.NewNode(t.common.Branch(), cond, loop);
+    if_true = t.graph.NewNode(t.common.IfTrue(), branch);
+    exit = t.graph.NewNode(t.common.IfFalse(), branch);
+    loop->ReplaceInput(1, if_true);
+  }
+
+  void chain(Node* control) { loop->ReplaceInput(0, control); }
+  void nest(While& that) {
+    that.loop->ReplaceInput(1, exit);
+    this->loop->ReplaceInput(0, that.if_true);
+  }
+};
+
+
+struct Counter {
+  Node* base;
+  Node* inc;
+  Node* phi;
+  Node* add;
+
+  Counter(While& w, int32_t b, int32_t k)
+      : base(w.t.jsgraph.Int32Constant(b)), inc(w.t.jsgraph.Int32Constant(k)) {
+    Build(w);
+  }
+
+  Counter(While& w, Node* b, Node* k) : base(b), inc(k) { Build(w); }
+
+  void Build(While& w) {
+    phi = w.t.graph.NewNode(w.t.op(2, false), base, base, w.loop);
+    add = w.t.graph.NewNode(&kIntAdd, phi, inc);
+    phi->ReplaceInput(1, add);
+  }
+};
+
+
+struct StoreLoop {
+  Node* base;
+  Node* val;
+  Node* phi;
+  Node* store;
+
+  explicit StoreLoop(While& w)
+      : base(w.t.jsgraph.Int32Constant(12)),
+        val(w.t.jsgraph.Int32Constant(13)) {
+    Build(w);
+  }
+
+  StoreLoop(While& w, Node* b, Node* v) : base(b), val(v) { Build(w); }
+
+  void Build(While& w) {
+    phi = w.t.graph.NewNode(w.t.op(2, true), base, base, w.loop);
+    store = w.t.graph.NewNode(&kStore, phi, val, w.loop);
+    phi->ReplaceInput(1, store);
+  }
+};
+
+
+TEST(LaLoop1) {
+  // One loop.
+  LoopFinderTester t;
+  While w(t, t.p0);
+  t.Return(t.p0, t.start, w.exit);
+
+  Node* chain[] = {w.loop};
+  t.CheckNestedLoops(chain, 1);
+
+  Node* header[] = {w.loop};
+  Node* body[] = {w.branch, w.if_true};
+  t.CheckLoop(header, 1, body, 2);
+}
+
+
+TEST(LaLoop1c) {
+  // One loop with a counter.
+  LoopFinderTester t;
+  While w(t, t.p0);
+  Counter c(w, 0, 1);
+  t.Return(c.phi, t.start, w.exit);
+
+  Node* chain[] = {w.loop};
+  t.CheckNestedLoops(chain, 1);
+
+  Node* header[] = {w.loop, c.phi};
+  Node* body[] = {w.branch, w.if_true, c.add};
+  t.CheckLoop(header, 2, body, 3);
+}
+
+
+TEST(LaLoop1e) {
+  // One loop with an effect phi.
+  LoopFinderTester t;
+  While w(t, t.p0);
+  StoreLoop c(w);
+  t.Return(t.p0, c.phi, w.exit);
+
+  Node* chain[] = {w.loop};
+  t.CheckNestedLoops(chain, 1);
+
+  Node* header[] = {w.loop, c.phi};
+  Node* body[] = {w.branch, w.if_true, c.store};
+  t.CheckLoop(header, 2, body, 3);
+}
+
+
+TEST(LaLoop1d) {
+  // One loop with two counters.
+  LoopFinderTester t;
+  While w(t, t.p0);
+  Counter c1(w, 0, 1);
+  Counter c2(w, 1, 1);
+  t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w.exit);
+
+  Node* chain[] = {w.loop};
+  t.CheckNestedLoops(chain, 1);
+
+  Node* header[] = {w.loop, c1.phi, c2.phi};
+  Node* body[] = {w.branch, w.if_true, c1.add, c2.add};
+  t.CheckLoop(header, 3, body, 4);
+}
+
+
+TEST(LaLoop2) {
+  // One loop following another.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  w2.chain(w1.exit);
+  t.Return(t.p0, t.start, w2.exit);
+
+  {
+    Node* chain[] = {w1.loop};
+    t.CheckNestedLoops(chain, 1);
+
+    Node* header[] = {w1.loop};
+    Node* body[] = {w1.branch, w1.if_true};
+    t.CheckLoop(header, 1, body, 2);
+  }
+
+  {
+    Node* chain[] = {w2.loop};
+    t.CheckNestedLoops(chain, 1);
+
+    Node* header[] = {w2.loop};
+    Node* body[] = {w2.branch, w2.if_true};
+    t.CheckLoop(header, 1, body, 2);
+  }
+}
+
+
+TEST(LaLoop2c) {
+  // One loop following another, each with counters.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  Counter c1(w1, 0, 1);
+  Counter c2(w2, 0, 1);
+  w2.chain(w1.exit);
+  t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit);
+
+  {
+    Node* chain[] = {w1.loop};
+    t.CheckNestedLoops(chain, 1);
+
+    Node* header[] = {w1.loop, c1.phi};
+    Node* body[] = {w1.branch, w1.if_true, c1.add};
+    t.CheckLoop(header, 2, body, 3);
+  }
+
+  {
+    Node* chain[] = {w2.loop};
+    t.CheckNestedLoops(chain, 1);
+
+    Node* header[] = {w2.loop, c2.phi};
+    Node* body[] = {w2.branch, w2.if_true, c2.add};
+    t.CheckLoop(header, 2, body, 3);
+  }
+}
+
+
+TEST(LaLoop2cc) {
+  // One loop following another; second loop uses phi from first.
+  for (int i = 0; i < 8; i++) {
+    LoopFinderTester t;
+    While w1(t, t.p0);
+    While w2(t, t.p0);
+    Counter c1(w1, 0, 1);
+
+    // various usage scenarios for the second loop.
+    Counter c2(w2, i & 1 ? t.p0 : c1.phi, i & 2 ? t.p0 : c1.phi);
+    if (i & 3) w2.branch->ReplaceInput(0, c1.phi);
+
+    w2.chain(w1.exit);
+    t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit);
+
+    {
+      Node* chain[] = {w1.loop};
+      t.CheckNestedLoops(chain, 1);
+
+      Node* header[] = {w1.loop, c1.phi};
+      Node* body[] = {w1.branch, w1.if_true, c1.add};
+      t.CheckLoop(header, 2, body, 3);
+    }
+
+    {
+      Node* chain[] = {w2.loop};
+      t.CheckNestedLoops(chain, 1);
+
+      Node* header[] = {w2.loop, c2.phi};
+      Node* body[] = {w2.branch, w2.if_true, c2.add};
+      t.CheckLoop(header, 2, body, 3);
+    }
+  }
+}
+
+
+TEST(LaNestedLoop1) {
+  // One loop nested in another.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  w2.nest(w1);
+  t.Return(t.p0, t.start, w1.exit);
+
+  Node* chain[] = {w1.loop, w2.loop};
+  t.CheckNestedLoops(chain, 2);
+
+  Node* h1[] = {w1.loop};
+  Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, w2.exit};
+  t.CheckLoop(h1, 1, b1, 6);
+
+  Node* h2[] = {w2.loop};
+  Node* b2[] = {w2.branch, w2.if_true};
+  t.CheckLoop(h2, 1, b2, 2);
+}
+
+
+TEST(LaNestedLoop1c) {
+  // One loop nested in another, each with a counter.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  Counter c1(w1, 0, 1);
+  Counter c2(w2, 0, 1);
+  w2.branch->ReplaceInput(0, c2.phi);
+  w2.nest(w1);
+  t.Return(c1.phi, t.start, w1.exit);
+
+  Node* chain[] = {w1.loop, w2.loop};
+  t.CheckNestedLoops(chain, 2);
+
+  Node* h1[] = {w1.loop, c1.phi};
+  Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true,
+                w2.exit,   c2.phi,     c1.add,  c2.add};
+  t.CheckLoop(h1, 2, b1, 9);
+
+  Node* h2[] = {w2.loop, c2.phi};
+  Node* b2[] = {w2.branch, w2.if_true, c2.add};
+  t.CheckLoop(h2, 2, b2, 3);
+}
+
+
+TEST(LaNestedLoop2) {
+  // Two loops nested in an outer loop.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  While w3(t, t.p0);
+  w2.nest(w1);
+  w3.nest(w1);
+  w3.chain(w2.exit);
+  t.Return(t.p0, t.start, w1.exit);
+
+  Node* chain1[] = {w1.loop, w2.loop};
+  t.CheckNestedLoops(chain1, 2);
+
+  Node* chain2[] = {w1.loop, w3.loop};
+  t.CheckNestedLoops(chain2, 2);
+
+  Node* h1[] = {w1.loop};
+  Node* b1[] = {w1.branch, w1.if_true, w2.loop,   w2.branch,  w2.if_true,
+                w2.exit,   w3.loop,    w3.branch, w3.if_true, w3.exit};
+  t.CheckLoop(h1, 1, b1, 10);
+
+  Node* h2[] = {w2.loop};
+  Node* b2[] = {w2.branch, w2.if_true};
+  t.CheckLoop(h2, 1, b2, 2);
+
+  Node* h3[] = {w3.loop};
+  Node* b3[] = {w3.branch, w3.if_true};
+  t.CheckLoop(h3, 1, b3, 2);
+}
+
+
+TEST(LaNestedLoop3) {
+  // Three nested loops.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  While w2(t, t.p0);
+  While w3(t, t.p0);
+  w2.loop->ReplaceInput(0, w1.if_true);
+  w3.loop->ReplaceInput(0, w2.if_true);
+  w2.loop->ReplaceInput(1, w3.exit);
+  w1.loop->ReplaceInput(1, w2.exit);
+  t.Return(t.p0, t.start, w1.exit);
+
+  Node* chain[] = {w1.loop, w2.loop, w3.loop};
+  t.CheckNestedLoops(chain, 3);
+
+  Node* h1[] = {w1.loop};
+  Node* b1[] = {w1.branch, w1.if_true, w2.loop,   w2.branch,  w2.if_true,
+                w2.exit,   w3.loop,    w3.branch, w3.if_true, w3.exit};
+  t.CheckLoop(h1, 1, b1, 10);
+
+  Node* h2[] = {w2.loop};
+  Node* b2[] = {w2.branch, w2.if_true, w3.loop, w3.branch, w3.if_true, w3.exit};
+  t.CheckLoop(h2, 1, b2, 6);
+
+  Node* h3[] = {w3.loop};
+  Node* b3[] = {w3.branch, w3.if_true};
+  t.CheckLoop(h3, 1, b3, 2);
+}
+
+
+TEST(LaNestedLoop3c) {
+  // Three nested loops with counters.
+  LoopFinderTester t;
+  While w1(t, t.p0);
+  Counter c1(w1, 0, 1);
+  While w2(t, t.p0);
+  Counter c2(w2, 0, 1);
+  While w3(t, t.p0);
+  Counter c3(w3, 0, 1);
+  w2.loop->ReplaceInput(0, w1.if_true);
+  w3.loop->ReplaceInput(0, w2.if_true);
+  w2.loop->ReplaceInput(1, w3.exit);
+  w1.loop->ReplaceInput(1, w2.exit);
+  w1.branch->ReplaceInput(0, c1.phi);
+  w2.branch->ReplaceInput(0, c2.phi);
+  w3.branch->ReplaceInput(0, c3.phi);
+  t.Return(c1.phi, t.start, w1.exit);
+
+  Node* chain[] = {w1.loop, w2.loop, w3.loop};
+  t.CheckNestedLoops(chain, 3);
+
+  Node* h1[] = {w1.loop, c1.phi};
+  Node* b1[] = {w1.branch, w1.if_true, c1.add,    c2.add,     c2.add,
+                c2.phi,    c3.phi,     w2.loop,   w2.branch,  w2.if_true,
+                w2.exit,   w3.loop,    w3.branch, w3.if_true, w3.exit};
+  t.CheckLoop(h1, 2, b1, 15);
+
+  Node* h2[] = {w2.loop, c2.phi};
+  Node* b2[] = {w2.branch, w2.if_true, c2.add,     c3.add, c3.phi,
+                w3.loop,   w3.branch,  w3.if_true, w3.exit};
+  t.CheckLoop(h2, 2, b2, 9);
+
+  Node* h3[] = {w3.loop, c3.phi};
+  Node* b3[] = {w3.branch, w3.if_true, c3.add};
+  t.CheckLoop(h3, 2, b3, 3);
+}
+
+
+TEST(LaMultipleExit1) {
+  const int kMaxExits = 10;
+  Node* merge[1 + kMaxExits];
+  Node* body[2 * kMaxExits];
+
+  // A single loop with {i} exits.
+  for (int i = 1; i < kMaxExits; i++) {
+    LoopFinderTester t;
+    Node* cond = t.p0;
+
+    int merge_count = 0;
+    int body_count = 0;
+    Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
+    Node* last = loop;
+
+    for (int e = 0; e < i; e++) {
+      Node* branch = t.graph.NewNode(t.common.Branch(), cond, last);
+      Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
+      Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
+      last = if_true;
+
+      body[body_count++] = branch;
+      body[body_count++] = if_true;
+      merge[merge_count++] = exit;
+    }
+
+    loop->ReplaceInput(1, last);  // form loop backedge.
+    Node* end = t.graph.NewNode(t.common.Merge(i), i, merge);  // form exit.
+    t.graph.SetEnd(end);
+
+    Node* h[] = {loop};
+    t.CheckLoop(h, 1, body, body_count);
+  }
+}
+
+
+TEST(LaMultipleBackedge1) {
+  const int kMaxBackedges = 10;
+  Node* loop_inputs[1 + kMaxBackedges];
+  Node* body[3 * kMaxBackedges];
+
+  // A single loop with {i} backedges.
+  for (int i = 1; i < kMaxBackedges; i++) {
+    LoopFinderTester t;
+
+    for (int j = 0; j <= i; j++) loop_inputs[j] = t.start;
+    Node* loop = t.graph.NewNode(t.common.Loop(1 + i), 1 + i, loop_inputs);
+
+    Node* cond = t.p0;
+    int body_count = 0;
+    Node* exit = loop;
+
+    for (int b = 0; b < i; b++) {
+      Node* branch = t.graph.NewNode(t.common.Branch(), cond, exit);
+      Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
+      Node* if_false = t.graph.NewNode(t.common.IfFalse(), branch);
+      exit = if_false;
+
+      body[body_count++] = branch;
+      body[body_count++] = if_true;
+      if (b != (i - 1)) body[body_count++] = if_false;
+
+      loop->ReplaceInput(1 + b, if_true);
+    }
+
+    t.graph.SetEnd(exit);
+
+    Node* h[] = {loop};
+    t.CheckLoop(h, 1, body, body_count);
+  }
+}
+
+
+TEST(LaEdgeMatrix1) {
+  // Test various kinds of extra edges added to a simple loop.
+  for (int i = 0; i < 3; i++) {
+    for (int j = 0; j < 3; j++) {
+      for (int k = 0; k < 3; k++) {
+        LoopFinderTester t;
+
+        Node* p1 = t.jsgraph.Int32Constant(11);
+        Node* p2 = t.jsgraph.Int32Constant(22);
+        Node* p3 = t.jsgraph.Int32Constant(33);
+
+        Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
+        Node* phi =
+            t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop);
+        Node* cond = t.graph.NewNode(&kIntAdd, phi, p2);
+        Node* branch = t.graph.NewNode(t.common.Branch(), cond, 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);
+        Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit);
+        t.graph.SetEnd(ret);
+
+        Node* choices[] = {p1, phi, cond};
+        p1->ReplaceUses(choices[i]);
+        p2->ReplaceUses(choices[j]);
+        p3->ReplaceUses(choices[k]);
+
+        Node* header[] = {loop, phi};
+        Node* body[] = {cond, branch, if_true};
+        t.CheckLoop(header, 2, body, 3);
+      }
+    }
+  }
+}
+
+
+void RunEdgeMatrix2(int i) {
+  DCHECK(i >= 0 && i < 5);
+  for (int j = 0; j < 5; j++) {
+    for (int k = 0; k < 5; k++) {
+      LoopFinderTester t;
+
+      Node* p1 = t.jsgraph.Int32Constant(11);
+      Node* p2 = t.jsgraph.Int32Constant(22);
+      Node* p3 = t.jsgraph.Int32Constant(33);
+
+      // outer loop.
+      Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
+      Node* phi1 =
+          t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop1);
+      Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one);
+      Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1);
+      Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1);
+      Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1);
+
+      // inner loop.
+      Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start);
+      Node* phi2 =
+          t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p2, loop2);
+      Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3);
+      Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2);
+      Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2);
+      Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2);
+      loop2->ReplaceInput(1, if_true2);
+      loop1->ReplaceInput(1, exit2);
+
+      Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1);
+      t.graph.SetEnd(ret);
+
+      Node* choices[] = {p1, phi1, cond1, phi2, cond2};
+      p1->ReplaceUses(choices[i]);
+      p2->ReplaceUses(choices[j]);
+      p3->ReplaceUses(choices[k]);
+
+      Node* header1[] = {loop1, phi1};
+      Node* body1[] = {cond1, branch1, if_true1, exit2,   loop2,
+                       phi2,  cond2,   branch2,  if_true2};
+      t.CheckLoop(header1, 2, body1, 9);
+
+      Node* header2[] = {loop2, phi2};
+      Node* body2[] = {cond2, branch2, if_true2};
+      t.CheckLoop(header2, 2, body2, 3);
+
+      Node* chain[] = {loop1, loop2};
+      t.CheckNestedLoops(chain, 2);
+    }
+  }
+}
+
+
+TEST(LaEdgeMatrix2_0) { RunEdgeMatrix2(0); }
+
+
+TEST(LaEdgeMatrix2_1) { RunEdgeMatrix2(1); }
+
+
+TEST(LaEdgeMatrix2_2) { RunEdgeMatrix2(2); }
+
+
+TEST(LaEdgeMatrix2_3) { RunEdgeMatrix2(3); }
+
+
+TEST(LaEdgeMatrix2_4) { RunEdgeMatrix2(4); }
+
+
+// Generates a triply-nested loop with extra edges between the phis and
+// conditions according to the edge choice parameters.
+void RunEdgeMatrix3(int c1a, int c1b, int c1c,    // line break
+                    int c2a, int c2b, int c2c,    // line break
+                    int c3a, int c3b, int c3c) {  // line break
+  LoopFinderTester t;
+
+  Node* p1a = t.jsgraph.Int32Constant(11);
+  Node* p1b = t.jsgraph.Int32Constant(22);
+  Node* p1c = t.jsgraph.Int32Constant(33);
+  Node* p2a = t.jsgraph.Int32Constant(44);
+  Node* p2b = t.jsgraph.Int32Constant(55);
+  Node* p2c = t.jsgraph.Int32Constant(66);
+  Node* p3a = t.jsgraph.Int32Constant(77);
+  Node* p3b = t.jsgraph.Int32Constant(88);
+  Node* p3c = t.jsgraph.Int32Constant(99);
+
+  // L1 depth = 0
+  Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
+  Node* phi1 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p1a, p1c, loop1);
+  Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b);
+  Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1);
+  Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1);
+  Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1);
+
+  // L2 depth = 1
+  Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start);
+  Node* phi2 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p2a, p2c, loop2);
+  Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b);
+  Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2);
+  Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2);
+  Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2);
+
+  // L3 depth = 2
+  Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start);
+  Node* phi3 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p3a, p3c, loop3);
+  Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b);
+  Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3);
+  Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3);
+  Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3);
+
+  loop3->ReplaceInput(1, if_true3);
+  loop2->ReplaceInput(1, exit3);
+  loop1->ReplaceInput(1, exit2);
+
+  Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1);
+  t.graph.SetEnd(ret);
+
+  // Mutate the graph according to the edge choices.
+
+  Node* o1[] = {t.one};
+  Node* o2[] = {t.one, phi1, cond1};
+  Node* o3[] = {t.one, phi1, cond1, phi2, cond2};
+
+  p1a->ReplaceUses(o1[c1a]);
+  p1b->ReplaceUses(o1[c1b]);
+
+  p2a->ReplaceUses(o2[c2a]);
+  p2b->ReplaceUses(o2[c2b]);
+
+  p3a->ReplaceUses(o3[c3a]);
+  p3b->ReplaceUses(o3[c3b]);
+
+  Node* l2[] = {phi1, cond1, phi2, cond2};
+  Node* l3[] = {phi1, cond1, phi2, cond2, phi3, cond3};
+
+  p1c->ReplaceUses(l2[c1c]);
+  p2c->ReplaceUses(l3[c2c]);
+  p3c->ReplaceUses(l3[c3c]);
+
+  // Run the tests and verify loop structure.
+
+  Node* chain[] = {loop1, loop2, loop3};
+  t.CheckNestedLoops(chain, 3);
+
+  Node* header1[] = {loop1, phi1};
+  Node* body1[] = {cond1, branch1, if_true1, exit2,    loop2,
+                   phi2,  cond2,   branch2,  if_true2, exit3,
+                   loop3, phi3,    cond3,    branch3,  if_true3};
+  t.CheckLoop(header1, 2, body1, 15);
+
+  Node* header2[] = {loop2, phi2};
+  Node* body2[] = {cond2, branch2, if_true2, exit3,   loop3,
+                   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) {
+  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);
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+
+// Test all possible legal triply-nested loops with conditions and phis.
+TEST(LaEdgeMatrix3_0) { RunEdgeMatrix3_i(0); }
+
+
+TEST(LaEdgeMatrix3_1) { RunEdgeMatrix3_i(1); }
+
+
+TEST(LaEdgeMatrix3_2) { RunEdgeMatrix3_i(2); }
+
+
+TEST(LaEdgeMatrix3_3) { RunEdgeMatrix3_i(3); }
+
+
+TEST(LaEdgeMatrix3_4) { RunEdgeMatrix3_i(4); }
+
+
+TEST(LaEdgeMatrix3_5) { RunEdgeMatrix3_i(5); }