Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/test/unittests/compiler/loop-peeling-unittest.cc b/test/unittests/compiler/loop-peeling-unittest.cc
new file mode 100644
index 0000000..9dcec85
--- /dev/null
+++ b/test/unittests/compiler/loop-peeling-unittest.cc
@@ -0,0 +1,500 @@
+// 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();
+ LoopTree::Loop* loop = loop_tree->outer_loops()[0];
+ EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, loop));
+ return Peel(loop_tree, loop);
+ }
+
+ PeeledIteration* Peel(LoopTree* loop_tree, LoopTree::Loop* loop) {
+ EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, c.phi, c.base,
+ IsMerge(inner.exit, if_falsei)));
+
+ EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged,
+ IsPhi(MachineRepresentation::kTagged, IsInt32Constant(1),
+ IsInt32Constant(2), IsMerge(b2t, b2f)),
+ IsInt32Constant(1), IsInt32Constant(2), loop));
+
+ Capture<Node*> merge;
+ EXPECT_THAT(
+ r, IsReturn(IsPhi(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged, 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(MachineRepresentation::kTagged,
+ IsInt32Add(IsInt32Constant(0), IsInt32Constant(1)),
+ IsInt32Add(IsInt32Constant(0), IsInt32Constant(2)),
+ CaptureEq(&entry)));
+
+ EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, eval,
+ IsInt32Add(phi, IsInt32Constant(1)),
+ IsInt32Add(phi, IsInt32Constant(2)), loop));
+
+ Capture<Node*> merge;
+ EXPECT_THAT(
+ r, IsReturn(IsPhi(MachineRepresentation::kTagged, phi, IsInt32Constant(0),
+ AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))),
+ start(), CaptureEq(&merge)));
+}
+
+
+TEST_F(LoopPeelingTest, TwoExitLoop_nope) {
+ Node* p0 = Parameter(0);
+ Node* loop = graph()->NewNode(common()->Loop(2), start(), start());
+ Branch b1 = NewBranch(p0, loop);
+ Branch b2 = NewBranch(p0, b1.if_true);
+
+ loop->ReplaceInput(1, b2.if_true);
+ Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, b2.if_false);
+ InsertReturn(p0, start(), merge);
+
+ {
+ LoopTree* loop_tree = GetLoopTree();
+ LoopTree::Loop* loop = loop_tree->outer_loops()[0];
+ EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop));
+ }
+}
+
+
+const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall",
+ 0, 0, 1, 1, 1, 2);
+
+
+TEST_F(LoopPeelingTest, TwoExitLoopWithCall_nope) {
+ Node* p0 = Parameter(0);
+ Node* loop = graph()->NewNode(common()->Loop(2), start(), start());
+ Branch b1 = NewBranch(p0, loop);
+
+ Node* call = graph()->NewNode(&kMockCall, b1.if_true);
+ Node* if_success = graph()->NewNode(common()->IfSuccess(), call);
+ Node* if_exception = graph()->NewNode(
+ common()->IfException(IfExceptionHint::kLocallyUncaught), call, call);
+
+ loop->ReplaceInput(1, if_success);
+ Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, if_exception);
+ InsertReturn(p0, start(), merge);
+
+ {
+ LoopTree* loop_tree = GetLoopTree();
+ LoopTree::Loop* loop = loop_tree->outer_loops()[0];
+ EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop));
+ }
+}
+
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8