diff options
Diffstat (limited to 'src/opt/nwk')
-rw-r--r-- | src/opt/nwk/module.make | 14 | ||||
-rw-r--r-- | src/opt/nwk/ntlnwk.h | 113 | ||||
-rw-r--r-- | src/opt/nwk/nwk.h | 307 | ||||
-rw-r--r-- | src/opt/nwk/nwkAig.c | 112 | ||||
-rw-r--r-- | src/opt/nwk/nwkBidec.c | 177 | ||||
-rw-r--r-- | src/opt/nwk/nwkCheck.c | 76 | ||||
-rw-r--r-- | src/opt/nwk/nwkDfs.c | 664 | ||||
-rw-r--r-- | src/opt/nwk/nwkFanio.c | 320 | ||||
-rw-r--r-- | src/opt/nwk/nwkFlow.c | 606 | ||||
-rw-r--r-- | src/opt/nwk/nwkFlow_depth.c | 631 | ||||
-rw-r--r-- | src/opt/nwk/nwkMan.c | 278 | ||||
-rw-r--r-- | src/opt/nwk/nwkMap.c | 396 | ||||
-rw-r--r-- | src/opt/nwk/nwkMerge.c | 1044 | ||||
-rw-r--r-- | src/opt/nwk/nwkMerge.h | 153 | ||||
-rw-r--r-- | src/opt/nwk/nwkObj.c | 204 | ||||
-rw-r--r-- | src/opt/nwk/nwkSpeedup.c | 382 | ||||
-rw-r--r-- | src/opt/nwk/nwkStrash.c | 149 | ||||
-rw-r--r-- | src/opt/nwk/nwkTiming.c | 894 | ||||
-rw-r--r-- | src/opt/nwk/nwkUtil.c | 643 | ||||
-rw-r--r-- | src/opt/nwk/nwk_.c | 52 |
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 + |