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