Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(733)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: test/cctest/compiler/test-loop-analysis.cc

Issue 803993002: [turbofan] First version of loop analysis: loop finder on the soup of nodes. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « test/cctest/cctest.gyp ('k') | tools/gyp/v8.gyp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: test/cctest/compiler/test-loop-analysis.cc
diff --git a/test/cctest/compiler/test-loop-analysis.cc b/test/cctest/compiler/test-loop-analysis.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9c112681c2b8f9b5ea1a86f5f080419329fee6e9
--- /dev/null
+++ b/test/cctest/compiler/test-loop-analysis.cc
@@ -0,0 +1,862 @@
+// 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(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));
+ }
+ }
+ }
+};
+
+
+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); }
« no previous file with comments | « test/cctest/cctest.gyp ('k') | tools/gyp/v8.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698