OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_inliner.h" | 5 #include "vm/flow_graph_inliner.h" |
6 | 6 |
7 #include "vm/block_scheduler.h" | 7 #include "vm/block_scheduler.h" |
8 #include "vm/compiler.h" | 8 #include "vm/compiler.h" |
9 #include "vm/flags.h" | 9 #include "vm/flags.h" |
10 #include "vm/flow_graph.h" | 10 #include "vm/flow_graph.h" |
(...skipping 1313 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1324 // variant and the shared join for all later variants. | 1324 // variant and the shared join for all later variants. |
1325 if (inlined_entries_[i]->IsGraphEntry()) { | 1325 if (inlined_entries_[i]->IsGraphEntry()) { |
1326 // Convert the old target entry to a new join entry. | 1326 // Convert the old target entry to a new join entry. |
1327 TargetEntryInstr* old_target = | 1327 TargetEntryInstr* old_target = |
1328 inlined_entries_[i]->AsGraphEntry()->normal_entry(); | 1328 inlined_entries_[i]->AsGraphEntry()->normal_entry(); |
1329 // Unuse all inputs in the the old graph entry since it is not part of | 1329 // Unuse all inputs in the the old graph entry since it is not part of |
1330 // the graph anymore. A new target be created instead. | 1330 // the graph anymore. A new target be created instead. |
1331 inlined_entries_[i]->AsGraphEntry()->UnuseAllInputs(); | 1331 inlined_entries_[i]->AsGraphEntry()->UnuseAllInputs(); |
1332 | 1332 |
1333 JoinEntryInstr* new_join = | 1333 JoinEntryInstr* new_join = |
1334 BranchSimplifier::ToJoinEntry(isolate(), old_target); | 1334 BranchSimplifier::ToJoinEntry(zone(), old_target); |
1335 old_target->ReplaceAsPredecessorWith(new_join); | 1335 old_target->ReplaceAsPredecessorWith(new_join); |
1336 for (intptr_t j = 0; j < old_target->dominated_blocks().length(); ++j) { | 1336 for (intptr_t j = 0; j < old_target->dominated_blocks().length(); ++j) { |
1337 BlockEntryInstr* block = old_target->dominated_blocks()[j]; | 1337 BlockEntryInstr* block = old_target->dominated_blocks()[j]; |
1338 new_join->AddDominatedBlock(block); | 1338 new_join->AddDominatedBlock(block); |
1339 } | 1339 } |
1340 // Create a new target with the join as unconditional successor. | 1340 // Create a new target with the join as unconditional successor. |
1341 TargetEntryInstr* new_target = | 1341 TargetEntryInstr* new_target = |
1342 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), | 1342 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
1343 old_target->try_index()); | 1343 old_target->try_index()); |
1344 new_target->InheritDeoptTarget(isolate(), new_join); | 1344 new_target->InheritDeoptTarget(zone(), new_join); |
1345 GotoInstr* new_goto = new(Z) GotoInstr(new_join); | 1345 GotoInstr* new_goto = new(Z) GotoInstr(new_join); |
1346 new_goto->InheritDeoptTarget(isolate(), new_join); | 1346 new_goto->InheritDeoptTarget(zone(), new_join); |
1347 new_target->LinkTo(new_goto); | 1347 new_target->LinkTo(new_goto); |
1348 new_target->set_last_instruction(new_goto); | 1348 new_target->set_last_instruction(new_goto); |
1349 new_join->predecessors_.Add(new_target); | 1349 new_join->predecessors_.Add(new_target); |
1350 | 1350 |
1351 // Record the new target for the first variant. | 1351 // Record the new target for the first variant. |
1352 inlined_entries_[i] = new_target; | 1352 inlined_entries_[i] = new_target; |
1353 } | 1353 } |
1354 ASSERT(inlined_entries_[i]->IsTargetEntry()); | 1354 ASSERT(inlined_entries_[i]->IsTargetEntry()); |
1355 // Record the shared join for this variant. | 1355 // Record the shared join for this variant. |
1356 BlockEntryInstr* join = | 1356 BlockEntryInstr* join = |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1400 call_data.exit_collector->PrepareGraphs(callee_graph); | 1400 call_data.exit_collector->PrepareGraphs(callee_graph); |
1401 inlined_entries_.Add(callee_graph->graph_entry()); | 1401 inlined_entries_.Add(callee_graph->graph_entry()); |
1402 exit_collector_->Union(call_data.exit_collector); | 1402 exit_collector_->Union(call_data.exit_collector); |
1403 | 1403 |
1404 // Replace parameter stubs and constants. Replace the receiver argument | 1404 // Replace parameter stubs and constants. Replace the receiver argument |
1405 // with a redefinition to prevent code from the inlined body from being | 1405 // with a redefinition to prevent code from the inlined body from being |
1406 // hoisted above the inlined entry. | 1406 // hoisted above the inlined entry. |
1407 ASSERT(arguments.length() > 0); | 1407 ASSERT(arguments.length() > 0); |
1408 Value* actual = arguments[0]; | 1408 Value* actual = arguments[0]; |
1409 RedefinitionInstr* redefinition = new(Z) | 1409 RedefinitionInstr* redefinition = new(Z) |
1410 RedefinitionInstr(actual->Copy(isolate())); | 1410 RedefinitionInstr(actual->Copy(Z)); |
1411 redefinition->set_ssa_temp_index( | 1411 redefinition->set_ssa_temp_index( |
1412 owner_->caller_graph()->alloc_ssa_temp_index()); | 1412 owner_->caller_graph()->alloc_ssa_temp_index()); |
1413 redefinition->UpdateType(CompileType::FromCid(receiver_cid)); | 1413 redefinition->UpdateType(CompileType::FromCid(receiver_cid)); |
1414 redefinition->InsertAfter(callee_graph->graph_entry()->normal_entry()); | 1414 redefinition->InsertAfter(callee_graph->graph_entry()->normal_entry()); |
1415 Definition* stub = (*call_data.parameter_stubs)[0]; | 1415 Definition* stub = (*call_data.parameter_stubs)[0]; |
1416 stub->ReplaceUsesWith(redefinition); | 1416 stub->ReplaceUsesWith(redefinition); |
1417 | 1417 |
1418 for (intptr_t i = 1; i < arguments.length(); ++i) { | 1418 for (intptr_t i = 1; i < arguments.length(); ++i) { |
1419 actual = arguments[i]; | 1419 actual = arguments[i]; |
1420 if (actual != NULL) { | 1420 if (actual != NULL) { |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1515 // in frequency order. If all variants are inlined, the entry to the last | 1515 // in frequency order. If all variants are inlined, the entry to the last |
1516 // inlined body is guarded by a CheckClassId instruction which can deopt. | 1516 // inlined body is guarded by a CheckClassId instruction which can deopt. |
1517 // If not all variants are inlined, we add a PolymorphicInstanceCall | 1517 // If not all variants are inlined, we add a PolymorphicInstanceCall |
1518 // instruction to handle the non-inlined variants. | 1518 // instruction to handle the non-inlined variants. |
1519 TargetEntryInstr* PolymorphicInliner::BuildDecisionGraph() { | 1519 TargetEntryInstr* PolymorphicInliner::BuildDecisionGraph() { |
1520 // Start with a fresh target entry. | 1520 // Start with a fresh target entry. |
1521 TargetEntryInstr* entry = | 1521 TargetEntryInstr* entry = |
1522 new(Z) TargetEntryInstr( | 1522 new(Z) TargetEntryInstr( |
1523 owner_->caller_graph()->allocate_block_id(), | 1523 owner_->caller_graph()->allocate_block_id(), |
1524 call_->GetBlock()->try_index()); | 1524 call_->GetBlock()->try_index()); |
1525 entry->InheritDeoptTarget(isolate(), call_); | 1525 entry->InheritDeoptTarget(zone(), call_); |
1526 | 1526 |
1527 // This function uses a cursor (a pointer to the 'current' instruction) to | 1527 // This function uses a cursor (a pointer to the 'current' instruction) to |
1528 // build the graph. The next instruction will be inserted after the | 1528 // build the graph. The next instruction will be inserted after the |
1529 // cursor. | 1529 // cursor. |
1530 TargetEntryInstr* current_block = entry; | 1530 TargetEntryInstr* current_block = entry; |
1531 Instruction* cursor = entry; | 1531 Instruction* cursor = entry; |
1532 | 1532 |
1533 Definition* receiver = call_->ArgumentAt(0); | 1533 Definition* receiver = call_->ArgumentAt(0); |
1534 // There are at least two variants including non-inlined ones, so we have | 1534 // There are at least two variants including non-inlined ones, so we have |
1535 // at least one branch on the class id. | 1535 // at least one branch on the class id. |
1536 LoadClassIdInstr* load_cid = | 1536 LoadClassIdInstr* load_cid = |
1537 new(Z) LoadClassIdInstr(new(Z) Value(receiver)); | 1537 new(Z) LoadClassIdInstr(new(Z) Value(receiver)); |
1538 load_cid->set_ssa_temp_index(owner_->caller_graph()->alloc_ssa_temp_index()); | 1538 load_cid->set_ssa_temp_index(owner_->caller_graph()->alloc_ssa_temp_index()); |
1539 cursor = AppendInstruction(cursor, load_cid); | 1539 cursor = AppendInstruction(cursor, load_cid); |
1540 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { | 1540 for (intptr_t i = 0; i < inlined_variants_.length(); ++i) { |
1541 // 1. Guard the body with a class id check. | 1541 // 1. Guard the body with a class id check. |
1542 if ((i == (inlined_variants_.length() - 1)) && | 1542 if ((i == (inlined_variants_.length() - 1)) && |
1543 non_inlined_variants_.is_empty()) { | 1543 non_inlined_variants_.is_empty()) { |
1544 // If it is the last variant use a check class id instruction which can | 1544 // If it is the last variant use a check class id instruction which can |
1545 // deoptimize, followed unconditionally by the body. | 1545 // deoptimize, followed unconditionally by the body. |
1546 RedefinitionInstr* cid_redefinition = | 1546 RedefinitionInstr* cid_redefinition = |
1547 new RedefinitionInstr(new(Z) Value(load_cid)); | 1547 new RedefinitionInstr(new(Z) Value(load_cid)); |
1548 cid_redefinition->set_ssa_temp_index( | 1548 cid_redefinition->set_ssa_temp_index( |
1549 owner_->caller_graph()->alloc_ssa_temp_index()); | 1549 owner_->caller_graph()->alloc_ssa_temp_index()); |
1550 cursor = AppendInstruction(cursor, cid_redefinition); | 1550 cursor = AppendInstruction(cursor, cid_redefinition); |
1551 CheckClassIdInstr* check_class_id = new(Z) CheckClassIdInstr( | 1551 CheckClassIdInstr* check_class_id = new(Z) CheckClassIdInstr( |
1552 new(Z) Value(cid_redefinition), | 1552 new(Z) Value(cid_redefinition), |
1553 inlined_variants_[i].cid, | 1553 inlined_variants_[i].cid, |
1554 call_->deopt_id()); | 1554 call_->deopt_id()); |
1555 check_class_id->InheritDeoptTarget(isolate(), call_); | 1555 check_class_id->InheritDeoptTarget(zone(), call_); |
1556 cursor = AppendInstruction(cursor, check_class_id); | 1556 cursor = AppendInstruction(cursor, check_class_id); |
1557 | 1557 |
1558 // The next instruction is the first instruction of the inlined body. | 1558 // The next instruction is the first instruction of the inlined body. |
1559 // Handle the two possible cases (unshared and shared subsequent | 1559 // Handle the two possible cases (unshared and shared subsequent |
1560 // predecessors) separately. | 1560 // predecessors) separately. |
1561 BlockEntryInstr* callee_entry = inlined_entries_[i]; | 1561 BlockEntryInstr* callee_entry = inlined_entries_[i]; |
1562 if (callee_entry->IsGraphEntry()) { | 1562 if (callee_entry->IsGraphEntry()) { |
1563 // Unshared. Graft the normal entry on after the check class | 1563 // Unshared. Graft the normal entry on after the check class |
1564 // instruction. | 1564 // instruction. |
1565 TargetEntryInstr* target = | 1565 TargetEntryInstr* target = |
(...skipping 12 matching lines...) Expand all Loading... |
1578 BlockEntryInstr* block = target->dominated_blocks()[j]; | 1578 BlockEntryInstr* block = target->dominated_blocks()[j]; |
1579 current_block->AddDominatedBlock(block); | 1579 current_block->AddDominatedBlock(block); |
1580 } | 1580 } |
1581 } else if (callee_entry->IsJoinEntry()) { | 1581 } else if (callee_entry->IsJoinEntry()) { |
1582 // Shared inlined body and this is a subsequent entry. We have | 1582 // Shared inlined body and this is a subsequent entry. We have |
1583 // already constructed a join and set its dominator. Add a jump to | 1583 // already constructed a join and set its dominator. Add a jump to |
1584 // the join. | 1584 // the join. |
1585 JoinEntryInstr* join = callee_entry->AsJoinEntry(); | 1585 JoinEntryInstr* join = callee_entry->AsJoinEntry(); |
1586 ASSERT(join->dominator() != NULL); | 1586 ASSERT(join->dominator() != NULL); |
1587 GotoInstr* goto_join = new GotoInstr(join); | 1587 GotoInstr* goto_join = new GotoInstr(join); |
1588 goto_join->InheritDeoptTarget(isolate(), join); | 1588 goto_join->InheritDeoptTarget(zone(), join); |
1589 cursor->LinkTo(goto_join); | 1589 cursor->LinkTo(goto_join); |
1590 current_block->set_last_instruction(goto_join); | 1590 current_block->set_last_instruction(goto_join); |
1591 } else { | 1591 } else { |
1592 // There is no possibility of a TargetEntry (the first entry to a | 1592 // There is no possibility of a TargetEntry (the first entry to a |
1593 // shared inlined body) because this is the last inlined entry. | 1593 // shared inlined body) because this is the last inlined entry. |
1594 UNREACHABLE(); | 1594 UNREACHABLE(); |
1595 } | 1595 } |
1596 cursor = NULL; | 1596 cursor = NULL; |
1597 } else { | 1597 } else { |
1598 // For all variants except the last, use a branch on the loaded class | 1598 // For all variants except the last, use a branch on the loaded class |
1599 // id. | 1599 // id. |
1600 const Smi& cid = Smi::ZoneHandle(Smi::New(inlined_variants_[i].cid)); | 1600 const Smi& cid = Smi::ZoneHandle(Smi::New(inlined_variants_[i].cid)); |
1601 ConstantInstr* cid_constant = new ConstantInstr(cid); | 1601 ConstantInstr* cid_constant = new ConstantInstr(cid); |
1602 cid_constant->set_ssa_temp_index( | 1602 cid_constant->set_ssa_temp_index( |
1603 owner_->caller_graph()->alloc_ssa_temp_index()); | 1603 owner_->caller_graph()->alloc_ssa_temp_index()); |
1604 StrictCompareInstr* compare = | 1604 StrictCompareInstr* compare = |
1605 new StrictCompareInstr(call_->instance_call()->token_pos(), | 1605 new StrictCompareInstr(call_->instance_call()->token_pos(), |
1606 Token::kEQ_STRICT, | 1606 Token::kEQ_STRICT, |
1607 new Value(load_cid), | 1607 new Value(load_cid), |
1608 new Value(cid_constant), | 1608 new Value(cid_constant), |
1609 false); // No number check. | 1609 false); // No number check. |
1610 BranchInstr* branch = new BranchInstr(compare); | 1610 BranchInstr* branch = new BranchInstr(compare); |
1611 branch->InheritDeoptTarget(isolate(), call_); | 1611 branch->InheritDeoptTarget(zone(), call_); |
1612 AppendInstruction(AppendInstruction(cursor, cid_constant), branch); | 1612 AppendInstruction(AppendInstruction(cursor, cid_constant), branch); |
1613 current_block->set_last_instruction(branch); | 1613 current_block->set_last_instruction(branch); |
1614 cursor = NULL; | 1614 cursor = NULL; |
1615 | 1615 |
1616 // 2. Handle a match by linking to the inlined body. There are three | 1616 // 2. Handle a match by linking to the inlined body. There are three |
1617 // cases (unshared, shared first predecessor, and shared subsequent | 1617 // cases (unshared, shared first predecessor, and shared subsequent |
1618 // predecessors). | 1618 // predecessors). |
1619 BlockEntryInstr* callee_entry = inlined_entries_[i]; | 1619 BlockEntryInstr* callee_entry = inlined_entries_[i]; |
1620 TargetEntryInstr* true_target = NULL; | 1620 TargetEntryInstr* true_target = NULL; |
1621 if (callee_entry->IsGraphEntry()) { | 1621 if (callee_entry->IsGraphEntry()) { |
(...skipping 11 matching lines...) Expand all Loading... |
1633 } else { | 1633 } else { |
1634 // Shared inlined body and this is a subsequent entry. We have | 1634 // Shared inlined body and this is a subsequent entry. We have |
1635 // already constructed a join. We need a fresh target that jumps to | 1635 // already constructed a join. We need a fresh target that jumps to |
1636 // the join. | 1636 // the join. |
1637 JoinEntryInstr* join = callee_entry->AsJoinEntry(); | 1637 JoinEntryInstr* join = callee_entry->AsJoinEntry(); |
1638 ASSERT(join != NULL); | 1638 ASSERT(join != NULL); |
1639 ASSERT(join->dominator() != NULL); | 1639 ASSERT(join->dominator() != NULL); |
1640 true_target = | 1640 true_target = |
1641 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), | 1641 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
1642 call_->GetBlock()->try_index()); | 1642 call_->GetBlock()->try_index()); |
1643 true_target->InheritDeoptTarget(isolate(), join); | 1643 true_target->InheritDeoptTarget(zone(), join); |
1644 GotoInstr* goto_join = new GotoInstr(join); | 1644 GotoInstr* goto_join = new GotoInstr(join); |
1645 goto_join->InheritDeoptTarget(isolate(), join); | 1645 goto_join->InheritDeoptTarget(zone(), join); |
1646 true_target->LinkTo(goto_join); | 1646 true_target->LinkTo(goto_join); |
1647 true_target->set_last_instruction(goto_join); | 1647 true_target->set_last_instruction(goto_join); |
1648 } | 1648 } |
1649 *branch->true_successor_address() = true_target; | 1649 *branch->true_successor_address() = true_target; |
1650 current_block->AddDominatedBlock(true_target); | 1650 current_block->AddDominatedBlock(true_target); |
1651 | 1651 |
1652 // 3. Prepare to handle a match failure on the next iteration or the | 1652 // 3. Prepare to handle a match failure on the next iteration or the |
1653 // fall-through code below for non-inlined variants. | 1653 // fall-through code below for non-inlined variants. |
1654 TargetEntryInstr* false_target = | 1654 TargetEntryInstr* false_target = |
1655 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), | 1655 new TargetEntryInstr(owner_->caller_graph()->allocate_block_id(), |
1656 call_->GetBlock()->try_index()); | 1656 call_->GetBlock()->try_index()); |
1657 false_target->InheritDeoptTarget(isolate(), call_); | 1657 false_target->InheritDeoptTarget(zone(), call_); |
1658 *branch->false_successor_address() = false_target; | 1658 *branch->false_successor_address() = false_target; |
1659 current_block->AddDominatedBlock(false_target); | 1659 current_block->AddDominatedBlock(false_target); |
1660 cursor = current_block = false_target; | 1660 cursor = current_block = false_target; |
1661 } | 1661 } |
1662 } | 1662 } |
1663 | 1663 |
1664 // Handle any non-inlined variants. | 1664 // Handle any non-inlined variants. |
1665 if (!non_inlined_variants_.is_empty()) { | 1665 if (!non_inlined_variants_.is_empty()) { |
1666 // Move push arguments of the call. | 1666 // Move push arguments of the call. |
1667 for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) { | 1667 for (intptr_t i = 0; i < call_->ArgumentCount(); ++i) { |
(...skipping 14 matching lines...) Expand all Loading... |
1682 new_checks.AddReceiverCheck(non_inlined_variants_[i].cid, | 1682 new_checks.AddReceiverCheck(non_inlined_variants_[i].cid, |
1683 *non_inlined_variants_[i].target, | 1683 *non_inlined_variants_[i].target, |
1684 non_inlined_variants_[i].count); | 1684 non_inlined_variants_[i].count); |
1685 } | 1685 } |
1686 PolymorphicInstanceCallInstr* fallback_call = | 1686 PolymorphicInstanceCallInstr* fallback_call = |
1687 new PolymorphicInstanceCallInstr(call_->instance_call(), | 1687 new PolymorphicInstanceCallInstr(call_->instance_call(), |
1688 new_checks, | 1688 new_checks, |
1689 true); // With checks. | 1689 true); // With checks. |
1690 fallback_call->set_ssa_temp_index( | 1690 fallback_call->set_ssa_temp_index( |
1691 owner_->caller_graph()->alloc_ssa_temp_index()); | 1691 owner_->caller_graph()->alloc_ssa_temp_index()); |
1692 fallback_call->InheritDeoptTarget(isolate(), call_); | 1692 fallback_call->InheritDeoptTarget(zone(), call_); |
1693 ReturnInstr* fallback_return = | 1693 ReturnInstr* fallback_return = |
1694 new ReturnInstr(call_->instance_call()->token_pos(), | 1694 new ReturnInstr(call_->instance_call()->token_pos(), |
1695 new Value(fallback_call)); | 1695 new Value(fallback_call)); |
1696 fallback_return->InheritDeoptTargetAfter( | 1696 fallback_return->InheritDeoptTargetAfter( |
1697 owner_->caller_graph(), | 1697 owner_->caller_graph(), |
1698 call_, | 1698 call_, |
1699 fallback_call); | 1699 fallback_call); |
1700 AppendInstruction(AppendInstruction(cursor, fallback_call), | 1700 AppendInstruction(AppendInstruction(cursor, fallback_call), |
1701 fallback_return); | 1701 fallback_return); |
1702 exit_collector_->AddExit(fallback_return); | 1702 exit_collector_->AddExit(fallback_return); |
(...skipping 173 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1876 intptr_t FlowGraphInliner::NextInlineId(const Function& function, | 1876 intptr_t FlowGraphInliner::NextInlineId(const Function& function, |
1877 intptr_t parent_id) { | 1877 intptr_t parent_id) { |
1878 const intptr_t id = inline_id_to_function_->length(); | 1878 const intptr_t id = inline_id_to_function_->length(); |
1879 inline_id_to_function_->Add(&function); | 1879 inline_id_to_function_->Add(&function); |
1880 caller_inline_id_->Add(parent_id); | 1880 caller_inline_id_->Add(parent_id); |
1881 return id; | 1881 return id; |
1882 } | 1882 } |
1883 | 1883 |
1884 | 1884 |
1885 } // namespace dart | 1885 } // namespace dart |
OLD | NEW |