1 /**CFile****************************************************************
2
3 FileName [ivyObj.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [And-Inverter Graph package.]
8
9 Synopsis [Adding/removing objects.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006.]
16
17 Revision [$Id: ivyObj.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 [Create the new node assuming it does not exist.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Ivy_ObjCreatePi(Ivy_Man_t * p)45 Ivy_Obj_t * Ivy_ObjCreatePi( Ivy_Man_t * p )
46 {
47 return Ivy_ObjCreate( p, Ivy_ObjCreateGhost(p, NULL, NULL, IVY_PI, IVY_INIT_NONE) );
48 }
49
50 /**Function*************************************************************
51
52 Synopsis [Create the new node assuming it does not exist.]
53
54 Description []
55
56 SideEffects []
57
58 SeeAlso []
59
60 ***********************************************************************/
Ivy_ObjCreatePo(Ivy_Man_t * p,Ivy_Obj_t * pDriver)61 Ivy_Obj_t * Ivy_ObjCreatePo( Ivy_Man_t * p, Ivy_Obj_t * pDriver )
62 {
63 return Ivy_ObjCreate( p, Ivy_ObjCreateGhost(p, pDriver, NULL, IVY_PO, IVY_INIT_NONE) );
64 }
65
66 /**Function*************************************************************
67
68 Synopsis [Create the new node assuming it does not exist.]
69
70 Description []
71
72 SideEffects []
73
74 SeeAlso []
75
76 ***********************************************************************/
Ivy_ObjCreate(Ivy_Man_t * p,Ivy_Obj_t * pGhost)77 Ivy_Obj_t * Ivy_ObjCreate( Ivy_Man_t * p, Ivy_Obj_t * pGhost )
78 {
79 Ivy_Obj_t * pObj;
80 assert( !Ivy_IsComplement(pGhost) );
81 assert( Ivy_ObjIsGhost(pGhost) );
82 assert( Ivy_TableLookup(p, pGhost) == NULL );
83 // get memory for the new object
84 pObj = Ivy_ManFetchMemory( p );
85 assert( Ivy_ObjIsNone(pObj) );
86 pObj->Id = Vec_PtrSize(p->vObjs);
87 Vec_PtrPush( p->vObjs, pObj );
88 // add basic info (fanins, compls, type, init)
89 pObj->Type = pGhost->Type;
90 pObj->Init = pGhost->Init;
91 // add connections
92 Ivy_ObjConnect( p, pObj, pGhost->pFanin0, pGhost->pFanin1 );
93 // compute level
94 if ( Ivy_ObjIsNode(pObj) )
95 pObj->Level = Ivy_ObjLevelNew(pObj);
96 else if ( Ivy_ObjIsLatch(pObj) )
97 pObj->Level = 0;
98 else if ( Ivy_ObjIsOneFanin(pObj) )
99 pObj->Level = Ivy_ObjFanin0(pObj)->Level;
100 else if ( !Ivy_ObjIsPi(pObj) )
101 assert( 0 );
102 // create phase
103 if ( Ivy_ObjIsNode(pObj) )
104 pObj->fPhase = Ivy_ObjFaninPhase(Ivy_ObjChild0(pObj)) & Ivy_ObjFaninPhase(Ivy_ObjChild1(pObj));
105 else if ( Ivy_ObjIsOneFanin(pObj) )
106 pObj->fPhase = Ivy_ObjFaninPhase(Ivy_ObjChild0(pObj));
107 // set the fail TFO flag
108 if ( Ivy_ObjIsNode(pObj) )
109 pObj->fFailTfo = Ivy_ObjFanin0(pObj)->fFailTfo | Ivy_ObjFanin1(pObj)->fFailTfo;
110 // mark the fanins in a special way if the node is EXOR
111 if ( Ivy_ObjIsExor(pObj) )
112 {
113 Ivy_ObjFanin0(pObj)->fExFan = 1;
114 Ivy_ObjFanin1(pObj)->fExFan = 1;
115 }
116 // add PIs/POs to the arrays
117 if ( Ivy_ObjIsPi(pObj) )
118 Vec_PtrPush( p->vPis, pObj );
119 else if ( Ivy_ObjIsPo(pObj) )
120 Vec_PtrPush( p->vPos, pObj );
121 // else if ( Ivy_ObjIsBuf(pObj) )
122 // Vec_PtrPush( p->vBufs, pObj );
123 if ( p->vRequired && Vec_IntSize(p->vRequired) <= pObj->Id )
124 Vec_IntFillExtra( p->vRequired, 2 * Vec_IntSize(p->vRequired), 1000000 );
125 // update node counters of the manager
126 p->nObjs[Ivy_ObjType(pObj)]++;
127 p->nCreated++;
128
129 // printf( "Adding %sAIG node: ", p->pHaig==NULL? "H":" " );
130 // Ivy_ObjPrintVerbose( p, pObj, p->pHaig==NULL );
131 // printf( "\n" );
132
133 // if HAIG is defined, create a corresponding node
134 if ( p->pHaig )
135 Ivy_ManHaigCreateObj( p, pObj );
136 return pObj;
137 }
138
139 /**Function*************************************************************
140
141 Synopsis [Connect the object to the fanin.]
142
143 Description []
144
145 SideEffects []
146
147 SeeAlso []
148
149 ***********************************************************************/
Ivy_ObjConnect(Ivy_Man_t * p,Ivy_Obj_t * pObj,Ivy_Obj_t * pFan0,Ivy_Obj_t * pFan1)150 void Ivy_ObjConnect( Ivy_Man_t * p, Ivy_Obj_t * pObj, Ivy_Obj_t * pFan0, Ivy_Obj_t * pFan1 )
151 {
152 assert( !Ivy_IsComplement(pObj) );
153 assert( Ivy_ObjIsPi(pObj) || Ivy_ObjIsOneFanin(pObj) || pFan1 != NULL );
154 // add the first fanin
155 pObj->pFanin0 = pFan0;
156 pObj->pFanin1 = pFan1;
157 // increment references of the fanins and add their fanouts
158 if ( Ivy_ObjFanin0(pObj) != NULL )
159 {
160 Ivy_ObjRefsInc( Ivy_ObjFanin0(pObj) );
161 if ( p->fFanout )
162 Ivy_ObjAddFanout( p, Ivy_ObjFanin0(pObj), pObj );
163 }
164 if ( Ivy_ObjFanin1(pObj) != NULL )
165 {
166 Ivy_ObjRefsInc( Ivy_ObjFanin1(pObj) );
167 if ( p->fFanout )
168 Ivy_ObjAddFanout( p, Ivy_ObjFanin1(pObj), pObj );
169 }
170 // add the node to the structural hash table
171 Ivy_TableInsert( p, pObj );
172 }
173
174 /**Function*************************************************************
175
176 Synopsis [Connect the object to the fanin.]
177
178 Description []
179
180 SideEffects []
181
182 SeeAlso []
183
184 ***********************************************************************/
Ivy_ObjDisconnect(Ivy_Man_t * p,Ivy_Obj_t * pObj)185 void Ivy_ObjDisconnect( Ivy_Man_t * p, Ivy_Obj_t * pObj )
186 {
187 assert( !Ivy_IsComplement(pObj) );
188 assert( Ivy_ObjIsPi(pObj) || Ivy_ObjIsOneFanin(pObj) || Ivy_ObjFanin1(pObj) != NULL );
189 // remove connections
190 if ( pObj->pFanin0 != NULL )
191 {
192 Ivy_ObjRefsDec(Ivy_ObjFanin0(pObj));
193 if ( p->fFanout )
194 Ivy_ObjDeleteFanout( p, Ivy_ObjFanin0(pObj), pObj );
195 }
196 if ( pObj->pFanin1 != NULL )
197 {
198 Ivy_ObjRefsDec(Ivy_ObjFanin1(pObj));
199 if ( p->fFanout )
200 Ivy_ObjDeleteFanout( p, Ivy_ObjFanin1(pObj), pObj );
201 }
202 assert( pObj->pNextFan0 == NULL );
203 assert( pObj->pNextFan1 == NULL );
204 assert( pObj->pPrevFan0 == NULL );
205 assert( pObj->pPrevFan1 == NULL );
206 // remove the node from the structural hash table
207 Ivy_TableDelete( p, pObj );
208 // add the first fanin
209 pObj->pFanin0 = NULL;
210 pObj->pFanin1 = NULL;
211 }
212
213 /**Function*************************************************************
214
215 Synopsis [Replaces the first fanin of the node by the new fanin.]
216
217 Description []
218
219 SideEffects []
220
221 SeeAlso []
222
223 ***********************************************************************/
Ivy_ObjPatchFanin0(Ivy_Man_t * p,Ivy_Obj_t * pObj,Ivy_Obj_t * pFaninNew)224 void Ivy_ObjPatchFanin0( Ivy_Man_t * p, Ivy_Obj_t * pObj, Ivy_Obj_t * pFaninNew )
225 {
226 Ivy_Obj_t * pFaninOld;
227 assert( !Ivy_IsComplement(pObj) );
228 pFaninOld = Ivy_ObjFanin0(pObj);
229 // decrement ref and remove fanout
230 Ivy_ObjRefsDec( pFaninOld );
231 if ( p->fFanout )
232 Ivy_ObjDeleteFanout( p, pFaninOld, pObj );
233 // update the fanin
234 pObj->pFanin0 = pFaninNew;
235 // increment ref and add fanout
236 Ivy_ObjRefsInc( Ivy_Regular(pFaninNew) );
237 if ( p->fFanout )
238 Ivy_ObjAddFanout( p, Ivy_Regular(pFaninNew), pObj );
239 // get rid of old fanin
240 if ( !Ivy_ObjIsPi(pFaninOld) && !Ivy_ObjIsConst1(pFaninOld) && Ivy_ObjRefs(pFaninOld) == 0 )
241 Ivy_ObjDelete_rec( p, pFaninOld, 1 );
242 }
243
244 /**Function*************************************************************
245
246 Synopsis [Deletes the node.]
247
248 Description []
249
250 SideEffects []
251
252 SeeAlso []
253
254 ***********************************************************************/
Ivy_ObjDelete(Ivy_Man_t * p,Ivy_Obj_t * pObj,int fFreeTop)255 void Ivy_ObjDelete( Ivy_Man_t * p, Ivy_Obj_t * pObj, int fFreeTop )
256 {
257 assert( !Ivy_IsComplement(pObj) );
258 assert( Ivy_ObjRefs(pObj) == 0 || !fFreeTop );
259 // update node counters of the manager
260 p->nObjs[pObj->Type]--;
261 p->nDeleted++;
262 // remove connections
263 Ivy_ObjDisconnect( p, pObj );
264 // remove PIs/POs from the arrays
265 if ( Ivy_ObjIsPi(pObj) )
266 Vec_PtrRemove( p->vPis, pObj );
267 else if ( Ivy_ObjIsPo(pObj) )
268 Vec_PtrRemove( p->vPos, pObj );
269 else if ( p->fFanout && Ivy_ObjIsBuf(pObj) )
270 Vec_PtrRemove( p->vBufs, pObj );
271 // clean and recycle the entry
272 if ( fFreeTop )
273 {
274 // free the node
275 Vec_PtrWriteEntry( p->vObjs, pObj->Id, NULL );
276 Ivy_ManRecycleMemory( p, pObj );
277 }
278 else
279 {
280 int nRefsOld = pObj->nRefs;
281 Ivy_Obj_t * pFanout = pObj->pFanout;
282 Ivy_ObjClean( pObj );
283 pObj->pFanout = pFanout;
284 pObj->nRefs = nRefsOld;
285 }
286 }
287
288 /**Function*************************************************************
289
290 Synopsis [Deletes the MFFC of the node.]
291
292 Description []
293
294 SideEffects []
295
296 SeeAlso []
297
298 ***********************************************************************/
Ivy_ObjDelete_rec(Ivy_Man_t * p,Ivy_Obj_t * pObj,int fFreeTop)299 void Ivy_ObjDelete_rec( Ivy_Man_t * p, Ivy_Obj_t * pObj, int fFreeTop )
300 {
301 Ivy_Obj_t * pFanin0, * pFanin1;
302 assert( !Ivy_IsComplement(pObj) );
303 assert( !Ivy_ObjIsNone(pObj) );
304 if ( Ivy_ObjIsConst1(pObj) || Ivy_ObjIsPi(pObj) )
305 return;
306 pFanin0 = Ivy_ObjFanin0(pObj);
307 pFanin1 = Ivy_ObjFanin1(pObj);
308 Ivy_ObjDelete( p, pObj, fFreeTop );
309 if ( pFanin0 && !Ivy_ObjIsNone(pFanin0) && Ivy_ObjRefs(pFanin0) == 0 )
310 Ivy_ObjDelete_rec( p, pFanin0, 1 );
311 if ( pFanin1 && !Ivy_ObjIsNone(pFanin1) && Ivy_ObjRefs(pFanin1) == 0 )
312 Ivy_ObjDelete_rec( p, pFanin1, 1 );
313 }
314
315 /**Function*************************************************************
316
317 Synopsis [Replaces one object by another.]
318
319 Description [Both objects are currently in the manager. The new object
320 (pObjNew) should be used instead of the old object (pObjOld). If the
321 new object is complemented or used, the buffer is added.]
322
323 SideEffects []
324
325 SeeAlso []
326
327 ***********************************************************************/
Ivy_ObjReplace(Ivy_Man_t * p,Ivy_Obj_t * pObjOld,Ivy_Obj_t * pObjNew,int fDeleteOld,int fFreeTop,int fUpdateLevel)328 void Ivy_ObjReplace( Ivy_Man_t * p, Ivy_Obj_t * pObjOld, Ivy_Obj_t * pObjNew, int fDeleteOld, int fFreeTop, int fUpdateLevel )
329 {
330 int nRefsOld;//, clk;
331 // the object to be replaced cannot be complemented
332 assert( !Ivy_IsComplement(pObjOld) );
333 // the object to be replaced cannot be a terminal
334 assert( Ivy_ObjIsNone(pObjOld) || !Ivy_ObjIsPi(pObjOld) );
335 // the object to be used cannot be a PO or assert
336 assert( !Ivy_ObjIsBuf(Ivy_Regular(pObjNew)) );
337 // the object cannot be the same
338 assert( pObjOld != Ivy_Regular(pObjNew) );
339 //printf( "Replacing %d by %d.\n", Ivy_Regular(pObjOld)->Id, Ivy_Regular(pObjNew)->Id );
340
341 // if HAIG is defined, create the choice node
342 if ( p->pHaig )
343 {
344 // if ( pObjOld->Id == 31 )
345 // {
346 // Ivy_ManShow( p, 0 );
347 // Ivy_ManShow( p->pHaig, 1 );
348 // }
349 Ivy_ManHaigCreateChoice( p, pObjOld, pObjNew );
350 }
351 // if the new object is complemented or already used, add the buffer
352 if ( Ivy_IsComplement(pObjNew) || Ivy_ObjIsLatch(pObjNew) || Ivy_ObjRefs(pObjNew) > 0 || Ivy_ObjIsPi(pObjNew) || Ivy_ObjIsConst1(pObjNew) )
353 pObjNew = Ivy_ObjCreate( p, Ivy_ObjCreateGhost(p, pObjNew, NULL, IVY_BUF, IVY_INIT_NONE) );
354 assert( !Ivy_IsComplement(pObjNew) );
355 if ( fUpdateLevel )
356 {
357 //clk = Abc_Clock();
358 // if the new node's arrival time is different, recursively update arrival time of the fanouts
359 if ( p->fFanout && !Ivy_ObjIsBuf(pObjNew) && pObjOld->Level != pObjNew->Level )
360 {
361 assert( Ivy_ObjIsNode(pObjOld) );
362 pObjOld->Level = pObjNew->Level;
363 Ivy_ObjUpdateLevel_rec( p, pObjOld );
364 }
365 //p->time1 += Abc_Clock() - clk;
366 // if the new node's required time has changed, recursively update required time of the fanins
367 //clk = Abc_Clock();
368 if ( p->vRequired )
369 {
370 int ReqNew = Vec_IntEntry(p->vRequired, pObjOld->Id);
371 if ( ReqNew < Vec_IntEntry(p->vRequired, pObjNew->Id) )
372 {
373 Vec_IntWriteEntry( p->vRequired, pObjNew->Id, ReqNew );
374 Ivy_ObjUpdateLevelR_rec( p, pObjNew, ReqNew );
375 }
376 }
377 //p->time2 += Abc_Clock() - clk;
378 }
379 // delete the old object
380 if ( fDeleteOld )
381 Ivy_ObjDelete_rec( p, pObjOld, fFreeTop );
382 // make sure object is not pointing to itself
383 assert( Ivy_ObjFanin0(pObjNew) == NULL || pObjOld != Ivy_ObjFanin0(pObjNew) );
384 assert( Ivy_ObjFanin1(pObjNew) == NULL || pObjOld != Ivy_ObjFanin1(pObjNew) );
385 // make sure the old node has no fanin fanout pointers
386 if ( p->fFanout )
387 {
388 assert( pObjOld->pFanout != NULL );
389 assert( pObjNew->pFanout == NULL );
390 pObjNew->pFanout = pObjOld->pFanout;
391 }
392 // transfer the old object
393 assert( Ivy_ObjRefs(pObjNew) == 0 );
394 nRefsOld = pObjOld->nRefs;
395 Ivy_ObjOverwrite( pObjOld, pObjNew );
396 pObjOld->nRefs = nRefsOld;
397 // patch the fanout of the fanins
398 if ( p->fFanout )
399 {
400 Ivy_ObjPatchFanout( p, Ivy_ObjFanin0(pObjOld), pObjNew, pObjOld );
401 if ( Ivy_ObjFanin1(pObjOld) )
402 Ivy_ObjPatchFanout( p, Ivy_ObjFanin1(pObjOld), pObjNew, pObjOld );
403 }
404 // update the hash table
405 Ivy_TableUpdate( p, pObjNew, pObjOld->Id );
406 // recycle the object that was taken over by pObjOld
407 Vec_PtrWriteEntry( p->vObjs, pObjNew->Id, NULL );
408 Ivy_ManRecycleMemory( p, pObjNew );
409 // if the new node is the buffer propagate it
410 if ( p->fFanout && Ivy_ObjIsBuf(pObjOld) )
411 Vec_PtrPush( p->vBufs, pObjOld );
412 // Ivy_ManCheckFanouts( p );
413 // printf( "\n" );
414 /*
415 if ( p->pHaig )
416 {
417 int x;
418 Ivy_ManShow( p, 0, NULL );
419 Ivy_ManShow( p->pHaig, 1, NULL );
420 x = 0;
421 }
422 */
423 // if ( Ivy_ManCheckFanoutNums(p) )
424 // {
425 // int x = 0;
426 // }
427 }
428
429 /**Function*************************************************************
430
431 Synopsis [Fixes buffer fanins.]
432
433 Description [This situation happens because NodeReplace is a lazy
434 procedure, which does not propagate the change to the fanouts but
435 instead records the change in the form of a buf/inv node.]
436
437 SideEffects []
438
439 SeeAlso []
440
441 ***********************************************************************/
Ivy_NodeFixBufferFanins(Ivy_Man_t * p,Ivy_Obj_t * pNode,int fUpdateLevel)442 void Ivy_NodeFixBufferFanins( Ivy_Man_t * p, Ivy_Obj_t * pNode, int fUpdateLevel )
443 {
444 Ivy_Obj_t * pFanReal0, * pFanReal1, * pResult = NULL;
445 if ( Ivy_ObjIsPo(pNode) )
446 {
447 if ( !Ivy_ObjIsBuf(Ivy_ObjFanin0(pNode)) )
448 return;
449 pFanReal0 = Ivy_ObjReal( Ivy_ObjChild0(pNode) );
450 Ivy_ObjPatchFanin0( p, pNode, pFanReal0 );
451 // Ivy_ManCheckFanouts( p );
452 return;
453 }
454 if ( !Ivy_ObjIsBuf(Ivy_ObjFanin0(pNode)) && !Ivy_ObjIsBuf(Ivy_ObjFanin1(pNode)) )
455 return;
456 // get the real fanins
457 pFanReal0 = Ivy_ObjReal( Ivy_ObjChild0(pNode) );
458 pFanReal1 = Ivy_ObjReal( Ivy_ObjChild1(pNode) );
459 // get the new node
460 if ( Ivy_ObjIsNode(pNode) )
461 pResult = Ivy_Oper( p, pFanReal0, pFanReal1, Ivy_ObjType(pNode) );
462 else if ( Ivy_ObjIsLatch(pNode) )
463 pResult = Ivy_Latch( p, pFanReal0, Ivy_ObjInit(pNode) );
464 else
465 assert( 0 );
466
467 //printf( "===== Replacing %d by %d.\n", pNode->Id, pResult->Id );
468 //Ivy_ObjPrintVerbose( p, pNode, 0 ); printf( "\n" );
469 //Ivy_ObjPrintVerbose( p, pResult, 0 ); printf( "\n" );
470
471 // perform the replacement
472 Ivy_ObjReplace( p, pNode, pResult, 1, 0, fUpdateLevel );
473 }
474
475 ////////////////////////////////////////////////////////////////////////
476 /// END OF FILE ///
477 ////////////////////////////////////////////////////////////////////////
478
479
480 ABC_NAMESPACE_IMPL_END
481
482