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

src/compiler/schedule.cc

 // Copyright 2013 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/compiler/schedule.h"
 
 #include "src/compiler/node.h"
 #include "src/compiler/node-properties.h"
 #include "src/ostreams.h"
 
@@ skipping 280 matching lines @@
   MoveSuccessors(block, end);
   for (size_t index = 0; index < succ_count; ++index) {
     AddSuccessor(block, succ_blocks[index]);
   }
   if (block->control_input() != nullptr) {
     SetControlInput(end, block->control_input());
   }
   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);
   succ->AddPredecessor(block);
 }
 
 
 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
   for (BasicBlock* const successor : from->successors()) {
     to->AddSuccessor(successor);
@@ skipping 13 matching lines @@
 
 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
   if (node->id() >= nodeid_to_block_.size()) {
     nodeid_to_block_.resize(node->id() + 1);
   }
   nodeid_to_block_[node->id()] = block;
 }
 
 
 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) {
       os << "  " << *node;
       if (NodeProperties::IsTyped(node)) {
         Type* type = NodeProperties::GetType(node);
         os << " : ";
         type->PrintTo(os);
       }
       os << "\n";
     }
     BasicBlock::Control control = block->control();
     if (control != BasicBlock::kNone) {
       os << "  ";
       if (block->control_input() != nullptr) {
         os << *block->control_input();
       } else {
         os << "Goto";
       }
       os << " -> ";
       comma = false;
       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";
     }
   }
   return os;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8