Ensure Schedules generated by the RawMachineAssembler are in edge-split form

src/compiler/schedule.cc

Index: src/compiler/schedule.cc
diff --git a/src/compiler/schedule.cc b/src/compiler/schedule.cc
index 455fcd120e1eab065205813328910517361af44e..18ee94b4b86e0d3c0bfd3f988acc6b90f145db34 100644
--- a/src/compiler/schedule.cc
+++ b/src/compiler/schedule.cc
@@ -298,6 +298,68 @@ void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
   SetControlInput(block, sw);
 }
 
+void Schedule::EnsureSplitEdgeForm() {
+  // Make a copy of all the blocks for the iteration, since adding the split
+  // edges will allocate new blocks.
+  BasicBlockVector all_blocks_copy(all_blocks_);
+
+  // Insert missing split edge blocks.
+  for (auto block : all_blocks_copy) {
+    if (block->PredecessorCount() > 1 && block != end_) {
+      for (auto current_pred = block->predecessors().begin();
+           current_pred != block->predecessors().end(); ++current_pred) {
+        BasicBlock* pred = *current_pred;
+        if (pred->SuccessorCount() > 1) {
+          // Found a predecessor block with multiple successors.
+          BasicBlock* split_edge_block = NewBasicBlock();
+          split_edge_block->set_control(BasicBlock::kGoto);
+          split_edge_block->successors().push_back(block);
+          split_edge_block->predecessors().push_back(pred);
+          split_edge_block->set_deferred(pred->deferred());
+          *current_pred = split_edge_block;
+          // Find a corresponding successor in the previous block, replace it
+          // with the split edge block... but only do it once, since we only
+          // replace the previous blocks in the current block one at a time.
+          bool found = false;
+          replace_if(pred->successors().begin(), pred->successors().end(),

[titzer, 2016/03/21 08:06:03]

A regular for loop would be more readable here.

[danno, 2016/03/22 07:53:44]

Done.

+                     [block, found](BasicBlock* e) mutable -> bool {
+                       if (!found && block == e) {
+                         found = true;
+                         return true;
+                       } else {
+                         return false;
+                       }
+                     },
+                     split_edge_block);
+        }
+      }
+    }
+  }
+}
+
+void Schedule::PropagateDeferredMark() {
+  // Push forward the deferred block marks through newly inserted blocks
+  // and other improperly maked blocks until a fixed point is reached.

[titzer, 2016/03/21 08:06:03]

s/maked/marked

[danno, 2016/03/22 07:53:44]

Done.

+  // TODO(danno): optimize the propagaion

[titzer, 2016/03/21 08:06:03]

s/propagaion/propagation

[danno, 2016/03/22 07:53:44]

Done.

+  bool done = false;
+  while (!done) {
+    done = true;
+    for (auto block : all_blocks_) {
+      if (!block->deferred()) {
+        bool deferred = block->PredecessorCount() > 0;
+        for (auto pred : block->predecessors()) {
+          if (!pred->deferred()) {
+            deferred = false;
+          }
+        }
+        if (deferred) {
+          block->set_deferred(true);
+          done = false;
+        }
+      }
+    }
+  }
+}
 
 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
   block->AddSuccessor(succ);
@@ -331,15 +393,24 @@ void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
 
 
 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
-  for (BasicBlock* block : *s.rpo_order()) {
-    os << "--- BLOCK B" << block->rpo_number();
+  for (BasicBlock* block :
+       ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
+    if (block->rpo_number() == -1) {
+      os << "--- BLOCK B" << block->id().ToInt() << " (block id)";
+    } else {
+      os << "--- BLOCK B" << block->rpo_number();
+    }
     if (block->deferred()) os << " (deferred)";
     if (block->PredecessorCount() != 0) os << " <- ";
     bool comma = false;
     for (BasicBlock const* predecessor : block->predecessors()) {
       if (comma) os << ", ";
       comma = true;
-      os << "B" << predecessor->rpo_number();
+      if (predecessor->rpo_number() == -1) {
+        os << "B" << predecessor->id().ToInt();
+      } else {
+        os << "B" << predecessor->rpo_number();
+      }
     }
     os << " ---\n";
     for (Node* node : *block) {
@@ -364,7 +435,11 @@ std::ostream& operator<<(std::ostream& os, const Schedule& s) {
       for (BasicBlock const* successor : block->successors()) {
         if (comma) os << ", ";
         comma = true;
-        os << "B" << successor->rpo_number();
+        if (successor->rpo_number() == -1) {
+          os << "B" << successor->id().ToInt();
+        } else {
+          os << "B" << successor->rpo_number();
+        }
       }
       os << "\n";
     }