1 /**CFile****************************************************************
2
3 FileName [aigMan.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [AIG package.]
8
9 Synopsis [AIG manager.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: aigMan.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "aig.h"
22 #include "misc/tim/tim.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Starts the AIG manager.]
38
39 Description [The argument of this procedure is a soft limit on the
40 the number of nodes, or 0 if the limit is unknown.]
41
42 SideEffects []
43
44 SeeAlso []
45
46 ***********************************************************************/
Aig_ManStart(int nNodesMax)47 Aig_Man_t * Aig_ManStart( int nNodesMax )
48 {
49 Aig_Man_t * p;
50 if ( nNodesMax <= 0 )
51 nNodesMax = 10007;
52 // start the manager
53 p = ABC_ALLOC( Aig_Man_t, 1 );
54 memset( p, 0, sizeof(Aig_Man_t) );
55 // perform initializations
56 p->nTravIds = 1;
57 p->fCatchExor = 0;
58 // allocate arrays for nodes
59 p->vCis = Vec_PtrAlloc( 100 );
60 p->vCos = Vec_PtrAlloc( 100 );
61 p->vObjs = Vec_PtrAlloc( 1000 );
62 p->vBufs = Vec_PtrAlloc( 100 );
63 //--jlong -- begin
64 p->unfold2_type_I = Vec_PtrAlloc( 4);
65 p->unfold2_type_II = Vec_PtrAlloc( 4);
66 //--jlong -- end
67 // prepare the internal memory manager
68 p->pMemObjs = Aig_MmFixedStart( sizeof(Aig_Obj_t), nNodesMax );
69 // create the constant node
70 p->pConst1 = Aig_ManFetchMemory( p );
71 p->pConst1->Type = AIG_OBJ_CONST1;
72 p->pConst1->fPhase = 1;
73 p->nObjs[AIG_OBJ_CONST1]++;
74 // start the table
75 p->nTableSize = Abc_PrimeCudd( nNodesMax );
76 p->pTable = ABC_ALLOC( Aig_Obj_t *, p->nTableSize );
77 memset( p->pTable, 0, sizeof(Aig_Obj_t *) * p->nTableSize );
78 return p;
79 }
80
81 /**Function*************************************************************
82
83 Synopsis [Duplicates the AIG manager.]
84
85 Description []
86
87 SideEffects []
88
89 SeeAlso []
90
91 ***********************************************************************/
Aig_ManStartFrom(Aig_Man_t * p)92 Aig_Man_t * Aig_ManStartFrom( Aig_Man_t * p )
93 {
94 Aig_Man_t * pNew;
95 Aig_Obj_t * pObj, * pObjNew;
96 int i;
97 // create the new manager
98 pNew = Aig_ManStart( Aig_ManObjNumMax(p) );
99 pNew->pName = Abc_UtilStrsav( p->pName );
100 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
101 // create the PIs
102 Aig_ManConst1(p)->pData = Aig_ManConst1(pNew);
103 Aig_ManForEachCi( p, pObj, i )
104 {
105 pObjNew = Aig_ObjCreateCi( pNew );
106 pObjNew->Level = pObj->Level;
107 pObj->pData = pObjNew;
108 }
109 return pNew;
110 }
111
112 /**Function*************************************************************
113
114 Synopsis [Duplicates the AIG manager recursively.]
115
116 Description []
117
118 SideEffects []
119
120 SeeAlso []
121
122 ***********************************************************************/
Aig_ManDup_rec(Aig_Man_t * pNew,Aig_Man_t * p,Aig_Obj_t * pObj)123 Aig_Obj_t * Aig_ManDup_rec( Aig_Man_t * pNew, Aig_Man_t * p, Aig_Obj_t * pObj )
124 {
125 Aig_Obj_t * pObjNew;
126 if ( pObj->pData )
127 return (Aig_Obj_t *)pObj->pData;
128 Aig_ManDup_rec( pNew, p, Aig_ObjFanin0(pObj) );
129 if ( Aig_ObjIsBuf(pObj) )
130 return (Aig_Obj_t *)(pObj->pData = Aig_ObjChild0Copy(pObj));
131 Aig_ManDup_rec( pNew, p, Aig_ObjFanin1(pObj) );
132 pObjNew = Aig_Oper( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj), Aig_ObjType(pObj) );
133 return (Aig_Obj_t *)(pObj->pData = pObjNew);
134 }
135
136 /**Function*************************************************************
137
138 Synopsis [Extracts the miter composed of XOR of the two nodes.]
139
140 Description []
141
142 SideEffects []
143
144 SeeAlso []
145
146 ***********************************************************************/
Aig_ManExtractMiter(Aig_Man_t * p,Aig_Obj_t * pNode1,Aig_Obj_t * pNode2)147 Aig_Man_t * Aig_ManExtractMiter( Aig_Man_t * p, Aig_Obj_t * pNode1, Aig_Obj_t * pNode2 )
148 {
149 Aig_Man_t * pNew;
150 Aig_Obj_t * pObj;
151 int i;
152 // create the new manager
153 pNew = Aig_ManStart( Aig_ManObjNumMax(p) );
154 pNew->pName = Abc_UtilStrsav( p->pName );
155 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
156 // create the PIs
157 Aig_ManCleanData( p );
158 Aig_ManConst1(p)->pData = Aig_ManConst1(pNew);
159 Aig_ManForEachCi( p, pObj, i )
160 pObj->pData = Aig_ObjCreateCi(pNew);
161 // dump the nodes
162 Aig_ManDup_rec( pNew, p, pNode1 );
163 Aig_ManDup_rec( pNew, p, pNode2 );
164 // construct the EXOR
165 pObj = Aig_Exor( pNew, (Aig_Obj_t *)pNode1->pData, (Aig_Obj_t *)pNode2->pData );
166 pObj = Aig_NotCond( pObj, Aig_Regular(pObj)->fPhase ^ Aig_IsComplement(pObj) );
167 // add the PO
168 Aig_ObjCreateCo( pNew, pObj );
169 // check the resulting network
170 if ( !Aig_ManCheck(pNew) )
171 printf( "Aig_ManExtractMiter(): The check has failed.\n" );
172 return pNew;
173 }
174
175
176 /**Function*************************************************************
177
178 Synopsis [Stops the AIG manager.]
179
180 Description []
181
182 SideEffects []
183
184 SeeAlso []
185
186 ***********************************************************************/
Aig_ManStop(Aig_Man_t * p)187 void Aig_ManStop( Aig_Man_t * p )
188 {
189 Aig_Obj_t * pObj;
190 int i;
191 if ( p->time1 ) { ABC_PRT( "time1", p->time1 ); }
192 if ( p->time2 ) { ABC_PRT( "time2", p->time2 ); }
193 // make sure the nodes have clean marks
194 Aig_ManForEachObj( p, pObj, i )
195 assert( !pObj->fMarkA && !pObj->fMarkB );
196 Tim_ManStopP( (Tim_Man_t **)&p->pManTime );
197 if ( p->pFanData )
198 Aig_ManFanoutStop( p );
199 if ( p->pManExdc )
200 Aig_ManStop( p->pManExdc );
201 // Aig_TableProfile( p );
202 Aig_MmFixedStop( p->pMemObjs, 0 );
203 Vec_PtrFreeP( &p->vCis );
204 Vec_PtrFreeP( &p->vCos );
205 Vec_PtrFreeP( &p->vObjs );
206 Vec_PtrFreeP( &p->vBufs );
207 //--jlong -- begin
208 Vec_PtrFreeP( &p->unfold2_type_I );
209 Vec_PtrFreeP( &p->unfold2_type_II );
210 //--jlong -- end
211 Vec_IntFreeP( &p->vLevelR );
212 Vec_VecFreeP( &p->vLevels );
213 Vec_IntFreeP( &p->vFlopNums );
214 Vec_IntFreeP( &p->vFlopReprs );
215 Vec_VecFreeP( (Vec_Vec_t **)&p->vOnehots );
216 Vec_VecFreeP( &p->vClockDoms );
217 Vec_IntFreeP( &p->vProbs );
218 Vec_IntFreeP( &p->vCiNumsOrig );
219 Vec_PtrFreeP( &p->vMapped );
220 if ( p->vSeqModelVec )
221 Vec_PtrFreeFree( p->vSeqModelVec );
222 ABC_FREE( p->pTerSimData );
223 ABC_FREE( p->pFastSim );
224 ABC_FREE( p->pData );
225 ABC_FREE( p->pSeqModel );
226 ABC_FREE( p->pName );
227 ABC_FREE( p->pSpec );
228 ABC_FREE( p->pObjCopies );
229 ABC_FREE( p->pReprs );
230 ABC_FREE( p->pEquivs );
231 ABC_FREE( p->pTable );
232 ABC_FREE( p );
233 }
234
235 /**Function*************************************************************
236
237 Synopsis [Stops the AIG manager.]
238
239 Description []
240
241 SideEffects []
242
243 SeeAlso []
244
245 ***********************************************************************/
Aig_ManStopP(Aig_Man_t ** p)246 void Aig_ManStopP( Aig_Man_t ** p )
247 {
248 if ( *p == NULL )
249 return;
250 Aig_ManStop( *p );
251 *p = NULL;
252 }
253
254 /**Function*************************************************************
255
256 Synopsis [Removes combinational logic that does not feed into POs.]
257
258 Description [Returns the number of dangling nodes removed.]
259
260 SideEffects []
261
262 SeeAlso []
263
264 ***********************************************************************/
Aig_ManCleanup(Aig_Man_t * p)265 int Aig_ManCleanup( Aig_Man_t * p )
266 {
267 Vec_Ptr_t * vObjs;
268 Aig_Obj_t * pNode;
269 int i, nNodesOld = Aig_ManNodeNum(p);
270 // collect roots of dangling nodes
271 vObjs = Vec_PtrAlloc( 100 );
272 Aig_ManForEachObj( p, pNode, i )
273 if ( Aig_ObjIsNode(pNode) && Aig_ObjRefs(pNode) == 0 )
274 Vec_PtrPush( vObjs, pNode );
275 // recursively remove dangling nodes
276 Vec_PtrForEachEntry( Aig_Obj_t *, vObjs, pNode, i )
277 Aig_ObjDelete_rec( p, pNode, 1 );
278 Vec_PtrFree( vObjs );
279 return nNodesOld - Aig_ManNodeNum(p);
280 }
281
282 /**Function*************************************************************
283
284 Synopsis [Adds POs for the nodes that otherwise would be dangling.]
285
286 Description [Returns the number of POs added.]
287
288 SideEffects []
289
290 SeeAlso []
291
292 ***********************************************************************/
Aig_ManAntiCleanup(Aig_Man_t * p)293 int Aig_ManAntiCleanup( Aig_Man_t * p )
294 {
295 Aig_Obj_t * pNode;
296 int i, nNodesOld = Aig_ManCoNum(p);
297 Aig_ManForEachObj( p, pNode, i )
298 if ( Aig_ObjIsNode(pNode) && Aig_ObjRefs(pNode) == 0 )
299 Aig_ObjCreateCo( p, pNode );
300 return nNodesOld - Aig_ManCoNum(p);
301 }
302
303 /**Function*************************************************************
304
305 Synopsis [Removes PIs without fanouts.]
306
307 Description [Returns the number of PIs removed.]
308
309 SideEffects []
310
311 SeeAlso []
312
313 ***********************************************************************/
Aig_ManCiCleanup(Aig_Man_t * p)314 int Aig_ManCiCleanup( Aig_Man_t * p )
315 {
316 Aig_Obj_t * pObj;
317 int i, k = 0, nPisOld = Aig_ManCiNum(p);
318 Vec_PtrForEachEntry( Aig_Obj_t *, p->vCis, pObj, i )
319 {
320 if ( i >= Aig_ManCiNum(p) - Aig_ManRegNum(p) )
321 Vec_PtrWriteEntry( p->vCis, k++, pObj );
322 else if ( Aig_ObjRefs(pObj) > 0 )
323 Vec_PtrWriteEntry( p->vCis, k++, pObj );
324 else
325 Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
326 }
327 Vec_PtrShrink( p->vCis, k );
328 p->nObjs[AIG_OBJ_CI] = Vec_PtrSize( p->vCis );
329 if ( Aig_ManRegNum(p) )
330 p->nTruePis = Aig_ManCiNum(p) - Aig_ManRegNum(p);
331 return nPisOld - Aig_ManCiNum(p);
332 }
333
334 /**Function*************************************************************
335
336 Synopsis [Removes POs with constant input.]
337
338 Description [Returns the number of POs removed.]
339
340 SideEffects []
341
342 SeeAlso []
343
344 ***********************************************************************/
Aig_ManCoCleanup(Aig_Man_t * p)345 int Aig_ManCoCleanup( Aig_Man_t * p )
346 {
347 Aig_Obj_t * pObj;
348 int i, k = 0, nPosOld = Aig_ManCoNum(p);
349 Vec_PtrForEachEntry( Aig_Obj_t *, p->vCos, pObj, i )
350 {
351 if ( i >= Aig_ManCoNum(p) - Aig_ManRegNum(p) )
352 Vec_PtrWriteEntry( p->vCos, k++, pObj );
353 else if ( !Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) || !Aig_ObjFaninC0(pObj) ) // non-const or const1
354 Vec_PtrWriteEntry( p->vCos, k++, pObj );
355 else
356 {
357 Aig_ObjDisconnect( p, pObj );
358 Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
359 }
360 }
361 Vec_PtrShrink( p->vCos, k );
362 p->nObjs[AIG_OBJ_CO] = Vec_PtrSize( p->vCos );
363 if ( Aig_ManRegNum(p) )
364 p->nTruePos = Aig_ManCoNum(p) - Aig_ManRegNum(p);
365 return nPosOld - Aig_ManCoNum(p);
366 }
367
368 /**Function*************************************************************
369
370 Synopsis [Stops the AIG manager.]
371
372 Description []
373
374 SideEffects []
375
376 SeeAlso []
377
378 ***********************************************************************/
Aig_ManPrintStats(Aig_Man_t * p)379 void Aig_ManPrintStats( Aig_Man_t * p )
380 {
381 int nChoices = Aig_ManChoiceNum(p);
382 printf( "%-15s : ", p->pName );
383 printf( "pi = %5d ", Aig_ManCiNum(p)-Aig_ManRegNum(p) );
384 printf( "po = %5d ", Aig_ManCoNum(p)-Aig_ManRegNum(p) );
385 if ( Aig_ManRegNum(p) )
386 printf( "lat = %5d ", Aig_ManRegNum(p) );
387 printf( "and = %7d ", Aig_ManAndNum(p) );
388 // printf( "Eq = %7d ", Aig_ManHaigCounter(p) );
389 if ( Aig_ManExorNum(p) )
390 printf( "xor = %5d ", Aig_ManExorNum(p) );
391 if ( nChoices )
392 printf( "ch = %5d ", nChoices );
393 if ( Aig_ManBufNum(p) )
394 printf( "buf = %5d ", Aig_ManBufNum(p) );
395 // printf( "Cre = %6d ", p->nCreated );
396 // printf( "Del = %6d ", p->nDeleted );
397 // printf( "Lev = %3d ", Aig_ManLevelNum(p) );
398 // printf( "Max = %7d ", Aig_ManObjNumMax(p) );
399 printf( "lev = %3d", Aig_ManLevels(p) );
400 printf( "\n" );
401 fflush( stdout );
402 }
403
404 /**Function*************************************************************
405
406 Synopsis [Reports the reduction of the AIG.]
407
408 Description []
409
410 SideEffects []
411
412 SeeAlso []
413
414 ***********************************************************************/
Aig_ManReportImprovement(Aig_Man_t * p,Aig_Man_t * pNew)415 void Aig_ManReportImprovement( Aig_Man_t * p, Aig_Man_t * pNew )
416 {
417 printf( "REG: Beg = %5d. End = %5d. (R =%5.1f %%) ",
418 Aig_ManRegNum(p), Aig_ManRegNum(pNew),
419 Aig_ManRegNum(p)? 100.0*(Aig_ManRegNum(p)-Aig_ManRegNum(pNew))/Aig_ManRegNum(p) : 0.0 );
420 printf( "AND: Beg = %6d. End = %6d. (R =%5.1f %%)",
421 Aig_ManNodeNum(p), Aig_ManNodeNum(pNew),
422 Aig_ManNodeNum(p)? 100.0*(Aig_ManNodeNum(p)-Aig_ManNodeNum(pNew))/Aig_ManNodeNum(p) : 0.0 );
423 printf( "\n" );
424 }
425
426 /**Function*************************************************************
427
428 Synopsis [Sets the number of registers in the AIG manager.]
429
430 Description [This procedure should be called after the manager is
431 fully constructed.]
432
433 SideEffects []
434
435 SeeAlso []
436
437 ***********************************************************************/
Aig_ManSetRegNum(Aig_Man_t * p,int nRegs)438 void Aig_ManSetRegNum( Aig_Man_t * p, int nRegs )
439 {
440 p->nRegs = nRegs;
441 p->nTruePis = Aig_ManCiNum(p) - nRegs;
442 p->nTruePos = Aig_ManCoNum(p) - nRegs;
443 Aig_ManSetCioIds( p );
444 }
445
446 /**Function*************************************************************
447
448 Synopsis []
449
450 Description []
451
452 SideEffects []
453
454 SeeAlso []
455
456 ***********************************************************************/
Aig_ManFlipFirstPo(Aig_Man_t * p)457 void Aig_ManFlipFirstPo( Aig_Man_t * p )
458 {
459 Aig_ObjChild0Flip( Aig_ManCo(p, 0) );
460 }
461
462 /**Function*************************************************************
463
464 Synopsis []
465
466 Description []
467
468 SideEffects []
469
470 SeeAlso []
471
472 ***********************************************************************/
Aig_ManReleaseData(Aig_Man_t * p)473 void * Aig_ManReleaseData( Aig_Man_t * p )
474 {
475 void * pD = p->pData;
476 p->pData = NULL;
477 return pD;
478 }
479
480 ////////////////////////////////////////////////////////////////////////
481 /// END OF FILE ///
482 ////////////////////////////////////////////////////////////////////////
483
484
485 ABC_NAMESPACE_IMPL_END
486
487