1317 |
1317 |
1318 |
1318 |
1319 //------------------------------Estimate_Block_Frequency----------------------- |
1319 //------------------------------Estimate_Block_Frequency----------------------- |
1320 // Estimate block frequencies based on IfNode probabilities. |
1320 // Estimate block frequencies based on IfNode probabilities. |
1321 void PhaseCFG::Estimate_Block_Frequency() { |
1321 void PhaseCFG::Estimate_Block_Frequency() { |
1322 int cnts = C->method() ? C->method()->interpreter_invocation_count() : 1; |
1322 |
1323 // Most of our algorithms will die horribly if frequency can become |
1323 // Force conditional branches leading to uncommon traps to be unlikely, |
1324 // negative so make sure cnts is a sane value. |
1324 // not because we get to the uncommon_trap with less relative frequency, |
1325 if( cnts <= 0 ) cnts = 1; |
1325 // but because an uncommon_trap typically causes a deopt, so we only get |
1326 float f = (float)cnts/(float)FreqCountInvocations; |
1326 // there once. |
|
1327 if (C->do_freq_based_layout()) { |
|
1328 Block_List worklist; |
|
1329 Block* root_blk = _blocks[0]; |
|
1330 for (uint i = 1; i < root_blk->num_preds(); i++) { |
|
1331 Block *pb = _bbs[root_blk->pred(i)->_idx]; |
|
1332 if (pb->has_uncommon_code()) { |
|
1333 worklist.push(pb); |
|
1334 } |
|
1335 } |
|
1336 while (worklist.size() > 0) { |
|
1337 Block* uct = worklist.pop(); |
|
1338 if (uct == _broot) continue; |
|
1339 for (uint i = 1; i < uct->num_preds(); i++) { |
|
1340 Block *pb = _bbs[uct->pred(i)->_idx]; |
|
1341 if (pb->_num_succs == 1) { |
|
1342 worklist.push(pb); |
|
1343 } else if (pb->num_fall_throughs() == 2) { |
|
1344 pb->update_uncommon_branch(uct); |
|
1345 } |
|
1346 } |
|
1347 } |
|
1348 } |
1327 |
1349 |
1328 // Create the loop tree and calculate loop depth. |
1350 // Create the loop tree and calculate loop depth. |
1329 _root_loop = create_loop_tree(); |
1351 _root_loop = create_loop_tree(); |
1330 _root_loop->compute_loop_depth(0); |
1352 _root_loop->compute_loop_depth(0); |
1331 |
1353 |
1332 // Compute block frequency of each block, relative to a single loop entry. |
1354 // Compute block frequency of each block, relative to a single loop entry. |
1333 _root_loop->compute_freq(); |
1355 _root_loop->compute_freq(); |
1334 |
1356 |
1335 // Adjust all frequencies to be relative to a single method entry |
1357 // Adjust all frequencies to be relative to a single method entry |
1336 _root_loop->_freq = f * 1.0; |
1358 _root_loop->_freq = 1.0; |
1337 _root_loop->scale_freq(); |
1359 _root_loop->scale_freq(); |
1338 |
1360 |
1339 // force paths ending at uncommon traps to be infrequent |
1361 // force paths ending at uncommon traps to be infrequent |
1340 Block_List worklist; |
1362 if (!C->do_freq_based_layout()) { |
1341 Block* root_blk = _blocks[0]; |
1363 Block_List worklist; |
1342 for (uint i = 0; i < root_blk->num_preds(); i++) { |
1364 Block* root_blk = _blocks[0]; |
1343 Block *pb = _bbs[root_blk->pred(i)->_idx]; |
1365 for (uint i = 1; i < root_blk->num_preds(); i++) { |
1344 if (pb->has_uncommon_code()) { |
1366 Block *pb = _bbs[root_blk->pred(i)->_idx]; |
1345 worklist.push(pb); |
1367 if (pb->has_uncommon_code()) { |
1346 } |
|
1347 } |
|
1348 while (worklist.size() > 0) { |
|
1349 Block* uct = worklist.pop(); |
|
1350 uct->_freq = PROB_MIN; |
|
1351 for (uint i = 0; i < uct->num_preds(); i++) { |
|
1352 Block *pb = _bbs[uct->pred(i)->_idx]; |
|
1353 if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) { |
|
1354 worklist.push(pb); |
1368 worklist.push(pb); |
|
1369 } |
|
1370 } |
|
1371 while (worklist.size() > 0) { |
|
1372 Block* uct = worklist.pop(); |
|
1373 uct->_freq = PROB_MIN; |
|
1374 for (uint i = 1; i < uct->num_preds(); i++) { |
|
1375 Block *pb = _bbs[uct->pred(i)->_idx]; |
|
1376 if (pb->_num_succs == 1 && pb->_freq > PROB_MIN) { |
|
1377 worklist.push(pb); |
|
1378 } |
1355 } |
1379 } |
1356 } |
1380 } |
1357 } |
1381 } |
1358 |
1382 |
1359 #ifndef PRODUCT |
1383 #ifndef PRODUCT |
1554 update_succ_freq(eb, freq * prob); |
1578 update_succ_freq(eb, freq * prob); |
1555 } |
1579 } |
1556 } |
1580 } |
1557 } |
1581 } |
1558 |
1582 |
1559 #if 0 |
|
1560 // Raise frequency of the loop backedge block, in an effort |
|
1561 // to keep it empty. Skip the method level "loop". |
|
1562 if (_parent != NULL) { |
|
1563 CFGElement* s = _members.at(_members.length() - 1); |
|
1564 if (s->is_block()) { |
|
1565 Block* bk = s->as_Block(); |
|
1566 if (bk->_num_succs == 1 && bk->_succs[0] == hd) { |
|
1567 // almost any value >= 1.0f works |
|
1568 // FIXME: raw constant |
|
1569 bk->_freq = 1.05f; |
|
1570 } |
|
1571 } |
|
1572 } |
|
1573 #endif |
|
1574 |
|
1575 // For all loops other than the outer, "method" loop, |
1583 // For all loops other than the outer, "method" loop, |
1576 // sum and normalize the exit probability. The "method" loop |
1584 // sum and normalize the exit probability. The "method" loop |
1577 // should keep the initial exit probability of 1, so that |
1585 // should keep the initial exit probability of 1, so that |
1578 // inner blocks do not get erroneously scaled. |
1586 // inner blocks do not get erroneously scaled. |
1579 if (_depth != 0) { |
1587 if (_depth != 0) { |
1587 // probabilities estimate the possibility of exit per |
1595 // probabilities estimate the possibility of exit per |
1588 // a single loop iteration; afterward, they estimate |
1596 // a single loop iteration; afterward, they estimate |
1589 // the probability of exit per loop entry. |
1597 // the probability of exit per loop entry. |
1590 for (int i = 0; i < _exits.length(); i++) { |
1598 for (int i = 0; i < _exits.length(); i++) { |
1591 Block* et = _exits.at(i).get_target(); |
1599 Block* et = _exits.at(i).get_target(); |
1592 float new_prob = _exits.at(i).get_prob() / exits_sum; |
1600 float new_prob = 0.0f; |
|
1601 if (_exits.at(i).get_prob() > 0.0f) { |
|
1602 new_prob = _exits.at(i).get_prob() / exits_sum; |
|
1603 } |
1593 BlockProbPair bpp(et, new_prob); |
1604 BlockProbPair bpp(et, new_prob); |
1594 _exits.at_put(i, bpp); |
1605 _exits.at_put(i, bpp); |
1595 } |
1606 } |
1596 |
1607 |
1597 // Save the total, but guard against unreasoable probability, |
1608 // Save the total, but guard against unreasonable probability, |
1598 // as the value is used to estimate the loop trip count. |
1609 // as the value is used to estimate the loop trip count. |
1599 // An infinite trip count would blur relative block |
1610 // An infinite trip count would blur relative block |
1600 // frequencies. |
1611 // frequencies. |
1601 if (exits_sum > 1.0f) exits_sum = 1.0; |
1612 if (exits_sum > 1.0f) exits_sum = 1.0; |
1602 if (exits_sum < PROB_MIN) exits_sum = PROB_MIN; |
1613 if (exits_sum < PROB_MIN) exits_sum = PROB_MIN; |
1686 } |
1697 } |
1687 |
1698 |
1688 return 0.0f; |
1699 return 0.0f; |
1689 } |
1700 } |
1690 |
1701 |
|
1702 //------------------------------num_fall_throughs----------------------------- |
|
1703 // Return the number of fall-through candidates for a block |
|
1704 int Block::num_fall_throughs() { |
|
1705 int eidx = end_idx(); |
|
1706 Node *n = _nodes[eidx]; // Get ending Node |
|
1707 |
|
1708 int op = n->Opcode(); |
|
1709 if (n->is_Mach()) { |
|
1710 if (n->is_MachNullCheck()) { |
|
1711 // In theory, either side can fall-thru, for simplicity sake, |
|
1712 // let's say only the false branch can now. |
|
1713 return 1; |
|
1714 } |
|
1715 op = n->as_Mach()->ideal_Opcode(); |
|
1716 } |
|
1717 |
|
1718 // Switch on branch type |
|
1719 switch( op ) { |
|
1720 case Op_CountedLoopEnd: |
|
1721 case Op_If: |
|
1722 return 2; |
|
1723 |
|
1724 case Op_Root: |
|
1725 case Op_Goto: |
|
1726 return 1; |
|
1727 |
|
1728 case Op_Catch: { |
|
1729 for (uint i = 0; i < _num_succs; i++) { |
|
1730 const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj(); |
|
1731 if (ci->_con == CatchProjNode::fall_through_index) { |
|
1732 return 1; |
|
1733 } |
|
1734 } |
|
1735 return 0; |
|
1736 } |
|
1737 |
|
1738 case Op_Jump: |
|
1739 case Op_NeverBranch: |
|
1740 case Op_TailCall: |
|
1741 case Op_TailJump: |
|
1742 case Op_Return: |
|
1743 case Op_Halt: |
|
1744 case Op_Rethrow: |
|
1745 return 0; |
|
1746 |
|
1747 default: |
|
1748 ShouldNotReachHere(); |
|
1749 } |
|
1750 |
|
1751 return 0; |
|
1752 } |
|
1753 |
|
1754 //------------------------------succ_fall_through----------------------------- |
|
1755 // Return true if a specific successor could be fall-through target. |
|
1756 bool Block::succ_fall_through(uint i) { |
|
1757 int eidx = end_idx(); |
|
1758 Node *n = _nodes[eidx]; // Get ending Node |
|
1759 |
|
1760 int op = n->Opcode(); |
|
1761 if (n->is_Mach()) { |
|
1762 if (n->is_MachNullCheck()) { |
|
1763 // In theory, either side can fall-thru, for simplicity sake, |
|
1764 // let's say only the false branch can now. |
|
1765 return _nodes[i + eidx + 1]->Opcode() == Op_IfFalse; |
|
1766 } |
|
1767 op = n->as_Mach()->ideal_Opcode(); |
|
1768 } |
|
1769 |
|
1770 // Switch on branch type |
|
1771 switch( op ) { |
|
1772 case Op_CountedLoopEnd: |
|
1773 case Op_If: |
|
1774 case Op_Root: |
|
1775 case Op_Goto: |
|
1776 return true; |
|
1777 |
|
1778 case Op_Catch: { |
|
1779 const CatchProjNode *ci = _nodes[i + eidx + 1]->as_CatchProj(); |
|
1780 return ci->_con == CatchProjNode::fall_through_index; |
|
1781 } |
|
1782 |
|
1783 case Op_Jump: |
|
1784 case Op_NeverBranch: |
|
1785 case Op_TailCall: |
|
1786 case Op_TailJump: |
|
1787 case Op_Return: |
|
1788 case Op_Halt: |
|
1789 case Op_Rethrow: |
|
1790 return false; |
|
1791 |
|
1792 default: |
|
1793 ShouldNotReachHere(); |
|
1794 } |
|
1795 |
|
1796 return false; |
|
1797 } |
|
1798 |
|
1799 //------------------------------update_uncommon_branch------------------------ |
|
1800 // Update the probability of a two-branch to be uncommon |
|
1801 void Block::update_uncommon_branch(Block* ub) { |
|
1802 int eidx = end_idx(); |
|
1803 Node *n = _nodes[eidx]; // Get ending Node |
|
1804 |
|
1805 int op = n->as_Mach()->ideal_Opcode(); |
|
1806 |
|
1807 assert(op == Op_CountedLoopEnd || op == Op_If, "must be a If"); |
|
1808 assert(num_fall_throughs() == 2, "must be a two way branch block"); |
|
1809 |
|
1810 // Which successor is ub? |
|
1811 uint s; |
|
1812 for (s = 0; s <_num_succs; s++) { |
|
1813 if (_succs[s] == ub) break; |
|
1814 } |
|
1815 assert(s < 2, "uncommon successor must be found"); |
|
1816 |
|
1817 // If ub is the true path, make the proability small, else |
|
1818 // ub is the false path, and make the probability large |
|
1819 bool invert = (_nodes[s + eidx + 1]->Opcode() == Op_IfFalse); |
|
1820 |
|
1821 // Get existing probability |
|
1822 float p = n->as_MachIf()->_prob; |
|
1823 |
|
1824 if (invert) p = 1.0 - p; |
|
1825 if (p > PROB_MIN) { |
|
1826 p = PROB_MIN; |
|
1827 } |
|
1828 if (invert) p = 1.0 - p; |
|
1829 |
|
1830 n->as_MachIf()->_prob = p; |
|
1831 } |
|
1832 |
1691 //------------------------------update_succ_freq------------------------------- |
1833 //------------------------------update_succ_freq------------------------------- |
1692 // Update the appropriate frequency associated with block 'b', a succesor of |
1834 // Update the appropriate frequency associated with block 'b', a succesor of |
1693 // a block in this loop. |
1835 // a block in this loop. |
1694 void CFGLoop::update_succ_freq(Block* b, float freq) { |
1836 void CFGLoop::update_succ_freq(Block* b, float freq) { |
1695 if (b->_loop == this) { |
1837 if (b->_loop == this) { |