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 2608114 : 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 58252838 : id_(id) {
34 2608114 : }
35 :
36 225030 : 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 225030 : if (loop_end_ == nullptr) return false; // This is not a loop.
41 351680 : return block->rpo_number_ >= rpo_number_ &&
42 351680 : block->rpo_number_ < loop_end_->rpo_number_;
43 : }
44 :
45 0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
46 31150564 : successors_.push_back(successor);
47 0 : }
48 :
49 0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50 31089199 : predecessors_.push_back(predecessor);
51 0 : }
52 :
53 150819606 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
54 :
55 23903546 : void BasicBlock::set_control(Control control) { control_ = control; }
56 :
57 0 : void BasicBlock::set_control_input(Node* control_input) {
58 10385979 : if (!nodes_.empty() && control_input == nodes_.back()) {
59 : nodes_.pop_back();
60 : }
61 10385979 : control_input_ = control_input;
62 0 : }
63 :
64 26549905 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
65 26549905 : loop_depth_ = loop_depth;
66 26549905 : }
67 :
68 134982135 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
69 134982135 : rpo_number_ = rpo_number;
70 134982135 : }
71 :
72 284999 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
73 :
74 26549840 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75 26549840 : loop_header_ = loop_header;
76 26549840 : }
77 :
78 : // static
79 1394705295 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
80 948194626 : while (b1 != b2) {
81 677195262 : if (b1->dominator_depth() < b2->dominator_depth()) {
82 : b2 = b2->dominator();
83 : } else {
84 : b1 = b1->dominator();
85 : }
86 : }
87 135499682 : 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 2610565 : 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 2610565 : start_(NewBasicBlock()),
145 5221322 : end_(NewBasicBlock()) {
146 2610737 : nodeid_to_block_.reserve(node_count_hint);
147 2610770 : }
148 :
149 377174058 : BasicBlock* Schedule::block(Node* node) const {
150 754348115 : if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
151 750814936 : return nodeid_to_block_[node->id()];
152 : }
153 : return nullptr;
154 : }
155 :
156 497817515 : bool Schedule::IsScheduled(Node* node) {
157 995635030 : if (node->id() >= nodeid_to_block_.size()) return false;
158 489073884 : return nodeid_to_block_[node->id()] != nullptr;
159 : }
160 :
161 19468927 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162 : DCHECK(block_id.ToSize() < all_blocks_.size());
163 38937854 : 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 26518197 : BasicBlock* Schedule::NewBasicBlock() {
172 : BasicBlock* block = new (zone_)
173 106073004 : BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174 26518305 : all_blocks_.push_back(block);
175 26518558 : return block;
176 : }
177 :
178 96289690 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
179 96289690 : 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 96289690 : SetBlockForNode(block, node);
186 96289703 : }
187 :
188 147985112 : void Schedule::AddNode(BasicBlock* block, Node* node) {
189 147985112 : 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 147984639 : SetBlockForNode(block, node);
196 147985156 : }
197 :
198 13504466 : void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
199 : DCHECK_EQ(BasicBlock::kNone, block->control());
200 : block->set_control(BasicBlock::kGoto);
201 13504466 : AddSuccessor(block, succ);
202 13504465 : }
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 411423 : 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 411423 : AddSuccessor(block, success_block);
229 411422 : AddSuccessor(block, exception_block);
230 411422 : SetControlInput(block, call);
231 411421 : }
232 :
233 6362603 : 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 6362603 : AddSuccessor(block, tblock);
239 6362656 : AddSuccessor(block, fblock);
240 6362654 : SetControlInput(block, branch);
241 6362652 : }
242 :
243 42091 : 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 504846 : for (size_t index = 0; index < succ_count; ++index) {
249 462755 : AddSuccessor(block, succ_blocks[index]);
250 : }
251 42091 : SetControlInput(block, sw);
252 42091 : }
253 :
254 251298 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255 : DCHECK_EQ(BasicBlock::kNone, block->control());
256 : block->set_control(BasicBlock::kTailCall);
257 125649 : SetControlInput(block, input);
258 125649 : if (block != end()) AddSuccessor(block, end());
259 125649 : }
260 :
261 5886391 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
262 : DCHECK_EQ(BasicBlock::kNone, block->control());
263 : block->set_control(BasicBlock::kReturn);
264 2943102 : SetControlInput(block, input);
265 2943289 : if (block != end()) AddSuccessor(block, end());
266 2943413 : }
267 :
268 176760 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269 : DCHECK_EQ(BasicBlock::kNone, block->control());
270 : block->set_control(BasicBlock::kDeoptimize);
271 88380 : SetControlInput(block, input);
272 88380 : if (block != end()) AddSuccessor(block, end());
273 88380 : }
274 :
275 670406 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
276 : DCHECK_EQ(BasicBlock::kNone, block->control());
277 : block->set_control(BasicBlock::kThrow);
278 335203 : SetControlInput(block, input);
279 335203 : if (block != end()) AddSuccessor(block, end());
280 335204 : }
281 :
282 79273 : 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 39636 : MoveSuccessors(block, end);
289 39637 : AddSuccessor(block, tblock);
290 39637 : AddSuccessor(block, fblock);
291 39637 : if (block->control_input() != nullptr) {
292 37861 : SetControlInput(end, block->control_input());
293 : }
294 39637 : SetControlInput(block, branch);
295 39637 : }
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 248012 : 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 8322447 : for (BasicBlock* block : all_blocks_copy) {
320 6997100 : if (block->PredecessorCount() > 1) {
321 : if (block != end_) {
322 : EnsureSplitEdgeForm(block);
323 : }
324 829323 : if (block->deferred()) {
325 52056 : EnsureDeferredCodeSingleEntryPoint(block);
326 : }
327 : }
328 : }
329 :
330 248012 : EliminateRedundantPhiNodes();
331 248012 : }
332 :
333 248012 : 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 770352 : while (!reached_fixed_point) {
342 : reached_fixed_point = true;
343 17904697 : for (BasicBlock* block : all_blocks_) {
344 17356041 : int predecessor_count = static_cast<int>(block->PredecessorCount());
345 128390954 : for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346 46839436 : Node* node = block->NodeAt(node_pos);
347 46839436 : if (node->opcode() == IrOpcode::kPhi) {
348 : Node* first_input = node->InputAt(0);
349 : bool inputs_equal = true;
350 6090847 : for (int i = 1; i < predecessor_count; ++i) {
351 : Node* input = node->InputAt(i);
352 2472395 : if (input != first_input && input != node) {
353 : inputs_equal = false;
354 : break;
355 : }
356 : }
357 5484783 : if (!inputs_equal) continue;
358 3618452 : node->ReplaceUses(first_input);
359 : block->RemoveNode(block->begin() + node_pos);
360 3618452 : --node_pos;
361 : reached_fixed_point = false;
362 : }
363 : }
364 : }
365 : }
366 248012 : }
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 52056 : 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 167704 : for (auto current_pred = block->predecessors().begin();
391 : current_pred != block->predecessors().end(); ++current_pred) {
392 62528 : BasicBlock* pred = *current_pred;
393 62528 : if (!pred->deferred()) {
394 : all_deferred = false;
395 : break;
396 : }
397 : }
398 :
399 53120 : if (all_deferred) return;
400 50992 : BasicBlock* merger = NewBasicBlock();
401 : merger->set_control(BasicBlock::kGoto);
402 50992 : merger->successors().push_back(block);
403 362948 : for (auto current_pred = block->predecessors().begin();
404 260964 : current_pred != block->predecessors().end(); ++current_pred) {
405 209972 : BasicBlock* pred = *current_pred;
406 209972 : merger->predecessors().push_back(pred);
407 209972 : pred->successors().clear();
408 209972 : pred->successors().push_back(merger);
409 : }
410 50992 : merger->set_deferred(false);
411 : block->predecessors().clear();
412 50992 : block->predecessors().push_back(merger);
413 50992 : MovePhis(block, merger);
414 : }
415 :
416 50992 : void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417 475444 : for (size_t i = 0; i < from->NodeCount();) {
418 399052 : Node* node = from->NodeAt(i);
419 373460 : 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 51184 : nodeid_to_block_[node->id()] = to;
424 : } else {
425 347868 : ++i;
426 : }
427 : }
428 50992 : }
429 :
430 181536 : 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 544608 : while (!done) {
436 : done = true;
437 1003972 : for (auto block : all_blocks_) {
438 405434 : if (!block->deferred()) {
439 405434 : bool deferred = block->PredecessorCount() > 0;
440 1281800 : for (auto pred : block->predecessors()) {
441 470932 : if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
442 : deferred = false;
443 : }
444 : }
445 405434 : if (deferred) {
446 : block->set_deferred(true);
447 : done = false;
448 : }
449 : }
450 : }
451 : }
452 181536 : }
453 :
454 31089075 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455 : block->AddSuccessor(succ);
456 : succ->AddPredecessor(block);
457 31089322 : }
458 :
459 39637 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460 140764 : for (BasicBlock* const successor : from->successors()) {
461 : to->AddSuccessor(successor);
462 186570 : for (BasicBlock*& predecessor : successor->predecessors()) {
463 63590 : if (predecessor == from) predecessor = to;
464 : }
465 : }
466 : from->ClearSuccessors();
467 39638 : }
468 :
469 10385979 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470 : block->set_control_input(node);
471 10385979 : SetBlockForNode(block, node);
472 10386131 : }
473 :
474 509690530 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475 764535738 : if (node->id() >= nodeid_to_block_.size()) {
476 31792912 : nodeid_to_block_.resize(node->id() + 1);
477 : }
478 509690644 : nodeid_to_block_[node->id()] = block;
479 254845322 : }
480 :
481 14 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
482 534 : for (BasicBlock* block :
483 118 : ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484 104 : if (block->rpo_number() == -1) {
485 0 : os << "--- BLOCK id:" << block->id().ToInt();
486 : } else {
487 104 : os << "--- BLOCK B" << block->rpo_number();
488 : }
489 104 : if (block->deferred()) os << " (deferred)";
490 104 : if (block->PredecessorCount() != 0) os << " <- ";
491 : bool comma = false;
492 428 : for (BasicBlock const* predecessor : block->predecessors()) {
493 110 : if (comma) os << ", ";
494 : comma = true;
495 110 : if (predecessor->rpo_number() == -1) {
496 0 : os << "id:" << predecessor->id().ToInt();
497 : } else {
498 110 : os << "B" << predecessor->rpo_number();
499 : }
500 : }
501 104 : os << " ---\n";
502 552 : for (Node* node : *block) {
503 344 : os << " " << *node;
504 344 : if (NodeProperties::IsTyped(node)) {
505 42 : os << " : " << NodeProperties::GetType(node);
506 : }
507 344 : os << "\n";
508 : }
509 : BasicBlock::Control control = block->control();
510 104 : if (control != BasicBlock::kNone) {
511 90 : os << " ";
512 90 : if (block->control_input() != nullptr) {
513 34 : os << *block->control_input();
514 : } else {
515 56 : os << "Goto";
516 : }
517 90 : os << " -> ";
518 : comma = false;
519 400 : for (BasicBlock const* successor : block->successors()) {
520 110 : if (comma) os << ", ";
521 : comma = true;
522 110 : if (successor->rpo_number() == -1) {
523 0 : os << "id:" << successor->id().ToInt();
524 : } else {
525 110 : os << "B" << successor->rpo_number();
526 : }
527 : }
528 90 : os << "\n";
529 : }
530 : }
531 14 : return os;
532 : }
533 :
534 : } // namespace compiler
535 : } // namespace internal
536 178779 : } // namespace v8
|
