From 21013d2641d49cebdc0aafbf25de34c438a0a0e1 Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Fri, 24 Oct 2014 13:57:32 +0000 Subject: [PATCH] Fix bugs in Scheduler hoisting and RPO loop bounds computations. R=mstarzinger@chromium.org BUG= Review URL: https://codereview.chromium.org/677683002 Cr-Commit-Position: refs/heads/master@{#24877} git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24877 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/scheduler.cc | 67 ++++++++++-------- test/cctest/compiler/test-scheduler.cc | 120 +++++++++++++++++---------------- 2 files changed, 101 insertions(+), 86 deletions(-) diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index c0f05c5..a75a9ef 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -562,15 +562,26 @@ class SpecialRPONumberer { BasicBlockVector* final_order = schedule_->rpo_order(); order->Serialize(final_order); - // Compute the correct loop header for every block and set the correct loop - // ends. + // Compute the correct loop headers and set the correct loop ends. LoopInfo* current_loop = NULL; BasicBlock* current_header = NULL; int loop_depth = 0; for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end(); ++i) { BasicBlock* current = *i; + + // Finish the previous loop(s) if we just exited them. + while (current_header != NULL && + current->rpo_number() >= current_header->loop_end()) { + DCHECK(current_header->IsLoopHeader()); + DCHECK(current_loop != NULL); + current_loop = current_loop->prev; + current_header = current_loop == NULL ? NULL : current_loop->header; + --loop_depth; + } current->set_loop_header(current_header); + + // Push a new loop onto the stack if this loop is a loop header. if (current->IsLoopHeader()) { loop_depth++; current_loop = &loops[current->loop_end()]; @@ -581,17 +592,10 @@ class SpecialRPONumberer { current_header = current_loop->header; Trace("B%d is a loop header, increment loop depth to %d\n", current->id().ToInt(), loop_depth); - } else { - while (current_header != NULL && - current->rpo_number() >= current_header->loop_end()) { - DCHECK(current_header->IsLoopHeader()); - DCHECK(current_loop != NULL); - current_loop = current_loop->prev; - current_header = current_loop == NULL ? NULL : current_loop->header; - --loop_depth; - } } + current->set_loop_depth(loop_depth); + if (current->loop_header() == NULL) { Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(), current->loop_depth()); @@ -756,6 +760,12 @@ class SpecialRPONumberer { os << " range: [" << block->rpo_number() << ", " << block->loop_end() << ")"; } + if (block->loop_header() != NULL) { + os << " header: B" << block->loop_header()->id(); + } + if (block->loop_depth() > 0) { + os << " depth: " << block->loop_depth(); + } os << "\n"; } } @@ -775,6 +785,7 @@ class SpecialRPONumberer { DCHECK(header->loop_end() >= 0); DCHECK(header->loop_end() <= static_cast(order->size())); DCHECK(header->loop_end() > header->rpo_number()); + DCHECK(header->loop_header() != header); // Verify the start ... end list relationship. int links = 0; @@ -1074,31 +1085,29 @@ class ScheduleLateNodeVisitor { // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively // into enclosing loop pre-headers until they would preceed their // ScheduleEarly position. - BasicBlock* hoist_block = block; + BasicBlock* hoist_block = GetPreHeader(block); while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) { - if (hoist_block->loop_depth() < block->loop_depth()) { - block = hoist_block; - Trace(" hoisting #%d:%s to block %d\n", node->id(), - node->op()->mnemonic(), block->id().ToInt()); - } - // Try to hoist to the pre-header of the loop header. - hoist_block = hoist_block->loop_header(); - if (hoist_block != NULL) { - BasicBlock* pre_header = hoist_block->dominator(); - DCHECK(pre_header == NULL || - *hoist_block->predecessors_begin() == pre_header); - Trace( - " hoist to pre-header B%d of loop header B%d, depth would be %d\n", - pre_header->id().ToInt(), hoist_block->id().ToInt(), - pre_header->loop_depth()); - hoist_block = pre_header; - } + Trace(" hoisting #%d:%s to block %d\n", node->id(), + node->op()->mnemonic(), hoist_block->id().ToInt()); + DCHECK_LT(hoist_block->loop_depth(), block->loop_depth()); + block = hoist_block; + hoist_block = GetPreHeader(hoist_block); } ScheduleNode(block, node); } private: + BasicBlock* GetPreHeader(BasicBlock* block) { + if (block->IsLoopHeader()) { + return block->dominator(); + } else if (block->loop_header() != NULL) { + return block->loop_header()->dominator(); + } else { + return NULL; + } + } + BasicBlock* GetCommonDominatorOfUses(Node* node) { BasicBlock* block = NULL; Node::Uses uses = node->uses(); diff --git a/test/cctest/compiler/test-scheduler.cc b/test/cctest/compiler/test-scheduler.cc index 7117c9b..e866876 100644 --- a/test/cctest/compiler/test-scheduler.cc +++ b/test/cctest/compiler/test-scheduler.cc @@ -24,12 +24,47 @@ using namespace v8::internal; using namespace v8::internal::compiler; // 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(order->size()); i++) { + CHECK(order->at(i)->rpo_number() == i); + if (!loops_allowed) { + CHECK_LT(order->at(i)->loop_end(), 0); + CHECK_EQ(NULL, order->at(i)->loop_header()); + } + } +} + + +static void CheckLoop(BasicBlockVector* order, BasicBlock** blocks, + int body_size) { + BasicBlock* header = blocks[0]; + CHECK_GT(header->loop_end(), 0); + CHECK_EQ(body_size, (header->loop_end() - header->rpo_number())); + for (int i = 0; i < body_size; i++) { + int num = blocks[i]->rpo_number(); + CHECK(num >= header->rpo_number() && num < header->loop_end()); + 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 (header->loop_end() < static_cast(order->size())) { + CHECK_NE(order->at(header->loop_end())->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); } }; @@ -48,29 +83,6 @@ static TestLoop* CreateLoop(Schedule* schedule, int count) { } -static void CheckRPONumbers(BasicBlockVector* order, size_t expected, - bool loops_allowed) { - CHECK(expected == order->size()); - for (int i = 0; i < static_cast(order->size()); i++) { - CHECK(order->at(i)->rpo_number() == i); - if (!loops_allowed) CHECK_LT(order->at(i)->loop_end(), 0); - } -} - - -static void CheckLoopContains(BasicBlock** blocks, int body_size) { - BasicBlock* header = blocks[0]; - CHECK_GT(header->loop_end(), 0); - CHECK_EQ(body_size, (header->loop_end() - header->rpo_number())); - for (int i = 0; i < body_size; i++) { - int num = blocks[i]->rpo_number(); - CHECK(num >= header->rpo_number() && num < header->loop_end()); - CHECK(header->LoopContains(blocks[i])); - CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header); - } -} - - static int GetScheduledNodeCount(Schedule* schedule) { int node_count = 0; for (BasicBlockVectorIter i = schedule->rpo_order()->begin(); @@ -167,7 +179,7 @@ TEST(RPOSelfLoop) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 1, true); BasicBlock* loop[] = {schedule.start()}; - CheckLoopContains(loop, 1); + CheckLoop(order, loop, 1); } @@ -180,7 +192,7 @@ TEST(RPOEntryLoop) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 2, true); BasicBlock* loop[] = {schedule.start(), schedule.end()}; - CheckLoopContains(loop, 2); + CheckLoop(order, loop, 2); } @@ -192,7 +204,7 @@ TEST(RPOEndLoop) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 3, true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); } @@ -205,7 +217,7 @@ TEST(RPOEndLoopNested) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 3, true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); } @@ -252,7 +264,7 @@ TEST(RPOLoop1) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 4, true); BasicBlock* loop[] = {B, C}; - CheckLoopContains(loop, 2); + CheckLoop(order, loop, 2); } @@ -274,7 +286,7 @@ TEST(RPOLoop2) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 4, true); BasicBlock* loop[] = {B, C}; - CheckLoopContains(loop, 2); + CheckLoop(order, loop, 2); } @@ -318,7 +330,7 @@ TEST(RPOLoopN) { Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 7, true); BasicBlock* loop[] = {B, C, D, E, F}; - CheckLoopContains(loop, 5); + CheckLoop(order, loop, 5); } } @@ -346,10 +358,10 @@ TEST(RPOLoopNest1) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 6, true); BasicBlock* loop1[] = {B, C, D, E}; - CheckLoopContains(loop1, 4); + CheckLoop(order, loop1, 4); BasicBlock* loop2[] = {C, D}; - CheckLoopContains(loop2, 2); + CheckLoop(order, loop2, 2); } @@ -382,13 +394,13 @@ TEST(RPOLoopNest2) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, 8, true); BasicBlock* loop1[] = {B, C, D, E, F, G}; - CheckLoopContains(loop1, 6); + CheckLoop(order, loop1, 6); BasicBlock* loop2[] = {C, D, E, F}; - CheckLoopContains(loop2, 4); + CheckLoop(order, loop2, 4); BasicBlock* loop3[] = {D, E}; - CheckLoopContains(loop3, 2); + CheckLoop(order, loop3, 2); } @@ -409,12 +421,11 @@ TEST(RPOLoopFollow1) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); - CheckLoopContains(loop1->nodes, loop1->count); - CHECK_EQ(static_cast(schedule.BasicBlockCount()), static_cast(order->size())); - CheckLoopContains(loop1->nodes, loop1->count); - CheckLoopContains(loop2->nodes, loop2->count); + + loop1->Check(order); + loop2->Check(order); } @@ -437,12 +448,10 @@ TEST(RPOLoopFollow2) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); - CheckLoopContains(loop1->nodes, loop1->count); - CHECK_EQ(static_cast(schedule.BasicBlockCount()), static_cast(order->size())); - CheckLoopContains(loop1->nodes, loop1->count); - CheckLoopContains(loop2->nodes, loop2->count); + loop1->Check(order); + loop2->Check(order); } @@ -463,12 +472,11 @@ TEST(RPOLoopFollowN) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); - CheckLoopContains(loop1->nodes, loop1->count); CHECK_EQ(static_cast(schedule.BasicBlockCount()), static_cast(order->size())); - CheckLoopContains(loop1->nodes, loop1->count); - CheckLoopContains(loop2->nodes, loop2->count); + loop1->Check(order); + loop2->Check(order); } } } @@ -496,15 +504,13 @@ TEST(RPONestedLoopFollow1) { ZonePool zone_pool(scope.main_isolate()); BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); - CheckLoopContains(loop1->nodes, loop1->count); - CHECK_EQ(static_cast(schedule.BasicBlockCount()), static_cast(order->size())); - CheckLoopContains(loop1->nodes, loop1->count); - CheckLoopContains(loop2->nodes, loop2->count); + loop1->Check(order); + loop2->Check(order); BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C}; - CheckLoopContains(loop3, 4); + CheckLoop(order, loop3, 4); } @@ -529,7 +535,7 @@ TEST(RPOLoopBackedges1) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, schedule.BasicBlockCount(), true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); } } } @@ -558,7 +564,7 @@ TEST(RPOLoopOutedges1) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, schedule.BasicBlockCount(), true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); } } } @@ -587,7 +593,7 @@ TEST(RPOLoopOutedges2) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, schedule.BasicBlockCount(), true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); } } @@ -615,10 +621,10 @@ TEST(RPOLoopOutloops1) { BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); CheckRPONumbers(order, schedule.BasicBlockCount(), true); - CheckLoopContains(loop1->nodes, loop1->count); + loop1->Check(order); for (int j = 0; j < size; j++) { - CheckLoopContains(loopN[j]->nodes, loopN[j]->count); + loopN[j]->Check(order); delete loopN[j]; } delete[] loopN; @@ -649,7 +655,7 @@ TEST(RPOLoopMultibackedge) { CheckRPONumbers(order, 5, true); BasicBlock* loop1[] = {B, C, D, E}; - CheckLoopContains(loop1, 4); + CheckLoop(order, loop1, 4); } -- 2.7.4