5 #include "src/compiler/schedule.h" 7 #include "src/compiler/node-properties.h" 8 #include "src/compiler/node.h" 9 #include "src/ostreams.h" 15 BasicBlock::BasicBlock(Zone* zone, Id
id)
22 loop_header_(nullptr),
26 control_input_(nullptr),
31 debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
36 bool BasicBlock::LoopContains(BasicBlock* block)
const {
38 DCHECK_LE(0, rpo_number_);
39 DCHECK_LE(0, block->rpo_number_);
40 if (loop_end_ ==
nullptr)
return false;
41 return block->rpo_number_ >= rpo_number_ &&
42 block->rpo_number_ < loop_end_->rpo_number_;
45 void BasicBlock::AddSuccessor(BasicBlock* successor) {
46 successors_.push_back(successor);
49 void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50 predecessors_.push_back(predecessor);
53 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
55 void BasicBlock::set_control(Control control) { control_ = control; }
57 void BasicBlock::set_control_input(Node* control_input) {
58 if (!nodes_.empty() && control_input == nodes_.back()) {
61 control_input_ = control_input;
64 void BasicBlock::set_loop_depth(int32_t loop_depth) {
65 loop_depth_ = loop_depth;
68 void BasicBlock::set_rpo_number(int32_t rpo_number) {
69 rpo_number_ = rpo_number;
72 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
74 void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75 loop_header_ = loop_header;
79 BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
81 if (b1->dominator_depth() < b2->dominator_depth()) {
90 void BasicBlock::Print() { StdoutStream{} <<
this; }
92 std::ostream& operator<<(std::ostream& os,
const BasicBlock& block) {
93 os <<
"B" << block.id();
95 AssemblerDebugInfo info = block.debug_info();
96 if (info.name) os << info;
98 const int kMaxDisplayedBlocks = 4;
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;
111 std::ostream& operator<<(std::ostream& os,
const BasicBlock::Control& c) {
113 case BasicBlock::kNone:
115 case BasicBlock::kGoto:
117 case BasicBlock::kCall:
119 case BasicBlock::kBranch:
120 return os <<
"branch";
121 case BasicBlock::kSwitch:
122 return os <<
"switch";
123 case BasicBlock::kDeoptimize:
124 return os <<
"deoptimize";
125 case BasicBlock::kTailCall:
126 return os <<
"tailcall";
127 case BasicBlock::kReturn:
128 return os <<
"return";
129 case BasicBlock::kThrow:
130 return os <<
"throw";
135 std::ostream& operator<<(std::ostream& os,
const BasicBlock::Id&
id) {
136 return os <<
id.ToSize();
139 Schedule::Schedule(Zone* zone,
size_t node_count_hint)
142 nodeid_to_block_(zone),
144 start_(NewBasicBlock()),
145 end_(NewBasicBlock()) {
146 nodeid_to_block_.reserve(node_count_hint);
149 BasicBlock* Schedule::block(Node* node)
const {
150 if (node->id() <
static_cast<NodeId
>(nodeid_to_block_.size())) {
151 return nodeid_to_block_[node->id()];
156 bool Schedule::IsScheduled(Node* node) {
157 if (node->id() >= nodeid_to_block_.size())
return false;
158 return nodeid_to_block_[node->id()] !=
nullptr;
161 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162 DCHECK(block_id.ToSize() < all_blocks_.size());
163 return all_blocks_[block_id.ToSize()];
166 bool Schedule::SameBasicBlock(Node* a, Node* b)
const {
167 BasicBlock* block = this->block(a);
168 return block !=
nullptr && block == this->block(b);
171 BasicBlock* Schedule::NewBasicBlock() {
172 BasicBlock* block =
new (zone_)
173 BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174 all_blocks_.push_back(block);
178 void Schedule::PlanNode(BasicBlock* block, Node* node) {
179 if (FLAG_trace_turbo_scheduler) {
180 StdoutStream{} <<
"Planning #" << node->id() <<
":" 181 << node->op()->mnemonic() <<
" for future add to B" 182 << block->id() <<
"\n";
184 DCHECK_NULL(this->block(node));
185 SetBlockForNode(block, node);
188 void Schedule::AddNode(BasicBlock* block, Node* node) {
189 if (FLAG_trace_turbo_scheduler) {
190 StdoutStream{} <<
"Adding #" << node->id() <<
":" << node->op()->mnemonic()
191 <<
" to B" << block->id() <<
"\n";
193 DCHECK(this->block(node) ==
nullptr || this->block(node) == block);
194 block->AddNode(node);
195 SetBlockForNode(block, node);
198 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
199 DCHECK_EQ(BasicBlock::kNone, block->control());
200 block->set_control(BasicBlock::kGoto);
201 AddSuccessor(block, succ);
207 bool IsPotentiallyThrowingCall(IrOpcode::Value 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:
223 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 SetControlInput(block, call);
233 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 SetControlInput(block, branch);
243 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
245 DCHECK_EQ(BasicBlock::kNone, block->control());
246 DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
247 block->set_control(BasicBlock::kSwitch);
248 for (
size_t index = 0; index < succ_count; ++index) {
249 AddSuccessor(block, succ_blocks[index]);
251 SetControlInput(block, sw);
254 void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255 DCHECK_EQ(BasicBlock::kNone, block->control());
256 block->set_control(BasicBlock::kTailCall);
257 SetControlInput(block, input);
258 if (block != end()) AddSuccessor(block, end());
261 void Schedule::AddReturn(BasicBlock* block, Node* input) {
262 DCHECK_EQ(BasicBlock::kNone, block->control());
263 block->set_control(BasicBlock::kReturn);
264 SetControlInput(block, input);
265 if (block != end()) AddSuccessor(block, end());
268 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269 DCHECK_EQ(BasicBlock::kNone, block->control());
270 block->set_control(BasicBlock::kDeoptimize);
271 SetControlInput(block, input);
272 if (block != end()) AddSuccessor(block, end());
275 void Schedule::AddThrow(BasicBlock* block, Node* input) {
276 DCHECK_EQ(BasicBlock::kNone, block->control());
277 block->set_control(BasicBlock::kThrow);
278 SetControlInput(block, input);
279 if (block != end()) AddSuccessor(block, end());
282 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 MoveSuccessors(block, end);
289 AddSuccessor(block, tblock);
290 AddSuccessor(block, fblock);
291 if (block->control_input() !=
nullptr) {
292 SetControlInput(end, block->control_input());
294 SetControlInput(block, branch);
297 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 MoveSuccessors(block, end);
304 for (
size_t index = 0; index < succ_count; ++index) {
305 AddSuccessor(block, succ_blocks[index]);
307 if (block->control_input() !=
nullptr) {
308 SetControlInput(end, block->control_input());
310 SetControlInput(block, sw);
313 void Schedule::EnsureCFGWellFormedness() {
316 BasicBlockVector all_blocks_copy(all_blocks_);
319 for (BasicBlock* block : all_blocks_copy) {
320 if (block->PredecessorCount() > 1) {
322 EnsureSplitEdgeForm(block);
324 if (block->deferred()) {
325 EnsureDeferredCodeSingleEntryPoint(block);
330 EliminateRedundantPhiNodes();
333 void Schedule::EliminateRedundantPhiNodes() {
340 bool reached_fixed_point =
false;
341 while (!reached_fixed_point) {
342 reached_fixed_point =
true;
343 for (BasicBlock* block : all_blocks_) {
344 int predecessor_count =
static_cast<int>(block->PredecessorCount());
345 for (
size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346 Node* node = block->NodeAt(node_pos);
347 if (node->opcode() == IrOpcode::kPhi) {
348 Node* first_input = node->InputAt(0);
349 bool inputs_equal =
true;
350 for (
int i = 1;
i < predecessor_count; ++
i) {
351 Node* input = node->InputAt(
i);
352 if (input != first_input && input != node) {
353 inputs_equal =
false;
357 if (!inputs_equal)
continue;
358 node->ReplaceUses(first_input);
359 block->RemoveNode(block->begin() + node_pos);
361 reached_fixed_point =
false;
368 void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
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);
379 void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
388 DCHECK(block->deferred() && block->PredecessorCount() > 1);
389 bool all_deferred =
true;
390 for (
auto current_pred = block->predecessors().begin();
391 current_pred != block->predecessors().end(); ++current_pred) {
392 BasicBlock* pred = *current_pred;
393 if (!pred->deferred()) {
394 all_deferred =
false;
399 if (all_deferred)
return;
400 BasicBlock* merger = NewBasicBlock();
401 merger->set_control(BasicBlock::kGoto);
402 merger->successors().push_back(block);
403 for (
auto current_pred = block->predecessors().begin();
404 current_pred != block->predecessors().end(); ++current_pred) {
405 BasicBlock* pred = *current_pred;
406 merger->predecessors().push_back(pred);
407 pred->successors().clear();
408 pred->successors().push_back(merger);
410 merger->set_deferred(
false);
411 block->predecessors().clear();
412 block->predecessors().push_back(merger);
413 MovePhis(block, merger);
416 void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417 for (
size_t i = 0;
i < from->NodeCount();) {
418 Node* node = from->NodeAt(
i);
419 if (node->opcode() == IrOpcode::kPhi) {
421 from->RemoveNode(from->begin() +
i);
422 DCHECK_EQ(nodeid_to_block_[node->id()], from);
423 nodeid_to_block_[node->id()] = to;
430 void Schedule::PropagateDeferredMark() {
437 for (
auto block : all_blocks_) {
438 if (!block->deferred()) {
439 bool deferred = block->PredecessorCount() > 0;
440 for (
auto pred : block->predecessors()) {
441 if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
446 block->set_deferred(
true);
454 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455 block->AddSuccessor(succ);
456 succ->AddPredecessor(block);
459 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460 for (BasicBlock*
const successor : from->successors()) {
461 to->AddSuccessor(successor);
462 for (BasicBlock*& predecessor : successor->predecessors()) {
463 if (predecessor == from) predecessor = to;
466 from->ClearSuccessors();
469 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470 block->set_control_input(node);
471 SetBlockForNode(block, node);
474 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475 if (node->id() >= nodeid_to_block_.size()) {
476 nodeid_to_block_.resize(node->id() + 1);
478 nodeid_to_block_[node->id()] = block;
481 std::ostream& operator<<(std::ostream& os,
const Schedule& s) {
482 for (BasicBlock* block :
483 ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484 if (block->rpo_number() == -1) {
485 os <<
"--- BLOCK id:" << block->id().ToInt();
487 os <<
"--- BLOCK B" << block->rpo_number();
489 if (block->deferred()) os <<
" (deferred)";
490 if (block->PredecessorCount() != 0) os <<
" <- ";
492 for (BasicBlock
const* predecessor : block->predecessors()) {
493 if (comma) os <<
", ";
495 if (predecessor->rpo_number() == -1) {
496 os <<
"id:" << predecessor->id().ToInt();
498 os <<
"B" << predecessor->rpo_number();
502 for (Node* node : *block) {
504 if (NodeProperties::IsTyped(node)) {
505 os <<
" : " << NodeProperties::GetType(node);
509 BasicBlock::Control control = block->control();
510 if (control != BasicBlock::kNone) {
512 if (block->control_input() !=
nullptr) {
513 os << *block->control_input();
519 for (BasicBlock
const* successor : block->successors()) {
520 if (comma) os <<
", ";
522 if (successor->rpo_number() == -1) {
523 os <<
"id:" << successor->id().ToInt();
525 os <<
"B" << successor->rpo_number();