[turbofan] Propagate "deferredness" to dominated basic blocks.

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 404 matching lines @@
     buffer[0] = schedule_->block(successors[0]);
     buffer[1] = schedule_->block(successors[1]);
   }
 
   void ConnectBranch(Node* branch) {
     BasicBlock* successor_blocks[2];
     CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue,
                            IrOpcode::kIfFalse);
 
     // Consider branch hints.
-    // TODO(turbofan): Propagate the deferred flag to all blocks dominated by
-    // this IfTrue/IfFalse later.
     switch (BranchHintOf(branch->op())) {
       case BranchHint::kNone:
         break;
       case BranchHint::kTrue:
         successor_blocks[1]->set_deferred(true);
         break;
       case BranchHint::kFalse:
         successor_blocks[0]->set_deferred(true);
         break;
     }
@@ skipping 90 matching lines @@
 // => If block A is a loop header, A appears before all blocks in the loop
 //    headed at A.
 // 2. All loops are contiguous in the order (i.e. no intervening blocks that
 //    do not belong to the loop.)
 // Note a simple RPO traversal satisfies (1) but not (2).
 class SpecialRPONumberer {
  public:
   SpecialRPONumberer(Zone* zone, Schedule* schedule)
       : zone_(zone), schedule_(schedule) {}
 
+  void ComputeAssemblyOrder() {

[Michael Starzinger, 2014/11/05 10:06:09]

There is a call to this method missing for the normal scheduler pipeline, the
two calls below only cover the side-channel for the raw machine assembler and
the floating control fusion.

+    // Compute the assembly order (non-deferred code first, deferred code
+    // afterwards).
+    int32_t number = 0;
+    for (auto const block : *schedule_->rpo_order()) {
+      if (!block->deferred()) block->set_ao_number(number++);
+    }
+    for (auto const block : *schedule_->rpo_order()) {
+      if (block->deferred()) block->set_ao_number(number++);
+    }
+  }
+
   void ComputeSpecialRPO() {
     // RPO should not have been computed for this schedule yet.
     CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
     CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));
 
     // Perform an iterative RPO traversal using an explicit stack,
     // recording backedges that form cycles. O(|B|).
     ZoneList<std::pair<BasicBlock*, size_t> > backedges(1, zone_);
     SpecialRPOStackFrame* stack = zone_->NewArray<SpecialRPOStackFrame>(
         static_cast<int>(schedule_->BasicBlockCount()));
@@ skipping 169 matching lines @@
 
       if (current->loop_header() == NULL) {
         Trace("B%d is not in a loop (depth == %d)\n", current->id().ToInt(),
               current->loop_depth());
       } else {
         Trace("B%d has loop header B%d, (depth == %d)\n", current->id().ToInt(),
               current->loop_header()->id().ToInt(), current->loop_depth());
       }
     }
 
-    // Compute the assembly order (non-deferred code first, deferred code
-    // afterwards).
-    int32_t number = 0;
-    for (auto block : *final_order) {
-      if (block->deferred()) continue;
-      block->set_ao_number(number++);
-    }
-    for (auto block : *final_order) {
-      if (!block->deferred()) continue;
-      block->set_ao_number(number++);
-    }
-
 #if DEBUG
     if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
     VerifySpecialRPO(num_loops, loops, final_order);
 #endif
   }
 
  private:
   // Numbering for BasicBlockData.rpo_number_ for this block traversal:
   static const int kBlockOnStack = -2;
   static const int kBlockVisited1 = -3;
@@ skipping 13 matching lines @@
     BlockList* Add(Zone* zone, BasicBlock* b) {
       BlockList* list = static_cast<BlockList*>(zone->New(sizeof(BlockList)));
       list->block = b;
       list->next = this;
       return list;
     }
 
     void Serialize(BasicBlockVector* final_order) {
       for (BlockList* l = this; l != NULL; l = l->next) {
         l->block->set_rpo_number(static_cast<int>(final_order->size()));
+        l->block->set_ao_number(static_cast<int>(final_order->size()));

[Michael Starzinger, 2014/11/05 10:06:09]

This gives you the RPO numbers, not the AO numbers.

         final_order->push_back(l->block);
       }
     }
   };
 
   struct LoopInfo {
     BasicBlock* header;
     ZoneList<BasicBlock*>* outgoing;
     BitVector* members;
     LoopInfo* prev;
@@ skipping 170 matching lines @@
 };
 
 
 BasicBlockVector* Scheduler::ComputeSpecialRPO(ZonePool* zone_pool,
                                                Schedule* schedule) {
   ZonePool::Scope zone_scope(zone_pool);
   Zone* zone = zone_scope.zone();
 
   SpecialRPONumberer numberer(zone, schedule);
   numberer.ComputeSpecialRPO();
+  numberer.ComputeAssemblyOrder();
   return schedule->rpo_order();
 }
 
 
 void Scheduler::ComputeSpecialRPONumbering() {
   Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n");
 
   SpecialRPONumberer numberer(zone_, schedule_);
   numberer.ComputeSpecialRPO();
 }
@@ skipping 20 matching lines @@
         // Don't examine backwards edges
         BasicBlock* pred = *current_pred;
         if (GetRPONumber(pred) < current_rpo_pos) {
           dominator = GetCommonDominator(dominator, *current_pred);
         }
         ++current_pred;
       }
       current_rpo->set_dominator(dominator);
       Trace("Block %d's idom is %d\n", current_rpo->id().ToInt(),
             dominator->id().ToInt());
+      // Propagate "deferredness" of the dominator.
+      if (dominator->deferred()) current_rpo->set_deferred(true);
     }
   }
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 3: Prepare use counts for nodes.
 
 
 class PrepareUsesVisitor : public NullNodeVisitor {
@@ skipping 326 matching lines @@
 
   // Iterate on phase 1: Build control-flow graph.
   CFGBuilder cfg_builder(zone_, this);
   cfg_builder.Run(block, node);
 
   // Iterate on phase 2: Compute special RPO and dominator tree.
   // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
   BasicBlockVector* rpo = schedule_->rpo_order();
   for (BasicBlockVectorIter i = rpo->begin(); i != rpo->end(); ++i) {
     BasicBlock* block = *i;
+    block->set_ao_number(-1);
     block->set_rpo_number(-1);
     block->set_loop_header(NULL);
     block->set_loop_depth(0);
     block->set_loop_end(-1);
   }
   schedule_->rpo_order()->clear();
   SpecialRPONumberer numberer(zone_, schedule_);
   numberer.ComputeSpecialRPO();
   GenerateImmediateDominatorTree();
+  numberer.ComputeAssemblyOrder();
   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 
   // Move previously planned nodes.
   // TODO(mstarzinger): Improve that by supporting bulk moves.
   MovePlannedNodes(block, schedule_->block(node));
 
   if (FLAG_trace_turbo_scheduler) {
     OFStream os(stdout);
     os << "Schedule after control flow fusion:" << *schedule_;
   }
 }
 
 
 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
   Trace("Move planned nodes from B%d to B%d\n", from->id().ToInt(),
         to->id().ToInt());
   NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]);
   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