Mercurial > hg > truffle

comparison src/share/vm/opto/loopnode.cpp @ 8048:8b3da8d14c93

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7197327: 40% regression on 8 b41 comp 8 b40 on specjvm2008.mpegaudio on oob Summary: Add support for expensive nodes. Reviewed-by: kvn
author roland
date Tue, 12 Feb 2013 12:56:11 +0100
parents 377508648226
children 30f42e691e70
comparison
equal deleted inserted replaced
8047:1e5e28bac299 8048:8b3da8d14c93
86 // Compute earliest legal control 86 // Compute earliest legal control
87 Node *PhaseIdealLoop::get_early_ctrl( Node *n ) { 87 Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {
88 assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" ); 88 assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );
89 uint i; 89 uint i;
90 Node *early; 90 Node *early;
91 if( n->in(0) ) { 91 if (n->in(0) && !n->is_expensive()) {
92 early = n->in(0); 92 early = n->in(0);
93 if( !early->is_CFG() ) // Might be a non-CFG multi-def 93 if (!early->is_CFG()) // Might be a non-CFG multi-def
94 early = get_ctrl(early); // So treat input as a straight data input 94 early = get_ctrl(early); // So treat input as a straight data input
95 i = 1; 95 i = 1;
96 } else { 96 } else {
97 early = get_ctrl(n->in(1)); 97 early = get_ctrl(n->in(1));
98 i = 2; 98 i = 2;
99 } 99 }
100 uint e_d = dom_depth(early); 100 uint e_d = dom_depth(early);
101 assert( early, "" ); 101 assert( early, "" );
102 for( ; i < n->req(); i++ ) { 102 for (; i < n->req(); i++) {
103 Node *cin = get_ctrl(n->in(i)); 103 Node *cin = get_ctrl(n->in(i));
104 assert( cin, "" ); 104 assert( cin, "" );
105 // Keep deepest dominator depth 105 // Keep deepest dominator depth
106 uint c_d = dom_depth(cin); 106 uint c_d = dom_depth(cin);
107 if( c_d > e_d ) { // Deeper guy? 107 if (c_d > e_d) { // Deeper guy?
108 early = cin; // Keep deepest found so far 108 early = cin; // Keep deepest found so far
109 e_d = c_d; 109 e_d = c_d;
110 } else if( c_d == e_d && // Same depth? 110 } else if (c_d == e_d && // Same depth?
111 early != cin ) { // If not equal, must use slower algorithm 111 early != cin) { // If not equal, must use slower algorithm
112 // If same depth but not equal, one _must_ dominate the other 112 // If same depth but not equal, one _must_ dominate the other
113 // and we want the deeper (i.e., dominated) guy. 113 // and we want the deeper (i.e., dominated) guy.
114 Node *n1 = early; 114 Node *n1 = early;
115 Node *n2 = cin; 115 Node *n2 = cin;
116 while( 1 ) { 116 while (1) {
117 n1 = idom(n1); // Walk up until break cycle 117 n1 = idom(n1); // Walk up until break cycle
118 n2 = idom(n2); 118 n2 = idom(n2);
119 if( n1 == cin || // Walked early up to cin 119 if (n1 == cin || // Walked early up to cin
120 dom_depth(n2) < c_d ) 120 dom_depth(n2) < c_d)
121 break; // early is deeper; keep him 121 break; // early is deeper; keep him
122 if( n2 == early || // Walked cin up to early 122 if (n2 == early || // Walked cin up to early
123 dom_depth(n1) < c_d ) { 123 dom_depth(n1) < c_d) {
124 early = cin; // cin is deeper; keep him 124 early = cin; // cin is deeper; keep him
125 break; 125 break;
126 } 126 }
127 } 127 }
128 e_d = dom_depth(early); // Reset depth register cache 128 e_d = dom_depth(early); // Reset depth register cache
130 } 130 }
131 131
132 // Return earliest legal location 132 // Return earliest legal location
133 assert(early == find_non_split_ctrl(early), "unexpected early control"); 133 assert(early == find_non_split_ctrl(early), "unexpected early control");
134 134
135 if (n->is_expensive()) {
136 assert(n->in(0), "should have control input");
137 early = get_early_ctrl_for_expensive(n, early);
138 }
139
135 return early; 140 return early;
136 } 141 }
142
143 //------------------------------get_early_ctrl_for_expensive---------------------------------
144 // Move node up the dominator tree as high as legal while still beneficial
145 Node *PhaseIdealLoop::get_early_ctrl_for_expensive(Node *n, Node* earliest) {
146 assert(n->in(0) && n->is_expensive(), "expensive node with control input here");
147 assert(OptimizeExpensiveOps, "optimization off?");
148
149 Node* ctl = n->in(0);
150 assert(ctl->is_CFG(), "expensive input 0 must be cfg");
151 uint min_dom_depth = dom_depth(earliest);
152 #ifdef ASSERT
153 if (!is_dominator(ctl, earliest) && !is_dominator(earliest, ctl)) {
154 dump_bad_graph("Bad graph detected in get_early_ctrl_for_expensive", n, earliest, ctl);
155 assert(false, "Bad graph detected in get_early_ctrl_for_expensive");
156 }
157 #endif
158 if (dom_depth(ctl) < min_dom_depth) {
159 return earliest;
160 }
161
162 while (1) {
163 Node *next = ctl;
164 // Moving the node out of a loop on the projection of a If
165 // confuses loop predication. So once we hit a Loop in a If branch
166 // that doesn't branch to an UNC, we stop. The code that process
167 // expensive nodes will notice the loop and skip over it to try to
168 // move the node further up.
169 if (ctl->is_CountedLoop() && ctl->in(1) != NULL && ctl->in(1)->in(0) != NULL && ctl->in(1)->in(0)->is_If()) {
170 if (!is_uncommon_trap_if_pattern(ctl->in(1)->as_Proj(), Deoptimization::Reason_none)) {
171 break;
172 }
173 next = idom(ctl->in(1)->in(0));
174 } else if (ctl->is_Proj()) {
175 // We only move it up along a projection if the projection is
176 // the single control projection for its parent: same code path,
177 // if it's a If with UNC or fallthrough of a call.
178 Node* parent_ctl = ctl->in(0);
179 if (parent_ctl == NULL) {
180 break;
181 } else if (parent_ctl->is_CountedLoopEnd() && parent_ctl->as_CountedLoopEnd()->loopnode() != NULL) {
182 next = parent_ctl->as_CountedLoopEnd()->loopnode()->init_control();
183 } else if (parent_ctl->is_If()) {
184 if (!is_uncommon_trap_if_pattern(ctl->as_Proj(), Deoptimization::Reason_none)) {
185 break;
186 }
187 assert(idom(ctl) == parent_ctl, "strange");
188 next = idom(parent_ctl);
189 } else if (ctl->is_CatchProj()) {
190 if (ctl->as_Proj()->_con != CatchProjNode::fall_through_index) {
191 break;
192 }
193 assert(parent_ctl->in(0)->in(0)->is_Call(), "strange graph");
194 next = parent_ctl->in(0)->in(0)->in(0);
195 } else {
196 // Check if parent control has a single projection (this
197 // control is the only possible successor of the parent
198 // control). If so, we can try to move the node above the
199 // parent control.
200 int nb_ctl_proj = 0;
201 for (DUIterator_Fast imax, i = parent_ctl->fast_outs(imax); i < imax; i++) {
202 Node *p = parent_ctl->fast_out(i);
203 if (p->is_Proj() && p->is_CFG()) {
204 nb_ctl_proj++;
205 if (nb_ctl_proj > 1) {
206 break;
207 }
208 }
209 }
210
211 if (nb_ctl_proj > 1) {
212 break;
213 }
214 assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call(), "unexpected node");
215 assert(idom(ctl) == parent_ctl, "strange");
216 next = idom(parent_ctl);
217 }
218 } else {
219 next = idom(ctl);
220 }
221 if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {
222 break;
223 }
224 ctl = next;
225 }
226
227 if (ctl != n->in(0)) {
228 _igvn.hash_delete(n);
229 n->set_req(0, ctl);
230 _igvn.hash_insert(n);
231 }
232
233 return ctl;
234 }
235
137 236
138 //------------------------------set_early_ctrl--------------------------------- 237 //------------------------------set_early_ctrl---------------------------------
139 // Set earliest legal control 238 // Set earliest legal control
140 void PhaseIdealLoop::set_early_ctrl( Node *n ) { 239 void PhaseIdealLoop::set_early_ctrl( Node *n ) {
141 Node *early = get_early_ctrl(n); 240 Node *early = get_early_ctrl(n);
1890 _igvn.replace_node(n, n->in(1)); 1989 _igvn.replace_node(n, n->in(1));
1891 } 1990 }
1892 } 1991 }
1893 } 1992 }
1894 1993
1994 //------------------------process_expensive_nodes-----------------------------
1995 // Expensive nodes have their control input set to prevent the GVN
1996 // from commoning them and as a result forcing the resulting node to
1997 // be in a more frequent path. Use CFG information here, to change the
1998 // control inputs so that some expensive nodes can be commoned while
1999 // not executed more frequently.
2000 bool PhaseIdealLoop::process_expensive_nodes() {
2001 assert(OptimizeExpensiveOps, "optimization off?");
2002
2003 // Sort nodes to bring similar nodes together
2004 C->sort_expensive_nodes();
2005
2006 bool progress = false;
2007
2008 for (int i = 0; i < C->expensive_count(); ) {
2009 Node* n = C->expensive_node(i);
2010 int start = i;
2011 // Find nodes similar to n
2012 i++;
2013 for (; i < C->expensive_count() && Compile::cmp_expensive_nodes(n, C->expensive_node(i)) == 0; i++);
2014 int end = i;
2015 // And compare them two by two
2016 for (int j = start; j < end; j++) {
2017 Node* n1 = C->expensive_node(j);
2018 if (is_node_unreachable(n1)) {
2019 continue;
2020 }
2021 for (int k = j+1; k < end; k++) {
2022 Node* n2 = C->expensive_node(k);
2023 if (is_node_unreachable(n2)) {
2024 continue;
2025 }
2026
2027 assert(n1 != n2, "should be pair of nodes");
2028
2029 Node* c1 = n1->in(0);
2030 Node* c2 = n2->in(0);
2031
2032 Node* parent_c1 = c1;
2033 Node* parent_c2 = c2;
2034
2035 // The call to get_early_ctrl_for_expensive() moves the
2036 // expensive nodes up but stops at loops that are in a if
2037 // branch. See whether we can exit the loop and move above the
2038 // If.
2039 if (c1->is_Loop()) {
2040 parent_c1 = c1->in(1);
2041 }
2042 if (c2->is_Loop()) {
2043 parent_c2 = c2->in(1);
2044 }
2045
2046 if (parent_c1 == parent_c2) {
2047 _igvn._worklist.push(n1);
2048 _igvn._worklist.push(n2);
2049 continue;
2050 }
2051
2052 // Look for identical expensive node up the dominator chain.
2053 if (is_dominator(c1, c2)) {
2054 c2 = c1;
2055 } else if (is_dominator(c2, c1)) {
2056 c1 = c2;
2057 } else if (parent_c1->is_Proj() && parent_c1->in(0)->is_If() &&
2058 parent_c2->is_Proj() && parent_c1->in(0) == parent_c2->in(0)) {
2059 // Both branches have the same expensive node so move it up
2060 // before the if.
2061 c1 = c2 = idom(parent_c1->in(0));
2062 }
2063 // Do the actual moves
2064 if (n1->in(0) != c1) {
2065 _igvn.hash_delete(n1);
2066 n1->set_req(0, c1);
2067 _igvn.hash_insert(n1);
2068 _igvn._worklist.push(n1);
2069 progress = true;
2070 }
2071 if (n2->in(0) != c2) {
2072 _igvn.hash_delete(n2);
2073 n2->set_req(0, c2);
2074 _igvn.hash_insert(n2);
2075 _igvn._worklist.push(n2);
2076 progress = true;
2077 }
2078 }
2079 }
2080 }
2081
2082 return progress;
2083 }
2084
2085
1895 //============================================================================= 2086 //=============================================================================
1896 //----------------------------build_and_optimize------------------------------- 2087 //----------------------------build_and_optimize-------------------------------
1897 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to 2088 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
1898 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups. 2089 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
1899 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool skip_loop_opts) { 2090 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool skip_loop_opts) {
1958 } 2149 }
1959 return; 2150 return;
1960 } 2151 }
1961 2152
1962 // Nothing to do, so get out 2153 // Nothing to do, so get out
1963 if( !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only ) { 2154 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2155 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2156 if (stop_early && !do_expensive_nodes) {
1964 _igvn.optimize(); // Cleanup NeverBranches 2157 _igvn.optimize(); // Cleanup NeverBranches
1965 return; 2158 return;
1966 } 2159 }
1967 2160
1968 // Set loop nesting depth 2161 // Set loop nesting depth
2056 assert(C->unique() == unique, "verification mode made Nodes? ? ?"); 2249 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2057 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything"); 2250 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2058 return; 2251 return;
2059 } 2252 }
2060 2253
2254 if (stop_early) {
2255 assert(do_expensive_nodes, "why are we here?");
2256 if (process_expensive_nodes()) {
2257 // If we made some progress when processing expensive nodes then
2258 // the IGVN may modify the graph in a way that will allow us to
2259 // make some more progress: we need to try processing expensive
2260 // nodes again.
2261 C->set_major_progress();
2262 }
2263
2264 _igvn.optimize();
2265
2266 return;
2267 }
2268
2061 // Some parser-inserted loop predicates could never be used by loop 2269 // Some parser-inserted loop predicates could never be used by loop
2062 // predication or they were moved away from loop during some optimizations. 2270 // predication or they were moved away from loop during some optimizations.
2063 // For example, peeling. Eliminate them before next loop optimizations. 2271 // For example, peeling. Eliminate them before next loop optimizations.
2064 if (UseLoopPredicate || LoopLimitCheck) { 2272 if (UseLoopPredicate || LoopLimitCheck) {
2065 eliminate_useless_predicates(); 2273 eliminate_useless_predicates();
2116 // that require basic-block info (like cloning through Phi's) 2324 // that require basic-block info (like cloning through Phi's)
2117 if( SplitIfBlocks && do_split_ifs ) { 2325 if( SplitIfBlocks && do_split_ifs ) {
2118 visited.Clear(); 2326 visited.Clear();
2119 split_if_with_blocks( visited, nstack ); 2327 split_if_with_blocks( visited, nstack );
2120 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); ); 2328 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2329 }
2330
2331 if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2332 C->set_major_progress();
2121 } 2333 }
2122 2334
2123 // Perform loop predication before iteration splitting 2335 // Perform loop predication before iteration splitting
2124 if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) { 2336 if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2125 _ltree_root->_child->loop_predication(this); 2337 _ltree_root->_child->loop_predication(this);
3297 Node *least = legal; // Best legal position so far 3509 Node *least = legal; // Best legal position so far
3298 while( early != legal ) { // While not at earliest legal 3510 while( early != legal ) { // While not at earliest legal
3299 #ifdef ASSERT 3511 #ifdef ASSERT
3300 if (legal->is_Start() && !early->is_Root()) { 3512 if (legal->is_Start() && !early->is_Root()) {
3301 // Bad graph. Print idom path and fail. 3513 // Bad graph. Print idom path and fail.
3302 dump_bad_graph(n, early, LCA); 3514 dump_bad_graph("Bad graph detected in build_loop_late", n, early, LCA);
3303 assert(false, "Bad graph detected in build_loop_late"); 3515 assert(false, "Bad graph detected in build_loop_late");
3304 } 3516 }
3305 #endif 3517 #endif
3306 // Find least loop nesting depth 3518 // Find least loop nesting depth
3307 legal = idom(legal); // Bump up the IDOM tree 3519 legal = idom(legal); // Bump up the IDOM tree
3348 if( !chosen_loop->_child ) // Inner loop? 3560 if( !chosen_loop->_child ) // Inner loop?
3349 chosen_loop->_body.push(n);// Collect inner loops 3561 chosen_loop->_body.push(n);// Collect inner loops
3350 } 3562 }
3351 3563
3352 #ifdef ASSERT 3564 #ifdef ASSERT
3353 void PhaseIdealLoop::dump_bad_graph(Node* n, Node* early, Node* LCA) { 3565 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
3354 tty->print_cr( "Bad graph detected in build_loop_late"); 3566 tty->print_cr(msg);
3355 tty->print("n: "); n->dump(); 3567 tty->print("n: "); n->dump();
3356 tty->print("early(n): "); early->dump(); 3568 tty->print("early(n): "); early->dump();
3357 if (n->in(0) != NULL && !n->in(0)->is_top() && 3569 if (n->in(0) != NULL && !n->in(0)->is_top() &&
3358 n->in(0) != early && !n->in(0)->is_Root()) { 3570 n->in(0) != early && !n->in(0)->is_Root()) {
3359 tty->print("n->in(0): "); n->in(0)->dump(); 3571 tty->print("n->in(0): "); n->in(0)->dump();