summaryrefslogtreecommitdiffstats
path: root/src/opt/nwk
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt/nwk')
-rw-r--r--src/opt/nwk/module.make14
-rw-r--r--src/opt/nwk/ntlnwk.h113
-rw-r--r--src/opt/nwk/nwk.h307
-rw-r--r--src/opt/nwk/nwkAig.c112
-rw-r--r--src/opt/nwk/nwkBidec.c177
-rw-r--r--src/opt/nwk/nwkCheck.c76
-rw-r--r--src/opt/nwk/nwkDfs.c664
-rw-r--r--src/opt/nwk/nwkFanio.c320
-rw-r--r--src/opt/nwk/nwkFlow.c606
-rw-r--r--src/opt/nwk/nwkFlow_depth.c631
-rw-r--r--src/opt/nwk/nwkMan.c278
-rw-r--r--src/opt/nwk/nwkMap.c396
-rw-r--r--src/opt/nwk/nwkMerge.c1044
-rw-r--r--src/opt/nwk/nwkMerge.h153
-rw-r--r--src/opt/nwk/nwkObj.c204
-rw-r--r--src/opt/nwk/nwkSpeedup.c382
-rw-r--r--src/opt/nwk/nwkStrash.c149
-rw-r--r--src/opt/nwk/nwkTiming.c894
-rw-r--r--src/opt/nwk/nwkUtil.c643
-rw-r--r--src/opt/nwk/nwk_.c52
20 files changed, 7215 insertions, 0 deletions
diff --git a/src/opt/nwk/module.make b/src/opt/nwk/module.make
new file mode 100644
index 00000000..13812d68
--- /dev/null
+++ b/src/opt/nwk/module.make
@@ -0,0 +1,14 @@
+SRC += src/opt/nwk/nwkAig.c \
+ src/opt/nwk/nwkCheck.c \
+ src/opt/nwk/nwkBidec.c \
+ src/opt/nwk/nwkDfs.c \
+ src/opt/nwk/nwkFanio.c \
+ src/opt/nwk/nwkFlow.c \
+ src/opt/nwk/nwkMan.c \
+ src/opt/nwk/nwkMap.c \
+ src/opt/nwk/nwkMerge.c \
+ src/opt/nwk/nwkObj.c \
+ src/opt/nwk/nwkSpeedup.c \
+ src/opt/nwk/nwkStrash.c \
+ src/opt/nwk/nwkTiming.c \
+ src/opt/nwk/nwkUtil.c
diff --git a/src/opt/nwk/ntlnwk.h b/src/opt/nwk/ntlnwk.h
new file mode 100644
index 00000000..5300e6f4
--- /dev/null
+++ b/src/opt/nwk/ntlnwk.h
@@ -0,0 +1,113 @@
+/**CFile****************************************************************
+
+ FileName [ntlnwk.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist and network representation.]
+
+ Synopsis [External declarations.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: ntlnwk.h,v 1.3 2008/10/24 14:18:44 mjarvin Exp $]
+
+***********************************************************************/
+
+#ifndef __NTLNWK_abc_opt_nwk_h
+#define __NTLNWK_abc_opt_nwk_h
+
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+ABC_NAMESPACE_HEADER_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct Ntl_Man_t_ Ntl_Man_t;
+typedef struct Nwk_Man_t_ Nwk_Man_t;
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// INLINED FUNCTIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// ITERATORS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+extern ABC_DLL Ntl_Man_t * Ntl_ManReadBlif( char * pFileName, int fCheck );
+extern ABC_DLL void Ntl_ManWriteBlif( Ntl_Man_t * p, char * pFileName );
+
+extern ABC_DLL Tim_Man_t * Ntl_ManReadTimeMan( Ntl_Man_t * p );
+extern ABC_DLL Ntl_Man_t * Ntl_ManDup( Ntl_Man_t * p );
+extern ABC_DLL void Ntl_ManFree( Ntl_Man_t * p );
+extern ABC_DLL int Ntl_ManIsComb( Ntl_Man_t * p );
+extern ABC_DLL void Ntl_ManPrintStats( Ntl_Man_t * p );
+extern ABC_DLL int Ntl_ManSweep( Ntl_Man_t * p, int fVerbose );
+extern ABC_DLL Ntl_Man_t * Ntl_ManInsertNtk( Ntl_Man_t * p, Nwk_Man_t * pNtk );
+extern ABC_DLL Ntl_Man_t * Ntl_ManInsertAig( Ntl_Man_t * p, Aig_Man_t * pAig );
+extern ABC_DLL Aig_Man_t * Ntl_ManExtract( Ntl_Man_t * p );
+extern ABC_DLL Aig_Man_t * Ntl_ManCollapse( Ntl_Man_t * p, int fSeq );
+extern ABC_DLL Aig_Man_t * Ntl_ManCollapseSeq( Ntl_Man_t * p, int nMinDomSize, int fVerbose );
+extern ABC_DLL Ntl_Man_t * Ntl_ManDupCollapseLuts( Ntl_Man_t * p );
+extern ABC_DLL Ntl_Man_t * Ntl_ManFraig( Ntl_Man_t * p, int nPartSize, int nConfLimit, int nLevelMax, int fUseCSat, int fVerbose );
+extern ABC_DLL void Ntl_ManPrepareCecMans( Ntl_Man_t * pMan1, Ntl_Man_t * pMan2, Aig_Man_t ** ppAig1, Aig_Man_t ** ppAig2 );
+extern ABC_DLL Vec_Ptr_t * Ntl_ManCollectCiNames( Ntl_Man_t * p );
+extern ABC_DLL Vec_Ptr_t * Ntl_ManCollectCoNames( Ntl_Man_t * p );
+extern ABC_DLL Ntl_Man_t * Ntl_ManScl( Ntl_Man_t * p, int fLatchConst, int fLatchEqual, int fVerbose );
+extern ABC_DLL Ntl_Man_t * Ntl_ManLcorr( Ntl_Man_t * p, int nConfMax, int fScorrGia, int fUseCSat, int fVerbose );
+extern ABC_DLL Ntl_Man_t * Ntl_ManSsw( Ntl_Man_t * p, Fra_Ssw_t * pPars );
+extern ABC_DLL Ntl_Man_t * Ntl_ManScorr( Ntl_Man_t * p, Ssw_Pars_t * pPars );
+extern ABC_DLL void Ntl_ManTransformInitValues( Ntl_Man_t * p );
+
+extern ABC_DLL void Ntl_ManPrepareCec( char * pFileName1, char * pFileName2, Aig_Man_t ** ppMan1, Aig_Man_t ** ppMan2 );
+extern ABC_DLL Aig_Man_t * Ntl_ManPrepareSec( char * pFileName1, char * pFileName2 );
+
+extern ABC_DLL Nwk_Man_t * Ntl_ManExtractNwk( Ntl_Man_t * p, Aig_Man_t * pAig, Tim_Man_t * pManTime );
+extern ABC_DLL Nwk_Man_t * Ntl_ManReadNwk( char * pFileName, Aig_Man_t * pAig, Tim_Man_t * pManTime );
+extern ABC_DLL void Nwk_ManPrintStats( Nwk_Man_t * p, If_Lib_t * pLutLib, int fSaveBest, int fDumpResult, int fPower, Ntl_Man_t * pNtl );
+extern ABC_DLL void Nwk_ManPrintStatsShort( Ntl_Man_t * p, Aig_Man_t * pAig, Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManPrintFanioNew( Nwk_Man_t * p );
+extern ABC_DLL Nwk_Man_t * Nwk_MappingIf( Aig_Man_t * p, Tim_Man_t * pManTime, If_Par_t * pPars );
+extern ABC_DLL void Nwk_ManSetIfParsDefault( If_Par_t * pPars );
+extern ABC_DLL void Nwk_ManBidecResyn( Nwk_Man_t * p, int fVerbose );
+extern ABC_DLL Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * p, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose );
+extern ABC_DLL Aig_Man_t * Nwk_ManStrash( Nwk_Man_t * p );
+extern ABC_DLL Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * p, void * pPars );
+extern ABC_DLL int Nwk_ManCheck( Nwk_Man_t * p );
+extern ABC_DLL void Nwk_ManDumpBlif( Nwk_Man_t * p, char * pFileName, Vec_Ptr_t * vCiNames, Vec_Ptr_t * vCoNames );
+extern ABC_DLL void Nwk_ManFree( Nwk_Man_t * p );
+
+
+
+ABC_NAMESPACE_HEADER_END
+
+
+
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
diff --git a/src/opt/nwk/nwk.h b/src/opt/nwk/nwk.h
new file mode 100644
index 00000000..79c7bb1a
--- /dev/null
+++ b/src/opt/nwk/nwk.h
@@ -0,0 +1,307 @@
+/**CFile****************************************************************
+
+ FileName [nwk.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [External declarations.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwk.h,v 1.1 2008/05/14 22:13:09 wudenni Exp $]
+
+***********************************************************************/
+
+#ifndef __NWK_abc_opt_nwk_h
+#define __NWK_abc_opt_nwk_h
+
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+#include "src/aig/aig/aig.h"
+#include "src/aig/hop/hop.h"
+#include "src/misc/tim/tim.h"
+#include "src/map/if/if.h"
+#include "src/bool/bdc/bdc.h"
+
+#include "src/proof/fra/fra.h"
+#include "src/proof/ssw/ssw.h"
+#include "ntlnwk.h"
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+ABC_NAMESPACE_HEADER_START
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct Nwk_Obj_t_ Nwk_Obj_t;
+
+// object types
+typedef enum {
+ NWK_OBJ_NONE, // 0: non-existant object
+ NWK_OBJ_CI, // 1: combinational input
+ NWK_OBJ_CO, // 2: combinational output
+ NWK_OBJ_NODE, // 3: logic node
+ NWK_OBJ_LATCH, // 4: register
+ NWK_OBJ_VOID // 5: unused object
+} Nwk_Type_t;
+
+struct Nwk_Man_t_
+{
+ // models of this design
+ char * pName; // the name of this design
+ char * pSpec; // the name of input file
+ // node representation
+ Vec_Ptr_t * vCis; // the primary inputs of the extracted part
+ Vec_Ptr_t * vCos; // the primary outputs of the extracted part
+ Vec_Ptr_t * vObjs; // the objects in the topological order
+ int nObjs[NWK_OBJ_VOID]; // counter of objects of each type
+ int nFanioPlus; // the number of extra fanins/fanouts alloc by default
+ // functionality, timing, memory, etc
+ Hop_Man_t * pManHop; // the functionality representation
+ Tim_Man_t * pManTime; // the timing manager
+ If_Lib_t * pLutLib; // the LUT library
+ Aig_MmFlex_t * pMemObjs; // memory for objects
+ Vec_Ptr_t * vTemp; // array used for incremental updates
+ int nTravIds; // the counter of traversal IDs
+ int nRealloced; // the number of realloced nodes
+ // sequential information
+ int nLatches; // the total number of latches
+ int nTruePis; // the number of true primary inputs
+ int nTruePos; // the number of true primary outputs
+};
+
+struct Nwk_Obj_t_
+{
+ Nwk_Man_t * pMan; // the manager
+ Hop_Obj_t * pFunc; // functionality
+ void * pCopy; // temporary pointer
+ union {
+ void * pNext; // temporary pointer
+ int iTemp; // temporary number
+ };
+ // node information
+ unsigned Type : 3; // object type
+ unsigned fInvert : 1; // complemented attribute
+ unsigned MarkA : 1; // temporary mark
+ unsigned MarkB : 1; // temporary mark
+ unsigned MarkC : 1; // temporary mark
+ unsigned PioId : 25; // number of this node in the PI/PO list
+ int Id; // unique ID
+ int TravId; // traversal ID
+ // timing information
+ int Level; // the topological level
+ float tArrival; // the arrival time
+ float tRequired; // the required time
+ float tSlack; // the slack
+ // fanin/fanout representation
+ int nFanins; // the number of fanins
+ int nFanouts; // the number of fanouts
+ int nFanioAlloc; // the number of allocated fanins/fanouts
+ Nwk_Obj_t ** pFanio; // fanins/fanouts
+};
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+
+////////////////////////////////////////////////////////////////////////
+/// INLINED FUNCTIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static inline int Nwk_ManCiNum( Nwk_Man_t * p ) { return p->nObjs[NWK_OBJ_CI]; }
+static inline int Nwk_ManCoNum( Nwk_Man_t * p ) { return p->nObjs[NWK_OBJ_CO]; }
+static inline int Nwk_ManNodeNum( Nwk_Man_t * p ) { return p->nObjs[NWK_OBJ_NODE]; }
+static inline int Nwk_ManLatchNum( Nwk_Man_t * p ) { return p->nObjs[NWK_OBJ_LATCH]; }
+static inline int Nwk_ManObjNumMax( Nwk_Man_t * p ) { return Vec_PtrSize(p->vObjs); }
+
+static inline Nwk_Obj_t * Nwk_ManCi( Nwk_Man_t * p, int i ) { return (Nwk_Obj_t *)Vec_PtrEntry( p->vCis, i ); }
+static inline Nwk_Obj_t * Nwk_ManCo( Nwk_Man_t * p, int i ) { return (Nwk_Obj_t *)Vec_PtrEntry( p->vCos, i ); }
+static inline Nwk_Obj_t * Nwk_ManObj( Nwk_Man_t * p, int i ) { return (Nwk_Obj_t *)Vec_PtrEntry( p->vObjs, i ); }
+
+static inline int Nwk_ObjId( Nwk_Obj_t * p ) { return p->Id; }
+static inline int Nwk_ObjPioNum( Nwk_Obj_t * p ) { return p->PioId; }
+static inline int Nwk_ObjFaninNum( Nwk_Obj_t * p ) { return p->nFanins; }
+static inline int Nwk_ObjFanoutNum( Nwk_Obj_t * p ) { return p->nFanouts; }
+
+static inline Nwk_Obj_t * Nwk_ObjFanin0( Nwk_Obj_t * p ) { return p->pFanio[0]; }
+static inline Nwk_Obj_t * Nwk_ObjFanout0( Nwk_Obj_t * p ) { return p->pFanio[p->nFanins]; }
+static inline Nwk_Obj_t * Nwk_ObjFanin( Nwk_Obj_t * p, int i ) { return p->pFanio[i]; }
+static inline Nwk_Obj_t * Nwk_ObjFanout( Nwk_Obj_t * p, int i ) { return p->pFanio[p->nFanins+1]; }
+
+static inline int Nwk_ObjIsNone( Nwk_Obj_t * p ) { return p->Type == NWK_OBJ_NONE; }
+static inline int Nwk_ObjIsCi( Nwk_Obj_t * p ) { return p->Type == NWK_OBJ_CI; }
+static inline int Nwk_ObjIsCo( Nwk_Obj_t * p ) { return p->Type == NWK_OBJ_CO; }
+static inline int Nwk_ObjIsNode( Nwk_Obj_t * p ) { return p->Type == NWK_OBJ_NODE; }
+static inline int Nwk_ObjIsLatch( Nwk_Obj_t * p ) { return p->Type == NWK_OBJ_LATCH; }
+static inline int Nwk_ObjIsPi( Nwk_Obj_t * p ) { return Nwk_ObjIsCi(p) && (p->pMan->pManTime == NULL || Tim_ManBoxForCi(p->pMan->pManTime, p->PioId) == -1); }
+static inline int Nwk_ObjIsPo( Nwk_Obj_t * p ) { return Nwk_ObjIsCo(p) && (p->pMan->pManTime == NULL || Tim_ManBoxForCo(p->pMan->pManTime, p->PioId) == -1); }
+static inline int Nwk_ObjIsLi( Nwk_Obj_t * p ) { return p->pMan->nTruePos && Nwk_ObjIsCo(p) && (int)p->PioId >= p->pMan->nTruePos; }
+static inline int Nwk_ObjIsLo( Nwk_Obj_t * p ) { return p->pMan->nTruePis && Nwk_ObjIsCi(p) && (int)p->PioId >= p->pMan->nTruePis; }
+
+static inline float Nwk_ObjArrival( Nwk_Obj_t * pObj ) { return pObj->tArrival; }
+static inline float Nwk_ObjRequired( Nwk_Obj_t * pObj ) { return pObj->tRequired; }
+static inline float Nwk_ObjSlack( Nwk_Obj_t * pObj ) { return pObj->tSlack; }
+static inline void Nwk_ObjSetArrival( Nwk_Obj_t * pObj, float Time ) { pObj->tArrival = Time; }
+static inline void Nwk_ObjSetRequired( Nwk_Obj_t * pObj, float Time ) { pObj->tRequired = Time; }
+static inline void Nwk_ObjSetSlack( Nwk_Obj_t * pObj, float Time ) { pObj->tSlack = Time; }
+
+static inline int Nwk_ObjLevel( Nwk_Obj_t * pObj ) { return pObj->Level; }
+static inline void Nwk_ObjSetLevel( Nwk_Obj_t * pObj, int Level ) { pObj->Level = Level; }
+
+static inline void Nwk_ObjSetTravId( Nwk_Obj_t * pObj, int TravId ) { pObj->TravId = TravId; }
+static inline void Nwk_ObjSetTravIdCurrent( Nwk_Obj_t * pObj ) { pObj->TravId = pObj->pMan->nTravIds; }
+static inline void Nwk_ObjSetTravIdPrevious( Nwk_Obj_t * pObj ) { pObj->TravId = pObj->pMan->nTravIds - 1; }
+static inline int Nwk_ObjIsTravIdCurrent( Nwk_Obj_t * pObj ) { return pObj->TravId == pObj->pMan->nTravIds; }
+static inline int Nwk_ObjIsTravIdPrevious( Nwk_Obj_t * pObj ) { return pObj->TravId == pObj->pMan->nTravIds - 1; }
+
+static inline int Nwk_ManTimeEqual( float f1, float f2, float Eps ) { return (f1 < f2 + Eps) && (f2 < f1 + Eps); }
+static inline int Nwk_ManTimeLess( float f1, float f2, float Eps ) { return (f1 < f2 + Eps); }
+static inline int Nwk_ManTimeMore( float f1, float f2, float Eps ) { return (f1 + Eps > f2); }
+
+////////////////////////////////////////////////////////////////////////
+/// ITERATORS ///
+////////////////////////////////////////////////////////////////////////
+
+#define Nwk_ManForEachCi( p, pObj, i ) \
+ Vec_PtrForEachEntry( Nwk_Obj_t *, p->vCis, pObj, i )
+#define Nwk_ManForEachCo( p, pObj, i ) \
+ Vec_PtrForEachEntry( Nwk_Obj_t *, p->vCos, pObj, i )
+#define Nwk_ManForEachPi( p, pObj, i ) \
+ Vec_PtrForEachEntry( Nwk_Obj_t *, p->vCis, pObj, i ) \
+ if ( !Nwk_ObjIsPi(pObj) ) {} else
+#define Nwk_ManForEachPo( p, pObj, i ) \
+ Vec_PtrForEachEntry( Nwk_Obj_t *, p->vCos, pObj, i ) \
+ if ( !Nwk_ObjIsPo(pObj) ) {} else
+#define Nwk_ManForEachObj( p, pObj, i ) \
+ for ( i = 0; (i < Vec_PtrSize(p->vObjs)) && (((pObj) = (Nwk_Obj_t *)Vec_PtrEntry(p->vObjs, i)), 1); i++ ) \
+ if ( pObj == NULL ) {} else
+#define Nwk_ManForEachNode( p, pObj, i ) \
+ for ( i = 0; (i < Vec_PtrSize(p->vObjs)) && (((pObj) = (Nwk_Obj_t *)Vec_PtrEntry(p->vObjs, i)), 1); i++ ) \
+ if ( (pObj) == NULL || !Nwk_ObjIsNode(pObj) ) {} else
+#define Nwk_ManForEachLatch( p, pObj, i ) \
+ for ( i = 0; (i < Vec_PtrSize(p->vObjs)) && (((pObj) = (Nwk_Obj_t *)Vec_PtrEntry(p->vObjs, i)), 1); i++ ) \
+ if ( (pObj) == NULL || !Nwk_ObjIsLatch(pObj) ) {} else
+
+#define Nwk_ObjForEachFanin( pObj, pFanin, i ) \
+ for ( i = 0; (i < (int)(pObj)->nFanins) && ((pFanin) = (pObj)->pFanio[i]); i++ )
+#define Nwk_ObjForEachFanout( pObj, pFanout, i ) \
+ for ( i = 0; (i < (int)(pObj)->nFanouts) && ((pFanout) = (pObj)->pFanio[(pObj)->nFanins+i]); i++ )
+
+// sequential iterators
+#define Nwk_ManForEachPiSeq( p, pObj, i ) \
+ Vec_PtrForEachEntryStop( Nwk_Obj_t *, p->vCis, pObj, i, (p)->nTruePis )
+#define Nwk_ManForEachPoSeq( p, pObj, i ) \
+ Vec_PtrForEachEntryStop( Nwk_Obj_t *, p->vCos, pObj, i, (p)->nTruePos )
+#define Nwk_ManForEachLoSeq( p, pObj, i ) \
+ for ( i = 0; (i < (p)->nLatches) && (((pObj) = (Nwk_Obj_t *)Vec_PtrEntry(p->vCis, i+(p)->nTruePis)), 1); i++ )
+#define Nwk_ManForEachLiSeq( p, pObj, i ) \
+ for ( i = 0; (i < (p)->nLatches) && (((pObj) = (Nwk_Obj_t *)Vec_PtrEntry(p->vCos, i+(p)->nTruePos)), 1); i++ )
+#define Nwk_ManForEachLiLoSeq( p, pObjLi, pObjLo, i ) \
+ for ( i = 0; (i < (p)->nLatches) && (((pObjLi) = Nwk_ManCo(p, i+(p)->nTruePos)), 1) \
+ && (((pObjLo) = Nwk_ManCi(p, i+(p)->nTruePis)), 1); i++ )
+
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/*=== nwkAig.c ==========================================================*/
+extern ABC_DLL Vec_Ptr_t * Nwk_ManDeriveRetimingCut( Aig_Man_t * p, int fForward, int fVerbose );
+/*=== nwkBidec.c ==========================================================*/
+extern ABC_DLL void Nwk_ManBidecResyn( Nwk_Man_t * pNtk, int fVerbose );
+extern ABC_DLL Hop_Obj_t * Nwk_NodeIfNodeResyn( Bdc_Man_t * p, Hop_Man_t * pHop, Hop_Obj_t * pRoot, int nVars, Vec_Int_t * vTruth, unsigned * puCare, float dProb );
+/*=== nwkCheck.c ==========================================================*/
+extern ABC_DLL int Nwk_ManCheck( Nwk_Man_t * p );
+/*=== nwkDfs.c ==========================================================*/
+extern ABC_DLL int Nwk_ManVerifyTopoOrder( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManLevelBackup( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManLevel( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManLevelMax( Nwk_Man_t * pNtk );
+extern ABC_DLL Vec_Vec_t * Nwk_ManLevelize( Nwk_Man_t * pNtk );
+extern ABC_DLL Vec_Ptr_t * Nwk_ManDfs( Nwk_Man_t * pNtk );
+extern ABC_DLL Vec_Ptr_t * Nwk_ManDfsNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes );
+extern ABC_DLL Vec_Ptr_t * Nwk_ManDfsReverse( Nwk_Man_t * pNtk );
+extern ABC_DLL Vec_Ptr_t * Nwk_ManSupportNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes );
+extern ABC_DLL void Nwk_ManSupportSum( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ObjMffcLabel( Nwk_Obj_t * pNode );
+/*=== nwkFanio.c ==========================================================*/
+extern ABC_DLL void Nwk_ObjCollectFanins( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes );
+extern ABC_DLL void Nwk_ObjCollectFanouts( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes );
+extern ABC_DLL int Nwk_ObjFindFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin );
+extern ABC_DLL int Nwk_ObjFindFanout( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanout );
+extern ABC_DLL void Nwk_ObjAddFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin );
+extern ABC_DLL void Nwk_ObjDeleteFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin );
+extern ABC_DLL void Nwk_ObjPatchFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFaninOld, Nwk_Obj_t * pFaninNew );
+extern ABC_DLL void Nwk_ObjTransferFanout( Nwk_Obj_t * pNodeFrom, Nwk_Obj_t * pNodeTo );
+extern ABC_DLL void Nwk_ObjReplace( Nwk_Obj_t * pNodeOld, Nwk_Obj_t * pNodeNew );
+/*=== nwkFlow.c ============================================================*/
+extern ABC_DLL Vec_Ptr_t * Nwk_ManRetimeCutForward( Nwk_Man_t * pMan, int nLatches, int fVerbose );
+extern ABC_DLL Vec_Ptr_t * Nwk_ManRetimeCutBackward( Nwk_Man_t * pMan, int nLatches, int fVerbose );
+/*=== nwkMan.c ============================================================*/
+extern ABC_DLL Nwk_Man_t * Nwk_ManAlloc();
+extern ABC_DLL void Nwk_ManFree( Nwk_Man_t * p );
+extern ABC_DLL float Nwl_ManComputeTotalSwitching( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManPrintStats( Nwk_Man_t * p, If_Lib_t * pLutLib, int fSaveBest, int fDumpResult, int fPower, Ntl_Man_t * pNtl );
+/*=== nwkMap.c ============================================================*/
+extern ABC_DLL Nwk_Man_t * Nwk_MappingIf( Aig_Man_t * p, Tim_Man_t * pManTime, If_Par_t * pPars );
+/*=== nwkObj.c ============================================================*/
+extern ABC_DLL Nwk_Obj_t * Nwk_ManCreateCi( Nwk_Man_t * pMan, int nFanouts );
+extern ABC_DLL Nwk_Obj_t * Nwk_ManCreateCo( Nwk_Man_t * pMan );
+extern ABC_DLL Nwk_Obj_t * Nwk_ManCreateNode( Nwk_Man_t * pMan, int nFanins, int nFanouts );
+extern ABC_DLL Nwk_Obj_t * Nwk_ManCreateBox( Nwk_Man_t * pMan, int nFanins, int nFanouts );
+extern ABC_DLL Nwk_Obj_t * Nwk_ManCreateLatch( Nwk_Man_t * pMan );
+extern ABC_DLL void Nwk_ManDeleteNode( Nwk_Obj_t * pObj );
+extern ABC_DLL void Nwk_ManDeleteNode_rec( Nwk_Obj_t * pObj );
+/*=== nwkSpeedup.c ============================================================*/
+extern ABC_DLL Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose );
+/*=== nwkStrash.c ============================================================*/
+extern ABC_DLL Aig_Man_t * Nwk_ManStrash( Nwk_Man_t * pNtk );
+/*=== nwkTiming.c ============================================================*/
+extern ABC_DLL int Nwk_ManVerifyTiming( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManDelayTraceSortPins( Nwk_Obj_t * pNode, int * pPinPerm, float * pPinDelays );
+extern ABC_DLL float Nwk_ManDelayTraceLut( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManDelayTracePrint( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManUpdate( Nwk_Obj_t * pObj, Nwk_Obj_t * pObjNew, Vec_Vec_t * vLevels );
+extern ABC_DLL int Nwk_ManVerifyLevel( Nwk_Man_t * pNtk );
+/*=== nwkUtil.c ============================================================*/
+extern ABC_DLL void Nwk_ManIncrementTravId( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManGetFaninMax( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManGetTotalFanins( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManPiNum( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManPoNum( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_ManGetAigNodeNum( Nwk_Man_t * pNtk );
+extern ABC_DLL int Nwk_NodeCompareLevelsIncrease( Nwk_Obj_t ** pp1, Nwk_Obj_t ** pp2 );
+extern ABC_DLL int Nwk_NodeCompareLevelsDecrease( Nwk_Obj_t ** pp1, Nwk_Obj_t ** pp2 );
+extern ABC_DLL void Nwk_ObjPrint( Nwk_Obj_t * pObj );
+extern ABC_DLL void Nwk_ManDumpBlif( Nwk_Man_t * pNtk, char * pFileName, Vec_Ptr_t * vCiNames, Vec_Ptr_t * vCoNames );
+extern ABC_DLL void Nwk_ManPrintFanioNew( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManCleanMarks( Nwk_Man_t * pNtk );
+extern ABC_DLL void Nwk_ManMinimumBase( Nwk_Man_t * pNtk, int fVerbose );
+extern ABC_DLL void Nwk_ManRemoveDupFanins( Nwk_Man_t * pNtk, int fVerbose );
+
+
+
+ABC_NAMESPACE_HEADER_END
+
+
+
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
diff --git a/src/opt/nwk/nwkAig.c b/src/opt/nwk/nwkAig.c
new file mode 100644
index 00000000..7dae0dca
--- /dev/null
+++ b/src/opt/nwk/nwkAig.c
@@ -0,0 +1,112 @@
+/**CFile****************************************************************
+
+ FileName [nwkAig.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis [Translating of AIG into the network.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkAig.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Converts AIG into the network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Man_t * Nwk_ManDeriveFromAig( Aig_Man_t * p )
+{
+ Nwk_Man_t * pNtk;
+ Aig_Obj_t * pObj;
+ int i;
+ pNtk = Nwk_ManAlloc();
+ pNtk->nFanioPlus = 0;
+ Hop_ManStop( pNtk->pManHop );
+ pNtk->pManHop = NULL;
+ pNtk->pName = Abc_UtilStrsav( p->pName );
+ pNtk->pSpec = Abc_UtilStrsav( p->pSpec );
+ pObj = Aig_ManConst1(p);
+ pObj->pData = Nwk_ManCreateNode( pNtk, 0, pObj->nRefs );
+ Aig_ManForEachPi( p, pObj, i )
+ pObj->pData = Nwk_ManCreateCi( pNtk, pObj->nRefs );
+ Aig_ManForEachNode( p, pObj, i )
+ {
+ pObj->pData = Nwk_ManCreateNode( pNtk, 2, pObj->nRefs );
+ Nwk_ObjAddFanin( (Nwk_Obj_t *)pObj->pData, (Nwk_Obj_t *)Aig_ObjFanin0(pObj)->pData );
+ Nwk_ObjAddFanin( (Nwk_Obj_t *)pObj->pData, (Nwk_Obj_t *)Aig_ObjFanin1(pObj)->pData );
+ }
+ Aig_ManForEachPo( p, pObj, i )
+ {
+ pObj->pData = Nwk_ManCreateCo( pNtk );
+ Nwk_ObjAddFanin( (Nwk_Obj_t *)pObj->pData, (Nwk_Obj_t *)Aig_ObjFanin0(pObj)->pData );
+ }
+ return pNtk;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Converts AIG into the network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManDeriveRetimingCut( Aig_Man_t * p, int fForward, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Man_t * pNtk;
+ Nwk_Obj_t * pNode;
+ Aig_Obj_t * pObj;
+ int i;
+ pNtk = Nwk_ManDeriveFromAig( p );
+ if ( fForward )
+ vNodes = Nwk_ManRetimeCutForward( pNtk, Aig_ManRegNum(p), fVerbose );
+ else
+ vNodes = Nwk_ManRetimeCutBackward( pNtk, Aig_ManRegNum(p), fVerbose );
+ Aig_ManForEachObj( p, pObj, i )
+ ((Nwk_Obj_t *)pObj->pData)->pCopy = pObj;
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pNode, i )
+ Vec_PtrWriteEntry( vNodes, i, pNode->pCopy );
+ Nwk_ManFree( pNtk );
+// assert( Vec_PtrSize(vNodes) <= Aig_ManRegNum(p) );
+ return vNodes;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkBidec.c b/src/opt/nwk/nwkBidec.c
new file mode 100644
index 00000000..1b6439d2
--- /dev/null
+++ b/src/opt/nwk/nwkBidec.c
@@ -0,0 +1,177 @@
+/**CFile****************************************************************
+
+ FileName [nwkBidec.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Bi-decomposition of local functions.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkBidec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static inline int Extra_TruthWordNum( int nVars ) { return nVars <= 5 ? 1 : (1 << (nVars - 5)); }
+static inline void Extra_TruthNot( unsigned * pOut, unsigned * pIn, int nVars )
+{
+ int w;
+ for ( w = Extra_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = ~pIn[w];
+}
+static inline void Extra_TruthOr( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars )
+{
+ int w;
+ for ( w = Extra_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = pIn0[w] | pIn1[w];
+}
+static inline void Extra_TruthSharp( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars )
+{
+ int w;
+ for ( w = Extra_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = pIn0[w] & ~pIn1[w];
+}
+
+static inline Hop_Obj_t * Bdc_FunCopyHop( Bdc_Fun_t * pObj ) { return Hop_NotCond( (Hop_Obj_t *)Bdc_FuncCopy(Bdc_Regular(pObj)), Bdc_IsComplement(pObj) ); }
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Resynthesizes nodes using bi-decomposition.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Hop_Obj_t * Nwk_NodeIfNodeResyn( Bdc_Man_t * p, Hop_Man_t * pHop, Hop_Obj_t * pRoot, int nVars, Vec_Int_t * vTruth, unsigned * puCare, float dProb )
+{
+ unsigned * pTruth;
+ Bdc_Fun_t * pFunc;
+ int nNodes, i;
+ assert( nVars <= 16 );
+ // derive truth table
+ pTruth = Hop_ManConvertAigToTruth( pHop, Hop_Regular(pRoot), nVars, vTruth, 0 );
+ if ( Hop_IsComplement(pRoot) )
+ for ( i = Abc_TruthWordNum(nVars)-1; i >= 0; i-- )
+ pTruth[i] = ~pTruth[i];
+ // perform power-aware decomposition
+ if ( dProb >= 0.0 )
+ {
+ float Prob = (float)2.0 * dProb * (1.0 - dProb);
+ assert( Prob >= 0.0 && Prob <= 0.5 );
+ if ( Prob >= 0.4 )
+ {
+ Extra_TruthNot( puCare, puCare, nVars );
+ if ( dProb > 0.5 ) // more 1s than 0s
+ Extra_TruthOr( pTruth, pTruth, puCare, nVars );
+ else
+ Extra_TruthSharp( pTruth, pTruth, puCare, nVars );
+ Extra_TruthNot( puCare, puCare, nVars );
+ // decompose truth table
+ Bdc_ManDecompose( p, pTruth, NULL, nVars, NULL, 1000 );
+ }
+ else
+ {
+ // decompose truth table
+ Bdc_ManDecompose( p, pTruth, puCare, nVars, NULL, 1000 );
+ }
+ }
+ else
+ {
+ // decompose truth table
+ Bdc_ManDecompose( p, pTruth, puCare, nVars, NULL, 1000 );
+ }
+ // convert back into HOP
+ Bdc_FuncSetCopy( Bdc_ManFunc( p, 0 ), Hop_ManConst1( pHop ) );
+ for ( i = 0; i < nVars; i++ )
+ Bdc_FuncSetCopy( Bdc_ManFunc( p, i+1 ), Hop_ManPi( pHop, i ) );
+ nNodes = Bdc_ManNodeNum(p);
+ for ( i = nVars + 1; i < nNodes; i++ )
+ {
+ pFunc = Bdc_ManFunc( p, i );
+ Bdc_FuncSetCopy( pFunc, Hop_And( pHop, Bdc_FunCopyHop(Bdc_FuncFanin0(pFunc)), Bdc_FunCopyHop(Bdc_FuncFanin1(pFunc)) ) );
+ }
+ return Bdc_FunCopyHop( Bdc_ManRoot(p) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Resynthesizes nodes using bi-decomposition.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManBidecResyn( Nwk_Man_t * pNtk, int fVerbose )
+{
+ Bdc_Par_t Pars = {0}, * pPars = &Pars;
+ Bdc_Man_t * p;
+ Nwk_Obj_t * pObj;
+ Vec_Int_t * vTruth;
+ int i, nGainTotal = 0, nNodes1, nNodes2;
+ int clk = clock();
+ pPars->nVarsMax = Nwk_ManGetFaninMax( pNtk );
+ pPars->fVerbose = fVerbose;
+ if ( pPars->nVarsMax < 2 )
+ {
+ printf( "Resynthesis is not performed for networks whose nodes are less than 2 inputs.\n" );
+ return;
+ }
+ if ( pPars->nVarsMax > 15 )
+ {
+ if ( fVerbose )
+ printf( "Resynthesis is not performed for nodes with more than 15 inputs.\n" );
+ pPars->nVarsMax = 15;
+ }
+ vTruth = Vec_IntAlloc( 0 );
+ p = Bdc_ManAlloc( pPars );
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ {
+ if ( Nwk_ObjFaninNum(pObj) > 15 )
+ continue;
+ nNodes1 = Hop_DagSize(pObj->pFunc);
+ pObj->pFunc = Nwk_NodeIfNodeResyn( p, pNtk->pManHop, pObj->pFunc, Nwk_ObjFaninNum(pObj), vTruth, NULL, -1.0 );
+ nNodes2 = Hop_DagSize(pObj->pFunc);
+ nGainTotal += nNodes1 - nNodes2;
+ }
+ Bdc_ManFree( p );
+ Vec_IntFree( vTruth );
+ if ( fVerbose )
+ {
+ printf( "Total gain in AIG nodes = %d. ", nGainTotal );
+ ABC_PRT( "Total runtime", clock() - clk );
+ }
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkCheck.c b/src/opt/nwk/nwkCheck.c
new file mode 100644
index 00000000..24a0d513
--- /dev/null
+++ b/src/opt/nwk/nwkCheck.c
@@ -0,0 +1,76 @@
+/**CFile****************************************************************
+
+ FileName [nwkCheck.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Consistency checking procedures.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkCheck.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Checking the logic network for consistency.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManCheck( Nwk_Man_t * p )
+{
+ Nwk_Obj_t * pObj, * pNext;
+ int i, k, m;
+ // check if the nodes have duplicated fanins
+ Nwk_ManForEachNode( p, pObj, i )
+ {
+ for ( k = 0; k < pObj->nFanins; k++ )
+ for ( m = k + 1; m < pObj->nFanins; m++ )
+ if ( pObj->pFanio[k] == pObj->pFanio[m] )
+ printf( "Node %d has duplicated fanin %d.\n", pObj->Id, pObj->pFanio[k]->Id );
+ }
+ // check if all nodes are in the correct fanin/fanout relationship
+ Nwk_ManForEachObj( p, pObj, i )
+ {
+ Nwk_ObjForEachFanin( pObj, pNext, k )
+ if ( Nwk_ObjFanoutNum(pNext) < 100 && Nwk_ObjFindFanout( pNext, pObj ) == -1 )
+ printf( "Nwk_ManCheck(): Object %d has fanin %d which does not have a corresponding fanout.\n", pObj->Id, pNext->Id );
+ Nwk_ObjForEachFanout( pObj, pNext, k )
+ if ( Nwk_ObjFindFanin( pNext, pObj ) == -1 )
+ printf( "Nwk_ManCheck(): Object %d has fanout %d which does not have a corresponding fanin.\n", pObj->Id, pNext->Id );
+ }
+ return 1;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkDfs.c b/src/opt/nwk/nwkDfs.c
new file mode 100644
index 00000000..59752c59
--- /dev/null
+++ b/src/opt/nwk/nwkDfs.c
@@ -0,0 +1,664 @@
+/**CFile****************************************************************
+
+ FileName [nwkDfs.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [DFS traversals.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Verifies that the objects are in a topo order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManVerifyTopoOrder( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj, * pNext;
+ int i, k, iBox, iTerm1, nTerms;
+ Nwk_ManIncrementTravId( pNtk );
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
+ {
+ Nwk_ObjForEachFanin( pObj, pNext, k )
+ {
+ if ( !Nwk_ObjIsTravIdCurrent(pNext) )
+ {
+ printf( "Node %d has fanin %d that is not in a topological order.\n", pObj->Id, pNext->Id );
+ return 0;
+ }
+ }
+ }
+ else if ( Nwk_ObjIsCi(pObj) )
+ {
+ if ( pNtk->pManTime )
+ {
+ iBox = Tim_ManBoxForCi( pNtk->pManTime, pObj->PioId );
+ if ( iBox >= 0 ) // this is not a true PI
+ {
+ iTerm1 = Tim_ManBoxInputFirst( pNtk->pManTime, iBox );
+ nTerms = Tim_ManBoxInputNum( pNtk->pManTime, iBox );
+ for ( k = 0; k < nTerms; k++ )
+ {
+ pNext = Nwk_ManCo( pNtk, iTerm1 + k );
+ if ( !Nwk_ObjIsTravIdCurrent(pNext) )
+ {
+ printf( "Box %d has input %d that is not in a topological order.\n", iBox, pNext->Id );
+ return 0;
+ }
+ }
+ }
+ }
+ }
+ else
+ assert( 0 );
+ Nwk_ObjSetTravIdCurrent( pObj );
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the number of logic levels not counting PIs/POs.]
+
+ Description [Assumes that white boxes have unit level.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManLevelBackup( Nwk_Man_t * pNtk )
+{
+ Tim_Man_t * pManTimeUnit;
+ Nwk_Obj_t * pObj, * pFanin;
+ int i, k, LevelMax, Level;
+ assert( Nwk_ManVerifyTopoOrder(pNtk) );
+ // clean the levels
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ Nwk_ObjSetLevel( pObj, 0 );
+ // perform level computation
+ LevelMax = 0;
+ pManTimeUnit = pNtk->pManTime ? Tim_ManDupUnit( pNtk->pManTime ) : NULL;
+ if ( pManTimeUnit )
+ Tim_ManIncrementTravId( pManTimeUnit );
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ if ( Nwk_ObjIsCi(pObj) )
+ {
+ Level = pManTimeUnit? (int)Tim_ManGetCiArrival( pManTimeUnit, pObj->PioId ) : 0;
+ Nwk_ObjSetLevel( pObj, Level );
+ }
+ else if ( Nwk_ObjIsCo(pObj) )
+ {
+ Level = Nwk_ObjLevel( Nwk_ObjFanin0(pObj) );
+ if ( pManTimeUnit )
+ Tim_ManSetCoArrival( pManTimeUnit, pObj->PioId, (float)Level );
+ Nwk_ObjSetLevel( pObj, Level );
+ if ( LevelMax < Nwk_ObjLevel(pObj) )
+ LevelMax = Nwk_ObjLevel(pObj);
+ }
+ else if ( Nwk_ObjIsNode(pObj) )
+ {
+ Level = 0;
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( Level < Nwk_ObjLevel(pFanin) )
+ Level = Nwk_ObjLevel(pFanin);
+ Nwk_ObjSetLevel( pObj, Level + 1 );
+ }
+ else
+ assert( 0 );
+ }
+ // set the old timing manager
+ if ( pManTimeUnit )
+ Tim_ManStop( pManTimeUnit );
+ return LevelMax;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the number of logic levels not counting PIs/POs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManLevel_rec( Nwk_Obj_t * pObj )
+{
+ Tim_Man_t * pManTime = pObj->pMan->pManTime;
+ Nwk_Obj_t * pNext;
+ int i, iBox, iTerm1, nTerms, LevelMax = 0;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjIsCi(pObj) )
+ {
+ if ( pManTime )
+ {
+ iBox = Tim_ManBoxForCi( pManTime, pObj->PioId );
+ if ( iBox >= 0 ) // this is not a true PI
+ {
+ iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
+ nTerms = Tim_ManBoxInputNum( pManTime, iBox );
+ for ( i = 0; i < nTerms; i++ )
+ {
+ pNext = Nwk_ManCo(pObj->pMan, iTerm1 + i);
+ Nwk_ManLevel_rec( pNext );
+ if ( LevelMax < Nwk_ObjLevel(pNext) )
+ LevelMax = Nwk_ObjLevel(pNext);
+ }
+ LevelMax++;
+ }
+ }
+ }
+ else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
+ {
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ {
+ Nwk_ManLevel_rec( pNext );
+ if ( LevelMax < Nwk_ObjLevel(pNext) )
+ LevelMax = Nwk_ObjLevel(pNext);
+ }
+ if ( Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0 )
+ LevelMax++;
+ }
+ else
+ assert( 0 );
+ Nwk_ObjSetLevel( pObj, LevelMax );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the number of logic levels not counting PIs/POs.]
+
+ Description [Does not assume that the objects are in a topo order.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManLevel( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ int i, LevelMax = 0;
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ Nwk_ObjSetLevel( pObj, 0 );
+ Nwk_ManIncrementTravId( pNtk );
+ Nwk_ManForEachPo( pNtk, pObj, i )
+ {
+ Nwk_ManLevel_rec( pObj );
+ if ( LevelMax < Nwk_ObjLevel(pObj) )
+ LevelMax = Nwk_ObjLevel(pObj);
+ }
+ Nwk_ManForEachCi( pNtk, pObj, i )
+ {
+ Nwk_ManLevel_rec( pObj );
+ if ( LevelMax < Nwk_ObjLevel(pObj) )
+ LevelMax = Nwk_ObjLevel(pObj);
+ }
+ return LevelMax;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the number of logic levels not counting PIs/POs.]
+
+ Description [Does not assume that the objects are in a topo order.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManLevelMax( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ int i, LevelMax = 0;
+ Nwk_ManForEachPo( pNtk, pObj, i )
+ if ( LevelMax < Nwk_ObjLevel(pObj) )
+ LevelMax = Nwk_ObjLevel(pObj);
+ return LevelMax;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the array of objects in the AIG manager ordered by level.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Vec_t * Nwk_ManLevelize( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ Vec_Vec_t * vLevels;
+ int nLevels, i;
+ assert( Nwk_ManVerifyLevel(pNtk) );
+ nLevels = Nwk_ManLevelMax( pNtk );
+ vLevels = Vec_VecStart( nLevels + 1 );
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ {
+ assert( Nwk_ObjLevel(pObj) <= nLevels );
+ Vec_VecPush( vLevels, Nwk_ObjLevel(pObj), pObj );
+ }
+ return vLevels;
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs DFS for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDfs_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ Nwk_ManDfs_rec( pNext, vNodes );
+ Vec_PtrPush( vNodes, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the DFS ordered array of all objects except latches.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManDfs( Nwk_Man_t * pNtk )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i;
+ Nwk_ManIncrementTravId( pNtk );
+ vNodes = Vec_PtrAlloc( 100 );
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ if ( Nwk_ObjIsCi(pObj) )
+ {
+ Nwk_ObjSetTravIdCurrent( pObj );
+ Vec_PtrPush( vNodes, pObj );
+ }
+ else if ( Nwk_ObjIsCo(pObj) )
+ Nwk_ManDfs_rec( pObj, vNodes );
+ }
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs DFS for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDfsNodes_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjIsCi(pObj) )
+ return;
+ assert( Nwk_ObjIsNode(pObj) );
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ Nwk_ManDfsNodes_rec( pNext, vNodes );
+ Vec_PtrPush( vNodes, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the set of internal nodes rooted in the given nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManDfsNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
+{
+ Vec_Ptr_t * vNodes;
+ int i;
+ // set the traversal ID
+ Nwk_ManIncrementTravId( pNtk );
+ // start the array of nodes
+ vNodes = Vec_PtrAlloc( 100 );
+ // go through the PO nodes and call for each of them
+ for ( i = 0; i < nNodes; i++ )
+ if ( Nwk_ObjIsCo(ppNodes[i]) )
+ Nwk_ManDfsNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
+ else
+ Nwk_ManDfsNodes_rec( ppNodes[i], vNodes );
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs DFS for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDfsReverse_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pNext;
+ int i, iBox, iTerm1, nTerms;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjIsCo(pObj) )
+ {
+ if ( pObj->pMan->pManTime )
+ {
+ iBox = Tim_ManBoxForCo( pObj->pMan->pManTime, pObj->PioId );
+ if ( iBox >= 0 ) // this is not a true PO
+ {
+ iTerm1 = Tim_ManBoxOutputFirst( pObj->pMan->pManTime, iBox );
+ nTerms = Tim_ManBoxOutputNum( pObj->pMan->pManTime, iBox );
+ for ( i = 0; i < nTerms; i++ )
+ {
+ pNext = Nwk_ManCi(pObj->pMan, iTerm1 + i);
+ Nwk_ManDfsReverse_rec( pNext, vNodes );
+ }
+ }
+ }
+ }
+ else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) )
+ {
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ Nwk_ManDfsReverse_rec( pNext, vNodes );
+ }
+ else
+ assert( 0 );
+ Vec_PtrPush( vNodes, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the DFS ordered array of all objects except latches.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManDfsReverse( Nwk_Man_t * pNtk )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i;
+ Nwk_ManIncrementTravId( pNtk );
+ vNodes = Vec_PtrAlloc( 100 );
+ Nwk_ManForEachPi( pNtk, pObj, i )
+ Nwk_ManDfsReverse_rec( pObj, vNodes );
+ // add nodes without fanins
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ if ( Nwk_ObjFaninNum(pObj) == 0 && !Nwk_ObjIsTravIdCurrent(pObj) )
+ Vec_PtrPush( vNodes, pObj );
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs DFS for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManSupportNodes_rec( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pFanin;
+ int i;
+ // if this node is already visited, skip
+ if ( Nwk_ObjIsTravIdCurrent( pNode ) )
+ return;
+ // mark the node as visited
+ Nwk_ObjSetTravIdCurrent( pNode );
+ // collect the CI
+ if ( Nwk_ObjIsCi(pNode) )
+ {
+ Vec_PtrPush( vNodes, pNode );
+ return;
+ }
+ assert( Nwk_ObjIsNode( pNode ) );
+ // visit the transitive fanin of the node
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ Nwk_ManSupportNodes_rec( pFanin, vNodes );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the set of CI nodes in the support of the given nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManSupportNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
+{
+ Vec_Ptr_t * vNodes;
+ int i;
+ // set the traversal ID
+ Nwk_ManIncrementTravId( pNtk );
+ // start the array of nodes
+ vNodes = Vec_PtrAlloc( 100 );
+ // go through the PO nodes and call for each of them
+ for ( i = 0; i < nNodes; i++ )
+ if ( Nwk_ObjIsCo(ppNodes[i]) )
+ Nwk_ManSupportNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
+ else
+ Nwk_ManSupportNodes_rec( ppNodes[i], vNodes );
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the sum total of supports of all outputs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManSupportSum( Nwk_Man_t * pNtk )
+{
+ Vec_Ptr_t * vSupp;
+ Nwk_Obj_t * pObj;
+ int i, nTotalSupps = 0;
+ Nwk_ManForEachCo( pNtk, pObj, i )
+ {
+ vSupp = Nwk_ManSupportNodes( pNtk, &pObj, 1 );
+ nTotalSupps += Vec_PtrSize( vSupp );
+ Vec_PtrFree( vSupp );
+ }
+ printf( "Total supports = %d.\n", nTotalSupps );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences the node's MFFC.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjDeref_rec( Nwk_Obj_t * pNode )
+{
+ Nwk_Obj_t * pFanin;
+ int i, Counter = 1;
+ if ( Nwk_ObjIsCi(pNode) )
+ return 0;
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ {
+ assert( pFanin->nFanouts > 0 );
+ if ( --pFanin->nFanouts == 0 )
+ Counter += Nwk_ObjDeref_rec( pFanin );
+ }
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [References the node's MFFC.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjRef_rec( Nwk_Obj_t * pNode )
+{
+ Nwk_Obj_t * pFanin;
+ int i, Counter = 1;
+ if ( Nwk_ObjIsCi(pNode) )
+ return 0;
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ {
+ if ( pFanin->nFanouts++ == 0 )
+ Counter += Nwk_ObjRef_rec( pFanin );
+ }
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjMffcLabel_rec( Nwk_Obj_t * pNode, int fTopmost )
+{
+ Nwk_Obj_t * pFanin;
+ int i;
+ // add to the new support nodes
+ if ( !fTopmost && (Nwk_ObjIsCi(pNode) || pNode->nFanouts > 0) )
+ return;
+ // skip visited nodes
+ if ( Nwk_ObjIsTravIdCurrent(pNode) )
+ return;
+ Nwk_ObjSetTravIdCurrent(pNode);
+ // recur on the children
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ Nwk_ObjMffcLabel_rec( pFanin, 0 );
+ // collect the internal node
+// printf( "%d ", pNode->Id );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects the internal nodes of the MFFC limited by cut.]
+
+ Description []
+
+ SideEffects [Increments the trav ID and marks visited nodes.]
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjMffcLabel( Nwk_Obj_t * pNode )
+{
+ int Count1, Count2;
+ // dereference the node
+ Count1 = Nwk_ObjDeref_rec( pNode );
+ // collect the nodes inside the MFFC
+ Nwk_ManIncrementTravId( pNode->pMan );
+ Nwk_ObjMffcLabel_rec( pNode, 1 );
+ // reference it back
+ Count2 = Nwk_ObjRef_rec( pNode );
+ assert( Count1 == Count2 );
+ return Count1;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkFanio.c b/src/opt/nwk/nwkFanio.c
new file mode 100644
index 00000000..79fc5b3a
--- /dev/null
+++ b/src/opt/nwk/nwkFanio.c
@@ -0,0 +1,320 @@
+/**CFile****************************************************************
+
+ FileName [nwkFanio.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Manipulation of fanins/fanouts.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkFanio.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Collects fanins of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjCollectFanins( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pFanin;
+ int i;
+ Vec_PtrClear(vNodes);
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ Vec_PtrPush( vNodes, pFanin );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects fanouts of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjCollectFanouts( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pFanout;
+ int i;
+ Vec_PtrClear(vNodes);
+ Nwk_ObjForEachFanout( pNode, pFanout, i )
+ Vec_PtrPush( vNodes, pFanout );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the number of the fanin of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjFindFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin )
+{
+ Nwk_Obj_t * pTemp;
+ int i;
+ Nwk_ObjForEachFanin( pObj, pTemp, i )
+ if ( pTemp == pFanin )
+ return i;
+ return -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the number of the fanout of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjFindFanout( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanout )
+{
+ Nwk_Obj_t * pTemp;
+ int i;
+ Nwk_ObjForEachFanout( pObj, pTemp, i )
+ if ( pTemp == pFanout )
+ return i;
+ return -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the node has to be reallocated.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Nwk_ObjReallocIsNeeded( Nwk_Obj_t * pObj )
+{
+ return pObj->nFanins + pObj->nFanouts == pObj->nFanioAlloc;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Reallocates the object.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static Nwk_Obj_t * Nwk_ManReallocNode( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t ** pFanioOld = pObj->pFanio;
+ assert( Nwk_ObjReallocIsNeeded(pObj) );
+ pObj->pFanio = (Nwk_Obj_t **)Aig_MmFlexEntryFetch( pObj->pMan->pMemObjs, 2 * pObj->nFanioAlloc * sizeof(Nwk_Obj_t *) );
+ memmove( pObj->pFanio, pFanioOld, pObj->nFanioAlloc * sizeof(Nwk_Obj_t *) );
+ pObj->nFanioAlloc *= 2;
+ pObj->pMan->nRealloced++;
+ return NULL;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates fanout/fanin relationship between the nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjAddFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin )
+{
+ int i;
+ assert( pObj->pMan == pFanin->pMan );
+ assert( pObj->Id >= 0 && pFanin->Id >= 0 );
+ if ( Nwk_ObjReallocIsNeeded(pObj) )
+ Nwk_ManReallocNode( pObj );
+ if ( Nwk_ObjReallocIsNeeded(pFanin) )
+ Nwk_ManReallocNode( pFanin );
+ for ( i = pObj->nFanins + pObj->nFanouts; i > pObj->nFanins; i-- )
+ pObj->pFanio[i] = pObj->pFanio[i-1];
+ pObj->pFanio[pObj->nFanins++] = pFanin;
+ pFanin->pFanio[pFanin->nFanins + pFanin->nFanouts++] = pObj;
+ pObj->Level = Abc_MaxInt( pObj->Level, pFanin->Level + Nwk_ObjIsNode(pObj) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Removes fanout/fanin relationship between the nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjDeleteFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFanin )
+{
+ int i, k, Limit, fFound;
+ // remove pFanin from the fanin list of pObj
+ Limit = pObj->nFanins + pObj->nFanouts;
+ fFound = 0;
+ for ( k = i = 0; i < Limit; i++ )
+ if ( fFound || pObj->pFanio[i] != pFanin )
+ pObj->pFanio[k++] = pObj->pFanio[i];
+ else
+ fFound = 1;
+ assert( i == k + 1 ); // if it fails, likely because of duplicated fanin
+ pObj->nFanins--;
+ // remove pObj from the fanout list of pFanin
+ Limit = pFanin->nFanins + pFanin->nFanouts;
+ fFound = 0;
+ for ( k = i = pFanin->nFanins; i < Limit; i++ )
+ if ( fFound || pFanin->pFanio[i] != pObj )
+ pFanin->pFanio[k++] = pFanin->pFanio[i];
+ else
+ fFound = 1;
+ assert( i == k + 1 ); // if it fails, likely because of duplicated fanout
+ pFanin->nFanouts--;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Replaces a fanin of the node.]
+
+ Description [The node is pObj. An old fanin of this node (pFaninOld) has to be
+ replaced by a new fanin (pFaninNew). Assumes that the node and the old fanin
+ are not complemented. The new fanin can be complemented. In this case, the
+ polarity of the new fanin will change, compared to the polarity of the old fanin.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjPatchFanin( Nwk_Obj_t * pObj, Nwk_Obj_t * pFaninOld, Nwk_Obj_t * pFaninNew )
+{
+ int i, k, iFanin, Limit;
+ assert( pFaninOld != pFaninNew );
+ assert( pObj != pFaninOld );
+ assert( pObj != pFaninNew );
+ assert( pObj->pMan == pFaninOld->pMan );
+ assert( pObj->pMan == pFaninNew->pMan );
+ // update the fanin
+ iFanin = Nwk_ObjFindFanin( pObj, pFaninOld );
+ if ( iFanin == -1 )
+ {
+ printf( "Nwk_ObjPatchFanin(); Error! Node %d is not among", pFaninOld->Id );
+ printf( " the fanins of node %d...\n", pObj->Id );
+ return;
+ }
+ pObj->pFanio[iFanin] = pFaninNew;
+ // remove pObj from the fanout list of pFaninOld
+ Limit = pFaninOld->nFanins + pFaninOld->nFanouts;
+ for ( k = i = pFaninOld->nFanins; i < Limit; i++ )
+ if ( pFaninOld->pFanio[i] != pObj )
+ pFaninOld->pFanio[k++] = pFaninOld->pFanio[i];
+ pFaninOld->nFanouts--;
+ // add pObj to the fanout list of pFaninNew
+ if ( Nwk_ObjReallocIsNeeded(pFaninNew) )
+ Nwk_ManReallocNode( pFaninNew );
+ pFaninNew->pFanio[pFaninNew->nFanins + pFaninNew->nFanouts++] = pObj;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Transfers fanout from the old node to the new node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjTransferFanout( Nwk_Obj_t * pNodeFrom, Nwk_Obj_t * pNodeTo )
+{
+ Vec_Ptr_t * vFanouts = pNodeFrom->pMan->vTemp;
+ Nwk_Obj_t * pTemp;
+ int nFanoutsOld, i;
+ assert( !Nwk_ObjIsCo(pNodeFrom) && !Nwk_ObjIsCo(pNodeTo) );
+ assert( pNodeFrom->pMan == pNodeTo->pMan );
+ assert( pNodeFrom != pNodeTo );
+ assert( Nwk_ObjFanoutNum(pNodeFrom) > 0 );
+ // get the fanouts of the old node
+ nFanoutsOld = Nwk_ObjFanoutNum(pNodeTo);
+ Nwk_ObjCollectFanouts( pNodeFrom, vFanouts );
+ // patch the fanin of each of them
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vFanouts, pTemp, i )
+ Nwk_ObjPatchFanin( pTemp, pNodeFrom, pNodeTo );
+ assert( Nwk_ObjFanoutNum(pNodeFrom) == 0 );
+ assert( Nwk_ObjFanoutNum(pNodeTo) == nFanoutsOld + Vec_PtrSize(vFanouts) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Replaces the node by a new node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjReplace( Nwk_Obj_t * pNodeOld, Nwk_Obj_t * pNodeNew )
+{
+ assert( pNodeOld->pMan == pNodeNew->pMan );
+ assert( pNodeOld != pNodeNew );
+ assert( Nwk_ObjFanoutNum(pNodeOld) > 0 );
+ // transfer the fanouts to the old node
+ Nwk_ObjTransferFanout( pNodeOld, pNodeNew );
+ // remove the old node
+ Nwk_ManDeleteNode_rec( pNodeOld );
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkFlow.c b/src/opt/nwk/nwkFlow.c
new file mode 100644
index 00000000..3961e5c2
--- /dev/null
+++ b/src/opt/nwk/nwkFlow.c
@@ -0,0 +1,606 @@
+/**CFile****************************************************************
+
+ FileName [nwkFlow.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis [Max-flow/min-cut computation.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkFlow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+/*
+ This code is based on the papers:
+ A. Hurst, A. Mishchenko, and R. Brayton, "Fast minimum-register retiming
+ via binary maximum-flow", Proc. FMCAD '07, pp. 181-187.
+ A. Hurst, A. Mishchenko, and R. Brayton, "Scalable min-area retiming
+ under simultaneous delay and initial state constraints". Proc. DAC'08.
+*/
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+// predecessors
+static inline Nwk_Obj_t * Nwk_ObjPred( Nwk_Obj_t * pObj ) { return (Nwk_Obj_t *)pObj->pCopy; }
+static inline int Nwk_ObjSetPred( Nwk_Obj_t * pObj, Nwk_Obj_t * p ) { pObj->pCopy = p; return 1; }
+// sink
+static inline int Nwk_ObjIsSink( Nwk_Obj_t * pObj ) { return pObj->MarkA; }
+static inline void Nwk_ObjSetSink( Nwk_Obj_t * pObj ) { pObj->MarkA = 1; }
+// flow
+static inline int Nwk_ObjHasFlow( Nwk_Obj_t * pObj ) { return pObj->MarkB; }
+static inline void Nwk_ObjSetFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 1; }
+static inline void Nwk_ObjClearFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 0; }
+
+// representation of visited nodes
+// pObj->TravId < pNtk->nTravIds-2 --- not visited
+// pObj->TravId == pNtk->nTravIds-2 --- visited bot only
+// pObj->TravId == pNtk->nTravIds-1 --- visited top only
+// pObj->TravId == pNtk->nTravIds --- visited bot and top
+static inline int Nwk_ObjVisitedBotOnly( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 2;
+}
+static inline int Nwk_ObjVisitedBot( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 2 || pObj->TravId == pObj->pMan->nTravIds;
+}
+static inline int Nwk_ObjVisitedTop( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 1 || pObj->TravId == pObj->pMan->nTravIds;
+}
+static inline void Nwk_ObjSetVisitedBot( Nwk_Obj_t * pObj )
+{
+ if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds - 2;
+ else if ( pObj->TravId == pObj->pMan->nTravIds - 1 )
+ pObj->TravId = pObj->pMan->nTravIds;
+ else
+ assert( 0 );
+}
+static inline void Nwk_ObjSetVisitedTop( Nwk_Obj_t * pObj )
+{
+ if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds - 1;
+ else if ( pObj->TravId == pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds;
+ else
+ assert( 0 );
+}
+static inline void Nwk_ManIncrementTravIdFlow( Nwk_Man_t * pMan )
+{
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManIncrementTravId( pMan );
+}
+
+static int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+static int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+
+static int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+static int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Marks TFI of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkTfiCone_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return;
+ pObj->MarkA = 1;
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ Nwk_ManMarkTfiCone_rec( pNext );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Marks TFO of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkTfoCone_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return;
+ pObj->MarkA = 1;
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ Nwk_ManMarkTfoCone_rec( pNext );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Fast forward flow pushing.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 0;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjHasFlow(pObj) )
+ return 0;
+ if ( Nwk_ObjIsSink(pObj) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( Nwk_ManPushForwardFast_rec( pNext, pObj ) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Fast backward flow pushing.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 0;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjHasFlow(pObj) )
+ return 0;
+ if ( Nwk_ObjIsSink(pObj) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushBackwardFast_rec( pNext, pObj ) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the bottom part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedBot(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedBot(pObj);
+ // propagate through the internal edge
+ if ( Nwk_ObjHasFlow(pObj) )
+ {
+ if ( Nwk_ObjPred(pObj) )
+ if ( Nwk_ManPushForwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ else if ( Nwk_ManPushForwardTop_rec(pObj, pObj) )
+ {
+ Nwk_ObjSetFlow( pObj );
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ // try to push through the fanins
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the top part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedTop(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedTop(pObj);
+ // check if this is the sink
+ if ( Nwk_ObjIsSink(pObj) )
+ return 1;
+ // try to push through the fanouts
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
+ return 1;
+ // redirect the flow
+ if ( Nwk_ObjHasFlow(pObj) && !Nwk_ObjIsCi(pObj) )
+ if ( Nwk_ManPushForwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
+ {
+ Nwk_ObjClearFlow( pObj );
+ return Nwk_ObjSetPred( pObj, NULL );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the bottom part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ if ( Nwk_ObjVisitedBot(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedBot(pObj);
+ // propagate through the internal edge
+ if ( Nwk_ObjHasFlow(pObj) )
+ {
+ if ( Nwk_ObjPred(pObj) )
+ if ( Nwk_ManPushBackwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ else if ( Nwk_ManPushBackwardTop_rec(pObj, pObj) )
+ {
+ Nwk_ObjSetFlow( pObj );
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the top part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedTop(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedTop(pObj);
+ // check if this is the sink
+ if ( Nwk_ObjIsSink(pObj) )
+ return 1;
+ // try to push through the fanins
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushBackwardBot_rec( pNext, pPred ) )
+ return 1;
+ // try to push through the fanouts
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( !Nwk_ObjIsCo(pObj) && Nwk_ManPushBackwardTop_rec( pNext, pPred ) )
+ return 1;
+ // redirect the flow
+ if ( Nwk_ObjHasFlow(pObj) )
+ if ( Nwk_ObjPred(pObj) && Nwk_ManPushBackwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
+ {
+ Nwk_ObjClearFlow( pObj );
+ return Nwk_ObjSetPred( pObj, NULL );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 0 if there is an unmarked path to a CI.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManVerifyCut_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return 1;
+ if ( Nwk_ObjIsLo(pObj) )
+ return 0;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 1;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( !Nwk_ManVerifyCut_rec( pNext ) )
+ return 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Verifies the forward cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManRetimeVerifyCutForward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pObj;
+ int i;
+ // mark the nodes
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ {
+ assert( pObj->MarkA == 0 );
+ pObj->MarkA = 1;
+ }
+ // traverse from the COs
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManForEachCo( pMan, pObj, i )
+ if ( !Nwk_ManVerifyCut_rec( pObj ) )
+ printf( "Nwk_ManRetimeVerifyCutForward(): Internal cut verification failed.\n" );
+ // unmark the nodes
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ pObj->MarkA = 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Verifies the forward cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManRetimeVerifyCutBackward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes )
+{
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes minimum cut for forward retiming.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManRetimeCutForward( Nwk_Man_t * pMan, int nLatches, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i, RetValue, Counter = 0, Counter2 = 0;
+ int clk = clock();
+ // set the sequential parameters
+ pMan->nLatches = nLatches;
+ pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
+ pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
+ // mark the COs and the TFO of PIs
+ Nwk_ManForEachCo( pMan, pObj, i )
+ pObj->MarkA = 1;
+ Nwk_ManForEachPiSeq( pMan, pObj, i )
+ Nwk_ManMarkTfoCone_rec( pObj );
+ // start flow computation from each LO
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushForwardFast_rec( pObj, NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter++;
+ }
+ if ( fVerbose )
+ printf( "Forward: Max-flow = %4d -> ", Counter );
+ // continue flow computation from each LO
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushForwardBot_rec( pObj, NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter2++;
+ }
+ if ( fVerbose )
+ printf( "%4d. ", Counter+Counter2 );
+ // repeat flow computation from each LO
+ if ( Counter2 > 0 )
+ {
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ RetValue = Nwk_ManPushForwardBot_rec( pObj, NULL );
+ assert( !RetValue );
+ }
+ }
+ // cut is a set of nodes whose bottom is visited but top is not visited
+ vNodes = Vec_PtrAlloc( Counter+Counter2 );
+ Counter = 0;
+ Nwk_ManForEachObj( pMan, pObj, i )
+ {
+ if ( Nwk_ObjVisitedBotOnly(pObj) )
+ {
+ assert( Nwk_ObjHasFlow(pObj) );
+ assert( !Nwk_ObjIsCo(pObj) );
+ Vec_PtrPush( vNodes, pObj );
+ Counter += Nwk_ObjIsCi(pObj);
+ }
+ }
+ Nwk_ManCleanMarks( pMan );
+// assert( Nwk_ManRetimeVerifyCutForward(pMan, vNodes) );
+ if ( fVerbose )
+ {
+ printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
+ ABC_PRT( "Time", clock() - clk );
+ }
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes minimum cut for backward retiming.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManRetimeCutBackward( Nwk_Man_t * pMan, int nLatches, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i, RetValue, Counter = 0, Counter2 = 0;
+ int clk = clock();
+ // set the sequential parameters
+ pMan->nLatches = nLatches;
+ pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
+ pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
+ // mark the CIs, the TFI of POs, and the constant nodes
+ Nwk_ManForEachCi( pMan, pObj, i )
+ pObj->MarkA = 1;
+ Nwk_ManForEachPoSeq( pMan, pObj, i )
+ Nwk_ManMarkTfiCone_rec( pObj );
+ Nwk_ManForEachNode( pMan, pObj, i )
+ if ( Nwk_ObjFaninNum(pObj) == 0 )
+ pObj->MarkA = 1;
+ // start flow computation from each LI driver
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushBackwardFast_rec( Nwk_ObjFanin0(pObj), NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter++;
+ }
+ if ( fVerbose )
+ printf( "Backward: Max-flow = %4d -> ", Counter );
+ // continue flow computation from each LI driver
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter2++;
+ }
+ if ( fVerbose )
+ printf( "%4d. ", Counter+Counter2 );
+ // repeat flow computation from each LI driver
+ if ( Counter2 > 0 )
+ {
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ RetValue = Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL );
+ assert( !RetValue );
+ }
+ }
+ // cut is a set of nodes whose bottom is visited but top is not visited
+ vNodes = Vec_PtrAlloc( Counter+Counter2 );
+ Nwk_ManForEachObj( pMan, pObj, i )
+ {
+ if ( Nwk_ObjVisitedBotOnly(pObj) )
+ {
+ assert( Nwk_ObjHasFlow(pObj) );
+ assert( !Nwk_ObjIsCo(pObj) );
+ Vec_PtrPush( vNodes, pObj );
+ }
+ }
+ // count CO drivers
+ Counter = 0;
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ if ( Nwk_ObjVisitedBotOnly( Nwk_ObjFanin0(pObj) ) )
+ Counter++;
+ Nwk_ManCleanMarks( pMan );
+// assert( Nwk_ManRetimeVerifyCutBackward(pMan, vNodes) );
+ if ( fVerbose )
+ {
+ printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
+ ABC_PRT( "Time", clock() - clk );
+ }
+ return vNodes;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkFlow_depth.c b/src/opt/nwk/nwkFlow_depth.c
new file mode 100644
index 00000000..6c2e7eb9
--- /dev/null
+++ b/src/opt/nwk/nwkFlow_depth.c
@@ -0,0 +1,631 @@
+/**CFile****************************************************************
+
+ FileName [nwkFlow.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis [Max-flow/min-cut computation.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkFlow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+/*
+ This code is based on the papers:
+ A. Hurst, A. Mishchenko, and R. Brayton, "Fast minimum-register retiming
+ via binary maximum-flow", Proc. FMCAD '07, pp. 181-187.
+ A. Hurst, A. Mishchenko, and R. Brayton, "Scalable min-area retiming
+ under simultaneous delay and initial state constraints". Proc. DAC'08.
+*/
+
+int DepthFwd, DepthBwd, DepthFwdMax, DepthBwdMax;
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+// predecessors
+static inline Nwk_Obj_t * Nwk_ObjPred( Nwk_Obj_t * pObj ) { return pObj->pCopy; }
+static inline int Nwk_ObjSetPred( Nwk_Obj_t * pObj, Nwk_Obj_t * p ) { pObj->pCopy = p; return 1; }
+// sink
+static inline int Nwk_ObjIsSink( Nwk_Obj_t * pObj ) { return pObj->MarkA; }
+static inline void Nwk_ObjSetSink( Nwk_Obj_t * pObj ) { pObj->MarkA = 1; }
+// flow
+static inline int Nwk_ObjHasFlow( Nwk_Obj_t * pObj ) { return pObj->MarkB; }
+static inline void Nwk_ObjSetFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 1; }
+static inline void Nwk_ObjClearFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 0; }
+
+// representation of visited nodes
+// pObj->TravId < pNtk->nTravIds-2 --- not visited
+// pObj->TravId == pNtk->nTravIds-2 --- visited bot only
+// pObj->TravId == pNtk->nTravIds-1 --- visited top only
+// pObj->TravId == pNtk->nTravIds --- visited bot and top
+static inline int Nwk_ObjVisitedBotOnly( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 2;
+}
+static inline int Nwk_ObjVisitedBot( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 2 || pObj->TravId == pObj->pMan->nTravIds;
+}
+static inline int Nwk_ObjVisitedTop( Nwk_Obj_t * pObj )
+{
+ return pObj->TravId == pObj->pMan->nTravIds - 1 || pObj->TravId == pObj->pMan->nTravIds;
+}
+static inline void Nwk_ObjSetVisitedBot( Nwk_Obj_t * pObj )
+{
+ if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds - 2;
+ else if ( pObj->TravId == pObj->pMan->nTravIds - 1 )
+ pObj->TravId = pObj->pMan->nTravIds;
+ else
+ assert( 0 );
+}
+static inline void Nwk_ObjSetVisitedTop( Nwk_Obj_t * pObj )
+{
+ if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds - 1;
+ else if ( pObj->TravId == pObj->pMan->nTravIds - 2 )
+ pObj->TravId = pObj->pMan->nTravIds;
+ else
+ assert( 0 );
+}
+static inline Nwk_ManIncrementTravIdFlow( Nwk_Man_t * pMan )
+{
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManIncrementTravId( pMan );
+}
+
+static int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+static int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+
+static int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+static int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Marks TFI of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkTfiCone_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return;
+ pObj->MarkA = 1;
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ Nwk_ManMarkTfiCone_rec( pNext );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Marks TFO of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkTfoCone_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return;
+ pObj->MarkA = 1;
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ Nwk_ManMarkTfoCone_rec( pNext );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Fast forward flow pushing.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 0;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjHasFlow(pObj) )
+ return 0;
+ if ( Nwk_ObjIsSink(pObj) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( Nwk_ManPushForwardFast_rec( pNext, pObj ) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Fast backward flow pushing.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 0;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ if ( Nwk_ObjHasFlow(pObj) )
+ return 0;
+ if ( Nwk_ObjIsSink(pObj) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushBackwardFast_rec( pNext, pObj ) )
+ {
+ Nwk_ObjSetFlow(pObj);
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the bottom part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedBot(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedBot(pObj);
+ DepthFwd++;
+ if ( DepthFwdMax < DepthFwd )
+ DepthFwdMax = DepthFwd;
+ // propagate through the internal edge
+ if ( Nwk_ObjHasFlow(pObj) )
+ {
+ if ( Nwk_ObjPred(pObj) )
+ if ( Nwk_ManPushForwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
+ {
+ DepthFwd--;
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ }
+ else if ( Nwk_ManPushForwardTop_rec(pObj, pObj) )
+ {
+ DepthFwd--;
+ Nwk_ObjSetFlow( pObj );
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ // try to push through the fanins
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
+ {
+ DepthFwd--;
+ return 1;
+ }
+ DepthFwd--;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the top part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedTop(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedTop(pObj);
+ // check if this is the sink
+ if ( Nwk_ObjIsSink(pObj) )
+ return 1;
+ DepthFwd++;
+ if ( DepthFwdMax < DepthFwd )
+ DepthFwdMax = DepthFwd;
+ // try to push through the fanouts
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
+ {
+ DepthFwd--;
+ return 1;
+ }
+ // redirect the flow
+ if ( Nwk_ObjHasFlow(pObj) && !Nwk_ObjIsCi(pObj) )
+ if ( Nwk_ManPushForwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
+ {
+ DepthFwd--;
+ Nwk_ObjClearFlow( pObj );
+ return Nwk_ObjSetPred( pObj, NULL );
+ }
+ DepthFwd--;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the bottom part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ if ( Nwk_ObjVisitedBot(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedBot(pObj);
+ // propagate through the internal edge
+ if ( Nwk_ObjHasFlow(pObj) )
+ {
+ if ( Nwk_ObjPred(pObj) )
+ if ( Nwk_ManPushBackwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ else if ( Nwk_ManPushBackwardTop_rec(pObj, pObj) )
+ {
+ Nwk_ObjSetFlow( pObj );
+ return Nwk_ObjSetPred( pObj, pPred );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Pushing the flow through the top part of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( Nwk_ObjVisitedTop(pObj) )
+ return 0;
+ Nwk_ObjSetVisitedTop(pObj);
+ // check if this is the sink
+ if ( Nwk_ObjIsSink(pObj) )
+ return 1;
+ // try to push through the fanins
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( Nwk_ManPushBackwardBot_rec( pNext, pPred ) )
+ return 1;
+ // try to push through the fanouts
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ if ( !Nwk_ObjIsCo(pObj) && Nwk_ManPushBackwardTop_rec( pNext, pPred ) )
+ return 1;
+ // redirect the flow
+ if ( Nwk_ObjHasFlow(pObj) )
+ if ( Nwk_ObjPred(pObj) && Nwk_ManPushBackwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
+ {
+ Nwk_ObjClearFlow( pObj );
+ return Nwk_ObjSetPred( pObj, NULL );
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 0 if there is an unmarked path to a CI.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManVerifyCut_rec( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( pObj->MarkA )
+ return 1;
+ if ( Nwk_ObjIsLo(pObj) )
+ return 0;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ return 1;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ if ( !Nwk_ManVerifyCut_rec( pNext ) )
+ return 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Verifies the forward cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManRetimeVerifyCutForward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes )
+{
+ Nwk_Obj_t * pObj;
+ int i;
+ // mark the nodes
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ {
+ assert( pObj->MarkA == 0 );
+ pObj->MarkA = 1;
+ }
+ // traverse from the COs
+ Nwk_ManIncrementTravId( pMan );
+ Nwk_ManForEachCo( pMan, pObj, i )
+ if ( !Nwk_ManVerifyCut_rec( pObj ) )
+ printf( "Nwk_ManRetimeVerifyCutForward(): Internal cut verification failed.\n" );
+ // unmark the nodes
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ pObj->MarkA = 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Verifies the forward cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManRetimeVerifyCutBackward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes )
+{
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes minimum cut for forward retiming.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManRetimeCutForward( Nwk_Man_t * pMan, int nLatches, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i, RetValue, Counter = 0, Counter2 = 0;
+ int clk = clock();
+ // set the sequential parameters
+ pMan->nLatches = nLatches;
+ pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
+ pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
+ // mark the COs and the TFO of PIs
+ Nwk_ManForEachCo( pMan, pObj, i )
+ pObj->MarkA = 1;
+ Nwk_ManForEachPiSeq( pMan, pObj, i )
+ Nwk_ManMarkTfoCone_rec( pObj );
+ // start flow computation from each LO
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushForwardFast_rec( pObj, NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter++;
+ }
+ if ( fVerbose )
+ printf( "Forward: Max-flow = %4d -> ", Counter );
+ // continue flow computation from each LO
+ DepthFwdMax = DepthFwd = 0;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ printf( "%d ", DepthFwdMax );
+ if ( !Nwk_ManPushForwardBot_rec( pObj, NULL ) )
+ continue;
+ assert( DepthFwd == 0 );
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter2++;
+ }
+ printf( "DepthMax = %d.\n", DepthFwdMax );
+ if ( fVerbose )
+ printf( "%4d. ", Counter+Counter2 );
+ // repeat flow computation from each LO
+ if ( Counter2 > 0 )
+ {
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLoSeq( pMan, pObj, i )
+ {
+ RetValue = Nwk_ManPushForwardBot_rec( pObj, NULL );
+ assert( !RetValue );
+ }
+ }
+ // cut is a set of nodes whose bottom is visited but top is not visited
+ vNodes = Vec_PtrAlloc( Counter+Counter2 );
+ Counter = 0;
+ Nwk_ManForEachObj( pMan, pObj, i )
+ {
+ if ( Nwk_ObjVisitedBotOnly(pObj) )
+ {
+ assert( Nwk_ObjHasFlow(pObj) );
+ assert( !Nwk_ObjIsCo(pObj) );
+ Vec_PtrPush( vNodes, pObj );
+ Counter += Nwk_ObjIsCi(pObj);
+ }
+ }
+ Nwk_ManCleanMarks( pMan );
+ assert( Nwk_ManRetimeVerifyCutForward(pMan, vNodes) );
+ if ( fVerbose )
+ {
+ printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
+ PRT( "Time", clock() - clk );
+ }
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes minimum cut for backward retiming.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * Nwk_ManRetimeCutBackward( Nwk_Man_t * pMan, int nLatches, int fVerbose )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ int i, RetValue, Counter = 0, Counter2 = 0;
+ int clk = clock();
+ // set the sequential parameters
+ pMan->nLatches = nLatches;
+ pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
+ pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
+ // mark the CIs, the TFI of POs, and the constant nodes
+ Nwk_ManForEachCi( pMan, pObj, i )
+ pObj->MarkA = 1;
+ Nwk_ManForEachPoSeq( pMan, pObj, i )
+ Nwk_ManMarkTfiCone_rec( pObj );
+ Nwk_ManForEachNode( pMan, pObj, i )
+ if ( Nwk_ObjFaninNum(pObj) == 0 )
+ pObj->MarkA = 1;
+ // start flow computation from each LI driver
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushBackwardFast_rec( Nwk_ObjFanin0(pObj), NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter++;
+ }
+ if ( fVerbose )
+ printf( "Backward: Max-flow = %4d -> ", Counter );
+ // continue flow computation from each LI driver
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ if ( !Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL ) )
+ continue;
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Counter2++;
+ }
+ if ( fVerbose )
+ printf( "%4d. ", Counter+Counter2 );
+ // repeat flow computation from each LI driver
+ if ( Counter2 > 0 )
+ {
+ Nwk_ManIncrementTravIdFlow( pMan );
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ {
+ RetValue = Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL );
+ assert( !RetValue );
+ }
+ }
+ // cut is a set of nodes whose bottom is visited but top is not visited
+ vNodes = Vec_PtrAlloc( Counter+Counter2 );
+ Nwk_ManForEachObj( pMan, pObj, i )
+ {
+ if ( Nwk_ObjVisitedBotOnly(pObj) )
+ {
+ assert( Nwk_ObjHasFlow(pObj) );
+ assert( !Nwk_ObjIsCo(pObj) );
+ Vec_PtrPush( vNodes, pObj );
+ }
+ }
+ // count CO drivers
+ Counter = 0;
+ Nwk_ManForEachLiSeq( pMan, pObj, i )
+ if ( Nwk_ObjVisitedBotOnly( Nwk_ObjFanin0(pObj) ) )
+ Counter++;
+ Nwk_ManCleanMarks( pMan );
+ assert( Nwk_ManRetimeVerifyCutBackward(pMan, vNodes) );
+ if ( fVerbose )
+ {
+ printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
+ PRT( "Time", clock() - clk );
+ }
+ return vNodes;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkMan.c b/src/opt/nwk/nwkMan.c
new file mode 100644
index 00000000..f286dc50
--- /dev/null
+++ b/src/opt/nwk/nwkMan.c
@@ -0,0 +1,278 @@
+/**CFile****************************************************************
+
+ FileName [nwkMan.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Network manager.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkMan.c,v 1.1 2008/10/10 14:09:30 mjarvin Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Allocates the manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Man_t * Nwk_ManAlloc()
+{
+ Nwk_Man_t * p;
+ p = ABC_ALLOC( Nwk_Man_t, 1 );
+ memset( p, 0, sizeof(Nwk_Man_t) );
+ p->vCis = Vec_PtrAlloc( 1000 );
+ p->vCos = Vec_PtrAlloc( 1000 );
+ p->vObjs = Vec_PtrAlloc( 1000 );
+ p->vTemp = Vec_PtrAlloc( 1000 );
+ p->nFanioPlus = 2;
+ p->pMemObjs = Aig_MmFlexStart();
+ p->pManHop = Hop_ManStart();
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Deallocates the manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManFree( Nwk_Man_t * p )
+{
+// printf( "The number of realloced nodes = %d.\n", p->nRealloced );
+ if ( p->pName ) ABC_FREE( p->pName );
+ if ( p->pSpec ) ABC_FREE( p->pSpec );
+ if ( p->vCis ) Vec_PtrFree( p->vCis );
+ if ( p->vCos ) Vec_PtrFree( p->vCos );
+ if ( p->vObjs ) Vec_PtrFree( p->vObjs );
+ if ( p->vTemp ) Vec_PtrFree( p->vTemp );
+ if ( p->pManTime ) Tim_ManStop( p->pManTime );
+ if ( p->pMemObjs ) Aig_MmFlexStop( p->pMemObjs, 0 );
+ if ( p->pManHop ) Hop_ManStop( p->pManHop );
+ ABC_FREE( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints stats of the manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManPrintLutSizes( Nwk_Man_t * p, If_Lib_t * pLutLib )
+{
+ Nwk_Obj_t * pObj;
+ int i, Counters[256] = {0};
+ Nwk_ManForEachNode( p, pObj, i )
+ Counters[Nwk_ObjFaninNum(pObj)]++;
+ printf( "LUTs by size: " );
+ for ( i = 0; i <= pLutLib->LutMax; i++ )
+ printf( "%d:%d ", i, Counters[i] );
+}
+
+/**Function*************************************************************
+
+ Synopsis [If the network is best, saves it in "best.blif" and returns 1.]
+
+ Description [If the networks are incomparable, saves the new network,
+ returns its parameters in the internal parameter structure, and returns 1.
+ If the new network is not a logic network, quits without saving and returns 0.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManCompareAndSaveBest( Nwk_Man_t * pNtk, void * pNtl )
+{
+// extern void Ntl_WriteBlifLogic( Nwk_Man_t * pNtk, void * pNtl, char * pFileName );
+ extern void Nwk_ManDumpBlif( Nwk_Man_t * pNtk, char * pFileName, Vec_Ptr_t * vPiNames, Vec_Ptr_t * vPoNames );
+ static struct ParStruct {
+ char * pName; // name of the best saved network
+ int Depth; // depth of the best saved network
+ int Flops; // flops in the best saved network
+ int Nodes; // nodes in the best saved network
+ int nPis; // the number of primary inputs
+ int nPos; // the number of primary outputs
+ } ParsNew, ParsBest = { 0 };
+ // free storage for the name
+ if ( pNtk == NULL )
+ {
+ ABC_FREE( ParsBest.pName );
+ return 0;
+ }
+ // get the parameters
+ ParsNew.Depth = Nwk_ManLevel( pNtk );
+ ParsNew.Flops = Nwk_ManLatchNum( pNtk );
+ ParsNew.Nodes = Nwk_ManNodeNum( pNtk );
+ ParsNew.nPis = Nwk_ManPiNum( pNtk );
+ ParsNew.nPos = Nwk_ManPoNum( pNtk );
+ // reset the parameters if the network has the same name
+ if ( ParsBest.pName == NULL ||
+ strcmp(ParsBest.pName, pNtk->pName) ||
+ ParsBest.Depth > ParsNew.Depth ||
+ (ParsBest.Depth == ParsNew.Depth && ParsBest.Flops > ParsNew.Flops) ||
+ (ParsBest.Depth == ParsNew.Depth && ParsBest.Flops == ParsNew.Flops && ParsBest.Nodes > ParsNew.Nodes) )
+ {
+ ABC_FREE( ParsBest.pName );
+ ParsBest.pName = Abc_UtilStrsav( pNtk->pName );
+ ParsBest.Depth = ParsNew.Depth;
+ ParsBest.Flops = ParsNew.Flops;
+ ParsBest.Nodes = ParsNew.Nodes;
+ ParsBest.nPis = ParsNew.nPis;
+ ParsBest.nPos = ParsNew.nPos;
+ // write the network
+// Ntl_WriteBlifLogic( pNtk, pNtl, "best.blif" );
+// Nwk_ManDumpBlif( pNtk, "best_map.blif", NULL, NULL );
+ return 1;
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+char * Nwk_FileNameGeneric( char * FileName )
+{
+ char * pDot, * pRes;
+ pRes = Abc_UtilStrsav( FileName );
+ if ( (pDot = strrchr( pRes, '.' )) )
+ *pDot = 0;
+ return pRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Marks nodes for power-optimization.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float Nwl_ManComputeTotalSwitching( Nwk_Man_t * pNtk )
+{
+ extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
+ Vec_Int_t * vSwitching;
+ float * pSwitching;
+ Aig_Man_t * pAig;
+ Aig_Obj_t * pObjAig;
+ Nwk_Obj_t * pObjAbc;
+ float Result = (float)0;
+ int i;
+ // strash the network
+ // map network into an AIG
+ pAig = Nwk_ManStrash( pNtk );
+ vSwitching = Saig_ManComputeSwitchProbs( pAig, 48, 16, 0 );
+ pSwitching = (float *)vSwitching->pArray;
+ Nwk_ManForEachObj( pNtk, pObjAbc, i )
+ {
+ if ( (pObjAig = Aig_Regular((Aig_Obj_t *)pObjAbc->pCopy)) )
+ Result += Nwk_ObjFanoutNum(pObjAbc) * pSwitching[pObjAig->Id];
+ }
+ Vec_IntFree( vSwitching );
+ Aig_ManStop( pAig );
+ return Result;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints stats of the manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManPrintStats( Nwk_Man_t * pNtk, If_Lib_t * pLutLib, int fSaveBest, int fDumpResult, int fPower, Ntl_Man_t * pNtl )
+{
+// extern int Ntl_ManLatchNum( Ntl_Man_t * p );
+// extern void Ntl_ManWriteBlifLogic( Nwk_Man_t * pNtk, void * pNtl, char * pFileName );
+ if ( fSaveBest )
+ Nwk_ManCompareAndSaveBest( pNtk, pNtl );
+ if ( fDumpResult )
+ {
+ char Buffer[1000] = {0};
+ const char * pNameGen = pNtk->pSpec? Nwk_FileNameGeneric( pNtk->pSpec ) : "nameless_";
+ sprintf( Buffer, "%s_dump.blif", pNameGen );
+// Ntl_ManWriteBlifLogic( pNtk, pNtl, Buffer );
+// sprintf( Buffer, "%s_dump_map.blif", pNameGen );
+// Nwk_ManDumpBlif( pNtk, Buffer, NULL, NULL );
+ if ( pNtk->pSpec ) ABC_FREE( pNameGen );
+ }
+
+ pNtk->pLutLib = pLutLib;
+ printf( "%-15s : ", pNtk->pName );
+ printf( "pi = %5d ", Nwk_ManPiNum(pNtk) );
+ printf( "po = %5d ", Nwk_ManPoNum(pNtk) );
+ printf( "ci = %5d ", Nwk_ManCiNum(pNtk) );
+ printf( "co = %5d ", Nwk_ManCoNum(pNtk) );
+// printf( "lat = %5d ", Ntl_ManLatchNum(pNtl) );
+ printf( "node = %5d ", Nwk_ManNodeNum(pNtk) );
+ printf( "edge = %5d ", Nwk_ManGetTotalFanins(pNtk) );
+ printf( "aig = %6d ", Nwk_ManGetAigNodeNum(pNtk) );
+ printf( "lev = %3d ", Nwk_ManLevel(pNtk) );
+// printf( "lev2 = %3d ", Nwk_ManLevelBackup(pNtk) );
+ printf( "delay = %5.2f ", Nwk_ManDelayTraceLut(pNtk) );
+ if ( fPower )
+ printf( "power = %7.2f ", Nwl_ManComputeTotalSwitching(pNtk) );
+ Nwk_ManPrintLutSizes( pNtk, pLutLib );
+ printf( "\n" );
+// Nwk_ManDelayTracePrint( pNtk, pLutLib );
+ fflush( stdout );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkMap.c b/src/opt/nwk/nwkMap.c
new file mode 100644
index 00000000..61ee50e8
--- /dev/null
+++ b/src/opt/nwk/nwkMap.c
@@ -0,0 +1,396 @@
+/**CFile****************************************************************
+
+ FileName [nwkMap.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Interface to technology mapping.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkMap.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+#include "src/map/if/if.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Load the network into FPGA manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManSetIfParsDefault( If_Par_t * pPars )
+{
+// extern void * Abc_FrameReadLibLut();
+ // set defaults
+ memset( pPars, 0, sizeof(If_Par_t) );
+ // user-controlable paramters
+// pPars->nLutSize = -1;
+ pPars->nLutSize = 6;
+ pPars->nCutsMax = 8;
+ pPars->nFlowIters = 1;
+ pPars->nAreaIters = 2;
+ pPars->DelayTarget = -1;
+ pPars->Epsilon = (float)0.005;
+ pPars->fPreprocess = 1;
+ pPars->fArea = 0;
+ pPars->fFancy = 0;
+ pPars->fExpRed = 1; ////
+ pPars->fLatchPaths = 0;
+ pPars->fEdge = 1;
+ pPars->fPower = 0;
+ pPars->fCutMin = 0;
+ pPars->fSeqMap = 0;
+ pPars->fVerbose = 0;
+ // internal parameters
+ pPars->fTruth = 0;
+ pPars->nLatches = 0;
+ pPars->fLiftLeaves = 0;
+// pPars->pLutLib = Abc_FrameReadLibLut();
+ pPars->pLutLib = NULL;
+ pPars->pTimesArr = NULL;
+ pPars->pTimesArr = NULL;
+ pPars->pFuncCost = NULL;
+/*
+ if ( pPars->nLutSize == -1 )
+ {
+ if ( pPars->pLutLib == NULL )
+ {
+ printf( "The LUT library is not given.\n" );
+ return;
+ }
+ // get LUT size from the library
+ pPars->nLutSize = pPars->pLutLib->LutMax;
+ }
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Load the network into FPGA manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Man_t * Nwk_ManToIf( Aig_Man_t * p, If_Par_t * pPars, Vec_Ptr_t * vAigToIf )
+{
+ extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
+ Vec_Int_t * vSwitching = NULL, * vSwitching2 = NULL;
+ float * pSwitching, * pSwitching2;
+ If_Man_t * pIfMan;
+ If_Obj_t * pIfObj;
+ Aig_Obj_t * pNode, * pFanin, * pPrev;
+ int i, clk = clock();
+ // set the number of registers (switch activity will be combinational)
+ Aig_ManSetRegNum( p, 0 );
+ if ( pPars->fPower )
+ {
+ vSwitching = Saig_ManComputeSwitchProbs( p, 48, 16, 0 );
+ if ( pPars->fVerbose )
+ {
+ ABC_PRT( "Computing switching activity", clock() - clk );
+ }
+ pSwitching = (float *)vSwitching->pArray;
+ vSwitching2 = Vec_IntStart( Aig_ManObjNumMax(p) );
+ pSwitching2 = (float *)vSwitching2->pArray;
+ }
+ // start the mapping manager and set its parameters
+ pIfMan = If_ManStart( pPars );
+ pIfMan->vSwitching = vSwitching2;
+ // load the AIG into the mapper
+ Aig_ManForEachObj( p, pNode, i )
+ {
+ if ( Aig_ObjIsAnd(pNode) )
+ {
+ pIfObj = If_ManCreateAnd( pIfMan,
+ If_NotCond( (If_Obj_t *)Aig_ObjFanin0(pNode)->pData, Aig_ObjFaninC0(pNode) ),
+ If_NotCond( (If_Obj_t *)Aig_ObjFanin1(pNode)->pData, Aig_ObjFaninC1(pNode) ) );
+// printf( "no%d=%d\n ", If_ObjId(pIfObj), If_ObjLevel(pIfObj) );
+ }
+ else if ( Aig_ObjIsPi(pNode) )
+ {
+ pIfObj = If_ManCreateCi( pIfMan );
+ If_ObjSetLevel( pIfObj, Aig_ObjLevel(pNode) );
+// printf( "pi%d=%d\n ", If_ObjId(pIfObj), If_ObjLevel(pIfObj) );
+ if ( pIfMan->nLevelMax < (int)pIfObj->Level )
+ pIfMan->nLevelMax = (int)pIfObj->Level;
+ }
+ else if ( Aig_ObjIsPo(pNode) )
+ {
+ pIfObj = If_ManCreateCo( pIfMan, If_NotCond( (If_Obj_t *)Aig_ObjFanin0(pNode)->pData, Aig_ObjFaninC0(pNode) ) );
+// printf( "po%d=%d\n ", If_ObjId(pIfObj), If_ObjLevel(pIfObj) );
+ }
+ else if ( Aig_ObjIsConst1(pNode) )
+ pIfObj = If_ManConst1( pIfMan );
+ else // add the node to the mapper
+ assert( 0 );
+ // save the result
+ assert( Vec_PtrEntry(vAigToIf, i) == NULL );
+ Vec_PtrWriteEntry( vAigToIf, i, pIfObj );
+ pNode->pData = pIfObj;
+ if ( vSwitching2 )
+ pSwitching2[pIfObj->Id] = pSwitching[pNode->Id];
+ // set up the choice node
+ if ( Aig_ObjIsChoice( p, pNode ) )
+ {
+ pIfMan->nChoices++;
+ for ( pPrev = pNode, pFanin = Aig_ObjEquiv(p, pNode); pFanin; pPrev = pFanin, pFanin = Aig_ObjEquiv(p, pFanin) )
+ If_ObjSetChoice( (If_Obj_t *)pPrev->pData, (If_Obj_t *)pFanin->pData );
+ If_ManCreateChoice( pIfMan, (If_Obj_t *)pNode->pData );
+ }
+// assert( If_ObjLevel(pIfObj) == Aig_ObjLevel(pNode) );
+ }
+ if ( vSwitching )
+ Vec_IntFree( vSwitching );
+ return pIfMan;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Recursively derives the local AIG for the cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Hop_Obj_t * Nwk_NodeIfToHop2_rec( Hop_Man_t * pHopMan, If_Man_t * pIfMan, If_Obj_t * pIfObj, Vec_Ptr_t * vVisited )
+{
+ If_Cut_t * pCut;
+ If_Obj_t * pTemp;
+ Hop_Obj_t * gFunc, * gFunc0, * gFunc1;
+ // get the best cut
+ pCut = If_ObjCutBest(pIfObj);
+ // if the cut is visited, return the result
+ if ( If_CutData(pCut) )
+ return (Hop_Obj_t *)If_CutData(pCut);
+ // mark the node as visited
+ Vec_PtrPush( vVisited, pCut );
+ // insert the worst case
+ If_CutSetData( pCut, (void *)1 );
+ // skip in case of primary input
+ if ( If_ObjIsCi(pIfObj) )
+ return (Hop_Obj_t *)If_CutData(pCut);
+ // compute the functions of the children
+ for ( pTemp = pIfObj; pTemp; pTemp = pTemp->pEquiv )
+ {
+ gFunc0 = Nwk_NodeIfToHop2_rec( pHopMan, pIfMan, pTemp->pFanin0, vVisited );
+ if ( gFunc0 == (void *)1 )
+ continue;
+ gFunc1 = Nwk_NodeIfToHop2_rec( pHopMan, pIfMan, pTemp->pFanin1, vVisited );
+ if ( gFunc1 == (void *)1 )
+ continue;
+ // both branches are solved
+ gFunc = Hop_And( pHopMan, Hop_NotCond(gFunc0, pTemp->fCompl0), Hop_NotCond(gFunc1, pTemp->fCompl1) );
+ if ( pTemp->fPhase != pIfObj->fPhase )
+ gFunc = Hop_Not(gFunc);
+ If_CutSetData( pCut, gFunc );
+ break;
+ }
+ return (Hop_Obj_t *)If_CutData(pCut);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Derives the local AIG for the cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Hop_Obj_t * Nwk_NodeIfToHop( Hop_Man_t * pHopMan, If_Man_t * pIfMan, If_Obj_t * pIfObj )
+{
+ If_Cut_t * pCut;
+ Hop_Obj_t * gFunc;
+ If_Obj_t * pLeaf;
+ int i;
+ // get the best cut
+ pCut = If_ObjCutBest(pIfObj);
+ assert( pCut->nLeaves > 1 );
+ // set the leaf variables
+ If_CutForEachLeaf( pIfMan, pCut, pLeaf, i )
+ If_CutSetData( If_ObjCutBest(pLeaf), Hop_IthVar(pHopMan, i) );
+ // recursively compute the function while collecting visited cuts
+ Vec_PtrClear( pIfMan->vTemp );
+ gFunc = Nwk_NodeIfToHop2_rec( pHopMan, pIfMan, pIfObj, pIfMan->vTemp );
+ if ( gFunc == (void *)1 )
+ {
+ printf( "Nwk_NodeIfToHop(): Computing local AIG has failed.\n" );
+ return NULL;
+ }
+// printf( "%d ", Vec_PtrSize(p->vTemp) );
+ // clean the cuts
+ If_CutForEachLeaf( pIfMan, pCut, pLeaf, i )
+ If_CutSetData( If_ObjCutBest(pLeaf), NULL );
+ Vec_PtrForEachEntry( If_Cut_t *, pIfMan->vTemp, pCut, i )
+ If_CutSetData( pCut, NULL );
+ return gFunc;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Man_t * Nwk_ManFromIf( If_Man_t * pIfMan, Aig_Man_t * p, Vec_Ptr_t * vAigToIf )
+{
+ Vec_Ptr_t * vIfToAig;
+ Nwk_Man_t * pNtk;
+ Nwk_Obj_t * pObjNew;
+ Aig_Obj_t * pObj, * pObjRepr;
+ If_Obj_t * pIfObj;
+ If_Cut_t * pCutBest;
+ int i, k, nLeaves, * ppLeaves;
+ assert( Aig_ManPiNum(p) == If_ManCiNum(pIfMan) );
+ assert( Aig_ManPoNum(p) == If_ManCoNum(pIfMan) );
+ assert( Aig_ManNodeNum(p) == If_ManAndNum(pIfMan) );
+ Aig_ManCleanData( p );
+ If_ManCleanCutData( pIfMan );
+ // create mapping of IF to AIG
+ vIfToAig = Vec_PtrStart( If_ManObjNum(pIfMan) );
+ Aig_ManForEachObj( p, pObj, i )
+ {
+ pIfObj = (If_Obj_t *)Vec_PtrEntry( vAigToIf, i );
+ Vec_PtrWriteEntry( vIfToAig, pIfObj->Id, pObj );
+ }
+ // construct the network
+ pNtk = Nwk_ManAlloc();
+ pNtk->pName = Abc_UtilStrsav( p->pName );
+ pNtk->pSpec = Abc_UtilStrsav( p->pSpec );
+// pNtk->nLatches = Aig_ManRegNum(p);
+// pNtk->nTruePis = Nwk_ManCiNum(pNtk) - pNtk->nLatches;
+// pNtk->nTruePos = Nwk_ManCoNum(pNtk) - pNtk->nLatches;
+ Aig_ManForEachObj( p, pObj, i )
+ {
+ pIfObj = (If_Obj_t *)Vec_PtrEntry( vAigToIf, i );
+ if ( pIfObj->nRefs == 0 && !If_ObjIsTerm(pIfObj) )
+ continue;
+ if ( Aig_ObjIsNode(pObj) )
+ {
+ pCutBest = If_ObjCutBest( pIfObj );
+ nLeaves = If_CutLeaveNum( pCutBest );
+ ppLeaves = If_CutLeaves( pCutBest );
+ // create node
+ pObjNew = Nwk_ManCreateNode( pNtk, nLeaves, pIfObj->nRefs );
+ for ( k = 0; k < nLeaves; k++ )
+ {
+ pObjRepr = (Aig_Obj_t *)Vec_PtrEntry( vIfToAig, ppLeaves[k] );
+ Nwk_ObjAddFanin( pObjNew, (Nwk_Obj_t *)pObjRepr->pData );
+ }
+ // get the functionality
+ pObjNew->pFunc = Nwk_NodeIfToHop( pNtk->pManHop, pIfMan, pIfObj );
+ }
+ else if ( Aig_ObjIsPi(pObj) )
+ pObjNew = Nwk_ManCreateCi( pNtk, pIfObj->nRefs );
+ else if ( Aig_ObjIsPo(pObj) )
+ {
+ pObjNew = Nwk_ManCreateCo( pNtk );
+ pObjNew->fInvert = Aig_ObjFaninC0(pObj);
+ Nwk_ObjAddFanin( pObjNew, (Nwk_Obj_t *)Aig_ObjFanin0(pObj)->pData );
+//printf( "%d ", pObjNew->Id );
+ }
+ else if ( Aig_ObjIsConst1(pObj) )
+ {
+ pObjNew = Nwk_ManCreateNode( pNtk, 0, pIfObj->nRefs );
+ pObjNew->pFunc = Hop_ManConst1( pNtk->pManHop );
+ }
+ else
+ assert( 0 );
+ pObj->pData = pObjNew;
+ }
+//printf( "\n" );
+ Vec_PtrFree( vIfToAig );
+ pNtk->pManTime = Tim_ManDup( pIfMan->pManTim, 0 );
+ Nwk_ManMinimumBase( pNtk, 0 );
+ assert( Nwk_ManCheck( pNtk ) );
+ return pNtk;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Interface with the FPGA mapping package.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Man_t * Nwk_MappingIf( Aig_Man_t * p, Tim_Man_t * pManTime, If_Par_t * pPars )
+{
+ Nwk_Man_t * pNtk;
+ If_Man_t * pIfMan;
+ Vec_Ptr_t * vAigToIf;
+ // set the arrival times
+ pPars->pTimesArr = ABC_ALLOC( float, Aig_ManPiNum(p) );
+ memset( pPars->pTimesArr, 0, sizeof(float) * Aig_ManPiNum(p) );
+ // translate into the mapper
+ vAigToIf = Vec_PtrStart( Aig_ManObjNumMax(p) );
+ pIfMan = Nwk_ManToIf( p, pPars, vAigToIf );
+ if ( pIfMan == NULL )
+ return NULL;
+ pIfMan->pManTim = Tim_ManDup( pManTime, 0 );
+ pIfMan->pPars->fCutMin = 0; // is not compatible with deriving result
+ if ( !If_ManPerformMapping( pIfMan ) )
+ {
+ If_ManStop( pIfMan );
+ return NULL;
+ }
+ // transform the result of mapping into the new network
+ pNtk = Nwk_ManFromIf( pIfMan, p, vAigToIf );
+ if ( pPars->fBidec && pPars->nLutSize <= 8 )
+ Nwk_ManBidecResyn( pNtk, 0 );
+ If_ManStop( pIfMan );
+ Vec_PtrFree( vAigToIf );
+ return pNtk;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkMerge.c b/src/opt/nwk/nwkMerge.c
new file mode 100644
index 00000000..fa9f7c78
--- /dev/null
+++ b/src/opt/nwk/nwkMerge.c
@@ -0,0 +1,1044 @@
+/**CFile****************************************************************
+
+ FileName [nwkMerge.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis [LUT merging algorithm.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+#include "nwkMerge.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Allocates the graph.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Grf_t * Nwk_ManGraphAlloc( int nVertsMax )
+{
+ Nwk_Grf_t * p;
+ p = ABC_ALLOC( Nwk_Grf_t, 1 );
+ memset( p, 0, sizeof(Nwk_Grf_t) );
+ p->nVertsMax = nVertsMax;
+ p->nEdgeHash = Abc_PrimeCudd( 3 * nVertsMax );
+ p->pEdgeHash = ABC_CALLOC( Nwk_Edg_t *, p->nEdgeHash );
+ p->pMemEdges = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash );
+ p->vPairs = Vec_IntAlloc( 1000 );
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Deallocates the graph.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphFree( Nwk_Grf_t * p )
+{
+ if ( p->vPairs ) Vec_IntFree( p->vPairs );
+ if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 );
+ if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 );
+ ABC_FREE( p->pVerts );
+ ABC_FREE( p->pEdgeHash );
+ ABC_FREE( p->pMapLut2Id );
+ ABC_FREE( p->pMapId2Lut );
+ ABC_FREE( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the graph for solving the problem.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphReportMemoryUsage( Nwk_Grf_t * p )
+{
+ p->nMemBytes1 =
+ sizeof(Nwk_Grf_t) +
+ sizeof(void *) * p->nEdgeHash +
+ sizeof(int) * (p->nObjs + p->nVertsMax) +
+ sizeof(Nwk_Edg_t) * p->nEdges;
+ p->nMemBytes2 =
+ sizeof(Nwk_Vrt_t) * p->nVerts +
+ sizeof(int) * 2 * p->nEdges;
+ printf( "Memory usage stats: Preprocessing = %.2f Mb. Solving = %.2f Mb.\n",
+ 1.0 * p->nMemBytes1 / (1<<20), 1.0 * p->nMemBytes2 / (1<<20) );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Finds or adds the edge to the graph.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 )
+{
+ Nwk_Edg_t * pEntry;
+ unsigned Key;
+ if ( iLut1 == iLut2 )
+ return;
+ if ( iLut1 > iLut2 )
+ {
+ Key = iLut1;
+ iLut1 = iLut2;
+ iLut2 = Key;
+ }
+ assert( iLut1 < iLut2 );
+ if ( p->nObjs < iLut2 )
+ p->nObjs = iLut2;
+ Key = (unsigned)(741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash;
+ for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
+ if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 )
+ return;
+ pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges );
+ pEntry->iNode1 = iLut1;
+ pEntry->iNode2 = iLut2;
+ pEntry->pNext = p->pEdgeHash[Key];
+ p->pEdgeHash[Key] = pEntry;
+ p->nEdges++;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds one entry to the list.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListAdd( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
+{
+ if ( *pList )
+ {
+ Nwk_Vrt_t * pHead;
+ pHead = p->pVerts[*pList];
+ pVertex->iPrev = 0;
+ pVertex->iNext = pHead->Id;
+ pHead->iPrev = pVertex->Id;
+ }
+ *pList = pVertex->Id;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Deletes one entry from the list.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListDelete( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
+{
+ assert( *pList );
+ if ( pVertex->iPrev )
+ {
+// assert( p->pVerts[pVertex->iPrev]->iNext == pVertex->Id );
+ p->pVerts[pVertex->iPrev]->iNext = pVertex->iNext;
+ }
+ if ( pVertex->iNext )
+ {
+// assert( p->pVerts[pVertex->iNext]->iPrev == pVertex->Id );
+ p->pVerts[pVertex->iNext]->iPrev = pVertex->iPrev;
+ }
+ if ( *pList == pVertex->Id )
+ *pList = pVertex->iNext;
+ pVertex->iPrev = pVertex->iNext = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Inserts the edge into one of the linked lists.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListInsert( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
+{
+ Nwk_Vrt_t * pNext;
+ assert( pVertex->nEdges > 0 );
+
+ if ( pVertex->nEdges == 1 )
+ {
+ pNext = p->pVerts[ pVertex->pEdges[0] ];
+ if ( pNext->nEdges >= NWK_MAX_LIST )
+ Nwk_ManGraphListAdd( p, p->pLists1 + NWK_MAX_LIST, pVertex );
+ else
+ Nwk_ManGraphListAdd( p, p->pLists1 + pNext->nEdges, pVertex );
+ }
+ else
+ {
+ if ( pVertex->nEdges >= NWK_MAX_LIST )
+ Nwk_ManGraphListAdd( p, p->pLists2 + NWK_MAX_LIST, pVertex );
+ else
+ Nwk_ManGraphListAdd( p, p->pLists2 + pVertex->nEdges, pVertex );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Extracts the edge from one of the linked lists.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListExtract( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
+{
+ Nwk_Vrt_t * pNext;
+ assert( pVertex->nEdges > 0 );
+
+ if ( pVertex->nEdges == 1 )
+ {
+ pNext = p->pVerts[ pVertex->pEdges[0] ];
+ if ( pNext->nEdges >= NWK_MAX_LIST )
+ Nwk_ManGraphListDelete( p, p->pLists1 + NWK_MAX_LIST, pVertex );
+ else
+ Nwk_ManGraphListDelete( p, p->pLists1 + pNext->nEdges, pVertex );
+ }
+ else
+ {
+ if ( pVertex->nEdges >= NWK_MAX_LIST )
+ Nwk_ManGraphListDelete( p, p->pLists2 + NWK_MAX_LIST, pVertex );
+ else
+ Nwk_ManGraphListDelete( p, p->pLists2 + pVertex->nEdges, pVertex );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the graph for solving the problem.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphPrepare( Nwk_Grf_t * p )
+{
+ Nwk_Edg_t * pEntry;
+ Nwk_Vrt_t * pVertex;
+ int * pnEdges, nBytes, i;
+ // allocate memory for the present objects
+ p->pMapLut2Id = ABC_ALLOC( int, p->nObjs+1 );
+ p->pMapId2Lut = ABC_ALLOC( int, p->nVertsMax+1 );
+ memset( p->pMapLut2Id, 0xff, sizeof(int) * (p->nObjs+1) );
+ memset( p->pMapId2Lut, 0xff, sizeof(int) * (p->nVertsMax+1) );
+ // mark present objects
+ Nwk_GraphForEachEdge( p, pEntry, i )
+ {
+ assert( pEntry->iNode1 <= p->nObjs );
+ assert( pEntry->iNode2 <= p->nObjs );
+ p->pMapLut2Id[ pEntry->iNode1 ] = 0;
+ p->pMapLut2Id[ pEntry->iNode2 ] = 0;
+ }
+ // map objects
+ p->nVerts = 0;
+ for ( i = 0; i <= p->nObjs; i++ )
+ {
+ if ( p->pMapLut2Id[i] == 0 )
+ {
+ p->pMapLut2Id[i] = ++p->nVerts;
+ p->pMapId2Lut[p->nVerts] = i;
+ }
+ }
+ // count the edges and mark present objects
+ pnEdges = ABC_CALLOC( int, p->nVerts+1 );
+ Nwk_GraphForEachEdge( p, pEntry, i )
+ {
+ // translate into vertices
+ assert( pEntry->iNode1 <= p->nObjs );
+ assert( pEntry->iNode2 <= p->nObjs );
+ pEntry->iNode1 = p->pMapLut2Id[pEntry->iNode1];
+ pEntry->iNode2 = p->pMapLut2Id[pEntry->iNode2];
+ // count the edges
+ assert( pEntry->iNode1 <= p->nVerts );
+ assert( pEntry->iNode2 <= p->nVerts );
+ pnEdges[pEntry->iNode1]++;
+ pnEdges[pEntry->iNode2]++;
+ }
+ // allocate the real graph
+ p->pMemVerts = Aig_MmFlexStart();
+ p->pVerts = ABC_ALLOC( Nwk_Vrt_t *, p->nVerts + 1 );
+ p->pVerts[0] = NULL;
+ for ( i = 1; i <= p->nVerts; i++ )
+ {
+ assert( pnEdges[i] > 0 );
+ nBytes = sizeof(Nwk_Vrt_t) + sizeof(int) * pnEdges[i];
+ p->pVerts[i] = (Nwk_Vrt_t *)Aig_MmFlexEntryFetch( p->pMemVerts, nBytes );
+ memset( p->pVerts[i], 0, nBytes );
+ p->pVerts[i]->Id = i;
+ }
+ // add edges to the real graph
+ Nwk_GraphForEachEdge( p, pEntry, i )
+ {
+ pVertex = p->pVerts[pEntry->iNode1];
+ pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode2;
+ pVertex = p->pVerts[pEntry->iNode2];
+ pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode1;
+ }
+ // put vertices into the data structure
+ for ( i = 1; i <= p->nVerts; i++ )
+ {
+ assert( p->pVerts[i]->nEdges == pnEdges[i] );
+ Nwk_ManGraphListInsert( p, p->pVerts[i] );
+ }
+ // clean up
+ Aig_MmFixedStop( p->pMemEdges, 0 ); p->pMemEdges = NULL;
+ ABC_FREE( p->pEdgeHash );
+// p->nEdgeHash = 0;
+ ABC_FREE( pnEdges );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sort pairs by the first vertex in the topological order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphSortPairs( Nwk_Grf_t * p )
+{
+ int nSize = Vec_IntSize(p->vPairs);
+ int * pIdToPair, i;
+ // allocate storage
+ pIdToPair = ABC_ALLOC( int, p->nObjs+1 );
+ for ( i = 0; i <= p->nObjs; i++ )
+ pIdToPair[i] = -1;
+ // create mapping
+ for ( i = 0; i < p->vPairs->nSize; i += 2 )
+ {
+ assert( pIdToPair[ p->vPairs->pArray[i] ] == -1 );
+ pIdToPair[ p->vPairs->pArray[i] ] = p->vPairs->pArray[i+1];
+ }
+ // recreate pairs
+ Vec_IntClear( p->vPairs );
+ for ( i = 0; i <= p->nObjs; i++ )
+ if ( pIdToPair[i] >= 0 )
+ {
+ assert( i < pIdToPair[i] );
+ Vec_IntPush( p->vPairs, i );
+ Vec_IntPush( p->vPairs, pIdToPair[i] );
+ }
+ assert( nSize == Vec_IntSize(p->vPairs) );
+ ABC_FREE( pIdToPair );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Updates the problem after pulling out one edge.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphCheckLists( Nwk_Grf_t * p )
+{
+ Nwk_Vrt_t * pVertex, * pNext;
+ int i, j;
+ assert( p->pLists1[0] == 0 );
+ for ( i = 1; i <= NWK_MAX_LIST; i++ )
+ if ( p->pLists1[i] )
+ {
+ pVertex = p->pVerts[ p->pLists1[i] ];
+ assert( pVertex->nEdges == 1 );
+ pNext = p->pVerts[ pVertex->pEdges[0] ];
+ assert( pNext->nEdges == i || pNext->nEdges > NWK_MAX_LIST );
+ }
+ // find the next vertext to extract
+ assert( p->pLists2[0] == 0 );
+ assert( p->pLists2[1] == 0 );
+ for ( j = 2; j <= NWK_MAX_LIST; j++ )
+ if ( p->pLists2[j] )
+ {
+ pVertex = p->pVerts[ p->pLists2[j] ];
+ assert( pVertex->nEdges == j || pVertex->nEdges > NWK_MAX_LIST );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Extracts the edge from one of the linked lists.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline void Nwk_ManGraphVertexRemoveEdge( Nwk_Vrt_t * pThis, Nwk_Vrt_t * pNext )
+{
+ int k;
+ for ( k = 0; k < pThis->nEdges; k++ )
+ if ( pThis->pEdges[k] == pNext->Id )
+ break;
+ assert( k < pThis->nEdges );
+ pThis->nEdges--;
+ for ( ; k < pThis->nEdges; k++ )
+ pThis->pEdges[k] = pThis->pEdges[k+1];
+}
+
+/**Function*************************************************************
+
+ Synopsis [Updates the problem after pulling out one edge.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphUpdate( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex, Nwk_Vrt_t * pNext )
+{
+ Nwk_Vrt_t * pChanged, * pOther;
+ int i, k;
+// Nwk_ManGraphCheckLists( p );
+ Nwk_ManGraphListExtract( p, pVertex );
+ Nwk_ManGraphListExtract( p, pNext );
+ // update neihbors of pVertex
+ Nwk_VertexForEachAdjacent( p, pVertex, pChanged, i )
+ {
+ if ( pChanged == pNext )
+ continue;
+ Nwk_ManGraphListExtract( p, pChanged );
+ // move those that use this one
+ if ( pChanged->nEdges > 1 )
+ Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
+ {
+ if ( pOther == pVertex || pOther->nEdges > 1 )
+ continue;
+ assert( pOther->nEdges == 1 );
+ Nwk_ManGraphListExtract( p, pOther );
+ pChanged->nEdges--;
+ Nwk_ManGraphListInsert( p, pOther );
+ pChanged->nEdges++;
+ }
+ // remove the edge
+ Nwk_ManGraphVertexRemoveEdge( pChanged, pVertex );
+ // add the changed vertex back
+ if ( pChanged->nEdges > 0 )
+ Nwk_ManGraphListInsert( p, pChanged );
+ }
+ // update neihbors of pNext
+ Nwk_VertexForEachAdjacent( p, pNext, pChanged, i )
+ {
+ if ( pChanged == pVertex )
+ continue;
+ Nwk_ManGraphListExtract( p, pChanged );
+ // move those that use this one
+ if ( pChanged->nEdges > 1 )
+ Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
+ {
+ if ( pOther == pNext || pOther->nEdges > 1 )
+ continue;
+ assert( pOther->nEdges == 1 );
+ Nwk_ManGraphListExtract( p, pOther );
+ pChanged->nEdges--;
+ Nwk_ManGraphListInsert( p, pOther );
+ pChanged->nEdges++;
+ }
+ // remove the edge
+ Nwk_ManGraphVertexRemoveEdge( pChanged, pNext );
+ // add the changed vertex back
+ if ( pChanged->nEdges > 0 )
+ Nwk_ManGraphListInsert( p, pChanged );
+ }
+ // add to the result
+ if ( pVertex->Id < pNext->Id )
+ {
+ Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
+ Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
+ }
+ else
+ {
+ Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
+ Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
+ }
+// Nwk_ManGraphCheckLists( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of entries in the list.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManGraphListLength( Nwk_Grf_t * p, int List )
+{
+ Nwk_Vrt_t * pThis;
+ int fVerbose = 0;
+ int Counter = 0;
+ Nwk_ListForEachVertex( p, List, pThis )
+ {
+ if ( fVerbose && Counter < 20 )
+ printf( "%d ", p->pVerts[pThis->pEdges[0]]->nEdges );
+ Counter++;
+ }
+ if ( fVerbose )
+ printf( "\n" );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the adjacent vertex with the mininum number of edges.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Vrt_t * Nwk_ManGraphListFindMinEdge( Nwk_Grf_t * p, Nwk_Vrt_t * pVert )
+{
+ Nwk_Vrt_t * pThis, * pMinCost = NULL;
+ int k;
+ Nwk_VertexForEachAdjacent( p, pVert, pThis, k )
+ {
+ if ( pMinCost == NULL || pMinCost->nEdges > pThis->nEdges )
+ pMinCost = pThis;
+ }
+ return pMinCost;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Finds the best vertext in the list.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Vrt_t * Nwk_ManGraphListFindMin( Nwk_Grf_t * p, int List )
+{
+ Nwk_Vrt_t * pThis, * pMinCost = NULL;
+ int k, Counter = 10000, BestCost = 1000000;
+ Nwk_ListForEachVertex( p, List, pThis )
+ {
+ for ( k = 0; k < pThis->nEdges; k++ )
+ {
+ if ( pMinCost == NULL || BestCost > p->pVerts[pThis->pEdges[k]]->nEdges )
+ {
+ BestCost = p->pVerts[pThis->pEdges[k]]->nEdges;
+ pMinCost = pThis;
+ }
+ }
+ if ( --Counter == 0 )
+ break;
+ }
+ return pMinCost;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Solves the problem by extracting one edge at a time.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManGraphSolve( Nwk_Grf_t * p )
+{
+ Nwk_Vrt_t * pVertex, * pNext;
+ int i, j;
+ Nwk_ManGraphPrepare( p );
+ while ( 1 )
+ {
+ // find the next vertex to extract
+ assert( p->pLists1[0] == 0 );
+ for ( i = 1; i <= NWK_MAX_LIST; i++ )
+ if ( p->pLists1[i] )
+ {
+// printf( "%d ", i );
+// printf( "ListA = %2d. Length = %5d.\n", i, Nwk_ManGraphListLength(p,p->pLists1[i]) );
+ pVertex = p->pVerts[ p->pLists1[i] ];
+ assert( pVertex->nEdges == 1 );
+ pNext = p->pVerts[ pVertex->pEdges[0] ];
+ Nwk_ManGraphUpdate( p, pVertex, pNext );
+ break;
+ }
+ if ( i < NWK_MAX_LIST + 1 )
+ continue;
+ // find the next vertex to extract
+ assert( p->pLists2[0] == 0 );
+ assert( p->pLists2[1] == 0 );
+ for ( j = 2; j <= NWK_MAX_LIST; j++ )
+ if ( p->pLists2[j] )
+ {
+// printf( "***%d ", j );
+// printf( "ListB = %2d. Length = %5d.\n", j, Nwk_ManGraphListLength(p,p->pLists2[j]) );
+ pVertex = Nwk_ManGraphListFindMin( p, p->pLists2[j] );
+ assert( pVertex->nEdges == j || j == NWK_MAX_LIST );
+ pNext = Nwk_ManGraphListFindMinEdge( p, pVertex );
+ Nwk_ManGraphUpdate( p, pVertex, pNext );
+ break;
+ }
+ if ( j == NWK_MAX_LIST + 1 )
+ break;
+ }
+ Nwk_ManGraphSortPairs( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Reads graph from file.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Grf_t * Nwk_ManLutMergeReadGraph( char * pFileName )
+{
+ Nwk_Grf_t * p;
+ FILE * pFile;
+ char Buffer[100];
+ int nNodes, nEdges, iNode1, iNode2;
+ pFile = fopen( pFileName, "r" );
+ fscanf( pFile, "%s %d", Buffer, &nNodes );
+ fscanf( pFile, "%s %d", Buffer, &nEdges );
+ p = Nwk_ManGraphAlloc( nNodes );
+ while ( fscanf( pFile, "%s %d %d", Buffer, &iNode1, &iNode2 ) == 3 )
+ Nwk_ManGraphHashEdge( p, iNode1, iNode2 );
+ assert( p->nEdges == nEdges );
+ fclose( pFile );
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Solves the graph coming from file.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManLutMergeGraphTest( char * pFileName )
+{
+ int nPairs;
+ Nwk_Grf_t * p;
+ int clk = clock();
+ p = Nwk_ManLutMergeReadGraph( pFileName );
+ ABC_PRT( "Reading", clock() - clk );
+ clk = clock();
+ Nwk_ManGraphSolve( p );
+ printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
+ p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
+ ABC_PRT( "Solving", clock() - clk );
+ nPairs = Vec_IntSize(p->vPairs)/2;
+ Nwk_ManGraphReportMemoryUsage( p );
+ Nwk_ManGraphFree( p );
+ return nPairs;
+}
+
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Marks the fanins of the node with the current trav ID.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkFanins_rec( Nwk_Obj_t * pLut, int nLevMin )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( !Nwk_ObjIsNode(pLut) )
+ return;
+ if ( Nwk_ObjIsTravIdCurrent( pLut ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pLut );
+ if ( Nwk_ObjLevel(pLut) < nLevMin )
+ return;
+ Nwk_ObjForEachFanin( pLut, pNext, i )
+ Nwk_ManMarkFanins_rec( pNext, nLevMin );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Marks the fanouts of the node with the current trav ID.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMarkFanouts_rec( Nwk_Obj_t * pLut, int nLevMax, int nFanMax )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ if ( !Nwk_ObjIsNode(pLut) )
+ return;
+ if ( Nwk_ObjIsTravIdCurrent( pLut ) )
+ return;
+ Nwk_ObjSetTravIdCurrent( pLut );
+ if ( Nwk_ObjLevel(pLut) > nLevMax )
+ return;
+ if ( Nwk_ObjFanoutNum(pLut) > nFanMax )
+ return;
+ Nwk_ObjForEachFanout( pLut, pNext, i )
+ Nwk_ManMarkFanouts_rec( pNext, nLevMax, nFanMax );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects the circle of nodes around the given set.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax )
+{
+ Nwk_Obj_t * pObj, * pNext;
+ int i, k;
+ Vec_PtrClear( vNext );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, i )
+ {
+ Nwk_ObjForEachFanin( pObj, pNext, k )
+ {
+ if ( !Nwk_ObjIsNode(pNext) )
+ continue;
+ if ( Nwk_ObjIsTravIdCurrent( pNext ) )
+ continue;
+ Nwk_ObjSetTravIdCurrent( pNext );
+ Vec_PtrPush( vNext, pNext );
+ }
+ Nwk_ObjForEachFanout( pObj, pNext, k )
+ {
+ if ( !Nwk_ObjIsNode(pNext) )
+ continue;
+ if ( Nwk_ObjIsTravIdCurrent( pNext ) )
+ continue;
+ Nwk_ObjSetTravIdCurrent( pNext );
+ if ( Nwk_ObjFanoutNum(pNext) > nFanMax )
+ continue;
+ Vec_PtrPush( vNext, pNext );
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects the circle of nodes removes from the given one.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManCollectNonOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
+{
+ Vec_Ptr_t * vTemp;
+ Nwk_Obj_t * pObj;
+ int i, k;
+ Vec_PtrClear( vCands );
+ if ( pPars->nMaxSuppSize - Nwk_ObjFaninNum(pLut) <= 1 )
+ return;
+
+ // collect nodes removed by this distance
+ assert( pPars->nMaxDistance > 0 );
+ Vec_PtrClear( vStart );
+ Vec_PtrPush( vStart, pLut );
+ Nwk_ManIncrementTravId( pLut->pMan );
+ Nwk_ObjSetTravIdCurrent( pLut );
+ for ( i = 1; i <= pPars->nMaxDistance; i++ )
+ {
+ Nwk_ManCollectCircle( vStart, vNext, pPars->nMaxFanout );
+ vTemp = vStart;
+ vStart = vNext;
+ vNext = vTemp;
+ // collect the nodes in vStart
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, k )
+ Vec_PtrPush( vCands, pObj );
+ }
+
+ // mark the TFI/TFO nodes
+ Nwk_ManIncrementTravId( pLut->pMan );
+ if ( pPars->fUseTfiTfo )
+ Nwk_ObjSetTravIdCurrent( pLut );
+ else
+ {
+ Nwk_ObjSetTravIdPrevious( pLut );
+ Nwk_ManMarkFanins_rec( pLut, Nwk_ObjLevel(pLut) - pPars->nMaxDistance );
+ Nwk_ObjSetTravIdPrevious( pLut );
+ Nwk_ManMarkFanouts_rec( pLut, Nwk_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout );
+ }
+
+ // collect nodes satisfying the following conditions:
+ // - they are close enough in terms of distance
+ // - they are not in the TFI/TFO of the LUT
+ // - they have no more than the given number of fanins
+ // - they have no more than the given diff in delay
+ k = 0;
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vCands, pObj, i )
+ {
+ if ( Nwk_ObjIsTravIdCurrent(pObj) )
+ continue;
+ if ( Nwk_ObjFaninNum(pLut) + Nwk_ObjFaninNum(pObj) > pPars->nMaxSuppSize )
+ continue;
+ if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
+ Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
+ continue;
+ Vec_PtrWriteEntry( vCands, k++, pObj );
+ }
+ Vec_PtrShrink( vCands, k );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Count the total number of fanins.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManCountTotalFanins( Nwk_Obj_t * pLut, Nwk_Obj_t * pCand )
+{
+ Nwk_Obj_t * pFanin;
+ int i, nCounter = Nwk_ObjFaninNum(pLut);
+ Nwk_ObjForEachFanin( pCand, pFanin, i )
+ nCounter += !pFanin->MarkC;
+ return nCounter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects overlapping candidates.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManCollectOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
+{
+ Nwk_Obj_t * pFanin, * pObj;
+ int i, k;
+ // mark fanins of pLut
+ Nwk_ObjForEachFanin( pLut, pFanin, i )
+ pFanin->MarkC = 1;
+ // collect the matching fanouts of each fanin of the node
+ Vec_PtrClear( vCands );
+ Nwk_ManIncrementTravId( pLut->pMan );
+ Nwk_ObjSetTravIdCurrent( pLut );
+ Nwk_ObjForEachFanin( pLut, pFanin, i )
+ {
+ if ( !Nwk_ObjIsNode(pFanin) )
+ continue;
+ if ( Nwk_ObjFanoutNum(pFanin) > pPars->nMaxFanout )
+ continue;
+ Nwk_ObjForEachFanout( pFanin, pObj, k )
+ {
+ if ( !Nwk_ObjIsNode(pObj) )
+ continue;
+ if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+ continue;
+ Nwk_ObjSetTravIdCurrent( pObj );
+ // check the difference in delay
+ if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
+ Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
+ continue;
+ // check the total number of fanins of the node
+ if ( Nwk_ManCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize )
+ continue;
+ Vec_PtrPush( vCands, pObj );
+ }
+ }
+ // unmark fanins of pLut
+ Nwk_ObjForEachFanin( pLut, pFanin, i )
+ pFanin->MarkC = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs LUT merging with parameters.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * pNtk, void * pParsInit )
+{
+ Nwk_LMPars_t * pPars = (Nwk_LMPars_t *)pParsInit;
+ Nwk_Grf_t * p;
+ Vec_Int_t * vResult;
+ Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2;
+ Nwk_Obj_t * pLut, * pCand;
+ int i, k, nVertsMax, nCands, clk = clock();
+ // count the number of vertices
+ nVertsMax = 0;
+ Nwk_ManForEachNode( pNtk, pLut, i )
+ nVertsMax += (int)(Nwk_ObjFaninNum(pLut) <= pPars->nMaxLutSize);
+ p = Nwk_ManGraphAlloc( nVertsMax );
+ // create graph
+ vStart = Vec_PtrAlloc( 1000 );
+ vNext = Vec_PtrAlloc( 1000 );
+ vCands1 = Vec_PtrAlloc( 1000 );
+ vCands2 = Vec_PtrAlloc( 1000 );
+ nCands = 0;
+ Nwk_ManForEachNode( pNtk, pLut, i )
+ {
+ if ( Nwk_ObjFaninNum(pLut) > pPars->nMaxLutSize )
+ continue;
+ Nwk_ManCollectOverlapCands( pLut, vCands1, pPars );
+ if ( pPars->fUseDiffSupp )
+ Nwk_ManCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars );
+ if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 )
+ continue;
+ nCands += Vec_PtrSize(vCands1) + Vec_PtrSize(vCands2);
+ // save candidates
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vCands1, pCand, k )
+ Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vCands2, pCand, k )
+ Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
+ // print statistics about this node
+ if ( pPars->fVeryVerbose )
+ printf( "Node %6d : Fanins = %d. Fanouts = %3d. Cand1 = %3d. Cand2 = %3d.\n",
+ Nwk_ObjId(pLut), Nwk_ObjFaninNum(pLut), Nwk_ObjFaninNum(pLut),
+ Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) );
+ }
+ Vec_PtrFree( vStart );
+ Vec_PtrFree( vNext );
+ Vec_PtrFree( vCands1 );
+ Vec_PtrFree( vCands2 );
+ if ( pPars->fVerbose )
+ {
+ printf( "Mergable LUTs = %6d. Total cands = %6d. ", p->nVertsMax, nCands );
+ ABC_PRT( "Deriving graph", clock() - clk );
+ }
+ // solve the graph problem
+ clk = clock();
+ Nwk_ManGraphSolve( p );
+ if ( pPars->fVerbose )
+ {
+ printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
+ p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
+ ABC_PRT( "Solving", clock() - clk );
+ Nwk_ManGraphReportMemoryUsage( p );
+ }
+ vResult = p->vPairs; p->vPairs = NULL;
+/*
+ for ( i = 0; i < vResult->nSize; i += 2 )
+ printf( "(%d,%d) ", vResult->pArray[i], vResult->pArray[i+1] );
+ printf( "\n" );
+*/
+ Nwk_ManGraphFree( p );
+ return vResult;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkMerge.h b/src/opt/nwk/nwkMerge.h
new file mode 100644
index 00000000..f6be760f
--- /dev/null
+++ b/src/opt/nwk/nwkMerge.h
@@ -0,0 +1,153 @@
+/**CFile****************************************************************
+
+ FileName [nwkMerge.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [External declarations.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkMerge.h,v 1.1 2008/05/14 22:13:09 wudenni Exp $]
+
+***********************************************************************/
+
+#ifndef __NWK_MERGE_H__
+#define __NWK_MERGE_H__
+
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+
+
+ABC_NAMESPACE_HEADER_START
+
+
+#define NWK_MAX_LIST 16
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+// the LUT merging parameters
+typedef struct Nwk_LMPars_t_ Nwk_LMPars_t;
+struct Nwk_LMPars_t_
+{
+ int nMaxLutSize; // the max LUT size for merging (N=5)
+ int nMaxSuppSize; // the max total support size after merging (S=5)
+ int nMaxDistance; // the max number of nodes separating LUTs
+ int nMaxLevelDiff; // the max difference in levels
+ int nMaxFanout; // the max number of fanouts to traverse
+ int fUseDiffSupp; // enables the use of nodes with different support
+ int fUseTfiTfo; // enables the use of TFO/TFO nodes as candidates
+ int fVeryVerbose; // enables additional verbose output
+ int fVerbose; // enables verbose output
+};
+
+// edge of the graph
+typedef struct Nwk_Edg_t_ Nwk_Edg_t;
+struct Nwk_Edg_t_
+{
+ int iNode1; // the first node
+ int iNode2; // the second node
+ Nwk_Edg_t * pNext; // the next edge
+};
+
+// vertex of the graph
+typedef struct Nwk_Vrt_t_ Nwk_Vrt_t;
+struct Nwk_Vrt_t_
+{
+ int Id; // the vertex number
+ int iPrev; // the previous vertex in the list
+ int iNext; // the next vertex in the list
+ int nEdges; // the number of edges
+ int pEdges[0]; // the array of edges
+};
+
+// the connectivity graph
+typedef struct Nwk_Grf_t_ Nwk_Grf_t;
+struct Nwk_Grf_t_
+{
+ // preliminary graph representation
+ int nObjs; // the number of objects
+ int nVertsMax; // the upper bound on the number of vertices
+ int nEdgeHash; // an approximate number of edges
+ Nwk_Edg_t ** pEdgeHash; // hash table for edges
+ Aig_MmFixed_t * pMemEdges; // memory for edges
+ // graph representation
+ int nEdges; // the number of edges
+ int nVerts; // the number of vertices
+ Nwk_Vrt_t ** pVerts; // the array of vertices
+ Aig_MmFlex_t * pMemVerts; // memory for vertices
+ // intermediate data
+ int pLists1[NWK_MAX_LIST+1]; // lists of nodes with one edge
+ int pLists2[NWK_MAX_LIST+1]; // lists of nodes with more than one edge
+ // the results of matching
+ Vec_Int_t * vPairs; // pairs matched in the graph
+ // object mappings
+ int * pMapLut2Id; // LUT numbers into vertex IDs
+ int * pMapId2Lut; // vertex IDs into LUT numbers
+ // other things
+ int nMemBytes1; // memory usage in bytes
+ int nMemBytes2; // memory usage in bytes
+};
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+#define Nwk_GraphForEachEdge( p, pEdge, k ) \
+ for ( k = 0; k < p->nEdgeHash; k++ ) \
+ for ( pEdge = p->pEdgeHash[k]; pEdge; pEdge = pEdge->pNext )
+
+#define Nwk_ListForEachVertex( p, List, pVrt ) \
+ for ( pVrt = List? p->pVerts[List] : NULL; pVrt; \
+ pVrt = pVrt->iNext? p->pVerts[pVrt->iNext] : NULL )
+
+#define Nwk_VertexForEachAdjacent( p, pVrt, pNext, k ) \
+ for ( k = 0; (k < pVrt->nEdges) && (((pNext) = p->pVerts[pVrt->pEdges[k]]), 1); k++ )
+
+////////////////////////////////////////////////////////////////////////
+/// INLINED FUNCTIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// ITERATORS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/*=== nwkMerge.c ==========================================================*/
+extern ABC_DLL Nwk_Grf_t * Nwk_ManGraphAlloc( int nVertsMax );
+extern ABC_DLL void Nwk_ManGraphFree( Nwk_Grf_t * p );
+extern ABC_DLL void Nwk_ManGraphReportMemoryUsage( Nwk_Grf_t * p );
+extern ABC_DLL void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 );
+extern ABC_DLL void Nwk_ManGraphSolve( Nwk_Grf_t * p );
+extern ABC_DLL int Nwk_ManLutMergeGraphTest( char * pFileName );
+
+
+
+ABC_NAMESPACE_HEADER_END
+
+
+
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
diff --git a/src/opt/nwk/nwkObj.c b/src/opt/nwk/nwkObj.c
new file mode 100644
index 00000000..e5930087
--- /dev/null
+++ b/src/opt/nwk/nwkObj.c
@@ -0,0 +1,204 @@
+/**CFile****************************************************************
+
+ FileName [nwkObj.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Manipulation of objects.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkObj.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Creates an object.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Obj_t * Nwk_ManCreateObj( Nwk_Man_t * p, int nFanins, int nFanouts )
+{
+ Nwk_Obj_t * pObj;
+ pObj = (Nwk_Obj_t *)Aig_MmFlexEntryFetch( p->pMemObjs, sizeof(Nwk_Obj_t) + (nFanins + nFanouts + p->nFanioPlus) * sizeof(Nwk_Obj_t *) );
+ memset( pObj, 0, sizeof(Nwk_Obj_t) );
+ pObj->pFanio = (Nwk_Obj_t **)((char *)pObj + sizeof(Nwk_Obj_t));
+ pObj->Id = Vec_PtrSize( p->vObjs );
+ Vec_PtrPush( p->vObjs, pObj );
+ pObj->pMan = p;
+ pObj->nFanioAlloc = nFanins + nFanouts + p->nFanioPlus;
+ return pObj;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Creates a primary input.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Obj_t * Nwk_ManCreateCi( Nwk_Man_t * p, int nFanouts )
+{
+ Nwk_Obj_t * pObj;
+ pObj = Nwk_ManCreateObj( p, 1, nFanouts );
+ pObj->PioId = Vec_PtrSize( p->vCis );
+ Vec_PtrPush( p->vCis, pObj );
+ pObj->Type = NWK_OBJ_CI;
+ p->nObjs[NWK_OBJ_CI]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates a primary output.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Obj_t * Nwk_ManCreateCo( Nwk_Man_t * p )
+{
+ Nwk_Obj_t * pObj;
+ pObj = Nwk_ManCreateObj( p, 1, 1 );
+ pObj->PioId = Vec_PtrSize( p->vCos );
+ Vec_PtrPush( p->vCos, pObj );
+ pObj->Type = NWK_OBJ_CO;
+ p->nObjs[NWK_OBJ_CO]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates a latch.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Obj_t * Nwk_ManCreateLatch( Nwk_Man_t * p )
+{
+ Nwk_Obj_t * pObj;
+ pObj = Nwk_ManCreateObj( p, 1, 1 );
+ pObj->Type = NWK_OBJ_LATCH;
+ p->nObjs[NWK_OBJ_LATCH]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates a node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Nwk_Obj_t * Nwk_ManCreateNode( Nwk_Man_t * p, int nFanins, int nFanouts )
+{
+ Nwk_Obj_t * pObj;
+ pObj = Nwk_ManCreateObj( p, nFanins, nFanouts );
+ pObj->Type = NWK_OBJ_NODE;
+ p->nObjs[NWK_OBJ_NODE]++;
+ return pObj;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Deletes the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDeleteNode( Nwk_Obj_t * pObj )
+{
+ Vec_Ptr_t * vNodes = pObj->pMan->vTemp;
+ Nwk_Obj_t * pTemp;
+ int i;
+ assert( Nwk_ObjFanoutNum(pObj) == 0 );
+ // delete fanins
+ Nwk_ObjCollectFanins( pObj, vNodes );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pTemp, i )
+ Nwk_ObjDeleteFanin( pObj, pTemp );
+ // remove from the list of objects
+ Vec_PtrWriteEntry( pObj->pMan->vObjs, pObj->Id, NULL );
+ pObj->pMan->nObjs[pObj->Type]--;
+ memset( pObj, 0, sizeof(Nwk_Obj_t) );
+ pObj->Id = -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Deletes the node and MFFC of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDeleteNode_rec( Nwk_Obj_t * pObj )
+{
+ Vec_Ptr_t * vNodes;
+ int i;
+ assert( !Nwk_ObjIsCi(pObj) );
+ assert( Nwk_ObjFanoutNum(pObj) == 0 );
+ vNodes = Vec_PtrAlloc( 100 );
+ Nwk_ObjCollectFanins( pObj, vNodes );
+ Nwk_ManDeleteNode( pObj );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ if ( Nwk_ObjIsNode(pObj) && Nwk_ObjFanoutNum(pObj) == 0 )
+ Nwk_ManDeleteNode_rec( pObj );
+ Vec_PtrFree( vNodes );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkSpeedup.c b/src/opt/nwk/nwkSpeedup.c
new file mode 100644
index 00000000..335d50f8
--- /dev/null
+++ b/src/opt/nwk/nwkSpeedup.c
@@ -0,0 +1,382 @@
+/**CFile****************************************************************
+
+ FileName [nwkSpeedup.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis [Global delay optimization using structural choices.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Adds strashed nodes for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Aig_ManSpeedupNode_rec( Aig_Man_t * pAig, Aig_Obj_t * pNode, Vec_Ptr_t * vNodes )
+{
+ if ( Aig_ObjIsTravIdCurrent(pAig, pNode) )
+ return 1;
+ if ( Aig_ObjIsPi(pNode) )
+ return 0;
+ assert( Aig_ObjIsNode(pNode) );
+ Aig_ObjSetTravIdCurrent( pAig, pNode );
+ if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin0(pNode), vNodes ) )
+ return 0;
+ if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin1(pNode), vNodes ) )
+ return 0;
+ Vec_PtrPush( vNodes, pNode );
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds strashed nodes for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Aig_ManSpeedupNode( Nwk_Man_t * pNtk, Aig_Man_t * pAig, Nwk_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes )
+{
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj, * pObj2;
+ Aig_Obj_t * ppCofs[32], * pAnd, * pTemp;
+ int nCofs, i, k, nSkip;
+
+ // quit of regulars are the same
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i )
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj2, k )
+ if ( i != k && Aig_Regular((Aig_Obj_t *)pObj->pCopy) == Aig_Regular((Aig_Obj_t *)pObj2->pCopy) )
+ {
+// printf( "Identical after structural hashing!!!\n" );
+ return;
+ }
+
+ // collect the AIG nodes
+ vNodes = Vec_PtrAlloc( 100 );
+ Aig_ManIncrementTravId( pAig );
+ Aig_ObjSetTravIdCurrent( pAig, Aig_ManConst1(pAig) );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, i )
+ {
+ pAnd = (Aig_Obj_t *)pObj->pCopy;
+ Aig_ObjSetTravIdCurrent( pAig, Aig_Regular(pAnd) );
+ }
+ // traverse from the root node
+ pAnd = (Aig_Obj_t *)pNode->pCopy;
+ if ( !Aig_ManSpeedupNode_rec( pAig, Aig_Regular(pAnd), vNodes ) )
+ {
+// printf( "Bad node!!!\n" );
+ Vec_PtrFree( vNodes );
+ return;
+ }
+
+ // derive cofactors
+ nCofs = (1 << Vec_PtrSize(vTimes));
+ for ( i = 0; i < nCofs; i++ )
+ {
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vLeaves, pObj, k )
+ {
+ pAnd = (Aig_Obj_t *)pObj->pCopy;
+ Aig_Regular(pAnd)->pData = Aig_Regular(pAnd);
+ }
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k )
+ {
+ pAnd = (Aig_Obj_t *)pObj->pCopy;
+ Aig_Regular(pAnd)->pData = Aig_NotCond( Aig_ManConst1(pAig), ((i & (1<<k)) == 0) );
+ }
+ Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pTemp, k )
+ pTemp->pData = Aig_And( pAig, Aig_ObjChild0Copy(pTemp), Aig_ObjChild1Copy(pTemp) );
+ // save the result
+ pAnd = (Aig_Obj_t *)pNode->pCopy;
+ ppCofs[i] = Aig_NotCond( (Aig_Obj_t *)Aig_Regular(pAnd)->pData, Aig_IsComplement(pAnd) );
+ }
+ Vec_PtrFree( vNodes );
+
+//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] );
+//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[1] );
+
+ // collect the resulting tree
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vTimes, pObj, k )
+ for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
+ {
+ pAnd = (Aig_Obj_t *)pObj->pCopy;
+ ppCofs[i] = Aig_Mux( pAig, Aig_Regular(pAnd), ppCofs[i+nSkip], ppCofs[i] );
+ }
+//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] );
+
+ // create choice node
+ pAnd = Aig_Regular((Aig_Obj_t *)pNode->pCopy); // repr
+ pTemp = Aig_Regular(ppCofs[0]); // new
+ if ( Aig_ObjEquiv(pAig, pAnd) == NULL && Aig_ObjEquiv(pAig, pTemp) == NULL && !Aig_ObjCheckTfi(pAig, pTemp, pAnd) )
+ pAig->pEquivs[pAnd->Id] = pTemp;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Determines timing-critical edges of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+unsigned Nwk_ManDelayTraceTCEdges( Nwk_Man_t * pNtk, Nwk_Obj_t * pNode, float tDelta, int fUseLutLib )
+{
+ int pPinPerm[32];
+ float pPinDelays[32];
+ If_Lib_t * pLutLib = fUseLutLib? pNtk->pLutLib : NULL;
+ Nwk_Obj_t * pFanin;
+ unsigned uResult = 0;
+ float tRequired, * pDelays;
+ int k;
+ tRequired = Nwk_ObjRequired(pNode);
+ if ( pLutLib == NULL )
+ {
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( tRequired < Nwk_ObjArrival(pFanin) + 1.0 + tDelta )
+ uResult |= (1 << k);
+ }
+ else if ( !pLutLib->fVarPinDelays )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)];
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( tRequired < Nwk_ObjArrival(pFanin) + pDelays[0] + tDelta )
+ uResult |= (1 << k);
+ }
+ else
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)];
+ Nwk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( tRequired < Nwk_ObjArrival(Nwk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
+ uResult |= (1 << pPinPerm[k]);
+ }
+ return uResult;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds choices to speed up the network by the given percentage.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
+{
+ Aig_Man_t * pAig, * pTemp;
+ Vec_Ptr_t * vTimeCries, * vTimeFanins;
+ Nwk_Obj_t * pNode, * pFanin, * pFanin2;
+ Aig_Obj_t * pAnd;
+ If_Lib_t * pTempLib = pNtk->pLutLib;
+ Tim_Man_t * pTempTim = NULL;
+ float tDelta, tArrival;
+ int i, k, k2, Counter, CounterRes, nTimeCris;
+ unsigned * puTCEdges;
+ // perform delay trace
+ if ( !fUseLutLib )
+ {
+ pNtk->pLutLib = NULL;
+ if ( pNtk->pManTime )
+ {
+ pTempTim = pNtk->pManTime;
+ pNtk->pManTime = Tim_ManDup( pTempTim, 1 );
+ }
+ }
+ tArrival = Nwk_ManDelayTraceLut( pNtk );
+ tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
+ if ( fVerbose )
+ {
+ printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
+ printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" );
+ if ( fUseLutLib )
+ printf( "Percentage = %d. ", Percentage );
+ printf( "\n" );
+ }
+ // mark the timing critical nodes and edges
+ puTCEdges = ABC_ALLOC( unsigned, Nwk_ManObjNumMax(pNtk) );
+ memset( puTCEdges, 0, sizeof(unsigned) * Nwk_ManObjNumMax(pNtk) );
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ if ( Nwk_ObjSlack(pNode) >= tDelta )
+ continue;
+ puTCEdges[pNode->Id] = Nwk_ManDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib );
+ }
+ if ( fVerbose )
+ {
+ Counter = CounterRes = 0;
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( !Nwk_ObjIsCi(pFanin) && Nwk_ObjSlack(pFanin) < tDelta )
+ Counter++;
+ CounterRes += Aig_WordCountOnes( puTCEdges[pNode->Id] );
+ }
+ printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n",
+ Nwk_ManGetTotalFanins(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
+ }
+ // start the resulting network
+ pAig = Nwk_ManStrash( pNtk );
+ pAig->pEquivs = ABC_ALLOC( Aig_Obj_t *, 3 * Aig_ManObjNumMax(pAig) );
+ memset( pAig->pEquivs, 0, sizeof(Aig_Obj_t *) * 3 * Aig_ManObjNumMax(pAig) );
+
+ // collect nodes to be used for resynthesis
+ Counter = CounterRes = 0;
+ vTimeCries = Vec_PtrAlloc( 16 );
+ vTimeFanins = Vec_PtrAlloc( 16 );
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ if ( Nwk_ObjSlack(pNode) >= tDelta )
+ continue;
+ // count the number of non-PI timing-critical nodes
+ nTimeCris = 0;
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
+ nTimeCris++;
+ if ( !fVeryVerbose && nTimeCris == 0 )
+ continue;
+ Counter++;
+ // count the total number of timing critical second-generation nodes
+ Vec_PtrClear( vTimeCries );
+ if ( nTimeCris )
+ {
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
+ Nwk_ObjForEachFanin( pFanin, pFanin2, k2 )
+ if ( puTCEdges[pFanin->Id] & (1<<k2) )
+ Vec_PtrPushUnique( vTimeCries, pFanin2 );
+ }
+// if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
+ if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
+ continue;
+ CounterRes++;
+ // collect second generation nodes
+ Vec_PtrClear( vTimeFanins );
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ {
+ if ( Nwk_ObjIsCi(pFanin) )
+ Vec_PtrPushUnique( vTimeFanins, pFanin );
+ else
+ Nwk_ObjForEachFanin( pFanin, pFanin2, k2 )
+ Vec_PtrPushUnique( vTimeFanins, pFanin2 );
+ }
+ // print the results
+ if ( fVeryVerbose )
+ {
+ printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id,
+ nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
+ Nwk_ObjForEachFanin( pNode, pFanin, k )
+ printf( "%d(%.2f)%s ", pFanin->Id, Nwk_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" );
+ printf( "\n" );
+ }
+ // add the node to choices
+ if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
+ continue;
+ // order the fanins in the increasing order of criticalily
+ if ( Vec_PtrSize(vTimeCries) > 1 )
+ {
+ pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
+ pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
+ if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
+ {
+ Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
+ Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
+ }
+ }
+ if ( Vec_PtrSize(vTimeCries) > 2 )
+ {
+ pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
+ pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
+ if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
+ {
+ Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
+ Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
+ }
+ pFanin = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
+ pFanin2 = (Nwk_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
+ if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) )
+ {
+ Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
+ Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
+ }
+ }
+ // add choice
+ Aig_ManSpeedupNode( pNtk, pAig, pNode, vTimeFanins, vTimeCries );
+ }
+ Vec_PtrFree( vTimeCries );
+ Vec_PtrFree( vTimeFanins );
+ ABC_FREE( puTCEdges );
+ if ( fVerbose )
+ printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n",
+ Nwk_ManNodeNum(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
+
+ // remove invalid choice nodes
+ Aig_ManForEachNode( pAig, pAnd, i )
+ if ( Aig_ObjEquiv(pAig, pAnd) )
+ {
+ if ( Aig_ObjRefs(Aig_ObjEquiv(pAig, pAnd)) > 0 )
+ pAig->pEquivs[pAnd->Id] = NULL;
+ }
+
+ // put back the library
+ if ( !fUseLutLib )
+ pNtk->pLutLib = pTempLib;
+ if ( pTempTim )
+ {
+ Tim_ManStop( pNtk->pManTime );
+ pNtk->pManTime = pTempTim;
+ }
+
+ // reconstruct the network
+ pAig = Aig_ManDupDfs( pTemp = pAig );
+ Aig_ManStop( pTemp );
+ // reset levels
+ Aig_ManChoiceLevel( pAig );
+ return pAig;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkStrash.c b/src/opt/nwk/nwkStrash.c
new file mode 100644
index 00000000..74fc4d56
--- /dev/null
+++ b/src/opt/nwk/nwkStrash.c
@@ -0,0 +1,149 @@
+/**CFile****************************************************************
+
+ FileName [nwkStrash.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Performs structural hashing for the network.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkStrash.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Derives AIG from the local functions of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManStrashNode_rec( Aig_Man_t * p, Hop_Obj_t * pObj )
+{
+ assert( !Hop_IsComplement(pObj) );
+ if ( !Hop_ObjIsNode(pObj) || Hop_ObjIsMarkA(pObj) )
+ return;
+ Nwk_ManStrashNode_rec( p, Hop_ObjFanin0(pObj) );
+ Nwk_ManStrashNode_rec( p, Hop_ObjFanin1(pObj) );
+ pObj->pData = Aig_And( p, (Aig_Obj_t *)Hop_ObjChild0Copy(pObj), (Aig_Obj_t *)Hop_ObjChild1Copy(pObj) );
+ assert( !Hop_ObjIsMarkA(pObj) ); // loop detection
+ Hop_ObjSetMarkA( pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Derives AIG from the local functions of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_Obj_t * Nwk_ManStrashNode( Aig_Man_t * p, Nwk_Obj_t * pObj )
+{
+ Hop_Man_t * pMan = pObj->pMan->pManHop;
+ Hop_Obj_t * pRoot = pObj->pFunc;
+ Nwk_Obj_t * pFanin;
+ int i;
+ assert( Nwk_ObjIsNode(pObj) );
+ // check the constant case
+ if ( Hop_Regular(pRoot) == Hop_ManConst1(pMan) )
+ return Aig_NotCond( Aig_ManConst1(p), Hop_IsComplement(pRoot) );
+ // set elementary variables
+ Nwk_ObjForEachFanin( pObj, pFanin, i )
+ Hop_IthVar(pMan, i)->pData = pFanin->pCopy;
+ // strash the AIG of this node
+ Nwk_ManStrashNode_rec( p, Hop_Regular(pRoot) );
+ Hop_ConeUnmark_rec( Hop_Regular(pRoot) );
+ // return the final node
+ return Aig_NotCond( (Aig_Obj_t *)Hop_Regular(pRoot)->pData, Hop_IsComplement(pRoot) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Derives AIG from the logic network.]
+
+ Description [Assumes topological ordering of nodes.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_Man_t * Nwk_ManStrash( Nwk_Man_t * pNtk )
+{
+ Vec_Ptr_t * vObjs;
+ Aig_Man_t * pMan;
+ Aig_Obj_t * pObjNew;
+ Nwk_Obj_t * pObj;
+ int i, Level;
+ pMan = Aig_ManStart( Nwk_ManGetAigNodeNum(pNtk) );
+ pMan->pName = Abc_UtilStrsav( pNtk->pName );
+ pMan->pSpec = Abc_UtilStrsav( pNtk->pSpec );
+ pMan->pManTime = Tim_ManDup( (Tim_Man_t *)pNtk->pManTime, 1 );
+ Tim_ManIncrementTravId( (Tim_Man_t *)pMan->pManTime );
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ pObj->pCopy = NULL;
+// Nwk_ManForEachObj( pNtk, pObj, i )
+ vObjs = Nwk_ManDfs( pNtk );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vObjs, pObj, i )
+ {
+ if ( Nwk_ObjIsCi(pObj) )
+ {
+ pObjNew = Aig_ObjCreatePi(pMan);
+ Level = Tim_ManGetCiArrival( (Tim_Man_t *)pMan->pManTime, pObj->PioId );
+ Aig_ObjSetLevel( pObjNew, Level );
+ }
+ else if ( Nwk_ObjIsCo(pObj) )
+ {
+ pObjNew = Aig_ObjCreatePo( pMan, Aig_NotCond((Aig_Obj_t *)Nwk_ObjFanin0(pObj)->pCopy, pObj->fInvert) );
+ Level = Aig_ObjLevel( pObjNew );
+ Tim_ManSetCoArrival( (Tim_Man_t *)pMan->pManTime, pObj->PioId, (float)Level );
+ }
+ else if ( Nwk_ObjIsNode(pObj) )
+ {
+ pObjNew = Nwk_ManStrashNode( pMan, pObj );
+ }
+ else
+ assert( 0 );
+ pObj->pCopy = pObjNew;
+ }
+ Vec_PtrFree( vObjs );
+ Aig_ManCleanup( pMan );
+ Aig_ManSetRegNum( pMan, 0 );
+ return pMan;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkTiming.c b/src/opt/nwk/nwkTiming.c
new file mode 100644
index 00000000..9419c175
--- /dev/null
+++ b/src/opt/nwk/nwkTiming.c
@@ -0,0 +1,894 @@
+/**CFile****************************************************************
+
+ FileName [nwkTiming.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Manipulation of timing information.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkTiming.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Cleans timing information for all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManCleanTiming( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ int i;
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ pObj->tArrival = pObj->tSlack = 0.0;
+ pObj->tRequired = TIM_ETERNITY;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sorts the pins in the decreasing order of delays.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDelayTraceSortPins( Nwk_Obj_t * pNode, int * pPinPerm, float * pPinDelays )
+{
+ Nwk_Obj_t * pFanin;
+ int i, j, best_i, temp;
+ // start the trivial permutation and collect pin delays
+ Nwk_ObjForEachFanin( pNode, pFanin, i )
+ {
+ pPinPerm[i] = i;
+ pPinDelays[i] = Nwk_ObjArrival(pFanin);
+ }
+ // selection sort the pins in the decreasible order of delays
+ // this order will match the increasing order of LUT input pins
+ for ( i = 0; i < Nwk_ObjFaninNum(pNode)-1; i++ )
+ {
+ best_i = i;
+ for ( j = i+1; j < Nwk_ObjFaninNum(pNode); j++ )
+ if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
+ best_i = j;
+ if ( best_i == i )
+ continue;
+ temp = pPinPerm[i];
+ pPinPerm[i] = pPinPerm[best_i];
+ pPinPerm[best_i] = temp;
+ }
+ // verify
+ assert( Nwk_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Nwk_ObjFaninNum(pNode) );
+ for ( i = 1; i < Nwk_ObjFaninNum(pNode); i++ )
+ {
+ assert( pPinPerm[i] < Nwk_ObjFaninNum(pNode) );
+ assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sorts the pins in the decreasing order of delays.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManWhereIsPin( Nwk_Obj_t * pFanout, Nwk_Obj_t * pFanin, int * pPinPerm )
+{
+ int i;
+ for ( i = 0; i < Nwk_ObjFaninNum(pFanout); i++ )
+ if ( Nwk_ObjFanin(pFanout, pPinPerm[i]) == pFanin )
+ return i;
+ return -1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the arrival times for the given object.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float Nwk_NodeComputeArrival( Nwk_Obj_t * pObj, int fUseSorting )
+{
+ If_Lib_t * pLutLib = pObj->pMan->pLutLib;
+ int pPinPerm[32];
+ float pPinDelays[32];
+ Nwk_Obj_t * pFanin;
+ float tArrival, * pDelays;
+ int k;
+ assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) );
+ if ( Nwk_ObjIsCi(pObj) )
+ return Nwk_ObjArrival(pObj);
+ if ( Nwk_ObjIsCo(pObj) )
+ return Nwk_ObjArrival( Nwk_ObjFanin0(pObj) );
+ tArrival = -TIM_ETERNITY;
+ if ( pLutLib == NULL )
+ {
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( tArrival < Nwk_ObjArrival(pFanin) + 1.0 )
+ tArrival = Nwk_ObjArrival(pFanin) + 1.0;
+ }
+ else if ( !pLutLib->fVarPinDelays )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[0] )
+ tArrival = Nwk_ObjArrival(pFanin) + pDelays[0];
+ }
+ else
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
+ if ( fUseSorting )
+ {
+ Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays );
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( tArrival < Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k] )
+ tArrival = Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k];
+ }
+ else
+ {
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[k] )
+ tArrival = Nwk_ObjArrival(pFanin) + pDelays[k];
+ }
+ }
+ if ( Nwk_ObjFaninNum(pObj) == 0 )
+ tArrival = 0.0;
+ return tArrival;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the required times for the given node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float Nwk_NodeComputeRequired( Nwk_Obj_t * pObj, int fUseSorting )
+{
+ If_Lib_t * pLutLib = pObj->pMan->pLutLib;
+ int pPinPerm[32];
+ float pPinDelays[32];
+ Nwk_Obj_t * pFanout;
+ float tRequired, tDelay, * pDelays;
+ int k, iFanin;
+ assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) );
+ if ( Nwk_ObjIsCo(pObj) )
+ return Nwk_ObjRequired(pObj);
+ tRequired = TIM_ETERNITY;
+ if ( pLutLib == NULL )
+ {
+ Nwk_ObjForEachFanout( pObj, pFanout, k )
+ {
+ tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : 1.0;
+ if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
+ tRequired = Nwk_ObjRequired(pFanout) - tDelay;
+ }
+ }
+ else if ( !pLutLib->fVarPinDelays )
+ {
+ Nwk_ObjForEachFanout( pObj, pFanout, k )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
+ tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[0];
+ if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
+ tRequired = Nwk_ObjRequired(pFanout) - tDelay;
+ }
+ }
+ else
+ {
+ if ( fUseSorting )
+ {
+ Nwk_ObjForEachFanout( pObj, pFanout, k )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
+ Nwk_ManDelayTraceSortPins( pFanout, pPinPerm, pPinDelays );
+ iFanin = Nwk_ManWhereIsPin( pFanout, pObj, pPinPerm );
+ assert( Nwk_ObjFanin(pFanout,pPinPerm[iFanin]) == pObj );
+ tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
+ if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
+ tRequired = Nwk_ObjRequired(pFanout) - tDelay;
+ }
+ }
+ else
+ {
+ Nwk_ObjForEachFanout( pObj, pFanout, k )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)];
+ iFanin = Nwk_ObjFindFanin( pFanout, pObj );
+ assert( Nwk_ObjFanin(pFanout,iFanin) == pObj );
+ tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
+ if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay )
+ tRequired = Nwk_ObjRequired(pFanout) - tDelay;
+ }
+ }
+ }
+ return tRequired;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Propagates the required times through the given node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float Nwk_NodePropagateRequired( Nwk_Obj_t * pObj, int fUseSorting )
+{
+ If_Lib_t * pLutLib = pObj->pMan->pLutLib;
+ int pPinPerm[32];
+ float pPinDelays[32];
+ Nwk_Obj_t * pFanin;
+ float tRequired = 0.0; // Suppress "might be used uninitialized"
+ float * pDelays;
+ int k;
+ assert( Nwk_ObjIsNode(pObj) );
+ if ( pLutLib == NULL )
+ {
+ tRequired = Nwk_ObjRequired(pObj) - (float)1.0;
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( Nwk_ObjRequired(pFanin) > tRequired )
+ Nwk_ObjSetRequired( pFanin, tRequired );
+ }
+ else if ( !pLutLib->fVarPinDelays )
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
+ tRequired = Nwk_ObjRequired(pObj) - pDelays[0];
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( Nwk_ObjRequired(pFanin) > tRequired )
+ Nwk_ObjSetRequired( pFanin, tRequired );
+ }
+ else
+ {
+ pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)];
+ if ( fUseSorting )
+ {
+ Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays );
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ {
+ tRequired = Nwk_ObjRequired(pObj) - pDelays[k];
+ if ( Nwk_ObjRequired(Nwk_ObjFanin(pObj,pPinPerm[k])) > tRequired )
+ Nwk_ObjSetRequired( Nwk_ObjFanin(pObj,pPinPerm[k]), tRequired );
+ }
+ }
+ else
+ {
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ {
+ tRequired = Nwk_ObjRequired(pObj) - pDelays[k];
+ if ( Nwk_ObjRequired(pFanin) > tRequired )
+ Nwk_ObjSetRequired( pFanin, tRequired );
+ }
+ }
+ }
+ return tRequired;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the delay trace of the given network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float Nwk_ManDelayTraceLut( Nwk_Man_t * pNtk )
+{
+ Vec_Ptr_t * vObjs;
+ int fUseSorting = 1;
+ If_Lib_t * pLutLib = pNtk->pLutLib;
+ Vec_Ptr_t * vNodes;
+ Nwk_Obj_t * pObj;
+ float tArrival, tRequired, tSlack;
+ int i;
+
+ // get the library
+ if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) )
+ {
+ printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
+ pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) );
+ return -TIM_ETERNITY;
+ }
+
+ // compute the reverse order of all objects
+ vNodes = Nwk_ManDfsReverse( pNtk );
+
+ // initialize the arrival times
+ Nwk_ManCleanTiming( pNtk );
+
+ // propagate arrival times
+ if ( pNtk->pManTime )
+ Tim_ManIncrementTravId( pNtk->pManTime );
+// Nwk_ManForEachObj( pNtk, pObj, i )
+ vObjs = Nwk_ManDfs( pNtk );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vObjs, pObj, i )
+ {
+ tArrival = Nwk_NodeComputeArrival( pObj, fUseSorting );
+ if ( Nwk_ObjIsCi(pObj) && pNtk->pManTime )
+ tArrival = Tim_ManGetCiArrival( pNtk->pManTime, pObj->PioId );
+ if ( Nwk_ObjIsCo(pObj) && pNtk->pManTime )
+ Tim_ManSetCoArrival( pNtk->pManTime, pObj->PioId, tArrival );
+ Nwk_ObjSetArrival( pObj, tArrival );
+ }
+ Vec_PtrFree( vObjs );
+
+ // get the latest arrival times
+ tArrival = -TIM_ETERNITY;
+ Nwk_ManForEachPo( pNtk, pObj, i )
+ if ( tArrival < Nwk_ObjArrival(pObj) )
+ tArrival = Nwk_ObjArrival(pObj);
+
+ // initialize the required times
+ if ( pNtk->pManTime )
+ {
+ Tim_ManIncrementTravId( pNtk->pManTime );
+ Tim_ManSetCoRequiredAll( pNtk->pManTime, tArrival );
+ }
+ else
+ {
+ Nwk_ManForEachCo( pNtk, pObj, i )
+ Nwk_ObjSetRequired( pObj, tArrival );
+ }
+
+ // propagate the required times
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ {
+ if ( Nwk_ObjIsNode(pObj) )
+ {
+ Nwk_NodePropagateRequired( pObj, fUseSorting );
+ }
+ else if ( Nwk_ObjIsCi(pObj) )
+ {
+ if ( pNtk->pManTime )
+ Tim_ManSetCiRequired( pNtk->pManTime, pObj->PioId, Nwk_ObjRequired(pObj) );
+ }
+ else if ( Nwk_ObjIsCo(pObj) )
+ {
+ if ( pNtk->pManTime )
+ {
+ tRequired = Tim_ManGetCoRequired( pNtk->pManTime, pObj->PioId );
+ Nwk_ObjSetRequired( pObj, tRequired );
+ }
+ if ( Nwk_ObjRequired(Nwk_ObjFanin0(pObj)) > Nwk_ObjRequired(pObj) )
+ Nwk_ObjSetRequired( Nwk_ObjFanin0(pObj), Nwk_ObjRequired(pObj) );
+ }
+
+ // set slack for this object
+ tSlack = Nwk_ObjRequired(pObj) - Nwk_ObjArrival(pObj);
+ assert( tSlack + 0.01 > 0.0 );
+ Nwk_ObjSetSlack( pObj, tSlack < 0.0 ? 0.0 : tSlack );
+ }
+ Vec_PtrFree( vNodes );
+ return tArrival;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the arrival times for the given node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManVerifyTiming( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ float tArrival, tRequired;
+ int i;
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ if ( Nwk_ObjIsCi(pObj) && Nwk_ObjFanoutNum(pObj) == 0 )
+ continue;
+ tArrival = Nwk_NodeComputeArrival( pObj, 1 );
+ tRequired = Nwk_NodeComputeRequired( pObj, 1 );
+ if ( !Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pObj), (float)0.01 ) )
+ printf( "Nwk_ManVerifyTiming(): Object %d has different arrival time (%.2f) from computed (%.2f).\n",
+ pObj->Id, Nwk_ObjArrival(pObj), tArrival );
+ if ( !Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) )
+ printf( "Nwk_ManVerifyTiming(): Object %d has different required time (%.2f) from computed (%.2f).\n",
+ pObj->Id, Nwk_ObjRequired(pObj), tRequired );
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints the delay trace for the given network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDelayTracePrint( Nwk_Man_t * pNtk )
+{
+ If_Lib_t * pLutLib = pNtk->pLutLib;
+ Nwk_Obj_t * pNode;
+ int i, Nodes, * pCounters;
+ float tArrival, tDelta, nSteps, Num;
+ // get the library
+ if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) )
+ {
+ printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
+ pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) );
+ return;
+ }
+ // decide how many steps
+ nSteps = pLutLib ? 20 : Nwk_ManLevelMax(pNtk);
+ pCounters = ABC_ALLOC( int, nSteps + 1 );
+ memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
+ // perform delay trace
+ tArrival = Nwk_ManDelayTraceLut( pNtk );
+ tDelta = tArrival / nSteps;
+ // count how many nodes have slack in the corresponding intervals
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ if ( Nwk_ObjFaninNum(pNode) == 0 )
+ continue;
+ Num = Nwk_ObjSlack(pNode) / tDelta;
+ if ( Num > nSteps )
+ continue;
+ assert( Num >=0 && Num <= nSteps );
+ pCounters[(int)Num]++;
+ }
+ // print the results
+ printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, pLutLib? "LUT library" : "unit-delay" );
+ Nodes = 0;
+ for ( i = 0; i < nSteps; i++ )
+ {
+ Nodes += pCounters[i];
+ printf( "%3d %s : %5d (%6.2f %%)\n", pLutLib? 5*(i+1) : i+1,
+ pLutLib? "%":"lev", Nodes, 100.0*Nodes/Nwk_ManNodeNum(pNtk) );
+ }
+ ABC_FREE( pCounters );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Inserts node into the queue of nodes sorted by level.]
+
+ Description [The inserted node should not go before the current position
+ given by iCurrent. If the arrival times are computed, the nodes are sorted
+ in the increasing order of levels. If the required times are computed,
+ the nodes are sorted in the decreasing order of levels.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_NodeUpdateAddToQueue( Vec_Ptr_t * vQueue, Nwk_Obj_t * pObj, int iCurrent, int fArrival )
+{
+ Nwk_Obj_t * pTemp1, * pTemp2;
+ int i;
+ Vec_PtrPush( vQueue, pObj );
+ for ( i = Vec_PtrSize(vQueue) - 1; i > iCurrent + 1; i-- )
+ {
+ pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i];
+ pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i-1];
+ if ( fArrival )
+ {
+ if ( Nwk_ObjLevel(pTemp2) <= Nwk_ObjLevel(pTemp1) )
+ break;
+ }
+ else
+ {
+ if ( Nwk_ObjLevel(pTemp2) >= Nwk_ObjLevel(pTemp1) )
+ break;
+ }
+ vQueue->pArray[i-1] = pTemp1;
+ vQueue->pArray[i] = pTemp2;
+ }
+ // verification
+ for ( i = iCurrent + 1; i < Vec_PtrSize(vQueue) - 1; i++ )
+ {
+ pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i];
+ pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i+1];
+ if ( fArrival )
+ assert( Nwk_ObjLevel(pTemp1) <= Nwk_ObjLevel(pTemp2) );
+ else
+ assert( Nwk_ObjLevel(pTemp1) >= Nwk_ObjLevel(pTemp2) );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Incrementally updates arrival times of the node.]
+
+ Description [Supports variable-pin delay model and white-boxes.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_NodeUpdateArrival( Nwk_Obj_t * pObj )
+{
+ Tim_Man_t * pManTime = pObj->pMan->pManTime;
+ Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
+ Nwk_Obj_t * pTemp;
+ Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
+ float tArrival;
+ int iCur, k, iBox, iTerm1, nTerms;
+ assert( Nwk_ObjIsNode(pObj) );
+ // verify the arrival time
+ tArrival = Nwk_NodeComputeArrival( pObj, 1 );
+ assert( Nwk_ManTimeLess( tArrival, Nwk_ObjRequired(pObj), (float)0.01 ) );
+ // initialize the queue with the node
+ Vec_PtrClear( vQueue );
+ Vec_PtrPush( vQueue, pObj );
+ pObj->MarkA = 1;
+ // process objects
+ if ( pManTime )
+ Tim_ManIncrementTravId( pManTime );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
+ {
+ pTemp->MarkA = 0;
+ tArrival = Nwk_NodeComputeArrival( pTemp, 1 );
+ if ( Nwk_ObjIsCi(pTemp) && pManTime )
+ tArrival = Tim_ManGetCiArrival( pManTime, pTemp->PioId );
+ if ( Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pTemp), (float)0.01 ) )
+ continue;
+ Nwk_ObjSetArrival( pTemp, tArrival );
+ // add the fanouts to the queue
+ if ( Nwk_ObjIsCo(pTemp) )
+ {
+ if ( pManTime )
+ {
+ iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId );
+ if ( iBox >= 0 ) // this CO is an input of the box
+ {
+ // it may happen that a box-input (CO) was already marked as visited
+ // when some other box-input of the same box was visited - here we undo this
+ if ( Tim_ManIsCoTravIdCurrent( pManTime, pTemp->PioId ) )
+ Tim_ManSetPreviousTravIdBoxInputs( pManTime, iBox );
+ Tim_ManSetCoArrival( pManTime, pTemp->PioId, tArrival );
+ Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox );
+ iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox );
+ nTerms = Tim_ManBoxOutputNum( pManTime, iBox );
+ for ( k = 0; k < nTerms; k++ )
+ {
+ pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k);
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+ }
+ else
+ {
+ Nwk_ObjForEachFanout( pTemp, pNext, k )
+ {
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Incrementally updates required times of the node.]
+
+ Description [Supports variable-pin delay model and white-boxes.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_NodeUpdateRequired( Nwk_Obj_t * pObj )
+{
+ Tim_Man_t * pManTime = pObj->pMan->pManTime;
+ Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
+ Nwk_Obj_t * pTemp;
+ Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
+ float tRequired;
+ int iCur, k, iBox, iTerm1, nTerms;
+ assert( Nwk_ObjIsNode(pObj) );
+ // make sure the node's required time remained the same
+ tRequired = Nwk_NodeComputeRequired( pObj, 1 );
+ assert( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) );
+ // initialize the queue with the node's faninsa and the old node's fanins
+ Vec_PtrClear( vQueue );
+ Nwk_ObjForEachFanin( pObj, pNext, k )
+ {
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, -1, 0 );
+ pNext->MarkA = 1;
+ }
+ // process objects
+ if ( pManTime )
+ Tim_ManIncrementTravId( pManTime );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
+ {
+ pTemp->MarkA = 0;
+ tRequired = Nwk_NodeComputeRequired( pTemp, 1 );
+ if ( Nwk_ObjIsCo(pTemp) && pManTime )
+ tRequired = Tim_ManGetCoRequired( pManTime, pTemp->PioId );
+ if ( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pTemp), (float)0.01 ) )
+ continue;
+ Nwk_ObjSetRequired( pTemp, tRequired );
+ // add the fanins to the queue
+ if ( Nwk_ObjIsCi(pTemp) )
+ {
+ if ( pManTime )
+ {
+ iBox = Tim_ManBoxForCi( pManTime, pTemp->PioId );
+ if ( iBox >= 0 ) // this CI is an output of the box
+ {
+ // it may happen that a box-output (CI) was already marked as visited
+ // when some other box-output of the same box was visited - here we undo this
+ if ( Tim_ManIsCiTravIdCurrent( pManTime, pTemp->PioId ) )
+ Tim_ManSetPreviousTravIdBoxOutputs( pManTime, iBox );
+ Tim_ManSetCiRequired( pManTime, pTemp->PioId, tRequired );
+ Tim_ManSetCurrentTravIdBoxOutputs( pManTime, iBox );
+ iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
+ nTerms = Tim_ManBoxInputNum( pManTime, iBox );
+ for ( k = 0; k < nTerms; k++ )
+ {
+ pNext = Nwk_ManCo(pNext->pMan, iTerm1 + k);
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+ }
+ else
+ {
+ Nwk_ObjForEachFanin( pTemp, pNext, k )
+ {
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the level of the node using its fanin levels.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ObjLevelNew( Nwk_Obj_t * pObj )
+{
+ Tim_Man_t * pManTime = pObj->pMan->pManTime;
+ Nwk_Obj_t * pFanin;
+ int i, iBox, iTerm1, nTerms, Level = 0;
+ if ( Nwk_ObjIsCi(pObj) || Nwk_ObjIsLatch(pObj) )
+ {
+ if ( pManTime )
+ {
+ iBox = Tim_ManBoxForCi( pManTime, pObj->PioId );
+ if ( iBox >= 0 ) // this CI is an output of the box
+ {
+ iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
+ nTerms = Tim_ManBoxInputNum( pManTime, iBox );
+ for ( i = 0; i < nTerms; i++ )
+ {
+ pFanin = Nwk_ManCo(pObj->pMan, iTerm1 + i);
+ Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) );
+ }
+ Level++;
+ }
+ }
+ return Level;
+ }
+ assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) );
+ Nwk_ObjForEachFanin( pObj, pFanin, i )
+ Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) );
+ return Level + (Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Incrementally updates level of the nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManUpdateLevel( Nwk_Obj_t * pObj )
+{
+ Tim_Man_t * pManTime = pObj->pMan->pManTime;
+ Vec_Ptr_t * vQueue = pObj->pMan->vTemp;
+ Nwk_Obj_t * pTemp;
+ Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized"
+ int LevelNew, iCur, k, iBox, iTerm1, nTerms;
+ assert( Nwk_ObjIsNode(pObj) );
+ // initialize the queue with the node
+ Vec_PtrClear( vQueue );
+ Vec_PtrPush( vQueue, pObj );
+ pObj->MarkA = 1;
+ // process objects
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur )
+ {
+ pTemp->MarkA = 0;
+ LevelNew = Nwk_ObjLevelNew( pTemp );
+ if ( LevelNew == Nwk_ObjLevel(pTemp) )
+ continue;
+ Nwk_ObjSetLevel( pTemp, LevelNew );
+ // add the fanouts to the queue
+ if ( Nwk_ObjIsCo(pTemp) )
+ {
+ if ( pManTime )
+ {
+ iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId );
+ if ( iBox >= 0 ) // this is not a true PO
+ {
+ Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox );
+ iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox );
+ nTerms = Tim_ManBoxOutputNum( pManTime, iBox );
+ for ( k = 0; k < nTerms; k++ )
+ {
+ pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k);
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+ }
+ else
+ {
+ Nwk_ObjForEachFanout( pTemp, pNext, k )
+ {
+ if ( pNext->MarkA )
+ continue;
+ Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 );
+ pNext->MarkA = 1;
+ }
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the level of the node using its fanin levels.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManVerifyLevel( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ int LevelNew, i;
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ {
+ assert( pObj->MarkA == 0 );
+ LevelNew = Nwk_ObjLevelNew( pObj );
+ if ( Nwk_ObjLevel(pObj) != LevelNew )
+ {
+ printf( "Object %6d: Mismatch betweeh levels: Actual = %d. Correct = %d.\n",
+ i, Nwk_ObjLevel(pObj), LevelNew );
+ }
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Replaces the node and incrementally updates levels.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManUpdate( Nwk_Obj_t * pObj, Nwk_Obj_t * pObjNew, Vec_Vec_t * vLevels )
+{
+ assert( pObj->pMan == pObjNew->pMan );
+ assert( pObj != pObjNew );
+ assert( Nwk_ObjFanoutNum(pObj) > 0 );
+ assert( Nwk_ObjIsNode(pObj) && !Nwk_ObjIsCo(pObjNew) );
+ // transfer fanouts to the old node
+ Nwk_ObjTransferFanout( pObj, pObjNew );
+ // transfer the timing information
+ // (this is needed because updating level happens if the level has changed;
+ // when we set the old level, it will be recomputed by the level updating
+ // procedure, which will update level of other nodes if there is a difference)
+ pObjNew->Level = pObj->Level;
+ pObjNew->tArrival = pObj->tArrival;
+ pObjNew->tRequired = pObj->tRequired;
+ // update required times of the old fanins
+ pObj->tRequired = TIM_ETERNITY;
+ Nwk_NodeUpdateRequired( pObj );
+ // remove the old node
+ Nwk_ManDeleteNode_rec( pObj );
+ // update the information of the new node
+ Nwk_ManUpdateLevel( pObjNew );
+ Nwk_NodeUpdateArrival( pObjNew );
+ Nwk_NodeUpdateRequired( pObjNew );
+//Nwk_ManVerifyTiming( pObjNew->pMan );
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwkUtil.c b/src/opt/nwk/nwkUtil.c
new file mode 100644
index 00000000..9d23c869
--- /dev/null
+++ b/src/opt/nwk/nwkUtil.c
@@ -0,0 +1,643 @@
+/**CFile****************************************************************
+
+ FileName [nwkUtil.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Logic network representation.]
+
+ Synopsis [Various utilities.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwkUtil.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include <math.h>
+#include "nwk.h"
+#include "src/bool/kit/kit.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Increments the current traversal ID of the network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManIncrementTravId( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pObj;
+ int i;
+ if ( pNtk->nTravIds >= (1<<26)-1 )
+ {
+ pNtk->nTravIds = 0;
+ Nwk_ManForEachObj( pNtk, pObj, i )
+ pObj->TravId = 0;
+ }
+ pNtk->nTravIds++;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Reads the maximum number of fanins of a node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManGetFaninMax( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pNode;
+ int i, nFaninsMax = 0;
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ if ( nFaninsMax < Nwk_ObjFaninNum(pNode) )
+ nFaninsMax = Nwk_ObjFaninNum(pNode);
+ }
+ return nFaninsMax;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Reads the total number of all fanins.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManGetTotalFanins( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pNode;
+ int i, nFanins = 0;
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ nFanins += Nwk_ObjFaninNum(pNode);
+ return nFanins;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Returns the number of true PIs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPiNum( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pNode;
+ int i, Counter = 0;
+ Nwk_ManForEachCi( pNtk, pNode, i )
+ Counter += Nwk_ObjIsPi( pNode );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the number of true POs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManPoNum( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pNode;
+ int i, Counter = 0;
+ Nwk_ManForEachCo( pNtk, pNode, i )
+ Counter += Nwk_ObjIsPo( pNode );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Reads the number of AIG nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManGetAigNodeNum( Nwk_Man_t * pNtk )
+{
+ Nwk_Obj_t * pNode;
+ int i, nNodes = 0;
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ if ( pNode->pFunc == NULL )
+ {
+ printf( "Nwk_ManGetAigNodeNum(): Local AIG of node %d is not assigned.\n", pNode->Id );
+ continue;
+ }
+ if ( Nwk_ObjFaninNum(pNode) < 2 )
+ continue;
+ nNodes += Hop_DagSize( pNode->pFunc );
+ }
+ return nNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Procedure used for sorting the nodes in increasing order of levels.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_NodeCompareLevelsIncrease( Nwk_Obj_t ** pp1, Nwk_Obj_t ** pp2 )
+{
+ int Diff = (*pp1)->Level - (*pp2)->Level;
+ if ( Diff < 0 )
+ return -1;
+ if ( Diff > 0 )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Procedure used for sorting the nodes in decreasing order of levels.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_NodeCompareLevelsDecrease( Nwk_Obj_t ** pp1, Nwk_Obj_t ** pp2 )
+{
+ int Diff = (*pp1)->Level - (*pp2)->Level;
+ if ( Diff > 0 )
+ return -1;
+ if ( Diff < 0 )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints the objects.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ObjPrint( Nwk_Obj_t * pObj )
+{
+ Nwk_Obj_t * pNext;
+ int i;
+ printf( "ObjId = %5d. ", pObj->Id );
+ if ( Nwk_ObjIsPi(pObj) )
+ printf( "PI" );
+ if ( Nwk_ObjIsPo(pObj) )
+ printf( "PO" );
+ if ( Nwk_ObjIsNode(pObj) )
+ printf( "Node" );
+ printf( " Fanins = " );
+ Nwk_ObjForEachFanin( pObj, pNext, i )
+ printf( "%d ", pNext->Id );
+ printf( " Fanouts = " );
+ Nwk_ObjForEachFanout( pObj, pNext, i )
+ printf( "%d ", pNext->Id );
+ printf( "\n" );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dumps the BLIF file for the network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManDumpBlif( Nwk_Man_t * pNtk, char * pFileName, Vec_Ptr_t * vPiNames, Vec_Ptr_t * vPoNames )
+{
+ FILE * pFile;
+ Vec_Ptr_t * vNodes;
+ Vec_Int_t * vTruth;
+ Vec_Int_t * vCover;
+ Nwk_Obj_t * pObj, * pFanin;
+ Aig_MmFlex_t * pMem;
+ char * pSop = NULL;
+ unsigned * pTruth;
+ int i, k, nDigits;
+ if ( Nwk_ManPoNum(pNtk) == 0 )
+ {
+ printf( "Nwk_ManDumpBlif(): Network does not have POs.\n" );
+ return;
+ }
+ // collect nodes in the DFS order
+ nDigits = Abc_Base10Log( Nwk_ManObjNumMax(pNtk) );
+ // write the file
+ pFile = fopen( pFileName, "w" );
+ fprintf( pFile, "# BLIF file written by procedure Nwk_ManDumpBlif()\n" );
+// fprintf( pFile, "# http://www.eecs.berkeley.edu/~alanmi/abc/\n" );
+ fprintf( pFile, ".model %s\n", pNtk->pName );
+ // write PIs
+ fprintf( pFile, ".inputs" );
+ Nwk_ManForEachCi( pNtk, pObj, i )
+ if ( vPiNames )
+ fprintf( pFile, " %s", (char*)Vec_PtrEntry(vPiNames, i) );
+ else
+ fprintf( pFile, " n%0*d", nDigits, pObj->Id );
+ fprintf( pFile, "\n" );
+ // write POs
+ fprintf( pFile, ".outputs" );
+ Nwk_ManForEachCo( pNtk, pObj, i )
+ if ( vPoNames )
+ fprintf( pFile, " %s", (char*)Vec_PtrEntry(vPoNames, i) );
+ else
+ fprintf( pFile, " n%0*d", nDigits, pObj->Id );
+ fprintf( pFile, "\n" );
+ // write nodes
+ pMem = Aig_MmFlexStart();
+ vTruth = Vec_IntAlloc( 1 << 16 );
+ vCover = Vec_IntAlloc( 1 << 16 );
+ vNodes = Nwk_ManDfs( pNtk );
+ Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
+ {
+ if ( !Nwk_ObjIsNode(pObj) )
+ continue;
+ // derive SOP for the AIG
+ pTruth = Hop_ManConvertAigToTruth( pNtk->pManHop, Hop_Regular(pObj->pFunc), Nwk_ObjFaninNum(pObj), vTruth, 0 );
+ if ( Hop_IsComplement(pObj->pFunc) )
+ Kit_TruthNot( pTruth, pTruth, Nwk_ObjFaninNum(pObj) );
+ pSop = Kit_PlaFromTruth( pMem, pTruth, Nwk_ObjFaninNum(pObj), vCover );
+ // write the node
+ fprintf( pFile, ".names" );
+ if ( !Kit_TruthIsConst0(pTruth, Nwk_ObjFaninNum(pObj)) && !Kit_TruthIsConst1(pTruth, Nwk_ObjFaninNum(pObj)) )
+ {
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( vPiNames && Nwk_ObjIsPi(pFanin) )
+ fprintf( pFile, " %s", (char*)Vec_PtrEntry(vPiNames, Nwk_ObjPioNum(pFanin)) );
+ else
+ fprintf( pFile, " n%0*d", nDigits, pFanin->Id );
+ }
+ fprintf( pFile, " n%0*d\n", nDigits, pObj->Id );
+ // write the function
+ fprintf( pFile, "%s", pSop );
+ }
+ Vec_IntFree( vCover );
+ Vec_IntFree( vTruth );
+ Vec_PtrFree( vNodes );
+ Aig_MmFlexStop( pMem, 0 );
+ // write POs
+ Nwk_ManForEachCo( pNtk, pObj, i )
+ {
+ fprintf( pFile, ".names" );
+ if ( vPiNames && Nwk_ObjIsPi(Nwk_ObjFanin0(pObj)) )
+ fprintf( pFile, " %s", (char*)Vec_PtrEntry(vPiNames, Nwk_ObjPioNum(Nwk_ObjFanin0(pObj))) );
+ else
+ fprintf( pFile, " n%0*d", nDigits, Nwk_ObjFanin0(pObj)->Id );
+ if ( vPoNames )
+ fprintf( pFile, " %s\n", (char*)Vec_PtrEntry(vPoNames, Nwk_ObjPioNum(pObj)) );
+ else
+ fprintf( pFile, " n%0*d\n", nDigits, pObj->Id );
+ fprintf( pFile, "%d 1\n", !pObj->fInvert );
+ }
+ fprintf( pFile, ".end\n\n" );
+ fclose( pFile );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints the distribution of fanins/fanouts in the network.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManPrintFanioNew( Nwk_Man_t * pNtk )
+{
+ char Buffer[100];
+ Nwk_Obj_t * pNode;
+ Vec_Int_t * vFanins, * vFanouts;
+ int nFanins, nFanouts, nFaninsMax, nFanoutsMax, nFaninsAll, nFanoutsAll;
+ int i, k, nSizeMax;
+
+ // determine the largest fanin and fanout
+ nFaninsMax = nFanoutsMax = 0;
+ nFaninsAll = nFanoutsAll = 0;
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ nFanins = Nwk_ObjFaninNum(pNode);
+ nFanouts = Nwk_ObjFanoutNum(pNode);
+ nFaninsAll += nFanins;
+ nFanoutsAll += nFanouts;
+ nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins );
+ nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts );
+ }
+
+ // allocate storage for fanin/fanout numbers
+ nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
+ vFanins = Vec_IntStart( nSizeMax );
+ vFanouts = Vec_IntStart( nSizeMax );
+
+ // count the number of fanins and fanouts
+ Nwk_ManForEachNode( pNtk, pNode, i )
+ {
+ nFanins = Nwk_ObjFaninNum(pNode);
+ nFanouts = Nwk_ObjFanoutNum(pNode);
+// nFanouts = Nwk_NodeMffcSize(pNode);
+
+ if ( nFanins < 10 )
+ Vec_IntAddToEntry( vFanins, nFanins, 1 );
+ else if ( nFanins < 100 )
+ Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
+ else if ( nFanins < 1000 )
+ Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
+ else if ( nFanins < 10000 )
+ Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
+ else if ( nFanins < 100000 )
+ Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
+ else if ( nFanins < 1000000 )
+ Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
+ else if ( nFanins < 10000000 )
+ Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );
+
+ if ( nFanouts < 10 )
+ Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
+ else if ( nFanouts < 100 )
+ Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
+ else if ( nFanouts < 1000 )
+ Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
+ else if ( nFanouts < 10000 )
+ Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
+ else if ( nFanouts < 100000 )
+ Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
+ else if ( nFanouts < 1000000 )
+ Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
+ else if ( nFanouts < 10000000 )
+ Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
+ }
+
+ printf( "The distribution of fanins and fanouts in the network:\n" );
+ printf( " Number Nodes with fanin Nodes with fanout\n" );
+ for ( k = 0; k < nSizeMax; k++ )
+ {
+ if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 )
+ continue;
+ if ( k < 10 )
+ printf( "%15d : ", k );
+ else
+ {
+ sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 );
+ printf( "%15s : ", Buffer );
+ }
+ if ( vFanins->pArray[k] == 0 )
+ printf( " " );
+ else
+ printf( "%12d ", vFanins->pArray[k] );
+ printf( " " );
+ if ( vFanouts->pArray[k] == 0 )
+ printf( " " );
+ else
+ printf( "%12d ", vFanouts->pArray[k] );
+ printf( "\n" );
+ }
+ Vec_IntFree( vFanins );
+ Vec_IntFree( vFanouts );
+
+ printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f.\n",
+ nFaninsMax, 1.0*nFaninsAll/Nwk_ManNodeNum(pNtk),
+ nFanoutsMax, 1.0*nFanoutsAll/Nwk_ManNodeNum(pNtk) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Cleans the temporary marks of the nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManCleanMarks( Nwk_Man_t * pMan )
+{
+ Nwk_Obj_t * pObj;
+ int i;
+ Nwk_ManForEachObj( pMan, pObj, i )
+ pObj->MarkA = pObj->MarkB = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManMinimumBaseNode( Nwk_Obj_t * pObj, Vec_Int_t * vTruth, int fVerbose )
+{
+ unsigned * pTruth;
+ Nwk_Obj_t * pFanin, * pObjNew;
+ Nwk_Man_t * pNtk = pObj->pMan;
+ int uSupp, nSuppSize, k, Counter = 0;
+ pTruth = Hop_ManConvertAigToTruth( pNtk->pManHop, Hop_Regular(pObj->pFunc), Nwk_ObjFaninNum(pObj), vTruth, 0 );
+ nSuppSize = Kit_TruthSupportSize(pTruth, Nwk_ObjFaninNum(pObj));
+ if ( nSuppSize == Nwk_ObjFaninNum(pObj) )
+ return 0;
+ Counter++;
+ uSupp = Kit_TruthSupport( pTruth, Nwk_ObjFaninNum(pObj) );
+ // create new node with the given support
+ pObjNew = Nwk_ManCreateNode( pNtk, nSuppSize, Nwk_ObjFanoutNum(pObj) );
+ Nwk_ObjForEachFanin( pObj, pFanin, k )
+ if ( uSupp & (1 << k) )
+ Nwk_ObjAddFanin( pObjNew, pFanin );
+ pObjNew->pFunc = Hop_Remap( pNtk->pManHop, pObj->pFunc, uSupp, Nwk_ObjFaninNum(pObj) );
+ if ( fVerbose )
+ printf( "Reducing node %d fanins from %d to %d.\n",
+ pObj->Id, Nwk_ObjFaninNum(pObj), Nwk_ObjFaninNum(pObjNew) );
+ Nwk_ObjReplace( pObj, pObjNew );
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Nwk_ManMinimumBaseInt( Nwk_Man_t * pNtk, int fVerbose )
+{
+ Vec_Int_t * vTruth;
+ Nwk_Obj_t * pObj;
+ int i, Counter = 0;
+ vTruth = Vec_IntAlloc( 1 << 16 );
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ Counter += Nwk_ManMinimumBaseNode( pObj, vTruth, fVerbose );
+ if ( fVerbose && Counter )
+ printf( "Support minimization reduced support of %d nodes.\n", Counter );
+ Vec_IntFree( vTruth );
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMinimumBaseRec( Nwk_Man_t * pNtk, int fVerbose )
+{
+ int i, clk = clock();
+ for ( i = 0; Nwk_ManMinimumBaseInt( pNtk, fVerbose ); i++ );
+ ABC_PRT( "Minbase", clock() - clk );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManMinimumBase( Nwk_Man_t * pNtk, int fVerbose )
+{
+ Vec_Int_t * vTruth;
+ Nwk_Obj_t * pObj;
+ int i, Counter = 0;
+ vTruth = Vec_IntAlloc( 1 << 16 );
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ Counter += Nwk_ManMinimumBaseNode( pObj, vTruth, fVerbose );
+ if ( fVerbose && Counter )
+ printf( "Support minimization reduced support of %d nodes.\n", Counter );
+ Vec_IntFree( vTruth );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManRemoveDupFaninsNode( Nwk_Obj_t * pObj, int iFan0, int iFan1, Vec_Int_t * vTruth )
+{
+ Hop_Man_t * pManHop = pObj->pMan->pManHop;
+// Nwk_Obj_t * pFanin0 = pObj->pFanio[iFan0];
+// Nwk_Obj_t * pFanin1 = pObj->pFanio[iFan1];
+ assert( pObj->pFanio[iFan0] == pObj->pFanio[iFan1] );
+ pObj->pFunc = Hop_Compose( pManHop, pObj->pFunc, Hop_IthVar(pManHop,iFan0), iFan1 );
+ Nwk_ManMinimumBaseNode( pObj, vTruth, 0 );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Minimizes the support of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Nwk_ManRemoveDupFanins( Nwk_Man_t * pNtk, int fVerbose )
+{
+ Vec_Int_t * vTruth;
+ Nwk_Obj_t * pObj;
+ int i, k, m, fFound;
+ // check if the nodes have duplicated fanins
+ vTruth = Vec_IntAlloc( 1 << 16 );
+ Nwk_ManForEachNode( pNtk, pObj, i )
+ {
+ fFound = 0;
+ for ( k = 0; k < pObj->nFanins; k++ )
+ {
+ for ( m = k + 1; m < pObj->nFanins; m++ )
+ if ( pObj->pFanio[k] == pObj->pFanio[m] )
+ {
+ if ( fVerbose )
+ printf( "Removing duplicated fanins of node %d (fanins %d and %d).\n",
+ pObj->Id, pObj->pFanio[k]->Id, pObj->pFanio[m]->Id );
+ Nwk_ManRemoveDupFaninsNode( pObj, k, m, vTruth );
+ fFound = 1;
+ break;
+ }
+ if ( fFound )
+ break;
+ }
+ }
+ Vec_IntFree( vTruth );
+// Nwk_ManMinimumBase( pNtk, fVerbose );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/nwk/nwk_.c b/src/opt/nwk/nwk_.c
new file mode 100644
index 00000000..882b077c
--- /dev/null
+++ b/src/opt/nwk/nwk_.c
@@ -0,0 +1,52 @@
+/**CFile****************************************************************
+
+ FileName [nwk_.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [Netlist representation.]
+
+ Synopsis []
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: nwk_.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 15:35:34 +0000