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.h" 8 #include "src/compiler/node-properties.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 id_(id) {} 31 32 33 bool BasicBlock::LoopContains(BasicBlock* block) const { 34 // RPO numbers must be initialized. 35 DCHECK(rpo_number_ >= 0); 36 DCHECK(block->rpo_number_ >= 0); 37 if (loop_end_ == nullptr) return false; // This is not a loop. 38 return block->rpo_number_ >= rpo_number_ && 39 block->rpo_number_ < loop_end_->rpo_number_; 40 } 41 42 43 void BasicBlock::AddSuccessor(BasicBlock* successor) { 44 successors_.push_back(successor); 45 } 46 47 48 void BasicBlock::AddPredecessor(BasicBlock* predecessor) { 49 predecessors_.push_back(predecessor); 50 } 51 52 53 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); } 54 55 56 void BasicBlock::set_control(Control control) { 57 control_ = control; 58 } 59 60 61 void BasicBlock::set_control_input(Node* control_input) { 62 control_input_ = control_input; 63 } 64 65 66 void BasicBlock::set_loop_depth(int32_t loop_depth) { 67 loop_depth_ = loop_depth; 68 } 69 70 71 void BasicBlock::set_rpo_number(int32_t rpo_number) { 72 rpo_number_ = rpo_number; 73 } 74 75 76 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; } 77 78 79 void BasicBlock::set_loop_header(BasicBlock* loop_header) { 80 loop_header_ = loop_header; 81 } 82 83 84 // static 85 BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { 86 while (b1 != b2) { 87 if (b1->dominator_depth() < b2->dominator_depth()) { 88 b2 = b2->dominator(); 89 } else { 90 b1 = b1->dominator(); 91 } 92 } 93 return b1; 94 } 95 96 97 std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) { 98 switch (c) { 99 case BasicBlock::kNone: 100 return os << "none"; 101 case BasicBlock::kGoto: 102 return os << "goto"; 103 case BasicBlock::kCall: 104 return os << "call"; 105 case BasicBlock::kBranch: 106 return os << "branch"; 107 case BasicBlock::kSwitch: 108 return os << "switch"; 109 case BasicBlock::kDeoptimize: 110 return os << "deoptimize"; 111 case BasicBlock::kTailCall: 112 return os << "tailcall"; 113 case BasicBlock::kReturn: 114 return os << "return"; 115 case BasicBlock::kThrow: 116 return os << "throw"; 117 } 118 UNREACHABLE(); 119 return os; 120 } 121 122 123 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) { 124 return os << id.ToSize(); 125 } 126 127 128 Schedule::Schedule(Zone* zone, size_t node_count_hint) 129 : zone_(zone), 130 all_blocks_(zone), 131 nodeid_to_block_(zone), 132 rpo_order_(zone), 133 start_(NewBasicBlock()), 134 end_(NewBasicBlock()) { 135 nodeid_to_block_.reserve(node_count_hint); 136 } 137 138 139 BasicBlock* Schedule::block(Node* node) const { 140 if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { 141 return nodeid_to_block_[node->id()]; 142 } 143 return nullptr; 144 } 145 146 147 bool Schedule::IsScheduled(Node* node) { 148 if (node->id() >= nodeid_to_block_.size()) return false; 149 return nodeid_to_block_[node->id()] != nullptr; 150 } 151 152 153 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) { 154 DCHECK(block_id.ToSize() < all_blocks_.size()); 155 return all_blocks_[block_id.ToSize()]; 156 } 157 158 159 bool Schedule::SameBasicBlock(Node* a, Node* b) const { 160 BasicBlock* block = this->block(a); 161 return block != nullptr && block == this->block(b); 162 } 163 164 165 BasicBlock* Schedule::NewBasicBlock() { 166 BasicBlock* block = new (zone_) 167 BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size())); 168 all_blocks_.push_back(block); 169 return block; 170 } 171 172 173 void Schedule::PlanNode(BasicBlock* block, Node* node) { 174 if (FLAG_trace_turbo_scheduler) { 175 OFStream os(stdout); 176 os << "Planning #" << node->id() << ":" << node->op()->mnemonic() 177 << " for future add to B" << block->id() << "\n"; 178 } 179 DCHECK(this->block(node) == nullptr); 180 SetBlockForNode(block, node); 181 } 182 183 184 void Schedule::AddNode(BasicBlock* block, Node* node) { 185 if (FLAG_trace_turbo_scheduler) { 186 OFStream os(stdout); 187 os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B" 188 << block->id() << "\n"; 189 } 190 DCHECK(this->block(node) == nullptr || this->block(node) == block); 191 block->AddNode(node); 192 SetBlockForNode(block, node); 193 } 194 195 196 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) { 197 DCHECK_EQ(BasicBlock::kNone, block->control()); 198 block->set_control(BasicBlock::kGoto); 199 AddSuccessor(block, succ); 200 } 201 202 203 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 204 BasicBlock* exception_block) { 205 DCHECK_EQ(BasicBlock::kNone, block->control()); 206 DCHECK_EQ(IrOpcode::kCall, call->opcode()); 207 block->set_control(BasicBlock::kCall); 208 AddSuccessor(block, success_block); 209 AddSuccessor(block, exception_block); 210 SetControlInput(block, call); 211 } 212 213 214 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 215 BasicBlock* fblock) { 216 DCHECK_EQ(BasicBlock::kNone, block->control()); 217 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); 218 block->set_control(BasicBlock::kBranch); 219 AddSuccessor(block, tblock); 220 AddSuccessor(block, fblock); 221 SetControlInput(block, branch); 222 } 223 224 225 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 226 size_t succ_count) { 227 DCHECK_EQ(BasicBlock::kNone, block->control()); 228 DCHECK_EQ(IrOpcode::kSwitch, sw->opcode()); 229 block->set_control(BasicBlock::kSwitch); 230 for (size_t index = 0; index < succ_count; ++index) { 231 AddSuccessor(block, succ_blocks[index]); 232 } 233 SetControlInput(block, sw); 234 } 235 236 237 void Schedule::AddTailCall(BasicBlock* block, Node* input) { 238 DCHECK_EQ(BasicBlock::kNone, block->control()); 239 block->set_control(BasicBlock::kTailCall); 240 SetControlInput(block, input); 241 if (block != end()) AddSuccessor(block, end()); 242 } 243 244 245 void Schedule::AddReturn(BasicBlock* block, Node* input) { 246 DCHECK_EQ(BasicBlock::kNone, block->control()); 247 block->set_control(BasicBlock::kReturn); 248 SetControlInput(block, input); 249 if (block != end()) AddSuccessor(block, end()); 250 } 251 252 253 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) { 254 DCHECK_EQ(BasicBlock::kNone, block->control()); 255 block->set_control(BasicBlock::kDeoptimize); 256 SetControlInput(block, input); 257 if (block != end()) AddSuccessor(block, end()); 258 } 259 260 261 void Schedule::AddThrow(BasicBlock* block, Node* input) { 262 DCHECK_EQ(BasicBlock::kNone, block->control()); 263 block->set_control(BasicBlock::kThrow); 264 SetControlInput(block, input); 265 if (block != end()) AddSuccessor(block, end()); 266 } 267 268 269 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 270 BasicBlock* tblock, BasicBlock* fblock) { 271 DCHECK_NE(BasicBlock::kNone, block->control()); 272 DCHECK_EQ(BasicBlock::kNone, end->control()); 273 end->set_control(block->control()); 274 block->set_control(BasicBlock::kBranch); 275 MoveSuccessors(block, end); 276 AddSuccessor(block, tblock); 277 AddSuccessor(block, fblock); 278 if (block->control_input() != nullptr) { 279 SetControlInput(end, block->control_input()); 280 } 281 SetControlInput(block, branch); 282 } 283 284 285 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 286 BasicBlock** succ_blocks, size_t succ_count) { 287 DCHECK_NE(BasicBlock::kNone, block->control()); 288 DCHECK_EQ(BasicBlock::kNone, end->control()); 289 end->set_control(block->control()); 290 block->set_control(BasicBlock::kSwitch); 291 MoveSuccessors(block, end); 292 for (size_t index = 0; index < succ_count; ++index) { 293 AddSuccessor(block, succ_blocks[index]); 294 } 295 if (block->control_input() != nullptr) { 296 SetControlInput(end, block->control_input()); 297 } 298 SetControlInput(block, sw); 299 } 300 301 302 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) { 303 block->AddSuccessor(succ); 304 succ->AddPredecessor(block); 305 } 306 307 308 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) { 309 for (BasicBlock* const successor : from->successors()) { 310 to->AddSuccessor(successor); 311 for (BasicBlock*& predecessor : successor->predecessors()) { 312 if (predecessor == from) predecessor = to; 313 } 314 } 315 from->ClearSuccessors(); 316 } 317 318 319 void Schedule::SetControlInput(BasicBlock* block, Node* node) { 320 block->set_control_input(node); 321 SetBlockForNode(block, node); 322 } 323 324 325 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) { 326 if (node->id() >= nodeid_to_block_.size()) { 327 nodeid_to_block_.resize(node->id() + 1); 328 } 329 nodeid_to_block_[node->id()] = block; 330 } 331 332 333 std::ostream& operator<<(std::ostream& os, const Schedule& s) { 334 for (BasicBlock* block : *s.rpo_order()) { 335 os << "--- BLOCK B" << block->rpo_number(); 336 if (block->deferred()) os << " (deferred)"; 337 if (block->PredecessorCount() != 0) os << " <- "; 338 bool comma = false; 339 for (BasicBlock const* predecessor : block->predecessors()) { 340 if (comma) os << ", "; 341 comma = true; 342 os << "B" << predecessor->rpo_number(); 343 } 344 os << " ---\n"; 345 for (Node* node : *block) { 346 os << " " << *node; 347 if (NodeProperties::IsTyped(node)) { 348 Type* type = NodeProperties::GetType(node); 349 os << " : "; 350 type->PrintTo(os); 351 } 352 os << "\n"; 353 } 354 BasicBlock::Control control = block->control(); 355 if (control != BasicBlock::kNone) { 356 os << " "; 357 if (block->control_input() != nullptr) { 358 os << *block->control_input(); 359 } else { 360 os << "Goto"; 361 } 362 os << " -> "; 363 comma = false; 364 for (BasicBlock const* successor : block->successors()) { 365 if (comma) os << ", "; 366 comma = true; 367 os << "B" << successor->rpo_number(); 368 } 369 os << "\n"; 370 } 371 } 372 return os; 373 } 374 375 } // namespace compiler 376 } // namespace internal 377 } // namespace v8 378
