diff options
Diffstat (limited to 'src/opt/ret')
| -rw-r--r-- | src/opt/ret/module.make | 8 | ||||
| -rw-r--r-- | src/opt/ret/retArea.c | 540 | ||||
| -rw-r--r-- | src/opt/ret/retCore.c | 132 | ||||
| -rw-r--r-- | src/opt/ret/retDelay.c | 305 | ||||
| -rw-r--r-- | src/opt/ret/retFlow.c | 783 | ||||
| -rw-r--r-- | src/opt/ret/retIncrem.c | 464 | ||||
| -rw-r--r-- | src/opt/ret/retInit.c | 349 | ||||
| -rw-r--r-- | src/opt/ret/retInt.h | 80 | ||||
| -rw-r--r-- | src/opt/ret/retLvalue.c | 395 | ||||
| -rw-r--r-- | src/opt/ret/ret_.c | 48 |
10 files changed, 3104 insertions, 0 deletions
diff --git a/src/opt/ret/module.make b/src/opt/ret/module.make new file mode 100644 index 00000000..4b14365e --- /dev/null +++ b/src/opt/ret/module.make @@ -0,0 +1,8 @@ +SRC += src/opt/ret/retArea.c \ + src/opt/ret/retCore.c \ + src/opt/ret/retDelay.c \ + src/opt/ret/retFlow.c \ + src/opt/ret/retIncrem.c \ + src/opt/ret/retInit.c \ + src/opt/ret/retLvalue.c + 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 /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retCore.c b/src/opt/ret/retCore.c new file mode 100644 index 00000000..47b2cbbc --- /dev/null +++ b/src/opt/ret/retCore.c @@ -0,0 +1,132 @@ +/**CFile**************************************************************** + + FileName [retCore.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [The core retiming procedures.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retCore.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +int timeRetime = 0; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Implementation of retiming.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOnly, int fOneStep, int fVerbose ) +{ + int nLatches = Abc_NtkLatchNum(pNtk); + int nLevels = Abc_NtkLevel(pNtk); + int RetValue = 0, clkTotal = clock(); + int nNodesOld, nLatchesOld; + assert( Mode > 0 && Mode < 7 ); + assert( !fForwardOnly || !fBackwardOnly ); + + // cleanup the network + nNodesOld = Abc_NtkNodeNum(pNtk); + nLatchesOld = Abc_NtkLatchNum(pNtk); + Abc_NtkCleanupSeq(pNtk, 0, 0, 0); + if ( nNodesOld > Abc_NtkNodeNum(pNtk) || nLatchesOld > Abc_NtkLatchNum(pNtk) ) + printf( "Cleanup before retiming removed %d dangling nodes and %d dangling latches.\n", + nNodesOld - Abc_NtkNodeNum(pNtk), nLatchesOld - Abc_NtkLatchNum(pNtk) ); + + // perform retiming + switch ( Mode ) + { + case 1: // forward + RetValue = Abc_NtkRetimeIncremental( pNtk, 1, 0, 0, fVerbose ); + break; + case 2: // backward + RetValue = Abc_NtkRetimeIncremental( pNtk, 0, 0, 0, fVerbose ); + break; + case 3: // min-area + RetValue = Abc_NtkRetimeMinArea( pNtk, fForwardOnly, fBackwardOnly, fVerbose ); + break; + case 4: // min-delay + if ( !fBackwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 1, 1, fOneStep, fVerbose ); + if ( !fForwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 0, 1, fOneStep, fVerbose ); + break; + case 5: // min-area + min-delay + RetValue = Abc_NtkRetimeMinArea( pNtk, fForwardOnly, fBackwardOnly, fVerbose ); + if ( !fBackwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 1, 1, 0, fVerbose ); + if ( !fForwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 0, 1, 0, fVerbose ); + break; + case 6: // Pan's algorithm + RetValue = Abc_NtkRetimeLValue( pNtk, 500, fVerbose ); + break; + default: + printf( "Unknown retiming option.\n" ); + break; + } + if ( fVerbose ) + { + printf( "Reduction in area = %3d. Reduction in delay = %3d. ", + nLatches - Abc_NtkLatchNum(pNtk), nLevels - Abc_NtkLevel(pNtk) ); + PRT( "Total runtime", clock() - clkTotal ); + } + timeRetime = clock() - clkTotal; + return RetValue; +} + +/**Function************************************************************* + + Synopsis [Used for automated debugging.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeDebug( Abc_Ntk_t * pNtk ) +{ + extern int Abc_NtkSecFraig( Abc_Ntk_t * pNtk1, Abc_Ntk_t * pNtk2, int nSeconds, int nFrames, int fVerbose ); + Abc_Ntk_t * pNtkRet; + assert( Abc_NtkIsLogic(pNtk) ); + Abc_NtkToSop( pNtk, 0 ); +// if ( !Abc_NtkCheck( pNtk ) ) +// fprintf( stdout, "Abc_NtkRetimeDebug(): Network check has failed.\n" ); +// Io_WriteBlifLogic( pNtk, "debug_temp.blif", 1 ); + pNtkRet = Abc_NtkDup( pNtk ); + Abc_NtkRetime( pNtkRet, 3, 0, 1, 0, 0 ); // debugging backward flow + return !Abc_NtkSecFraig( pNtk, pNtkRet, 10000, 3, 0 ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retDelay.c b/src/opt/ret/retDelay.c new file mode 100644 index 00000000..bcfe3a2e --- /dev/null +++ b/src/opt/ret/retDelay.c @@ -0,0 +1,305 @@ +/**CFile**************************************************************** + + FileName [retDelay.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [Incremental retiming for optimum delay.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retDelay.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose ); +static int Abc_NtkRetimeTiming( Abc_Ntk_t * pNtk, int fForward, Vec_Ptr_t * vCritical ); +static int Abc_NtkRetimeTiming_rec( Abc_Obj_t * pObj, int fForward ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Retimes incrementally for minimum delay.] + + Description [This procedure cannot be called in the application code + because it assumes that the network is preprocessed by removing LIs/LOs.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nIterLimit, int fForward, int fVerbose ) +{ + int IterBest, DelayBest; + int IterBest2, DelayBest2; + // try to find the best delay iteration on a copy + DelayBest = Abc_NtkRetimeMinDelayTry( pNtkCopy, fForward, 0, nIterLimit, &IterBest, fVerbose ); + if ( IterBest == 0 ) + return 1; + // perform the given number of iterations on the original network + DelayBest2 = Abc_NtkRetimeMinDelayTry( pNtk, fForward, 1, IterBest, &IterBest2, fVerbose ); + assert( DelayBest == DelayBest2 ); + assert( IterBest == IterBest2 ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Returns the best delay and the number of best iteration.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose ) +{ + Abc_Ntk_t * pNtkNew = NULL; + Vec_Ptr_t * vCritical; + Vec_Int_t * vValues; + Abc_Obj_t * pObj; + int i, k, IterBest, DelayCur, DelayBest, DelayStart, LatchesBest; + // transfer intitial values + if ( fInitial ) + { + if ( fForward ) + Abc_NtkRetimeTranferToCopy( pNtk ); + else + { + // save initial value of the latches + vValues = Abc_NtkRetimeCollectLatchValues( pNtk ); + // start the network for initial value computation + pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk ); + } + } + +if ( fVerbose && !fInitial ) + printf( "Performing analysis:\n" ); + // find the best iteration + DelayBest = ABC_INFINITY; IterBest = 0; LatchesBest = Abc_NtkLatchNum(pNtk); + vCritical = Vec_PtrAlloc( 100 ); + for ( i = 0; ; i++ ) + { + // perform moves for the timing-critical nodes + DelayCur = Abc_NtkRetimeTiming( pNtk, fForward, vCritical ); + if ( i == 0 ) + DelayStart = DelayCur; + // record this position if it has the best delay + if ( DelayBest > DelayCur ) + { +if ( fVerbose && !fInitial ) + printf( "%s Iter = %3d. Delay = %3d. Latches = %5d. Delta = %6.2f. Ratio = %4.2f %%\n", + fForward ? "Fwd": "Bwd", i, DelayCur, Abc_NtkLatchNum(pNtk), + 1.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/(DelayBest-DelayCur), + 100.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/Abc_NtkLatchNum(pNtk)/(DelayBest-DelayCur) ); + + DelayBest = DelayCur; + IterBest = i; + LatchesBest = Abc_NtkLatchNum(pNtk); + } + // quit after timing analysis + if ( i == nIterLimit ) + break; + // skip if 10 interations did not give improvement + if ( i - IterBest > 20 ) + break; + // try retiming to improve the delay + Vec_PtrForEachEntry( vCritical, pObj, k ) + if ( Abc_NtkRetimeNodeIsEnabled(pObj, fForward) ) + Abc_NtkRetimeNode( pObj, fForward, fInitial ); + // share latches + if ( !fForward ) + Abc_NtkRetimeShareLatches( pNtk, fInitial ); + } + Vec_PtrFree( vCritical ); + // transfer the initial state back to the latches + if ( fInitial ) + { + if ( fForward ) + Abc_NtkRetimeTranferFromCopy( pNtk ); + else + { + Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose ); + Abc_NtkDelete( pNtkNew ); + Vec_IntFree( vValues ); + } + } +if ( fVerbose && !fInitial ) + printf( "%s : Starting delay = %3d. Final delay = %3d. IterBest = %2d (out of %2d).\n", + fForward? "Forward " : "Backward", DelayStart, DelayBest, IterBest, nIterLimit ); + *pIterBest = (nIterLimit == 1) ? 1 : IterBest; + return DelayBest; +} + +/**Function************************************************************* + + Synopsis [Returns the set of timing-critical nodes.] + + Description [Performs static timing analysis on the network. Uses + unit-delay model.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeTiming( Abc_Ntk_t * pNtk, int fForward, Vec_Ptr_t * vCritical ) +{ + Vec_Ptr_t * vLatches; + Abc_Obj_t * pObj, * pNext; + int i, k, LevelCur, LevelMax = 0; + // mark all objects except nodes + Abc_NtkIncrementTravId(pNtk); + vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( Abc_ObjIsLatch(pObj) ) + Vec_PtrPush( vLatches, pObj ); + if ( Abc_ObjIsNode(pObj) ) + continue; + pObj->Level = 0; + Abc_NodeSetTravIdCurrent( pObj ); + } + // perform analysis from CIs/COs + if ( fForward ) + { + Vec_PtrForEachEntry( vLatches, pObj, i ) + { + Abc_ObjForEachFanout( pObj, pNext, k ) + { + LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + } + Abc_NtkForEachPi( pNtk, pObj, i ) + { + Abc_ObjForEachFanout( pObj, pNext, k ) + { + LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + } + } + else + { + Vec_PtrForEachEntry( vLatches, pObj, i ) + { + LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + Abc_NtkForEachPo( pNtk, pObj, i ) + { + LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + } + // collect timing critical nodes, which should be retimed forward/backward + Vec_PtrClear( vCritical ); + Abc_NtkIncrementTravId(pNtk); + if ( fForward ) + { + Vec_PtrForEachEntry( vLatches, pObj, i ) + { + Abc_ObjForEachFanout( pObj, pNext, k ) + { + if ( Abc_NodeIsTravIdCurrent(pNext) ) + continue; + if ( LevelMax != (int)pNext->Level ) + continue; + // new critical node + Vec_PtrPush( vCritical, pNext ); + Abc_NodeSetTravIdCurrent( pNext ); + } + } + } + else + { + Vec_PtrForEachEntry( vLatches, pObj, i ) + { + Abc_ObjForEachFanin( pObj, pNext, k ) + { + if ( Abc_NodeIsTravIdCurrent(pNext) ) + continue; + if ( LevelMax != (int)pNext->Level ) + continue; + // new critical node + Vec_PtrPush( vCritical, pNext ); + Abc_NodeSetTravIdCurrent( pNext ); + } + } + } + Vec_PtrFree( vLatches ); + return LevelMax; +} + +/**Function************************************************************* + + Synopsis [Recursively performs timing analysis.] + + Description [Performs static timing analysis on the network. Uses + unit-delay model.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeTiming_rec( Abc_Obj_t * pObj, int fForward ) +{ + Abc_Obj_t * pNext; + int i, LevelCur, LevelMax = 0; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return pObj->Level; + Abc_NodeSetTravIdCurrent(pObj); + // visit the next nodes + if ( fForward ) + { + Abc_ObjForEachFanout( pObj, pNext, i ) + { + LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + } + else + { + Abc_ObjForEachFanin( pObj, pNext, i ) + { + LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward ); + if ( LevelMax < LevelCur ) + LevelMax = LevelCur; + } + } +// printf( "Node %3d -> Level %3d.\n", pObj->Id, LevelMax + 1 ); + pObj->Level = LevelMax + 1; + return pObj->Level; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retFlow.c b/src/opt/ret/retFlow.c new file mode 100644 index 00000000..47ee8516 --- /dev/null +++ b/src/opt/ret/retFlow.c @@ -0,0 +1,783 @@ +/**CFile**************************************************************** + + FileName [retFlow.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Implementation of maximum flow (min-area retiming).] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retFlow.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static inline int Abc_ObjSetPath( Abc_Obj_t * pObj, Abc_Obj_t * pNext ) { pObj->pCopy = pNext; return 1; } +static inline Abc_Obj_t * Abc_ObjGetPath( Abc_Obj_t * pObj ) { return pObj->pCopy; } +static inline Abc_Obj_t * Abc_ObjGetFanoutPath( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout; + int i; + assert( Abc_ObjGetPath(pObj) ); + Abc_ObjForEachFanout( pObj, pFanout, i ) + if ( Abc_ObjGetPath(pFanout) == pObj ) + return pFanout; + return NULL; +} +static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanin; + int i; + assert( Abc_ObjGetPath(pObj) ); + Abc_ObjForEachFanin( pObj, pFanin, i ) + if ( Abc_ObjGetPath(pFanin) == pObj ) + return pFanin; + return NULL; +} +static inline Abc_Obj_t * Abc_ObjGetPredecessorBwd( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + return NULL; +} +static inline Abc_Obj_t * Abc_ObjGetPredecessorFwd( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + return NULL; +} + +static int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ); +static int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ); +static int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj ); +static int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj ); +//static int Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj ); +static int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin ); +static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward ); +static void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ); +static int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ); +static void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ); +static void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Test-bench for the max-flow computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk ) +{ + Vec_Ptr_t * vMinCut; + Abc_Obj_t * pObj; + int i; + + // forward flow + Abc_NtkForEachPo( pNtk, pObj, i ) + pObj->fMarkA = 1; + Abc_NtkForEachLatch( pNtk, pObj, i ) + pObj->fMarkA = Abc_ObjFanin0(pObj)->fMarkA = 1; +// Abc_ObjFanin0(pObj)->fMarkA = 1; + vMinCut = Abc_NtkMaxFlow( pNtk, 1, 1 ); + Vec_PtrFree( vMinCut ); + Abc_NtkCleanMarkA( pNtk ); + + // backward flow + Abc_NtkForEachPi( pNtk, pObj, i ) + pObj->fMarkA = 1; + Abc_NtkForEachLatch( pNtk, pObj, i ) + pObj->fMarkA = Abc_ObjFanout0(pObj)->fMarkA = 1; +// Abc_ObjFanout0(pObj)->fMarkA = 1; + vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 ); + Vec_PtrFree( vMinCut ); + Abc_NtkCleanMarkA( pNtk ); + +} + +/**Function************************************************************* + + Synopsis [Implementation of max-flow/min-cut computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose ) +{ + Vec_Ptr_t * vMinCut; + Abc_Obj_t * pLatch; + int Flow, FlowCur, RetValue, i; + int clk = clock(); + int fUseDirectedFlow = 1; + + // find the max-flow + Abc_NtkCleanCopy( pNtk ); + Flow = 0; + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { +// assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) ); +// FlowCur = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 ); + Flow += FlowCur; + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) ); + Flow += FlowCur; + } + if ( FlowCur ) + Abc_NtkIncrementTravId(pNtk); + } + + if ( !fUseDirectedFlow ) + { + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { + // assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ); + Flow += FlowCur; + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ); + Flow += FlowCur; + } + if ( FlowCur ) + Abc_NtkIncrementTravId(pNtk); + } + } +// Abc_NtkMaxFlowPrintFlow( pNtk, fForward ); + + // mark the nodes reachable from the latches + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { +// assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + if ( fUseDirectedFlow ) + RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) ); +// RetValue = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 ); + else + RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ); + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + if ( fUseDirectedFlow ) + RetValue = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) ); + else + RetValue = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ); + } + assert( RetValue == 0 ); + } + + // find the min-cut with the smallest volume + vMinCut = Abc_NtkMaxFlowMinCut( pNtk, fForward ); + // verify the cut + if ( !Abc_NtkMaxFlowVerifyCut(pNtk, vMinCut, fForward) ) + printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" ); + // make the cut retimable + Abc_NtkMaxFlowMinCutUpdate( pNtk, vMinCut, fForward ); + + // report the results + if ( fVerbose ) + { + printf( "L = %6d. %s max-flow = %6d. Min-cut = %6d. ", + Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) ); +PRT( "Time", clock() - clk ); + } + +// Abc_NtkMaxFlowPrintCut( pNtk, vMinCut ); + return vMinCut; +} + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext, * pPred; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // get the predecessor + pPred = Abc_ObjGetPredecessorBwd( pObj ); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + return 0; + } + // pObj has flow - find the fanout with flow + if ( pPred == NULL ) + return 0; + // go through the successors of the predecessor + Abc_ObjForEachFanin( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + Abc_ObjForEachFanout( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + // try the fanout + if ( Abc_NtkMaxFlowBwdPath_rec( pPred ) ) + return Abc_ObjSetPath( pPred, NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext, * pPred; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // get the predecessor + pPred = Abc_ObjGetPredecessorFwd( pObj ); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + return 0; + } + // pObj has flow - find the fanout with flow + if ( pPred == NULL ) + return 0; + // go through the successors of the predecessor + Abc_ObjForEachFanout( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + Abc_ObjForEachFanin( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + // try the fanout + if ( Abc_NtkMaxFlowFwdPath_rec( pPred ) ) + return Abc_ObjSetPath( pPred, NULL ); + return 0; +} + + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this edge.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin ) +{ + Abc_Obj_t * pFanin, * pFanout; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // skip the fanin which already has flow + if ( fFanin && Abc_ObjGetPath(pPrev) ) + return 0; + // if the node has no flow, try to push through the fanouts + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // try to push flow through the fanouts + Abc_ObjForEachFanout( pObj, pFanout, i ) + if ( Abc_NtkMaxFlowFwdPath3_rec(pFanout, pObj, 1) ) + return fFanin? Abc_ObjSetPath(pPrev, pObj) : 1; + } + // try to push through the fanins + Abc_ObjForEachFanin( pObj, pFanin, i ) + if ( !Abc_ObjIsLatch(pFanin) && Abc_NtkMaxFlowFwdPath3_rec(pFanin, pObj, 0) ) + return Abc_ObjSetPath( pFanin, NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this node.] + + Description [This procedure works for directed graphs only!] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout, * pFanin; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanin( pObj, pFanin, i ) + if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) ) + return Abc_ObjSetPath( pObj, pFanin ); + return 0; + } + // pObj has flow - find the fanout with flow + pFanout = Abc_ObjGetFanoutPath( pObj ); + if ( pFanout == NULL ) + return 0; + // go through the fanins of the fanout with flow + Abc_ObjForEachFanin( pFanout, pFanin, i ) + if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) ) + return Abc_ObjSetPath( pFanout, pFanin ); + // try the fanout + if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) ) + return Abc_ObjSetPath( pFanout, NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this node.] + + Description [This procedure works for directed graphs only!] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout, * pFanin; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanout( pObj, pFanout, i ) + if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) ) + return Abc_ObjSetPath( pObj, pFanout ); + return 0; + } + // pObj has flow - find the fanout with flow + pFanin = Abc_ObjGetFaninPath( pObj ); + if ( pFanin == NULL ) + return 0; + // go through the fanins of the fanout with flow + Abc_ObjForEachFanout( pFanin, pFanout, i ) + if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) ) + return Abc_ObjSetPath( pFanin, pFanout ); + // try the fanout + if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) ) + return Abc_ObjSetPath( pFanin, NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Find minimum-volume minumum cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward ) +{ + Vec_Ptr_t * vMinCut; + Abc_Obj_t * pObj; + int i; + // collect the cut nodes + vMinCut = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + // node without flow is not a cut node + if ( !Abc_ObjGetPath(pObj) ) + continue; + // unvisited node is below the cut + if ( !Abc_NodeIsTravIdCurrent(pObj) ) + continue; + // add terminal with flow or node whose path is not visited + if ( pObj->fMarkA || !Abc_NodeIsTravIdCurrent( Abc_ObjGetPath(pObj) ) ) + Vec_PtrPush( vMinCut, pObj ); + } + return vMinCut; +} + +/**Function************************************************************* + + Synopsis [Marks the TFI cone with MarkA.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowMarkCut_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + if ( pObj->fMarkA ) + return; + pObj->fMarkA = 1; + Abc_ObjForEachFanin( pObj, pNext, i ) + Abc_NtkMaxFlowMarkCut_rec( pNext ); +} + +/**Function************************************************************* + + Synopsis [Visits the TFI up to marked nodes and collects marked nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowCollectCut_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes ) +{ + Abc_Obj_t * pNext; + int i; + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent(pObj); + if ( pObj->fMarkA ) + { + Vec_PtrPush( vNodes, pObj ); + return; + } + Abc_ObjForEachFanin( pObj, pNext, i ) + Abc_NtkMaxFlowCollectCut_rec( pNext, vNodes ); +} + +/**Function************************************************************* + + Synopsis [Updates the minimum cut to be retimable.] + + Description [This procedure also labels the nodes reachable from + the latches to the cut with fMarkA.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) +{ + Abc_Obj_t * pObj, * pNext; + int i, k; + // clean marks + Abc_NtkForEachObj( pNtk, pObj, i ) + pObj->fMarkA = 0; + // set latch outputs + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_ObjFanout0(pObj)->fMarkA = 1; + // traverse from cut nodes + Vec_PtrForEachEntry( vMinCut, pObj, i ) + Abc_NtkMaxFlowMarkCut_rec( pObj ); + if ( fForward ) + { + // change mincut to be nodes with unmarked fanouts + Vec_PtrClear( vMinCut ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( !pObj->fMarkA ) + continue; + Abc_ObjForEachFanout( pObj, pNext, k ) + { + if ( pNext->fMarkA ) + continue; + Vec_PtrPush( vMinCut, pObj ); + break; + } + } + } + else + { + // change mincut to be marked fanins of the unmarked nodes + Vec_PtrClear( vMinCut ); + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_NtkMaxFlowCollectCut_rec( Abc_ObjFanin0(pObj), vMinCut ); + // transfer the attribute + Abc_NtkForEachObj( pNtk, pObj, i ) + pObj->fMarkA = Abc_NodeIsTravIdCurrent(pObj); + // unmark the cut nodes + Vec_PtrForEachEntry( vMinCut, pObj, i ) + pObj->fMarkA = 0; + } +} + +/**Function************************************************************* + + Synopsis [Verifies the min-cut is indeed a cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowVerifyCut_rec( Abc_Obj_t * pObj, int fForward ) +{ + Abc_Obj_t * pNext; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 1; + Abc_NodeSetTravIdCurrent(pObj); + // visit the node + if ( fForward ) + { + if ( Abc_ObjIsCo(pObj) ) + return 0; + // explore the fanouts + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) ) + return 0; + } + else + { + if ( Abc_ObjIsCi(pObj) ) + return 0; + // explore the fanins + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Verifies the min-cut is indeed a cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) +{ + Abc_Obj_t * pObj; + int i; + // mark the cut with the current traversal ID + Abc_NtkIncrementTravId(pNtk); + Vec_PtrForEachEntry( vMinCut, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + // search from the latches for a path to the COs/CIs + Abc_NtkForEachLatch( pNtk, pObj, i ) + { + if ( fForward ) + { + if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) ) + return 0; + } + else + { + if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) ) + return 0; + } + } +/* + { + // count the volume of the cut + int Counter = 0; + Abc_NtkForEachObj( pNtk, pObj, i ) + Counter += Abc_NodeIsTravIdCurrent( pObj ); + printf( "Volume = %d.\n", Counter ); + } +*/ + return 1; +} + +/**Function************************************************************* + + Synopsis [Prints the flows.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward ) +{ + Abc_Obj_t * pLatch, * pNext, * pPrev; + int i; + if ( fForward ) + { + Vec_PtrForEachEntry( pNtk->vBoxes, pLatch, i ) + { + assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + if ( Abc_ObjGetPath(Abc_ObjFanout0(pLatch)) == NULL ) // no flow through this latch + continue; + printf( "Path = " ); + for ( pNext = Abc_ObjFanout0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) ) + { + printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id ); + pPrev = pNext; + } + if ( !Abc_ObjIsPo(pPrev) ) + printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanout0(pPrev)), Abc_ObjFanout0(pPrev)->Id ); + printf( "\n" ); + } + } + else + { + Vec_PtrForEachEntry( pNtk->vBoxes, pLatch, i ) + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + if ( Abc_ObjGetPath(Abc_ObjFanin0(pLatch)) == NULL ) // no flow through this latch + continue; + printf( "Path = " ); + for ( pNext = Abc_ObjFanin0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) ) + { + printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id ); + pPrev = pNext; + } + if ( !Abc_ObjIsPi(pPrev) ) + printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanin0(pPrev)), Abc_ObjFanin0(pPrev)->Id ); + printf( "\n" ); + } + } +} + +/**Function************************************************************* + + Synopsis [Prints the min-cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ) +{ + Abc_Obj_t * pObj; + int i; + printf( "Min-cut: " ); + Vec_PtrForEachEntry( vMinCut, pObj, i ) + printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id ); + printf( "\n" ); + printf( "Marked nodes: " ); + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( pObj->fMarkA ) + printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id ); + printf( "\n" ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retIncrem.c b/src/opt/ret/retIncrem.c new file mode 100644 index 00000000..ba8104be --- /dev/null +++ b/src/opt/ret/retIncrem.c @@ -0,0 +1,464 @@ +/**CFile**************************************************************** + + FileName [retIncrem.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [Incremental retiming in one direction.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retIncrem.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs retiming in one direction.] + + Description [Currently does not retime over black boxes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int fOneStep, int fVerbose ) +{ + Abc_Ntk_t * pNtkCopy = NULL; + Vec_Ptr_t * vBoxes; + st_table * tLatches; + int nLatches = Abc_NtkLatchNum(pNtk); + int nIdMaxStart = Abc_NtkObjNumMax(pNtk); + int RetValue, nIterLimit; + if ( Abc_NtkNodeNum(pNtk) == 0 ) + return 0; + // reorder CI/CO/latch inputs + Abc_NtkOrderCisCos( pNtk ); + if ( fMinDelay ) + { + nIterLimit = fOneStep? 1 : 2 * Abc_NtkLevel(pNtk); + pNtkCopy = Abc_NtkDup( pNtk ); + tLatches = Abc_NtkRetimePrepareLatches( pNtkCopy ); + st_free_table( tLatches ); + } + // collect latches and remove CIs/COs + tLatches = Abc_NtkRetimePrepareLatches( pNtk ); + // share the latches + Abc_NtkRetimeShareLatches( pNtk, 0 ); + // save boxes + vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL; + // perform the retiming + if ( fMinDelay ) + Abc_NtkRetimeMinDelay( pNtk, pNtkCopy, nIterLimit, fForward, fVerbose ); + else + Abc_NtkRetimeOneWay( pNtk, fForward, fVerbose ); + if ( fMinDelay ) + Abc_NtkDelete( pNtkCopy ); + // share the latches + Abc_NtkRetimeShareLatches( pNtk, 0 ); + // restore boxes + pNtk->vBoxes = vBoxes; + // finalize the latches + RetValue = Abc_NtkRetimeFinalizeLatches( pNtk, tLatches, nIdMaxStart ); + st_free_table( tLatches ); + if ( RetValue == 0 ) + return 0; + // fix the COs +// Abc_NtkLogicMakeSimpleCos( pNtk, 0 ); + // check for correctness + if ( !Abc_NtkCheck( pNtk ) ) + fprintf( stdout, "Abc_NtkRetimeForward(): Network check has failed.\n" ); + // return the number of latches saved + return nLatches - Abc_NtkLatchNum(pNtk); +} + +/**Function************************************************************* + + Synopsis [Prepares the network for retiming.] + + Description [Hash latches into their number in the original network.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk ) +{ + st_table * tLatches; + Abc_Obj_t * pLatch, * pLatchIn, * pLatchOut, * pFanin; + int i, nOffSet = Abc_NtkBoxNum(pNtk) - Abc_NtkLatchNum(pNtk); + // collect latches and remove CIs/COs + tLatches = st_init_table( st_ptrcmp, st_ptrhash ); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + // map latch into its true number + st_insert( tLatches, (void *)pLatch, (void *)(i-nOffSet) ); + // disconnect LI + pLatchIn = Abc_ObjFanin0(pLatch); + pFanin = Abc_ObjFanin0(pLatchIn); + Abc_ObjTransferFanout( pLatchIn, pFanin ); + Abc_ObjDeleteFanin( pLatchIn, pFanin ); + // disconnect LO + pLatchOut = Abc_ObjFanout0(pLatch); + pFanin = Abc_ObjFanin0(pLatchOut); + if ( Abc_ObjFanoutNum(pLatchOut) > 0 ) + Abc_ObjTransferFanout( pLatchOut, pFanin ); + Abc_ObjDeleteFanin( pLatchOut, pFanin ); + } + return tLatches; +} + +/**Function************************************************************* + + Synopsis [Finalizes the latches after retiming.] + + Description [Reuses the LIs/LOs for old latches.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nIdMaxStart ) +{ + Vec_Ptr_t * vCisOld, * vCosOld, * vBoxesOld, * vCisNew, * vCosNew, * vBoxesNew; + Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut; + int i, Index; + // create new arrays + vCisOld = pNtk->vCis; pNtk->vCis = NULL; vCisNew = Vec_PtrAlloc( 100 ); + vCosOld = pNtk->vCos; pNtk->vCos = NULL; vCosNew = Vec_PtrAlloc( 100 ); + vBoxesOld = pNtk->vBoxes; pNtk->vBoxes = NULL; vBoxesNew = Vec_PtrAlloc( 100 ); + // copy boxes and their CIs/COs + Vec_PtrForEachEntryStop( vCisOld, pObj, i, Vec_PtrSize(vCisOld) - st_count(tLatches) ) + Vec_PtrPush( vCisNew, pObj ); + Vec_PtrForEachEntryStop( vCosOld, pObj, i, Vec_PtrSize(vCosOld) - st_count(tLatches) ) + Vec_PtrPush( vCosNew, pObj ); + Vec_PtrForEachEntryStop( vBoxesOld, pObj, i, Vec_PtrSize(vBoxesOld) - st_count(tLatches) ) + Vec_PtrPush( vBoxesNew, pObj ); + // go through the latches + Abc_NtkForEachObj( pNtk, pLatch, i ) + { + if ( !Abc_ObjIsLatch(pLatch) ) + continue; + if ( Abc_ObjId(pLatch) >= (unsigned)nIdMaxStart ) + { + // this is a new latch + pLatchIn = Abc_NtkCreateBi(pNtk); + pLatchOut = Abc_NtkCreateBo(pNtk); + Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" ); + Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" ); + } + else + { + // this is an old latch + // get its number in the original order + if ( !st_lookup( tLatches, (char *)pLatch, (char **)&Index ) ) + { + printf( "Abc_NtkRetimeFinalizeLatches(): Internal error.\n" ); + return 0; + } + assert( pLatch == Vec_PtrEntry(vBoxesOld, Vec_PtrSize(vBoxesOld) - st_count(tLatches) + Index) ); + // reconnect with the old LIs/LOs + pLatchIn = Vec_PtrEntry( vCosOld, Vec_PtrSize(vCosOld) - st_count(tLatches) + Index ); + pLatchOut = Vec_PtrEntry( vCisOld, Vec_PtrSize(vCisOld) - st_count(tLatches) + Index ); + } + // connect + Abc_ObjAddFanin( pLatchIn, Abc_ObjFanin0(pLatch) ); + Abc_ObjPatchFanin( pLatch, Abc_ObjFanin0(pLatch), pLatchIn ); + if ( Abc_ObjFanoutNum(pLatch) > 0 ) + Abc_ObjTransferFanout( pLatch, pLatchOut ); + Abc_ObjAddFanin( pLatchOut, pLatch ); + // add to the arrays + Vec_PtrPush( vCisNew, pLatchOut ); + Vec_PtrPush( vCosNew, pLatchIn ); + Vec_PtrPush( vBoxesNew, pLatch ); + } + // free useless Cis/Cos + Vec_PtrForEachEntry( vCisOld, pObj, i ) + if ( !Abc_ObjIsPi(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 ) + Abc_NtkDeleteObj(pObj); + Vec_PtrForEachEntry( vCosOld, pObj, i ) + if ( !Abc_ObjIsPo(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 ) + Abc_NtkDeleteObj(pObj); + // set the new arrays + pNtk->vCis = vCisNew; Vec_PtrFree( vCisOld ); + pNtk->vCos = vCosNew; Vec_PtrFree( vCosOld ); + pNtk->vBoxes = vBoxesNew; Vec_PtrFree( vBoxesOld ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Performs retiming one way, forward or backward.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose ) +{ + Abc_Ntk_t * pNtkNew; + Vec_Int_t * vValues; + Abc_Obj_t * pObj; + int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 10000; + if ( fForward ) + Abc_NtkRetimeTranferToCopy( pNtk ); + else + { + // save initial values of the latches + vValues = Abc_NtkRetimeCollectLatchValues( pNtk ); + // start the network for initial value computation + pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk ); + } + // try to move latches forward whenever possible + do { + fChanges = 0; + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( !Abc_ObjIsNode(pObj) ) + continue; + if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) ) + { + Abc_NtkRetimeNode( pObj, fForward, 1 ); + fChanges = 1; + nTotalMoves++; + if ( nTotalMoves >= nTotalMovesLimit ) + { + printf( "Stopped after %d latch moves.\n", nTotalMoves ); + break; + } + } + } + } while ( fChanges && nTotalMoves < nTotalMovesLimit ); + // transfer the initial state back to the latches + if ( fForward ) + Abc_NtkRetimeTranferFromCopy( pNtk ); + else + { + Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose ); + Abc_NtkDelete( pNtkNew ); + Vec_IntFree( vValues ); + } + return 0; +} + + +/**Function************************************************************* + + Synopsis [Returns 1 if retiming forward/backward is possible.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward ) +{ + Abc_Obj_t * pNext; + int i; + assert( Abc_ObjIsNode(pObj) ); + if ( fForward ) + { + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) ) + return 0; + } + else + { + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Retimes the node backward or forward.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial ) +{ + Abc_Ntk_t * pNtkNew = NULL; + Vec_Ptr_t * vNodes; + Abc_Obj_t * pNext, * pLatch; + int i; + vNodes = Vec_PtrAlloc( 10 ); + if ( fForward ) + { + // compute the initial value + if ( fInitial ) + pObj->pCopy = (void *)Abc_ObjSopSimulate( pObj ); + // collect fanins + Abc_NodeCollectFanins( pObj, vNodes ); + // make the node point to the fanins fanins + Vec_PtrForEachEntry( vNodes, pNext, i ) + { + assert( Abc_ObjIsLatch(pNext) ); + Abc_ObjPatchFanin( pObj, pNext, Abc_ObjFanin0(pNext) ); + if ( Abc_ObjFanoutNum(pNext) == 0 ) + Abc_NtkDeleteObj(pNext); + } + // add a new latch on top + pNext = Abc_NtkCreateLatch(pObj->pNtk); + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Abc_ObjTransferFanout( pObj, pNext ); + Abc_ObjAddFanin( pNext, pObj ); + // set the initial value + if ( fInitial ) + pNext->pCopy = pObj->pCopy; + } + else + { + // compute the initial value + if ( fInitial ) + { + pNtkNew = Abc_ObjFanout0(pObj)->pCopy->pNtk; + Abc_NtkDupObj( pNtkNew, pObj, 0 ); + Abc_ObjForEachFanout( pObj, pNext, i ) + { + assert( Abc_ObjFaninNum(pNext->pCopy) == 0 ); + Abc_ObjAddFanin( pNext->pCopy, pObj->pCopy ); + } + } + // collect fanouts + Abc_NodeCollectFanouts( pObj, vNodes ); + // make the fanouts fanouts point to the node + Vec_PtrForEachEntry( vNodes, pNext, i ) + { + assert( Abc_ObjIsLatch(pNext) ); + Abc_ObjTransferFanout( pNext, pObj ); + Abc_NtkDeleteObj( pNext ); + } + // add new latches to the fanins + Abc_ObjForEachFanin( pObj, pNext, i ) + { + pLatch = Abc_NtkCreateLatch(pObj->pNtk); + Abc_ObjPatchFanin( pObj, pNext, pLatch ); + Abc_ObjAddFanin( pLatch, pNext ); + // create buffer isomorphic to this latch + if ( fInitial ) + { + pLatch->pCopy = Abc_NtkCreateNodeBuf( pNtkNew, NULL ); + Abc_ObjAddFanin( pObj->pCopy, pLatch->pCopy ); + } + } + } + Vec_PtrFree( vNodes ); +} + +/**Function************************************************************* + + Synopsis [Returns the number of compatible fanout latches.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeCheckCompatibleLatchFanouts( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pFanout; + int i, nLatches = 0, Init = -1; + Abc_ObjForEachFanout( pObj, pFanout, i ) + { + if ( !Abc_ObjIsLatch(pFanout) ) + continue; + if ( Init == -1 ) + { + Init = (int)pObj->pData; + nLatches++; + } + else if ( Init == (int)pObj->pData ) + nLatches++; + } + return nLatches; +} + +/**Function************************************************************* + + Synopsis [Retimes the node backward or forward.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pFanin, * pLatchTop, * pLatchCur; + int i, k; + vNodes = Vec_PtrAlloc( 10 ); + // consider latch fanins + Abc_NtkForEachObj( pNtk, pFanin, i ) + { + if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 ) + continue; + // get the first latch + pLatchTop = NULL; + Abc_ObjForEachFanout( pFanin, pLatchTop, k ) + if ( Abc_ObjIsLatch(pLatchTop) ) + break; + assert( pLatchTop && Abc_ObjIsLatch(pLatchTop) ); + // redirect compatible fanout latches to the first latch + Abc_NodeCollectFanouts( pFanin, vNodes ); + Vec_PtrForEachEntry( vNodes, pLatchCur, k ) + { + if ( !Abc_ObjIsLatch(pLatchCur) ) + continue; + if ( pLatchCur == pLatchTop ) + continue; + if ( pLatchCur->pData != pLatchTop->pData ) + continue; + // connect the initial state + if ( fInitial ) + Abc_ObjAddFanin( pLatchCur->pCopy, pLatchTop->pCopy ); + // redirect the fanouts + Abc_ObjTransferFanout( pLatchCur, pLatchTop ); + Abc_NtkDeleteObj(pLatchCur); + } + } + Vec_PtrFree( vNodes ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retInit.c b/src/opt/ret/retInit.c new file mode 100644 index 00000000..dcb71c60 --- /dev/null +++ b/src/opt/ret/retInit.c @@ -0,0 +1,349 @@ +/**CFile**************************************************************** + + FileName [retInit.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [Initial state computation for backward retiming.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retInit.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Abc_NtkRetimeVerifyModel( Abc_Ntk_t * pNtkCone, Vec_Int_t * vValues, int * pModel ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes initial values of the new latches.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkRetimeInitialValues( Abc_Ntk_t * pNtkCone, Vec_Int_t * vValues, int fVerbose ) +{ + Vec_Int_t * vSolution; + Abc_Ntk_t * pNtkMiter, * pNtkLogic; + int RetValue, clk; + if ( pNtkCone == NULL ) + return Vec_IntDup( vValues ); + // convert the target network to AIG + pNtkLogic = Abc_NtkDup( pNtkCone ); + Abc_NtkToAig( pNtkLogic ); + // get the miter + pNtkMiter = Abc_NtkCreateTarget( pNtkLogic, pNtkLogic->vCos, vValues ); + if ( fVerbose ) + printf( "The miter for initial state computation has %d AIG nodes. ", Abc_NtkNodeNum(pNtkMiter) ); + // solve the miter + clk = clock(); + RetValue = Abc_NtkMiterSat( pNtkMiter, (sint64)500000, (sint64)50000000, 0, NULL, NULL ); + if ( fVerbose ) + { PRT( "SAT solving time", clock() - clk ); } + // analyze the result + if ( RetValue == 1 ) + printf( "Abc_NtkRetimeInitialValues(): The problem is unsatisfiable. DC latch values are used.\n" ); + else if ( RetValue == -1 ) + printf( "Abc_NtkRetimeInitialValues(): The SAT problem timed out. DC latch values are used.\n" ); + else if ( !Abc_NtkRetimeVerifyModel( pNtkCone, vValues, pNtkMiter->pModel ) ) + printf( "Abc_NtkRetimeInitialValues(): The computed counter-example is incorrect.\n" ); + // set the values of the latches + vSolution = RetValue? NULL : Vec_IntAllocArray( pNtkMiter->pModel, Abc_NtkPiNum(pNtkLogic) ); + pNtkMiter->pModel = NULL; + Abc_NtkDelete( pNtkMiter ); + Abc_NtkDelete( pNtkLogic ); + return vSolution; +} + +/**Function************************************************************* + + Synopsis [Computes the results of simulating one node.] + + Description [Assumes that fanins have pCopy set to the input values.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_ObjSopSimulate( Abc_Obj_t * pObj ) +{ + char * pCube, * pSop = pObj->pData; + int nVars, Value, v, ResOr, ResAnd, ResVar; + assert( pSop && !Abc_SopIsExorType(pSop) ); + // simulate the SOP of the node + ResOr = 0; + nVars = Abc_SopGetVarNum(pSop); + Abc_SopForEachCube( pSop, nVars, pCube ) + { + ResAnd = 1; + Abc_CubeForEachVar( pCube, Value, v ) + { + if ( Value == '0' ) + ResVar = 1 ^ ((int)Abc_ObjFanin(pObj, v)->pCopy); + else if ( Value == '1' ) + ResVar = (int)Abc_ObjFanin(pObj, v)->pCopy; + else + continue; + ResAnd &= ResVar; + } + ResOr |= ResAnd; + } + // complement the result if necessary + if ( !Abc_SopGetPhase(pSop) ) + ResOr ^= 1; + return ResOr; +} + +/**Function************************************************************* + + Synopsis [Verifies the counter-example.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeVerifyModel( Abc_Ntk_t * pNtkCone, Vec_Int_t * vValues, int * pModel ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pObj; + int i, Counter = 0; + assert( Abc_NtkIsSopLogic(pNtkCone) ); + // set the PIs + Abc_NtkForEachPi( pNtkCone, pObj, i ) + pObj->pCopy = (void *)pModel[i]; + // simulate the internal nodes + vNodes = Abc_NtkDfs( pNtkCone, 0 ); + Vec_PtrForEachEntry( vNodes, pObj, i ) + pObj->pCopy = (void *)Abc_ObjSopSimulate( pObj ); + Vec_PtrFree( vNodes ); + // compare the outputs + Abc_NtkForEachPo( pNtkCone, pObj, i ) + pObj->pCopy = Abc_ObjFanin0(pObj)->pCopy; + Abc_NtkForEachPo( pNtkCone, pObj, i ) + Counter += (Vec_IntEntry(vValues, i) != (int)pObj->pCopy); + if ( Counter > 0 ) + printf( "%d outputs (out of %d) have a value mismatch.\n", Counter, Abc_NtkPoNum(pNtkCone) ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values to pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeTranferToCopy( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + pObj->pCopy = (void *)Abc_LatchIsInit1(pObj); +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values from pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeTranferFromCopy( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + pObj->pData = (void *)(pObj->pCopy? ABC_INIT_ONE : ABC_INIT_ZERO); +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values to pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkRetimeCollectLatchValues( Abc_Ntk_t * pNtk ) +{ + Vec_Int_t * vValues; + Abc_Obj_t * pObj; + int i; + vValues = Vec_IntAlloc( Abc_NtkLatchNum(pNtk) ); + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + Vec_IntPush( vValues, Abc_LatchIsInit1(pObj) ); + return vValues; +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values from pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeInsertLatchValues( Abc_Ntk_t * pNtk, Vec_Int_t * vValues ) +{ + Abc_Obj_t * pObj; + int i, Counter = 0; + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + pObj->pCopy = (void *)Counter++; + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + pObj->pData = (void *)(vValues? (Vec_IntEntry(vValues,(int)pObj->pCopy)? ABC_INIT_ONE : ABC_INIT_ZERO) : ABC_INIT_DC); +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values to pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Abc_Ntk_t * Abc_NtkRetimeBackwardInitialStart( Abc_Ntk_t * pNtk ) +{ + Abc_Ntk_t * pNtkNew; + Abc_Obj_t * pObj; + int i; + // create the network used for the initial state computation + pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 ); + // create POs corresponding to the initial values + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + pObj->pCopy = Abc_NtkCreatePo(pNtkNew); + return pNtkNew; +} + +/**Function************************************************************* + + Synopsis [Transfer latch initial values to pCopy.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeBackwardInitialFinish( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew, Vec_Int_t * vValuesOld, int fVerbose ) +{ + Vec_Int_t * vValuesNew; + Abc_Obj_t * pObj; + int i; + // create PIs corresponding to the initial values + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjIsLatch(pObj) ) + Abc_ObjAddFanin( pObj->pCopy, Abc_NtkCreatePi(pNtkNew) ); + // assign dummy node names + Abc_NtkAddDummyPiNames( pNtkNew ); + Abc_NtkAddDummyPoNames( pNtkNew ); + // check the network + if ( !Abc_NtkCheck( pNtkNew ) ) + fprintf( stdout, "Abc_NtkRetimeBackwardInitialFinish(): Network check has failed.\n" ); + // derive new initial values + vValuesNew = Abc_NtkRetimeInitialValues( pNtkNew, vValuesOld, fVerbose ); + // insert new initial values + Abc_NtkRetimeInsertLatchValues( pNtk, vValuesNew ); + if ( vValuesNew ) Vec_IntFree( vValuesNew ); +} + + +/**Function************************************************************* + + Synopsis [Cycles the circuit to create a new initial state.] + + Description [Simulates the circuit with random input for the given + number of timeframes to get a better initial state.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkCycleInitStateSop( Abc_Ntk_t * pNtk, int nFrames, int fVerbose ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pObj; + int i, f; + assert( Abc_NtkIsSopLogic(pNtk) ); + srand( 0x12341234 ); + // initialize the values + Abc_NtkForEachPi( pNtk, pObj, i ) + pObj->pCopy = (void *)(rand() & 1); + Abc_NtkForEachLatch( pNtk, pObj, i ) + pObj->pCopy = (void *)Abc_LatchIsInit1(pObj); + // simulate for the given number of timeframes + vNodes = Abc_NtkDfs( pNtk, 0 ); + for ( f = 0; f < nFrames; f++ ) + { + // simulate internal nodes + Vec_PtrForEachEntry( vNodes, pObj, i ) + pObj->pCopy = (void *)Abc_ObjSopSimulate( pObj ); + // bring the results to the COs + Abc_NtkForEachCo( pNtk, pObj, i ) + pObj->pCopy = Abc_ObjFanin0(pObj)->pCopy; + // assign PI values + Abc_NtkForEachPi( pNtk, pObj, i ) + pObj->pCopy = (void *)(rand() & 1); + // transfer the latch values + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_ObjFanout0(pObj)->pCopy = Abc_ObjFanin0(pObj)->pCopy; + } + Vec_PtrFree( vNodes ); + // set the final values + Abc_NtkForEachLatch( pNtk, pObj, i ) + pObj->pData = (void *)(Abc_ObjFanout0(pObj)->pCopy ? ABC_INIT_ONE : ABC_INIT_ZERO); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retInt.h b/src/opt/ret/retInt.h new file mode 100644 index 00000000..51428bce --- /dev/null +++ b/src/opt/ret/retInt.h @@ -0,0 +1,80 @@ +/**CFile**************************************************************** + + FileName [retInt.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [Internal declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retInt.h,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __RET_INT_H__ +#define __RET_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include "abc.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== retArea.c ========================================================*/ +extern int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose ); +/*=== retCore.c ========================================================*/ +extern int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOnly, int fOneStep, int fVerbose ); +/*=== retDelay.c ========================================================*/ +extern int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nIterLimit, int fForward, int fVerbose ); +/*=== retDirect.c ========================================================*/ +extern int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int fOneStep, int fVerbose ); +extern void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial ); +extern int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward ); +extern void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial ); +extern st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk ); +extern int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nIdMaxStart ); +/*=== retFlow.c ========================================================*/ +extern void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk ); +extern Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose ); +/*=== retInit.c ========================================================*/ +extern Vec_Int_t * Abc_NtkRetimeInitialValues( Abc_Ntk_t * pNtkSat, Vec_Int_t * vValues, int fVerbose ); +extern int Abc_ObjSopSimulate( Abc_Obj_t * pObj ); +extern void Abc_NtkRetimeTranferToCopy( Abc_Ntk_t * pNtk ); +extern void Abc_NtkRetimeTranferFromCopy( Abc_Ntk_t * pNtk ); +extern Vec_Int_t * Abc_NtkRetimeCollectLatchValues( Abc_Ntk_t * pNtk ); +extern void Abc_NtkRetimeInsertLatchValues( Abc_Ntk_t * pNtk, Vec_Int_t * vValues ); +extern Abc_Ntk_t * Abc_NtkRetimeBackwardInitialStart( Abc_Ntk_t * pNtk ); +extern void Abc_NtkRetimeBackwardInitialFinish( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew, Vec_Int_t * vValuesOld, int fVerbose ); +/*=== retLvalue.c ========================================================*/ +extern int Abc_NtkRetimeLValue( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ); + +#endif + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/retLvalue.c b/src/opt/ret/retLvalue.c new file mode 100644 index 00000000..b4d9e946 --- /dev/null +++ b/src/opt/ret/retLvalue.c @@ -0,0 +1,395 @@ +/**CFile**************************************************************** + + FileName [retLvalue.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [Implementation of Pan's retiming algorithm.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: retLvalue.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// node status after updating its arrival time +enum { ABC_RET_UPDATE_FAIL, ABC_RET_UPDATE_NO, ABC_RET_UPDATE_YES }; + +// the internal procedures +static Vec_Int_t * Abc_NtkRetimeGetLags( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ); +static int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose ); +static int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi, int nMaxIters, int fVerbose ); +static int Abc_NtkRetimeUpdateLValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi ); +static int Abc_NtkRetimePosOverLimit( Abc_Ntk_t * pNtk, int Fi ); +static Vec_Ptr_t * Abc_ManCollectLatches( Abc_Ntk_t * pNtk ); +static int Abc_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose ); + +static inline int Abc_NodeComputeLag( int LValue, int Fi ) { return (LValue + (1<<16)*Fi)/Fi - (1<<16) - (int)(LValue % Fi == 0); } +static inline int Abc_NodeGetLValue( Abc_Obj_t * pNode ) { return (int)pNode->pCopy; } +static inline void Abc_NodeSetLValue( Abc_Obj_t * pNode, int Value ) { pNode->pCopy = (void *)Value; } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Implements Pan's retiming algorithm.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeLValue( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ) +{ + Vec_Int_t * vLags; + int nLatches = Abc_NtkLatchNum(pNtk); + assert( Abc_NtkIsLogic( pNtk ) ); + // get the lags + vLags = Abc_NtkRetimeGetLags( pNtk, nIterLimit, fVerbose ); + // compute the retiming +// Abc_NtkRetimeUsingLags( pNtk, vLags, fVerbose ); + Vec_IntFree( vLags ); + // fix the COs +// Abc_NtkLogicMakeSimpleCos( pNtk, 0 ); + // check for correctness + if ( !Abc_NtkCheck( pNtk ) ) + fprintf( stdout, "Abc_NtkRetimeLValue(): Network check has failed.\n" ); + // return the number of latches saved + return nLatches - Abc_NtkLatchNum(pNtk); +} + +/**Function************************************************************* + + Synopsis [Computes the retiming lags.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Abc_NtkRetimeGetLags( Abc_Ntk_t * pNtk, int nIterLimit, int fVerbose ) +{ + Vec_Int_t * vLags; + Vec_Ptr_t * vNodes, * vLatches; + Abc_Obj_t * pNode; + int i, FiMax, FiBest, RetValue, clk, clkIter; + char NodeLag; + + // get the upper bound on the clock period + FiMax = Abc_NtkLevel(pNtk); + + // make sure this clock period is feasible + vNodes = Abc_NtkDfs( pNtk, 0 ); + vLatches = Abc_ManCollectLatches( pNtk ); + if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiMax, nIterLimit, fVerbose ) ) + { + Vec_PtrFree( vNodes ); + printf( "Abc_NtkRetimeGetLags() error: The upper bound on the clock period cannot be computed.\n" ); + return Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); + } + + // search for the optimal clock period between 0 and nLevelMax +clk = clock(); + FiBest = Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, 0, FiMax, nIterLimit, fVerbose ); +clkIter = clock() - clk; + + // recompute the best l-values + RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, FiBest, nIterLimit, fVerbose ); + assert( RetValue ); + + // fix the problem with non-converged delays + Abc_NtkForEachNode( pNtk, pNode, i ) + if ( Abc_NodeGetLValue(pNode) < -ABC_INFINITY/2 ) + Abc_NodeSetLValue( pNode, 0 ); + + // write the retiming lags + vLags = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); + Abc_NtkForEachNode( pNtk, pNode, i ) + { + NodeLag = Abc_NodeComputeLag( Abc_NodeGetLValue(pNode), FiBest ); + Vec_IntWriteEntry( vLags, pNode->Id, NodeLag ); + } +/* + Abc_NtkForEachPo( pNtk, pNode, i ) + printf( "%d ", Abc_NodeGetLValue(Abc_ObjFanin0(pNode)) ); + printf( "\n" ); + Abc_NtkForEachLatch( pNtk, pNode, i ) + printf( "%d/%d ", Abc_NodeGetLValue(Abc_ObjFanout0(pNode)), Abc_NodeGetLValue(Abc_ObjFanout0(pNode)) + FiBest ); + printf( "\n" ); +*/ + + // print the result +// if ( fVerbose ) + printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest ); +/* + { + FILE * pTable; + pTable = fopen( "iscas/seqmap__stats2.txt", "a+" ); + fprintf( pTable, "%d ", FiBest ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } +*/ + Vec_PtrFree( vNodes ); + Vec_PtrFree( vLatches ); + return vLags; +} + +/**Function************************************************************* + + Synopsis [Performs binary search for the optimal clock period.] + + Description [Assumes that FiMin is infeasible while FiMax is feasible.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int FiMin, int FiMax, int nMaxIters, int fVerbose ) +{ + int Median; + assert( FiMin < FiMax ); + if ( FiMin + 1 == FiMax ) + return FiMax; + Median = FiMin + (FiMax - FiMin)/2; + if ( Abc_NtkRetimeForPeriod( pNtk, vNodes, vLatches, Median, nMaxIters, fVerbose ) ) + return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible + else + return Abc_NtkRetimeSearch_rec( pNtk, vNodes, vLatches, Median, FiMax, nMaxIters, fVerbose ); // Median is infeasible +} + +/**Function************************************************************* + + Synopsis [Returns 1 if retiming with this clock period is feasible.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi, int nMaxIters, int fVerbose ) +{ + Abc_Obj_t * pObj; + int c, i, fConverged; + // set l-values of all nodes to be minus infinity, except PIs and constants + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( Abc_ObjFaninNum(pObj) == 0 ) + Abc_NodeSetLValue( pObj, 0 ); + else + Abc_NodeSetLValue( pObj, -ABC_INFINITY ); + // update all values iteratively + fConverged = 0; + for ( c = 1; c <= nMaxIters; c++ ) + { + if ( !Abc_NtkRetimeUpdateLValue( pNtk, vNodes, vLatches, Fi ) ) + { + fConverged = 1; + break; + } + if ( Abc_NtkRetimePosOverLimit(pNtk, Fi) ) + break; + } + // report the results + if ( fVerbose ) + { + if ( !fConverged ) + printf( "Period = %3d. Iterations = %3d. Infeasible %s\n", Fi, c, (c > nMaxIters)? "(timeout)" : "" ); + else + printf( "Period = %3d. Iterations = %3d. Feasible\n", Fi, c ); + } +/* + // check if any AND gates have infinite delay + Counter = 0; + Abc_NtkForEachNode( pNtk, pObj, i ) + Counter += (Abc_NodeGetLValue(pObj) < -ABC_INFINITY/2); + if ( Counter > 0 ) + printf( "Warning: %d internal nodes have wrong l-values!\n", Counter ); +*/ + return fConverged; +} + +/**Function************************************************************* + + Synopsis [Performs one iteration of l-value computation for the nodes.] + + Description [Experimentally it was found that checking POs changes + is not enough to detect the convergence of l-values in the network.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeUpdateLValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLatches, int Fi ) +{ + Abc_Obj_t * pObj, * pFanin; + int i, k, lValueNew, fChange; + // go through the nodes and detect change + fChange = 0; + Vec_PtrForEachEntry( vNodes, pObj, i ) + { + assert( Abc_ObjIsNode(pObj) ); + lValueNew = -ABC_INFINITY; + Abc_ObjForEachFanin( pObj, pFanin, k ) + { + if ( lValueNew < Abc_NodeGetLValue(pFanin) ) + lValueNew = Abc_NodeGetLValue(pFanin); + } + lValueNew++; + if ( Abc_NodeGetLValue(pObj) < lValueNew ) + { + Abc_NodeSetLValue( pObj, lValueNew ); + fChange = 1; + } + } + // propagate values through the latches + Vec_PtrForEachEntry( vLatches, pObj, i ) + Abc_NodeSetLValue( Abc_ObjFanout0(pObj), Abc_NodeGetLValue(Abc_ObjFanin0(Abc_ObjFanin0(pObj))) - Fi ); + return fChange; +} + +/**Function************************************************************* + + Synopsis [Detects the case when l-values exceeded the limit.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimePosOverLimit( Abc_Ntk_t * pNtk, int Fi ) +{ + Abc_Obj_t * pObj; + int i; + Abc_NtkForEachPo( pNtk, pObj, i ) + if ( Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Collects latches in the topological order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_ManCollectLatches_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLatches ) +{ + Abc_Obj_t * pDriver; + if ( !Abc_ObjIsLatch(pObj) ) + return; + // skip already collected latches + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent(pObj); + // get the driver node feeding into the latch + pDriver = Abc_ObjFanin0(Abc_ObjFanin0(pObj)); + // call recursively if the driver looks like a latch output + if ( Abc_ObjIsBo(pDriver) ) + Abc_ManCollectLatches_rec( Abc_ObjFanin0(pDriver), vLatches ); + // collect the latch + Vec_PtrPush( vLatches, pObj ); +} + +/**Function************************************************************* + + Synopsis [Collects latches in the topological order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Abc_ManCollectLatches( Abc_Ntk_t * pNtk ) +{ + Vec_Ptr_t * vLatches; + Abc_Obj_t * pObj; + int i; + vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) ); + Abc_NtkIncrementTravId( pNtk ); + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_ManCollectLatches_rec( pObj, vLatches ); + assert( Vec_PtrSize(vLatches) == Abc_NtkLatchNum(pNtk) ); + return vLatches; +} + +/**Function************************************************************* + + Synopsis [Implements the retiming given as the array of retiming lags.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose ) +{ + Abc_Obj_t * pObj; + int fChanges, fForward, nTotalMoves, Lag, Counter, i; + // iterate over the nodes + nTotalMoves = 0; + do { + fChanges = 0; + Abc_NtkForEachNode( pNtk, pObj, i ) + { + Lag = Vec_IntEntry( vLags, pObj->Id ); + if ( !Lag ) + continue; + fForward = (Lag < 0); + if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) ) + { + Abc_NtkRetimeNode( pObj, fForward, 0 ); + fChanges = 1; + nTotalMoves++; + Vec_IntAddToEntry( vLags, pObj->Id, fForward? 1 : -1 ); + } + } + } while ( fChanges ); + if ( fVerbose ) + printf( "Total latch moves = %d.\n", nTotalMoves ); + // check if there are remaining lags + Counter = 0; + Abc_NtkForEachNode( pNtk, pObj, i ) + Counter += (Vec_IntEntry( vLags, pObj->Id ) != 0); + if ( Counter ) + printf( "Warning! The number of nodes with unrealized lag = %d.\n", Counter ); + return 1; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/ret/ret_.c b/src/opt/ret/ret_.c new file mode 100644 index 00000000..89625e17 --- /dev/null +++ b/src/opt/ret/ret_.c @@ -0,0 +1,48 @@ +/**CFile**************************************************************** + + FileName [ret_.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Retiming package.] + + Synopsis [] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - Oct 31, 2006.] + + Revision [$Id: ret_.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "retInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |