Mercurial > hg > truffle
comparison src/share/vm/opto/loopTransform.cpp @ 1172:b2b6a9bf6238
6894779: Loop Predication for Loop Optimizer in C2
Summary: Loop predication implementation
Reviewed-by: never, kvn
author | cfang |
---|---|
date | Tue, 12 Jan 2010 14:37:35 -0800 |
parents | bd02caa94611 |
children | b71f13525cc8 |
comparison
equal
deleted
inserted
replaced
1160:f24201449cac | 1172:b2b6a9bf6238 |
---|---|
547 if( iff->Opcode() == Op_If ) { // Test? | 547 if( iff->Opcode() == Op_If ) { // Test? |
548 | 548 |
549 // Comparing trip+off vs limit | 549 // Comparing trip+off vs limit |
550 Node *bol = iff->in(1); | 550 Node *bol = iff->in(1); |
551 if( bol->req() != 2 ) continue; // dead constant test | 551 if( bol->req() != 2 ) continue; // dead constant test |
552 if (!bol->is_Bool()) { | |
553 assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only"); | |
554 continue; | |
555 } | |
552 Node *cmp = bol->in(1); | 556 Node *cmp = bol->in(1); |
553 | 557 |
554 Node *rc_exp = cmp->in(1); | 558 Node *rc_exp = cmp->in(1); |
555 Node *limit = cmp->in(2); | 559 Node *limit = cmp->in(2); |
556 | 560 |
873 } | 877 } |
874 | 878 |
875 //------------------------------is_invariant----------------------------- | 879 //------------------------------is_invariant----------------------------- |
876 // Return true if n is invariant | 880 // Return true if n is invariant |
877 bool IdealLoopTree::is_invariant(Node* n) const { | 881 bool IdealLoopTree::is_invariant(Node* n) const { |
878 Node *n_c = _phase->get_ctrl(n); | 882 Node *n_c = _phase->has_ctrl(n) ? _phase->get_ctrl(n) : n; |
879 if (n_c->is_top()) return false; | 883 if (n_c->is_top()) return false; |
880 return !is_member(_phase->get_loop(n_c)); | 884 return !is_member(_phase->get_loop(n_c)); |
881 } | 885 } |
882 | 886 |
883 | 887 |
1592 //============================================================================= | 1596 //============================================================================= |
1593 //------------------------------iteration_split_impl--------------------------- | 1597 //------------------------------iteration_split_impl--------------------------- |
1594 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) { | 1598 bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) { |
1595 // Check and remove empty loops (spam micro-benchmarks) | 1599 // Check and remove empty loops (spam micro-benchmarks) |
1596 if( policy_do_remove_empty_loop(phase) ) | 1600 if( policy_do_remove_empty_loop(phase) ) |
1597 return true; // Here we removed an empty loop | 1601 return true; // Here we removed an empty loop |
1598 | 1602 |
1599 bool should_peel = policy_peeling(phase); // Should we peel? | 1603 bool should_peel = policy_peeling(phase); // Should we peel? |
1600 | 1604 |
1601 bool should_unswitch = policy_unswitching(phase); | 1605 bool should_unswitch = policy_unswitching(phase); |
1602 | 1606 |
1686 // Double loop body for unrolling. Adjust the minimum-trip test (will do | 1690 // Double loop body for unrolling. Adjust the minimum-trip test (will do |
1687 // twice as many iterations as before) and the main body limit (only do | 1691 // twice as many iterations as before) and the main body limit (only do |
1688 // an even number of trips). If we are peeling, we might enable some RCE | 1692 // an even number of trips). If we are peeling, we might enable some RCE |
1689 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if | 1693 // and we'd rather unroll the post-RCE'd loop SO... do not unroll if |
1690 // peeling. | 1694 // peeling. |
1691 if( should_unroll && !should_peel ) | 1695 if( should_unroll && !should_peel ) |
1692 phase->do_unroll(this,old_new, true); | 1696 phase->do_unroll(this,old_new, true); |
1693 | 1697 |
1694 // Adjust the pre-loop limits to align the main body | 1698 // Adjust the pre-loop limits to align the main body |
1695 // iterations. | 1699 // iterations. |
1696 if( should_align ) | 1700 if( should_align ) |
1697 Unimplemented(); | 1701 Unimplemented(); |
1729 if( !_child && // If not an inner loop, do not split | 1733 if( !_child && // If not an inner loop, do not split |
1730 !_irreducible && | 1734 !_irreducible && |
1731 _allow_optimizations && | 1735 _allow_optimizations && |
1732 !tail()->is_top() ) { // Also ignore the occasional dead backedge | 1736 !tail()->is_top() ) { // Also ignore the occasional dead backedge |
1733 if (!_has_call) { | 1737 if (!_has_call) { |
1734 if (!iteration_split_impl( phase, old_new )) { | 1738 if (!iteration_split_impl( phase, old_new )) { |
1735 return false; | 1739 return false; |
1736 } | 1740 } |
1737 } else if (policy_unswitching(phase)) { | 1741 } else if (policy_unswitching(phase)) { |
1738 phase->do_unswitching(this, old_new); | 1742 phase->do_unswitching(this, old_new); |
1739 } | 1743 } |
1740 } | 1744 } |
1741 | 1745 |
1744 if( _head->is_CountedLoop() ) phase->reorg_offsets( this ); | 1748 if( _head->is_CountedLoop() ) phase->reorg_offsets( this ); |
1745 if( _next && !_next->iteration_split( phase, old_new )) | 1749 if( _next && !_next->iteration_split( phase, old_new )) |
1746 return false; | 1750 return false; |
1747 return true; | 1751 return true; |
1748 } | 1752 } |
1753 | |
1754 //-------------------------------is_uncommon_trap_proj---------------------------- | |
1755 // Return true if proj is the form of "proj->[region->..]call_uct" | |
1756 bool PhaseIdealLoop::is_uncommon_trap_proj(ProjNode* proj, bool must_reason_predicate) { | |
1757 int path_limit = 10; | |
1758 assert(proj, "invalid argument"); | |
1759 Node* out = proj; | |
1760 for (int ct = 0; ct < path_limit; ct++) { | |
1761 out = out->unique_ctrl_out(); | |
1762 if (out == NULL || out->is_Root() || out->is_Start()) | |
1763 return false; | |
1764 if (out->is_CallStaticJava()) { | |
1765 int req = out->as_CallStaticJava()->uncommon_trap_request(); | |
1766 if (req != 0) { | |
1767 Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(req); | |
1768 if (!must_reason_predicate || reason == Deoptimization::Reason_predicate){ | |
1769 return true; | |
1770 } | |
1771 } | |
1772 return false; // don't do further after call | |
1773 } | |
1774 } | |
1775 return false; | |
1776 } | |
1777 | |
1778 //-------------------------------is_uncommon_trap_if_pattern------------------------- | |
1779 // Return true for "if(test)-> proj -> ... | |
1780 // | | |
1781 // V | |
1782 // other_proj->[region->..]call_uct" | |
1783 // | |
1784 // "must_reason_predicate" means the uct reason must be Reason_predicate | |
1785 bool PhaseIdealLoop::is_uncommon_trap_if_pattern(ProjNode *proj, bool must_reason_predicate) { | |
1786 Node *in0 = proj->in(0); | |
1787 if (!in0->is_If()) return false; | |
1788 IfNode* iff = in0->as_If(); | |
1789 | |
1790 // we need "If(Conv2B(Opaque1(...)))" pattern for must_reason_predicate | |
1791 if (must_reason_predicate) { | |
1792 if (iff->in(1)->Opcode() != Op_Conv2B || | |
1793 iff->in(1)->in(1)->Opcode() != Op_Opaque1) { | |
1794 return false; | |
1795 } | |
1796 } | |
1797 | |
1798 ProjNode* other_proj = iff->proj_out(1-proj->_con)->as_Proj(); | |
1799 return is_uncommon_trap_proj(other_proj, must_reason_predicate); | |
1800 } | |
1801 | |
1802 //------------------------------create_new_if_for_predicate------------------------ | |
1803 // create a new if above the uct_if_pattern for the predicate to be promoted. | |
1804 // | |
1805 // before after | |
1806 // ---------- ---------- | |
1807 // ctrl ctrl | |
1808 // | | | |
1809 // | | | |
1810 // v v | |
1811 // iff new_iff | |
1812 // / \ / \ | |
1813 // / \ / \ | |
1814 // v v v v | |
1815 // uncommon_proj cont_proj if_uct if_cont | |
1816 // \ | | | | | |
1817 // \ | | | | | |
1818 // v v v | v | |
1819 // rgn loop | iff | |
1820 // | | / \ | |
1821 // | | / \ | |
1822 // v | v v | |
1823 // uncommon_trap | uncommon_proj cont_proj | |
1824 // \ \ | | | |
1825 // \ \ | | | |
1826 // v v v v | |
1827 // rgn loop | |
1828 // | | |
1829 // | | |
1830 // v | |
1831 // uncommon_trap | |
1832 // | |
1833 // | |
1834 // We will create a region to guard the uct call if there is no one there. | |
1835 // The true projecttion (if_cont) of the new_iff is returned. | |
1836 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj) { | |
1837 assert(is_uncommon_trap_if_pattern(cont_proj, true), "must be a uct if pattern!"); | |
1838 IfNode* iff = cont_proj->in(0)->as_If(); | |
1839 | |
1840 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); | |
1841 Node *rgn = uncommon_proj->unique_ctrl_out(); | |
1842 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); | |
1843 | |
1844 if (!rgn->is_Region()) { // create a region to guard the call | |
1845 assert(rgn->is_Call(), "must be call uct"); | |
1846 CallNode* call = rgn->as_Call(); | |
1847 rgn = new (C, 1) RegionNode(1); | |
1848 _igvn.set_type(rgn, rgn->bottom_type()); | |
1849 rgn->add_req(uncommon_proj); | |
1850 set_idom(rgn, idom(uncommon_proj), dom_depth(uncommon_proj)+1); | |
1851 _igvn.hash_delete(call); | |
1852 call->set_req(0, rgn); | |
1853 } | |
1854 | |
1855 // Create new_iff | |
1856 uint iffdd = dom_depth(iff); | |
1857 IdealLoopTree* lp = get_loop(iff); | |
1858 IfNode *new_iff = new (C, 2) IfNode(iff->in(0), NULL, iff->_prob, iff->_fcnt); | |
1859 register_node(new_iff, lp, idom(iff), iffdd); | |
1860 Node *if_cont = new (C, 1) IfTrueNode(new_iff); | |
1861 Node *if_uct = new (C, 1) IfFalseNode(new_iff); | |
1862 if (cont_proj->is_IfFalse()) { | |
1863 // Swap | |
1864 Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; | |
1865 } | |
1866 register_node(if_cont, lp, new_iff, iffdd); | |
1867 register_node(if_uct, get_loop(rgn), new_iff, iffdd); | |
1868 | |
1869 // if_cont to iff | |
1870 _igvn.hash_delete(iff); | |
1871 iff->set_req(0, if_cont); | |
1872 set_idom(iff, if_cont, dom_depth(iff)); | |
1873 | |
1874 // if_uct to rgn | |
1875 _igvn.hash_delete(rgn); | |
1876 rgn->add_req(if_uct); | |
1877 Node* ridom = idom(rgn); | |
1878 Node* nrdom = dom_lca(ridom, new_iff); | |
1879 set_idom(rgn, nrdom, dom_depth(rgn)); | |
1880 | |
1881 // rgn must have no phis | |
1882 assert(!rgn->as_Region()->has_phi(), "region must have no phis"); | |
1883 | |
1884 return if_cont->as_Proj(); | |
1885 } | |
1886 | |
1887 //------------------------------find_predicate_insertion_point-------------------------- | |
1888 // Find a good location to insert a predicate | |
1889 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c) { | |
1890 if (start_c == C->root() || !start_c->is_Proj()) | |
1891 return NULL; | |
1892 if (is_uncommon_trap_if_pattern(start_c->as_Proj(), true/*Reason_Predicate*/)) { | |
1893 return start_c->as_Proj(); | |
1894 } | |
1895 return NULL; | |
1896 } | |
1897 | |
1898 //------------------------------Invariance----------------------------------- | |
1899 // Helper class for loop_predication_impl to compute invariance on the fly and | |
1900 // clone invariants. | |
1901 class Invariance : public StackObj { | |
1902 VectorSet _visited, _invariant; | |
1903 Node_Stack _stack; | |
1904 VectorSet _clone_visited; | |
1905 Node_List _old_new; // map of old to new (clone) | |
1906 IdealLoopTree* _lpt; | |
1907 PhaseIdealLoop* _phase; | |
1908 | |
1909 // Helper function to set up the invariance for invariance computation | |
1910 // If n is a known invariant, set up directly. Otherwise, look up the | |
1911 // the possibility to push n onto the stack for further processing. | |
1912 void visit(Node* use, Node* n) { | |
1913 if (_lpt->is_invariant(n)) { // known invariant | |
1914 _invariant.set(n->_idx); | |
1915 } else if (!n->is_CFG()) { | |
1916 Node *n_ctrl = _phase->ctrl_or_self(n); | |
1917 Node *u_ctrl = _phase->ctrl_or_self(use); // self if use is a CFG | |
1918 if (_phase->is_dominator(n_ctrl, u_ctrl)) { | |
1919 _stack.push(n, n->in(0) == NULL ? 1 : 0); | |
1920 } | |
1921 } | |
1922 } | |
1923 | |
1924 // Compute invariance for "the_node" and (possibly) all its inputs recursively | |
1925 // on the fly | |
1926 void compute_invariance(Node* n) { | |
1927 assert(_visited.test(n->_idx), "must be"); | |
1928 visit(n, n); | |
1929 while (_stack.is_nonempty()) { | |
1930 Node* n = _stack.node(); | |
1931 uint idx = _stack.index(); | |
1932 if (idx == n->req()) { // all inputs are processed | |
1933 _stack.pop(); | |
1934 // n is invariant if it's inputs are all invariant | |
1935 bool all_inputs_invariant = true; | |
1936 for (uint i = 0; i < n->req(); i++) { | |
1937 Node* in = n->in(i); | |
1938 if (in == NULL) continue; | |
1939 assert(_visited.test(in->_idx), "must have visited input"); | |
1940 if (!_invariant.test(in->_idx)) { // bad guy | |
1941 all_inputs_invariant = false; | |
1942 break; | |
1943 } | |
1944 } | |
1945 if (all_inputs_invariant) { | |
1946 _invariant.set(n->_idx); // I am a invariant too | |
1947 } | |
1948 } else { // process next input | |
1949 _stack.set_index(idx + 1); | |
1950 Node* m = n->in(idx); | |
1951 if (m != NULL && !_visited.test_set(m->_idx)) { | |
1952 visit(n, m); | |
1953 } | |
1954 } | |
1955 } | |
1956 } | |
1957 | |
1958 // Helper function to set up _old_new map for clone_nodes. | |
1959 // If n is a known invariant, set up directly ("clone" of n == n). | |
1960 // Otherwise, push n onto the stack for real cloning. | |
1961 void clone_visit(Node* n) { | |
1962 assert(_invariant.test(n->_idx), "must be invariant"); | |
1963 if (_lpt->is_invariant(n)) { // known invariant | |
1964 _old_new.map(n->_idx, n); | |
1965 } else{ // to be cloned | |
1966 assert (!n->is_CFG(), "should not see CFG here"); | |
1967 _stack.push(n, n->in(0) == NULL ? 1 : 0); | |
1968 } | |
1969 } | |
1970 | |
1971 // Clone "n" and (possibly) all its inputs recursively | |
1972 void clone_nodes(Node* n, Node* ctrl) { | |
1973 clone_visit(n); | |
1974 while (_stack.is_nonempty()) { | |
1975 Node* n = _stack.node(); | |
1976 uint idx = _stack.index(); | |
1977 if (idx == n->req()) { // all inputs processed, clone n! | |
1978 _stack.pop(); | |
1979 // clone invariant node | |
1980 Node* n_cl = n->clone(); | |
1981 _old_new.map(n->_idx, n_cl); | |
1982 _phase->register_new_node(n_cl, ctrl); | |
1983 for (uint i = 0; i < n->req(); i++) { | |
1984 Node* in = n_cl->in(i); | |
1985 if (in == NULL) continue; | |
1986 n_cl->set_req(i, _old_new[in->_idx]); | |
1987 } | |
1988 } else { // process next input | |
1989 _stack.set_index(idx + 1); | |
1990 Node* m = n->in(idx); | |
1991 if (m != NULL && !_clone_visited.test_set(m->_idx)) { | |
1992 clone_visit(m); // visit the input | |
1993 } | |
1994 } | |
1995 } | |
1996 } | |
1997 | |
1998 public: | |
1999 Invariance(Arena* area, IdealLoopTree* lpt) : | |
2000 _lpt(lpt), _phase(lpt->_phase), | |
2001 _visited(area), _invariant(area), _stack(area, 10 /* guess */), | |
2002 _clone_visited(area), _old_new(area) | |
2003 {} | |
2004 | |
2005 // Map old to n for invariance computation and clone | |
2006 void map_ctrl(Node* old, Node* n) { | |
2007 assert(old->is_CFG() && n->is_CFG(), "must be"); | |
2008 _old_new.map(old->_idx, n); // "clone" of old is n | |
2009 _invariant.set(old->_idx); // old is invariant | |
2010 _clone_visited.set(old->_idx); | |
2011 } | |
2012 | |
2013 // Driver function to compute invariance | |
2014 bool is_invariant(Node* n) { | |
2015 if (!_visited.test_set(n->_idx)) | |
2016 compute_invariance(n); | |
2017 return (_invariant.test(n->_idx) != 0); | |
2018 } | |
2019 | |
2020 // Driver function to clone invariant | |
2021 Node* clone(Node* n, Node* ctrl) { | |
2022 assert(ctrl->is_CFG(), "must be"); | |
2023 assert(_invariant.test(n->_idx), "must be an invariant"); | |
2024 if (!_clone_visited.test(n->_idx)) | |
2025 clone_nodes(n, ctrl); | |
2026 return _old_new[n->_idx]; | |
2027 } | |
2028 }; | |
2029 | |
2030 //------------------------------is_range_check_if ----------------------------------- | |
2031 // Returns true if the predicate of iff is in "scale*iv + offset u< load_range(ptr)" format | |
2032 // Note: this function is particularly designed for loop predication. We require load_range | |
2033 // and offset to be loop invariant computed on the fly by "invar" | |
2034 bool IdealLoopTree::is_range_check_if(IfNode *iff, PhaseIdealLoop *phase, Invariance& invar) const { | |
2035 if (!is_loop_exit(iff)) { | |
2036 return false; | |
2037 } | |
2038 if (!iff->in(1)->is_Bool()) { | |
2039 return false; | |
2040 } | |
2041 const BoolNode *bol = iff->in(1)->as_Bool(); | |
2042 if (bol->_test._test != BoolTest::lt) { | |
2043 return false; | |
2044 } | |
2045 if (!bol->in(1)->is_Cmp()) { | |
2046 return false; | |
2047 } | |
2048 const CmpNode *cmp = bol->in(1)->as_Cmp(); | |
2049 if (cmp->Opcode() != Op_CmpU ) { | |
2050 return false; | |
2051 } | |
2052 if (cmp->in(2)->Opcode() != Op_LoadRange) { | |
2053 return false; | |
2054 } | |
2055 LoadRangeNode* lr = (LoadRangeNode*)cmp->in(2); | |
2056 if (!invar.is_invariant(lr)) { // loadRange must be invariant | |
2057 return false; | |
2058 } | |
2059 Node *iv = _head->as_CountedLoop()->phi(); | |
2060 int scale = 0; | |
2061 Node *offset = NULL; | |
2062 if (!phase->is_scaled_iv_plus_offset(cmp->in(1), iv, &scale, &offset)) { | |
2063 return false; | |
2064 } | |
2065 if(offset && !invar.is_invariant(offset)) { // offset must be invariant | |
2066 return false; | |
2067 } | |
2068 return true; | |
2069 } | |
2070 | |
2071 //------------------------------rc_predicate----------------------------------- | |
2072 // Create a range check predicate | |
2073 // | |
2074 // for (i = init; i < limit; i += stride) { | |
2075 // a[scale*i+offset] | |
2076 // } | |
2077 // | |
2078 // Compute max(scale*i + offset) for init <= i < limit and build the predicate | |
2079 // as "max(scale*i + offset) u< a.length". | |
2080 // | |
2081 // There are two cases for max(scale*i + offset): | |
2082 // (1) stride*scale > 0 | |
2083 // max(scale*i + offset) = scale*(limit-stride) + offset | |
2084 // (2) stride*scale < 0 | |
2085 // max(scale*i + offset) = scale*init + offset | |
2086 BoolNode* PhaseIdealLoop::rc_predicate(Node* ctrl, | |
2087 int scale, Node* offset, | |
2088 Node* init, Node* limit, Node* stride, | |
2089 Node* range) { | |
2090 Node* max_idx_expr = init; | |
2091 int stride_con = stride->get_int(); | |
2092 if ((stride_con > 0) == (scale > 0)) { | |
2093 max_idx_expr = new (C, 3) SubINode(limit, stride); | |
2094 register_new_node(max_idx_expr, ctrl); | |
2095 } | |
2096 | |
2097 if (scale != 1) { | |
2098 ConNode* con_scale = _igvn.intcon(scale); | |
2099 max_idx_expr = new (C, 3) MulINode(max_idx_expr, con_scale); | |
2100 register_new_node(max_idx_expr, ctrl); | |
2101 } | |
2102 | |
2103 if (offset && (!offset->is_Con() || offset->get_int() != 0)){ | |
2104 max_idx_expr = new (C, 3) AddINode(max_idx_expr, offset); | |
2105 register_new_node(max_idx_expr, ctrl); | |
2106 } | |
2107 | |
2108 CmpUNode* cmp = new (C, 3) CmpUNode(max_idx_expr, range); | |
2109 register_new_node(cmp, ctrl); | |
2110 BoolNode* bol = new (C, 2) BoolNode(cmp, BoolTest::lt); | |
2111 register_new_node(bol, ctrl); | |
2112 return bol; | |
2113 } | |
2114 | |
2115 //------------------------------ loop_predication_impl-------------------------- | |
2116 // Insert loop predicates for null checks and range checks | |
2117 bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) { | |
2118 if (!UseLoopPredicate) return false; | |
2119 | |
2120 // Too many traps seen? | |
2121 bool tmt = C->too_many_traps(C->method(), 0, Deoptimization::Reason_predicate); | |
2122 int tc = C->trap_count(Deoptimization::Reason_predicate); | |
2123 if (tmt || tc > 0) { | |
2124 if (TraceLoopPredicate) { | |
2125 tty->print_cr("too many predicate traps: %d", tc); | |
2126 C->method()->print(); // which method has too many predicate traps | |
2127 tty->print_cr(""); | |
2128 } | |
2129 return false; | |
2130 } | |
2131 | |
2132 CountedLoopNode *cl = NULL; | |
2133 if (loop->_head->is_CountedLoop()) { | |
2134 cl = loop->_head->as_CountedLoop(); | |
2135 // do nothing for iteration-splitted loops | |
2136 if(!cl->is_normal_loop()) return false; | |
2137 } | |
2138 | |
2139 LoopNode *lpn = loop->_head->as_Loop(); | |
2140 Node* entry = lpn->in(LoopNode::EntryControl); | |
2141 | |
2142 ProjNode *predicate_proj = find_predicate_insertion_point(entry); | |
2143 if (!predicate_proj){ | |
2144 #ifndef PRODUCT | |
2145 if (TraceLoopPredicate) { | |
2146 tty->print("missing predicate:"); | |
2147 loop->dump_head(); | |
2148 } | |
2149 #endif | |
2150 return false; | |
2151 } | |
2152 | |
2153 ConNode* zero = _igvn.intcon(0); | |
2154 set_ctrl(zero, C->root()); | |
2155 Node *cond_false = new (C, 2) Conv2BNode(zero); | |
2156 register_new_node(cond_false, C->root()); | |
2157 ConNode* one = _igvn.intcon(1); | |
2158 set_ctrl(one, C->root()); | |
2159 Node *cond_true = new (C, 2) Conv2BNode(one); | |
2160 register_new_node(cond_true, C->root()); | |
2161 | |
2162 ResourceArea *area = Thread::current()->resource_area(); | |
2163 Invariance invar(area, loop); | |
2164 | |
2165 // Create list of if-projs such that a newer proj dominates all older | |
2166 // projs in the list, and they all dominate loop->tail() | |
2167 Node_List if_proj_list(area); | |
2168 LoopNode *head = loop->_head->as_Loop(); | |
2169 Node *current_proj = loop->tail(); //start from tail | |
2170 while ( current_proj != head ) { | |
2171 if (loop == get_loop(current_proj) && // still in the loop ? | |
2172 current_proj->is_Proj() && // is a projection ? | |
2173 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ? | |
2174 if_proj_list.push(current_proj); | |
2175 } | |
2176 current_proj = idom(current_proj); | |
2177 } | |
2178 | |
2179 bool hoisted = false; // true if at least one proj is promoted | |
2180 while (if_proj_list.size() > 0) { | |
2181 // Following are changed to nonnull when a predicate can be hoisted | |
2182 ProjNode* new_predicate_proj = NULL; | |
2183 BoolNode* new_predicate_bol = NULL; | |
2184 | |
2185 ProjNode* proj = if_proj_list.pop()->as_Proj(); | |
2186 IfNode* iff = proj->in(0)->as_If(); | |
2187 | |
2188 if (!is_uncommon_trap_if_pattern(proj)) { | |
2189 if (loop->is_loop_exit(iff)) { | |
2190 // stop processing the remaining projs in the list because the execution of them | |
2191 // depends on the condition of "iff" (iff->in(1)). | |
2192 break; | |
2193 } else { | |
2194 // Both arms are inside the loop. There are two cases: | |
2195 // (1) there is one backward branch. In this case, any remaining proj | |
2196 // in the if_proj list post-dominates "iff". So, the condition of "iff" | |
2197 // does not determine the execution the remining projs directly, and we | |
2198 // can safely continue. | |
2199 // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj" | |
2200 // does not dominate loop->tail(), so it can not be in the if_proj list. | |
2201 continue; | |
2202 } | |
2203 } | |
2204 | |
2205 Node* test = iff->in(1); | |
2206 if (!test->is_Bool()){ //Conv2B, ... | |
2207 continue; | |
2208 } | |
2209 BoolNode* bol = test->as_Bool(); | |
2210 if (invar.is_invariant(bol)) { | |
2211 // Invariant test | |
2212 new_predicate_proj = create_new_if_for_predicate(predicate_proj); | |
2213 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0); | |
2214 new_predicate_bol = invar.clone(bol, ctrl)->as_Bool(); | |
2215 if (TraceLoopPredicate) tty->print("invariant"); | |
2216 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) { | |
2217 // Range check (only for counted loops) | |
2218 new_predicate_proj = create_new_if_for_predicate(predicate_proj); | |
2219 Node *ctrl = new_predicate_proj->in(0)->as_If()->in(0); | |
2220 const Node* cmp = bol->in(1)->as_Cmp(); | |
2221 Node* idx = cmp->in(1); | |
2222 assert(!invar.is_invariant(idx), "index is variant"); | |
2223 assert(cmp->in(2)->Opcode() == Op_LoadRange, "must be"); | |
2224 LoadRangeNode* ld_rng = (LoadRangeNode*)cmp->in(2); // LoadRangeNode | |
2225 assert(invar.is_invariant(ld_rng), "load range must be invariant"); | |
2226 ld_rng = (LoadRangeNode*)invar.clone(ld_rng, ctrl); | |
2227 int scale = 1; | |
2228 Node* offset = zero; | |
2229 bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset); | |
2230 assert(ok, "must be index expression"); | |
2231 if (offset && offset != zero) { | |
2232 assert(invar.is_invariant(offset), "offset must be loop invariant"); | |
2233 offset = invar.clone(offset, ctrl); | |
2234 } | |
2235 Node* init = cl->init_trip(); | |
2236 Node* limit = cl->limit(); | |
2237 Node* stride = cl->stride(); | |
2238 new_predicate_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, ld_rng); | |
2239 if (TraceLoopPredicate) tty->print("range check"); | |
2240 } | |
2241 | |
2242 if (new_predicate_proj == NULL) { | |
2243 // The other proj of the "iff" is a uncommon trap projection, and we can assume | |
2244 // the other proj will not be executed ("executed" means uct raised). | |
2245 continue; | |
2246 } else { | |
2247 // Success - attach condition (new_predicate_bol) to predicate if | |
2248 invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate | |
2249 IfNode* new_iff = new_predicate_proj->in(0)->as_If(); | |
2250 | |
2251 // Negate test if necessary | |
2252 if (proj->_con != predicate_proj->_con) { | |
2253 new_predicate_bol = new (C, 2) BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate()); | |
2254 register_new_node(new_predicate_bol, new_iff->in(0)); | |
2255 if (TraceLoopPredicate) tty->print_cr(" if negated: %d", iff->_idx); | |
2256 } else { | |
2257 if (TraceLoopPredicate) tty->print_cr(" if: %d", iff->_idx); | |
2258 } | |
2259 | |
2260 _igvn.hash_delete(new_iff); | |
2261 new_iff->set_req(1, new_predicate_bol); | |
2262 | |
2263 _igvn.hash_delete(iff); | |
2264 iff->set_req(1, proj->is_IfFalse() ? cond_false : cond_true); | |
2265 | |
2266 Node* ctrl = new_predicate_proj; // new control | |
2267 ProjNode* dp = proj; // old control | |
2268 assert(get_loop(dp) == loop, "guarenteed at the time of collecting proj"); | |
2269 // Find nodes (depends only on the test) off the surviving projection; | |
2270 // move them outside the loop with the control of proj_clone | |
2271 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) { | |
2272 Node* cd = dp->fast_out(i); // Control-dependent node | |
2273 if (cd->depends_only_on_test()) { | |
2274 assert(cd->in(0) == dp, ""); | |
2275 _igvn.hash_delete(cd); | |
2276 cd->set_req(0, ctrl); // ctrl, not NULL | |
2277 set_early_ctrl(cd); | |
2278 _igvn._worklist.push(cd); | |
2279 IdealLoopTree *new_loop = get_loop(get_ctrl(cd)); | |
2280 if (new_loop != loop) { | |
2281 if (!loop->_child) loop->_body.yank(cd); | |
2282 if (!new_loop->_child ) new_loop->_body.push(cd); | |
2283 } | |
2284 --i; | |
2285 --imax; | |
2286 } | |
2287 } | |
2288 | |
2289 hoisted = true; | |
2290 C->set_major_progress(); | |
2291 } | |
2292 } // end while | |
2293 | |
2294 #ifndef PRODUCT | |
2295 // report that the loop predication has been actually performed | |
2296 // for this loop | |
2297 if (TraceLoopPredicate && hoisted) { | |
2298 tty->print("Loop Predication Performed:"); | |
2299 loop->dump_head(); | |
2300 } | |
2301 #endif | |
2302 | |
2303 return hoisted; | |
2304 } | |
2305 | |
2306 //------------------------------loop_predication-------------------------------- | |
2307 // driver routine for loop predication optimization | |
2308 bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) { | |
2309 bool hoisted = false; | |
2310 // Recursively promote predicates | |
2311 if ( _child ) { | |
2312 hoisted = _child->loop_predication( phase); | |
2313 } | |
2314 | |
2315 // self | |
2316 if (!_irreducible && !tail()->is_top()) { | |
2317 hoisted |= phase->loop_predication_impl(this); | |
2318 } | |
2319 | |
2320 if ( _next ) { //sibling | |
2321 hoisted |= _next->loop_predication( phase); | |
2322 } | |
2323 | |
2324 return hoisted; | |
2325 } |