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 3115429 : 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 61494952 : id_(id) {
34 3115429 : }
35 :
36 215934 : 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 215934 : if (loop_end_ == nullptr) return false; // This is not a loop.
41 339044 : return block->rpo_number_ >= rpo_number_ &&
42 123110 : block->rpo_number_ < loop_end_->rpo_number_;
43 : }
44 :
45 0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
46 31781983 : successors_.push_back(successor);
47 0 : }
48 :
49 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50 31723937 : predecessors_.push_back(predecessor);
51 0 : }
52 :
53 157448302 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
54 :
55 24511022 : void BasicBlock::set_control(Control control) { control_ = control; }
56 :
57 0 : void BasicBlock::set_control_input(Node* control_input) {
58 11009558 : if (!nodes_.empty() && control_input == nodes_.back()) {
59 : nodes_.pop_back();
60 : }
61 11009558 : control_input_ = control_input;
62 0 : }
63 :
64 27665951 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
65 27665951 : loop_depth_ = loop_depth;
66 27665951 : }
67 :
68 138907542 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
69 138907542 : rpo_number_ = rpo_number;
70 138907542 : }
71 :
72 272185 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
73 :
74 27666029 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75 27666029 : loop_header_ = loop_header;
76 27666029 : }
77 :
78 : // static
79 131890149 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
80 800158844 : while (b1 != b2) {
81 668268695 : if (b1->dominator_depth() < b2->dominator_depth()) {
82 : b2 = b2->dominator();
83 : } else {
84 : b1 = b1->dominator();
85 : }
86 : }
87 131890149 : 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 3117179 : 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 3117179 : start_(NewBasicBlock()),
145 6235106 : end_(NewBasicBlock()) {
146 3118267 : nodeid_to_block_.reserve(node_count_hint);
147 3118118 : }
148 :
149 384114433 : BasicBlock* Schedule::block(Node* node) const {
150 384114435 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
151 764525056 : return nodeid_to_block_[node->id()];
152 : }
153 : return nullptr;
154 : }
155 :
156 515446071 : bool Schedule::IsScheduled(Node* node) {
157 1030892142 : if (node->id() >= nodeid_to_block_.size()) return false;
158 506573790 : return nodeid_to_block_[node->id()] != nullptr;
159 : }
160 :
161 20820881 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162 : DCHECK(block_id.ToSize() < all_blocks_.size());
163 20820881 : 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 27631724 : BasicBlock* Schedule::NewBasicBlock() {
172 : BasicBlock* block = new (zone_)
173 82895818 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174 27632047 : all_blocks_.push_back(block);
175 27633559 : return block;
176 : }
177 :
178 101518211 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
179 101518211 : 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 101518211 : SetBlockForNode(block, node);
186 101516944 : }
187 :
188 154801880 : void Schedule::AddNode(BasicBlock* block, Node* node) {
189 154801880 : 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 154798917 : SetBlockForNode(block, node);
196 154801267 : }
197 :
198 13486041 : 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 13486109 : }
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 426865 : 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 426866 : SetControlInput(block, call);
231 426866 : }
232 :
233 6390834 : 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 6391043 : SetControlInput(block, branch);
241 6391057 : }
242 :
243 40314 : 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 932812 : for (size_t index = 0; index < succ_count; ++index) {
249 446249 : AddSuccessor(block, succ_blocks[index]);
250 : }
251 40314 : SetControlInput(block, sw);
252 40314 : }
253 :
254 126427 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255 : DCHECK_EQ(BasicBlock::kNone, block->control());
256 : block->set_control(BasicBlock::kTailCall);
257 126427 : SetControlInput(block, input);
258 126427 : if (block != end()) AddSuccessor(block, end());
259 126428 : }
260 :
261 3521455 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
262 : DCHECK_EQ(BasicBlock::kNone, block->control());
263 : block->set_control(BasicBlock::kReturn);
264 3521455 : SetControlInput(block, input);
265 3521772 : if (block != end()) AddSuccessor(block, end());
266 3523744 : }
267 :
268 86360 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269 : DCHECK_EQ(BasicBlock::kNone, block->control());
270 : block->set_control(BasicBlock::kDeoptimize);
271 86360 : SetControlInput(block, input);
272 86360 : if (block != end()) AddSuccessor(block, end());
273 86360 : }
274 :
275 340536 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
276 : DCHECK_EQ(BasicBlock::kNone, block->control());
277 : block->set_control(BasicBlock::kThrow);
278 340536 : SetControlInput(block, input);
279 340539 : if (block != end()) AddSuccessor(block, end());
280 340540 : }
281 :
282 38957 : 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 38957 : MoveSuccessors(block, end);
289 : AddSuccessor(block, tblock);
290 : AddSuccessor(block, fblock);
291 38959 : if (block->control_input() != nullptr) {
292 37591 : SetControlInput(end, block->control_input());
293 : }
294 38959 : SetControlInput(block, branch);
295 38959 : }
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 248803 : 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 7008969 : for (BasicBlock* block : all_blocks_copy) {
320 6760166 : if (block->PredecessorCount() > 1) {
321 : if (block != end_) {
322 : EnsureSplitEdgeForm(block);
323 : }
324 777599 : if (block->deferred()) {
325 54352 : EnsureDeferredCodeSingleEntryPoint(block);
326 : }
327 : }
328 : }
329 :
330 248803 : EliminateRedundantPhiNodes();
331 248803 : }
332 :
333 248803 : 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 528030 : while (!reached_fixed_point) {
342 : reached_fixed_point = true;
343 17269666 : for (BasicBlock* block : all_blocks_) {
344 16990439 : int predecessor_count = static_cast<int>(block->PredecessorCount());
345 108138185 : for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346 : Node* node = block->NodeAt(node_pos);
347 45573873 : if (node->opcode() == IrOpcode::kPhi) {
348 : Node* first_input = node->InputAt(0);
349 : bool inputs_equal = true;
350 7034655 : for (int i = 1; i < predecessor_count; ++i) {
351 : Node* input = node->InputAt(i);
352 2451175 : if (input != first_input && input != node) {
353 : inputs_equal = false;
354 : break;
355 : }
356 : }
357 5772639 : if (!inputs_equal) continue;
358 3952472 : node->ReplaceUses(first_input);
359 : block->RemoveNode(block->begin() + node_pos);
360 3952472 : --node_pos;
361 : reached_fixed_point = false;
362 : }
363 : }
364 : }
365 : }
366 248803 : }
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 54352 : 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 120576 : for (auto current_pred = block->predecessors().begin();
391 : current_pred != block->predecessors().end(); ++current_pred) {
392 65104 : BasicBlock* pred = *current_pred;
393 65104 : if (!pred->deferred()) {
394 : all_deferred = false;
395 : break;
396 : }
397 : }
398 :
399 55472 : if (all_deferred) return;
400 53232 : BasicBlock* merger = NewBasicBlock();
401 : merger->set_control(BasicBlock::kGoto);
402 53232 : merger->successors().push_back(block);
403 321420 : for (auto current_pred = block->predecessors().begin();
404 268188 : current_pred != block->predecessors().end(); ++current_pred) {
405 214956 : BasicBlock* pred = *current_pred;
406 214956 : merger->predecessors().push_back(pred);
407 214956 : pred->successors().clear();
408 214956 : pred->successors().push_back(merger);
409 : }
410 53232 : merger->set_deferred(false);
411 : block->predecessors().clear();
412 53232 : block->predecessors().push_back(merger);
413 53232 : MovePhis(block, merger);
414 : }
415 :
416 53232 : void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417 469644 : for (size_t i = 0; i < from->NodeCount();) {
418 : Node* node = from->NodeAt(i);
419 416412 : 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 68656 : nodeid_to_block_[node->id()] = to;
424 : } else {
425 382084 : ++i;
426 : }
427 : }
428 53232 : }
429 :
430 181535 : 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 363070 : while (!done) {
436 : done = true;
437 586967 : for (auto block : all_blocks_) {
438 405432 : if (!block->deferred()) {
439 405432 : bool deferred = block->PredecessorCount() > 0;
440 640897 : for (auto pred : block->predecessors()) {
441 235465 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
442 : deferred = false;
443 : }
444 : }
445 405432 : if (deferred) {
446 : block->set_deferred(true);
447 : done = false;
448 : }
449 : }
450 : }
451 : }
452 181535 : }
453 :
454 2386 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455 : block->AddSuccessor(succ);
456 : succ->AddPredecessor(block);
457 2386 : }
458 :
459 38957 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460 97607 : for (BasicBlock* const successor : from->successors()) {
461 : to->AddSuccessor(successor);
462 118991 : for (BasicBlock*& predecessor : successor->predecessors()) {
463 60341 : if (predecessor == from) predecessor = to;
464 : }
465 : }
466 : from->ClearSuccessors();
467 38960 : }
468 :
469 11009558 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470 : block->set_control_input(node);
471 11009558 : SetBlockForNode(block, node);
472 11009803 : }
473 :
474 267424148 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475 534848296 : if (node->id() >= nodeid_to_block_.size()) {
476 31995882 : nodeid_to_block_.resize(node->id() + 1);
477 : }
478 534848110 : nodeid_to_block_[node->id()] = block;
479 267424055 : }
480 :
481 28 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
482 136 : for (BasicBlock* block :
483 136 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484 108 : if (block->rpo_number() == -1) {
485 0 : os << "--- BLOCK id:" << block->id().ToInt();
486 : } else {
487 108 : os << "--- BLOCK B" << block->rpo_number();
488 : }
489 108 : if (block->deferred()) os << " (deferred)";
490 108 : if (block->PredecessorCount() != 0) os << " <- ";
491 : bool comma = false;
492 200 : for (BasicBlock const* predecessor : block->predecessors()) {
493 92 : if (comma) os << ", ";
494 : comma = true;
495 92 : if (predecessor->rpo_number() == -1) {
496 0 : os << "id:" << predecessor->id().ToInt();
497 : } else {
498 92 : os << "B" << predecessor->rpo_number();
499 : }
500 : }
501 108 : os << " ---\n";
502 478 : for (Node* node : *block) {
503 370 : os << " " << *node;
504 370 : if (NodeProperties::IsTyped(node)) {
505 42 : os << " : " << NodeProperties::GetType(node);
506 : }
507 370 : os << "\n";
508 : }
509 : BasicBlock::Control control = block->control();
510 108 : if (control != BasicBlock::kNone) {
511 80 : os << " ";
512 80 : if (block->control_input() != nullptr) {
513 40 : os << *block->control_input();
514 : } else {
515 40 : os << "Goto";
516 : }
517 80 : os << " -> ";
518 : comma = false;
519 172 : for (BasicBlock const* successor : block->successors()) {
520 92 : if (comma) os << ", ";
521 : comma = true;
522 92 : if (successor->rpo_number() == -1) {
523 0 : os << "id:" << successor->id().ToInt();
524 : } else {
525 92 : os << "B" << successor->rpo_number();
526 : }
527 : }
528 80 : os << "\n";
529 : }
530 : }
531 28 : return os;
532 : }
533 :
534 : } // namespace compiler
535 : } // namespace internal
536 121996 : } // namespace v8
|
