Fix bugs in Scheduler hoisting and RPO loop bounds computations.

test/cctest/compiler/test-scheduler.cc

 // 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 "test/cctest/cctest.h"
 
 #include "src/compiler/access-builder.h"
 #include "src/compiler/common-operator.h"
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/generic-node.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/graph-visualizer.h"
 #include "src/compiler/js-operator.h"
 #include "src/compiler/machine-operator.h"
 #include "src/compiler/node.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"
 
 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<int>(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<int>(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); }
 };
 
 
 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->AddSuccessor(loop->nodes[i - 1], loop->nodes[i]);
   }
   schedule->AddSuccessor(loop->nodes[count - 1], loop->nodes[0]);
   return loop;
 }
 
 
-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_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();
        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();
@@ skipping 76 matching lines @@
 
 
 TEST(RPOSelfLoop) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
   schedule.AddSuccessor(schedule.start(), schedule.start());
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
   CheckRPONumbers(order, 1, true);
   BasicBlock* loop[] = {schedule.start()};
-  CheckLoopContains(loop, 1);
+  CheckLoop(order, loop, 1);
 }
 
 
 TEST(RPOEntryLoop) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
   schedule.AddSuccessor(schedule.start(), schedule.end());
   schedule.AddSuccessor(schedule.end(), schedule.start());
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
   CheckRPONumbers(order, 2, true);
   BasicBlock* loop[] = {schedule.start(), schedule.end()};
-  CheckLoopContains(loop, 2);
+  CheckLoop(order, loop, 2);
 }
 
 
 TEST(RPOEndLoop) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
   schedule.AddSuccessor(schedule.start(), loop1->header());
   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);
 }
 
 
 TEST(RPOEndLoopNested) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
   SmartPointer<TestLoop> loop1(CreateLoop(&schedule, 2));
   schedule.AddSuccessor(schedule.start(), loop1->header());
   schedule.AddSuccessor(loop1->last(), schedule.start());
   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);
 }
 
 
 TEST(RPODiamond) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
 
   BasicBlock* A = schedule.start();
   BasicBlock* B = schedule.NewBasicBlock();
   BasicBlock* C = schedule.NewBasicBlock();
@@ skipping 26 matching lines @@
 
   schedule.AddSuccessor(A, B);
   schedule.AddSuccessor(B, C);
   schedule.AddSuccessor(C, B);
   schedule.AddSuccessor(C, D);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
   CheckRPONumbers(order, 4, true);
   BasicBlock* loop[] = {B, C};
-  CheckLoopContains(loop, 2);
+  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.AddSuccessor(A, B);
   schedule.AddSuccessor(B, C);
   schedule.AddSuccessor(C, B);
   schedule.AddSuccessor(B, D);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
   CheckRPONumbers(order, 4, true);
   BasicBlock* loop[] = {B, C};
-  CheckLoopContains(loop, 2);
+  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();
@@ skipping 23 matching lines @@
     if (i == 7) schedule.AddSuccessor(C, G);
     if (i == 8) schedule.AddSuccessor(D, G);
     if (i == 9) schedule.AddSuccessor(E, G);
     if (i == 10) schedule.AddSuccessor(F, G);
 
     ZonePool zone_pool(scope.main_isolate());
     BasicBlockVector* order =
         Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
     CheckRPONumbers(order, 7, true);
     BasicBlock* loop[] = {B, C, D, E, F};
-    CheckLoopContains(loop, 5);
+    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.AddSuccessor(A, B);
   schedule.AddSuccessor(B, C);
   schedule.AddSuccessor(C, D);
   schedule.AddSuccessor(D, C);
   schedule.AddSuccessor(D, E);
   schedule.AddSuccessor(E, B);
   schedule.AddSuccessor(E, F);
 
   ZonePool zone_pool(scope.main_isolate());
   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);
 }
 
 
 TEST(RPOLoopNest2) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
 
   BasicBlock* A = schedule.start();
   BasicBlock* B = schedule.NewBasicBlock();
   BasicBlock* C = schedule.NewBasicBlock();
@@ skipping 12 matching lines @@
   schedule.AddSuccessor(G, H);
 
   schedule.AddSuccessor(E, D);
   schedule.AddSuccessor(F, C);
   schedule.AddSuccessor(G, B);
 
   ZonePool zone_pool(scope.main_isolate());
   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);
 }
 
 
 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.AddSuccessor(A, loop1->header());
   schedule.AddSuccessor(loop1->header(), loop2->header());
   schedule.AddSuccessor(loop2->last(), E);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
 
-  CheckLoopContains(loop1->nodes, loop1->count);
-
   CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
            static_cast<int>(order->size()));
-  CheckLoopContains(loop1->nodes, loop1->count);
-  CheckLoopContains(loop2->nodes, loop2->count);
+
+  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.AddSuccessor(A, loop1->header());
   schedule.AddSuccessor(loop1->header(), S);
   schedule.AddSuccessor(S, loop2->header());
   schedule.AddSuccessor(loop2->last(), E);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
 
-  CheckLoopContains(loop1->nodes, loop1->count);
-
   CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
            static_cast<int>(order->size()));
-  CheckLoopContains(loop1->nodes, loop1->count);
-  CheckLoopContains(loop2->nodes, loop2->count);
+  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.AddSuccessor(A, loop1->header());
       schedule.AddSuccessor(loop1->nodes[exit], loop2->header());
       schedule.AddSuccessor(loop2->nodes[exit], E);
       ZonePool zone_pool(scope.main_isolate());
       BasicBlockVector* order =
           Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
-      CheckLoopContains(loop1->nodes, loop1->count);
 
       CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
                static_cast<int>(order->size()));
-      CheckLoopContains(loop1->nodes, loop1->count);
-      CheckLoopContains(loop2->nodes, loop2->count);
+      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.AddSuccessor(A, B);
   schedule.AddSuccessor(B, loop1->header());
   schedule.AddSuccessor(loop1->header(), loop2->header());
   schedule.AddSuccessor(loop2->last(), C);
   schedule.AddSuccessor(C, E);
   schedule.AddSuccessor(C, B);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
 
-  CheckLoopContains(loop1->nodes, loop1->count);
-
   CHECK_EQ(static_cast<int>(schedule.BasicBlockCount()),
            static_cast<int>(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);
 }
 
 
 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.AddSuccessor(A, loop1->header());
       schedule.AddSuccessor(loop1->last(), E);
 
       schedule.AddSuccessor(loop1->nodes[i], loop1->header());
       schedule.AddSuccessor(loop1->nodes[j], E);
 
       ZonePool zone_pool(scope.main_isolate());
       BasicBlockVector* order =
           Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
       CheckRPONumbers(order, schedule.BasicBlockCount(), true);
-      CheckLoopContains(loop1->nodes, loop1->count);
+      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.AddSuccessor(A, loop1->header());
       schedule.AddSuccessor(loop1->last(), E);
 
       schedule.AddSuccessor(loop1->nodes[i], loop1->header());
       schedule.AddSuccessor(loop1->nodes[j], D);
       schedule.AddSuccessor(D, E);
 
       ZonePool zone_pool(scope.main_isolate());
       BasicBlockVector* order =
           Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
       CheckRPONumbers(order, schedule.BasicBlockCount(), true);
-      CheckLoopContains(loop1->nodes, loop1->count);
+      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.AddSuccessor(A, loop1->header());
     schedule.AddSuccessor(loop1->last(), E);
 
     for (int j = 0; j < size; j++) {
       BasicBlock* O = schedule.NewBasicBlock();
       schedule.AddSuccessor(loop1->nodes[j], O);
       schedule.AddSuccessor(O, E);
     }
 
     ZonePool zone_pool(scope.main_isolate());
     BasicBlockVector* order =
         Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
     CheckRPONumbers(order, schedule.BasicBlockCount(), true);
-    CheckLoopContains(loop1->nodes, loop1->count);
+    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.AddSuccessor(A, loop1->header());
     schedule.AddSuccessor(loop1->last(), E);
 
     TestLoop** loopN = new TestLoop* [size];
     for (int j = 0; j < size; j++) {
       loopN[j] = CreateLoop(&schedule, 2);
       schedule.AddSuccessor(loop1->nodes[j], loopN[j]->header());
       schedule.AddSuccessor(loopN[j]->last(), E);
     }
 
     ZonePool zone_pool(scope.main_isolate());
     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;
   }
 }
 
 
 TEST(RPOLoopMultibackedge) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
@@ skipping 10 matching lines @@
   schedule.AddSuccessor(B, E);
   schedule.AddSuccessor(C, B);
   schedule.AddSuccessor(D, B);
   schedule.AddSuccessor(E, B);
 
   ZonePool zone_pool(scope.main_isolate());
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&zone_pool, &schedule);
   CheckRPONumbers(order, 5, true);
 
   BasicBlock* loop1[] = {B, C, D, E};
-  CheckLoopContains(loop1, 4);
+  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()));
 
@@ skipping 1248 matching lines @@
   graph.SetEnd(end);
 
   Schedule* schedule = ComputeAndVerifySchedule(5, &graph);
   BasicBlock* block = schedule->block(loop);
   CHECK_NE(NULL, loop);
   CHECK_EQ(block, schedule->block(effect));
   CHECK_GE(block->rpo_number(), 0);
 }
 
 #endif