| /**CFile**************************************************************** |
| |
| FileName [resDivs.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Resynthesis package.] |
| |
| Synopsis [Collect divisors for the given window.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - January 15, 2007.] |
| |
| Revision [$Id: resDivs.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "base/abc/abc.h" |
| #include "resInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| static void Res_WinMarkTfi( Res_Win_t * p ); |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Adds candidate divisors of the node to its window.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Res_WinDivisors( Res_Win_t * p, int nLevDivMax ) |
| { |
| Abc_Obj_t * pObj, * pFanout, * pFanin; |
| int k, f, m; |
| |
| // set the maximum level of the divisors |
| p->nLevDivMax = nLevDivMax; |
| |
| // mark the TFI with the current trav ID |
| Abc_NtkIncrementTravId( p->pNode->pNtk ); |
| Res_WinMarkTfi( p ); |
| |
| // mark with the current trav ID those nodes that should not be divisors: |
| // (1) the node and its TFO |
| // (2) the MFFC of the node |
| // (3) the node's fanins (these are treated as a special case) |
| Abc_NtkIncrementTravId( p->pNode->pNtk ); |
| Res_WinSweepLeafTfo_rec( p->pNode, p->nLevDivMax ); |
| Res_WinVisitMffc( p->pNode ); |
| Abc_ObjForEachFanin( p->pNode, pObj, k ) |
| Abc_NodeSetTravIdCurrent( pObj ); |
| |
| // at this point the nodes are marked with two trav IDs: |
| // nodes to be collected as divisors are marked with previous trav ID |
| // nodes to be avoided as divisors are marked with current trav ID |
| |
| // start collecting the divisors |
| Vec_PtrClear( p->vDivs ); |
| Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pObj, k ) |
| { |
| assert( (int)pObj->Level >= p->nLevLeafMin ); |
| if ( !Abc_NodeIsTravIdPrevious(pObj) ) |
| continue; |
| if ( (int)pObj->Level > p->nLevDivMax ) |
| continue; |
| Vec_PtrPush( p->vDivs, pObj ); |
| } |
| // add the internal nodes to the data structure |
| Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodes, pObj, k ) |
| { |
| if ( !Abc_NodeIsTravIdPrevious(pObj) ) |
| continue; |
| if ( (int)pObj->Level > p->nLevDivMax ) |
| continue; |
| Vec_PtrPush( p->vDivs, pObj ); |
| } |
| |
| // explore the fanouts of already collected divisors |
| p->nDivsPlus = 0; |
| Vec_PtrForEachEntry( Abc_Obj_t *, p->vDivs, pObj, k ) |
| { |
| // consider fanouts of this node |
| Abc_ObjForEachFanout( pObj, pFanout, f ) |
| { |
| // stop if there are too many fanouts |
| if ( f > 20 ) |
| break; |
| // skip nodes that are already added |
| if ( Abc_NodeIsTravIdPrevious(pFanout) ) |
| continue; |
| // skip nodes in the TFO or in the MFFC of node |
| if ( Abc_NodeIsTravIdCurrent(pFanout) ) |
| continue; |
| // skip COs |
| if ( !Abc_ObjIsNode(pFanout) ) |
| continue; |
| // skip nodes with large level |
| if ( (int)pFanout->Level > p->nLevDivMax ) |
| continue; |
| // skip nodes whose fanins are not divisors |
| Abc_ObjForEachFanin( pFanout, pFanin, m ) |
| if ( !Abc_NodeIsTravIdPrevious(pFanin) ) |
| break; |
| if ( m < Abc_ObjFaninNum(pFanout) ) |
| continue; |
| // add the node to the divisors |
| Vec_PtrPush( p->vDivs, pFanout ); |
| Vec_PtrPush( p->vNodes, pFanout ); |
| Abc_NodeSetTravIdPrevious( pFanout ); |
| p->nDivsPlus++; |
| } |
| } |
| /* |
| printf( "Node level = %d. ", Abc_ObjLevel(p->pNode) ); |
| Vec_PtrForEachEntryStart( Abc_Obj_t *, p->vDivs, pObj, k, Vec_PtrSize(p->vDivs)-p->nDivsPlus ) |
| printf( "%d ", Abc_ObjLevel(pObj) ); |
| printf( "\n" ); |
| */ |
| //printf( "%d ", p->nDivsPlus ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Marks the TFI cone of the node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Res_WinMarkTfi_rec( Res_Win_t * p, Abc_Obj_t * pObj ) |
| { |
| Abc_Obj_t * pFanin; |
| int i; |
| if ( Abc_NodeIsTravIdCurrent(pObj) ) |
| return; |
| Abc_NodeSetTravIdCurrent( pObj ); |
| assert( Abc_ObjIsNode(pObj) ); |
| // visit the fanins of the node |
| Abc_ObjForEachFanin( pObj, pFanin, i ) |
| Res_WinMarkTfi_rec( p, pFanin ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Marks the TFI cone of the node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Res_WinMarkTfi( Res_Win_t * p ) |
| { |
| Abc_Obj_t * pObj; |
| int i; |
| // mark the leaves |
| Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pObj, i ) |
| Abc_NodeSetTravIdCurrent( pObj ); |
| // start from the node |
| Res_WinMarkTfi_rec( p, p->pNode ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Marks the TFO of the collected nodes up to the given level.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Res_WinSweepLeafTfo_rec( Abc_Obj_t * pObj, int nLevelLimit ) |
| { |
| Abc_Obj_t * pFanout; |
| int i; |
| if ( Abc_ObjIsCo(pObj) || (int)pObj->Level > nLevelLimit ) |
| return; |
| if ( Abc_NodeIsTravIdCurrent(pObj) ) |
| return; |
| Abc_NodeSetTravIdCurrent( pObj ); |
| Abc_ObjForEachFanout( pObj, pFanout, i ) |
| Res_WinSweepLeafTfo_rec( pFanout, nLevelLimit ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Dereferences the node's MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Res_NodeDeref_rec( Abc_Obj_t * pNode ) |
| { |
| Abc_Obj_t * pFanin; |
| int i, Counter = 1; |
| if ( Abc_ObjIsCi(pNode) ) |
| return 0; |
| Abc_NodeSetTravIdCurrent( pNode ); |
| Abc_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| assert( pFanin->vFanouts.nSize > 0 ); |
| if ( --pFanin->vFanouts.nSize == 0 ) |
| Counter += Res_NodeDeref_rec( pFanin ); |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [References the node's MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Res_NodeRef_rec( Abc_Obj_t * pNode ) |
| { |
| Abc_Obj_t * pFanin; |
| int i, Counter = 1; |
| if ( Abc_ObjIsCi(pNode) ) |
| return 0; |
| Abc_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| if ( pFanin->vFanouts.nSize++ == 0 ) |
| Counter += Res_NodeRef_rec( pFanin ); |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Labels MFFC of the node with the current trav ID.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Res_WinVisitMffc( Abc_Obj_t * pNode ) |
| { |
| int Count1, Count2; |
| assert( Abc_ObjIsNode(pNode) ); |
| // dereference the node (mark with the current trav ID) |
| Count1 = Res_NodeDeref_rec( pNode ); |
| // reference it back |
| Count2 = Res_NodeRef_rec( pNode ); |
| assert( Count1 == Count2 ); |
| return Count1; |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
