[v8-dev] [v8] r24876 committed - Add Schedule::InsertBranch to fuse control flow graphs....

codesite-noreply via v8-dev Fri, 24 Oct 2014 06:49:06 -0700

Revision: 24876
Author:   [email protected]
Date:     Fri Oct 24 13:48:02 2014 UTC
Log:      Add Schedule::InsertBranch to fuse control flow graphs.


[email protected]
TEST=cctest/test-schedule/TestScheduleInsertBranch

Review URL: https://codereview.chromium.org/675983002
https://code.google.com/p/v8/source/detail?r=24876

Modified:
 /branches/bleeding_edge/src/compiler/schedule.cc
 /branches/bleeding_edge/src/compiler/schedule.h
 /branches/bleeding_edge/test/cctest/compiler/test-schedule.cc
 /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc

=======================================

--- /branches/bleeding_edge/src/compiler/schedule.cc Wed Oct 22 11:24:552014 UTC+++ /branches/bleeding_edge/src/compiler/schedule.cc Fri Oct 24 13:48:022014 UTC

@@ -51,7 +51,6 @@


 void BasicBlock::set_control(Control control) {
-  DCHECK(control_ == BasicBlock::kNone);
   control_ = control;
 }

@@ -213,12 +212,42 @@
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
 }
+
+

+void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node*branch,

+                            BasicBlock* tblock, BasicBlock* fblock) {
+  DCHECK(block->control() != BasicBlock::kNone);
+  DCHECK(end->control() == BasicBlock::kNone);
+  end->set_control(block->control());
+  block->set_control(BasicBlock::kBranch);
+  MoveSuccessors(block, end);
+  AddSuccessor(block, tblock);
+  AddSuccessor(block, fblock);
+  if (block->control_input() != NULL) {
+    SetControlInput(end, block->control_input());
+  }
+  SetControlInput(block, branch);
+}


 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
   block->AddSuccessor(succ);
   succ->AddPredecessor(block);
 }
+
+
+void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
+  for (BasicBlock::Predecessors::iterator i = from->successors_begin();
+       i != from->successors_end(); ++i) {
+    BasicBlock* succ = *i;
+    to->AddSuccessor(succ);
+    for (BasicBlock::Predecessors::iterator j = succ->predecessors_begin();
+         j != succ->predecessors_end(); ++j) {
+      if (*j == from) *j = to;
+    }
+  }
+  from->ClearSuccessors();
+}


 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
=======================================

--- /branches/bleeding_edge/src/compiler/schedule.h Wed Oct 22 11:24:552014 UTC+++ /branches/bleeding_edge/src/compiler/schedule.h Fri Oct 24 13:48:022014 UTC

@@ -95,6 +95,7 @@
   }
   size_t PredecessorCount() const { return predecessors_.size(); }
   BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
+  void ClearPredecessors() { predecessors_.clear(); }
   void AddPredecessor(BasicBlock* predecessor);

   typedef ZoneVector<BasicBlock*> Successors;
@@ -108,6 +109,7 @@
   }
   size_t SuccessorCount() const { return successors_.size(); }
   BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
+  void ClearSuccessors() { successors_.clear(); }
   void AddSuccessor(BasicBlock* successor);

   // Nodes in the basic block.
@@ -240,7 +242,14 @@
   // BasicBlock building: add a throw at the end of {block}.
   void AddThrow(BasicBlock* block, Node* input);

-  void AddSuccessor(BasicBlock* block, BasicBlock* succ);
+  // BasicBlock mutation: insert a branch into the end of {block}.
+  void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
+                    BasicBlock* tblock, BasicBlock* fblock);
+
+  // Exposed publicly for testing only.
+  void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) {
+    return AddSuccessor(block, succ);
+  }

   BasicBlockVector* rpo_order() { return &rpo_order_; }
   const BasicBlockVector* rpo_order() const { return &rpo_order_; }
@@ -256,6 +265,9 @@
   friend class ScheduleVisualizer;
   friend class BasicBlockInstrumentor;

+  void AddSuccessor(BasicBlock* block, BasicBlock* succ);
+  void MoveSuccessors(BasicBlock* from, BasicBlock* to);
+
   void SetControlInput(BasicBlock* block, Node* node);
   void SetBlockForNode(BasicBlock* block, Node* node);

=======================================

--- /branches/bleeding_edge/test/cctest/compiler/test-schedule.cc Tue Sep30 08:23:20 2014 UTC+++ /branches/bleeding_edge/test/cctest/compiler/test-schedule.cc Fri Oct24 13:48:02 2014 UTC

@@ -30,12 +30,11 @@

 TEST(TestScheduleAddNode) {
   HandleAndZoneScope scope;
+  Schedule schedule(scope.main_zone());
   Graph graph(scope.main_zone());
   Node* n0 = graph.NewNode(&dummy_operator);
   Node* n1 = graph.NewNode(&dummy_operator);

-  Schedule schedule(scope.main_zone());
-
   BasicBlock* entry = schedule.start();
   schedule.AddNode(entry, n0);
   schedule.AddNode(entry, n1);
@@ -51,8 +50,8 @@

 TEST(TestScheduleAddGoto) {
   HandleAndZoneScope scope;
+  Schedule schedule(scope.main_zone());

-  Schedule schedule(scope.main_zone());
   BasicBlock* entry = schedule.start();
   BasicBlock* next = schedule.NewBasicBlock();

@@ -71,16 +70,15 @@
 TEST(TestScheduleAddBranch) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
+  Graph graph(scope.main_zone());
+  CommonOperatorBuilder common(scope.main_zone());
+  Node* n0 = graph.NewNode(&dummy_operator);
+  Node* b = graph.NewNode(common.Branch(), n0);

   BasicBlock* entry = schedule.start();
   BasicBlock* tblock = schedule.NewBasicBlock();
   BasicBlock* fblock = schedule.NewBasicBlock();

-  Graph graph(scope.main_zone());
-  CommonOperatorBuilder common(scope.main_zone());
-  Node* n0 = graph.NewNode(&dummy_operator);
-  Node* b = graph.NewNode(common.Branch(), n0);
-
   schedule.AddBranch(entry, b, tblock, fblock);

   CHECK_EQ(0, static_cast<int>(entry->PredecessorCount()));
@@ -124,6 +122,40 @@
   CHECK_EQ(1, static_cast<int>(entry->SuccessorCount()));
   CHECK_EQ(schedule.end(), entry->SuccessorAt(0));
 }
+
+
+TEST(TestScheduleInsertBranch) {
+  HandleAndZoneScope scope;
+  Schedule schedule(scope.main_zone());
+  Graph graph(scope.main_zone());
+  CommonOperatorBuilder common(scope.main_zone());
+  Node* n0 = graph.NewNode(&dummy_operator);
+  Node* n1 = graph.NewNode(&dummy_operator);
+  Node* b = graph.NewNode(common.Branch(), n1);
+
+  BasicBlock* entry = schedule.start();
+  BasicBlock* tblock = schedule.NewBasicBlock();
+  BasicBlock* fblock = schedule.NewBasicBlock();
+  BasicBlock* merge = schedule.NewBasicBlock();
+  schedule.AddReturn(entry, n0);
+  schedule.AddGoto(tblock, merge);
+  schedule.AddGoto(fblock, merge);
+
+  schedule.InsertBranch(entry, merge, b, tblock, fblock);
+
+  CHECK_EQ(0, static_cast<int>(entry->PredecessorCount()));
+  CHECK_EQ(2, static_cast<int>(entry->SuccessorCount()));
+  CHECK_EQ(tblock, entry->SuccessorAt(0));
+  CHECK_EQ(fblock, entry->SuccessorAt(1));
+
+  CHECK_EQ(2, static_cast<int>(merge->PredecessorCount()));
+  CHECK_EQ(1, static_cast<int>(merge->SuccessorCount()));
+  CHECK_EQ(schedule.end(), merge->SuccessorAt(0));
+
+  CHECK_EQ(1, static_cast<int>(schedule.end()->PredecessorCount()));
+  CHECK_EQ(0, static_cast<int>(schedule.end()->SuccessorCount()));
+  CHECK_EQ(merge, schedule.end()->PredecessorAt(0));
+}


 TEST(BuildMulNodeGraph) {
=======================================

--- /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Wed Oct22 17:15:38 2014 UTC+++ /branches/bleeding_edge/test/cctest/compiler/test-scheduler.cc Fri Oct24 13:48:02 2014 UTC

@@ -39,9 +39,11 @@
   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]);
+    if (i > 0) {
+      schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]);
+    }
   }
-  schedule->AddSuccessor(loop->nodes[count - 1], loop->nodes[0]);
+  schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]);
   return loop;
 }

@@ -160,7 +162,7 @@
 TEST(RPOSelfLoop) {
   HandleAndZoneScope scope;
   Schedule schedule(scope.main_zone());
-  schedule.AddSuccessor(schedule.start(), schedule.start());
+  schedule.AddSuccessorForTesting(schedule.start(), schedule.start());
   ZonePool zone_pool(scope.main_isolate());