deps/v8/src/compiler/scheduler.cc

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/scheduler.h"
   6
   7 #include <iomanip>
   8
   9 #include "src/bit-vector.h"
  10 #include "src/compiler/common-operator.h"
  11 #include "src/compiler/control-equivalence.h"
  12 #include "src/compiler/graph.h"
  13 #include "src/compiler/node.h"
  14 #include "src/compiler/node-marker.h"
  15 #include "src/compiler/node-properties.h"
  16 #include "src/zone-containers.h"
  17
  18 namespace v8 {
  19 namespace internal {
  20 namespace compiler {
  21
  22 #define TRACE(...)                                       \
  23   do {                                                   \
  24     if (FLAG_trace_turbo_scheduler) PrintF(__VA_ARGS__); \
  25   } while (false)
  26
  27 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags)
  28     : zone_(zone),
  29       graph_(graph),
  30       schedule_(schedule),
  31       flags_(flags),
  32       scheduled_nodes_(zone),
  33       schedule_root_nodes_(zone),
  34       schedule_queue_(zone),
  35       node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone) {}
  36
  37
  38 Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags) {
  39   Schedule* schedule = new (graph->zone())
  40       Schedule(graph->zone(), static_cast<size_t>(graph->NodeCount()));
  41   Scheduler scheduler(zone, graph, schedule, flags);
  42
  43   scheduler.BuildCFG();
  44   scheduler.ComputeSpecialRPONumbering();
  45   scheduler.GenerateImmediateDominatorTree();
  46
  47   scheduler.PrepareUses();
  48   scheduler.ScheduleEarly();
  49   scheduler.ScheduleLate();
  50
  51   scheduler.SealFinalSchedule();
  52
  53   return schedule;
  54 }
  55
  56
  57 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
  58   SchedulerData def = {schedule_->start(), 0, kUnknown};
  59   return def;
  60 }
  61
  62
  63 Scheduler::SchedulerData* Scheduler::GetData(Node* node) {
  64   return &node_data_[node->id()];
  65 }
  66
  67
  68 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
  69   SchedulerData* data = GetData(node);
  70   if (data->placement_ == kUnknown) {  // Compute placement, once, on demand.
  71     switch (node->opcode()) {
  72       case IrOpcode::kParameter:
  73       case IrOpcode::kOsrValue:
  74         // Parameters and OSR values are always fixed to the start block.
  75         data->placement_ = kFixed;
  76         break;
  77       case IrOpcode::kPhi:
  78       case IrOpcode::kEffectPhi: {
  79         // Phis and effect phis are fixed if their control inputs are, whereas
  80         // otherwise they are coupled to a floating control node.
  81         Placement p = GetPlacement(NodeProperties::GetControlInput(node));
  82         data->placement_ = (p == kFixed ? kFixed : kCoupled);
  83         break;
  84       }
  85 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
  86       CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
  87 #undef DEFINE_CONTROL_CASE
  88       {
  89         // Control nodes that were not control-reachable from end may float.
  90         data->placement_ = kSchedulable;
  91         break;
  92       }
  93       default:
  94         data->placement_ = kSchedulable;
  95         break;
  96     }
  97   }
  98   return data->placement_;
  99 }
 100
 101
 102 void Scheduler::UpdatePlacement(Node* node, Placement placement) {
 103   SchedulerData* data = GetData(node);
 104   if (data->placement_ != kUnknown) {  // Trap on mutation, not initialization.
 105     switch (node->opcode()) {
 106       case IrOpcode::kParameter:
 107         // Parameters are fixed once and for all.
 108         UNREACHABLE();
 109         break;
 110       case IrOpcode::kPhi:
 111       case IrOpcode::kEffectPhi: {
 112         // Phis and effect phis are coupled to their respective blocks.
 113         DCHECK_EQ(Scheduler::kCoupled, data->placement_);
 114         DCHECK_EQ(Scheduler::kFixed, placement);
 115         Node* control = NodeProperties::GetControlInput(node);
 116         BasicBlock* block = schedule_->block(control);
 117         schedule_->AddNode(block, node);
 118         break;
 119       }
 120 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
 121       CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
 122 #undef DEFINE_CONTROL_CASE
 123       {
 124         // Control nodes force coupled uses to be placed.
 125         for (auto use : node->uses()) {
 126           if (GetPlacement(use) == Scheduler::kCoupled) {
 127             DCHECK_EQ(node, NodeProperties::GetControlInput(use));
 128             UpdatePlacement(use, placement);
 129           }
 130         }
 131         break;
 132       }
 133       default:
 134         DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
 135         DCHECK_EQ(Scheduler::kScheduled, placement);
 136         break;
 137     }
 138     // Reduce the use count of the node's inputs to potentially make them
 139     // schedulable. If all the uses of a node have been scheduled, then the node
 140     // itself can be scheduled.
 141     for (Edge const edge : node->input_edges()) {
 142       DecrementUnscheduledUseCount(edge.to(), edge.index(), edge.from());
 143     }
 144   }
 145   data->placement_ = placement;
 146 }
 147
 148
 149 bool Scheduler::IsCoupledControlEdge(Node* node, int index) {
 150   return GetPlacement(node) == kCoupled &&
 151          NodeProperties::FirstControlIndex(node) == index;
 152 }
 153
 154
 155 void Scheduler::IncrementUnscheduledUseCount(Node* node, int index,
 156                                              Node* from) {
 157   // Make sure that control edges from coupled nodes are not counted.
 158   if (IsCoupledControlEdge(from, index)) return;
 159
 160   // Tracking use counts for fixed nodes is useless.
 161   if (GetPlacement(node) == kFixed) return;
 162
 163   // Use count for coupled nodes is summed up on their control.
 164   if (GetPlacement(node) == kCoupled) {
 165     Node* control = NodeProperties::GetControlInput(node);
 166     return IncrementUnscheduledUseCount(control, index, from);
 167   }
 168
 169   ++(GetData(node)->unscheduled_count_);
 170   if (FLAG_trace_turbo_scheduler) {
 171     TRACE("  Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
 172           node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
 173           GetData(node)->unscheduled_count_);
 174   }
 175 }
 176
 177
 178 void Scheduler::DecrementUnscheduledUseCount(Node* node, int index,
 179                                              Node* from) {
 180   // Make sure that control edges from coupled nodes are not counted.
 181   if (IsCoupledControlEdge(from, index)) return;
 182
 183   // Tracking use counts for fixed nodes is useless.
 184   if (GetPlacement(node) == kFixed) return;
 185
 186   // Use count for coupled nodes is summed up on their control.
 187   if (GetPlacement(node) == kCoupled) {
 188     Node* control = NodeProperties::GetControlInput(node);
 189     return DecrementUnscheduledUseCount(control, index, from);
 190   }
 191
 192   DCHECK(GetData(node)->unscheduled_count_ > 0);
 193   --(GetData(node)->unscheduled_count_);
 194   if (FLAG_trace_turbo_scheduler) {
 195     TRACE("  Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(),
 196           node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
 197           GetData(node)->unscheduled_count_);
 198   }
 199   if (GetData(node)->unscheduled_count_ == 0) {
 200     TRACE("    newly eligible #%d:%s\n", node->id(), node->op()->mnemonic());
 201     schedule_queue_.push(node);
 202   }
 203 }
 204
 205
 206 // -----------------------------------------------------------------------------
 207 // Phase 1: Build control-flow graph.
 208
 209
 210 // Internal class to build a control flow graph (i.e the basic blocks and edges
 211 // between them within a Schedule) from the node graph. Visits control edges of
 212 // the graph backwards from an end node in order to find the connected control
 213 // subgraph, needed for scheduling.
 214 class CFGBuilder : public ZoneObject {
 215  public:
 216   CFGBuilder(Zone* zone, Scheduler* scheduler)
 217       : zone_(zone),
 218         scheduler_(scheduler),
 219         schedule_(scheduler->schedule_),
 220         queued_(scheduler->graph_, 2),
 221         queue_(zone),
 222         control_(zone),
 223         component_entry_(NULL),
 224         component_start_(NULL),
 225         component_end_(NULL) {}
 226
 227   // Run the control flow graph construction algorithm by walking the graph
 228   // backwards from end through control edges, building and connecting the
 229   // basic blocks for control nodes.
 230   void Run() {
 231     ResetDataStructures();
 232     Queue(scheduler_->graph_->end());
 233
 234     while (!queue_.empty()) {  // Breadth-first backwards traversal.
 235       Node* node = queue_.front();
 236       queue_.pop();
 237       int max = NodeProperties::PastControlIndex(node);
 238       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
 239         Queue(node->InputAt(i));
 240       }
 241     }
 242
 243     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
 244       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
 245     }
 246   }
 247
 248   // Run the control flow graph construction for a minimal control-connected
 249   // component ending in {exit} and merge that component into an existing
 250   // control flow graph at the bottom of {block}.
 251   void Run(BasicBlock* block, Node* exit) {
 252     ResetDataStructures();
 253     Queue(exit);
 254
 255     component_entry_ = NULL;
 256     component_start_ = block;
 257     component_end_ = schedule_->block(exit);
 258     scheduler_->equivalence_->Run(exit);
 259     while (!queue_.empty()) {  // Breadth-first backwards traversal.
 260       Node* node = queue_.front();
 261       queue_.pop();
 262
 263       // Use control dependence equivalence to find a canonical single-entry
 264       // single-exit region that makes up a minimal component to be scheduled.
 265       if (IsSingleEntrySingleExitRegion(node, exit)) {
 266         TRACE("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic());
 267         DCHECK(!component_entry_);
 268         component_entry_ = node;
 269         continue;
 270       }
 271
 272       int max = NodeProperties::PastControlIndex(node);
 273       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
 274         Queue(node->InputAt(i));
 275       }
 276     }
 277     DCHECK(component_entry_);
 278
 279     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
 280       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
 281     }
 282   }
 283
 284  private:
 285   friend class ScheduleLateNodeVisitor;
 286   friend class Scheduler;
 287
 288   void FixNode(BasicBlock* block, Node* node) {
 289     schedule_->AddNode(block, node);
 290     scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 291   }
 292
 293   void Queue(Node* node) {
 294     // Mark the connected control nodes as they are queued.
 295     if (!queued_.Get(node)) {
 296       BuildBlocks(node);
 297       queue_.push(node);
 298       queued_.Set(node, true);
 299       control_.push_back(node);
 300     }
 301   }
 302
 303   void BuildBlocks(Node* node) {
 304     switch (node->opcode()) {
 305       case IrOpcode::kEnd:
 306         FixNode(schedule_->end(), node);
 307         break;
 308       case IrOpcode::kStart:
 309         FixNode(schedule_->start(), node);
 310         break;
 311       case IrOpcode::kLoop:
 312       case IrOpcode::kMerge:
 313         BuildBlockForNode(node);
 314         break;
 315       case IrOpcode::kBranch:
 316       case IrOpcode::kSwitch:
 317         BuildBlocksForSuccessors(node);
 318         break;
 319       case IrOpcode::kCall:
 320         if (IsExceptionalCall(node)) {
 321           BuildBlocksForSuccessors(node);
 322         }
 323         break;
 324       default:
 325         break;
 326     }
 327   }
 328
 329   void ConnectBlocks(Node* node) {
 330     switch (node->opcode()) {
 331       case IrOpcode::kLoop:
 332       case IrOpcode::kMerge:
 333         ConnectMerge(node);
 334         break;
 335       case IrOpcode::kBranch:
 336         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 337         ConnectBranch(node);
 338         break;
 339       case IrOpcode::kSwitch:
 340         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 341         ConnectSwitch(node);
 342         break;
 343       case IrOpcode::kDeoptimize:
 344         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 345         ConnectDeoptimize(node);
 346         break;
 347       case IrOpcode::kReturn:
 348         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 349         ConnectReturn(node);
 350         break;
 351       case IrOpcode::kThrow:
 352         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 353         ConnectThrow(node);
 354         break;
 355       case IrOpcode::kCall:
 356         if (IsExceptionalCall(node)) {
 357           scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 358           ConnectCall(node);
 359         }
 360         break;
 361       default:
 362         break;
 363     }
 364   }
 365
 366   BasicBlock* BuildBlockForNode(Node* node) {
 367     BasicBlock* block = schedule_->block(node);
 368     if (block == NULL) {
 369       block = schedule_->NewBasicBlock();
 370       TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
 371             node->op()->mnemonic());
 372       FixNode(block, node);
 373     }
 374     return block;
 375   }
 376
 377   void BuildBlocksForSuccessors(Node* node) {
 378     size_t const successor_cnt = node->op()->ControlOutputCount();
 379     Node** successors = zone_->NewArray<Node*>(successor_cnt);
 380     NodeProperties::CollectControlProjections(node, successors, successor_cnt);
 381     for (size_t index = 0; index < successor_cnt; ++index) {
 382       BuildBlockForNode(successors[index]);
 383     }
 384   }
 385
 386   void CollectSuccessorBlocks(Node* node, BasicBlock** successor_blocks,
 387                               size_t successor_cnt) {
 388     Node** successors = reinterpret_cast<Node**>(successor_blocks);
 389     NodeProperties::CollectControlProjections(node, successors, successor_cnt);
 390     for (size_t index = 0; index < successor_cnt; ++index) {
 391       successor_blocks[index] = schedule_->block(successors[index]);
 392     }
 393   }
 394
 395   BasicBlock* FindPredecessorBlock(Node* node) {
 396     BasicBlock* predecessor_block = nullptr;
 397     while (true) {
 398       predecessor_block = schedule_->block(node);
 399       if (predecessor_block != nullptr) break;
 400       node = NodeProperties::GetControlInput(node);
 401     }
 402     return predecessor_block;
 403   }
 404
 405   void ConnectCall(Node* call) {
 406     BasicBlock* successor_blocks[2];
 407     CollectSuccessorBlocks(call, successor_blocks, arraysize(successor_blocks));
 408
 409     // Consider the exception continuation to be deferred.
 410     successor_blocks[1]->set_deferred(true);
 411
 412     Node* call_control = NodeProperties::GetControlInput(call);
 413     BasicBlock* call_block = FindPredecessorBlock(call_control);
 414     TraceConnect(call, call_block, successor_blocks[0]);
 415     TraceConnect(call, call_block, successor_blocks[1]);
 416     schedule_->AddCall(call_block, call, successor_blocks[0],
 417                        successor_blocks[1]);
 418   }
 419
 420   void ConnectBranch(Node* branch) {
 421     BasicBlock* successor_blocks[2];
 422     CollectSuccessorBlocks(branch, successor_blocks,
 423                            arraysize(successor_blocks));
 424
 425     // Consider branch hints.
 426     switch (BranchHintOf(branch->op())) {
 427       case BranchHint::kNone:
 428         break;
 429       case BranchHint::kTrue:
 430         successor_blocks[1]->set_deferred(true);
 431         break;
 432       case BranchHint::kFalse:
 433         successor_blocks[0]->set_deferred(true);
 434         break;
 435     }
 436
 437     if (branch == component_entry_) {
 438       TraceConnect(branch, component_start_, successor_blocks[0]);
 439       TraceConnect(branch, component_start_, successor_blocks[1]);
 440       schedule_->InsertBranch(component_start_, component_end_, branch,
 441                               successor_blocks[0], successor_blocks[1]);
 442     } else {
 443       Node* branch_control = NodeProperties::GetControlInput(branch);
 444       BasicBlock* branch_block = FindPredecessorBlock(branch_control);
 445       TraceConnect(branch, branch_block, successor_blocks[0]);
 446       TraceConnect(branch, branch_block, successor_blocks[1]);
 447       schedule_->AddBranch(branch_block, branch, successor_blocks[0],
 448                            successor_blocks[1]);
 449     }
 450   }
 451
 452   void ConnectSwitch(Node* sw) {
 453     size_t const successor_count = sw->op()->ControlOutputCount();
 454     BasicBlock** successor_blocks =
 455         zone_->NewArray<BasicBlock*>(successor_count);
 456     CollectSuccessorBlocks(sw, successor_blocks, successor_count);
 457
 458     if (sw == component_entry_) {
 459       for (size_t index = 0; index < successor_count; ++index) {
 460         TraceConnect(sw, component_start_, successor_blocks[index]);
 461       }
 462       schedule_->InsertSwitch(component_start_, component_end_, sw,
 463                               successor_blocks, successor_count);
 464     } else {
 465       Node* switch_control = NodeProperties::GetControlInput(sw);
 466       BasicBlock* switch_block = FindPredecessorBlock(switch_control);
 467       for (size_t index = 0; index < successor_count; ++index) {
 468         TraceConnect(sw, switch_block, successor_blocks[index]);
 469       }
 470       schedule_->AddSwitch(switch_block, sw, successor_blocks, successor_count);
 471     }
 472   }
 473
 474   void ConnectMerge(Node* merge) {
 475     // Don't connect the special merge at the end to its predecessors.
 476     if (IsFinalMerge(merge)) return;
 477
 478     BasicBlock* block = schedule_->block(merge);
 479     DCHECK_NOT_NULL(block);
 480     // For all of the merge's control inputs, add a goto at the end to the
 481     // merge's basic block.
 482     for (Node* const input : merge->inputs()) {
 483       BasicBlock* predecessor_block = FindPredecessorBlock(input);
 484       TraceConnect(merge, predecessor_block, block);
 485       schedule_->AddGoto(predecessor_block, block);
 486     }
 487   }
 488
 489   void ConnectReturn(Node* ret) {
 490     Node* return_control = NodeProperties::GetControlInput(ret);
 491     BasicBlock* return_block = FindPredecessorBlock(return_control);
 492     TraceConnect(ret, return_block, NULL);
 493     schedule_->AddReturn(return_block, ret);
 494   }
 495
 496   void ConnectDeoptimize(Node* deopt) {
 497     Node* deoptimize_control = NodeProperties::GetControlInput(deopt);
 498     BasicBlock* deoptimize_block = FindPredecessorBlock(deoptimize_control);
 499     TraceConnect(deopt, deoptimize_block, NULL);
 500     schedule_->AddDeoptimize(deoptimize_block, deopt);
 501   }
 502
 503   void ConnectThrow(Node* thr) {
 504     Node* throw_control = NodeProperties::GetControlInput(thr);
 505     BasicBlock* throw_block = FindPredecessorBlock(throw_control);
 506     TraceConnect(thr, throw_block, NULL);
 507     schedule_->AddThrow(throw_block, thr);
 508   }
 509
 510   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
 511     DCHECK_NOT_NULL(block);
 512     if (succ == NULL) {
 513       TRACE("Connect #%d:%s, id:%d -> end\n", node->id(),
 514             node->op()->mnemonic(), block->id().ToInt());
 515     } else {
 516       TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(),
 517             node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt());
 518     }
 519   }
 520
 521   bool IsExceptionalCall(Node* node) {
 522     for (Node* const use : node->uses()) {
 523       if (use->opcode() == IrOpcode::kIfException) return true;
 524     }
 525     return false;
 526   }
 527
 528   bool IsFinalMerge(Node* node) {
 529     return (node->opcode() == IrOpcode::kMerge &&
 530             node == scheduler_->graph_->end()->InputAt(0));
 531   }
 532
 533   bool IsSingleEntrySingleExitRegion(Node* entry, Node* exit) const {
 534     size_t entry_class = scheduler_->equivalence_->ClassOf(entry);
 535     size_t exit_class = scheduler_->equivalence_->ClassOf(exit);
 536     return entry != exit && entry_class == exit_class;
 537   }
 538
 539   void ResetDataStructures() {
 540     control_.clear();
 541     DCHECK(queue_.empty());
 542     DCHECK(control_.empty());
 543   }
 544
 545   Zone* zone_;
 546   Scheduler* scheduler_;
 547   Schedule* schedule_;
 548   NodeMarker<bool> queued_;      // Mark indicating whether node is queued.
 549   ZoneQueue<Node*> queue_;       // Queue used for breadth-first traversal.
 550   NodeVector control_;           // List of encountered control nodes.
 551   Node* component_entry_;        // Component single-entry node.
 552   BasicBlock* component_start_;  // Component single-entry block.
 553   BasicBlock* component_end_;    // Component single-exit block.
 554 };
 555
 556
 557 void Scheduler::BuildCFG() {
 558   TRACE("--- CREATING CFG -------------------------------------------\n");
 559
 560   // Instantiate a new control equivalence algorithm for the graph.
 561   equivalence_ = new (zone_) ControlEquivalence(zone_, graph_);
 562
 563   // Build a control-flow graph for the main control-connected component that
 564   // is being spanned by the graph's start and end nodes.
 565   control_flow_builder_ = new (zone_) CFGBuilder(zone_, this);
 566   control_flow_builder_->Run();
 567
 568   // Initialize per-block data.
 569   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 570 }
 571
 572
 573 // -----------------------------------------------------------------------------
 574 // Phase 2: Compute special RPO and dominator tree.
 575
 576
 577 // Compute the special reverse-post-order block ordering, which is essentially
 578 // a RPO of the graph where loop bodies are contiguous. Properties:
 579 // 1. If block A is a predecessor of B, then A appears before B in the order,
 580 //    unless B is a loop header and A is in the loop headed at B
 581 //    (i.e. A -> B is a backedge).
 582 // => If block A dominates block B, then A appears before B in the order.
 583 // => If block A is a loop header, A appears before all blocks in the loop
 584 //    headed at A.
 585 // 2. All loops are contiguous in the order (i.e. no intervening blocks that
 586 //    do not belong to the loop.)
 587 // Note a simple RPO traversal satisfies (1) but not (2).
 588 class SpecialRPONumberer : public ZoneObject {
 589  public:
 590   SpecialRPONumberer(Zone* zone, Schedule* schedule)
 591       : zone_(zone),
 592         schedule_(schedule),
 593         order_(NULL),
 594         beyond_end_(NULL),
 595         loops_(zone),
 596         backedges_(zone),
 597         stack_(zone),
 598         previous_block_count_(0),
 599         empty_(0, zone) {}
 600
 601   // Computes the special reverse-post-order for the main control flow graph,
 602   // that is for the graph spanned between the schedule's start and end blocks.
 603   void ComputeSpecialRPO() {
 604     DCHECK(schedule_->end()->SuccessorCount() == 0);
 605     DCHECK(!order_);  // Main order does not exist yet.
 606     ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end());
 607   }
 608
 609   // Computes the special reverse-post-order for a partial control flow graph,
 610   // that is for the graph spanned between the given {entry} and {end} blocks,
 611   // then updates the existing ordering with this new information.
 612   void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) {
 613     DCHECK(order_);  // Main order to be updated is present.
 614     ComputeAndInsertSpecialRPO(entry, end);
 615   }
 616
 617   // Serialize the previously computed order as a special reverse-post-order
 618   // numbering for basic blocks into the final schedule.
 619   void SerializeRPOIntoSchedule() {
 620     int32_t number = 0;
 621     for (BasicBlock* b = order_; b != NULL; b = b->rpo_next()) {
 622       b->set_rpo_number(number++);
 623       schedule_->rpo_order()->push_back(b);
 624     }
 625     BeyondEndSentinel()->set_rpo_number(number);
 626   }
 627
 628   // Print and verify the special reverse-post-order.
 629   void PrintAndVerifySpecialRPO() {
 630 #if DEBUG
 631     if (FLAG_trace_turbo_scheduler) PrintRPO();
 632     VerifySpecialRPO();
 633 #endif
 634   }
 635
 636   const ZoneList<BasicBlock*>& GetOutgoingBlocks(BasicBlock* block) {
 637     if (HasLoopNumber(block)) {
 638       LoopInfo const& loop = loops_[GetLoopNumber(block)];
 639       if (loop.outgoing) return *loop.outgoing;
 640     }
 641     return empty_;
 642   }
 643
 644  private:
 645   typedef std::pair<BasicBlock*, size_t> Backedge;
 646
 647   // Numbering for BasicBlock::rpo_number for this block traversal:
 648   static const int kBlockOnStack = -2;
 649   static const int kBlockVisited1 = -3;
 650   static const int kBlockVisited2 = -4;
 651   static const int kBlockUnvisited1 = -1;
 652   static const int kBlockUnvisited2 = kBlockVisited1;
 653
 654   struct SpecialRPOStackFrame {
 655     BasicBlock* block;
 656     size_t index;
 657   };
 658
 659   struct LoopInfo {
 660     BasicBlock* header;
 661     ZoneList<BasicBlock*>* outgoing;
 662     BitVector* members;
 663     LoopInfo* prev;
 664     BasicBlock* end;
 665     BasicBlock* start;
 666
 667     void AddOutgoing(Zone* zone, BasicBlock* block) {
 668       if (outgoing == NULL) {
 669         outgoing = new (zone) ZoneList<BasicBlock*>(2, zone);
 670       }
 671       outgoing->Add(block, zone);
 672     }
 673   };
 674
 675   int Push(ZoneVector<SpecialRPOStackFrame>& stack, int depth,
 676            BasicBlock* child, int unvisited) {
 677     if (child->rpo_number() == unvisited) {
 678       stack[depth].block = child;
 679       stack[depth].index = 0;
 680       child->set_rpo_number(kBlockOnStack);
 681       return depth + 1;
 682     }
 683     return depth;
 684   }
 685
 686   BasicBlock* PushFront(BasicBlock* head, BasicBlock* block) {
 687     block->set_rpo_next(head);
 688     return block;
 689   }
 690
 691   static int GetLoopNumber(BasicBlock* block) { return block->loop_number(); }
 692   static void SetLoopNumber(BasicBlock* block, int loop_number) {
 693     return block->set_loop_number(loop_number);
 694   }
 695   static bool HasLoopNumber(BasicBlock* block) {
 696     return block->loop_number() >= 0;
 697   }
 698
 699   // TODO(mstarzinger): We only need this special sentinel because some tests
 700   // use the schedule's end block in actual control flow (e.g. with end having
 701   // successors). Once this has been cleaned up we can use the end block here.
 702   BasicBlock* BeyondEndSentinel() {
 703     if (beyond_end_ == NULL) {
 704       BasicBlock::Id id = BasicBlock::Id::FromInt(-1);
 705       beyond_end_ = new (schedule_->zone()) BasicBlock(schedule_->zone(), id);
 706     }
 707     return beyond_end_;
 708   }
 709
 710   // Compute special RPO for the control flow graph between {entry} and {end},
 711   // mutating any existing order so that the result is still valid.
 712   void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) {
 713     // RPO should not have been serialized for this schedule yet.
 714     CHECK_EQ(kBlockUnvisited1, schedule_->start()->loop_number());
 715     CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
 716     CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));
 717
 718     // Find correct insertion point within existing order.
 719     BasicBlock* insertion_point = entry->rpo_next();
 720     BasicBlock* order = insertion_point;
 721
 722     // Perform an iterative RPO traversal using an explicit stack,
 723     // recording backedges that form cycles. O(|B|).
 724     DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount());
 725     stack_.resize(schedule_->BasicBlockCount() - previous_block_count_);
 726     previous_block_count_ = schedule_->BasicBlockCount();
 727     int stack_depth = Push(stack_, 0, entry, kBlockUnvisited1);
 728     int num_loops = static_cast<int>(loops_.size());
 729
 730     while (stack_depth > 0) {
 731       int current = stack_depth - 1;
 732       SpecialRPOStackFrame* frame = &stack_[current];
 733
 734       if (frame->block != end &&
 735           frame->index < frame->block->SuccessorCount()) {
 736         // Process the next successor.
 737         BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
 738         if (succ->rpo_number() == kBlockVisited1) continue;
 739         if (succ->rpo_number() == kBlockOnStack) {
 740           // The successor is on the stack, so this is a backedge (cycle).
 741           backedges_.push_back(Backedge(frame->block, frame->index - 1));
 742           if (!HasLoopNumber(succ)) {
 743             // Assign a new loop number to the header if it doesn't have one.
 744             SetLoopNumber(succ, num_loops++);
 745           }
 746         } else {
 747           // Push the successor onto the stack.
 748           DCHECK(succ->rpo_number() == kBlockUnvisited1);
 749           stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited1);
 750         }
 751       } else {
 752         // Finished with all successors; pop the stack and add the block.
 753         order = PushFront(order, frame->block);
 754         frame->block->set_rpo_number(kBlockVisited1);
 755         stack_depth--;
 756       }
 757     }
 758
 759     // If no loops were encountered, then the order we computed was correct.
 760     if (num_loops > static_cast<int>(loops_.size())) {
 761       // Otherwise, compute the loop information from the backedges in order
 762       // to perform a traversal that groups loop bodies together.
 763       ComputeLoopInfo(stack_, num_loops, &backedges_);
 764
 765       // Initialize the "loop stack". Note the entry could be a loop header.
 766       LoopInfo* loop =
 767           HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : NULL;
 768       order = insertion_point;
 769
 770       // Perform an iterative post-order traversal, visiting loop bodies before
 771       // edges that lead out of loops. Visits each block once, but linking loop
 772       // sections together is linear in the loop size, so overall is
 773       // O(|B| + max(loop_depth) * max(|loop|))
 774       stack_depth = Push(stack_, 0, entry, kBlockUnvisited2);
 775       while (stack_depth > 0) {
 776         SpecialRPOStackFrame* frame = &stack_[stack_depth - 1];
 777         BasicBlock* block = frame->block;
 778         BasicBlock* succ = NULL;
 779
 780         if (block != end && frame->index < block->SuccessorCount()) {
 781           // Process the next normal successor.
 782           succ = block->SuccessorAt(frame->index++);
 783         } else if (HasLoopNumber(block)) {
 784           // Process additional outgoing edges from the loop header.
 785           if (block->rpo_number() == kBlockOnStack) {
 786             // Finish the loop body the first time the header is left on the
 787             // stack.
 788             DCHECK(loop != NULL && loop->header == block);
 789             loop->start = PushFront(order, block);
 790             order = loop->end;
 791             block->set_rpo_number(kBlockVisited2);
 792             // Pop the loop stack and continue visiting outgoing edges within
 793             // the context of the outer loop, if any.
 794             loop = loop->prev;
 795             // We leave the loop header on the stack; the rest of this iteration
 796             // and later iterations will go through its outgoing edges list.
 797           }
 798
 799           // Use the next outgoing edge if there are any.
 800           int outgoing_index =
 801               static_cast<int>(frame->index - block->SuccessorCount());
 802           LoopInfo* info = &loops_[GetLoopNumber(block)];
 803           DCHECK(loop != info);
 804           if (block != entry && info->outgoing != NULL &&
 805               outgoing_index < info->outgoing->length()) {
 806             succ = info->outgoing->at(outgoing_index);
 807             frame->index++;
 808           }
 809         }
 810
 811         if (succ != NULL) {
 812           // Process the next successor.
 813           if (succ->rpo_number() == kBlockOnStack) continue;
 814           if (succ->rpo_number() == kBlockVisited2) continue;
 815           DCHECK(succ->rpo_number() == kBlockUnvisited2);
 816           if (loop != NULL && !loop->members->Contains(succ->id().ToInt())) {
 817             // The successor is not in the current loop or any nested loop.
 818             // Add it to the outgoing edges of this loop and visit it later.
 819             loop->AddOutgoing(zone_, succ);
 820           } else {
 821             // Push the successor onto the stack.
 822             stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2);
 823             if (HasLoopNumber(succ)) {
 824               // Push the inner loop onto the loop stack.
 825               DCHECK(GetLoopNumber(succ) < num_loops);
 826               LoopInfo* next = &loops_[GetLoopNumber(succ)];
 827               next->end = order;
 828               next->prev = loop;
 829               loop = next;
 830             }
 831           }
 832         } else {
 833           // Finished with all successors of the current block.
 834           if (HasLoopNumber(block)) {
 835             // If we are going to pop a loop header, then add its entire body.
 836             LoopInfo* info = &loops_[GetLoopNumber(block)];
 837             for (BasicBlock* b = info->start; true; b = b->rpo_next()) {
 838               if (b->rpo_next() == info->end) {
 839                 b->set_rpo_next(order);
 840                 info->end = order;
 841                 break;
 842               }
 843             }
 844             order = info->start;
 845           } else {
 846             // Pop a single node off the stack and add it to the order.
 847             order = PushFront(order, block);
 848             block->set_rpo_number(kBlockVisited2);
 849           }
 850           stack_depth--;
 851         }
 852       }
 853     }
 854
 855     // Publish new order the first time.
 856     if (order_ == NULL) order_ = order;
 857
 858     // Compute the correct loop headers and set the correct loop ends.
 859     LoopInfo* current_loop = NULL;
 860     BasicBlock* current_header = entry->loop_header();
 861     int32_t loop_depth = entry->loop_depth();
 862     if (entry->IsLoopHeader()) --loop_depth;  // Entry might be a loop header.
 863     for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) {
 864       BasicBlock* current = b;
 865
 866       // Reset BasicBlock::rpo_number again.
 867       current->set_rpo_number(kBlockUnvisited1);
 868
 869       // Finish the previous loop(s) if we just exited them.
 870       while (current_header != NULL && current == current_header->loop_end()) {
 871         DCHECK(current_header->IsLoopHeader());
 872         DCHECK(current_loop != NULL);
 873         current_loop = current_loop->prev;
 874         current_header = current_loop == NULL ? NULL : current_loop->header;
 875         --loop_depth;
 876       }
 877       current->set_loop_header(current_header);
 878
 879       // Push a new loop onto the stack if this loop is a loop header.
 880       if (HasLoopNumber(current)) {
 881         ++loop_depth;
 882         current_loop = &loops_[GetLoopNumber(current)];
 883         BasicBlock* end = current_loop->end;
 884         current->set_loop_end(end == NULL ? BeyondEndSentinel() : end);
 885         current_header = current_loop->header;
 886         TRACE("id:%d is a loop header, increment loop depth to %d\n",
 887               current->id().ToInt(), loop_depth);
 888       }
 889
 890       current->set_loop_depth(loop_depth);
 891
 892       if (current->loop_header() == NULL) {
 893         TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(),
 894               current->loop_depth());
 895       } else {
 896         TRACE("id:%d has loop header id:%d, (depth == %d)\n",
 897               current->id().ToInt(), current->loop_header()->id().ToInt(),
 898               current->loop_depth());
 899       }
 900     }
 901   }
 902
 903   // Computes loop membership from the backedges of the control flow graph.
 904   void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue,
 905                        size_t num_loops, ZoneVector<Backedge>* backedges) {
 906     // Extend existing loop membership vectors.
 907     for (LoopInfo& loop : loops_) {
 908       BitVector* new_members = new (zone_)
 909           BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_);
 910       new_members->CopyFrom(*loop.members);
 911       loop.members = new_members;
 912     }
 913
 914     // Extend loop information vector.
 915     loops_.resize(num_loops, LoopInfo());
 916
 917     // Compute loop membership starting from backedges.
 918     // O(max(loop_depth) * max(|loop|)
 919     for (size_t i = 0; i < backedges->size(); i++) {
 920       BasicBlock* member = backedges->at(i).first;
 921       BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
 922       size_t loop_num = GetLoopNumber(header);
 923       if (loops_[loop_num].header == NULL) {
 924         loops_[loop_num].header = header;
 925         loops_[loop_num].members = new (zone_)
 926             BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_);
 927       }
 928
 929       int queue_length = 0;
 930       if (member != header) {
 931         // As long as the header doesn't have a backedge to itself,
 932         // Push the member onto the queue and process its predecessors.
 933         if (!loops_[loop_num].members->Contains(member->id().ToInt())) {
 934           loops_[loop_num].members->Add(member->id().ToInt());
 935         }
 936         queue[queue_length++].block = member;
 937       }
 938
 939       // Propagate loop membership backwards. All predecessors of M up to the
 940       // loop header H are members of the loop too. O(|blocks between M and H|).
 941       while (queue_length > 0) {
 942         BasicBlock* block = queue[--queue_length].block;
 943         for (size_t i = 0; i < block->PredecessorCount(); i++) {
 944           BasicBlock* pred = block->PredecessorAt(i);
 945           if (pred != header) {
 946             if (!loops_[loop_num].members->Contains(pred->id().ToInt())) {
 947               loops_[loop_num].members->Add(pred->id().ToInt());
 948               queue[queue_length++].block = pred;
 949             }
 950           }
 951         }
 952       }
 953     }
 954   }
 955
 956 #if DEBUG
 957   void PrintRPO() {
 958     OFStream os(stdout);
 959     os << "RPO with " << loops_.size() << " loops";
 960     if (loops_.size() > 0) {
 961       os << " (";
 962       for (size_t i = 0; i < loops_.size(); i++) {
 963         if (i > 0) os << " ";
 964         os << "id:" << loops_[i].header->id();
 965       }
 966       os << ")";
 967     }
 968     os << ":\n";
 969
 970     for (BasicBlock* block = order_; block != NULL; block = block->rpo_next()) {
 971       os << std::setw(5) << "B" << block->rpo_number() << ":";
 972       for (size_t i = 0; i < loops_.size(); i++) {
 973         bool range = loops_[i].header->LoopContains(block);
 974         bool membership = loops_[i].header != block && range;
 975         os << (membership ? " |" : "  ");
 976         os << (range ? "x" : " ");
 977       }
 978       os << "  id:" << block->id() << ": ";
 979       if (block->loop_end() != NULL) {
 980         os << " range: [B" << block->rpo_number() << ", B"
 981            << block->loop_end()->rpo_number() << ")";
 982       }
 983       if (block->loop_header() != NULL) {
 984         os << " header: id:" << block->loop_header()->id();
 985       }
 986       if (block->loop_depth() > 0) {
 987         os << " depth: " << block->loop_depth();
 988       }
 989       os << "\n";
 990     }
 991   }
 992
 993   void VerifySpecialRPO() {
 994     BasicBlockVector* order = schedule_->rpo_order();
 995     DCHECK(order->size() > 0);
 996     DCHECK((*order)[0]->id().ToInt() == 0);  // entry should be first.
 997
 998     for (size_t i = 0; i < loops_.size(); i++) {
 999       LoopInfo* loop = &loops_[i];
1000       BasicBlock* header = loop->header;
1001       BasicBlock* end = header->loop_end();
1002
1003       DCHECK(header != NULL);
1004       DCHECK(header->rpo_number() >= 0);
1005       DCHECK(header->rpo_number() < static_cast<int>(order->size()));
1006       DCHECK(end != NULL);
1007       DCHECK(end->rpo_number() <= static_cast<int>(order->size()));
1008       DCHECK(end->rpo_number() > header->rpo_number());
1009       DCHECK(header->loop_header() != header);
1010
1011       // Verify the start ... end list relationship.
1012       int links = 0;
1013       BasicBlock* block = loop->start;
1014       DCHECK_EQ(header, block);
1015       bool end_found;
1016       while (true) {
1017         if (block == NULL || block == loop->end) {
1018           end_found = (loop->end == block);
1019           break;
1020         }
1021         // The list should be in same order as the final result.
1022         DCHECK(block->rpo_number() == links + header->rpo_number());
1023         links++;
1024         block = block->rpo_next();
1025         DCHECK_LT(links, static_cast<int>(2 * order->size()));  // cycle?
1026       }
1027       DCHECK(links > 0);
1028       DCHECK(links == end->rpo_number() - header->rpo_number());
1029       DCHECK(end_found);
1030
1031       // Check loop depth of the header.
1032       int loop_depth = 0;
1033       for (LoopInfo* outer = loop; outer != NULL; outer = outer->prev) {
1034         loop_depth++;
1035       }
1036       DCHECK_EQ(loop_depth, header->loop_depth());
1037
1038       // Check the contiguousness of loops.
1039       int count = 0;
1040       for (int j = 0; j < static_cast<int>(order->size()); j++) {
1041         BasicBlock* block = order->at(j);
1042         DCHECK(block->rpo_number() == j);
1043         if (j < header->rpo_number() || j >= end->rpo_number()) {
1044           DCHECK(!header->LoopContains(block));
1045         } else {
1046           DCHECK(header->LoopContains(block));
1047           DCHECK_GE(block->loop_depth(), loop_depth);
1048           count++;
1049         }
1050       }
1051       DCHECK(links == count);
1052     }
1053   }
1054 #endif  // DEBUG
1055
1056   Zone* zone_;
1057   Schedule* schedule_;
1058   BasicBlock* order_;
1059   BasicBlock* beyond_end_;
1060   ZoneVector<LoopInfo> loops_;
1061   ZoneVector<Backedge> backedges_;
1062   ZoneVector<SpecialRPOStackFrame> stack_;
1063   size_t previous_block_count_;
1064   ZoneList<BasicBlock*> const empty_;
1065 };
1066
1067
1068 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
1069   SpecialRPONumberer numberer(zone, schedule);
1070   numberer.ComputeSpecialRPO();
1071   numberer.SerializeRPOIntoSchedule();
1072   numberer.PrintAndVerifySpecialRPO();
1073   return schedule->rpo_order();
1074 }
1075
1076
1077 void Scheduler::ComputeSpecialRPONumbering() {
1078   TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n");
1079
1080   // Compute the special reverse-post-order for basic blocks.
1081   special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_);
1082   special_rpo_->ComputeSpecialRPO();
1083 }
1084
1085
1086 void Scheduler::PropagateImmediateDominators(BasicBlock* block) {
1087   for (/*nop*/; block != NULL; block = block->rpo_next()) {
1088     auto pred = block->predecessors().begin();
1089     auto end = block->predecessors().end();
1090     DCHECK(pred != end);  // All blocks except start have predecessors.
1091     BasicBlock* dominator = *pred;
1092     bool deferred = dominator->deferred();
1093     // For multiple predecessors, walk up the dominator tree until a common
1094     // dominator is found. Visitation order guarantees that all predecessors
1095     // except for backwards edges have been visited.
1096     for (++pred; pred != end; ++pred) {
1097       // Don't examine backwards edges.
1098       if ((*pred)->dominator_depth() < 0) continue;
1099       dominator = BasicBlock::GetCommonDominator(dominator, *pred);
1100       deferred = deferred & (*pred)->deferred();
1101     }
1102     block->set_dominator(dominator);
1103     block->set_dominator_depth(dominator->dominator_depth() + 1);
1104     block->set_deferred(deferred | block->deferred());
1105     TRACE("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(),
1106           dominator->id().ToInt(), block->dominator_depth());
1107   }
1108 }
1109
1110
1111 void Scheduler::GenerateImmediateDominatorTree() {
1112   TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
1113
1114   // Seed start block to be the first dominator.
1115   schedule_->start()->set_dominator_depth(0);
1116
1117   // Build the block dominator tree resulting from the above seed.
1118   PropagateImmediateDominators(schedule_->start()->rpo_next());
1119 }
1120
1121
1122 // -----------------------------------------------------------------------------
1123 // Phase 3: Prepare use counts for nodes.
1124
1125
1126 class PrepareUsesVisitor {
1127  public:
1128   explicit PrepareUsesVisitor(Scheduler* scheduler)
1129       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
1130
1131   void Pre(Node* node) {
1132     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
1133       // Fixed nodes are always roots for schedule late.
1134       scheduler_->schedule_root_nodes_.push_back(node);
1135       if (!schedule_->IsScheduled(node)) {
1136         // Make sure root nodes are scheduled in their respective blocks.
1137         TRACE("Scheduling fixed position node #%d:%s\n", node->id(),
1138               node->op()->mnemonic());
1139         IrOpcode::Value opcode = node->opcode();
1140         BasicBlock* block =
1141             opcode == IrOpcode::kParameter
1142                 ? schedule_->start()
1143                 : schedule_->block(NodeProperties::GetControlInput(node));
1144         DCHECK(block != NULL);
1145         schedule_->AddNode(block, node);
1146       }
1147     }
1148   }
1149
1150   void PostEdge(Node* from, int index, Node* to) {
1151     // If the edge is from an unscheduled node, then tally it in the use count
1152     // for all of its inputs. The same criterion will be used in ScheduleLate
1153     // for decrementing use counts.
1154     if (!schedule_->IsScheduled(from)) {
1155       DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
1156       scheduler_->IncrementUnscheduledUseCount(to, index, from);
1157     }
1158   }
1159
1160  private:
1161   Scheduler* scheduler_;
1162   Schedule* schedule_;
1163 };
1164
1165
1166 void Scheduler::PrepareUses() {
1167   TRACE("--- PREPARE USES -------------------------------------------\n");
1168
1169   // Count the uses of every node, which is used to ensure that all of a
1170   // node's uses are scheduled before the node itself.
1171   PrepareUsesVisitor prepare_uses(this);
1172
1173   // TODO(turbofan): simplify the careful pre/post ordering here.
1174   BoolVector visited(graph_->NodeCount(), false, zone_);
1175   ZoneStack<Node::InputEdges::iterator> stack(zone_);
1176   Node* node = graph_->end();
1177   prepare_uses.Pre(node);
1178   visited[node->id()] = true;
1179   stack.push(node->input_edges().begin());
1180   while (!stack.empty()) {
1181     Edge edge = *stack.top();
1182     Node* node = edge.to();
1183     if (visited[node->id()]) {
1184       prepare_uses.PostEdge(edge.from(), edge.index(), edge.to());
1185       if (++stack.top() == edge.from()->input_edges().end()) stack.pop();
1186     } else {
1187       prepare_uses.Pre(node);
1188       visited[node->id()] = true;
1189       if (node->InputCount() > 0) stack.push(node->input_edges().begin());
1190     }
1191   }
1192 }
1193
1194
1195 // -----------------------------------------------------------------------------
1196 // Phase 4: Schedule nodes early.
1197
1198
1199 class ScheduleEarlyNodeVisitor {
1200  public:
1201   ScheduleEarlyNodeVisitor(Zone* zone, Scheduler* scheduler)
1202       : scheduler_(scheduler), schedule_(scheduler->schedule_), queue_(zone) {}
1203
1204   // Run the schedule early algorithm on a set of fixed root nodes.
1205   void Run(NodeVector* roots) {
1206     for (Node* const root : *roots) {
1207       queue_.push(root);
1208       while (!queue_.empty()) {
1209         VisitNode(queue_.front());
1210         queue_.pop();
1211       }
1212     }
1213   }
1214
1215  private:
1216   // Visits one node from the queue and propagates its current schedule early
1217   // position to all uses. This in turn might push more nodes onto the queue.
1218   void VisitNode(Node* node) {
1219     Scheduler::SchedulerData* data = scheduler_->GetData(node);
1220
1221     // Fixed nodes already know their schedule early position.
1222     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
1223       data->minimum_block_ = schedule_->block(node);
1224       TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1225             node->id(), node->op()->mnemonic(),
1226             data->minimum_block_->id().ToInt(),
1227             data->minimum_block_->dominator_depth());
1228     }
1229
1230     // No need to propagate unconstrained schedule early positions.
1231     if (data->minimum_block_ == schedule_->start()) return;
1232
1233     // Propagate schedule early position.
1234     DCHECK(data->minimum_block_ != NULL);
1235     for (auto use : node->uses()) {
1236       PropagateMinimumPositionToNode(data->minimum_block_, use);
1237     }
1238   }
1239
1240   // Propagates {block} as another minimum position into the given {node}. This
1241   // has the net effect of computing the minimum dominator block of {node} that
1242   // still post-dominates all inputs to {node} when the queue is processed.
1243   void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) {
1244     Scheduler::SchedulerData* data = scheduler_->GetData(node);
1245
1246     // No need to propagate to fixed node, it's guaranteed to be a root.
1247     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;
1248
1249     // Coupled nodes influence schedule early position of their control.
1250     if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1251       Node* control = NodeProperties::GetControlInput(node);
1252       PropagateMinimumPositionToNode(block, control);
1253     }
1254
1255     // Propagate new position if it is deeper down the dominator tree than the
1256     // current. Note that all inputs need to have minimum block position inside
1257     // the dominator chain of {node}'s minimum block position.
1258     DCHECK(InsideSameDominatorChain(block, data->minimum_block_));
1259     if (block->dominator_depth() > data->minimum_block_->dominator_depth()) {
1260       data->minimum_block_ = block;
1261       queue_.push(node);
1262       TRACE("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1263             node->id(), node->op()->mnemonic(),
1264             data->minimum_block_->id().ToInt(),
1265             data->minimum_block_->dominator_depth());
1266     }
1267   }
1268
1269 #if DEBUG
1270   bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) {
1271     BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2);
1272     return dominator == b1 || dominator == b2;
1273   }
1274 #endif
1275
1276   Scheduler* scheduler_;
1277   Schedule* schedule_;
1278   ZoneQueue<Node*> queue_;
1279 };
1280
1281
1282 void Scheduler::ScheduleEarly() {
1283   TRACE("--- SCHEDULE EARLY -----------------------------------------\n");
1284   if (FLAG_trace_turbo_scheduler) {
1285     TRACE("roots: ");
1286     for (Node* node : schedule_root_nodes_) {
1287       TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1288     }
1289     TRACE("\n");
1290   }
1291
1292   // Compute the minimum block for each node thereby determining the earliest
1293   // position each node could be placed within a valid schedule.
1294   ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
1295   schedule_early_visitor.Run(&schedule_root_nodes_);
1296 }
1297
1298
1299 // -----------------------------------------------------------------------------
1300 // Phase 5: Schedule nodes late.
1301
1302
1303 class ScheduleLateNodeVisitor {
1304  public:
1305   ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
1306       : scheduler_(scheduler),
1307         schedule_(scheduler_->schedule_),
1308         marked_(scheduler->zone_),
1309         marking_queue_(scheduler->zone_) {}
1310
1311   // Run the schedule late algorithm on a set of fixed root nodes.
1312   void Run(NodeVector* roots) {
1313     for (Node* const root : *roots) {
1314       ProcessQueue(root);
1315     }
1316   }
1317
1318  private:
1319   void ProcessQueue(Node* root) {
1320     ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
1321     for (Node* node : root->inputs()) {
1322       // Don't schedule coupled nodes on their own.
1323       if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1324         node = NodeProperties::GetControlInput(node);
1325       }
1326
1327       // Test schedulability condition by looking at unscheduled use count.
1328       if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;
1329
1330       queue->push(node);
1331       do {
1332         Node* const node = queue->front();
1333         queue->pop();
1334         VisitNode(node);
1335       } while (!queue->empty());
1336     }
1337   }
1338
1339   // Visits one node from the queue of schedulable nodes and determines its
1340   // schedule late position. Also hoists nodes out of loops to find a more
1341   // optimal scheduling position.
1342   void VisitNode(Node* node) {
1343     DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1344
1345     // Don't schedule nodes that are already scheduled.
1346     if (schedule_->IsScheduled(node)) return;
1347     DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));
1348
1349     // Determine the dominating block for all of the uses of this node. It is
1350     // the latest block that this node can be scheduled in.
1351     TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
1352     BasicBlock* block = GetCommonDominatorOfUses(node);
1353     DCHECK_NOT_NULL(block);
1354
1355     // The schedule early block dominates the schedule late block.
1356     BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
1357     DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
1358     TRACE(
1359         "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n",
1360         node->id(), node->op()->mnemonic(), block->id().ToInt(),
1361         block->loop_depth(), min_block->id().ToInt());
1362
1363     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
1364     // into enclosing loop pre-headers until they would preceed their schedule
1365     // early position.
1366     BasicBlock* hoist_block = GetHoistBlock(block);
1367     if (hoist_block &&
1368         hoist_block->dominator_depth() >= min_block->dominator_depth()) {
1369       do {
1370         TRACE("  hoisting #%d:%s to block id:%d\n", node->id(),
1371               node->op()->mnemonic(), hoist_block->id().ToInt());
1372         DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
1373         block = hoist_block;
1374         hoist_block = GetHoistBlock(hoist_block);
1375       } while (hoist_block &&
1376                hoist_block->dominator_depth() >= min_block->dominator_depth());
1377     } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
1378       // Split the {node} if beneficial and return the new {block} for it.
1379       block = SplitNode(block, node);
1380     }
1381
1382     // Schedule the node or a floating control structure.
1383     if (IrOpcode::IsMergeOpcode(node->opcode())) {
1384       ScheduleFloatingControl(block, node);
1385     } else {
1386       ScheduleNode(block, node);
1387     }
1388   }
1389
1390   // Mark {block} and push its non-marked predecessor on the marking queue.
1391   void MarkBlock(BasicBlock* block) {
1392     DCHECK_LT(block->id().ToSize(), marked_.size());
1393     marked_[block->id().ToSize()] = true;
1394     for (BasicBlock* pred_block : block->predecessors()) {
1395       DCHECK_LT(pred_block->id().ToSize(), marked_.size());
1396       if (marked_[pred_block->id().ToSize()]) continue;
1397       marking_queue_.push_back(pred_block);
1398     }
1399   }
1400
1401   BasicBlock* SplitNode(BasicBlock* block, Node* node) {
1402     // For now, we limit splitting to pure nodes.
1403     if (!node->op()->HasProperty(Operator::kPure)) return block;
1404     // TODO(titzer): fix the special case of splitting of projections.
1405     if (node->opcode() == IrOpcode::kProjection) return block;
1406
1407     // The {block} is common dominator of all uses of {node}, so we cannot
1408     // split anything unless the {block} has at least two successors.
1409     DCHECK_EQ(block, GetCommonDominatorOfUses(node));
1410     if (block->SuccessorCount() < 2) return block;
1411
1412     // Clear marking bits.
1413     DCHECK(marking_queue_.empty());
1414     std::fill(marked_.begin(), marked_.end(), false);
1415     marked_.resize(schedule_->BasicBlockCount() + 1, false);
1416
1417     // Check if the {node} has uses in {block}.
1418     for (Edge edge : node->use_edges()) {
1419       BasicBlock* use_block = GetBlockForUse(edge);
1420       if (use_block == nullptr || marked_[use_block->id().ToSize()]) continue;
1421       if (use_block == block) {
1422         TRACE("  not splitting #%d:%s, it is used in id:%d\n", node->id(),
1423               node->op()->mnemonic(), block->id().ToInt());
1424         marking_queue_.clear();
1425         return block;
1426       }
1427       MarkBlock(use_block);
1428     }
1429
1430     // Compute transitive marking closure; a block is marked if all its
1431     // successors are marked.
1432     do {
1433       BasicBlock* top_block = marking_queue_.front();
1434       marking_queue_.pop_front();
1435       if (marked_[top_block->id().ToSize()]) continue;
1436       bool marked = true;
1437       for (BasicBlock* successor : top_block->successors()) {
1438         if (!marked_[successor->id().ToSize()]) {
1439           marked = false;
1440           break;
1441         }
1442       }
1443       if (marked) MarkBlock(top_block);
1444     } while (!marking_queue_.empty());
1445
1446     // If the (common dominator) {block} is marked, we know that all paths from
1447     // {block} to the end contain at least one use of {node}, and hence there's
1448     // no point in splitting the {node} in this case.
1449     if (marked_[block->id().ToSize()]) {
1450       TRACE("  not splitting #%d:%s, its common dominator id:%d is perfect\n",
1451             node->id(), node->op()->mnemonic(), block->id().ToInt());
1452       return block;
1453     }
1454
1455     // Split {node} for uses according to the previously computed marking
1456     // closure. Every marking partition has a unique dominator, which get's a
1457     // copy of the {node} with the exception of the first partition, which get's
1458     // the {node} itself.
1459     ZoneMap<BasicBlock*, Node*> dominators(scheduler_->zone_);
1460     for (Edge edge : node->use_edges()) {
1461       BasicBlock* use_block = GetBlockForUse(edge);
1462       if (use_block == nullptr) continue;
1463       while (marked_[use_block->dominator()->id().ToSize()]) {
1464         use_block = use_block->dominator();
1465       }
1466       auto& use_node = dominators[use_block];
1467       if (use_node == nullptr) {
1468         if (dominators.size() == 1u) {
1469           // Place the {node} at {use_block}.
1470           block = use_block;
1471           use_node = node;
1472           TRACE("  pushing #%d:%s down to id:%d\n", node->id(),
1473                 node->op()->mnemonic(), block->id().ToInt());
1474         } else {
1475           // Place a copy of {node} at {use_block}.
1476           use_node = CloneNode(node);
1477           TRACE("  cloning #%d:%s for id:%d\n", use_node->id(),
1478                 use_node->op()->mnemonic(), use_block->id().ToInt());
1479           scheduler_->schedule_queue_.push(use_node);
1480         }
1481       }
1482       edge.UpdateTo(use_node);
1483     }
1484     return block;
1485   }
1486
1487   BasicBlock* GetHoistBlock(BasicBlock* block) {
1488     if (block->IsLoopHeader()) return block->dominator();
1489     // We have to check to make sure that the {block} dominates all
1490     // of the outgoing blocks.  If it doesn't, then there is a path
1491     // out of the loop which does not execute this {block}, so we
1492     // can't hoist operations from this {block} out of the loop, as
1493     // that would introduce additional computations.
1494     if (BasicBlock* header_block = block->loop_header()) {
1495       for (BasicBlock* outgoing_block :
1496            scheduler_->special_rpo_->GetOutgoingBlocks(header_block)) {
1497         if (BasicBlock::GetCommonDominator(block, outgoing_block) != block) {
1498           return nullptr;
1499         }
1500       }
1501       return header_block->dominator();
1502     }
1503     return nullptr;
1504   }
1505
1506   BasicBlock* GetCommonDominatorOfUses(Node* node) {
1507     BasicBlock* block = nullptr;
1508     for (Edge edge : node->use_edges()) {
1509       BasicBlock* use_block = GetBlockForUse(edge);
1510       block = block == NULL ? use_block : use_block == NULL
1511                                               ? block
1512                                               : BasicBlock::GetCommonDominator(
1513                                                     block, use_block);
1514     }
1515     return block;
1516   }
1517
1518   BasicBlock* FindPredecessorBlock(Node* node) {
1519     return scheduler_->control_flow_builder_->FindPredecessorBlock(node);
1520   }
1521
1522   BasicBlock* GetBlockForUse(Edge edge) {
1523     Node* use = edge.from();
1524     if (IrOpcode::IsPhiOpcode(use->opcode())) {
1525       // If the use is from a coupled (i.e. floating) phi, compute the common
1526       // dominator of its uses. This will not recurse more than one level.
1527       if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) {
1528         TRACE("  inspecting uses of coupled #%d:%s\n", use->id(),
1529               use->op()->mnemonic());
1530         DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use));
1531         return GetCommonDominatorOfUses(use);
1532       }
1533       // If the use is from a fixed (i.e. non-floating) phi, we use the
1534       // predecessor block of the corresponding control input to the merge.
1535       if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1536         TRACE("  input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(),
1537               use->op()->mnemonic());
1538         Node* merge = NodeProperties::GetControlInput(use, 0);
1539         DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
1540         Node* input = NodeProperties::GetControlInput(merge, edge.index());
1541         return FindPredecessorBlock(input);
1542       }
1543     } else if (IrOpcode::IsMergeOpcode(use->opcode())) {
1544       // If the use is from a fixed (i.e. non-floating) merge, we use the
1545       // predecessor block of the current input to the merge.
1546       if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1547         TRACE("  input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(),
1548               use->op()->mnemonic());
1549         return FindPredecessorBlock(edge.to());
1550       }
1551     }
1552     BasicBlock* result = schedule_->block(use);
1553     if (result == NULL) return NULL;
1554     TRACE("  must dominate use #%d:%s in id:%d\n", use->id(),
1555           use->op()->mnemonic(), result->id().ToInt());
1556     return result;
1557   }
1558
1559   void ScheduleFloatingControl(BasicBlock* block, Node* node) {
1560     scheduler_->FuseFloatingControl(block, node);
1561   }
1562
1563   void ScheduleNode(BasicBlock* block, Node* node) {
1564     schedule_->PlanNode(block, node);
1565     scheduler_->scheduled_nodes_[block->id().ToSize()].push_back(node);
1566     scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
1567   }
1568
1569   Node* CloneNode(Node* node) {
1570     int const input_count = node->InputCount();
1571     Node** const inputs = scheduler_->zone_->NewArray<Node*>(input_count);
1572     for (int index = 0; index < input_count; ++index) {
1573       Node* const input = node->InputAt(index);
1574       scheduler_->IncrementUnscheduledUseCount(input, index, node);
1575       inputs[index] = input;
1576     }
1577     Node* copy = scheduler_->graph_->NewNode(node->op(), input_count, inputs);
1578     TRACE(("clone #%d:%s -> #%d\n"), node->id(), node->op()->mnemonic(),
1579           copy->id());
1580     scheduler_->node_data_.resize(copy->id() + 1,
1581                                   scheduler_->DefaultSchedulerData());
1582     scheduler_->node_data_[copy->id()] = scheduler_->node_data_[node->id()];
1583     return copy;
1584   }
1585
1586   Scheduler* scheduler_;
1587   Schedule* schedule_;
1588   BoolVector marked_;
1589   ZoneDeque<BasicBlock*> marking_queue_;
1590 };
1591
1592
1593 void Scheduler::ScheduleLate() {
1594   TRACE("--- SCHEDULE LATE ------------------------------------------\n");
1595   if (FLAG_trace_turbo_scheduler) {
1596     TRACE("roots: ");
1597     for (Node* node : schedule_root_nodes_) {
1598       TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1599     }
1600     TRACE("\n");
1601   }
1602
1603   // Schedule: Places nodes in dominator block of all their uses.
1604   ScheduleLateNodeVisitor schedule_late_visitor(zone_, this);
1605   schedule_late_visitor.Run(&schedule_root_nodes_);
1606 }
1607
1608
1609 // -----------------------------------------------------------------------------
1610 // Phase 6: Seal the final schedule.
1611
1612
1613 void Scheduler::SealFinalSchedule() {
1614   TRACE("--- SEAL FINAL SCHEDULE ------------------------------------\n");
1615
1616   // Serialize the assembly order and reverse-post-order numbering.
1617   special_rpo_->SerializeRPOIntoSchedule();
1618   special_rpo_->PrintAndVerifySpecialRPO();
1619
1620   // Add collected nodes for basic blocks to their blocks in the right order.
1621   int block_num = 0;
1622   for (NodeVector& nodes : scheduled_nodes_) {
1623     BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++);
1624     BasicBlock* block = schedule_->GetBlockById(id);
1625     for (auto i = nodes.rbegin(); i != nodes.rend(); ++i) {
1626       schedule_->AddNode(block, *i);
1627     }
1628   }
1629 }
1630
1631
1632 // -----------------------------------------------------------------------------
1633
1634
1635 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
1636   TRACE("--- FUSE FLOATING CONTROL ----------------------------------\n");
1637   if (FLAG_trace_turbo_scheduler) {
1638     OFStream os(stdout);
1639     os << "Schedule before control flow fusion:\n" << *schedule_;
1640   }
1641
1642   // Iterate on phase 1: Build control-flow graph.
1643   control_flow_builder_->Run(block, node);
1644
1645   // Iterate on phase 2: Compute special RPO and dominator tree.
1646   special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
1647   // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
1648   for (BasicBlock* b = block->rpo_next(); b != NULL; b = b->rpo_next()) {
1649     b->set_dominator_depth(-1);
1650     b->set_dominator(NULL);
1651   }
1652   PropagateImmediateDominators(block->rpo_next());
1653
1654   // Iterate on phase 4: Schedule nodes early.
1655   // TODO(mstarzinger): The following loop gathering the propagation roots is a
1656   // temporary solution and should be merged into the rest of the scheduler as
1657   // soon as the approach settled for all floating loops.
1658   NodeVector propagation_roots(control_flow_builder_->control_);
1659   for (Node* node : control_flow_builder_->control_) {
1660     for (Node* use : node->uses()) {
1661       if (NodeProperties::IsPhi(use)) propagation_roots.push_back(use);
1662     }
1663   }
1664   if (FLAG_trace_turbo_scheduler) {
1665     TRACE("propagation roots: ");
1666     for (Node* node : propagation_roots) {
1667       TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1668     }
1669     TRACE("\n");
1670   }
1671   ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
1672   schedule_early_visitor.Run(&propagation_roots);
1673
1674   // Move previously planned nodes.
1675   // TODO(mstarzinger): Improve that by supporting bulk moves.
1676   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
1677   MovePlannedNodes(block, schedule_->block(node));
1678
1679   if (FLAG_trace_turbo_scheduler) {
1680     OFStream os(stdout);
1681     os << "Schedule after control flow fusion:\n" << *schedule_;
1682   }
1683 }
1684
1685
1686 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
1687   TRACE("Move planned nodes from id:%d to id:%d\n", from->id().ToInt(),
1688         to->id().ToInt());
1689   NodeVector* nodes = &(scheduled_nodes_[from->id().ToSize()]);
1690   for (Node* const node : *nodes) {
1691     schedule_->SetBlockForNode(to, node);
1692     scheduled_nodes_[to->id().ToSize()].push_back(node);
1693   }
1694   nodes->clear();
1695 }
1696
1697 }  // namespace compiler
1698 }  // namespace internal
1699 }  // namespace v8