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 3417146 : 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 61661258 : id_(id) {
34 3417146 : }
35 :
36 223084 : 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 223084 : if (loop_end_ == nullptr) return false; // This is not a loop.
41 348370 : return block->rpo_number_ >= rpo_number_ &&
42 348370 : block->rpo_number_ < loop_end_->rpo_number_;
43 : }
44 :
45 0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
46 31046656 : successors_.push_back(successor);
47 0 : }
48 :
49 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50 30957999 : predecessors_.push_back(predecessor);
51 0 : }
52 :
53 150825940 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
54 :
55 23989263 : void BasicBlock::set_control(Control control) { control_ = control; }
56 :
57 0 : void BasicBlock::set_control_input(Node* control_input) {
58 10964813 : if (!nodes_.empty() && control_input == nodes_.back()) {
59 : nodes_.pop_back();
60 : }
61 10964813 : control_input_ = control_input;
62 0 : }
63 :
64 27470684 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
65 27470684 : loop_depth_ = loop_depth;
66 27470684 : }
67 :
68 137915823 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
69 137915823 : rpo_number_ = rpo_number;
70 137915823 : }
71 :
72 284954 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
73 :
74 27470770 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75 27470770 : loop_header_ = loop_header;
76 27470770 : }
77 :
78 : // static
79 1133593273 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
80 787246262 : while (b1 != b2) {
81 551113696 : if (b1->dominator_depth() < b2->dominator_depth()) {
82 : b2 = b2->dominator();
83 : } else {
84 : b1 = b1->dominator();
85 : }
86 : }
87 118066283 : return b1;
88 : }
89 :
90 0 : void BasicBlock::Print() { StdoutStream{} << this; }
91 :
92 0 : std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
93 0 : 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 3419841 : 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 3419841 : start_(NewBasicBlock()),
145 6839856 : end_(NewBasicBlock()) {
146 3420059 : nodeid_to_block_.reserve(node_count_hint);
147 3419952 : }
148 :
149 356866507 : BasicBlock* Schedule::block(Node* node) const {
150 713733013 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
151 710147870 : return nodeid_to_block_[node->id()];
152 : }
153 : return nullptr;
154 : }
155 :
156 483523181 : bool Schedule::IsScheduled(Node* node) {
157 967046362 : if (node->id() >= nodeid_to_block_.size()) return false;
158 474593329 : return nodeid_to_block_[node->id()] != nullptr;
159 : }
160 :
161 20750031 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162 : DCHECK(block_id.ToSize() < all_blocks_.size());
163 41500062 : 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 27413373 : BasicBlock* Schedule::NewBasicBlock() {
172 : BasicBlock* block = new (zone_)
173 109653712 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174 27413483 : all_blocks_.push_back(block);
175 27413763 : return block;
176 : }
177 :
178 95110261 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
179 95110261 : 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 95110261 : SetBlockForNode(block, node);
186 95110158 : }
187 :
188 148250870 : void Schedule::AddNode(BasicBlock* block, Node* node) {
189 148250870 : 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 148250477 : SetBlockForNode(block, node);
196 148250906 : }
197 :
198 13038338 : void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
199 : DCHECK_EQ(BasicBlock::kNone, block->control());
200 : block->set_control(BasicBlock::kGoto);
201 13038338 : AddSuccessor(block, succ);
202 13038343 : }
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 354359 : 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 354359 : AddSuccessor(block, success_block);
229 354359 : AddSuccessor(block, exception_block);
230 354359 : SetControlInput(block, call);
231 354359 : }
232 :
233 6138553 : 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 6138553 : AddSuccessor(block, tblock);
239 6138631 : AddSuccessor(block, fblock);
240 6138631 : SetControlInput(block, branch);
241 6138624 : }
242 :
243 45927 : 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 549276 : for (size_t index = 0; index < succ_count; ++index) {
249 503349 : AddSuccessor(block, succ_blocks[index]);
250 : }
251 45927 : SetControlInput(block, sw);
252 45927 : }
253 :
254 251290 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255 : DCHECK_EQ(BasicBlock::kNone, block->control());
256 : block->set_control(BasicBlock::kTailCall);
257 125645 : SetControlInput(block, input);
258 125645 : if (block != end()) AddSuccessor(block, end());
259 125645 : }
260 :
261 7547863 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
262 : DCHECK_EQ(BasicBlock::kNone, block->control());
263 : block->set_control(BasicBlock::kReturn);
264 3773795 : SetControlInput(block, input);
265 3774068 : if (block != end()) AddSuccessor(block, end());
266 3774194 : }
267 :
268 182276 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269 : DCHECK_EQ(BasicBlock::kNone, block->control());
270 : block->set_control(BasicBlock::kDeoptimize);
271 91138 : SetControlInput(block, input);
272 91138 : if (block != end()) AddSuccessor(block, end());
273 91138 : }
274 :
275 616952 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
276 : DCHECK_EQ(BasicBlock::kNone, block->control());
277 : block->set_control(BasicBlock::kThrow);
278 308476 : SetControlInput(block, input);
279 308476 : if (block != end()) AddSuccessor(block, end());
280 308477 : }
281 :
282 128879 : 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 64439 : MoveSuccessors(block, end);
289 64440 : AddSuccessor(block, tblock);
290 64440 : AddSuccessor(block, fblock);
291 64440 : if (block->control_input() != nullptr) {
292 62380 : SetControlInput(end, block->control_input());
293 : }
294 64440 : SetControlInput(block, branch);
295 64440 : }
296 :
297 2 : 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 4 : 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 293772 : 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 7907858 : for (BasicBlock* block : all_blocks_copy) {
320 6614198 : if (block->PredecessorCount() > 1) {
321 : if (block != end_) {
322 : EnsureSplitEdgeForm(block);
323 : }
324 706116 : if (block->deferred()) {
325 49656 : EnsureDeferredCodeSingleEntryPoint(block);
326 : }
327 : }
328 : }
329 :
330 293772 : EliminateRedundantPhiNodes();
331 293772 : }
332 :
333 293772 : 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 907019 : while (!reached_fixed_point) {
342 : reached_fixed_point = true;
343 17093344 : for (BasicBlock* block : all_blocks_) {
344 16454394 : int predecessor_count = static_cast<int>(block->PredecessorCount());
345 120503530 : for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346 43797371 : Node* node = block->NodeAt(node_pos);
347 43797371 : if (node->opcode() == IrOpcode::kPhi) {
348 : Node* first_input = node->InputAt(0);
349 : bool inputs_equal = true;
350 5635451 : for (int i = 1; i < predecessor_count; ++i) {
351 : Node* input = node->InputAt(i);
352 2259060 : if (input != first_input && input != node) {
353 : inputs_equal = false;
354 : break;
355 : }
356 : }
357 5130527 : if (!inputs_equal) continue;
358 3376391 : node->ReplaceUses(first_input);
359 : block->RemoveNode(block->begin() + node_pos);
360 3376391 : --node_pos;
361 : reached_fixed_point = false;
362 : }
363 : }
364 : }
365 : }
366 293772 : }
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 49656 : 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 160504 : for (auto current_pred = block->predecessors().begin();
391 : current_pred != block->predecessors().end(); ++current_pred) {
392 60128 : BasicBlock* pred = *current_pred;
393 60128 : if (!pred->deferred()) {
394 : all_deferred = false;
395 : break;
396 : }
397 : }
398 :
399 50720 : if (all_deferred) return;
400 48592 : BasicBlock* merger = NewBasicBlock();
401 : merger->set_control(BasicBlock::kGoto);
402 48592 : merger->successors().push_back(block);
403 345017 : for (auto current_pred = block->predecessors().begin();
404 247833 : current_pred != block->predecessors().end(); ++current_pred) {
405 199241 : BasicBlock* pred = *current_pred;
406 199241 : merger->predecessors().push_back(pred);
407 199241 : pred->successors().clear();
408 199241 : pred->successors().push_back(merger);
409 : }
410 48592 : merger->set_deferred(false);
411 : block->predecessors().clear();
412 48592 : block->predecessors().push_back(merger);
413 48592 : MovePhis(block, merger);
414 : }
415 :
416 48592 : void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417 482235 : for (size_t i = 0; i < from->NodeCount();) {
418 406779 : Node* node = from->NodeAt(i);
419 385051 : 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 43456 : nodeid_to_block_[node->id()] = to;
424 : } else {
425 363323 : ++i;
426 : }
427 : }
428 48592 : }
429 :
430 226857 : 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 680571 : while (!done) {
436 : done = true;
437 1254585 : for (auto block : all_blocks_) {
438 506637 : if (!block->deferred()) {
439 506637 : bool deferred = block->PredecessorCount() > 0;
440 1601742 : for (auto pred : block->predecessors()) {
441 588468 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
442 : deferred = false;
443 : }
444 : }
445 506637 : if (deferred) {
446 : block->set_deferred(true);
447 : done = false;
448 : }
449 : }
450 : }
451 : }
452 226857 : }
453 :
454 30957850 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455 : block->AddSuccessor(succ);
456 : succ->AddPredecessor(block);
457 30958144 : }
458 :
459 64440 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460 217687 : for (BasicBlock* const successor : from->successors()) {
461 : to->AddSuccessor(successor);
462 268921 : for (BasicBlock*& predecessor : successor->predecessors()) {
463 91307 : if (predecessor == from) predecessor = to;
464 : }
465 : }
466 : from->ClearSuccessors();
467 64441 : }
468 :
469 10964813 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470 : block->set_control_input(node);
471 10964813 : SetBlockForNode(block, node);
472 10965001 : }
473 :
474 509097002 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475 763645430 : if (node->id() >= nodeid_to_block_.size()) {
476 31790114 : nodeid_to_block_.resize(node->id() + 1);
477 : }
478 509097148 : nodeid_to_block_[node->id()] = block;
479 254548574 : }
480 :
481 16 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
482 606 : for (BasicBlock* block :
483 134 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484 118 : if (block->rpo_number() == -1) {
485 0 : os << "--- BLOCK id:" << block->id().ToInt();
486 : } else {
487 118 : os << "--- BLOCK B" << block->rpo_number();
488 : }
489 118 : if (block->deferred()) os << " (deferred)";
490 118 : if (block->PredecessorCount() != 0) os << " <- ";
491 : bool comma = false;
492 484 : for (BasicBlock const* predecessor : block->predecessors()) {
493 124 : if (comma) os << ", ";
494 : comma = true;
495 124 : if (predecessor->rpo_number() == -1) {
496 0 : os << "id:" << predecessor->id().ToInt();
497 : } else {
498 124 : os << "B" << predecessor->rpo_number();
499 : }
500 : }
501 118 : os << " ---\n";
502 592 : for (Node* node : *block) {
503 356 : os << " " << *node;
504 356 : if (NodeProperties::IsTyped(node)) {
505 42 : os << " : " << NodeProperties::GetType(node);
506 : }
507 356 : os << "\n";
508 : }
509 : BasicBlock::Control control = block->control();
510 118 : if (control != BasicBlock::kNone) {
511 102 : os << " ";
512 102 : if (block->control_input() != nullptr) {
513 38 : os << *block->control_input();
514 : } else {
515 64 : os << "Goto";
516 : }
517 102 : os << " -> ";
518 : comma = false;
519 452 : for (BasicBlock const* successor : block->successors()) {
520 124 : if (comma) os << ", ";
521 : comma = true;
522 124 : if (successor->rpo_number() == -1) {
523 0 : os << "id:" << successor->id().ToInt();
524 : } else {
525 124 : os << "B" << successor->rpo_number();
526 : }
527 : }
528 102 : os << "\n";
529 : }
530 : }
531 16 : return os;
532 : }
533 :
534 : } // namespace compiler
535 : } // namespace internal
536 183867 : } // namespace v8
|
