238 //------------------------------small_cache------------------------------------
239 struct small_cache : public Dict {
240
241 small_cache() : Dict( cmpkey, hashptr ) {}
242 Node *probe( Node *use_blk ) { return (Node*)((*this)[use_blk]); }
243 void lru_insert( Node *use_blk, Node *new_def ) { Insert(use_blk,new_def); }
244 };
245
246 //------------------------------spinup-----------------------------------------
247 // "Spin up" the dominator tree, starting at the use site and stopping when we
248 // find the post-dominating point.
249
250 // We must be at the merge point which post-dominates 'new_false' and
251 // 'new_true'. Figure out which edges into the RegionNode eventually lead up
252 // to false and which to true. Put in a PhiNode to merge values; plug in
253 // the appropriate false-arm or true-arm values. If some path leads to the
254 // original IF, then insert a Phi recursively.
255 Node *PhaseIdealLoop::spinup( Node *iff_dom, Node *new_false, Node *new_true, Node *use_blk, Node *def, small_cache *cache ) {
256 if (use_blk->is_top()) // Handle dead uses
257 return use_blk;
258 Node *prior_n = (Node*)0xdeadbeef;
259 Node *n = use_blk; // Get path input
260 assert( use_blk != iff_dom, "" );
261 // Here's the "spinup" the dominator tree loop. Do a cache-check
262 // along the way, in case we've come this way before.
263 while( n != iff_dom ) { // Found post-dominating point?
264 prior_n = n;
265 n = idom(n); // Search higher
266 Node *s = cache->probe( prior_n ); // Check cache
267 if( s ) return s; // Cache hit!
268 }
269
270 Node *phi_post;
271 if( prior_n == new_false || prior_n == new_true ) {
272 phi_post = def->clone();
273 phi_post->set_req(0, prior_n );
274 register_new_node(phi_post, prior_n);
275 } else {
276 // This method handles both control uses (looking for Regions) or data
277 // uses (looking for Phis). If looking for a control use, then we need
278 // to insert a Region instead of a Phi; however Regions always exist
285 assert( prior_n->is_Region(), "must be a post-dominating merge point" );
286
287 // Need a Phi here
288 phi_post = PhiNode::make_blank(prior_n, def);
289 // Search for both true and false on all paths till find one.
290 for( uint i = 1; i < phi_post->req(); i++ ) // For all paths
291 phi_post->init_req( i, spinup( iff_dom, new_false, new_true, prior_n->in(i), def, cache ) );
292 Node *t = _igvn.hash_find_insert(phi_post);
293 if( t ) { // See if we already have this one
294 // phi_post will not be used, so kill it
295 _igvn.remove_dead_node(phi_post);
296 phi_post->destruct();
297 phi_post = t;
298 } else {
299 register_new_node( phi_post, prior_n );
300 }
301 }
302 }
303
304 // Update cache everywhere
305 prior_n = (Node*)0xdeadbeef; // Reset IDOM walk
306 n = use_blk; // Get path input
307 // Spin-up the idom tree again, basically doing path-compression.
308 // Insert cache entries along the way, so that if we ever hit this
309 // point in the IDOM tree again we'll stop immediately on a cache hit.
310 while( n != iff_dom ) { // Found post-dominating point?
311 prior_n = n;
312 n = idom(n); // Search higher
313 cache->lru_insert( prior_n, phi_post ); // Fill cache
314 } // End of while not gone high enough
315
316 return phi_post;
317 }
318
319 //------------------------------find_use_block---------------------------------
320 // Find the block a USE is in. Normally USE's are in the same block as the
321 // using instruction. For Phi-USE's, the USE is in the predecessor block
322 // along the corresponding path.
323 Node *PhaseIdealLoop::find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true ) {
324 // CFG uses are their own block
325 if( use->is_CFG() )
|
238 //------------------------------small_cache------------------------------------
239 struct small_cache : public Dict {
240
241 small_cache() : Dict( cmpkey, hashptr ) {}
242 Node *probe( Node *use_blk ) { return (Node*)((*this)[use_blk]); }
243 void lru_insert( Node *use_blk, Node *new_def ) { Insert(use_blk,new_def); }
244 };
245
246 //------------------------------spinup-----------------------------------------
247 // "Spin up" the dominator tree, starting at the use site and stopping when we
248 // find the post-dominating point.
249
250 // We must be at the merge point which post-dominates 'new_false' and
251 // 'new_true'. Figure out which edges into the RegionNode eventually lead up
252 // to false and which to true. Put in a PhiNode to merge values; plug in
253 // the appropriate false-arm or true-arm values. If some path leads to the
254 // original IF, then insert a Phi recursively.
255 Node *PhaseIdealLoop::spinup( Node *iff_dom, Node *new_false, Node *new_true, Node *use_blk, Node *def, small_cache *cache ) {
256 if (use_blk->is_top()) // Handle dead uses
257 return use_blk;
258 Node *prior_n = (Node*)(uintptr_t)0xdeadbeef;
259 Node *n = use_blk; // Get path input
260 assert( use_blk != iff_dom, "" );
261 // Here's the "spinup" the dominator tree loop. Do a cache-check
262 // along the way, in case we've come this way before.
263 while( n != iff_dom ) { // Found post-dominating point?
264 prior_n = n;
265 n = idom(n); // Search higher
266 Node *s = cache->probe( prior_n ); // Check cache
267 if( s ) return s; // Cache hit!
268 }
269
270 Node *phi_post;
271 if( prior_n == new_false || prior_n == new_true ) {
272 phi_post = def->clone();
273 phi_post->set_req(0, prior_n );
274 register_new_node(phi_post, prior_n);
275 } else {
276 // This method handles both control uses (looking for Regions) or data
277 // uses (looking for Phis). If looking for a control use, then we need
278 // to insert a Region instead of a Phi; however Regions always exist
285 assert( prior_n->is_Region(), "must be a post-dominating merge point" );
286
287 // Need a Phi here
288 phi_post = PhiNode::make_blank(prior_n, def);
289 // Search for both true and false on all paths till find one.
290 for( uint i = 1; i < phi_post->req(); i++ ) // For all paths
291 phi_post->init_req( i, spinup( iff_dom, new_false, new_true, prior_n->in(i), def, cache ) );
292 Node *t = _igvn.hash_find_insert(phi_post);
293 if( t ) { // See if we already have this one
294 // phi_post will not be used, so kill it
295 _igvn.remove_dead_node(phi_post);
296 phi_post->destruct();
297 phi_post = t;
298 } else {
299 register_new_node( phi_post, prior_n );
300 }
301 }
302 }
303
304 // Update cache everywhere
305 prior_n = (Node*)(uintptr_t)0xdeadbeef; // Reset IDOM walk
306 n = use_blk; // Get path input
307 // Spin-up the idom tree again, basically doing path-compression.
308 // Insert cache entries along the way, so that if we ever hit this
309 // point in the IDOM tree again we'll stop immediately on a cache hit.
310 while( n != iff_dom ) { // Found post-dominating point?
311 prior_n = n;
312 n = idom(n); // Search higher
313 cache->lru_insert( prior_n, phi_post ); // Fill cache
314 } // End of while not gone high enough
315
316 return phi_post;
317 }
318
319 //------------------------------find_use_block---------------------------------
320 // Find the block a USE is in. Normally USE's are in the same block as the
321 // using instruction. For Phi-USE's, the USE is in the predecessor block
322 // along the corresponding path.
323 Node *PhaseIdealLoop::find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true ) {
324 // CFG uses are their own block
325 if( use->is_CFG() )
|