From da5e0785dfb98335bd49a13bf9e86e736fb931be Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 11 Nov 2006 08:01:00 -0800 Subject: Version abc61111 --- src/opt/ret/module.make | 13 +- src/opt/ret/retArea.c | 202 ++++++++++++--------- src/opt/ret/retBwd.c | 65 ------- src/opt/ret/retCore.c | 56 +++++- src/opt/ret/retDelay.c | 236 ++++++++++++++++++++++++- src/opt/ret/retFlow.c | 12 ++ src/opt/ret/retFwd.c | 65 ------- src/opt/ret/retIncrem.c | 460 ++++++++++++++++++++++++++++++++++++++++++++++++ src/opt/ret/retInit.c | 311 ++++++++++++++++++++++++++++++-- src/opt/ret/retInt.h | 24 ++- 10 files changed, 1188 insertions(+), 256 deletions(-) delete mode 100644 src/opt/ret/retBwd.c delete mode 100644 src/opt/ret/retFwd.c create mode 100644 src/opt/ret/retIncrem.c (limited to 'src/opt/ret') diff --git a/src/opt/ret/module.make b/src/opt/ret/module.make index 9ac0bf1f..c65021c4 100644 --- a/src/opt/ret/module.make +++ b/src/opt/ret/module.make @@ -1,8 +1,7 @@ -SRC += src/opt/dec/retArea.c \ - src/opt/dec/retBwd.c \ - src/opt/dec/retCore.c \ - src/opt/dec/retDelay.c \ - src/opt/dec/retFlow.c \ - src/opt/dec/retFwd.c \ - src/opt/dec/retInit.c +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 diff --git a/src/opt/ret/retArea.c b/src/opt/ret/retArea.c index 7f93b87b..41d19592 100644 --- a/src/opt/ret/retArea.c +++ b/src/opt/ret/retArea.c @@ -50,38 +50,36 @@ extern Abc_Ntk_t * Abc_NtkAttachBottom( Abc_Ntk_t * pNtkTop, Abc_Ntk_t * pNtkBot SeeAlso [] ***********************************************************************/ -int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fVerbose ) +int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose ) { - Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom, * pNtkMiter; - Vec_Int_t * vValues; + Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom; + Vec_Int_t * vValuesNew = NULL, * vValues; int nLatches = Abc_NtkLatchNum(pNtk); + 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 - vValues = Abc_NtkCollectLatchValues( pNtk ); // Abc_NtkRetimeMinAreaFwd( pNtk, fVerbose ); - pNtkTotal = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ); - -// while ( Abc_NtkRetimeMinAreaFwd( pNtk, fVerbose ) ); +// pNtkTotal = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ); + if ( !fBackwardOnly ) + while ( Abc_NtkRetimeMinAreaFwd( pNtk, fVerbose ) ); + // remember initial values + vValues = Abc_NtkCollectLatchValues( pNtk ); // perform backward retiming -// while ( pNtkBottom = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ) ) -// pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom ); + if ( !fForwardOnly ) +// pNtkTotal = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ); + while ( pNtkBottom = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ) ) + pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom ); // compute initial values - if ( pNtkTotal ) - { - // convert the target network to AIG - Abc_NtkLogicToAig( pNtkTotal ); - // get the miter - pNtkMiter = Abc_NtkCreateTarget( pNtkTotal, pNtkTotal->vCos, vValues ); - Abc_NtkDelete( pNtkTotal ); - // get the initial values - Abc_NtkRetimeInitialValues( pNtk, pNtkMiter, fVerbose ); - Abc_NtkDelete( pNtkMiter ); - } - Vec_IntFree( vValues ); + 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 Abc_NtkLogicMakeSimpleCos( pNtk, 0 ); // check for correctness @@ -309,46 +307,6 @@ void Abc_NtkRetimeMinAreaRemoveBuffers( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuffers ) Vec_PtrFree( vBuffers ); } -/**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 [Compute initial values.] @@ -369,7 +327,7 @@ int Abc_NtkRetimeMinAreaInitValue_rec( Abc_Obj_t * pObj ) return (int)pObj->pCopy; Abc_NodeSetTravIdCurrent(pObj); // consider the case of a latch output - if ( Abc_ObjIsBi(pObj) ) + if ( Abc_ObjIsBo(pObj) ) { assert( Abc_ObjIsLatch(Abc_ObjFanin0(pObj)) ); pObj->pCopy = (void *)Abc_NtkRetimeMinAreaInitValue_rec( Abc_ObjFanin0(pObj) ); @@ -431,8 +389,11 @@ Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t return pObj->pCopy; Abc_NodeSetTravIdCurrent(pObj); // consider the case of a latch output - if ( Abc_ObjIsBo(pObj) ) - return Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) ); + 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 ) @@ -462,7 +423,7 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin int i; // create new network pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 ); - // set mapping of new latches into the PIs of the network + // map new latches into PIs of the new network Abc_NtkIncrementTravId(pNtk); Vec_PtrForEachEntry( vMinCut, pObj, i ) { @@ -475,6 +436,9 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin 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 ); // assign dummy node names Abc_NtkAddDummyPiNames( pNtkNew ); Abc_NtkAddDummyPoNames( pNtkNew ); @@ -483,6 +447,76 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin return pNtkNew; } +/**Function************************************************************* + + Synopsis [Mark the inside of the min-cut with current traversal ID.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeMinAreaMarkInside_rec( Abc_Obj_t * pObj, int fForward ) +{ + Abc_Obj_t * pNext; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent( pObj ); + // make sure we never reach PIs/POs/latches + if ( Abc_ObjIsPi(pObj) || Abc_ObjIsPo(pObj) || Abc_ObjIsLatch(pObj) ) + printf( "Abc_NtkRetimeMinAreaMarkInside(): The set of nodes is not a cut. Internal error!!!\n" ); + // continue to explore the cone + if ( fForward ) + { + Abc_ObjForEachFanout( pObj, pNext, i ) + Abc_NtkRetimeMinAreaMarkInside_rec( pNext, fForward ); + } + else + { + Abc_ObjForEachFanin( pObj, pNext, i ) + Abc_NtkRetimeMinAreaMarkInside_rec( pNext, fForward ); + } +} + +/**Function************************************************************* + + Synopsis [Marks the inside of the min-cut with current traversal ID.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkRetimeMinAreaMarkInside( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) +{ + Abc_Obj_t * pObj; + int i; + // mark the mincut + Abc_NtkIncrementTravId(pNtk); + Vec_PtrForEachEntry( vMinCut, pObj, i ) + Abc_NodeSetTravIdCurrent( pObj ); + // mark the area inside of the cut + if ( fForward ) + { + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_NtkRetimeMinAreaMarkInside_rec( Abc_ObjFanout0(pObj), fForward ); + } + else + { + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_NtkRetimeMinAreaMarkInside_rec( Abc_ObjFanin0(pObj), fForward ); + // unmark the nodes in the cut + Vec_PtrForEachEntry( vMinCut, pObj, i ) + Abc_NodeSetTravIdPrevious( pObj ); + } +} + /**Function************************************************************* Synopsis [Updates the network after backward retiming.] @@ -496,9 +530,11 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin ***********************************************************************/ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) { - Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vFanouts; - Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pFanout; + Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes; + Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext; int i, k; + // mark the inside of min-cut with new trav ID + Abc_NtkRetimeMinAreaMarkInside( pNtk, vMinCut, fForward ); // create new latches Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) ); Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) ); @@ -511,8 +547,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i if ( !Abc_ObjIsLatch(pObj) ) Vec_PtrPush( vBoxesNew, pObj ); // create or reuse latches - Abc_NtkIncrementTravId(pNtk); - vFanouts = Vec_PtrAlloc( 100 ); + vNodes = Vec_PtrAlloc( 100 ); Vec_PtrForEachEntry( vMinCut, pObj, i ) { if ( Abc_ObjIsCi(pObj) && fForward ) @@ -520,7 +555,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i pLatchOut = pObj; pLatch = Abc_ObjFanin0(pLatchOut); pLatchIn = Abc_ObjFanin0(pLatch); - assert( Abc_ObjIsBi(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBo(pLatchIn) ); + assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) ); // mark the latch as reused Abc_NodeSetTravIdCurrent( pLatch ); } @@ -529,15 +564,15 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i pLatchIn = pObj; pLatch = Abc_ObjFanout0(pLatchIn); pLatchOut = Abc_ObjFanout0(pLatch); - assert( Abc_ObjIsBi(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBo(pLatchIn) ); + assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) ); // mark the latch as reused Abc_NodeSetTravIdCurrent( pLatch ); } else { - pLatchOut = Abc_NtkCreateBi(pNtk); + pLatchOut = Abc_NtkCreateBo(pNtk); pLatch = Abc_NtkCreateLatch(pNtk); - pLatchIn = Abc_NtkCreateBo(pNtk); + pLatchIn = Abc_NtkCreateBi(pNtk); Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatchOut), NULL ); Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatchIn), NULL ); // connect @@ -545,16 +580,20 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i Abc_ObjAddFanin( pLatch, pLatchIn ); if ( fForward ) { - Abc_ObjTransferFanout( pObj, pLatchOut ); 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 ( !Abc_NodeIsTravIdCurrent(pNext) ) + Abc_ObjPatchFanin( pNext, pObj, pLatchOut ); } else { - // redirect unmarked edges - Abc_NodeCollectFanouts( pObj, vFanouts ); - Vec_PtrForEachEntry( vFanouts, pFanout, k ) - if ( !pFanout->fMarkA ) - Abc_ObjPatchFanin( pFanout, pObj, pLatchOut ); + // redirect edges to the visited fanouts of the node + Abc_NodeCollectFanouts( pObj, vNodes ); + Vec_PtrForEachEntry( vNodes, pNext, k ) + if ( Abc_NodeIsTravIdCurrent(pNext) ) + Abc_ObjPatchFanin( pNext, pObj, pLatchOut ); } // connect latch to the node Abc_ObjAddFanin( pLatchIn, pObj ); @@ -563,7 +602,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i Vec_PtrPush( vBoxesNew, pLatch ); Vec_PtrPush( vCos, pLatchIn ); } - Vec_PtrFree( vFanouts ); + Vec_PtrFree( vNodes ); // remove useless latches Vec_PtrForEachEntry( vBoxes, pObj, i ) { @@ -574,7 +613,8 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i pLatchOut = Abc_ObjFanout0(pObj); pLatch = pObj; pLatchIn = Abc_ObjFanin0(pObj); - Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) ); + if ( Abc_ObjFanoutNum(pLatchOut) > 0 ) + Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) ); Abc_NtkDeleteObj( pLatchOut ); Abc_NtkDeleteObj( pObj ); Abc_NtkDeleteObj( pLatchIn ); diff --git a/src/opt/ret/retBwd.c b/src/opt/ret/retBwd.c deleted file mode 100644 index 7eefc4e0..00000000 --- a/src/opt/ret/retBwd.c +++ /dev/null @@ -1,65 +0,0 @@ -/**CFile**************************************************************** - - FileName [retBwd.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Retiming package.] - - Synopsis [Most backward retiming.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - Oct 31, 2006.] - - Revision [$Id: retBwd.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "retInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeBackward( Abc_Ntk_t * pNtk, int fVerbose ) -{ - printf( "Not implemented.\n" ); - return 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/ret/retCore.c b/src/opt/ret/retCore.c index 541f5962..8ef4e79b 100644 --- a/src/opt/ret/retCore.c +++ b/src/opt/ret/retCore.c @@ -24,6 +24,8 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +int timeRetime = 0; + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -39,36 +41,74 @@ SeeAlso [] ***********************************************************************/ -int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fVerbose ) +int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOnly, int fVerbose ) { - int RetValue; + int nLatches = Abc_NtkLatchNum(pNtk); + int nLevels = Abc_NtkGetLevelNum(pNtk); + int RetValue = 0, clkTotal = clock(); assert( Mode > 0 && Mode < 6 ); + assert( !fForwardOnly || !fBackwardOnly ); // perform forward retiming switch ( Mode ) { case 1: // forward - RetValue = Abc_NtkRetimeForward( pNtk, fVerbose ); + RetValue = Abc_NtkRetimeIncremental( pNtk, 1, 0, fVerbose ); break; case 2: // backward - RetValue = Abc_NtkRetimeBackward( pNtk, fVerbose ); + RetValue = Abc_NtkRetimeIncremental( pNtk, 0, 0, fVerbose ); break; case 3: // min-area - RetValue = Abc_NtkRetimeMinArea( pNtk, fVerbose ); + RetValue = Abc_NtkRetimeMinArea( pNtk, fForwardOnly, fBackwardOnly, fVerbose ); break; case 4: // min-delay - RetValue = Abc_NtkRetimeMinDelay( pNtk, fVerbose ); + if ( !fBackwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 1, 1, fVerbose ); + if ( !fForwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 0, 1, fVerbose ); break; case 5: // min-area + min-delay - RetValue = Abc_NtkRetimeMinArea( pNtk, fVerbose ); - RetValue += Abc_NtkRetimeMinDelay( pNtk, fVerbose ); + RetValue = Abc_NtkRetimeMinArea( pNtk, fForwardOnly, fBackwardOnly, fVerbose ); + if ( !fBackwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 1, 1, fVerbose ); + if ( !fForwardOnly ) + RetValue += Abc_NtkRetimeIncremental( pNtk, 0, 1, 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_NtkGetLevelNum(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_NtkLogicToSop( pNtk, 0 ); + pNtkRet = Abc_NtkDup( pNtk ); + Abc_NtkRetime( pNtkRet, 3, 0, 1, 0 ); + 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 index b7ccc570..d2d87447 100644 --- a/src/opt/ret/retDelay.c +++ b/src/opt/ret/retDelay.c @@ -24,30 +24,44 @@ /// 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 [] + Synopsis [Retimes incrementally for minimum delay.] - Description [] + 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, int fVerbose ) +int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nIterLimit, int fForward, int fVerbose ) { - printf( "Not implemented.\n" ); - return 0; + 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 [] + Synopsis [Returns the best delay and the number of best iteration.] Description [] @@ -56,7 +70,217 @@ int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, int fVerbose ) 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; + // 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 ); + } + } + // find the best iteration + DelayBest = ABC_INFINITY; IterBest = 0; + 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 ) + { + DelayBest = DelayCur; + IterBest = i; + } + // quit after timing analysis + if ( i == nIterLimit ) + break; + // try retiming to improve the delay + Vec_PtrForEachEntry( vCritical, pObj, k ) + if ( Abc_NtkRetimeNodeIsEnabled(pObj, fForward) ) + Abc_NtkRetimeNode( pObj, fForward, 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 ( !fInitial && fVerbose ) + printf( "%s : Starting delay = %3d. Final delay = %3d. IterBest = %2d (out of %2d).\n", + fForward? "Forward " : "Backward", DelayStart, DelayBest, IterBest, nIterLimit ); + *pIterBest = 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 index 9b8393f3..642a1f69 100644 --- a/src/opt/ret/retFlow.c +++ b/src/opt/ret/retFlow.c @@ -126,9 +126,12 @@ Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose ) printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" ); // report the results + if ( fVerbose ) + { printf( "Latches = %6d. %s max-flow = %6d. Min-cut = %6d. ", Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) ); PRT( "Time", clock() - clk ); + } // Abc_NtkMaxFlowPrintCut( vMinCut ); return vMinCut; @@ -377,6 +380,15 @@ int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int 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; } diff --git a/src/opt/ret/retFwd.c b/src/opt/ret/retFwd.c deleted file mode 100644 index c33abc30..00000000 --- a/src/opt/ret/retFwd.c +++ /dev/null @@ -1,65 +0,0 @@ -/**CFile**************************************************************** - - FileName [retFwd.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Retiming package.] - - Synopsis [Most forward retiming.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - Oct 31, 2006.] - - Revision [$Id: retFwd.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "retInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkRetimeForward( Abc_Ntk_t * pNtk, int fVerbose ) -{ - printf( "Not implemented.\n" ); - return 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/ret/retIncrem.c b/src/opt/ret/retIncrem.c new file mode 100644 index 00000000..d2ad6a72 --- /dev/null +++ b/src/opt/ret/retIncrem.c @@ -0,0 +1,460 @@ +/**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 st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk ); +static int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nIdMaxStart ); +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 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 = 2 * Abc_NtkGetLevelNum(pNtk); + pNtkCopy = Abc_NtkDup( pNtk ); + tLatches = Abc_NtkRetimePrepareLatches( pNtkCopy ); + st_free_table( tLatches ); + } + // collect latches and remove CIs/COs + tLatches = Abc_NtkRetimePrepareLatches( pNtk ); + // 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 ); + // 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); + 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( pLatchIn, Abc_ObjName(pLatchIn), NULL ); + Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatchOut), NULL ); + } + 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 ); + 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 = 5000; + 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); + 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 ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pFanin, * pLatch, * pLatchTop, * pLatchCur; + int i, k; + vNodes = Vec_PtrAlloc( 10 ); + // consider latch fanins + Abc_NtkForEachObj( pNtk, pLatch, i ) + { + if ( !Abc_ObjIsLatch(pLatch) ) + continue; + pFanin = Abc_ObjFanin0(pLatch); + if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 ) + continue; + // get the first latch + Abc_ObjForEachFanout( pFanin, pLatchTop, k ) + if ( Abc_ObjIsLatch(pLatchTop) ) + break; + assert( Abc_ObjIsLatch(pLatchTop) ); + // redirect compatible fanout latches to the first latch + Abc_NodeCollectFanouts( pFanin, vNodes ); + Vec_PtrForEachEntry( vNodes, pLatchCur, k ) + { + if ( pLatchCur == pLatchTop ) + continue; + if ( !Abc_ObjIsLatch(pLatchCur) ) + continue; + if ( pLatchCur->pData != pLatchTop->pData ) + continue; + // 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 index 169d5a63..3eb80da1 100644 --- a/src/opt/ret/retInit.c +++ b/src/opt/ret/retInit.c @@ -1,12 +1,12 @@ /**CFile**************************************************************** - FileName [ret_.c] + FileName [retInit.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Retiming package.] - Synopsis [] + Synopsis [Initial state computation for backward retiming.] Author [Alan Mishchenko] @@ -14,7 +14,7 @@ Date [Ver. 1.0. Started - Oct 31, 2006.] - Revision [$Id: ret_.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] + Revision [$Id: retInit.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $] ***********************************************************************/ @@ -24,6 +24,8 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +static int Abc_NtkRetimeVerifyModel( Abc_Ntk_t * pNtkCone, Vec_Int_t * vValues, int * pModel ); + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -39,29 +41,306 @@ SeeAlso [] ***********************************************************************/ -void Abc_NtkRetimeInitialValues( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkMiter, int fVerbose ) +Vec_Int_t * Abc_NtkRetimeInitialValues( Abc_Ntk_t * pNtkCone, Vec_Int_t * vValues, int fVerbose ) { - Abc_Obj_t * pLatch; - int * pModel, RetValue, clk, i; + 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_NtkLogicToAig( pNtkLogic ); + // get the miter + pNtkMiter = Abc_NtkCreateTarget( pNtkLogic, pNtkLogic->vCos, vValues ); if ( fVerbose ) - printf( "The number of ANDs in the AIG = %5d.\n", Abc_NtkNodeNum(pNtkMiter) ); + printf( "The miter for initial state computation has %d AIG nodes. ", Abc_NtkNodeNum(pNtkMiter) ); // solve the miter -clk = clock(); + clk = clock(); RetValue = Abc_NtkMiterSat( pNtkMiter, (sint64)500000, (sint64)50000000, 0, 0, NULL, NULL ); -if ( fVerbose && clock() - clk > 100 ) -{ -PRT( "SAT solving time", clock() - clk ); -} + 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 - pModel = pNtkMiter->pModel; pNtkMiter->pModel = NULL; - Abc_NtkForEachLatch( pNtk, pLatch, i ) - pLatch->pData = (void *)(pModel? (pModel[i]? ABC_INIT_ONE : ABC_INIT_ZERO) : ABC_INIT_DC); - FREE( pModel ); + 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) ); + pObj = Abc_NtkPo(pNtkNew, 0); + // 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); } //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/ret/retInt.h b/src/opt/ret/retInt.h index 2cb465fa..9b3aa00a 100644 --- a/src/opt/ret/retInt.h +++ b/src/opt/ret/retInt.h @@ -44,20 +44,28 @@ //////////////////////////////////////////////////////////////////////// /*=== retArea.c ========================================================*/ -extern int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fVerbose ); -/*=== retBwd.c ========================================================*/ -extern int Abc_NtkRetimeBackward( Abc_Ntk_t * pNtk, int fVerbose ); +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 fVerbose ); +extern int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOnly, int fVerbose ); /*=== retDelay.c ========================================================*/ -extern int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, int fVerbose ); +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 fVerbose ); +extern void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk ); +extern int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward ); +extern void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial ); /*=== retFlow.c ========================================================*/ extern void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk ); extern Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose ); -/*=== retFwd.c ========================================================*/ -extern int Abc_NtkRetimeForward( Abc_Ntk_t * pNtk, int fVerbose ); /*=== retInit.c ========================================================*/ -extern void Abc_NtkRetimeInitialValues( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkMiter, int fVerbose ); +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 ); #endif -- cgit v1.2.3