379 // Setup 'vertex' as DFS to vertex mapping.
380 // Setup 'semi' as vertex to DFS mapping.
381 // Set 'parent' to DFS parent.
382 static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );
383 void setdepth( uint size, uint *dom_depth );
384
385 // Fast union-find work
386 void COMPRESS();
387 NTarjan *EVAL(void);
388 void LINK( NTarjan *w, NTarjan *ntarjan0 );
389 #ifndef PRODUCT
390 void dump(int offset) const;
391 #endif
392 };
393
394 //------------------------------Dominator--------------------------------------
395 // Compute the dominator tree of the sea of nodes. This version walks all CFG
396 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
397 // it needs a count of the CFG nodes for the mapping table. This is the
398 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
399 void PhaseIdealLoop::Dominators( ) {
400 ResourceMark rm;
401 // Setup mappings from my Graph to Tarjan's stuff and back
402 // Note: Tarjan uses 1-based arrays
403 NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
404 // Initialize _control field for fast reference
405 int i;
406 for( i= C->unique()-1; i>=0; i-- )
407 ntarjan[i]._control = NULL;
408
409 // Store the DFS order for the main loop
410 uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
411 memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint));
412
413 // Tarjan's algorithm, almost verbatim:
414 // Step 1:
415 VectorSet visited(Thread::current()->resource_area());
416 int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
417
418 // Tarjan is using 1-based arrays, so these are some initialize flags
419 ntarjan[0]._size = ntarjan[0]._semi = 0;
437 }
438
439 // w is added to a bucket here, and only here.
440 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
441 // Thus bucket can be a linked list.
442 w->_bucket = ntarjan[w->_semi]._bucket;
443 ntarjan[w->_semi]._bucket = w;
444
445 w->_parent->LINK( w, &ntarjan[0] );
446
447 // Step 3:
448 for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
449 NTarjan *u = vx->EVAL();
450 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
451 }
452
453 // Cleanup any unreachable loops now. Unreachable loops are loops that
454 // flow into the main graph (and hence into ROOT) but are not reachable
455 // from above. Such code is dead, but requires a global pass to detect
456 // it; this global pass was the 'build_loop_tree' pass run just prior.
457 if( whead->is_Region() ) {
458 for( uint i = 1; i < whead->req(); i++ ) {
459 if (!has_node(whead->in(i))) {
460 // Kill dead input path
461 assert( !visited.test(whead->in(i)->_idx),
462 "input with no loop must be dead" );
463 _igvn.hash_delete(whead);
464 whead->del_req(i);
465 _igvn._worklist.push(whead);
466 for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
467 Node* p = whead->fast_out(j);
468 if( p->is_Phi() ) {
469 _igvn.hash_delete(p);
470 p->del_req(i);
471 _igvn._worklist.push(p);
472 }
473 }
474 i--; // Rerun same iteration
475 } // End of if dead input path
476 } // End of for all input paths
477 } // End if if whead is a Region
|
379 // Setup 'vertex' as DFS to vertex mapping.
380 // Setup 'semi' as vertex to DFS mapping.
381 // Set 'parent' to DFS parent.
382 static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );
383 void setdepth( uint size, uint *dom_depth );
384
385 // Fast union-find work
386 void COMPRESS();
387 NTarjan *EVAL(void);
388 void LINK( NTarjan *w, NTarjan *ntarjan0 );
389 #ifndef PRODUCT
390 void dump(int offset) const;
391 #endif
392 };
393
394 //------------------------------Dominator--------------------------------------
395 // Compute the dominator tree of the sea of nodes. This version walks all CFG
396 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
397 // it needs a count of the CFG nodes for the mapping table. This is the
398 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
399 void PhaseIdealLoop::Dominators() {
400 ResourceMark rm;
401 // Setup mappings from my Graph to Tarjan's stuff and back
402 // Note: Tarjan uses 1-based arrays
403 NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
404 // Initialize _control field for fast reference
405 int i;
406 for( i= C->unique()-1; i>=0; i-- )
407 ntarjan[i]._control = NULL;
408
409 // Store the DFS order for the main loop
410 uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
411 memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint));
412
413 // Tarjan's algorithm, almost verbatim:
414 // Step 1:
415 VectorSet visited(Thread::current()->resource_area());
416 int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
417
418 // Tarjan is using 1-based arrays, so these are some initialize flags
419 ntarjan[0]._size = ntarjan[0]._semi = 0;
437 }
438
439 // w is added to a bucket here, and only here.
440 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
441 // Thus bucket can be a linked list.
442 w->_bucket = ntarjan[w->_semi]._bucket;
443 ntarjan[w->_semi]._bucket = w;
444
445 w->_parent->LINK( w, &ntarjan[0] );
446
447 // Step 3:
448 for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
449 NTarjan *u = vx->EVAL();
450 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
451 }
452
453 // Cleanup any unreachable loops now. Unreachable loops are loops that
454 // flow into the main graph (and hence into ROOT) but are not reachable
455 // from above. Such code is dead, but requires a global pass to detect
456 // it; this global pass was the 'build_loop_tree' pass run just prior.
457 if( !_verify_only && whead->is_Region() ) {
458 for( uint i = 1; i < whead->req(); i++ ) {
459 if (!has_node(whead->in(i))) {
460 // Kill dead input path
461 assert( !visited.test(whead->in(i)->_idx),
462 "input with no loop must be dead" );
463 _igvn.hash_delete(whead);
464 whead->del_req(i);
465 _igvn._worklist.push(whead);
466 for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
467 Node* p = whead->fast_out(j);
468 if( p->is_Phi() ) {
469 _igvn.hash_delete(p);
470 p->del_req(i);
471 _igvn._worklist.push(p);
472 }
473 }
474 i--; // Rerun same iteration
475 } // End of if dead input path
476 } // End of for all input paths
477 } // End if if whead is a Region
|