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 | |
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 | |
36 | 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 | void BasicBlock::AddSuccessor(BasicBlock* successor) { |
46 | successors_.push_back(successor); |
47 | } |
48 | |
49 | void BasicBlock::AddPredecessor(BasicBlock* predecessor) { |
50 | predecessors_.push_back(predecessor); |
51 | } |
52 | |
53 | void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); } |
54 | |
55 | void BasicBlock::set_control(Control control) { control_ = control; } |
56 | |
57 | void 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 | |
64 | void BasicBlock::set_loop_depth(int32_t loop_depth) { |
65 | loop_depth_ = loop_depth; |
66 | } |
67 | |
68 | void BasicBlock::set_rpo_number(int32_t rpo_number) { |
69 | rpo_number_ = rpo_number; |
70 | } |
71 | |
72 | void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; } |
73 | |
74 | void BasicBlock::(BasicBlock* ) { |
75 | loop_header_ = loop_header; |
76 | } |
77 | |
78 | // static |
79 | BasicBlock* 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 | |
90 | void BasicBlock::Print() { StdoutStream{} << this; } |
91 | |
92 | std::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 = █ |
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 | |
111 | std::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 | |
135 | std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) { |
136 | return os << id.ToSize(); |
137 | } |
138 | |
139 | Schedule::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 | |
149 | BasicBlock* 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 | |
156 | bool Schedule::IsScheduled(Node* node) { |
157 | if (node->id() >= nodeid_to_block_.size()) return false; |
158 | return nodeid_to_block_[node->id()] != nullptr; |
159 | } |
160 | |
161 | BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) { |
162 | DCHECK(block_id.ToSize() < all_blocks_.size()); |
163 | return all_blocks_[block_id.ToSize()]; |
164 | } |
165 | |
166 | bool Schedule::SameBasicBlock(Node* a, Node* b) const { |
167 | BasicBlock* block = this->block(a); |
168 | return block != nullptr && block == this->block(b); |
169 | } |
170 | |
171 | BasicBlock* 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 | |
178 | void 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 | |
188 | void 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 | |
198 | void 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 |
205 | namespace { |
206 | |
207 | bool 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 | |
223 | void 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 | |
233 | void 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 | |
243 | void 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 | |
254 | void 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 | |
261 | void 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 | |
268 | void 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 | |
275 | void 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 | |
282 | void 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 | |
297 | void 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 | |
313 | void 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 | |
333 | void 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 | |
368 | void 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 | |
379 | void 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 | |
416 | void 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 | |
430 | void 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 | |
454 | void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) { |
455 | block->AddSuccessor(succ); |
456 | succ->AddPredecessor(block); |
457 | } |
458 | |
459 | void 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 | |
469 | void Schedule::SetControlInput(BasicBlock* block, Node* node) { |
470 | block->set_control_input(node); |
471 | SetBlockForNode(block, node); |
472 | } |
473 | |
474 | void 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 | |
481 | std::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 | |