Mercurial > hg > truffle
comparison src/share/vm/ci/ciTypeFlow.cpp @ 367:194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
Reviewed-by: rasbold, jrose
author | never |
---|---|
date | Wed, 17 Sep 2008 12:59:52 -0700 |
parents | a61af66fc99e |
children | ad8c8ca4ab0f |
comparison
equal
deleted
inserted
replaced
366:8261ee795323 | 367:194b8e3a2fc4 |
---|---|
336 for (int i=0; i<max_cells; i++) { | 336 for (int i=0; i<max_cells; i++) { |
337 _types[i] = top_type(); | 337 _types[i] = top_type(); |
338 } | 338 } |
339 _trap_bci = -1; | 339 _trap_bci = -1; |
340 _trap_index = 0; | 340 _trap_index = 0; |
341 } | 341 _def_locals.clear(); |
342 } | |
343 | |
342 | 344 |
343 // ------------------------------------------------------------------ | 345 // ------------------------------------------------------------------ |
344 // ciTypeFlow::get_start_state | 346 // ciTypeFlow::get_start_state |
345 // | 347 // |
346 // Set this vector to the method entry state. | 348 // Set this vector to the method entry state. |
733 // ------------------------------------------------------------------ | 735 // ------------------------------------------------------------------ |
734 // ciTypeFlow::StateVector::do_new | 736 // ciTypeFlow::StateVector::do_new |
735 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) { | 737 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) { |
736 bool will_link; | 738 bool will_link; |
737 ciKlass* klass = str->get_klass(will_link); | 739 ciKlass* klass = str->get_klass(will_link); |
738 if (!will_link) { | 740 if (!will_link || str->is_unresolved_klass()) { |
739 trap(str, klass, str->get_klass_index()); | 741 trap(str, klass, str->get_klass_index()); |
740 } else { | 742 } else { |
741 push_object(klass); | 743 push_object(klass); |
742 } | 744 } |
743 } | 745 } |
1266 pop_int(); | 1268 pop_int(); |
1267 break; | 1269 break; |
1268 } | 1270 } |
1269 case Bytecodes::_iinc: | 1271 case Bytecodes::_iinc: |
1270 { | 1272 { |
1271 check_int(local(str->get_index())); | 1273 int lnum = str->get_index(); |
1274 check_int(local(lnum)); | |
1275 store_to_local(lnum); | |
1272 break; | 1276 break; |
1273 } | 1277 } |
1274 case Bytecodes::_iload: load_local_int(str->get_index()); break; | 1278 case Bytecodes::_iload: load_local_int(str->get_index()); break; |
1275 case Bytecodes::_iload_0: load_local_int(0); break; | 1279 case Bytecodes::_iload_0: load_local_int(0); break; |
1276 case Bytecodes::_iload_1: load_local_int(1); break; | 1280 case Bytecodes::_iload_1: load_local_int(1); break; |
1504 } | 1508 } |
1505 } | 1509 } |
1506 } | 1510 } |
1507 #endif | 1511 #endif |
1508 | 1512 |
1513 | |
1514 // ------------------------------------------------------------------ | |
1515 // ciTypeFlow::SuccIter::next | |
1516 // | |
1517 void ciTypeFlow::SuccIter::next() { | |
1518 int succ_ct = _pred->successors()->length(); | |
1519 int next = _index + 1; | |
1520 if (next < succ_ct) { | |
1521 _index = next; | |
1522 _succ = _pred->successors()->at(next); | |
1523 return; | |
1524 } | |
1525 for (int i = next - succ_ct; i < _pred->exceptions()->length(); i++) { | |
1526 // Do not compile any code for unloaded exception types. | |
1527 // Following compiler passes are responsible for doing this also. | |
1528 ciInstanceKlass* exception_klass = _pred->exc_klasses()->at(i); | |
1529 if (exception_klass->is_loaded()) { | |
1530 _index = next; | |
1531 _succ = _pred->exceptions()->at(i); | |
1532 return; | |
1533 } | |
1534 next++; | |
1535 } | |
1536 _index = -1; | |
1537 _succ = NULL; | |
1538 } | |
1539 | |
1540 // ------------------------------------------------------------------ | |
1541 // ciTypeFlow::SuccIter::set_succ | |
1542 // | |
1543 void ciTypeFlow::SuccIter::set_succ(Block* succ) { | |
1544 int succ_ct = _pred->successors()->length(); | |
1545 if (_index < succ_ct) { | |
1546 _pred->successors()->at_put(_index, succ); | |
1547 } else { | |
1548 int idx = _index - succ_ct; | |
1549 _pred->exceptions()->at_put(idx, succ); | |
1550 } | |
1551 } | |
1552 | |
1509 // ciTypeFlow::Block | 1553 // ciTypeFlow::Block |
1510 // | 1554 // |
1511 // A basic block. | 1555 // A basic block. |
1512 | 1556 |
1513 // ------------------------------------------------------------------ | 1557 // ------------------------------------------------------------------ |
1524 new (outer->arena()) JsrSet(outer->arena(), jsrs->size()); | 1568 new (outer->arena()) JsrSet(outer->arena(), jsrs->size()); |
1525 jsrs->copy_into(new_jsrs); | 1569 jsrs->copy_into(new_jsrs); |
1526 _jsrs = new_jsrs; | 1570 _jsrs = new_jsrs; |
1527 _next = NULL; | 1571 _next = NULL; |
1528 _on_work_list = false; | 1572 _on_work_list = false; |
1529 _pre_order = -1; assert(!has_pre_order(), ""); | 1573 _backedge_copy = false; |
1530 _private_copy = false; | 1574 _exception_entry = false; |
1531 _trap_bci = -1; | 1575 _trap_bci = -1; |
1532 _trap_index = 0; | 1576 _trap_index = 0; |
1577 df_init(); | |
1533 | 1578 |
1534 if (CITraceTypeFlow) { | 1579 if (CITraceTypeFlow) { |
1535 tty->print_cr(">> Created new block"); | 1580 tty->print_cr(">> Created new block"); |
1536 print_on(tty); | 1581 print_on(tty); |
1537 } | 1582 } |
1539 assert(this->outer() == outer, "outer link set up"); | 1584 assert(this->outer() == outer, "outer link set up"); |
1540 assert(!outer->have_block_count(), "must not have mapped blocks yet"); | 1585 assert(!outer->have_block_count(), "must not have mapped blocks yet"); |
1541 } | 1586 } |
1542 | 1587 |
1543 // ------------------------------------------------------------------ | 1588 // ------------------------------------------------------------------ |
1544 // ciTypeFlow::Block::clone_loop_head | 1589 // ciTypeFlow::Block::df_init |
1545 // | 1590 void ciTypeFlow::Block::df_init() { |
1546 ciTypeFlow::Block* | 1591 _pre_order = -1; assert(!has_pre_order(), ""); |
1547 ciTypeFlow::Block::clone_loop_head(ciTypeFlow* analyzer, | 1592 _post_order = -1; assert(!has_post_order(), ""); |
1548 int branch_bci, | 1593 _loop = NULL; |
1549 ciTypeFlow::Block* target, | 1594 _irreducible_entry = false; |
1550 ciTypeFlow::JsrSet* jsrs) { | 1595 _rpo_next = NULL; |
1551 // Loop optimizations are not performed on Tier1 compiles. Do nothing. | |
1552 if (analyzer->env()->comp_level() < CompLevel_full_optimization) { | |
1553 return target; | |
1554 } | |
1555 | |
1556 // The current block ends with a branch. | |
1557 // | |
1558 // If the target block appears to be the test-clause of a for loop, and | |
1559 // it is not too large, and it has not yet been cloned, clone it. | |
1560 // The pre-existing copy becomes the private clone used only by | |
1561 // the initial iteration of the loop. (We know we are simulating | |
1562 // the initial iteration right now, since we have never calculated | |
1563 // successors before for this block.) | |
1564 | |
1565 if (branch_bci <= start() | |
1566 && (target->limit() - target->start()) <= CICloneLoopTestLimit | |
1567 && target->private_copy_count() == 0) { | |
1568 // Setting the private_copy bit ensures that the target block cannot be | |
1569 // reached by any other paths, such as fall-in from the loop body. | |
1570 // The private copy will be accessible only on successor lists | |
1571 // created up to this point. | |
1572 target->set_private_copy(true); | |
1573 if (CITraceTypeFlow) { | |
1574 tty->print(">> Cloning a test-clause block "); | |
1575 print_value_on(tty); | |
1576 tty->cr(); | |
1577 } | |
1578 // If the target is the current block, then later on a new copy of the | |
1579 // target block will be created when its bytecodes are reached by | |
1580 // an alternate path. (This is the case for loops with the loop | |
1581 // head at the bci-wise bottom of the loop, as with pre-1.4.2 javac.) | |
1582 // | |
1583 // Otherwise, duplicate the target block now and use it immediately. | |
1584 // (The case for loops with the loop head at the bci-wise top of the | |
1585 // loop, as with 1.4.2 javac.) | |
1586 // | |
1587 // In either case, the new copy of the block will remain public. | |
1588 if (target != this) { | |
1589 target = analyzer->block_at(branch_bci, jsrs); | |
1590 } | |
1591 } | |
1592 return target; | |
1593 } | 1596 } |
1594 | 1597 |
1595 // ------------------------------------------------------------------ | 1598 // ------------------------------------------------------------------ |
1596 // ciTypeFlow::Block::successors | 1599 // ciTypeFlow::Block::successors |
1597 // | 1600 // |
1642 case Bytecodes::_if_icmpgt: case Bytecodes::_if_icmple: | 1645 case Bytecodes::_if_icmpgt: case Bytecodes::_if_icmple: |
1643 case Bytecodes::_if_acmpeq: case Bytecodes::_if_acmpne: | 1646 case Bytecodes::_if_acmpeq: case Bytecodes::_if_acmpne: |
1644 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull: | 1647 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull: |
1645 // Our successors are the branch target and the next bci. | 1648 // Our successors are the branch target and the next bci. |
1646 branch_bci = str->get_dest(); | 1649 branch_bci = str->get_dest(); |
1647 clone_loop_head(analyzer, branch_bci, this, jsrs); | |
1648 _successors = | 1650 _successors = |
1649 new (arena) GrowableArray<Block*>(arena, 2, 0, NULL); | 1651 new (arena) GrowableArray<Block*>(arena, 2, 0, NULL); |
1650 assert(_successors->length() == IF_NOT_TAKEN, ""); | 1652 assert(_successors->length() == IF_NOT_TAKEN, ""); |
1651 _successors->append(analyzer->block_at(next_bci, jsrs)); | 1653 _successors->append(analyzer->block_at(next_bci, jsrs)); |
1652 assert(_successors->length() == IF_TAKEN, ""); | 1654 assert(_successors->length() == IF_TAKEN, ""); |
1656 case Bytecodes::_goto: | 1658 case Bytecodes::_goto: |
1657 branch_bci = str->get_dest(); | 1659 branch_bci = str->get_dest(); |
1658 _successors = | 1660 _successors = |
1659 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL); | 1661 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL); |
1660 assert(_successors->length() == GOTO_TARGET, ""); | 1662 assert(_successors->length() == GOTO_TARGET, ""); |
1661 target = analyzer->block_at(branch_bci, jsrs); | 1663 _successors->append(analyzer->block_at(branch_bci, jsrs)); |
1662 // If the target block has not been visited yet, and looks like | |
1663 // a two-way branch, attempt to clone it if it is a loop head. | |
1664 if (target->_successors != NULL | |
1665 && target->_successors->length() == (IF_TAKEN + 1)) { | |
1666 target = clone_loop_head(analyzer, branch_bci, target, jsrs); | |
1667 } | |
1668 _successors->append(target); | |
1669 break; | 1664 break; |
1670 | 1665 |
1671 case Bytecodes::_jsr: | 1666 case Bytecodes::_jsr: |
1672 branch_bci = str->get_dest(); | 1667 branch_bci = str->get_dest(); |
1673 _successors = | 1668 _successors = |
1799 _exc_klasses->append(klass); | 1794 _exc_klasses->append(klass); |
1800 } | 1795 } |
1801 } | 1796 } |
1802 | 1797 |
1803 // ------------------------------------------------------------------ | 1798 // ------------------------------------------------------------------ |
1804 // ciTypeFlow::Block::is_simpler_than | 1799 // ciTypeFlow::Block::set_backedge_copy |
1805 // | 1800 // Use this only to make a pre-existing public block into a backedge copy. |
1806 // A relation used to order our work list. We work on a block earlier | 1801 void ciTypeFlow::Block::set_backedge_copy(bool z) { |
1807 // if it has a smaller jsr stack or it occurs earlier in the program | 1802 assert(z || (z == is_backedge_copy()), "cannot make a backedge copy public"); |
1808 // text. | 1803 _backedge_copy = z; |
1809 // | 1804 } |
1810 // Note: maybe we should redo this functionality to make blocks | 1805 |
1811 // which correspond to exceptions lower priority. | 1806 // ------------------------------------------------------------------ |
1812 bool ciTypeFlow::Block::is_simpler_than(ciTypeFlow::Block* other) { | 1807 // ciTypeFlow::Block::is_clonable_exit |
1813 if (other == NULL) { | 1808 // |
1814 return true; | 1809 // At most 2 normal successors, one of which continues looping, |
1815 } else { | 1810 // and all exceptional successors must exit. |
1816 int size1 = _jsrs->size(); | 1811 bool ciTypeFlow::Block::is_clonable_exit(ciTypeFlow::Loop* lp) { |
1817 int size2 = other->_jsrs->size(); | 1812 int normal_cnt = 0; |
1818 if (size1 < size2) { | 1813 int in_loop_cnt = 0; |
1819 return true; | 1814 for (SuccIter iter(this); !iter.done(); iter.next()) { |
1820 } else if (size2 < size1) { | 1815 Block* succ = iter.succ(); |
1821 return false; | 1816 if (iter.is_normal_ctrl()) { |
1817 if (++normal_cnt > 2) return false; | |
1818 if (lp->contains(succ->loop())) { | |
1819 if (++in_loop_cnt > 1) return false; | |
1820 } | |
1822 } else { | 1821 } else { |
1823 #if 0 | 1822 if (lp->contains(succ->loop())) return false; |
1824 if (size1 > 0) { | 1823 } |
1825 int r1 = _jsrs->record_at(0)->return_address(); | 1824 } |
1826 int r2 = _jsrs->record_at(0)->return_address(); | 1825 return in_loop_cnt == 1; |
1827 if (r1 < r2) { | 1826 } |
1828 return true; | 1827 |
1829 } else if (r2 < r1) { | 1828 // ------------------------------------------------------------------ |
1830 return false; | 1829 // ciTypeFlow::Block::looping_succ |
1831 } else { | 1830 // |
1832 int e1 = _jsrs->record_at(0)->return_address(); | 1831 ciTypeFlow::Block* ciTypeFlow::Block::looping_succ(ciTypeFlow::Loop* lp) { |
1833 int e2 = _jsrs->record_at(0)->return_address(); | 1832 assert(successors()->length() <= 2, "at most 2 normal successors"); |
1834 if (e1 < e2) { | 1833 for (SuccIter iter(this); !iter.done(); iter.next()) { |
1835 return true; | 1834 Block* succ = iter.succ(); |
1836 } else if (e2 < e1) { | 1835 if (lp->contains(succ->loop())) { |
1837 return false; | 1836 return succ; |
1838 } | 1837 } |
1839 } | 1838 } |
1840 } | 1839 return NULL; |
1841 #endif | |
1842 return (start() <= other->start()); | |
1843 } | |
1844 } | |
1845 } | |
1846 | |
1847 // ------------------------------------------------------------------ | |
1848 // ciTypeFlow::Block::set_private_copy | |
1849 // Use this only to make a pre-existing public block into a private copy. | |
1850 void ciTypeFlow::Block::set_private_copy(bool z) { | |
1851 assert(z || (z == is_private_copy()), "cannot make a private copy public"); | |
1852 _private_copy = z; | |
1853 } | 1840 } |
1854 | 1841 |
1855 #ifndef PRODUCT | 1842 #ifndef PRODUCT |
1856 // ------------------------------------------------------------------ | 1843 // ------------------------------------------------------------------ |
1857 // ciTypeFlow::Block::print_value_on | 1844 // ciTypeFlow::Block::print_value_on |
1858 void ciTypeFlow::Block::print_value_on(outputStream* st) const { | 1845 void ciTypeFlow::Block::print_value_on(outputStream* st) const { |
1859 if (has_pre_order()) st->print("#%-2d ", pre_order()); | 1846 if (has_pre_order()) st->print("#%-2d ", pre_order()); |
1847 if (has_rpo()) st->print("rpo#%-2d ", rpo()); | |
1860 st->print("[%d - %d)", start(), limit()); | 1848 st->print("[%d - %d)", start(), limit()); |
1849 if (is_loop_head()) st->print(" lphd"); | |
1850 if (is_irreducible_entry()) st->print(" irred"); | |
1861 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); } | 1851 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); } |
1862 if (is_private_copy()) st->print("/private_copy"); | 1852 if (is_backedge_copy()) st->print("/backedge_copy"); |
1863 } | 1853 } |
1864 | 1854 |
1865 // ------------------------------------------------------------------ | 1855 // ------------------------------------------------------------------ |
1866 // ciTypeFlow::Block::print_on | 1856 // ciTypeFlow::Block::print_on |
1867 void ciTypeFlow::Block::print_on(outputStream* st) const { | 1857 void ciTypeFlow::Block::print_on(outputStream* st) const { |
1869 outer()->method()->print_codes_on(start(), limit(), st); | 1859 outer()->method()->print_codes_on(start(), limit(), st); |
1870 } | 1860 } |
1871 st->print_cr(" ==================================================== "); | 1861 st->print_cr(" ==================================================== "); |
1872 st->print (" "); | 1862 st->print (" "); |
1873 print_value_on(st); | 1863 print_value_on(st); |
1864 st->print(" Stored locals: "); def_locals()->print_on(st, outer()->method()->max_locals()); tty->cr(); | |
1865 if (loop() && loop()->parent() != NULL) { | |
1866 st->print(" loops:"); | |
1867 Loop* lp = loop(); | |
1868 do { | |
1869 st->print(" %d<-%d", lp->head()->pre_order(),lp->tail()->pre_order()); | |
1870 if (lp->is_irreducible()) st->print("(ir)"); | |
1871 lp = lp->parent(); | |
1872 } while (lp->parent() != NULL); | |
1873 } | |
1874 st->cr(); | 1874 st->cr(); |
1875 _state->print_on(st); | 1875 _state->print_on(st); |
1876 if (_successors == NULL) { | 1876 if (_successors == NULL) { |
1877 st->print_cr(" No successor information"); | 1877 st->print_cr(" No successor information"); |
1878 } else { | 1878 } else { |
1905 } | 1905 } |
1906 st->print_cr(" ==================================================== "); | 1906 st->print_cr(" ==================================================== "); |
1907 } | 1907 } |
1908 #endif | 1908 #endif |
1909 | 1909 |
1910 #ifndef PRODUCT | |
1911 // ------------------------------------------------------------------ | |
1912 // ciTypeFlow::LocalSet::print_on | |
1913 void ciTypeFlow::LocalSet::print_on(outputStream* st, int limit) const { | |
1914 st->print("{"); | |
1915 for (int i = 0; i < max; i++) { | |
1916 if (test(i)) st->print(" %d", i); | |
1917 } | |
1918 if (limit > max) { | |
1919 st->print(" %d..%d ", max, limit); | |
1920 } | |
1921 st->print(" }"); | |
1922 } | |
1923 #endif | |
1924 | |
1910 // ciTypeFlow | 1925 // ciTypeFlow |
1911 // | 1926 // |
1912 // This is a pass over the bytecodes which computes the following: | 1927 // This is a pass over the bytecodes which computes the following: |
1913 // basic block structure | 1928 // basic block structure |
1914 // interpreter type-states (a la the verifier) | 1929 // interpreter type-states (a la the verifier) |
1920 _method = method; | 1935 _method = method; |
1921 _methodBlocks = method->get_method_blocks(); | 1936 _methodBlocks = method->get_method_blocks(); |
1922 _max_locals = method->max_locals(); | 1937 _max_locals = method->max_locals(); |
1923 _max_stack = method->max_stack(); | 1938 _max_stack = method->max_stack(); |
1924 _code_size = method->code_size(); | 1939 _code_size = method->code_size(); |
1940 _has_irreducible_entry = false; | |
1925 _osr_bci = osr_bci; | 1941 _osr_bci = osr_bci; |
1926 _failure_reason = NULL; | 1942 _failure_reason = NULL; |
1927 assert(start_bci() >= 0 && start_bci() < code_size() , "correct osr_bci argument"); | 1943 assert(start_bci() >= 0 && start_bci() < code_size() , "correct osr_bci argument"); |
1928 | |
1929 _work_list = NULL; | 1944 _work_list = NULL; |
1930 _next_pre_order = 0; | |
1931 | 1945 |
1932 _ciblock_count = _methodBlocks->num_blocks(); | 1946 _ciblock_count = _methodBlocks->num_blocks(); |
1933 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, _ciblock_count); | 1947 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, _ciblock_count); |
1934 for (int i = 0; i < _ciblock_count; i++) { | 1948 for (int i = 0; i < _ciblock_count; i++) { |
1935 _idx_to_blocklist[i] = NULL; | 1949 _idx_to_blocklist[i] = NULL; |
1947 assert(!work_list_empty(), "work list must not be empty"); | 1961 assert(!work_list_empty(), "work list must not be empty"); |
1948 Block* next_block = _work_list; | 1962 Block* next_block = _work_list; |
1949 _work_list = next_block->next(); | 1963 _work_list = next_block->next(); |
1950 next_block->set_next(NULL); | 1964 next_block->set_next(NULL); |
1951 next_block->set_on_work_list(false); | 1965 next_block->set_on_work_list(false); |
1952 if (!next_block->has_pre_order()) { | |
1953 // Assign "pre_order" as each new block is taken from the work list. | |
1954 // This number may be used by following phases to order block visits. | |
1955 assert(!have_block_count(), "must not have mapped blocks yet") | |
1956 next_block->set_pre_order(_next_pre_order++); | |
1957 } | |
1958 return next_block; | 1966 return next_block; |
1959 } | 1967 } |
1960 | 1968 |
1961 // ------------------------------------------------------------------ | 1969 // ------------------------------------------------------------------ |
1962 // ciTypeFlow::add_to_work_list | 1970 // ciTypeFlow::add_to_work_list |
1963 // | 1971 // |
1964 // Add a basic block to our work list. | 1972 // Add a basic block to our work list. |
1973 // List is sorted by decreasing postorder sort (same as increasing RPO) | |
1965 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) { | 1974 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) { |
1966 assert(!block->is_on_work_list(), "must not already be on work list"); | 1975 assert(!block->is_on_work_list(), "must not already be on work list"); |
1967 | 1976 |
1968 if (CITraceTypeFlow) { | 1977 if (CITraceTypeFlow) { |
1969 tty->print(">> Adding block%s ", block->has_pre_order() ? " (again)" : ""); | 1978 tty->print(">> Adding block "); |
1970 block->print_value_on(tty); | 1979 block->print_value_on(tty); |
1971 tty->print_cr(" to the work list : "); | 1980 tty->print_cr(" to the work list : "); |
1972 } | 1981 } |
1973 | 1982 |
1974 block->set_on_work_list(true); | 1983 block->set_on_work_list(true); |
1975 if (block->is_simpler_than(_work_list)) { | 1984 |
1985 // decreasing post order sort | |
1986 | |
1987 Block* prev = NULL; | |
1988 Block* current = _work_list; | |
1989 int po = block->post_order(); | |
1990 while (current != NULL) { | |
1991 if (!current->has_post_order() || po > current->post_order()) | |
1992 break; | |
1993 prev = current; | |
1994 current = current->next(); | |
1995 } | |
1996 if (prev == NULL) { | |
1976 block->set_next(_work_list); | 1997 block->set_next(_work_list); |
1977 _work_list = block; | 1998 _work_list = block; |
1978 } else { | 1999 } else { |
1979 Block *temp = _work_list; | 2000 block->set_next(current); |
1980 while (!block->is_simpler_than(temp->next())) { | 2001 prev->set_next(block); |
1981 if (CITraceTypeFlow) { | 2002 } |
1982 tty->print("."); | 2003 |
1983 } | |
1984 temp = temp->next(); | |
1985 } | |
1986 block->set_next(temp->next()); | |
1987 temp->set_next(block); | |
1988 } | |
1989 if (CITraceTypeFlow) { | 2004 if (CITraceTypeFlow) { |
1990 tty->cr(); | 2005 tty->cr(); |
1991 } | 2006 } |
1992 } | 2007 } |
1993 | 2008 |
2006 | 2021 |
2007 ciBlock* ciblk = _methodBlocks->block_containing(bci); | 2022 ciBlock* ciblk = _methodBlocks->block_containing(bci); |
2008 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries"); | 2023 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries"); |
2009 Block* block = get_block_for(ciblk->index(), jsrs, option); | 2024 Block* block = get_block_for(ciblk->index(), jsrs, option); |
2010 | 2025 |
2011 assert(block == NULL? (option == no_create): block->is_private_copy() == (option == create_private_copy), "create option consistent with result"); | 2026 assert(block == NULL? (option == no_create): block->is_backedge_copy() == (option == create_backedge_copy), "create option consistent with result"); |
2012 | 2027 |
2013 if (CITraceTypeFlow) { | 2028 if (CITraceTypeFlow) { |
2014 if (block != NULL) { | 2029 if (block != NULL) { |
2015 tty->print(">> Found block "); | 2030 tty->print(">> Found block "); |
2016 block->print_value_on(tty); | 2031 block->print_value_on(tty); |
2070 // Following compiler passes are responsible for doing this also. | 2085 // Following compiler passes are responsible for doing this also. |
2071 continue; | 2086 continue; |
2072 } | 2087 } |
2073 | 2088 |
2074 if (block->meet_exception(exception_klass, state)) { | 2089 if (block->meet_exception(exception_klass, state)) { |
2075 // Block was modified. Add it to the work list. | 2090 // Block was modified and has PO. Add it to the work list. |
2076 if (!block->is_on_work_list()) { | 2091 if (block->has_post_order() && |
2092 !block->is_on_work_list()) { | |
2077 add_to_work_list(block); | 2093 add_to_work_list(block); |
2078 } | 2094 } |
2079 } | 2095 } |
2080 } | 2096 } |
2081 } | 2097 } |
2089 ciTypeFlow::StateVector* state) { | 2105 ciTypeFlow::StateVector* state) { |
2090 int len = successors->length(); | 2106 int len = successors->length(); |
2091 for (int i = 0; i < len; i++) { | 2107 for (int i = 0; i < len; i++) { |
2092 Block* block = successors->at(i); | 2108 Block* block = successors->at(i); |
2093 if (block->meet(state)) { | 2109 if (block->meet(state)) { |
2094 // Block was modified. Add it to the work list. | 2110 // Block was modified and has PO. Add it to the work list. |
2095 if (!block->is_on_work_list()) { | 2111 if (block->has_post_order() && |
2112 !block->is_on_work_list()) { | |
2096 add_to_work_list(block); | 2113 add_to_work_list(block); |
2097 } | 2114 } |
2098 } | 2115 } |
2099 } | 2116 } |
2100 } | 2117 } |
2131 } | 2148 } |
2132 | 2149 |
2133 return true; | 2150 return true; |
2134 } | 2151 } |
2135 | 2152 |
2153 // ------------------------------------------------------------------ | |
2154 // ciTypeFlow::clone_loop_heads | |
2155 // | |
2156 // Clone the loop heads | |
2157 bool ciTypeFlow::clone_loop_heads(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) { | |
2158 bool rslt = false; | |
2159 for (PreorderLoops iter(loop_tree_root()); !iter.done(); iter.next()) { | |
2160 lp = iter.current(); | |
2161 Block* head = lp->head(); | |
2162 if (lp == loop_tree_root() || | |
2163 lp->is_irreducible() || | |
2164 !head->is_clonable_exit(lp)) | |
2165 continue; | |
2166 | |
2167 // check not already cloned | |
2168 if (head->backedge_copy_count() != 0) | |
2169 continue; | |
2170 | |
2171 // check _no_ shared head below us | |
2172 Loop* ch; | |
2173 for (ch = lp->child(); ch != NULL && ch->head() != head; ch = ch->sibling()); | |
2174 if (ch != NULL) | |
2175 continue; | |
2176 | |
2177 // Clone head | |
2178 Block* new_head = head->looping_succ(lp); | |
2179 Block* clone = clone_loop_head(lp, temp_vector, temp_set); | |
2180 // Update lp's info | |
2181 clone->set_loop(lp); | |
2182 lp->set_head(new_head); | |
2183 lp->set_tail(clone); | |
2184 // And move original head into outer loop | |
2185 head->set_loop(lp->parent()); | |
2186 | |
2187 rslt = true; | |
2188 } | |
2189 return rslt; | |
2190 } | |
2191 | |
2192 // ------------------------------------------------------------------ | |
2193 // ciTypeFlow::clone_loop_head | |
2194 // | |
2195 // Clone lp's head and replace tail's successors with clone. | |
2196 // | |
2197 // | | |
2198 // v | |
2199 // head <-> body | |
2200 // | | |
2201 // v | |
2202 // exit | |
2203 // | |
2204 // new_head | |
2205 // | |
2206 // | | |
2207 // v | |
2208 // head ----------\ | |
2209 // | | | |
2210 // | v | |
2211 // | clone <-> body | |
2212 // | | | |
2213 // | /--/ | |
2214 // | | | |
2215 // v v | |
2216 // exit | |
2217 // | |
2218 ciTypeFlow::Block* ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) { | |
2219 Block* head = lp->head(); | |
2220 Block* tail = lp->tail(); | |
2221 if (CITraceTypeFlow) { | |
2222 tty->print(">> Requesting clone of loop head "); head->print_value_on(tty); | |
2223 tty->print(" for predecessor "); tail->print_value_on(tty); | |
2224 tty->cr(); | |
2225 } | |
2226 Block* clone = block_at(head->start(), head->jsrs(), create_backedge_copy); | |
2227 assert(clone->backedge_copy_count() == 1, "one backedge copy for all back edges"); | |
2228 | |
2229 assert(!clone->has_pre_order(), "just created"); | |
2230 clone->set_next_pre_order(); | |
2231 | |
2232 // Insert clone after (orig) tail in reverse post order | |
2233 clone->set_rpo_next(tail->rpo_next()); | |
2234 tail->set_rpo_next(clone); | |
2235 | |
2236 // tail->head becomes tail->clone | |
2237 for (SuccIter iter(tail); !iter.done(); iter.next()) { | |
2238 if (iter.succ() == head) { | |
2239 iter.set_succ(clone); | |
2240 break; | |
2241 } | |
2242 } | |
2243 flow_block(tail, temp_vector, temp_set); | |
2244 if (head == tail) { | |
2245 // For self-loops, clone->head becomes clone->clone | |
2246 flow_block(clone, temp_vector, temp_set); | |
2247 for (SuccIter iter(clone); !iter.done(); iter.next()) { | |
2248 if (iter.succ() == head) { | |
2249 iter.set_succ(clone); | |
2250 break; | |
2251 } | |
2252 } | |
2253 } | |
2254 flow_block(clone, temp_vector, temp_set); | |
2255 | |
2256 return clone; | |
2257 } | |
2136 | 2258 |
2137 // ------------------------------------------------------------------ | 2259 // ------------------------------------------------------------------ |
2138 // ciTypeFlow::flow_block | 2260 // ciTypeFlow::flow_block |
2139 // | 2261 // |
2140 // Interpret the effects of the bytecodes on the incoming state | 2262 // Interpret the effects of the bytecodes on the incoming state |
2157 limit = control; | 2279 limit = control; |
2158 } | 2280 } |
2159 | 2281 |
2160 // Grab the state from the current block. | 2282 // Grab the state from the current block. |
2161 block->copy_state_into(state); | 2283 block->copy_state_into(state); |
2284 state->def_locals()->clear(); | |
2162 | 2285 |
2163 GrowableArray<Block*>* exceptions = block->exceptions(); | 2286 GrowableArray<Block*>* exceptions = block->exceptions(); |
2164 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses(); | 2287 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses(); |
2165 bool has_exceptions = exceptions->length() > 0; | 2288 bool has_exceptions = exceptions->length() > 0; |
2289 | |
2290 bool exceptions_used = false; | |
2166 | 2291 |
2167 ciBytecodeStream str(method()); | 2292 ciBytecodeStream str(method()); |
2168 str.reset_to_bci(start); | 2293 str.reset_to_bci(start); |
2169 Bytecodes::Code code; | 2294 Bytecodes::Code code; |
2170 while ((code = str.next()) != ciBytecodeStream::EOBC() && | 2295 while ((code = str.next()) != ciBytecodeStream::EOBC() && |
2171 str.cur_bci() < limit) { | 2296 str.cur_bci() < limit) { |
2172 // Check for exceptional control flow from this point. | 2297 // Check for exceptional control flow from this point. |
2173 if (has_exceptions && can_trap(str)) { | 2298 if (has_exceptions && can_trap(str)) { |
2174 flow_exceptions(exceptions, exc_klasses, state); | 2299 flow_exceptions(exceptions, exc_klasses, state); |
2300 exceptions_used = true; | |
2175 } | 2301 } |
2176 // Apply the effects of the current bytecode to our state. | 2302 // Apply the effects of the current bytecode to our state. |
2177 bool res = state->apply_one_bytecode(&str); | 2303 bool res = state->apply_one_bytecode(&str); |
2178 | 2304 |
2179 // Watch for bailouts. | 2305 // Watch for bailouts. |
2187 if (CITraceTypeFlow) { | 2313 if (CITraceTypeFlow) { |
2188 tty->print_cr(">> Found trap"); | 2314 tty->print_cr(">> Found trap"); |
2189 block->print_on(tty); | 2315 block->print_on(tty); |
2190 } | 2316 } |
2191 | 2317 |
2318 // Save set of locals defined in this block | |
2319 block->def_locals()->add(state->def_locals()); | |
2320 | |
2192 // Record (no) successors. | 2321 // Record (no) successors. |
2193 block->successors(&str, state, jsrs); | 2322 block->successors(&str, state, jsrs); |
2323 | |
2324 assert(!has_exceptions || exceptions_used, "Not removing exceptions"); | |
2194 | 2325 |
2195 // Discontinue interpretation of this Block. | 2326 // Discontinue interpretation of this Block. |
2196 return; | 2327 return; |
2197 } | 2328 } |
2198 } | 2329 } |
2200 GrowableArray<Block*>* successors = NULL; | 2331 GrowableArray<Block*>* successors = NULL; |
2201 if (control != ciBlock::fall_through_bci) { | 2332 if (control != ciBlock::fall_through_bci) { |
2202 // Check for exceptional control flow from this point. | 2333 // Check for exceptional control flow from this point. |
2203 if (has_exceptions && can_trap(str)) { | 2334 if (has_exceptions && can_trap(str)) { |
2204 flow_exceptions(exceptions, exc_klasses, state); | 2335 flow_exceptions(exceptions, exc_klasses, state); |
2336 exceptions_used = true; | |
2205 } | 2337 } |
2206 | 2338 |
2207 // Fix the JsrSet to reflect effect of the bytecode. | 2339 // Fix the JsrSet to reflect effect of the bytecode. |
2208 block->copy_jsrs_into(jsrs); | 2340 block->copy_jsrs_into(jsrs); |
2209 jsrs->apply_control(this, &str, state); | 2341 jsrs->apply_control(this, &str, state); |
2216 } else { | 2348 } else { |
2217 // Fall through control | 2349 // Fall through control |
2218 successors = block->successors(&str, NULL, NULL); | 2350 successors = block->successors(&str, NULL, NULL); |
2219 } | 2351 } |
2220 | 2352 |
2353 // Save set of locals defined in this block | |
2354 block->def_locals()->add(state->def_locals()); | |
2355 | |
2356 // Remove untaken exception paths | |
2357 if (!exceptions_used) | |
2358 exceptions->clear(); | |
2359 | |
2221 // Pass our state to successors. | 2360 // Pass our state to successors. |
2222 flow_successors(successors, state); | 2361 flow_successors(successors, state); |
2362 } | |
2363 | |
2364 // ------------------------------------------------------------------ | |
2365 // ciTypeFlow::PostOrderLoops::next | |
2366 // | |
2367 // Advance to next loop tree using a postorder, left-to-right traversal. | |
2368 void ciTypeFlow::PostorderLoops::next() { | |
2369 assert(!done(), "must not be done."); | |
2370 if (_current->sibling() != NULL) { | |
2371 _current = _current->sibling(); | |
2372 while (_current->child() != NULL) { | |
2373 _current = _current->child(); | |
2374 } | |
2375 } else { | |
2376 _current = _current->parent(); | |
2377 } | |
2378 } | |
2379 | |
2380 // ------------------------------------------------------------------ | |
2381 // ciTypeFlow::PreOrderLoops::next | |
2382 // | |
2383 // Advance to next loop tree using a preorder, left-to-right traversal. | |
2384 void ciTypeFlow::PreorderLoops::next() { | |
2385 assert(!done(), "must not be done."); | |
2386 if (_current->child() != NULL) { | |
2387 _current = _current->child(); | |
2388 } else if (_current->sibling() != NULL) { | |
2389 _current = _current->sibling(); | |
2390 } else { | |
2391 while (_current != _root && _current->sibling() == NULL) { | |
2392 _current = _current->parent(); | |
2393 } | |
2394 if (_current == _root) { | |
2395 _current = NULL; | |
2396 assert(done(), "must be done."); | |
2397 } else { | |
2398 assert(_current->sibling() != NULL, "must be more to do"); | |
2399 _current = _current->sibling(); | |
2400 } | |
2401 } | |
2402 } | |
2403 | |
2404 // ------------------------------------------------------------------ | |
2405 // ciTypeFlow::Loop::sorted_merge | |
2406 // | |
2407 // Merge the branch lp into this branch, sorting on the loop head | |
2408 // pre_orders. Returns the leaf of the merged branch. | |
2409 // Child and sibling pointers will be setup later. | |
2410 // Sort is (looking from leaf towards the root) | |
2411 // descending on primary key: loop head's pre_order, and | |
2412 // ascending on secondary key: loop tail's pre_order. | |
2413 ciTypeFlow::Loop* ciTypeFlow::Loop::sorted_merge(Loop* lp) { | |
2414 Loop* leaf = this; | |
2415 Loop* prev = NULL; | |
2416 Loop* current = leaf; | |
2417 while (lp != NULL) { | |
2418 int lp_pre_order = lp->head()->pre_order(); | |
2419 // Find insertion point for "lp" | |
2420 while (current != NULL) { | |
2421 if (current == lp) | |
2422 return leaf; // Already in list | |
2423 if (current->head()->pre_order() < lp_pre_order) | |
2424 break; | |
2425 if (current->head()->pre_order() == lp_pre_order && | |
2426 current->tail()->pre_order() > lp->tail()->pre_order()) { | |
2427 break; | |
2428 } | |
2429 prev = current; | |
2430 current = current->parent(); | |
2431 } | |
2432 Loop* next_lp = lp->parent(); // Save future list of items to insert | |
2433 // Insert lp before current | |
2434 lp->set_parent(current); | |
2435 if (prev != NULL) { | |
2436 prev->set_parent(lp); | |
2437 } else { | |
2438 leaf = lp; | |
2439 } | |
2440 prev = lp; // Inserted item is new prev[ious] | |
2441 lp = next_lp; // Next item to insert | |
2442 } | |
2443 return leaf; | |
2444 } | |
2445 | |
2446 // ------------------------------------------------------------------ | |
2447 // ciTypeFlow::build_loop_tree | |
2448 // | |
2449 // Incrementally build loop tree. | |
2450 void ciTypeFlow::build_loop_tree(Block* blk) { | |
2451 assert(!blk->is_post_visited(), "precondition"); | |
2452 Loop* innermost = NULL; // merge of loop tree branches over all successors | |
2453 | |
2454 for (SuccIter iter(blk); !iter.done(); iter.next()) { | |
2455 Loop* lp = NULL; | |
2456 Block* succ = iter.succ(); | |
2457 if (!succ->is_post_visited()) { | |
2458 // Found backedge since predecessor post visited, but successor is not | |
2459 assert(succ->pre_order() <= blk->pre_order(), "should be backedge"); | |
2460 | |
2461 // Create a LoopNode to mark this loop. | |
2462 lp = new (arena()) Loop(succ, blk); | |
2463 if (succ->loop() == NULL) | |
2464 succ->set_loop(lp); | |
2465 // succ->loop will be updated to innermost loop on a later call, when blk==succ | |
2466 | |
2467 } else { // Nested loop | |
2468 lp = succ->loop(); | |
2469 | |
2470 // If succ is loop head, find outer loop. | |
2471 while (lp != NULL && lp->head() == succ) { | |
2472 lp = lp->parent(); | |
2473 } | |
2474 if (lp == NULL) { | |
2475 // Infinite loop, it's parent is the root | |
2476 lp = loop_tree_root(); | |
2477 } | |
2478 } | |
2479 | |
2480 // Check for irreducible loop. | |
2481 // Successor has already been visited. If the successor's loop head | |
2482 // has already been post-visited, then this is another entry into the loop. | |
2483 while (lp->head()->is_post_visited() && lp != loop_tree_root()) { | |
2484 _has_irreducible_entry = true; | |
2485 lp->set_irreducible(succ); | |
2486 if (!succ->is_on_work_list()) { | |
2487 // Assume irreducible entries need more data flow | |
2488 add_to_work_list(succ); | |
2489 } | |
2490 lp = lp->parent(); | |
2491 assert(lp != NULL, "nested loop must have parent by now"); | |
2492 } | |
2493 | |
2494 // Merge loop tree branch for all successors. | |
2495 innermost = innermost == NULL ? lp : innermost->sorted_merge(lp); | |
2496 | |
2497 } // end loop | |
2498 | |
2499 if (innermost == NULL) { | |
2500 assert(blk->successors()->length() == 0, "CFG exit"); | |
2501 blk->set_loop(loop_tree_root()); | |
2502 } else if (innermost->head() == blk) { | |
2503 // If loop header, complete the tree pointers | |
2504 if (blk->loop() != innermost) { | |
2505 #if ASSERT | |
2506 assert(blk->loop()->head() == innermost->head(), "same head"); | |
2507 Loop* dl; | |
2508 for (dl = innermost; dl != NULL && dl != blk->loop(); dl = dl->parent()); | |
2509 assert(dl == blk->loop(), "blk->loop() already in innermost list"); | |
2510 #endif | |
2511 blk->set_loop(innermost); | |
2512 } | |
2513 innermost->def_locals()->add(blk->def_locals()); | |
2514 Loop* l = innermost; | |
2515 Loop* p = l->parent(); | |
2516 while (p && l->head() == blk) { | |
2517 l->set_sibling(p->child()); // Put self on parents 'next child' | |
2518 p->set_child(l); // Make self the first child of parent | |
2519 p->def_locals()->add(l->def_locals()); | |
2520 l = p; // Walk up the parent chain | |
2521 p = l->parent(); | |
2522 } | |
2523 } else { | |
2524 blk->set_loop(innermost); | |
2525 innermost->def_locals()->add(blk->def_locals()); | |
2526 } | |
2527 } | |
2528 | |
2529 // ------------------------------------------------------------------ | |
2530 // ciTypeFlow::Loop::contains | |
2531 // | |
2532 // Returns true if lp is nested loop. | |
2533 bool ciTypeFlow::Loop::contains(ciTypeFlow::Loop* lp) const { | |
2534 assert(lp != NULL, ""); | |
2535 if (this == lp || head() == lp->head()) return true; | |
2536 int depth1 = depth(); | |
2537 int depth2 = lp->depth(); | |
2538 if (depth1 > depth2) | |
2539 return false; | |
2540 while (depth1 < depth2) { | |
2541 depth2--; | |
2542 lp = lp->parent(); | |
2543 } | |
2544 return this == lp; | |
2545 } | |
2546 | |
2547 // ------------------------------------------------------------------ | |
2548 // ciTypeFlow::Loop::depth | |
2549 // | |
2550 // Loop depth | |
2551 int ciTypeFlow::Loop::depth() const { | |
2552 int dp = 0; | |
2553 for (Loop* lp = this->parent(); lp != NULL; lp = lp->parent()) | |
2554 dp++; | |
2555 return dp; | |
2556 } | |
2557 | |
2558 #ifndef PRODUCT | |
2559 // ------------------------------------------------------------------ | |
2560 // ciTypeFlow::Loop::print | |
2561 void ciTypeFlow::Loop::print(outputStream* st, int indent) const { | |
2562 for (int i = 0; i < indent; i++) st->print(" "); | |
2563 st->print("%d<-%d %s", | |
2564 is_root() ? 0 : this->head()->pre_order(), | |
2565 is_root() ? 0 : this->tail()->pre_order(), | |
2566 is_irreducible()?" irr":""); | |
2567 st->print(" defs: "); | |
2568 def_locals()->print_on(st, _head->outer()->method()->max_locals()); | |
2569 st->cr(); | |
2570 for (Loop* ch = child(); ch != NULL; ch = ch->sibling()) | |
2571 ch->print(st, indent+2); | |
2572 } | |
2573 #endif | |
2574 | |
2575 // ------------------------------------------------------------------ | |
2576 // ciTypeFlow::df_flow_types | |
2577 // | |
2578 // Perform the depth first type flow analysis. Helper for flow_types. | |
2579 void ciTypeFlow::df_flow_types(Block* start, | |
2580 bool do_flow, | |
2581 StateVector* temp_vector, | |
2582 JsrSet* temp_set) { | |
2583 int dft_len = 100; | |
2584 GrowableArray<Block*> stk(arena(), dft_len, 0, NULL); | |
2585 | |
2586 ciBlock* dummy = _methodBlocks->make_dummy_block(); | |
2587 JsrSet* root_set = new JsrSet(NULL, 0); | |
2588 Block* root_head = new (arena()) Block(this, dummy, root_set); | |
2589 Block* root_tail = new (arena()) Block(this, dummy, root_set); | |
2590 root_head->set_pre_order(0); | |
2591 root_head->set_post_order(0); | |
2592 root_tail->set_pre_order(max_jint); | |
2593 root_tail->set_post_order(max_jint); | |
2594 set_loop_tree_root(new (arena()) Loop(root_head, root_tail)); | |
2595 | |
2596 stk.push(start); | |
2597 | |
2598 _next_pre_order = 0; // initialize pre_order counter | |
2599 _rpo_list = NULL; | |
2600 int next_po = 0; // initialize post_order counter | |
2601 | |
2602 // Compute RPO and the control flow graph | |
2603 int size; | |
2604 while ((size = stk.length()) > 0) { | |
2605 Block* blk = stk.top(); // Leave node on stack | |
2606 if (!blk->is_visited()) { | |
2607 // forward arc in graph | |
2608 assert (!blk->has_pre_order(), ""); | |
2609 blk->set_next_pre_order(); | |
2610 | |
2611 if (_next_pre_order >= MaxNodeLimit / 2) { | |
2612 // Too many basic blocks. Bail out. | |
2613 // This can happen when try/finally constructs are nested to depth N, | |
2614 // and there is O(2**N) cloning of jsr bodies. See bug 4697245! | |
2615 // "MaxNodeLimit / 2" is used because probably the parser will | |
2616 // generate at least twice that many nodes and bail out. | |
2617 record_failure("too many basic blocks"); | |
2618 return; | |
2619 } | |
2620 if (do_flow) { | |
2621 flow_block(blk, temp_vector, temp_set); | |
2622 if (failing()) return; // Watch for bailouts. | |
2623 } | |
2624 } else if (!blk->is_post_visited()) { | |
2625 // cross or back arc | |
2626 for (SuccIter iter(blk); !iter.done(); iter.next()) { | |
2627 Block* succ = iter.succ(); | |
2628 if (!succ->is_visited()) { | |
2629 stk.push(succ); | |
2630 } | |
2631 } | |
2632 if (stk.length() == size) { | |
2633 // There were no additional children, post visit node now | |
2634 stk.pop(); // Remove node from stack | |
2635 | |
2636 build_loop_tree(blk); | |
2637 blk->set_post_order(next_po++); // Assign post order | |
2638 prepend_to_rpo_list(blk); | |
2639 assert(blk->is_post_visited(), ""); | |
2640 | |
2641 if (blk->is_loop_head() && !blk->is_on_work_list()) { | |
2642 // Assume loop heads need more data flow | |
2643 add_to_work_list(blk); | |
2644 } | |
2645 } | |
2646 } else { | |
2647 stk.pop(); // Remove post-visited node from stack | |
2648 } | |
2649 } | |
2223 } | 2650 } |
2224 | 2651 |
2225 // ------------------------------------------------------------------ | 2652 // ------------------------------------------------------------------ |
2226 // ciTypeFlow::flow_types | 2653 // ciTypeFlow::flow_types |
2227 // | 2654 // |
2231 ResourceMark rm; | 2658 ResourceMark rm; |
2232 StateVector* temp_vector = new StateVector(this); | 2659 StateVector* temp_vector = new StateVector(this); |
2233 JsrSet* temp_set = new JsrSet(NULL, 16); | 2660 JsrSet* temp_set = new JsrSet(NULL, 16); |
2234 | 2661 |
2235 // Create the method entry block. | 2662 // Create the method entry block. |
2236 Block* block = block_at(start_bci(), temp_set); | 2663 Block* start = block_at(start_bci(), temp_set); |
2237 block->set_pre_order(_next_pre_order++); | |
2238 assert(block->is_start(), "start block must have order #0"); | |
2239 | 2664 |
2240 // Load the initial state into it. | 2665 // Load the initial state into it. |
2241 const StateVector* start_state = get_start_state(); | 2666 const StateVector* start_state = get_start_state(); |
2242 if (failing()) return; | 2667 if (failing()) return; |
2243 block->meet(start_state); | 2668 start->meet(start_state); |
2244 add_to_work_list(block); | 2669 |
2245 | 2670 // Depth first visit |
2246 // Trickle away. | 2671 df_flow_types(start, true /*do flow*/, temp_vector, temp_set); |
2672 | |
2673 if (failing()) return; | |
2674 assert(_rpo_list == start, "must be start"); | |
2675 | |
2676 // Any loops found? | |
2677 if (loop_tree_root()->child() != NULL && | |
2678 env()->comp_level() >= CompLevel_full_optimization) { | |
2679 // Loop optimizations are not performed on Tier1 compiles. | |
2680 | |
2681 bool changed = clone_loop_heads(loop_tree_root(), temp_vector, temp_set); | |
2682 | |
2683 // If some loop heads were cloned, recompute postorder and loop tree | |
2684 if (changed) { | |
2685 loop_tree_root()->set_child(NULL); | |
2686 for (Block* blk = _rpo_list; blk != NULL;) { | |
2687 Block* next = blk->rpo_next(); | |
2688 blk->df_init(); | |
2689 blk = next; | |
2690 } | |
2691 df_flow_types(start, false /*no flow*/, temp_vector, temp_set); | |
2692 } | |
2693 } | |
2694 | |
2695 if (CITraceTypeFlow) { | |
2696 tty->print_cr("\nLoop tree"); | |
2697 loop_tree_root()->print(); | |
2698 } | |
2699 | |
2700 // Continue flow analysis until fixed point reached | |
2701 | |
2702 debug_only(int max_block = _next_pre_order;) | |
2703 | |
2247 while (!work_list_empty()) { | 2704 while (!work_list_empty()) { |
2248 Block* block = work_list_next(); | 2705 Block* blk = work_list_next(); |
2249 flow_block(block, temp_vector, temp_set); | 2706 assert (blk->has_post_order(), "post order assigned above"); |
2250 | 2707 |
2251 | 2708 flow_block(blk, temp_vector, temp_set); |
2252 // NodeCountCutoff is the number of nodes at which the parser | 2709 |
2253 // will bail out. Probably if we already have lots of BBs, | 2710 assert (max_block == _next_pre_order, "no new blocks"); |
2254 // the parser will generate at least twice that many nodes and bail out. | 2711 assert (!failing(), "no more bailouts"); |
2255 // Therefore, this is a conservatively large limit at which to | |
2256 // bail out in the pre-parse typeflow pass. | |
2257 int block_limit = MaxNodeLimit / 2; | |
2258 | |
2259 if (_next_pre_order >= block_limit) { | |
2260 // Too many basic blocks. Bail out. | |
2261 // | |
2262 // This can happen when try/finally constructs are nested to depth N, | |
2263 // and there is O(2**N) cloning of jsr bodies. See bug 4697245! | |
2264 record_failure("too many basic blocks"); | |
2265 return; | |
2266 } | |
2267 | |
2268 // Watch for bailouts. | |
2269 if (failing()) return; | |
2270 } | 2712 } |
2271 } | 2713 } |
2272 | 2714 |
2273 // ------------------------------------------------------------------ | 2715 // ------------------------------------------------------------------ |
2274 // ciTypeFlow::map_blocks | 2716 // ciTypeFlow::map_blocks |
2275 // | 2717 // |
2276 // Create the block map, which indexes blocks in pre_order. | 2718 // Create the block map, which indexes blocks in reverse post-order. |
2277 void ciTypeFlow::map_blocks() { | 2719 void ciTypeFlow::map_blocks() { |
2278 assert(_block_map == NULL, "single initialization"); | 2720 assert(_block_map == NULL, "single initialization"); |
2279 int pre_order_limit = _next_pre_order; | 2721 int block_ct = _next_pre_order; |
2280 _block_map = NEW_ARENA_ARRAY(arena(), Block*, pre_order_limit); | 2722 _block_map = NEW_ARENA_ARRAY(arena(), Block*, block_ct); |
2281 assert(pre_order_limit == block_count(), ""); | 2723 assert(block_ct == block_count(), ""); |
2282 int po; | 2724 |
2283 for (po = 0; po < pre_order_limit; po++) { | 2725 Block* blk = _rpo_list; |
2284 debug_only(_block_map[po] = NULL); | 2726 for (int m = 0; m < block_ct; m++) { |
2285 } | 2727 int rpo = blk->rpo(); |
2286 ciMethodBlocks *mblks = _methodBlocks; | 2728 assert(rpo == m, "should be sequential"); |
2287 ciBlock* current = NULL; | 2729 _block_map[rpo] = blk; |
2288 int limit_bci = code_size(); | 2730 blk = blk->rpo_next(); |
2289 for (int bci = 0; bci < limit_bci; bci++) { | 2731 } |
2290 ciBlock* ciblk = mblks->block_containing(bci); | 2732 assert(blk == NULL, "should be done"); |
2291 if (ciblk != NULL && ciblk != current) { | 2733 |
2292 current = ciblk; | 2734 for (int j = 0; j < block_ct; j++) { |
2293 int curidx = ciblk->index(); | 2735 assert(_block_map[j] != NULL, "must not drop any blocks"); |
2294 int block_count = (_idx_to_blocklist[curidx] == NULL) ? 0 : _idx_to_blocklist[curidx]->length(); | 2736 Block* block = _block_map[j]; |
2295 for (int i = 0; i < block_count; i++) { | |
2296 Block* block = _idx_to_blocklist[curidx]->at(i); | |
2297 if (!block->has_pre_order()) continue; | |
2298 int po = block->pre_order(); | |
2299 assert(_block_map[po] == NULL, "unique ref to block"); | |
2300 assert(0 <= po && po < pre_order_limit, ""); | |
2301 _block_map[po] = block; | |
2302 } | |
2303 } | |
2304 } | |
2305 for (po = 0; po < pre_order_limit; po++) { | |
2306 assert(_block_map[po] != NULL, "must not drop any blocks"); | |
2307 Block* block = _block_map[po]; | |
2308 // Remove dead blocks from successor lists: | 2737 // Remove dead blocks from successor lists: |
2309 for (int e = 0; e <= 1; e++) { | 2738 for (int e = 0; e <= 1; e++) { |
2310 GrowableArray<Block*>* l = e? block->exceptions(): block->successors(); | 2739 GrowableArray<Block*>* l = e? block->exceptions(): block->successors(); |
2311 for (int i = 0; i < l->length(); i++) { | 2740 for (int k = 0; k < l->length(); k++) { |
2312 Block* s = l->at(i); | 2741 Block* s = l->at(k); |
2313 if (!s->has_pre_order()) { | 2742 if (!s->has_post_order()) { |
2314 if (CITraceTypeFlow) { | 2743 if (CITraceTypeFlow) { |
2315 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order()); | 2744 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order()); |
2316 s->print_value_on(tty); | 2745 s->print_value_on(tty); |
2317 tty->cr(); | 2746 tty->cr(); |
2318 } | 2747 } |
2319 l->remove(s); | 2748 l->remove(s); |
2320 --i; | 2749 --k; |
2321 } | 2750 } |
2322 } | 2751 } |
2323 } | 2752 } |
2324 } | 2753 } |
2325 } | 2754 } |
2327 // ------------------------------------------------------------------ | 2756 // ------------------------------------------------------------------ |
2328 // ciTypeFlow::get_block_for | 2757 // ciTypeFlow::get_block_for |
2329 // | 2758 // |
2330 // Find a block with this ciBlock which has a compatible JsrSet. | 2759 // Find a block with this ciBlock which has a compatible JsrSet. |
2331 // If no such block exists, create it, unless the option is no_create. | 2760 // If no such block exists, create it, unless the option is no_create. |
2332 // If the option is create_private_copy, always create a fresh private copy. | 2761 // If the option is create_backedge_copy, always create a fresh backedge copy. |
2333 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) { | 2762 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) { |
2334 Arena* a = arena(); | 2763 Arena* a = arena(); |
2335 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; | 2764 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; |
2336 if (blocks == NULL) { | 2765 if (blocks == NULL) { |
2337 // Query only? | 2766 // Query only? |
2340 // Allocate the growable array. | 2769 // Allocate the growable array. |
2341 blocks = new (a) GrowableArray<Block*>(a, 4, 0, NULL); | 2770 blocks = new (a) GrowableArray<Block*>(a, 4, 0, NULL); |
2342 _idx_to_blocklist[ciBlockIndex] = blocks; | 2771 _idx_to_blocklist[ciBlockIndex] = blocks; |
2343 } | 2772 } |
2344 | 2773 |
2345 if (option != create_private_copy) { | 2774 if (option != create_backedge_copy) { |
2346 int len = blocks->length(); | 2775 int len = blocks->length(); |
2347 for (int i = 0; i < len; i++) { | 2776 for (int i = 0; i < len; i++) { |
2348 Block* block = blocks->at(i); | 2777 Block* block = blocks->at(i); |
2349 if (!block->is_private_copy() && block->is_compatible_with(jsrs)) { | 2778 if (!block->is_backedge_copy() && block->is_compatible_with(jsrs)) { |
2350 return block; | 2779 return block; |
2351 } | 2780 } |
2352 } | 2781 } |
2353 } | 2782 } |
2354 | 2783 |
2355 // Query only? | 2784 // Query only? |
2356 if (option == no_create) return NULL; | 2785 if (option == no_create) return NULL; |
2357 | 2786 |
2358 // We did not find a compatible block. Create one. | 2787 // We did not find a compatible block. Create one. |
2359 Block* new_block = new (a) Block(this, _methodBlocks->block(ciBlockIndex), jsrs); | 2788 Block* new_block = new (a) Block(this, _methodBlocks->block(ciBlockIndex), jsrs); |
2360 if (option == create_private_copy) new_block->set_private_copy(true); | 2789 if (option == create_backedge_copy) new_block->set_backedge_copy(true); |
2361 blocks->append(new_block); | 2790 blocks->append(new_block); |
2362 return new_block; | 2791 return new_block; |
2363 } | 2792 } |
2364 | 2793 |
2365 // ------------------------------------------------------------------ | 2794 // ------------------------------------------------------------------ |
2366 // ciTypeFlow::private_copy_count | 2795 // ciTypeFlow::backedge_copy_count |
2367 // | 2796 // |
2368 int ciTypeFlow::private_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const { | 2797 int ciTypeFlow::backedge_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const { |
2369 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; | 2798 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex]; |
2370 | 2799 |
2371 if (blocks == NULL) { | 2800 if (blocks == NULL) { |
2372 return 0; | 2801 return 0; |
2373 } | 2802 } |
2374 | 2803 |
2375 int count = 0; | 2804 int count = 0; |
2376 int len = blocks->length(); | 2805 int len = blocks->length(); |
2377 for (int i = 0; i < len; i++) { | 2806 for (int i = 0; i < len; i++) { |
2378 Block* block = blocks->at(i); | 2807 Block* block = blocks->at(i); |
2379 if (block->is_private_copy() && block->is_compatible_with(jsrs)) { | 2808 if (block->is_backedge_copy() && block->is_compatible_with(jsrs)) { |
2380 count++; | 2809 count++; |
2381 } | 2810 } |
2382 } | 2811 } |
2383 | 2812 |
2384 return count; | 2813 return count; |
2403 flow_types(); | 2832 flow_types(); |
2404 // Watch for bailouts. | 2833 // Watch for bailouts. |
2405 if (failing()) { | 2834 if (failing()) { |
2406 return; | 2835 return; |
2407 } | 2836 } |
2837 | |
2838 map_blocks(); | |
2839 | |
2408 if (CIPrintTypeFlow || CITraceTypeFlow) { | 2840 if (CIPrintTypeFlow || CITraceTypeFlow) { |
2409 print_on(tty); | 2841 rpo_print_on(tty); |
2410 } | 2842 } |
2411 map_blocks(); | |
2412 } | 2843 } |
2413 | 2844 |
2414 // ------------------------------------------------------------------ | 2845 // ------------------------------------------------------------------ |
2415 // ciTypeFlow::record_failure() | 2846 // ciTypeFlow::record_failure() |
2416 // The ciTypeFlow object keeps track of failure reasons separately from the ciEnv. | 2847 // The ciTypeFlow object keeps track of failure reasons separately from the ciEnv. |
2464 } | 2895 } |
2465 } | 2896 } |
2466 st->print_cr("********************************************************"); | 2897 st->print_cr("********************************************************"); |
2467 st->cr(); | 2898 st->cr(); |
2468 } | 2899 } |
2900 | |
2901 void ciTypeFlow::rpo_print_on(outputStream* st) const { | |
2902 st->print_cr("********************************************************"); | |
2903 st->print ("TypeFlow for "); | |
2904 method()->name()->print_symbol_on(st); | |
2905 int limit_bci = code_size(); | |
2906 st->print_cr(" %d bytes", limit_bci); | |
2907 for (Block* blk = _rpo_list; blk != NULL; blk = blk->rpo_next()) { | |
2908 blk->print_on(st); | |
2909 st->print_cr("--------------------------------------------------------"); | |
2910 st->cr(); | |
2911 } | |
2912 st->print_cr("********************************************************"); | |
2913 st->cr(); | |
2914 } | |
2469 #endif | 2915 #endif |