src/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 <deque>
   6 #include <queue>
   7
   8 #include "src/compiler/scheduler.h"
   9
  10 #include "src/compiler/graph.h"
  11 #include "src/compiler/graph-inl.h"
  12 #include "src/compiler/node.h"
  13 #include "src/compiler/node-properties.h"
  14 #include "src/compiler/node-properties-inl.h"
  15 #include "src/data-flow.h"
  16
  17 namespace v8 {
  18 namespace internal {
  19 namespace compiler {
  20
  21 static inline void Trace(const char* msg, ...) {
  22   if (FLAG_trace_turbo_scheduler) {
  23     va_list arguments;
  24     va_start(arguments, msg);
  25     base::OS::VPrint(msg, arguments);
  26     va_end(arguments);
  27   }
  28 }
  29
  30
  31 // Internal class to build a control flow graph (i.e the basic blocks and edges
  32 // between them within a Schedule) from the node graph.
  33 // Visits the control edges of the graph backwards from end in order to find
  34 // the connected control subgraph, needed for scheduling.
  35 class CFGBuilder {
  36  public:
  37   Scheduler* scheduler_;
  38   Schedule* schedule_;
  39   ZoneQueue<Node*> queue_;
  40   NodeVector control_;
  41
  42   CFGBuilder(Zone* zone, Scheduler* scheduler)
  43       : scheduler_(scheduler),
  44         schedule_(scheduler->schedule_),
  45         queue_(zone),
  46         control_(zone) {}
  47
  48   // Run the control flow graph construction algorithm by walking the graph
  49   // backwards from end through control edges, building and connecting the
  50   // basic blocks for control nodes.
  51   void Run() {
  52     Graph* graph = scheduler_->graph_;
  53     FixNode(schedule_->start(), graph->start());
  54     Queue(graph->end());
  55
  56     while (!queue_.empty()) {  // Breadth-first backwards traversal.
  57       Node* node = queue_.front();
  58       queue_.pop();
  59       int max = NodeProperties::PastControlIndex(node);
  60       for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
  61         Queue(node->InputAt(i));
  62       }
  63     }
  64
  65     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
  66       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
  67     }
  68
  69     FixNode(schedule_->end(), graph->end());
  70   }
  71
  72   void FixNode(BasicBlock* block, Node* node) {
  73     schedule_->AddNode(block, node);
  74     scheduler_->GetData(node)->is_connected_control_ = true;
  75     scheduler_->GetData(node)->placement_ = Scheduler::kFixed;
  76   }
  77
  78   void Queue(Node* node) {
  79     // Mark the connected control nodes as they queued.
  80     Scheduler::SchedulerData* data = scheduler_->GetData(node);
  81     if (!data->is_connected_control_) {
  82       BuildBlocks(node);
  83       queue_.push(node);
  84       control_.push_back(node);
  85       data->is_connected_control_ = true;
  86     }
  87   }
  88
  89   void BuildBlocks(Node* node) {
  90     switch (node->opcode()) {
  91       case IrOpcode::kLoop:
  92       case IrOpcode::kMerge:
  93         BuildBlockForNode(node);
  94         break;
  95       case IrOpcode::kBranch:
  96         BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse);
  97         break;
  98       default:
  99         break;
 100     }
 101   }
 102
 103   void ConnectBlocks(Node* node) {
 104     switch (node->opcode()) {
 105       case IrOpcode::kLoop:
 106       case IrOpcode::kMerge:
 107         ConnectMerge(node);
 108         break;
 109       case IrOpcode::kBranch:
 110         scheduler_->schedule_root_nodes_.push_back(node);
 111         ConnectBranch(node);
 112         break;
 113       case IrOpcode::kReturn:
 114         scheduler_->schedule_root_nodes_.push_back(node);
 115         ConnectReturn(node);
 116         break;
 117       default:
 118         break;
 119     }
 120   }
 121
 122   void BuildBlockForNode(Node* node) {
 123     if (schedule_->block(node) == NULL) {
 124       BasicBlock* block = schedule_->NewBasicBlock();
 125       Trace("Create block B%d for #%d:%s\n", block->id(), node->id(),
 126             node->op()->mnemonic());
 127       FixNode(block, node);
 128     }
 129   }
 130
 131   void BuildBlocksForSuccessors(Node* node, IrOpcode::Value a,
 132                                 IrOpcode::Value b) {
 133     Node* successors[2];
 134     CollectSuccessorProjections(node, successors, a, b);
 135     BuildBlockForNode(successors[0]);
 136     BuildBlockForNode(successors[1]);
 137   }
 138
 139   // Collect the branch-related projections from a node, such as IfTrue,
 140   // IfFalse.
 141   // TODO(titzer): consider moving this to node.h
 142   void CollectSuccessorProjections(Node* node, Node** buffer,
 143                                    IrOpcode::Value true_opcode,
 144                                    IrOpcode::Value false_opcode) {
 145     buffer[0] = NULL;
 146     buffer[1] = NULL;
 147     for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) {
 148       if ((*i)->opcode() == true_opcode) {
 149         DCHECK_EQ(NULL, buffer[0]);
 150         buffer[0] = *i;
 151       }
 152       if ((*i)->opcode() == false_opcode) {
 153         DCHECK_EQ(NULL, buffer[1]);
 154         buffer[1] = *i;
 155       }
 156     }
 157     DCHECK_NE(NULL, buffer[0]);
 158     DCHECK_NE(NULL, buffer[1]);
 159   }
 160
 161   void CollectSuccessorBlocks(Node* node, BasicBlock** buffer,
 162                               IrOpcode::Value true_opcode,
 163                               IrOpcode::Value false_opcode) {
 164     Node* successors[2];
 165     CollectSuccessorProjections(node, successors, true_opcode, false_opcode);
 166     buffer[0] = schedule_->block(successors[0]);
 167     buffer[1] = schedule_->block(successors[1]);
 168   }
 169
 170   void ConnectBranch(Node* branch) {
 171     Node* branch_block_node = NodeProperties::GetControlInput(branch);
 172     BasicBlock* branch_block = schedule_->block(branch_block_node);
 173     DCHECK(branch_block != NULL);
 174
 175     BasicBlock* successor_blocks[2];
 176     CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue,
 177                            IrOpcode::kIfFalse);
 178
 179     TraceConnect(branch, branch_block, successor_blocks[0]);
 180     TraceConnect(branch, branch_block, successor_blocks[1]);
 181
 182     schedule_->AddBranch(branch_block, branch, successor_blocks[0],
 183                          successor_blocks[1]);
 184   }
 185
 186   void ConnectMerge(Node* merge) {
 187     BasicBlock* block = schedule_->block(merge);
 188     DCHECK(block != NULL);
 189     // For all of the merge's control inputs, add a goto at the end to the
 190     // merge's basic block.
 191     for (InputIter j = merge->inputs().begin(); j != merge->inputs().end();
 192          ++j) {
 193       BasicBlock* predecessor_block = schedule_->block(*j);
 194       if ((*j)->opcode() != IrOpcode::kReturn) {
 195         TraceConnect(merge, predecessor_block, block);
 196         schedule_->AddGoto(predecessor_block, block);
 197       }
 198     }
 199   }
 200
 201   void ConnectReturn(Node* ret) {
 202     Node* return_block_node = NodeProperties::GetControlInput(ret);
 203     BasicBlock* return_block = schedule_->block(return_block_node);
 204     TraceConnect(ret, return_block, NULL);
 205     schedule_->AddReturn(return_block, ret);
 206   }
 207
 208   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
 209     DCHECK_NE(NULL, block);
 210     if (succ == NULL) {
 211       Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(),
 212             block->id());
 213     } else {
 214       Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(),
 215             block->id(), succ->id());
 216     }
 217   }
 218 };
 219
 220
 221 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
 222   SchedulerData def = {0, 0, false, false, kUnknown};
 223   return def;
 224 }
 225
 226
 227 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule)
 228     : zone_(zone),
 229       graph_(graph),
 230       schedule_(schedule),
 231       scheduled_nodes_(zone),
 232       schedule_root_nodes_(zone),
 233       node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone),
 234       has_floating_control_(false) {}
 235
 236
 237 Schedule* Scheduler::ComputeSchedule(Graph* graph) {
 238   Schedule* schedule;
 239   bool had_floating_control = false;
 240   do {
 241     Zone tmp_zone(graph->zone()->isolate());
 242     schedule = new (graph->zone()) Schedule(graph->zone());
 243     Scheduler scheduler(&tmp_zone, graph, schedule);
 244
 245     scheduler.BuildCFG();
 246
 247     Scheduler::ComputeSpecialRPO(schedule);
 248     scheduler.GenerateImmediateDominatorTree();
 249
 250     scheduler.PrepareUses();
 251     scheduler.ScheduleEarly();
 252     scheduler.ScheduleLate();
 253
 254     had_floating_control = scheduler.ConnectFloatingControl();
 255   } while (had_floating_control);
 256
 257   return schedule;
 258 }
 259
 260
 261 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
 262   SchedulerData* data = GetData(node);
 263   if (data->placement_ == kUnknown) {  // Compute placement, once, on demand.
 264     switch (node->opcode()) {
 265       case IrOpcode::kParameter:
 266         // Parameters are always fixed to the start node.
 267         data->placement_ = kFixed;
 268         break;
 269       case IrOpcode::kPhi:
 270       case IrOpcode::kEffectPhi: {
 271         // Phis and effect phis are fixed if their control inputs are.
 272         data->placement_ = GetPlacement(NodeProperties::GetControlInput(node));
 273         break;
 274       }
 275 #define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V:
 276         CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE)
 277 #undef DEFINE_FLOATING_CONTROL_CASE
 278         {
 279           // Control nodes that were not control-reachable from end may float.
 280           data->placement_ = kSchedulable;
 281           if (!data->is_connected_control_) {
 282             data->is_floating_control_ = true;
 283             has_floating_control_ = true;
 284             Trace("Floating control found: #%d:%s\n", node->id(),
 285                   node->op()->mnemonic());
 286           }
 287           break;
 288         }
 289       default:
 290         data->placement_ = kSchedulable;
 291         break;
 292     }
 293   }
 294   return data->placement_;
 295 }
 296
 297
 298 void Scheduler::BuildCFG() {
 299   Trace("---------------- CREATING CFG ------------------\n");
 300   CFGBuilder cfg_builder(zone_, this);
 301   cfg_builder.Run();
 302   // Initialize per-block data.
 303   scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_));
 304 }
 305
 306
 307 BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
 308   while (b1 != b2) {
 309     int b1_rpo = GetRPONumber(b1);
 310     int b2_rpo = GetRPONumber(b2);
 311     DCHECK(b1_rpo != b2_rpo);
 312     if (b1_rpo < b2_rpo) {
 313       b2 = b2->dominator_;
 314     } else {
 315       b1 = b1->dominator_;
 316     }
 317   }
 318   return b1;
 319 }
 320
 321
 322 void Scheduler::GenerateImmediateDominatorTree() {
 323   // Build the dominator graph.  TODO(danno): consider using Lengauer & Tarjan's
 324   // if this becomes really slow.
 325   Trace("------------ IMMEDIATE BLOCK DOMINATORS -----------\n");
 326   for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) {
 327     BasicBlock* current_rpo = schedule_->rpo_order_[i];
 328     if (current_rpo != schedule_->start()) {
 329       BasicBlock::Predecessors::iterator current_pred =
 330           current_rpo->predecessors().begin();
 331       BasicBlock::Predecessors::iterator end =
 332           current_rpo->predecessors().end();
 333       DCHECK(current_pred != end);
 334       BasicBlock* dominator = *current_pred;
 335       ++current_pred;
 336       // For multiple predecessors, walk up the rpo ordering until a common
 337       // dominator is found.
 338       int current_rpo_pos = GetRPONumber(current_rpo);
 339       while (current_pred != end) {
 340         // Don't examine backwards edges
 341         BasicBlock* pred = *current_pred;
 342         if (GetRPONumber(pred) < current_rpo_pos) {
 343           dominator = GetCommonDominator(dominator, *current_pred);
 344         }
 345         ++current_pred;
 346       }
 347       current_rpo->dominator_ = dominator;
 348       Trace("Block %d's idom is %d\n", current_rpo->id(), dominator->id());
 349     }
 350   }
 351 }
 352
 353
 354 class ScheduleEarlyNodeVisitor : public NullNodeVisitor {
 355  public:
 356   explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler)
 357       : has_changed_rpo_constraints_(true),
 358         scheduler_(scheduler),
 359         schedule_(scheduler->schedule_) {}
 360
 361   GenericGraphVisit::Control Pre(Node* node) {
 362     int max_rpo = 0;
 363     // Fixed nodes already know their schedule early position.
 364     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
 365       BasicBlock* block = schedule_->block(node);
 366       DCHECK(block != NULL);
 367       max_rpo = block->rpo_number_;
 368       if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) {
 369         has_changed_rpo_constraints_ = true;
 370       }
 371       scheduler_->GetData(node)->minimum_rpo_ = max_rpo;
 372       Trace("Preschedule #%d:%s minimum_rpo = %d\n", node->id(),
 373             node->op()->mnemonic(), max_rpo);
 374     }
 375     return GenericGraphVisit::CONTINUE;
 376   }
 377
 378   GenericGraphVisit::Control Post(Node* node) {
 379     int max_rpo = 0;
 380     // Otherwise, the minimum rpo for the node is the max of all of the inputs.
 381     if (scheduler_->GetPlacement(node) != Scheduler::kFixed) {
 382       for (InputIter i = node->inputs().begin(); i != node->inputs().end();
 383            ++i) {
 384         int control_rpo = scheduler_->GetData(*i)->minimum_rpo_;
 385         if (control_rpo > max_rpo) {
 386           max_rpo = control_rpo;
 387         }
 388       }
 389       if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) {
 390         has_changed_rpo_constraints_ = true;
 391       }
 392       scheduler_->GetData(node)->minimum_rpo_ = max_rpo;
 393       Trace("Postschedule #%d:%s minimum_rpo = %d\n", node->id(),
 394             node->op()->mnemonic(), max_rpo);
 395     }
 396     return GenericGraphVisit::CONTINUE;
 397   }
 398
 399   // TODO(mstarzinger): Dirty hack to unblock others, schedule early should be
 400   // rewritten to use a pre-order traversal from the start instead.
 401   bool has_changed_rpo_constraints_;
 402
 403  private:
 404   Scheduler* scheduler_;
 405   Schedule* schedule_;
 406 };
 407
 408
 409 void Scheduler::ScheduleEarly() {
 410   Trace("------------------- SCHEDULE EARLY ----------------\n");
 411
 412   int fixpoint_count = 0;
 413   ScheduleEarlyNodeVisitor visitor(this);
 414   while (visitor.has_changed_rpo_constraints_) {
 415     visitor.has_changed_rpo_constraints_ = false;
 416     graph_->VisitNodeInputsFromEnd(&visitor);
 417     fixpoint_count++;
 418   }
 419
 420   Trace("It took %d iterations to determine fixpoint\n", fixpoint_count);
 421 }
 422
 423
 424 class PrepareUsesVisitor : public NullNodeVisitor {
 425  public:
 426   explicit PrepareUsesVisitor(Scheduler* scheduler)
 427       : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
 428
 429   GenericGraphVisit::Control Pre(Node* node) {
 430     if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
 431       // Fixed nodes are always roots for schedule late.
 432       scheduler_->schedule_root_nodes_.push_back(node);
 433       if (!schedule_->IsScheduled(node)) {
 434         // Make sure root nodes are scheduled in their respective blocks.
 435         Trace("  Scheduling fixed position node #%d:%s\n", node->id(),
 436               node->op()->mnemonic());
 437         IrOpcode::Value opcode = node->opcode();
 438         BasicBlock* block =
 439             opcode == IrOpcode::kParameter
 440                 ? schedule_->start()
 441                 : schedule_->block(NodeProperties::GetControlInput(node));
 442         DCHECK(block != NULL);
 443         schedule_->AddNode(block, node);
 444       }
 445     }
 446
 447     return GenericGraphVisit::CONTINUE;
 448   }
 449
 450   void PostEdge(Node* from, int index, Node* to) {
 451     // If the edge is from an unscheduled node, then tally it in the use count
 452     // for all of its inputs. The same criterion will be used in ScheduleLate
 453     // for decrementing use counts.
 454     if (!schedule_->IsScheduled(from)) {
 455       DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
 456       ++(scheduler_->GetData(to)->unscheduled_count_);
 457       Trace("  Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(),
 458             to->op()->mnemonic(), from->id(), from->op()->mnemonic(),
 459             scheduler_->GetData(to)->unscheduled_count_);
 460     }
 461   }
 462
 463  private:
 464   Scheduler* scheduler_;
 465   Schedule* schedule_;
 466 };
 467
 468
 469 void Scheduler::PrepareUses() {
 470   Trace("------------------- PREPARE USES ------------------\n");
 471   // Count the uses of every node, it will be used to ensure that all of a
 472   // node's uses are scheduled before the node itself.
 473   PrepareUsesVisitor prepare_uses(this);
 474   graph_->VisitNodeInputsFromEnd(&prepare_uses);
 475 }
 476
 477
 478 class ScheduleLateNodeVisitor : public NullNodeVisitor {
 479  public:
 480   explicit ScheduleLateNodeVisitor(Scheduler* scheduler)
 481       : scheduler_(scheduler), schedule_(scheduler_->schedule_) {}
 482
 483   GenericGraphVisit::Control Pre(Node* node) {
 484     // Don't schedule nodes that are already scheduled.
 485     if (schedule_->IsScheduled(node)) {
 486       return GenericGraphVisit::CONTINUE;
 487     }
 488     Scheduler::SchedulerData* data = scheduler_->GetData(node);
 489     DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
 490
 491     // If all the uses of a node have been scheduled, then the node itself can
 492     // be scheduled.
 493     bool eligible = data->unscheduled_count_ == 0;
 494     Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(),
 495           node->op()->mnemonic(), eligible ? "true" : "false");
 496     if (!eligible) return GenericGraphVisit::DEFER;
 497
 498     // Determine the dominating block for all of the uses of this node. It is
 499     // the latest block that this node can be scheduled in.
 500     BasicBlock* block = NULL;
 501     for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end();
 502          ++i) {
 503       BasicBlock* use_block = GetBlockForUse(i.edge());
 504       block = block == NULL ? use_block : use_block == NULL
 505                                               ? block
 506                                               : scheduler_->GetCommonDominator(
 507                                                     block, use_block);
 508     }
 509     DCHECK(block != NULL);
 510
 511     int min_rpo = data->minimum_rpo_;
 512     Trace(
 513         "Schedule late conservative for #%d:%s is B%d at loop depth %d, "
 514         "minimum_rpo = %d\n",
 515         node->id(), node->op()->mnemonic(), block->id(), block->loop_depth_,
 516         min_rpo);
 517     // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
 518     // into enclosing loop pre-headers until they would preceed their
 519     // ScheduleEarly position.
 520     BasicBlock* hoist_block = block;
 521     while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) {
 522       if (hoist_block->loop_depth_ < block->loop_depth_) {
 523         block = hoist_block;
 524         Trace("  hoisting #%d:%s to block %d\n", node->id(),
 525               node->op()->mnemonic(), block->id());
 526       }
 527       // Try to hoist to the pre-header of the loop header.
 528       hoist_block = hoist_block->loop_header();
 529       if (hoist_block != NULL) {
 530         BasicBlock* pre_header = hoist_block->dominator_;
 531         DCHECK(pre_header == NULL ||
 532                *hoist_block->predecessors().begin() == pre_header);
 533         Trace(
 534             "  hoist to pre-header B%d of loop header B%d, depth would be %d\n",
 535             pre_header->id(), hoist_block->id(), pre_header->loop_depth_);
 536         hoist_block = pre_header;
 537       }
 538     }
 539
 540     ScheduleNode(block, node);
 541
 542     return GenericGraphVisit::CONTINUE;
 543   }
 544
 545  private:
 546   BasicBlock* GetBlockForUse(Node::Edge edge) {
 547     Node* use = edge.from();
 548     IrOpcode::Value opcode = use->opcode();
 549     if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) {
 550       // If the use is from a fixed (i.e. non-floating) phi, use the block
 551       // of the corresponding control input to the merge.
 552       int index = edge.index();
 553       if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
 554         Trace("  input@%d into a fixed phi #%d:%s\n", index, use->id(),
 555               use->op()->mnemonic());
 556         Node* merge = NodeProperties::GetControlInput(use, 0);
 557         opcode = merge->opcode();
 558         DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop);
 559         use = NodeProperties::GetControlInput(merge, index);
 560       }
 561     }
 562     BasicBlock* result = schedule_->block(use);
 563     if (result == NULL) return NULL;
 564     Trace("  must dominate use #%d:%s in B%d\n", use->id(),
 565           use->op()->mnemonic(), result->id());
 566     return result;
 567   }
 568
 569   void ScheduleNode(BasicBlock* block, Node* node) {
 570     schedule_->PlanNode(block, node);
 571     scheduler_->scheduled_nodes_[block->id()].push_back(node);
 572
 573     // Reduce the use count of the node's inputs to potentially make them
 574     // schedulable.
 575     for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
 576       Scheduler::SchedulerData* data = scheduler_->GetData(*i);
 577       DCHECK(data->unscheduled_count_ > 0);
 578       --data->unscheduled_count_;
 579       if (FLAG_trace_turbo_scheduler) {
 580         Trace("  Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(),
 581               (*i)->op()->mnemonic(), i.edge().from()->id(),
 582               i.edge().from()->op()->mnemonic(), data->unscheduled_count_);
 583         if (data->unscheduled_count_ == 0) {
 584           Trace("  newly eligible #%d:%s\n", (*i)->id(),
 585                 (*i)->op()->mnemonic());
 586         }
 587       }
 588     }
 589   }
 590
 591   Scheduler* scheduler_;
 592   Schedule* schedule_;
 593 };
 594
 595
 596 void Scheduler::ScheduleLate() {
 597   Trace("------------------- SCHEDULE LATE -----------------\n");
 598   if (FLAG_trace_turbo_scheduler) {
 599     Trace("roots: ");
 600     for (NodeVectorIter i = schedule_root_nodes_.begin();
 601          i != schedule_root_nodes_.end(); ++i) {
 602       Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic());
 603     }
 604     Trace("\n");
 605   }
 606
 607   // Schedule: Places nodes in dominator block of all their uses.
 608   ScheduleLateNodeVisitor schedule_late_visitor(this);
 609
 610   {
 611     Zone zone(zone_->isolate());
 612     GenericGraphVisit::Visit<ScheduleLateNodeVisitor,
 613                              NodeInputIterationTraits<Node> >(
 614         graph_, &zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(),
 615         &schedule_late_visitor);
 616   }
 617
 618   // Add collected nodes for basic blocks to their blocks in the right order.
 619   int block_num = 0;
 620   for (NodeVectorVectorIter i = scheduled_nodes_.begin();
 621        i != scheduled_nodes_.end(); ++i) {
 622     for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) {
 623       schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j);
 624     }
 625     block_num++;
 626   }
 627 }
 628
 629
 630 bool Scheduler::ConnectFloatingControl() {
 631   if (!has_floating_control_) return false;
 632
 633   Trace("Connecting floating control...\n");
 634
 635   // Process blocks and instructions backwards to find and connect floating
 636   // control nodes into the control graph according to the block they were
 637   // scheduled into.
 638   int max = static_cast<int>(schedule_->rpo_order()->size());
 639   for (int i = max - 1; i >= 0; i--) {
 640     BasicBlock* block = schedule_->rpo_order()->at(i);
 641     // TODO(titzer): we place at most one floating control structure per
 642     // basic block because scheduling currently can interleave phis from
 643     // one subgraph with the merges from another subgraph.
 644     bool one_placed = false;
 645     for (int j = static_cast<int>(block->nodes_.size()) - 1; j >= 0; j--) {
 646       Node* node = block->nodes_[j];
 647       SchedulerData* data = GetData(node);
 648       if (data->is_floating_control_ && !data->is_connected_control_ &&
 649           !one_placed) {
 650         Trace("  Floating control #%d:%s was scheduled in B%d\n", node->id(),
 651               node->op()->mnemonic(), block->id());
 652         ConnectFloatingControlSubgraph(block, node);
 653         one_placed = true;
 654       }
 655     }
 656   }
 657
 658   return true;
 659 }
 660
 661
 662 void Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) {
 663   Node* block_start = block->nodes_[0];
 664   DCHECK(IrOpcode::IsControlOpcode(block_start->opcode()));
 665   // Find the current "control successor" of the node that starts the block
 666   // by searching the control uses for a control input edge from a connected
 667   // control node.
 668   Node* control_succ = NULL;
 669   for (UseIter i = block_start->uses().begin(); i != block_start->uses().end();
 670        ++i) {
 671     Node::Edge edge = i.edge();
 672     if (NodeProperties::IsControlEdge(edge) &&
 673         GetData(edge.from())->is_connected_control_) {
 674       DCHECK_EQ(NULL, control_succ);
 675       control_succ = edge.from();
 676       control_succ->ReplaceInput(edge.index(), end);
 677     }
 678   }
 679   DCHECK_NE(NULL, control_succ);
 680   Trace("  Inserting floating control end %d:%s between %d:%s -> %d:%s\n",
 681         end->id(), end->op()->mnemonic(), control_succ->id(),
 682         control_succ->op()->mnemonic(), block_start->id(),
 683         block_start->op()->mnemonic());
 684
 685   // Find the "start" node of the control subgraph, which should be the
 686   // unique node that is itself floating control but has a control input that
 687   // is not floating.
 688   Node* start = NULL;
 689   ZoneQueue<Node*> queue(zone_);
 690   queue.push(end);
 691   GetData(end)->is_connected_control_ = true;
 692   while (!queue.empty()) {
 693     Node* node = queue.front();
 694     queue.pop();
 695     Trace("  Search #%d:%s for control subgraph start\n", node->id(),
 696           node->op()->mnemonic());
 697     int max = NodeProperties::PastControlIndex(node);
 698     for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
 699       Node* input = node->InputAt(i);
 700       SchedulerData* data = GetData(input);
 701       if (data->is_floating_control_) {
 702         // {input} is floating control.
 703         if (!data->is_connected_control_) {
 704           // First time seeing {input} during this traversal, queue it.
 705           queue.push(input);
 706           data->is_connected_control_ = true;
 707         }
 708       } else {
 709         // Otherwise, {node} is the start node, because it is floating control
 710         // but is connected to {input} that is not floating control.
 711         DCHECK_EQ(NULL, start);  // There can be only one.
 712         start = node;
 713       }
 714     }
 715   }
 716
 717   DCHECK_NE(NULL, start);
 718   start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start);
 719
 720   Trace("  Connecting floating control start %d:%s to %d:%s\n", start->id(),
 721         start->op()->mnemonic(), block_start->id(),
 722         block_start->op()->mnemonic());
 723 }
 724
 725
 726 // Numbering for BasicBlockData.rpo_number_ for this block traversal:
 727 static const int kBlockOnStack = -2;
 728 static const int kBlockVisited1 = -3;
 729 static const int kBlockVisited2 = -4;
 730 static const int kBlockUnvisited1 = -1;
 731 static const int kBlockUnvisited2 = kBlockVisited1;
 732
 733 struct SpecialRPOStackFrame {
 734   BasicBlock* block;
 735   int index;
 736 };
 737
 738 struct BlockList {
 739   BasicBlock* block;
 740   BlockList* next;
 741
 742   BlockList* Add(Zone* zone, BasicBlock* b) {
 743     BlockList* list = static_cast<BlockList*>(zone->New(sizeof(BlockList)));
 744     list->block = b;
 745     list->next = this;
 746     return list;
 747   }
 748
 749   void Serialize(BasicBlockVector* final_order) {
 750     for (BlockList* l = this; l != NULL; l = l->next) {
 751       l->block->rpo_number_ = static_cast<int>(final_order->size());
 752       final_order->push_back(l->block);
 753     }
 754   }
 755 };
 756
 757 struct LoopInfo {
 758   BasicBlock* header;
 759   ZoneList<BasicBlock*>* outgoing;
 760   BitVector* members;
 761   LoopInfo* prev;
 762   BlockList* end;
 763   BlockList* start;
 764
 765   void AddOutgoing(Zone* zone, BasicBlock* block) {
 766     if (outgoing == NULL) outgoing = new (zone) ZoneList<BasicBlock*>(2, zone);
 767     outgoing->Add(block, zone);
 768   }
 769 };
 770
 771
 772 static int Push(SpecialRPOStackFrame* stack, int depth, BasicBlock* child,
 773                 int unvisited) {
 774   if (child->rpo_number_ == unvisited) {
 775     stack[depth].block = child;
 776     stack[depth].index = 0;
 777     child->rpo_number_ = kBlockOnStack;
 778     return depth + 1;
 779   }
 780   return depth;
 781 }
 782
 783
 784 // Computes loop membership from the backedges of the control flow graph.
 785 static LoopInfo* ComputeLoopInfo(
 786     Zone* zone, SpecialRPOStackFrame* queue, int num_loops, int num_blocks,
 787     ZoneList<std::pair<BasicBlock*, int> >* backedges) {
 788   LoopInfo* loops = zone->NewArray<LoopInfo>(num_loops);
 789   memset(loops, 0, num_loops * sizeof(LoopInfo));
 790
 791   // Compute loop membership starting from backedges.
 792   // O(max(loop_depth) * max(|loop|)
 793   for (int i = 0; i < backedges->length(); i++) {
 794     BasicBlock* member = backedges->at(i).first;
 795     BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
 796     int loop_num = header->loop_end_;
 797     if (loops[loop_num].header == NULL) {
 798       loops[loop_num].header = header;
 799       loops[loop_num].members = new (zone) BitVector(num_blocks, zone);
 800     }
 801
 802     int queue_length = 0;
 803     if (member != header) {
 804       // As long as the header doesn't have a backedge to itself,
 805       // Push the member onto the queue and process its predecessors.
 806       if (!loops[loop_num].members->Contains(member->id())) {
 807         loops[loop_num].members->Add(member->id());
 808       }
 809       queue[queue_length++].block = member;
 810     }
 811
 812     // Propagate loop membership backwards. All predecessors of M up to the
 813     // loop header H are members of the loop too. O(|blocks between M and H|).
 814     while (queue_length > 0) {
 815       BasicBlock* block = queue[--queue_length].block;
 816       for (int i = 0; i < block->PredecessorCount(); i++) {
 817         BasicBlock* pred = block->PredecessorAt(i);
 818         if (pred != header) {
 819           if (!loops[loop_num].members->Contains(pred->id())) {
 820             loops[loop_num].members->Add(pred->id());
 821             queue[queue_length++].block = pred;
 822           }
 823         }
 824       }
 825     }
 826   }
 827   return loops;
 828 }
 829
 830
 831 #if DEBUG
 832 static void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) {
 833   PrintF("-- RPO with %d loops ", num_loops);
 834   if (num_loops > 0) {
 835     PrintF("(");
 836     for (int i = 0; i < num_loops; i++) {
 837       if (i > 0) PrintF(" ");
 838       PrintF("B%d", loops[i].header->id());
 839     }
 840     PrintF(") ");
 841   }
 842   PrintF("-- \n");
 843
 844   for (int i = 0; i < static_cast<int>(order->size()); i++) {
 845     BasicBlock* block = (*order)[i];
 846     int bid = block->id();
 847     PrintF("%5d:", i);
 848     for (int i = 0; i < num_loops; i++) {
 849       bool membership = loops[i].members->Contains(bid);
 850       bool range = loops[i].header->LoopContains(block);
 851       PrintF(membership ? " |" : "  ");
 852       PrintF(range ? "x" : " ");
 853     }
 854     PrintF("  B%d: ", bid);
 855     if (block->loop_end_ >= 0) {
 856       PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_);
 857     }
 858     PrintF("\n");
 859   }
 860 }
 861
 862
 863 static void VerifySpecialRPO(int num_loops, LoopInfo* loops,
 864                              BasicBlockVector* order) {
 865   DCHECK(order->size() > 0);
 866   DCHECK((*order)[0]->id() == 0);  // entry should be first.
 867
 868   for (int i = 0; i < num_loops; i++) {
 869     LoopInfo* loop = &loops[i];
 870     BasicBlock* header = loop->header;
 871
 872     DCHECK(header != NULL);
 873     DCHECK(header->rpo_number_ >= 0);
 874     DCHECK(header->rpo_number_ < static_cast<int>(order->size()));
 875     DCHECK(header->loop_end_ >= 0);
 876     DCHECK(header->loop_end_ <= static_cast<int>(order->size()));
 877     DCHECK(header->loop_end_ > header->rpo_number_);
 878
 879     // Verify the start ... end list relationship.
 880     int links = 0;
 881     BlockList* l = loop->start;
 882     DCHECK(l != NULL && l->block == header);
 883     bool end_found;
 884     while (true) {
 885       if (l == NULL || l == loop->end) {
 886         end_found = (loop->end == l);
 887         break;
 888       }
 889       // The list should be in same order as the final result.
 890       DCHECK(l->block->rpo_number_ == links + loop->header->rpo_number_);
 891       links++;
 892       l = l->next;
 893       DCHECK(links < static_cast<int>(2 * order->size()));  // cycle?
 894     }
 895     DCHECK(links > 0);
 896     DCHECK(links == (header->loop_end_ - header->rpo_number_));
 897     DCHECK(end_found);
 898
 899     // Check the contiguousness of loops.
 900     int count = 0;
 901     for (int j = 0; j < static_cast<int>(order->size()); j++) {
 902       BasicBlock* block = order->at(j);
 903       DCHECK(block->rpo_number_ == j);
 904       if (j < header->rpo_number_ || j >= header->loop_end_) {
 905         DCHECK(!loop->members->Contains(block->id()));
 906       } else {
 907         if (block == header) {
 908           DCHECK(!loop->members->Contains(block->id()));
 909         } else {
 910           DCHECK(loop->members->Contains(block->id()));
 911         }
 912         count++;
 913       }
 914     }
 915     DCHECK(links == count);
 916   }
 917 }
 918 #endif  // DEBUG
 919
 920
 921 // Compute the special reverse-post-order block ordering, which is essentially
 922 // a RPO of the graph where loop bodies are contiguous. Properties:
 923 // 1. If block A is a predecessor of B, then A appears before B in the order,
 924 //    unless B is a loop header and A is in the loop headed at B
 925 //    (i.e. A -> B is a backedge).
 926 // => If block A dominates block B, then A appears before B in the order.
 927 // => If block A is a loop header, A appears before all blocks in the loop
 928 //    headed at A.
 929 // 2. All loops are contiguous in the order (i.e. no intervening blocks that
 930 //    do not belong to the loop.)
 931 // Note a simple RPO traversal satisfies (1) but not (3).
 932 BasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) {
 933   Zone tmp_zone(schedule->zone()->isolate());
 934   Zone* zone = &tmp_zone;
 935   Trace("------------- COMPUTING SPECIAL RPO ---------------\n");
 936   // RPO should not have been computed for this schedule yet.
 937   CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number_);
 938   CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size()));
 939
 940   // Perform an iterative RPO traversal using an explicit stack,
 941   // recording backedges that form cycles. O(|B|).
 942   ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone);
 943   SpecialRPOStackFrame* stack =
 944       zone->NewArray<SpecialRPOStackFrame>(schedule->BasicBlockCount());
 945   BasicBlock* entry = schedule->start();
 946   BlockList* order = NULL;
 947   int stack_depth = Push(stack, 0, entry, kBlockUnvisited1);
 948   int num_loops = 0;
 949
 950   while (stack_depth > 0) {
 951     int current = stack_depth - 1;
 952     SpecialRPOStackFrame* frame = stack + current;
 953
 954     if (frame->index < frame->block->SuccessorCount()) {
 955       // Process the next successor.
 956       BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
 957       if (succ->rpo_number_ == kBlockVisited1) continue;
 958       if (succ->rpo_number_ == kBlockOnStack) {
 959         // The successor is on the stack, so this is a backedge (cycle).
 960         backedges.Add(
 961             std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone);
 962         if (succ->loop_end_ < 0) {
 963           // Assign a new loop number to the header if it doesn't have one.
 964           succ->loop_end_ = num_loops++;
 965         }
 966       } else {
 967         // Push the successor onto the stack.
 968         DCHECK(succ->rpo_number_ == kBlockUnvisited1);
 969         stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1);
 970       }
 971     } else {
 972       // Finished with all successors; pop the stack and add the block.
 973       order = order->Add(zone, frame->block);
 974       frame->block->rpo_number_ = kBlockVisited1;
 975       stack_depth--;
 976     }
 977   }
 978
 979   // If no loops were encountered, then the order we computed was correct.
 980   LoopInfo* loops = NULL;
 981   if (num_loops != 0) {
 982     // Otherwise, compute the loop information from the backedges in order
 983     // to perform a traversal that groups loop bodies together.
 984     loops = ComputeLoopInfo(zone, stack, num_loops, schedule->BasicBlockCount(),
 985                             &backedges);
 986
 987     // Initialize the "loop stack". Note the entry could be a loop header.
 988     LoopInfo* loop = entry->IsLoopHeader() ? &loops[entry->loop_end_] : NULL;
 989     order = NULL;
 990
 991     // Perform an iterative post-order traversal, visiting loop bodies before
 992     // edges that lead out of loops. Visits each block once, but linking loop
 993     // sections together is linear in the loop size, so overall is
 994     // O(|B| + max(loop_depth) * max(|loop|))
 995     stack_depth = Push(stack, 0, entry, kBlockUnvisited2);
 996     while (stack_depth > 0) {
 997       SpecialRPOStackFrame* frame = stack + (stack_depth - 1);
 998       BasicBlock* block = frame->block;
 999       BasicBlock* succ = NULL;
1000
1001       if (frame->index < block->SuccessorCount()) {
1002         // Process the next normal successor.
1003         succ = block->SuccessorAt(frame->index++);
1004       } else if (block->IsLoopHeader()) {
1005         // Process additional outgoing edges from the loop header.
1006         if (block->rpo_number_ == kBlockOnStack) {
1007           // Finish the loop body the first time the header is left on the
1008           // stack.
1009           DCHECK(loop != NULL && loop->header == block);
1010           loop->start = order->Add(zone, block);
1011           order = loop->end;
1012           block->rpo_number_ = kBlockVisited2;
1013           // Pop the loop stack and continue visiting outgoing edges within the
1014           // the context of the outer loop, if any.
1015           loop = loop->prev;
1016           // We leave the loop header on the stack; the rest of this iteration
1017           // and later iterations will go through its outgoing edges list.
1018         }
1019
1020         // Use the next outgoing edge if there are any.
1021         int outgoing_index = frame->index - block->SuccessorCount();
1022         LoopInfo* info = &loops[block->loop_end_];
1023         DCHECK(loop != info);
1024         if (info->outgoing != NULL &&
1025             outgoing_index < info->outgoing->length()) {
1026           succ = info->outgoing->at(outgoing_index);
1027           frame->index++;
1028         }
1029       }
1030
1031       if (succ != NULL) {
1032         // Process the next successor.
1033         if (succ->rpo_number_ == kBlockOnStack) continue;
1034         if (succ->rpo_number_ == kBlockVisited2) continue;
1035         DCHECK(succ->rpo_number_ == kBlockUnvisited2);
1036         if (loop != NULL && !loop->members->Contains(succ->id())) {
1037           // The successor is not in the current loop or any nested loop.
1038           // Add it to the outgoing edges of this loop and visit it later.
1039           loop->AddOutgoing(zone, succ);
1040         } else {
1041           // Push the successor onto the stack.
1042           stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2);
1043           if (succ->IsLoopHeader()) {
1044             // Push the inner loop onto the loop stack.
1045             DCHECK(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops);
1046             LoopInfo* next = &loops[succ->loop_end_];
1047             next->end = order;
1048             next->prev = loop;
1049             loop = next;
1050           }
1051         }
1052       } else {
1053         // Finished with all successors of the current block.
1054         if (block->IsLoopHeader()) {
1055           // If we are going to pop a loop header, then add its entire body.
1056           LoopInfo* info = &loops[block->loop_end_];
1057           for (BlockList* l = info->start; true; l = l->next) {
1058             if (l->next == info->end) {
1059               l->next = order;
1060               info->end = order;
1061               break;
1062             }
1063           }
1064           order = info->start;
1065         } else {
1066           // Pop a single node off the stack and add it to the order.
1067           order = order->Add(zone, block);
1068           block->rpo_number_ = kBlockVisited2;
1069         }
1070         stack_depth--;
1071       }
1072     }
1073   }
1074
1075   // Construct the final order from the list.
1076   BasicBlockVector* final_order = &schedule->rpo_order_;
1077   order->Serialize(final_order);
1078
1079   // Compute the correct loop header for every block and set the correct loop
1080   // ends.
1081   LoopInfo* current_loop = NULL;
1082   BasicBlock* current_header = NULL;
1083   int loop_depth = 0;
1084   for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end();
1085        ++i) {
1086     BasicBlock* current = *i;
1087     current->loop_header_ = current_header;
1088     if (current->IsLoopHeader()) {
1089       loop_depth++;
1090       current_loop = &loops[current->loop_end_];
1091       BlockList* end = current_loop->end;
1092       current->loop_end_ = end == NULL ? static_cast<int>(final_order->size())
1093                                        : end->block->rpo_number_;
1094       current_header = current_loop->header;
1095       Trace("B%d is a loop header, increment loop depth to %d\n", current->id(),
1096             loop_depth);
1097     } else {
1098       while (current_header != NULL &&
1099              current->rpo_number_ >= current_header->loop_end_) {
1100         DCHECK(current_header->IsLoopHeader());
1101         DCHECK(current_loop != NULL);
1102         current_loop = current_loop->prev;
1103         current_header = current_loop == NULL ? NULL : current_loop->header;
1104         --loop_depth;
1105       }
1106     }
1107     current->loop_depth_ = loop_depth;
1108     if (current->loop_header_ == NULL) {
1109       Trace("B%d is not in a loop (depth == %d)\n", current->id(),
1110             current->loop_depth_);
1111     } else {
1112       Trace("B%d has loop header B%d, (depth == %d)\n", current->id(),
1113             current->loop_header_->id(), current->loop_depth_);
1114     }
1115   }
1116
1117 #if DEBUG
1118   if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order);
1119   VerifySpecialRPO(num_loops, loops, final_order);
1120 #endif
1121   return final_order;
1122 }
1123 }
1124 }
1125 }  // namespace v8::internal::compiler