diff options
Diffstat (limited to 'deps/v8/test/unittests/compiler/loop-peeling-unittest.cc')
-rw-r--r-- | deps/v8/test/unittests/compiler/loop-peeling-unittest.cc | 451 |
1 files changed, 451 insertions, 0 deletions
diff --git a/deps/v8/test/unittests/compiler/loop-peeling-unittest.cc b/deps/v8/test/unittests/compiler/loop-peeling-unittest.cc new file mode 100644 index 0000000000..dd0c46c42a --- /dev/null +++ b/deps/v8/test/unittests/compiler/loop-peeling-unittest.cc @@ -0,0 +1,451 @@ +// Copyright 2015 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/access-builder.h" +#include "src/compiler/graph.h" +#include "src/compiler/graph-visualizer.h" +#include "src/compiler/js-graph.h" +#include "src/compiler/loop-peeling.h" +#include "src/compiler/machine-operator.h" +#include "src/compiler/node.h" +#include "src/compiler/node-properties.h" +#include "test/unittests/compiler/compiler-test-utils.h" +#include "test/unittests/compiler/graph-unittest.h" +#include "test/unittests/compiler/node-test-utils.h" +#include "testing/gmock-support.h" + +using testing::AllOf; +using testing::BitEq; +using testing::Capture; +using testing::CaptureEq; + +namespace v8 { +namespace internal { +namespace compiler { + +struct While { + Node* loop; + Node* branch; + Node* if_true; + Node* exit; +}; + + +// A helper for building branches. +struct Branch { + Node* branch; + Node* if_true; + Node* if_false; +}; + + +// A helper for building counters attached to loops. +struct Counter { + Node* base; + Node* inc; + Node* phi; + Node* add; +}; + + +class LoopPeelingTest : public GraphTest { + public: + LoopPeelingTest() : GraphTest(1), machine_(zone()) {} + ~LoopPeelingTest() OVERRIDE {} + + protected: + MachineOperatorBuilder machine_; + + MachineOperatorBuilder* machine() { return &machine_; } + + LoopTree* GetLoopTree() { + if (FLAG_trace_turbo_graph) { + OFStream os(stdout); + os << AsRPO(*graph()); + } + Zone zone; + return LoopFinder::BuildLoopTree(graph(), &zone); + } + + + PeeledIteration* PeelOne() { + LoopTree* loop_tree = GetLoopTree(); + return Peel(loop_tree, loop_tree->outer_loops()[0]); + } + + PeeledIteration* Peel(LoopTree* loop_tree, LoopTree::Loop* loop) { + PeeledIteration* peeled = + LoopPeeler::Peel(graph(), common(), loop_tree, loop, zone()); + if (FLAG_trace_turbo_graph) { + OFStream os(stdout); + os << AsRPO(*graph()); + } + return peeled; + } + + Node* InsertReturn(Node* val, Node* effect, Node* control) { + Node* r = graph()->NewNode(common()->Return(), val, effect, control); + graph()->SetEnd(r); + return r; + } + + Node* ExpectPeeled(Node* node, PeeledIteration* iter) { + Node* p = iter->map(node); + EXPECT_NE(node, p); + return p; + } + + void ExpectNotPeeled(Node* node, PeeledIteration* iter) { + EXPECT_EQ(node, iter->map(node)); + } + + While NewWhile(Node* cond, Node* control = nullptr) { + if (control == nullptr) control = start(); + Node* loop = graph()->NewNode(common()->Loop(2), control, control); + Node* branch = graph()->NewNode(common()->Branch(), cond, loop); + Node* if_true = graph()->NewNode(common()->IfTrue(), branch); + Node* exit = graph()->NewNode(common()->IfFalse(), branch); + loop->ReplaceInput(1, if_true); + return {loop, branch, if_true, exit}; + } + + void Chain(While* a, Node* control) { a->loop->ReplaceInput(0, control); } + void Nest(While* a, While* b) { + b->loop->ReplaceInput(1, a->exit); + a->loop->ReplaceInput(0, b->if_true); + } + Node* NewPhi(While* w, Node* a, Node* b) { + return graph()->NewNode(common()->Phi(kMachAnyTagged, 2), a, b, w->loop); + } + + Branch NewBranch(Node* cond, Node* control = nullptr) { + if (control == nullptr) control = start(); + Node* branch = graph()->NewNode(common()->Branch(), cond, control); + Node* if_true = graph()->NewNode(common()->IfTrue(), branch); + Node* if_false = graph()->NewNode(common()->IfFalse(), branch); + return {branch, if_true, if_false}; + } + + Counter NewCounter(While* w, int32_t b, int32_t k) { + Node* base = Int32Constant(b); + Node* inc = Int32Constant(k); + Node* phi = + graph()->NewNode(common()->Phi(kMachAnyTagged, 2), base, base, w->loop); + Node* add = graph()->NewNode(machine()->Int32Add(), phi, inc); + phi->ReplaceInput(1, add); + return {base, inc, phi, add}; + } +}; + + +TEST_F(LoopPeelingTest, SimpleLoop) { + Node* p0 = Parameter(0); + While w = NewWhile(p0); + Node* r = InsertReturn(p0, start(), w.exit); + + PeeledIteration* peeled = PeelOne(); + + Node* br1 = ExpectPeeled(w.branch, peeled); + Node* if_true1 = ExpectPeeled(w.if_true, peeled); + Node* if_false1 = ExpectPeeled(w.exit, peeled); + + EXPECT_THAT(br1, IsBranch(p0, start())); + EXPECT_THAT(if_true1, IsIfTrue(br1)); + EXPECT_THAT(if_false1, IsIfFalse(br1)); + + EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); + EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(w.exit, if_false1))); +} + + +TEST_F(LoopPeelingTest, SimpleLoopWithCounter) { + Node* p0 = Parameter(0); + While w = NewWhile(p0); + Counter c = NewCounter(&w, 0, 1); + Node* r = InsertReturn(c.phi, start(), w.exit); + + PeeledIteration* peeled = PeelOne(); + + Node* br1 = ExpectPeeled(w.branch, peeled); + Node* if_true1 = ExpectPeeled(w.if_true, peeled); + Node* if_false1 = ExpectPeeled(w.exit, peeled); + + EXPECT_THAT(br1, IsBranch(p0, start())); + EXPECT_THAT(if_true1, IsIfTrue(br1)); + EXPECT_THAT(if_false1, IsIfFalse(br1)); + EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); + + EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); + + Capture<Node*> merge; + EXPECT_THAT( + r, IsReturn(IsPhi(kMachAnyTagged, c.phi, c.base, + AllOf(CaptureEq(&merge), IsMerge(w.exit, if_false1))), + start(), CaptureEq(&merge))); +} + + +TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_outer) { + Node* p0 = Parameter(0); + While outer = NewWhile(p0); + While inner = NewWhile(p0); + Nest(&inner, &outer); + + Counter c = NewCounter(&outer, 0, 1); + Node* r = InsertReturn(c.phi, start(), outer.exit); + + PeeledIteration* peeled = PeelOne(); + + Node* bro = ExpectPeeled(outer.branch, peeled); + Node* if_trueo = ExpectPeeled(outer.if_true, peeled); + Node* if_falseo = ExpectPeeled(outer.exit, peeled); + + EXPECT_THAT(bro, IsBranch(p0, start())); + EXPECT_THAT(if_trueo, IsIfTrue(bro)); + EXPECT_THAT(if_falseo, IsIfFalse(bro)); + + Node* bri = ExpectPeeled(inner.branch, peeled); + Node* if_truei = ExpectPeeled(inner.if_true, peeled); + Node* if_falsei = ExpectPeeled(inner.exit, peeled); + + EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); + EXPECT_THAT(if_truei, IsIfTrue(bri)); + EXPECT_THAT(if_falsei, IsIfFalse(bri)); + + EXPECT_THAT(outer.loop, IsLoop(if_falsei, inner.exit)); + EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); + + Capture<Node*> merge; + EXPECT_THAT( + r, + IsReturn(IsPhi(kMachAnyTagged, c.phi, c.base, + AllOf(CaptureEq(&merge), IsMerge(outer.exit, if_falseo))), + start(), CaptureEq(&merge))); +} + + +TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_inner) { + Node* p0 = Parameter(0); + While outer = NewWhile(p0); + While inner = NewWhile(p0); + Nest(&inner, &outer); + + Counter c = NewCounter(&outer, 0, 1); + Node* r = InsertReturn(c.phi, start(), outer.exit); + + LoopTree* loop_tree = GetLoopTree(); + LoopTree::Loop* loop = loop_tree->ContainingLoop(inner.loop); + EXPECT_NE(nullptr, loop); + EXPECT_EQ(1u, loop->depth()); + + PeeledIteration* peeled = Peel(loop_tree, loop); + + ExpectNotPeeled(outer.loop, peeled); + ExpectNotPeeled(outer.branch, peeled); + ExpectNotPeeled(outer.if_true, peeled); + ExpectNotPeeled(outer.exit, peeled); + + Node* bri = ExpectPeeled(inner.branch, peeled); + Node* if_truei = ExpectPeeled(inner.if_true, peeled); + Node* if_falsei = ExpectPeeled(inner.exit, peeled); + + EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); + EXPECT_THAT(if_truei, IsIfTrue(bri)); + EXPECT_THAT(if_falsei, IsIfFalse(bri)); + + EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); + ExpectNotPeeled(c.add, peeled); + + EXPECT_THAT(r, IsReturn(c.phi, start(), outer.exit)); +} + + +TEST_F(LoopPeelingTest, SimpleInnerCounter_peel_inner) { + Node* p0 = Parameter(0); + While outer = NewWhile(p0); + While inner = NewWhile(p0); + Nest(&inner, &outer); + Counter c = NewCounter(&inner, 0, 1); + Node* phi = NewPhi(&outer, Int32Constant(11), c.phi); + + Node* r = InsertReturn(phi, start(), outer.exit); + + LoopTree* loop_tree = GetLoopTree(); + LoopTree::Loop* loop = loop_tree->ContainingLoop(inner.loop); + EXPECT_NE(nullptr, loop); + EXPECT_EQ(1u, loop->depth()); + + PeeledIteration* peeled = Peel(loop_tree, loop); + + ExpectNotPeeled(outer.loop, peeled); + ExpectNotPeeled(outer.branch, peeled); + ExpectNotPeeled(outer.if_true, peeled); + ExpectNotPeeled(outer.exit, peeled); + + Node* bri = ExpectPeeled(inner.branch, peeled); + Node* if_truei = ExpectPeeled(inner.if_true, peeled); + Node* if_falsei = ExpectPeeled(inner.exit, peeled); + + EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); + EXPECT_THAT(if_truei, IsIfTrue(bri)); + EXPECT_THAT(if_falsei, IsIfFalse(bri)); + + EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); + EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); + + Node* back = phi->InputAt(1); + EXPECT_THAT(back, IsPhi(kMachAnyTagged, c.phi, c.base, + IsMerge(inner.exit, if_falsei))); + + EXPECT_THAT(phi, + IsPhi(kMachAnyTagged, IsInt32Constant(11), back, outer.loop)); + + EXPECT_THAT(r, IsReturn(phi, start(), outer.exit)); +} + + +TEST_F(LoopPeelingTest, TwoBackedgeLoop) { + Node* p0 = Parameter(0); + Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); + Branch b1 = NewBranch(p0, loop); + Branch b2 = NewBranch(p0, b1.if_true); + + loop->ReplaceInput(1, b2.if_true); + loop->ReplaceInput(2, b2.if_false); + + Node* r = InsertReturn(p0, start(), b1.if_false); + + PeeledIteration* peeled = PeelOne(); + + Node* b1b = ExpectPeeled(b1.branch, peeled); + Node* b1t = ExpectPeeled(b1.if_true, peeled); + Node* b1f = ExpectPeeled(b1.if_false, peeled); + + EXPECT_THAT(b1b, IsBranch(p0, start())); + EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); + EXPECT_THAT(b1f, IsIfFalse(b1b)); + + Node* b2b = ExpectPeeled(b2.branch, peeled); + Node* b2t = ExpectPeeled(b2.if_true, peeled); + Node* b2f = ExpectPeeled(b2.if_false, peeled); + + EXPECT_THAT(b2b, IsBranch(p0, b1t)); + EXPECT_THAT(b2t, IsIfTrue(b2b)); + EXPECT_THAT(b2f, IsIfFalse(b2b)); + + EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); + EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(b1.if_false, b1f))); +} + + +TEST_F(LoopPeelingTest, TwoBackedgeLoopWithPhi) { + Node* p0 = Parameter(0); + Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); + Branch b1 = NewBranch(p0, loop); + Branch b2 = NewBranch(p0, b1.if_true); + Node* phi = + graph()->NewNode(common()->Phi(kMachAnyTagged, 3), Int32Constant(0), + Int32Constant(1), Int32Constant(2), loop); + + loop->ReplaceInput(1, b2.if_true); + loop->ReplaceInput(2, b2.if_false); + + Node* r = InsertReturn(phi, start(), b1.if_false); + + PeeledIteration* peeled = PeelOne(); + + Node* b1b = ExpectPeeled(b1.branch, peeled); + Node* b1t = ExpectPeeled(b1.if_true, peeled); + Node* b1f = ExpectPeeled(b1.if_false, peeled); + + EXPECT_THAT(b1b, IsBranch(p0, start())); + EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); + EXPECT_THAT(b1f, IsIfFalse(b1b)); + + Node* b2b = ExpectPeeled(b2.branch, peeled); + Node* b2t = ExpectPeeled(b2.if_true, peeled); + Node* b2f = ExpectPeeled(b2.if_false, peeled); + + EXPECT_THAT(b2b, IsBranch(p0, b1t)); + EXPECT_THAT(b2t, IsIfTrue(b2b)); + EXPECT_THAT(b2f, IsIfFalse(b2b)); + + EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); + + EXPECT_THAT( + phi, IsPhi(kMachAnyTagged, IsPhi(kMachAnyTagged, IsInt32Constant(1), + IsInt32Constant(2), IsMerge(b2t, b2f)), + IsInt32Constant(1), IsInt32Constant(2), loop)); + + Capture<Node*> merge; + EXPECT_THAT( + r, IsReturn(IsPhi(kMachAnyTagged, phi, IsInt32Constant(0), + AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), + start(), CaptureEq(&merge))); +} + + +TEST_F(LoopPeelingTest, TwoBackedgeLoopWithCounter) { + Node* p0 = Parameter(0); + Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); + Branch b1 = NewBranch(p0, loop); + Branch b2 = NewBranch(p0, b1.if_true); + Node* phi = + graph()->NewNode(common()->Phi(kMachAnyTagged, 3), Int32Constant(0), + Int32Constant(1), Int32Constant(2), loop); + + phi->ReplaceInput( + 1, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(1))); + phi->ReplaceInput( + 2, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(2))); + + loop->ReplaceInput(1, b2.if_true); + loop->ReplaceInput(2, b2.if_false); + + Node* r = InsertReturn(phi, start(), b1.if_false); + + PeeledIteration* peeled = PeelOne(); + + Node* b1b = ExpectPeeled(b1.branch, peeled); + Node* b1t = ExpectPeeled(b1.if_true, peeled); + Node* b1f = ExpectPeeled(b1.if_false, peeled); + + EXPECT_THAT(b1b, IsBranch(p0, start())); + EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); + EXPECT_THAT(b1f, IsIfFalse(b1b)); + + Node* b2b = ExpectPeeled(b2.branch, peeled); + Node* b2t = ExpectPeeled(b2.if_true, peeled); + Node* b2f = ExpectPeeled(b2.if_false, peeled); + + EXPECT_THAT(b2b, IsBranch(p0, b1t)); + EXPECT_THAT(b2t, IsIfTrue(b2b)); + EXPECT_THAT(b2f, IsIfFalse(b2b)); + + Capture<Node*> entry; + EXPECT_THAT(loop, IsLoop(AllOf(CaptureEq(&entry), IsMerge(b2t, b2f)), + b2.if_true, b2.if_false)); + + Node* eval = phi->InputAt(0); + + EXPECT_THAT(eval, IsPhi(kMachAnyTagged, + IsInt32Add(IsInt32Constant(0), IsInt32Constant(1)), + IsInt32Add(IsInt32Constant(0), IsInt32Constant(2)), + CaptureEq(&entry))); + + EXPECT_THAT(phi, + IsPhi(kMachAnyTagged, eval, IsInt32Add(phi, IsInt32Constant(1)), + IsInt32Add(phi, IsInt32Constant(2)), loop)); + + Capture<Node*> merge; + EXPECT_THAT( + r, IsReturn(IsPhi(kMachAnyTagged, phi, IsInt32Constant(0), + AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), + start(), CaptureEq(&merge))); +} + + +} // namespace compiler +} // namespace internal +} // namespace v8 |