diff options
Diffstat (limited to 'src/opt/res/resWin.c')
| -rw-r--r-- | src/opt/res/resWin.c | 485 |
1 files changed, 0 insertions, 485 deletions
diff --git a/src/opt/res/resWin.c b/src/opt/res/resWin.c deleted file mode 100644 index a3648925..00000000 --- a/src/opt/res/resWin.c +++ /dev/null @@ -1,485 +0,0 @@ -/**CFile**************************************************************** - - FileName [resWin.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Resynthesis package.] - - Synopsis [Windowing algorithm.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - January 15, 2007.] - - Revision [$Id: resWin.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "abc.h" -#include "resInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Allocates the window.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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) ); - // 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; -} - -/**Function************************************************************* - - Synopsis [Frees the window.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Res_WinFree( Res_Win_t * p ) -{ - 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 [Collect the limited TFI cone of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Res_WinCollectLeavesAndNodes( Res_Win_t * p ) -{ - Vec_Ptr_t * vFront; - Abc_Obj_t * pObj, * pTemp; - int i, k, m; - - 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, 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 ); - } - } - } - if ( Vec_PtrSize(p->vLeaves) == 0 ) - return 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 ); - return 1; -} - - - -/**Function************************************************************* - - Synopsis [Returns 1 if the node should be a root.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int Res_WinComputeRootsCheck( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit ) -{ - 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 [Recursively collects the root candidates.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Res_WinComputeRoots_rec( Abc_Obj_t * pNode, int nLevelMax, int nFanoutLimit, Vec_Ptr_t * vRoots ) -{ - Abc_Obj_t * pFanout; - int i; - assert( Abc_ObjIsNode(pNode) ); - if ( Abc_NodeIsTravIdCurrent(pNode) ) - return; - 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 paths from the roots to the leaves.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 ) - 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.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 roots - if ( i < Abc_ObjFanoutNum(pObj) ) - Vec_PtrPushUnique( vRoots, pObj ); - else // otherwise, call recursively - Abc_ObjForEachFanout( pObj, pFanout, i ) - Res_WinFinalizeRoots_rec( pFanout, vRoots ); -} - -/**Function************************************************************* - - 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.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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_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.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Res_WinAddMissing_rec( Res_Win_t * p, Abc_Obj_t * pObj, int nLevTravMin ) -{ - Abc_Obj_t * pFanin; - int i; - // skip the already collected leaves, nodes, and branches - if ( Abc_NodeIsTravIdCurrent(pObj) ) - return; - // if this is not an internal node - make it a new branch - if ( !Abc_NodeIsTravIdPrevious(pObj) ) - { - assert( Vec_PtrFind(p->vLeaves, pObj) == -1 ); - Abc_NodeSetTravIdCurrent( pObj ); - Vec_PtrPush( p->vBranches, pObj ); - return; - } - 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, nLevTravMin ); - // collect the node - Vec_PtrPush( p->vNodes, pObj ); -} - -/**Function************************************************************* - - Synopsis [Adds to the window nodes and leaves in the TFI of the roots.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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, p->nLevTravMin ); -} - - - - -/**Function************************************************************* - - Synopsis [Returns 1 if the window is trivial (without TFO).] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Res_WinIsTrivial( Res_Win_t * p ) -{ - return Vec_PtrSize(p->vRoots) == 1 && Vec_PtrEntry(p->vRoots, 0) == p->pNode; -} - -/**Function************************************************************* - - Synopsis [Computes the window.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Res_WinCompute( Abc_Obj_t * pNode, int nWinTfiMax, int nWinTfoMax, Res_Win_t * p ) -{ - assert( Abc_ObjIsNode(pNode) ); - assert( nWinTfiMax > 0 && nWinTfiMax < 10 ); - assert( nWinTfoMax >= 0 && nWinTfoMax < 10 ); - - // initialize the window - p->pNode = pNode; - p->nWinTfiMax = nWinTfiMax; - p->nWinTfoMax = nWinTfoMax; - - Vec_PtrClear( p->vBranches ); - Vec_PtrClear( p->vDivs ); - Vec_PtrClear( p->vRoots ); - Vec_PtrPush( p->vRoots, pNode ); - - // compute the leaves - if ( !Res_WinCollectLeavesAndNodes( p ) ) - return 0; - - // 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; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |