Start immediate dominator propagation at entry to floating control.

src/compiler/scheduler.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 <deque>
 #include <queue>
 
 #include "src/compiler/scheduler.h"
 
 #include "src/bit-vector.h"
@@ skipping 1019 matching lines @@
 
 void Scheduler::ComputeSpecialRPONumbering() {
   Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n");
 
   // Compute the special reverse-post-order for basic blocks.
   special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_);
   special_rpo_->ComputeSpecialRPO();
 }
 
 
-void Scheduler::GenerateImmediateDominatorTree() {
-  Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
-
-  // TODO(danno): Consider using Lengauer & Tarjan's if this becomes too slow.
-
-  // Build the block dominator tree.
-  schedule_->start()->set_dominator_depth(0);
-  BasicBlock* second = schedule_->start()->rpo_next();
-  for (BasicBlock* block = second; block != NULL; block = block->rpo_next()) {
+// TODO(danno): Consider using Lengauer & Tarjan's if this becomes too slow.

[titzer, 2014/11/27 10:59:59]

I think we can remove this TODO

[Michael Starzinger, 2014/11/27 11:29:31]

Done.

+void Scheduler::PropagateImmediateDominators(BasicBlock* block) {
+  for (/*nop*/; block != NULL; block = block->rpo_next()) {
     BasicBlock::Predecessors::iterator pred = block->predecessors_begin();
     BasicBlock::Predecessors::iterator end = block->predecessors_end();
     DCHECK(pred != end);  // All blocks except start have predecessors.
     BasicBlock* dominator = *pred;
     // For multiple predecessors, walk up the dominator tree until a common
     // dominator is found. Visitation order guarantees that all predecessors
     // except for backwards edges have been visited.
     for (++pred; pred != end; ++pred) {
       // Don't examine backwards edges.
       if ((*pred)->dominator_depth() < 0) continue;
       dominator = GetCommonDominator(dominator, *pred);
     }
     block->set_dominator(dominator);
     block->set_dominator_depth(dominator->dominator_depth() + 1);
     // Propagate "deferredness" of the dominator.
     if (dominator->deferred()) block->set_deferred(true);
     Trace("Block B%d's idom is B%d, depth = %d\n", block->id().ToInt(),
           dominator->id().ToInt(), block->dominator_depth());
   }
 }
 
 
+void Scheduler::GenerateImmediateDominatorTree() {
+  Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
+
+  // Seed start block to be the first dominator.
+  schedule_->start()->set_dominator_depth(0);
+
+  // Build the block dominator tree resulting from the above seed.
+  PropagateImmediateDominators(schedule_->start()->rpo_next());
+}
+
+
 // -----------------------------------------------------------------------------
 // Phase 3: Prepare use counts for nodes.
 
 
 class PrepareUsesVisitor : public NullNodeVisitor {
  public:
   explicit PrepareUsesVisitor(Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
 
   void Pre(Node* node) {
@@ skipping 346 matching lines @@
     OFStream os(stdout);
     os << "Schedule before control flow fusion:\n" << *schedule_;
   }
 
   // Iterate on phase 1: Build control-flow graph.
   control_flow_builder_->Run(block, node);
 
   // Iterate on phase 2: Compute special RPO and dominator tree.
   special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
   // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
-  for (BasicBlock* block : schedule_->all_blocks_) {
-    block->set_dominator_depth(-1);
-    block->set_dominator(NULL);
+  for (BasicBlock* b = block->rpo_next(); b != NULL; b = b->rpo_next()) {
+    b->set_dominator_depth(-1);
+    b->set_dominator(NULL);
   }
-  GenerateImmediateDominatorTree();
+  PropagateImmediateDominators(block->rpo_next());
 
   // Iterate on phase 4: Schedule nodes early.
   // TODO(mstarzinger): The following loop gathering the propagation roots is a
   // temporary solution and should be merged into the rest of the scheduler as
   // soon as the approach settled for all floating loops.
   NodeVector propagation_roots(control_flow_builder_->control_);
   for (Node* node : control_flow_builder_->control_) {
     for (Node* use : node->uses()) {
       if (use->opcode() == IrOpcode::kPhi ||
           use->opcode() == IrOpcode::kEffectPhi) {
@@ skipping 30 matching lines @@
   for (NodeVectorIter i = nodes->begin(); i != nodes->end(); ++i) {
     schedule_->SetBlockForNode(to, *i);
     scheduled_nodes_[to->id().ToSize()].push_back(*i);
   }
   nodes->clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8