Schedule floating control.

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/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/verifier.h"
 
 using namespace v8::internal;
 using namespace v8::internal::compiler;
 
+// TODO(titzer): pull RPO tests out to their own file.
 struct TestLoop {
   int count;
   BasicBlock** nodes;
   BasicBlock* header() { return nodes[0]; }
   BasicBlock* last() { return nodes[count - 1]; }
   ~TestLoop() { delete[] nodes; }
 };
 
 
 static TestLoop* CreateLoop(Schedule* schedule, int count) {
@@ skipping 25 matching lines @@
   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_;
+    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);
+
+  if (FLAG_trace_turbo_scheduler) {
+    OFStream os(stdout);
+    os << *schedule << endl;
+  }
+  ScheduleVerifier::Run(schedule);
+  CHECK_EQ(expected, GetScheduledNodeCount(schedule));
+  return schedule;
+}
+
+
 TEST(RPODegenerate1) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
 
   BasicBlockVector* order = Scheduler::ComputeSpecialRPO(&schedule);
   CheckRPONumbers(order, 1, false);
   CHECK_EQ(schedule.start(), order->at(0));
 }
 
 
@@ skipping 520 matching lines @@
 
   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(&graph));
 }
 
 
-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 void PrintGraph(Graph* graph) {
-  OFStream os(stdout);
-  os << AsDOT(*graph);
-}
-
-
-static void PrintSchedule(Schedule* schedule) {
-  OFStream os(stdout);
-  os << *schedule << endl;
-}
-
-
 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));
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-
-  CHECK_EQ(13, GetScheduledNodeCount(schedule));
+  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());
   Operator* op;
@@ skipping 125 matching lines @@
   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);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-  CHECK_EQ(20, GetScheduledNodeCount(schedule));
+  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());
   Operator* op;
@@ skipping 92 matching lines @@
   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);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-  CHECK_EQ(19, GetScheduledNodeCount(schedule));
+  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());
   Operator* op;
@@ skipping 227 matching lines @@
   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);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-  CHECK_EQ(46, GetScheduledNodeCount(schedule));
+  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());
   Operator* op;
@@ skipping 309 matching lines @@
   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);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-  CHECK_EQ(62, GetScheduledNodeCount(schedule));
+  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());
   MachineOperatorBuilder machine_builder(scope.main_zone());
@@ skipping 104 matching lines @@
   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);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
-
-  CHECK_EQ(19, GetScheduledNodeCount(schedule));
-
+  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
 
 // So we can get a real JS function.
 static Handle<JSFunction> Compile(const char* source) {
@@ skipping 92 matching lines @@
                                             lazy_deopt_node);  // control
 
   Node* merge_node =
       graph.NewNode(common.Merge(2), return_node, deoptimization_node);
 
   Node* end_node = graph.NewNode(common.End(), merge_node);
 
   graph.SetStart(start_node);
   graph.SetEnd(end_node);
 
-  PrintGraph(&graph);
-
-  Schedule* schedule = Scheduler::ComputeSchedule(&graph);
-
-  PrintSchedule(schedule);
+  Schedule* schedule = ComputeAndVerifySchedule(12, &graph);
 
   // Tests:
   // Continuation and deopt have basic blocks.
   BasicBlock* cont_block = schedule->block(cont_node);
   BasicBlock* deopt_block = schedule->block(lazy_deopt_node);
   BasicBlock* call_block = schedule->block(call_node);
   CHECK_NE(NULL, cont_block);
   CHECK_NE(NULL, deopt_block);
   CHECK_NE(NULL, call_block);
   // The basic blocks are different.
@@ skipping 10 matching lines @@
   // The lazy deopt block contains framestate + bailout (and nothing else).
   CHECK_EQ(deoptimization_node, deopt_block->control_input_);
   CHECK_EQ(5, static_cast<int>(deopt_block->nodes_.size()));
   CHECK_EQ(lazy_deopt_node, deopt_block->nodes_[0]);
   CHECK_EQ(IrOpcode::kStateValues, deopt_block->nodes_[1]->op()->opcode());
   CHECK_EQ(IrOpcode::kStateValues, deopt_block->nodes_[2]->op()->opcode());
   CHECK_EQ(IrOpcode::kStateValues, deopt_block->nodes_[3]->op()->opcode());
   CHECK_EQ(state_node, deopt_block->nodes_[4]);
 }
 
+
+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(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());
+  MachineOperatorBuilder machine(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(machine.Int32Add(), 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());
+  MachineOperatorBuilder machine(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(machine.Int32Add(), 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);
+}
+
 #endif