Line data Source code
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.h"
8 : #include "src/compiler/node-properties.h"
9 : #include "src/ostreams.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 : namespace compiler {
14 :
15 1311610 : 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 34829472 : id_(id) {
34 1311610 : }
35 :
36 1438 : bool BasicBlock::LoopContains(BasicBlock* block) const {
37 : // RPO numbers must be initialized.
38 : DCHECK(rpo_number_ >= 0);
39 : DCHECK(block->rpo_number_ >= 0);
40 1438 : if (loop_end_ == nullptr) return false; // This is not a loop.
41 2876 : return block->rpo_number_ >= rpo_number_ &&
42 2876 : block->rpo_number_ < loop_end_->rpo_number_;
43 : }
44 :
45 :
46 0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
47 19474234 : successors_.push_back(successor);
48 0 : }
49 :
50 :
51 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
52 19177181 : predecessors_.push_back(predecessor);
53 0 : }
54 :
55 :
56 95030052 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
57 :
58 :
59 0 : void BasicBlock::set_control(Control control) {
60 14781568 : control_ = control;
61 0 : }
62 :
63 :
64 0 : void BasicBlock::set_control_input(Node* control_input) {
65 7028155 : control_input_ = control_input;
66 0 : }
67 :
68 :
69 16305869 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
70 16305869 : loop_depth_ = loop_depth;
71 16305869 : }
72 :
73 :
74 78308450 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
75 78308450 : rpo_number_ = rpo_number;
76 78308450 : }
77 :
78 :
79 147259 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
80 :
81 :
82 16305827 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
83 16305827 : loop_header_ = loop_header;
84 16305827 : }
85 :
86 :
87 : // static
88 1135100524 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
89 755980430 : while (b1 != b2) {
90 561910340 : if (b1->dominator_depth() < b2->dominator_depth()) {
91 : b2 = b2->dominator();
92 : } else {
93 : b1 = b1->dominator();
94 : }
95 : }
96 97035045 : return b1;
97 : }
98 :
99 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
100 0 : os << "B" << block.id();
101 : #if DEBUG
102 : AssemblerDebugInfo info = block.debug_info();
103 : if (info.name) os << info;
104 : // Print predecessor blocks for better debugging.
105 : const int kMaxDisplayedBlocks = 4;
106 : int i = 0;
107 : const BasicBlock* current_block = █
108 : while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
109 : current_block = current_block->predecessors().front();
110 : os << " <= B" << current_block->id();
111 : info = current_block->debug_info();
112 : if (info.name) os << info;
113 : }
114 : #endif
115 0 : return os;
116 : }
117 :
118 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
119 0 : switch (c) {
120 : case BasicBlock::kNone:
121 0 : return os << "none";
122 : case BasicBlock::kGoto:
123 0 : return os << "goto";
124 : case BasicBlock::kCall:
125 0 : return os << "call";
126 : case BasicBlock::kBranch:
127 0 : return os << "branch";
128 : case BasicBlock::kSwitch:
129 0 : return os << "switch";
130 : case BasicBlock::kDeoptimize:
131 0 : return os << "deoptimize";
132 : case BasicBlock::kTailCall:
133 0 : return os << "tailcall";
134 : case BasicBlock::kReturn:
135 0 : return os << "return";
136 : case BasicBlock::kThrow:
137 0 : return os << "throw";
138 : }
139 0 : UNREACHABLE();
140 : return os;
141 : }
142 :
143 :
144 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
145 0 : return os << id.ToSize();
146 : }
147 :
148 :
149 1315747 : Schedule::Schedule(Zone* zone, size_t node_count_hint)
150 : : zone_(zone),
151 : all_blocks_(zone),
152 : nodeid_to_block_(zone),
153 : rpo_order_(zone),
154 1315747 : start_(NewBasicBlock()),
155 2631464 : end_(NewBasicBlock()) {
156 1315744 : nodeid_to_block_.reserve(node_count_hint);
157 1315740 : }
158 :
159 :
160 252951572 : BasicBlock* Schedule::block(Node* node) const {
161 505903143 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
162 503013368 : return nodeid_to_block_[node->id()];
163 : }
164 : return nullptr;
165 : }
166 :
167 :
168 314911892 : bool Schedule::IsScheduled(Node* node) {
169 629823784 : if (node->id() >= nodeid_to_block_.size()) return false;
170 303696076 : return nodeid_to_block_[node->id()] != nullptr;
171 : }
172 :
173 :
174 12870449 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
175 : DCHECK(block_id.ToSize() < all_blocks_.size());
176 25740898 : return all_blocks_[block_id.ToSize()];
177 : }
178 :
179 :
180 1 : bool Schedule::SameBasicBlock(Node* a, Node* b) const {
181 : BasicBlock* block = this->block(a);
182 2 : return block != nullptr && block == this->block(b);
183 : }
184 :
185 :
186 16103140 : BasicBlock* Schedule::NewBasicBlock() {
187 : BasicBlock* block = new (zone_)
188 64412532 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
189 16103126 : all_blocks_.push_back(block);
190 16103396 : return block;
191 : }
192 :
193 :
194 60270419 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
195 60270419 : if (FLAG_trace_turbo_scheduler) {
196 0 : OFStream os(stdout);
197 0 : os << "Planning #" << node->id() << ":" << node->op()->mnemonic()
198 0 : << " for future add to B" << block->id() << "\n";
199 : }
200 : DCHECK(this->block(node) == nullptr);
201 60270419 : SetBlockForNode(block, node);
202 60270893 : }
203 :
204 :
205 95030052 : void Schedule::AddNode(BasicBlock* block, Node* node) {
206 95030052 : if (FLAG_trace_turbo_scheduler) {
207 0 : OFStream os(stdout);
208 0 : os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B"
209 0 : << block->id() << "\n";
210 : }
211 : DCHECK(this->block(node) == nullptr || this->block(node) == block);
212 : block->AddNode(node);
213 95028801 : SetBlockForNode(block, node);
214 95029469 : }
215 :
216 :
217 7214215 : void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
218 : DCHECK_EQ(BasicBlock::kNone, block->control());
219 : block->set_control(BasicBlock::kGoto);
220 7214215 : AddSuccessor(block, succ);
221 7214213 : }
222 :
223 : #if DEBUG
224 : namespace {
225 :
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 : return true;
233 : default:
234 : return false;
235 : }
236 : }
237 :
238 : } // namespace
239 : #endif // DEBUG
240 :
241 463906 : void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
242 : BasicBlock* exception_block) {
243 : DCHECK_EQ(BasicBlock::kNone, block->control());
244 : DCHECK(IsPotentiallyThrowingCall(call->opcode()));
245 : block->set_control(BasicBlock::kCall);
246 463906 : AddSuccessor(block, success_block);
247 463906 : AddSuccessor(block, exception_block);
248 : SetControlInput(block, call);
249 463906 : }
250 :
251 :
252 4282121 : void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
253 : BasicBlock* fblock) {
254 : DCHECK_EQ(BasicBlock::kNone, block->control());
255 : DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
256 : block->set_control(BasicBlock::kBranch);
257 4282121 : AddSuccessor(block, tblock);
258 4282150 : AddSuccessor(block, fblock);
259 : SetControlInput(block, branch);
260 4282187 : }
261 :
262 :
263 23140 : void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
264 : size_t succ_count) {
265 : DCHECK_EQ(BasicBlock::kNone, block->control());
266 : DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
267 : block->set_control(BasicBlock::kSwitch);
268 191444 : for (size_t index = 0; index < succ_count; ++index) {
269 168304 : AddSuccessor(block, succ_blocks[index]);
270 : }
271 : SetControlInput(block, sw);
272 23140 : }
273 :
274 :
275 298454 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
276 : DCHECK_EQ(BasicBlock::kNone, block->control());
277 : block->set_control(BasicBlock::kTailCall);
278 : SetControlInput(block, input);
279 149227 : if (block != end()) AddSuccessor(block, end());
280 149227 : }
281 :
282 :
283 3239916 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
284 : DCHECK_EQ(BasicBlock::kNone, block->control());
285 : block->set_control(BasicBlock::kReturn);
286 : SetControlInput(block, input);
287 1619972 : if (block != end()) AddSuccessor(block, end());
288 1619952 : }
289 :
290 :
291 60260 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
292 : DCHECK_EQ(BasicBlock::kNone, block->control());
293 : block->set_control(BasicBlock::kDeoptimize);
294 : SetControlInput(block, input);
295 30130 : if (block != end()) AddSuccessor(block, end());
296 30130 : }
297 :
298 :
299 142280 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
300 : DCHECK_EQ(BasicBlock::kNone, block->control());
301 : block->set_control(BasicBlock::kThrow);
302 : SetControlInput(block, input);
303 71140 : if (block != end()) AddSuccessor(block, end());
304 71140 : }
305 :
306 :
307 430059 : void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
308 : BasicBlock* tblock, BasicBlock* fblock) {
309 : DCHECK_NE(BasicBlock::kNone, block->control());
310 : DCHECK_EQ(BasicBlock::kNone, end->control());
311 : end->set_control(block->control());
312 : block->set_control(BasicBlock::kBranch);
313 215029 : MoveSuccessors(block, end);
314 215032 : AddSuccessor(block, tblock);
315 215030 : AddSuccessor(block, fblock);
316 215030 : if (block->control_input() != nullptr) {
317 : SetControlInput(end, block->control_input());
318 : }
319 : SetControlInput(block, branch);
320 215027 : }
321 :
322 :
323 2 : void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
324 : BasicBlock** succ_blocks, size_t succ_count) {
325 : DCHECK_NE(BasicBlock::kNone, block->control());
326 : DCHECK_EQ(BasicBlock::kNone, end->control());
327 : end->set_control(block->control());
328 : block->set_control(BasicBlock::kSwitch);
329 1 : MoveSuccessors(block, end);
330 4 : for (size_t index = 0; index < succ_count; ++index) {
331 3 : AddSuccessor(block, succ_blocks[index]);
332 : }
333 1 : if (block->control_input() != nullptr) {
334 : SetControlInput(end, block->control_input());
335 : }
336 : SetControlInput(block, sw);
337 1 : }
338 :
339 347839 : void Schedule::EnsureCFGWellFormedness() {
340 : // Make a copy of all the blocks for the iteration, since adding the split
341 : // edges will allocate new blocks.
342 : BasicBlockVector all_blocks_copy(all_blocks_);
343 :
344 : // Insert missing split edge blocks.
345 3760511 : for (auto block : all_blocks_copy) {
346 2510293 : if (block->PredecessorCount() > 1) {
347 554538 : if (block != end_) {
348 490632 : EnsureSplitEdgeForm(block);
349 : }
350 554539 : if (block->deferred()) {
351 15681 : EnsureDeferredCodeSingleEntryPoint(block);
352 : }
353 : }
354 : }
355 347840 : }
356 :
357 490632 : void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
358 : DCHECK(block->PredecessorCount() > 1 && block != end_);
359 3564912 : for (auto current_pred = block->predecessors().begin();
360 1873341 : current_pred != block->predecessors().end(); ++current_pred) {
361 1382709 : BasicBlock* pred = *current_pred;
362 1382709 : if (pred->SuccessorCount() > 1) {
363 : // Found a predecessor block with multiple successors.
364 710307 : BasicBlock* split_edge_block = NewBasicBlock();
365 : split_edge_block->set_control(BasicBlock::kGoto);
366 710307 : split_edge_block->successors().push_back(block);
367 710307 : split_edge_block->predecessors().push_back(pred);
368 710307 : split_edge_block->set_deferred(block->deferred());
369 710307 : *current_pred = split_edge_block;
370 : // Find a corresponding successor in the previous block, replace it
371 : // with the split edge block... but only do it once, since we only
372 : // replace the previous blocks in the current block one at a time.
373 2481930 : for (auto successor = pred->successors().begin();
374 : successor != pred->successors().end(); ++successor) {
375 1061316 : if (*successor == block) {
376 710307 : *successor = split_edge_block;
377 710307 : break;
378 : }
379 : }
380 : }
381 : }
382 490632 : }
383 :
384 15681 : void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
385 : // If a deferred block has multiple predecessors, they have to
386 : // all be deferred. Otherwise, we can run into a situation where a range
387 : // that spills only in deferred blocks inserts its spill in the block, but
388 : // other ranges need moves inserted by ResolveControlFlow in the predecessors,
389 : // which may clobber the register of this range.
390 : // To ensure that, when a deferred block has multiple predecessors, and some
391 : // are not deferred, we add a non-deferred block to collect all such edges.
392 :
393 : DCHECK(block->deferred() && block->PredecessorCount() > 1);
394 : bool all_deferred = true;
395 105938 : for (auto current_pred = block->predecessors().begin();
396 : current_pred != block->predecessors().end(); ++current_pred) {
397 61303 : BasicBlock* pred = *current_pred;
398 61303 : if (!pred->deferred()) {
399 : all_deferred = false;
400 : break;
401 : }
402 : }
403 :
404 28954 : if (all_deferred) return;
405 2408 : BasicBlock* merger = NewBasicBlock();
406 : merger->set_control(BasicBlock::kGoto);
407 2408 : merger->successors().push_back(block);
408 34099 : for (auto current_pred = block->predecessors().begin();
409 29283 : current_pred != block->predecessors().end(); ++current_pred) {
410 26875 : BasicBlock* pred = *current_pred;
411 26875 : merger->predecessors().push_back(pred);
412 26875 : pred->successors().clear();
413 26875 : pred->successors().push_back(merger);
414 : }
415 2408 : merger->set_deferred(false);
416 : block->predecessors().clear();
417 2408 : block->predecessors().push_back(merger);
418 : }
419 :
420 347840 : void Schedule::PropagateDeferredMark() {
421 : // Push forward the deferred block marks through newly inserted blocks and
422 : // other improperly marked blocks until a fixed point is reached.
423 : // TODO(danno): optimize the propagation
424 : bool done = false;
425 1094823 : while (!done) {
426 : done = true;
427 14046739 : for (auto block : all_blocks_) {
428 7157919 : if (!block->deferred()) {
429 5309672 : bool deferred = block->PredecessorCount() > 0;
430 23731223 : for (auto pred : block->predecessors()) {
431 13111879 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
432 : deferred = false;
433 : }
434 : }
435 5309672 : if (deferred) {
436 : block->set_deferred(true);
437 : done = false;
438 : }
439 : }
440 : }
441 : }
442 347840 : }
443 :
444 19177141 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
445 : block->AddSuccessor(succ);
446 : succ->AddPredecessor(block);
447 19177174 : }
448 :
449 :
450 215031 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
451 727157 : for (BasicBlock* const successor : from->successors()) {
452 : to->AddSuccessor(successor);
453 1665777 : for (BasicBlock*& predecessor : successor->predecessors()) {
454 1071587 : if (predecessor == from) predecessor = to;
455 : }
456 : }
457 : from->ClearSuccessors();
458 215033 : }
459 :
460 :
461 0 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
462 : block->set_control_input(node);
463 7028155 : SetBlockForNode(block, node);
464 0 : }
465 :
466 :
467 331015683 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
468 496523493 : if (node->id() >= nodeid_to_block_.size()) {
469 24111110 : nodeid_to_block_.resize(node->id() + 1);
470 : }
471 331015746 : nodeid_to_block_[node->id()] = block;
472 165507873 : }
473 :
474 :
475 14 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
476 364 : for (BasicBlock* block :
477 84 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
478 70 : if (block->rpo_number() == -1) {
479 0 : os << "--- BLOCK id:" << block->id().ToInt();
480 : } else {
481 70 : os << "--- BLOCK B" << block->rpo_number();
482 : }
483 70 : if (block->deferred()) os << " (deferred)";
484 70 : if (block->PredecessorCount() != 0) os << " <- ";
485 : bool comma = false;
486 280 : for (BasicBlock const* predecessor : block->predecessors()) {
487 70 : if (comma) os << ", ";
488 : comma = true;
489 70 : if (predecessor->rpo_number() == -1) {
490 0 : os << "id:" << predecessor->id().ToInt();
491 : } else {
492 70 : os << "B" << predecessor->rpo_number();
493 : }
494 : }
495 70 : os << " ---\n";
496 196 : for (Node* node : *block) {
497 56 : os << " " << *node;
498 56 : if (NodeProperties::IsTyped(node)) {
499 : Type* type = NodeProperties::GetType(node);
500 0 : os << " : ";
501 0 : type->PrintTo(os);
502 : }
503 56 : os << "\n";
504 : }
505 : BasicBlock::Control control = block->control();
506 70 : if (control != BasicBlock::kNone) {
507 56 : os << " ";
508 56 : if (block->control_input() != nullptr) {
509 28 : os << *block->control_input();
510 : } else {
511 28 : os << "Goto";
512 : }
513 56 : os << " -> ";
514 : comma = false;
515 252 : for (BasicBlock const* successor : block->successors()) {
516 70 : if (comma) os << ", ";
517 : comma = true;
518 70 : if (successor->rpo_number() == -1) {
519 0 : os << "id:" << successor->id().ToInt();
520 : } else {
521 70 : os << "B" << successor->rpo_number();
522 : }
523 : }
524 56 : os << "\n";
525 : }
526 : }
527 14 : return os;
528 : }
529 :
530 : } // namespace compiler
531 : } // namespace internal
532 : } // namespace v8
|
