From 5ebf135b6ab0fb5181e383a889f72f96b033adef Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 10 Nov 2014 14:55:27 -0800 Subject: Adding cyclicity check for netlist with boxes. --- src/base/abc/abc.h | 2 + src/base/abc/abcDfs.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++ src/base/abc/abcHieGia.c | 184 +++++++++++++++++++++++++++++++++++++++++++++++ src/base/abc/module.make | 1 + src/base/io/io.c | 25 ++++++- src/base/io/ioUtil.c | 12 ++++ 6 files changed, 403 insertions(+), 3 deletions(-) create mode 100644 src/base/abc/abcHieGia.c (limited to 'src/base') diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h index 62df9450..eb21b091 100644 --- a/src/base/abc/abc.h +++ b/src/base/abc/abc.h @@ -610,6 +610,7 @@ extern ABC_DLL Vec_Ptr_t * Abc_NtkDfsIter( Abc_Ntk_t * pNtk, int fCollect extern ABC_DLL Vec_Ptr_t * Abc_NtkDfsIterNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots ); extern ABC_DLL Vec_Ptr_t * Abc_NtkDfsHie( Abc_Ntk_t * pNtk, int fCollectAll ); extern ABC_DLL int Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk ); +extern ABC_DLL Vec_Ptr_t * Abc_NtkDfsWithBoxes( Abc_Ntk_t * pNtk ); extern ABC_DLL Vec_Ptr_t * Abc_NtkSupport( Abc_Ntk_t * pNtk ); extern ABC_DLL Vec_Ptr_t * Abc_NtkNodeSupport( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes ); extern ABC_DLL Vec_Ptr_t * Abc_AigDfs( Abc_Ntk_t * pNtk, int fCollectAll, int fCollectCos ); @@ -619,6 +620,7 @@ extern ABC_DLL Vec_Vec_t * Abc_NtkLevelize( Abc_Ntk_t * pNtk ); extern ABC_DLL int Abc_NtkLevel( Abc_Ntk_t * pNtk ); extern ABC_DLL int Abc_NtkLevelReverse( Abc_Ntk_t * pNtk ); extern ABC_DLL int Abc_NtkIsAcyclic( Abc_Ntk_t * pNtk ); +extern ABC_DLL int Abc_NtkIsAcyclicWithBoxes( Abc_Ntk_t * pNtk ); extern ABC_DLL Vec_Ptr_t * Abc_AigGetLevelizedOrder( Abc_Ntk_t * pNtk, int fCollectCis ); /*=== abcFanio.c ==========================================================*/ extern ABC_DLL void Abc_ObjAddFanin( Abc_Obj_t * pObj, Abc_Obj_t * pFanin ); diff --git a/src/base/abc/abcDfs.c b/src/base/abc/abcDfs.c index 08b62389..e6c9226f 100644 --- a/src/base/abc/abcDfs.c +++ b/src/base/abc/abcDfs.c @@ -687,6 +687,95 @@ int Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk ) return 1; } +/**Function************************************************************* + + Synopsis [Create DFS ordering of nets.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkDfsNets_rec( Abc_Obj_t * pNet, Vec_Ptr_t * vNets ) +{ + Abc_Obj_t * pNext; + Abc_Obj_t * pNode; int i; + assert( Abc_ObjIsNet(pNet) ); + if ( Abc_NodeIsTravIdCurrent( pNet ) ) + return; + Abc_NodeSetTravIdCurrent( pNet ); + pNode = Abc_ObjFanin0( pNet ); + Abc_ObjForEachFanin( pNode, pNext, i ) + Abc_NtkDfsNets_rec( pNext, vNets ); + Abc_ObjForEachFanout( pNode, pNext, i ) + Vec_PtrPush( vNets, pNext ); +} +Vec_Ptr_t * Abc_NtkDfsNets( Abc_Ntk_t * pNtk ) +{ + Vec_Ptr_t * vNets; + Abc_Obj_t * pObj; int i; + vNets = Vec_PtrAlloc( 100 ); + Abc_NtkIncrementTravId( pNtk ); + Abc_NtkForEachCi( pNtk, pObj, i ) + Abc_NodeSetTravIdCurrent( Abc_ObjFanout0(pObj) ); + Abc_NtkForEachCi( pNtk, pObj, i ) + Vec_PtrPush( vNets, Abc_ObjFanout0(pObj) ); + Abc_NtkForEachCo( pNtk, pObj, i ) + Abc_NtkDfsNets_rec( Abc_ObjFanin0(pObj), vNets ); + return vNets; +} + +/**Function************************************************************* + + Synopsis [Returns the DFS ordered array of logic nodes.] + + Description [Collects only the internal nodes, leaving out CIs and CO. + However it marks with the current TravId both CIs and COs.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkDfsWithBoxes_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes ) +{ + Abc_Obj_t * pFanin; + int i; + assert( !Abc_ObjIsNet(pNode) ); + if ( Abc_ObjIsBo(pNode) ) + pNode = Abc_ObjFanin0(pNode); + if ( Abc_ObjIsPi(pNode) ) + return; + assert( Abc_ObjIsNode( pNode ) || Abc_ObjIsBox( pNode ) ); + if ( Abc_NodeIsTravIdCurrent( pNode ) ) + return; + Abc_NodeSetTravIdCurrent( pNode ); + Abc_ObjForEachFanin( pNode, pFanin, i ) + { + if ( Abc_ObjIsBox(pNode) ) + pFanin = Abc_ObjFanin0(pFanin); + assert( Abc_ObjIsNet(pFanin) ); + Abc_NtkDfsWithBoxes_rec( Abc_ObjFanin0Ntk(pFanin), vNodes ); + } + Vec_PtrPush( vNodes, pNode ); +} +Vec_Ptr_t * Abc_NtkDfsWithBoxes( Abc_Ntk_t * pNtk ) +{ + Vec_Ptr_t * vNodes; + Abc_Obj_t * pObj; + int i; + Abc_NtkIncrementTravId( pNtk ); + vNodes = Vec_PtrAlloc( 100 ); + Abc_NtkForEachPo( pNtk, pObj, i ) + { + assert( Abc_ObjIsNet(Abc_ObjFanin0(pObj)) ); + Abc_NtkDfsWithBoxes_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes ); + } + return vNodes; +} + /**Function************************************************************* @@ -1353,6 +1442,99 @@ int Abc_NtkIsAcyclic( Abc_Ntk_t * pNtk ) } return fAcyclic; } + +/**Function************************************************************* + + Synopsis [Checks for the loops with boxes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkIsAcyclicWithBoxes_rec( Abc_Obj_t * pNode ) +{ + Abc_Ntk_t * pNtk = pNode->pNtk; + Abc_Obj_t * pFanin; + int fAcyclic, i; + assert( !Abc_ObjIsNet(pNode) ); + if ( Abc_ObjIsBo(pNode) ) + pNode = Abc_ObjFanin0(pNode); + if ( Abc_ObjIsPi(pNode) ) + return 1; + assert( Abc_ObjIsNode(pNode) || Abc_ObjIsBox(pNode) ); + // make sure the node is not visited + assert( !Abc_NodeIsTravIdPrevious(pNode) ); + // check if the node is part of the combinational loop + if ( Abc_NodeIsTravIdCurrent(pNode) ) + { + fprintf( stdout, "Network \"%s\" contains combinational loop!\n", Abc_NtkName(pNtk) ); + if ( Abc_ObjIsBox(pNode) ) + fprintf( stdout, "Box \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(pNode) ); + else + fprintf( stdout, "Node \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(Abc_ObjFanout0(pNode)) ); + return 0; + } + // mark this node as a node on the current path + Abc_NodeSetTravIdCurrent( pNode ); + // visit the transitive fanin + Abc_ObjForEachFanin( pNode, pFanin, i ) + { + if ( Abc_ObjIsBox(pNode) ) + pFanin = Abc_ObjFanin0(pFanin); + pFanin = Abc_ObjFanin0Ntk(pFanin); + // make sure there is no mixing of networks + assert( pFanin->pNtk == pNode->pNtk ); + // check if the fanin is visited + if ( Abc_ObjIsPi(pFanin) ) + continue; + if ( Abc_ObjIsBo(pFanin) ) + pFanin = Abc_ObjFanin0(pFanin); + assert( Abc_ObjIsNode(pFanin) || Abc_ObjIsBox(pFanin) ); + if ( Abc_NodeIsTravIdPrevious(pFanin) ) + continue; + // traverse the fanin's cone searching for the loop + if ( (fAcyclic = Abc_NtkIsAcyclicWithBoxes_rec(pFanin)) ) + continue; + // return as soon as the loop is detected + fprintf( stdout, " %s ->", Abc_ObjName( Abc_ObjIsBox(pFanin) ? pFanin : Abc_ObjFanout0(pFanin) ) ); + return 0; + } + // mark this node as a visited node + assert( Abc_ObjIsNode(pNode) || Abc_ObjIsBox(pNode) ); + Abc_NodeSetTravIdPrevious( pNode ); + return 1; +} +int Abc_NtkIsAcyclicWithBoxes( Abc_Ntk_t * pNtk ) +{ + Abc_Obj_t * pNode; + int fAcyclic; + int i; + // set the traversal ID for this DFS ordering + Abc_NtkIncrementTravId( pNtk ); + Abc_NtkIncrementTravId( pNtk ); + // pNode->TravId == pNet->nTravIds means "pNode is on the path" + // pNode->TravId == pNet->nTravIds - 1 means "pNode is visited but is not on the path" + // pNode->TravId < pNet->nTravIds - 1 means "pNode is not visited" + // traverse the network to detect cycles + fAcyclic = 1; + Abc_NtkForEachPo( pNtk, pNode, i ) + { + pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode)); + if ( Abc_NodeIsTravIdPrevious(pNode) ) + continue; + // traverse the output logic cone + if ( (fAcyclic = Abc_NtkIsAcyclicWithBoxes_rec(pNode)) ) + continue; + // stop as soon as the first loop is detected + fprintf( stdout, " PO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) ); + break; + } + return fAcyclic; +} + /**Function************************************************************* diff --git a/src/base/abc/abcHieGia.c b/src/base/abc/abcHieGia.c new file mode 100644 index 00000000..1586dcd7 --- /dev/null +++ b/src/base/abc/abcHieGia.c @@ -0,0 +1,184 @@ +/**CFile**************************************************************** + + FileName [abcHieGia.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Procedures to handle hierarchy.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcHieGia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Transfers the AIG from one manager into another.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NodeStrashToGia_rec( Gia_Man_t * pNew, Hop_Obj_t * pObj ) +{ + assert( !Hop_IsComplement(pObj) ); + if ( !Hop_ObjIsNode(pObj) || Hop_ObjIsMarkA(pObj) ) + return; + Abc_NodeStrashToGia_rec( pNew, Hop_ObjFanin0(pObj) ); + Abc_NodeStrashToGia_rec( pNew, Hop_ObjFanin1(pObj) ); + pObj->iData = Gia_ManHashAnd( pNew, Hop_ObjChild0CopyI(pObj), Hop_ObjChild1CopyI(pObj) ); + assert( !Hop_ObjIsMarkA(pObj) ); // loop detection + Hop_ObjSetMarkA( pObj ); +} +int Abc_NodeStrashToGia( Gia_Man_t * pNew, Abc_Obj_t * pNode ) +{ + Hop_Man_t * pMan = (Hop_Man_t *)pNode->pNtk->pManFunc; + Hop_Obj_t * pRoot = (Hop_Obj_t *)pNode->pData; + Abc_Obj_t * pFanin; int i; + assert( Abc_ObjIsNode(pNode) ); + assert( Abc_NtkHasAig(pNode->pNtk) && !Abc_NtkIsStrash(pNode->pNtk) ); + // check the constant case + if ( Abc_NodeIsConst(pNode) || Hop_Regular(pRoot) == Hop_ManConst1(pMan) ) + return Abc_LitNotCond( 1, Hop_IsComplement(pRoot) ); + // set elementary variables + Abc_ObjForEachFanin( pNode, pFanin, i ) + assert( pFanin->iTemp != -1 ); + Abc_ObjForEachFanin( pNode, pFanin, i ) + Hop_IthVar(pMan, i)->iData = pFanin->iTemp; + // strash the AIG of this node + Abc_NodeStrashToGia_rec( pNew, Hop_Regular(pRoot) ); + Hop_ConeUnmark_rec( Hop_Regular(pRoot) ); + return Abc_LitNotCond( Hop_Regular(pRoot)->iData, Hop_IsComplement(pRoot) ); +} + + +/**Function************************************************************* + + Synopsis [Flattens the logic hierarchy of the netlist.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManFlattenLogicHierarchy_rec( Gia_Man_t * pNew, Abc_Ntk_t * pNtk, int * pCounter ) +{ + Vec_Ptr_t * vDfs = (Vec_Ptr_t *)pNtk->pData; + Abc_Obj_t * pObj, * pTerm; + int i, k; (*pCounter)++; + //printf( "[%d:%d] ", Abc_NtkPiNum(pNtk), Abc_NtkPoNum(pNtk) ); + Vec_PtrForEachEntry( Abc_Obj_t *, vDfs, pObj, i ) + { + if ( Abc_ObjIsNode(pObj) ) + Abc_ObjFanout0(pObj)->iTemp = Abc_NodeStrashToGia( pNew, pObj ); + else + { + Abc_Ntk_t * pModel = (Abc_Ntk_t *)pObj->pData; + assert( !Abc_ObjIsLatch(pObj) ); + assert( Abc_NtkPiNum(pModel) == Abc_ObjFaninNum(pObj) ); + assert( Abc_NtkPoNum(pModel) == Abc_ObjFanoutNum(pObj) ); + Abc_NtkFillTemp( pModel ); + Abc_ObjForEachFanin( pObj, pTerm, k ) + { + assert( Abc_ObjIsNet(Abc_ObjFanin0(pTerm)) ); +// Abc_ObjFanout0(Abc_NtkPi(pModel, k))->iTemp = Gia_ManAppendBuf( pNew, Abc_ObjFanin0(pTerm)->iTemp ); + Abc_ObjFanout0(Abc_NtkPi(pModel, k))->iTemp = Abc_ObjFanin0(pTerm)->iTemp; + } + Gia_ManFlattenLogicHierarchy_rec( pNew, pModel, pCounter ); + Abc_ObjForEachFanout( pObj, pTerm, k ) + { + assert( Abc_ObjIsNet(Abc_ObjFanout0(pTerm)) ); +// Abc_ObjFanout0(pTerm)->iTemp = Gia_ManAppendBuf( pNew, Abc_ObjFanin0(Abc_NtkPo(pModel, k))->iTemp ); + Abc_ObjFanout0(pTerm)->iTemp = Abc_ObjFanin0(Abc_NtkPo(pModel, k))->iTemp; + } + } + } +} +Gia_Man_t * Gia_ManFlattenLogicHierarchy( Abc_Ntk_t * pNtk ) +{ + Gia_Man_t * pNew, * pTemp; + Abc_Ntk_t * pModel; + Abc_Obj_t * pTerm; + int i, Counter = -1; + assert( Abc_NtkIsNetlist(pNtk) ); + +// Abc_NtkPrintBoxInfo( pNtk ); + Abc_NtkFillTemp( pNtk ); + + // start the manager + pNew = Gia_ManStart( Abc_NtkObjNumMax(pNtk) ); + pNew->pName = Abc_UtilStrsav(pNtk->pName); + pNew->pSpec = Abc_UtilStrsav(pNtk->pSpec); + + // create PIs and buffers + Abc_NtkForEachPi( pNtk, pTerm, i ) + pTerm->iTemp = Gia_ManAppendCi( pNew ); + Abc_NtkForEachPi( pNtk, pTerm, i ) +// Abc_ObjFanout0(pTerm)->iTemp = Gia_ManAppendBuf( pNew, pTerm->iTemp ); + Abc_ObjFanout0(pTerm)->iTemp = pTerm->iTemp; + + // create DFS order of nets + if ( !pNtk->pDesign ) + pNtk->pData = Abc_NtkDfsWithBoxes( pNtk ); + else + Vec_PtrForEachEntry( Abc_Ntk_t *, pNtk->pDesign->vModules, pModel, i ) + pModel->pData = Abc_NtkDfsWithBoxes( pModel ); + + // call recursively + Gia_ManHashAlloc( pNew ); + Gia_ManFlattenLogicHierarchy_rec( pNew, pNtk, &Counter ); + Gia_ManHashStop( pNew ); + printf( "Hierarchy reader flattened %d instances of logic boxes.\n", Counter ); + + // delete DFS order of nets + if ( !pNtk->pDesign ) + Vec_PtrFreeP( (Vec_Ptr_t **)&pNtk->pData ); + else + Vec_PtrForEachEntry( Abc_Ntk_t *, pNtk->pDesign->vModules, pModel, i ) + Vec_PtrFreeP( (Vec_Ptr_t **)&pModel->pData ); + + // create buffers and POs + Abc_NtkForEachPo( pNtk, pTerm, i ) +// pTerm->iTemp = Gia_ManAppendBuf( pNew, Abc_ObjFanin0(pTerm)->iTemp ); + pTerm->iTemp = Abc_ObjFanin0(pTerm)->iTemp; + Abc_NtkForEachPo( pNtk, pTerm, i ) + Gia_ManAppendCo( pNew, pTerm->iTemp ); + + pNew = Gia_ManCleanup( pTemp = pNew ); + Gia_ManStop( pTemp ); + return pNew; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/base/abc/module.make b/src/base/abc/module.make index e7c6345d..34517b04 100644 --- a/src/base/abc/module.make +++ b/src/base/abc/module.make @@ -8,6 +8,7 @@ SRC += src/base/abc/abcAig.c \ src/base/abc/abcFunc.c \ src/base/abc/abcHie.c \ src/base/abc/abcHieCec.c \ + src/base/abc/abcHieGia.c \ src/base/abc/abcHieNew.c \ src/base/abc/abcLatch.c \ src/base/abc/abcLib.c \ diff --git a/src/base/io/io.c b/src/base/io/io.c index 39c08db4..42a4a370 100644 --- a/src/base/io/io.c +++ b/src/base/io/io.c @@ -170,13 +170,14 @@ int IoCommandRead( Abc_Frame_t * pAbc, int argc, char ** argv ) char Command[1000]; Abc_Ntk_t * pNtk; char * pFileName, * pTemp; - int c, fCheck, fBarBufs; + int c, fCheck, fBarBufs, fReadGia; fCheck = 1; fBarBufs = 0; + fReadGia = 0; glo_fMapped = 0; Extra_UtilGetoptReset(); - while ( ( c = Extra_UtilGetopt( argc, argv, "mcbh" ) ) != EOF ) + while ( ( c = Extra_UtilGetopt( argc, argv, "mcbgh" ) ) != EOF ) { switch ( c ) { @@ -189,6 +190,9 @@ int IoCommandRead( Abc_Frame_t * pAbc, int argc, char ** argv ) case 'b': fBarBufs ^= 1; break; + case 'g': + fReadGia ^= 1; + break; case 'h': goto usage; default: @@ -225,6 +229,20 @@ int IoCommandRead( Abc_Frame_t * pAbc, int argc, char ** argv ) Cmd_CommandExecute( pAbc, Command ); return 0; } + if ( fReadGia ) + { + extern Gia_Man_t * Gia_ManFlattenLogicHierarchy( Abc_Ntk_t * pNtk ); + Abc_Ntk_t * pNtk = Io_ReadNetlist( pFileName, Io_ReadFileType(pFileName), fCheck ); + Gia_Man_t * pGia = Gia_ManFlattenLogicHierarchy( pNtk ); + Abc_NtkDelete( pNtk ); + if ( pGia == NULL ) + { + Abc_Print( 1, "Abc_CommandBlast(): Bit-blasting has failed.\n" ); + return 0; + } + Abc_FrameUpdateGia( pAbc, pGia ); + return 0; + } // check if the library is available if ( glo_fMapped && Abc_FrameReadLibGen() == NULL ) { @@ -247,13 +265,14 @@ int IoCommandRead( Abc_Frame_t * pAbc, int argc, char ** argv ) return 0; usage: - fprintf( pAbc->Err, "usage: read [-mcbh] \n" ); + fprintf( pAbc->Err, "usage: read [-mcbgh] \n" ); fprintf( pAbc->Err, "\t replaces the current network by the network read from \n" ); fprintf( pAbc->Err, "\t by calling the parser that matches the extension of \n" ); fprintf( pAbc->Err, "\t (to read a hierarchical design, use \"read_hie\")\n" ); fprintf( pAbc->Err, "\t-m : toggle reading mapped Verilog [default = %s]\n", glo_fMapped? "yes":"no" ); fprintf( pAbc->Err, "\t-c : toggle network check after reading [default = %s]\n", fCheck? "yes":"no" ); fprintf( pAbc->Err, "\t-b : toggle reading barrier buffers [default = %s]\n", fBarBufs? "yes":"no" ); + fprintf( pAbc->Err, "\t-g : toggle reading and flattening into &-space [default = %s]\n", fBarBufs? "yes":"no" ); fprintf( pAbc->Err, "\t-h : prints the command summary\n" ); fprintf( pAbc->Err, "\tfile : the name of a file to read\n" ); return 1; diff --git a/src/base/io/ioUtil.c b/src/base/io/ioUtil.c index 24ed029a..671c6d56 100644 --- a/src/base/io/ioUtil.c +++ b/src/base/io/ioUtil.c @@ -158,7 +158,19 @@ Abc_Ntk_t * Io_ReadNetlist( char * pFileName, Io_FileType_t FileType, int fCheck return NULL; } if ( Abc_NtkBlackboxNum(pNtk) || Abc_NtkWhiteboxNum(pNtk) ) + { + int i, fCycle = 0; + Abc_Ntk_t * pModel; fprintf( stdout, "Warning: The network contains hierarchy.\n" ); + Vec_PtrForEachEntry( Abc_Ntk_t *, pNtk->pDesign->vModules, pModel, i ) + if ( !Abc_NtkIsAcyclicWithBoxes( pModel ) ) + fCycle = 1; + if ( fCycle ) + { + Abc_NtkDelete( pNtk ); + return NULL; + } + } return pNtk; } -- cgit v1.2.3