scheduler.cc 65.2 KB
Newer Older
1 2 3 4 5 6
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/scheduler.h"

7 8
#include <iomanip>

9
#include "src/base/adapters.h"
10
#include "src/bit-vector.h"
11
#include "src/compiler/common-operator.h"
12
#include "src/compiler/control-equivalence.h"
13
#include "src/compiler/graph.h"
14
#include "src/compiler/node-marker.h"
15
#include "src/compiler/node-properties.h"
16 17
#include "src/compiler/node.h"
#include "src/zone/zone-containers.h"
18 19 20 21 22

namespace v8 {
namespace internal {
namespace compiler {

23 24 25 26
#define TRACE(...)                                       \
  do {                                                   \
    if (FLAG_trace_turbo_scheduler) PrintF(__VA_ARGS__); \
  } while (false)
27

28 29
Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
                     size_t node_count_hint)
30
    : zone_(zone),
31 32
      graph_(graph),
      schedule_(schedule),
33
      flags_(flags),
34 35
      scheduled_nodes_(zone),
      schedule_root_nodes_(zone),
36
      schedule_queue_(zone),
37 38 39 40
      node_data_(zone) {
  node_data_.reserve(node_count_hint);
  node_data_.resize(graph->NodeCount(), DefaultSchedulerData());
}
41

42
Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags) {
43 44
  Zone* schedule_zone =
      (flags & Scheduler::kTempSchedule) ? zone : graph->zone();
45 46 47 48 49 50 51 52 53

  // Reserve 10% more space for nodes if node splitting is enabled to try to
  // avoid resizing the vector since that would triple its zone memory usage.
  float node_hint_multiplier = (flags & Scheduler::kSplitNodes) ? 1.1 : 1;
  size_t node_count_hint = node_hint_multiplier * graph->NodeCount();

  Schedule* schedule =
      new (schedule_zone) Schedule(schedule_zone, node_count_hint);
  Scheduler scheduler(zone, graph, schedule, flags, node_count_hint);
54

55 56 57
  scheduler.BuildCFG();
  scheduler.ComputeSpecialRPONumbering();
  scheduler.GenerateImmediateDominatorTree();
58

59 60 61
  scheduler.PrepareUses();
  scheduler.ScheduleEarly();
  scheduler.ScheduleLate();
62

63 64
  scheduler.SealFinalSchedule();

65 66 67 68
  return schedule;
}


69
Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
70
  SchedulerData def = {schedule_->start(), 0, kUnknown};
71 72 73 74
  return def;
}


75 76 77 78
Scheduler::SchedulerData* Scheduler::GetData(Node* node) {
  return &node_data_[node->id()];
}

79
Scheduler::Placement Scheduler::InitializePlacement(Node* node) {
80
  SchedulerData* data = GetData(node);
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  if (data->placement_ == kFixed) {
    // Nothing to do for control nodes that have been already fixed in
    // the schedule.
    return data->placement_;
  }
  DCHECK_EQ(kUnknown, data->placement_);
  switch (node->opcode()) {
    case IrOpcode::kParameter:
    case IrOpcode::kOsrValue:
      // Parameters and OSR values are always fixed to the start block.
      data->placement_ = kFixed;
      break;
    case IrOpcode::kPhi:
    case IrOpcode::kEffectPhi: {
      // Phis and effect phis are fixed if their control inputs are, whereas
      // otherwise they are coupled to a floating control node.
      Placement p = GetPlacement(NodeProperties::GetControlInput(node));
      data->placement_ = (p == kFixed ? kFixed : kCoupled);
      break;
    }
101 102 103
#define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
      CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
#undef DEFINE_CONTROL_CASE
104 105 106 107
      {
        // Control nodes that were not control-reachable from end may float.
        data->placement_ = kSchedulable;
        break;
108
    }
109 110 111
    default:
      data->placement_ = kSchedulable;
      break;
112 113 114 115
  }
  return data->placement_;
}

116 117 118 119 120
Scheduler::Placement Scheduler::GetPlacement(Node* node) {
  return GetData(node)->placement_;
}

bool Scheduler::IsLive(Node* node) { return GetPlacement(node) != kUnknown; }
121

122 123
void Scheduler::UpdatePlacement(Node* node, Placement placement) {
  SchedulerData* data = GetData(node);
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
  if (data->placement_ == kUnknown) {
    // We only update control nodes from {kUnknown} to {kFixed}.  Ideally, we
    // should check that {node} is a control node (including exceptional calls),
    // but that is expensive.
    DCHECK_EQ(Scheduler::kFixed, placement);
    data->placement_ = placement;
    return;
  }

  switch (node->opcode()) {
    case IrOpcode::kParameter:
      // Parameters are fixed once and for all.
      UNREACHABLE();
      break;
    case IrOpcode::kPhi:
    case IrOpcode::kEffectPhi: {
      // Phis and effect phis are coupled to their respective blocks.
      DCHECK_EQ(Scheduler::kCoupled, data->placement_);
      DCHECK_EQ(Scheduler::kFixed, placement);
      Node* control = NodeProperties::GetControlInput(node);
      BasicBlock* block = schedule_->block(control);
      schedule_->AddNode(block, node);
      break;
    }
148 149 150
#define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
      CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
#undef DEFINE_CONTROL_CASE
151 152
      {
        // Control nodes force coupled uses to be placed.
153 154 155 156
        for (auto use : node->uses()) {
          if (GetPlacement(use) == Scheduler::kCoupled) {
            DCHECK_EQ(node, NodeProperties::GetControlInput(use));
            UpdatePlacement(use, placement);
157 158
          }
      }
159
      break;
160
    }
161 162 163 164 165 166 167 168 169 170
    default:
      DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
      DCHECK_EQ(Scheduler::kScheduled, placement);
      break;
  }
  // Reduce the use count of the node's inputs to potentially make them
  // schedulable. If all the uses of a node have been scheduled, then the node
  // itself can be scheduled.
  for (Edge const edge : node->input_edges()) {
    DecrementUnscheduledUseCount(edge.to(), edge.index(), edge.from());
171 172 173 174 175
  }
  data->placement_ = placement;
}


176 177 178 179 180 181 182 183 184 185 186
bool Scheduler::IsCoupledControlEdge(Node* node, int index) {
  return GetPlacement(node) == kCoupled &&
         NodeProperties::FirstControlIndex(node) == index;
}


void Scheduler::IncrementUnscheduledUseCount(Node* node, int index,
                                             Node* from) {
  // Make sure that control edges from coupled nodes are not counted.
  if (IsCoupledControlEdge(from, index)) return;

187 188 189
  // Tracking use counts for fixed nodes is useless.
  if (GetPlacement(node) == kFixed) return;

190
  // Use count for coupled nodes is summed up on their control.
191 192
  if (GetPlacement(node) == kCoupled) {
    Node* control = NodeProperties::GetControlInput(node);
193
    return IncrementUnscheduledUseCount(control, index, from);
194
  }
195

196 197
  ++(GetData(node)->unscheduled_count_);
  if (FLAG_trace_turbo_scheduler) {
198
    TRACE("  Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
199 200 201 202 203 204
          node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
          GetData(node)->unscheduled_count_);
  }
}


205 206 207 208 209
void Scheduler::DecrementUnscheduledUseCount(Node* node, int index,
                                             Node* from) {
  // Make sure that control edges from coupled nodes are not counted.
  if (IsCoupledControlEdge(from, index)) return;

210 211 212
  // Tracking use counts for fixed nodes is useless.
  if (GetPlacement(node) == kFixed) return;

213
  // Use count for coupled nodes is summed up on their control.
214 215
  if (GetPlacement(node) == kCoupled) {
    Node* control = NodeProperties::GetControlInput(node);
216
    return DecrementUnscheduledUseCount(control, index, from);
217
  }
218

219
  DCHECK_LT(0, GetData(node)->unscheduled_count_);
220 221
  --(GetData(node)->unscheduled_count_);
  if (FLAG_trace_turbo_scheduler) {
222
    TRACE("  Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(),
223 224 225 226
          node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
          GetData(node)->unscheduled_count_);
  }
  if (GetData(node)->unscheduled_count_ == 0) {
227
    TRACE("    newly eligible #%d:%s\n", node->id(), node->op()->mnemonic());
228 229 230 231 232
    schedule_queue_.push(node);
  }
}


233
// -----------------------------------------------------------------------------
234
// Phase 1: Build control-flow graph.
235 236


237
// Internal class to build a control flow graph (i.e the basic blocks and edges
238 239 240
// between them within a Schedule) from the node graph. Visits control edges of
// the graph backwards from an end node in order to find the connected control
// subgraph, needed for scheduling.
241
class CFGBuilder : public ZoneObject {
242
 public:
243
  CFGBuilder(Zone* zone, Scheduler* scheduler)
244 245
      : zone_(zone),
        scheduler_(scheduler),
246
        schedule_(scheduler->schedule_),
247
        queued_(scheduler->graph_, 2),
248
        queue_(zone),
249
        control_(zone),
250 251 252
        component_entry_(nullptr),
        component_start_(nullptr),
        component_end_(nullptr) {}
253 254 255 256 257

  // Run the control flow graph construction algorithm by walking the graph
  // backwards from end through control edges, building and connecting the
  // basic blocks for control nodes.
  void Run() {
258
    ResetDataStructures();
259
    Queue(scheduler_->graph_->end());
260 261 262 263 264 265 266 267 268

    while (!queue_.empty()) {  // Breadth-first backwards traversal.
      Node* node = queue_.front();
      queue_.pop();
      int max = NodeProperties::PastControlIndex(node);
      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
        Queue(node->InputAt(i));
      }
    }
269

270 271 272 273 274
    for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
      ConnectBlocks(*i);  // Connect block to its predecessor/successors.
    }
  }

275
  // Run the control flow graph construction for a minimal control-connected
276
  // component ending in {exit} and merge that component into an existing
277
  // control flow graph at the bottom of {block}.
278
  void Run(BasicBlock* block, Node* exit) {
279
    ResetDataStructures();
280
    Queue(exit);
281

282
    component_entry_ = nullptr;
283
    component_start_ = block;
284 285
    component_end_ = schedule_->block(exit);
    scheduler_->equivalence_->Run(exit);
286 287 288
    while (!queue_.empty()) {  // Breadth-first backwards traversal.
      Node* node = queue_.front();
      queue_.pop();
289 290 291 292

      // Use control dependence equivalence to find a canonical single-entry
      // single-exit region that makes up a minimal component to be scheduled.
      if (IsSingleEntrySingleExitRegion(node, exit)) {
293
        TRACE("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic());
294
        DCHECK(!component_entry_);
295 296 297 298
        component_entry_ = node;
        continue;
      }

299 300 301 302 303
      int max = NodeProperties::PastControlIndex(node);
      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
        Queue(node->InputAt(i));
      }
    }
304
    DCHECK(component_entry_);
305 306 307 308 309 310 311

    for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
      ConnectBlocks(*i);  // Connect block to its predecessor/successors.
    }
  }

 private:
312
  friend class ScheduleLateNodeVisitor;
313 314
  friend class Scheduler;

315 316
  void FixNode(BasicBlock* block, Node* node) {
    schedule_->AddNode(block, node);
317
    scheduler_->UpdatePlacement(node, Scheduler::kFixed);
318
  }
319

320
  void Queue(Node* node) {
321
    // Mark the connected control nodes as they are queued.
322
    if (!queued_.Get(node)) {
323 324
      BuildBlocks(node);
      queue_.push(node);
325
      queued_.Set(node, true);
326 327 328 329 330
      control_.push_back(node);
    }
  }

  void BuildBlocks(Node* node) {
331
    switch (node->opcode()) {
332 333 334 335 336 337
      case IrOpcode::kEnd:
        FixNode(schedule_->end(), node);
        break;
      case IrOpcode::kStart:
        FixNode(schedule_->start(), node);
        break;
338 339 340 341
      case IrOpcode::kLoop:
      case IrOpcode::kMerge:
        BuildBlockForNode(node);
        break;
342 343 344 345 346 347 348
      case IrOpcode::kTerminate: {
        // Put Terminate in the loop to which it refers.
        Node* loop = NodeProperties::GetControlInput(node);
        BasicBlock* block = BuildBlockForNode(loop);
        FixNode(block, node);
        break;
      }
349
      case IrOpcode::kBranch:
350 351
      case IrOpcode::kSwitch:
        BuildBlocksForSuccessors(node);
352
        break;
353 354 355 356
#define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
        JS_OP_LIST(BUILD_BLOCK_JS_CASE)
// JS opcodes are just like calls => fall through.
#undef BUILD_BLOCK_JS_CASE
357
      case IrOpcode::kCall:
358
      case IrOpcode::kCallWithCallerSavedRegisters:
svenpanne's avatar
svenpanne committed
359
        if (NodeProperties::IsExceptionalCall(node)) {
360 361 362
          BuildBlocksForSuccessors(node);
        }
        break;
363 364 365 366 367
      default:
        break;
    }
  }

368
  void ConnectBlocks(Node* node) {
369 370 371 372 373 374
    switch (node->opcode()) {
      case IrOpcode::kLoop:
      case IrOpcode::kMerge:
        ConnectMerge(node);
        break;
      case IrOpcode::kBranch:
375
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
376 377
        ConnectBranch(node);
        break;
378 379 380 381
      case IrOpcode::kSwitch:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectSwitch(node);
        break;
382 383 384 385
      case IrOpcode::kDeoptimize:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectDeoptimize(node);
        break;
386 387 388 389
      case IrOpcode::kTailCall:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectTailCall(node);
        break;
390
      case IrOpcode::kReturn:
391
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
392 393
        ConnectReturn(node);
        break;
394 395 396 397
      case IrOpcode::kThrow:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectThrow(node);
        break;
398 399 400 401
#define CONNECT_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
        JS_OP_LIST(CONNECT_BLOCK_JS_CASE)
// JS opcodes are just like calls => fall through.
#undef CONNECT_BLOCK_JS_CASE
402
      case IrOpcode::kCall:
403
      case IrOpcode::kCallWithCallerSavedRegisters:
svenpanne's avatar
svenpanne committed
404
        if (NodeProperties::IsExceptionalCall(node)) {
405 406 407 408
          scheduler_->UpdatePlacement(node, Scheduler::kFixed);
          ConnectCall(node);
        }
        break;
409 410 411 412 413
      default:
        break;
    }
  }

414 415
  BasicBlock* BuildBlockForNode(Node* node) {
    BasicBlock* block = schedule_->block(node);
416
    if (block == nullptr) {
417
      block = schedule_->NewBasicBlock();
418
      TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
419 420
            node->op()->mnemonic());
      FixNode(block, node);
421
    }
422
    return block;
423 424
  }

425
  void BuildBlocksForSuccessors(Node* node) {
426 427 428 429
    size_t const successor_cnt = node->op()->ControlOutputCount();
    Node** successors = zone_->NewArray<Node*>(successor_cnt);
    NodeProperties::CollectControlProjections(node, successors, successor_cnt);
    for (size_t index = 0; index < successor_cnt; ++index) {
430 431
      BuildBlockForNode(successors[index]);
    }
432 433
  }

434
  void CollectSuccessorBlocks(Node* node, BasicBlock** successor_blocks,
435
                              size_t successor_cnt) {
436
    Node** successors = reinterpret_cast<Node**>(successor_blocks);
437 438
    NodeProperties::CollectControlProjections(node, successors, successor_cnt);
    for (size_t index = 0; index < successor_cnt; ++index) {
439 440
      successor_blocks[index] = schedule_->block(successors[index]);
    }
441 442
  }

443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
  BasicBlock* FindPredecessorBlock(Node* node) {
    BasicBlock* predecessor_block = nullptr;
    while (true) {
      predecessor_block = schedule_->block(node);
      if (predecessor_block != nullptr) break;
      node = NodeProperties::GetControlInput(node);
    }
    return predecessor_block;
  }

  void ConnectCall(Node* call) {
    BasicBlock* successor_blocks[2];
    CollectSuccessorBlocks(call, successor_blocks, arraysize(successor_blocks));

    // Consider the exception continuation to be deferred.
    successor_blocks[1]->set_deferred(true);

    Node* call_control = NodeProperties::GetControlInput(call);
    BasicBlock* call_block = FindPredecessorBlock(call_control);
    TraceConnect(call, call_block, successor_blocks[0]);
    TraceConnect(call, call_block, successor_blocks[1]);
    schedule_->AddCall(call_block, call, successor_blocks[0],
                       successor_blocks[1]);
  }

468 469
  void ConnectBranch(Node* branch) {
    BasicBlock* successor_blocks[2];
470 471
    CollectSuccessorBlocks(branch, successor_blocks,
                           arraysize(successor_blocks));
472

473 474 475 476 477 478 479 480 481 482 483 484
    // Consider branch hints.
    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;
    }

485
    if (branch == component_entry_) {
486 487 488 489 490
      TraceConnect(branch, component_start_, successor_blocks[0]);
      TraceConnect(branch, component_start_, successor_blocks[1]);
      schedule_->InsertBranch(component_start_, component_end_, branch,
                              successor_blocks[0], successor_blocks[1]);
    } else {
491 492
      Node* branch_control = NodeProperties::GetControlInput(branch);
      BasicBlock* branch_block = FindPredecessorBlock(branch_control);
493 494 495 496 497
      TraceConnect(branch, branch_block, successor_blocks[0]);
      TraceConnect(branch, branch_block, successor_blocks[1]);
      schedule_->AddBranch(branch_block, branch, successor_blocks[0],
                           successor_blocks[1]);
    }
498 499
  }

500 501 502
  void ConnectSwitch(Node* sw) {
    size_t const successor_count = sw->op()->ControlOutputCount();
    BasicBlock** successor_blocks =
503
        zone_->NewArray<BasicBlock*>(successor_count);
504 505 506 507 508 509 510 511 512
    CollectSuccessorBlocks(sw, successor_blocks, successor_count);

    if (sw == component_entry_) {
      for (size_t index = 0; index < successor_count; ++index) {
        TraceConnect(sw, component_start_, successor_blocks[index]);
      }
      schedule_->InsertSwitch(component_start_, component_end_, sw,
                              successor_blocks, successor_count);
    } else {
513 514
      Node* switch_control = NodeProperties::GetControlInput(sw);
      BasicBlock* switch_block = FindPredecessorBlock(switch_control);
515
      for (size_t index = 0; index < successor_count; ++index) {
516
        TraceConnect(sw, switch_block, successor_blocks[index]);
517
      }
518
      schedule_->AddSwitch(switch_block, sw, successor_blocks, successor_count);
519 520 521
    }
  }

522
  void ConnectMerge(Node* merge) {
523 524 525
    // Don't connect the special merge at the end to its predecessors.
    if (IsFinalMerge(merge)) return;

526
    BasicBlock* block = schedule_->block(merge);
527
    DCHECK_NOT_NULL(block);
528 529
    // For all of the merge's control inputs, add a goto at the end to the
    // merge's basic block.
530
    for (Node* const input : merge->inputs()) {
531
      BasicBlock* predecessor_block = FindPredecessorBlock(input);
532 533
      TraceConnect(merge, predecessor_block, block);
      schedule_->AddGoto(predecessor_block, block);
534 535 536
    }
  }

537 538 539
  void ConnectTailCall(Node* call) {
    Node* call_control = NodeProperties::GetControlInput(call);
    BasicBlock* call_block = FindPredecessorBlock(call_control);
540
    TraceConnect(call, call_block, nullptr);
541 542 543
    schedule_->AddTailCall(call_block, call);
  }

544
  void ConnectReturn(Node* ret) {
545 546
    Node* return_control = NodeProperties::GetControlInput(ret);
    BasicBlock* return_block = FindPredecessorBlock(return_control);
547
    TraceConnect(ret, return_block, nullptr);
548 549 550
    schedule_->AddReturn(return_block, ret);
  }

551 552 553
  void ConnectDeoptimize(Node* deopt) {
    Node* deoptimize_control = NodeProperties::GetControlInput(deopt);
    BasicBlock* deoptimize_block = FindPredecessorBlock(deoptimize_control);
554
    TraceConnect(deopt, deoptimize_block, nullptr);
555 556 557
    schedule_->AddDeoptimize(deoptimize_block, deopt);
  }

558
  void ConnectThrow(Node* thr) {
559 560
    Node* throw_control = NodeProperties::GetControlInput(thr);
    BasicBlock* throw_block = FindPredecessorBlock(throw_control);
561
    TraceConnect(thr, throw_block, nullptr);
562 563 564
    schedule_->AddThrow(throw_block, thr);
  }

565
  void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
566
    DCHECK_NOT_NULL(block);
567
    if (succ == nullptr) {
568
      TRACE("Connect #%d:%s, id:%d -> end\n", node->id(),
569
            node->op()->mnemonic(), block->id().ToInt());
570
    } else {
571
      TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(),
572
            node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt());
573 574
    }
  }
575 576

  bool IsFinalMerge(Node* node) {
577 578
    return (node->opcode() == IrOpcode::kMerge &&
            node == scheduler_->graph_->end()->InputAt(0));
579
  }
580

581 582 583 584 585 586
  bool IsSingleEntrySingleExitRegion(Node* entry, Node* exit) const {
    size_t entry_class = scheduler_->equivalence_->ClassOf(entry);
    size_t exit_class = scheduler_->equivalence_->ClassOf(exit);
    return entry != exit && entry_class == exit_class;
  }

587 588 589 590 591 592
  void ResetDataStructures() {
    control_.clear();
    DCHECK(queue_.empty());
    DCHECK(control_.empty());
  }

593
  Zone* zone_;
594 595
  Scheduler* scheduler_;
  Schedule* schedule_;
596 597 598 599 600 601
  NodeMarker<bool> queued_;      // Mark indicating whether node is queued.
  ZoneQueue<Node*> queue_;       // Queue used for breadth-first traversal.
  NodeVector control_;           // List of encountered control nodes.
  Node* component_entry_;        // Component single-entry node.
  BasicBlock* component_start_;  // Component single-entry block.
  BasicBlock* component_end_;    // Component single-exit block.
602 603 604
};


605
void Scheduler::BuildCFG() {
606
  TRACE("--- CREATING CFG -------------------------------------------\n");
607

608 609 610
  // Instantiate a new control equivalence algorithm for the graph.
  equivalence_ = new (zone_) ControlEquivalence(zone_, graph_);

611 612
  // Build a control-flow graph for the main control-connected component that
  // is being spanned by the graph's start and end nodes.
613 614
  control_flow_builder_ = new (zone_) CFGBuilder(zone_, this);
  control_flow_builder_->Run();
615

616
  // Initialize per-block data.
617 618 619
  // Reserve an extra 10% to avoid resizing vector when fusing floating control.
  scheduled_nodes_.reserve(schedule_->BasicBlockCount() * 1.1);
  scheduled_nodes_.resize(schedule_->BasicBlockCount());
620 621 622
}


623 624 625 626 627 628 629 630 631 632 633 634 635 636 637
// -----------------------------------------------------------------------------
// Phase 2: Compute special RPO and dominator tree.


// Compute the special reverse-post-order block ordering, which is essentially
// a RPO of the graph where loop bodies are contiguous. Properties:
// 1. If block A is a predecessor of B, then A appears before B in the order,
//    unless B is a loop header and A is in the loop headed at B
//    (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 (2).
638
class SpecialRPONumberer : public ZoneObject {
639 640
 public:
  SpecialRPONumberer(Zone* zone, Schedule* schedule)
641 642
      : zone_(zone),
        schedule_(schedule),
643 644
        order_(nullptr),
        beyond_end_(nullptr),
645
        loops_(zone),
646
        backedges_(zone),
647
        stack_(zone),
648 649
        previous_block_count_(0),
        empty_(0, zone) {}
650 651 652

  // Computes the special reverse-post-order for the main control flow graph,
  // that is for the graph spanned between the schedule's start and end blocks.
653
  void ComputeSpecialRPO() {
654
    DCHECK_EQ(0, schedule_->end()->SuccessorCount());
655
    DCHECK(!order_);  // Main order does not exist yet.
656
    ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end());
657 658 659 660 661 662
  }

  // Computes the special reverse-post-order for a partial control flow graph,
  // that is for the graph spanned between the given {entry} and {end} blocks,
  // then updates the existing ordering with this new information.
  void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) {
663
    DCHECK(order_);  // Main order to be updated is present.
664 665 666 667 668 669 670
    ComputeAndInsertSpecialRPO(entry, end);
  }

  // Serialize the previously computed order as a special reverse-post-order
  // numbering for basic blocks into the final schedule.
  void SerializeRPOIntoSchedule() {
    int32_t number = 0;
671
    for (BasicBlock* b = order_; b != nullptr; b = b->rpo_next()) {
672 673
      b->set_rpo_number(number++);
      schedule_->rpo_order()->push_back(b);
674
    }
675
    BeyondEndSentinel()->set_rpo_number(number);
676 677 678 679 680 681 682 683 684 685
  }

  // Print and verify the special reverse-post-order.
  void PrintAndVerifySpecialRPO() {
#if DEBUG
    if (FLAG_trace_turbo_scheduler) PrintRPO();
    VerifySpecialRPO();
#endif
  }

686
  const ZoneVector<BasicBlock*>& GetOutgoingBlocks(BasicBlock* block) {
687 688 689 690 691 692 693
    if (HasLoopNumber(block)) {
      LoopInfo const& loop = loops_[GetLoopNumber(block)];
      if (loop.outgoing) return *loop.outgoing;
    }
    return empty_;
  }

694
 private:
695 696
  typedef std::pair<BasicBlock*, size_t> Backedge;

697
  // Numbering for BasicBlock::rpo_number for this block traversal:
698 699 700 701 702 703 704 705 706 707 708 709 710
  static const int kBlockOnStack = -2;
  static const int kBlockVisited1 = -3;
  static const int kBlockVisited2 = -4;
  static const int kBlockUnvisited1 = -1;
  static const int kBlockUnvisited2 = kBlockVisited1;

  struct SpecialRPOStackFrame {
    BasicBlock* block;
    size_t index;
  };

  struct LoopInfo {
    BasicBlock* header;
711
    ZoneVector<BasicBlock*>* outgoing;
712 713
    BitVector* members;
    LoopInfo* prev;
714 715
    BasicBlock* end;
    BasicBlock* start;
716 717

    void AddOutgoing(Zone* zone, BasicBlock* block) {
718
      if (outgoing == nullptr) {
719 720
        outgoing = new (zone->New(sizeof(ZoneVector<BasicBlock*>)))
            ZoneVector<BasicBlock*>(zone);
721
      }
722
      outgoing->push_back(block);
723 724 725
    }
  };

726 727
  int Push(ZoneVector<SpecialRPOStackFrame>& stack, int depth,
           BasicBlock* child, int unvisited) {
728 729 730 731 732 733 734 735 736
    if (child->rpo_number() == unvisited) {
      stack[depth].block = child;
      stack[depth].index = 0;
      child->set_rpo_number(kBlockOnStack);
      return depth + 1;
    }
    return depth;
  }

737 738 739 740 741
  BasicBlock* PushFront(BasicBlock* head, BasicBlock* block) {
    block->set_rpo_next(head);
    return block;
  }

742
  static int GetLoopNumber(BasicBlock* block) { return block->loop_number(); }
743
  static void SetLoopNumber(BasicBlock* block, int loop_number) {
744
    return block->set_loop_number(loop_number);
745 746
  }
  static bool HasLoopNumber(BasicBlock* block) {
747
    return block->loop_number() >= 0;
748 749
  }

750 751 752 753
  // TODO(mstarzinger): We only need this special sentinel because some tests
  // use the schedule's end block in actual control flow (e.g. with end having
  // successors). Once this has been cleaned up we can use the end block here.
  BasicBlock* BeyondEndSentinel() {
754
    if (beyond_end_ == nullptr) {
755 756 757 758 759 760
      BasicBlock::Id id = BasicBlock::Id::FromInt(-1);
      beyond_end_ = new (schedule_->zone()) BasicBlock(schedule_->zone(), id);
    }
    return beyond_end_;
  }

761 762 763 764
  // Compute special RPO for the control flow graph between {entry} and {end},
  // mutating any existing order so that the result is still valid.
  void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) {
    // RPO should not have been serialized for this schedule yet.
765
    CHECK_EQ(kBlockUnvisited1, schedule_->start()->loop_number());
766 767 768
    CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
    CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));

769
    // Find correct insertion point within existing order.
770 771
    BasicBlock* insertion_point = entry->rpo_next();
    BasicBlock* order = insertion_point;
772

773 774
    // Perform an iterative RPO traversal using an explicit stack,
    // recording backedges that form cycles. O(|B|).
775 776 777 778
    DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount());
    stack_.resize(schedule_->BasicBlockCount() - previous_block_count_);
    previous_block_count_ = schedule_->BasicBlockCount();
    int stack_depth = Push(stack_, 0, entry, kBlockUnvisited1);
779
    int num_loops = static_cast<int>(loops_.size());
780 781 782

    while (stack_depth > 0) {
      int current = stack_depth - 1;
783
      SpecialRPOStackFrame* frame = &stack_[current];
784

785 786
      if (frame->block != end &&
          frame->index < frame->block->SuccessorCount()) {
787 788 789 790 791
        // Process the next successor.
        BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
        if (succ->rpo_number() == kBlockVisited1) continue;
        if (succ->rpo_number() == kBlockOnStack) {
          // The successor is on the stack, so this is a backedge (cycle).
792
          backedges_.push_back(Backedge(frame->block, frame->index - 1));
793
          if (!HasLoopNumber(succ)) {
794
            // Assign a new loop number to the header if it doesn't have one.
795
            SetLoopNumber(succ, num_loops++);
796 797 798
          }
        } else {
          // Push the successor onto the stack.
799
          DCHECK_EQ(kBlockUnvisited1, succ->rpo_number());
800
          stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited1);
801 802 803
        }
      } else {
        // Finished with all successors; pop the stack and add the block.
804
        order = PushFront(order, frame->block);
805 806 807 808 809 810
        frame->block->set_rpo_number(kBlockVisited1);
        stack_depth--;
      }
    }

    // If no loops were encountered, then the order we computed was correct.
811
    if (num_loops > static_cast<int>(loops_.size())) {
812 813
      // Otherwise, compute the loop information from the backedges in order
      // to perform a traversal that groups loop bodies together.
814
      ComputeLoopInfo(stack_, num_loops, &backedges_);
815 816

      // Initialize the "loop stack". Note the entry could be a loop header.
817
      LoopInfo* loop =
818
          HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : nullptr;
819
      order = insertion_point;
820 821 822 823 824

      // Perform an iterative post-order traversal, visiting loop bodies before
      // edges that lead out of loops. Visits each block once, but linking loop
      // sections together is linear in the loop size, so overall is
      // O(|B| + max(loop_depth) * max(|loop|))
825
      stack_depth = Push(stack_, 0, entry, kBlockUnvisited2);
826
      while (stack_depth > 0) {
827
        SpecialRPOStackFrame* frame = &stack_[stack_depth - 1];
828
        BasicBlock* block = frame->block;
829
        BasicBlock* succ = nullptr;
830

831
        if (block != end && frame->index < block->SuccessorCount()) {
832 833
          // Process the next normal successor.
          succ = block->SuccessorAt(frame->index++);
834
        } else if (HasLoopNumber(block)) {
835 836 837 838
          // Process additional outgoing edges from the loop header.
          if (block->rpo_number() == kBlockOnStack) {
            // Finish the loop body the first time the header is left on the
            // stack.
839
            DCHECK(loop != nullptr && loop->header == block);
840
            loop->start = PushFront(order, block);
841
            order = loop->end;
842 843 844 845 846 847 848 849 850
            block->set_rpo_number(kBlockVisited2);
            // Pop the loop stack and continue visiting outgoing edges within
            // the context of the outer loop, if any.
            loop = loop->prev;
            // We leave the loop header on the stack; the rest of this iteration
            // and later iterations will go through its outgoing edges list.
          }

          // Use the next outgoing edge if there are any.
851
          size_t outgoing_index = frame->index - block->SuccessorCount();
852
          LoopInfo* info = &loops_[GetLoopNumber(block)];
853
          DCHECK(loop != info);
854
          if (block != entry && info->outgoing != nullptr &&
855
              outgoing_index < info->outgoing->size()) {
856 857 858 859 860
            succ = info->outgoing->at(outgoing_index);
            frame->index++;
          }
        }

861
        if (succ != nullptr) {
862 863 864
          // Process the next successor.
          if (succ->rpo_number() == kBlockOnStack) continue;
          if (succ->rpo_number() == kBlockVisited2) continue;
865
          DCHECK_EQ(kBlockUnvisited2, succ->rpo_number());
866
          if (loop != nullptr && !loop->members->Contains(succ->id().ToInt())) {
867 868 869 870 871
            // The successor is not in the current loop or any nested loop.
            // Add it to the outgoing edges of this loop and visit it later.
            loop->AddOutgoing(zone_, succ);
          } else {
            // Push the successor onto the stack.
872
            stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2);
873
            if (HasLoopNumber(succ)) {
874
              // Push the inner loop onto the loop stack.
875 876
              DCHECK(GetLoopNumber(succ) < num_loops);
              LoopInfo* next = &loops_[GetLoopNumber(succ)];
877
              next->end = order;
878 879 880 881 882 883
              next->prev = loop;
              loop = next;
            }
          }
        } else {
          // Finished with all successors of the current block.
884
          if (HasLoopNumber(block)) {
885
            // If we are going to pop a loop header, then add its entire body.
886
            LoopInfo* info = &loops_[GetLoopNumber(block)];
887 888 889
            for (BasicBlock* b = info->start; true; b = b->rpo_next()) {
              if (b->rpo_next() == info->end) {
                b->set_rpo_next(order);
890
                info->end = order;
891 892 893
                break;
              }
            }
894
            order = info->start;
895 896
          } else {
            // Pop a single node off the stack and add it to the order.
897
            order = PushFront(order, block);
898 899 900 901 902 903 904
            block->set_rpo_number(kBlockVisited2);
          }
          stack_depth--;
        }
      }
    }

905
    // Publish new order the first time.
906
    if (order_ == nullptr) order_ = order;
907

908
    // Compute the correct loop headers and set the correct loop ends.
909
    LoopInfo* current_loop = nullptr;
910 911 912
    BasicBlock* current_header = entry->loop_header();
    int32_t loop_depth = entry->loop_depth();
    if (entry->IsLoopHeader()) --loop_depth;  // Entry might be a loop header.
913 914
    for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) {
      BasicBlock* current = b;
915

916 917 918
      // Reset BasicBlock::rpo_number again.
      current->set_rpo_number(kBlockUnvisited1);

919
      // Finish the previous loop(s) if we just exited them.
920 921
      while (current_header != nullptr &&
             current == current_header->loop_end()) {
922
        DCHECK(current_header->IsLoopHeader());
923
        DCHECK_NOT_NULL(current_loop);
924
        current_loop = current_loop->prev;
925 926
        current_header =
            current_loop == nullptr ? nullptr : current_loop->header;
927 928
        --loop_depth;
      }
929
      current->set_loop_header(current_header);
930 931

      // Push a new loop onto the stack if this loop is a loop header.
932
      if (HasLoopNumber(current)) {
933
        ++loop_depth;
934
        current_loop = &loops_[GetLoopNumber(current)];
935
        BasicBlock* end = current_loop->end;
936
        current->set_loop_end(end == nullptr ? BeyondEndSentinel() : end);
937
        current_header = current_loop->header;
938
        TRACE("id:%d is a loop header, increment loop depth to %d\n",
939 940
              current->id().ToInt(), loop_depth);
      }
941

942
      current->set_loop_depth(loop_depth);
943

944
      if (current->loop_header() == nullptr) {
945
        TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(),
946 947
              current->loop_depth());
      } else {
948
        TRACE("id:%d has loop header id:%d, (depth == %d)\n",
949 950
              current->id().ToInt(), current->loop_header()->id().ToInt(),
              current->loop_depth());
951 952 953 954 955
      }
    }
  }

  // Computes loop membership from the backedges of the control flow graph.
956
  void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue,
957
                       size_t num_loops, ZoneVector<Backedge>* backedges) {
958 959
    // Extend existing loop membership vectors.
    for (LoopInfo& loop : loops_) {
960 961
      loop.members->Resize(static_cast<int>(schedule_->BasicBlockCount()),
                           zone_);
962 963 964
    }

    // Extend loop information vector.
965
    loops_.resize(num_loops, LoopInfo());
966 967 968

    // Compute loop membership starting from backedges.
    // O(max(loop_depth) * max(|loop|)
969
    for (size_t i = 0; i < backedges->size(); i++) {
970 971
      BasicBlock* member = backedges->at(i).first;
      BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
972
      size_t loop_num = GetLoopNumber(header);
973
      if (loops_[loop_num].header == nullptr) {
974 975 976
        loops_[loop_num].header = header;
        loops_[loop_num].members = new (zone_)
            BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_);
977 978 979 980 981 982
      }

      int queue_length = 0;
      if (member != header) {
        // As long as the header doesn't have a backedge to itself,
        // Push the member onto the queue and process its predecessors.
983 984
        if (!loops_[loop_num].members->Contains(member->id().ToInt())) {
          loops_[loop_num].members->Add(member->id().ToInt());
985 986 987 988 989 990 991 992 993 994 995
        }
        queue[queue_length++].block = member;
      }

      // Propagate loop membership backwards. All predecessors of M up to the
      // loop header H are members of the loop too. O(|blocks between M and H|).
      while (queue_length > 0) {
        BasicBlock* block = queue[--queue_length].block;
        for (size_t i = 0; i < block->PredecessorCount(); i++) {
          BasicBlock* pred = block->PredecessorAt(i);
          if (pred != header) {
996 997
            if (!loops_[loop_num].members->Contains(pred->id().ToInt())) {
              loops_[loop_num].members->Add(pred->id().ToInt());
998 999 1000 1001 1002 1003 1004 1005 1006
              queue[queue_length++].block = pred;
            }
          }
        }
      }
    }
  }

#if DEBUG
1007
  void PrintRPO() {
1008
    OFStream os(stdout);
1009 1010 1011 1012
    os << "RPO with " << loops_.size() << " loops";
    if (loops_.size() > 0) {
      os << " (";
      for (size_t i = 0; i < loops_.size(); i++) {
1013
        if (i > 0) os << " ";
1014
        os << "id:" << loops_[i].header->id();
1015
      }
1016
      os << ")";
1017
    }
1018
    os << ":\n";
1019

1020 1021
    for (BasicBlock* block = order_; block != nullptr;
         block = block->rpo_next()) {
1022
      os << std::setw(5) << "B" << block->rpo_number() << ":";
1023 1024 1025
      for (size_t i = 0; i < loops_.size(); i++) {
        bool range = loops_[i].header->LoopContains(block);
        bool membership = loops_[i].header != block && range;
1026 1027 1028
        os << (membership ? " |" : "  ");
        os << (range ? "x" : " ");
      }
1029
      os << "  id:" << block->id() << ": ";
1030
      if (block->loop_end() != nullptr) {
1031
        os << " range: [B" << block->rpo_number() << ", B"
1032
           << block->loop_end()->rpo_number() << ")";
1033
      }
1034
      if (block->loop_header() != nullptr) {
1035
        os << " header: id:" << block->loop_header()->id();
1036 1037 1038 1039
      }
      if (block->loop_depth() > 0) {
        os << " depth: " << block->loop_depth();
      }
1040 1041 1042 1043
      os << "\n";
    }
  }

1044 1045
  void VerifySpecialRPO() {
    BasicBlockVector* order = schedule_->rpo_order();
1046 1047
    DCHECK_LT(0, order->size());
    DCHECK_EQ(0, (*order)[0]->id().ToInt());  // entry should be first.
1048

1049 1050
    for (size_t i = 0; i < loops_.size(); i++) {
      LoopInfo* loop = &loops_[i];
1051
      BasicBlock* header = loop->header;
1052
      BasicBlock* end = header->loop_end();
1053

1054
      DCHECK_NOT_NULL(header);
1055 1056
      DCHECK_LE(0, header->rpo_number());
      DCHECK_LT(header->rpo_number(), order->size());
1057
      DCHECK_NOT_NULL(end);
1058 1059 1060
      DCHECK_LE(end->rpo_number(), order->size());
      DCHECK_GT(end->rpo_number(), header->rpo_number());
      DCHECK_NE(header->loop_header(), header);
1061 1062 1063

      // Verify the start ... end list relationship.
      int links = 0;
1064 1065
      BasicBlock* block = loop->start;
      DCHECK_EQ(header, block);
1066 1067
      bool end_found;
      while (true) {
1068
        if (block == nullptr || block == loop->end) {
1069
          end_found = (loop->end == block);
1070 1071 1072
          break;
        }
        // The list should be in same order as the final result.
1073
        DCHECK(block->rpo_number() == links + header->rpo_number());
1074
        links++;
1075
        block = block->rpo_next();
1076
        DCHECK_LT(links, static_cast<int>(2 * order->size()));  // cycle?
1077
      }
1078 1079
      DCHECK_LT(0, links);
      DCHECK_EQ(links, end->rpo_number() - header->rpo_number());
1080 1081
      DCHECK(end_found);

1082 1083
      // Check loop depth of the header.
      int loop_depth = 0;
1084
      for (LoopInfo* outer = loop; outer != nullptr; outer = outer->prev) {
1085 1086 1087 1088
        loop_depth++;
      }
      DCHECK_EQ(loop_depth, header->loop_depth());

1089
      // Check the contiguousness of loops.
1090
      int count = 0;
1091 1092
      for (int j = 0; j < static_cast<int>(order->size()); j++) {
        BasicBlock* block = order->at(j);
1093
        DCHECK_EQ(block->rpo_number(), j);
1094
        if (j < header->rpo_number() || j >= end->rpo_number()) {
1095
          DCHECK(!header->LoopContains(block));
1096
        } else {
1097
          DCHECK(header->LoopContains(block));
1098
          DCHECK_GE(block->loop_depth(), loop_depth);
1099 1100 1101
          count++;
        }
      }
1102
      DCHECK_EQ(links, count);
1103 1104 1105 1106 1107 1108
    }
  }
#endif  // DEBUG

  Zone* zone_;
  Schedule* schedule_;
1109
  BasicBlock* order_;
1110
  BasicBlock* beyond_end_;
1111
  ZoneVector<LoopInfo> loops_;
1112
  ZoneVector<Backedge> backedges_;
1113 1114
  ZoneVector<SpecialRPOStackFrame> stack_;
  size_t previous_block_count_;
1115
  ZoneVector<BasicBlock*> const empty_;
1116 1117 1118
};


1119
BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
1120 1121
  SpecialRPONumberer numberer(zone, schedule);
  numberer.ComputeSpecialRPO();
1122 1123
  numberer.SerializeRPOIntoSchedule();
  numberer.PrintAndVerifySpecialRPO();
1124 1125 1126 1127 1128
  return schedule->rpo_order();
}


void Scheduler::ComputeSpecialRPONumbering() {
1129
  TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n");
1130

1131 1132 1133
  // Compute the special reverse-post-order for basic blocks.
  special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_);
  special_rpo_->ComputeSpecialRPO();
1134 1135 1136
}


1137
void Scheduler::PropagateImmediateDominators(BasicBlock* block) {
1138
  for (/*nop*/; block != nullptr; block = block->rpo_next()) {
1139 1140
    auto pred = block->predecessors().begin();
    auto end = block->predecessors().end();
1141 1142
    DCHECK(pred != end);  // All blocks except start have predecessors.
    BasicBlock* dominator = *pred;
1143
    bool deferred = dominator->deferred();
1144 1145 1146 1147 1148 1149
    // 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;
1150
      dominator = BasicBlock::GetCommonDominator(dominator, *pred);
1151
      deferred = deferred & (*pred)->deferred();
1152
    }
1153 1154
    block->set_dominator(dominator);
    block->set_dominator_depth(dominator->dominator_depth() + 1);
1155
    block->set_deferred(deferred | block->deferred());
1156
    TRACE("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(),
1157
          dominator->id().ToInt(), block->dominator_depth());
1158 1159 1160 1161
  }
}


1162
void Scheduler::GenerateImmediateDominatorTree() {
1163
  TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
1164 1165 1166 1167 1168 1169 1170 1171 1172

  // 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());
}


1173
// -----------------------------------------------------------------------------
1174
// Phase 3: Prepare use counts for nodes.
1175 1176


1177
class PrepareUsesVisitor {
1178 1179 1180 1181
 public:
  explicit PrepareUsesVisitor(Scheduler* scheduler)
      : scheduler_(scheduler), schedule_(scheduler->schedule_) {}

1182
  void Pre(Node* node) {
1183
    if (scheduler_->InitializePlacement(node) == Scheduler::kFixed) {
1184 1185 1186 1187
      // Fixed nodes are always roots for schedule late.
      scheduler_->schedule_root_nodes_.push_back(node);
      if (!schedule_->IsScheduled(node)) {
        // Make sure root nodes are scheduled in their respective blocks.
1188
        TRACE("Scheduling fixed position node #%d:%s\n", node->id(),
1189 1190 1191 1192 1193 1194
              node->op()->mnemonic());
        IrOpcode::Value opcode = node->opcode();
        BasicBlock* block =
            opcode == IrOpcode::kParameter
                ? schedule_->start()
                : schedule_->block(NodeProperties::GetControlInput(node));
1195
        DCHECK_NOT_NULL(block);
1196 1197 1198 1199 1200 1201 1202
        schedule_->AddNode(block, node);
      }
    }
  }

  void PostEdge(Node* from, int index, Node* to) {
    // If the edge is from an unscheduled node, then tally it in the use count
1203
    // for all of its inputs. The same criterion will be used in ScheduleLate
1204
    // for decrementing use counts.
1205
    if (!schedule_->IsScheduled(from)) {
1206
      DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
1207
      scheduler_->IncrementUnscheduledUseCount(to, index, from);
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217
    }
  }

 private:
  Scheduler* scheduler_;
  Schedule* schedule_;
};


void Scheduler::PrepareUses() {
1218
  TRACE("--- PREPARE USES -------------------------------------------\n");
1219

1220
  // Count the uses of every node, which is used to ensure that all of a
1221 1222
  // node's uses are scheduled before the node itself.
  PrepareUsesVisitor prepare_uses(this);
1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242

  // TODO(turbofan): simplify the careful pre/post ordering here.
  BoolVector visited(graph_->NodeCount(), false, zone_);
  ZoneStack<Node::InputEdges::iterator> stack(zone_);
  Node* node = graph_->end();
  prepare_uses.Pre(node);
  visited[node->id()] = true;
  stack.push(node->input_edges().begin());
  while (!stack.empty()) {
    Edge edge = *stack.top();
    Node* node = edge.to();
    if (visited[node->id()]) {
      prepare_uses.PostEdge(edge.from(), edge.index(), edge.to());
      if (++stack.top() == edge.from()->input_edges().end()) stack.pop();
    } else {
      prepare_uses.Pre(node);
      visited[node->id()] = true;
      if (node->InputCount() > 0) stack.push(node->input_edges().begin());
    }
  }
1243 1244 1245 1246
}


// -----------------------------------------------------------------------------
1247
// Phase 4: Schedule nodes early.
1248 1249


1250
class ScheduleEarlyNodeVisitor {
1251
 public:
1252 1253
  ScheduleEarlyNodeVisitor(Zone* zone, Scheduler* scheduler)
      : scheduler_(scheduler), schedule_(scheduler->schedule_), queue_(zone) {}
1254

1255 1256
  // Run the schedule early algorithm on a set of fixed root nodes.
  void Run(NodeVector* roots) {
1257 1258
    for (Node* const root : *roots) {
      queue_.push(root);
1259 1260 1261
      while (!queue_.empty()) {
        VisitNode(queue_.front());
        queue_.pop();
1262 1263 1264 1265
      }
    }
  }

1266 1267 1268 1269
 private:
  // Visits one node from the queue and propagates its current schedule early
  // position to all uses. This in turn might push more nodes onto the queue.
  void VisitNode(Node* node) {
1270
    Scheduler::SchedulerData* data = scheduler_->GetData(node);
1271 1272 1273 1274

    // Fixed nodes already know their schedule early position.
    if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
      data->minimum_block_ = schedule_->block(node);
1275
      TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1276 1277 1278
            node->id(), node->op()->mnemonic(),
            data->minimum_block_->id().ToInt(),
            data->minimum_block_->dominator_depth());
1279 1280 1281 1282 1283 1284
    }

    // No need to propagate unconstrained schedule early positions.
    if (data->minimum_block_ == schedule_->start()) return;

    // Propagate schedule early position.
1285
    DCHECK_NOT_NULL(data->minimum_block_);
1286
    for (auto use : node->uses()) {
1287 1288 1289
      if (scheduler_->IsLive(use)) {
        PropagateMinimumPositionToNode(data->minimum_block_, use);
      }
1290 1291 1292
    }
  }

1293 1294 1295 1296
  // Propagates {block} as another minimum position into the given {node}. This
  // has the net effect of computing the minimum dominator block of {node} that
  // still post-dominates all inputs to {node} when the queue is processed.
  void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) {
1297 1298 1299 1300 1301
    Scheduler::SchedulerData* data = scheduler_->GetData(node);

    // No need to propagate to fixed node, it's guaranteed to be a root.
    if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;

1302 1303 1304
    // Coupled nodes influence schedule early position of their control.
    if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
      Node* control = NodeProperties::GetControlInput(node);
1305
      PropagateMinimumPositionToNode(block, control);
1306 1307
    }

1308 1309 1310 1311 1312
    // Propagate new position if it is deeper down the dominator tree than the
    // current. Note that all inputs need to have minimum block position inside
    // the dominator chain of {node}'s minimum block position.
    DCHECK(InsideSameDominatorChain(block, data->minimum_block_));
    if (block->dominator_depth() > data->minimum_block_->dominator_depth()) {
1313 1314
      data->minimum_block_ = block;
      queue_.push(node);
1315
      TRACE("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1316 1317 1318
            node->id(), node->op()->mnemonic(),
            data->minimum_block_->id().ToInt(),
            data->minimum_block_->dominator_depth());
1319 1320
    }
  }
1321

1322 1323
#if DEBUG
  bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) {
1324
    BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2);
1325 1326 1327 1328
    return dominator == b1 || dominator == b2;
  }
#endif

1329 1330
  Scheduler* scheduler_;
  Schedule* schedule_;
1331
  ZoneQueue<Node*> queue_;
1332 1333 1334 1335
};


void Scheduler::ScheduleEarly() {
1336
  TRACE("--- SCHEDULE EARLY -----------------------------------------\n");
1337
  if (FLAG_trace_turbo_scheduler) {
1338
    TRACE("roots: ");
1339
    for (Node* node : schedule_root_nodes_) {
1340
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1341
    }
1342
    TRACE("\n");
1343
  }
1344

1345
  // Compute the minimum block for each node thereby determining the earliest
1346
  // position each node could be placed within a valid schedule.
1347 1348
  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
  schedule_early_visitor.Run(&schedule_root_nodes_);
1349 1350 1351
}


1352
// -----------------------------------------------------------------------------
1353
// Phase 5: Schedule nodes late.
1354 1355


1356
class ScheduleLateNodeVisitor {
1357
 public:
1358
  ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
1359 1360
      : zone_(zone),
        scheduler_(scheduler),
1361 1362 1363
        schedule_(scheduler_->schedule_),
        marked_(scheduler->zone_),
        marking_queue_(scheduler->zone_) {}
1364

1365 1366
  // Run the schedule late algorithm on a set of fixed root nodes.
  void Run(NodeVector* roots) {
1367 1368
    for (Node* const root : *roots) {
      ProcessQueue(root);
1369 1370 1371 1372 1373
    }
  }

 private:
  void ProcessQueue(Node* root) {
1374
    ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
danno's avatar
danno committed
1375
    for (Node* node : root->inputs()) {
1376 1377 1378 1379 1380 1381 1382 1383 1384
      // Don't schedule coupled nodes on their own.
      if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
        node = NodeProperties::GetControlInput(node);
      }

      // Test schedulability condition by looking at unscheduled use count.
      if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;

      queue->push(node);
1385 1386
      do {
        Node* const node = queue->front();
1387
        queue->pop();
1388 1389
        VisitNode(node);
      } while (!queue->empty());
1390
    }
1391 1392 1393 1394 1395 1396
  }

  // Visits one node from the queue of schedulable nodes and determines its
  // schedule late position. Also hoists nodes out of loops to find a more
  // optimal scheduling position.
  void VisitNode(Node* node) {
1397
    DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1398 1399 1400

    // Don't schedule nodes that are already scheduled.
    if (schedule_->IsScheduled(node)) return;
1401
    DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));
1402 1403 1404

    // Determine the dominating block for all of the uses of this node. It is
    // the latest block that this node can be scheduled in.
1405
    TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
1406 1407 1408
    BasicBlock* block = GetCommonDominatorOfUses(node);
    DCHECK_NOT_NULL(block);

1409 1410
    // The schedule early block dominates the schedule late block.
    BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
1411
    DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
1412
    TRACE(
1413 1414 1415
        "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n",
        node->id(), node->op()->mnemonic(), block->id().ToInt(),
        block->loop_depth(), min_block->id().ToInt());
1416 1417

    // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
1418
    // into enclosing loop pre-headers until they would precede their schedule
1419
    // early position.
1420
    BasicBlock* hoist_block = GetHoistBlock(block);
1421 1422 1423
    if (hoist_block &&
        hoist_block->dominator_depth() >= min_block->dominator_depth()) {
      do {
1424
        TRACE("  hoisting #%d:%s to block id:%d\n", node->id(),
1425 1426 1427
              node->op()->mnemonic(), hoist_block->id().ToInt());
        DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
        block = hoist_block;
1428
        hoist_block = GetHoistBlock(hoist_block);
1429 1430 1431 1432 1433
      } while (hoist_block &&
               hoist_block->dominator_depth() >= min_block->dominator_depth());
    } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
      // Split the {node} if beneficial and return the new {block} for it.
      block = SplitNode(block, node);
1434 1435
    }

1436
    // Schedule the node or a floating control structure.
1437
    if (IrOpcode::IsMergeOpcode(node->opcode())) {
1438
      ScheduleFloatingControl(block, node);
1439 1440
    } else if (node->opcode() == IrOpcode::kFinishRegion) {
      ScheduleRegion(block, node);
1441 1442 1443
    } else {
      ScheduleNode(block, node);
    }
1444 1445
  }

1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459
  // Mark {block} and push its non-marked predecessor on the marking queue.
  void MarkBlock(BasicBlock* block) {
    DCHECK_LT(block->id().ToSize(), marked_.size());
    marked_[block->id().ToSize()] = true;
    for (BasicBlock* pred_block : block->predecessors()) {
      DCHECK_LT(pred_block->id().ToSize(), marked_.size());
      if (marked_[pred_block->id().ToSize()]) continue;
      marking_queue_.push_back(pred_block);
    }
  }

  BasicBlock* SplitNode(BasicBlock* block, Node* node) {
    // For now, we limit splitting to pure nodes.
    if (!node->op()->HasProperty(Operator::kPure)) return block;
1460 1461
    // TODO(titzer): fix the special case of splitting of projections.
    if (node->opcode() == IrOpcode::kProjection) return block;
1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474

    // The {block} is common dominator of all uses of {node}, so we cannot
    // split anything unless the {block} has at least two successors.
    DCHECK_EQ(block, GetCommonDominatorOfUses(node));
    if (block->SuccessorCount() < 2) return block;

    // Clear marking bits.
    DCHECK(marking_queue_.empty());
    std::fill(marked_.begin(), marked_.end(), false);
    marked_.resize(schedule_->BasicBlockCount() + 1, false);

    // Check if the {node} has uses in {block}.
    for (Edge edge : node->use_edges()) {
1475
      if (!scheduler_->IsLive(edge.from())) continue;
1476 1477 1478
      BasicBlock* use_block = GetBlockForUse(edge);
      if (use_block == nullptr || marked_[use_block->id().ToSize()]) continue;
      if (use_block == block) {
1479
        TRACE("  not splitting #%d:%s, it is used in id:%d\n", node->id(),
1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506
              node->op()->mnemonic(), block->id().ToInt());
        marking_queue_.clear();
        return block;
      }
      MarkBlock(use_block);
    }

    // Compute transitive marking closure; a block is marked if all its
    // successors are marked.
    do {
      BasicBlock* top_block = marking_queue_.front();
      marking_queue_.pop_front();
      if (marked_[top_block->id().ToSize()]) continue;
      bool marked = true;
      for (BasicBlock* successor : top_block->successors()) {
        if (!marked_[successor->id().ToSize()]) {
          marked = false;
          break;
        }
      }
      if (marked) MarkBlock(top_block);
    } while (!marking_queue_.empty());

    // If the (common dominator) {block} is marked, we know that all paths from
    // {block} to the end contain at least one use of {node}, and hence there's
    // no point in splitting the {node} in this case.
    if (marked_[block->id().ToSize()]) {
1507
      TRACE("  not splitting #%d:%s, its common dominator id:%d is perfect\n",
1508 1509 1510 1511 1512 1513 1514 1515 1516 1517
            node->id(), node->op()->mnemonic(), block->id().ToInt());
      return block;
    }

    // Split {node} for uses according to the previously computed marking
    // closure. Every marking partition has a unique dominator, which get's a
    // copy of the {node} with the exception of the first partition, which get's
    // the {node} itself.
    ZoneMap<BasicBlock*, Node*> dominators(scheduler_->zone_);
    for (Edge edge : node->use_edges()) {
1518
      if (!scheduler_->IsLive(edge.from())) continue;
1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529
      BasicBlock* use_block = GetBlockForUse(edge);
      if (use_block == nullptr) continue;
      while (marked_[use_block->dominator()->id().ToSize()]) {
        use_block = use_block->dominator();
      }
      auto& use_node = dominators[use_block];
      if (use_node == nullptr) {
        if (dominators.size() == 1u) {
          // Place the {node} at {use_block}.
          block = use_block;
          use_node = node;
1530
          TRACE("  pushing #%d:%s down to id:%d\n", node->id(),
1531 1532 1533 1534
                node->op()->mnemonic(), block->id().ToInt());
        } else {
          // Place a copy of {node} at {use_block}.
          use_node = CloneNode(node);
1535
          TRACE("  cloning #%d:%s for id:%d\n", use_node->id(),
1536 1537 1538 1539 1540 1541 1542 1543 1544
                use_node->op()->mnemonic(), use_block->id().ToInt());
          scheduler_->schedule_queue_.push(use_node);
        }
      }
      edge.UpdateTo(use_node);
    }
    return block;
  }

1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559
  BasicBlock* GetHoistBlock(BasicBlock* block) {
    if (block->IsLoopHeader()) return block->dominator();
    // We have to check to make sure that the {block} dominates all
    // of the outgoing blocks.  If it doesn't, then there is a path
    // out of the loop which does not execute this {block}, so we
    // can't hoist operations from this {block} out of the loop, as
    // that would introduce additional computations.
    if (BasicBlock* header_block = block->loop_header()) {
      for (BasicBlock* outgoing_block :
           scheduler_->special_rpo_->GetOutgoingBlocks(header_block)) {
        if (BasicBlock::GetCommonDominator(block, outgoing_block) != block) {
          return nullptr;
        }
      }
      return header_block->dominator();
1560
    }
1561
    return nullptr;
1562 1563
  }

1564
  BasicBlock* GetCommonDominatorOfUses(Node* node) {
1565
    BasicBlock* block = nullptr;
danno's avatar
danno committed
1566
    for (Edge edge : node->use_edges()) {
1567
      if (!scheduler_->IsLive(edge.from())) continue;
danno's avatar
danno committed
1568
      BasicBlock* use_block = GetBlockForUse(edge);
1569 1570 1571 1572 1573
      block = block == nullptr
                  ? use_block
                  : use_block == nullptr
                        ? block
                        : BasicBlock::GetCommonDominator(block, use_block);
1574 1575 1576 1577
    }
    return block;
  }

1578 1579 1580 1581
  BasicBlock* FindPredecessorBlock(Node* node) {
    return scheduler_->control_flow_builder_->FindPredecessorBlock(node);
  }

danno's avatar
danno committed
1582
  BasicBlock* GetBlockForUse(Edge edge) {
1583 1584
    // TODO(titzer): ignore uses from dead nodes (not visited in PrepareUses()).
    // Dead uses only occur if the graph is not trimmed before scheduling.
1585
    Node* use = edge.from();
1586
    if (IrOpcode::IsPhiOpcode(use->opcode())) {
1587 1588 1589
      // If the use is from a coupled (i.e. floating) phi, compute the common
      // dominator of its uses. This will not recurse more than one level.
      if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) {
1590
        TRACE("  inspecting uses of coupled #%d:%s\n", use->id(),
1591
              use->op()->mnemonic());
1592 1593
        // TODO(titzer): reenable once above TODO is addressed.
        //        DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use));
1594 1595
        return GetCommonDominatorOfUses(use);
      }
1596 1597
      // If the use is from a fixed (i.e. non-floating) phi, we use the
      // predecessor block of the corresponding control input to the merge.
1598
      if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1599
        TRACE("  input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(),
1600 1601
              use->op()->mnemonic());
        Node* merge = NodeProperties::GetControlInput(use, 0);
1602 1603 1604 1605 1606 1607 1608 1609
        DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
        Node* input = NodeProperties::GetControlInput(merge, edge.index());
        return FindPredecessorBlock(input);
      }
    } else if (IrOpcode::IsMergeOpcode(use->opcode())) {
      // If the use is from a fixed (i.e. non-floating) merge, we use the
      // predecessor block of the current input to the merge.
      if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1610
        TRACE("  input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(),
1611 1612
              use->op()->mnemonic());
        return FindPredecessorBlock(edge.to());
1613
      }
1614 1615
    }
    BasicBlock* result = schedule_->block(use);
1616
    if (result == nullptr) return nullptr;
1617
    TRACE("  must dominate use #%d:%s in id:%d\n", use->id(),
1618
          use->op()->mnemonic(), result->id().ToInt());
1619 1620 1621
    return result;
  }

1622 1623 1624 1625
  void ScheduleFloatingControl(BasicBlock* block, Node* node) {
    scheduler_->FuseFloatingControl(block, node);
  }

1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653
  void ScheduleRegion(BasicBlock* block, Node* region_end) {
    // We only allow regions of instructions connected into a linear
    // effect chain. The only value allowed to be produced by a node
    // in the chain must be the value consumed by the FinishRegion node.

    // We schedule back to front; we first schedule FinishRegion.
    CHECK_EQ(IrOpcode::kFinishRegion, region_end->opcode());
    ScheduleNode(block, region_end);

    // Schedule the chain.
    Node* node = NodeProperties::GetEffectInput(region_end);
    while (node->opcode() != IrOpcode::kBeginRegion) {
      DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
      DCHECK_EQ(1, node->op()->EffectInputCount());
      DCHECK_EQ(1, node->op()->EffectOutputCount());
      DCHECK_EQ(0, node->op()->ControlOutputCount());
      // The value output (if there is any) must be consumed
      // by the EndRegion node.
      DCHECK(node->op()->ValueOutputCount() == 0 ||
             node == region_end->InputAt(0));
      ScheduleNode(block, node);
      node = NodeProperties::GetEffectInput(node);
    }
    // Schedule the BeginRegion node.
    DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
    ScheduleNode(block, node);
  }

1654 1655
  void ScheduleNode(BasicBlock* block, Node* node) {
    schedule_->PlanNode(block, node);
1656 1657 1658 1659 1660 1661
    size_t block_id = block->id().ToSize();
    if (!scheduler_->scheduled_nodes_[block_id]) {
      scheduler_->scheduled_nodes_[block_id] =
          new (zone_->New(sizeof(NodeVector))) NodeVector(zone_);
    }
    scheduler_->scheduled_nodes_[block_id]->push_back(node);
1662
    scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
1663 1664
  }

1665 1666 1667 1668 1669 1670
  Node* CloneNode(Node* node) {
    int const input_count = node->InputCount();
    for (int index = 0; index < input_count; ++index) {
      Node* const input = node->InputAt(index);
      scheduler_->IncrementUnscheduledUseCount(input, index, node);
    }
1671
    Node* const copy = scheduler_->graph_->CloneNode(node);
1672 1673
    TRACE(("clone #%d:%s -> #%d\n"), node->id(), node->op()->mnemonic(),
          copy->id());
1674 1675 1676 1677 1678 1679
    scheduler_->node_data_.resize(copy->id() + 1,
                                  scheduler_->DefaultSchedulerData());
    scheduler_->node_data_[copy->id()] = scheduler_->node_data_[node->id()];
    return copy;
  }

1680
  Zone* zone_;
1681 1682
  Scheduler* scheduler_;
  Schedule* schedule_;
1683 1684
  BoolVector marked_;
  ZoneDeque<BasicBlock*> marking_queue_;
1685 1686 1687 1688
};


void Scheduler::ScheduleLate() {
1689
  TRACE("--- SCHEDULE LATE ------------------------------------------\n");
1690
  if (FLAG_trace_turbo_scheduler) {
1691
    TRACE("roots: ");
1692
    for (Node* node : schedule_root_nodes_) {
1693
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1694
    }
1695
    TRACE("\n");
1696
  }
1697 1698

  // Schedule: Places nodes in dominator block of all their uses.
1699 1700
  ScheduleLateNodeVisitor schedule_late_visitor(zone_, this);
  schedule_late_visitor.Run(&schedule_root_nodes_);
1701 1702 1703 1704 1705 1706 1707 1708
}


// -----------------------------------------------------------------------------
// Phase 6: Seal the final schedule.


void Scheduler::SealFinalSchedule() {
1709
  TRACE("--- SEAL FINAL SCHEDULE ------------------------------------\n");
1710 1711 1712 1713

  // Serialize the assembly order and reverse-post-order numbering.
  special_rpo_->SerializeRPOIntoSchedule();
  special_rpo_->PrintAndVerifySpecialRPO();
1714 1715 1716

  // Add collected nodes for basic blocks to their blocks in the right order.
  int block_num = 0;
1717
  for (NodeVector* nodes : scheduled_nodes_) {
1718 1719
    BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++);
    BasicBlock* block = schedule_->GetBlockById(id);
1720 1721 1722 1723
    if (nodes) {
      for (Node* node : base::Reversed(*nodes)) {
        schedule_->AddNode(block, node);
      }
1724 1725 1726 1727 1728
    }
  }
}


1729 1730 1731
// -----------------------------------------------------------------------------


1732
void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
1733
  TRACE("--- FUSE FLOATING CONTROL ----------------------------------\n");
1734 1735 1736
  if (FLAG_trace_turbo_scheduler) {
    OFStream os(stdout);
    os << "Schedule before control flow fusion:\n" << *schedule_;
1737 1738
  }

1739
  // Iterate on phase 1: Build control-flow graph.
1740
  control_flow_builder_->Run(block, node);
1741 1742

  // Iterate on phase 2: Compute special RPO and dominator tree.
1743
  special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
1744
  // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
1745
  for (BasicBlock* b = block->rpo_next(); b != nullptr; b = b->rpo_next()) {
1746
    b->set_dominator_depth(-1);
1747
    b->set_dominator(nullptr);
1748
  }
1749
  PropagateImmediateDominators(block->rpo_next());
1750

1751 1752 1753 1754
  // 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.
1755 1756
  NodeVector propagation_roots(control_flow_builder_->control_);
  for (Node* node : control_flow_builder_->control_) {
1757
    for (Node* use : node->uses()) {
1758 1759 1760
      if (NodeProperties::IsPhi(use) && IsLive(use)) {
        propagation_roots.push_back(use);
      }
1761 1762 1763
    }
  }
  if (FLAG_trace_turbo_scheduler) {
1764
    TRACE("propagation roots: ");
1765
    for (Node* node : propagation_roots) {
1766
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1767
    }
1768
    TRACE("\n");
1769 1770 1771 1772
  }
  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
  schedule_early_visitor.Run(&propagation_roots);

1773 1774
  // Move previously planned nodes.
  // TODO(mstarzinger): Improve that by supporting bulk moves.
1775
  scheduled_nodes_.resize(schedule_->BasicBlockCount());
1776
  MovePlannedNodes(block, schedule_->block(node));
1777

1778 1779
  if (FLAG_trace_turbo_scheduler) {
    OFStream os(stdout);
1780
    os << "Schedule after control flow fusion:\n" << *schedule_;
1781
  }
1782
}
1783 1784


1785
void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
1786
  TRACE("Move planned nodes from id:%d to id:%d\n", from->id().ToInt(),
1787
        to->id().ToInt());
1788 1789 1790 1791 1792
  NodeVector* from_nodes = scheduled_nodes_[from->id().ToSize()];
  NodeVector* to_nodes = scheduled_nodes_[to->id().ToSize()];
  if (!from_nodes) return;

  for (Node* const node : *from_nodes) {
1793
    schedule_->SetBlockForNode(to, node);
1794
  }
1795 1796 1797 1798 1799 1800 1801
  if (to_nodes) {
    to_nodes->insert(to_nodes->end(), from_nodes->begin(), from_nodes->end());
    from_nodes->clear();
  } else {
    std::swap(scheduled_nodes_[from->id().ToSize()],
              scheduled_nodes_[to->id().ToSize()]);
  }
1802 1803
}

1804 1805
#undef TRACE

1806 1807 1808
}  // namespace compiler
}  // namespace internal
}  // namespace v8