summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/base/wln/wln.h2
-rw-r--r--src/base/wln/wlnNdr.c5
-rw-r--r--src/base/wln/wlnNtk.c135
3 files changed, 141 insertions, 1 deletions
diff --git a/src/base/wln/wln.h b/src/base/wln/wln.h
index 54150c56..22247893 100644
--- a/src/base/wln/wln.h
+++ b/src/base/wln/wln.h
@@ -163,6 +163,7 @@ static inline void Wln_ObjSetFanout( Wln_Ntk_t * p, int i, int f, int v
static inline void Wln_NtkIncrementTravId( Wln_Ntk_t * p ) { if (!p->nTravIds++) Vec_IntFill(&p->vTravIds, Vec_IntCap(&p->vTypes), 0); }
static inline void Wln_ObjSetTravIdCurrent( Wln_Ntk_t * p, int i ) { Vec_IntWriteEntry( &p->vTravIds, i, p->nTravIds ); }
+static inline void Wln_ObjSetTravIdPrevious( Wln_Ntk_t * p, int i ) { Vec_IntWriteEntry( &p->vTravIds, i, p->nTravIds-1 ); }
static inline int Wln_ObjIsTravIdCurrent( Wln_Ntk_t * p, int i ) { return (Vec_IntEntry(&p->vTravIds, i) == p->nTravIds); }
static inline int Wln_ObjIsTravIdPrevious( Wln_Ntk_t * p, int i ) { return (Vec_IntEntry(&p->vTravIds, i) == p->nTravIds-1); }
static inline int Wln_ObjCheckTravId( Wln_Ntk_t * p, int i ) { if ( Wln_ObjIsTravIdCurrent(p, i) ) return 1; Wln_ObjSetTravIdCurrent(p, i); return 0; }
@@ -225,6 +226,7 @@ extern void Wln_NtkFree( Wln_Ntk_t * p );
extern int Wln_NtkMemUsage( Wln_Ntk_t * p );
extern void Wln_NtkPrint( Wln_Ntk_t * p );
extern Wln_Ntk_t * Wln_NtkDupDfs( Wln_Ntk_t * p );
+extern int Wln_NtkIsAcyclic( Wln_Ntk_t * p );
extern void Wln_NtkCreateRefs( Wln_Ntk_t * p );
extern void Wln_NtkStartFaninMap( Wln_Ntk_t * p, Vec_Int_t * vFaninMap, int nMulti );
extern void Wln_NtkStartFanoutMap( Wln_Ntk_t * p, Vec_Int_t * vFanoutMap, Vec_Int_t * vFanoutNums, int nMulti );
diff --git a/src/base/wln/wlnNdr.c b/src/base/wln/wlnNdr.c
index 60179ed4..e9e0bf83 100644
--- a/src/base/wln/wlnNdr.c
+++ b/src/base/wln/wlnNdr.c
@@ -270,6 +270,11 @@ Wln_Ntk_t * Wln_NtkFromNdr( void * pData )
//Ndr_NtkPrintObjects( pNtk );
Wln_WriteVer( pNtk, "temp_ndr.v" );
printf( "Dumped design \"%s\" into file \"temp_ndr.v\".\n", pNtk->pName );
+ if ( !Wln_NtkIsAcyclic(pNtk) )
+ {
+ Wln_NtkFree(pNtk);
+ return NULL;
+ }
// derive topological order
pNtk = Wln_NtkDupDfs( pTemp = pNtk );
Wln_NtkFree( pTemp );
diff --git a/src/base/wln/wlnNtk.c b/src/base/wln/wlnNtk.c
index a845b55e..f5762c2b 100644
--- a/src/base/wln/wlnNtk.c
+++ b/src/base/wln/wlnNtk.c
@@ -129,6 +129,139 @@ void Wln_NtkPrint( Wln_Ntk_t * p )
printf( "\n" );
}
+
+
+/**Function*************************************************************
+
+ Synopsis [Detects combinational loops.]
+
+ Description [This procedure is based on the idea suggested by Donald Chai.
+ As we traverse the network and visit the nodes, we need to distinquish
+ three types of nodes: (1) those that are visited for the first time,
+ (2) those that have been visited in this traversal but are currently not
+ on the traversal path, (3) those that have been visited and are currently
+ on the travesal path. When the node of type (3) is encountered, it means
+ that there is a combinational loop. To mark the three types of nodes,
+ two new values of the traversal IDs are used.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Wln_NtkIsAcyclic_rec( Wln_Ntk_t * p, int iObj )
+{
+ int i, iFanin;
+ //printf( "Visiting node %d\n", iObj );
+ if ( 43309 == iObj )
+ {
+ int s = 0;
+ }
+ // skip the node if it is already visited
+ if ( Wln_ObjIsTravIdPrevious(p, iObj) )
+ return 1;
+ // check if the node is part of the combinational loop
+ if ( Wln_ObjIsTravIdCurrent(p, iObj) )
+ {
+ fprintf( stdout, "Network contains combinational loop!\n" );
+ fprintf( stdout, "Node %16s is encountered twice on the following path:\n", Wln_ObjName(p, iObj) );
+ fprintf( stdout, "Node %16s (ID %6d) of type %5s (type ID %2d) ->\n",
+ Wln_ObjName(p, iObj), iObj, Abc_OperName(Wln_ObjType(p, iObj)), Wln_ObjType(p, iObj) );
+ return 0;
+ }
+ // mark this node as a node on the current path
+ Wln_ObjSetTravIdCurrent( p, iObj );
+ // quit if it is a CI or constant node
+ if ( Wln_ObjIsCi(p, iObj) || Wln_ObjIsFf(p, iObj) || Wln_ObjFaninNum(p, iObj) == 0 )
+ {
+ // mark this node as a visited node
+ Wln_ObjSetTravIdPrevious( p, iObj );
+ return 1;
+ }
+ // traverse the fanin's cone searching for the loop
+ Wln_ObjForEachFanin( p, iObj, iFanin, i )
+ {
+ if ( !Wln_NtkIsAcyclic_rec(p, iFanin) )
+ {
+ // return as soon as the loop is detected
+ fprintf( stdout, "Node %16s (ID %6d) of type %5s (type ID %2d) ->\n",
+ Wln_ObjName(p, iObj), iObj, Abc_OperName(Wln_ObjType(p, iObj)), Wln_ObjType(p, iObj) );
+ return 0;
+ }
+ }
+ // mark this node as a visited node
+ Wln_ObjSetTravIdPrevious( p, iObj );
+ return 1;
+}
+int Wln_NtkIsAcyclic( Wln_Ntk_t * p )
+{
+ int fAcyclic, i, iObj, nUnvisited = 0 ;
+ // set the traversal ID for this DFS ordering
+ Wln_NtkIncrementTravId( p );
+ Wln_NtkIncrementTravId( p );
+ // iObj->TravId == pNet->nTravIds means "iObj is on the path"
+ // iObj->TravId == pNet->nTravIds - 1 means "iObj is visited but is not on the path"
+ // iObj->TravId < pNet->nTravIds - 1 means "iObj is not visited"
+ // traverse the network to detect cycles
+ fAcyclic = 1;
+ Wln_NtkForEachCo( p, iObj, i )
+ {
+ // traverse the output logic cone
+ if ( (fAcyclic = Wln_NtkIsAcyclic_rec(p, iObj)) )
+ continue;
+ // stop as soon as the first loop is detected
+ fprintf( stdout, "Primary output %16s (ID %6d)\n", Wln_ObjName(p, iObj), iObj );
+ break;
+ }
+ Wln_NtkForEachFf( p, iObj, i )
+ {
+ // traverse the output logic cone
+ if ( (fAcyclic = Wln_NtkIsAcyclic_rec(p, iObj)) )
+ continue;
+ // stop as soon as the first loop is detected
+ fprintf( stdout, "Flip-flop %16s (ID %6d)\n", Wln_ObjName(p, iObj), iObj );
+ break;
+ }
+ Wln_NtkForEachObj( p, iObj )
+ nUnvisited += !Wln_ObjIsTravIdPrevious(p, iObj) && !Wln_ObjIsCi(p, iObj);
+ if ( nUnvisited )
+ {
+ int nSinks = 0;
+ Wln_NtkCreateRefs(p);
+ printf( "The network has %d objects and %d (%6.2f %%) of them are not connected to the outputs.\n",
+ Wln_NtkObjNum(p), nUnvisited, 100.0*nUnvisited/Wln_NtkObjNum(p) );
+ Wln_NtkForEachObj( p, iObj )
+ if ( !Wln_ObjRefs(p, iObj) && !Wln_ObjIsCi(p, iObj) && !Wln_ObjIsFf(p, iObj) )
+ nSinks++;
+ if ( nSinks )
+ {
+ int nPrinted = 0;
+ printf( "These unconnected objects feed into %d sink objects without fanout:\n", nSinks );
+ Wln_NtkForEachObj( p, iObj )
+ if ( !Wln_ObjRefs(p, iObj) && !Wln_ObjIsCi(p, iObj) && !Wln_ObjIsFf(p, iObj) )
+ {
+ fprintf( stdout, "Node %16s (ID %6d) of type %5s (type ID %2d)\n",
+ Wln_ObjName(p, iObj), iObj, Abc_OperName(Wln_ObjType(p, iObj)), Wln_ObjType(p, iObj) );
+ if ( ++nPrinted == 5 )
+ break;
+ }
+ if ( nPrinted < nSinks )
+ printf( "...\n" );
+ }
+ Wln_NtkForEachObj( p, iObj )
+ if ( /*!Wln_ObjRefs(p, iObj) &&*/ !Wln_ObjIsTravIdPrevious(p, iObj) && !Wln_ObjIsCi(p, iObj) )
+ {
+ // traverse the output logic cone
+ if ( (fAcyclic = Wln_NtkIsAcyclic_rec(p, iObj)) )
+ continue;
+ // stop as soon as the first loop is detected
+ fprintf( stdout, "Unconnected object %s\n", Wln_ObjName(p, iObj) );
+ break;
+ }
+ }
+ return fAcyclic;
+}
+
/**Function*************************************************************
Synopsis [Duplicating network.]
@@ -186,7 +319,7 @@ int Wln_NtkDupDfs_rec( Wln_Ntk_t * pNew, Wln_Ntk_t * p, int iObj )
return 0;
if ( Wln_ObjCopy(p, iObj) )
return Wln_ObjCopy(p, iObj);
- //printf( "Visiting node %d\n", iObj );
+ //printf( "Visiting node %16s (ID %6d) of type %5s (type ID %2d)\n", Wln_ObjName(p, iObj), iObj, Abc_OperName(Wln_ObjType(p, iObj)), Wln_ObjType(p, iObj) );
assert( !Wln_ObjIsFf(p, iObj) );
Wln_ObjForEachFanin( p, iObj, iFanin, i )
Wln_NtkDupDfs_rec( pNew, p, iFanin );
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-25 21:39:42 +0000