OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/schedule.h" | 5 #include "src/compiler/schedule.h" |
6 | 6 |
7 #include "src/compiler/node.h" | 7 #include "src/compiler/node.h" |
8 #include "src/compiler/node-properties.h" | 8 #include "src/compiler/node-properties.h" |
9 #include "src/ostreams.h" | 9 #include "src/ostreams.h" |
10 | 10 |
(...skipping 297 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
308 MoveSuccessors(block, end); | 308 MoveSuccessors(block, end); |
309 for (size_t index = 0; index < succ_count; ++index) { | 309 for (size_t index = 0; index < succ_count; ++index) { |
310 AddSuccessor(block, succ_blocks[index]); | 310 AddSuccessor(block, succ_blocks[index]); |
311 } | 311 } |
312 if (block->control_input() != nullptr) { | 312 if (block->control_input() != nullptr) { |
313 SetControlInput(end, block->control_input()); | 313 SetControlInput(end, block->control_input()); |
314 } | 314 } |
315 SetControlInput(block, sw); | 315 SetControlInput(block, sw); |
316 } | 316 } |
317 | 317 |
318 void Schedule::EnsureSplitEdgeForm() { | 318 void Schedule::EnsureCFGWellFormedness() { |
319 // Make a copy of all the blocks for the iteration, since adding the split | 319 // Make a copy of all the blocks for the iteration, since adding the split |
320 // edges will allocate new blocks. | 320 // edges will allocate new blocks. |
321 BasicBlockVector all_blocks_copy(all_blocks_); | 321 BasicBlockVector all_blocks_copy(all_blocks_); |
322 | 322 |
323 // Insert missing split edge blocks. | 323 // Insert missing split edge blocks. |
324 for (auto block : all_blocks_copy) { | 324 for (auto block : all_blocks_copy) { |
325 if (block->PredecessorCount() > 1 && block != end_) { | 325 if (block->PredecessorCount() > 1) { |
326 for (auto current_pred = block->predecessors().begin(); | 326 if (block != end_) { |
327 current_pred != block->predecessors().end(); ++current_pred) { | 327 EnsureSplitEdgeForm(block); |
328 BasicBlock* pred = *current_pred; | 328 } |
329 if (pred->SuccessorCount() > 1) { | 329 if (block->deferred()) { |
330 // Found a predecessor block with multiple successors. | 330 EnsureDeferredCodeSingleEntryPoint(block); |
331 BasicBlock* split_edge_block = NewBasicBlock(); | 331 } |
332 split_edge_block->set_control(BasicBlock::kGoto); | 332 } |
333 split_edge_block->successors().push_back(block); | 333 } |
334 split_edge_block->predecessors().push_back(pred); | 334 } |
335 split_edge_block->set_deferred(pred->deferred()); | 335 |
336 *current_pred = split_edge_block; | 336 void Schedule::EnsureSplitEdgeForm(BasicBlock* block) { |
337 // Find a corresponding successor in the previous block, replace it | 337 DCHECK(block->PredecessorCount() > 1 && block != end_); |
338 // with the split edge block... but only do it once, since we only | 338 for (auto current_pred = block->predecessors().begin(); |
339 // replace the previous blocks in the current block one at a time. | 339 current_pred != block->predecessors().end(); ++current_pred) { |
340 for (auto successor = pred->successors().begin(); | 340 BasicBlock* pred = *current_pred; |
341 successor != pred->successors().end(); ++successor) { | 341 if (pred->SuccessorCount() > 1) { |
342 if (*successor == block) { | 342 // Found a predecessor block with multiple successors. |
343 *successor = split_edge_block; | 343 BasicBlock* split_edge_block = NewBasicBlock(); |
344 break; | 344 split_edge_block->set_control(BasicBlock::kGoto); |
345 } | 345 split_edge_block->successors().push_back(block); |
346 } | 346 split_edge_block->predecessors().push_back(pred); |
| 347 split_edge_block->set_deferred(pred->deferred()); |
| 348 *current_pred = split_edge_block; |
| 349 // Find a corresponding successor in the previous block, replace it |
| 350 // with the split edge block... but only do it once, since we only |
| 351 // replace the previous blocks in the current block one at a time. |
| 352 for (auto successor = pred->successors().begin(); |
| 353 successor != pred->successors().end(); ++successor) { |
| 354 if (*successor == block) { |
| 355 *successor = split_edge_block; |
| 356 break; |
347 } | 357 } |
348 } | 358 } |
349 } | 359 } |
350 } | 360 } |
351 } | 361 } |
352 | 362 |
| 363 void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) { |
| 364 // If a deferred block has multiple predecessors, they have to |
| 365 // all be deferred. Otherwise, we can run into a situation where a range |
| 366 // that spills only in deferred blocks inserts its spill in the block, but |
| 367 // other ranges need moves inserted by ResolveControlFlow in the predecessors, |
| 368 // which may clobber the register of this range. |
| 369 // To ensure that, when a deferred block has multiple predecessors, and some |
| 370 // are not deferred, we add a non-deferred block to collect all such edges. |
| 371 |
| 372 DCHECK(block->deferred() && block->PredecessorCount() > 1); |
| 373 bool all_deferred = true; |
| 374 for (auto current_pred = block->predecessors().begin(); |
| 375 current_pred != block->predecessors().end(); ++current_pred) { |
| 376 BasicBlock* pred = *current_pred; |
| 377 if (!pred->deferred()) { |
| 378 all_deferred = false; |
| 379 break; |
| 380 } |
| 381 } |
| 382 |
| 383 if (all_deferred) return; |
| 384 BasicBlock* merger = NewBasicBlock(); |
| 385 merger->set_control(BasicBlock::kGoto); |
| 386 merger->successors().push_back(block); |
| 387 for (auto current_pred = block->predecessors().begin(); |
| 388 current_pred != block->predecessors().end(); ++current_pred) { |
| 389 BasicBlock* pred = *current_pred; |
| 390 merger->predecessors().push_back(pred); |
| 391 pred->successors().clear(); |
| 392 pred->successors().push_back(merger); |
| 393 } |
| 394 merger->set_deferred(false); |
| 395 block->predecessors().clear(); |
| 396 block->predecessors().push_back(merger); |
| 397 } |
| 398 |
353 void Schedule::PropagateDeferredMark() { | 399 void Schedule::PropagateDeferredMark() { |
354 // Push forward the deferred block marks through newly inserted blocks and | 400 // Push forward the deferred block marks through newly inserted blocks and |
355 // other improperly marked blocks until a fixed point is reached. | 401 // other improperly marked blocks until a fixed point is reached. |
356 // TODO(danno): optimize the propagation | 402 // TODO(danno): optimize the propagation |
357 bool done = false; | 403 bool done = false; |
358 while (!done) { | 404 while (!done) { |
359 done = true; | 405 done = true; |
360 for (auto block : all_blocks_) { | 406 for (auto block : all_blocks_) { |
361 if (!block->deferred()) { | 407 if (!block->deferred()) { |
362 bool deferred = block->PredecessorCount() > 0; | 408 bool deferred = block->PredecessorCount() > 0; |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
456 } | 502 } |
457 os << "\n"; | 503 os << "\n"; |
458 } | 504 } |
459 } | 505 } |
460 return os; | 506 return os; |
461 } | 507 } |
462 | 508 |
463 } // namespace compiler | 509 } // namespace compiler |
464 } // namespace internal | 510 } // namespace internal |
465 } // namespace v8 | 511 } // namespace v8 |
OLD | NEW |