1 /**CFile****************************************************************
2
3 FileName [ivyMan.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [And-Inverter Graph package.]
8
9 Synopsis [AIG manager.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006.]
16
17 Revision [$Id: ivy_.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "ivy.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 [Starts the AIG manager.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Ivy_ManStart()45 Ivy_Man_t * Ivy_ManStart()
46 {
47 Ivy_Man_t * p;
48 // start the manager
49 p = ABC_ALLOC( Ivy_Man_t, 1 );
50 memset( p, 0, sizeof(Ivy_Man_t) );
51 // perform initializations
52 p->Ghost.Id = -1;
53 p->nTravIds = 1;
54 p->fCatchExor = 1;
55 // allocate arrays for nodes
56 p->vPis = Vec_PtrAlloc( 100 );
57 p->vPos = Vec_PtrAlloc( 100 );
58 p->vBufs = Vec_PtrAlloc( 100 );
59 p->vObjs = Vec_PtrAlloc( 100 );
60 // prepare the internal memory manager
61 Ivy_ManStartMemory( p );
62 // create the constant node
63 p->pConst1 = Ivy_ManFetchMemory( p );
64 p->pConst1->fPhase = 1;
65 Vec_PtrPush( p->vObjs, p->pConst1 );
66 p->nCreated = 1;
67 // start the table
68 p->nTableSize = 10007;
69 p->pTable = ABC_ALLOC( int, p->nTableSize );
70 memset( p->pTable, 0, sizeof(int) * p->nTableSize );
71 return p;
72 }
73
74 /**Function*************************************************************
75
76 Synopsis [Duplicates the AIG manager.]
77
78 Description []
79
80 SideEffects []
81
82 SeeAlso []
83
84 ***********************************************************************/
Ivy_ManStartFrom(Ivy_Man_t * p)85 Ivy_Man_t * Ivy_ManStartFrom( Ivy_Man_t * p )
86 {
87 Ivy_Man_t * pNew;
88 Ivy_Obj_t * pObj;
89 int i;
90 // create the new manager
91 pNew = Ivy_ManStart();
92 // create the PIs
93 Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
94 Ivy_ManForEachPi( p, pObj, i )
95 pObj->pEquiv = Ivy_ObjCreatePi(pNew);
96 return pNew;
97 }
98
99 /**Function*************************************************************
100
101 Synopsis [Duplicates the AIG manager.]
102
103 Description []
104
105 SideEffects []
106
107 SeeAlso []
108
109 ***********************************************************************/
Ivy_ManDup(Ivy_Man_t * p)110 Ivy_Man_t * Ivy_ManDup( Ivy_Man_t * p )
111 {
112 Vec_Int_t * vNodes, * vLatches;
113 Ivy_Man_t * pNew;
114 Ivy_Obj_t * pObj;
115 int i;
116 // collect latches and nodes in the DFS order
117 vNodes = Ivy_ManDfsSeq( p, &vLatches );
118 // create the new manager
119 pNew = Ivy_ManStart();
120 // create the PIs
121 Ivy_ManConst1(p)->pEquiv = Ivy_ManConst1(pNew);
122 Ivy_ManForEachPi( p, pObj, i )
123 pObj->pEquiv = Ivy_ObjCreatePi(pNew);
124 // create the fake PIs for latches
125 Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
126 pObj->pEquiv = Ivy_ObjCreatePi(pNew);
127 // duplicate internal nodes
128 Ivy_ManForEachNodeVec( p, vNodes, pObj, i )
129 if ( Ivy_ObjIsBuf(pObj) )
130 pObj->pEquiv = Ivy_ObjChild0Equiv(pObj);
131 else
132 pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
133 // add the POs
134 Ivy_ManForEachPo( p, pObj, i )
135 Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(pObj) );
136 // transform additional PI nodes into latches and connect them
137 Ivy_ManForEachNodeVec( p, vLatches, pObj, i )
138 {
139 assert( !Ivy_ObjFaninC0(pObj) );
140 pObj->pEquiv->Type = IVY_LATCH;
141 pObj->pEquiv->Init = pObj->Init;
142 Ivy_ObjConnect( pNew, pObj->pEquiv, Ivy_ObjChild0Equiv(pObj), NULL );
143 }
144 // shrink the arrays
145 Vec_PtrShrink( pNew->vPis, Ivy_ManPiNum(p) );
146 // update the counters of different objects
147 pNew->nObjs[IVY_PI] -= Ivy_ManLatchNum(p);
148 pNew->nObjs[IVY_LATCH] += Ivy_ManLatchNum(p);
149 // free arrays
150 Vec_IntFree( vNodes );
151 Vec_IntFree( vLatches );
152 // make sure structural hashing did not change anything
153 assert( Ivy_ManNodeNum(p) == Ivy_ManNodeNum(pNew) );
154 assert( Ivy_ManLatchNum(p) == Ivy_ManLatchNum(pNew) );
155 // check the resulting network
156 if ( !Ivy_ManCheck(pNew) )
157 printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
158 return pNew;
159 }
160
161 /**Function*************************************************************
162
163 Synopsis [Stops the AIG manager.]
164
165 Description []
166
167 SideEffects []
168
169 SeeAlso []
170
171 ***********************************************************************/
Ivy_ManFrames(Ivy_Man_t * pMan,int nLatches,int nFrames,int fInit,Vec_Ptr_t ** pvMapping)172 Ivy_Man_t * Ivy_ManFrames( Ivy_Man_t * pMan, int nLatches, int nFrames, int fInit, Vec_Ptr_t ** pvMapping )
173 {
174 Vec_Ptr_t * vMapping;
175 Ivy_Man_t * pNew;
176 Ivy_Obj_t * pObj;
177 int i, f, nPis, nPos, nIdMax;
178 assert( Ivy_ManLatchNum(pMan) == 0 );
179 assert( nFrames > 0 );
180 // prepare the mapping
181 nPis = Ivy_ManPiNum(pMan) - nLatches;
182 nPos = Ivy_ManPoNum(pMan) - nLatches;
183 nIdMax = Ivy_ManObjIdMax(pMan);
184 // create the new manager
185 pNew = Ivy_ManStart();
186 // set the starting values of latch inputs
187 for ( i = 0; i < nLatches; i++ )
188 Ivy_ManPo(pMan, nPos+i)->pEquiv = fInit? Ivy_Not(Ivy_ManConst1(pNew)) : Ivy_ObjCreatePi(pNew);
189 // add timeframes
190 vMapping = Vec_PtrStart( nIdMax * nFrames + 1 );
191 for ( f = 0; f < nFrames; f++ )
192 {
193 // create PIs
194 Ivy_ManConst1(pMan)->pEquiv = Ivy_ManConst1(pNew);
195 for ( i = 0; i < nPis; i++ )
196 Ivy_ManPi(pMan, i)->pEquiv = Ivy_ObjCreatePi(pNew);
197 // transfer values to latch outputs
198 for ( i = 0; i < nLatches; i++ )
199 Ivy_ManPi(pMan, nPis+i)->pEquiv = Ivy_ManPo(pMan, nPos+i)->pEquiv;
200 // perform strashing
201 Ivy_ManForEachNode( pMan, pObj, i )
202 pObj->pEquiv = Ivy_And( pNew, Ivy_ObjChild0Equiv(pObj), Ivy_ObjChild1Equiv(pObj) );
203 // create POs
204 for ( i = 0; i < nPos; i++ )
205 Ivy_ManPo(pMan, i)->pEquiv = Ivy_ObjCreatePo( pNew, Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, i)) );
206 // set the results of latch inputs
207 for ( i = 0; i < nLatches; i++ )
208 Ivy_ManPo(pMan, nPos+i)->pEquiv = Ivy_ObjChild0Equiv(Ivy_ManPo(pMan, nPos+i));
209 // save the pointers in this frame
210 Ivy_ManForEachObj( pMan, pObj, i )
211 Vec_PtrWriteEntry( vMapping, f * nIdMax + i, pObj->pEquiv );
212 }
213 // connect latches
214 if ( !fInit )
215 for ( i = 0; i < nLatches; i++ )
216 Ivy_ObjCreatePo( pNew, Ivy_ManPo(pMan, nPos+i)->pEquiv );
217 // remove dangling nodes
218 Ivy_ManCleanup(pNew);
219 *pvMapping = vMapping;
220 // check the resulting network
221 if ( !Ivy_ManCheck(pNew) )
222 printf( "Ivy_ManFrames(): The check has failed.\n" );
223 return pNew;
224 }
225
226
227 /**Function*************************************************************
228
229 Synopsis [Stops the AIG manager.]
230
231 Description []
232
233 SideEffects []
234
235 SeeAlso []
236
237 ***********************************************************************/
Ivy_ManStop(Ivy_Man_t * p)238 void Ivy_ManStop( Ivy_Man_t * p )
239 {
240 if ( p->time1 ) { ABC_PRT( "Update lev ", p->time1 ); }
241 if ( p->time2 ) { ABC_PRT( "Update levR ", p->time2 ); }
242 // Ivy_TableProfile( p );
243 // if ( p->vFanouts ) Ivy_ManStopFanout( p );
244 if ( p->vChunks ) Ivy_ManStopMemory( p );
245 if ( p->vRequired ) Vec_IntFree( p->vRequired );
246 if ( p->vPis ) Vec_PtrFree( p->vPis );
247 if ( p->vPos ) Vec_PtrFree( p->vPos );
248 if ( p->vBufs ) Vec_PtrFree( p->vBufs );
249 if ( p->vObjs ) Vec_PtrFree( p->vObjs );
250 ABC_FREE( p->pTable );
251 ABC_FREE( p );
252 }
253
254 /**Function*************************************************************
255
256 Synopsis [Removes nodes without fanout.]
257
258 Description [Returns the number of dangling nodes removed.]
259
260 SideEffects []
261
262 SeeAlso []
263
264 ***********************************************************************/
Ivy_ManCleanup(Ivy_Man_t * p)265 int Ivy_ManCleanup( Ivy_Man_t * p )
266 {
267 Ivy_Obj_t * pNode;
268 int i, nNodesOld;
269 nNodesOld = Ivy_ManNodeNum(p);
270 Ivy_ManForEachObj( p, pNode, i )
271 if ( Ivy_ObjIsNode(pNode) || Ivy_ObjIsLatch(pNode) || Ivy_ObjIsBuf(pNode) )
272 if ( Ivy_ObjRefs(pNode) == 0 )
273 Ivy_ObjDelete_rec( p, pNode, 1 );
274 //printf( "Cleanup removed %d nodes.\n", nNodesOld - Ivy_ManNodeNum(p) );
275 return nNodesOld - Ivy_ManNodeNum(p);
276 }
277
278 /**Function*************************************************************
279
280 Synopsis [Marks nodes reachable from the given one.]
281
282 Description [Returns the number of dangling nodes removed.]
283
284 SideEffects []
285
286 SeeAlso []
287
288 ***********************************************************************/
Ivy_ManCleanupSeq_rec(Ivy_Obj_t * pObj)289 void Ivy_ManCleanupSeq_rec( Ivy_Obj_t * pObj )
290 {
291 if ( Ivy_ObjIsMarkA(pObj) )
292 return;
293 Ivy_ObjSetMarkA(pObj);
294 if ( pObj->pFanin0 != NULL )
295 Ivy_ManCleanupSeq_rec( Ivy_ObjFanin0(pObj) );
296 if ( pObj->pFanin1 != NULL )
297 Ivy_ManCleanupSeq_rec( Ivy_ObjFanin1(pObj) );
298 }
299
300 /**Function*************************************************************
301
302 Synopsis [Removes logic that does not feed into POs.]
303
304 Description [Returns the number of dangling nodes removed.]
305
306 SideEffects []
307
308 SeeAlso []
309
310 ***********************************************************************/
Ivy_ManCleanupSeq(Ivy_Man_t * p)311 int Ivy_ManCleanupSeq( Ivy_Man_t * p )
312 {
313 Vec_Ptr_t * vNodes;
314 Ivy_Obj_t * pObj;
315 int i, RetValue;
316 // mark the constant and PIs
317 Ivy_ObjSetMarkA( Ivy_ManConst1(p) );
318 Ivy_ManForEachPi( p, pObj, i )
319 Ivy_ObjSetMarkA( pObj );
320 // mark nodes visited from POs
321 Ivy_ManForEachPo( p, pObj, i )
322 Ivy_ManCleanupSeq_rec( pObj );
323 // collect unmarked nodes
324 vNodes = Vec_PtrAlloc( 100 );
325 Ivy_ManForEachObj( p, pObj, i )
326 {
327 if ( Ivy_ObjIsMarkA(pObj) )
328 Ivy_ObjClearMarkA(pObj);
329 else
330 Vec_PtrPush( vNodes, pObj );
331 }
332 if ( Vec_PtrSize(vNodes) == 0 )
333 {
334 Vec_PtrFree( vNodes );
335 //printf( "Sequential sweep cleaned out %d nodes.\n", 0 );
336 return 0;
337 }
338 // disconnect the marked objects
339 Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, i )
340 Ivy_ObjDisconnect( p, pObj );
341 // remove the dangling objects
342 Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, i )
343 {
344 assert( Ivy_ObjIsNode(pObj) || Ivy_ObjIsLatch(pObj) || Ivy_ObjIsBuf(pObj) );
345 assert( Ivy_ObjRefs(pObj) == 0 );
346 // update node counters of the manager
347 p->nObjs[pObj->Type]--;
348 p->nDeleted++;
349 // delete buffer from the array of buffers
350 if ( p->fFanout && Ivy_ObjIsBuf(pObj) )
351 Vec_PtrRemove( p->vBufs, pObj );
352 // free the node
353 Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
354 Ivy_ManRecycleMemory( p, pObj );
355 }
356 // return the number of nodes freed
357 RetValue = Vec_PtrSize(vNodes);
358 Vec_PtrFree( vNodes );
359 //printf( "Sequential sweep cleaned out %d nodes.\n", RetValue );
360 return RetValue;
361 }
362
363
364 /**Function*************************************************************
365
366 Synopsis [Checks if latches form self-loop.]
367
368 Description []
369
370 SideEffects []
371
372 SeeAlso []
373
374 ***********************************************************************/
Ivy_ManLatchIsSelfFeed_rec(Ivy_Obj_t * pLatch,Ivy_Obj_t * pLatchRoot)375 int Ivy_ManLatchIsSelfFeed_rec( Ivy_Obj_t * pLatch, Ivy_Obj_t * pLatchRoot )
376 {
377 if ( !Ivy_ObjIsLatch(pLatch) && !Ivy_ObjIsBuf(pLatch) )
378 return 0;
379 if ( pLatch == pLatchRoot )
380 return 1;
381 return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatchRoot );
382 }
383
384 /**Function*************************************************************
385
386 Synopsis [Checks if latches form self-loop.]
387
388 Description []
389
390 SideEffects []
391
392 SeeAlso []
393
394 ***********************************************************************/
Ivy_ManLatchIsSelfFeed(Ivy_Obj_t * pLatch)395 int Ivy_ManLatchIsSelfFeed( Ivy_Obj_t * pLatch )
396 {
397 if ( !Ivy_ObjIsLatch(pLatch) )
398 return 0;
399 return Ivy_ManLatchIsSelfFeed_rec( Ivy_ObjFanin0(pLatch), pLatch );
400 }
401
402
403 /**Function*************************************************************
404
405 Synopsis [Returns the number of dangling nodes removed.]
406
407 Description []
408
409 SideEffects []
410
411 SeeAlso []
412
413 ***********************************************************************/
Ivy_ManPropagateBuffers(Ivy_Man_t * p,int fUpdateLevel)414 int Ivy_ManPropagateBuffers( Ivy_Man_t * p, int fUpdateLevel )
415 {
416 Ivy_Obj_t * pNode;
417 int LimitFactor = 100;
418 int NodeBeg = Ivy_ManNodeNum(p);
419 int nSteps;
420 for ( nSteps = 0; Vec_PtrSize(p->vBufs) > 0; nSteps++ )
421 {
422 pNode = (Ivy_Obj_t *)Vec_PtrEntryLast(p->vBufs);
423 while ( Ivy_ObjIsBuf(pNode) )
424 pNode = Ivy_ObjReadFirstFanout( p, pNode );
425 // check if this buffer should remain
426 if ( Ivy_ManLatchIsSelfFeed(pNode) )
427 {
428 Vec_PtrPop(p->vBufs);
429 continue;
430 }
431 //printf( "Propagating buffer %d with input %d and output %d\n", Ivy_ObjFaninId0(pNode), Ivy_ObjFaninId0(Ivy_ObjFanin0(pNode)), pNode->Id );
432 //printf( "Latch num %d\n", Ivy_ManLatchNum(p) );
433 Ivy_NodeFixBufferFanins( p, pNode, fUpdateLevel );
434 if ( nSteps > NodeBeg * LimitFactor )
435 {
436 printf( "Structural hashing is not finished after %d forward latch moves.\n", NodeBeg * LimitFactor );
437 printf( "This circuit cannot be forward-retimed completely. Quitting.\n" );
438 break;
439 }
440 }
441 // printf( "Number of steps = %d. Nodes beg = %d. Nodes end = %d.\n", nSteps, NodeBeg, Ivy_ManNodeNum(p) );
442 return nSteps;
443 }
444
445 /**Function*************************************************************
446
447 Synopsis [Stops the AIG manager.]
448
449 Description []
450
451 SideEffects []
452
453 SeeAlso []
454
455 ***********************************************************************/
Ivy_ManPrintStats(Ivy_Man_t * p)456 void Ivy_ManPrintStats( Ivy_Man_t * p )
457 {
458 printf( "PI/PO = %d/%d ", Ivy_ManPiNum(p), Ivy_ManPoNum(p) );
459 printf( "A = %7d. ", Ivy_ManAndNum(p) );
460 printf( "L = %5d. ", Ivy_ManLatchNum(p) );
461 // printf( "X = %d. ", Ivy_ManExorNum(p) );
462 // printf( "B = %3d. ", Ivy_ManBufNum(p) );
463 printf( "MaxID = %7d. ", Ivy_ManObjIdMax(p) );
464 // printf( "Cre = %d. ", p->nCreated );
465 // printf( "Del = %d. ", p->nDeleted );
466 printf( "Lev = %3d. ", Ivy_ManLatchNum(p)? -1 : Ivy_ManLevels(p) );
467 printf( "\n" );
468 fflush( stdout );
469 }
470
471 /**Function*************************************************************
472
473 Synopsis [Converts a combinational AIG manager into a sequential one.]
474
475 Description []
476
477 SideEffects []
478
479 SeeAlso []
480
481 ***********************************************************************/
Ivy_ManMakeSeq(Ivy_Man_t * p,int nLatches,int * pInits)482 void Ivy_ManMakeSeq( Ivy_Man_t * p, int nLatches, int * pInits )
483 {
484 Ivy_Obj_t * pObj, * pLatch;
485 Ivy_Init_t Init;
486 int i;
487 if ( nLatches == 0 )
488 return;
489 assert( nLatches < Ivy_ManPiNum(p) && nLatches < Ivy_ManPoNum(p) );
490 assert( Ivy_ManPiNum(p) == Vec_PtrSize(p->vPis) );
491 assert( Ivy_ManPoNum(p) == Vec_PtrSize(p->vPos) );
492 assert( Vec_PtrSize( p->vBufs ) == 0 );
493 // create fanouts
494 if ( p->fFanout == 0 )
495 Ivy_ManStartFanout( p );
496 // collect the POs to be converted into latches
497 for ( i = 0; i < nLatches; i++ )
498 {
499 // get the latch value
500 Init = pInits? (Ivy_Init_t)pInits[i] : IVY_INIT_0;
501 // create latch
502 pObj = Ivy_ManPo( p, Ivy_ManPoNum(p) - nLatches + i );
503 pLatch = Ivy_Latch( p, Ivy_ObjChild0(pObj), Init );
504 Ivy_ObjDisconnect( p, pObj );
505 // recycle the old PO object
506 Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
507 Ivy_ManRecycleMemory( p, pObj );
508 // convert the corresponding PI to a buffer and connect it to the latch
509 pObj = Ivy_ManPi( p, Ivy_ManPiNum(p) - nLatches + i );
510 pObj->Type = IVY_BUF;
511 Ivy_ObjConnect( p, pObj, pLatch, NULL );
512 // save the buffer
513 Vec_PtrPush( p->vBufs, pObj );
514 }
515 // shrink the arrays
516 Vec_PtrShrink( p->vPis, Ivy_ManPiNum(p) - nLatches );
517 Vec_PtrShrink( p->vPos, Ivy_ManPoNum(p) - nLatches );
518 // update the counters of different objects
519 p->nObjs[IVY_PI] -= nLatches;
520 p->nObjs[IVY_PO] -= nLatches;
521 p->nObjs[IVY_BUF] += nLatches;
522 p->nDeleted -= 2 * nLatches;
523 // remove dangling nodes
524 Ivy_ManCleanup(p);
525 Ivy_ManCleanupSeq(p);
526 /*
527 // check for dangling nodes
528 Ivy_ManForEachObj( p, pObj, i )
529 if ( !Ivy_ObjIsPi(pObj) && !Ivy_ObjIsPo(pObj) && !Ivy_ObjIsConst1(pObj) )
530 {
531 assert( Ivy_ObjRefs(pObj) > 0 );
532 assert( Ivy_ObjRefs(pObj) == Ivy_ObjFanoutNum(p, pObj) );
533 }
534 */
535 // perform hashing by propagating the buffers
536 Ivy_ManPropagateBuffers( p, 0 );
537 if ( Ivy_ManBufNum(p) )
538 printf( "The number of remaining buffers is %d.\n", Ivy_ManBufNum(p) );
539 // fix the levels
540 Ivy_ManResetLevels( p );
541 // check the resulting network
542 if ( !Ivy_ManCheck(p) )
543 printf( "Ivy_ManMakeSeq(): The check has failed.\n" );
544 }
545
546 ////////////////////////////////////////////////////////////////////////
547 /// END OF FILE ///
548 ////////////////////////////////////////////////////////////////////////
549
550
551 ABC_NAMESPACE_IMPL_END
552
553