1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
/**CFile****************************************************************
FileName [ivyDfs.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [And-Inverter Graph package.]
Synopsis [DFS collection procedures.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - May 11, 2006.]
Revision [$Id: ivyDfs.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
***********************************************************************/
#include "ivy.h"
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Collects nodes in the DFS order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManDfs_rec( Ivy_Obj_t * pObj, Vec_Int_t * vNodes )
{
if ( Ivy_ObjIsConst1(pObj) || Ivy_ObjIsCi(pObj) )
return;
if ( Ivy_ObjIsMarkA(pObj) )
return;
Ivy_ObjSetMarkA(pObj);
assert( Ivy_ObjIsBuf(pObj) || Ivy_ObjIsAnd(pObj) || Ivy_ObjIsExor(pObj) );
Ivy_ManDfs_rec( Ivy_ObjFanin0(pObj), vNodes );
if ( !Ivy_ObjIsBuf(pObj) )
Ivy_ManDfs_rec( Ivy_ObjFanin1(pObj), vNodes );
Vec_IntPush( vNodes, pObj->Id );
}
/**Function*************************************************************
Synopsis [Collects AND/EXOR nodes in the DFS order from CIs to COs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Ivy_ManDfs( Ivy_Man_t * p )
{
Vec_Int_t * vNodes;
Ivy_Obj_t * pObj;
int i;
// collect the nodes
vNodes = Vec_IntAlloc( Ivy_ManNodeNum(p) );
if ( Ivy_ManLatchNum(p) > 0 )
Ivy_ManForEachCo( p, pObj, i )
Ivy_ManDfs_rec( Ivy_ObjFanin0(pObj), vNodes );
else
Ivy_ManForEachPo( p, pObj, i )
Ivy_ManDfs_rec( Ivy_ObjFanin0(pObj), vNodes );
// unmark the collected nodes
Ivy_ManForEachNodeVec( p, vNodes, pObj, i )
Ivy_ObjClearMarkA(pObj);
// make sure network does not have dangling nodes
assert( Vec_IntSize(vNodes) == Ivy_ManNodeNum(p) + Ivy_ManBufNum(p) );
return vNodes;
}
/**Function*************************************************************
Synopsis [Collects nodes in the DFS order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Ivy_ManDfsExt_rec( Ivy_Obj_t * pObj, Vec_Int_t * vNodes )
{
Vec_Int_t * vFanins;
int i, Fanin;
if ( !Ivy_ObjIsNodeExt(pObj) || Ivy_ObjIsMarkA(pObj) )
return;
// mark the node as visited
Ivy_ObjSetMarkA(pObj);
// traverse the fanins
vFanins = Ivy_ObjGetFanins( pObj );
Vec_IntForEachEntry( vFanins, Fanin, i )
Ivy_ManDfsExt_rec( Ivy_ObjObj(pObj, Ivy_FanId(Fanin)), vNodes );
// add the node
Vec_IntPush( vNodes, pObj->Id );
}
/**Function*************************************************************
Synopsis [Collects nodes in the DFS order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Ivy_ManDfsExt( Ivy_Man_t * p )
{
Vec_Int_t * vNodes;
Ivy_Obj_t * pObj, * pFanin;
int i;
assert( p->fExtended );
assert( Ivy_ManLatchNum(p) == 0 );
// make sure network does not have buffers
vNodes = Vec_IntAlloc( 10 );
Ivy_ManForEachPo( p, pObj, i )
{
pFanin = Ivy_ManObj( p, Ivy_FanId( Ivy_ObjReadFanin(pObj,0) ) );
Ivy_ManDfsExt_rec( pFanin, vNodes );
}
Ivy_ManForEachNodeVec( p, vNodes, pObj, i )
Ivy_ObjClearMarkA(pObj);
// make sure network does not have dangling nodes
// the network may have dangling nodes if some fanins of ESOPs do not appear in cubes
// assert( p->nNodes == Vec_PtrSize(vNodes) );
return vNodes;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
|
