diff options
Diffstat (limited to 'src/opt/res/resWin.c')
-rw-r--r-- | src/opt/res/resWin.c | 358 |
1 files changed, 228 insertions, 130 deletions
diff --git a/src/opt/res/resWin.c b/src/opt/res/resWin.c index fa74b219..80a65ea8 100644 --- a/src/opt/res/resWin.c +++ b/src/opt/res/resWin.c @@ -43,12 +43,19 @@ Res_Win_t * Res_WinAlloc() { Res_Win_t * p; + // start the manager p = ALLOC( Res_Win_t, 1 ); memset( p, 0, sizeof(Res_Win_t) ); - p->vLevels = Vec_VecStart( 128 ); - p->vLeaves = Vec_PtrAlloc( 512 ); - p->vRoots = Vec_PtrAlloc( 512 ); - p->vDivs = Vec_PtrAlloc( 512 ); + // set internal parameters + p->nFanoutLimit = 10; + p->nLevTfiMinus = 3; + // allocate storage + p->vRoots = Vec_PtrAlloc( 256 ); + p->vLeaves = Vec_PtrAlloc( 256 ); + p->vBranches = Vec_PtrAlloc( 256 ); + p->vNodes = Vec_PtrAlloc( 256 ); + p->vDivs = Vec_PtrAlloc( 256 ); + p->vMatrix = Vec_VecStart( 128 ); return p; } @@ -65,48 +72,87 @@ Res_Win_t * Res_WinAlloc() ***********************************************************************/ void Res_WinFree( Res_Win_t * p ) { - Vec_VecFree( p->vLevels ); - Vec_PtrFree( p->vLeaves ); Vec_PtrFree( p->vRoots ); + Vec_PtrFree( p->vLeaves ); + Vec_PtrFree( p->vBranches ); + Vec_PtrFree( p->vNodes ); Vec_PtrFree( p->vDivs ); + Vec_VecFree( p->vMatrix ); free( p ); } + + /**Function************************************************************* - Synopsis [Collects nodes in the limited TFI of the node.] + Synopsis [Collect the limited TFI cone of the node.] - Description [Marks the collected nodes.] + Description [] SideEffects [] SeeAlso [] ***********************************************************************/ -void Res_WinCollectNodeTfi( Res_Win_t * p ) +void Res_WinCollectLeavesAndNodes( Res_Win_t * p ) { Vec_Ptr_t * vFront; - Abc_Obj_t * pObj, * pFanin; + Abc_Obj_t * pObj, * pTemp; int i, k, m; - // expand storage for levels - if ( Vec_VecSize( p->vLevels ) <= (int)p->pNode->Level + p->nWinTfoMax ) - Vec_VecExpand( p->vLevels, (int)p->pNode->Level + p->nWinTfoMax ); - // start the frontier - Vec_VecClear( p->vLevels ); - Res_WinAddNode( p, p->pNode ); - // add one level at a time - Vec_VecForEachLevelReverseStartStop( p->vLevels, vFront, i, p->pNode->Level, p->nLevLeaves + 1 ) + + assert( p->nWinTfiMax > 0 ); + assert( Vec_VecSize(p->vMatrix) > p->nWinTfiMax ); + + // start matrix with the node + Vec_VecClear( p->vMatrix ); + Vec_VecPush( p->vMatrix, 0, p->pNode ); + Abc_NtkIncrementTravId( p->pNode->pNtk ); + Abc_NodeSetTravIdCurrent( p->pNode ); + + // collect the leaves (nodes pTemp such that "p->pNode->Level - pTemp->Level > p->nWinTfiMax") + Vec_PtrClear( p->vLeaves ); + Vec_VecForEachLevelStartStop( p->vMatrix, vFront, i, 0, p->nWinTfiMax ) { Vec_PtrForEachEntry( vFront, pObj, k ) - Abc_ObjForEachFanin( pObj, pFanin, m ) - if ( !pFanin->fMarkA ) - Res_WinAddNode( p, pFanin ); + { + Abc_ObjForEachFanin( pObj, pTemp, m ) + { + if ( Abc_NodeIsTravIdCurrent( pTemp ) ) + continue; + Abc_NodeSetTravIdCurrent( pTemp ); + if ( Abc_ObjIsCi(pTemp) || (int)(p->pNode->Level - pTemp->Level) > p->nWinTfiMax ) + Vec_PtrPush( p->vLeaves, pTemp ); + else + Vec_VecPush( p->vMatrix, p->pNode->Level - pTemp->Level, pTemp ); + } + } } + assert( Vec_PtrSize(p->vLeaves) > 0 ); + + // collect the nodes in the reverse order + Vec_PtrClear( p->vNodes ); + Vec_VecForEachLevelReverseStartStop( p->vMatrix, vFront, i, p->nWinTfiMax, 0 ) + { + Vec_PtrForEachEntry( vFront, pObj, k ) + Vec_PtrPush( p->vNodes, pObj ); + Vec_PtrClear( vFront ); + } + + // get the lowest leaf level + p->nLevLeafMin = ABC_INFINITY; + Vec_PtrForEachEntry( p->vLeaves, pObj, k ) + p->nLevLeafMin = ABC_MIN( p->nLevLeafMin, (int)pObj->Level ); + + // set minimum traversal level + p->nLevTravMin = ABC_MAX( ((int)p->pNode->Level) - p->nWinTfiMax - p->nLevTfiMinus, p->nLevLeafMin ); + assert( p->nLevTravMin >= 0 ); } + + /**Function************************************************************* - Synopsis [Collect all the nodes that fanin into the window nodes.] + Synopsis [Returns 1 if the node should be a root.] Description [] @@ -115,24 +161,25 @@ void Res_WinCollectNodeTfi( Res_Win_t * p ) SeeAlso [] ***********************************************************************/ -void Res_WinCollectLeaves( Res_Win_t * p ) +static inline int Res_WinComputeRootsCheck( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit ) { - Vec_Ptr_t * vLevel; - Abc_Obj_t * pObj; - int i, k; - // add the leaves - Vec_PtrClear( p->vLeaves ); - // collect the nodes below the given level - Vec_VecForEachEntryStartStop( p->vLevels, pObj, i, k, 0, p->nLevLeaves ) - Vec_PtrPush( p->vLeaves, pObj ); - // remove leaves from the set - Vec_VecForEachLevelStartStop( p->vLevels, vLevel, i, 0, p->nLevLeaves ) - Vec_PtrClear( vLevel ); + Abc_Obj_t * pFanout; + int i; + // the node is the root if one of the following is true: + // (1) the node has more than fanouts than the limit + if ( Abc_ObjFanoutNum(pNode) > nFanoutLimit ) + return 1; + // (2) the node has CO fanouts + // (3) the node has fanouts above the cutoff level + Abc_ObjForEachFanout( pNode, pFanout, i ) + if ( Abc_ObjIsCo(pFanout) || (int)pFanout->Level > nLevelMax ) + return 1; + return 0; } /**Function************************************************************* - Synopsis [Marks the TFO of the collected nodes up to the given level.] + Synopsis [Recursively collects the root candidates.] Description [] @@ -141,22 +188,85 @@ void Res_WinCollectLeaves( Res_Win_t * p ) SeeAlso [] ***********************************************************************/ -void Res_WinSweepLeafTfo_rec( Abc_Obj_t * pObj, int nLevelLimit, Abc_Obj_t * pNode ) +void Res_WinComputeRoots_rec( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit, Vec_Ptr_t * vRoots ) { Abc_Obj_t * pFanout; int i; - if ( Abc_ObjIsCo(pObj) || (int)pObj->Level > nLevelLimit || pObj == pNode ) - return; - if ( Abc_NodeIsTravIdCurrent(pObj) ) + assert( Abc_ObjIsNode(pNode) ); + if ( Abc_NodeIsTravIdCurrent(pNode) ) return; - Abc_NodeSetTravIdCurrent( pObj ); - Abc_ObjForEachFanout( pObj, pFanout, i ) - Res_WinSweepLeafTfo_rec( pFanout, nLevelLimit, pNode ); + Abc_NodeSetTravIdCurrent( pNode ); + // check if the node should be the root + if ( Res_WinComputeRootsCheck( pNode, nLevelMax, nFanoutLimit ) ) + Vec_PtrPush( vRoots, pNode ); + else // if not, explore its fanouts + Abc_ObjForEachFanout( pNode, pFanout, i ) + Res_WinComputeRoots_rec( pFanout, nLevelMax, nFanoutLimit, vRoots ); +} + +/**Function************************************************************* + + Synopsis [Recursively collects the root candidates.] + + Description [Returns 1 if the only root is this node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Res_WinComputeRoots( Res_Win_t * p ) +{ + Vec_PtrClear( p->vRoots ); + Abc_NtkIncrementTravId( p->pNode->pNtk ); + Res_WinComputeRoots_rec( p->pNode, p->pNode->Level + p->nWinTfoMax, p->nFanoutLimit, p->vRoots ); + assert( Vec_PtrSize(p->vRoots) > 0 ); + if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode ) + return 0; + return 1; +} + + + +/**Function************************************************************* + + Synopsis [Marks the paths from the roots to the leaves.] + + Description [Returns 1 if the the node can reach a leaf.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Res_WinMarkPaths_rec( Abc_Obj_t * pNode, Abc_Obj_t * pPivot, int nLevelMin ) +{ + Abc_Obj_t * pFanin; + int i, RetValue; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pNode) ) + return 1; + if ( Abc_NodeIsTravIdPrevious(pNode) ) + return 0; + // assume that the node does not have access to the leaves + Abc_NodeSetTravIdPrevious( pNode ); + // skip nodes below the given level + if ( pNode == pPivot || (int)pNode->Level <= nLevelMin ) + return 0; + assert( Abc_ObjIsNode(pNode) ); + // check if the fanins have access to the leaves + RetValue = 0; + Abc_ObjForEachFanin( pNode, pFanin, i ) + RetValue |= Res_WinMarkPaths_rec( pFanin, pPivot, nLevelMin ); + // relabel the node if it has access to the leaves + if ( RetValue ) + Abc_NodeSetTravIdCurrent( pNode ); + return RetValue; } /**Function************************************************************* - Synopsis [Marks the TFO of the collected nodes up to the given level.] + Synopsis [Marks the paths from the roots to the leaves.] Description [] @@ -165,15 +275,25 @@ void Res_WinSweepLeafTfo_rec( Abc_Obj_t * pObj, int nLevelLimit, Abc_Obj_t * pNo SeeAlso [] ***********************************************************************/ -void Res_WinSweepLeafTfo( Res_Win_t * p ) +void Res_WinMarkPaths( Res_Win_t * p ) { Abc_Obj_t * pObj; int i; + // mark the leaves + Abc_NtkIncrementTravId( p->pNode->pNtk ); Abc_NtkIncrementTravId( p->pNode->pNtk ); Vec_PtrForEachEntry( p->vLeaves, pObj, i ) - Res_WinSweepLeafTfo_rec( pObj, p->pNode->Level + p->nWinTfoMax, p->pNode ); + Abc_NodeSetTravIdCurrent( pObj ); + // traverse from the roots and mark the nodes that can reach leaves + // the nodes that do not reach leaves have previous trav ID + // the nodes that reach leaves have current trav ID + Vec_PtrForEachEntry( p->vRoots, pObj, i ) + Res_WinMarkPaths_rec( pObj, p->pNode, p->nLevTravMin ); } + + + /**Function************************************************************* Synopsis [Recursively collects the roots.] @@ -185,29 +305,27 @@ void Res_WinSweepLeafTfo( Res_Win_t * p ) SeeAlso [] ***********************************************************************/ -void Res_WinCollectRoots_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vRoots ) +void Res_WinFinalizeRoots_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vRoots ) { Abc_Obj_t * pFanout; int i; assert( Abc_ObjIsNode(pObj) ); + assert( Abc_NodeIsTravIdCurrent(pObj) ); // check if the node has all fanouts marked Abc_ObjForEachFanout( pObj, pFanout, i ) if ( !Abc_NodeIsTravIdCurrent(pFanout) ) break; - // if some of the fanouts are unmarked, add the node to the root + // if some of the fanouts are unmarked, add the node to the roots if ( i < Abc_ObjFanoutNum(pObj) ) - { Vec_PtrPushUnique( vRoots, pObj ); - return; - } - // otherwise, call recursively - Abc_ObjForEachFanout( pObj, pFanout, i ) - Res_WinCollectRoots_rec( pFanout, vRoots ); + else // otherwise, call recursively + Abc_ObjForEachFanout( pObj, pFanout, i ) + Res_WinFinalizeRoots_rec( pFanout, vRoots ); } /**Function************************************************************* - Synopsis [Collects the roots of the window.] + Synopsis [Finalizes the roots of the window.] Description [Roots of the window are the nodes that have at least one fanout that it not in the TFO of the leaves.] @@ -217,13 +335,21 @@ void Res_WinCollectRoots_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vRoots ) SeeAlso [] ***********************************************************************/ -void Res_WinCollectRoots( Res_Win_t * p ) +int Res_WinFinalizeRoots( Res_Win_t * p ) { assert( !Abc_NodeIsTravIdCurrent(p->pNode) ); + // mark the node with the old traversal ID + Abc_NodeSetTravIdCurrent( p->pNode ); + // recollect the roots Vec_PtrClear( p->vRoots ); - Res_WinCollectRoots_rec( p->pNode, p->vRoots ); + Res_WinFinalizeRoots_rec( p->pNode, p->vRoots ); + assert( Vec_PtrSize(p->vRoots) > 0 ); + if ( Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode ) + return 0; + return 1; } + /**Function************************************************************* Synopsis [Recursively adds missing nodes and leaves.] @@ -235,23 +361,27 @@ void Res_WinCollectRoots( Res_Win_t * p ) SeeAlso [] ***********************************************************************/ -void Res_WinAddMissing_rec( Res_Win_t * p, Abc_Obj_t * pObj ) +void Res_WinAddMissing_rec( Res_Win_t * p, Abc_Obj_t * pObj, int nLevTravMin ) { Abc_Obj_t * pFanin; int i; - if ( pObj->fMarkA ) + // skip the already collected leaves, nodes, and branches + if ( Abc_NodeIsTravIdCurrent(pObj) ) return; - if ( !Abc_NodeIsTravIdCurrent(pObj) || (int)pObj->Level <= p->nLevLeaves ) + // if this is not an internal node - make it a new branch + if ( !Abc_NodeIsTravIdPrevious(pObj) ) { - p->nLeavesPlus++; - Vec_PtrPush( p->vLeaves, pObj ); - pObj->fMarkA = 1; + Abc_NodeSetTravIdCurrent( pObj ); + Vec_PtrPush( p->vBranches, pObj ); return; } - Res_WinAddNode( p, pObj ); + assert( Abc_ObjIsNode(pObj) ); // if this is a CI, then the window is incorrect! + Abc_NodeSetTravIdCurrent( pObj ); // visit the fanins of the node Abc_ObjForEachFanin( pObj, pFanin, i ) - Res_WinAddMissing_rec( p, pFanin ); + Res_WinAddMissing_rec( p, pFanin, nLevTravMin ); + // collect the node + Vec_PtrPush( p->vNodes, pObj ); } /**Function************************************************************* @@ -269,34 +399,25 @@ void Res_WinAddMissing( Res_Win_t * p ) { Abc_Obj_t * pObj; int i; + // mark the leaves + Abc_NtkIncrementTravId( p->pNode->pNtk ); + Vec_PtrForEachEntry( p->vLeaves, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + // mark the already collected nodes + Vec_PtrForEachEntry( p->vNodes, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + // explore from the roots + Vec_PtrClear( p->vBranches ); Vec_PtrForEachEntry( p->vRoots, pObj, i ) - Res_WinAddMissing_rec( p, pObj ); + Res_WinAddMissing_rec( p, pObj, p->nLevTravMin ); } -/**Function************************************************************* - - Synopsis [Unmarks the leaves and nodes of the window.] - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Res_WinUnmark( Res_Win_t * p ) -{ - Abc_Obj_t * pObj; - int i, k; - Vec_VecForEachEntry( p->vLevels, pObj, i, k ) - pObj->fMarkA = 0; - Vec_PtrForEachEntry( p->vLeaves, pObj, i ) - pObj->fMarkA = 0; -} + /**Function************************************************************* - Synopsis [Verifies the window.] + Synopsis [Returns 1 if the window is trivial (without TFO).] Description [] @@ -305,30 +426,9 @@ void Res_WinUnmark( Res_Win_t * p ) SeeAlso [] ***********************************************************************/ -void Res_WinVerify( Res_Win_t * p ) +int Res_WinIsTrivial( Res_Win_t * p ) { - Abc_Obj_t * pObj, * pFanin; - int i, k, f; - // make sure the nodes are not marked - Abc_NtkForEachObj( p->pNode->pNtk, pObj, i ) - assert( !pObj->fMarkA ); - // mark the leaves - Vec_PtrForEachEntry( p->vLeaves, pObj, i ) - pObj->fMarkA = 1; - // make sure all nodes in the topological order have their fanins in the set - Vec_VecForEachEntryStartStop( p->vLevels, pObj, i, k, p->nLevLeaves + 1, (int)p->pNode->Level + p->nWinTfoMax ) - { - assert( (int)pObj->Level == i ); - assert( !pObj->fMarkA ); - Abc_ObjForEachFanin( pObj, pFanin, f ) - assert( pFanin->fMarkA ); - pObj->fMarkA = 1; - } - // make sure the roots are marked - Vec_PtrForEachEntry( p->vRoots, pObj, i ) - assert( pObj->fMarkA ); - // unmark - Res_WinUnmark( p ); + return Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode; } /**Function************************************************************* @@ -345,31 +445,29 @@ void Res_WinVerify( Res_Win_t * p ) int Res_WinCompute( Abc_Obj_t * pNode, int nWinTfiMax, int nWinTfoMax, Res_Win_t * p ) { assert( Abc_ObjIsNode(pNode) ); - assert( nWinTfiMax > 0 && nWinTfoMax > 0 ); + assert( nWinTfiMax > 0 && nWinTfiMax < 10 ); + assert( nWinTfoMax >= 0 && nWinTfoMax < 10 ); + // initialize the window - p->pNode = pNode; + p->pNode = pNode; p->nWinTfiMax = nWinTfiMax; p->nWinTfoMax = nWinTfoMax; - p->nLeavesPlus = 0; - p->nLevLeaves = ABC_MAX( 0, ((int)p->pNode->Level) - p->nWinTfiMax - 1 ); - // collect the nodes in TFI cone of pNode above the level of leaves (p->nLevLeaves) - Res_WinCollectNodeTfi( p ); - // find the leaves of the window - Res_WinCollectLeaves( p ); - // mark the TFO of the collected nodes up to the given level (p->pNode->Level + p->nWinTfoMax) - Res_WinSweepLeafTfo( p ); - // find the roots of the window - Res_WinCollectRoots( p ); - // add the nodes in the TFI of the roots that are not yet in the window - Res_WinAddMissing( p ); - // unmark window nodes - Res_WinUnmark( p ); - // clear the divisor information - p->nLevDivMax = 0; - p->nDivsPlus = 0; - Vec_PtrClear( p->vDivs ); - // verify the resulting window -// Res_WinVerify( p ); + Vec_PtrClear( p->vRoots ); + Vec_PtrPush( p->vRoots, pNode ); + + // compute the leaves + Res_WinCollectLeavesAndNodes( p ); + + // compute the candidate roots + if ( p->nWinTfoMax > 0 && Res_WinComputeRoots(p) ) + { + // mark the paths from the roots to the leaves + Res_WinMarkPaths( p ); + // refine the roots and add branches and missing nodes + if ( Res_WinFinalizeRoots( p ) ) + Res_WinAddMissing( p ); + } + return 1; } |