1 /**CFile****************************************************************
2
3 FileName [giaBalance.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [AIG balancing.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22 #include "misc/vec/vecHash.h"
23 #include "misc/vec/vecQue.h"
24 #include "opt/dau/dau.h"
25
26 ABC_NAMESPACE_IMPL_START
27
28
29 ////////////////////////////////////////////////////////////////////////
30 /// DECLARATIONS ///
31 ////////////////////////////////////////////////////////////////////////
32
33 // operation manager
34 typedef struct Dam_Man_t_ Dam_Man_t;
35 struct Dam_Man_t_
36 {
37 Gia_Man_t * pGia; // user's AIG
38 Vec_Int_t * vNod2Set; // node ID into fanin set
39 Vec_Int_t * vDiv2Nod; // div ID into root node set
40 Vec_Int_t * vSetStore; // fanin set storage
41 Vec_Int_t * vNodStore; // root node set storage
42 Vec_Flt_t * vCounts; // occur counts
43 Vec_Int_t * vNodLevR; // node reverse level
44 Vec_Int_t * vDivLevR; // divisor reverse level
45 Vec_Int_t * vVisit; // visited MUXes
46 Vec_Que_t * vQue; // pairs by their weight
47 Hash_IntMan_t * vHash; // pair hash table
48 abctime clkStart; // starting the clock
49 int nLevelMax; // maximum level
50 int nDivs; // extracted divisor count
51 int nAnds; // total AND node count
52 int nGain; // total gain in AND nodes
53 int nGainX; // gain from XOR nodes
54 };
55
Dam_ObjHand(Dam_Man_t * p,int i)56 static inline int Dam_ObjHand( Dam_Man_t * p, int i ) { return i < Vec_IntSize(p->vNod2Set) ? Vec_IntEntry(p->vNod2Set, i) : 0; }
Dam_ObjSet(Dam_Man_t * p,int i)57 static inline int * Dam_ObjSet( Dam_Man_t * p, int i ) { int h = Dam_ObjHand(p, i); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vSetStore, h); }
58
Dam_DivHand(Dam_Man_t * p,int d)59 static inline int Dam_DivHand( Dam_Man_t * p, int d ) { return d < Vec_IntSize(p->vDiv2Nod) ? Vec_IntEntry(p->vDiv2Nod, d) : 0; }
Dam_DivSet(Dam_Man_t * p,int d)60 static inline int * Dam_DivSet( Dam_Man_t * p, int d ) { int h = Dam_DivHand(p, d); if ( h == 0 ) return NULL; return Vec_IntEntryP(p->vNodStore, h); }
61
62
63 ////////////////////////////////////////////////////////////////////////
64 /// FUNCTION DEFINITIONS ///
65 ////////////////////////////////////////////////////////////////////////
66
67 /**Function*************************************************************
68
69 Synopsis [Simplify multi-input AND/XOR.]
70
71 Description []
72
73 SideEffects []
74
75 SeeAlso []
76
77 ***********************************************************************/
Gia_ManSimplifyXor(Vec_Int_t * vSuper)78 void Gia_ManSimplifyXor( Vec_Int_t * vSuper )
79 {
80 int i, k = 0, Prev = -1, This, fCompl = 0;
81 Vec_IntForEachEntry( vSuper, This, i )
82 {
83 if ( This == 0 )
84 continue;
85 if ( This == 1 )
86 fCompl ^= 1;
87 else if ( Prev != This )
88 Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
89 else
90 Prev = -1, k--;
91 }
92 Vec_IntShrink( vSuper, k );
93 if ( Vec_IntSize( vSuper ) == 0 )
94 Vec_IntPush( vSuper, fCompl );
95 else if ( fCompl )
96 Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) );
97 }
Gia_ManSimplifyAnd(Vec_Int_t * vSuper)98 void Gia_ManSimplifyAnd( Vec_Int_t * vSuper )
99 {
100 int i, k = 0, Prev = -1, This;
101 Vec_IntForEachEntry( vSuper, This, i )
102 {
103 if ( This == 0 )
104 { Vec_IntFill(vSuper, 1, 0); return; }
105 if ( This == 1 )
106 continue;
107 if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) )
108 Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
109 else if ( Prev != This )
110 { Vec_IntFill(vSuper, 1, 0); return; }
111 }
112 Vec_IntShrink( vSuper, k );
113 if ( Vec_IntSize( vSuper ) == 0 )
114 Vec_IntPush( vSuper, 1 );
115 }
116
117 /**Function*************************************************************
118
119 Synopsis [Collect multi-input AND/XOR.]
120
121 Description []
122
123 SideEffects []
124
125 SeeAlso []
126
127 ***********************************************************************/
Gia_ManSuperCollectXor_rec(Gia_Man_t * p,Gia_Obj_t * pObj,int fStrict)128 void Gia_ManSuperCollectXor_rec( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
129 {
130 assert( !Gia_IsComplement(pObj) );
131 if ( !Gia_ObjIsXor(pObj) ||
132 (fStrict && Gia_ObjRefNum(p, pObj) > 1) ||
133 Gia_ObjRefNum(p, pObj) > 2 ||
134 (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
135 Vec_IntSize(p->vSuper) > 50 )
136 {
137 Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
138 return;
139 }
140 assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
141 Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj), fStrict );
142 Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj), fStrict );
143 }
Gia_ManSuperCollectAnd_rec(Gia_Man_t * p,Gia_Obj_t * pObj,int fStrict)144 void Gia_ManSuperCollectAnd_rec( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
145 {
146 if ( Gia_IsComplement(pObj) ||
147 !Gia_ObjIsAndReal(p, pObj) ||
148 (fStrict && Gia_ObjRefNum(p, pObj) > 1) ||
149 Gia_ObjRefNum(p, pObj) > 2 ||
150 (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) ||
151 Vec_IntSize(p->vSuper) > 50 )
152 {
153 Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
154 return;
155 }
156 Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj), fStrict );
157 Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj), fStrict );
158 }
Gia_ManSuperCollect(Gia_Man_t * p,Gia_Obj_t * pObj,int fStrict)159 void Gia_ManSuperCollect( Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
160 {
161 // int nSize;
162 if ( p->vSuper == NULL )
163 p->vSuper = Vec_IntAlloc( 1000 );
164 else
165 Vec_IntClear( p->vSuper );
166 if ( Gia_ObjIsXor(pObj) )
167 {
168 assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
169 Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj), fStrict );
170 Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj), fStrict );
171 // nSize = Vec_IntSize(vSuper);
172 Vec_IntSort( p->vSuper, 0 );
173 Gia_ManSimplifyXor( p->vSuper );
174 // if ( nSize != Vec_IntSize(vSuper) )
175 // printf( "X %d->%d ", nSize, Vec_IntSize(vSuper) );
176 }
177 else if ( Gia_ObjIsAndReal(p, pObj) )
178 {
179 Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj), fStrict );
180 Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj), fStrict );
181 // nSize = Vec_IntSize(vSuper);
182 Vec_IntSort( p->vSuper, 0 );
183 Gia_ManSimplifyAnd( p->vSuper );
184 // if ( nSize != Vec_IntSize(vSuper) )
185 // printf( "A %d->%d ", nSize, Vec_IntSize(vSuper) );
186 }
187 else assert( 0 );
188 // if ( nSize > 10 )
189 // printf( "%d ", nSize );
190 assert( Vec_IntSize(p->vSuper) > 0 );
191 }
192
193 /**Function*************************************************************
194
195 Synopsis []
196
197 Description []
198
199 SideEffects []
200
201 SeeAlso []
202
203 ***********************************************************************/
Gia_ManFindSharedNode(Gia_Man_t * pNew,Vec_Int_t * vSuper,int iLit0)204 int Gia_ManFindSharedNode( Gia_Man_t * pNew, Vec_Int_t * vSuper, int iLit0 )
205 {
206 int i, iLit1 = Vec_IntEntryLast(vSuper);
207 // iterate through the nodes whose level is equal to that of the last one
208 int iLit1Level = Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1));
209 for ( i = Vec_IntSize(vSuper)-1; i >= 0; i-- )
210 {
211 int iLit2 = Vec_IntEntry(vSuper, i);
212 if ( iLit1Level != Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
213 break;
214 if ( Abc_Lit2Var(iLit0) != Abc_Lit2Var(iLit2) && !Gia_ManHashLookupInt(pNew, iLit0, iLit2) ) // new node
215 continue;
216 // swap iLit2 and iLit1
217 if ( iLit2 != iLit1 )
218 {
219 Vec_IntWriteEntry( vSuper, i, iLit1 );
220 Vec_IntWriteEntry( vSuper, Vec_IntSize(vSuper)-1, iLit2 );
221 }
222 break;
223 }
224 return Vec_IntPop(vSuper);
225 }
Gia_ManPrepareLastTwo(Gia_Man_t * pNew,Vec_Int_t * vSuper)226 void Gia_ManPrepareLastTwo( Gia_Man_t * pNew, Vec_Int_t * vSuper )
227 {
228 int i, k, Stop, Lit1, Lit2, Level1, Level2, * pArray;
229 int nSize = Vec_IntSize(vSuper);
230 if ( nSize == 2 )
231 return;
232 assert( nSize > 2 );
233 Level1 = Gia_ObjLevelId( pNew, Abc_Lit2Var(Vec_IntEntry(vSuper, nSize-2)) );
234 // find the first one with Level1
235 for ( Stop = nSize-3; Stop >= 0; Stop-- )
236 {
237 Level2 = Gia_ObjLevelId( pNew, Abc_Lit2Var(Vec_IntEntry(vSuper, Stop)) );
238 if ( Level1 != Level2 )
239 break;
240 }
241 if ( Stop == nSize-3 )
242 return;
243 // avoid worst-case quadratic behavior by looking at the last 8 nodes
244 Stop = Abc_MaxInt( Stop, nSize - 9 );
245 for ( i = nSize - 1; i > Stop; i-- )
246 for ( k = i - 1; k > Stop; k-- )
247 {
248 Lit1 = Vec_IntEntry(vSuper, i);
249 Lit2 = Vec_IntEntry(vSuper, k);
250 if ( Abc_Lit2Var(Lit1) != Abc_Lit2Var(Lit2) && !Gia_ManHashLookupInt(pNew, Lit1, Lit2) ) // new node
251 continue;
252 // move Lit1 to be last and Lit2 to be the one before
253 pArray = Vec_IntArray( vSuper );
254 if ( i != nSize-1 )
255 ABC_SWAP( int, pArray[i], pArray[nSize-1] );
256 if ( k != nSize-2 )
257 ABC_SWAP( int, pArray[k], pArray[nSize-2] );
258 }
259 }
Gia_ManCreateGate(Gia_Man_t * pNew,Gia_Obj_t * pObj,Vec_Int_t * vSuper)260 void Gia_ManCreateGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper )
261 {
262 int iLit0 = Vec_IntPop(vSuper);
263 int iLit1 = Vec_IntPop(vSuper);
264 // int iLit1 = Gia_ManFindSharedNode(pNew, vSuper, iLit0);
265 int iLit, i;
266 if ( !Gia_ObjIsXor(pObj) )
267 iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 );
268 else if ( pNew->pMuxes )
269 iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 );
270 else
271 iLit = Gia_ManHashXor( pNew, iLit0, iLit1 );
272 Vec_IntPush( vSuper, iLit );
273 Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) );
274 // shift to the corrent location
275 for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
276 {
277 int iLit1 = Vec_IntEntry(vSuper, i);
278 int iLit2 = Vec_IntEntry(vSuper, i-1);
279 if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
280 break;
281 Vec_IntWriteEntry( vSuper, i, iLit2 );
282 Vec_IntWriteEntry( vSuper, i-1, iLit1 );
283 }
284 }
Gia_ManBalanceGate(Gia_Man_t * pNew,Gia_Obj_t * pObj,Vec_Int_t * vSuper,int * pLits,int nLits)285 int Gia_ManBalanceGate( Gia_Man_t * pNew, Gia_Obj_t * pObj, Vec_Int_t * vSuper, int * pLits, int nLits )
286 {
287 assert( !Gia_ObjIsBuf(pObj) );
288 Vec_IntClear( vSuper );
289 if ( nLits == 1 )
290 Vec_IntPush( vSuper, pLits[0] );
291 else if ( nLits == 2 )
292 {
293 Vec_IntPush( vSuper, pLits[0] );
294 Vec_IntPush( vSuper, pLits[1] );
295 Gia_ManCreateGate( pNew, pObj, vSuper );
296 }
297 else if ( nLits > 2 )
298 {
299 // collect levels
300 int i, * pArray, * pPerm; //int iLit;
301 for ( i = 0; i < nLits; i++ )
302 Vec_IntPush( vSuper, Gia_ObjLevelId(pNew, Abc_Lit2Var(pLits[i])) );
303 // sort by level
304 Vec_IntGrow( vSuper, 4 * nLits );
305 pArray = Vec_IntArray( vSuper );
306 pPerm = pArray + nLits;
307 Abc_QuickSortCostData( pArray, nLits, 1, (word *)(pArray + 2 * nLits), pPerm );
308 // collect in the increasing order of level
309 for ( i = 0; i < nLits; i++ )
310 Vec_IntWriteEntry( vSuper, i, pLits[pPerm[i]] );
311 Vec_IntShrink( vSuper, nLits );
312 /*
313 Vec_IntForEachEntry( vSuper, iLit, i )
314 printf( "%d ", Gia_ObjLevel(pNew, Gia_ManObj( pNew, Abc_Lit2Var(iLit) )) );
315 printf( "\n" );
316 */
317 // perform incremental extraction
318 while ( Vec_IntSize(vSuper) > 1 )
319 {
320 if ( !Gia_ObjIsXor(pObj) )
321 Gia_ManPrepareLastTwo( pNew, vSuper );
322 Gia_ManCreateGate( pNew, pObj, vSuper );
323 }
324 }
325 // consider trivial case
326 assert( Vec_IntSize(vSuper) == 1 );
327 return Vec_IntEntry(vSuper, 0);
328 }
329
330 /**Function*************************************************************
331
332 Synopsis []
333
334 Description []
335
336 SideEffects []
337
338 SeeAlso []
339
340 ***********************************************************************/
Gia_ManBalance_rec(Gia_Man_t * pNew,Gia_Man_t * p,Gia_Obj_t * pObj,int fStrict)341 void Gia_ManBalance_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj, int fStrict )
342 {
343 int i, iLit, iBeg, iEnd;
344 if ( ~pObj->Value )
345 return;
346 assert( Gia_ObjIsAnd(pObj) );
347 assert( !Gia_ObjIsBuf(pObj) );
348 // handle MUX
349 if ( Gia_ObjIsMux(p, pObj) )
350 {
351 Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
352 Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj), fStrict );
353 Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj), fStrict );
354 pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
355 Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
356 return;
357 }
358 // find supergate
359 Gia_ManSuperCollect( p, pObj, fStrict );
360 // save entries
361 if ( p->vStore == NULL )
362 p->vStore = Vec_IntAlloc( 1000 );
363 iBeg = Vec_IntSize( p->vStore );
364 Vec_IntAppend( p->vStore, p->vSuper );
365 iEnd = Vec_IntSize( p->vStore );
366 // call recursively
367 Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd )
368 {
369 Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) );
370 Gia_ManBalance_rec( pNew, p, pTemp, fStrict );
371 Vec_IntWriteEntry( p->vStore, i, Abc_LitNotCond(pTemp->Value, Abc_LitIsCompl(iLit)) );
372 }
373 assert( Vec_IntSize(p->vStore) == iEnd );
374 // consider general case
375 pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg );
376 Vec_IntShrink( p->vStore, iBeg );
377 }
Gia_ManBalanceInt(Gia_Man_t * p,int fStrict)378 Gia_Man_t * Gia_ManBalanceInt( Gia_Man_t * p, int fStrict )
379 {
380 Gia_Man_t * pNew, * pTemp;
381 Gia_Obj_t * pObj;
382 int i;
383 Gia_ManFillValue( p );
384 Gia_ManCreateRefs( p );
385 // start the new manager
386 pNew = Gia_ManStart( Gia_ManObjNum(p) );
387 pNew->pName = Abc_UtilStrsav( p->pName );
388 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
389 pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
390 pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
391 // create constant and inputs
392 Gia_ManConst0(p)->Value = 0;
393 Gia_ManForEachCi( p, pObj, i )
394 pObj->Value = Gia_ManAppendCi( pNew );
395 // set arrival times for the input of the new AIG
396 if ( p->vCiArrs )
397 {
398 int Id, And2Delay = p->And2Delay ? p->And2Delay : 1;
399 Gia_ManForEachCiId( pNew, Id, i )
400 Vec_IntWriteEntry( pNew->vLevels, Id, Vec_IntEntry(p->vCiArrs, i)/And2Delay );
401 }
402 else if ( p->vInArrs )
403 {
404 int Id, And2Delay = p->And2Delay ? p->And2Delay : 1;
405 Gia_ManForEachCiId( pNew, Id, i )
406 Vec_IntWriteEntry( pNew->vLevels, Id, (int)(Vec_FltEntry(p->vInArrs, i)/And2Delay) );
407 }
408 // create internal nodes
409 Gia_ManHashStart( pNew );
410 Gia_ManForEachBuf( p, pObj, i )
411 {
412 Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
413 pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
414 Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
415 }
416 Gia_ManForEachCo( p, pObj, i )
417 {
418 Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj), fStrict );
419 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
420 }
421 assert( !fStrict || Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
422 Gia_ManHashStop( pNew );
423 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
424 // perform cleanup
425 pNew = Gia_ManCleanup( pTemp = pNew );
426 Gia_ManStop( pTemp );
427 return pNew;
428 }
429
430 /**Function*************************************************************
431
432 Synopsis []
433
434 Description []
435
436 SideEffects []
437
438 SeeAlso []
439
440 ***********************************************************************/
Gia_ManBalance(Gia_Man_t * p,int fSimpleAnd,int fStrict,int fVerbose)441 Gia_Man_t * Gia_ManBalance( Gia_Man_t * p, int fSimpleAnd, int fStrict, int fVerbose )
442 {
443 Gia_Man_t * pNew, * pNew1, * pNew2;
444 if ( fVerbose ) Gia_ManPrintStats( p, NULL );
445 pNew = fSimpleAnd ? Gia_ManDup( p ) : Gia_ManDupMuxes( p, 2 );
446 Gia_ManTransferTiming( pNew, p );
447 if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
448 pNew1 = Gia_ManBalanceInt( pNew, fStrict );
449 Gia_ManTransferTiming( pNew1, pNew );
450 if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
451 Gia_ManStop( pNew );
452 pNew2 = Gia_ManDupNoMuxes( pNew1, 0 );
453 Gia_ManTransferTiming( pNew2, pNew1 );
454 if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
455 Gia_ManStop( pNew1 );
456 return pNew2;
457 }
458
459
460
461
462
463 /**Function*************************************************************
464
465 Synopsis []
466
467 Description []
468
469 SideEffects []
470
471 SeeAlso []
472
473 ***********************************************************************/
Dam_ManAlloc(Gia_Man_t * pGia)474 Dam_Man_t * Dam_ManAlloc( Gia_Man_t * pGia )
475 {
476 Dam_Man_t * p;
477 p = ABC_CALLOC( Dam_Man_t, 1 );
478 p->clkStart = Abc_Clock();
479 p->vVisit = Vec_IntAlloc( 1000 );
480 p->pGia = pGia;
481 return p;
482 }
Dam_ManFree(Dam_Man_t * p)483 void Dam_ManFree( Dam_Man_t * p )
484 {
485 Vec_IntFreeP( &p->vVisit );
486 Vec_IntFreeP( &p->vDivLevR );
487 Vec_IntFreeP( &p->vNodLevR );
488 Vec_IntFreeP( &p->vNod2Set );
489 Vec_IntFreeP( &p->vDiv2Nod );
490 Vec_IntFreeP( &p->vSetStore );
491 Vec_IntFreeP( &p->vNodStore );
492 Vec_FltFreeP( &p->vCounts );
493 Vec_QueFreeP( &p->vQue );
494 Hash_IntManStop( p->vHash );
495 ABC_FREE( p );
496 }
497
498 /**Function*************************************************************
499
500 Synopsis [Collect initial multi-input gates.]
501
502 Description []
503
504 SideEffects []
505
506 SeeAlso []
507
508 ***********************************************************************/
Dam_ManCollectSets_rec(Dam_Man_t * p,int Id)509 void Dam_ManCollectSets_rec( Dam_Man_t * p, int Id )
510 {
511 Gia_Obj_t * pObj;
512 int i, iBeg, iEnd, iLit;
513 if ( Dam_ObjHand(p, Id) || Id == 0 )
514 return;
515 pObj = Gia_ManObj(p->pGia, Id);
516 if ( Gia_ObjIsCi(pObj) )
517 return;
518 if ( Gia_ObjIsBuf(pObj) )
519 {
520 Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
521 return;
522 }
523 if ( Gia_ObjIsMux(p->pGia, pObj) )
524 {
525 if ( pObj->fMark0 )
526 return;
527 pObj->fMark0 = 1;
528 Vec_IntPush( p->vVisit, Id );
529 Dam_ManCollectSets_rec( p, Gia_ObjFaninId0(pObj, Id) );
530 Dam_ManCollectSets_rec( p, Gia_ObjFaninId1(pObj, Id) );
531 Dam_ManCollectSets_rec( p, Gia_ObjFaninId2(p->pGia, Id) );
532 p->nAnds += 3;
533 return;
534 }
535 Gia_ManSuperCollect( p->pGia, pObj, 0 );
536 Vec_IntWriteEntry( p->vNod2Set, Id, Vec_IntSize(p->vSetStore) );
537 Vec_IntPush( p->vSetStore, Vec_IntSize(p->pGia->vSuper) );
538 p->nAnds += (1 + 2 * Gia_ObjIsXor(pObj)) * (Vec_IntSize(p->pGia->vSuper) - 1);
539 // save entries
540 iBeg = Vec_IntSize( p->vSetStore );
541 Vec_IntAppend( p->vSetStore, p->pGia->vSuper );
542 iEnd = Vec_IntSize( p->vSetStore );
543 // call recursively
544 Vec_IntForEachEntryStartStop( p->vSetStore, iLit, i, iBeg, iEnd )
545 Dam_ManCollectSets_rec( p, Abc_Lit2Var(iLit) );
546 }
Dam_ManCollectSets(Dam_Man_t * p)547 void Dam_ManCollectSets( Dam_Man_t * p )
548 {
549 Gia_Obj_t * pObj;
550 int i;
551 Gia_ManCreateRefs( p->pGia );
552 p->vNod2Set = Vec_IntStart( Gia_ManObjNum(p->pGia) );
553 p->vSetStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
554 Vec_IntPush( p->vSetStore, -1 );
555 Vec_IntClear( p->vVisit );
556 Gia_ManForEachCo( p->pGia, pObj, i )
557 Dam_ManCollectSets_rec( p, Gia_ObjFaninId0p(p->pGia, pObj) );
558 ABC_FREE( p->pGia->pRefs );
559 Gia_ManForEachObjVec( p->vVisit, p->pGia, pObj, i )
560 pObj->fMark0 = 0;
561 }
562
563 /**Function*************************************************************
564
565 Synopsis [Create divisors.]
566
567 Description []
568
569 SideEffects []
570
571 SeeAlso []
572
573 ***********************************************************************/
Dam_ManDivSlack(Dam_Man_t * p,int iLit0,int iLit1,int LevR)574 int Dam_ManDivSlack( Dam_Man_t * p, int iLit0, int iLit1, int LevR )
575 {
576 int Lev0 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit0)));
577 int Lev1 = Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLit1)));
578 int Slack = p->nLevelMax - LevR - Abc_MaxInt(Lev0, Lev1) - 1 - (int)(iLit0 > iLit1);
579 return Abc_MinInt( Slack, 100 );
580 }
Dam_ManCreateMultiRefs(Dam_Man_t * p,Vec_Int_t ** pvRefsAnd,Vec_Int_t ** pvRefsXor)581 void Dam_ManCreateMultiRefs( Dam_Man_t * p, Vec_Int_t ** pvRefsAnd, Vec_Int_t ** pvRefsXor )
582 {
583 Vec_Int_t * vRefsAnd, * vRefsXor;
584 Gia_Obj_t * pObj;
585 int i, k, * pSet;
586 vRefsAnd = Vec_IntStart( 2 * Gia_ManObjNum(p->pGia) );
587 vRefsXor = Vec_IntStart( Gia_ManObjNum(p->pGia) );
588 Gia_ManForEachAnd( p->pGia, pObj, i )
589 {
590 if ( !Dam_ObjHand(p, i) )
591 continue;
592 pSet = Dam_ObjSet(p, i);
593 if ( Gia_ObjIsXor(pObj) )
594 for ( k = 1; k <= pSet[0]; k++ )
595 {
596 assert( !Abc_LitIsCompl(pSet[k]) );
597 Vec_IntAddToEntry( vRefsXor, Abc_Lit2Var(pSet[k]), 1 );
598 }
599 else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
600 for ( k = 1; k <= pSet[0]; k++ )
601 Vec_IntAddToEntry( vRefsAnd, pSet[k], 1 );
602 else assert( 0 );
603 }
604 *pvRefsAnd = vRefsAnd;
605 *pvRefsXor = vRefsXor;
606 }
Dam_ManCreatePairs(Dam_Man_t * p,int fVerbose)607 void Dam_ManCreatePairs( Dam_Man_t * p, int fVerbose )
608 {
609 Gia_Obj_t * pObj;
610 Hash_IntMan_t * vHash;
611 Vec_Int_t * vRefsAnd, * vRefsXor, * vSuper, * vDivs, * vRemap, * vLevRMax;
612 int i, j, k, Num, FanK, FanJ, nRefs, iNode, iDiv, * pSet;
613 int nPairsAll = 0, nPairsTried = 0, nPairsUsed = 0, nPairsXor = 0;
614 int nDivsAll = 0, nDivsUsed = 0, nDivsXor = 0;
615 Dam_ManCollectSets( p );
616 vSuper = p->pGia->vSuper;
617 vDivs = Vec_IntAlloc( Gia_ManObjNum(p->pGia) );
618 vHash = Hash_IntManStart( Gia_ManObjNum(p->pGia)/2 );
619 vLevRMax = Vec_IntStart( 1000 );
620 Dam_ManCreateMultiRefs( p, &vRefsAnd, &vRefsXor );
621 Gia_ManForEachAnd( p->pGia, pObj, i )
622 {
623 if ( !Dam_ObjHand(p, i) )
624 continue;
625 pSet = Dam_ObjSet(p, i);
626 nPairsAll += pSet[0] * (pSet[0] - 1) / 2;
627 Vec_IntClear(vSuper);
628 if ( Gia_ObjIsXor(pObj) )
629 {
630 for ( k = 1; k <= pSet[0]; k++ )
631 if ( Vec_IntEntry(vRefsXor, Abc_Lit2Var(pSet[k])) > 1 )
632 Vec_IntPush( vSuper, pSet[k] );
633 }
634 else if ( Gia_ObjIsAndReal(p->pGia, pObj) )
635 {
636 for ( k = 1; k <= pSet[0]; k++ )
637 if ( Vec_IntEntry(vRefsAnd, pSet[k]) > 1 )
638 Vec_IntPush( vSuper, pSet[k] );
639 }
640 else assert( 0 );
641 if ( Vec_IntSize(vSuper) < 2 )
642 continue;
643 // enumerate pairs
644 nPairsTried += Vec_IntSize(vSuper) * (Vec_IntSize(vSuper) - 1) / 2;
645 Vec_IntPush( vDivs, -i ); // remember node
646 Vec_IntForEachEntry( vSuper, FanK, k )
647 Vec_IntForEachEntryStart( vSuper, FanJ, j, k+1 )
648 {
649 if ( (FanK > FanJ) ^ Gia_ObjIsXor(pObj) )
650 Num = Hash_Int2ManInsert( vHash, FanJ, FanK, 0 );
651 else
652 Num = Hash_Int2ManInsert( vHash, FanK, FanJ, 0 );
653 if ( Hash_Int2ObjInc( vHash, Num ) == 1 )
654 {
655 nDivsUsed++;
656 nDivsXor += Gia_ObjIsXor(pObj);
657 }
658 Vec_IntPush( vDivs, Num ); // remember devisor
659 // update reverse level
660 if ( Num >= Vec_IntSize(vLevRMax) )
661 Vec_IntFillExtra( vLevRMax, 3 * Vec_IntSize(vLevRMax) / 2, 0 );
662 Vec_IntUpdateEntry( vLevRMax, Num, Vec_IntEntry(p->vNodLevR, i) );
663 }
664 }
665 Vec_IntFree( vRefsAnd );
666 Vec_IntFree( vRefsXor );
667 // Hash_IntManProfile( vHash );
668 // remove entries that appear only once
669 p->vHash = Hash_IntManStart( 3 * nDivsUsed /2 );
670 p->vCounts = Vec_FltAlloc( 2 * nDivsUsed ); Vec_FltPush( p->vCounts, ABC_INFINITY );
671 p->vQue = Vec_QueAlloc( Vec_FltCap(p->vCounts) );
672 Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) );
673 // mapping div to node
674 p->vDiv2Nod = Vec_IntAlloc( 2 * nDivsUsed ); Vec_IntPush( p->vDiv2Nod, ABC_INFINITY );
675 p->vNodStore = Vec_IntAlloc( Gia_ManObjNum(p->pGia) ); Vec_IntPush( p->vNodStore, -1 );
676 nDivsAll = Hash_IntManEntryNum(vHash);
677 vRemap = Vec_IntStartFull( nDivsAll+1 );
678 for ( i = 1; i <= nDivsAll; i++ )
679 {
680 nRefs = Hash_IntObjData2(vHash, i);
681 if ( nRefs < 2 )
682 continue;
683 nPairsUsed += nRefs;
684 if ( Hash_IntObjData0(vHash, i) > Hash_IntObjData1(vHash, i) )
685 nPairsXor += nRefs;
686 Num = Hash_Int2ManInsert( p->vHash, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), 0 );
687 assert( Num == Hash_IntManEntryNum(p->vHash) );
688 assert( Num == Vec_FltSize(p->vCounts) );
689 Vec_FltPush( p->vCounts, nRefs + 0.005*Dam_ManDivSlack(p, Hash_IntObjData0(vHash, i), Hash_IntObjData1(vHash, i), Vec_IntEntry(vLevRMax, i)) );
690 Vec_QuePush( p->vQue, Num );
691 // remember divisors
692 assert( Num == Vec_IntSize(p->vDiv2Nod) );
693 Vec_IntPush( p->vDiv2Nod, Vec_IntSize(p->vNodStore) );
694 Vec_IntPush( p->vNodStore, 0 );
695 Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
696 // remember entry
697 Vec_IntWriteEntry( vRemap, i, Num );
698 }
699 assert( Vec_FltSize(p->vCounts) == Hash_IntManEntryNum(p->vHash)+1 );
700 assert( Vec_IntSize(p->vDiv2Nod) == nDivsUsed+1 );
701 Hash_IntManStop( vHash );
702 Vec_IntFree( vLevRMax );
703 // fill in the divisors
704 iNode = -1;
705 Vec_IntForEachEntry( vDivs, iDiv, i )
706 {
707 if ( iDiv < 0 )
708 {
709 iNode = -iDiv;
710 continue;
711 }
712 Num = Vec_IntEntry( vRemap, iDiv );
713 if ( Num == -1 )
714 continue;
715 pSet = Dam_DivSet( p, Num );
716 pSet[++pSet[0]] = iNode;
717 }
718 Vec_IntFree( vRemap );
719 Vec_IntFree( vDivs );
720 // create storage for reverse level of divisor during update
721 p->vDivLevR = Vec_IntStart( 2 * nDivsUsed );
722 // make sure divisors are added correctly
723 // for ( i = 1; i <= nDivsUsed; i++ )
724 // assert( Dam_DivSet(p, i)[0] == Vec_FltEntry(p->vCounts, i)+1 );
725 if ( !fVerbose )
726 return;
727 // print stats
728 printf( "Pairs:" );
729 printf( " Total =%9d (%6.2f %%)", nPairsAll, 100.0 * nPairsAll / Abc_MaxInt(nPairsAll, 1) );
730 printf( " Tried =%9d (%6.2f %%)", nPairsTried, 100.0 * nPairsTried / Abc_MaxInt(nPairsAll, 1) );
731 printf( " Used =%9d (%6.2f %%)", nPairsUsed, 100.0 * nPairsUsed / Abc_MaxInt(nPairsAll, 1) );
732 printf( " Xor =%9d (%6.2f %%)", nPairsXor, 100.0 * nPairsXor / Abc_MaxInt(nPairsAll, 1) );
733 printf( "\n" );
734 printf( "Div: " );
735 printf( " Total =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
736 printf( " Tried =%9d (%6.2f %%)", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
737 printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
738 printf( " Xor =%9d (%6.2f %%)", nDivsXor, 100.0 * nDivsXor / Abc_MaxInt(nDivsAll, 1) );
739 printf( "\n" );
740 }
741
742 /**Function*************************************************************
743
744 Synopsis [Derives new AIG.]
745
746 Description []
747
748 SideEffects []
749
750 SeeAlso []
751
752 ***********************************************************************/
Dam_ManMultiAig_rec(Dam_Man_t * pMan,Gia_Man_t * pNew,Gia_Man_t * p,Gia_Obj_t * pObj)753 void Dam_ManMultiAig_rec( Dam_Man_t * pMan, Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
754 {
755 int i, * pSet;
756 if ( ~pObj->Value )
757 return;
758 assert( Gia_ObjIsAnd(pObj) );
759 pSet = Dam_ObjSet(pMan, Gia_ObjId(p, pObj));
760 if ( pSet == NULL )
761 {
762 Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
763 Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin1(pObj) );
764 if ( Gia_ObjIsMux(p, pObj) )
765 {
766 Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin2(p, pObj) );
767 pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
768 }
769 else if ( Gia_ObjIsXor(pObj) )
770 pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
771 else
772 pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
773 Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
774 return;
775 }
776 assert( Gia_ObjIsXor(pObj) || Gia_ObjIsAndReal(p, pObj) );
777 // call recursively
778 for ( i = 1; i <= pSet[0]; i++ )
779 {
780 Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(pSet[i]) );
781 Dam_ManMultiAig_rec( pMan, pNew, p, pTemp );
782 pSet[i] = Abc_LitNotCond( pTemp->Value, Abc_LitIsCompl(pSet[i]) );
783 }
784 // create balanced gate
785 pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, pSet + 1, pSet[0] );
786 }
Dam_ManMultiAig(Dam_Man_t * pMan)787 Gia_Man_t * Dam_ManMultiAig( Dam_Man_t * pMan )
788 {
789 Gia_Man_t * p = pMan->pGia;
790 Gia_Man_t * pNew, * pTemp;
791 Gia_Obj_t * pObj;
792 int i;
793 // start the new manager
794 pNew = Gia_ManStart( 2*Gia_ManObjNum(p) );
795 pNew->pName = Abc_UtilStrsav( p->pName );
796 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
797 pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
798 pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
799 // create constant and inputs
800 Gia_ManFillValue( p );
801 Gia_ManConst0(p)->Value = 0;
802 Gia_ManForEachCi( p, pObj, i )
803 {
804 pObj->Value = Gia_ManAppendCi( pNew );
805 Vec_IntWriteEntry( pNew->vLevels, Abc_Lit2Var(pObj->Value), Gia_ObjLevel(p, pObj) );
806 }
807 // create internal nodes
808 Gia_ManHashStart( pNew );
809 Gia_ManForEachBuf( p, pObj, i )
810 {
811 Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
812 pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
813 Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
814 }
815 Gia_ManForEachCo( p, pObj, i )
816 {
817 Dam_ManMultiAig_rec( pMan, pNew, p, Gia_ObjFanin0(pObj) );
818 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
819 }
820 // assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
821 Gia_ManHashStop( pNew );
822 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
823 // perform cleanup
824 pNew = Gia_ManCleanup( pTemp = pNew );
825 Gia_ManStop( pTemp );
826 return pNew;
827 }
828
829 /**Function*************************************************************
830
831 Synopsis [Updates the data-structure after extracting one divisor.]
832
833 Description []
834
835 SideEffects []
836
837 SeeAlso []
838
839 ***********************************************************************/
Dam_PrintDiv(Dam_Man_t * p,int iDiv)840 void Dam_PrintDiv( Dam_Man_t * p, int iDiv )
841 {
842 if ( iDiv == 0 )
843 printf( "Final statistics after extracting %6d divisors: ", p->nDivs );
844 else
845 {
846 char Buffer[100];
847 int iData0 = Hash_IntObjData0(p->vHash, iDiv);
848 int iData1 = Hash_IntObjData1(p->vHash, iDiv);
849 printf( "Div%5d : ", p->nDivs+1 );
850 printf( "D%-8d = ", iDiv );
851 sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData0)? '!':' ', Abc_Lit2Var(iData0) );
852 printf( "%8s ", Buffer );
853 printf( "%c ", (iData0 < iData1) ? '*' : '+' );
854 sprintf( Buffer, "%c%d", Abc_LitIsCompl(iData1)? '!':' ', Abc_Lit2Var(iData1) );
855 printf( "%8s ", Buffer );
856 printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, iDiv) );
857 }
858 printf( "Divs =%8d ", Hash_IntManEntryNum(p->vHash) );
859 printf( "Ands =%8d ", p->nAnds - p->nGain );
860 Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
861 }
Dam_PrintQue(Dam_Man_t * p)862 void Dam_PrintQue( Dam_Man_t * p )
863 {
864 int i;
865 printf( "Divisor queue: \n" );
866 for ( i = 1; i <= Hash_IntManEntryNum(p->vHash); i++ )
867 {
868 int iLit0 = Hash_IntObjData0(p->vHash, i);
869 int iLit1 = Hash_IntObjData1(p->vHash, i);
870 printf( "Div %7d : ", i );
871 printf( "Weight %9.2f ", Vec_FltEntry(p->vCounts, i) );
872 printf( "F = %c%c ", Abc_LitIsCompl(iLit0) ? '!': ' ', 'a' + Abc_Lit2Var(iLit0)-1 );
873 printf( "%c ", (Hash_IntObjData0(p->vHash, i) < Hash_IntObjData1(p->vHash, i)) ? '*':'+' );
874 printf( "%c%c ", Abc_LitIsCompl(iLit1) ? '!': ' ', 'a' + Abc_Lit2Var(iLit1)-1 );
875 printf( "\n" );
876 }
877 }
Dam_ManUpdateNode(Dam_Man_t * p,int iObj,int iLit0,int iLit1,int iLitNew,Vec_Int_t * vDivs)878 int Dam_ManUpdateNode( Dam_Man_t * p, int iObj, int iLit0, int iLit1, int iLitNew, Vec_Int_t * vDivs )
879 {
880 int * pSet = Dam_ObjSet( p, iObj );
881 int i, k, c, Num, iLit, iLit2, fPres;
882 // check if literal can be found
883 for ( i = 1; i <= pSet[0]; i++ )
884 if ( pSet[i] == iLit0 )
885 break;
886 if ( i > pSet[0] )
887 return 0;
888 // check if literal can be found
889 for ( i = 1; i <= pSet[0]; i++ )
890 if ( pSet[i] == iLit1 )
891 break;
892 if ( i > pSet[0] )
893 return 0;
894 // compact literals
895 Vec_IntPush( vDivs, -iObj );
896 for ( k = i = 1; i <= pSet[0]; i++ )
897 {
898 if ( iLit0 == pSet[i] || iLit1 == pSet[i] )
899 continue;
900 pSet[k++] = iLit = pSet[i];
901 // reduce weights of the divisors
902 fPres = 0;
903 for ( c = 0; c < 2; c++ )
904 {
905 iLit2 = c ? iLit1 : iLit0;
906 if ( (iLit > iLit2) ^ (iLit0 > iLit1) )
907 Num = *Hash_Int2ManLookup( p->vHash, iLit2, iLit );
908 else
909 Num = *Hash_Int2ManLookup( p->vHash, iLit, iLit2 );
910 if ( Num > 0 )
911 {
912 Vec_FltAddToEntry( p->vCounts, Num, -1 );
913 if ( Vec_QueIsMember(p->vQue, Num) )
914 {
915 Vec_QueUpdate( p->vQue, Num );
916 fPres |= (1 << c);
917 }
918 }
919 }
920 if ( fPres != 3 )
921 continue;
922 if ( (iLit > iLitNew) ^ (iLit0 > iLit1) )
923 Num = Hash_Int2ManInsert( p->vHash, iLitNew, iLit, 0 );
924 else
925 Num = Hash_Int2ManInsert( p->vHash, iLit, iLitNew, 0 );
926 Hash_Int2ObjInc( p->vHash, Num );
927 Vec_IntPush( vDivs, Num );
928 // update reverse level
929 if ( Num >= Vec_IntSize(p->vDivLevR) )
930 Vec_IntFillExtra( p->vDivLevR, 3 * Vec_IntSize(p->vDivLevR) / 2, 0 );
931 Vec_IntUpdateEntry( p->vDivLevR, Num, Vec_IntEntry(p->vNodLevR, iObj) );
932 }
933 pSet[k] = iLitNew;
934 pSet[0] = k;
935 return 1;
936 }
Dam_ManUpdate(Dam_Man_t * p,int iDiv)937 void Dam_ManUpdate( Dam_Man_t * p, int iDiv )
938 {
939 Vec_Int_t * vDivs = p->pGia->vSuper;
940 int iLit0 = Hash_IntObjData0(p->vHash, iDiv);
941 int iLit1 = Hash_IntObjData1(p->vHash, iDiv);
942 int i, iLitNew, * pSet, * pNods = Dam_DivSet( p, iDiv );
943 int nPresent = 0, nPairsStart, nPairsStop, pPairsNew, nRefs;
944 int fThisIsXor = (iLit0 > iLit1), iDivTemp, iNode;
945 // Dam_PrintQue( p );
946 if ( fThisIsXor )
947 iLitNew = Gia_ManAppendXorReal( p->pGia, iLit0, iLit1 );
948 else
949 iLitNew = Gia_ManAppendAnd( p->pGia, iLit0, iLit1 );
950 Gia_ObjSetGateLevel( p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew)) );
951 // printf( "%d ", Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia, Abc_Lit2Var(iLitNew))) );
952 // replace entries
953 assert( pNods[0] >= 2 );
954 nPairsStart = Hash_IntManEntryNum(p->vHash) + 1;
955 Vec_IntClear( vDivs );
956 for ( i = 1; i <= pNods[0]; i++ )
957 nPresent += Dam_ManUpdateNode( p, pNods[i], iLit0, iLit1, iLitNew, vDivs );
958 nPairsStop = Hash_IntManEntryNum(p->vHash) + 1;
959 // extend arrayvs
960 pPairsNew = 0;
961 Vec_FltFillExtra( p->vCounts, nPairsStop, 0 );
962 Vec_IntFillExtra( p->vDiv2Nod, nPairsStop, -1 );
963 for ( i = nPairsStart; i < nPairsStop; i++ )
964 {
965 nRefs = Hash_IntObjData2(p->vHash, i);
966 if ( nRefs < 2 )
967 continue;
968 Vec_FltWriteEntry( p->vCounts, i, nRefs + 0.001*Dam_ManDivSlack(p, Hash_IntObjData0(p->vHash, i), Hash_IntObjData1(p->vHash, i), Vec_IntEntry(p->vDivLevR, i)) );
969 Vec_QuePush( p->vQue, i );
970 // remember divisors
971 Vec_IntWriteEntry( p->vDiv2Nod, i, Vec_IntSize(p->vNodStore) );
972 Vec_IntPush( p->vNodStore, 0 );
973 Vec_IntFillExtra( p->vNodStore, Vec_IntSize(p->vNodStore) + nRefs, -1 );
974 pPairsNew++;
975 }
976 // printf( "Added %d new pairs\n", pPairsNew );
977 // fill in the divisors
978 iNode = -1;
979 Vec_IntForEachEntry( vDivs, iDivTemp, i )
980 {
981 if ( iDivTemp < 0 )
982 {
983 iNode = -iDivTemp;
984 continue;
985 }
986 if ( Vec_IntEntry(p->vDiv2Nod, iDivTemp) == -1 )
987 continue;
988 pSet = Dam_DivSet( p, iDivTemp );
989 pSet[++pSet[0]] = iNode;
990 }
991 // make sure divisors are added correctly
992 for ( i = nPairsStart; i < nPairsStop; i++ )
993 if ( Vec_IntEntry(p->vDiv2Nod, i) > 0 )
994 assert( Dam_DivSet(p, i)[0] == Hash_IntObjData2(p->vHash, i) );
995 // update costs
996 Vec_FltWriteEntry( p->vCounts, iDiv, 0 );
997 p->nGain += (1 + 2 * fThisIsXor) * (nPresent - 1);
998 p->nGainX += 3 * fThisIsXor * (nPresent - 1);
999 p->nDivs++;
1000 }
1001
1002 /**Function*************************************************************
1003
1004 Synopsis [Perform extraction for multi-input AND/XOR.]
1005
1006 Description []
1007
1008 SideEffects []
1009
1010 SeeAlso []
1011
1012 ***********************************************************************/
Dam_ManAreaBalanceInt(Gia_Man_t * pGia,Vec_Int_t * vCiLevels,int nNewNodesMax,int fVerbose,int fVeryVerbose)1013 Gia_Man_t * Dam_ManAreaBalanceInt( Gia_Man_t * pGia, Vec_Int_t * vCiLevels, int nNewNodesMax, int fVerbose, int fVeryVerbose )
1014 {
1015 Gia_Man_t * pNew;
1016 Dam_Man_t * p;
1017 int i, iDiv;
1018 p = Dam_ManAlloc( pGia );
1019 p->nLevelMax = Gia_ManSetLevels( p->pGia, vCiLevels );
1020 p->vNodLevR = Gia_ManReverseLevel( p->pGia );
1021 Vec_IntFillExtra( p->pGia->vLevels, 3*Gia_ManObjNum(p->pGia)/2, 0 );
1022 Dam_ManCreatePairs( p, fVerbose );
1023 for ( i = 0; i < nNewNodesMax && Vec_QueTopPriority(p->vQue) >= 2; i++ )
1024 {
1025 iDiv = Vec_QuePop(p->vQue);
1026 if ( fVeryVerbose )
1027 Dam_PrintDiv( p, iDiv );
1028 Dam_ManUpdate( p, iDiv );
1029 }
1030 if ( fVeryVerbose )
1031 Dam_PrintDiv( p, 0 );
1032 pNew = Dam_ManMultiAig( p );
1033 if ( fVerbose )
1034 {
1035 int nDivsAll = Hash_IntManEntryNum(p->vHash);
1036 int nDivsUsed = p->nDivs;
1037 printf( "Div: " );
1038 printf( " Total =%9d (%6.2f %%) ", nDivsAll, 100.0 * nDivsAll / Abc_MaxInt(nDivsAll, 1) );
1039 printf( " Used =%9d (%6.2f %%)", nDivsUsed, 100.0 * nDivsUsed / Abc_MaxInt(nDivsAll, 1) );
1040 printf( " Gain =%6d (%6.2f %%)", p->nGain, 100.0 * p->nGain / Abc_MaxInt(p->nAnds, 1) );
1041 printf( " GainX = %d ", p->nGainX );
1042 Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
1043 }
1044 Dam_ManFree( p );
1045 return pNew;
1046 }
Gia_ManAreaBalance(Gia_Man_t * p,int fSimpleAnd,int nNewNodesMax,int fVerbose,int fVeryVerbose)1047 Gia_Man_t * Gia_ManAreaBalance( Gia_Man_t * p, int fSimpleAnd, int nNewNodesMax, int fVerbose, int fVeryVerbose )
1048 {
1049 Gia_Man_t * pNew0, * pNew, * pNew1, * pNew2;
1050 Vec_Int_t * vCiLevels;
1051 // set arrival times for the input of the new AIG
1052 if ( p->vCiArrs )
1053 {
1054 int i, Id, And2Delay = p->And2Delay ? p->And2Delay : 1;
1055 Vec_IntFreeP( &p->vLevels );
1056 p->vLevels = Vec_IntStart( Gia_ManObjNum(p) );
1057 Gia_ManForEachCiId( p, Id, i )
1058 Vec_IntWriteEntry( p->vLevels, Id, Vec_IntEntry(p->vCiArrs, i)/And2Delay );
1059 }
1060 else if ( p->vInArrs )
1061 {
1062 int i, Id, And2Delay = p->And2Delay ? p->And2Delay : 1;
1063 Gia_ManForEachCiId( p, Id, i )
1064 Vec_IntWriteEntry( p->vLevels, Id, (int)(Vec_FltEntry(p->vInArrs, i)/And2Delay) );
1065 }
1066 // determine CI levels
1067 if ( p->pManTime && p->vLevels == NULL )
1068 Gia_ManLevelWithBoxes( p );
1069 vCiLevels = Gia_ManGetCiLevels( p );
1070 // get the starting manager
1071 pNew0 = Gia_ManHasMapping(p) ? (Gia_Man_t *)Dsm_ManDeriveGia(p, 0) : Gia_ManDup(p);
1072 Gia_ManTransferTiming( pNew0, p );
1073 if ( fVerbose ) Gia_ManPrintStats( pNew0, NULL );
1074 // derive internal manager
1075 pNew = fSimpleAnd ? Gia_ManDup( pNew0 ) : Gia_ManDupMuxes( pNew0, 2 );
1076 Gia_ManTransferTiming( pNew, pNew0 );
1077 if ( fVerbose ) Gia_ManPrintStats( pNew, NULL );
1078 if ( pNew0 != p ) Gia_ManStop( pNew0 );
1079 // perform the operation
1080 pNew1 = Dam_ManAreaBalanceInt( pNew, vCiLevels, nNewNodesMax, fVerbose, fVeryVerbose );
1081 Gia_ManTransferTiming( pNew1, pNew );
1082 if ( fVerbose ) Gia_ManPrintStats( pNew1, NULL );
1083 Gia_ManStop( pNew );
1084 Vec_IntFreeP( &vCiLevels );
1085 // derive the final result
1086 pNew2 = Gia_ManDupNoMuxes( pNew1, 0 );
1087 Gia_ManTransferTiming( pNew2, pNew1 );
1088 if ( fVerbose ) Gia_ManPrintStats( pNew2, NULL );
1089 Gia_ManStop( pNew1 );
1090 // normalize if needed
1091 if ( !Gia_ManIsNormalized(pNew2) )
1092 {
1093 pNew2 = Gia_ManDupNormalize( pNew1 = pNew2, 0 );
1094 Gia_ManTransferTiming( pNew2, pNew1 );
1095 Gia_ManStop( pNew1 );
1096 }
1097 //Gia_ManTransferTiming( pNew2, p );
1098 return pNew2;
1099 }
1100
1101 ////////////////////////////////////////////////////////////////////////
1102 /// END OF FILE ///
1103 ////////////////////////////////////////////////////////////////////////
1104
1105
1106 ABC_NAMESPACE_IMPL_END
1107
1108