From 7d0921330b1f4e789901b4c2450920e7c412f95f Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 8 May 2006 08:01:00 -0700 Subject: Version abc60508 --- abc.dsp | 24 +++- src/base/abc/abc.h | 18 +-- src/base/abc/abcAig.c | 31 +++++ src/base/abc/abcCheck.c | 5 +- src/base/abc/abcNames.c | 113 +++++------------ src/base/abc/abcNtk.c | 27 ++-- src/base/abc/abcObj.c | 33 ++++- src/base/abc/abcUtil.c | 51 ++++++++ src/base/abci/abcPrint.c | 2 + src/base/abci/abcProve.c | 4 +- src/base/abci/abcSat.c | 10 +- src/base/io/ioReadBlif.c | 5 +- src/base/io/ioReadEdif.c | 3 +- src/misc/extra/extra.h | 5 + src/misc/extra/extraUtilMemory.c | 21 ++++ src/misc/extra/extraUtilTruth.c | 6 +- src/misc/nm/nm.h | 69 ++++++++++ src/misc/nm/nmApi.c | 262 ++++++++++++++++++++++++++++++++++++++ src/misc/nm/nmInt.h | 86 +++++++++++++ src/misc/nm/nmTable.c | 263 +++++++++++++++++++++++++++++++++++++++ src/opt/cut/cutTruth.c | 11 +- todo.txt | 3 +- 22 files changed, 933 insertions(+), 119 deletions(-) create mode 100644 src/misc/nm/nm.h create mode 100644 src/misc/nm/nmApi.c create mode 100644 src/misc/nm/nmInt.h create mode 100644 src/misc/nm/nmTable.c diff --git a/abc.dsp b/abc.dsp index df2775df..775b88a2 100644 --- a/abc.dsp +++ b/abc.dsp @@ -42,7 +42,7 @@ RSC=rc.exe # PROP Ignore_Export_Lib 0 # PROP Target_Dir "" # ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c -# ADD CPP /nologo /W3 /GX /O2 /I "src\base\abc" /I "src\base\abci" /I "src\base\abcs" /I "src\base\seq" /I "src\base\cmd" /I "src\base\io" /I "src\base\main" /I "src\bdd\cudd" /I "src\bdd\epd" /I "src\bdd\mtr" /I "src\bdd\parse" /I "src\bdd\dsd" /I "src\bdd\reo" /I "src\sop\ft" /I "src\sat\aig" /I "src\sat\asat" /I "src\sat\msat" /I "src\sat\fraig" /I "src\opt\cut" /I "src\opt\dec" /I "src\opt\fxu" /I "src\opt\sim" /I "src\opt\rwr" /I "src\map\fpga" /I "src\map\pga" /I "src\map\mapper" /I "src\map\mio" /I "src\map\super" /I "src\misc\extra" /I "src\misc\st" /I "src\misc\mvc" /I "src\misc\util" /I "src\misc\npn" /I "src\misc\vec" /I "src\misc\espresso" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /D "__STDC__" /FR /YX /FD /c +# ADD CPP /nologo /W3 /GX /O2 /I "src\base\abc" /I "src\base\abci" /I "src\base\abcs" /I "src\base\seq" /I "src\base\cmd" /I "src\base\io" /I "src\base\main" /I "src\bdd\cudd" /I "src\bdd\epd" /I "src\bdd\mtr" /I "src\bdd\parse" /I "src\bdd\dsd" /I "src\bdd\reo" /I "src\sop\ft" /I "src\sat\aig" /I "src\sat\asat" /I "src\sat\msat" /I "src\sat\fraig" /I "src\opt\cut" /I "src\opt\dec" /I "src\opt\fxu" /I "src\opt\sim" /I "src\opt\rwr" /I "src\map\fpga" /I "src\map\pga" /I "src\map\mapper" /I "src\map\mio" /I "src\map\super" /I "src\misc\extra" /I "src\misc\st" /I "src\misc\mvc" /I "src\misc\util" /I "src\misc\npn" /I "src\misc\vec" /I "src\misc\espresso" /I "src\misc\nm" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /D "__STDC__" /FR /YX /FD /c # ADD BASE RSC /l 0x409 /d "NDEBUG" # ADD RSC /l 0x409 /d "NDEBUG" BSC32=bscmake.exe @@ -66,7 +66,7 @@ LINK32=link.exe # PROP Ignore_Export_Lib 0 # PROP Target_Dir "" # ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c -# ADD CPP /nologo /W3 /Gm /GX /ZI /Od /I "src\base\abc" /I "src\base\abci" /I "src\base\abcs" /I "src\base\seq" /I "src\base\cmd" /I "src\base\io" /I "src\base\main" /I "src\bdd\cudd" /I "src\bdd\epd" /I "src\bdd\mtr" /I "src\bdd\parse" /I "src\bdd\dsd" /I "src\bdd\reo" /I "src\sop\ft" /I "src\sat\aig" /I "src\sat\asat" /I "src\sat\msat" /I "src\sat\fraig" /I "src\opt\cut" /I "src\opt\dec" /I "src\opt\fxu" /I "src\opt\sim" /I "src\opt\rwr" /I "src\map\fpga" /I "src\map\pga" /I "src\map\mapper" /I "src\map\mio" /I "src\map\super" /I "src\misc\extra" /I "src\misc\st" /I "src\misc\mvc" /I "src\misc\util" /I "src\misc\npn" /I "src\misc\vec" /I "src\misc\espresso" /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /D "__STDC__" /FR /YX /FD /GZ /c +# ADD CPP /nologo /W3 /Gm /GX /ZI /Od /I "src\base\abc" /I "src\base\abci" /I "src\base\abcs" /I "src\base\seq" /I "src\base\cmd" /I "src\base\io" /I "src\base\main" /I "src\bdd\cudd" /I "src\bdd\epd" /I "src\bdd\mtr" /I "src\bdd\parse" /I "src\bdd\dsd" /I "src\bdd\reo" /I "src\sop\ft" /I "src\sat\aig" /I "src\sat\asat" /I "src\sat\msat" /I "src\sat\fraig" /I "src\opt\cut" /I "src\opt\dec" /I "src\opt\fxu" /I "src\opt\sim" /I "src\opt\rwr" /I "src\map\fpga" /I "src\map\pga" /I "src\map\mapper" /I "src\map\mio" /I "src\map\super" /I "src\misc\extra" /I "src\misc\st" /I "src\misc\mvc" /I "src\misc\util" /I "src\misc\npn" /I "src\misc\vec" /I "src\misc\espresso" /I "src\misc\nm" /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /D "__STDC__" /FR /YX /FD /GZ /c # SUBTRACT CPP /X # ADD BASE RSC /l 0x409 /d "_DEBUG" # ADD RSC /l 0x409 /d "_DEBUG" @@ -2077,6 +2077,26 @@ SOURCE=.\src\misc\espresso\verify.c SOURCE=.\src\misc\util\util_hack.h # End Source File # End Group +# Begin Group "nm" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=.\src\misc\nm\nm.h +# End Source File +# Begin Source File + +SOURCE=.\src\misc\nm\nmApi.c +# End Source File +# Begin Source File + +SOURCE=.\src\misc\nm\nmInt.h +# End Source File +# Begin Source File + +SOURCE=.\src\misc\nm\nmTable.c +# End Source File +# End Group # End Group # End Group # Begin Group "Header Files" diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index 32365b81..1fb57f67 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -40,6 +40,7 @@ extern "C" { #include "solver.h" #include "vec.h" #include "stmm.h" +#include "nm.h" //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// @@ -158,12 +159,13 @@ struct Abc_Ntk_t_ char * pSpec; // the name of the spec file if present int Id; // network ID // name representation - stmm_table * tName2Net; // the table hashing net names into net pointer - stmm_table * tObj2Name; // the table hashing PI/PO/latch pointers into names +// stmm_table * tName2Net; // the table hashing net names into net pointer +// stmm_table * tObj2Name; // the table hashing PI/PO/latch pointers into names // components of the network Vec_Ptr_t * vObjs; // the array of all objects (net, nodes, latches) Vec_Ptr_t * vCis; // the array of combinational inputs (PIs followed by latches) Vec_Ptr_t * vCos; // the array of combinational outputs (POs followed by latches) + Vec_Ptr_t * vAsserts; // the array of assertions Vec_Ptr_t * vLats; // the array of latches (or the cutset in the sequential network) Vec_Ptr_t * vCutSet; // the array of cutset nodes (used in the sequential AIG) // the stats about the number of living objects @@ -174,6 +176,7 @@ struct Abc_Ntk_t_ int nLatches; // the number of live latches int nPis; // the number of primary inputs int nPos; // the number of primary outputs + int nAsserts; // the number of assertion primary outputs // the functionality manager void * pManFunc; // AIG manager, BDD manager, or memory manager for SOPs // the global functions (BDDs) @@ -198,6 +201,8 @@ struct Abc_Ntk_t_ Vec_Int_t * vIntTemp; // the temporary array Vec_Str_t * vStrTemp; // the temporary array void * pData; // the temporary pointer + // name manager + Nm_Man_t * pManName; // the backup network and the step number Abc_Ntk_t * pNetBackup; // the pointer to the previous backup network int iStep; // the generation number for the given network @@ -207,7 +212,7 @@ struct Abc_Ntk_t_ short fHieVisited; // flag to mark the visited network short fHiePath; // flag to mark the network on the path // memory management - Extra_MmFlex_t * pMmNames; // memory manager for net names +// Extra_MmFlex_t * pMmNames; // memory manager for net names Extra_MmFixed_t* pMmObj; // memory manager for objects Extra_MmStep_t * pMmStep; // memory manager for arrays }; @@ -540,15 +545,13 @@ extern Abc_Obj_t * Abc_ObjAlloc( Abc_Ntk_t * pNtk, Abc_ObjType_t Type ); extern void Abc_ObjRecycle( Abc_Obj_t * pObj ); extern void Abc_ObjAdd( Abc_Obj_t * pObj ); /*=== abcNames.c ====================================================*/ -extern char * Abc_NtkRegisterName( Abc_Ntk_t * pNtk, char * pName ); -extern char * Abc_NtkRegisterNamePlus( Abc_Ntk_t * pNtk, char * pName, char * pSuffix ); +//extern char * Abc_NtkRegisterName( Abc_Ntk_t * pNtk, char * pName ); +//extern char * Abc_NtkRegisterNamePlus( Abc_Ntk_t * pNtk, char * pName, char * pSuffix ); extern char * Abc_ObjName( Abc_Obj_t * pNode ); extern char * Abc_ObjNameSuffix( Abc_Obj_t * pObj, char * pSuffix ); -extern char * Abc_ObjNameUnique( Abc_Ntk_t * pNtk, char * pName ); extern char * Abc_ObjNameDummy( char * pPrefix, int Num, int nDigits ); extern char * Abc_NtkLogicStoreName( Abc_Obj_t * pNodeNew, char * pNameOld ); extern char * Abc_NtkLogicStoreNamePlus( Abc_Obj_t * pNodeNew, char * pNameOld, char * pSuffix ); -extern void Abc_NtkCreateCioNamesTable( Abc_Ntk_t * pNtk ); extern void Abc_NtkDupCioNamesTable( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ); extern void Abc_NtkDupCioNamesTableDual( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ); extern Vec_Ptr_t * Abc_NodeGetFaninNames( Abc_Obj_t * pNode ); @@ -561,7 +564,6 @@ extern void Abc_NtkAddDummyPiNames( Abc_Ntk_t * pNtk ); extern void Abc_NtkAddDummyPoNames( Abc_Ntk_t * pNtk ); extern void Abc_NtkAddDummyLatchNames( Abc_Ntk_t * pNtk ); extern void Abc_NtkShortNames( Abc_Ntk_t * pNtk ); -extern stmm_table * Abc_NtkNamesToTable( Vec_Ptr_t * vNodes ); /*=== abcNetlist.c ==========================================================*/ extern Abc_Ntk_t * Abc_NtkNetlistToLogic( Abc_Ntk_t * pNtk ); extern Abc_Ntk_t * Abc_NtkLogicToNetlist( Abc_Ntk_t * pNtk, int fDirect ); diff --git a/src/base/abc/abcAig.c b/src/base/abc/abcAig.c index 0d75eb76..f1171992 100644 --- a/src/base/abc/abcAig.c +++ b/src/base/abc/abcAig.c @@ -58,6 +58,11 @@ struct Abc_Aig_t_ Vec_Ptr_t * vStackReplaceNew; // the nodes to be used for replacement Vec_Vec_t * vLevels; // the nodes to be updated Vec_Vec_t * vLevelsR; // the nodes to be updated + + int nStrash0; + int nStrash1; + int nStrash5; + int nStrash2; }; // iterators through the entries in the linked lists of nodes @@ -164,6 +169,8 @@ int Abc_AigCleanup( Abc_Aig_t * pMan ) Vec_Ptr_t * vDangles; Abc_Obj_t * pAnd; int i, nNodesOld; +// printf( "Strash0 = %d. Strash1 = %d. Strash100 = %d. StrashM = %d.\n", +// pMan->nStrash0, pMan->nStrash1, pMan->nStrash5, pMan->nStrash2 ); nNodesOld = pMan->nEntries; // collect the AND nodes that do not fanout vDangles = Vec_PtrAlloc( 100 ); @@ -369,6 +376,27 @@ Abc_Obj_t * Abc_AigAndLookup( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 ) return p0; return Abc_ObjNot(pConst1); } +/* + { + int nFans0 = Abc_ObjFanoutNum( Abc_ObjRegular(p0) ); + int nFans1 = Abc_ObjFanoutNum( Abc_ObjRegular(p1) ); + if ( nFans0 == 0 || nFans1 == 0 ) + pMan->nStrash0++; + else if ( nFans0 == 1 || nFans1 == 1 ) + pMan->nStrash1++; + else if ( nFans0 <= 100 && nFans1 <= 100 ) + pMan->nStrash5++; + else + pMan->nStrash2++; + } +*/ + { + int nFans0 = Abc_ObjFanoutNum( Abc_ObjRegular(p0) ); + int nFans1 = Abc_ObjFanoutNum( Abc_ObjRegular(p1) ); + if ( nFans0 == 0 || nFans1 == 0 ) + return NULL; + } + // order the arguments if ( Abc_ObjRegular(p0)->Id > Abc_ObjRegular(p1)->Id ) pAnd = p0, p0 = p1, p1 = pAnd; @@ -377,7 +405,10 @@ Abc_Obj_t * Abc_AigAndLookup( Abc_Aig_t * pMan, Abc_Obj_t * p0, Abc_Obj_t * p1 ) // find the matching node in the table Abc_AigBinForEachEntry( pMan->pBins[Key], pAnd ) if ( p0 == Abc_ObjChild0(pAnd) && p1 == Abc_ObjChild1(pAnd) ) + { +// assert( Abc_ObjFanoutNum(Abc_ObjRegular(p0)) && Abc_ObjFanoutNum(p1) ); return pAnd; + } return NULL; } diff --git a/src/base/abc/abcCheck.c b/src/base/abc/abcCheck.c index 5c152409..49e0e825 100644 --- a/src/base/abc/abcCheck.c +++ b/src/base/abc/abcCheck.c @@ -233,6 +233,7 @@ bool Abc_NtkCheckNames( Abc_Ntk_t * pNtk ) if ( Abc_NtkIsNetlist(pNtk) ) { +/* // check that the nets in the table are also in the network stmm_foreach_item( pNtk->tName2Net, gen, &pName, (char**)&pNet ) { @@ -251,8 +252,9 @@ bool Abc_NtkCheckNames( Abc_Ntk_t * pNtk ) return 0; } } +*/ } - +/* // check PI/PO/latch names Abc_NtkForEachPi( pNtk, pObj, i ) { @@ -293,6 +295,7 @@ bool Abc_NtkCheckNames( Abc_Ntk_t * pNtk ) return 0; } } +*/ return 1; } diff --git a/src/base/abc/abcNames.c b/src/base/abc/abcNames.c index 14f0b505..f9fbe9db 100644 --- a/src/base/abc/abcNames.c +++ b/src/base/abc/abcNames.c @@ -44,11 +44,14 @@ ***********************************************************************/ char * Abc_NtkRegisterName( Abc_Ntk_t * pNtk, char * pName ) { +/* char * pRegName; if ( pName == NULL ) return NULL; pRegName = Extra_MmFlexEntryFetch( pNtk->pMmNames, strlen(pName) + 1 ); strcpy( pRegName, pName ); return pRegName; +*/ + return NULL; } /**Function************************************************************* @@ -64,11 +67,14 @@ char * Abc_NtkRegisterName( Abc_Ntk_t * pNtk, char * pName ) ***********************************************************************/ char * Abc_NtkRegisterNamePlus( Abc_Ntk_t * pNtk, char * pName, char * pSuffix ) { +/* char * pRegName; assert( pName && pSuffix ); pRegName = Extra_MmFlexEntryFetch( pNtk->pMmNames, strlen(pName) + strlen(pSuffix) + 1 ); sprintf( pRegName, "%s%s", pName, pSuffix ); return pRegName; +*/ + return NULL; } /**Function************************************************************* @@ -90,7 +96,9 @@ char * Abc_ObjName( Abc_Obj_t * pObj ) char * pName; // check if the object is in the lookup table - if ( stmm_lookup( pObj->pNtk->tObj2Name, (char *)pObj, &pName ) ) +// if ( stmm_lookup( pObj->pNtk->tObj2Name, (char *)pObj, &pName ) ) +// return pName; + if ( pName = Nm_ManFindNameById(pObj->pNtk->pManName, pObj->Id) ) return pName; // consider network types @@ -134,33 +142,6 @@ char * Abc_ObjNameSuffix( Abc_Obj_t * pObj, char * pSuffix ) return Buffer; } -/**Function************************************************************* - - Synopsis [Finds a unique name for the node.] - - Description [If the name exists, tries appending numbers to it until - it becomes unique.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -char * Abc_ObjNameUnique( Abc_Ntk_t * pNtk, char * pName ) -{ - static char Buffer[1000]; - int Counter; - assert( 0 ); - if ( !stmm_is_member( pNtk->tName2Net, pName ) ) - return pName; - for ( Counter = 1; ; Counter++ ) - { - sprintf( Buffer, "%s_%d", pName, Counter ); - if ( !stmm_is_member( pNtk->tName2Net, Buffer ) ) - return Buffer; - } - return NULL; -} /**Function************************************************************* @@ -195,6 +176,7 @@ char * Abc_ObjNameDummy( char * pPrefix, int Num, int nDigits ) ***********************************************************************/ char * Abc_NtkLogicStoreName( Abc_Obj_t * pObjNew, char * pNameOld ) { +/* char * pNewName; assert( Abc_ObjIsCio(pObjNew) ); // get the new name @@ -205,6 +187,9 @@ char * Abc_NtkLogicStoreName( Abc_Obj_t * pObjNew, char * pNameOld ) assert( 0 ); // the object is added for the second time } return pNewName; +*/ + Nm_ManStoreIdName( pObjNew->pNtk->pManName, pObjNew->Id, pNameOld, NULL ); + return NULL; } /**Function************************************************************* @@ -220,6 +205,7 @@ char * Abc_NtkLogicStoreName( Abc_Obj_t * pObjNew, char * pNameOld ) ***********************************************************************/ char * Abc_NtkLogicStoreNamePlus( Abc_Obj_t * pObjNew, char * pNameOld, char * pSuffix ) { +/* char * pNewName; assert( pSuffix ); assert( Abc_ObjIsCio(pObjNew) ); @@ -231,31 +217,9 @@ char * Abc_NtkLogicStoreNamePlus( Abc_Obj_t * pObjNew, char * pNameOld, char * p assert( 0 ); // the object is added for the second time } return pNewName; -} - -/**Function************************************************************* - - Synopsis [Creates the name arrays from the old network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkCreateCioNamesTable( Abc_Ntk_t * pNtk ) -{ - Abc_Obj_t * pObj; - int i; - assert( Abc_NtkIsNetlist(pNtk) ); - assert( st_count(pNtk->tObj2Name) == 0 ); - Abc_NtkForEachPi( pNtk, pObj, i ) - Abc_NtkLogicStoreName( pObj, Abc_ObjFanout0(pObj)->pData ); - Abc_NtkForEachPo( pNtk, pObj, i ) - Abc_NtkLogicStoreName( pObj, Abc_ObjFanin0(pObj)->pData ); - Abc_NtkForEachLatch( pNtk, pObj, i ) - Abc_NtkLogicStoreName( pObj, Abc_ObjFanout0(pObj)->pData ); +*/ + Nm_ManStoreIdName( pObjNew->pNtk->pManName, pObjNew->Id, pNameOld, pSuffix ); + return NULL; } /**Function************************************************************* @@ -276,16 +240,16 @@ void Abc_NtkDupCioNamesTable( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ) assert( Abc_NtkPiNum(pNtk) == Abc_NtkPiNum(pNtkNew) ); assert( Abc_NtkPoNum(pNtk) == Abc_NtkPoNum(pNtkNew) ); assert( Abc_NtkLatchNum(pNtk) == Abc_NtkLatchNum(pNtkNew) ); - assert( st_count(pNtk->tObj2Name) > 0 ); - assert( st_count(pNtkNew->tObj2Name) == 0 ); +// assert( st_count(pNtk->tObj2Name) > 0 ); +// assert( st_count(pNtkNew->tObj2Name) == 0 ); // copy the CI/CO names if given Abc_NtkForEachPi( pNtk, pObj, i ) - Abc_NtkLogicStoreName( Abc_NtkPi(pNtkNew,i), Abc_ObjName(pObj) ); + Abc_NtkLogicStoreName( Abc_NtkPi(pNtkNew,i), Abc_ObjName(Abc_ObjFanout0Ntk(pObj)) ); Abc_NtkForEachPo( pNtk, pObj, i ) - Abc_NtkLogicStoreName( Abc_NtkPo(pNtkNew,i), Abc_ObjName(pObj) ); + Abc_NtkLogicStoreName( Abc_NtkPo(pNtkNew,i), Abc_ObjName(Abc_ObjFanin0Ntk(pObj)) ); if ( !Abc_NtkIsSeq(pNtk) ) Abc_NtkForEachLatch( pNtk, pObj, i ) - Abc_NtkLogicStoreName( Abc_NtkLatch(pNtkNew,i), Abc_ObjName(pObj) ); + Abc_NtkLogicStoreName( Abc_NtkLatch(pNtkNew,i), Abc_ObjName(Abc_ObjFanout0Ntk(pObj)) ); } /**Function************************************************************* @@ -306,8 +270,8 @@ void Abc_NtkDupCioNamesTableDual( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ) assert( Abc_NtkPiNum(pNtk) == Abc_NtkPiNum(pNtkNew) ); assert( Abc_NtkPoNum(pNtk) * 2 == Abc_NtkPoNum(pNtkNew) ); assert( Abc_NtkLatchNum(pNtk) == Abc_NtkLatchNum(pNtkNew) ); - assert( st_count(pNtk->tObj2Name) > 0 ); - assert( st_count(pNtkNew->tObj2Name) == 0 ); +// assert( st_count(pNtk->tObj2Name) > 0 ); +// assert( st_count(pNtkNew->tObj2Name) == 0 ); // copy the CI/CO names if given Abc_NtkForEachPi( pNtk, pObj, i ) Abc_NtkLogicStoreName( Abc_NtkPi(pNtkNew,i), Abc_ObjName(pObj) ); @@ -573,35 +537,16 @@ void Abc_NtkAddDummyLatchNames( Abc_Ntk_t * pNtk ) ***********************************************************************/ void Abc_NtkShortNames( Abc_Ntk_t * pNtk ) { - stmm_free_table( pNtk->tObj2Name ); - pNtk->tObj2Name = stmm_init_table(stmm_ptrcmp, stmm_ptrhash); +// stmm_free_table( pNtk->tObj2Name ); +// pNtk->tObj2Name = stmm_init_table(stmm_ptrcmp, stmm_ptrhash); + Nm_ManFree( pNtk->pManName ); + pNtk->pManName = Nm_ManCreate( Abc_NtkPiNum(pNtk) + Abc_NtkPoNum(pNtk) + Abc_NtkLatchNum(pNtk) + 10 ); + Abc_NtkAddDummyPiNames( pNtk ); Abc_NtkAddDummyPoNames( pNtk ); Abc_NtkAddDummyLatchNames( pNtk ); } -/**Function************************************************************* - - Synopsis [Returns the hash table with these names.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -stmm_table * Abc_NtkNamesToTable( Vec_Ptr_t * vNodes ) -{ - stmm_table * tTable; - Abc_Obj_t * pObj; - int i; - tTable = stmm_init_table(strcmp, stmm_strhash); - Vec_PtrForEachEntry( vNodes, pObj, i ) - stmm_insert( tTable, Abc_ObjName(pObj), (char *)pObj ); - return tTable; -} - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abc/abcNtk.c b/src/base/abc/abcNtk.c index 0640d661..c8bdf987 100644 --- a/src/base/abc/abcNtk.c +++ b/src/base/abc/abcNtk.c @@ -57,14 +57,15 @@ Abc_Ntk_t * Abc_NtkAlloc( Abc_NtkType_t Type, Abc_NtkFunc_t Func ) pNtk->vCutSet = Vec_PtrAlloc( 100 ); pNtk->vCis = Vec_PtrAlloc( 100 ); pNtk->vCos = Vec_PtrAlloc( 100 ); + pNtk->vAsserts = Vec_PtrAlloc( 100 ); pNtk->vPtrTemp = Vec_PtrAlloc( 100 ); pNtk->vIntTemp = Vec_IntAlloc( 100 ); pNtk->vStrTemp = Vec_StrAlloc( 100 ); // start the hash table - pNtk->tName2Net = stmm_init_table(strcmp, stmm_strhash); - pNtk->tObj2Name = stmm_init_table(stmm_ptrcmp, stmm_ptrhash); +// pNtk->tName2Net = stmm_init_table(strcmp, stmm_strhash); +// pNtk->tObj2Name = stmm_init_table(stmm_ptrcmp, stmm_ptrhash); // start the memory managers - pNtk->pMmNames = Extra_MmFlexStart(); +// pNtk->pMmNames = Extra_MmFlexStart(); pNtk->pMmObj = Extra_MmFixedStart( sizeof(Abc_Obj_t) ); pNtk->pMmStep = Extra_MmStepStart( ABC_NUM_STEPS ); // get ready to assign the first Obj ID @@ -94,6 +95,9 @@ Abc_Ntk_t * Abc_NtkAlloc( Abc_NtkType_t Type, Abc_NtkFunc_t Func ) } else Vec_PtrPush( pNtk->vObjs, NULL ); + // name manager + pNtk->pManName = Nm_ManCreate( 1000 ); +//printf( "Allocated newtork %p\n", pNtk ); return pNtk; } @@ -146,7 +150,8 @@ Abc_Ntk_t * Abc_NtkStartFrom( Abc_Ntk_t * pNtk, Abc_NtkType_t Type, Abc_NtkFunc_ Abc_HManAddProto( pObj->pCopy, pObj ); } // transfer the names - Abc_NtkDupCioNamesTable( pNtk, pNtkNew ); + if ( Type != ABC_NTK_NETLIST ) + Abc_NtkDupCioNamesTable( pNtk, pNtkNew ); Abc_ManTimeDup( pNtk, pNtkNew ); // check that the CI/CO/latches are copied correctly assert( Abc_NtkCiNum(pNtk) == Abc_NtkCiNum(pNtkNew) ); @@ -335,7 +340,7 @@ void Abc_NtkFinalizeRead( Abc_Ntk_t * pNtk ) // fix the net drivers Abc_NtkFixNonDrivenNets( pNtk ); // create the names table - Abc_NtkCreateCioNamesTable( pNtk ); +// Abc_NtkCreateCioNamesTable( pNtk ); // add latches to the CI/CO arrays Abc_NtkForEachLatch( pNtk, pLatch, i ) { @@ -735,6 +740,7 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) int LargePiece = (4 << ABC_NUM_STEPS); if ( pNtk == NULL ) return; +//printf( "Deleted newtork %p\n", pNtk ); // make sure all the marks are clean Abc_NtkForEachObj( pNtk, pObj, i ) { @@ -761,6 +767,7 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) // free the arrays Vec_PtrFree( pNtk->vCis ); Vec_PtrFree( pNtk->vCos ); + Vec_PtrFree( pNtk->vAsserts ); Vec_PtrFree( pNtk->vObjs ); Vec_PtrFree( pNtk->vLats ); Vec_PtrFree( pNtk->vCutSet ); @@ -769,15 +776,15 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) Vec_StrFree( pNtk->vStrTemp ); if ( pNtk->pModel ) free( pNtk->pModel ); // free the hash table of Obj name into Obj ID - stmm_free_table( pNtk->tName2Net ); - stmm_free_table( pNtk->tObj2Name ); +// stmm_free_table( pNtk->tName2Net ); +// stmm_free_table( pNtk->tObj2Name ); TotalMemory = 0; - TotalMemory += Extra_MmFlexReadMemUsage(pNtk->pMmNames); +// TotalMemory += Extra_MmFlexReadMemUsage(pNtk->pMmNames); TotalMemory += Extra_MmFixedReadMemUsage(pNtk->pMmObj); TotalMemory += Extra_MmStepReadMemUsage(pNtk->pMmStep); // fprintf( stdout, "The total memory allocated internally by the network = %0.2f Mb.\n", ((double)TotalMemory)/(1<<20) ); // free the storage - Extra_MmFlexStop ( pNtk->pMmNames, 0 ); +// Extra_MmFlexStop ( pNtk->pMmNames, 0 ); Extra_MmFixedStop( pNtk->pMmObj, 0 ); Extra_MmStepStop ( pNtk->pMmStep, 0 ); // free the timing manager @@ -797,6 +804,8 @@ void Abc_NtkDelete( Abc_Ntk_t * pNtk ) } else if ( !Abc_NtkHasMapping(pNtk) ) assert( 0 ); + // name manager + Nm_ManFree( pNtk->pManName ); // free the hierarchy if ( Abc_NtkIsNetlist(pNtk) && pNtk->tName2Model ) { diff --git a/src/base/abc/abcObj.c b/src/base/abc/abcObj.c index 4be253d1..56fcef95 100644 --- a/src/base/abc/abcObj.c +++ b/src/base/abc/abcObj.c @@ -101,12 +101,14 @@ void Abc_ObjAdd( Abc_Obj_t * pObj ) // perform specialized operations depending on the object type if ( Abc_ObjIsNet(pObj) ) { +/* // add the name to the table if ( pObj->pData && stmm_insert( pNtk->tName2Net, pObj->pData, (char *)pObj ) ) { printf( "Error: The net is already in the table...\n" ); assert( 0 ); } +*/ pNtk->nNets++; } else if ( Abc_ObjIsNode(pObj) ) @@ -169,12 +171,19 @@ Abc_Obj_t * Abc_NtkDupObj( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj ) } } else if ( Abc_ObjIsNet(pObj) ) // copy the name - pObjNew->pData = Abc_NtkRegisterName( pNtkNew, pObj->pData ); + { +// pObjNew->pData = Abc_NtkRegisterName( pNtkNew, pObj->pData ); + } else if ( Abc_ObjIsLatch(pObj) ) // copy the reset value pObjNew->pData = pObj->pData; pObj->pCopy = pObjNew; // add the object to the network Abc_ObjAdd( pObjNew ); + + + if ( Abc_ObjIsNet(pObj) ) + pObjNew->pData = Nm_ManStoreIdName( pNtkNew->pManName, pObjNew->Id, pObj->pData, NULL ); + return pObjNew; } @@ -214,12 +223,15 @@ void Abc_NtkDeleteObj( Abc_Obj_t * pObj ) // perform specialized operations depending on the object type if ( Abc_ObjIsNet(pObj) ) { + assert( 0 ); +/* // remove the net from the hash table of nets if ( pObj->pData && !stmm_delete( pNtk->tName2Net, (char **)&pObj->pData, (char **)&pObj ) ) { printf( "Error: The net is not in the table...\n" ); assert( 0 ); } +*/ pObj->pData = NULL; pNtk->nNets--; } @@ -238,11 +250,15 @@ void Abc_NtkDeleteObj( Abc_Obj_t * pObj ) assert( Abc_NtkPoNum(pObj->pNtk) > 0 ); Vec_PtrRemove( pObj->pNtk->vCos, pObj ); pObj->pNtk->nPos--; + + assert( 0 ); +/* // add the name to the table if ( !stmm_delete( pObj->pNtk->tObj2Name, (char **)&pObj, NULL ) ) { assert( 0 ); // the PO is not in the table } +*/ } else assert( 0 ); @@ -359,10 +375,16 @@ Abc_Obj_t * Abc_NtkFindCo( Abc_Ntk_t * pNtk, char * pName ) Abc_Obj_t * Abc_NtkFindNet( Abc_Ntk_t * pNtk, char * pName ) { Abc_Obj_t * pNet; + int ObjId; assert( Abc_NtkIsNetlist(pNtk) ); - if ( stmm_lookup( pNtk->tName2Net, pName, (char**)&pNet ) ) - return pNet; - return NULL; +// if ( stmm_lookup( pNtk->tName2Net, pName, (char**)&pNet ) ) +// return pNet; +// return NULL; + ObjId = Nm_ManFindIdByName( pNtk->pManName, pName, NULL ); + if ( ObjId == -1 ) + return NULL; + pNet = Abc_NtkObj( pNtk, ObjId ); + return pNet; } /**Function************************************************************* @@ -384,8 +406,9 @@ Abc_Obj_t * Abc_NtkFindOrCreateNet( Abc_Ntk_t * pNtk, char * pName ) return pNet; // create a new net pNet = Abc_ObjAlloc( pNtk, ABC_OBJ_NET ); - pNet->pData = Abc_NtkRegisterName( pNtk, pName ); +// pNet->pData = Abc_NtkRegisterName( pNtk, pName ); Abc_ObjAdd( pNet ); + pNet->pData = Nm_ManStoreIdName( pNtk->pManName, pNet->Id, pName, NULL ); return pNet; } diff --git a/src/base/abc/abcUtil.c b/src/base/abc/abcUtil.c index 8449c91d..034aa38f 100644 --- a/src/base/abc/abcUtil.c +++ b/src/base/abc/abcUtil.c @@ -1064,6 +1064,57 @@ void Abc_NtkReassignIds( Abc_Ntk_t * pNtk ) Abc_AigRehash( pNtk->pManFunc ); } +/**Function************************************************************* + + Synopsis [Detect cases when non-trivial FF matching is possible.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkDetectMatching( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pLatch, * pFanin; + int i, nTFFs, nJKFFs; + nTFFs = nJKFFs = 0; + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + pFanin = Abc_ObjFanin0(pLatch); + if ( Abc_ObjFaninNum(pFanin) != 2 ) + continue; + if ( Abc_NodeIsExorType(pLatch) ) + { + if ( Abc_ObjFanin0(Abc_ObjFanin0(pFanin)) == pLatch || + Abc_ObjFanin1(Abc_ObjFanin0(pFanin)) == pLatch ) + nTFFs++; + } + if ( Abc_ObjFaninNum( Abc_ObjFanin0(pFanin) ) != 2 || + Abc_ObjFaninNum( Abc_ObjFanin1(pFanin) ) != 2 ) + continue; + +/* + if ( !Abc_ObjFaninC0(pLatch) || + !Abc_ObjFaninC0( Abc_ObjFanin0(pFanin) ) || + !Abc_ObjFaninC1( Abc_ObjFanin0(pFanin) ) ) + continue; +*/ + + if ( (Abc_ObjFanin0(Abc_ObjFanin0(pFanin)) == pLatch || + Abc_ObjFanin1(Abc_ObjFanin0(pFanin)) == pLatch) && + (Abc_ObjFanin0(Abc_ObjFanin1(pFanin)) == pLatch || + Abc_ObjFanin1(Abc_ObjFanin1(pFanin)) == pLatch) ) + { + nJKFFs++; + } + } + printf( "D = %6d. T = %6d. JK = %6d. (%6.2f %%)\n", + Abc_NtkLatchNum(pNtk), nTFFs, nJKFFs, 100.0 * nJKFFs / Abc_NtkLatchNum(pNtk) ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/base/abci/abcPrint.c b/src/base/abci/abcPrint.c index d7b270bf..2aad721b 100644 --- a/src/base/abci/abcPrint.c +++ b/src/base/abci/abcPrint.c @@ -50,6 +50,8 @@ void Abc_NtkPrintStats( FILE * pFile, Abc_Ntk_t * pNtk, int fFactored ) { int Num, Num2; +// Abc_NtkDetectMatching( pNtk ); +// return; fprintf( pFile, "%-13s:", pNtk->pName ); fprintf( pFile, " i/o = %4d/%4d", Abc_NtkPiNum(pNtk), Abc_NtkPoNum(pNtk) ); diff --git a/src/base/abci/abcProve.c b/src/base/abci/abcProve.c index c0e904bf..23315223 100644 --- a/src/base/abci/abcProve.c +++ b/src/base/abci/abcProve.c @@ -140,8 +140,9 @@ int Abc_NtkMiterProve( Abc_Ntk_t ** ppNtk, void * pPars ) if ( RetValue >= 0 ) break; } - } + } +/* // try to prove it using brute force SAT if ( RetValue < 0 && pParams->fUseBdds ) { @@ -161,6 +162,7 @@ int Abc_NtkMiterProve( Abc_Ntk_t ** ppNtk, void * pPars ) pNtk = pNtkTemp; Abc_NtkMiterPrint( pNtk, "BDD building", clk, pParams->fVerbose ); } +*/ if ( RetValue < 0 ) { diff --git a/src/base/abci/abcSat.c b/src/base/abci/abcSat.c index 9348231b..06376eed 100644 --- a/src/base/abci/abcSat.c +++ b/src/base/abci/abcSat.c @@ -422,7 +422,15 @@ int Abc_NtkMiterSatCreateInt( solver * pSat, Abc_Ntk_t * pNtk, int fJFront ) pNode->pCopy = (Abc_Obj_t *)vNodes->nSize; Vec_PtrPush( vNodes, pNode ); Abc_NtkClauseTriv( pSat, pNode, vVars ); - +/* + // add the PI variables first + Abc_NtkForEachCi( pNtk, pNode, i ) + { + pNode->fMarkA = 1; + pNode->pCopy = (Abc_Obj_t *)vNodes->nSize; + Vec_PtrPush( vNodes, pNode ); + } +*/ // collect the nodes that need clauses and top-level assignments Abc_NtkForEachCo( pNtk, pNode, i ) { diff --git a/src/base/io/ioReadBlif.c b/src/base/io/ioReadBlif.c index f6d92af7..3d33e6a3 100644 --- a/src/base/io/ioReadBlif.c +++ b/src/base/io/ioReadBlif.c @@ -216,6 +216,8 @@ Abc_Ntk_t * Io_ReadBlifNetworkOne( Io_ReadBlif_t * p ) { printf( "%s: File parsing skipped after line %d (\"%s\").\n", p->pFileName, Extra_FileReaderGetLineNumber(p->pReader, 0), p->vTokens->pArray[0] ); + Abc_NtkDelete(pNtk); + p->pNtkCur = NULL; return NULL; } @@ -573,7 +575,8 @@ int Io_ReadBlifNetworkSubcircuit( Io_ReadBlif_t * p, Vec_Ptr_t * vTokens ) // store the names of formal/actual inputs/outputs of the box vNames = Vec_PtrAlloc( 10 ); Vec_PtrForEachEntryStart( vTokens, pName, i, 1 ) - Vec_PtrPush( vNames, Abc_NtkRegisterName(p->pNtkCur, pName) ); +// Vec_PtrPush( vNames, Abc_NtkRegisterName(p->pNtkCur, pName) ); + Vec_PtrPush( vNames, Extra_UtilStrsav(pName) ); // memory leak!!! // create a new box and add it to the network pBox = Abc_NtkCreateBox( p->pNtkCur ); diff --git a/src/base/io/ioReadEdif.c b/src/base/io/ioReadEdif.c index 3bdf2567..7c447523 100644 --- a/src/base/io/ioReadEdif.c +++ b/src/base/io/ioReadEdif.c @@ -121,7 +121,8 @@ Abc_Ntk_t * Io_ReadEdifNetwork( Extra_FileReader_t * p ) else { pObj = Abc_NtkCreateNode( pNtk ); - pObj->pData = Abc_NtkRegisterName( pNtk, pGateName ); +// pObj->pData = Abc_NtkRegisterName( pNtk, pGateName ); + pObj->pData = Extra_UtilStrsav( pGateName ); // memory leak!!! } Abc_ObjAddFanin( pNet, pObj ); } diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h index e02ec82a..6336f5ea 100644 --- a/src/misc/extra/extra.h +++ b/src/misc/extra/extra.h @@ -41,6 +41,10 @@ extern "C" { /* Nested includes */ /*---------------------------------------------------------------------------*/ +// this include should be the first one in the list +// it is used to catch memory leaks on Windows +#include "leaks.h" + #include #include #include @@ -463,6 +467,7 @@ extern unsigned Extra_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, i (obj) ? ((type *) realloc((char *) obj, sizeof(type) * (num))) : \ ((type *) malloc(sizeof(type) * (num))) + extern long Extra_CpuTime(); extern int Extra_GetSoftDataLimit(); extern void Extra_UtilGetoptReset(); diff --git a/src/misc/extra/extraUtilMemory.c b/src/misc/extra/extraUtilMemory.c index c9137c56..768f86fa 100644 --- a/src/misc/extra/extraUtilMemory.c +++ b/src/misc/extra/extraUtilMemory.c @@ -73,6 +73,9 @@ struct Extra_MmStep_t_ Extra_MmFixed_t ** pMems; // memory managers: 2^1 words, 2^2 words, etc int nMapSize; // the size of the memory array Extra_MmFixed_t ** pMap; // maps the number of bytes into its memory manager + int nLargeChunksAlloc; // the maximum number of large memory chunks + int nLargeChunks; // the current number of large memory chunks + void ** pLargeChunks; // the allocated large memory chunks }; /*---------------------------------------------------------------------------*/ @@ -448,6 +451,7 @@ Extra_MmStep_t * Extra_MmStepStart( int nSteps ) Extra_MmStep_t * p; int i, k; p = ALLOC( Extra_MmStep_t, 1 ); + memset( p, 0, sizeof(Extra_MmStep_t) ); p->nMems = nSteps; // start the fixed memory managers p->pMems = ALLOC( Extra_MmFixed_t *, p->nMems ); @@ -483,6 +487,12 @@ void Extra_MmStepStop( Extra_MmStep_t * p, int fVerbose ) int i; for ( i = 0; i < p->nMems; i++ ) Extra_MmFixedStop( p->pMems[i], fVerbose ); +// if ( p->pLargeChunks ) +// { +// for ( i = 0; i < p->nLargeChunks; i++ ) +// free( p->pLargeChunks[i] ); +// free( p->pLargeChunks ); +// } free( p->pMems ); free( p->pMap ); free( p ); @@ -506,6 +516,17 @@ char * Extra_MmStepEntryFetch( Extra_MmStep_t * p, int nBytes ) if ( nBytes > p->nMapSize ) { // printf( "Allocating %d bytes.\n", nBytes ); +/* + if ( p->nLargeChunks == p->nLargeChunksAlloc ) + { + if ( p->nLargeChunksAlloc == 0 ) + p->nLargeChunksAlloc = 5; + p->nLargeChunksAlloc *= 2; + p->pLargeChunks = REALLOC( char *, p->pLargeChunks, p->nLargeChunksAlloc ); + } + p->pLargeChunks[ p->nLargeChunks++ ] = ALLOC( char, nBytes ); + return p->pLargeChunks[ p->nLargeChunks - 1 ]; +*/ return ALLOC( char, nBytes ); } return Extra_MmFixedEntryFetch( p->pMap[nBytes] ); diff --git a/src/misc/extra/extraUtilTruth.c b/src/misc/extra/extraUtilTruth.c index 2d6f307c..74308ab2 100644 --- a/src/misc/extra/extraUtilTruth.c +++ b/src/misc/extra/extraUtilTruth.c @@ -706,23 +706,27 @@ int Extra_TruthMinCofSuppOverlap( unsigned * pTruth, int nVars, int * pVarMin ) static unsigned uCofactor[16]; int i, ValueCur, ValueMin, VarMin; unsigned uSupp0, uSupp1; + int nVars0, nVars1; assert( nVars <= 9 ); ValueMin = 32; + VarMin = -1; for ( i = 0; i < nVars; i++ ) { // get negative cofactor Extra_TruthCopy( uCofactor, pTruth, nVars ); Extra_TruthCofactor0( uCofactor, nVars, i ); uSupp0 = Extra_TruthSupport( uCofactor, nVars ); + nVars0 = Extra_WordCountOnes( uSupp0 ); //Extra_PrintBinary( stdout, &uSupp0, 8 ); printf( "\n" ); // get positive cofactor Extra_TruthCopy( uCofactor, pTruth, nVars ); Extra_TruthCofactor1( uCofactor, nVars, i ); uSupp1 = Extra_TruthSupport( uCofactor, nVars ); + nVars1 = Extra_WordCountOnes( uSupp1 ); //Extra_PrintBinary( stdout, &uSupp1, 8 ); printf( "\n" ); // get the number of common vars ValueCur = Extra_WordCountOnes( uSupp0 & uSupp1 ); - if ( ValueMin > ValueCur ) + if ( ValueMin > ValueCur && nVars0 <= 5 && nVars1 <= 5 ) { ValueMin = ValueCur; VarMin = i; diff --git a/src/misc/nm/nm.h b/src/misc/nm/nm.h new file mode 100644 index 00000000..5b17aaed --- /dev/null +++ b/src/misc/nm/nm.h @@ -0,0 +1,69 @@ +/**CFilextern e**************************************************************** + + FileName [nm.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Name manager.] + + Synopsis [External declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: nm.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __NM_H__ +#define __NM_H__ + +#ifdef __cplusplus +extern "C" { +#endif + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Nm_Man_t_ Nm_Man_t; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== nmApi.c ==========================================================*/ +extern Nm_Man_t * Nm_ManCreate( int nSize ); +extern void Nm_ManFree( Nm_Man_t * p ); +extern int Nm_ManNumEntries( Nm_Man_t * p ); +extern char * Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, char * pName, char * pSuffix ); +extern char * Nm_ManCreateUniqueName( Nm_Man_t * p, int ObjId ); +extern char * Nm_ManFindNameById( Nm_Man_t * p, int ObjId ); +extern int Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int * pSecond ); +extern void Nm_ManPrintTables( Nm_Man_t * p ); + +#ifdef __cplusplus +} +#endif + +#endif + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/misc/nm/nmApi.c b/src/misc/nm/nmApi.c new file mode 100644 index 00000000..72ec24e6 --- /dev/null +++ b/src/misc/nm/nmApi.c @@ -0,0 +1,262 @@ +/**CFile**************************************************************** + + FileName [nmApi.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Name manager.] + + Synopsis [APIs of the name manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: nmApi.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "nmInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates the name manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Nm_Man_t * Nm_ManCreate( int nSize ) +{ + Nm_Man_t * p; + // allocate the table + p = ALLOC( Nm_Man_t, 1 ); + memset( p, 0, sizeof(Nm_Man_t) ); + // set the parameters + p->nSizeFactor = 3; // determined how much larger the table should be compared to data in it + p->nGrowthFactor = 3; // determined how much the table grows after resizing + // allocate and clean the bins + p->nBins = Cudd_PrimeNm(p->nSizeFactor*nSize); + p->pBinsI2N = ALLOC( Nm_Entry_t *, p->nBins ); + p->pBinsN2I = ALLOC( Nm_Entry_t *, p->nBins ); + memset( p->pBinsI2N, 0, sizeof(Nm_Entry_t *) * p->nBins ); + memset( p->pBinsN2I, 0, sizeof(Nm_Entry_t *) * p->nBins ); + // start the memory manager + p->pMem = Extra_MmFlexStart(); + return p; +} + +/**Function************************************************************* + + Synopsis [Deallocates the name manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nm_ManFree( Nm_Man_t * p ) +{ + Extra_MmFlexStop( p->pMem, 0 ); + FREE( p->pBinsI2N ); + FREE( p->pBinsN2I ); + FREE( p ); +} + +/**Function************************************************************* + + Synopsis [Returns the number of objects with names.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nm_ManNumEntries( Nm_Man_t * p ) +{ + return p->nEntries; +} + +/**Function************************************************************* + + Synopsis [Creates a new entry in the name manager.] + + Description [Returns 1 if the entry with the given object ID + already exists in the name manager.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Nm_ManStoreIdName( Nm_Man_t * p, int ObjId, char * pName, char * pSuffix ) +{ + Nm_Entry_t * pEntry, * pEntry2; + int RetValue, nEntrySize; + if ( pEntry = Nm_ManTableLookupId(p, ObjId) ) + { + if ( strcmp(pEntry->Name, pName) == 0 ) + printf( "Nm_ManStoreIdName(): Entry with the same ID and name already exists.\n" ); + else + printf( "Nm_ManStoreIdName(): Entry with the same ID and different name already exists.\n" ); + return NULL; + } + if ( pSuffix == NULL && (pEntry = Nm_ManTableLookupName(p, pName, &pEntry2)) && pEntry2 ) + { + printf( "Nm_ManStoreIdName(): Two entries with the same name already exist.\n" ); + return NULL; + } + // create the entry + nEntrySize = sizeof(Nm_Entry_t) + strlen(pName) + (pSuffix?strlen(pSuffix):0) + 1; + nEntrySize = (nEntrySize / 4 + ((nEntrySize % 4) > 0)) * 4; + pEntry = (Nm_Entry_t *)Extra_MmFlexEntryFetch( p->pMem, nEntrySize ); + pEntry->ObjId = ObjId; + sprintf( pEntry->Name, "%s%s", pName, pSuffix? pSuffix : "" ); + // add the entry to the hash table + RetValue = Nm_ManTableAdd( p, pEntry ); + assert( RetValue == 1 ); + return pEntry->Name; +} + + +/**Function************************************************************* + + Synopsis [Finds a unique name for the node.] + + Description [If the name exists, tries appending numbers to it until + it becomes unique.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Nm_ManCreateUniqueName( Nm_Man_t * p, int ObjId ) +{ + static char NameStr[1000]; + Nm_Entry_t * pEntry; + int i; + if ( pEntry = Nm_ManTableLookupId(p, ObjId) ) + return pEntry->Name; + sprintf( NameStr, "[%d]", ObjId ); + for ( i = 1; Nm_ManTableLookupName(p, NameStr, NULL); i++ ) + sprintf( NameStr, "[%d]_%d", ObjId, i ); + return Nm_ManStoreIdName( p, ObjId, NameStr, NULL ); +} + +/**Function************************************************************* + + Synopsis [Returns name of the object if the ID is known.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Nm_ManFindNameById( Nm_Man_t * p, int ObjId ) +{ + Nm_Entry_t * pEntry; + if ( pEntry = Nm_ManTableLookupId(p, ObjId) ) + return pEntry->Name; + return NULL; +} + +/**Function************************************************************* + + Synopsis [Returns ID of the object if its name is known.] + + Description [This procedure may return two IDs because POs and latches + may have the same name (the only allowed case of name duplication).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nm_ManFindIdByName( Nm_Man_t * p, char * pName, int * pSecond ) +{ + Nm_Entry_t * pEntry, * pEntry2; + if ( pEntry = Nm_ManTableLookupName(p, pName, &pEntry2) ) + { + if ( pSecond ) + *pSecond = pEntry2? pEntry2->ObjId : -1; + return pEntry->ObjId; + } + return -1; +} + + +/**Function************************************************************* + + Synopsis [Prints distribution of entries in the bins.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nm_ManPrintTables( Nm_Man_t * p ) +{ + int i, Counter; + + // rehash the entries from the old table + Counter = 0; + printf( "Int2Name: " ); + for ( i = 0; i < p->nBins; i++ ) + { + if ( Counter == 0 && p->pBinsI2N[i] == NULL ) + continue; + if ( p->pBinsI2N[i] ) + Counter++; + else + { + printf( "%d ", Counter ); + Counter = 0; + } + } + printf( "\n" ); + + // rehash the entries from the old table + Counter = 0; + printf( "Name2Int: " ); + for ( i = 0; i < p->nBins; i++ ) + { + if ( Counter == 0 && p->pBinsN2I[i] == NULL ) + continue; + if ( p->pBinsN2I[i] ) + Counter++; + else + { + printf( "%d ", Counter ); + Counter = 0; + } + } + printf( "\n" ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/misc/nm/nmInt.h b/src/misc/nm/nmInt.h new file mode 100644 index 00000000..d0475c23 --- /dev/null +++ b/src/misc/nm/nmInt.h @@ -0,0 +1,86 @@ +/**CFile**************************************************************** + + FileName [nmInt.h] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Name manager.] + + Synopsis [Internal declarations.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: nmInt.h,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __NM_INT_H__ +#define __NM_INT_H__ + +#ifdef __cplusplus +extern "C" { +#endif + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include "extra.h" +#include "nm.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// BASIC TYPES /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Nm_Entry_t_ Nm_Entry_t; +struct Nm_Entry_t_ +{ + int ObjId; // object ID + char Name[0]; // name of the object +}; + +struct Nm_Man_t_ +{ + Nm_Entry_t ** pBinsI2N; // mapping IDs into names + Nm_Entry_t ** pBinsN2I; // mapping names into IDs + int nBins; // the number of bins in tables + int nEntries; // the number of entries + int nSizeFactor; // determined how much larger the table should be + int nGrowthFactor; // determined how much the table grows after resizing + Extra_MmFlex_t * pMem; // memory manager for entries (and names) +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== nmTable.c ==========================================================*/ +extern int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry ); +extern int Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry ); +extern Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId ); +extern Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** ppSecond ); +extern unsigned int Cudd_PrimeNm( unsigned int p ); + +#ifdef __cplusplus +} +#endif + +#endif + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/misc/nm/nmTable.c b/src/misc/nm/nmTable.c new file mode 100644 index 00000000..86c520d8 --- /dev/null +++ b/src/misc/nm/nmTable.c @@ -0,0 +1,263 @@ +/**CFile**************************************************************** + + FileName [nmTable.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Name manager.] + + Synopsis [Hash table for the name manager.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: nmTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "nmInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// hashing for integers +static unsigned Nm_HashNumber( int Num, int TableSize ) +{ + unsigned Key = 0; + Key ^= ( Num & 0xFF) * 7937; + Key ^= ((Num >> 8) & 0xFF) * 2971; + Key ^= ((Num >> 16) & 0xFF) * 911; + Key ^= ((Num >> 24) & 0xFF) * 353; + return Key % TableSize; +} + +// hashing for strings +static unsigned Nm_HashString( char * pName, int TableSize ) +{ + static int s_Primes[10] = { + 1291, 1699, 2357, 4177, 5147, + 5647, 6343, 7103, 7873, 8147 + }; + unsigned i, Key = 0; + for ( i = 0; pName[i] != '\0'; i++ ) + Key ^= s_Primes[i%10]*pName[i]; + return Key % TableSize; +} + +static void Nm_ManResize( Nm_Man_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Adds an entry to two hash tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nm_ManTableAdd( Nm_Man_t * p, Nm_Entry_t * pEntry ) +{ + int i; + // resize the tables if needed + if ( p->nEntries * p->nSizeFactor > p->nBins ) + { +// Nm_ManPrintTables( p ); + Nm_ManResize( p ); + } + // hash it by ID + for ( i = Nm_HashNumber(pEntry->ObjId, p->nBins); p->pBinsI2N[i]; i = (i+1) % p->nBins ) + if ( p->pBinsI2N[i] == pEntry ) + return 0; + assert( p->pBinsI2N[i] == NULL ); + p->pBinsI2N[i] = pEntry; + // hash it by Name + for ( i = Nm_HashString(pEntry->Name, p->nBins); p->pBinsN2I[i]; i = (i+1) % p->nBins ) + if ( p->pBinsN2I[i] == pEntry ) + return 0; + assert( p->pBinsN2I[i] == NULL ); + p->pBinsN2I[i] = pEntry; + // report successfully added entry + p->nEntries++; + return 1; +} + +/**Function************************************************************* + + Synopsis [Deletes the entry from two hash tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nm_ManTableDelete( Nm_Man_t * p, Nm_Entry_t * pEntry ) +{ + assert( 0 ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Looks up the entry by ID.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Nm_Entry_t * Nm_ManTableLookupId( Nm_Man_t * p, int ObjId ) +{ + int i; + for ( i = Nm_HashNumber(ObjId, p->nBins); p->pBinsI2N[i]; i = (i+1) % p->nBins ) + if ( p->pBinsI2N[i]->ObjId == ObjId ) + return p->pBinsI2N[i]; + return NULL; +} + +/**Function************************************************************* + + Synopsis [Looks up the entry by name. May return two entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Nm_Entry_t * Nm_ManTableLookupName( Nm_Man_t * p, char * pName, Nm_Entry_t ** ppSecond ) +{ + Nm_Entry_t * pFirst, * pSecond; + int i; + pFirst = pSecond = NULL; + for ( i = Nm_HashString(pName, p->nBins); p->pBinsN2I[i]; i = (i+1) % p->nBins ) + if ( strcmp(p->pBinsN2I[i]->Name, pName) == 0 ) + { + if ( pFirst == NULL ) + pFirst = p->pBinsN2I[i]; + else if ( pSecond == NULL ) + pSecond = p->pBinsN2I[i]; + else + assert( 0 ); // name appears more than 2 times + } + // save the names + if ( ppSecond ) + *ppSecond = pSecond; + return pFirst; +} + + +/**Function************************************************************* + + Synopsis [Resizes the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nm_ManResize( Nm_Man_t * p ) +{ + Nm_Entry_t ** pBinsNewI2N, ** pBinsNewN2I, * pEntry; + int nBinsNew, Counter, e, i, clk; + +clk = clock(); + // get the new table size + nBinsNew = Cudd_PrimeCopy( p->nGrowthFactor * p->nBins ); + // allocate a new array + pBinsNewI2N = ALLOC( Nm_Entry_t *, nBinsNew ); + pBinsNewN2I = ALLOC( Nm_Entry_t *, nBinsNew ); + memset( pBinsNewI2N, 0, sizeof(Nm_Entry_t *) * nBinsNew ); + memset( pBinsNewN2I, 0, sizeof(Nm_Entry_t *) * nBinsNew ); + // rehash the entries from the old table + Counter = 0; + for ( e = 0; e < p->nBins; e++ ) + { + pEntry = p->pBinsI2N[e]; + if ( pEntry == NULL ) + continue; + Counter++; + + // hash it by ID + for ( i = Nm_HashNumber(pEntry->ObjId, nBinsNew); pBinsNewI2N[i]; i = (i+1) % nBinsNew ) + if ( pBinsNewI2N[i] == pEntry ) + assert( 0 ); + assert( pBinsNewI2N[i] == NULL ); + pBinsNewI2N[i] = pEntry; + // hash it by Name + for ( i = Nm_HashString(pEntry->Name, nBinsNew); pBinsNewN2I[i]; i = (i+1) % nBinsNew ) + if ( pBinsNewN2I[i] == pEntry ) + assert( 0 ); + assert( pBinsNewN2I[i] == NULL ); + pBinsNewN2I[i] = pEntry; + } + assert( Counter == p->nEntries ); +// printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew ); +// PRT( "Time", clock() - clk ); + // replace the table and the parameters + free( p->pBinsI2N ); + free( p->pBinsN2I ); + p->pBinsI2N = pBinsNewI2N; + p->pBinsN2I = pBinsNewN2I; + p->nBins = nBinsNew; +} + + + +/**Function************************************************************* + + Synopsis [Returns the smallest prime larger than the number.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned int Cudd_PrimeNm( unsigned int p) +{ + int i,pn; + + p--; + do { + p++; + if (p&1) { + pn = 1; + i = 3; + while ((unsigned) (i * i) <= p) { + if (p % i == 0) { + pn = 0; + break; + } + i += 2; + } + } else { + pn = 0; + } + } while (!pn); + return(p); + +} /* end of Cudd_Prime */ + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutTruth.c b/src/opt/cut/cutTruth.c index 54b3aac0..2e36c9e1 100644 --- a/src/opt/cut/cutTruth.c +++ b/src/opt/cut/cutTruth.c @@ -193,22 +193,25 @@ void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_C if ( !p->pParams->fFancy ) return; + if ( pCut->nLeaves != 7 ) + return; + // count the total number of truth tables computed nTotal++; // MAPPING INTO ALTERA 6-2 LOGIC BLOCKS // call this procedure to find the minimum number of common variables in the cofactors // if this number is less or equal than 3, the cut can be implemented using the 6-2 logic block -// if ( Extra_TruthMinCofSuppOverlap( Cut_CutReadTruth(pCut), pCut->nVarsMax, NULL ) <= 3 ) -// nGood++; + if ( Extra_TruthMinCofSuppOverlap( Cut_CutReadTruth(pCut), pCut->nVarsMax, NULL ) <= 4 ) + nGood++; // MAPPING INTO ACTEL 2x2 CELLS // call this procedure to see if a semi-canonical form can be found in the lookup table // (if it exists, then a two-level 3-input LUT implementation of the cut exists) // Before this procedure is called, cell manager should be defined by calling // Cut_CellLoad (make sure file "cells22_daomap_iwls.txt" is available in the working dir) - if ( Cut_CellIsRunning() && pCut->nVarsMax <= 9 ) - nGood += Cut_CellTruthLookup( Cut_CutReadTruth(pCut), pCut->nVarsMax ); +// if ( Cut_CellIsRunning() && pCut->nVarsMax <= 9 ) +// nGood += Cut_CellTruthLookup( Cut_CutReadTruth(pCut), pCut->nVarsMax ); } diff --git a/todo.txt b/todo.txt index 5caecc7d..8759b4f6 100644 --- a/todo.txt +++ b/todo.txt @@ -48,5 +48,6 @@ Other great projects: - specialized synthesis for EXORs and large MUXes - sequential AIG rewriting - +- add asserts +- add untouchables -- cgit v1.2.3