From 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 08:01:00 -0800 Subject: Version abc80130 --- src/map/if/ifUtil.c | 658 ---------------------------------------------------- 1 file changed, 658 deletions(-) delete mode 100644 src/map/if/ifUtil.c (limited to 'src/map/if/ifUtil.c') diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c deleted file mode 100644 index 2624efd0..00000000 --- a/src/map/if/ifUtil.c +++ /dev/null @@ -1,658 +0,0 @@ -/**CFile**************************************************************** - - FileName [ifUtil.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [FPGA mapping based on priority cuts.] - - Synopsis [Various utilities.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - November 21, 2006.] - - Revision [$Id: ifUtil.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "if.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Sets all the node copy to NULL.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanNodeCopy( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - If_ObjSetCopy( pObj, NULL ); -} - -/**Function************************************************************* - - Synopsis [Sets all the cut data to NULL.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanCutData( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - If_CutSetData( If_ObjCutBest(pObj), NULL ); -} - -/**Function************************************************************* - - Synopsis [Sets all visited marks to 0.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManCleanMarkV( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - pObj->fVisit = 0; -} - -/**Function************************************************************* - - Synopsis [Returns the max delay of the POs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManDelayMax( If_Man_t * p, int fSeq ) -{ - If_Obj_t * pObj; - float DelayBest; - int i; - if ( p->pPars->fLatchPaths && p->pPars->nLatches == 0 ) - { - printf( "Delay optimization of latch path is not performed because there is no latches.\n" ); - p->pPars->fLatchPaths = 0; - } - DelayBest = -IF_FLOAT_LARGE; - if ( fSeq ) - { - assert( p->pPars->nLatches > 0 ); - If_ManForEachPo( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - else if ( p->pPars->fLatchPaths ) - { - If_ManForEachLatchInput( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - else - { - If_ManForEachCo( p, pObj, i ) - if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) ) - DelayBest = If_ObjArrTime(If_ObjFanin0(pObj)); - } - return DelayBest; -} - -/**Function************************************************************* - - Synopsis [Computes the required times of all nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManComputeRequired( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i, Counter; - float reqTime; - - // compute area, clean required times, collect nodes used in the mapping -// p->AreaGlo = If_ManScanMapping( p ); - If_ManMarkMapping( p ); - - if ( p->pManTim == NULL ) - { - // consider the case when the required times are given - if ( p->pPars->pTimesReq ) - { - assert( !p->pPars->fAreaOnly ); - // make sure that the required time hold - Counter = 0; - If_ManForEachCo( p, pObj, i ) - { - if ( If_ObjArrTime(If_ObjFanin0(pObj)) > p->pPars->pTimesReq[i] + p->fEpsilon ) - { - Counter++; - // printf( "Required times are violated for output %d (arr = %d; req = %d).\n", - // i, (int)If_ObjArrTime(If_ObjFanin0(pObj)), (int)p->pPars->pTimesReq[i] ); - } - If_ObjFanin0(pObj)->Required = p->pPars->pTimesReq[i]; - } - if ( Counter ) - printf( "Required times are violated for %d outputs.\n", Counter ); - } - else - { - // get the global required times - p->RequiredGlo = If_ManDelayMax( p, 0 ); - // update the required times according to the target - if ( p->pPars->DelayTarget != -1 ) - { - if ( p->RequiredGlo > p->pPars->DelayTarget + p->fEpsilon ) - { - if ( p->fNextRound == 0 ) - { - p->fNextRound = 1; - printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->pPars->DelayTarget ); - } - } - else if ( p->RequiredGlo < p->pPars->DelayTarget - p->fEpsilon ) - { - if ( p->fNextRound == 0 ) - { - p->fNextRound = 1; - printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget ); - } - p->RequiredGlo = p->pPars->DelayTarget; - } - } - // do not propagate required times if area minimization is requested - if ( p->pPars->fAreaOnly ) - return; - // set the required times for the POs - if ( p->pPars->fLatchPaths ) - { - If_ManForEachLatchInput( p, pObj, i ) - If_ObjFanin0(pObj)->Required = p->RequiredGlo; - } - else - { - If_ManForEachCo( p, pObj, i ) - If_ObjFanin0(pObj)->Required = p->RequiredGlo; - } - } - // go through the nodes in the reverse topological order - // Vec_PtrForEachEntry( p->vMapped, pObj, i ) - // If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); - If_ManForEachObjReverse( p, pObj, i ) - { - if ( pObj->nRefs == 0 ) - continue; - If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); - } - } - else - { - // get the global required times - p->RequiredGlo = If_ManDelayMax( p, 0 ); - // do not propagate required times if area minimization is requested - if ( p->pPars->fAreaOnly ) - return; - // set the required times for the POs - Tim_ManIncrementTravId( p->pManTim ); - if ( p->pPars->fLatchPaths ) - { - assert( 0 ); - If_ManForEachPo( p, pObj, i ) - Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, IF_FLOAT_LARGE ); - If_ManForEachLatchInput( p, pObj, i ) - Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo ); - } - else - { - Tim_ManSetPoRequiredAll( p->pManTim, p->RequiredGlo ); -// If_ManForEachCo( p, pObj, i ) -// Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo ); - } - // go through the nodes in the reverse topological order - If_ManForEachObjReverse( p, pObj, i ) - { - if ( If_ObjIsAnd(pObj) ) - { - if ( pObj->nRefs == 0 ) - continue; - If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required ); - } - else if ( If_ObjIsCi(pObj) ) - { - reqTime = pObj->Required; - Tim_ManSetPiRequired( p->pManTim, pObj->IdPio, reqTime ); - } - else if ( If_ObjIsCo(pObj) ) - { - reqTime = Tim_ManGetPoRequired( p->pManTim, pObj->IdPio ); - If_ObjFanin0(pObj)->Required = IF_MIN( reqTime, If_ObjFanin0(pObj)->Required ); - } - else if ( If_ObjIsConst1(pObj) ) - { - } - else // add the node to the mapper - assert( 0 ); - } - } -} - -#if 0 - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMapping_rec( If_Man_t * p, If_Obj_t * pObj, If_Obj_t ** ppStore ) -{ - If_Obj_t * pLeaf; - If_Cut_t * pCutBest; - float aArea; - int i; - if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) ) - return 0.0; - // store the node in the structure by level - assert( If_ObjIsAnd(pObj) ); - pObj->pCopy = (char *)ppStore[pObj->Level]; - ppStore[pObj->Level] = pObj; - // visit the transitive fanin of the selected cut - pCutBest = If_ObjCutBest(pObj); - p->nNets += pCutBest->nLeaves; - aArea = If_CutLutArea( p, pCutBest ); - If_CutForEachLeaf( p, pCutBest, pLeaf, i ) - aArea += If_ManScanMapping_rec( p, pLeaf, ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMapping( If_Man_t * p ) -{ - If_Obj_t * pObj, ** ppStore; - float aArea; - int i; - assert( !p->pPars->fLiftLeaves ); - // clean all references - p->nNets = 0; - If_ManForEachObj( p, pObj, i ) - { - pObj->Required = IF_FLOAT_LARGE; - pObj->nVisits = pObj->nVisitsCopy; - pObj->nRefs = 0; - } - // allocate place to store the nodes - ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 ); - memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) ); - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - If_ManForEachCo( p, pObj, i ) - aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore ); - // reconnect the nodes in reverse topological order - Vec_PtrClear( p->vMapped ); - for ( i = p->nLevelMax; i >= 0; i-- ) - for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy ) - Vec_PtrPush( p->vMapped, pObj ); - free( ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMappingDirect( If_Man_t * p ) -{ - If_Obj_t * pObj, ** ppStore; - float aArea; - int i; - assert( !p->pPars->fLiftLeaves ); - // clean all references - If_ManForEachObj( p, pObj, i ) - { - pObj->Required = IF_FLOAT_LARGE; - pObj->nVisits = pObj->nVisitsCopy; - pObj->nRefs = 0; - } - // allocate place to store the nodes - ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 ); - memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) ); - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - If_ManForEachCo( p, pObj, i ) - aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore ); - // reconnect the nodes in reverse topological order - Vec_PtrClear( p->vMapped ); -// for ( i = p->nLevelMax; i >= 0; i-- ) - for ( i = 0; i <= p->nLevelMax; i++ ) - for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy ) - Vec_PtrPush( p->vMapped, pObj ); - free( ppStore ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMappingSeq_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vMapped ) -{ - If_Obj_t * pLeaf; - If_Cut_t * pCutBest; - float aArea; - int i, Shift; - // treat latches transparently - if ( If_ObjIsLatch(pObj) ) - return If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), vMapped ); - // consider trivial cases - if ( pObj->nRefs++ || If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) ) - return 0.0; - // store the node in the structure by level - assert( If_ObjIsAnd(pObj) ); - // visit the transitive fanin of the selected cut - pCutBest = If_ObjCutBest(pObj); - aArea = If_ObjIsAnd(pObj)? If_CutLutArea(p, pCutBest) : (float)0.0; - If_CutForEachLeafSeq( p, pCutBest, pLeaf, Shift, i ) - aArea += If_ManScanMappingSeq_rec( p, pLeaf, vMapped ); - // add the node - Vec_PtrPush( vMapped, pObj ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManScanMappingSeq( If_Man_t * p ) -{ - If_Obj_t * pObj; - float aArea; - int i; - assert( p->pPars->fLiftLeaves ); - // clean all references - If_ManForEachObj( p, pObj, i ) - pObj->nRefs = 0; - // collect nodes reachable from POs in the DFS order through the best cuts - aArea = 0; - Vec_PtrClear( p->vMapped ); - If_ManForEachPo( p, pObj, i ) - aArea += If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), p->vMapped ); - return aArea; -} - -#endif - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [Collects the nodes in reverse topological order in array - p->vMapping.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManResetOriginalRefs( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - pObj->nRefs = 0; - If_ManForEachObj( p, pObj, i ) - { - if ( If_ObjIsAnd(pObj) ) - { - pObj->pFanin0->nRefs++; - pObj->pFanin1->nRefs++; - } - else if ( If_ObjIsCo(pObj) ) - pObj->pFanin0->nRefs++; - } -} - -/**Function************************************************************* - - Synopsis [Computes cross-cut of the circuit.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_ManCrossCut( If_Man_t * p ) -{ - If_Obj_t * pObj, * pFanin; - int i, nCutSize = 0, nCutSizeMax = 0; - If_ManForEachObj( p, pObj, i ) - { - if ( !If_ObjIsAnd(pObj) ) - continue; - // consider the node - if ( nCutSizeMax < ++nCutSize ) - nCutSizeMax = nCutSize; - if ( pObj->nVisits == 0 ) - nCutSize--; - // consider the fanins - pFanin = If_ObjFanin0(pObj); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - pFanin = If_ObjFanin1(pObj); - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - // consider the choice class - if ( pObj->fRepr ) - for ( pFanin = pObj; pFanin; pFanin = pFanin->pEquiv ) - if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 ) - nCutSize--; - } - If_ManForEachObj( p, pObj, i ) - { - assert( If_ObjIsCi(pObj) || pObj->fVisit == 0 ); - pObj->nVisits = pObj->nVisitsCopy; - } - assert( nCutSize == 0 ); -// printf( "Max cross cut size = %6d.\n", nCutSizeMax ); - return nCutSizeMax; -} - -/**Function************************************************************* - - Synopsis [Computes the reverse topological order of nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p ) -{ - Vec_Ptr_t * vOrder; - If_Obj_t * pObj, ** ppStore; - int i; - // allocate place to store the nodes - ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 ); - memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) ); - // add the nodes - If_ManForEachObj( p, pObj, i ) - { - assert( pObj->Level >= 0 && pObj->Level <= (unsigned)p->nLevelMax ); - pObj->pCopy = (char *)ppStore[pObj->Level]; - ppStore[pObj->Level] = pObj; - } - vOrder = Vec_PtrAlloc( If_ManObjNum(p) ); - for ( i = p->nLevelMax; i >= 0; i-- ) - for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy ) - Vec_PtrPush( vOrder, pObj ); - free( ppStore ); - // print the order -// Vec_PtrForEachEntry( vOrder, pObj, i ) -// printf( "Obj %2d Type %d Level = %d\n", pObj->Id, pObj->Type, pObj->Level ); - return vOrder; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -float If_ManMarkMapping_rec( If_Man_t * p, If_Obj_t * pObj ) -{ - If_Obj_t * pLeaf; - If_Cut_t * pCutBest; - float aArea; - int i; - if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) ) - return 0.0; - // store the node in the structure by level - assert( If_ObjIsAnd(pObj) ); - // visit the transitive fanin of the selected cut - pCutBest = If_ObjCutBest(pObj); - p->nNets += pCutBest->nLeaves; - aArea = If_CutLutArea( p, pCutBest ); - If_CutForEachLeaf( p, pCutBest, pLeaf, i ) - aArea += If_ManMarkMapping_rec( p, pLeaf ); - return aArea; -} - -/**Function************************************************************* - - Synopsis [Computes area, references, and nodes used in the mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManMarkMapping( If_Man_t * p ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachObj( p, pObj, i ) - { - pObj->Required = IF_FLOAT_LARGE; - pObj->nVisits = pObj->nVisitsCopy; - pObj->nRefs = 0; - } - p->nNets = 0; - p->AreaGlo = 0.0; - If_ManForEachCo( p, pObj, i ) - p->AreaGlo += If_ManMarkMapping_rec( p, If_ObjFanin0(pObj) ); -} - -/**Function************************************************************* - - Synopsis [Collects nodes used in the mapping in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p ) -{ - Vec_Ptr_t * vOrder; - If_Obj_t * pObj; - int i; - If_ManMarkMapping( p ); - vOrder = Vec_PtrAlloc( If_ManObjNum(p) ); - If_ManForEachObj( p, pObj, i ) - if ( If_ObjIsAnd(pObj) && pObj->nRefs ) - Vec_PtrPush( vOrder, pObj ); - return vOrder; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -- cgit v1.2.3