summaryrefslogtreecommitdiffstats
path: root/src/opt
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt')
-rw-r--r--src/opt/cut/abcCut.c2
-rw-r--r--src/opt/dec/decAbc.c22
-rw-r--r--src/opt/ret/module.make3
-rw-r--r--src/opt/ret/retArea.c331
-rw-r--r--src/opt/ret/retCore.c26
-rw-r--r--src/opt/ret/retDelay.c24
-rw-r--r--src/opt/ret/retFlow.c370
-rw-r--r--src/opt/ret/retIncrem.c44
-rw-r--r--src/opt/ret/retInit.c1
-rw-r--r--src/opt/ret/retInt.h6
-rw-r--r--src/opt/ret/retLvalue.c419
11 files changed, 941 insertions, 307 deletions
diff --git a/src/opt/cut/abcCut.c b/src/opt/cut/abcCut.c
index 35814593..3b70e9c1 100644
--- a/src/opt/cut/abcCut.c
+++ b/src/opt/cut/abcCut.c
@@ -218,6 +218,7 @@ void Abc_NtkCutsOracle( Abc_Ntk_t * pNtk, Cut_Oracle_t * p )
***********************************************************************/
Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams )
{
+/*
Cut_Man_t * p;
Abc_Obj_t * pObj, * pNode;
int i, nIters, fStatus;
@@ -303,6 +304,7 @@ printf( "Converged after %d iterations.\n", nIters );
}
//Abc_NtkPrintCuts( p, pNtk, 1 );
return p;
+*/
}
/**Function*************************************************************
diff --git a/src/opt/dec/decAbc.c b/src/opt/dec/decAbc.c
index 23d60826..bd960c14 100644
--- a/src/opt/dec/decAbc.c
+++ b/src/opt/dec/decAbc.c
@@ -214,26 +214,26 @@ void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, bool fUpda
SeeAlso []
***********************************************************************/
-Aig_Obj_t * Dec_GraphToNetworkAig( Aig_Man_t * pMan, Dec_Graph_t * pGraph )
+Hop_Obj_t * Dec_GraphToNetworkAig( Hop_Man_t * pMan, Dec_Graph_t * pGraph )
{
Dec_Node_t * pNode;
- Aig_Obj_t * pAnd0, * pAnd1;
+ Hop_Obj_t * pAnd0, * pAnd1;
int i;
// check for constant function
if ( Dec_GraphIsConst(pGraph) )
- return Aig_NotCond( Aig_ManConst1(pMan), Dec_GraphIsComplement(pGraph) );
+ return Hop_NotCond( Hop_ManConst1(pMan), Dec_GraphIsComplement(pGraph) );
// check for a literal
if ( Dec_GraphIsVar(pGraph) )
- return Aig_NotCond( Dec_GraphVar(pGraph)->pFunc, Dec_GraphIsComplement(pGraph) );
+ return Hop_NotCond( Dec_GraphVar(pGraph)->pFunc, Dec_GraphIsComplement(pGraph) );
// build the AIG nodes corresponding to the AND gates of the graph
Dec_GraphForEachNode( pGraph, pNode, i )
{
- pAnd0 = Aig_NotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl );
- pAnd1 = Aig_NotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl );
- pNode->pFunc = Aig_And( pMan, pAnd0, pAnd1 );
+ pAnd0 = Hop_NotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl );
+ pAnd1 = Hop_NotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl );
+ pNode->pFunc = Hop_And( pMan, pAnd0, pAnd1 );
}
// complement the result if necessary
- return Aig_NotCond( pNode->pFunc, Dec_GraphIsComplement(pGraph) );
+ return Hop_NotCond( pNode->pFunc, Dec_GraphIsComplement(pGraph) );
}
/**Function*************************************************************
@@ -247,9 +247,9 @@ Aig_Obj_t * Dec_GraphToNetworkAig( Aig_Man_t * pMan, Dec_Graph_t * pGraph )
SeeAlso []
***********************************************************************/
-Aig_Obj_t * Dec_GraphFactorSop( Aig_Man_t * pMan, char * pSop )
+Hop_Obj_t * Dec_GraphFactorSop( Hop_Man_t * pMan, char * pSop )
{
- Aig_Obj_t * pFunc;
+ Hop_Obj_t * pFunc;
Dec_Graph_t * pFForm;
Dec_Node_t * pNode;
int i;
@@ -257,7 +257,7 @@ Aig_Obj_t * Dec_GraphFactorSop( Aig_Man_t * pMan, char * pSop )
pFForm = Dec_Factor( pSop );
// collect the fanins
Dec_GraphForEachLeaf( pFForm, pNode, i )
- pNode->pFunc = Aig_IthVar( pMan, i );
+ pNode->pFunc = Hop_IthVar( pMan, i );
// perform strashing
pFunc = Dec_GraphToNetworkAig( pMan, pFForm );
Dec_GraphFree( pFForm );
diff --git a/src/opt/ret/module.make b/src/opt/ret/module.make
index c65021c4..4b14365e 100644
--- a/src/opt/ret/module.make
+++ b/src/opt/ret/module.make
@@ -3,5 +3,6 @@ SRC += src/opt/ret/retArea.c \
src/opt/ret/retDelay.c \
src/opt/ret/retFlow.c \
src/opt/ret/retIncrem.c \
- src/opt/ret/retInit.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
index 41d19592..5eec8e80 100644
--- a/src/opt/ret/retArea.c
+++ b/src/opt/ret/retArea.c
@@ -24,12 +24,9 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-static int Abc_NtkRetimeMinAreaFwd( Abc_Ntk_t * pNtk, int fVerbose );
-static Abc_Ntk_t * Abc_NtkRetimeMinAreaBwd( Abc_Ntk_t * pNtk, int fVerbose );
+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 Vec_Ptr_t * Abc_NtkRetimeMinAreaAddBuffers( Abc_Ntk_t * pNtk );
-static void Abc_NtkRetimeMinAreaRemoveBuffers( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuffers );
-static void Abc_NtkRetimeMinAreaInitValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
+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 );
@@ -55,6 +52,7 @@ int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly,
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) );
@@ -62,17 +60,24 @@ int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly,
// reorder CI/CO/latch inputs
Abc_NtkOrderCisCos( pNtk );
// perform forward retiming
-// Abc_NtkRetimeMinAreaFwd( pNtk, fVerbose );
-// pNtkTotal = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose );
if ( !fBackwardOnly )
- while ( Abc_NtkRetimeMinAreaFwd( pNtk, fVerbose ) );
+ {
+ 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 )
-// pNtkTotal = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose );
- while ( pNtkBottom = Abc_NtkRetimeMinAreaBwd( pNtk, fVerbose ) )
- pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom );
+ {
+ 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 );
@@ -80,8 +85,8 @@ int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly,
Abc_NtkInsertLatchValues( pNtk, vValuesNew );
if ( vValuesNew ) Vec_IntFree( vValuesNew );
if ( vValues ) Vec_IntFree( vValues );
- // fix the COs
- Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
+ // 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" );
@@ -91,7 +96,7 @@ int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly,
/**Function*************************************************************
- Synopsis [Performs min-area retiming forward.]
+ Synopsis [Performs min-area retiming backward.]
Description []
@@ -100,33 +105,35 @@ int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly,
SeeAlso []
***********************************************************************/
-int Abc_NtkRetimeMinAreaFwd( Abc_Ntk_t * pNtk, int fVerbose )
-{
- Vec_Ptr_t * vBuffers, * vMinCut;
+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 TFO(PIs)
- Abc_NtkRetimeMinAreaPrepare( pNtk, 1 );
- // add buffers on edges feeding into the marked nodes
- vBuffers = Abc_NtkRetimeMinAreaAddBuffers( pNtk );
+ // mark current latches and TFI(POs)
+ Abc_NtkRetimeMinAreaPrepare( pNtk, fForward );
// run the maximum forward flow
- vMinCut = Abc_NtkMaxFlow( pNtk, 1, fVerbose );
- assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) );
+ 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) )
{
- Abc_NtkRetimeMinAreaInitValue( pNtk, vMinCut );
- Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, 1 );
+ pNtkNew = (Abc_Ntk_t *)1;
+ if ( fForward )
+ Abc_NtkRetimeMinAreaInitValues( pNtk, vMinCut );
+ else
+ pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut );
+ Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, fForward );
}
// clean up
- Abc_NtkRetimeMinAreaRemoveBuffers( pNtk, vBuffers );
Vec_PtrFree( vMinCut );
Abc_NtkCleanMarkA( pNtk );
- return nLatches - Abc_NtkLatchNum(pNtk);
+ return pNtkNew;
}
/**Function*************************************************************
- Synopsis [Performs min-area retiming backward.]
+ Synopsis [Marks the cone with MarkA.]
Description []
@@ -135,26 +142,23 @@ int Abc_NtkRetimeMinAreaFwd( Abc_Ntk_t * pNtk, int fVerbose )
SeeAlso []
***********************************************************************/
-Abc_Ntk_t * Abc_NtkRetimeMinAreaBwd( Abc_Ntk_t * pNtk, int fVerbose )
+void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward )
{
- Abc_Ntk_t * pNtkNew = NULL;
- Vec_Ptr_t * vMinCut;
- int nLatches = Abc_NtkLatchNum(pNtk);
- // mark current latches and TFI(POs)
- Abc_NtkRetimeMinAreaPrepare( pNtk, 0 );
- // run the maximum forward flow
- vMinCut = Abc_NtkMaxFlow( pNtk, 0, fVerbose );
- assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) );
- // create new latch boundary if there is improvement
- if ( Vec_PtrSize(vMinCut) < Abc_NtkLatchNum(pNtk) )
+ 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
{
- pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut );
- Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, 0 );
+ Abc_ObjForEachFanin( pObj, pNext, i )
+ Abc_NtkMarkCone_rec( pNext, fForward );
}
- // clean up
- Vec_PtrFree( vMinCut );
- Abc_NtkCleanMarkA( pNtk );
- return pNtkNew;
}
/**Function*************************************************************
@@ -168,22 +172,22 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaBwd( Abc_Ntk_t * pNtk, int fVerbose )
SeeAlso []
***********************************************************************/
-void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward )
+void Abc_NtkUnmarkCone_rec( Abc_Obj_t * pObj, int fForward )
{
Abc_Obj_t * pNext;
int i;
- if ( pObj->fMarkA )
+ if ( !pObj->fMarkA || Abc_ObjIsLatch(pObj) )
return;
- pObj->fMarkA = 1;
+ pObj->fMarkA = 0;
if ( fForward )
{
Abc_ObjForEachFanout( pObj, pNext, i )
- Abc_NtkMarkCone_rec( pNext, fForward );
+ Abc_NtkUnmarkCone_rec( pNext, fForward );
}
else
{
Abc_ObjForEachFanin( pObj, pNext, i )
- Abc_NtkMarkCone_rec( pNext, fForward );
+ Abc_NtkUnmarkCone_rec( pNext, fForward );
}
}
@@ -200,8 +204,9 @@ void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward )
***********************************************************************/
void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward )
{
- Abc_Obj_t * pObj;
- int i;
+ Vec_Ptr_t * vNodes;
+ Abc_Obj_t * pObj, * pFanin;
+ int i, k;
if ( fForward )
{
// mark the frontier
@@ -212,9 +217,20 @@ void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward )
pObj->fMarkA = 1;
Abc_ObjFanin0(pObj)->fMarkA = 1;
}
- // mark the nodes reachable from the POs
+ // 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
{
@@ -234,81 +250,6 @@ void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward )
/**Function*************************************************************
- Synopsis [Add extra buffers.]
-
- Description [This is needed to make sure that forward retiming
- works correctly. This has to do with the nodes in the TFO cone
- of the PIs having multiple incoming edges.]
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-Vec_Ptr_t * Abc_NtkRetimeMinAreaAddBuffers( Abc_Ntk_t * pNtk )
-{
- Vec_Ptr_t * vFeeds, * vFanouts;
- Abc_Obj_t * pObj, * pFanin, * pFanout, * pBuffer;
- int i, k;
- // collect all nodes that are feeding into the marked nodes
- Abc_NtkIncrementTravId(pNtk);
- vFeeds = Vec_PtrAlloc( 100 );
- Abc_NtkForEachObj( pNtk, pObj, i )
- {
- if ( !pObj->fMarkA )
- continue;
- Abc_ObjForEachFanin( pObj, pFanin, k )
- if ( !pFanin->fMarkA && !Abc_NodeIsTravIdCurrent(pFanin) )
- {
- Abc_NodeSetTravIdCurrent( pFanin );
- Vec_PtrPush( vFeeds, pFanin );
- }
- }
- // add buffers for each such node
- vFanouts = Vec_PtrAlloc( 100 );
- Vec_PtrForEachEntry( vFeeds, pObj, i )
- {
- // create and remember the buffers
- pBuffer = Abc_NtkCreateNodeBuf( pNtk, pObj );
- Vec_PtrWriteEntry( vFeeds, i, pBuffer );
- // patch the fanin of each marked fanout to point to the buffer
- Abc_NodeCollectFanouts( pObj, vFanouts );
- Vec_PtrForEachEntry( vFanouts, pFanout, k )
- if ( pFanout->fMarkA )
- Abc_ObjPatchFanin( pFanout, pObj, pBuffer );
- }
- Vec_PtrFree( vFanouts );
- // mark the new buffers
- Vec_PtrForEachEntry( vFeeds, pObj, i )
- pObj->fMarkA = 1;
- return vFeeds;
-}
-
-/**Function*************************************************************
-
- Synopsis [Removes extra buffers.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_NtkRetimeMinAreaRemoveBuffers( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuffers )
-{
- Abc_Obj_t * pObj;
- int i;
- Vec_PtrForEachEntry( vBuffers, pObj, i )
- {
- Abc_ObjTransferFanout( pObj, Abc_ObjFanin0(pObj) );
- Abc_NtkDeleteObj( pObj );
- }
- Vec_PtrFree( vBuffers );
-}
-
-/**Function*************************************************************
-
Synopsis [Compute initial values.]
Description []
@@ -318,7 +259,7 @@ void Abc_NtkRetimeMinAreaRemoveBuffers( Abc_Ntk_t * pNtk, Vec_Ptr_t * vBuffers )
SeeAlso []
***********************************************************************/
-int Abc_NtkRetimeMinAreaInitValue_rec( Abc_Obj_t * pObj )
+int Abc_NtkRetimeMinAreaInitValues_rec( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanin;
int i;
@@ -330,13 +271,13 @@ int Abc_NtkRetimeMinAreaInitValue_rec( Abc_Obj_t * pObj )
if ( Abc_ObjIsBo(pObj) )
{
assert( Abc_ObjIsLatch(Abc_ObjFanin0(pObj)) );
- pObj->pCopy = (void *)Abc_NtkRetimeMinAreaInitValue_rec( 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_NtkRetimeMinAreaInitValue_rec( pFanin );
+ Abc_NtkRetimeMinAreaInitValues_rec( pFanin );
// compute the value of the node
pObj->pCopy = (void *)Abc_ObjSopSimulate(pObj);
return (int)pObj->pCopy;
@@ -353,7 +294,7 @@ int Abc_NtkRetimeMinAreaInitValue_rec( Abc_Obj_t * pObj )
SeeAlso []
***********************************************************************/
-void Abc_NtkRetimeMinAreaInitValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
+void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
{
Abc_Obj_t * pObj;
int i;
@@ -366,7 +307,10 @@ void Abc_NtkRetimeMinAreaInitValue( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
}
// propagate initial values
Vec_PtrForEachEntry( vMinCut, pObj, i )
- Abc_NtkRetimeMinAreaInitValue_rec( pObj );
+ Abc_NtkRetimeMinAreaInitValues_rec( pObj );
+ // unmark the latches
+ Abc_NtkForEachLatch( pNtk, pObj, i )
+ Abc_NodeSetTravIdPrevious( pObj );
}
/**Function*************************************************************
@@ -439,6 +383,9 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin
// 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 );
@@ -449,79 +396,10 @@ Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMin
/**Function*************************************************************
- Synopsis [Mark the inside of the min-cut with current traversal ID.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_NtkRetimeMinAreaMarkInside_rec( Abc_Obj_t * pObj, int fForward )
-{
- Abc_Obj_t * pNext;
- int i;
- // skip visited nodes
- if ( Abc_NodeIsTravIdCurrent(pObj) )
- return;
- Abc_NodeSetTravIdCurrent( pObj );
- // make sure we never reach PIs/POs/latches
- if ( Abc_ObjIsPi(pObj) || Abc_ObjIsPo(pObj) || Abc_ObjIsLatch(pObj) )
- printf( "Abc_NtkRetimeMinAreaMarkInside(): The set of nodes is not a cut. Internal error!!!\n" );
- // continue to explore the cone
- if ( fForward )
- {
- Abc_ObjForEachFanout( pObj, pNext, i )
- Abc_NtkRetimeMinAreaMarkInside_rec( pNext, fForward );
- }
- else
- {
- Abc_ObjForEachFanin( pObj, pNext, i )
- Abc_NtkRetimeMinAreaMarkInside_rec( pNext, fForward );
- }
-}
-
-/**Function*************************************************************
-
- Synopsis [Marks the inside of the min-cut with current traversal ID.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_NtkRetimeMinAreaMarkInside( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
-{
- Abc_Obj_t * pObj;
- int i;
- // mark the mincut
- Abc_NtkIncrementTravId(pNtk);
- Vec_PtrForEachEntry( vMinCut, pObj, i )
- Abc_NodeSetTravIdCurrent( pObj );
- // mark the area inside of the cut
- if ( fForward )
- {
- Abc_NtkForEachLatch( pNtk, pObj, i )
- Abc_NtkRetimeMinAreaMarkInside_rec( Abc_ObjFanout0(pObj), fForward );
- }
- else
- {
- Abc_NtkForEachLatch( pNtk, pObj, i )
- Abc_NtkRetimeMinAreaMarkInside_rec( Abc_ObjFanin0(pObj), fForward );
- // unmark the nodes in the cut
- Vec_PtrForEachEntry( vMinCut, pObj, i )
- Abc_NodeSetTravIdPrevious( pObj );
- }
-}
-
-/**Function*************************************************************
-
Synopsis [Updates the network after backward retiming.]
- Description []
+ Description [Assumes that fMarkA denotes all nodes reachabe from
+ the latches toward the cut.]
SideEffects []
@@ -530,11 +408,9 @@ void Abc_NtkRetimeMinAreaMarkInside( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int
***********************************************************************/
void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
{
- Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes;
- Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext;
+ Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes, * vBuffers;
+ Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext, * pBuffer;
int i, k;
- // mark the inside of min-cut with new trav ID
- Abc_NtkRetimeMinAreaMarkInside( pNtk, vMinCut, fForward );
// create new latches
Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) );
Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) );
@@ -548,6 +424,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
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 )
@@ -558,6 +435,27 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
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 )
{
@@ -567,14 +465,15 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
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(pLatchOut), NULL );
- Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatchIn), NULL );
+ Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
+ Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" );
// connect
Abc_ObjAddFanin( pLatchOut, pLatch );
Abc_ObjAddFanin( pLatch, pLatchIn );
@@ -584,7 +483,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
// redirect edges to the unvisited fanouts of the node
Abc_NodeCollectFanouts( pObj, vNodes );
Vec_PtrForEachEntry( vNodes, pNext, k )
- if ( !Abc_NodeIsTravIdCurrent(pNext) )
+ if ( !pNext->fMarkA )
Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
}
else
@@ -592,7 +491,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
// redirect edges to the visited fanouts of the node
Abc_NodeCollectFanouts( pObj, vNodes );
Vec_PtrForEachEntry( vNodes, pNext, k )
- if ( Abc_NodeIsTravIdCurrent(pNext) )
+ if ( pNext->fMarkA )
Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
}
// connect latch to the node
@@ -603,6 +502,13 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
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 )
{
@@ -626,6 +532,7 @@ void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, i
Vec_PtrFree( vBoxes );
}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/opt/ret/retCore.c b/src/opt/ret/retCore.c
index 8ef4e79b..a0e66c92 100644
--- a/src/opt/ret/retCore.c
+++ b/src/opt/ret/retCore.c
@@ -44,11 +44,21 @@ int timeRetime = 0;
int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOnly, int fVerbose )
{
int nLatches = Abc_NtkLatchNum(pNtk);
- int nLevels = Abc_NtkGetLevelNum(pNtk);
+ int nLevels = Abc_NtkLevel(pNtk);
int RetValue = 0, clkTotal = clock();
- assert( Mode > 0 && Mode < 6 );
+ int nNodesOld, nLatchesOld;
+ assert( Mode > 0 && Mode < 7 );
assert( !fForwardOnly || !fBackwardOnly );
- // perform forward retiming
+
+ // 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
@@ -73,6 +83,9 @@ int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOn
if ( !fForwardOnly )
RetValue += Abc_NtkRetimeIncremental( pNtk, 0, 1, fVerbose );
break;
+ case 6: // Pan's algorithm
+ RetValue = Abc_NtkRetimeLValue( pNtk, 200, fVerbose );
+ break;
default:
printf( "Unknown retiming option.\n" );
break;
@@ -80,7 +93,7 @@ int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly, int fBackwardOn
if ( fVerbose )
{
printf( "Reduction in area = %3d. Reduction in delay = %3d. ",
- nLatches - Abc_NtkLatchNum(pNtk), nLevels - Abc_NtkGetLevelNum(pNtk) );
+ nLatches - Abc_NtkLatchNum(pNtk), nLevels - Abc_NtkLevel(pNtk) );
PRT( "Total runtime", clock() - clkTotal );
}
timeRetime = clock() - clkTotal;
@@ -104,8 +117,11 @@ int Abc_NtkRetimeDebug( Abc_Ntk_t * pNtk )
Abc_Ntk_t * pNtkRet;
assert( Abc_NtkIsLogic(pNtk) );
Abc_NtkLogicToSop( 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 );
+ Abc_NtkRetime( pNtkRet, 3, 0, 1, 0 ); // debugging backward flow
return !Abc_NtkSecFraig( pNtk, pNtkRet, 10000, 3, 0 );
}
diff --git a/src/opt/ret/retDelay.c b/src/opt/ret/retDelay.c
index d2d87447..80c75729 100644
--- a/src/opt/ret/retDelay.c
+++ b/src/opt/ret/retDelay.c
@@ -76,7 +76,7 @@ int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int fForward, int fInitial, int
Vec_Ptr_t * vCritical;
Vec_Int_t * vValues;
Abc_Obj_t * pObj;
- int i, k, IterBest, DelayCur, DelayBest, DelayStart;
+ int i, k, IterBest, DelayCur, DelayBest, DelayStart, LatchesBest;
// transfer intitial values
if ( fInitial )
{
@@ -90,8 +90,15 @@ int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int fForward, int fInitial, int
pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
}
}
+if ( fVerbose )
+{
+ if ( !fInitial )
+ printf( "Performing analysis:\n" );
+ else
+ printf( "Moving latches to the best position:\n" );
+}
// find the best iteration
- DelayBest = ABC_INFINITY; IterBest = 0;
+ DelayBest = ABC_INFINITY; IterBest = 0; LatchesBest = Abc_NtkLatchNum(pNtk);
vCritical = Vec_PtrAlloc( 100 );
for ( i = 0; ; i++ )
{
@@ -102,16 +109,29 @@ int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int fForward, int fInitial, int
// record this position if it has the best delay
if ( DelayBest > DelayCur )
{
+if ( fVerbose )
+ 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
diff --git a/src/opt/ret/retFlow.c b/src/opt/ret/retFlow.c
index 642a1f69..24d7bf57 100644
--- a/src/opt/ret/retFlow.c
+++ b/src/opt/ret/retFlow.c
@@ -46,14 +46,40 @@ static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * 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_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward );
static int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
static int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
-static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk );
+static int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
+static int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
+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 );
-static void Abc_NtkMaxFlowPrintCut( Vec_Ptr_t * vMinCut );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
@@ -93,6 +119,7 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 );
Vec_PtrFree( vMinCut );
Abc_NtkCleanMarkA( pNtk );
+
}
/**Function*************************************************************
@@ -109,37 +136,102 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
{
Vec_Ptr_t * vMinCut;
- int Flow, RetValue;
+ Abc_Obj_t * pLatch;
+ int Flow, FlowCur, RetValue, i;
int clk = clock();
- int Start = 0;
+ int fUseDirectedFlow = 1;
// find the max-flow
Abc_NtkCleanCopy( pNtk );
- for ( Flow = 0; Abc_NtkMaxFlowPath( pNtk, &Start, fForward ); Flow++ );
+ Flow = 0;
+ Abc_NtkIncrementTravId(pNtk);
+ Abc_NtkForEachLatch( pNtk, pLatch, i )
+ {
+ if ( fForward )
+ {
+// assert( !Abc_ObjFanout0(pLatch)->fMarkA );
+ FlowCur = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
+ 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) );
+ 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
- RetValue = Abc_NtkMaxFlowPath( pNtk, NULL, fForward );
- assert( RetValue == 0 );
- vMinCut = Abc_NtkMaxFlowMinCut( pNtk );
+ 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( "Latches = %6d. %s max-flow = %6d. Min-cut = %6d. ",
+ 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( vMinCut );
+// Abc_NtkMaxFlowPrintCut( pNtk, vMinCut );
return vMinCut;
}
/**Function*************************************************************
- Synopsis [Finds and augments one path.]
+ Synopsis [Tries to find an augmenting path originating in this node.]
Description []
@@ -148,35 +240,44 @@ PRT( "Time", clock() - clk );
SeeAlso []
***********************************************************************/
-int Abc_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward )
+int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
{
- Abc_Obj_t * pLatch;
- int i, LatchStart = pStart? *pStart : 0;
- Abc_NtkIncrementTravId(pNtk);
- Vec_PtrForEachEntryStart( pNtk->vBoxes, pLatch, i, LatchStart )
+ 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) )
{
- if ( !Abc_ObjIsLatch(pLatch) )
- continue;
- if ( fForward )
- {
- assert( !Abc_ObjFanout0(pLatch)->fMarkA );
- if ( Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ) )
- {
- if ( pStart ) *pStart = i + 1;
- return 1;
- }
- }
- else
- {
- assert( !Abc_ObjFanin0(pLatch)->fMarkA );
- if ( Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ) )
- {
- if ( pStart ) *pStart = i + 1;
- return 1;
- }
- }
+ // 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;
}
- if ( pStart ) *pStart = 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;
}
@@ -191,7 +292,59 @@ int Abc_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward )
SeeAlso []
***********************************************************************/
-int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
+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 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;
@@ -207,7 +360,7 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
return Abc_ObjSetPath( pObj, (void *)1 );
// explore the fanins
Abc_ObjForEachFanin( pObj, pFanin, i )
- if ( Abc_NtkMaxFlowBwdPath_rec(pFanin) )
+ if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
return Abc_ObjSetPath( pObj, pFanin );
return 0;
}
@@ -217,10 +370,10 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
return 0;
// go through the fanins of the fanout with flow
Abc_ObjForEachFanin( pFanout, pFanin, i )
- if ( pFanin != pObj && Abc_NtkMaxFlowBwdPath_rec( pFanin ) )
+ if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) )
return Abc_ObjSetPath( pFanout, pFanin );
// try the fanout
- if ( Abc_NtkMaxFlowBwdPath_rec( pFanout ) )
+ if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) )
return Abc_ObjSetPath( pFanout, NULL );
return 0;
}
@@ -229,14 +382,14 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
Synopsis [Tries to find an augmenting path originating in this node.]
- Description []
+ Description [This procedure works for directed graphs only!]
SideEffects []
SeeAlso []
***********************************************************************/
-int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
+int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanout, * pFanin;
int i;
@@ -252,7 +405,7 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
return Abc_ObjSetPath( pObj, (void *)1 );
// explore the fanins
Abc_ObjForEachFanout( pObj, pFanout, i )
- if ( Abc_NtkMaxFlowFwdPath_rec(pFanout) )
+ if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) )
return Abc_ObjSetPath( pObj, pFanout );
return 0;
}
@@ -262,18 +415,17 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
return 0;
// go through the fanins of the fanout with flow
Abc_ObjForEachFanout( pFanin, pFanout, i )
- if ( pFanout != pObj && Abc_NtkMaxFlowFwdPath_rec( pFanout ) )
+ if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) )
return Abc_ObjSetPath( pFanin, pFanout );
// try the fanout
- if ( Abc_NtkMaxFlowFwdPath_rec( pFanin ) )
+ if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) )
return Abc_ObjSetPath( pFanin, NULL );
return 0;
}
-
/**Function*************************************************************
- Synopsis [Find one minumum cut.]
+ Synopsis [Find minimum-volume minumum cut.]
Description []
@@ -282,7 +434,7 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
SeeAlso []
***********************************************************************/
-Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk )
+Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward )
{
Vec_Ptr_t * vMinCut;
Abc_Obj_t * pObj;
@@ -306,6 +458,113 @@ Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk )
/**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 []
@@ -369,13 +628,11 @@ int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward
{
if ( fForward )
{
- assert( !Abc_ObjFanout0(pObj)->fMarkA );
if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) )
return 0;
}
else
{
- assert( !Abc_ObjFanin0(pObj)->fMarkA );
if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) )
return 0;
}
@@ -456,13 +713,18 @@ void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward )
SeeAlso []
***********************************************************************/
-void Abc_NtkMaxFlowPrintCut( Vec_Ptr_t * vMinCut )
+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( "%d ", pObj->Id );
+ 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" );
}
diff --git a/src/opt/ret/retIncrem.c b/src/opt/ret/retIncrem.c
index d2ad6a72..93305a8e 100644
--- a/src/opt/ret/retIncrem.c
+++ b/src/opt/ret/retIncrem.c
@@ -24,8 +24,6 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-static st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk );
-static int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nIdMaxStart );
static int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose );
////////////////////////////////////////////////////////////////////////
@@ -57,13 +55,15 @@ int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int
Abc_NtkOrderCisCos( pNtk );
if ( fMinDelay )
{
- nIterLimit = 2 * Abc_NtkGetLevelNum(pNtk);
+ nIterLimit = 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
@@ -74,7 +74,7 @@ int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int
if ( fMinDelay )
Abc_NtkDelete( pNtkCopy );
// share the latches
- Abc_NtkRetimeShareLatches( pNtk );
+ Abc_NtkRetimeShareLatches( pNtk, 0 );
// restore boxes
pNtk->vBoxes = vBoxes;
// finalize the latches
@@ -83,7 +83,7 @@ int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int
if ( RetValue == 0 )
return 0;
// fix the COs
- Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
+// Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
// check for correctness
if ( !Abc_NtkCheck( pNtk ) )
fprintf( stdout, "Abc_NtkRetimeForward(): Network check has failed.\n" );
@@ -121,7 +121,8 @@ st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk )
// disconnect LO
pLatchOut = Abc_ObjFanout0(pLatch);
pFanin = Abc_ObjFanin0(pLatchOut);
- Abc_ObjTransferFanout( pLatchOut, pFanin );
+ if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
+ Abc_ObjTransferFanout( pLatchOut, pFanin );
Abc_ObjDeleteFanin( pLatchOut, pFanin );
}
return tLatches;
@@ -164,8 +165,8 @@ int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nId
// this is a new latch
pLatchIn = Abc_NtkCreateBi(pNtk);
pLatchOut = Abc_NtkCreateBo(pNtk);
- Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatchIn), NULL );
- Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatchOut), NULL );
+ Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
+ Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" );
}
else
{
@@ -184,7 +185,8 @@ int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nId
// connect
Abc_ObjAddFanin( pLatchIn, Abc_ObjFanin0(pLatch) );
Abc_ObjPatchFanin( pLatch, Abc_ObjFanin0(pLatch), pLatchIn );
- Abc_ObjTransferFanout( pLatch, pLatchOut );
+ if ( Abc_ObjFanoutNum(pLatch) > 0 )
+ Abc_ObjTransferFanout( pLatch, pLatchOut );
Abc_ObjAddFanin( pLatchOut, pLatch );
// add to the arrays
Vec_PtrPush( vCisNew, pLatchOut );
@@ -221,7 +223,7 @@ int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
Abc_Ntk_t * pNtkNew;
Vec_Int_t * vValues;
Abc_Obj_t * pObj;
- int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 5000;
+ int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 10000;
if ( fForward )
Abc_NtkRetimeTranferToCopy( pNtk );
else
@@ -330,7 +332,8 @@ void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial )
}
// add a new latch on top
pNext = Abc_NtkCreateLatch(pObj->pNtk);
- Abc_ObjTransferFanout( pObj, pNext );
+ if ( Abc_ObjFanoutNum(pObj) > 0 )
+ Abc_ObjTransferFanout( pObj, pNext );
Abc_ObjAddFanin( pNext, pObj );
// set the initial value
if ( fInitial )
@@ -416,35 +419,36 @@ int Abc_NtkRetimeCheckCompatibleLatchFanouts( Abc_Obj_t * pObj )
SeeAlso []
***********************************************************************/
-void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk )
+void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial )
{
Vec_Ptr_t * vNodes;
- Abc_Obj_t * pFanin, * pLatch, * pLatchTop, * pLatchCur;
+ Abc_Obj_t * pFanin, * pLatchTop, * pLatchCur;
int i, k;
vNodes = Vec_PtrAlloc( 10 );
// consider latch fanins
- Abc_NtkForEachObj( pNtk, pLatch, i )
+ Abc_NtkForEachObj( pNtk, pFanin, i )
{
- if ( !Abc_ObjIsLatch(pLatch) )
- continue;
- pFanin = Abc_ObjFanin0(pLatch);
if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 )
continue;
// get the first latch
+ pLatchTop = NULL;
Abc_ObjForEachFanout( pFanin, pLatchTop, k )
if ( Abc_ObjIsLatch(pLatchTop) )
break;
- assert( Abc_ObjIsLatch(pLatchTop) );
+ assert( pLatchTop && Abc_ObjIsLatch(pLatchTop) );
// redirect compatible fanout latches to the first latch
Abc_NodeCollectFanouts( pFanin, vNodes );
Vec_PtrForEachEntry( vNodes, pLatchCur, k )
{
- if ( pLatchCur == pLatchTop )
- continue;
if ( !Abc_ObjIsLatch(pLatchCur) )
continue;
+ if ( pLatchCur == 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);
diff --git a/src/opt/ret/retInit.c b/src/opt/ret/retInit.c
index 3eb80da1..b53ceeae 100644
--- a/src/opt/ret/retInit.c
+++ b/src/opt/ret/retInit.c
@@ -281,7 +281,6 @@ void Abc_NtkRetimeBackwardInitialFinish( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew,
Abc_NtkForEachObj( pNtk, pObj, i )
if ( Abc_ObjIsLatch(pObj) )
Abc_ObjAddFanin( pObj->pCopy, Abc_NtkCreatePi(pNtkNew) );
- pObj = Abc_NtkPo(pNtkNew, 0);
// assign dummy node names
Abc_NtkAddDummyPiNames( pNtkNew );
Abc_NtkAddDummyPoNames( pNtkNew );
diff --git a/src/opt/ret/retInt.h b/src/opt/ret/retInt.h
index 9b3aa00a..28529cdc 100644
--- a/src/opt/ret/retInt.h
+++ b/src/opt/ret/retInt.h
@@ -51,9 +51,11 @@ extern int Abc_NtkRetime( Abc_Ntk_t * pNtk, int Mode, int fForwardOnly,
extern int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nIterLimit, int fForward, int fVerbose );
/*=== retDirect.c ========================================================*/
extern int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int fVerbose );
-extern void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk );
+extern 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 );
@@ -66,6 +68,8 @@ 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
diff --git a/src/opt/ret/retLvalue.c b/src/opt/ret/retLvalue.c
new file mode 100644
index 00000000..ebb42808
--- /dev/null
+++ b/src/opt/ret/retLvalue.c
@@ -0,0 +1,419 @@
+/**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_NtkRetimeUsingLags( Abc_Ntk_t * pNtk, Vec_Int_t * vLags, int fVerbose );
+static int Abc_NtkRetimeSearch_rec( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, int FiMin, int FiMax, int nMaxIters, int fVerbose );
+static int Abc_NtkRetimeForPeriod( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, int Fi, int nMaxIters, int fVerbose );
+static int Abc_NtkRetimeNodeUpdateLValue( Abc_Obj_t * pObj, int Fi );
+static Vec_Ptr_t * Abc_NtkRetimeCollect( Abc_Ntk_t * pNtk );
+
+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;
+ Abc_Obj_t * pNode;
+ int i, FiMax, FiBest, RetValue, clk, clkIter;
+ char NodeLag;
+
+ // get the upper bound on the clock period
+ FiMax = 10 + Abc_NtkLevel(pNtk);
+
+ // make sure this clock period is feasible
+ vNodes = Abc_NtkRetimeCollect(pNtk);
+ if ( !Abc_NtkRetimeForPeriod( pNtk, vNodes, 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, 0, FiMax, nIterLimit, fVerbose );
+clkIter = clock() - clk;
+
+ // recompute the best l-values
+ RetValue = Abc_NtkRetimeForPeriod( pNtk, vNodes, FiBest, nIterLimit, fVerbose );
+ assert( RetValue );
+ Vec_PtrFree( vNodes );
+
+ // 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 );
+ }
+
+ // print the result
+// if ( fVerbose )
+ printf( "The best clock period is %3d. (Currently, network is not modified.)\n", FiBest );
+/*
+ // print the statistic into a file
+ {
+ FILE * pTable;
+ pTable = fopen( "a/ret__stats.txt", "a+" );
+ fprintf( pTable, "%d ", FiBest );
+ fclose( pTable );
+ }
+*/
+
+/*
+ printf( "lvalues and lags : " );
+ Abc_NtkForEachNode( pNtk, pNode, i )
+ printf( "%d=%d(%d) ", pNode->Id, Abc_NodeGetLValue(pNode), Abc_NodeGetLag(pNode) );
+ printf( "\n" );
+*/
+/*
+ {
+ FILE * pTable;
+ pTable = fopen( "a/ret_stats_pan.txt", "a+" );
+ fprintf( pTable, "%s ", pNtk->pName );
+ fprintf( pTable, "%d ", FiBest );
+ fprintf( pTable, "\n" );
+ fclose( pTable );
+ }
+*/
+ 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, 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, Median, nMaxIters, fVerbose ) )
+ return Abc_NtkRetimeSearch_rec( pNtk, vNodes, FiMin, Median, nMaxIters, fVerbose ); // Median is feasible
+ else
+ return Abc_NtkRetimeSearch_rec( pNtk, vNodes, 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, int Fi, int nMaxIters, int fVerbose )
+{
+ Abc_Obj_t * pObj;
+ int i, c, fContained, fChange, RetValue, Counter;
+ char * pReason = "";
+
+ // 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
+ Counter = 0;
+ fContained = 1;
+ fChange = 1;
+ for ( c = 0; fContained && fChange && c < nMaxIters; c++ )
+ {
+ // go through the nodes and detect change
+ fChange = 0;
+ Vec_PtrForEachEntry( vNodes, pObj, i )
+ {
+ RetValue = Abc_NtkRetimeNodeUpdateLValue( pObj, Fi );
+ if ( RetValue == ABC_RET_UPDATE_FAIL )
+ {
+ fContained = 0;
+ break;
+ }
+ if ( RetValue == ABC_RET_UPDATE_NO )
+ continue;
+ // updating happened
+ fChange = 1;
+ Counter++;
+ }
+ }
+ if ( c == nMaxIters )
+ {
+ fContained = 0;
+ pReason = "(timeout)";
+ }
+ else
+ c++;
+ // report the results
+ if ( fVerbose )
+ {
+ if ( !fContained )
+ printf( "Period = %3d. Iterations = %3d. Updates = %10d. Infeasible %s\n", Fi, c, Counter, pReason );
+ else
+ printf( "Period = %3d. Iterations = %3d. Updates = %10d. Feasible\n", Fi, c, Counter );
+ }
+/*
+ // 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 fContained;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the l-value of the node.]
+
+ Description [The node can be internal or a PO.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Abc_NtkRetimeNodeUpdateLValue( Abc_Obj_t * pObj, int Fi )
+{
+ Abc_Obj_t * pFanin;
+ int lValueNew, i;
+ // terminals
+ if ( Abc_ObjFaninNum(pObj) == 0 )
+ return ABC_RET_UPDATE_NO;
+ // primary outputs
+ if ( Abc_ObjIsPo(pObj) )
+ return (Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) > Fi)? ABC_RET_UPDATE_FAIL : ABC_RET_UPDATE_NO;
+ // other types of objects
+ if ( Abc_ObjIsBi(pObj) || Abc_ObjIsBo(pObj) )
+ lValueNew = Abc_NodeGetLValue(Abc_ObjFanin0(pObj));
+ else if ( Abc_ObjIsLatch(pObj) )
+ lValueNew = Abc_NodeGetLValue(Abc_ObjFanin0(pObj)) - Fi;
+ else
+ {
+ assert( Abc_ObjIsNode(pObj) );
+ lValueNew = -ABC_INFINITY;
+ Abc_ObjForEachFanin( pObj, pFanin, i )
+ if ( lValueNew < Abc_NodeGetLValue(pFanin) )
+ lValueNew = Abc_NodeGetLValue(pFanin);
+ lValueNew++;
+ }
+ // check if it needs to be updated
+ if ( lValueNew <= Abc_NodeGetLValue(pObj) )
+ return ABC_RET_UPDATE_NO;
+ // update if needed
+ Abc_NodeSetLValue( pObj, lValueNew );
+ return ABC_RET_UPDATE_YES;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Implements the retiming given as a set 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;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collect objects in the topological order from the latch inputs.]
+
+ Description [If flag fOnlyMarked is set, collects only marked nodes.
+ Otherwise, collects only unmarked nodes.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Abc_NtkRetimeCollect_rec( Abc_Obj_t * pObj, int fOnlyMarked, Vec_Ptr_t * vNodes )
+{
+ Abc_Obj_t * pFanin;
+ int i;
+ // skip collected nodes
+ if ( Abc_NodeIsTravIdCurrent(pObj) )
+ return;
+ Abc_NodeSetTravIdCurrent(pObj);
+ // collect recursively
+ if ( fOnlyMarked ^ pObj->fMarkA )
+ return;
+ // visit the fanins
+ Abc_ObjForEachFanin( pObj, pFanin, i )
+ Abc_NtkRetimeCollect_rec( pFanin, fOnlyMarked, vNodes );
+ // collect non-trivial objects
+ if ( Abc_ObjFaninNum(pObj) > 0 )
+ Vec_PtrPush( vNodes, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collect objects in the topological order using LIs as a cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NtkRetimeCollect( Abc_Ntk_t * pNtk )
+{
+ Vec_Ptr_t * vNodes;
+ Abc_Obj_t * pObj, * pFanin;
+ int i, k;
+ vNodes = Vec_PtrAlloc( 100 );
+ // mark the latch inputs
+ Abc_NtkForEachLatch( pNtk, pObj, i )
+ Abc_ObjFanin0(pObj)->fMarkA = 1;
+ // collect nodes in the DFS order from the marked nodes
+ Abc_NtkIncrementTravId(pNtk);
+ Abc_NtkForEachPo( pNtk, pObj, i )
+ Abc_NtkRetimeCollect_rec( pObj, 0, vNodes );
+ Abc_NtkForEachLatch( pNtk, pObj, i )
+ Abc_ObjForEachFanin( Abc_ObjFanin0(pObj), pFanin, k )
+ Abc_NtkRetimeCollect_rec( pFanin, 0, vNodes );
+ // collect marked nodes
+ Abc_NtkIncrementTravId(pNtk);
+ Abc_NtkForEachLatch( pNtk, pObj, i )
+ Abc_NtkRetimeCollect_rec( Abc_ObjFanin0(pObj), 1, vNodes );
+ // clean the marks
+ Abc_NtkForEachLatch( pNtk, pObj, i )
+ Abc_ObjFanin0(pObj)->fMarkA = 0;
+ return vNodes;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-07 12:53:24 +0000