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