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