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 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 id_(id) { 34 } 35 36 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 if (loop_end_ == nullptr) return false; // This is not a loop. 41 return block->rpo_number_ >= rpo_number_ && 42 block->rpo_number_ < loop_end_->rpo_number_; 43 } 44 45 46 void BasicBlock::AddSuccessor(BasicBlock* successor) { 47 successors_.push_back(successor); 48 } 49 50 51 void BasicBlock::AddPredecessor(BasicBlock* predecessor) { 52 predecessors_.push_back(predecessor); 53 } 54 55 56 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); } 57 58 59 void BasicBlock::set_control(Control control) { 60 control_ = control; 61 } 62 63 64 void BasicBlock::set_control_input(Node* control_input) { 65 control_input_ = control_input; 66 } 67 68 69 void BasicBlock::set_loop_depth(int32_t loop_depth) { 70 loop_depth_ = loop_depth; 71 } 72 73 74 void BasicBlock::set_rpo_number(int32_t rpo_number) { 75 rpo_number_ = rpo_number; 76 } 77 78 79 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; } 80 81 82 void BasicBlock::set_loop_header(BasicBlock* loop_header) { 83 loop_header_ = loop_header; 84 } 85 86 87 // static 88 BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { 89 while (b1 != b2) { 90 if (b1->dominator_depth() < b2->dominator_depth()) { 91 b2 = b2->dominator(); 92 } else { 93 b1 = b1->dominator(); 94 } 95 } 96 return b1; 97 } 98 99 void BasicBlock::Print() { StdoutStream{} << this; } 100 101 std::ostream& operator<<(std::ostream& os, const BasicBlock& block) { 102 os << "B" << block.id(); 103 #if DEBUG 104 AssemblerDebugInfo info = block.debug_info(); 105 if (info.name) os << info; 106 // Print predecessor blocks for better debugging. 107 const int kMaxDisplayedBlocks = 4; 108 int i = 0; 109 const BasicBlock* current_block = █ 110 while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) { 111 current_block = current_block->predecessors().front(); 112 os << " <= B" << current_block->id(); 113 info = current_block->debug_info(); 114 if (info.name) os << info; 115 } 116 #endif 117 return os; 118 } 119 120 std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) { 121 switch (c) { 122 case BasicBlock::kNone: 123 return os << "none"; 124 case BasicBlock::kGoto: 125 return os << "goto"; 126 case BasicBlock::kCall: 127 return os << "call"; 128 case BasicBlock::kBranch: 129 return os << "branch"; 130 case BasicBlock::kSwitch: 131 return os << "switch"; 132 case BasicBlock::kDeoptimize: 133 return os << "deoptimize"; 134 case BasicBlock::kTailCall: 135 return os << "tailcall"; 136 case BasicBlock::kReturn: 137 return os << "return"; 138 case BasicBlock::kThrow: 139 return os << "throw"; 140 } 141 UNREACHABLE(); 142 } 143 144 145 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) { 146 return os << id.ToSize(); 147 } 148 149 150 Schedule::Schedule(Zone* zone, size_t node_count_hint) 151 : zone_(zone), 152 all_blocks_(zone), 153 nodeid_to_block_(zone), 154 rpo_order_(zone), 155 start_(NewBasicBlock()), 156 end_(NewBasicBlock()) { 157 nodeid_to_block_.reserve(node_count_hint); 158 } 159 160 161 BasicBlock* Schedule::block(Node* node) const { 162 if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { 163 return nodeid_to_block_[node->id()]; 164 } 165 return nullptr; 166 } 167 168 169 bool Schedule::IsScheduled(Node* node) { 170 if (node->id() >= nodeid_to_block_.size()) return false; 171 return nodeid_to_block_[node->id()] != nullptr; 172 } 173 174 175 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) { 176 DCHECK(block_id.ToSize() < all_blocks_.size()); 177 return all_blocks_[block_id.ToSize()]; 178 } 179 180 181 bool Schedule::SameBasicBlock(Node* a, Node* b) const { 182 BasicBlock* block = this->block(a); 183 return block != nullptr && block == this->block(b); 184 } 185 186 187 BasicBlock* Schedule::NewBasicBlock() { 188 BasicBlock* block = new (zone_) 189 BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size())); 190 all_blocks_.push_back(block); 191 return block; 192 } 193 194 195 void Schedule::PlanNode(BasicBlock* block, Node* node) { 196 if (FLAG_trace_turbo_scheduler) { 197 StdoutStream{} << "Planning #" << node->id() << ":" 198 << node->op()->mnemonic() << " for future add to B" 199 << block->id() << "\n"; 200 } 201 DCHECK_NULL(this->block(node)); 202 SetBlockForNode(block, node); 203 } 204 205 206 void Schedule::AddNode(BasicBlock* block, Node* node) { 207 if (FLAG_trace_turbo_scheduler) { 208 StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic() 209 << " to B" << block->id() << "\n"; 210 } 211 DCHECK(this->block(node) == nullptr || this->block(node) == block); 212 block->AddNode(node); 213 SetBlockForNode(block, node); 214 } 215 216 217 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) { 218 DCHECK_EQ(BasicBlock::kNone, block->control()); 219 block->set_control(BasicBlock::kGoto); 220 AddSuccessor(block, succ); 221 } 222 223 #if DEBUG 224 namespace { 225 226 bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) { 227 switch (opcode) { 228 #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name: 229 JS_OP_LIST(BUILD_BLOCK_JS_CASE) 230 #undef BUILD_BLOCK_JS_CASE 231 case IrOpcode::kCall: 232 case IrOpcode::kCallWithCallerSavedRegisters: 233 return true; 234 default: 235 return false; 236 } 237 } 238 239 } // namespace 240 #endif // DEBUG 241 242 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 243 BasicBlock* exception_block) { 244 DCHECK_EQ(BasicBlock::kNone, block->control()); 245 DCHECK(IsPotentiallyThrowingCall(call->opcode())); 246 block->set_control(BasicBlock::kCall); 247 AddSuccessor(block, success_block); 248 AddSuccessor(block, exception_block); 249 SetControlInput(block, call); 250 } 251 252 253 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 254 BasicBlock* fblock) { 255 DCHECK_EQ(BasicBlock::kNone, block->control()); 256 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); 257 block->set_control(BasicBlock::kBranch); 258 AddSuccessor(block, tblock); 259 AddSuccessor(block, fblock); 260 SetControlInput(block, branch); 261 } 262 263 264 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 265 size_t succ_count) { 266 DCHECK_EQ(BasicBlock::kNone, block->control()); 267 DCHECK_EQ(IrOpcode::kSwitch, sw->opcode()); 268 block->set_control(BasicBlock::kSwitch); 269 for (size_t index = 0; index < succ_count; ++index) { 270 AddSuccessor(block, succ_blocks[index]); 271 } 272 SetControlInput(block, sw); 273 } 274 275 276 void Schedule::AddTailCall(BasicBlock* block, Node* input) { 277 DCHECK_EQ(BasicBlock::kNone, block->control()); 278 block->set_control(BasicBlock::kTailCall); 279 SetControlInput(block, input); 280 if (block != end()) AddSuccessor(block, end()); 281 } 282 283 284 void Schedule::AddReturn(BasicBlock* block, Node* input) { 285 DCHECK_EQ(BasicBlock::kNone, block->control()); 286 block->set_control(BasicBlock::kReturn); 287 SetControlInput(block, input); 288 if (block != end()) AddSuccessor(block, end()); 289 } 290 291 292 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) { 293 DCHECK_EQ(BasicBlock::kNone, block->control()); 294 block->set_control(BasicBlock::kDeoptimize); 295 SetControlInput(block, input); 296 if (block != end()) AddSuccessor(block, end()); 297 } 298 299 300 void Schedule::AddThrow(BasicBlock* block, Node* input) { 301 DCHECK_EQ(BasicBlock::kNone, block->control()); 302 block->set_control(BasicBlock::kThrow); 303 SetControlInput(block, input); 304 if (block != end()) AddSuccessor(block, end()); 305 } 306 307 308 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 309 BasicBlock* tblock, BasicBlock* fblock) { 310 DCHECK_NE(BasicBlock::kNone, block->control()); 311 DCHECK_EQ(BasicBlock::kNone, end->control()); 312 end->set_control(block->control()); 313 block->set_control(BasicBlock::kBranch); 314 MoveSuccessors(block, end); 315 AddSuccessor(block, tblock); 316 AddSuccessor(block, fblock); 317 if (block->control_input() != nullptr) { 318 SetControlInput(end, block->control_input()); 319 } 320 SetControlInput(block, branch); 321 } 322 323 324 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 325 BasicBlock** succ_blocks, size_t succ_count) { 326 DCHECK_NE(BasicBlock::kNone, block->control()); 327 DCHECK_EQ(BasicBlock::kNone, end->control()); 328 end->set_control(block->control()); 329 block->set_control(BasicBlock::kSwitch); 330 MoveSuccessors(block, end); 331 for (size_t index = 0; index < succ_count; ++index) { 332 AddSuccessor(block, succ_blocks[index]); 333 } 334 if (block->control_input() != nullptr) { 335 SetControlInput(end, block->control_input()); 336 } 337 SetControlInput(block, sw); 338 } 339 340 void Schedule::EnsureCFGWellFormedness() { 341 // Make a copy of all the blocks for the iteration, since adding the split 342 // edges will allocate new blocks. 343 BasicBlockVector all_blocks_copy(all_blocks_); 344 345 // Insert missing split edge blocks. 346 for (auto block : all_blocks_copy) { 347 if (block->PredecessorCount() > 1) { 348 if (block != end_) { 349 EnsureSplitEdgeForm(block); 350 } 351 if (block->deferred()) { 352 EnsureDeferredCodeSingleEntryPoint(block); 353 } 354 } else { 355 EliminateNoopPhiNodes(block); 356 } 357 } 358 } 359 360 void Schedule::EliminateNoopPhiNodes(BasicBlock* block) { 361 // Ensure that useless phi nodes in blocks that only have a single predecessor 362 // -- which can happen with the automatically generated code in the CSA and 363 // torque -- are pruned. 364 if (block->PredecessorCount() == 1) { 365 for (size_t i = 0; i < block->NodeCount();) { 366 Node* node = block->NodeAt(i); 367 if (node->opcode() == IrOpcode::kPhi) { 368 node->ReplaceUses(node->InputAt(0)); 369 block->RemoveNode(block->begin() + i); 370 } else { 371 ++i; 372 } 373 } 374 } 375 } 376 377 void Schedule::EnsureSplitEdgeForm(BasicBlock* block) { 378 DCHECK(block->PredecessorCount() > 1 && block != end_); 379 for (auto current_pred = block->predecessors().begin(); 380 current_pred != block->predecessors().end(); ++current_pred) { 381 BasicBlock* pred = *current_pred; 382 if (pred->SuccessorCount() > 1) { 383 // Found a predecessor block with multiple successors. 384 BasicBlock* split_edge_block = NewBasicBlock(); 385 split_edge_block->set_control(BasicBlock::kGoto); 386 split_edge_block->successors().push_back(block); 387 split_edge_block->predecessors().push_back(pred); 388 split_edge_block->set_deferred(block->deferred()); 389 *current_pred = split_edge_block; 390 // Find a corresponding successor in the previous block, replace it 391 // with the split edge block... but only do it once, since we only 392 // replace the previous blocks in the current block one at a time. 393 for (auto successor = pred->successors().begin(); 394 successor != pred->successors().end(); ++successor) { 395 if (*successor == block) { 396 *successor = split_edge_block; 397 break; 398 } 399 } 400 } 401 } 402 } 403 404 void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) { 405 // If a deferred block has multiple predecessors, they have to 406 // all be deferred. Otherwise, we can run into a situation where a range 407 // that spills only in deferred blocks inserts its spill in the block, but 408 // other ranges need moves inserted by ResolveControlFlow in the predecessors, 409 // which may clobber the register of this range. 410 // To ensure that, when a deferred block has multiple predecessors, and some 411 // are not deferred, we add a non-deferred block to collect all such edges. 412 413 DCHECK(block->deferred() && block->PredecessorCount() > 1); 414 bool all_deferred = true; 415 for (auto current_pred = block->predecessors().begin(); 416 current_pred != block->predecessors().end(); ++current_pred) { 417 BasicBlock* pred = *current_pred; 418 if (!pred->deferred()) { 419 all_deferred = false; 420 break; 421 } 422 } 423 424 if (all_deferred) return; 425 BasicBlock* merger = NewBasicBlock(); 426 merger->set_control(BasicBlock::kGoto); 427 merger->successors().push_back(block); 428 for (auto current_pred = block->predecessors().begin(); 429 current_pred != block->predecessors().end(); ++current_pred) { 430 BasicBlock* pred = *current_pred; 431 merger->predecessors().push_back(pred); 432 pred->successors().clear(); 433 pred->successors().push_back(merger); 434 } 435 merger->set_deferred(false); 436 block->predecessors().clear(); 437 block->predecessors().push_back(merger); 438 MovePhis(block, merger); 439 } 440 441 void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) { 442 for (size_t i = 0; i < from->NodeCount();) { 443 Node* node = from->NodeAt(i); 444 if (node->opcode() == IrOpcode::kPhi) { 445 to->AddNode(node); 446 from->RemoveNode(from->begin() + i); 447 DCHECK_EQ(nodeid_to_block_[node->id()], from); 448 nodeid_to_block_[node->id()] = to; 449 } else { 450 ++i; 451 } 452 } 453 } 454 455 void Schedule::PropagateDeferredMark() { 456 // Push forward the deferred block marks through newly inserted blocks and 457 // other improperly marked blocks until a fixed point is reached. 458 // TODO(danno): optimize the propagation 459 bool done = false; 460 while (!done) { 461 done = true; 462 for (auto block : all_blocks_) { 463 if (!block->deferred()) { 464 bool deferred = block->PredecessorCount() > 0; 465 for (auto pred : block->predecessors()) { 466 if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) { 467 deferred = false; 468 } 469 } 470 if (deferred) { 471 block->set_deferred(true); 472 done = false; 473 } 474 } 475 } 476 } 477 } 478 479 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) { 480 block->AddSuccessor(succ); 481 succ->AddPredecessor(block); 482 } 483 484 485 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) { 486 for (BasicBlock* const successor : from->successors()) { 487 to->AddSuccessor(successor); 488 for (BasicBlock*& predecessor : successor->predecessors()) { 489 if (predecessor == from) predecessor = to; 490 } 491 } 492 from->ClearSuccessors(); 493 } 494 495 496 void Schedule::SetControlInput(BasicBlock* block, Node* node) { 497 block->set_control_input(node); 498 SetBlockForNode(block, node); 499 } 500 501 502 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) { 503 if (node->id() >= nodeid_to_block_.size()) { 504 nodeid_to_block_.resize(node->id() + 1); 505 } 506 nodeid_to_block_[node->id()] = block; 507 } 508 509 510 std::ostream& operator<<(std::ostream& os, const Schedule& s) { 511 for (BasicBlock* block : 512 ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) { 513 if (block->rpo_number() == -1) { 514 os << "--- BLOCK id:" << block->id().ToInt(); 515 } else { 516 os << "--- BLOCK B" << block->rpo_number(); 517 } 518 if (block->deferred()) os << " (deferred)"; 519 if (block->PredecessorCount() != 0) os << " <- "; 520 bool comma = false; 521 for (BasicBlock const* predecessor : block->predecessors()) { 522 if (comma) os << ", "; 523 comma = true; 524 if (predecessor->rpo_number() == -1) { 525 os << "id:" << predecessor->id().ToInt(); 526 } else { 527 os << "B" << predecessor->rpo_number(); 528 } 529 } 530 os << " ---\n"; 531 for (Node* node : *block) { 532 os << " " << *node; 533 if (NodeProperties::IsTyped(node)) { 534 os << " : " << NodeProperties::GetType(node); 535 } 536 os << "\n"; 537 } 538 BasicBlock::Control control = block->control(); 539 if (control != BasicBlock::kNone) { 540 os << " "; 541 if (block->control_input() != nullptr) { 542 os << *block->control_input(); 543 } else { 544 os << "Goto"; 545 } 546 os << " -> "; 547 comma = false; 548 for (BasicBlock const* successor : block->successors()) { 549 if (comma) os << ", "; 550 comma = true; 551 if (successor->rpo_number() == -1) { 552 os << "id:" << successor->id().ToInt(); 553 } else { 554 os << "B" << successor->rpo_number(); 555 } 556 } 557 os << "\n"; 558 } 559 } 560 return os; 561 } 562 563 } // namespace compiler 564 } // namespace internal 565 } // namespace v8 566