88 // We can re-run the above DFS pass with the correct number of blocks, 89 // and hack the Tarjan algorithm below to be robust in the presence of 90 // such dead loops (as was done for the NTarjan code farther below). 91 // Since this situation is so unlikely, instead I've decided to bail out. 92 // CNC 7/24/2001 93 C->record_method_not_compilable("unreachable loop"); 94 return; 95 } 96 _blocks._cnt = _num_blocks; 97 98 // Tarjan is using 1-based arrays, so these are some initialize flags 99 tarjan[0]._size = tarjan[0]._semi = 0; 100 tarjan[0]._label = &tarjan[0]; 101 102 uint i; 103 for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order 104 Tarjan *w = &tarjan[i]; // Get vertex from DFS 105 106 // Step 2: 107 Node *whead = w->_block->head(); 108 for( uint j=1; j < whead->req(); j++ ) { 109 Block *b = _bbs[whead->in(j)->_idx]; 110 Tarjan *vx = &tarjan[b->_pre_order]; 111 Tarjan *u = vx->EVAL(); 112 if( u->_semi < w->_semi ) 113 w->_semi = u->_semi; 114 } 115 116 // w is added to a bucket here, and only here. 117 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). 118 // Thus bucket can be a linked list. 119 // Thus we do not need a small integer name for each Block. 120 w->_bucket = tarjan[w->_semi]._bucket; 121 tarjan[w->_semi]._bucket = w; 122 123 w->_parent->LINK( w, &tarjan[0] ); 124 125 // Step 3: 126 for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { 127 Tarjan *u = vx->EVAL(); 128 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; 129 } | 88 // We can re-run the above DFS pass with the correct number of blocks, 89 // and hack the Tarjan algorithm below to be robust in the presence of 90 // such dead loops (as was done for the NTarjan code farther below). 91 // Since this situation is so unlikely, instead I've decided to bail out. 92 // CNC 7/24/2001 93 C->record_method_not_compilable("unreachable loop"); 94 return; 95 } 96 _blocks._cnt = _num_blocks; 97 98 // Tarjan is using 1-based arrays, so these are some initialize flags 99 tarjan[0]._size = tarjan[0]._semi = 0; 100 tarjan[0]._label = &tarjan[0]; 101 102 uint i; 103 for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order 104 Tarjan *w = &tarjan[i]; // Get vertex from DFS 105 106 // Step 2: 107 Node *whead = w->_block->head(); 108 for (uint j = 1; j < whead->req(); j++) { 109 Block* b = get_block_for_node(whead->in(j)); 110 Tarjan *vx = &tarjan[b->_pre_order]; 111 Tarjan *u = vx->EVAL(); 112 if( u->_semi < w->_semi ) 113 w->_semi = u->_semi; 114 } 115 116 // w is added to a bucket here, and only here. 117 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). 118 // Thus bucket can be a linked list. 119 // Thus we do not need a small integer name for each Block. 120 w->_bucket = tarjan[w->_semi]._bucket; 121 tarjan[w->_semi]._bucket = w; 122 123 w->_parent->LINK( w, &tarjan[0] ); 124 125 // Step 3: 126 for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { 127 Tarjan *u = vx->EVAL(); 128 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; 129 } |