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 }