OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1534 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1545 if (block->HasParentLoopHeader()) { | 1545 if (block->HasParentLoopHeader()) { |
1546 int header_id = block->parent_loop_header()->block_id(); | 1546 int header_id = block->parent_loop_header()->block_id(); |
1547 loop_side_effects_[header_id].Add(block->IsLoopHeader() | 1547 loop_side_effects_[header_id].Add(block->IsLoopHeader() |
1548 ? loop_side_effects_[id] | 1548 ? loop_side_effects_[id] |
1549 : side_effects); | 1549 : side_effects); |
1550 } | 1550 } |
1551 } | 1551 } |
1552 } | 1552 } |
1553 | 1553 |
1554 | 1554 |
| 1555 SmartArrayPointer<char> GetGVNFlagsString(GVNFlagSet flags) { |
| 1556 #if DEBUG |
| 1557 char buffer[kLastFlag * 128]; |
| 1558 const char* separator = ""; |
| 1559 const char* comma = ", "; |
| 1560 buffer[0] = 0; |
| 1561 uint32_t set_depends_on = 0; |
| 1562 uint32_t set_changes = 0; |
| 1563 for (int bit = 0; bit < kLastFlag; ++bit) { |
| 1564 if ((flags.ToIntegral() & (1 << bit)) != 0) { |
| 1565 if (bit % 2 == 0) { |
| 1566 set_changes++; |
| 1567 } else { |
| 1568 set_depends_on++; |
| 1569 } |
| 1570 } |
| 1571 } |
| 1572 bool positive_changes = set_changes < (kLastFlag / 2); |
| 1573 bool positive_depends_on = set_depends_on < (kLastFlag / 2); |
| 1574 if (set_changes > 0) { |
| 1575 if (positive_changes) { |
| 1576 strcat(buffer, "changes ["); |
| 1577 } else { |
| 1578 strcat(buffer, "changes all except ["); |
| 1579 } |
| 1580 for (int bit = 0; bit < kLastFlag; ++bit) { |
| 1581 if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_changes) { |
| 1582 switch (static_cast<GVNFlag>(bit)) { |
| 1583 #define DECLARE_FLAG(type) \ |
| 1584 case kChanges##type: \ |
| 1585 strcat(buffer, separator); \ |
| 1586 strcat(buffer, #type); \ |
| 1587 separator = comma; \ |
| 1588 break; |
| 1589 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) |
| 1590 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) |
| 1591 #undef DECLARE_FLAG |
| 1592 default: |
| 1593 break; |
| 1594 } |
| 1595 } |
| 1596 } |
| 1597 strcat(buffer, "]"); |
| 1598 } |
| 1599 if (set_depends_on > 0) { |
| 1600 separator = ""; |
| 1601 if (set_changes > 0) { |
| 1602 strcat(buffer, ", "); |
| 1603 } |
| 1604 if (positive_depends_on) { |
| 1605 strcat(buffer, "depends on ["); |
| 1606 } else { |
| 1607 strcat(buffer, "depends on all except ["); |
| 1608 } |
| 1609 for (int bit = 0; bit < kLastFlag; ++bit) { |
| 1610 if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_depends_on) { |
| 1611 switch (static_cast<GVNFlag>(bit)) { |
| 1612 #define DECLARE_FLAG(type) \ |
| 1613 case kDependsOn##type: \ |
| 1614 strcat(buffer, separator); \ |
| 1615 strcat(buffer, #type); \ |
| 1616 separator = comma; \ |
| 1617 break; |
| 1618 GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) |
| 1619 GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) |
| 1620 #undef DECLARE_FLAG |
| 1621 default: |
| 1622 break; |
| 1623 } |
| 1624 } |
| 1625 } |
| 1626 strcat(buffer, "]"); |
| 1627 } |
| 1628 #else |
| 1629 char buffer[128]; |
| 1630 snprintf(buffer, 128, "0x%08X", flags.ToIntegral()); |
| 1631 #endif |
| 1632 char* result = new char[strlen(buffer) + 1]; |
| 1633 strcpy(result, buffer); |
| 1634 return SmartArrayPointer<char>(result); |
| 1635 } |
| 1636 |
| 1637 |
1555 void HGlobalValueNumberer::LoopInvariantCodeMotion() { | 1638 void HGlobalValueNumberer::LoopInvariantCodeMotion() { |
1556 for (int i = graph_->blocks()->length() - 1; i >= 0; --i) { | 1639 for (int i = graph_->blocks()->length() - 1; i >= 0; --i) { |
1557 HBasicBlock* block = graph_->blocks()->at(i); | 1640 HBasicBlock* block = graph_->blocks()->at(i); |
1558 if (block->IsLoopHeader()) { | 1641 if (block->IsLoopHeader()) { |
1559 GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; | 1642 GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; |
1560 TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n", | 1643 TraceGVN("Try loop invariant motion for block B%d %s\n", |
1561 block->block_id(), | 1644 block->block_id(), |
1562 side_effects.ToIntegral()); | 1645 *GetGVNFlagsString(side_effects)); |
1563 | 1646 |
1564 GVNFlagSet accumulated_first_time_depends; | 1647 GVNFlagSet accumulated_first_time_depends; |
1565 GVNFlagSet accumulated_first_time_changes; | 1648 GVNFlagSet accumulated_first_time_changes; |
1566 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); | 1649 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); |
1567 for (int j = block->block_id(); j <= last->block_id(); ++j) { | 1650 for (int j = block->block_id(); j <= last->block_id(); ++j) { |
1568 ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects, | 1651 ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects, |
1569 &accumulated_first_time_depends, | 1652 &accumulated_first_time_depends, |
1570 &accumulated_first_time_changes); | 1653 &accumulated_first_time_changes); |
1571 } | 1654 } |
1572 } | 1655 } |
1573 } | 1656 } |
1574 } | 1657 } |
1575 | 1658 |
1576 | 1659 |
1577 void HGlobalValueNumberer::ProcessLoopBlock( | 1660 void HGlobalValueNumberer::ProcessLoopBlock( |
1578 HBasicBlock* block, | 1661 HBasicBlock* block, |
1579 HBasicBlock* loop_header, | 1662 HBasicBlock* loop_header, |
1580 GVNFlagSet loop_kills, | 1663 GVNFlagSet loop_kills, |
1581 GVNFlagSet* first_time_depends, | 1664 GVNFlagSet* first_time_depends, |
1582 GVNFlagSet* first_time_changes) { | 1665 GVNFlagSet* first_time_changes) { |
1583 HBasicBlock* pre_header = loop_header->predecessors()->at(0); | 1666 HBasicBlock* pre_header = loop_header->predecessors()->at(0); |
1584 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); | 1667 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); |
1585 TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n", | 1668 TraceGVN("Loop invariant motion for B%d %s\n", |
1586 block->block_id(), | 1669 block->block_id(), |
1587 depends_flags.ToIntegral()); | 1670 *GetGVNFlagsString(depends_flags)); |
1588 HInstruction* instr = block->first(); | 1671 HInstruction* instr = block->first(); |
1589 while (instr != NULL) { | 1672 while (instr != NULL) { |
1590 HInstruction* next = instr->next(); | 1673 HInstruction* next = instr->next(); |
1591 bool hoisted = false; | 1674 bool hoisted = false; |
1592 if (instr->CheckFlag(HValue::kUseGVN)) { | 1675 if (instr->CheckFlag(HValue::kUseGVN)) { |
1593 TraceGVN("Checking instruction %d (%s) instruction GVN flags 0x%X, " | 1676 TraceGVN("Checking instruction %d (%s) %s. Loop %s\n", |
1594 "loop kills 0x%X\n", | |
1595 instr->id(), | 1677 instr->id(), |
1596 instr->Mnemonic(), | 1678 instr->Mnemonic(), |
1597 instr->gvn_flags().ToIntegral(), | 1679 *GetGVNFlagsString(instr->gvn_flags()), |
1598 depends_flags.ToIntegral()); | 1680 *GetGVNFlagsString(loop_kills)); |
1599 bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); | 1681 bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); |
1600 if (instr->IsTransitionElementsKind()) { | 1682 if (instr->IsTransitionElementsKind()) { |
1601 // It's possible to hoist transitions out of a loop as long as the | 1683 // It's possible to hoist transitions out of a loop as long as the |
1602 // hoisting wouldn't move the transition past a DependsOn of one of it's | 1684 // hoisting wouldn't move the transition past a DependsOn of one of it's |
1603 // changes or any instructions that might change an objects map or | 1685 // changes or any instructions that might change an objects map or |
1604 // elements contents. | 1686 // elements contents. |
1605 GVNFlagSet changes = instr->ChangesFlags(); | 1687 GVNFlagSet changes = instr->ChangesFlags(); |
1606 GVNFlagSet hoist_depends_blockers = | 1688 GVNFlagSet hoist_depends_blockers = |
1607 HValue::ConvertChangesToDependsFlags(changes); | 1689 HValue::ConvertChangesToDependsFlags(changes); |
1608 // In addition to not hoisting transitions above other instructions that | 1690 // In addition to not hoisting transitions above other instructions that |
1609 // change dependencies that the transition changes, it must not be | 1691 // change dependencies that the transition changes, it must not be |
1610 // hoisted above map changes and stores to an elements backing store | 1692 // hoisted above map changes and stores to an elements backing store |
1611 // that the transition might change. | 1693 // that the transition might change. |
1612 GVNFlagSet hoist_change_blockers = changes; | 1694 GVNFlagSet hoist_change_blockers = changes; |
1613 hoist_change_blockers.Add(kChangesMaps); | 1695 hoist_change_blockers.Add(kChangesMaps); |
1614 HTransitionElementsKind* trans = HTransitionElementsKind::cast(instr); | 1696 HTransitionElementsKind* trans = HTransitionElementsKind::cast(instr); |
1615 if (trans->original_map()->has_fast_double_elements()) { | 1697 if (trans->original_map()->has_fast_double_elements()) { |
1616 hoist_change_blockers.Add(kChangesDoubleArrayElements); | 1698 hoist_change_blockers.Add(kChangesDoubleArrayElements); |
1617 } | 1699 } |
1618 if (trans->transitioned_map()->has_fast_double_elements()) { | 1700 if (trans->transitioned_map()->has_fast_double_elements()) { |
1619 hoist_change_blockers.Add(kChangesArrayElements); | 1701 hoist_change_blockers.Add(kChangesArrayElements); |
1620 } | 1702 } |
1621 TraceGVN("Checking dependencies on HTransitionElementsKind %d (%s) " | 1703 TraceGVN("Checking dependencies on HTransitionElementsKind %d (%s) " |
1622 "hoist depends blockers 0x%X, hoist change blockers 0x%X, " | 1704 "hoist blockers: %s %s; " |
1623 "accumulated depends 0x%X, accumulated changes 0x%X\n", | 1705 "first-time accumulated: %s %s\n", |
1624 instr->id(), | 1706 instr->id(), |
1625 instr->Mnemonic(), | 1707 instr->Mnemonic(), |
1626 hoist_depends_blockers.ToIntegral(), | 1708 *GetGVNFlagsString(hoist_depends_blockers), |
1627 hoist_change_blockers.ToIntegral(), | 1709 *GetGVNFlagsString(hoist_change_blockers), |
1628 first_time_depends->ToIntegral(), | 1710 *GetGVNFlagsString(*first_time_depends), |
1629 first_time_changes->ToIntegral()); | 1711 *GetGVNFlagsString(*first_time_changes)); |
1630 // It's possible to hoist transition from the current loop loop only if | 1712 // It's possible to hoist transition from the current loop loop only if |
1631 // they dominate all of the successor blocks in the same loop and there | 1713 // they dominate all of the successor blocks in the same loop and there |
1632 // are not any instructions that have Changes/DependsOn that intervene | 1714 // are not any instructions that have Changes/DependsOn that intervene |
1633 // between it and the beginning of the loop header. | 1715 // between it and the beginning of the loop header. |
1634 bool in_nested_loop = block != loop_header && | 1716 bool in_nested_loop = block != loop_header && |
1635 ((block->parent_loop_header() != loop_header) || | 1717 ((block->parent_loop_header() != loop_header) || |
1636 block->IsLoopHeader()); | 1718 block->IsLoopHeader()); |
1637 can_hoist = !in_nested_loop && | 1719 can_hoist = !in_nested_loop && |
1638 block->IsLoopSuccessorDominator() && | 1720 block->IsLoopSuccessorDominator() && |
1639 !first_time_depends->ContainsAnyOf(hoist_depends_blockers) && | 1721 !first_time_depends->ContainsAnyOf(hoist_depends_blockers) && |
(...skipping 14 matching lines...) Expand all Loading... |
1654 instr->Unlink(); | 1736 instr->Unlink(); |
1655 instr->InsertBefore(pre_header->end()); | 1737 instr->InsertBefore(pre_header->end()); |
1656 if (instr->HasSideEffects()) removed_side_effects_ = true; | 1738 if (instr->HasSideEffects()) removed_side_effects_ = true; |
1657 hoisted = true; | 1739 hoisted = true; |
1658 } | 1740 } |
1659 } | 1741 } |
1660 } | 1742 } |
1661 if (!hoisted) { | 1743 if (!hoisted) { |
1662 // If an instruction is not hoisted, we have to account for its side | 1744 // If an instruction is not hoisted, we have to account for its side |
1663 // effects when hoisting later HTransitionElementsKind instructions. | 1745 // effects when hoisting later HTransitionElementsKind instructions. |
| 1746 GVNFlagSet previous_depends = *first_time_depends; |
| 1747 GVNFlagSet previous_changes = *first_time_changes; |
1664 first_time_depends->Add(instr->DependsOnFlags()); | 1748 first_time_depends->Add(instr->DependsOnFlags()); |
1665 first_time_changes->Add(instr->ChangesFlags()); | 1749 first_time_changes->Add(instr->ChangesFlags()); |
| 1750 if (!(previous_depends == *first_time_depends)) { |
| 1751 TraceGVN("Updated first-time accumulated %s\n", |
| 1752 *GetGVNFlagsString(*first_time_depends)); |
| 1753 } |
| 1754 if (!(previous_changes == *first_time_changes)) { |
| 1755 TraceGVN("Updated first-time accumulated %s\n", |
| 1756 *GetGVNFlagsString(*first_time_changes)); |
| 1757 } |
1666 } | 1758 } |
1667 instr = next; | 1759 instr = next; |
1668 } | 1760 } |
1669 } | 1761 } |
1670 | 1762 |
1671 | 1763 |
1672 bool HGlobalValueNumberer::AllowCodeMotion() { | 1764 bool HGlobalValueNumberer::AllowCodeMotion() { |
1673 return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount; | 1765 return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount; |
1674 } | 1766 } |
1675 | 1767 |
(...skipping 6690 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
8366 } | 8458 } |
8367 } | 8459 } |
8368 | 8460 |
8369 #ifdef DEBUG | 8461 #ifdef DEBUG |
8370 if (graph_ != NULL) graph_->Verify(false); // No full verify. | 8462 if (graph_ != NULL) graph_->Verify(false); // No full verify. |
8371 if (allocator_ != NULL) allocator_->Verify(); | 8463 if (allocator_ != NULL) allocator_->Verify(); |
8372 #endif | 8464 #endif |
8373 } | 8465 } |
8374 | 8466 |
8375 } } // namespace v8::internal | 8467 } } // namespace v8::internal |
OLD | NEW |