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/schedule.h"
6
7 #include "src/compiler/node-properties.h"
8 #include "src/compiler/node.h"
9 #include "src/ostreams.h"
10
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14
BasicBlock(Zone * zone,Id id)15 BasicBlock::BasicBlock(Zone* zone, Id id)
16 : loop_number_(-1),
17 rpo_number_(-1),
18 deferred_(false),
19 dominator_depth_(-1),
20 dominator_(nullptr),
21 rpo_next_(nullptr),
22 loop_header_(nullptr),
23 loop_end_(nullptr),
24 loop_depth_(0),
25 control_(kNone),
26 control_input_(nullptr),
27 nodes_(zone),
28 successors_(zone),
29 predecessors_(zone),
30 #if DEBUG
31 debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
32 #endif
33 id_(id) {
34 }
35
LoopContains(BasicBlock * block) const36 bool BasicBlock::LoopContains(BasicBlock* block) const {
37 // RPO numbers must be initialized.
38 DCHECK_LE(0, rpo_number_);
39 DCHECK_LE(0, block->rpo_number_);
40 if (loop_end_ == nullptr) return false; // This is not a loop.
41 return block->rpo_number_ >= rpo_number_ &&
42 block->rpo_number_ < loop_end_->rpo_number_;
43 }
44
45
AddSuccessor(BasicBlock * successor)46 void BasicBlock::AddSuccessor(BasicBlock* successor) {
47 successors_.push_back(successor);
48 }
49
50
AddPredecessor(BasicBlock * predecessor)51 void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
52 predecessors_.push_back(predecessor);
53 }
54
55
AddNode(Node * node)56 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
57
58
set_control(Control control)59 void BasicBlock::set_control(Control control) {
60 control_ = control;
61 }
62
63
set_control_input(Node * control_input)64 void BasicBlock::set_control_input(Node* control_input) {
65 control_input_ = control_input;
66 }
67
68
set_loop_depth(int32_t loop_depth)69 void BasicBlock::set_loop_depth(int32_t loop_depth) {
70 loop_depth_ = loop_depth;
71 }
72
73
set_rpo_number(int32_t rpo_number)74 void BasicBlock::set_rpo_number(int32_t rpo_number) {
75 rpo_number_ = rpo_number;
76 }
77
78
set_loop_end(BasicBlock * loop_end)79 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
80
81
set_loop_header(BasicBlock * loop_header)82 void BasicBlock::set_loop_header(BasicBlock* loop_header) {
83 loop_header_ = loop_header;
84 }
85
86
87 // static
GetCommonDominator(BasicBlock * b1,BasicBlock * b2)88 BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
89 while (b1 != b2) {
90 if (b1->dominator_depth() < b2->dominator_depth()) {
91 b2 = b2->dominator();
92 } else {
93 b1 = b1->dominator();
94 }
95 }
96 return b1;
97 }
98
Print()99 void BasicBlock::Print() { StdoutStream{} << this; }
100
operator <<(std::ostream & os,const BasicBlock & block)101 std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
102 os << "B" << block.id();
103 #if DEBUG
104 AssemblerDebugInfo info = block.debug_info();
105 if (info.name) os << info;
106 // Print predecessor blocks for better debugging.
107 const int kMaxDisplayedBlocks = 4;
108 int i = 0;
109 const BasicBlock* current_block = █
110 while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
111 current_block = current_block->predecessors().front();
112 os << " <= B" << current_block->id();
113 info = current_block->debug_info();
114 if (info.name) os << info;
115 }
116 #endif
117 return os;
118 }
119
operator <<(std::ostream & os,const BasicBlock::Control & c)120 std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
121 switch (c) {
122 case BasicBlock::kNone:
123 return os << "none";
124 case BasicBlock::kGoto:
125 return os << "goto";
126 case BasicBlock::kCall:
127 return os << "call";
128 case BasicBlock::kBranch:
129 return os << "branch";
130 case BasicBlock::kSwitch:
131 return os << "switch";
132 case BasicBlock::kDeoptimize:
133 return os << "deoptimize";
134 case BasicBlock::kTailCall:
135 return os << "tailcall";
136 case BasicBlock::kReturn:
137 return os << "return";
138 case BasicBlock::kThrow:
139 return os << "throw";
140 }
141 UNREACHABLE();
142 }
143
144
operator <<(std::ostream & os,const BasicBlock::Id & id)145 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
146 return os << id.ToSize();
147 }
148
149
Schedule(Zone * zone,size_t node_count_hint)150 Schedule::Schedule(Zone* zone, size_t node_count_hint)
151 : zone_(zone),
152 all_blocks_(zone),
153 nodeid_to_block_(zone),
154 rpo_order_(zone),
155 start_(NewBasicBlock()),
156 end_(NewBasicBlock()) {
157 nodeid_to_block_.reserve(node_count_hint);
158 }
159
160
block(Node * node) const161 BasicBlock* Schedule::block(Node* node) const {
162 if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
163 return nodeid_to_block_[node->id()];
164 }
165 return nullptr;
166 }
167
168
IsScheduled(Node * node)169 bool Schedule::IsScheduled(Node* node) {
170 if (node->id() >= nodeid_to_block_.size()) return false;
171 return nodeid_to_block_[node->id()] != nullptr;
172 }
173
174
GetBlockById(BasicBlock::Id block_id)175 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
176 DCHECK(block_id.ToSize() < all_blocks_.size());
177 return all_blocks_[block_id.ToSize()];
178 }
179
180
SameBasicBlock(Node * a,Node * b) const181 bool Schedule::SameBasicBlock(Node* a, Node* b) const {
182 BasicBlock* block = this->block(a);
183 return block != nullptr && block == this->block(b);
184 }
185
186
NewBasicBlock()187 BasicBlock* Schedule::NewBasicBlock() {
188 BasicBlock* block = new (zone_)
189 BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
190 all_blocks_.push_back(block);
191 return block;
192 }
193
194
PlanNode(BasicBlock * block,Node * node)195 void Schedule::PlanNode(BasicBlock* block, Node* node) {
196 if (FLAG_trace_turbo_scheduler) {
197 StdoutStream{} << "Planning #" << node->id() << ":"
198 << node->op()->mnemonic() << " for future add to B"
199 << block->id() << "\n";
200 }
201 DCHECK_NULL(this->block(node));
202 SetBlockForNode(block, node);
203 }
204
205
AddNode(BasicBlock * block,Node * node)206 void Schedule::AddNode(BasicBlock* block, Node* node) {
207 if (FLAG_trace_turbo_scheduler) {
208 StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
209 << " to B" << block->id() << "\n";
210 }
211 DCHECK(this->block(node) == nullptr || this->block(node) == block);
212 block->AddNode(node);
213 SetBlockForNode(block, node);
214 }
215
216
AddGoto(BasicBlock * block,BasicBlock * succ)217 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
218 DCHECK_EQ(BasicBlock::kNone, block->control());
219 block->set_control(BasicBlock::kGoto);
220 AddSuccessor(block, succ);
221 }
222
223 #if DEBUG
224 namespace {
225
IsPotentiallyThrowingCall(IrOpcode::Value opcode)226 bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
227 switch (opcode) {
228 #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
229 JS_OP_LIST(BUILD_BLOCK_JS_CASE)
230 #undef BUILD_BLOCK_JS_CASE
231 case IrOpcode::kCall:
232 case IrOpcode::kCallWithCallerSavedRegisters:
233 return true;
234 default:
235 return false;
236 }
237 }
238
239 } // namespace
240 #endif // DEBUG
241
AddCall(BasicBlock * block,Node * call,BasicBlock * success_block,BasicBlock * exception_block)242 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
243 BasicBlock* exception_block) {
244 DCHECK_EQ(BasicBlock::kNone, block->control());
245 DCHECK(IsPotentiallyThrowingCall(call->opcode()));
246 block->set_control(BasicBlock::kCall);
247 AddSuccessor(block, success_block);
248 AddSuccessor(block, exception_block);
249 SetControlInput(block, call);
250 }
251
252
AddBranch(BasicBlock * block,Node * branch,BasicBlock * tblock,BasicBlock * fblock)253 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
254 BasicBlock* fblock) {
255 DCHECK_EQ(BasicBlock::kNone, block->control());
256 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
257 block->set_control(BasicBlock::kBranch);
258 AddSuccessor(block, tblock);
259 AddSuccessor(block, fblock);
260 SetControlInput(block, branch);
261 }
262
263
AddSwitch(BasicBlock * block,Node * sw,BasicBlock ** succ_blocks,size_t succ_count)264 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
265 size_t succ_count) {
266 DCHECK_EQ(BasicBlock::kNone, block->control());
267 DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
268 block->set_control(BasicBlock::kSwitch);
269 for (size_t index = 0; index < succ_count; ++index) {
270 AddSuccessor(block, succ_blocks[index]);
271 }
272 SetControlInput(block, sw);
273 }
274
275
AddTailCall(BasicBlock * block,Node * input)276 void Schedule::AddTailCall(BasicBlock* block, Node* input) {
277 DCHECK_EQ(BasicBlock::kNone, block->control());
278 block->set_control(BasicBlock::kTailCall);
279 SetControlInput(block, input);
280 if (block != end()) AddSuccessor(block, end());
281 }
282
283
AddReturn(BasicBlock * block,Node * input)284 void Schedule::AddReturn(BasicBlock* block, Node* input) {
285 DCHECK_EQ(BasicBlock::kNone, block->control());
286 block->set_control(BasicBlock::kReturn);
287 SetControlInput(block, input);
288 if (block != end()) AddSuccessor(block, end());
289 }
290
291
AddDeoptimize(BasicBlock * block,Node * input)292 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
293 DCHECK_EQ(BasicBlock::kNone, block->control());
294 block->set_control(BasicBlock::kDeoptimize);
295 SetControlInput(block, input);
296 if (block != end()) AddSuccessor(block, end());
297 }
298
299
AddThrow(BasicBlock * block,Node * input)300 void Schedule::AddThrow(BasicBlock* block, Node* input) {
301 DCHECK_EQ(BasicBlock::kNone, block->control());
302 block->set_control(BasicBlock::kThrow);
303 SetControlInput(block, input);
304 if (block != end()) AddSuccessor(block, end());
305 }
306
307
InsertBranch(BasicBlock * block,BasicBlock * end,Node * branch,BasicBlock * tblock,BasicBlock * fblock)308 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
309 BasicBlock* tblock, BasicBlock* fblock) {
310 DCHECK_NE(BasicBlock::kNone, block->control());
311 DCHECK_EQ(BasicBlock::kNone, end->control());
312 end->set_control(block->control());
313 block->set_control(BasicBlock::kBranch);
314 MoveSuccessors(block, end);
315 AddSuccessor(block, tblock);
316 AddSuccessor(block, fblock);
317 if (block->control_input() != nullptr) {
318 SetControlInput(end, block->control_input());
319 }
320 SetControlInput(block, branch);
321 }
322
323
InsertSwitch(BasicBlock * block,BasicBlock * end,Node * sw,BasicBlock ** succ_blocks,size_t succ_count)324 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
325 BasicBlock** succ_blocks, size_t succ_count) {
326 DCHECK_NE(BasicBlock::kNone, block->control());
327 DCHECK_EQ(BasicBlock::kNone, end->control());
328 end->set_control(block->control());
329 block->set_control(BasicBlock::kSwitch);
330 MoveSuccessors(block, end);
331 for (size_t index = 0; index < succ_count; ++index) {
332 AddSuccessor(block, succ_blocks[index]);
333 }
334 if (block->control_input() != nullptr) {
335 SetControlInput(end, block->control_input());
336 }
337 SetControlInput(block, sw);
338 }
339
EnsureCFGWellFormedness()340 void Schedule::EnsureCFGWellFormedness() {
341 // Make a copy of all the blocks for the iteration, since adding the split
342 // edges will allocate new blocks.
343 BasicBlockVector all_blocks_copy(all_blocks_);
344
345 // Insert missing split edge blocks.
346 for (auto block : all_blocks_copy) {
347 if (block->PredecessorCount() > 1) {
348 if (block != end_) {
349 EnsureSplitEdgeForm(block);
350 }
351 if (block->deferred()) {
352 EnsureDeferredCodeSingleEntryPoint(block);
353 }
354 } else {
355 EliminateNoopPhiNodes(block);
356 }
357 }
358 }
359
EliminateNoopPhiNodes(BasicBlock * block)360 void Schedule::EliminateNoopPhiNodes(BasicBlock* block) {
361 // Ensure that useless phi nodes in blocks that only have a single predecessor
362 // -- which can happen with the automatically generated code in the CSA and
363 // torque -- are pruned.
364 if (block->PredecessorCount() == 1) {
365 for (size_t i = 0; i < block->NodeCount();) {
366 Node* node = block->NodeAt(i);
367 if (node->opcode() == IrOpcode::kPhi) {
368 node->ReplaceUses(node->InputAt(0));
369 block->RemoveNode(block->begin() + i);
370 } else {
371 ++i;
372 }
373 }
374 }
375 }
376
EnsureSplitEdgeForm(BasicBlock * block)377 void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
378 DCHECK(block->PredecessorCount() > 1 && block != end_);
379 for (auto current_pred = block->predecessors().begin();
380 current_pred != block->predecessors().end(); ++current_pred) {
381 BasicBlock* pred = *current_pred;
382 if (pred->SuccessorCount() > 1) {
383 // Found a predecessor block with multiple successors.
384 BasicBlock* split_edge_block = NewBasicBlock();
385 split_edge_block->set_control(BasicBlock::kGoto);
386 split_edge_block->successors().push_back(block);
387 split_edge_block->predecessors().push_back(pred);
388 split_edge_block->set_deferred(block->deferred());
389 *current_pred = split_edge_block;
390 // Find a corresponding successor in the previous block, replace it
391 // with the split edge block... but only do it once, since we only
392 // replace the previous blocks in the current block one at a time.
393 for (auto successor = pred->successors().begin();
394 successor != pred->successors().end(); ++successor) {
395 if (*successor == block) {
396 *successor = split_edge_block;
397 break;
398 }
399 }
400 }
401 }
402 }
403
EnsureDeferredCodeSingleEntryPoint(BasicBlock * block)404 void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
405 // If a deferred block has multiple predecessors, they have to
406 // all be deferred. Otherwise, we can run into a situation where a range
407 // that spills only in deferred blocks inserts its spill in the block, but
408 // other ranges need moves inserted by ResolveControlFlow in the predecessors,
409 // which may clobber the register of this range.
410 // To ensure that, when a deferred block has multiple predecessors, and some
411 // are not deferred, we add a non-deferred block to collect all such edges.
412
413 DCHECK(block->deferred() && block->PredecessorCount() > 1);
414 bool all_deferred = true;
415 for (auto current_pred = block->predecessors().begin();
416 current_pred != block->predecessors().end(); ++current_pred) {
417 BasicBlock* pred = *current_pred;
418 if (!pred->deferred()) {
419 all_deferred = false;
420 break;
421 }
422 }
423
424 if (all_deferred) return;
425 BasicBlock* merger = NewBasicBlock();
426 merger->set_control(BasicBlock::kGoto);
427 merger->successors().push_back(block);
428 for (auto current_pred = block->predecessors().begin();
429 current_pred != block->predecessors().end(); ++current_pred) {
430 BasicBlock* pred = *current_pred;
431 merger->predecessors().push_back(pred);
432 pred->successors().clear();
433 pred->successors().push_back(merger);
434 }
435 merger->set_deferred(false);
436 block->predecessors().clear();
437 block->predecessors().push_back(merger);
438 MovePhis(block, merger);
439 }
440
MovePhis(BasicBlock * from,BasicBlock * to)441 void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
442 for (size_t i = 0; i < from->NodeCount();) {
443 Node* node = from->NodeAt(i);
444 if (node->opcode() == IrOpcode::kPhi) {
445 to->AddNode(node);
446 from->RemoveNode(from->begin() + i);
447 DCHECK_EQ(nodeid_to_block_[node->id()], from);
448 nodeid_to_block_[node->id()] = to;
449 } else {
450 ++i;
451 }
452 }
453 }
454
PropagateDeferredMark()455 void Schedule::PropagateDeferredMark() {
456 // Push forward the deferred block marks through newly inserted blocks and
457 // other improperly marked blocks until a fixed point is reached.
458 // TODO(danno): optimize the propagation
459 bool done = false;
460 while (!done) {
461 done = true;
462 for (auto block : all_blocks_) {
463 if (!block->deferred()) {
464 bool deferred = block->PredecessorCount() > 0;
465 for (auto pred : block->predecessors()) {
466 if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
467 deferred = false;
468 }
469 }
470 if (deferred) {
471 block->set_deferred(true);
472 done = false;
473 }
474 }
475 }
476 }
477 }
478
AddSuccessor(BasicBlock * block,BasicBlock * succ)479 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
480 block->AddSuccessor(succ);
481 succ->AddPredecessor(block);
482 }
483
484
MoveSuccessors(BasicBlock * from,BasicBlock * to)485 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
486 for (BasicBlock* const successor : from->successors()) {
487 to->AddSuccessor(successor);
488 for (BasicBlock*& predecessor : successor->predecessors()) {
489 if (predecessor == from) predecessor = to;
490 }
491 }
492 from->ClearSuccessors();
493 }
494
495
SetControlInput(BasicBlock * block,Node * node)496 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
497 block->set_control_input(node);
498 SetBlockForNode(block, node);
499 }
500
501
SetBlockForNode(BasicBlock * block,Node * node)502 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
503 if (node->id() >= nodeid_to_block_.size()) {
504 nodeid_to_block_.resize(node->id() + 1);
505 }
506 nodeid_to_block_[node->id()] = block;
507 }
508
509
operator <<(std::ostream & os,const Schedule & s)510 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
511 for (BasicBlock* block :
512 ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
513 if (block->rpo_number() == -1) {
514 os << "--- BLOCK id:" << block->id().ToInt();
515 } else {
516 os << "--- BLOCK B" << block->rpo_number();
517 }
518 if (block->deferred()) os << " (deferred)";
519 if (block->PredecessorCount() != 0) os << " <- ";
520 bool comma = false;
521 for (BasicBlock const* predecessor : block->predecessors()) {
522 if (comma) os << ", ";
523 comma = true;
524 if (predecessor->rpo_number() == -1) {
525 os << "id:" << predecessor->id().ToInt();
526 } else {
527 os << "B" << predecessor->rpo_number();
528 }
529 }
530 os << " ---\n";
531 for (Node* node : *block) {
532 os << " " << *node;
533 if (NodeProperties::IsTyped(node)) {
534 os << " : " << NodeProperties::GetType(node);
535 }
536 os << "\n";
537 }
538 BasicBlock::Control control = block->control();
539 if (control != BasicBlock::kNone) {
540 os << " ";
541 if (block->control_input() != nullptr) {
542 os << *block->control_input();
543 } else {
544 os << "Goto";
545 }
546 os << " -> ";
547 comma = false;
548 for (BasicBlock const* successor : block->successors()) {
549 if (comma) os << ", ";
550 comma = true;
551 if (successor->rpo_number() == -1) {
552 os << "id:" << successor->id().ToInt();
553 } else {
554 os << "B" << successor->rpo_number();
555 }
556 }
557 os << "\n";
558 }
559 }
560 return os;
561 }
562
563 } // namespace compiler
564 } // namespace internal
565 } // namespace v8
566