diff options
Diffstat (limited to 'deps/v8/test/cctest/compiler/test-scheduler.cc')
| -rw-r--r-- | deps/v8/test/cctest/compiler/test-scheduler.cc | 2124 |
1 files changed, 0 insertions, 2124 deletions
diff --git a/deps/v8/test/cctest/compiler/test-scheduler.cc b/deps/v8/test/cctest/compiler/test-scheduler.cc deleted file mode 100644 index 1b79ed5449..0000000000 --- a/deps/v8/test/cctest/compiler/test-scheduler.cc +++ /dev/null @@ -1,2124 +0,0 @@ -// 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-operator.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; - -Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0, 0, 1, - 0, 0); - -// TODO(titzer): pull RPO tests out to their own file. -static void CheckRPONumbers(BasicBlockVector* order, size_t expected, - bool loops_allowed) { - CHECK(expected == order->size()); - for (int i = 0; i < static_cast<int>(order->size()); i++) { - CHECK(order->at(i)->rpo_number() == i); - if (!loops_allowed) { - CHECK_EQ(NULL, order->at(i)->loop_end()); - CHECK_EQ(NULL, order->at(i)->loop_header()); - } - } -} - - -static void CheckLoop(BasicBlockVector* order, BasicBlock** blocks, - int body_size) { - BasicBlock* header = blocks[0]; - BasicBlock* end = header->loop_end(); - CHECK_NE(NULL, end); - CHECK_GT(end->rpo_number(), 0); - CHECK_EQ(body_size, end->rpo_number() - header->rpo_number()); - for (int i = 0; i < body_size; i++) { - CHECK_GE(blocks[i]->rpo_number(), header->rpo_number()); - CHECK_LT(blocks[i]->rpo_number(), end->rpo_number()); - CHECK(header->LoopContains(blocks[i])); - CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header); - } - if (header->rpo_number() > 0) { - CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header); - } - if (end->rpo_number() < static_cast<int>(order->size())) { - CHECK_NE(order->at(end->rpo_number())->loop_header(), header); - } -} - - -struct TestLoop { - int count; - BasicBlock** nodes; - BasicBlock* header() { return nodes[0]; } - BasicBlock* last() { return nodes[count - 1]; } - ~TestLoop() { delete[] nodes; } - - void Check(BasicBlockVector* order) { CheckLoop(order, nodes, count); } -}; - - -static TestLoop* CreateLoop(Schedule* schedule, int count) { - TestLoop* loop = new TestLoop(); - loop->count = count; - loop->nodes = new BasicBlock* [count]; - for (int i = 0; i < count; i++) { - loop->nodes[i] = schedule->NewBasicBlock(); - if (i > 0) { - schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]); - } - } - schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]); - return loop; -} - - -static int GetScheduledNodeCount(Schedule* schedule) { - int node_count = 0; - for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); - i != schedule->rpo_order()->end(); ++i) { - BasicBlock* block = *i; - for (BasicBlock::const_iterator j = block->begin(); j != block->end(); - ++j) { - ++node_count; - } - BasicBlock::Control control = block->control(); - if (control != BasicBlock::kNone) { - ++node_count; - } - } - return node_count; -} - - -static Schedule* ComputeAndVerifySchedule(int expected, Graph* graph) { - if (FLAG_trace_turbo) { - OFStream os(stdout); - os << AsDOT(*graph); - } - - Schedule* schedule = Scheduler::ComputeSchedule(graph->zone(), graph); - - if (FLAG_trace_turbo_scheduler) { - OFStream os(stdout); - os << *schedule << std::endl; - } - ScheduleVerifier::Run(schedule); - CHECK_EQ(expected, GetScheduledNodeCount(schedule)); - return schedule; -} - - -TEST(RPODegenerate1) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 1, false); - CHECK_EQ(schedule.start(), order->at(0)); -} - - -TEST(RPODegenerate2) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - schedule.AddGoto(schedule.start(), schedule.end()); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 2, false); - CHECK_EQ(schedule.start(), order->at(0)); - CHECK_EQ(schedule.end(), order->at(1)); -} - - -TEST(RPOLine) { - HandleAndZoneScope scope; - - for (int i = 0; i < 10; i++) { - Schedule schedule(scope.main_zone()); - - BasicBlock* last = schedule.start(); - for (int j = 0; j < i; j++) { - BasicBlock* block = schedule.NewBasicBlock(); - block->set_deferred(i & 1); - schedule.AddGoto(last, block); - last = block; - } - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 1 + i, false); - - for (size_t i = 0; i < schedule.BasicBlockCount(); i++) { - BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(i)); - if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) { - CHECK(block->rpo_number() + 1 == block->SuccessorAt(0)->rpo_number()); - } - } - } -} - - -TEST(RPOSelfLoop) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - schedule.AddSuccessorForTesting(schedule.start(), schedule.start()); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 1, true); - BasicBlock* loop[] = {schedule.start()}; - CheckLoop(order, loop, 1); -} - - -TEST(RPOEntryLoop) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - BasicBlock* body = schedule.NewBasicBlock(); - schedule.AddSuccessorForTesting(schedule.start(), body); - schedule.AddSuccessorForTesting(body, schedule.start()); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 2, true); - BasicBlock* loop[] = {schedule.start(), body}; - CheckLoop(order, loop, 2); -} - - -TEST(RPOEndLoop) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); - schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 3, true); - loop1->Check(order); -} - - -TEST(RPOEndLoopNested) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2)); - schedule.AddSuccessorForTesting(schedule.start(), loop1->header()); - schedule.AddSuccessorForTesting(loop1->last(), schedule.start()); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 3, true); - loop1->Check(order); -} - - -TEST(RPODiamond) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(A, C); - schedule.AddSuccessorForTesting(B, D); - schedule.AddSuccessorForTesting(C, D); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 4, false); - - CHECK_EQ(0, A->rpo_number()); - CHECK((B->rpo_number() == 1 && C->rpo_number() == 2) || - (B->rpo_number() == 2 && C->rpo_number() == 1)); - CHECK_EQ(3, D->rpo_number()); -} - - -TEST(RPOLoop1) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(C, B); - schedule.AddSuccessorForTesting(C, D); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 4, true); - BasicBlock* loop[] = {B, C}; - CheckLoop(order, loop, 2); -} - - -TEST(RPOLoop2) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(C, B); - schedule.AddSuccessorForTesting(B, D); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 4, true); - BasicBlock* loop[] = {B, C}; - CheckLoop(order, loop, 2); -} - - -TEST(RPOLoopN) { - HandleAndZoneScope scope; - - for (int i = 0; i < 11; i++) { - Schedule schedule(scope.main_zone()); - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.NewBasicBlock(); - BasicBlock* E = schedule.NewBasicBlock(); - BasicBlock* F = schedule.NewBasicBlock(); - BasicBlock* G = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(C, D); - schedule.AddSuccessorForTesting(D, E); - schedule.AddSuccessorForTesting(E, F); - schedule.AddSuccessorForTesting(F, B); - schedule.AddSuccessorForTesting(B, G); - - // Throw in extra backedges from time to time. - if (i == 1) schedule.AddSuccessorForTesting(B, B); - if (i == 2) schedule.AddSuccessorForTesting(C, B); - if (i == 3) schedule.AddSuccessorForTesting(D, B); - if (i == 4) schedule.AddSuccessorForTesting(E, B); - if (i == 5) schedule.AddSuccessorForTesting(F, B); - - // Throw in extra loop exits from time to time. - if (i == 6) schedule.AddSuccessorForTesting(B, G); - if (i == 7) schedule.AddSuccessorForTesting(C, G); - if (i == 8) schedule.AddSuccessorForTesting(D, G); - if (i == 9) schedule.AddSuccessorForTesting(E, G); - if (i == 10) schedule.AddSuccessorForTesting(F, G); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 7, true); - BasicBlock* loop[] = {B, C, D, E, F}; - CheckLoop(order, loop, 5); - } -} - - -TEST(RPOLoopNest1) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.NewBasicBlock(); - BasicBlock* E = schedule.NewBasicBlock(); - BasicBlock* F = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(C, D); - schedule.AddSuccessorForTesting(D, C); - schedule.AddSuccessorForTesting(D, E); - schedule.AddSuccessorForTesting(E, B); - schedule.AddSuccessorForTesting(E, F); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 6, true); - BasicBlock* loop1[] = {B, C, D, E}; - CheckLoop(order, loop1, 4); - - BasicBlock* loop2[] = {C, D}; - CheckLoop(order, loop2, 2); -} - - -TEST(RPOLoopNest2) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.NewBasicBlock(); - BasicBlock* E = schedule.NewBasicBlock(); - BasicBlock* F = schedule.NewBasicBlock(); - BasicBlock* G = schedule.NewBasicBlock(); - BasicBlock* H = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(C, D); - schedule.AddSuccessorForTesting(D, E); - schedule.AddSuccessorForTesting(E, F); - schedule.AddSuccessorForTesting(F, G); - schedule.AddSuccessorForTesting(G, H); - - schedule.AddSuccessorForTesting(E, D); - schedule.AddSuccessorForTesting(F, C); - schedule.AddSuccessorForTesting(G, B); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 8, true); - BasicBlock* loop1[] = {B, C, D, E, F, G}; - CheckLoop(order, loop1, 6); - - BasicBlock* loop2[] = {C, D, E, F}; - CheckLoop(order, loop2, 4); - - BasicBlock* loop3[] = {D, E}; - CheckLoop(order, loop3, 2); -} - - -TEST(RPOLoopFollow1) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); - SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); - - BasicBlock* A = schedule.start(); - BasicBlock* E = schedule.end(); - - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); - schedule.AddSuccessorForTesting(loop2->last(), E); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - - CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), - static_cast<int>(order->size())); - - loop1->Check(order); - loop2->Check(order); -} - - -TEST(RPOLoopFollow2) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); - SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); - - BasicBlock* A = schedule.start(); - BasicBlock* S = schedule.NewBasicBlock(); - BasicBlock* E = schedule.end(); - - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->header(), S); - schedule.AddSuccessorForTesting(S, loop2->header()); - schedule.AddSuccessorForTesting(loop2->last(), E); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - - CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), - static_cast<int>(order->size())); - loop1->Check(order); - loop2->Check(order); -} - - -TEST(RPOLoopFollowN) { - HandleAndZoneScope scope; - - for (int size = 1; size < 5; size++) { - for (int exit = 0; exit < size; exit++) { - Schedule schedule(scope.main_zone()); - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); - SmartPointer<TestLoop> loop2(CreateLoop(&schedule, size)); - BasicBlock* A = schedule.start(); - BasicBlock* E = schedule.end(); - - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header()); - schedule.AddSuccessorForTesting(loop2->nodes[exit], E); - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - - CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), - static_cast<int>(order->size())); - loop1->Check(order); - loop2->Check(order); - } - } -} - - -TEST(RPONestedLoopFollow1) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 1)); - SmartPointer<TestLoop> loop2(CreateLoop(&schedule, 1)); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* E = schedule.end(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, loop1->header()); - schedule.AddSuccessorForTesting(loop1->header(), loop2->header()); - schedule.AddSuccessorForTesting(loop2->last(), C); - schedule.AddSuccessorForTesting(C, E); - schedule.AddSuccessorForTesting(C, B); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - - CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()), - static_cast<int>(order->size())); - loop1->Check(order); - loop2->Check(order); - - BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C}; - CheckLoop(order, loop3, 4); -} - - -TEST(RPOLoopBackedges1) { - HandleAndZoneScope scope; - - int size = 8; - for (int i = 0; i < size; i++) { - for (int j = 0; j < size; j++) { - Schedule schedule(scope.main_zone()); - BasicBlock* A = schedule.start(); - BasicBlock* E = schedule.end(); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->last(), E); - - schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); - schedule.AddSuccessorForTesting(loop1->nodes[j], E); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, schedule.BasicBlockCount(), true); - loop1->Check(order); - } - } -} - - -TEST(RPOLoopOutedges1) { - HandleAndZoneScope scope; - - int size = 8; - for (int i = 0; i < size; i++) { - for (int j = 0; j < size; j++) { - Schedule schedule(scope.main_zone()); - BasicBlock* A = schedule.start(); - BasicBlock* D = schedule.NewBasicBlock(); - BasicBlock* E = schedule.end(); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->last(), E); - - schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header()); - schedule.AddSuccessorForTesting(loop1->nodes[j], D); - schedule.AddSuccessorForTesting(D, E); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, schedule.BasicBlockCount(), true); - loop1->Check(order); - } - } -} - - -TEST(RPOLoopOutedges2) { - HandleAndZoneScope scope; - - int size = 8; - for (int i = 0; i < size; i++) { - Schedule schedule(scope.main_zone()); - BasicBlock* A = schedule.start(); - BasicBlock* E = schedule.end(); - - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->last(), E); - - for (int j = 0; j < size; j++) { - BasicBlock* O = schedule.NewBasicBlock(); - schedule.AddSuccessorForTesting(loop1->nodes[j], O); - schedule.AddSuccessorForTesting(O, E); - } - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, schedule.BasicBlockCount(), true); - loop1->Check(order); - } -} - - -TEST(RPOLoopOutloops1) { - HandleAndZoneScope scope; - - int size = 8; - for (int i = 0; i < size; i++) { - Schedule schedule(scope.main_zone()); - BasicBlock* A = schedule.start(); - BasicBlock* E = schedule.end(); - SmartPointer<TestLoop> loop1(CreateLoop(&schedule, size)); - schedule.AddSuccessorForTesting(A, loop1->header()); - schedule.AddSuccessorForTesting(loop1->last(), E); - - TestLoop** loopN = new TestLoop* [size]; - for (int j = 0; j < size; j++) { - loopN[j] = CreateLoop(&schedule, 2); - schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header()); - schedule.AddSuccessorForTesting(loopN[j]->last(), E); - } - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, schedule.BasicBlockCount(), true); - loop1->Check(order); - - for (int j = 0; j < size; j++) { - loopN[j]->Check(order); - delete loopN[j]; - } - delete[] loopN; - } -} - - -TEST(RPOLoopMultibackedge) { - HandleAndZoneScope scope; - Schedule schedule(scope.main_zone()); - - BasicBlock* A = schedule.start(); - BasicBlock* B = schedule.NewBasicBlock(); - BasicBlock* C = schedule.NewBasicBlock(); - BasicBlock* D = schedule.NewBasicBlock(); - BasicBlock* E = schedule.NewBasicBlock(); - - schedule.AddSuccessorForTesting(A, B); - schedule.AddSuccessorForTesting(B, C); - schedule.AddSuccessorForTesting(B, D); - schedule.AddSuccessorForTesting(B, E); - schedule.AddSuccessorForTesting(C, B); - schedule.AddSuccessorForTesting(D, B); - schedule.AddSuccessorForTesting(E, B); - - BasicBlockVector* order = - Scheduler::ComputeSpecialRPO(scope.main_zone(), &schedule); - CheckRPONumbers(order, 5, true); - - BasicBlock* loop1[] = {B, C, D, E}; - CheckLoop(order, loop1, 4); -} - - -TEST(BuildScheduleEmpty) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder builder(scope.main_zone()); - graph.SetStart(graph.NewNode(builder.Start(0))); - graph.SetEnd(graph.NewNode(builder.End(), graph.start())); - - USE(Scheduler::ComputeSchedule(scope.main_zone(), &graph)); -} - - -TEST(BuildScheduleOneParameter) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder builder(scope.main_zone()); - graph.SetStart(graph.NewNode(builder.Start(0))); - - Node* p1 = graph.NewNode(builder.Parameter(0), graph.start()); - Node* ret = graph.NewNode(builder.Return(), p1, graph.start(), graph.start()); - - graph.SetEnd(graph.NewNode(builder.End(), ret)); - - USE(Scheduler::ComputeSchedule(scope.main_zone(), &graph)); -} - - -TEST(BuildScheduleIfSplit) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - graph.SetStart(graph.NewNode(builder.Start(3))); - - Node* p1 = graph.NewNode(builder.Parameter(0), graph.start()); - Node* p2 = graph.NewNode(builder.Parameter(1), graph.start()); - Node* p3 = graph.NewNode(builder.Parameter(2), graph.start()); - Node* p4 = graph.NewNode(builder.Parameter(3), graph.start()); - Node* p5 = graph.NewNode(builder.Parameter(4), graph.start()); - Node* cmp = graph.NewNode(js_builder.LessThanOrEqual(), p1, p2, p3, - graph.start(), graph.start()); - Node* branch = graph.NewNode(builder.Branch(), cmp, graph.start()); - Node* true_branch = graph.NewNode(builder.IfTrue(), branch); - Node* false_branch = graph.NewNode(builder.IfFalse(), branch); - - Node* ret1 = graph.NewNode(builder.Return(), p4, graph.start(), true_branch); - Node* ret2 = graph.NewNode(builder.Return(), p5, graph.start(), false_branch); - Node* merge = graph.NewNode(builder.Merge(2), ret1, ret2); - graph.SetEnd(graph.NewNode(builder.End(), merge)); - - ComputeAndVerifySchedule(13, &graph); -} - - -TEST(BuildScheduleIfSplitWithEffects) { - HandleAndZoneScope scope; - Isolate* isolate = scope.main_isolate(); - Graph graph(scope.main_zone()); - CommonOperatorBuilder common_builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - const Operator* op; - - Handle<HeapObject> object = - Handle<HeapObject>(isolate->heap()->undefined_value(), isolate); - Unique<HeapObject> unique_constant = - Unique<HeapObject>::CreateUninitialized(object); - - // Manually transcripted code for: - // function turbo_fan_test(a, b, c, y) { - // if (a < b) { - // return a + b - c * c - a + y; - // } else { - // return c * c - a; - // } - // } - op = common_builder.Start(0); - Node* n0 = graph.NewNode(op); - USE(n0); - Node* nil = graph.NewNode(common_builder.Dead()); - op = common_builder.End(); - Node* n23 = graph.NewNode(op, nil); - USE(n23); - op = common_builder.Merge(2); - Node* n22 = graph.NewNode(op, nil, nil); - USE(n22); - op = common_builder.Return(); - Node* n16 = graph.NewNode(op, nil, nil, nil); - USE(n16); - op = js_builder.Add(); - Node* n15 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n15); - op = js_builder.Subtract(); - Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n14); - op = js_builder.Subtract(); - Node* n13 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n13); - op = js_builder.Add(); - Node* n11 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n11); - op = common_builder.Parameter(0); - Node* n2 = graph.NewNode(op, n0); - USE(n2); - n11->ReplaceInput(0, n2); - op = common_builder.Parameter(0); - Node* n3 = graph.NewNode(op, n0); - USE(n3); - n11->ReplaceInput(1, n3); - op = common_builder.HeapConstant(unique_constant); - Node* n7 = graph.NewNode(op); - USE(n7); - n11->ReplaceInput(2, n7); - op = js_builder.LessThan(); - Node* n8 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n8); - n8->ReplaceInput(0, n2); - n8->ReplaceInput(1, n3); - n8->ReplaceInput(2, n7); - n8->ReplaceInput(3, n0); - n8->ReplaceInput(4, n0); - n11->ReplaceInput(3, n8); - op = common_builder.IfTrue(); - Node* n10 = graph.NewNode(op, nil); - USE(n10); - op = common_builder.Branch(); - Node* n9 = graph.NewNode(op, nil, nil); - USE(n9); - n9->ReplaceInput(0, n8); - n9->ReplaceInput(1, n0); - n10->ReplaceInput(0, n9); - n11->ReplaceInput(4, n10); - n13->ReplaceInput(0, n11); - op = js_builder.Multiply(); - Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n12); - op = common_builder.Parameter(0); - Node* n4 = graph.NewNode(op, n0); - USE(n4); - n12->ReplaceInput(0, n4); - n12->ReplaceInput(1, n4); - n12->ReplaceInput(2, n7); - n12->ReplaceInput(3, n11); - n12->ReplaceInput(4, n10); - n13->ReplaceInput(1, n12); - n13->ReplaceInput(2, n7); - n13->ReplaceInput(3, n12); - n13->ReplaceInput(4, n10); - n14->ReplaceInput(0, n13); - n14->ReplaceInput(1, n2); - n14->ReplaceInput(2, n7); - n14->ReplaceInput(3, n13); - n14->ReplaceInput(4, n10); - n15->ReplaceInput(0, n14); - op = common_builder.Parameter(0); - Node* n5 = graph.NewNode(op, n0); - USE(n5); - n15->ReplaceInput(1, n5); - n15->ReplaceInput(2, n7); - n15->ReplaceInput(3, n14); - n15->ReplaceInput(4, n10); - n16->ReplaceInput(0, n15); - n16->ReplaceInput(1, n15); - n16->ReplaceInput(2, n10); - n22->ReplaceInput(0, n16); - op = common_builder.Return(); - Node* n21 = graph.NewNode(op, nil, nil, nil); - USE(n21); - op = js_builder.Subtract(); - Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n20); - op = js_builder.Multiply(); - Node* n19 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n19); - n19->ReplaceInput(0, n4); - n19->ReplaceInput(1, n4); - n19->ReplaceInput(2, n7); - n19->ReplaceInput(3, n8); - op = common_builder.IfFalse(); - Node* n18 = graph.NewNode(op, nil); - USE(n18); - n18->ReplaceInput(0, n9); - n19->ReplaceInput(4, n18); - n20->ReplaceInput(0, n19); - n20->ReplaceInput(1, n2); - n20->ReplaceInput(2, n7); - n20->ReplaceInput(3, n19); - n20->ReplaceInput(4, n18); - n21->ReplaceInput(0, n20); - n21->ReplaceInput(1, n20); - n21->ReplaceInput(2, n18); - n22->ReplaceInput(1, n21); - n23->ReplaceInput(0, n22); - - graph.SetStart(n0); - graph.SetEnd(n23); - - ComputeAndVerifySchedule(20, &graph); -} - - -TEST(BuildScheduleSimpleLoop) { - HandleAndZoneScope scope; - Isolate* isolate = scope.main_isolate(); - Graph graph(scope.main_zone()); - CommonOperatorBuilder common_builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - const Operator* op; - - Handle<HeapObject> object = - Handle<HeapObject>(isolate->heap()->undefined_value(), isolate); - Unique<HeapObject> unique_constant = - Unique<HeapObject>::CreateUninitialized(object); - - // Manually transcripted code for: - // function turbo_fan_test(a, b) { - // while (a < b) { - // a++; - // } - // return a; - // } - op = common_builder.Start(0); - Node* n0 = graph.NewNode(op); - USE(n0); - Node* nil = graph.NewNode(common_builder.Dead()); - op = common_builder.End(); - Node* n20 = graph.NewNode(op, nil); - USE(n20); - op = common_builder.Return(); - Node* n19 = graph.NewNode(op, nil, nil, nil); - USE(n19); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n8 = graph.NewNode(op, nil, nil, nil); - USE(n8); - op = common_builder.Parameter(0); - Node* n2 = graph.NewNode(op, n0); - USE(n2); - n8->ReplaceInput(0, n2); - op = js_builder.Add(); - Node* n18 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n18); - op = js_builder.ToNumber(); - Node* n16 = graph.NewNode(op, nil, nil, nil, nil); - USE(n16); - n16->ReplaceInput(0, n8); - op = common_builder.HeapConstant(unique_constant); - Node* n5 = graph.NewNode(op); - USE(n5); - n16->ReplaceInput(1, n5); - op = js_builder.LessThan(); - Node* n12 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n12); - n12->ReplaceInput(0, n8); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n9 = graph.NewNode(op, nil, nil, nil); - USE(n9); - op = common_builder.Parameter(0); - Node* n3 = graph.NewNode(op, n0); - USE(n3); - n9->ReplaceInput(0, n3); - n9->ReplaceInput(1, n9); - op = common_builder.Loop(2); - Node* n6 = graph.NewNode(op, nil, nil); - USE(n6); - n6->ReplaceInput(0, n0); - op = common_builder.IfTrue(); - Node* n14 = graph.NewNode(op, nil); - USE(n14); - op = common_builder.Branch(); - Node* n13 = graph.NewNode(op, nil, nil); - USE(n13); - n13->ReplaceInput(0, n12); - n13->ReplaceInput(1, n6); - n14->ReplaceInput(0, n13); - n6->ReplaceInput(1, n14); - n9->ReplaceInput(2, n6); - n12->ReplaceInput(1, n9); - n12->ReplaceInput(2, n5); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n10 = graph.NewNode(op, nil, nil, nil); - USE(n10); - n10->ReplaceInput(0, n0); - n10->ReplaceInput(1, n18); - n10->ReplaceInput(2, n6); - n12->ReplaceInput(3, n10); - n12->ReplaceInput(4, n6); - n16->ReplaceInput(2, n12); - n16->ReplaceInput(3, n14); - n18->ReplaceInput(0, n16); - op = common_builder.NumberConstant(0); - Node* n17 = graph.NewNode(op); - USE(n17); - n18->ReplaceInput(1, n17); - n18->ReplaceInput(2, n5); - n18->ReplaceInput(3, n16); - n18->ReplaceInput(4, n14); - n8->ReplaceInput(1, n18); - n8->ReplaceInput(2, n6); - n19->ReplaceInput(0, n8); - n19->ReplaceInput(1, n12); - op = common_builder.IfFalse(); - Node* n15 = graph.NewNode(op, nil); - USE(n15); - n15->ReplaceInput(0, n13); - n19->ReplaceInput(2, n15); - n20->ReplaceInput(0, n19); - - graph.SetStart(n0); - graph.SetEnd(n20); - - ComputeAndVerifySchedule(19, &graph); -} - - -TEST(BuildScheduleComplexLoops) { - HandleAndZoneScope scope; - Isolate* isolate = scope.main_isolate(); - Graph graph(scope.main_zone()); - CommonOperatorBuilder common_builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - const Operator* op; - - Handle<HeapObject> object = - Handle<HeapObject>(isolate->heap()->undefined_value(), isolate); - Unique<HeapObject> unique_constant = - Unique<HeapObject>::CreateUninitialized(object); - - // Manually transcripted code for: - // function turbo_fan_test(a, b, c) { - // while (a < b) { - // a++; - // while (c < b) { - // c++; - // } - // } - // while (a < b) { - // a += 2; - // } - // return a; - // } - op = common_builder.Start(0); - Node* n0 = graph.NewNode(op); - USE(n0); - Node* nil = graph.NewNode(common_builder.Dead()); - op = common_builder.End(); - Node* n46 = graph.NewNode(op, nil); - USE(n46); - op = common_builder.Return(); - Node* n45 = graph.NewNode(op, nil, nil, nil); - USE(n45); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n35 = graph.NewNode(op, nil, nil, nil); - USE(n35); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n9 = graph.NewNode(op, nil, nil, nil); - USE(n9); - op = common_builder.Parameter(0); - Node* n2 = graph.NewNode(op, n0); - USE(n2); - n9->ReplaceInput(0, n2); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n23 = graph.NewNode(op, nil, nil, nil); - USE(n23); - op = js_builder.Add(); - Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n20); - op = js_builder.ToNumber(); - Node* n18 = graph.NewNode(op, nil, nil, nil, nil); - USE(n18); - n18->ReplaceInput(0, n9); - op = common_builder.HeapConstant(unique_constant); - Node* n6 = graph.NewNode(op); - USE(n6); - n18->ReplaceInput(1, n6); - op = js_builder.LessThan(); - Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n14); - n14->ReplaceInput(0, n9); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n10 = graph.NewNode(op, nil, nil, nil); - USE(n10); - op = common_builder.Parameter(0); - Node* n3 = graph.NewNode(op, n0); - USE(n3); - n10->ReplaceInput(0, n3); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n24 = graph.NewNode(op, nil, nil, nil); - USE(n24); - n24->ReplaceInput(0, n10); - n24->ReplaceInput(1, n24); - op = common_builder.Loop(2); - Node* n21 = graph.NewNode(op, nil, nil); - USE(n21); - op = common_builder.IfTrue(); - Node* n16 = graph.NewNode(op, nil); - USE(n16); - op = common_builder.Branch(); - Node* n15 = graph.NewNode(op, nil, nil); - USE(n15); - n15->ReplaceInput(0, n14); - op = common_builder.Loop(2); - Node* n7 = graph.NewNode(op, nil, nil); - USE(n7); - n7->ReplaceInput(0, n0); - op = common_builder.IfFalse(); - Node* n30 = graph.NewNode(op, nil); - USE(n30); - op = common_builder.Branch(); - Node* n28 = graph.NewNode(op, nil, nil); - USE(n28); - op = js_builder.LessThan(); - Node* n27 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n27); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n25 = graph.NewNode(op, nil, nil, nil); - USE(n25); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n11 = graph.NewNode(op, nil, nil, nil); - USE(n11); - op = common_builder.Parameter(0); - Node* n4 = graph.NewNode(op, n0); - USE(n4); - n11->ReplaceInput(0, n4); - n11->ReplaceInput(1, n25); - n11->ReplaceInput(2, n7); - n25->ReplaceInput(0, n11); - op = js_builder.Add(); - Node* n32 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n32); - op = js_builder.ToNumber(); - Node* n31 = graph.NewNode(op, nil, nil, nil, nil); - USE(n31); - n31->ReplaceInput(0, n25); - n31->ReplaceInput(1, n6); - n31->ReplaceInput(2, n27); - op = common_builder.IfTrue(); - Node* n29 = graph.NewNode(op, nil); - USE(n29); - n29->ReplaceInput(0, n28); - n31->ReplaceInput(3, n29); - n32->ReplaceInput(0, n31); - op = common_builder.NumberConstant(0); - Node* n19 = graph.NewNode(op); - USE(n19); - n32->ReplaceInput(1, n19); - n32->ReplaceInput(2, n6); - n32->ReplaceInput(3, n31); - n32->ReplaceInput(4, n29); - n25->ReplaceInput(1, n32); - n25->ReplaceInput(2, n21); - n27->ReplaceInput(0, n25); - n27->ReplaceInput(1, n24); - n27->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n26 = graph.NewNode(op, nil, nil, nil); - USE(n26); - n26->ReplaceInput(0, n20); - n26->ReplaceInput(1, n32); - n26->ReplaceInput(2, n21); - n27->ReplaceInput(3, n26); - n27->ReplaceInput(4, n21); - n28->ReplaceInput(0, n27); - n28->ReplaceInput(1, n21); - n30->ReplaceInput(0, n28); - n7->ReplaceInput(1, n30); - n15->ReplaceInput(1, n7); - n16->ReplaceInput(0, n15); - n21->ReplaceInput(0, n16); - n21->ReplaceInput(1, n29); - n24->ReplaceInput(2, n21); - n10->ReplaceInput(1, n24); - n10->ReplaceInput(2, n7); - n14->ReplaceInput(1, n10); - n14->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n12 = graph.NewNode(op, nil, nil, nil); - USE(n12); - n12->ReplaceInput(0, n0); - n12->ReplaceInput(1, n27); - n12->ReplaceInput(2, n7); - n14->ReplaceInput(3, n12); - n14->ReplaceInput(4, n7); - n18->ReplaceInput(2, n14); - n18->ReplaceInput(3, n16); - n20->ReplaceInput(0, n18); - n20->ReplaceInput(1, n19); - n20->ReplaceInput(2, n6); - n20->ReplaceInput(3, n18); - n20->ReplaceInput(4, n16); - n23->ReplaceInput(0, n20); - n23->ReplaceInput(1, n23); - n23->ReplaceInput(2, n21); - n9->ReplaceInput(1, n23); - n9->ReplaceInput(2, n7); - n35->ReplaceInput(0, n9); - op = js_builder.Add(); - Node* n44 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n44); - n44->ReplaceInput(0, n35); - op = common_builder.NumberConstant(0); - Node* n43 = graph.NewNode(op); - USE(n43); - n44->ReplaceInput(1, n43); - n44->ReplaceInput(2, n6); - op = js_builder.LessThan(); - Node* n39 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n39); - n39->ReplaceInput(0, n35); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n36 = graph.NewNode(op, nil, nil, nil); - USE(n36); - n36->ReplaceInput(0, n10); - n36->ReplaceInput(1, n36); - op = common_builder.Loop(2); - Node* n33 = graph.NewNode(op, nil, nil); - USE(n33); - op = common_builder.IfFalse(); - Node* n17 = graph.NewNode(op, nil); - USE(n17); - n17->ReplaceInput(0, n15); - n33->ReplaceInput(0, n17); - op = common_builder.IfTrue(); - Node* n41 = graph.NewNode(op, nil); - USE(n41); - op = common_builder.Branch(); - Node* n40 = graph.NewNode(op, nil, nil); - USE(n40); - n40->ReplaceInput(0, n39); - n40->ReplaceInput(1, n33); - n41->ReplaceInput(0, n40); - n33->ReplaceInput(1, n41); - n36->ReplaceInput(2, n33); - n39->ReplaceInput(1, n36); - n39->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n38 = graph.NewNode(op, nil, nil, nil); - USE(n38); - n38->ReplaceInput(0, n14); - n38->ReplaceInput(1, n44); - n38->ReplaceInput(2, n33); - n39->ReplaceInput(3, n38); - n39->ReplaceInput(4, n33); - n44->ReplaceInput(3, n39); - n44->ReplaceInput(4, n41); - n35->ReplaceInput(1, n44); - n35->ReplaceInput(2, n33); - n45->ReplaceInput(0, n35); - n45->ReplaceInput(1, n39); - op = common_builder.IfFalse(); - Node* n42 = graph.NewNode(op, nil); - USE(n42); - n42->ReplaceInput(0, n40); - n45->ReplaceInput(2, n42); - n46->ReplaceInput(0, n45); - - graph.SetStart(n0); - graph.SetEnd(n46); - - ComputeAndVerifySchedule(46, &graph); -} - - -TEST(BuildScheduleBreakAndContinue) { - HandleAndZoneScope scope; - Isolate* isolate = scope.main_isolate(); - Graph graph(scope.main_zone()); - CommonOperatorBuilder common_builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - const Operator* op; - - Handle<HeapObject> object = - Handle<HeapObject>(isolate->heap()->undefined_value(), isolate); - Unique<HeapObject> unique_constant = - Unique<HeapObject>::CreateUninitialized(object); - - // Manually transcripted code for: - // function turbo_fan_test(a, b, c) { - // var d = 0; - // while (a < b) { - // a++; - // while (c < b) { - // c++; - // if (d == 0) break; - // a++; - // } - // if (a == 1) continue; - // d++; - // } - // return a + d; - // } - op = common_builder.Start(0); - Node* n0 = graph.NewNode(op); - USE(n0); - Node* nil = graph.NewNode(common_builder.Dead()); - op = common_builder.End(); - Node* n58 = graph.NewNode(op, nil); - USE(n58); - op = common_builder.Return(); - Node* n57 = graph.NewNode(op, nil, nil, nil); - USE(n57); - op = js_builder.Add(); - Node* n56 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n56); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n10 = graph.NewNode(op, nil, nil, nil); - USE(n10); - op = common_builder.Parameter(0); - Node* n2 = graph.NewNode(op, n0); - USE(n2); - n10->ReplaceInput(0, n2); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n25 = graph.NewNode(op, nil, nil, nil); - USE(n25); - op = js_builder.Add(); - Node* n22 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n22); - op = js_builder.ToNumber(); - Node* n20 = graph.NewNode(op, nil, nil, nil, nil); - USE(n20); - n20->ReplaceInput(0, n10); - op = common_builder.HeapConstant(unique_constant); - Node* n6 = graph.NewNode(op); - USE(n6); - n20->ReplaceInput(1, n6); - op = js_builder.LessThan(); - Node* n16 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n16); - n16->ReplaceInput(0, n10); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n11 = graph.NewNode(op, nil, nil, nil); - USE(n11); - op = common_builder.Parameter(0); - Node* n3 = graph.NewNode(op, n0); - USE(n3); - n11->ReplaceInput(0, n3); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n26 = graph.NewNode(op, nil, nil, nil); - USE(n26); - n26->ReplaceInput(0, n11); - n26->ReplaceInput(1, n26); - op = common_builder.Loop(2); - Node* n23 = graph.NewNode(op, nil, nil); - USE(n23); - op = common_builder.IfTrue(); - Node* n18 = graph.NewNode(op, nil); - USE(n18); - op = common_builder.Branch(); - Node* n17 = graph.NewNode(op, nil, nil); - USE(n17); - n17->ReplaceInput(0, n16); - op = common_builder.Loop(2); - Node* n8 = graph.NewNode(op, nil, nil); - USE(n8); - n8->ReplaceInput(0, n0); - op = common_builder.Merge(2); - Node* n53 = graph.NewNode(op, nil, nil); - USE(n53); - op = common_builder.IfTrue(); - Node* n49 = graph.NewNode(op, nil); - USE(n49); - op = common_builder.Branch(); - Node* n48 = graph.NewNode(op, nil, nil); - USE(n48); - op = js_builder.Equal(); - Node* n47 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n47); - n47->ReplaceInput(0, n25); - op = common_builder.NumberConstant(0); - Node* n46 = graph.NewNode(op); - USE(n46); - n47->ReplaceInput(1, n46); - n47->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n42 = graph.NewNode(op, nil, nil, nil); - USE(n42); - op = js_builder.LessThan(); - Node* n30 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n30); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n27 = graph.NewNode(op, nil, nil, nil); - USE(n27); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n12 = graph.NewNode(op, nil, nil, nil); - USE(n12); - op = common_builder.Parameter(0); - Node* n4 = graph.NewNode(op, n0); - USE(n4); - n12->ReplaceInput(0, n4); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n41 = graph.NewNode(op, nil, nil, nil); - USE(n41); - n41->ReplaceInput(0, n27); - op = js_builder.Add(); - Node* n35 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n35); - op = js_builder.ToNumber(); - Node* n34 = graph.NewNode(op, nil, nil, nil, nil); - USE(n34); - n34->ReplaceInput(0, n27); - n34->ReplaceInput(1, n6); - n34->ReplaceInput(2, n30); - op = common_builder.IfTrue(); - Node* n32 = graph.NewNode(op, nil); - USE(n32); - op = common_builder.Branch(); - Node* n31 = graph.NewNode(op, nil, nil); - USE(n31); - n31->ReplaceInput(0, n30); - n31->ReplaceInput(1, n23); - n32->ReplaceInput(0, n31); - n34->ReplaceInput(3, n32); - n35->ReplaceInput(0, n34); - op = common_builder.NumberConstant(0); - Node* n21 = graph.NewNode(op); - USE(n21); - n35->ReplaceInput(1, n21); - n35->ReplaceInput(2, n6); - n35->ReplaceInput(3, n34); - n35->ReplaceInput(4, n32); - n41->ReplaceInput(1, n35); - op = common_builder.Merge(2); - Node* n40 = graph.NewNode(op, nil, nil); - USE(n40); - op = common_builder.IfFalse(); - Node* n33 = graph.NewNode(op, nil); - USE(n33); - n33->ReplaceInput(0, n31); - n40->ReplaceInput(0, n33); - op = common_builder.IfTrue(); - Node* n39 = graph.NewNode(op, nil); - USE(n39); - op = common_builder.Branch(); - Node* n38 = graph.NewNode(op, nil, nil); - USE(n38); - op = js_builder.Equal(); - Node* n37 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n37); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n28 = graph.NewNode(op, nil, nil, nil); - USE(n28); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n13 = graph.NewNode(op, nil, nil, nil); - USE(n13); - op = common_builder.NumberConstant(0); - Node* n7 = graph.NewNode(op); - USE(n7); - n13->ReplaceInput(0, n7); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n54 = graph.NewNode(op, nil, nil, nil); - USE(n54); - n54->ReplaceInput(0, n28); - op = js_builder.Add(); - Node* n52 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n52); - op = js_builder.ToNumber(); - Node* n51 = graph.NewNode(op, nil, nil, nil, nil); - USE(n51); - n51->ReplaceInput(0, n28); - n51->ReplaceInput(1, n6); - n51->ReplaceInput(2, n47); - op = common_builder.IfFalse(); - Node* n50 = graph.NewNode(op, nil); - USE(n50); - n50->ReplaceInput(0, n48); - n51->ReplaceInput(3, n50); - n52->ReplaceInput(0, n51); - n52->ReplaceInput(1, n21); - n52->ReplaceInput(2, n6); - n52->ReplaceInput(3, n51); - n52->ReplaceInput(4, n50); - n54->ReplaceInput(1, n52); - n54->ReplaceInput(2, n53); - n13->ReplaceInput(1, n54); - n13->ReplaceInput(2, n8); - n28->ReplaceInput(0, n13); - n28->ReplaceInput(1, n28); - n28->ReplaceInput(2, n23); - n37->ReplaceInput(0, n28); - op = common_builder.NumberConstant(0); - Node* n36 = graph.NewNode(op); - USE(n36); - n37->ReplaceInput(1, n36); - n37->ReplaceInput(2, n6); - n37->ReplaceInput(3, n35); - n37->ReplaceInput(4, n32); - n38->ReplaceInput(0, n37); - n38->ReplaceInput(1, n32); - n39->ReplaceInput(0, n38); - n40->ReplaceInput(1, n39); - n41->ReplaceInput(2, n40); - n12->ReplaceInput(1, n41); - n12->ReplaceInput(2, n8); - n27->ReplaceInput(0, n12); - n27->ReplaceInput(1, n35); - n27->ReplaceInput(2, n23); - n30->ReplaceInput(0, n27); - n30->ReplaceInput(1, n26); - n30->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n29 = graph.NewNode(op, nil, nil, nil); - USE(n29); - n29->ReplaceInput(0, n22); - op = js_builder.Add(); - Node* n45 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n45); - op = js_builder.ToNumber(); - Node* n44 = graph.NewNode(op, nil, nil, nil, nil); - USE(n44); - n44->ReplaceInput(0, n25); - n44->ReplaceInput(1, n6); - n44->ReplaceInput(2, n37); - op = common_builder.IfFalse(); - Node* n43 = graph.NewNode(op, nil); - USE(n43); - n43->ReplaceInput(0, n38); - n44->ReplaceInput(3, n43); - n45->ReplaceInput(0, n44); - n45->ReplaceInput(1, n21); - n45->ReplaceInput(2, n6); - n45->ReplaceInput(3, n44); - n45->ReplaceInput(4, n43); - n29->ReplaceInput(1, n45); - n29->ReplaceInput(2, n23); - n30->ReplaceInput(3, n29); - n30->ReplaceInput(4, n23); - n42->ReplaceInput(0, n30); - n42->ReplaceInput(1, n37); - n42->ReplaceInput(2, n40); - n47->ReplaceInput(3, n42); - n47->ReplaceInput(4, n40); - n48->ReplaceInput(0, n47); - n48->ReplaceInput(1, n40); - n49->ReplaceInput(0, n48); - n53->ReplaceInput(0, n49); - n53->ReplaceInput(1, n50); - n8->ReplaceInput(1, n53); - n17->ReplaceInput(1, n8); - n18->ReplaceInput(0, n17); - n23->ReplaceInput(0, n18); - n23->ReplaceInput(1, n43); - n26->ReplaceInput(2, n23); - n11->ReplaceInput(1, n26); - n11->ReplaceInput(2, n8); - n16->ReplaceInput(1, n11); - n16->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n14 = graph.NewNode(op, nil, nil, nil); - USE(n14); - n14->ReplaceInput(0, n0); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n55 = graph.NewNode(op, nil, nil, nil); - USE(n55); - n55->ReplaceInput(0, n47); - n55->ReplaceInput(1, n52); - n55->ReplaceInput(2, n53); - n14->ReplaceInput(1, n55); - n14->ReplaceInput(2, n8); - n16->ReplaceInput(3, n14); - n16->ReplaceInput(4, n8); - n20->ReplaceInput(2, n16); - n20->ReplaceInput(3, n18); - n22->ReplaceInput(0, n20); - n22->ReplaceInput(1, n21); - n22->ReplaceInput(2, n6); - n22->ReplaceInput(3, n20); - n22->ReplaceInput(4, n18); - n25->ReplaceInput(0, n22); - n25->ReplaceInput(1, n45); - n25->ReplaceInput(2, n23); - n10->ReplaceInput(1, n25); - n10->ReplaceInput(2, n8); - n56->ReplaceInput(0, n10); - n56->ReplaceInput(1, n13); - n56->ReplaceInput(2, n6); - n56->ReplaceInput(3, n16); - op = common_builder.IfFalse(); - Node* n19 = graph.NewNode(op, nil); - USE(n19); - n19->ReplaceInput(0, n17); - n56->ReplaceInput(4, n19); - n57->ReplaceInput(0, n56); - n57->ReplaceInput(1, n56); - n57->ReplaceInput(2, n19); - n58->ReplaceInput(0, n57); - - graph.SetStart(n0); - graph.SetEnd(n58); - - ComputeAndVerifySchedule(62, &graph); -} - - -TEST(BuildScheduleSimpleLoopWithCodeMotion) { - HandleAndZoneScope scope; - Isolate* isolate = scope.main_isolate(); - Graph graph(scope.main_zone()); - CommonOperatorBuilder common_builder(scope.main_zone()); - JSOperatorBuilder js_builder(scope.main_zone()); - const Operator* op; - - Handle<HeapObject> object = - Handle<HeapObject>(isolate->heap()->undefined_value(), isolate); - Unique<HeapObject> unique_constant = - Unique<HeapObject>::CreateUninitialized(object); - - // Manually transcripted code for: - // function turbo_fan_test(a, b, c) { - // while (a < b) { - // a += b + c; - // } - // return a; - // } - op = common_builder.Start(0); - Node* n0 = graph.NewNode(op); - USE(n0); - Node* nil = graph.NewNode(common_builder.Dead()); - op = common_builder.End(); - Node* n22 = graph.NewNode(op, nil); - USE(n22); - op = common_builder.Return(); - Node* n21 = graph.NewNode(op, nil, nil, nil); - USE(n21); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n9 = graph.NewNode(op, nil, nil, nil); - USE(n9); - op = common_builder.Parameter(0); - Node* n2 = graph.NewNode(op, n0); - USE(n2); - n9->ReplaceInput(0, n2); - op = js_builder.Add(); - Node* n20 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n20); - n20->ReplaceInput(0, n9); - op = &kIntAdd; - Node* n19 = graph.NewNode(op, nil, nil); - USE(n19); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n10 = graph.NewNode(op, nil, nil, nil); - USE(n10); - op = common_builder.Parameter(0); - Node* n3 = graph.NewNode(op, n0); - USE(n3); - n10->ReplaceInput(0, n3); - n10->ReplaceInput(1, n10); - op = common_builder.Loop(2); - Node* n7 = graph.NewNode(op, nil, nil); - USE(n7); - n7->ReplaceInput(0, n0); - op = common_builder.IfTrue(); - Node* n17 = graph.NewNode(op, nil); - USE(n17); - op = common_builder.Branch(); - Node* n16 = graph.NewNode(op, nil, nil); - USE(n16); - op = js_builder.ToBoolean(); - Node* n15 = graph.NewNode(op, nil, nil, nil, nil); - USE(n15); - op = js_builder.LessThan(); - Node* n14 = graph.NewNode(op, nil, nil, nil, nil, nil); - USE(n14); - n14->ReplaceInput(0, n9); - n14->ReplaceInput(1, n10); - op = common_builder.HeapConstant(unique_constant); - Node* n6 = graph.NewNode(op); - USE(n6); - n14->ReplaceInput(2, n6); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n12 = graph.NewNode(op, nil, nil, nil); - USE(n12); - n12->ReplaceInput(0, n0); - n12->ReplaceInput(1, n20); - n12->ReplaceInput(2, n7); - n14->ReplaceInput(3, n12); - n14->ReplaceInput(4, n7); - n15->ReplaceInput(0, n14); - n15->ReplaceInput(1, n6); - n15->ReplaceInput(2, n14); - n15->ReplaceInput(3, n7); - n16->ReplaceInput(0, n15); - n16->ReplaceInput(1, n7); - n17->ReplaceInput(0, n16); - n7->ReplaceInput(1, n17); - n10->ReplaceInput(2, n7); - n19->ReplaceInput(0, n2); - op = common_builder.Phi(kMachAnyTagged, 2); - Node* n11 = graph.NewNode(op, nil, nil, nil); - USE(n11); - op = common_builder.Parameter(0); - Node* n4 = graph.NewNode(op, n0); - USE(n4); - n11->ReplaceInput(0, n4); - n11->ReplaceInput(1, n11); - n11->ReplaceInput(2, n7); - n19->ReplaceInput(1, n3); - n20->ReplaceInput(1, n19); - n20->ReplaceInput(2, n6); - n20->ReplaceInput(3, n19); - n20->ReplaceInput(4, n17); - n9->ReplaceInput(1, n20); - n9->ReplaceInput(2, n7); - n21->ReplaceInput(0, n9); - n21->ReplaceInput(1, n15); - op = common_builder.IfFalse(); - Node* n18 = graph.NewNode(op, nil); - USE(n18); - n18->ReplaceInput(0, n16); - n21->ReplaceInput(2, n18); - n22->ReplaceInput(0, n21); - - graph.SetStart(n0); - graph.SetEnd(n22); - - Schedule* schedule = ComputeAndVerifySchedule(19, &graph); - // Make sure the integer-only add gets hoisted to a different block that the - // JSAdd. - CHECK(schedule->block(n19) != schedule->block(n20)); -} - - -#if V8_TURBOFAN_TARGET - -static Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, - Node* cond) { - Node* tv = graph->NewNode(common->Int32Constant(6)); - Node* fv = graph->NewNode(common->Int32Constant(7)); - Node* br = graph->NewNode(common->Branch(), cond, graph->start()); - Node* t = graph->NewNode(common->IfTrue(), br); - Node* f = graph->NewNode(common->IfFalse(), br); - Node* m = graph->NewNode(common->Merge(2), t, f); - Node* phi = graph->NewNode(common->Phi(kMachAnyTagged, 2), tv, fv, m); - return phi; -} - - -TEST(FloatingDiamond1) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(1)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* d1 = CreateDiamond(&graph, &common, p0); - Node* ret = graph.NewNode(common.Return(), d1, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(13, &graph); -} - - -TEST(FloatingDiamond2) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* p1 = graph.NewNode(common.Parameter(1), start); - Node* d1 = CreateDiamond(&graph, &common, p0); - Node* d2 = CreateDiamond(&graph, &common, p1); - Node* add = graph.NewNode(&kIntAdd, d1, d2); - Node* ret = graph.NewNode(common.Return(), add, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(24, &graph); -} - - -TEST(FloatingDiamond3) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* p1 = graph.NewNode(common.Parameter(1), start); - Node* d1 = CreateDiamond(&graph, &common, p0); - Node* d2 = CreateDiamond(&graph, &common, p1); - Node* add = graph.NewNode(&kIntAdd, d1, d2); - Node* d3 = CreateDiamond(&graph, &common, add); - Node* ret = graph.NewNode(common.Return(), d3, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(33, &graph); -} - - -TEST(NestedFloatingDiamonds) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - SimplifiedOperatorBuilder simplified(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - - Node* fv = graph.NewNode(common.Int32Constant(7)); - Node* br = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - - Node* map = graph.NewNode( - simplified.LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0, p0, - start, f); - Node* br1 = graph.NewNode(common.Branch(), map, graph.start()); - Node* t1 = graph.NewNode(common.IfTrue(), br1); - Node* f1 = graph.NewNode(common.IfFalse(), br1); - Node* m1 = graph.NewNode(common.Merge(2), t1, f1); - Node* ttrue = graph.NewNode(common.Int32Constant(1)); - Node* ffalse = graph.NewNode(common.Int32Constant(0)); - Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), ttrue, ffalse, m1); - - - Node* m = graph.NewNode(common.Merge(2), t, f); - Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), fv, phi1, m); - Node* ephi1 = graph.NewNode(common.EffectPhi(2), start, map, m); - - Node* ret = graph.NewNode(common.Return(), phi, ephi1, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(23, &graph); -} - - -TEST(NestedFloatingDiamondWithChain) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* p1 = graph.NewNode(common.Parameter(1), start); - Node* c = graph.NewNode(common.Int32Constant(7)); - - Node* brA1 = graph.NewNode(common.Branch(), p0, graph.start()); - Node* tA1 = graph.NewNode(common.IfTrue(), brA1); - Node* fA1 = graph.NewNode(common.IfFalse(), brA1); - Node* mA1 = graph.NewNode(common.Merge(2), tA1, fA1); - Node* phiA1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p1, mA1); - - Node* brB1 = graph.NewNode(common.Branch(), p1, graph.start()); - Node* tB1 = graph.NewNode(common.IfTrue(), brB1); - Node* fB1 = graph.NewNode(common.IfFalse(), brB1); - Node* mB1 = graph.NewNode(common.Merge(2), tB1, fB1); - Node* phiB1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p1, mB1); - - Node* brA2 = graph.NewNode(common.Branch(), phiB1, mA1); - Node* tA2 = graph.NewNode(common.IfTrue(), brA2); - Node* fA2 = graph.NewNode(common.IfFalse(), brA2); - Node* mA2 = graph.NewNode(common.Merge(2), tA2, fA2); - Node* phiA2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phiB1, c, mA2); - - Node* brB2 = graph.NewNode(common.Branch(), phiA1, mB1); - Node* tB2 = graph.NewNode(common.IfTrue(), brB2); - Node* fB2 = graph.NewNode(common.IfFalse(), brB2); - Node* mB2 = graph.NewNode(common.Merge(2), tB2, fB2); - Node* phiB2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phiA1, c, mB2); - - Node* add = graph.NewNode(&kIntAdd, phiA2, phiB2); - Node* ret = graph.NewNode(common.Return(), add, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(35, &graph); -} - - -TEST(NestedFloatingDiamondWithLoop) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - - Node* fv = graph.NewNode(common.Int32Constant(7)); - Node* br = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - - Node* loop = graph.NewNode(common.Loop(2), f, start); - Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop); - - Node* add = graph.NewNode(&kIntAdd, ind, fv); - Node* br1 = graph.NewNode(common.Branch(), add, loop); - Node* t1 = graph.NewNode(common.IfTrue(), br1); - Node* f1 = graph.NewNode(common.IfFalse(), br1); - - loop->ReplaceInput(1, t1); // close loop. - ind->ReplaceInput(1, ind); // close induction variable. - - Node* m = graph.NewNode(common.Merge(2), t, f1); - Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), fv, ind, m); - - Node* ret = graph.NewNode(common.Return(), phi, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(20, &graph); -} - - -TEST(LoopedFloatingDiamond1) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - - Node* c = graph.NewNode(common.Int32Constant(7)); - Node* loop = graph.NewNode(common.Loop(2), start, start); - Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop); - Node* add = graph.NewNode(&kIntAdd, ind, c); - - Node* br = graph.NewNode(common.Branch(), add, loop); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - - Node* br1 = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t1 = graph.NewNode(common.IfTrue(), br1); - Node* f1 = graph.NewNode(common.IfFalse(), br1); - Node* m1 = graph.NewNode(common.Merge(2), t1, f1); - Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), add, p0, m1); - - loop->ReplaceInput(1, t); // close loop. - ind->ReplaceInput(1, phi1); // close induction variable. - - Node* ret = graph.NewNode(common.Return(), ind, start, f); - Node* end = graph.NewNode(common.End(), ret, f); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(20, &graph); -} - - -TEST(LoopedFloatingDiamond2) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - - Node* c = graph.NewNode(common.Int32Constant(7)); - Node* loop = graph.NewNode(common.Loop(2), start, start); - Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop); - - Node* br1 = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t1 = graph.NewNode(common.IfTrue(), br1); - Node* f1 = graph.NewNode(common.IfFalse(), br1); - Node* m1 = graph.NewNode(common.Merge(2), t1, f1); - Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), c, ind, m1); - - Node* add = graph.NewNode(&kIntAdd, ind, phi1); - - Node* br = graph.NewNode(common.Branch(), add, loop); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - - loop->ReplaceInput(1, t); // close loop. - ind->ReplaceInput(1, add); // close induction variable. - - Node* ret = graph.NewNode(common.Return(), ind, start, f); - Node* end = graph.NewNode(common.End(), ret, f); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(20, &graph); -} - - -TEST(LoopedFloatingDiamond3) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - - Node* c = graph.NewNode(common.Int32Constant(7)); - Node* loop = graph.NewNode(common.Loop(2), start, start); - Node* ind = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop); - - Node* br1 = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t1 = graph.NewNode(common.IfTrue(), br1); - Node* f1 = graph.NewNode(common.IfFalse(), br1); - - Node* loop1 = graph.NewNode(common.Loop(2), t1, start); - Node* ind1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), p0, p0, loop); - - Node* add1 = graph.NewNode(&kIntAdd, ind1, c); - Node* br2 = graph.NewNode(common.Branch(), add1, loop1); - Node* t2 = graph.NewNode(common.IfTrue(), br2); - Node* f2 = graph.NewNode(common.IfFalse(), br2); - - loop1->ReplaceInput(1, t2); // close inner loop. - ind1->ReplaceInput(1, ind1); // close inner induction variable. - - Node* m1 = graph.NewNode(common.Merge(2), f1, f2); - Node* phi1 = graph.NewNode(common.Phi(kMachAnyTagged, 2), c, ind1, m1); - - Node* add = graph.NewNode(&kIntAdd, ind, phi1); - - Node* br = graph.NewNode(common.Branch(), add, loop); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - - loop->ReplaceInput(1, t); // close loop. - ind->ReplaceInput(1, add); // close induction variable. - - Node* ret = graph.NewNode(common.Return(), ind, start, f); - Node* end = graph.NewNode(common.End(), ret, f); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(28, &graph); -} - - -TEST(PhisPushedDownToDifferentBranches) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(2)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* p1 = graph.NewNode(common.Parameter(1), start); - - Node* v1 = graph.NewNode(common.Int32Constant(1)); - Node* v2 = graph.NewNode(common.Int32Constant(2)); - Node* v3 = graph.NewNode(common.Int32Constant(3)); - Node* v4 = graph.NewNode(common.Int32Constant(4)); - Node* br = graph.NewNode(common.Branch(), p0, graph.start()); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - Node* m = graph.NewNode(common.Merge(2), t, f); - Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), v1, v2, m); - Node* phi2 = graph.NewNode(common.Phi(kMachAnyTagged, 2), v3, v4, m); - - Node* br2 = graph.NewNode(common.Branch(), p1, graph.start()); - Node* t2 = graph.NewNode(common.IfTrue(), br2); - Node* f2 = graph.NewNode(common.IfFalse(), br2); - Node* m2 = graph.NewNode(common.Merge(2), t2, f2); - Node* phi3 = graph.NewNode(common.Phi(kMachAnyTagged, 2), phi, phi2, m2); - - Node* ret = graph.NewNode(common.Return(), phi3, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - ComputeAndVerifySchedule(24, &graph); -} - - -TEST(BranchHintTrue) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(1)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* tv = graph.NewNode(common.Int32Constant(6)); - Node* fv = graph.NewNode(common.Int32Constant(7)); - Node* br = graph.NewNode(common.Branch(BranchHint::kTrue), p0, start); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - Node* m = graph.NewNode(common.Merge(2), t, f); - Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m); - Node* ret = graph.NewNode(common.Return(), phi, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - Schedule* schedule = ComputeAndVerifySchedule(13, &graph); - // Make sure the false block is marked as deferred. - CHECK(!schedule->block(t)->deferred()); - CHECK(schedule->block(f)->deferred()); -} - - -TEST(BranchHintFalse) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(1)); - graph.SetStart(start); - - Node* p0 = graph.NewNode(common.Parameter(0), start); - Node* tv = graph.NewNode(common.Int32Constant(6)); - Node* fv = graph.NewNode(common.Int32Constant(7)); - Node* br = graph.NewNode(common.Branch(BranchHint::kFalse), p0, start); - Node* t = graph.NewNode(common.IfTrue(), br); - Node* f = graph.NewNode(common.IfFalse(), br); - Node* m = graph.NewNode(common.Merge(2), t, f); - Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 2), tv, fv, m); - Node* ret = graph.NewNode(common.Return(), phi, start, start); - Node* end = graph.NewNode(common.End(), ret, start); - - graph.SetEnd(end); - - Schedule* schedule = ComputeAndVerifySchedule(13, &graph); - // Make sure the true block is marked as deferred. - CHECK(schedule->block(t)->deferred()); - CHECK(!schedule->block(f)->deferred()); -} - - -TEST(ScheduleTerminate) { - HandleAndZoneScope scope; - Graph graph(scope.main_zone()); - CommonOperatorBuilder common(scope.main_zone()); - - Node* start = graph.NewNode(common.Start(1)); - graph.SetStart(start); - - Node* loop = graph.NewNode(common.Loop(2), start, start); - loop->ReplaceInput(1, loop); // self loop, NTL. - - Node* effect = graph.NewNode(common.EffectPhi(1), start, loop); - effect->ReplaceInput(0, effect); - - Node* terminate = graph.NewNode(common.Terminate(1), effect, loop); - Node* end = graph.NewNode(common.End(), terminate); - - graph.SetEnd(end); - - Schedule* schedule = ComputeAndVerifySchedule(6, &graph); - BasicBlock* block = schedule->block(loop); - CHECK_NE(NULL, loop); - CHECK_EQ(block, schedule->block(effect)); - CHECK_GE(block->rpo_number(), 0); -} - -#endif |