1 /**CFile****************************************************************
2
3 FileName [giaCof.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Cofactor estimation procedures.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaCof.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include <math.h>
22 #include "gia.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 typedef struct Cof_Fan_t_ Cof_Fan_t;
32 struct Cof_Fan_t_
33 {
34 unsigned iFan : 31; // ID of the fanin/fanout
35 unsigned fCompl : 1; // complemented attribute
36 };
37
38 typedef struct Cof_Obj_t_ Cof_Obj_t;
39 struct Cof_Obj_t_
40 {
41 unsigned fTerm : 1; // terminal node (CI/CO)
42 unsigned fPhase : 1; // value under 000 pattern
43 unsigned fMark0 : 1; // first user-controlled mark
44 unsigned fMark1 : 1; // second user-controlled mark
45 unsigned nFanins : 4; // the number of fanins
46 unsigned nFanouts : 24; // total number of fanouts
47 unsigned nFanoutsM; // total number of MUX ctrl fanouts
48 unsigned Value; // application specific data
49 int Id; // ID of the node
50 int iNext; // next one in the linked list
51 int iLit; // literal of the node after rehashing
52 Cof_Fan_t Fanios[0]; // the array of fanins/fanouts
53 };
54
55 typedef struct Cof_Man_t_ Cof_Man_t;
56 struct Cof_Man_t_
57 {
58 Gia_Man_t * pGia; // the original AIG manager
59 Vec_Int_t * vCis; // the vector of CIs (PIs + LOs)
60 Vec_Int_t * vCos; // the vector of COs (POs + LIs)
61 int nObjs; // the number of objects
62 int nNodes; // the number of nodes
63 int nTravIds; // traversal ID of the network
64 int * pObjData; // the logic network defined for the AIG
65 int nObjData; // the size of array to store the logic network
66 int * pLevels; // the linked lists of levels
67 int nLevels; // the max number of logic levels
68 };
69
Gia_ObjHandle(Gia_Obj_t * pObj)70 static inline unsigned Gia_ObjHandle( Gia_Obj_t * pObj ) { return pObj->Value; }
71
Cof_ObjLevel(Cof_Man_t * p,Cof_Obj_t * pObj)72 static inline int Cof_ObjLevel( Cof_Man_t * p, Cof_Obj_t * pObj ) { return Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia,pObj->Id)); }
73
Cof_ObjHandle(Cof_Man_t * p,Cof_Obj_t * pObj)74 static inline unsigned Cof_ObjHandle( Cof_Man_t * p, Cof_Obj_t * pObj ) { return (unsigned)(((int *)pObj) - p->pObjData); }
Cof_ObjHandleDiff(Cof_Obj_t * pObj,Cof_Obj_t * pFanin)75 static inline unsigned Cof_ObjHandleDiff( Cof_Obj_t * pObj, Cof_Obj_t * pFanin ) { return (unsigned)(((int *)pObj) - ((int *)pFanin)); }
76
Cof_ObjIsTerm(Cof_Obj_t * pObj)77 static inline int Cof_ObjIsTerm( Cof_Obj_t * pObj ) { return pObj->fTerm; }
Cof_ObjIsCi(Cof_Obj_t * pObj)78 static inline int Cof_ObjIsCi( Cof_Obj_t * pObj ) { return pObj->fTerm && pObj->nFanins == 0; }
Cof_ObjIsCo(Cof_Obj_t * pObj)79 static inline int Cof_ObjIsCo( Cof_Obj_t * pObj ) { return pObj->fTerm && pObj->nFanins == 1; }
Cof_ObjIsNode(Cof_Obj_t * pObj)80 static inline int Cof_ObjIsNode( Cof_Obj_t * pObj ) { return!pObj->fTerm && pObj->nFanins > 0; }
Cof_ObjIsConst0(Cof_Obj_t * pObj)81 static inline int Cof_ObjIsConst0( Cof_Obj_t * pObj ) { return!pObj->fTerm && pObj->nFanins == 0; }
82
Cof_ObjFaninNum(Cof_Obj_t * pObj)83 static inline int Cof_ObjFaninNum( Cof_Obj_t * pObj ) { return pObj->nFanins; }
Cof_ObjFanoutNum(Cof_Obj_t * pObj)84 static inline int Cof_ObjFanoutNum( Cof_Obj_t * pObj ) { return pObj->nFanouts; }
Cof_ObjSize(Cof_Obj_t * pObj)85 static inline int Cof_ObjSize( Cof_Obj_t * pObj ) { return sizeof(Cof_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts; }
86
Cof_ManObj(Cof_Man_t * p,unsigned iHandle)87 static inline Cof_Obj_t * Cof_ManObj( Cof_Man_t * p, unsigned iHandle ) { return (Cof_Obj_t *)(p->pObjData + iHandle); }
Cof_ObjFanin(Cof_Obj_t * pObj,int i)88 static inline Cof_Obj_t * Cof_ObjFanin( Cof_Obj_t * pObj, int i ) { return (Cof_Obj_t *)(((int *)pObj) - pObj->Fanios[i].iFan); }
Cof_ObjFanout(Cof_Obj_t * pObj,int i)89 static inline Cof_Obj_t * Cof_ObjFanout( Cof_Obj_t * pObj, int i ) { return (Cof_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i].iFan); }
90
Cof_ManObjNum(Cof_Man_t * p)91 static inline int Cof_ManObjNum( Cof_Man_t * p ) { return p->nObjs; }
Cof_ManNodeNum(Cof_Man_t * p)92 static inline int Cof_ManNodeNum( Cof_Man_t * p ) { return p->nNodes; }
93
Cof_ManResetTravId(Cof_Man_t * p)94 static inline void Cof_ManResetTravId( Cof_Man_t * p ) { extern void Cof_ManCleanValue( Cof_Man_t * p ); Cof_ManCleanValue( p ); p->nTravIds = 1; }
Cof_ManIncrementTravId(Cof_Man_t * p)95 static inline void Cof_ManIncrementTravId( Cof_Man_t * p ) { p->nTravIds++; }
Cof_ObjSetTravId(Cof_Obj_t * pObj,int TravId)96 static inline void Cof_ObjSetTravId( Cof_Obj_t * pObj, int TravId ) { pObj->Value = TravId; }
Cof_ObjSetTravIdCurrent(Cof_Man_t * p,Cof_Obj_t * pObj)97 static inline void Cof_ObjSetTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj ) { pObj->Value = p->nTravIds; }
Cof_ObjSetTravIdPrevious(Cof_Man_t * p,Cof_Obj_t * pObj)98 static inline void Cof_ObjSetTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj ) { pObj->Value = p->nTravIds - 1; }
Cof_ObjIsTravIdCurrent(Cof_Man_t * p,Cof_Obj_t * pObj)99 static inline int Cof_ObjIsTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj ) { return ((int)pObj->Value == p->nTravIds); }
Cof_ObjIsTravIdPrevious(Cof_Man_t * p,Cof_Obj_t * pObj)100 static inline int Cof_ObjIsTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj ) { return ((int)pObj->Value == p->nTravIds - 1); }
101
102 #define Cof_ManForEachObj( p, pObj, i ) \
103 for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) )
104 #define Cof_ManForEachNode( p, pObj, i ) \
105 for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) ) if ( Cof_ObjIsTerm(pObj) ) {} else
106 #define Cof_ObjForEachFanin( pObj, pNext, i ) \
107 for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Cof_ObjFanin(pObj,i)); i++ )
108 #define Cof_ObjForEachFanout( pObj, pNext, i ) \
109 for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Cof_ObjFanout(pObj,i)); i++ )
110
111 ////////////////////////////////////////////////////////////////////////
112 /// FUNCTION DEFINITIONS ///
113 ////////////////////////////////////////////////////////////////////////
114
115 /**Function*************************************************************
116
117 Synopsis [Creates logic network isomorphic to the given AIG.]
118
119 Description []
120
121 SideEffects []
122
123 SeeAlso []
124
125 ***********************************************************************/
Cof_ManCreateLogicSimple(Gia_Man_t * pGia)126 Cof_Man_t * Cof_ManCreateLogicSimple( Gia_Man_t * pGia )
127 {
128 Cof_Man_t * p;
129 Cof_Obj_t * pObjLog, * pFanLog;
130 Gia_Obj_t * pObj;
131 int * pMuxRefs;
132 int i, iHandle = 0;
133 p = ABC_CALLOC( Cof_Man_t, 1 );
134 p->pGia = pGia;
135 p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
136 p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
137 p->nObjData = (sizeof(Cof_Obj_t) / 4) * Gia_ManObjNum(pGia) + 4 * Gia_ManAndNum(pGia) + 2 * Gia_ManCoNum(pGia);
138 p->pObjData = ABC_CALLOC( int, p->nObjData );
139 ABC_FREE( pGia->pRefs );
140 Gia_ManCreateRefs( pGia );
141 Gia_ManForEachObj( pGia, pObj, i )
142 {
143 pObj->Value = iHandle;
144 pObjLog = Cof_ManObj( p, iHandle );
145 pObjLog->nFanins = 0;
146 pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
147 pObjLog->Id = i;
148 pObjLog->Value = 0;
149 if ( Gia_ObjIsAnd(pObj) )
150 {
151 pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) );
152 pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan =
153 pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
154 pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj);
155
156 pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin1(pObj)) );
157 pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan =
158 pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
159 pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC1(pObj);
160 p->nNodes++;
161 }
162 else if ( Gia_ObjIsCo(pObj) )
163 {
164 pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) );
165 pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan =
166 pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
167 pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj);
168
169 pObjLog->fTerm = 1;
170 Vec_IntPush( p->vCos, iHandle );
171 }
172 else if ( Gia_ObjIsCi(pObj) )
173 {
174 pObjLog->fTerm = 1;
175 Vec_IntPush( p->vCis, iHandle );
176 }
177 iHandle += Cof_ObjSize( pObjLog );
178 p->nObjs++;
179 }
180 assert( iHandle == p->nObjData );
181 pMuxRefs = Gia_ManCreateMuxRefs( pGia );
182 Gia_ManForEachObj( pGia, pObj, i )
183 {
184 pObjLog = Cof_ManObj( p, Gia_ObjHandle(pObj) );
185 assert( pObjLog->nFanouts == pObjLog->Value );
186 pObjLog->nFanoutsM = pMuxRefs[i];
187 }
188 ABC_FREE( pMuxRefs );
189 return p;
190 }
191
192 /**Function*************************************************************
193
194 Synopsis [Creates logic network isomorphic to the given AIG.]
195
196 Description []
197
198 SideEffects []
199
200 SeeAlso []
201
202 ***********************************************************************/
Cof_ManStop(Cof_Man_t * p)203 void Cof_ManStop( Cof_Man_t * p )
204 {
205 Vec_IntFree( p->vCis );
206 Vec_IntFree( p->vCos );
207 ABC_FREE( p->pObjData );
208 ABC_FREE( p->pLevels );
209 ABC_FREE( p );
210 }
211
212
213 /**Function*************************************************************
214
215 Synopsis [Collects support nodes.]
216
217 Description []
218
219 SideEffects []
220
221 SeeAlso []
222
223 ***********************************************************************/
Cof_ManTfoSize_rec(Cof_Man_t * p,Cof_Obj_t * pObj)224 int Cof_ManTfoSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
225 {
226 Cof_Obj_t * pNext;
227 unsigned i, Counter = 0;
228 if ( Cof_ObjIsTravIdCurrent(p, pObj) )
229 return 0;
230 Cof_ObjSetTravIdCurrent(p, pObj);
231 if ( Cof_ObjIsCo(pObj) )
232 return 0;
233 assert( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) );
234 Cof_ObjForEachFanout( pObj, pNext, i )
235 Counter += Cof_ManTfoSize_rec( p, pNext );
236 return 1 + Counter;
237 }
238
239 /**Function*************************************************************
240
241 Synopsis [Collects support nodes.]
242
243 Description []
244
245 SideEffects []
246
247 SeeAlso []
248
249 ***********************************************************************/
Cof_ManTfoSize(Cof_Man_t * p,Cof_Obj_t ** ppObjs,int nObjs)250 int Cof_ManTfoSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs )
251 {
252 int i, Counter = 0;
253 Cof_ManIncrementTravId( p );
254 for ( i = 0; i < nObjs; i++ )
255 Counter += Cof_ManTfoSize_rec( p, ppObjs[i] ) - 1;
256 return Counter;
257 }
258
259 /**Function*************************************************************
260
261 Synopsis [Collects support nodes.]
262
263 Description []
264
265 SideEffects []
266
267 SeeAlso []
268
269 ***********************************************************************/
Cof_ManTfiSize_rec(Cof_Man_t * p,Cof_Obj_t * pObj)270 int Cof_ManTfiSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
271 {
272 Cof_Obj_t * pNext;
273 unsigned i, Counter = 0;
274 if ( Cof_ObjIsTravIdCurrent(p, pObj) )
275 return 0;
276 Cof_ObjSetTravIdCurrent(p, pObj);
277 if ( Cof_ObjIsCi(pObj) )
278 return 0;
279 assert( Cof_ObjIsNode(pObj) );
280 Cof_ObjForEachFanin( pObj, pNext, i )
281 Counter += Cof_ManTfiSize_rec( p, pNext );
282 return 1 + Counter;
283 }
284
285 /**Function*************************************************************
286
287 Synopsis [Collects support nodes.]
288
289 Description []
290
291 SideEffects []
292
293 SeeAlso []
294
295 ***********************************************************************/
Cof_ManTfiSize(Cof_Man_t * p,Cof_Obj_t ** ppObjs,int nObjs)296 int Cof_ManTfiSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs )
297 {
298 int i, Counter = 0;
299 Cof_ManIncrementTravId( p );
300 for ( i = 0; i < nObjs; i++ )
301 if ( Cof_ObjIsCo(ppObjs[i]) )
302 Counter += Cof_ManTfiSize_rec( p, Cof_ObjFanin(ppObjs[i],0) );
303 else
304 Counter += Cof_ManTfiSize_rec( p, ppObjs[i] );
305 return Counter;
306 }
307
308 /**Function*************************************************************
309
310 Synopsis [Collects support nodes.]
311
312 Description []
313
314 SideEffects []
315
316 SeeAlso []
317
318 ***********************************************************************/
Cof_ManSuppSize_rec(Cof_Man_t * p,Cof_Obj_t * pObj)319 int Cof_ManSuppSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
320 {
321 Cof_Obj_t * pNext;
322 unsigned i, Counter = 0;
323 if ( Cof_ObjIsTravIdCurrent(p, pObj) )
324 return 0;
325 Cof_ObjSetTravIdCurrent(p, pObj);
326 if ( Cof_ObjIsCi(pObj) )
327 return 1;
328 assert( Cof_ObjIsNode(pObj) );
329 Cof_ObjForEachFanin( pObj, pNext, i )
330 Counter += Cof_ManSuppSize_rec( p, pNext );
331 return Counter;
332 }
333
334 /**Function*************************************************************
335
336 Synopsis [Collects support nodes.]
337
338 Description []
339
340 SideEffects []
341
342 SeeAlso []
343
344 ***********************************************************************/
Cof_ManSuppSize(Cof_Man_t * p,Cof_Obj_t ** ppObjs,int nObjs)345 int Cof_ManSuppSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs )
346 {
347 int i, Counter = 0;
348 Cof_ManIncrementTravId( p );
349 for ( i = 0; i < nObjs; i++ )
350 if ( Cof_ObjIsCo(ppObjs[i]) )
351 Counter += Cof_ManSuppSize_rec( p, Cof_ObjFanin(ppObjs[i],0) );
352 else
353 Counter += Cof_ManSuppSize_rec( p, ppObjs[i] );
354 return Counter;
355 }
356
357
358 /**Function*************************************************************
359
360 Synopsis [Cleans the value.]
361
362 Description []
363
364 SideEffects []
365
366 SeeAlso []
367
368 ***********************************************************************/
Cof_ManCleanValue(Cof_Man_t * p)369 void Cof_ManCleanValue( Cof_Man_t * p )
370 {
371 Cof_Obj_t * pObj;
372 int i;
373 Cof_ManForEachObj( p, pObj, i )
374 pObj->Value = 0;
375 }
376
377 /**Function*************************************************************
378
379 Synopsis [Returns sorted array of node handles with largest fanout.]
380
381 Description []
382
383 SideEffects []
384
385 SeeAlso []
386
387 ***********************************************************************/
Cof_ManInsertEntry_rec(Vec_Ptr_t * vNodes,Cof_Obj_t * pNode,int nNodeMax)388 void Cof_ManInsertEntry_rec( Vec_Ptr_t * vNodes, Cof_Obj_t * pNode, int nNodeMax )
389 {
390 Cof_Obj_t * pLast;
391 if ( Vec_PtrSize(vNodes) == 0 )
392 {
393 Vec_PtrPush(vNodes, pNode);
394 return;
395 }
396 pLast = (Cof_Obj_t *)Vec_PtrPop(vNodes);
397 if ( Cof_ObjFanoutNum(pLast) < Cof_ObjFanoutNum(pNode) )
398 {
399 Cof_ManInsertEntry_rec( vNodes, pNode, nNodeMax );
400 if ( Vec_PtrSize(vNodes) < nNodeMax )
401 Vec_PtrPush( vNodes, pLast );
402 }
403 else
404 {
405 Vec_PtrPush( vNodes, pLast );
406 if ( Vec_PtrSize(vNodes) < nNodeMax )
407 Vec_PtrPush( vNodes, pNode );
408 }
409 }
410
411 /**Function*************************************************************
412
413 Synopsis [Returns sorted array of node handles with largest fanout.]
414
415 Description []
416
417 SideEffects []
418
419 SeeAlso []
420
421 ***********************************************************************/
Cof_ManCollectHighFanout(Cof_Man_t * p,int nNodes)422 Vec_Ptr_t * Cof_ManCollectHighFanout( Cof_Man_t * p, int nNodes )
423 {
424 Vec_Ptr_t * vNodes;
425 Cof_Obj_t * pObj;
426 int i;
427 vNodes = Vec_PtrAlloc( nNodes );
428 Cof_ManForEachObj( p, pObj, i )
429 if ( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) )
430 Cof_ManInsertEntry_rec( vNodes, pObj, nNodes );
431 return vNodes;
432 }
433
434 /**Function*************************************************************
435
436 Synopsis [Returns sorted array of node handles with largest fanout.]
437
438 Description []
439
440 SideEffects []
441
442 SeeAlso []
443
444 ***********************************************************************/
Cof_ManCountRemoved(Cof_Man_t * p,Cof_Obj_t * pRoot,int fConst1)445 int Cof_ManCountRemoved( Cof_Man_t * p, Cof_Obj_t * pRoot, int fConst1 )
446 {
447 Gia_Obj_t * pNextGia;
448 Cof_Obj_t * pTemp, * pNext, * pFanin0, * pFanin1;
449 int Counter = 0, LevelStart, LevelNext;
450 int i, k, iHandle, iLit0, iLit1, iNextNew;
451 // restart the trav ids
452 Cof_ManIncrementTravId( p );
453 Cof_ObjSetTravIdCurrent( p, pRoot );
454 // add the node to the queue
455 LevelStart = Cof_ObjLevel(p, pRoot);
456 assert( p->pLevels[LevelStart] == 0 );
457 pRoot->iNext = 0;
458 p->pLevels[LevelStart] = Cof_ObjHandle( p, pRoot );
459 // set the new literal
460 pRoot->iLit = Abc_Var2Lit( 0, fConst1 );
461 // process nodes in the levelized order
462 for ( i = LevelStart; i < p->nLevels; i++ )
463 {
464 for ( iHandle = p->pLevels[i];
465 iHandle && (pTemp = Cof_ManObj(p, iHandle));
466 iHandle = pTemp->iNext )
467 {
468 assert( pTemp->Id != Abc_Lit2Var(pTemp->iLit) );
469 Cof_ObjForEachFanout( pTemp, pNext, k )
470 {
471 if ( Cof_ObjIsCo(pNext) )
472 continue;
473 if ( Cof_ObjIsTravIdCurrent(p, pNext) )
474 continue;
475 pFanin0 = Cof_ObjFanin( pNext, 0 );
476 pFanin1 = Cof_ObjFanin( pNext, 1 );
477 assert( pFanin0 == pTemp || pFanin1 == pTemp );
478 pNextGia = Gia_ManObj( p->pGia, pNext->Id );
479 if ( Cof_ObjIsTravIdCurrent(p, pFanin0) )
480 iLit0 = Abc_LitNotCond( pFanin0->iLit, Gia_ObjFaninC0(pNextGia) );
481 else
482 iLit0 = Gia_ObjFaninLit0( pNextGia, pNext->Id );
483 if ( Cof_ObjIsTravIdCurrent(p, pFanin1) )
484 iLit1 = Abc_LitNotCond( pFanin1->iLit, Gia_ObjFaninC1(pNextGia) );
485 else
486 iLit1 = Gia_ObjFaninLit1( pNextGia, pNext->Id );
487 iNextNew = Gia_ManHashAndTry( p->pGia, iLit0, iLit1 );
488 if ( iNextNew == -1 )
489 continue;
490 Cof_ObjSetTravIdCurrent(p, pNext);
491 // set the new literal
492 pNext->iLit = iNextNew;
493 // add it to be processed
494 LevelNext = Cof_ObjLevel( p, pNext );
495 assert( LevelNext > i && LevelNext < p->nLevels );
496 pNext->iNext = p->pLevels[LevelNext];
497 p->pLevels[LevelNext] = Cof_ObjHandle( p, pNext );
498 Counter++;
499 }
500 }
501 p->pLevels[i] = 0;
502 }
503 return Counter;
504 }
505
506 /**Function*************************************************************
507
508 Synopsis [Returns sorted array of node handles with largest fanout.]
509
510 Description []
511
512 SideEffects []
513
514 SeeAlso []
515
516 ***********************************************************************/
Cof_ManPrintHighFanoutOne(Cof_Man_t * p,Cof_Obj_t * pObj)517 void Cof_ManPrintHighFanoutOne( Cof_Man_t * p, Cof_Obj_t * pObj )
518 {
519 printf( "%7d : ", pObj->Id );
520 printf( "i/o/c =%2d %5d %5d ", Cof_ObjFaninNum(pObj), Cof_ObjFanoutNum(pObj), 2*pObj->nFanoutsM );
521 printf( "l =%4d ", Cof_ObjLevel(p, pObj) );
522 printf( "s =%5d ", Cof_ManSuppSize(p, &pObj, 1) );
523 printf( "TFI =%7d ", Cof_ManTfiSize(p, &pObj, 1) );
524 printf( "TFO =%7d ", Cof_ManTfoSize(p, &pObj, 1) );
525 printf( "C0 =%6d ", Cof_ManCountRemoved(p, pObj, 0) );
526 printf( "C1 =%6d", Cof_ManCountRemoved(p, pObj, 1) );
527 printf( "\n" );
528 }
529
530 /**Function*************************************************************
531
532 Synopsis [Returns sorted array of node handles with largest fanout.]
533
534 Description []
535
536 SideEffects []
537
538 SeeAlso []
539
540 ***********************************************************************/
Cof_ManPrintHighFanout(Cof_Man_t * p,int nNodes)541 void Cof_ManPrintHighFanout( Cof_Man_t * p, int nNodes )
542 {
543 Vec_Ptr_t * vNodes;
544 Cof_Obj_t * pObj;
545 int i;
546 vNodes = Cof_ManCollectHighFanout( p, nNodes );
547 Vec_PtrForEachEntry( Cof_Obj_t *, vNodes, pObj, i )
548 Cof_ManPrintHighFanoutOne( p, pObj );
549 Vec_PtrFree( vNodes );
550 }
551
552
553 /**Function*************************************************************
554
555 Synopsis [Compute MFFC size of the node.]
556
557 Description []
558
559 SideEffects []
560
561 SeeAlso []
562
563 ***********************************************************************/
Cof_NodeDeref_rec(Cof_Obj_t * pNode)564 int Cof_NodeDeref_rec( Cof_Obj_t * pNode )
565 {
566 if ( pNode->nFanins == 0 )
567 return 0;
568 if ( --pNode->nFanouts > 0 )
569 return 0;
570 return 1 + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 0) )
571 + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 1) );
572 }
Cof_NodeRef_rec(Cof_Obj_t * pNode)573 int Cof_NodeRef_rec( Cof_Obj_t * pNode )
574 {
575 if ( pNode->nFanins == 0 )
576 return 0;
577 if ( pNode->nFanouts++ > 0 )
578 return 0;
579 return 1 + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 0) )
580 + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 1) );
581 }
Cof_ObjMffcSize(Cof_Obj_t * pNode)582 static inline int Cof_ObjMffcSize( Cof_Obj_t * pNode )
583 {
584 int Count1, Count2, nFanout;
585 nFanout = pNode->nFanouts;
586 pNode->nFanouts = 1;
587 Count1 = Cof_NodeDeref_rec( pNode );
588 Count2 = Cof_NodeRef_rec( pNode );
589 pNode->nFanouts = nFanout;
590 assert( Count1 == Count2 );
591 return Count1;
592 }
593
594 /**Function*************************************************************
595
596 Synopsis [Prints the distribution of fanins/fanouts in the network.]
597
598 Description []
599
600 SideEffects []
601
602 SeeAlso []
603
604 ***********************************************************************/
Cof_ManPrintFanio(Cof_Man_t * p)605 void Cof_ManPrintFanio( Cof_Man_t * p )
606 {
607 char Buffer[100];
608 Cof_Obj_t * pNode;
609 Vec_Int_t * vFanins, * vFanouts, * vMffcs;
610 int nFanins, nFanouts, nMffcs, nFaninsMax, nFanoutsMax, nMffcsMax, nFaninsAll, nFanoutsAll, nMffcsAll;
611 int i, k, nSizeMax, nMffcNodes = 0;
612
613 // determine the largest fanin and fanout
614 nFaninsMax = nFanoutsMax = nMffcsMax = 0;
615 nFaninsAll = nFanoutsAll = nMffcsAll = 0;
616 Cof_ManForEachNode( p, pNode, i )
617 {
618 if ( i == 0 ) continue;
619 nFanins = Cof_ObjFaninNum(pNode);
620 nFanouts = Cof_ObjFanoutNum(pNode);
621 nMffcs = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0;
622 nFaninsAll += nFanins;
623 nFanoutsAll += nFanouts;
624 nMffcsAll += nMffcs;
625 nFaninsMax = Abc_MaxInt( nFaninsMax, nFanins );
626 nFanoutsMax = Abc_MaxInt( nFanoutsMax, nFanouts );
627 nMffcsMax = Abc_MaxInt( nMffcsMax, nMffcs );
628 }
629
630 // allocate storage for fanin/fanout numbers
631 nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
632 nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nMffcsMax) + 1), nSizeMax );
633 vFanins = Vec_IntStart( nSizeMax );
634 vFanouts = Vec_IntStart( nSizeMax );
635 vMffcs = Vec_IntStart( nSizeMax );
636
637 // count the number of fanins and fanouts
638 Cof_ManForEachNode( p, pNode, i )
639 {
640 if ( i == 0 ) continue;
641 nFanins = Cof_ObjFaninNum(pNode);
642 nFanouts = Cof_ObjFanoutNum(pNode);
643 nMffcs = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0;
644
645 if ( nFanins < 10 )
646 Vec_IntAddToEntry( vFanins, nFanins, 1 );
647 else if ( nFanins < 100 )
648 Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
649 else if ( nFanins < 1000 )
650 Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
651 else if ( nFanins < 10000 )
652 Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
653 else if ( nFanins < 100000 )
654 Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
655 else if ( nFanins < 1000000 )
656 Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
657 else if ( nFanins < 10000000 )
658 Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );
659
660 if ( nFanouts < 10 )
661 Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
662 else if ( nFanouts < 100 )
663 Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
664 else if ( nFanouts < 1000 )
665 Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
666 else if ( nFanouts < 10000 )
667 Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
668 else if ( nFanouts < 100000 )
669 Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
670 else if ( nFanouts < 1000000 )
671 Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
672 else if ( nFanouts < 10000000 )
673 Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
674
675 if ( nMffcs == 0 )
676 continue;
677 nMffcNodes++;
678
679 if ( nMffcs < 10 )
680 Vec_IntAddToEntry( vMffcs, nMffcs, 1 );
681 else if ( nMffcs < 100 )
682 Vec_IntAddToEntry( vMffcs, 10 + nMffcs/10, 1 );
683 else if ( nMffcs < 1000 )
684 Vec_IntAddToEntry( vMffcs, 20 + nMffcs/100, 1 );
685 else if ( nMffcs < 10000 )
686 Vec_IntAddToEntry( vMffcs, 30 + nMffcs/1000, 1 );
687 else if ( nMffcs < 100000 )
688 Vec_IntAddToEntry( vMffcs, 40 + nMffcs/10000, 1 );
689 else if ( nMffcs < 1000000 )
690 Vec_IntAddToEntry( vMffcs, 50 + nMffcs/100000, 1 );
691 else if ( nMffcs < 10000000 )
692 Vec_IntAddToEntry( vMffcs, 60 + nMffcs/1000000, 1 );
693 }
694
695 printf( "The distribution of fanins, fanouts. and MFFCs in the network:\n" );
696 printf( " Number Nodes with fanin Nodes with fanout Nodes with MFFC\n" );
697
698 for ( k = 0; k < nSizeMax; k++ )
699 {
700 if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 && vMffcs->pArray[k] == 0 )
701 continue;
702 if ( k < 10 )
703 printf( "%15d : ", k );
704 else
705 {
706 sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 );
707 printf( "%15s : ", Buffer );
708 }
709 if ( vFanins->pArray[k] == 0 )
710 printf( " " );
711 else
712 printf( "%11d ", vFanins->pArray[k] );
713 printf( " " );
714 if ( vFanouts->pArray[k] == 0 )
715 printf( " " );
716 else
717 printf( "%12d ", vFanouts->pArray[k] );
718 printf( " " );
719 if ( vMffcs->pArray[k] == 0 )
720 printf( " " );
721 else
722 printf( " %12d ", vMffcs->pArray[k] );
723 printf( "\n" );
724 }
725 Vec_IntFree( vFanins );
726 Vec_IntFree( vFanouts );
727 Vec_IntFree( vMffcs );
728
729 printf( "Fanins: Max = %d. Ave = %.2f. Fanouts: Max = %d. Ave = %.2f. MFFCs: Max = %d. Ave = %.2f.\n",
730 nFaninsMax, 1.0*nFaninsAll /Cof_ManNodeNum(p),
731 nFanoutsMax, 1.0*nFanoutsAll/Cof_ManNodeNum(p),
732 nMffcsMax, 1.0*nMffcsAll /nMffcNodes );
733 }
734
735 /**Function*************************************************************
736
737 Synopsis [Returns sorted array of node handles with largest fanout.]
738
739 Description []
740
741 SideEffects []
742
743 SeeAlso []
744
745 ***********************************************************************/
Gia_ManPrintFanio(Gia_Man_t * pGia,int nNodes)746 void Gia_ManPrintFanio( Gia_Man_t * pGia, int nNodes )
747 {
748 Cof_Man_t * p;
749 abctime clk = Abc_Clock();
750 p = Cof_ManCreateLogicSimple( pGia );
751 p->nLevels = 1 + Gia_ManLevelNum( pGia );
752 p->pLevels = ABC_CALLOC( int, p->nLevels );
753 Cof_ManPrintFanio( p );
754
755 if ( nNodes > 0 )
756 {
757 Cof_ManResetTravId( p );
758 Gia_ManHashStart( pGia );
759 Cof_ManPrintHighFanout( p, nNodes );
760 Gia_ManHashStop( pGia );
761 ABC_PRMn( "Memory for logic network", 4*p->nObjData );
762 ABC_PRT( "Time", Abc_Clock() - clk );
763 }
764
765 Cof_ManStop( p );
766 }
767
768
769 /**Function*************************************************************
770
771 Synopsis [Duplicates AIG in the DFS order while putting CIs first.]
772
773 Description []
774
775 SideEffects []
776
777 SeeAlso []
778
779 ***********************************************************************/
Gia_ManDupCofInt(Gia_Man_t * p,int iVar)780 Gia_Man_t * Gia_ManDupCofInt( Gia_Man_t * p, int iVar )
781 {
782 Gia_Man_t * pNew;
783 Gia_Obj_t * pObj, * pPivot;
784 int i, iCofVar = -1;
785 if ( !(iVar > 0 && iVar < Gia_ManObjNum(p)) )
786 {
787 printf( "Gia_ManDupCof(): Variable %d is out of range (%d; %d).\n", iVar, 0, Gia_ManObjNum(p) );
788 return NULL;
789 }
790 // find the cofactoring variable
791 pPivot = Gia_ManObj( p, iVar );
792 if ( !Gia_ObjIsCand(pPivot) )
793 {
794 printf( "Gia_ManDupCof(): Variable %d should be a CI or an AND node.\n", iVar );
795 return NULL;
796 }
797 pNew = Gia_ManStart( Gia_ManObjNum(p) );
798 pNew->pName = Abc_UtilStrsav( p->pName );
799 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
800 Gia_ManHashAlloc( pNew );
801 Gia_ManFillValue( p );
802 Gia_ManConst0(p)->Value = 0;
803 // compute negative cofactor
804 Gia_ManForEachCi( p, pObj, i )
805 {
806 pObj->Value = Gia_ManAppendCi(pNew);
807 if ( pObj == pPivot )
808 {
809 iCofVar = pObj->Value;
810 pObj->Value = Abc_Var2Lit( 0, 0 );
811 }
812 }
813 Gia_ManForEachAnd( p, pObj, i )
814 {
815 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
816 if ( pObj == pPivot )
817 {
818 iCofVar = pObj->Value;
819 pObj->Value = Abc_Var2Lit( 0, 0 );
820 }
821 }
822 Gia_ManForEachCo( p, pObj, i )
823 pObj->Value = Gia_ObjFanin0Copy(pObj);
824 // compute the positive cofactor
825 Gia_ManForEachCi( p, pObj, i )
826 {
827 pObj->Value = Abc_Var2Lit( Gia_ObjId(pNew, Gia_ManCi(pNew, i)), 0 );
828 if ( pObj == pPivot )
829 pObj->Value = Abc_Var2Lit( 0, 1 );
830 }
831 Gia_ManForEachAnd( p, pObj, i )
832 {
833 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
834 if ( pObj == pPivot )
835 pObj->Value = Abc_Var2Lit( 0, 1 );
836 }
837 // create MUXes
838 assert( iCofVar > 0 );
839 Gia_ManForEachCo( p, pObj, i )
840 {
841 if ( pObj->Value == (unsigned)Gia_ObjFanin0Copy(pObj) )
842 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
843 else
844 pObj->Value = Gia_ManAppendCo( pNew, Gia_ManHashMux(pNew, iCofVar, Gia_ObjFanin0Copy(pObj), pObj->Value) );
845 }
846 Gia_ManHashStop( pNew );
847 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
848 return pNew;
849 }
850
851 /**Function*************************************************************
852
853 Synopsis [Duplicates AIG in the DFS order while putting CIs first.]
854
855 Description []
856
857 SideEffects []
858
859 SeeAlso []
860
861 ***********************************************************************/
Gia_ManDupCof(Gia_Man_t * p,int iVar)862 Gia_Man_t * Gia_ManDupCof( Gia_Man_t * p, int iVar )
863 {
864 Gia_Man_t * pNew, * pTemp;
865 pNew = Gia_ManDupCofInt( p, iVar );
866 pNew = Gia_ManCleanup( pTemp = pNew );
867 Gia_ManStop( pTemp );
868 return pNew;
869 }
870
871
872 /**Function*************************************************************
873
874 Synopsis [Determines variables whose fanout count is higher than this.]
875
876 Description [Variables are returned in a reverse topological order.]
877
878 SideEffects []
879
880 SeeAlso []
881
882 ***********************************************************************/
Gia_ManCofVars(Gia_Man_t * p,int nFanLim)883 Vec_Int_t * Gia_ManCofVars( Gia_Man_t * p, int nFanLim )
884 {
885 Vec_Int_t * vVars;
886 Gia_Obj_t * pObj;
887 int i;
888 ABC_FREE( p->pRefs );
889 Gia_ManCreateRefs( p );
890 vVars = Vec_IntAlloc( 100 );
891 Gia_ManForEachObj( p, pObj, i )
892 if ( Gia_ObjIsCand(pObj) && Gia_ObjRefNum(p, pObj) >= nFanLim )
893 Vec_IntPush( vVars, i );
894 ABC_FREE( p->pRefs );
895 return vVars;
896 }
897
898 /**Function*************************************************************
899
900 Synopsis [Transfers attributes from the original one to the final one.]
901
902 Description []
903
904 SideEffects []
905
906 SeeAlso []
907
908 ***********************************************************************/
Gia_ManTransfer(Gia_Man_t * pAig,Gia_Man_t * pCof,Gia_Man_t * pNew,Vec_Int_t * vSigs)909 Vec_Int_t * Gia_ManTransfer( Gia_Man_t * pAig, Gia_Man_t * pCof, Gia_Man_t * pNew, Vec_Int_t * vSigs )
910 {
911 Vec_Int_t * vSigsNew;
912 Gia_Obj_t * pObj, * pObjF;
913 int i;
914 vSigsNew = Vec_IntAlloc( 100 );
915 Gia_ManForEachObjVec( vSigs, pAig, pObj, i )
916 {
917 assert( Gia_ObjIsCand(pObj) );
918 pObjF = Gia_ManObj( pCof, Abc_Lit2Var(pObj->Value) );
919 if ( pObjF->Value && ~pObjF->Value )
920 Vec_IntPushUnique( vSigsNew, Abc_Lit2Var(pObjF->Value) );
921 }
922 return vSigsNew;
923 }
924
925 /**Function*************************************************************
926
927 Synopsis [Cofactors selected variables (should be in reverse topo order).]
928
929 Description []
930
931 SideEffects []
932
933 SeeAlso []
934
935 ***********************************************************************/
Gia_ManDupCofAllInt(Gia_Man_t * p,Vec_Int_t * vSigs,int fVerbose)936 Gia_Man_t * Gia_ManDupCofAllInt( Gia_Man_t * p, Vec_Int_t * vSigs, int fVerbose )
937 {
938 Vec_Int_t * vSigsNew, * vTemp;
939 Gia_Man_t * pAig, * pCof, * pNew;
940 int iVar;
941 if ( fVerbose )
942 {
943 printf( "Cofactoring %d signals.\n", Vec_IntSize(vSigs) );
944 Gia_ManPrintStats( p, NULL );
945 }
946 if ( Vec_IntSize( vSigs ) > 200 )
947 {
948 printf( "Too many signals to cofactor.\n" );
949 return NULL;
950 }
951 pAig = Gia_ManDup( p );
952 vSigsNew = Vec_IntDup( vSigs );
953 while ( Vec_IntSize(vSigsNew) > 0 )
954 {
955 Vec_IntSort( vSigsNew, 0 );
956 iVar = Vec_IntPop( vSigsNew );
957 // Gia_ManCreateRefs( pAig );
958 // printf( "ref count = %d\n", Gia_ObjRefNum( pAig, Gia_ManObj(pAig, iVar) ) );
959 // ABC_FREE( pAig->pRefs );
960 pCof = Gia_ManDupCofInt( pAig, iVar );
961 pNew = Gia_ManCleanup( pCof );
962 vSigsNew = Gia_ManTransfer( pAig, pCof, pNew, vTemp = vSigsNew );
963 Vec_IntFree( vTemp );
964 Gia_ManStop( pAig );
965 Gia_ManStop( pCof );
966 pAig = pNew;
967 if ( fVerbose )
968 printf( "Cofactored variable %d.\n", iVar );
969 if ( fVerbose )
970 Gia_ManPrintStats( pAig, NULL );
971 }
972 Vec_IntFree( vSigsNew );
973 return pAig;
974 }
975
976 /**Function*************************************************************
977
978 Synopsis [Cofactors all variables whose fanout is higher than this.]
979
980 Description []
981
982 SideEffects []
983
984 SeeAlso []
985
986 ***********************************************************************/
Gia_ManDupCofAll(Gia_Man_t * p,int nFanLim,int fVerbose)987 Gia_Man_t * Gia_ManDupCofAll( Gia_Man_t * p, int nFanLim, int fVerbose )
988 {
989 Gia_Man_t * pNew;
990 Vec_Int_t * vSigs = Gia_ManCofVars( p, nFanLim );
991 pNew = Gia_ManDupCofAllInt( p, vSigs, fVerbose );
992 Vec_IntFree( vSigs );
993 return pNew;
994 }
995
996 ////////////////////////////////////////////////////////////////////////
997 /// END OF FILE ///
998 ////////////////////////////////////////////////////////////////////////
999
1000
1001 ABC_NAMESPACE_IMPL_END
1002
1003