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