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