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-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 1722087 : 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 35222256 : id_(id) {
34 1722087 : }
35 :
36 1438 : 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 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 18929377 : successors_.push_back(successor);
48 0 : }
49 :
50 :
51 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
52 18538498 : predecessors_.push_back(predecessor);
53 0 : }
54 :
55 :
56 100752089 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
57 :
58 :
59 0 : void BasicBlock::set_control(Control control) {
60 14158297 : control_ = control;
61 0 : }
62 :
63 :
64 0 : void BasicBlock::set_control_input(Node* control_input) {
65 7164944 : control_input_ = control_input;
66 0 : }
67 :
68 :
69 16150261 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
70 16150261 : loop_depth_ = loop_depth;
71 16150261 : }
72 :
73 :
74 76005099 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
75 76005099 : rpo_number_ = rpo_number;
76 76005099 : }
77 :
78 :
79 136748 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
80 :
81 :
82 16150169 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
83 16150169 : loop_header_ = loop_header;
84 16150169 : }
85 :
86 :
87 : // static
88 969581531 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
89 680859162 : while (b1 != b2) {
90 462622172 : if (b1->dominator_depth() < b2->dominator_depth()) {
91 : b2 = b2->dominator();
92 : } else {
93 : b1 = b1->dominator();
94 : }
95 : }
96 109118495 : return b1;
97 : }
98 :
99 0 : void BasicBlock::Print() { OFStream(stdout) << this; }
100 :
101 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
102 0 : 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 0 : return os;
118 : }
119 :
120 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
121 0 : switch (c) {
122 : case BasicBlock::kNone:
123 0 : return os << "none";
124 : case BasicBlock::kGoto:
125 0 : return os << "goto";
126 : case BasicBlock::kCall:
127 0 : return os << "call";
128 : case BasicBlock::kBranch:
129 0 : return os << "branch";
130 : case BasicBlock::kSwitch:
131 0 : return os << "switch";
132 : case BasicBlock::kDeoptimize:
133 0 : return os << "deoptimize";
134 : case BasicBlock::kTailCall:
135 0 : return os << "tailcall";
136 : case BasicBlock::kReturn:
137 0 : return os << "return";
138 : case BasicBlock::kThrow:
139 0 : return os << "throw";
140 : }
141 0 : UNREACHABLE();
142 : }
143 :
144 :
145 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
146 0 : return os << id.ToSize();
147 : }
148 :
149 :
150 1725514 : 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 1725514 : start_(NewBasicBlock()),
156 3451050 : end_(NewBasicBlock()) {
157 1725555 : nodeid_to_block_.reserve(node_count_hint);
158 1725535 : }
159 :
160 :
161 284182637 : BasicBlock* Schedule::block(Node* node) const {
162 568365273 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
163 565060558 : return nodeid_to_block_[node->id()];
164 : }
165 : return nullptr;
166 : }
167 :
168 :
169 360753371 : bool Schedule::IsScheduled(Node* node) {
170 721506742 : if (node->id() >= nodeid_to_block_.size()) return false;
171 348371900 : return nodeid_to_block_[node->id()] != nullptr;
172 : }
173 :
174 :
175 13799790 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
176 : DCHECK(block_id.ToSize() < all_blocks_.size());
177 27599580 : return all_blocks_[block_id.ToSize()];
178 : }
179 :
180 :
181 1 : bool Schedule::SameBasicBlock(Node* a, Node* b) const {
182 : BasicBlock* block = this->block(a);
183 2 : return block != nullptr && block == this->block(b);
184 : }
185 :
186 :
187 15889026 : BasicBlock* Schedule::NewBasicBlock() {
188 : BasicBlock* block = new (zone_)
189 63556134 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
190 15889041 : all_blocks_.push_back(block);
191 15889230 : return block;
192 : }
193 :
194 :
195 69004971 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
196 69004971 : if (FLAG_trace_turbo_scheduler) {
197 0 : OFStream os(stdout);
198 0 : os << "Planning #" << node->id() << ":" << node->op()->mnemonic()
199 0 : << " for future add to B" << block->id() << "\n";
200 : }
201 : DCHECK_NULL(this->block(node));
202 69004971 : SetBlockForNode(block, node);
203 69005193 : }
204 :
205 :
206 100744990 : void Schedule::AddNode(BasicBlock* block, Node* node) {
207 100744990 : if (FLAG_trace_turbo_scheduler) {
208 0 : OFStream os(stdout);
209 0 : os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B"
210 0 : << block->id() << "\n";
211 : }
212 : DCHECK(this->block(node) == nullptr || this->block(node) == block);
213 : block->AddNode(node);
214 100743643 : SetBlockForNode(block, node);
215 100744190 : }
216 :
217 :
218 6792000 : void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
219 : DCHECK_EQ(BasicBlock::kNone, block->control());
220 : block->set_control(BasicBlock::kGoto);
221 6792000 : AddSuccessor(block, succ);
222 6791975 : }
223 :
224 : #if DEBUG
225 : namespace {
226 :
227 : bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
228 : switch (opcode) {
229 : #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
230 : JS_OP_LIST(BUILD_BLOCK_JS_CASE)
231 : #undef BUILD_BLOCK_JS_CASE
232 : case IrOpcode::kCall:
233 : case IrOpcode::kCallWithCallerSavedRegisters:
234 : return true;
235 : default:
236 : return false;
237 : }
238 : }
239 :
240 : } // namespace
241 : #endif // DEBUG
242 :
243 306596 : void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
244 : BasicBlock* exception_block) {
245 : DCHECK_EQ(BasicBlock::kNone, block->control());
246 : DCHECK(IsPotentiallyThrowingCall(call->opcode()));
247 : block->set_control(BasicBlock::kCall);
248 306596 : AddSuccessor(block, success_block);
249 306596 : AddSuccessor(block, exception_block);
250 : SetControlInput(block, call);
251 306596 : }
252 :
253 :
254 3893258 : void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
255 : BasicBlock* fblock) {
256 : DCHECK_EQ(BasicBlock::kNone, block->control());
257 : DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
258 : block->set_control(BasicBlock::kBranch);
259 3893258 : AddSuccessor(block, tblock);
260 3893317 : AddSuccessor(block, fblock);
261 : SetControlInput(block, branch);
262 3893322 : }
263 :
264 :
265 31191 : void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
266 : size_t succ_count) {
267 : DCHECK_EQ(BasicBlock::kNone, block->control());
268 : DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
269 : block->set_control(BasicBlock::kSwitch);
270 413527 : for (size_t index = 0; index < succ_count; ++index) {
271 382336 : AddSuccessor(block, succ_blocks[index]);
272 : }
273 : SetControlInput(block, sw);
274 31191 : }
275 :
276 :
277 331838 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
278 : DCHECK_EQ(BasicBlock::kNone, block->control());
279 : block->set_control(BasicBlock::kTailCall);
280 : SetControlInput(block, input);
281 165919 : if (block != end()) AddSuccessor(block, end());
282 165919 : }
283 :
284 :
285 4046931 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
286 : DCHECK_EQ(BasicBlock::kNone, block->control());
287 : block->set_control(BasicBlock::kReturn);
288 : SetControlInput(block, input);
289 2023522 : if (block != end()) AddSuccessor(block, end());
290 2023507 : }
291 :
292 :
293 198634 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
294 : DCHECK_EQ(BasicBlock::kNone, block->control());
295 : block->set_control(BasicBlock::kDeoptimize);
296 : SetControlInput(block, input);
297 99317 : if (block != end()) AddSuccessor(block, end());
298 99317 : }
299 :
300 :
301 261146 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
302 : DCHECK_EQ(BasicBlock::kNone, block->control());
303 : block->set_control(BasicBlock::kThrow);
304 : SetControlInput(block, input);
305 130573 : if (block != end()) AddSuccessor(block, end());
306 130573 : }
307 :
308 :
309 543058 : void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
310 : BasicBlock* tblock, BasicBlock* fblock) {
311 : DCHECK_NE(BasicBlock::kNone, block->control());
312 : DCHECK_EQ(BasicBlock::kNone, end->control());
313 : end->set_control(block->control());
314 : block->set_control(BasicBlock::kBranch);
315 271528 : MoveSuccessors(block, end);
316 271529 : AddSuccessor(block, tblock);
317 271530 : AddSuccessor(block, fblock);
318 271530 : if (block->control_input() != nullptr) {
319 : SetControlInput(end, block->control_input());
320 : }
321 : SetControlInput(block, branch);
322 271530 : }
323 :
324 :
325 2 : void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
326 : BasicBlock** succ_blocks, size_t succ_count) {
327 : DCHECK_NE(BasicBlock::kNone, block->control());
328 : DCHECK_EQ(BasicBlock::kNone, end->control());
329 : end->set_control(block->control());
330 : block->set_control(BasicBlock::kSwitch);
331 1 : MoveSuccessors(block, end);
332 4 : for (size_t index = 0; index < succ_count; ++index) {
333 3 : AddSuccessor(block, succ_blocks[index]);
334 : }
335 1 : if (block->control_input() != nullptr) {
336 : SetControlInput(end, block->control_input());
337 : }
338 : SetControlInput(block, sw);
339 1 : }
340 :
341 265724 : void Schedule::EnsureCFGWellFormedness() {
342 : // Make a copy of all the blocks for the iteration, since adding the split
343 : // edges will allocate new blocks.
344 : BasicBlockVector all_blocks_copy(all_blocks_);
345 :
346 : // Insert missing split edge blocks.
347 2491041 : for (auto block : all_blocks_copy) {
348 1636837 : if (block->PredecessorCount() > 1) {
349 322756 : if (block != end_) {
350 291103 : EnsureSplitEdgeForm(block);
351 : }
352 322756 : if (block->deferred()) {
353 17718 : EnsureDeferredCodeSingleEntryPoint(block);
354 : }
355 : }
356 : }
357 265724 : }
358 :
359 291103 : void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
360 : DCHECK(block->PredecessorCount() > 1 && block != end_);
361 2170191 : for (auto current_pred = block->predecessors().begin();
362 1147206 : current_pred != block->predecessors().end(); ++current_pred) {
363 856103 : BasicBlock* pred = *current_pred;
364 856103 : if (pred->SuccessorCount() > 1) {
365 : // Found a predecessor block with multiple successors.
366 440779 : BasicBlock* split_edge_block = NewBasicBlock();
367 : split_edge_block->set_control(BasicBlock::kGoto);
368 440779 : split_edge_block->successors().push_back(block);
369 440779 : split_edge_block->predecessors().push_back(pred);
370 440779 : split_edge_block->set_deferred(block->deferred());
371 440779 : *current_pred = split_edge_block;
372 : // Find a corresponding successor in the previous block, replace it
373 : // with the split edge block... but only do it once, since we only
374 : // replace the previous blocks in the current block one at a time.
375 1506335 : for (auto successor = pred->successors().begin();
376 : successor != pred->successors().end(); ++successor) {
377 624777 : if (*successor == block) {
378 440779 : *successor = split_edge_block;
379 440779 : break;
380 : }
381 : }
382 : }
383 : }
384 291103 : }
385 :
386 17718 : void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
387 : // If a deferred block has multiple predecessors, they have to
388 : // all be deferred. Otherwise, we can run into a situation where a range
389 : // that spills only in deferred blocks inserts its spill in the block, but
390 : // other ranges need moves inserted by ResolveControlFlow in the predecessors,
391 : // which may clobber the register of this range.
392 : // To ensure that, when a deferred block has multiple predecessors, and some
393 : // are not deferred, we add a non-deferred block to collect all such edges.
394 :
395 : DCHECK(block->deferred() && block->PredecessorCount() > 1);
396 : bool all_deferred = true;
397 127301 : for (auto current_pred = block->predecessors().begin();
398 : current_pred != block->predecessors().end(); ++current_pred) {
399 77873 : BasicBlock* pred = *current_pred;
400 77873 : if (!pred->deferred()) {
401 : all_deferred = false;
402 : break;
403 : }
404 : }
405 :
406 31710 : if (all_deferred) return;
407 3726 : BasicBlock* merger = NewBasicBlock();
408 : merger->set_control(BasicBlock::kGoto);
409 3726 : merger->successors().push_back(block);
410 41167 : for (auto current_pred = block->predecessors().begin();
411 33715 : current_pred != block->predecessors().end(); ++current_pred) {
412 29989 : BasicBlock* pred = *current_pred;
413 29989 : merger->predecessors().push_back(pred);
414 29989 : pred->successors().clear();
415 29989 : pred->successors().push_back(merger);
416 : }
417 3726 : merger->set_deferred(false);
418 : block->predecessors().clear();
419 3726 : block->predecessors().push_back(merger);
420 3726 : MovePhis(block, merger);
421 : }
422 :
423 3726 : void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
424 39778 : for (size_t i = 0; i < from->NodeCount();) {
425 39425 : Node* node = from->NodeAt(i);
426 32326 : if (node->opcode() == IrOpcode::kPhi) {
427 : to->AddNode(node);
428 : from->RemoveNode(from->begin() + i);
429 : DCHECK_EQ(nodeid_to_block_[node->id()], from);
430 14198 : nodeid_to_block_[node->id()] = to;
431 : } else {
432 25227 : ++i;
433 : }
434 : }
435 3726 : }
436 :
437 265724 : void Schedule::PropagateDeferredMark() {
438 : // Push forward the deferred block marks through newly inserted blocks and
439 : // other improperly marked blocks until a fixed point is reached.
440 : // TODO(danno): optimize the propagation
441 : bool done = false;
442 819647 : while (!done) {
443 : done = true;
444 10886816 : for (auto block : all_blocks_) {
445 5869862 : if (!block->deferred()) {
446 3912506 : bool deferred = block->PredecessorCount() > 0;
447 17516276 : for (auto pred : block->predecessors()) {
448 9691264 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
449 : deferred = false;
450 : }
451 : }
452 3912506 : if (deferred) {
453 : block->set_deferred(true);
454 : done = false;
455 : }
456 : }
457 : }
458 : }
459 265724 : }
460 :
461 18538498 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
462 : block->AddSuccessor(succ);
463 : succ->AddPredecessor(block);
464 18538496 : }
465 :
466 :
467 271530 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
468 933939 : for (BasicBlock* const successor : from->successors()) {
469 : to->AddSuccessor(successor);
470 1515904 : for (BasicBlock*& predecessor : successor->predecessors()) {
471 734146 : if (predecessor == from) predecessor = to;
472 : }
473 : }
474 : from->ClearSuccessors();
475 271530 : }
476 :
477 :
478 0 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
479 : block->set_control_input(node);
480 7164944 : SetBlockForNode(block, node);
481 0 : }
482 :
483 :
484 366953657 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
485 550430444 : if (node->id() >= nodeid_to_block_.size()) {
486 17675562 : nodeid_to_block_.resize(node->id() + 1);
487 : }
488 366953740 : nodeid_to_block_[node->id()] = block;
489 183476870 : }
490 :
491 :
492 12 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
493 312 : for (BasicBlock* block :
494 72 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
495 60 : if (block->rpo_number() == -1) {
496 0 : os << "--- BLOCK id:" << block->id().ToInt();
497 : } else {
498 60 : os << "--- BLOCK B" << block->rpo_number();
499 : }
500 60 : if (block->deferred()) os << " (deferred)";
501 60 : if (block->PredecessorCount() != 0) os << " <- ";
502 : bool comma = false;
503 240 : for (BasicBlock const* predecessor : block->predecessors()) {
504 60 : if (comma) os << ", ";
505 : comma = true;
506 60 : if (predecessor->rpo_number() == -1) {
507 0 : os << "id:" << predecessor->id().ToInt();
508 : } else {
509 60 : os << "B" << predecessor->rpo_number();
510 : }
511 : }
512 60 : os << " ---\n";
513 168 : for (Node* node : *block) {
514 48 : os << " " << *node;
515 48 : if (NodeProperties::IsTyped(node)) {
516 : Type* type = NodeProperties::GetType(node);
517 0 : os << " : ";
518 0 : type->PrintTo(os);
519 : }
520 48 : os << "\n";
521 : }
522 : BasicBlock::Control control = block->control();
523 60 : if (control != BasicBlock::kNone) {
524 48 : os << " ";
525 48 : if (block->control_input() != nullptr) {
526 24 : os << *block->control_input();
527 : } else {
528 24 : os << "Goto";
529 : }
530 48 : os << " -> ";
531 : comma = false;
532 216 : for (BasicBlock const* successor : block->successors()) {
533 60 : if (comma) os << ", ";
534 : comma = true;
535 60 : if (successor->rpo_number() == -1) {
536 0 : os << "id:" << successor->id().ToInt();
537 : } else {
538 60 : os << "B" << successor->rpo_number();
539 : }
540 : }
541 48 : os << "\n";
542 : }
543 : }
544 12 : return os;
545 : }
546 :
547 : } // namespace compiler
548 : } // namespace internal
549 : } // namespace v8
|
