Switch schedule early phase to 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/compiler/graph.h"
@@ skipping 45 matching lines @@
     scheduler.ScheduleLate();
 
     had_floating_control = scheduler.ConnectFloatingControl();
   } while (had_floating_control);
 
   return schedule;
 }
 
 
 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
-  SchedulerData def = {0, -1, false, false, kUnknown};
+  SchedulerData def = {NULL, 0, false, false, kUnknown};
   return def;
 }
 
 
 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
   SchedulerData* data = GetData(node);
   if (data->placement_ == kUnknown) {  // Compute placement, once, on demand.
     switch (node->opcode()) {
       case IrOpcode::kParameter:
         // Parameters are always fixed to the start node.
@@ skipping 231 matching lines @@
             block->id().ToInt());
     } else {
       Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
             block->id().ToInt(), succ->id().ToInt());
     }
   }
 };
 
 
 void Scheduler::BuildCFG() {
-  Trace("---------------- CREATING CFG ------------------\n");
+  Trace("--- CREATING CFG -------------------------------------------\n");
   CFGBuilder cfg_builder(zone_, this);
   cfg_builder.Run();
   // Initialize per-block data.
   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 }
 
 
 void Scheduler::GenerateImmediateDominatorTree() {
   // Build the dominator graph.  TODO(danno): consider using Lengauer & Tarjan's
   // if this becomes really slow.
-  Trace("------------ IMMEDIATE BLOCK DOMINATORS -----------\n");
+  Trace("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
   for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
     BasicBlock* current_rpo = schedule_->rpo_order_[i];
     if (current_rpo != schedule_->start()) {
       BasicBlock::Predecessors::iterator current_pred =
           current_rpo->predecessors_begin();
       BasicBlock::Predecessors::iterator end = current_rpo->predecessors_end();
       DCHECK(current_pred != end);
       BasicBlock* dominator = *current_pred;
       ++current_pred;
       // For multiple predecessors, walk up the rpo ordering until a common
@@ skipping 58 matching lines @@
     }
   }
 
  private:
   Scheduler* scheduler_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::PrepareUses() {
-  Trace("------------------- PREPARE USES ------------------\n");
+  Trace("--- PREPARE USES -------------------------------------------\n");
 
   // Count the uses of every node, it will be used to ensure that all of a
   // node's uses are scheduled before the node itself.
   PrepareUsesVisitor prepare_uses(this);
   graph_->VisitNodeInputsFromEnd(&prepare_uses);
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 3: Schedule nodes early.
 
 
 class ScheduleEarlyNodeVisitor : public NullNodeVisitor {
  public:
   explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler)
       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
 
   GenericGraphVisit::Control Pre(Node* node) {
+    Scheduler::SchedulerData* data = scheduler_->GetData(node);
     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
       // Fixed nodes already know their schedule early position.
-      Scheduler::SchedulerData* data = scheduler_->GetData(node);
-      BasicBlock* block = schedule_->block(node);
-      DCHECK(block != NULL);
-      if (data->minimum_rpo_ < 0) {
-        data->minimum_rpo_ = block->rpo_number();
+      if (data->minimum_block_ == NULL) {
+        data->minimum_block_ = schedule_->block(node);
         Trace("Preschedule #%d:%s minimum_rpo = %d (fixed)\n", node->id(),
-              node->op()->mnemonic(), data->minimum_rpo_);
+              node->op()->mnemonic(), data->minimum_block_->rpo_number());
       }
     } else {
       // For unfixed nodes the minimum RPO is the max of all of the inputs.
-      Scheduler::SchedulerData* data = scheduler_->GetData(node);
-      if (data->minimum_rpo_ < 0) {
-        data->minimum_rpo_ = ComputeMaximumInputRPO(node);
-        if (data->minimum_rpo_ < 0) return GenericGraphVisit::REENTER;
+      if (data->minimum_block_ == NULL) {
+        data->minimum_block_ = ComputeMaximumInputRPO(node);
+        if (data->minimum_block_ == NULL) return GenericGraphVisit::REENTER;
         Trace("Preschedule #%d:%s minimum_rpo = %d\n", node->id(),
-              node->op()->mnemonic(), data->minimum_rpo_);
+              node->op()->mnemonic(), data->minimum_block_->rpo_number());
       }
-      DCHECK_GE(data->minimum_rpo_, 0);
     }
+    DCHECK_NE(data->minimum_block_, NULL);
     return GenericGraphVisit::CONTINUE;
   }
 
   GenericGraphVisit::Control Post(Node* node) {
+    Scheduler::SchedulerData* data = scheduler_->GetData(node);
     if (scheduler_->GetPlacement(node) != Scheduler::kFixed) {
-      Scheduler::SchedulerData* data = scheduler_->GetData(node);
       // For unfixed nodes the minimum RPO is the max of all of the inputs.
-      if (data->minimum_rpo_ < 0) {
-        data->minimum_rpo_ = ComputeMaximumInputRPO(node);
+      if (data->minimum_block_ == NULL) {
+        data->minimum_block_ = ComputeMaximumInputRPO(node);
         Trace("Postschedule #%d:%s minimum_rpo = %d\n", node->id(),
-              node->op()->mnemonic(), data->minimum_rpo_);
+              node->op()->mnemonic(), data->minimum_block_->rpo_number());
       }
-      DCHECK_GE(data->minimum_rpo_, 0);
     }
+    DCHECK_NE(data->minimum_block_, NULL);
     return GenericGraphVisit::CONTINUE;
   }
 
   // Computes the maximum of the minimum RPOs for all inputs. If the maximum
-  // cannot be determined (i.e. minimum RPO for at least one input not known),
-  // then a negative number is returned.
-  int ComputeMaximumInputRPO(Node* node) {
-    int max_rpo = 0;
+  // cannot be determined (i.e. minimum RPO for at least one input is {NULL}),
+  // then {NULL} is returned.
+  BasicBlock* ComputeMaximumInputRPO(Node* node) {
+    BasicBlock* max_block = schedule_->start();
     for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
       DCHECK_NE(node, *i);  // Loops only exist for fixed nodes.
-      int control_rpo = scheduler_->GetData(*i)->minimum_rpo_;
-      if (control_rpo > max_rpo) {
-        max_rpo = control_rpo;
-      } else if (control_rpo < 0) {
-        return control_rpo;
+      BasicBlock* block = scheduler_->GetData(*i)->minimum_block_;
+      if (block == NULL) return NULL;
+      if (block->rpo_number() > max_block->rpo_number()) {
+        max_block = block;
       }
     }
-    return max_rpo;
+    return max_block;
   }
 
  private:
   Scheduler* scheduler_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::ScheduleEarly() {
-  Trace("------------------- SCHEDULE EARLY ----------------\n");
+  Trace("--- SCHEDULE EARLY -----------------------------------------\n");
 
   // Compute the minimum RPO for each node thereby determining the earliest
   // position each node could be placed within a valid schedule.
   ScheduleEarlyNodeVisitor visitor(this);
   graph_->VisitNodeInputsFromEnd(&visitor);
 }
 
 
 // -----------------------------------------------------------------------------
 // Phase 4: Schedule nodes late.
@@ skipping 25 matching lines @@
     for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end();
          ++i) {
       BasicBlock* use_block = GetBlockForUse(i.edge());
       block = block == NULL ? use_block : use_block == NULL
                                               ? block
                                               : scheduler_->GetCommonDominator(
                                                     block, use_block);
     }
     DCHECK(block != NULL);
 
-    int min_rpo = data->minimum_rpo_;
+    int min_rpo = data->minimum_block_->rpo_number();
     Trace(
         "Schedule late conservative for #%d:%s is B%d at loop depth %d, "
         "minimum_rpo = %d\n",
         node->id(), node->op()->mnemonic(), block->id().ToInt(),
         block->loop_depth(), min_rpo);
     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
     // into enclosing loop pre-headers until they would preceed their
     // ScheduleEarly position.
     BasicBlock* hoist_block = block;
     while (hoist_block != NULL && hoist_block->rpo_number() >= min_rpo) {
@@ skipping 66 matching lines @@
       }
     }
   }
 
   Scheduler* scheduler_;
   Schedule* schedule_;
 };
 
 
 void Scheduler::ScheduleLate() {
-  Trace("------------------- SCHEDULE LATE -----------------\n");
+  Trace("--- SCHEDULE LATE ------------------------------------------\n");
   if (FLAG_trace_turbo_scheduler) {
     Trace("roots: ");
     for (NodeVectorIter i = schedule_root_nodes_.begin();
          i != schedule_root_nodes_.end(); ++i) {
       Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic());
     }
     Trace("\n");
   }
 
   // Schedule: Places nodes in dominator block of all their uses.
@@ skipping 325 matching lines @@
 //    (i.e. A -> B is a backedge).
 // => If block A dominates block B, then A appears before B in the order.
 // => 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 (3).
 BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) {
   Zone tmp_zone(schedule->zone()->isolate());
   Zone* zone = &tmp_zone;
-  Trace("------------- COMPUTING SPECIAL RPO ---------------\n");
+  Trace("--- COMPUTING SPECIAL RPO ----------------------------------\n");
   // 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()));
   BasicBlock* entry = schedule->start();
@@ skipping 173 matching lines @@
 #if DEBUG
   if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
   VerifySpecialRPO(num_loops, loops, final_order);
 #endif
   return final_order;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8