1 #ifdef USE_PRAGMA_IDENT_SRC
2 #pragma ident "@(#)ciTypeFlow.cpp 1.47 07/09/28 10:23:20 JVM"
3 #endif
4 /*
5 * Copyright 2000-2007 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
324 }
325 }
326
327
328 // ------------------------------------------------------------------
329 // ciTypeFlow::StateVector::StateVector
330 //
331 // Build a new state vector
332 ciTypeFlow::StateVector::StateVector(ciTypeFlow* analyzer) {
333 _outer = analyzer;
334 _stack_size = -1;
335 _monitor_count = -1;
336 // Allocate the _types array
337 int max_cells = analyzer->max_cells();
338 _types = (ciType**)analyzer->arena()->Amalloc(sizeof(ciType*) * max_cells);
339 for (int i=0; i<max_cells; i++) {
340 _types[i] = top_type();
341 }
342 _trap_bci = -1;
343 _trap_index = 0;
344 }
345
346 // ------------------------------------------------------------------
347 // ciTypeFlow::get_start_state
348 //
349 // Set this vector to the method entry state.
350 const ciTypeFlow::StateVector* ciTypeFlow::get_start_state() {
351 StateVector* state = new StateVector(this);
352 if (is_osr_flow()) {
353 ciTypeFlow* non_osr_flow = method()->get_flow_analysis();
354 if (non_osr_flow->failing()) {
355 record_failure(non_osr_flow->failure_reason());
356 return NULL;
357 }
358 JsrSet* jsrs = new JsrSet(NULL, 16);
359 Block* non_osr_block = non_osr_flow->existing_block_at(start_bci(), jsrs);
360 if (non_osr_block == NULL) {
361 record_failure("cannot reach OSR point");
362 return NULL;
363 }
364 // load up the non-OSR state at this point
365 non_osr_block->copy_state_into(state);
721 // ciTypeFlow::StateVector::do_multianewarray
722 void ciTypeFlow::StateVector::do_multianewarray(ciBytecodeStream* str) {
723 int dimensions = str->get_dimensions();
724 bool will_link;
725 ciArrayKlass* array_klass = str->get_klass(will_link)->as_array_klass();
726 if (!will_link) {
727 trap(str, array_klass, str->get_klass_index());
728 } else {
729 for (int i = 0; i < dimensions; i++) {
730 pop_int();
731 }
732 push_object(array_klass);
733 }
734 }
735
736 // ------------------------------------------------------------------
737 // ciTypeFlow::StateVector::do_new
738 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) {
739 bool will_link;
740 ciKlass* klass = str->get_klass(will_link);
741 if (!will_link) {
742 trap(str, klass, str->get_klass_index());
743 } else {
744 push_object(klass);
745 }
746 }
747
748 // ------------------------------------------------------------------
749 // ciTypeFlow::StateVector::do_newarray
750 void ciTypeFlow::StateVector::do_newarray(ciBytecodeStream* str) {
751 pop_int();
752 ciKlass* klass = ciTypeArrayKlass::make((BasicType)str->get_index());
753 push_object(klass);
754 }
755
756 // ------------------------------------------------------------------
757 // ciTypeFlow::StateVector::do_putfield
758 void ciTypeFlow::StateVector::do_putfield(ciBytecodeStream* str) {
759 do_putstatic(str);
760 if (_trap_bci != -1) return; // unloaded field holder, etc.
761 // could add assert here for type of object.
1254 {
1255 pop_int();
1256 pop_int();
1257 break;
1258 }
1259 case Bytecodes::_ifeq:
1260 case Bytecodes::_ifle:
1261 case Bytecodes::_iflt:
1262 case Bytecodes::_ifge:
1263 case Bytecodes::_ifgt:
1264 case Bytecodes::_ifne:
1265 case Bytecodes::_ireturn:
1266 case Bytecodes::_lookupswitch:
1267 case Bytecodes::_tableswitch:
1268 {
1269 pop_int();
1270 break;
1271 }
1272 case Bytecodes::_iinc:
1273 {
1274 check_int(local(str->get_index()));
1275 break;
1276 }
1277 case Bytecodes::_iload: load_local_int(str->get_index()); break;
1278 case Bytecodes::_iload_0: load_local_int(0); break;
1279 case Bytecodes::_iload_1: load_local_int(1); break;
1280 case Bytecodes::_iload_2: load_local_int(2); break;
1281 case Bytecodes::_iload_3: load_local_int(3); break;
1282
1283 case Bytecodes::_instanceof:
1284 {
1285 // Check for uncommon trap:
1286 do_checkcast(str);
1287 pop_object();
1288 push_int();
1289 break;
1290 }
1291 case Bytecodes::_invokeinterface: do_invoke(str, true); break;
1292 case Bytecodes::_invokespecial: do_invoke(str, true); break;
1293 case Bytecodes::_invokestatic: do_invoke(str, false); break;
1294
1492 int num_locals = _outer->max_locals();
1493 int num_stack = stack_size();
1494 int num_monitors = monitor_count();
1495 st->print_cr(" State : locals %d, stack %d, monitors %d", num_locals, num_stack, num_monitors);
1496 if (num_stack >= 0) {
1497 int i;
1498 for (i = 0; i < num_locals; i++) {
1499 st->print(" local %2d : ", i);
1500 print_cell_on(st, local(i));
1501 st->cr();
1502 }
1503 for (i = 0; i < num_stack; i++) {
1504 st->print(" stack %2d : ", i);
1505 print_cell_on(st, stack(i));
1506 st->cr();
1507 }
1508 }
1509 }
1510 #endif
1511
1512 // ciTypeFlow::Block
1513 //
1514 // A basic block.
1515
1516 // ------------------------------------------------------------------
1517 // ciTypeFlow::Block::Block
1518 ciTypeFlow::Block::Block(ciTypeFlow* outer,
1519 ciBlock *ciblk,
1520 ciTypeFlow::JsrSet* jsrs) {
1521 _ciblock = ciblk;
1522 _exceptions = NULL;
1523 _exc_klasses = NULL;
1524 _successors = NULL;
1525 _state = new (outer->arena()) StateVector(outer);
1526 JsrSet* new_jsrs =
1527 new (outer->arena()) JsrSet(outer->arena(), jsrs->size());
1528 jsrs->copy_into(new_jsrs);
1529 _jsrs = new_jsrs;
1530 _next = NULL;
1531 _on_work_list = false;
1532 _pre_order = -1; assert(!has_pre_order(), "");
1533 _private_copy = false;
1534 _trap_bci = -1;
1535 _trap_index = 0;
1536
1537 if (CITraceTypeFlow) {
1538 tty->print_cr(">> Created new block");
1539 print_on(tty);
1540 }
1541
1542 assert(this->outer() == outer, "outer link set up");
1543 assert(!outer->have_block_count(), "must not have mapped blocks yet");
1544 }
1545
1546 // ------------------------------------------------------------------
1547 // ciTypeFlow::Block::clone_loop_head
1548 //
1549 ciTypeFlow::Block*
1550 ciTypeFlow::Block::clone_loop_head(ciTypeFlow* analyzer,
1551 int branch_bci,
1552 ciTypeFlow::Block* target,
1553 ciTypeFlow::JsrSet* jsrs) {
1554 // Loop optimizations are not performed on Tier1 compiles. Do nothing.
1555 if (analyzer->env()->comp_level() < CompLevel_full_optimization) {
1556 return target;
1557 }
1558
1559 // The current block ends with a branch.
1560 //
1561 // If the target block appears to be the test-clause of a for loop, and
1562 // it is not too large, and it has not yet been cloned, clone it.
1563 // The pre-existing copy becomes the private clone used only by
1564 // the initial iteration of the loop. (We know we are simulating
1565 // the initial iteration right now, since we have never calculated
1566 // successors before for this block.)
1567
1568 if (branch_bci <= start()
1569 && (target->limit() - target->start()) <= CICloneLoopTestLimit
1570 && target->private_copy_count() == 0) {
1571 // Setting the private_copy bit ensures that the target block cannot be
1572 // reached by any other paths, such as fall-in from the loop body.
1573 // The private copy will be accessible only on successor lists
1574 // created up to this point.
1575 target->set_private_copy(true);
1576 if (CITraceTypeFlow) {
1577 tty->print(">> Cloning a test-clause block ");
1578 print_value_on(tty);
1579 tty->cr();
1580 }
1581 // If the target is the current block, then later on a new copy of the
1582 // target block will be created when its bytecodes are reached by
1583 // an alternate path. (This is the case for loops with the loop
1584 // head at the bci-wise bottom of the loop, as with pre-1.4.2 javac.)
1585 //
1586 // Otherwise, duplicate the target block now and use it immediately.
1587 // (The case for loops with the loop head at the bci-wise top of the
1588 // loop, as with 1.4.2 javac.)
1589 //
1590 // In either case, the new copy of the block will remain public.
1591 if (target != this) {
1592 target = analyzer->block_at(branch_bci, jsrs);
1593 }
1594 }
1595 return target;
1596 }
1597
1598 // ------------------------------------------------------------------
1599 // ciTypeFlow::Block::successors
1600 //
1601 // Get the successors for this Block.
1602 GrowableArray<ciTypeFlow::Block*>*
1603 ciTypeFlow::Block::successors(ciBytecodeStream* str,
1604 ciTypeFlow::StateVector* state,
1605 ciTypeFlow::JsrSet* jsrs) {
1606 if (_successors == NULL) {
1607 if (CITraceTypeFlow) {
1608 tty->print(">> Computing successors for block ");
1609 print_value_on(tty);
1610 tty->cr();
1611 }
1612
1613 ciTypeFlow* analyzer = outer();
1614 Arena* arena = analyzer->arena();
1615 Block* block = NULL;
1630 _successors->append(block);
1631 } else {
1632 int current_bci = str->cur_bci();
1633 int next_bci = str->next_bci();
1634 int branch_bci = -1;
1635 Block* target = NULL;
1636 assert(str->next_bci() == limit(), "bad block end");
1637 // This block is not a simple fall-though. Interpret
1638 // the current bytecode to find our successors.
1639 switch (str->cur_bc()) {
1640 case Bytecodes::_ifeq: case Bytecodes::_ifne:
1641 case Bytecodes::_iflt: case Bytecodes::_ifge:
1642 case Bytecodes::_ifgt: case Bytecodes::_ifle:
1643 case Bytecodes::_if_icmpeq: case Bytecodes::_if_icmpne:
1644 case Bytecodes::_if_icmplt: case Bytecodes::_if_icmpge:
1645 case Bytecodes::_if_icmpgt: case Bytecodes::_if_icmple:
1646 case Bytecodes::_if_acmpeq: case Bytecodes::_if_acmpne:
1647 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull:
1648 // Our successors are the branch target and the next bci.
1649 branch_bci = str->get_dest();
1650 clone_loop_head(analyzer, branch_bci, this, jsrs);
1651 _successors =
1652 new (arena) GrowableArray<Block*>(arena, 2, 0, NULL);
1653 assert(_successors->length() == IF_NOT_TAKEN, "");
1654 _successors->append(analyzer->block_at(next_bci, jsrs));
1655 assert(_successors->length() == IF_TAKEN, "");
1656 _successors->append(analyzer->block_at(branch_bci, jsrs));
1657 break;
1658
1659 case Bytecodes::_goto:
1660 branch_bci = str->get_dest();
1661 _successors =
1662 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1663 assert(_successors->length() == GOTO_TARGET, "");
1664 target = analyzer->block_at(branch_bci, jsrs);
1665 // If the target block has not been visited yet, and looks like
1666 // a two-way branch, attempt to clone it if it is a loop head.
1667 if (target->_successors != NULL
1668 && target->_successors->length() == (IF_TAKEN + 1)) {
1669 target = clone_loop_head(analyzer, branch_bci, target, jsrs);
1670 }
1671 _successors->append(target);
1672 break;
1673
1674 case Bytecodes::_jsr:
1675 branch_bci = str->get_dest();
1676 _successors =
1677 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1678 assert(_successors->length() == GOTO_TARGET, "");
1679 _successors->append(analyzer->block_at(branch_bci, jsrs));
1680 break;
1681
1682 case Bytecodes::_goto_w:
1683 case Bytecodes::_jsr_w:
1684 _successors =
1685 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1686 assert(_successors->length() == GOTO_TARGET, "");
1687 _successors->append(analyzer->block_at(str->get_far_dest(), jsrs));
1688 break;
1689
1690 case Bytecodes::_tableswitch: {
1691 Bytecode_tableswitch *tableswitch =
1787
1788 for ( ; !str.is_done(); str.next()) {
1789 ciExceptionHandler* handler = str.handler();
1790 int bci = handler->handler_bci();
1791 ciInstanceKlass* klass = NULL;
1792 if (bci == -1) {
1793 // There is no catch all. It is possible to exit the method.
1794 break;
1795 }
1796 if (handler->is_catch_all()) {
1797 klass = analyzer->env()->Throwable_klass();
1798 } else {
1799 klass = handler->catch_klass();
1800 }
1801 _exceptions->append(analyzer->block_at(bci, _jsrs));
1802 _exc_klasses->append(klass);
1803 }
1804 }
1805
1806 // ------------------------------------------------------------------
1807 // ciTypeFlow::Block::is_simpler_than
1808 //
1809 // A relation used to order our work list. We work on a block earlier
1810 // if it has a smaller jsr stack or it occurs earlier in the program
1811 // text.
1812 //
1813 // Note: maybe we should redo this functionality to make blocks
1814 // which correspond to exceptions lower priority.
1815 bool ciTypeFlow::Block::is_simpler_than(ciTypeFlow::Block* other) {
1816 if (other == NULL) {
1817 return true;
1818 } else {
1819 int size1 = _jsrs->size();
1820 int size2 = other->_jsrs->size();
1821 if (size1 < size2) {
1822 return true;
1823 } else if (size2 < size1) {
1824 return false;
1825 } else {
1826 #if 0
1827 if (size1 > 0) {
1828 int r1 = _jsrs->record_at(0)->return_address();
1829 int r2 = _jsrs->record_at(0)->return_address();
1830 if (r1 < r2) {
1831 return true;
1832 } else if (r2 < r1) {
1833 return false;
1834 } else {
1835 int e1 = _jsrs->record_at(0)->return_address();
1836 int e2 = _jsrs->record_at(0)->return_address();
1837 if (e1 < e2) {
1838 return true;
1839 } else if (e2 < e1) {
1840 return false;
1841 }
1842 }
1843 }
1844 #endif
1845 return (start() <= other->start());
1846 }
1847 }
1848 }
1849
1850 // ------------------------------------------------------------------
1851 // ciTypeFlow::Block::set_private_copy
1852 // Use this only to make a pre-existing public block into a private copy.
1853 void ciTypeFlow::Block::set_private_copy(bool z) {
1854 assert(z || (z == is_private_copy()), "cannot make a private copy public");
1855 _private_copy = z;
1856 }
1857
1858 #ifndef PRODUCT
1859 // ------------------------------------------------------------------
1860 // ciTypeFlow::Block::print_value_on
1861 void ciTypeFlow::Block::print_value_on(outputStream* st) const {
1862 if (has_pre_order()) st->print("#%-2d ", pre_order());
1863 st->print("[%d - %d)", start(), limit());
1864 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); }
1865 if (is_private_copy()) st->print("/private_copy");
1866 }
1867
1868 // ------------------------------------------------------------------
1869 // ciTypeFlow::Block::print_on
1870 void ciTypeFlow::Block::print_on(outputStream* st) const {
1871 if ((Verbose || WizardMode)) {
1872 outer()->method()->print_codes_on(start(), limit(), st);
1873 }
1874 st->print_cr(" ==================================================== ");
1875 st->print (" ");
1876 print_value_on(st);
1877 st->cr();
1878 _state->print_on(st);
1879 if (_successors == NULL) {
1880 st->print_cr(" No successor information");
1881 } else {
1882 int num_successors = _successors->length();
1883 st->print_cr(" Successors : %d", num_successors);
1884 for (int i = 0; i < num_successors; i++) {
1885 Block* successor = _successors->at(i);
1886 st->print(" ");
1887 successor->print_value_on(st);
1888 st->cr();
1889 }
1890 }
1891 if (_exceptions == NULL) {
1892 st->print_cr(" No exception information");
1893 } else {
1894 int num_exceptions = _exceptions->length();
1895 st->print_cr(" Exceptions : %d", num_exceptions);
1896 for (int i = 0; i < num_exceptions; i++) {
1897 Block* exc_succ = _exceptions->at(i);
1898 ciInstanceKlass* exc_klass = _exc_klasses->at(i);
1899 st->print(" ");
1900 exc_succ->print_value_on(st);
1901 st->print(" -- ");
1902 exc_klass->name()->print_symbol_on(st);
1903 st->cr();
1904 }
1905 }
1906 if (has_trap()) {
1907 st->print_cr(" Traps on %d with trap index %d", trap_bci(), trap_index());
1908 }
1909 st->print_cr(" ==================================================== ");
1910 }
1911 #endif
1912
1913 // ciTypeFlow
1914 //
1915 // This is a pass over the bytecodes which computes the following:
1916 // basic block structure
1917 // interpreter type-states (a la the verifier)
1918
1919 // ------------------------------------------------------------------
1920 // ciTypeFlow::ciTypeFlow
1921 ciTypeFlow::ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci) {
1922 _env = env;
1923 _method = method;
1924 _methodBlocks = method->get_method_blocks();
1925 _max_locals = method->max_locals();
1926 _max_stack = method->max_stack();
1927 _code_size = method->code_size();
1928 _osr_bci = osr_bci;
1929 _failure_reason = NULL;
1930 assert(start_bci() >= 0 && start_bci() < code_size() , "correct osr_bci argument");
1931
1932 _work_list = NULL;
1933 _next_pre_order = 0;
1934
1935 _ciblock_count = _methodBlocks->num_blocks();
1936 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, _ciblock_count);
1937 for (int i = 0; i < _ciblock_count; i++) {
1938 _idx_to_blocklist[i] = NULL;
1939 }
1940 _block_map = NULL; // until all blocks are seen
1941 _jsr_count = 0;
1942 _jsr_records = NULL;
1943 }
1944
1945 // ------------------------------------------------------------------
1946 // ciTypeFlow::work_list_next
1947 //
1948 // Get the next basic block from our work list.
1949 ciTypeFlow::Block* ciTypeFlow::work_list_next() {
1950 assert(!work_list_empty(), "work list must not be empty");
1951 Block* next_block = _work_list;
1952 _work_list = next_block->next();
1953 next_block->set_next(NULL);
1954 next_block->set_on_work_list(false);
1955 if (!next_block->has_pre_order()) {
1956 // Assign "pre_order" as each new block is taken from the work list.
1957 // This number may be used by following phases to order block visits.
1958 assert(!have_block_count(), "must not have mapped blocks yet")
1959 next_block->set_pre_order(_next_pre_order++);
1960 }
1961 return next_block;
1962 }
1963
1964 // ------------------------------------------------------------------
1965 // ciTypeFlow::add_to_work_list
1966 //
1967 // Add a basic block to our work list.
1968 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) {
1969 assert(!block->is_on_work_list(), "must not already be on work list");
1970
1971 if (CITraceTypeFlow) {
1972 tty->print(">> Adding block%s ", block->has_pre_order() ? " (again)" : "");
1973 block->print_value_on(tty);
1974 tty->print_cr(" to the work list : ");
1975 }
1976
1977 block->set_on_work_list(true);
1978 if (block->is_simpler_than(_work_list)) {
1979 block->set_next(_work_list);
1980 _work_list = block;
1981 } else {
1982 Block *temp = _work_list;
1983 while (!block->is_simpler_than(temp->next())) {
1984 if (CITraceTypeFlow) {
1985 tty->print(".");
1986 }
1987 temp = temp->next();
1988 }
1989 block->set_next(temp->next());
1990 temp->set_next(block);
1991 }
1992 if (CITraceTypeFlow) {
1993 tty->cr();
1994 }
1995 }
1996
1997 // ------------------------------------------------------------------
1998 // ciTypeFlow::block_at
1999 //
2000 // Return the block beginning at bci which has a JsrSet compatible
2001 // with jsrs.
2002 ciTypeFlow::Block* ciTypeFlow::block_at(int bci, ciTypeFlow::JsrSet* jsrs, CreateOption option) {
2003 // First find the right ciBlock.
2004 if (CITraceTypeFlow) {
2005 tty->print(">> Requesting block for %d/", bci);
2006 jsrs->print_on(tty);
2007 tty->cr();
2008 }
2009
2010 ciBlock* ciblk = _methodBlocks->block_containing(bci);
2011 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries");
2012 Block* block = get_block_for(ciblk->index(), jsrs, option);
2013
2014 assert(block == NULL? (option == no_create): block->is_private_copy() == (option == create_private_copy), "create option consistent with result");
2015
2016 if (CITraceTypeFlow) {
2017 if (block != NULL) {
2018 tty->print(">> Found block ");
2019 block->print_value_on(tty);
2020 tty->cr();
2021 } else {
2022 tty->print_cr(">> No such block.");
2023 }
2024 }
2025
2026 return block;
2027 }
2028
2029 // ------------------------------------------------------------------
2030 // ciTypeFlow::make_jsr_record
2031 //
2032 // Make a JsrRecord for a given (entry, return) pair, if such a record
2033 // does not already exist.
2034 ciTypeFlow::JsrRecord* ciTypeFlow::make_jsr_record(int entry_address,
2058 // ciTypeFlow::flow_exceptions
2059 //
2060 // Merge the current state into all exceptional successors at the
2061 // current point in the code.
2062 void ciTypeFlow::flow_exceptions(GrowableArray<ciTypeFlow::Block*>* exceptions,
2063 GrowableArray<ciInstanceKlass*>* exc_klasses,
2064 ciTypeFlow::StateVector* state) {
2065 int len = exceptions->length();
2066 assert(exc_klasses->length() == len, "must have same length");
2067 for (int i = 0; i < len; i++) {
2068 Block* block = exceptions->at(i);
2069 ciInstanceKlass* exception_klass = exc_klasses->at(i);
2070
2071 if (!exception_klass->is_loaded()) {
2072 // Do not compile any code for unloaded exception types.
2073 // Following compiler passes are responsible for doing this also.
2074 continue;
2075 }
2076
2077 if (block->meet_exception(exception_klass, state)) {
2078 // Block was modified. Add it to the work list.
2079 if (!block->is_on_work_list()) {
2080 add_to_work_list(block);
2081 }
2082 }
2083 }
2084 }
2085
2086 // ------------------------------------------------------------------
2087 // ciTypeFlow::flow_successors
2088 //
2089 // Merge the current state into all successors at the current point
2090 // in the code.
2091 void ciTypeFlow::flow_successors(GrowableArray<ciTypeFlow::Block*>* successors,
2092 ciTypeFlow::StateVector* state) {
2093 int len = successors->length();
2094 for (int i = 0; i < len; i++) {
2095 Block* block = successors->at(i);
2096 if (block->meet(state)) {
2097 // Block was modified. Add it to the work list.
2098 if (!block->is_on_work_list()) {
2099 add_to_work_list(block);
2100 }
2101 }
2102 }
2103 }
2104
2105 // ------------------------------------------------------------------
2106 // ciTypeFlow::can_trap
2107 //
2108 // Tells if a given instruction is able to generate an exception edge.
2109 bool ciTypeFlow::can_trap(ciBytecodeStream& str) {
2110 // Cf. GenerateOopMap::do_exception_edge.
2111 if (!Bytecodes::can_trap(str.cur_bc())) return false;
2112
2113 switch (str.cur_bc()) {
2114 case Bytecodes::_ldc:
2115 case Bytecodes::_ldc_w:
2116 case Bytecodes::_ldc2_w:
2117 case Bytecodes::_aload_0:
2118 // These bytecodes can trap for rewriting. We need to assume that
2119 // they do not throw exceptions to make the monitor analysis work.
2120 return false;
2121
2122 case Bytecodes::_ireturn:
2123 case Bytecodes::_lreturn:
2124 case Bytecodes::_freturn:
2125 case Bytecodes::_dreturn:
2126 case Bytecodes::_areturn:
2127 case Bytecodes::_return:
2128 // We can assume the monitor stack is empty in this analysis.
2129 return false;
2130
2131 case Bytecodes::_monitorexit:
2132 // We can assume monitors are matched in this analysis.
2133 return false;
2134 }
2135
2136 return true;
2137 }
2138
2139
2140 // ------------------------------------------------------------------
2141 // ciTypeFlow::flow_block
2142 //
2143 // Interpret the effects of the bytecodes on the incoming state
2144 // vector of a basic block. Push the changed state to succeeding
2145 // basic blocks.
2146 void ciTypeFlow::flow_block(ciTypeFlow::Block* block,
2147 ciTypeFlow::StateVector* state,
2148 ciTypeFlow::JsrSet* jsrs) {
2149 if (CITraceTypeFlow) {
2150 tty->print("\n>> ANALYZING BLOCK : ");
2151 tty->cr();
2152 block->print_on(tty);
2153 }
2154 assert(block->has_pre_order(), "pre-order is assigned before 1st flow");
2155
2156 int start = block->start();
2157 int limit = block->limit();
2158 int control = block->control();
2159 if (control != ciBlock::fall_through_bci) {
2160 limit = control;
2161 }
2162
2163 // Grab the state from the current block.
2164 block->copy_state_into(state);
2165
2166 GrowableArray<Block*>* exceptions = block->exceptions();
2167 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses();
2168 bool has_exceptions = exceptions->length() > 0;
2169
2170 ciBytecodeStream str(method());
2171 str.reset_to_bci(start);
2172 Bytecodes::Code code;
2173 while ((code = str.next()) != ciBytecodeStream::EOBC() &&
2174 str.cur_bci() < limit) {
2175 // Check for exceptional control flow from this point.
2176 if (has_exceptions && can_trap(str)) {
2177 flow_exceptions(exceptions, exc_klasses, state);
2178 }
2179 // Apply the effects of the current bytecode to our state.
2180 bool res = state->apply_one_bytecode(&str);
2181
2182 // Watch for bailouts.
2183 if (failing()) return;
2184
2185 if (res) {
2186
2187 // We have encountered a trap. Record it in this block.
2188 block->set_trap(state->trap_bci(), state->trap_index());
2189
2190 if (CITraceTypeFlow) {
2191 tty->print_cr(">> Found trap");
2192 block->print_on(tty);
2193 }
2194
2195 // Record (no) successors.
2196 block->successors(&str, state, jsrs);
2197
2198 // Discontinue interpretation of this Block.
2199 return;
2200 }
2201 }
2202
2203 GrowableArray<Block*>* successors = NULL;
2204 if (control != ciBlock::fall_through_bci) {
2205 // Check for exceptional control flow from this point.
2206 if (has_exceptions && can_trap(str)) {
2207 flow_exceptions(exceptions, exc_klasses, state);
2208 }
2209
2210 // Fix the JsrSet to reflect effect of the bytecode.
2211 block->copy_jsrs_into(jsrs);
2212 jsrs->apply_control(this, &str, state);
2213
2214 // Find successor edges based on old state and new JsrSet.
2215 successors = block->successors(&str, state, jsrs);
2216
2217 // Apply the control changes to the state.
2218 state->apply_one_bytecode(&str);
2219 } else {
2220 // Fall through control
2221 successors = block->successors(&str, NULL, NULL);
2222 }
2223
2224 // Pass our state to successors.
2225 flow_successors(successors, state);
2226 }
2227
2228 // ------------------------------------------------------------------
2229 // ciTypeFlow::flow_types
2230 //
2231 // Perform the type flow analysis, creating and cloning Blocks as
2232 // necessary.
2233 void ciTypeFlow::flow_types() {
2234 ResourceMark rm;
2235 StateVector* temp_vector = new StateVector(this);
2236 JsrSet* temp_set = new JsrSet(NULL, 16);
2237
2238 // Create the method entry block.
2239 Block* block = block_at(start_bci(), temp_set);
2240 block->set_pre_order(_next_pre_order++);
2241 assert(block->is_start(), "start block must have order #0");
2242
2243 // Load the initial state into it.
2244 const StateVector* start_state = get_start_state();
2245 if (failing()) return;
2246 block->meet(start_state);
2247 add_to_work_list(block);
2248
2249 // Trickle away.
2250 while (!work_list_empty()) {
2251 Block* block = work_list_next();
2252 flow_block(block, temp_vector, temp_set);
2253
2254
2255 // NodeCountCutoff is the number of nodes at which the parser
2256 // will bail out. Probably if we already have lots of BBs,
2257 // the parser will generate at least twice that many nodes and bail out.
2258 // Therefore, this is a conservatively large limit at which to
2259 // bail out in the pre-parse typeflow pass.
2260 int block_limit = MaxNodeLimit / 2;
2261
2262 if (_next_pre_order >= block_limit) {
2263 // Too many basic blocks. Bail out.
2264 //
2265 // This can happen when try/finally constructs are nested to depth N,
2266 // and there is O(2**N) cloning of jsr bodies. See bug 4697245!
2267 record_failure("too many basic blocks");
2268 return;
2269 }
2270
2271 // Watch for bailouts.
2272 if (failing()) return;
2273 }
2274 }
2275
2276 // ------------------------------------------------------------------
2277 // ciTypeFlow::map_blocks
2278 //
2279 // Create the block map, which indexes blocks in pre_order.
2280 void ciTypeFlow::map_blocks() {
2281 assert(_block_map == NULL, "single initialization");
2282 int pre_order_limit = _next_pre_order;
2283 _block_map = NEW_ARENA_ARRAY(arena(), Block*, pre_order_limit);
2284 assert(pre_order_limit == block_count(), "");
2285 int po;
2286 for (po = 0; po < pre_order_limit; po++) {
2287 debug_only(_block_map[po] = NULL);
2288 }
2289 ciMethodBlocks *mblks = _methodBlocks;
2290 ciBlock* current = NULL;
2291 int limit_bci = code_size();
2292 for (int bci = 0; bci < limit_bci; bci++) {
2293 ciBlock* ciblk = mblks->block_containing(bci);
2294 if (ciblk != NULL && ciblk != current) {
2295 current = ciblk;
2296 int curidx = ciblk->index();
2297 int block_count = (_idx_to_blocklist[curidx] == NULL) ? 0 : _idx_to_blocklist[curidx]->length();
2298 for (int i = 0; i < block_count; i++) {
2299 Block* block = _idx_to_blocklist[curidx]->at(i);
2300 if (!block->has_pre_order()) continue;
2301 int po = block->pre_order();
2302 assert(_block_map[po] == NULL, "unique ref to block");
2303 assert(0 <= po && po < pre_order_limit, "");
2304 _block_map[po] = block;
2305 }
2306 }
2307 }
2308 for (po = 0; po < pre_order_limit; po++) {
2309 assert(_block_map[po] != NULL, "must not drop any blocks");
2310 Block* block = _block_map[po];
2311 // Remove dead blocks from successor lists:
2312 for (int e = 0; e <= 1; e++) {
2313 GrowableArray<Block*>* l = e? block->exceptions(): block->successors();
2314 for (int i = 0; i < l->length(); i++) {
2315 Block* s = l->at(i);
2316 if (!s->has_pre_order()) {
2317 if (CITraceTypeFlow) {
2318 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order());
2319 s->print_value_on(tty);
2320 tty->cr();
2321 }
2322 l->remove(s);
2323 --i;
2324 }
2325 }
2326 }
2327 }
2328 }
2329
2330 // ------------------------------------------------------------------
2331 // ciTypeFlow::get_block_for
2332 //
2333 // Find a block with this ciBlock which has a compatible JsrSet.
2334 // If no such block exists, create it, unless the option is no_create.
2335 // If the option is create_private_copy, always create a fresh private copy.
2336 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) {
2337 Arena* a = arena();
2338 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
2339 if (blocks == NULL) {
2340 // Query only?
2341 if (option == no_create) return NULL;
2342
2343 // Allocate the growable array.
2344 blocks = new (a) GrowableArray<Block*>(a, 4, 0, NULL);
2345 _idx_to_blocklist[ciBlockIndex] = blocks;
2346 }
2347
2348 if (option != create_private_copy) {
2349 int len = blocks->length();
2350 for (int i = 0; i < len; i++) {
2351 Block* block = blocks->at(i);
2352 if (!block->is_private_copy() && block->is_compatible_with(jsrs)) {
2353 return block;
2354 }
2355 }
2356 }
2357
2358 // Query only?
2359 if (option == no_create) return NULL;
2360
2361 // We did not find a compatible block. Create one.
2362 Block* new_block = new (a) Block(this, _methodBlocks->block(ciBlockIndex), jsrs);
2363 if (option == create_private_copy) new_block->set_private_copy(true);
2364 blocks->append(new_block);
2365 return new_block;
2366 }
2367
2368 // ------------------------------------------------------------------
2369 // ciTypeFlow::private_copy_count
2370 //
2371 int ciTypeFlow::private_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const {
2372 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
2373
2374 if (blocks == NULL) {
2375 return 0;
2376 }
2377
2378 int count = 0;
2379 int len = blocks->length();
2380 for (int i = 0; i < len; i++) {
2381 Block* block = blocks->at(i);
2382 if (block->is_private_copy() && block->is_compatible_with(jsrs)) {
2383 count++;
2384 }
2385 }
2386
2387 return count;
2388 }
2389
2390 // ------------------------------------------------------------------
2391 // ciTypeFlow::do_flow
2392 //
2393 // Perform type inference flow analysis.
2394 void ciTypeFlow::do_flow() {
2395 if (CITraceTypeFlow) {
2396 tty->print_cr("\nPerforming flow analysis on method");
2397 method()->print();
2398 if (is_osr_flow()) tty->print(" at OSR bci %d", start_bci());
2399 tty->cr();
2400 method()->print_codes();
2401 }
2402 if (CITraceTypeFlow) {
2403 tty->print_cr("Initial CI Blocks");
2404 print_on(tty);
2405 }
2406 flow_types();
2407 // Watch for bailouts.
2408 if (failing()) {
2409 return;
2410 }
2411 if (CIPrintTypeFlow || CITraceTypeFlow) {
2412 print_on(tty);
2413 }
2414 map_blocks();
2415 }
2416
2417 // ------------------------------------------------------------------
2418 // ciTypeFlow::record_failure()
2419 // The ciTypeFlow object keeps track of failure reasons separately from the ciEnv.
2420 // This is required because there is not a 1-1 relation between the ciEnv and
2421 // the TypeFlow passes within a compilation task. For example, if the compiler
2422 // is considering inlining a method, it will request a TypeFlow. If that fails,
2423 // the compilation as a whole may continue without the inlining. Some TypeFlow
2424 // requests are not optional; if they fail the requestor is responsible for
2425 // copying the failure reason up to the ciEnv. (See Parse::Parse.)
2426 void ciTypeFlow::record_failure(const char* reason) {
2427 if (env()->log() != NULL) {
2428 env()->log()->elem("failure reason='%s' phase='typeflow'", reason);
2429 }
2430 if (_failure_reason == NULL) {
2431 // Record the first failure reason.
2432 _failure_reason = reason;
2433 }
2434 }
2452 current->print_on(st);
2453
2454 GrowableArray<Block*>* blocks = _idx_to_blocklist[blk->index()];
2455 int num_blocks = (blocks == NULL) ? 0 : blocks->length();
2456
2457 if (num_blocks == 0) {
2458 st->print_cr(" No Blocks");
2459 } else {
2460 for (int i = 0; i < num_blocks; i++) {
2461 Block* block = blocks->at(i);
2462 block->print_on(st);
2463 }
2464 }
2465 st->print_cr("--------------------------------------------------------");
2466 st->cr();
2467 }
2468 }
2469 st->print_cr("********************************************************");
2470 st->cr();
2471 }
2472 #endif
|
1 #ifdef USE_PRAGMA_IDENT_SRC
2 #pragma ident "@(#)ciTypeFlow.cpp 1.47 07/09/28 10:23:20 JVM"
3 #endif
4 /*
5 * Copyright 2000-2008 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
324 }
325 }
326
327
328 // ------------------------------------------------------------------
329 // ciTypeFlow::StateVector::StateVector
330 //
331 // Build a new state vector
332 ciTypeFlow::StateVector::StateVector(ciTypeFlow* analyzer) {
333 _outer = analyzer;
334 _stack_size = -1;
335 _monitor_count = -1;
336 // Allocate the _types array
337 int max_cells = analyzer->max_cells();
338 _types = (ciType**)analyzer->arena()->Amalloc(sizeof(ciType*) * max_cells);
339 for (int i=0; i<max_cells; i++) {
340 _types[i] = top_type();
341 }
342 _trap_bci = -1;
343 _trap_index = 0;
344 _def_locals.clear();
345 }
346
347
348 // ------------------------------------------------------------------
349 // ciTypeFlow::get_start_state
350 //
351 // Set this vector to the method entry state.
352 const ciTypeFlow::StateVector* ciTypeFlow::get_start_state() {
353 StateVector* state = new StateVector(this);
354 if (is_osr_flow()) {
355 ciTypeFlow* non_osr_flow = method()->get_flow_analysis();
356 if (non_osr_flow->failing()) {
357 record_failure(non_osr_flow->failure_reason());
358 return NULL;
359 }
360 JsrSet* jsrs = new JsrSet(NULL, 16);
361 Block* non_osr_block = non_osr_flow->existing_block_at(start_bci(), jsrs);
362 if (non_osr_block == NULL) {
363 record_failure("cannot reach OSR point");
364 return NULL;
365 }
366 // load up the non-OSR state at this point
367 non_osr_block->copy_state_into(state);
723 // ciTypeFlow::StateVector::do_multianewarray
724 void ciTypeFlow::StateVector::do_multianewarray(ciBytecodeStream* str) {
725 int dimensions = str->get_dimensions();
726 bool will_link;
727 ciArrayKlass* array_klass = str->get_klass(will_link)->as_array_klass();
728 if (!will_link) {
729 trap(str, array_klass, str->get_klass_index());
730 } else {
731 for (int i = 0; i < dimensions; i++) {
732 pop_int();
733 }
734 push_object(array_klass);
735 }
736 }
737
738 // ------------------------------------------------------------------
739 // ciTypeFlow::StateVector::do_new
740 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) {
741 bool will_link;
742 ciKlass* klass = str->get_klass(will_link);
743 if (!will_link || str->is_unresolved_klass()) {
744 trap(str, klass, str->get_klass_index());
745 } else {
746 push_object(klass);
747 }
748 }
749
750 // ------------------------------------------------------------------
751 // ciTypeFlow::StateVector::do_newarray
752 void ciTypeFlow::StateVector::do_newarray(ciBytecodeStream* str) {
753 pop_int();
754 ciKlass* klass = ciTypeArrayKlass::make((BasicType)str->get_index());
755 push_object(klass);
756 }
757
758 // ------------------------------------------------------------------
759 // ciTypeFlow::StateVector::do_putfield
760 void ciTypeFlow::StateVector::do_putfield(ciBytecodeStream* str) {
761 do_putstatic(str);
762 if (_trap_bci != -1) return; // unloaded field holder, etc.
763 // could add assert here for type of object.
1256 {
1257 pop_int();
1258 pop_int();
1259 break;
1260 }
1261 case Bytecodes::_ifeq:
1262 case Bytecodes::_ifle:
1263 case Bytecodes::_iflt:
1264 case Bytecodes::_ifge:
1265 case Bytecodes::_ifgt:
1266 case Bytecodes::_ifne:
1267 case Bytecodes::_ireturn:
1268 case Bytecodes::_lookupswitch:
1269 case Bytecodes::_tableswitch:
1270 {
1271 pop_int();
1272 break;
1273 }
1274 case Bytecodes::_iinc:
1275 {
1276 int lnum = str->get_index();
1277 check_int(local(lnum));
1278 store_to_local(lnum);
1279 break;
1280 }
1281 case Bytecodes::_iload: load_local_int(str->get_index()); break;
1282 case Bytecodes::_iload_0: load_local_int(0); break;
1283 case Bytecodes::_iload_1: load_local_int(1); break;
1284 case Bytecodes::_iload_2: load_local_int(2); break;
1285 case Bytecodes::_iload_3: load_local_int(3); break;
1286
1287 case Bytecodes::_instanceof:
1288 {
1289 // Check for uncommon trap:
1290 do_checkcast(str);
1291 pop_object();
1292 push_int();
1293 break;
1294 }
1295 case Bytecodes::_invokeinterface: do_invoke(str, true); break;
1296 case Bytecodes::_invokespecial: do_invoke(str, true); break;
1297 case Bytecodes::_invokestatic: do_invoke(str, false); break;
1298
1496 int num_locals = _outer->max_locals();
1497 int num_stack = stack_size();
1498 int num_monitors = monitor_count();
1499 st->print_cr(" State : locals %d, stack %d, monitors %d", num_locals, num_stack, num_monitors);
1500 if (num_stack >= 0) {
1501 int i;
1502 for (i = 0; i < num_locals; i++) {
1503 st->print(" local %2d : ", i);
1504 print_cell_on(st, local(i));
1505 st->cr();
1506 }
1507 for (i = 0; i < num_stack; i++) {
1508 st->print(" stack %2d : ", i);
1509 print_cell_on(st, stack(i));
1510 st->cr();
1511 }
1512 }
1513 }
1514 #endif
1515
1516
1517 // ------------------------------------------------------------------
1518 // ciTypeFlow::SuccIter::next
1519 //
1520 void ciTypeFlow::SuccIter::next() {
1521 int succ_ct = _pred->successors()->length();
1522 int next = _index + 1;
1523 if (next < succ_ct) {
1524 _index = next;
1525 _succ = _pred->successors()->at(next);
1526 return;
1527 }
1528 for (int i = next - succ_ct; i < _pred->exceptions()->length(); i++) {
1529 // Do not compile any code for unloaded exception types.
1530 // Following compiler passes are responsible for doing this also.
1531 ciInstanceKlass* exception_klass = _pred->exc_klasses()->at(i);
1532 if (exception_klass->is_loaded()) {
1533 _index = next;
1534 _succ = _pred->exceptions()->at(i);
1535 return;
1536 }
1537 next++;
1538 }
1539 _index = -1;
1540 _succ = NULL;
1541 }
1542
1543 // ------------------------------------------------------------------
1544 // ciTypeFlow::SuccIter::set_succ
1545 //
1546 void ciTypeFlow::SuccIter::set_succ(Block* succ) {
1547 int succ_ct = _pred->successors()->length();
1548 if (_index < succ_ct) {
1549 _pred->successors()->at_put(_index, succ);
1550 } else {
1551 int idx = _index - succ_ct;
1552 _pred->exceptions()->at_put(idx, succ);
1553 }
1554 }
1555
1556 // ciTypeFlow::Block
1557 //
1558 // A basic block.
1559
1560 // ------------------------------------------------------------------
1561 // ciTypeFlow::Block::Block
1562 ciTypeFlow::Block::Block(ciTypeFlow* outer,
1563 ciBlock *ciblk,
1564 ciTypeFlow::JsrSet* jsrs) {
1565 _ciblock = ciblk;
1566 _exceptions = NULL;
1567 _exc_klasses = NULL;
1568 _successors = NULL;
1569 _state = new (outer->arena()) StateVector(outer);
1570 JsrSet* new_jsrs =
1571 new (outer->arena()) JsrSet(outer->arena(), jsrs->size());
1572 jsrs->copy_into(new_jsrs);
1573 _jsrs = new_jsrs;
1574 _next = NULL;
1575 _on_work_list = false;
1576 _backedge_copy = false;
1577 _exception_entry = false;
1578 _trap_bci = -1;
1579 _trap_index = 0;
1580 df_init();
1581
1582 if (CITraceTypeFlow) {
1583 tty->print_cr(">> Created new block");
1584 print_on(tty);
1585 }
1586
1587 assert(this->outer() == outer, "outer link set up");
1588 assert(!outer->have_block_count(), "must not have mapped blocks yet");
1589 }
1590
1591 // ------------------------------------------------------------------
1592 // ciTypeFlow::Block::df_init
1593 void ciTypeFlow::Block::df_init() {
1594 _pre_order = -1; assert(!has_pre_order(), "");
1595 _post_order = -1; assert(!has_post_order(), "");
1596 _loop = NULL;
1597 _irreducible_entry = false;
1598 _rpo_next = NULL;
1599 }
1600
1601 // ------------------------------------------------------------------
1602 // ciTypeFlow::Block::successors
1603 //
1604 // Get the successors for this Block.
1605 GrowableArray<ciTypeFlow::Block*>*
1606 ciTypeFlow::Block::successors(ciBytecodeStream* str,
1607 ciTypeFlow::StateVector* state,
1608 ciTypeFlow::JsrSet* jsrs) {
1609 if (_successors == NULL) {
1610 if (CITraceTypeFlow) {
1611 tty->print(">> Computing successors for block ");
1612 print_value_on(tty);
1613 tty->cr();
1614 }
1615
1616 ciTypeFlow* analyzer = outer();
1617 Arena* arena = analyzer->arena();
1618 Block* block = NULL;
1633 _successors->append(block);
1634 } else {
1635 int current_bci = str->cur_bci();
1636 int next_bci = str->next_bci();
1637 int branch_bci = -1;
1638 Block* target = NULL;
1639 assert(str->next_bci() == limit(), "bad block end");
1640 // This block is not a simple fall-though. Interpret
1641 // the current bytecode to find our successors.
1642 switch (str->cur_bc()) {
1643 case Bytecodes::_ifeq: case Bytecodes::_ifne:
1644 case Bytecodes::_iflt: case Bytecodes::_ifge:
1645 case Bytecodes::_ifgt: case Bytecodes::_ifle:
1646 case Bytecodes::_if_icmpeq: case Bytecodes::_if_icmpne:
1647 case Bytecodes::_if_icmplt: case Bytecodes::_if_icmpge:
1648 case Bytecodes::_if_icmpgt: case Bytecodes::_if_icmple:
1649 case Bytecodes::_if_acmpeq: case Bytecodes::_if_acmpne:
1650 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull:
1651 // Our successors are the branch target and the next bci.
1652 branch_bci = str->get_dest();
1653 _successors =
1654 new (arena) GrowableArray<Block*>(arena, 2, 0, NULL);
1655 assert(_successors->length() == IF_NOT_TAKEN, "");
1656 _successors->append(analyzer->block_at(next_bci, jsrs));
1657 assert(_successors->length() == IF_TAKEN, "");
1658 _successors->append(analyzer->block_at(branch_bci, jsrs));
1659 break;
1660
1661 case Bytecodes::_goto:
1662 branch_bci = str->get_dest();
1663 _successors =
1664 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1665 assert(_successors->length() == GOTO_TARGET, "");
1666 _successors->append(analyzer->block_at(branch_bci, jsrs));
1667 break;
1668
1669 case Bytecodes::_jsr:
1670 branch_bci = str->get_dest();
1671 _successors =
1672 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1673 assert(_successors->length() == GOTO_TARGET, "");
1674 _successors->append(analyzer->block_at(branch_bci, jsrs));
1675 break;
1676
1677 case Bytecodes::_goto_w:
1678 case Bytecodes::_jsr_w:
1679 _successors =
1680 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1681 assert(_successors->length() == GOTO_TARGET, "");
1682 _successors->append(analyzer->block_at(str->get_far_dest(), jsrs));
1683 break;
1684
1685 case Bytecodes::_tableswitch: {
1686 Bytecode_tableswitch *tableswitch =
1782
1783 for ( ; !str.is_done(); str.next()) {
1784 ciExceptionHandler* handler = str.handler();
1785 int bci = handler->handler_bci();
1786 ciInstanceKlass* klass = NULL;
1787 if (bci == -1) {
1788 // There is no catch all. It is possible to exit the method.
1789 break;
1790 }
1791 if (handler->is_catch_all()) {
1792 klass = analyzer->env()->Throwable_klass();
1793 } else {
1794 klass = handler->catch_klass();
1795 }
1796 _exceptions->append(analyzer->block_at(bci, _jsrs));
1797 _exc_klasses->append(klass);
1798 }
1799 }
1800
1801 // ------------------------------------------------------------------
1802 // ciTypeFlow::Block::set_backedge_copy
1803 // Use this only to make a pre-existing public block into a backedge copy.
1804 void ciTypeFlow::Block::set_backedge_copy(bool z) {
1805 assert(z || (z == is_backedge_copy()), "cannot make a backedge copy public");
1806 _backedge_copy = z;
1807 }
1808
1809 // ------------------------------------------------------------------
1810 // ciTypeFlow::Block::is_clonable_exit
1811 //
1812 // At most 2 normal successors, one of which continues looping,
1813 // and all exceptional successors must exit.
1814 bool ciTypeFlow::Block::is_clonable_exit(ciTypeFlow::Loop* lp) {
1815 int normal_cnt = 0;
1816 int in_loop_cnt = 0;
1817 for (SuccIter iter(this); !iter.done(); iter.next()) {
1818 Block* succ = iter.succ();
1819 if (iter.is_normal_ctrl()) {
1820 if (++normal_cnt > 2) return false;
1821 if (lp->contains(succ->loop())) {
1822 if (++in_loop_cnt > 1) return false;
1823 }
1824 } else {
1825 if (lp->contains(succ->loop())) return false;
1826 }
1827 }
1828 return in_loop_cnt == 1;
1829 }
1830
1831 // ------------------------------------------------------------------
1832 // ciTypeFlow::Block::looping_succ
1833 //
1834 ciTypeFlow::Block* ciTypeFlow::Block::looping_succ(ciTypeFlow::Loop* lp) {
1835 assert(successors()->length() <= 2, "at most 2 normal successors");
1836 for (SuccIter iter(this); !iter.done(); iter.next()) {
1837 Block* succ = iter.succ();
1838 if (lp->contains(succ->loop())) {
1839 return succ;
1840 }
1841 }
1842 return NULL;
1843 }
1844
1845 #ifndef PRODUCT
1846 // ------------------------------------------------------------------
1847 // ciTypeFlow::Block::print_value_on
1848 void ciTypeFlow::Block::print_value_on(outputStream* st) const {
1849 if (has_pre_order()) st->print("#%-2d ", pre_order());
1850 if (has_rpo()) st->print("rpo#%-2d ", rpo());
1851 st->print("[%d - %d)", start(), limit());
1852 if (is_loop_head()) st->print(" lphd");
1853 if (is_irreducible_entry()) st->print(" irred");
1854 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); }
1855 if (is_backedge_copy()) st->print("/backedge_copy");
1856 }
1857
1858 // ------------------------------------------------------------------
1859 // ciTypeFlow::Block::print_on
1860 void ciTypeFlow::Block::print_on(outputStream* st) const {
1861 if ((Verbose || WizardMode)) {
1862 outer()->method()->print_codes_on(start(), limit(), st);
1863 }
1864 st->print_cr(" ==================================================== ");
1865 st->print (" ");
1866 print_value_on(st);
1867 st->print(" Stored locals: "); def_locals()->print_on(st, outer()->method()->max_locals()); tty->cr();
1868 if (loop() && loop()->parent() != NULL) {
1869 st->print(" loops:");
1870 Loop* lp = loop();
1871 do {
1872 st->print(" %d<-%d", lp->head()->pre_order(),lp->tail()->pre_order());
1873 if (lp->is_irreducible()) st->print("(ir)");
1874 lp = lp->parent();
1875 } while (lp->parent() != NULL);
1876 }
1877 st->cr();
1878 _state->print_on(st);
1879 if (_successors == NULL) {
1880 st->print_cr(" No successor information");
1881 } else {
1882 int num_successors = _successors->length();
1883 st->print_cr(" Successors : %d", num_successors);
1884 for (int i = 0; i < num_successors; i++) {
1885 Block* successor = _successors->at(i);
1886 st->print(" ");
1887 successor->print_value_on(st);
1888 st->cr();
1889 }
1890 }
1891 if (_exceptions == NULL) {
1892 st->print_cr(" No exception information");
1893 } else {
1894 int num_exceptions = _exceptions->length();
1895 st->print_cr(" Exceptions : %d", num_exceptions);
1896 for (int i = 0; i < num_exceptions; i++) {
1897 Block* exc_succ = _exceptions->at(i);
1898 ciInstanceKlass* exc_klass = _exc_klasses->at(i);
1899 st->print(" ");
1900 exc_succ->print_value_on(st);
1901 st->print(" -- ");
1902 exc_klass->name()->print_symbol_on(st);
1903 st->cr();
1904 }
1905 }
1906 if (has_trap()) {
1907 st->print_cr(" Traps on %d with trap index %d", trap_bci(), trap_index());
1908 }
1909 st->print_cr(" ==================================================== ");
1910 }
1911 #endif
1912
1913 #ifndef PRODUCT
1914 // ------------------------------------------------------------------
1915 // ciTypeFlow::LocalSet::print_on
1916 void ciTypeFlow::LocalSet::print_on(outputStream* st, int limit) const {
1917 st->print("{");
1918 for (int i = 0; i < max; i++) {
1919 if (test(i)) st->print(" %d", i);
1920 }
1921 if (limit > max) {
1922 st->print(" %d..%d ", max, limit);
1923 }
1924 st->print(" }");
1925 }
1926 #endif
1927
1928 // ciTypeFlow
1929 //
1930 // This is a pass over the bytecodes which computes the following:
1931 // basic block structure
1932 // interpreter type-states (a la the verifier)
1933
1934 // ------------------------------------------------------------------
1935 // ciTypeFlow::ciTypeFlow
1936 ciTypeFlow::ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci) {
1937 _env = env;
1938 _method = method;
1939 _methodBlocks = method->get_method_blocks();
1940 _max_locals = method->max_locals();
1941 _max_stack = method->max_stack();
1942 _code_size = method->code_size();
1943 _has_irreducible_entry = false;
1944 _osr_bci = osr_bci;
1945 _failure_reason = NULL;
1946 assert(start_bci() >= 0 && start_bci() < code_size() , "correct osr_bci argument");
1947 _work_list = NULL;
1948
1949 _ciblock_count = _methodBlocks->num_blocks();
1950 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, _ciblock_count);
1951 for (int i = 0; i < _ciblock_count; i++) {
1952 _idx_to_blocklist[i] = NULL;
1953 }
1954 _block_map = NULL; // until all blocks are seen
1955 _jsr_count = 0;
1956 _jsr_records = NULL;
1957 }
1958
1959 // ------------------------------------------------------------------
1960 // ciTypeFlow::work_list_next
1961 //
1962 // Get the next basic block from our work list.
1963 ciTypeFlow::Block* ciTypeFlow::work_list_next() {
1964 assert(!work_list_empty(), "work list must not be empty");
1965 Block* next_block = _work_list;
1966 _work_list = next_block->next();
1967 next_block->set_next(NULL);
1968 next_block->set_on_work_list(false);
1969 return next_block;
1970 }
1971
1972 // ------------------------------------------------------------------
1973 // ciTypeFlow::add_to_work_list
1974 //
1975 // Add a basic block to our work list.
1976 // List is sorted by decreasing postorder sort (same as increasing RPO)
1977 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) {
1978 assert(!block->is_on_work_list(), "must not already be on work list");
1979
1980 if (CITraceTypeFlow) {
1981 tty->print(">> Adding block ");
1982 block->print_value_on(tty);
1983 tty->print_cr(" to the work list : ");
1984 }
1985
1986 block->set_on_work_list(true);
1987
1988 // decreasing post order sort
1989
1990 Block* prev = NULL;
1991 Block* current = _work_list;
1992 int po = block->post_order();
1993 while (current != NULL) {
1994 if (!current->has_post_order() || po > current->post_order())
1995 break;
1996 prev = current;
1997 current = current->next();
1998 }
1999 if (prev == NULL) {
2000 block->set_next(_work_list);
2001 _work_list = block;
2002 } else {
2003 block->set_next(current);
2004 prev->set_next(block);
2005 }
2006
2007 if (CITraceTypeFlow) {
2008 tty->cr();
2009 }
2010 }
2011
2012 // ------------------------------------------------------------------
2013 // ciTypeFlow::block_at
2014 //
2015 // Return the block beginning at bci which has a JsrSet compatible
2016 // with jsrs.
2017 ciTypeFlow::Block* ciTypeFlow::block_at(int bci, ciTypeFlow::JsrSet* jsrs, CreateOption option) {
2018 // First find the right ciBlock.
2019 if (CITraceTypeFlow) {
2020 tty->print(">> Requesting block for %d/", bci);
2021 jsrs->print_on(tty);
2022 tty->cr();
2023 }
2024
2025 ciBlock* ciblk = _methodBlocks->block_containing(bci);
2026 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries");
2027 Block* block = get_block_for(ciblk->index(), jsrs, option);
2028
2029 assert(block == NULL? (option == no_create): block->is_backedge_copy() == (option == create_backedge_copy), "create option consistent with result");
2030
2031 if (CITraceTypeFlow) {
2032 if (block != NULL) {
2033 tty->print(">> Found block ");
2034 block->print_value_on(tty);
2035 tty->cr();
2036 } else {
2037 tty->print_cr(">> No such block.");
2038 }
2039 }
2040
2041 return block;
2042 }
2043
2044 // ------------------------------------------------------------------
2045 // ciTypeFlow::make_jsr_record
2046 //
2047 // Make a JsrRecord for a given (entry, return) pair, if such a record
2048 // does not already exist.
2049 ciTypeFlow::JsrRecord* ciTypeFlow::make_jsr_record(int entry_address,
2073 // ciTypeFlow::flow_exceptions
2074 //
2075 // Merge the current state into all exceptional successors at the
2076 // current point in the code.
2077 void ciTypeFlow::flow_exceptions(GrowableArray<ciTypeFlow::Block*>* exceptions,
2078 GrowableArray<ciInstanceKlass*>* exc_klasses,
2079 ciTypeFlow::StateVector* state) {
2080 int len = exceptions->length();
2081 assert(exc_klasses->length() == len, "must have same length");
2082 for (int i = 0; i < len; i++) {
2083 Block* block = exceptions->at(i);
2084 ciInstanceKlass* exception_klass = exc_klasses->at(i);
2085
2086 if (!exception_klass->is_loaded()) {
2087 // Do not compile any code for unloaded exception types.
2088 // Following compiler passes are responsible for doing this also.
2089 continue;
2090 }
2091
2092 if (block->meet_exception(exception_klass, state)) {
2093 // Block was modified and has PO. Add it to the work list.
2094 if (block->has_post_order() &&
2095 !block->is_on_work_list()) {
2096 add_to_work_list(block);
2097 }
2098 }
2099 }
2100 }
2101
2102 // ------------------------------------------------------------------
2103 // ciTypeFlow::flow_successors
2104 //
2105 // Merge the current state into all successors at the current point
2106 // in the code.
2107 void ciTypeFlow::flow_successors(GrowableArray<ciTypeFlow::Block*>* successors,
2108 ciTypeFlow::StateVector* state) {
2109 int len = successors->length();
2110 for (int i = 0; i < len; i++) {
2111 Block* block = successors->at(i);
2112 if (block->meet(state)) {
2113 // Block was modified and has PO. Add it to the work list.
2114 if (block->has_post_order() &&
2115 !block->is_on_work_list()) {
2116 add_to_work_list(block);
2117 }
2118 }
2119 }
2120 }
2121
2122 // ------------------------------------------------------------------
2123 // ciTypeFlow::can_trap
2124 //
2125 // Tells if a given instruction is able to generate an exception edge.
2126 bool ciTypeFlow::can_trap(ciBytecodeStream& str) {
2127 // Cf. GenerateOopMap::do_exception_edge.
2128 if (!Bytecodes::can_trap(str.cur_bc())) return false;
2129
2130 switch (str.cur_bc()) {
2131 case Bytecodes::_ldc:
2132 case Bytecodes::_ldc_w:
2133 case Bytecodes::_ldc2_w:
2134 case Bytecodes::_aload_0:
2135 // These bytecodes can trap for rewriting. We need to assume that
2136 // they do not throw exceptions to make the monitor analysis work.
2137 return false;
2138
2139 case Bytecodes::_ireturn:
2140 case Bytecodes::_lreturn:
2141 case Bytecodes::_freturn:
2142 case Bytecodes::_dreturn:
2143 case Bytecodes::_areturn:
2144 case Bytecodes::_return:
2145 // We can assume the monitor stack is empty in this analysis.
2146 return false;
2147
2148 case Bytecodes::_monitorexit:
2149 // We can assume monitors are matched in this analysis.
2150 return false;
2151 }
2152
2153 return true;
2154 }
2155
2156 // ------------------------------------------------------------------
2157 // ciTypeFlow::clone_loop_heads
2158 //
2159 // Clone the loop heads
2160 bool ciTypeFlow::clone_loop_heads(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) {
2161 bool rslt = false;
2162 for (PreorderLoops iter(loop_tree_root()); !iter.done(); iter.next()) {
2163 lp = iter.current();
2164 Block* head = lp->head();
2165 if (lp == loop_tree_root() ||
2166 lp->is_irreducible() ||
2167 !head->is_clonable_exit(lp))
2168 continue;
2169
2170 // check not already cloned
2171 if (head->backedge_copy_count() != 0)
2172 continue;
2173
2174 // check _no_ shared head below us
2175 Loop* ch;
2176 for (ch = lp->child(); ch != NULL && ch->head() != head; ch = ch->sibling());
2177 if (ch != NULL)
2178 continue;
2179
2180 // Clone head
2181 Block* new_head = head->looping_succ(lp);
2182 Block* clone = clone_loop_head(lp, temp_vector, temp_set);
2183 // Update lp's info
2184 clone->set_loop(lp);
2185 lp->set_head(new_head);
2186 lp->set_tail(clone);
2187 // And move original head into outer loop
2188 head->set_loop(lp->parent());
2189
2190 rslt = true;
2191 }
2192 return rslt;
2193 }
2194
2195 // ------------------------------------------------------------------
2196 // ciTypeFlow::clone_loop_head
2197 //
2198 // Clone lp's head and replace tail's successors with clone.
2199 //
2200 // |
2201 // v
2202 // head <-> body
2203 // |
2204 // v
2205 // exit
2206 //
2207 // new_head
2208 //
2209 // |
2210 // v
2211 // head ----------\
2212 // | |
2213 // | v
2214 // | clone <-> body
2215 // | |
2216 // | /--/
2217 // | |
2218 // v v
2219 // exit
2220 //
2221 ciTypeFlow::Block* ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) {
2222 Block* head = lp->head();
2223 Block* tail = lp->tail();
2224 if (CITraceTypeFlow) {
2225 tty->print(">> Requesting clone of loop head "); head->print_value_on(tty);
2226 tty->print(" for predecessor "); tail->print_value_on(tty);
2227 tty->cr();
2228 }
2229 Block* clone = block_at(head->start(), head->jsrs(), create_backedge_copy);
2230 assert(clone->backedge_copy_count() == 1, "one backedge copy for all back edges");
2231
2232 assert(!clone->has_pre_order(), "just created");
2233 clone->set_next_pre_order();
2234
2235 // Insert clone after (orig) tail in reverse post order
2236 clone->set_rpo_next(tail->rpo_next());
2237 tail->set_rpo_next(clone);
2238
2239 // tail->head becomes tail->clone
2240 for (SuccIter iter(tail); !iter.done(); iter.next()) {
2241 if (iter.succ() == head) {
2242 iter.set_succ(clone);
2243 }
2244 }
2245 flow_block(tail, temp_vector, temp_set);
2246 if (head == tail) {
2247 // For self-loops, clone->head becomes clone->clone
2248 flow_block(clone, temp_vector, temp_set);
2249 for (SuccIter iter(clone); !iter.done(); iter.next()) {
2250 if (iter.succ() == head) {
2251 iter.set_succ(clone);
2252 break;
2253 }
2254 }
2255 }
2256 flow_block(clone, temp_vector, temp_set);
2257
2258 return clone;
2259 }
2260
2261 // ------------------------------------------------------------------
2262 // ciTypeFlow::flow_block
2263 //
2264 // Interpret the effects of the bytecodes on the incoming state
2265 // vector of a basic block. Push the changed state to succeeding
2266 // basic blocks.
2267 void ciTypeFlow::flow_block(ciTypeFlow::Block* block,
2268 ciTypeFlow::StateVector* state,
2269 ciTypeFlow::JsrSet* jsrs) {
2270 if (CITraceTypeFlow) {
2271 tty->print("\n>> ANALYZING BLOCK : ");
2272 tty->cr();
2273 block->print_on(tty);
2274 }
2275 assert(block->has_pre_order(), "pre-order is assigned before 1st flow");
2276
2277 int start = block->start();
2278 int limit = block->limit();
2279 int control = block->control();
2280 if (control != ciBlock::fall_through_bci) {
2281 limit = control;
2282 }
2283
2284 // Grab the state from the current block.
2285 block->copy_state_into(state);
2286 state->def_locals()->clear();
2287
2288 GrowableArray<Block*>* exceptions = block->exceptions();
2289 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses();
2290 bool has_exceptions = exceptions->length() > 0;
2291
2292 bool exceptions_used = false;
2293
2294 ciBytecodeStream str(method());
2295 str.reset_to_bci(start);
2296 Bytecodes::Code code;
2297 while ((code = str.next()) != ciBytecodeStream::EOBC() &&
2298 str.cur_bci() < limit) {
2299 // Check for exceptional control flow from this point.
2300 if (has_exceptions && can_trap(str)) {
2301 flow_exceptions(exceptions, exc_klasses, state);
2302 exceptions_used = true;
2303 }
2304 // Apply the effects of the current bytecode to our state.
2305 bool res = state->apply_one_bytecode(&str);
2306
2307 // Watch for bailouts.
2308 if (failing()) return;
2309
2310 if (res) {
2311
2312 // We have encountered a trap. Record it in this block.
2313 block->set_trap(state->trap_bci(), state->trap_index());
2314
2315 if (CITraceTypeFlow) {
2316 tty->print_cr(">> Found trap");
2317 block->print_on(tty);
2318 }
2319
2320 // Save set of locals defined in this block
2321 block->def_locals()->add(state->def_locals());
2322
2323 // Record (no) successors.
2324 block->successors(&str, state, jsrs);
2325
2326 assert(!has_exceptions || exceptions_used, "Not removing exceptions");
2327
2328 // Discontinue interpretation of this Block.
2329 return;
2330 }
2331 }
2332
2333 GrowableArray<Block*>* successors = NULL;
2334 if (control != ciBlock::fall_through_bci) {
2335 // Check for exceptional control flow from this point.
2336 if (has_exceptions && can_trap(str)) {
2337 flow_exceptions(exceptions, exc_klasses, state);
2338 exceptions_used = true;
2339 }
2340
2341 // Fix the JsrSet to reflect effect of the bytecode.
2342 block->copy_jsrs_into(jsrs);
2343 jsrs->apply_control(this, &str, state);
2344
2345 // Find successor edges based on old state and new JsrSet.
2346 successors = block->successors(&str, state, jsrs);
2347
2348 // Apply the control changes to the state.
2349 state->apply_one_bytecode(&str);
2350 } else {
2351 // Fall through control
2352 successors = block->successors(&str, NULL, NULL);
2353 }
2354
2355 // Save set of locals defined in this block
2356 block->def_locals()->add(state->def_locals());
2357
2358 // Remove untaken exception paths
2359 if (!exceptions_used)
2360 exceptions->clear();
2361
2362 // Pass our state to successors.
2363 flow_successors(successors, state);
2364 }
2365
2366 // ------------------------------------------------------------------
2367 // ciTypeFlow::PostOrderLoops::next
2368 //
2369 // Advance to next loop tree using a postorder, left-to-right traversal.
2370 void ciTypeFlow::PostorderLoops::next() {
2371 assert(!done(), "must not be done.");
2372 if (_current->sibling() != NULL) {
2373 _current = _current->sibling();
2374 while (_current->child() != NULL) {
2375 _current = _current->child();
2376 }
2377 } else {
2378 _current = _current->parent();
2379 }
2380 }
2381
2382 // ------------------------------------------------------------------
2383 // ciTypeFlow::PreOrderLoops::next
2384 //
2385 // Advance to next loop tree using a preorder, left-to-right traversal.
2386 void ciTypeFlow::PreorderLoops::next() {
2387 assert(!done(), "must not be done.");
2388 if (_current->child() != NULL) {
2389 _current = _current->child();
2390 } else if (_current->sibling() != NULL) {
2391 _current = _current->sibling();
2392 } else {
2393 while (_current != _root && _current->sibling() == NULL) {
2394 _current = _current->parent();
2395 }
2396 if (_current == _root) {
2397 _current = NULL;
2398 assert(done(), "must be done.");
2399 } else {
2400 assert(_current->sibling() != NULL, "must be more to do");
2401 _current = _current->sibling();
2402 }
2403 }
2404 }
2405
2406 // ------------------------------------------------------------------
2407 // ciTypeFlow::Loop::sorted_merge
2408 //
2409 // Merge the branch lp into this branch, sorting on the loop head
2410 // pre_orders. Returns the leaf of the merged branch.
2411 // Child and sibling pointers will be setup later.
2412 // Sort is (looking from leaf towards the root)
2413 // descending on primary key: loop head's pre_order, and
2414 // ascending on secondary key: loop tail's pre_order.
2415 ciTypeFlow::Loop* ciTypeFlow::Loop::sorted_merge(Loop* lp) {
2416 Loop* leaf = this;
2417 Loop* prev = NULL;
2418 Loop* current = leaf;
2419 while (lp != NULL) {
2420 int lp_pre_order = lp->head()->pre_order();
2421 // Find insertion point for "lp"
2422 while (current != NULL) {
2423 if (current == lp)
2424 return leaf; // Already in list
2425 if (current->head()->pre_order() < lp_pre_order)
2426 break;
2427 if (current->head()->pre_order() == lp_pre_order &&
2428 current->tail()->pre_order() > lp->tail()->pre_order()) {
2429 break;
2430 }
2431 prev = current;
2432 current = current->parent();
2433 }
2434 Loop* next_lp = lp->parent(); // Save future list of items to insert
2435 // Insert lp before current
2436 lp->set_parent(current);
2437 if (prev != NULL) {
2438 prev->set_parent(lp);
2439 } else {
2440 leaf = lp;
2441 }
2442 prev = lp; // Inserted item is new prev[ious]
2443 lp = next_lp; // Next item to insert
2444 }
2445 return leaf;
2446 }
2447
2448 // ------------------------------------------------------------------
2449 // ciTypeFlow::build_loop_tree
2450 //
2451 // Incrementally build loop tree.
2452 void ciTypeFlow::build_loop_tree(Block* blk) {
2453 assert(!blk->is_post_visited(), "precondition");
2454 Loop* innermost = NULL; // merge of loop tree branches over all successors
2455
2456 for (SuccIter iter(blk); !iter.done(); iter.next()) {
2457 Loop* lp = NULL;
2458 Block* succ = iter.succ();
2459 if (!succ->is_post_visited()) {
2460 // Found backedge since predecessor post visited, but successor is not
2461 assert(succ->pre_order() <= blk->pre_order(), "should be backedge");
2462
2463 // Create a LoopNode to mark this loop.
2464 lp = new (arena()) Loop(succ, blk);
2465 if (succ->loop() == NULL)
2466 succ->set_loop(lp);
2467 // succ->loop will be updated to innermost loop on a later call, when blk==succ
2468
2469 } else { // Nested loop
2470 lp = succ->loop();
2471
2472 // If succ is loop head, find outer loop.
2473 while (lp != NULL && lp->head() == succ) {
2474 lp = lp->parent();
2475 }
2476 if (lp == NULL) {
2477 // Infinite loop, it's parent is the root
2478 lp = loop_tree_root();
2479 }
2480 }
2481
2482 // Check for irreducible loop.
2483 // Successor has already been visited. If the successor's loop head
2484 // has already been post-visited, then this is another entry into the loop.
2485 while (lp->head()->is_post_visited() && lp != loop_tree_root()) {
2486 _has_irreducible_entry = true;
2487 lp->set_irreducible(succ);
2488 if (!succ->is_on_work_list()) {
2489 // Assume irreducible entries need more data flow
2490 add_to_work_list(succ);
2491 }
2492 lp = lp->parent();
2493 assert(lp != NULL, "nested loop must have parent by now");
2494 }
2495
2496 // Merge loop tree branch for all successors.
2497 innermost = innermost == NULL ? lp : innermost->sorted_merge(lp);
2498
2499 } // end loop
2500
2501 if (innermost == NULL) {
2502 assert(blk->successors()->length() == 0, "CFG exit");
2503 blk->set_loop(loop_tree_root());
2504 } else if (innermost->head() == blk) {
2505 // If loop header, complete the tree pointers
2506 if (blk->loop() != innermost) {
2507 #if ASSERT
2508 assert(blk->loop()->head() == innermost->head(), "same head");
2509 Loop* dl;
2510 for (dl = innermost; dl != NULL && dl != blk->loop(); dl = dl->parent());
2511 assert(dl == blk->loop(), "blk->loop() already in innermost list");
2512 #endif
2513 blk->set_loop(innermost);
2514 }
2515 innermost->def_locals()->add(blk->def_locals());
2516 Loop* l = innermost;
2517 Loop* p = l->parent();
2518 while (p && l->head() == blk) {
2519 l->set_sibling(p->child()); // Put self on parents 'next child'
2520 p->set_child(l); // Make self the first child of parent
2521 p->def_locals()->add(l->def_locals());
2522 l = p; // Walk up the parent chain
2523 p = l->parent();
2524 }
2525 } else {
2526 blk->set_loop(innermost);
2527 innermost->def_locals()->add(blk->def_locals());
2528 }
2529 }
2530
2531 // ------------------------------------------------------------------
2532 // ciTypeFlow::Loop::contains
2533 //
2534 // Returns true if lp is nested loop.
2535 bool ciTypeFlow::Loop::contains(ciTypeFlow::Loop* lp) const {
2536 assert(lp != NULL, "");
2537 if (this == lp || head() == lp->head()) return true;
2538 int depth1 = depth();
2539 int depth2 = lp->depth();
2540 if (depth1 > depth2)
2541 return false;
2542 while (depth1 < depth2) {
2543 depth2--;
2544 lp = lp->parent();
2545 }
2546 return this == lp;
2547 }
2548
2549 // ------------------------------------------------------------------
2550 // ciTypeFlow::Loop::depth
2551 //
2552 // Loop depth
2553 int ciTypeFlow::Loop::depth() const {
2554 int dp = 0;
2555 for (Loop* lp = this->parent(); lp != NULL; lp = lp->parent())
2556 dp++;
2557 return dp;
2558 }
2559
2560 #ifndef PRODUCT
2561 // ------------------------------------------------------------------
2562 // ciTypeFlow::Loop::print
2563 void ciTypeFlow::Loop::print(outputStream* st, int indent) const {
2564 for (int i = 0; i < indent; i++) st->print(" ");
2565 st->print("%d<-%d %s",
2566 is_root() ? 0 : this->head()->pre_order(),
2567 is_root() ? 0 : this->tail()->pre_order(),
2568 is_irreducible()?" irr":"");
2569 st->print(" defs: ");
2570 def_locals()->print_on(st, _head->outer()->method()->max_locals());
2571 st->cr();
2572 for (Loop* ch = child(); ch != NULL; ch = ch->sibling())
2573 ch->print(st, indent+2);
2574 }
2575 #endif
2576
2577 // ------------------------------------------------------------------
2578 // ciTypeFlow::df_flow_types
2579 //
2580 // Perform the depth first type flow analysis. Helper for flow_types.
2581 void ciTypeFlow::df_flow_types(Block* start,
2582 bool do_flow,
2583 StateVector* temp_vector,
2584 JsrSet* temp_set) {
2585 int dft_len = 100;
2586 GrowableArray<Block*> stk(arena(), dft_len, 0, NULL);
2587
2588 ciBlock* dummy = _methodBlocks->make_dummy_block();
2589 JsrSet* root_set = new JsrSet(NULL, 0);
2590 Block* root_head = new (arena()) Block(this, dummy, root_set);
2591 Block* root_tail = new (arena()) Block(this, dummy, root_set);
2592 root_head->set_pre_order(0);
2593 root_head->set_post_order(0);
2594 root_tail->set_pre_order(max_jint);
2595 root_tail->set_post_order(max_jint);
2596 set_loop_tree_root(new (arena()) Loop(root_head, root_tail));
2597
2598 stk.push(start);
2599
2600 _next_pre_order = 0; // initialize pre_order counter
2601 _rpo_list = NULL;
2602 int next_po = 0; // initialize post_order counter
2603
2604 // Compute RPO and the control flow graph
2605 int size;
2606 while ((size = stk.length()) > 0) {
2607 Block* blk = stk.top(); // Leave node on stack
2608 if (!blk->is_visited()) {
2609 // forward arc in graph
2610 assert (!blk->has_pre_order(), "");
2611 blk->set_next_pre_order();
2612
2613 if (_next_pre_order >= MaxNodeLimit / 2) {
2614 // Too many basic blocks. Bail out.
2615 // This can happen when try/finally constructs are nested to depth N,
2616 // and there is O(2**N) cloning of jsr bodies. See bug 4697245!
2617 // "MaxNodeLimit / 2" is used because probably the parser will
2618 // generate at least twice that many nodes and bail out.
2619 record_failure("too many basic blocks");
2620 return;
2621 }
2622 if (do_flow) {
2623 flow_block(blk, temp_vector, temp_set);
2624 if (failing()) return; // Watch for bailouts.
2625 }
2626 } else if (!blk->is_post_visited()) {
2627 // cross or back arc
2628 for (SuccIter iter(blk); !iter.done(); iter.next()) {
2629 Block* succ = iter.succ();
2630 if (!succ->is_visited()) {
2631 stk.push(succ);
2632 }
2633 }
2634 if (stk.length() == size) {
2635 // There were no additional children, post visit node now
2636 stk.pop(); // Remove node from stack
2637
2638 build_loop_tree(blk);
2639 blk->set_post_order(next_po++); // Assign post order
2640 prepend_to_rpo_list(blk);
2641 assert(blk->is_post_visited(), "");
2642
2643 if (blk->is_loop_head() && !blk->is_on_work_list()) {
2644 // Assume loop heads need more data flow
2645 add_to_work_list(blk);
2646 }
2647 }
2648 } else {
2649 stk.pop(); // Remove post-visited node from stack
2650 }
2651 }
2652 }
2653
2654 // ------------------------------------------------------------------
2655 // ciTypeFlow::flow_types
2656 //
2657 // Perform the type flow analysis, creating and cloning Blocks as
2658 // necessary.
2659 void ciTypeFlow::flow_types() {
2660 ResourceMark rm;
2661 StateVector* temp_vector = new StateVector(this);
2662 JsrSet* temp_set = new JsrSet(NULL, 16);
2663
2664 // Create the method entry block.
2665 Block* start = block_at(start_bci(), temp_set);
2666
2667 // Load the initial state into it.
2668 const StateVector* start_state = get_start_state();
2669 if (failing()) return;
2670 start->meet(start_state);
2671
2672 // Depth first visit
2673 df_flow_types(start, true /*do flow*/, temp_vector, temp_set);
2674
2675 if (failing()) return;
2676 assert(_rpo_list == start, "must be start");
2677
2678 // Any loops found?
2679 if (loop_tree_root()->child() != NULL &&
2680 env()->comp_level() >= CompLevel_full_optimization) {
2681 // Loop optimizations are not performed on Tier1 compiles.
2682
2683 bool changed = clone_loop_heads(loop_tree_root(), temp_vector, temp_set);
2684
2685 // If some loop heads were cloned, recompute postorder and loop tree
2686 if (changed) {
2687 loop_tree_root()->set_child(NULL);
2688 for (Block* blk = _rpo_list; blk != NULL;) {
2689 Block* next = blk->rpo_next();
2690 blk->df_init();
2691 blk = next;
2692 }
2693 df_flow_types(start, false /*no flow*/, temp_vector, temp_set);
2694 }
2695 }
2696
2697 if (CITraceTypeFlow) {
2698 tty->print_cr("\nLoop tree");
2699 loop_tree_root()->print();
2700 }
2701
2702 // Continue flow analysis until fixed point reached
2703
2704 debug_only(int max_block = _next_pre_order;)
2705
2706 while (!work_list_empty()) {
2707 Block* blk = work_list_next();
2708 assert (blk->has_post_order(), "post order assigned above");
2709
2710 flow_block(blk, temp_vector, temp_set);
2711
2712 assert (max_block == _next_pre_order, "no new blocks");
2713 assert (!failing(), "no more bailouts");
2714 }
2715 }
2716
2717 // ------------------------------------------------------------------
2718 // ciTypeFlow::map_blocks
2719 //
2720 // Create the block map, which indexes blocks in reverse post-order.
2721 void ciTypeFlow::map_blocks() {
2722 assert(_block_map == NULL, "single initialization");
2723 int block_ct = _next_pre_order;
2724 _block_map = NEW_ARENA_ARRAY(arena(), Block*, block_ct);
2725 assert(block_ct == block_count(), "");
2726
2727 Block* blk = _rpo_list;
2728 for (int m = 0; m < block_ct; m++) {
2729 int rpo = blk->rpo();
2730 assert(rpo == m, "should be sequential");
2731 _block_map[rpo] = blk;
2732 blk = blk->rpo_next();
2733 }
2734 assert(blk == NULL, "should be done");
2735
2736 for (int j = 0; j < block_ct; j++) {
2737 assert(_block_map[j] != NULL, "must not drop any blocks");
2738 Block* block = _block_map[j];
2739 // Remove dead blocks from successor lists:
2740 for (int e = 0; e <= 1; e++) {
2741 GrowableArray<Block*>* l = e? block->exceptions(): block->successors();
2742 for (int k = 0; k < l->length(); k++) {
2743 Block* s = l->at(k);
2744 if (!s->has_post_order()) {
2745 if (CITraceTypeFlow) {
2746 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order());
2747 s->print_value_on(tty);
2748 tty->cr();
2749 }
2750 l->remove(s);
2751 --k;
2752 }
2753 }
2754 }
2755 }
2756 }
2757
2758 // ------------------------------------------------------------------
2759 // ciTypeFlow::get_block_for
2760 //
2761 // Find a block with this ciBlock which has a compatible JsrSet.
2762 // If no such block exists, create it, unless the option is no_create.
2763 // If the option is create_backedge_copy, always create a fresh backedge copy.
2764 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) {
2765 Arena* a = arena();
2766 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
2767 if (blocks == NULL) {
2768 // Query only?
2769 if (option == no_create) return NULL;
2770
2771 // Allocate the growable array.
2772 blocks = new (a) GrowableArray<Block*>(a, 4, 0, NULL);
2773 _idx_to_blocklist[ciBlockIndex] = blocks;
2774 }
2775
2776 if (option != create_backedge_copy) {
2777 int len = blocks->length();
2778 for (int i = 0; i < len; i++) {
2779 Block* block = blocks->at(i);
2780 if (!block->is_backedge_copy() && block->is_compatible_with(jsrs)) {
2781 return block;
2782 }
2783 }
2784 }
2785
2786 // Query only?
2787 if (option == no_create) return NULL;
2788
2789 // We did not find a compatible block. Create one.
2790 Block* new_block = new (a) Block(this, _methodBlocks->block(ciBlockIndex), jsrs);
2791 if (option == create_backedge_copy) new_block->set_backedge_copy(true);
2792 blocks->append(new_block);
2793 return new_block;
2794 }
2795
2796 // ------------------------------------------------------------------
2797 // ciTypeFlow::backedge_copy_count
2798 //
2799 int ciTypeFlow::backedge_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const {
2800 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
2801
2802 if (blocks == NULL) {
2803 return 0;
2804 }
2805
2806 int count = 0;
2807 int len = blocks->length();
2808 for (int i = 0; i < len; i++) {
2809 Block* block = blocks->at(i);
2810 if (block->is_backedge_copy() && block->is_compatible_with(jsrs)) {
2811 count++;
2812 }
2813 }
2814
2815 return count;
2816 }
2817
2818 // ------------------------------------------------------------------
2819 // ciTypeFlow::do_flow
2820 //
2821 // Perform type inference flow analysis.
2822 void ciTypeFlow::do_flow() {
2823 if (CITraceTypeFlow) {
2824 tty->print_cr("\nPerforming flow analysis on method");
2825 method()->print();
2826 if (is_osr_flow()) tty->print(" at OSR bci %d", start_bci());
2827 tty->cr();
2828 method()->print_codes();
2829 }
2830 if (CITraceTypeFlow) {
2831 tty->print_cr("Initial CI Blocks");
2832 print_on(tty);
2833 }
2834 flow_types();
2835 // Watch for bailouts.
2836 if (failing()) {
2837 return;
2838 }
2839
2840 map_blocks();
2841
2842 if (CIPrintTypeFlow || CITraceTypeFlow) {
2843 rpo_print_on(tty);
2844 }
2845 }
2846
2847 // ------------------------------------------------------------------
2848 // ciTypeFlow::record_failure()
2849 // The ciTypeFlow object keeps track of failure reasons separately from the ciEnv.
2850 // This is required because there is not a 1-1 relation between the ciEnv and
2851 // the TypeFlow passes within a compilation task. For example, if the compiler
2852 // is considering inlining a method, it will request a TypeFlow. If that fails,
2853 // the compilation as a whole may continue without the inlining. Some TypeFlow
2854 // requests are not optional; if they fail the requestor is responsible for
2855 // copying the failure reason up to the ciEnv. (See Parse::Parse.)
2856 void ciTypeFlow::record_failure(const char* reason) {
2857 if (env()->log() != NULL) {
2858 env()->log()->elem("failure reason='%s' phase='typeflow'", reason);
2859 }
2860 if (_failure_reason == NULL) {
2861 // Record the first failure reason.
2862 _failure_reason = reason;
2863 }
2864 }
2882 current->print_on(st);
2883
2884 GrowableArray<Block*>* blocks = _idx_to_blocklist[blk->index()];
2885 int num_blocks = (blocks == NULL) ? 0 : blocks->length();
2886
2887 if (num_blocks == 0) {
2888 st->print_cr(" No Blocks");
2889 } else {
2890 for (int i = 0; i < num_blocks; i++) {
2891 Block* block = blocks->at(i);
2892 block->print_on(st);
2893 }
2894 }
2895 st->print_cr("--------------------------------------------------------");
2896 st->cr();
2897 }
2898 }
2899 st->print_cr("********************************************************");
2900 st->cr();
2901 }
2902
2903 void ciTypeFlow::rpo_print_on(outputStream* st) const {
2904 st->print_cr("********************************************************");
2905 st->print ("TypeFlow for ");
2906 method()->name()->print_symbol_on(st);
2907 int limit_bci = code_size();
2908 st->print_cr(" %d bytes", limit_bci);
2909 for (Block* blk = _rpo_list; blk != NULL; blk = blk->rpo_next()) {
2910 blk->print_on(st);
2911 st->print_cr("--------------------------------------------------------");
2912 st->cr();
2913 }
2914 st->print_cr("********************************************************");
2915 st->cr();
2916 }
2917 #endif
|