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 2990114 : 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 61018146 : id_(id) {
34 2990114 : }
35 :
36 213222 : 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 213222 : if (loop_end_ == nullptr) return false; // This is not a loop.
41 334524 : return block->rpo_number_ >= rpo_number_ &&
42 121302 : block->rpo_number_ < loop_end_->rpo_number_;
43 : }
44 :
45 0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
46 31814317 : successors_.push_back(successor);
47 0 : }
48 :
49 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50 31755363 : predecessors_.push_back(predecessor);
51 0 : }
52 :
53 157402313 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
54 :
55 24522965 : void BasicBlock::set_control(Control control) { control_ = control; }
56 :
57 0 : void BasicBlock::set_control_input(Node* control_input) {
58 10812624 : if (!nodes_.empty() && control_input == nodes_.back()) {
59 : nodes_.pop_back();
60 : }
61 10812624 : control_input_ = control_input;
62 0 : }
63 :
64 27553190 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
65 27553190 : loop_depth_ = loop_depth;
66 27553190 : }
67 :
68 139023076 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
69 139023076 : rpo_number_ = rpo_number;
70 139023076 : }
71 :
72 269819 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
73 :
74 27552975 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75 27552975 : loop_header_ = loop_header;
76 27552975 : }
77 :
78 : // static
79 138234569 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
80 816149496 : while (b1 != b2) {
81 677914927 : if (b1->dominator_depth() < b2->dominator_depth()) {
82 : b2 = b2->dominator();
83 : } else {
84 : b1 = b1->dominator();
85 : }
86 : }
87 138234569 : return b1;
88 : }
89 :
90 0 : void BasicBlock::Print() { StdoutStream{} << this; }
91 :
92 0 : 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 0 : return os;
109 : }
110 :
111 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
112 0 : switch (c) {
113 : case BasicBlock::kNone:
114 0 : return os << "none";
115 : case BasicBlock::kGoto:
116 0 : return os << "goto";
117 : case BasicBlock::kCall:
118 0 : return os << "call";
119 : case BasicBlock::kBranch:
120 0 : return os << "branch";
121 : case BasicBlock::kSwitch:
122 0 : return os << "switch";
123 : case BasicBlock::kDeoptimize:
124 0 : return os << "deoptimize";
125 : case BasicBlock::kTailCall:
126 0 : return os << "tailcall";
127 : case BasicBlock::kReturn:
128 0 : return os << "return";
129 : case BasicBlock::kThrow:
130 0 : return os << "throw";
131 : }
132 0 : UNREACHABLE();
133 : }
134 :
135 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
136 0 : return os << id.ToSize();
137 : }
138 :
139 2991848 : 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 2991848 : start_(NewBasicBlock()),
145 5984361 : end_(NewBasicBlock()) {
146 2993291 : nodeid_to_block_.reserve(node_count_hint);
147 2992756 : }
148 :
149 387406442 : BasicBlock* Schedule::block(Node* node) const {
150 387406444 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
151 771499516 : return nodeid_to_block_[node->id()];
152 : }
153 : return nullptr;
154 : }
155 :
156 519494470 : bool Schedule::IsScheduled(Node* node) {
157 1038988940 : if (node->id() >= nodeid_to_block_.size()) return false;
158 510899748 : return nodeid_to_block_[node->id()] != nullptr;
159 : }
160 :
161 20531583 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162 : DCHECK(block_id.ToSize() < all_blocks_.size());
163 20531583 : return all_blocks_[block_id.ToSize()];
164 : }
165 :
166 1 : bool Schedule::SameBasicBlock(Node* a, Node* b) const {
167 : BasicBlock* block = this->block(a);
168 2 : return block != nullptr && block == this->block(b);
169 : }
170 :
171 27518723 : BasicBlock* Schedule::NewBasicBlock() {
172 : BasicBlock* block = new (zone_)
173 82556641 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174 27518959 : all_blocks_.push_back(block);
175 27520576 : return block;
176 : }
177 :
178 101302391 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
179 101302391 : if (FLAG_trace_turbo_scheduler) {
180 0 : StdoutStream{} << "Planning #" << node->id() << ":"
181 0 : << node->op()->mnemonic() << " for future add to B"
182 0 : << block->id() << "\n";
183 : }
184 : DCHECK_NULL(this->block(node));
185 101302391 : SetBlockForNode(block, node);
186 101301864 : }
187 :
188 154671275 : void Schedule::AddNode(BasicBlock* block, Node* node) {
189 154671275 : if (FLAG_trace_turbo_scheduler) {
190 0 : StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
191 0 : << " to B" << block->id() << "\n";
192 : }
193 : DCHECK(this->block(node) == nullptr || this->block(node) == block);
194 : block->AddNode(node);
195 154669955 : SetBlockForNode(block, node);
196 154671365 : }
197 :
198 13696475 : 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 13696481 : }
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 414953 : 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 414951 : SetControlInput(block, call);
231 414951 : }
232 :
233 6420270 : 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 6420410 : SetControlInput(block, branch);
241 6420401 : }
242 :
243 41079 : 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 935831 : for (size_t index = 0; index < succ_count; ++index) {
249 447373 : AddSuccessor(block, succ_blocks[index]);
250 : }
251 41082 : SetControlInput(block, sw);
252 41082 : }
253 :
254 126457 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255 : DCHECK_EQ(BasicBlock::kNone, block->control());
256 : block->set_control(BasicBlock::kTailCall);
257 126457 : SetControlInput(block, input);
258 126457 : if (block != end()) AddSuccessor(block, end());
259 126457 : }
260 :
261 3310041 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
262 : DCHECK_EQ(BasicBlock::kNone, block->control());
263 : block->set_control(BasicBlock::kReturn);
264 3310041 : SetControlInput(block, input);
265 3310166 : if (block != end()) AddSuccessor(block, end());
266 3310686 : }
267 :
268 85411 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269 : DCHECK_EQ(BasicBlock::kNone, block->control());
270 : block->set_control(BasicBlock::kDeoptimize);
271 85411 : SetControlInput(block, input);
272 85411 : if (block != end()) AddSuccessor(block, end());
273 85411 : }
274 :
275 337111 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
276 : DCHECK_EQ(BasicBlock::kNone, block->control());
277 : block->set_control(BasicBlock::kThrow);
278 337111 : SetControlInput(block, input);
279 337112 : if (block != end()) AddSuccessor(block, end());
280 337113 : }
281 :
282 39503 : 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 39503 : MoveSuccessors(block, end);
289 : AddSuccessor(block, tblock);
290 : AddSuccessor(block, fblock);
291 39503 : if (block->control_input() != nullptr) {
292 37725 : SetControlInput(end, block->control_input());
293 : }
294 39503 : SetControlInput(block, branch);
295 39504 : }
296 :
297 1 : 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 1 : MoveSuccessors(block, end);
304 7 : for (size_t index = 0; index < succ_count; ++index) {
305 3 : AddSuccessor(block, succ_blocks[index]);
306 : }
307 1 : if (block->control_input() != nullptr) {
308 1 : SetControlInput(end, block->control_input());
309 : }
310 1 : SetControlInput(block, sw);
311 1 : }
312 :
313 248535 : 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 7185897 : for (BasicBlock* block : all_blocks_copy) {
320 6937362 : if (block->PredecessorCount() > 1) {
321 : if (block != end_) {
322 : EnsureSplitEdgeForm(block);
323 : }
324 786319 : if (block->deferred()) {
325 52728 : EnsureDeferredCodeSingleEntryPoint(block);
326 : }
327 : }
328 : }
329 :
330 248535 : EliminateRedundantPhiNodes();
331 248535 : }
332 :
333 248535 : 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 526446 : while (!reached_fixed_point) {
342 : reached_fixed_point = true;
343 17482254 : for (BasicBlock* block : all_blocks_) {
344 17204343 : int predecessor_count = static_cast<int>(block->PredecessorCount());
345 109596737 : for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346 : Node* node = block->NodeAt(node_pos);
347 46196197 : if (node->opcode() == IrOpcode::kPhi) {
348 : Node* first_input = node->InputAt(0);
349 : bool inputs_equal = true;
350 6792515 : for (int i = 1; i < predecessor_count; ++i) {
351 : Node* input = node->InputAt(i);
352 2364399 : if (input != first_input && input != node) {
353 : inputs_equal = false;
354 : break;
355 : }
356 : }
357 5623971 : if (!inputs_equal) continue;
358 3843844 : node->ReplaceUses(first_input);
359 : block->RemoveNode(block->begin() + node_pos);
360 3843844 : --node_pos;
361 : reached_fixed_point = false;
362 : }
363 : }
364 : }
365 : }
366 248535 : }
367 :
368 0 : 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 0 : }
378 :
379 52728 : 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 116432 : for (auto current_pred = block->predecessors().begin();
391 : current_pred != block->predecessors().end(); ++current_pred) {
392 62640 : BasicBlock* pred = *current_pred;
393 62640 : if (!pred->deferred()) {
394 : all_deferred = false;
395 : break;
396 : }
397 : }
398 :
399 53792 : if (all_deferred) return;
400 51664 : BasicBlock* merger = NewBasicBlock();
401 : merger->set_control(BasicBlock::kGoto);
402 51664 : merger->successors().push_back(block);
403 323172 : for (auto current_pred = block->predecessors().begin();
404 271508 : current_pred != block->predecessors().end(); ++current_pred) {
405 219844 : BasicBlock* pred = *current_pred;
406 219844 : merger->predecessors().push_back(pred);
407 219844 : pred->successors().clear();
408 219844 : pred->successors().push_back(merger);
409 : }
410 51664 : merger->set_deferred(false);
411 : block->predecessors().clear();
412 51664 : block->predecessors().push_back(merger);
413 51664 : MovePhis(block, merger);
414 : }
415 :
416 51664 : void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417 446404 : for (size_t i = 0; i < from->NodeCount();) {
418 : Node* node = from->NodeAt(i);
419 394740 : 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 59584 : nodeid_to_block_[node->id()] = to;
424 : } else {
425 364948 : ++i;
426 : }
427 : }
428 51664 : }
429 :
430 181619 : 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 363238 : while (!done) {
436 : done = true;
437 587219 : for (auto block : all_blocks_) {
438 405600 : if (!block->deferred()) {
439 405600 : bool deferred = block->PredecessorCount() > 0;
440 641149 : for (auto pred : block->predecessors()) {
441 235549 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
442 : deferred = false;
443 : }
444 : }
445 405600 : if (deferred) {
446 : block->set_deferred(true);
447 : done = false;
448 : }
449 : }
450 : }
451 : }
452 181619 : }
453 :
454 2386 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455 : block->AddSuccessor(succ);
456 : succ->AddPredecessor(block);
457 2386 : }
458 :
459 39504 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460 98823 : for (BasicBlock* const successor : from->successors()) {
461 : to->AddSuccessor(successor);
462 120742 : for (BasicBlock*& predecessor : successor->predecessors()) {
463 61423 : if (predecessor == from) predecessor = to;
464 : }
465 : }
466 : from->ClearSuccessors();
467 39504 : }
468 :
469 10812624 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470 : block->set_control_input(node);
471 10812624 : SetBlockForNode(block, node);
472 10812766 : }
473 :
474 266991700 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475 533983400 : if (node->id() >= nodeid_to_block_.size()) {
476 32189683 : nodeid_to_block_.resize(node->id() + 1);
477 : }
478 533983334 : nodeid_to_block_[node->id()] = block;
479 266991667 : }
480 :
481 12 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
482 98 : for (BasicBlock* block :
483 98 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484 86 : if (block->rpo_number() == -1) {
485 0 : os << "--- BLOCK id:" << block->id().ToInt();
486 : } else {
487 86 : os << "--- BLOCK B" << block->rpo_number();
488 : }
489 86 : if (block->deferred()) os << " (deferred)";
490 86 : if (block->PredecessorCount() != 0) os << " <- ";
491 : bool comma = false;
492 176 : for (BasicBlock const* predecessor : block->predecessors()) {
493 90 : if (comma) os << ", ";
494 : comma = true;
495 90 : if (predecessor->rpo_number() == -1) {
496 0 : os << "id:" << predecessor->id().ToInt();
497 : } else {
498 90 : os << "B" << predecessor->rpo_number();
499 : }
500 : }
501 86 : os << " ---\n";
502 340 : for (Node* node : *block) {
503 254 : os << " " << *node;
504 254 : if (NodeProperties::IsTyped(node)) {
505 42 : os << " : " << NodeProperties::GetType(node);
506 : }
507 254 : os << "\n";
508 : }
509 : BasicBlock::Control control = block->control();
510 86 : if (control != BasicBlock::kNone) {
511 74 : os << " ";
512 74 : if (block->control_input() != nullptr) {
513 30 : os << *block->control_input();
514 : } else {
515 44 : os << "Goto";
516 : }
517 74 : os << " -> ";
518 : comma = false;
519 164 : for (BasicBlock const* successor : block->successors()) {
520 90 : if (comma) os << ", ";
521 : comma = true;
522 90 : if (successor->rpo_number() == -1) {
523 0 : os << "id:" << successor->id().ToInt();
524 : } else {
525 90 : os << "B" << successor->rpo_number();
526 : }
527 : }
528 74 : os << "\n";
529 : }
530 : }
531 12 : return os;
532 : }
533 :
534 : } // namespace compiler
535 : } // namespace internal
536 120216 : } // namespace v8
|
