380 #ifndef PRODUCT
381 void dump(int offset) const;
382 #endif
383 };
384
385 // Compute the dominator tree of the sea of nodes. This version walks all CFG
386 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
387 // it needs a count of the CFG nodes for the mapping table. This is the
388 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
389 void PhaseIdealLoop::Dominators() {
390 ResourceMark rm;
391 // Setup mappings from my Graph to Tarjan's stuff and back
392 // Note: Tarjan uses 1-based arrays
393 NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
394 // Initialize _control field for fast reference
395 int i;
396 for( i= C->unique()-1; i>=0; i-- )
397 ntarjan[i]._control = NULL;
398
399 // Store the DFS order for the main loop
400 uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
401 memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint));
402
403 // Tarjan's algorithm, almost verbatim:
404 // Step 1:
405 VectorSet visited(Thread::current()->resource_area());
406 int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
407
408 // Tarjan is using 1-based arrays, so these are some initialize flags
409 ntarjan[0]._size = ntarjan[0]._semi = 0;
410 ntarjan[0]._label = &ntarjan[0];
411
412 for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order
413 NTarjan *w = &ntarjan[i]; // Get Node from DFS
414 assert(w->_control != NULL,"bad DFS walk");
415
416 // Step 2:
417 Node *whead = w->_control;
418 for( uint j=0; j < whead->req(); j++ ) { // For each predecessor
419 if( whead->in(j) == NULL || !whead->in(j)->is_CFG() )
420 continue; // Only process control nodes
421 uint b = dfsorder[whead->in(j)->_idx];
422 if(b == max_uint) continue;
423 NTarjan *vx = &ntarjan[b];
424 NTarjan *u = vx->EVAL();
425 if( u->_semi < w->_semi )
426 w->_semi = u->_semi;
427 }
428
429 // w is added to a bucket here, and only here.
430 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
431 // Thus bucket can be a linked list.
432 w->_bucket = ntarjan[w->_semi]._bucket;
433 ntarjan[w->_semi]._bucket = w;
434
435 w->_parent->LINK( w, &ntarjan[0] );
436
437 // Step 3:
438 for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
439 NTarjan *u = vx->EVAL();
440 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
441 }
442
|
380 #ifndef PRODUCT
381 void dump(int offset) const;
382 #endif
383 };
384
385 // Compute the dominator tree of the sea of nodes. This version walks all CFG
386 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
387 // it needs a count of the CFG nodes for the mapping table. This is the
388 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
389 void PhaseIdealLoop::Dominators() {
390 ResourceMark rm;
391 // Setup mappings from my Graph to Tarjan's stuff and back
392 // Note: Tarjan uses 1-based arrays
393 NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
394 // Initialize _control field for fast reference
395 int i;
396 for( i= C->unique()-1; i>=0; i-- )
397 ntarjan[i]._control = NULL;
398
399 // Store the DFS order for the main loop
400 const uint fill_value = (uint) -1;
401 uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
402 memset(dfsorder, fill_value, (C->unique()+1) * sizeof(uint));
403
404 // Tarjan's algorithm, almost verbatim:
405 // Step 1:
406 VectorSet visited(Thread::current()->resource_area());
407 int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
408
409 // Tarjan is using 1-based arrays, so these are some initialize flags
410 ntarjan[0]._size = ntarjan[0]._semi = 0;
411 ntarjan[0]._label = &ntarjan[0];
412
413 for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order
414 NTarjan *w = &ntarjan[i]; // Get Node from DFS
415 assert(w->_control != NULL,"bad DFS walk");
416
417 // Step 2:
418 Node *whead = w->_control;
419 for( uint j=0; j < whead->req(); j++ ) { // For each predecessor
420 if( whead->in(j) == NULL || !whead->in(j)->is_CFG() )
421 continue; // Only process control nodes
422 uint b = dfsorder[whead->in(j)->_idx];
423 if(b == fill_value) continue;
424 NTarjan *vx = &ntarjan[b];
425 NTarjan *u = vx->EVAL();
426 if( u->_semi < w->_semi )
427 w->_semi = u->_semi;
428 }
429
430 // w is added to a bucket here, and only here.
431 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
432 // Thus bucket can be a linked list.
433 w->_bucket = ntarjan[w->_semi]._bucket;
434 ntarjan[w->_semi]._bucket = w;
435
436 w->_parent->LINK( w, &ntarjan[0] );
437
438 // Step 3:
439 for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
440 NTarjan *u = vx->EVAL();
441 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
442 }
443
|