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