1 /**CFile****************************************************************
2
3 FileName [giaScl.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Sequential cleanup.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaScl.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis [Marks unreachable internal nodes and returns their number.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Gia_ManCombMarkUsed_rec(Gia_Man_t * p,Gia_Obj_t * pObj)45 int Gia_ManCombMarkUsed_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
46 {
47 if ( pObj == NULL )
48 return 0;
49 if ( !pObj->fMark0 )
50 return 0;
51 pObj->fMark0 = 0;
52 assert( Gia_ObjIsAnd(pObj) );
53 assert( !Gia_ObjIsBuf(pObj) );
54 return 1 + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) )
55 + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin1(pObj) )
56 + (p->pNexts ? Gia_ManCombMarkUsed_rec( p, Gia_ObjNextObj(p, Gia_ObjId(p, pObj)) ) : 0)
57 + (p->pSibls ? Gia_ManCombMarkUsed_rec( p, Gia_ObjSiblObj(p, Gia_ObjId(p, pObj)) ) : 0)
58 + (p->pMuxes ? Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin2(p, pObj) ) : 0);
59 }
Gia_ManCombMarkUsed(Gia_Man_t * p)60 int Gia_ManCombMarkUsed( Gia_Man_t * p )
61 {
62 Gia_Obj_t * pObj;
63 int i, nNodes = 0;
64 Gia_ManForEachObj( p, pObj, i )
65 pObj->fMark0 = Gia_ObjIsAnd(pObj) && !Gia_ObjIsBuf(pObj);
66 Gia_ManForEachBuf( p, pObj, i )
67 nNodes += Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) );
68 Gia_ManForEachCo( p, pObj, i )
69 nNodes += Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) );
70 return nNodes;
71 }
72
73 /**Function*************************************************************
74
75 Synopsis [Performs combinational cleanup.]
76
77 Description []
78
79 SideEffects []
80
81 SeeAlso []
82
83 ***********************************************************************/
Gia_ManCleanup(Gia_Man_t * p)84 Gia_Man_t * Gia_ManCleanup( Gia_Man_t * p )
85 {
86 Gia_ManCombMarkUsed( p );
87 return Gia_ManDupMarked( p );
88 }
89
90 /**Function*************************************************************
91
92 Synopsis [Skip the first outputs during cleanup.]
93
94 Description []
95
96 SideEffects []
97
98 SeeAlso []
99
100 ***********************************************************************/
Gia_ManCleanupOutputs(Gia_Man_t * p,int nOutputs)101 Gia_Man_t * Gia_ManCleanupOutputs( Gia_Man_t * p, int nOutputs )
102 {
103 Gia_Obj_t * pObj;
104 int i;
105 assert( Gia_ManRegNum(p) == 0 );
106 assert( nOutputs < Gia_ManCoNum(p) );
107 Gia_ManCombMarkUsed( p );
108 Gia_ManForEachCo( p, pObj, i )
109 if ( i < nOutputs )
110 pObj->fMark0 = 1;
111 else
112 break;
113 return Gia_ManDupMarked( p );
114 }
115
116
117 /**Function*************************************************************
118
119 Synopsis [Marks CIs/COs/ANDs unreachable from POs.]
120
121 Description []
122
123 SideEffects []
124
125 SeeAlso []
126
127 ***********************************************************************/
Gia_ManSeqMarkUsed_rec(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vRoots)128 int Gia_ManSeqMarkUsed_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vRoots )
129 {
130 if ( !pObj->fMark0 )
131 return 0;
132 pObj->fMark0 = 0;
133 if ( Gia_ObjIsCo(pObj) )
134 return Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots );
135 if ( Gia_ObjIsRo(p, pObj) )
136 {
137 Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ObjRoToRi(p, pObj)) );
138 return 0;
139 }
140 assert( Gia_ObjIsAnd(pObj) );
141 return 1 + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots )
142 + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin1(pObj), vRoots );
143 }
144
145 /**Function*************************************************************
146
147 Synopsis [Marks CIs/COs/ANDs unreachable from POs.]
148
149 Description []
150
151 SideEffects []
152
153 SeeAlso []
154
155 ***********************************************************************/
Gia_ManSeqMarkUsed(Gia_Man_t * p)156 int Gia_ManSeqMarkUsed( Gia_Man_t * p )
157 {
158 Vec_Int_t * vRoots;
159 Gia_Obj_t * pObj;
160 int i, nNodes = 0;
161 Gia_ManSetMark0( p );
162 Gia_ManConst0(p)->fMark0 = 0;
163 Gia_ManForEachPi( p, pObj, i )
164 pObj->fMark0 = 0;
165 vRoots = Gia_ManCollectPoIds( p );
166 Gia_ManForEachObjVec( vRoots, p, pObj, i )
167 nNodes += Gia_ManSeqMarkUsed_rec( p, pObj, vRoots );
168 Vec_IntFree( vRoots );
169 return nNodes;
170 }
171
172 /**Function*************************************************************
173
174 Synopsis [Performs sequential cleanup.]
175
176 Description []
177
178 SideEffects []
179
180 SeeAlso []
181
182 ***********************************************************************/
Gia_ManSeqCleanup(Gia_Man_t * p)183 Gia_Man_t * Gia_ManSeqCleanup( Gia_Man_t * p )
184 {
185 Gia_ManSeqMarkUsed( p );
186 return Gia_ManDupMarked( p );
187 }
188
189 /**Function*************************************************************
190
191 Synopsis [Find representatives due to identical fanins.]
192
193 Description [Returns the old manager if there is no changes.]
194
195 SideEffects []
196
197 SeeAlso []
198
199 ***********************************************************************/
Gia_ManReduceEquiv(Gia_Man_t * p,int fVerbose)200 Gia_Man_t * Gia_ManReduceEquiv( Gia_Man_t * p, int fVerbose )
201 {
202 Gia_Man_t * pNew;
203 Gia_Obj_t * pObjRi, * pObjRo;
204 unsigned * pCi2Lit, * pMaps;
205 int i, iLit, nFanins = 1, Counter0 = 0, Counter = 0;
206 Gia_ManForEachRi( p, pObjRi, i )
207 Gia_ObjFanin0(pObjRi)->Value = 0;
208 Gia_ManForEachRi( p, pObjRi, i )
209 if ( Gia_ObjFanin0(pObjRi)->Value == 0 )
210 Gia_ObjFanin0(pObjRi)->Value = 2*nFanins++;
211 pCi2Lit = ABC_FALLOC( unsigned, Gia_ManCiNum(p) );
212 pMaps = ABC_FALLOC( unsigned, 2 * nFanins );
213 Gia_ManForEachRiRo( p, pObjRi, pObjRo, i )
214 {
215 iLit = Gia_ObjFanin0Copy( pObjRi );
216 if ( Gia_ObjFaninId0p(p, pObjRi) == 0 && Gia_ObjFaninC0(pObjRi) == 0 ) // const 0
217 pCi2Lit[Gia_ManPiNum(p)+i] = 0, Counter0++;
218 else if ( ~pMaps[iLit] ) // in this case, ID(pObj) > ID(pRepr)
219 pCi2Lit[Gia_ManPiNum(p)+i] = pMaps[iLit], Counter++;
220 else
221 pMaps[iLit] = Abc_Var2Lit( Gia_ObjId(p, pObjRo), 0 );
222 }
223 /*
224 Gia_ManForEachCi( p, pObjRo, i )
225 {
226 if ( ~pCi2Lit[i] )
227 {
228 Gia_Obj_t * pObj0 = Gia_ObjRoToRi(p, pObjRo);
229 Gia_Obj_t * pObj1 = Gia_ObjRoToRi(p, Gia_ManObj(p, pCi2Lit[i]));
230 Gia_Obj_t * pFan0 = Gia_ObjChild0( p, Gia_ObjRoToRi(p, pObjRo) );
231 Gia_Obj_t * pFan1 = Gia_ObjChild0( p, Gia_ObjRoToRi(p, Gia_ManObj(p, pCi2Lit[i])) );
232 assert( pFan0 == pFan1 );
233 }
234 }
235 */
236 // if ( fVerbose )
237 // printf( "ReduceEquiv detected %d constant regs and %d equivalent regs.\n", Counter0, Counter );
238 ABC_FREE( pMaps );
239 if ( Counter0 || Counter )
240 pNew = Gia_ManDupDfsCiMap( p, (int *)pCi2Lit, NULL );
241 else
242 pNew = p;
243 ABC_FREE( pCi2Lit );
244 return pNew;
245 }
246
247 /**Function*************************************************************
248
249 Synopsis [Performs sequential cleanup.]
250
251 Description []
252
253 SideEffects []
254
255 SeeAlso []
256
257 ***********************************************************************/
Gia_ManSeqStructSweep(Gia_Man_t * p,int fConst,int fEquiv,int fVerbose)258 Gia_Man_t * Gia_ManSeqStructSweep( Gia_Man_t * p, int fConst, int fEquiv, int fVerbose )
259 {
260 Gia_Man_t * pTemp;
261 if ( Gia_ManRegNum(p) == 0 )
262 return Gia_ManCleanup( p );
263 if ( fVerbose )
264 printf( "Performing sequential cleanup.\n" );
265 p = Gia_ManSeqCleanup( pTemp = p );
266 if ( fVerbose )
267 Gia_ManReportImprovement( pTemp, p );
268 if ( fConst && Gia_ManRegNum(p) )
269 {
270 p = Gia_ManReduceConst( pTemp = p, fVerbose );
271 if ( fVerbose )
272 Gia_ManReportImprovement( pTemp, p );
273 Gia_ManStop( pTemp );
274 }
275 if ( fVerbose && fEquiv )
276 printf( "Merging combinationally equivalent flops.\n" );
277 if ( fEquiv )
278 while ( 1 )
279 {
280 p = Gia_ManSeqCleanup( pTemp = p );
281 if ( fVerbose )
282 Gia_ManReportImprovement( pTemp, p );
283 Gia_ManStop( pTemp );
284 if ( Gia_ManRegNum(p) == 0 )
285 break;
286 p = Gia_ManReduceEquiv( pTemp = p, fVerbose );
287 if ( p == pTemp )
288 break;
289 Gia_ManStop( pTemp );
290 }
291 return p;
292 }
293
294 ////////////////////////////////////////////////////////////////////////
295 /// END OF FILE ///
296 ////////////////////////////////////////////////////////////////////////
297
298
299 ABC_NAMESPACE_IMPL_END
300
301