diff options
Diffstat (limited to 'src/opt/ret/retArea.c')
| -rw-r--r-- | src/opt/ret/retArea.c | 540 |
1 files changed, 540 insertions, 0 deletions
diff --git a/src/opt/ret/retArea.c b/src/opt/ret/retArea.c new file mode 100644 index 00000000..5eec8e80 --- /dev/null +++ b/src/opt/ret/retArea.c @@ -0,0 +1,540 @@ +/**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 /// +//////////////////////////////////////////////////////////////////////// + + |