/**CFile**************************************************************** FileName [mfsDiv.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [The good old minimization with complete don't-cares.] Synopsis [Procedures to compute candidate divisors.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: mfsDiv.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "mfsInt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Marks and collects the TFI cone of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_MfsWinMarkTfi_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vCone ) { Abc_Obj_t * pFanin; int i; if ( Abc_NodeIsTravIdCurrent(pObj) ) return; Abc_NodeSetTravIdCurrent( pObj ); if ( Abc_ObjIsCi(pObj) ) { Vec_PtrPush( vCone, pObj ); return; } assert( Abc_ObjIsNode(pObj) ); // visit the fanins of the node Abc_ObjForEachFanin( pObj, pFanin, i ) Abc_MfsWinMarkTfi_rec( pFanin, vCone ); Vec_PtrPush( vCone, pObj ); } /**Function************************************************************* Synopsis [Marks and collects the TFI cone of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Abc_MfsWinMarkTfi( Abc_Obj_t * pNode ) { Vec_Ptr_t * vCone; vCone = Vec_PtrAlloc( 100 ); Abc_MfsWinMarkTfi_rec( pNode, vCone ); return vCone; } /**Function************************************************************* Synopsis [Marks the TFO of the collected nodes up to the given level.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_MfsWinSweepLeafTfo_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 ) Abc_MfsWinSweepLeafTfo_rec( pFanout, nLevelLimit ); } /**Function************************************************************* Synopsis [Dereferences the node's MFFC.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_MfsNodeDeref_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 += Abc_MfsNodeDeref_rec( pFanin ); } return Counter; } /**Function************************************************************* Synopsis [References the node's MFFC.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_MfsNodeRef_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 += Abc_MfsNodeRef_rec( pFanin ); } return Counter; } /**Function************************************************************* Synopsis [Labels MFFC of the node with the current trav ID.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_MfsWinVisitMffc( Abc_Obj_t * pNode ) { int Count1, Count2; assert( Abc_ObjIsNode(pNode) ); // dereference the node (mark with the current trav ID) Count1 = Abc_MfsNodeDeref_rec( pNode ); // reference it back Count2 = Abc_MfsNodeRef_rec( pNode ); assert( Count1 == Count2 ); return Count1; } /**Function************************************************************* Synopsis [Computes divisors and add them to nodes in the window.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Abc_MfsComputeDivisors( Mfs_Man_t * p, Abc_Obj_t * pNode, int nLevDivMax ) { Vec_Ptr_t * vCone, * vDivs; Abc_Obj_t * pObj, * pFanout, * pFanin; int k, f, m; int nDivsPlus = 0, nTrueSupp; assert( p->vDivs == NULL ); // mark the TFI with the current trav ID Abc_NtkIncrementTravId( pNode->pNtk ); vCone = Abc_MfsWinMarkTfi( pNode ); // count the number of PIs nTrueSupp = 0; Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, k ) nTrueSupp += Abc_ObjIsCi(pObj); // printf( "%d(%d) ", Vec_PtrSize(p->vSupp), m ); // 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( pNode->pNtk ); Abc_MfsWinSweepLeafTfo_rec( pNode, nLevDivMax ); // Abc_MfsWinVisitMffc( pNode ); Abc_ObjForEachFanin( 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 vDivs = Vec_PtrAlloc( p->pPars->nWinMax ); Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, k ) { if ( !Abc_NodeIsTravIdPrevious(pObj) ) continue; if ( (int)pObj->Level > nLevDivMax ) continue; Vec_PtrPush( vDivs, pObj ); if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax ) break; } Vec_PtrFree( vCone ); // explore the fanouts of already collected divisors if ( Vec_PtrSize(vDivs) < p->pPars->nWinMax ) Vec_PtrForEachEntry( Abc_Obj_t *, vDivs, pObj, k ) { // consider fanouts of this node Abc_ObjForEachFanout( pObj, pFanout, f ) { // stop if there are too many fanouts if ( p->pPars->nFanoutsMax && f > p->pPars->nFanoutsMax ) 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 > nLevDivMax ) continue; // skip nodes whose fanins are not divisors -- here we skip more than we need to skip!!! (revise later) August 7, 2009 Abc_ObjForEachFanin( pFanout, pFanin, m ) if ( !Abc_NodeIsTravIdPrevious(pFanin) ) break; if ( m < Abc_ObjFaninNum(pFanout) ) continue; // make sure this divisor in not among the nodes // Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodes, pFanin, m ) // assert( pFanout != pFanin ); // add the node to the divisors Vec_PtrPush( vDivs, pFanout ); // Vec_PtrPush( p->vNodes, pFanout ); Vec_PtrPushUnique( p->vNodes, pFanout ); Abc_NodeSetTravIdPrevious( pFanout ); nDivsPlus++; if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax ) break; } if ( Vec_PtrSize(vDivs) >= p->pPars->nWinMax ) break; } p->nMaxDivs += (Vec_PtrSize(vDivs) >= p->pPars->nWinMax); // sort the divisors by level in the increasing order Vec_PtrSort( vDivs, (int (*)(void))Abc_NodeCompareLevelsIncrease ); // add the fanins of the node Abc_ObjForEachFanin( pNode, pFanin, k ) Vec_PtrPush( vDivs, pFanin ); /* printf( "Node level = %d. ", Abc_ObjLevel(p->pNode) ); Vec_PtrForEachEntryStart( Abc_Obj_t *, vDivs, pObj, k, Vec_PtrSize(vDivs)-p->nDivsPlus ) printf( "%d ", Abc_ObjLevel(pObj) ); printf( "\n" ); */ //printf( "%d ", p->nDivsPlus ); // printf( "(%d+%d)(%d+%d+%d) ", Vec_PtrSize(p->vSupp), Vec_PtrSize(p->vNodes), // nTrueSupp, Vec_PtrSize(vDivs)-nTrueSupp-nDivsPlus, nDivsPlus ); return vDivs; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END