1644
1645 //------------------------------compute_freq-----------------------------------
1646 // Compute the frequency of each block and loop, relative to a single entry
1647 // into the dominating loop head.
1648 void CFGLoop::compute_freq() {
1649 // Bottom up traversal of loop tree (visit inner loops first.)
1650 // Set loop head frequency to 1.0, then transitively
1651 // compute frequency for all successors in the loop,
1652 // as well as for each exit edge. Inner loops are
1653 // treated as single blocks with loop exit targets
1654 // as the successor blocks.
1655
1656 // Nested loops first
1657 CFGLoop* ch = _child;
1658 while (ch != NULL) {
1659 ch->compute_freq();
1660 ch = ch->_sibling;
1661 }
1662 assert (_members.length() > 0, "no empty loops");
1663 Block* hd = head();
1664 hd->_freq = 1.0f;
1665 for (int i = 0; i < _members.length(); i++) {
1666 CFGElement* s = _members.at(i);
1667 float freq = s->_freq;
1668 if (s->is_block()) {
1669 Block* b = s->as_Block();
1670 for (uint j = 0; j < b->_num_succs; j++) {
1671 Block* sb = b->_succs[j];
1672 update_succ_freq(sb, freq * b->succ_prob(j));
1673 }
1674 } else {
1675 CFGLoop* lp = s->as_CFGLoop();
1676 assert(lp->_parent == this, "immediate child");
1677 for (int k = 0; k < lp->_exits.length(); k++) {
1678 Block* eb = lp->_exits.at(k).get_target();
1679 float prob = lp->_exits.at(k).get_prob();
1680 update_succ_freq(eb, freq * prob);
1681 }
1682 }
1683 }
1684
1685 // For all loops other than the outer, "method" loop,
1686 // sum and normalize the exit probability. The "method" loop
1687 // should keep the initial exit probability of 1, so that
1688 // inner blocks do not get erroneously scaled.
1689 if (_depth != 0) {
1690 // Total the exit probabilities for this loop.
1691 float exits_sum = 0.0f;
1692 for (int i = 0; i < _exits.length(); i++) {
1693 exits_sum += _exits.at(i).get_prob();
1694 }
1695
1696 // Normalize the exit probabilities. Until now, the
1697 // probabilities estimate the possibility of exit per
1698 // a single loop iteration; afterward, they estimate
1699 // the probability of exit per loop entry.
1700 for (int i = 0; i < _exits.length(); i++) {
1701 Block* et = _exits.at(i).get_target();
1702 float new_prob = 0.0f;
1703 if (_exits.at(i).get_prob() > 0.0f) {
1704 new_prob = _exits.at(i).get_prob() / exits_sum;
1705 }
1706 BlockProbPair bpp(et, new_prob);
1707 _exits.at_put(i, bpp);
1708 }
1709
1710 // Save the total, but guard against unreasonable probability,
1711 // as the value is used to estimate the loop trip count.
1918
1919 // If ub is the true path, make the proability small, else
1920 // ub is the false path, and make the probability large
1921 bool invert = (get_node(s + eidx + 1)->Opcode() == Op_IfFalse);
1922
1923 // Get existing probability
1924 float p = n->as_MachIf()->_prob;
1925
1926 if (invert) p = 1.0 - p;
1927 if (p > PROB_MIN) {
1928 p = PROB_MIN;
1929 }
1930 if (invert) p = 1.0 - p;
1931
1932 n->as_MachIf()->_prob = p;
1933 }
1934
1935 //------------------------------update_succ_freq-------------------------------
1936 // Update the appropriate frequency associated with block 'b', a successor of
1937 // a block in this loop.
1938 void CFGLoop::update_succ_freq(Block* b, float freq) {
1939 if (b->_loop == this) {
1940 if (b == head()) {
1941 // back branch within the loop
1942 // Do nothing now, the loop carried frequency will be
1943 // adjust later in scale_freq().
1944 } else {
1945 // simple branch within the loop
1946 b->_freq += freq;
1947 }
1948 } else if (!in_loop_nest(b)) {
1949 // branch is exit from this loop
1950 BlockProbPair bpp(b, freq);
1951 _exits.append(bpp);
1952 } else {
1953 // branch into nested loop
1954 CFGLoop* ch = b->_loop;
1955 ch->_freq += freq;
1956 }
1957 }
1958
1959 //------------------------------in_loop_nest-----------------------------------
1960 // Determine if block b is in the receiver's loop nest.
1961 bool CFGLoop::in_loop_nest(Block* b) {
1962 int depth = _depth;
1963 CFGLoop* b_loop = b->_loop;
1964 int b_depth = b_loop->_depth;
1965 if (depth == b_depth) {
1966 return true;
1967 }
1968 while (b_depth > depth) {
1969 b_loop = b_loop->_parent;
1970 b_depth = b_loop->_depth;
1971 }
1972 return b_loop == this;
1973 }
1974
1975 //------------------------------scale_freq-------------------------------------
1976 // Scale frequency of loops and blocks by trip counts from outer loops
1977 // Do a top down traversal of loop tree (visit outer loops first.)
1978 void CFGLoop::scale_freq() {
1979 float loop_freq = _freq * trip_count();
1980 _freq = loop_freq;
1981 for (int i = 0; i < _members.length(); i++) {
1982 CFGElement* s = _members.at(i);
1983 float block_freq = s->_freq * loop_freq;
1984 if (g_isnan(block_freq) || block_freq < MIN_BLOCK_FREQUENCY)
1985 block_freq = MIN_BLOCK_FREQUENCY;
1986 s->_freq = block_freq;
1987 }
1988 CFGLoop* ch = _child;
1989 while (ch != NULL) {
1990 ch->scale_freq();
1991 ch = ch->_sibling;
1992 }
1993 }
1994
1995 // Frequency of outer loop
1996 float CFGLoop::outer_loop_freq() const {
1997 if (_child != NULL) {
1998 return _child->_freq;
1999 }
2000 return _freq;
2001 }
2002
2003 #ifndef PRODUCT
2004 //------------------------------dump_tree--------------------------------------
2005 void CFGLoop::dump_tree() const {
2006 dump();
2007 if (_child != NULL) _child->dump_tree();
2008 if (_sibling != NULL) _sibling->dump_tree();
2009 }
2010
2011 //------------------------------dump-------------------------------------------
2012 void CFGLoop::dump() const {
2013 for (int i = 0; i < _depth; i++) tty->print(" ");
2014 tty->print("%s: %d trip_count: %6.0f freq: %6.0f\n",
2015 _depth == 0 ? "Method" : "Loop", _id, trip_count(), _freq);
2016 for (int i = 0; i < _depth; i++) tty->print(" ");
2025 CFGElement *s = _members.at(i);
2026 if (s->is_block()) {
2027 Block *b = s->as_Block();
2028 tty->print(" B%d(%6.3f)", b->_pre_order, b->_freq);
2029 } else {
2030 CFGLoop* lp = s->as_CFGLoop();
2031 tty->print(" L%d(%6.3f)", lp->_id, lp->_freq);
2032 }
2033 }
2034 tty->print("\n");
2035 for (int i = 0; i < _depth; i++) tty->print(" ");
2036 tty->print(" exits: ");
2037 k = 0;
2038 for (int i = 0; i < _exits.length(); i++) {
2039 if (k++ >= 7) {
2040 tty->print("\n ");
2041 for (int j = 0; j < _depth+1; j++) tty->print(" ");
2042 k = 0;
2043 }
2044 Block *blk = _exits.at(i).get_target();
2045 float prob = _exits.at(i).get_prob();
2046 tty->print(" ->%d@%d%%", blk->_pre_order, (int)(prob*100));
2047 }
2048 tty->print("\n");
2049 }
2050 #endif
|
1644
1645 //------------------------------compute_freq-----------------------------------
1646 // Compute the frequency of each block and loop, relative to a single entry
1647 // into the dominating loop head.
1648 void CFGLoop::compute_freq() {
1649 // Bottom up traversal of loop tree (visit inner loops first.)
1650 // Set loop head frequency to 1.0, then transitively
1651 // compute frequency for all successors in the loop,
1652 // as well as for each exit edge. Inner loops are
1653 // treated as single blocks with loop exit targets
1654 // as the successor blocks.
1655
1656 // Nested loops first
1657 CFGLoop* ch = _child;
1658 while (ch != NULL) {
1659 ch->compute_freq();
1660 ch = ch->_sibling;
1661 }
1662 assert (_members.length() > 0, "no empty loops");
1663 Block* hd = head();
1664 hd->_freq = 1.0;
1665 for (int i = 0; i < _members.length(); i++) {
1666 CFGElement* s = _members.at(i);
1667 double freq = s->_freq;
1668 if (s->is_block()) {
1669 Block* b = s->as_Block();
1670 for (uint j = 0; j < b->_num_succs; j++) {
1671 Block* sb = b->_succs[j];
1672 update_succ_freq(sb, freq * b->succ_prob(j));
1673 }
1674 } else {
1675 CFGLoop* lp = s->as_CFGLoop();
1676 assert(lp->_parent == this, "immediate child");
1677 for (int k = 0; k < lp->_exits.length(); k++) {
1678 Block* eb = lp->_exits.at(k).get_target();
1679 double prob = lp->_exits.at(k).get_prob();
1680 update_succ_freq(eb, freq * prob);
1681 }
1682 }
1683 }
1684
1685 // For all loops other than the outer, "method" loop,
1686 // sum and normalize the exit probability. The "method" loop
1687 // should keep the initial exit probability of 1, so that
1688 // inner blocks do not get erroneously scaled.
1689 if (_depth != 0) {
1690 // Total the exit probabilities for this loop.
1691 double exits_sum = 0.0f;
1692 for (int i = 0; i < _exits.length(); i++) {
1693 exits_sum += _exits.at(i).get_prob();
1694 }
1695
1696 // Normalize the exit probabilities. Until now, the
1697 // probabilities estimate the possibility of exit per
1698 // a single loop iteration; afterward, they estimate
1699 // the probability of exit per loop entry.
1700 for (int i = 0; i < _exits.length(); i++) {
1701 Block* et = _exits.at(i).get_target();
1702 float new_prob = 0.0f;
1703 if (_exits.at(i).get_prob() > 0.0f) {
1704 new_prob = _exits.at(i).get_prob() / exits_sum;
1705 }
1706 BlockProbPair bpp(et, new_prob);
1707 _exits.at_put(i, bpp);
1708 }
1709
1710 // Save the total, but guard against unreasonable probability,
1711 // as the value is used to estimate the loop trip count.
1918
1919 // If ub is the true path, make the proability small, else
1920 // ub is the false path, and make the probability large
1921 bool invert = (get_node(s + eidx + 1)->Opcode() == Op_IfFalse);
1922
1923 // Get existing probability
1924 float p = n->as_MachIf()->_prob;
1925
1926 if (invert) p = 1.0 - p;
1927 if (p > PROB_MIN) {
1928 p = PROB_MIN;
1929 }
1930 if (invert) p = 1.0 - p;
1931
1932 n->as_MachIf()->_prob = p;
1933 }
1934
1935 //------------------------------update_succ_freq-------------------------------
1936 // Update the appropriate frequency associated with block 'b', a successor of
1937 // a block in this loop.
1938 void CFGLoop::update_succ_freq(Block* b, double freq) {
1939 if (b->_loop == this) {
1940 if (b == head()) {
1941 // back branch within the loop
1942 // Do nothing now, the loop carried frequency will be
1943 // adjust later in scale_freq().
1944 } else {
1945 // simple branch within the loop
1946 b->_freq += freq;
1947 }
1948 } else if (!in_loop_nest(b)) {
1949 // branch is exit from this loop
1950 BlockProbPair bpp(b, freq);
1951 _exits.append(bpp);
1952 } else {
1953 // branch into nested loop
1954 CFGLoop* ch = b->_loop;
1955 ch->_freq += freq;
1956 }
1957 }
1958
1959 //------------------------------in_loop_nest-----------------------------------
1960 // Determine if block b is in the receiver's loop nest.
1961 bool CFGLoop::in_loop_nest(Block* b) {
1962 int depth = _depth;
1963 CFGLoop* b_loop = b->_loop;
1964 int b_depth = b_loop->_depth;
1965 if (depth == b_depth) {
1966 return true;
1967 }
1968 while (b_depth > depth) {
1969 b_loop = b_loop->_parent;
1970 b_depth = b_loop->_depth;
1971 }
1972 return b_loop == this;
1973 }
1974
1975 //------------------------------scale_freq-------------------------------------
1976 // Scale frequency of loops and blocks by trip counts from outer loops
1977 // Do a top down traversal of loop tree (visit outer loops first.)
1978 void CFGLoop::scale_freq() {
1979 double loop_freq = _freq * trip_count();
1980 _freq = loop_freq;
1981 for (int i = 0; i < _members.length(); i++) {
1982 CFGElement* s = _members.at(i);
1983 double block_freq = s->_freq * loop_freq;
1984 if (g_isnan(block_freq) || block_freq < MIN_BLOCK_FREQUENCY)
1985 block_freq = MIN_BLOCK_FREQUENCY;
1986 s->_freq = block_freq;
1987 }
1988 CFGLoop* ch = _child;
1989 while (ch != NULL) {
1990 ch->scale_freq();
1991 ch = ch->_sibling;
1992 }
1993 }
1994
1995 // Frequency of outer loop
1996 double CFGLoop::outer_loop_freq() const {
1997 if (_child != NULL) {
1998 return _child->_freq;
1999 }
2000 return _freq;
2001 }
2002
2003 #ifndef PRODUCT
2004 //------------------------------dump_tree--------------------------------------
2005 void CFGLoop::dump_tree() const {
2006 dump();
2007 if (_child != NULL) _child->dump_tree();
2008 if (_sibling != NULL) _sibling->dump_tree();
2009 }
2010
2011 //------------------------------dump-------------------------------------------
2012 void CFGLoop::dump() const {
2013 for (int i = 0; i < _depth; i++) tty->print(" ");
2014 tty->print("%s: %d trip_count: %6.0f freq: %6.0f\n",
2015 _depth == 0 ? "Method" : "Loop", _id, trip_count(), _freq);
2016 for (int i = 0; i < _depth; i++) tty->print(" ");
2025 CFGElement *s = _members.at(i);
2026 if (s->is_block()) {
2027 Block *b = s->as_Block();
2028 tty->print(" B%d(%6.3f)", b->_pre_order, b->_freq);
2029 } else {
2030 CFGLoop* lp = s->as_CFGLoop();
2031 tty->print(" L%d(%6.3f)", lp->_id, lp->_freq);
2032 }
2033 }
2034 tty->print("\n");
2035 for (int i = 0; i < _depth; i++) tty->print(" ");
2036 tty->print(" exits: ");
2037 k = 0;
2038 for (int i = 0; i < _exits.length(); i++) {
2039 if (k++ >= 7) {
2040 tty->print("\n ");
2041 for (int j = 0; j < _depth+1; j++) tty->print(" ");
2042 k = 0;
2043 }
2044 Block *blk = _exits.at(i).get_target();
2045 double prob = _exits.at(i).get_prob();
2046 tty->print(" ->%d@%d%%", blk->_pre_order, (int)(prob*100));
2047 }
2048 tty->print("\n");
2049 }
2050 #endif
|