diff options
Diffstat (limited to 'src/opt/ret/retArea.c')
| -rw-r--r-- | src/opt/ret/retArea.c | 540 |
1 files changed, 0 insertions, 540 deletions
diff --git a/src/opt/ret/retArea.c b/src/opt/ret/retArea.c deleted file mode 100644 index 5eec8e80..00000000 --- a/src/opt/ret/retArea.c +++ /dev/null @@ -1,540 +0,0 @@ -/**CFile**************************************************************** - - FileName [retArea.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Retiming package.] - - Synopsis [Min-area retiming.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - Oct 31, 2006.] - - Revision [$Id: retArea.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "retInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -static Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose ); -static void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward ); -static void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ); -static Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ); -static void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ); - -extern Abc_Ntk_t * Abc_NtkAttachBottom( Abc_Ntk_t * pNtkTop, Abc_Ntk_t * pNtkBottom ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Performs min-area retiming.] - - Description [Returns the number of latches reduced.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose ) -{ - Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom; - Vec_Int_t * vValuesNew = NULL, * vValues; - int nLatches = Abc_NtkLatchNum(pNtk); - int fOneFrame = 0; - assert( !fForwardOnly || !fBackwardOnly ); - // there should not be black boxes - assert( Abc_NtkIsSopLogic(pNtk) ); - assert( Abc_NtkLatchNum(pNtk) == Vec_PtrSize(pNtk->vBoxes) ); - // reorder CI/CO/latch inputs - Abc_NtkOrderCisCos( pNtk ); - // perform forward retiming - if ( !fBackwardOnly ) - { - if ( fOneFrame ) - Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose ); - else - while ( Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose ) ); - } - // remember initial values - vValues = Abc_NtkCollectLatchValues( pNtk ); - // perform backward retiming - if ( !fForwardOnly ) - { - if ( fOneFrame ) - pNtkTotal = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose ); - else - while ( pNtkBottom = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose ) ) - pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom ); - } - // compute initial values - vValuesNew = Abc_NtkRetimeInitialValues( pNtkTotal, vValues, fVerbose ); - if ( pNtkTotal ) Abc_NtkDelete( pNtkTotal ); - // insert new initial values - Abc_NtkInsertLatchValues( pNtk, vValuesNew ); - if ( vValuesNew ) Vec_IntFree( vValuesNew ); - if ( vValues ) Vec_IntFree( vValues ); - // fix the COs (this changes the circuit structure) -// Abc_NtkLogicMakeSimpleCos( pNtk, 0 ); - // check for correctness - if ( !Abc_NtkCheck( pNtk ) ) - fprintf( stdout, "Abc_NtkRetimeMinArea(): Network check has failed.\n" ); - // return the number of latches saved - return nLatches - Abc_NtkLatchNum(pNtk); -} - -/**Function************************************************************* - - Synopsis [Performs min-area retiming backward.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose ) -{ - Abc_Ntk_t * pNtkNew = NULL; - Vec_Ptr_t * vMinCut; - int nLatches = Abc_NtkLatchNum(pNtk); - // mark current latches and TFI(POs) - Abc_NtkRetimeMinAreaPrepare( pNtk, fForward ); - // run the maximum forward flow - vMinCut = Abc_NtkMaxFlow( pNtk, fForward, fVerbose ); -// assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) ); - // create new latch boundary if there is improvement - if ( Vec_PtrSize(vMinCut) < Abc_NtkLatchNum(pNtk) ) - { - pNtkNew = (Abc_Ntk_t *)1; - if ( fForward ) - Abc_NtkRetimeMinAreaInitValues( pNtk, vMinCut ); - else - pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut ); - Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, fForward ); - } - // clean up - Vec_PtrFree( vMinCut ); - Abc_NtkCleanMarkA( pNtk ); - return pNtkNew; -} - -/**Function************************************************************* - - Synopsis [Marks the cone with MarkA.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward ) -{ - Abc_Obj_t * pNext; - int i; - if ( pObj->fMarkA ) - return; - pObj->fMarkA = 1; - if ( fForward ) - { - Abc_ObjForEachFanout( pObj, pNext, i ) - Abc_NtkMarkCone_rec( pNext, fForward ); - } - else - { - Abc_ObjForEachFanin( pObj, pNext, i ) - Abc_NtkMarkCone_rec( pNext, fForward ); - } -} - -/**Function************************************************************* - - Synopsis [Marks the cone with MarkA.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkUnmarkCone_rec( Abc_Obj_t * pObj, int fForward ) -{ - Abc_Obj_t * pNext; - int i; - if ( !pObj->fMarkA || Abc_ObjIsLatch(pObj) ) - return; - pObj->fMarkA = 0; - if ( fForward ) - { - Abc_ObjForEachFanout( pObj, pNext, i ) - Abc_NtkUnmarkCone_rec( pNext, fForward ); - } - else - { - Abc_ObjForEachFanin( pObj, pNext, i ) - Abc_NtkUnmarkCone_rec( pNext, fForward ); - } -} - -/**Function************************************************************* - - Synopsis [Prepares the network for running MaxFlow.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward ) -{ - Vec_Ptr_t * vNodes; - Abc_Obj_t * pObj, * pFanin; - int i, k; - if ( fForward ) - { - // mark the frontier - Abc_NtkForEachPo( pNtk, pObj, i ) - pObj->fMarkA = 1; - Abc_NtkForEachLatch( pNtk, pObj, i ) - { - pObj->fMarkA = 1; - Abc_ObjFanin0(pObj)->fMarkA = 1; - } - // mark the nodes reachable from the PIs - Abc_NtkForEachPi( pNtk, pObj, i ) - Abc_NtkMarkCone_rec( pObj, fForward ); - // collect the unmarked fanins of the marked nodes - vNodes = Vec_PtrAlloc( 100 ); - Abc_NtkForEachObj( pNtk, pObj, i ) - if ( pObj->fMarkA ) - Abc_ObjForEachFanin( pObj, pFanin, k ) - if ( !pFanin->fMarkA ) - Vec_PtrPush( vNodes, pFanin ); - // mark these nodes - Vec_PtrForEachEntry( vNodes, pObj, i ) - pObj->fMarkA = 1; - Vec_PtrFree( vNodes ); - } - else - { - // mark the frontier - Abc_NtkForEachPi( pNtk, pObj, i ) - pObj->fMarkA = 1; - Abc_NtkForEachLatch( pNtk, pObj, i ) - { - pObj->fMarkA = 1; - Abc_ObjFanout0(pObj)->fMarkA = 1; - } - // mark the nodes reachable from the POs - Abc_NtkForEachPo( pNtk, pObj, i ) - Abc_NtkMarkCone_rec( pObj, fForward ); - } -} - -/**Function************************************************************* - - Synopsis [Compute initial values.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeMinAreaInitValues_rec( Abc_Obj_t * pObj ) -{ - Abc_Obj_t * pFanin; - int i; - // skip visited nodes - if ( Abc_NodeIsTravIdCurrent(pObj) ) - return (int)pObj->pCopy; - Abc_NodeSetTravIdCurrent(pObj); - // consider the case of a latch output - if ( Abc_ObjIsBo(pObj) ) - { - assert( Abc_ObjIsLatch(Abc_ObjFanin0(pObj)) ); - pObj->pCopy = (void *)Abc_NtkRetimeMinAreaInitValues_rec( Abc_ObjFanin0(pObj) ); - return (int)pObj->pCopy; - } - assert( Abc_ObjIsNode(pObj) ); - // visit the fanins - Abc_ObjForEachFanin( pObj, pFanin, i ) - Abc_NtkRetimeMinAreaInitValues_rec( pFanin ); - // compute the value of the node - pObj->pCopy = (void *)Abc_ObjSopSimulate(pObj); - return (int)pObj->pCopy; -} - -/**Function************************************************************* - - Synopsis [Compute initial values.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ) -{ - Abc_Obj_t * pObj; - int i; - // transfer initial values to pCopy and mark the latches - Abc_NtkIncrementTravId(pNtk); - Abc_NtkForEachLatch( pNtk, pObj, i ) - { - pObj->pCopy = (void *)Abc_LatchIsInit1(pObj); - Abc_NodeSetTravIdCurrent( pObj ); - } - // propagate initial values - Vec_PtrForEachEntry( vMinCut, pObj, i ) - Abc_NtkRetimeMinAreaInitValues_rec( pObj ); - // unmark the latches - Abc_NtkForEachLatch( pNtk, pObj, i ) - Abc_NodeSetTravIdPrevious( pObj ); -} - -/**Function************************************************************* - - Synopsis [Performs min-area retiming backward.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj ) -{ - Abc_Obj_t * pFanin; - int i; - // skip visited nodes - if ( Abc_NodeIsTravIdCurrent(pObj) ) - return pObj->pCopy; - Abc_NodeSetTravIdCurrent(pObj); - // consider the case of a latch output - if ( Abc_ObjIsBi(pObj) ) - { - pObj->pCopy = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) ); - return pObj->pCopy; - } - assert( Abc_ObjIsNode(pObj) ); - // visit the fanins - Abc_ObjForEachFanin( pObj, pFanin, i ) - Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, pFanin ); - // compute the value of the node - Abc_NtkDupObj( pNtkNew, pObj, 0 ); - Abc_ObjForEachFanin( pObj, pFanin, i ) - Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy ); - return pObj->pCopy; -} - -/**Function************************************************************* - - Synopsis [Creates the network from computing initial state.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ) -{ - Abc_Ntk_t * pNtkNew; - Abc_Obj_t * pObj, * pObjNew; - int i; - // create new network - pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 ); - // map new latches into PIs of the new network - Abc_NtkIncrementTravId(pNtk); - Vec_PtrForEachEntry( vMinCut, pObj, i ) - { - pObj->pCopy = Abc_NtkCreatePi(pNtkNew); - Abc_NodeSetTravIdCurrent( pObj ); - } - // construct the network recursively - Abc_NtkForEachLatch( pNtk, pObj, i ) - { - pObjNew = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) ); - Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObjNew ); - } - // unmark the nodes in the cut - Vec_PtrForEachEntry( vMinCut, pObj, i ) - Abc_NodeSetTravIdPrevious( pObj ); - // unmark the latches - Abc_NtkForEachLatch( pNtk, pObj, i ) - Abc_NodeSetTravIdPrevious( pObj ); - // assign dummy node names - Abc_NtkAddDummyPiNames( pNtkNew ); - Abc_NtkAddDummyPoNames( pNtkNew ); - if ( !Abc_NtkCheck( pNtkNew ) ) - fprintf( stdout, "Abc_NtkRetimeMinAreaConstructNtk(): Network check has failed.\n" ); - return pNtkNew; -} - -/**Function************************************************************* - - Synopsis [Updates the network after backward retiming.] - - Description [Assumes that fMarkA denotes all nodes reachabe from - the latches toward the cut.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) -{ - Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes, * vBuffers; - Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext, * pBuffer; - int i, k; - // create new latches - Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) ); - Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) ); - vCis = pNtk->vCis; pNtk->vCis = NULL; - vCos = pNtk->vCos; pNtk->vCos = NULL; - vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL; - // transfer boxes - vBoxesNew = Vec_PtrAlloc(100); - Vec_PtrForEachEntry( vBoxes, pObj, i ) - if ( !Abc_ObjIsLatch(pObj) ) - Vec_PtrPush( vBoxesNew, pObj ); - // create or reuse latches - vNodes = Vec_PtrAlloc( 100 ); - vBuffers = Vec_PtrAlloc( 100 ); - Vec_PtrForEachEntry( vMinCut, pObj, i ) - { - if ( Abc_ObjIsCi(pObj) && fForward ) - { - pLatchOut = pObj; - pLatch = Abc_ObjFanin0(pLatchOut); - pLatchIn = Abc_ObjFanin0(pLatch); - assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) ); - // mark the latch as reused - Abc_NodeSetTravIdCurrent( pLatch ); - - // check if there are marked fanouts - // (these are fanouts to be connected to the latch input) - Abc_ObjForEachFanout( pObj, pNext, k ) - if ( pNext->fMarkA ) - break; - if ( k < Abc_ObjFanoutNum(pObj) ) - { - // add the buffer - pBuffer = Abc_NtkCreateNodeBuf( pNtk, Abc_ObjFanin0(pLatchIn) ); - Abc_ObjPatchFanin( pLatchIn, Abc_ObjFanin0(pLatchIn), pBuffer ); - Vec_PtrPush( vBuffers, pBuffer ); - // redirect edges to the unvisited fanouts of the node - Abc_NodeCollectFanouts( pObj, vNodes ); - Vec_PtrForEachEntry( vNodes, pNext, k ) - if ( pNext->fMarkA ) - Abc_ObjPatchFanin( pNext, pObj, pBuffer ); - } - assert( Abc_ObjFanoutNum(pObj) > 0 ); -// if ( Abc_ObjFanoutNum(pObj) == 0 ) -// Abc_NtkDeleteObj_rec( pObj, 0 ); - } - else if ( Abc_ObjIsCo(pObj) && !fForward ) - { - pLatchIn = pObj; - pLatch = Abc_ObjFanout0(pLatchIn); - pLatchOut = Abc_ObjFanout0(pLatch); - assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) ); - // mark the latch as reused - Abc_NodeSetTravIdCurrent( pLatch ); - assert( !Abc_ObjFanin0(pLatchIn)->fMarkA ); - } - else - { - pLatchOut = Abc_NtkCreateBo(pNtk); - pLatch = Abc_NtkCreateLatch(pNtk); - pLatchIn = Abc_NtkCreateBi(pNtk); - Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" ); - Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" ); - // connect - Abc_ObjAddFanin( pLatchOut, pLatch ); - Abc_ObjAddFanin( pLatch, pLatchIn ); - if ( fForward ) - { - pLatch->pData = (void *)(pObj->pCopy? ABC_INIT_ONE : ABC_INIT_ZERO); - // redirect edges to the unvisited fanouts of the node - Abc_NodeCollectFanouts( pObj, vNodes ); - Vec_PtrForEachEntry( vNodes, pNext, k ) - if ( !pNext->fMarkA ) - Abc_ObjPatchFanin( pNext, pObj, pLatchOut ); - } - else - { - // redirect edges to the visited fanouts of the node - Abc_NodeCollectFanouts( pObj, vNodes ); - Vec_PtrForEachEntry( vNodes, pNext, k ) - if ( pNext->fMarkA ) - Abc_ObjPatchFanin( pNext, pObj, pLatchOut ); - } - // connect latch to the node - Abc_ObjAddFanin( pLatchIn, pObj ); - } - Vec_PtrPush( vCis, pLatchOut ); - Vec_PtrPush( vBoxesNew, pLatch ); - Vec_PtrPush( vCos, pLatchIn ); - } - Vec_PtrFree( vNodes ); - // remove buffers - Vec_PtrForEachEntry( vBuffers, pObj, i ) - { - Abc_ObjTransferFanout( pObj, Abc_ObjFanin0(pObj) ); - Abc_NtkDeleteObj( pObj ); - } - Vec_PtrFree( vBuffers ); - // remove useless latches - Vec_PtrForEachEntry( vBoxes, pObj, i ) - { - if ( !Abc_ObjIsLatch(pObj) ) - continue; - if ( Abc_NodeIsTravIdCurrent(pObj) ) - continue; - pLatchOut = Abc_ObjFanout0(pObj); - pLatch = pObj; - pLatchIn = Abc_ObjFanin0(pObj); - if ( Abc_ObjFanoutNum(pLatchOut) > 0 ) - Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) ); - Abc_NtkDeleteObj( pLatchOut ); - Abc_NtkDeleteObj( pObj ); - Abc_NtkDeleteObj( pLatchIn ); - } - // set the arrays - pNtk->vCis = vCis; - pNtk->vCos = vCos; - pNtk->vBoxes = vBoxesNew; - Vec_PtrFree( vBoxes ); -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |