1 /**CFile****************************************************************
2 
3   FileName    [acecFadds.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [CEC for arithmetic circuits.]
8 
9   Synopsis    [Detecting half-adders and full-adders.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - June 20, 2005.]
16 
17   Revision    [$Id: acecFadds.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "acecInt.h"
22 #include "misc/vec/vecWec.h"
23 #include "misc/tim/tim.h"
24 
25 ABC_NAMESPACE_IMPL_START
26 
27 
28 ////////////////////////////////////////////////////////////////////////
29 ///                        DECLARATIONS                              ///
30 ////////////////////////////////////////////////////////////////////////
31 
32 #define Dtc_ForEachCut( pList, pCut, i ) for ( i = 0, pCut = pList + 1; i < pList[0]; i++, pCut += pCut[0] + 1 )
33 #define Dtc_ForEachFadd( vFadds, i )     for ( i = 0; i < Vec_IntSize(vFadds)/5; i++ )
34 
35 ////////////////////////////////////////////////////////////////////////
36 ///                     FUNCTION DEFINITIONS                         ///
37 ////////////////////////////////////////////////////////////////////////
38 
39 /**Function*************************************************************
40 
41   Synopsis    [Detecting HADDs in the AIG.]
42 
43   Description []
44 
45   SideEffects []
46 
47   SeeAlso     []
48 
49 ***********************************************************************/
Gia_ManDetectHalfAdders(Gia_Man_t * p,int fVerbose)50 Vec_Int_t * Gia_ManDetectHalfAdders( Gia_Man_t * p, int fVerbose )
51 {
52     Vec_Int_t * vHadds = Vec_IntAlloc( 1000 );
53     Gia_Obj_t * pObj, * pFan0, * pFan1;
54     int i, iLit, iFan0, iFan1, fComplDiff, Count, Counts[5] = {0};
55     Gia_ManHashStart( p );
56     if ( p->nXors )
57     {
58         Gia_ManForEachAnd( p, pObj, i )
59         {
60             if ( !Gia_ObjIsXor(pObj) )
61                 continue;
62             Count = 0;
63             iFan0 = Gia_ObjFaninId0(pObj, i);
64             iFan1 = Gia_ObjFaninId1(pObj, i);
65             if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 0), Abc_Var2Lit(iFan1, 0))) )
66                 Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
67             if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 1), Abc_Var2Lit(iFan1, 1))) )
68                 Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
69             if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 0), Abc_Var2Lit(iFan1, 1))) )
70                 Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
71             if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 1), Abc_Var2Lit(iFan1, 0))) )
72                 Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
73             Counts[Count]++;
74         }
75     }
76     else
77     {
78         ABC_FREE( p->pRefs );
79         Gia_ManCreateRefs( p );
80         Gia_ManForEachAnd( p, pObj, i )
81         {
82             if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
83                 continue;
84             Count = 0;
85             if ( Gia_ObjRefNumId(p, Gia_ObjFaninId0(pObj, i)) > 1 )
86                 Vec_IntPushTwo( vHadds, i, Gia_ObjFaninId0(pObj, i) ), Count++;
87             if ( Gia_ObjRefNumId(p, Gia_ObjFaninId1(pObj, i)) > 1 )
88                 Vec_IntPushTwo( vHadds, i, Gia_ObjFaninId1(pObj, i) ), Count++;
89             iFan0 = Gia_ObjId( p, pFan0 );
90             iFan1 = Gia_ObjId( p, pFan1 );
91             fComplDiff =          (Gia_ObjFaninC0(Gia_ObjFanin0(pObj)) ^ Gia_ObjFaninC1(Gia_ObjFanin0(pObj)));
92             assert( fComplDiff == (Gia_ObjFaninC0(Gia_ObjFanin1(pObj)) ^ Gia_ObjFaninC1(Gia_ObjFanin1(pObj))) );
93             if ( fComplDiff )
94             {
95                 if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 0), Abc_Var2Lit(iFan1, 0))) )
96                     Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
97                 if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 1), Abc_Var2Lit(iFan1, 1))) )
98                     Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
99             }
100             else
101             {
102                 if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 0), Abc_Var2Lit(iFan1, 1))) )
103                     Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
104                 if ( (iLit = Gia_ManHashLookupInt(p, Abc_Var2Lit(iFan0, 1), Abc_Var2Lit(iFan1, 0))) )
105                     Vec_IntPushTwo( vHadds, i, Abc_Lit2Var(iLit) ), Count++;
106             }
107             Counts[Count]++;
108         }
109         ABC_FREE( p->pRefs );
110     }
111     Gia_ManHashStop( p );
112     if ( fVerbose )
113     {
114         int iXor, iAnd;
115         printf( "Found %d half-adders with XOR gates: ", Vec_IntSize(vHadds)/2 );
116         for ( i = 0; i <= 4; i++ )
117             printf( "%d=%d ", i, Counts[i] );
118         printf( "\n" );
119 
120         Vec_IntForEachEntryDouble( vHadds, iXor, iAnd, i )
121         {
122             pObj = Gia_ManObj( p, iXor );
123             printf( "%3d : %5d %5d -> %5d %5d\n", i, Gia_ObjFaninId0(pObj, iXor), Gia_ObjFaninId1(pObj, iXor), iXor, iAnd );
124         }
125     }
126     return vHadds;
127 }
128 
129 /**Function*************************************************************
130 
131   Synopsis    [Derive GIA with boxes containing adder-chains.]
132 
133   Description []
134 
135   SideEffects []
136 
137   SeeAlso     []
138 
139 ***********************************************************************/
Gia_ManIllustrateBoxes(Gia_Man_t * p)140 void Gia_ManIllustrateBoxes( Gia_Man_t * p )
141 {
142     Tim_Man_t * pManTime = (Tim_Man_t *)p->pManTime;
143     int nBoxes = Tim_ManBoxNum( pManTime );
144     int i, k, curCi, curCo, nBoxIns, nBoxOuts;
145     Gia_Obj_t * pObj;
146     // walk through the boxes
147     curCi = Tim_ManPiNum(pManTime);
148     curCo = 0;
149     for ( i = 0; i < nBoxes; i++ )
150     {
151         nBoxIns = Tim_ManBoxInputNum(pManTime, i);
152         nBoxOuts = Tim_ManBoxOutputNum(pManTime, i);
153         printf( "Box %4d  [%d x %d] :   ", i, nBoxIns, nBoxOuts );
154         printf( "Input obj IDs = " );
155         for ( k = 0; k < nBoxIns; k++ )
156         {
157             pObj = Gia_ManCo( p, curCo + k );
158             printf( "%d ", Gia_ObjId(p, pObj) );
159         }
160         printf( "  Output obj IDs = " );
161         for ( k = 0; k < nBoxOuts; k++ )
162         {
163             pObj = Gia_ManCi( p, curCi + k );
164             printf( "%d ", Gia_ObjId(p, pObj) );
165         }
166         curCo += nBoxIns;
167         curCi += nBoxOuts;
168         printf( "\n" );
169     }
170     curCo += Tim_ManPoNum(pManTime);
171     // verify counts
172     assert( curCi == Gia_ManCiNum(p) );
173     assert( curCo == Gia_ManCoNum(p) );
174 }
175 
176 /**Function*************************************************************
177 
178   Synopsis    [Detecting FADDs in the AIG.]
179 
180   Description []
181 
182   SideEffects []
183 
184   SeeAlso     []
185 
186 ***********************************************************************/
Dtc_ManCutMergeOne(int * pCut0,int * pCut1,int * pCut)187 int Dtc_ManCutMergeOne( int * pCut0, int * pCut1, int * pCut )
188 {
189     int i, k;
190     for ( k = 0; k <= pCut1[0]; k++ )
191         pCut[k] = pCut1[k];
192     for ( i = 1; i <= pCut0[0]; i++ )
193     {
194         for ( k = 1; k <= pCut1[0]; k++ )
195             if ( pCut0[i] == pCut1[k] )
196                 break;
197         if ( k <= pCut1[0] )
198             continue;
199         if ( pCut[0] == 3 )
200             return 0;
201         pCut[1+pCut[0]++] = pCut0[i];
202     }
203     assert( pCut[0] == 2 || pCut[0] == 3 );
204     if ( pCut[1] > pCut[2] )
205         ABC_SWAP( int, pCut[1], pCut[2] );
206     assert( pCut[1] < pCut[2] );
207     if ( pCut[0] == 2 )
208         return 1;
209     if ( pCut[2] > pCut[3] )
210         ABC_SWAP( int, pCut[2], pCut[3] );
211     if ( pCut[1] > pCut[2] )
212         ABC_SWAP( int, pCut[1], pCut[2] );
213     assert( pCut[1] < pCut[2] );
214     assert( pCut[2] < pCut[3] );
215     return 1;
216 }
Dtc_ManCutCheckEqual(Vec_Int_t * vCuts,int * pCutNew)217 int Dtc_ManCutCheckEqual( Vec_Int_t * vCuts, int * pCutNew )
218 {
219     int * pList = Vec_IntArray( vCuts );
220     int i, k, * pCut;
221     Dtc_ForEachCut( pList, pCut, i )
222     {
223         for ( k = 0; k <= pCut[0]; k++ )
224             if ( pCut[k] != pCutNew[k] )
225                 break;
226         if ( k > pCut[0] )
227             return 1;
228     }
229     return 0;
230 }
Dtc_ObjComputeTruth_rec(Gia_Obj_t * pObj)231 int Dtc_ObjComputeTruth_rec( Gia_Obj_t * pObj )
232 {
233     int Truth0, Truth1;
234     if ( pObj->Value )
235         return pObj->Value;
236     assert( Gia_ObjIsAnd(pObj) );
237     Truth0 = Dtc_ObjComputeTruth_rec( Gia_ObjFanin0(pObj) );
238     Truth1 = Dtc_ObjComputeTruth_rec( Gia_ObjFanin1(pObj) );
239     if ( Gia_ObjIsXor(pObj) )
240         return (pObj->Value = (Gia_ObjFaninC0(pObj) ? ~Truth0 : Truth0) ^ (Gia_ObjFaninC1(pObj) ? ~Truth1 : Truth1));
241     else
242         return (pObj->Value = (Gia_ObjFaninC0(pObj) ? ~Truth0 : Truth0) & (Gia_ObjFaninC1(pObj) ? ~Truth1 : Truth1));
243 }
Dtc_ObjCleanTruth_rec(Gia_Obj_t * pObj)244 void Dtc_ObjCleanTruth_rec( Gia_Obj_t * pObj )
245 {
246     if ( !pObj->Value )
247         return;
248     pObj->Value = 0;
249     if ( !Gia_ObjIsAnd(pObj) )
250         return;
251     Dtc_ObjCleanTruth_rec( Gia_ObjFanin0(pObj) );
252     Dtc_ObjCleanTruth_rec( Gia_ObjFanin1(pObj) );
253 }
Dtc_ObjComputeTruth(Gia_Man_t * p,int iObj,int * pCut,int * pTruth)254 int Dtc_ObjComputeTruth( Gia_Man_t * p, int iObj, int * pCut, int * pTruth )
255 {
256     unsigned Truth, Truths[3] = { 0xAA, 0xCC, 0xF0 }; int i;
257     for ( i = 1; i <= pCut[0]; i++ )
258         Gia_ManObj(p, pCut[i])->Value = Truths[i-1];
259     Truth = 0xFF & Dtc_ObjComputeTruth_rec( Gia_ManObj(p, iObj) );
260     Dtc_ObjCleanTruth_rec( Gia_ManObj(p, iObj) );
261     if ( pTruth )
262         *pTruth = Truth;
263     if ( Truth == 0x66 || Truth == 0x99 )
264         return 3;
265     if ( Truth == 0x96 || Truth == 0x69 )
266         return 1;
267     if ( Truth == 0xE8 || Truth == 0xD4 || Truth == 0xB2 || Truth == 0x71 ||
268          Truth == 0x17 || Truth == 0x2B || Truth == 0x4D || Truth == 0x8E )
269         return 2;
270     return 0;
271 }
Dtc_ManCutMerge(Gia_Man_t * p,int iObj,int * pList0,int * pList1,Vec_Int_t * vCuts,Vec_Int_t * vCutsXor2,Vec_Int_t * vCutsXor,Vec_Int_t * vCutsMaj)272 void Dtc_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_Int_t * vCuts, Vec_Int_t * vCutsXor2, Vec_Int_t * vCutsXor, Vec_Int_t * vCutsMaj )
273 {
274     int fVerbose = 0;
275     Vec_Int_t * vTemp;
276     int i, k, c, Type, * pCut0, * pCut1, pCut[4];
277     if ( fVerbose )
278         printf( "Object %d = :\n", iObj );
279     Vec_IntFill( vCuts, 2, 1 );
280     Vec_IntPush( vCuts, iObj );
281     Dtc_ForEachCut( pList0, pCut0, i )
282     Dtc_ForEachCut( pList1, pCut1, k )
283     {
284         if ( !Dtc_ManCutMergeOne(pCut0, pCut1, pCut) )
285             continue;
286         if ( Dtc_ManCutCheckEqual(vCuts, pCut) )
287             continue;
288         Vec_IntAddToEntry( vCuts, 0, 1 );
289         if ( fVerbose )
290             printf( "%d : ", pCut[0] );
291         for ( c = 0; c <= pCut[0]; c++ )
292         {
293             Vec_IntPush( vCuts, pCut[c] );
294             if ( fVerbose && c )
295                 printf( "%d ", pCut[c] );
296         }
297         if ( fVerbose )
298             printf( "\n" );
299         if ( pCut[0] == 2 )
300         {
301             int Value = Dtc_ObjComputeTruth( p, iObj, pCut, NULL );
302             assert( Value == 3 || Value == 0 );
303             if ( Value == 3 )
304             {
305                 Vec_IntPush( vCutsXor2, pCut[1] );
306                 Vec_IntPush( vCutsXor2, pCut[2] );
307                 Vec_IntPush( vCutsXor2, iObj );
308             }
309             continue;
310         }
311         if ( pCut[0] != 3 )
312             continue;
313         Type = Dtc_ObjComputeTruth( p, iObj, pCut, NULL );
314         if ( Type == 0 )
315             continue;
316         vTemp = Type == 1 ? vCutsXor : vCutsMaj;
317         if ( fVerbose )
318             printf( "%d = %s(", iObj, Type == 1 ? "XOR" : "MAJ" );
319         for ( c = 1; c <= pCut[0]; c++ )
320         {
321             if ( fVerbose )
322                 printf( " %d", pCut[c] );
323             Vec_IntPush( vTemp, pCut[c] );
324         }
325         if ( fVerbose )
326             printf( " )\n" );
327         Vec_IntPush( vTemp, iObj );
328     }
329 }
Dtc_ManComputeCuts(Gia_Man_t * p,Vec_Int_t ** pvCutsXor2,Vec_Int_t ** pvCutsXor,Vec_Int_t ** pvCutsMaj,int fVerbose)330 void Dtc_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvCutsXor2, Vec_Int_t ** pvCutsXor, Vec_Int_t ** pvCutsMaj, int fVerbose )
331 {
332     Gia_Obj_t * pObj;
333     int * pList0, * pList1, i, nCuts = 0;
334     Vec_Int_t * vTemp = Vec_IntAlloc( 1000 );
335     Vec_Int_t * vCutsXor2 = Vec_IntAlloc( Gia_ManAndNum(p) );
336     Vec_Int_t * vCutsXor = Vec_IntAlloc( Gia_ManAndNum(p) );
337     Vec_Int_t * vCutsMaj = Vec_IntAlloc( Gia_ManAndNum(p) );
338     Vec_Int_t * vCuts = Vec_IntAlloc( 30 * Gia_ManAndNum(p) );
339     Vec_IntFill( vCuts, Gia_ManObjNum(p), 0 );
340     Gia_ManCleanValue( p );
341     Gia_ManForEachCi( p, pObj, i )
342     {
343         Vec_IntWriteEntry( vCuts, Gia_ObjId(p, pObj), Vec_IntSize(vCuts) );
344         Vec_IntPush( vCuts, 1 );
345         Vec_IntPush( vCuts, 1 );
346         Vec_IntPush( vCuts, Gia_ObjId(p, pObj) );
347     }
348     Gia_ManForEachAnd( p, pObj, i )
349     {
350         pList0 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId0(pObj, i)) );
351         pList1 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId1(pObj, i)) );
352         Dtc_ManCutMerge( p, i, pList0, pList1, vTemp, vCutsXor2, vCutsXor, vCutsMaj );
353         Vec_IntWriteEntry( vCuts, i, Vec_IntSize(vCuts) );
354         Vec_IntAppend( vCuts, vTemp );
355         nCuts += Vec_IntEntry( vTemp, 0 );
356     }
357     if ( fVerbose )
358         printf( "Nodes = %d.  Cuts = %d.  Cuts/Node = %.2f.  Ints/Node = %.2f.\n",
359             Gia_ManAndNum(p), nCuts, 1.0*nCuts/Gia_ManAndNum(p), 1.0*Vec_IntSize(vCuts)/Gia_ManAndNum(p) );
360     Vec_IntFree( vTemp );
361     Vec_IntFree( vCuts );
362     if ( pvCutsXor2 )
363         *pvCutsXor2 = vCutsXor2;
364     else
365         Vec_IntFree( vCutsXor2 );
366     *pvCutsXor = vCutsXor;
367     *pvCutsMaj = vCutsMaj;
368 }
Dtc_ManFindCommonCuts(Gia_Man_t * p,Vec_Int_t * vCutsXor,Vec_Int_t * vCutsMaj)369 Vec_Int_t * Dtc_ManFindCommonCuts( Gia_Man_t * p, Vec_Int_t * vCutsXor, Vec_Int_t * vCutsMaj )
370 {
371     int * pCuts0 = Vec_IntArray(vCutsXor);
372     int * pCuts1 = Vec_IntArray(vCutsMaj);
373     int * pLimit0 = Vec_IntLimit(vCutsXor);
374     int * pLimit1 = Vec_IntLimit(vCutsMaj);   int i;
375     Vec_Int_t * vFadds = Vec_IntAlloc( 1000 );
376     assert( Vec_IntSize(vCutsXor) % 4 == 0 );
377     assert( Vec_IntSize(vCutsMaj) % 4 == 0 );
378     while ( pCuts0 < pLimit0 && pCuts1 < pLimit1 )
379     {
380         for ( i = 0; i < 3; i++ )
381             if ( pCuts0[i] != pCuts1[i] )
382                 break;
383         if ( i == 3 )
384         {
385             for ( i = 0; i < 4; i++ )
386                 Vec_IntPush( vFadds, pCuts0[i] );
387             Vec_IntPush( vFadds, pCuts1[3] );
388             pCuts0 += 4;
389             pCuts1 += 4;
390         }
391         else if ( pCuts0[i] < pCuts1[i] )
392             pCuts0 += 4;
393         else if ( pCuts0[i] > pCuts1[i] )
394             pCuts1 += 4;
395     }
396     assert( Vec_IntSize(vFadds) % 5 == 0 );
397     return vFadds;
398 }
Dtc_ManPrintFadds(Vec_Int_t * vFadds)399 void Dtc_ManPrintFadds( Vec_Int_t * vFadds )
400 {
401     int i;
402     Dtc_ForEachFadd( vFadds, i )
403     {
404         printf( "%6d : ", i );
405         printf( "%6d ", Vec_IntEntry(vFadds, 5*i+0) );
406         printf( "%6d ", Vec_IntEntry(vFadds, 5*i+1) );
407         printf( "%6d ", Vec_IntEntry(vFadds, 5*i+2) );
408         printf( " ->  " );
409         printf( "%6d ", Vec_IntEntry(vFadds, 5*i+3) );
410         printf( "%6d ", Vec_IntEntry(vFadds, 5*i+4) );
411         printf( "\n" );
412 
413         if ( i == 100 )
414         {
415             printf( "Skipping other FADDs.\n" );
416             break;
417         }
418     }
419 }
Dtc_ManCompare(int * pCut0,int * pCut1)420 int Dtc_ManCompare( int * pCut0, int * pCut1 )
421 {
422     if ( pCut0[0] < pCut1[0] ) return -1;
423     if ( pCut0[0] > pCut1[0] ) return  1;
424     if ( pCut0[1] < pCut1[1] ) return -1;
425     if ( pCut0[1] > pCut1[1] ) return  1;
426     if ( pCut0[2] < pCut1[2] ) return -1;
427     if ( pCut0[2] > pCut1[2] ) return  1;
428     return 0;
429 }
Dtc_ManCompare2(int * pCut0,int * pCut1)430 int Dtc_ManCompare2( int * pCut0, int * pCut1 )
431 {
432     if ( pCut0[4] < pCut1[4] ) return -1;
433     if ( pCut0[4] > pCut1[4] ) return  1;
434     return 0;
435 }
436 // returns array of 5-tuples containing inputs/sum/cout of each full adder
Gia_ManDetectFullAdders(Gia_Man_t * p,int fVerbose,Vec_Int_t ** pvCutsXor2)437 Vec_Int_t * Gia_ManDetectFullAdders( Gia_Man_t * p, int fVerbose, Vec_Int_t ** pvCutsXor2 )
438 {
439     Vec_Int_t * vCutsXor, * vCutsMaj, * vFadds;
440     Dtc_ManComputeCuts( p, pvCutsXor2, &vCutsXor, &vCutsMaj, fVerbose );
441     qsort( Vec_IntArray(vCutsXor), (size_t)(Vec_IntSize(vCutsXor)/4), 16, (int (*)(const void *, const void *))Dtc_ManCompare );
442     qsort( Vec_IntArray(vCutsMaj), (size_t)(Vec_IntSize(vCutsMaj)/4), 16, (int (*)(const void *, const void *))Dtc_ManCompare );
443     vFadds = Dtc_ManFindCommonCuts( p, vCutsXor, vCutsMaj );
444     qsort( Vec_IntArray(vFadds), (size_t)(Vec_IntSize(vFadds)/5), 20, (int (*)(const void *, const void *))Dtc_ManCompare2 );
445     if ( fVerbose )
446         printf( "XOR3 cuts = %d.  MAJ cuts = %d.  Full-adders = %d.\n", Vec_IntSize(vCutsXor)/4, Vec_IntSize(vCutsMaj)/4, Vec_IntSize(vFadds)/5 );
447     if ( fVerbose )
448         Dtc_ManPrintFadds( vFadds );
449     Vec_IntFree( vCutsXor );
450     Vec_IntFree( vCutsMaj );
451     return vFadds;
452 }
453 
454 /**Function*************************************************************
455 
456   Synopsis    [Map each MAJ into the topmost MAJ of its chain.]
457 
458   Description []
459 
460   SideEffects []
461 
462   SeeAlso     []
463 
464 ***********************************************************************/
465 // maps MAJ nodes into FADD indexes
Gia_ManCreateMap(Gia_Man_t * p,Vec_Int_t * vFadds)466 Vec_Int_t * Gia_ManCreateMap( Gia_Man_t * p, Vec_Int_t * vFadds )
467 {
468     Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );  int i;
469     Dtc_ForEachFadd( vFadds, i )
470         Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+4), i );
471     return vMap;
472 }
473 // find chain length (for each MAJ, how many FADDs are rooted in its first input)
Gia_ManFindChains_rec(Gia_Man_t * p,int iMaj,Vec_Int_t * vFadds,Vec_Int_t * vMap,Vec_Int_t * vLength)474 int Gia_ManFindChains_rec( Gia_Man_t * p, int iMaj, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Int_t * vLength )
475 {
476     assert( Vec_IntEntry(vMap, iMaj) >= 0 ); // MAJ
477     if ( Vec_IntEntry(vLength, iMaj) >= 0 )
478         return Vec_IntEntry(vLength, iMaj);
479     assert( Gia_ObjIsAnd(Gia_ManObj(p, iMaj)) );
480     {
481         int iFadd = Vec_IntEntry( vMap, iMaj );
482         int iXor0 = Vec_IntEntry( vFadds, 5*iFadd+0 );
483         int iXor1 = Vec_IntEntry( vFadds, 5*iFadd+1 );
484         int iXor2 = Vec_IntEntry( vFadds, 5*iFadd+2 );
485         int iLen0 = Vec_IntEntry( vMap, iXor0 ) == -1 ? 0 : Gia_ManFindChains_rec( p, iXor0, vFadds, vMap, vLength );
486         int iLen1 = Vec_IntEntry( vMap, iXor1 ) == -1 ? 0 : Gia_ManFindChains_rec( p, iXor1, vFadds, vMap, vLength );
487         int iLen2 = Vec_IntEntry( vMap, iXor2 ) == -1 ? 0 : Gia_ManFindChains_rec( p, iXor2, vFadds, vMap, vLength );
488         int iLen = Abc_MaxInt( iLen0, Abc_MaxInt(iLen1, iLen2) );
489         if ( iLen0 < iLen )
490         {
491             if ( iLen == iLen1 )
492             {
493                 ABC_SWAP( int, Vec_IntArray(vFadds)[5*iFadd+0], Vec_IntArray(vFadds)[5*iFadd+1] );
494             }
495             else if ( iLen == iLen2 )
496             {
497                 ABC_SWAP( int, Vec_IntArray(vFadds)[5*iFadd+0], Vec_IntArray(vFadds)[5*iFadd+2] );
498             }
499         }
500         Vec_IntWriteEntry( vLength, iMaj, iLen + 1 );
501         return iLen + 1;
502     }
503 }
504 // for each FADD find the longest chain and reorder its inputs
Gia_ManFindChains(Gia_Man_t * p,Vec_Int_t * vFadds,Vec_Int_t * vMap)505 void Gia_ManFindChains( Gia_Man_t * p, Vec_Int_t * vFadds, Vec_Int_t * vMap )
506 {
507     int i;
508     // for each FADD find the longest chain rooted in it
509     Vec_Int_t * vLength = Vec_IntStartFull( Gia_ManObjNum(p) );
510     Dtc_ForEachFadd( vFadds, i )
511         Gia_ManFindChains_rec( p, Vec_IntEntry(vFadds, 5*i+4), vFadds, vMap, vLength );
512     Vec_IntFree( vLength );
513 }
514 // collect one carry-chain
Gia_ManCollectOneChain(Gia_Man_t * p,Vec_Int_t * vFadds,int iFaddTop,Vec_Int_t * vMap,Vec_Int_t * vChain)515 void Gia_ManCollectOneChain( Gia_Man_t * p, Vec_Int_t * vFadds, int iFaddTop, Vec_Int_t * vMap, Vec_Int_t * vChain )
516 {
517     int iFadd;
518     Vec_IntClear( vChain );
519     for ( iFadd = iFaddTop; iFadd >= 0 &&
520           !Gia_ObjIsTravIdCurrentId(p, Vec_IntEntry(vFadds, 5*iFadd+3)) &&
521           !Gia_ObjIsTravIdCurrentId(p, Vec_IntEntry(vFadds, 5*iFadd+4));
522           iFadd = Vec_IntEntry(vMap, Vec_IntEntry(vFadds, 5*iFadd+0)) )
523           {
524                 Vec_IntPush( vChain, iFadd );
525           }
526     Vec_IntReverseOrder( vChain );
527 }
Gia_ManMarkWithTravId_rec(Gia_Man_t * p,int Id)528 void Gia_ManMarkWithTravId_rec( Gia_Man_t * p, int Id )
529 {
530     Gia_Obj_t * pObj;
531     if ( Gia_ObjIsTravIdCurrentId(p, Id) )
532         return;
533     Gia_ObjSetTravIdCurrentId(p, Id);
534     pObj = Gia_ManObj( p, Id );
535     if ( Gia_ObjIsAnd(pObj) )
536         Gia_ManMarkWithTravId_rec( p, Gia_ObjFaninId0(pObj, Id) );
537     if ( Gia_ObjIsAnd(pObj) )
538         Gia_ManMarkWithTravId_rec( p, Gia_ObjFaninId1(pObj, Id) );
539 }
540 // returns mapping of each MAJ into the topmost elements of its chain
Gia_ManCollectTopmost(Gia_Man_t * p,Vec_Int_t * vFadds,Vec_Int_t * vMap,int nFaddMin)541 Vec_Wec_t * Gia_ManCollectTopmost( Gia_Man_t * p, Vec_Int_t * vFadds, Vec_Int_t * vMap, int nFaddMin )
542 {
543     int i, j, iFadd;
544     Vec_Int_t * vChain  = Vec_IntAlloc( 100 );
545     Vec_Wec_t * vChains = Vec_WecAlloc( Vec_IntSize(vFadds)/5 );
546     // erase elements appearing as FADD inputs
547     Vec_Bit_t * vMarksTop = Vec_BitStart( Vec_IntSize(vFadds)/5 );
548     Dtc_ForEachFadd( vFadds, i )
549         if ( (iFadd = Vec_IntEntry(vMap, Vec_IntEntry(vFadds, 5*i+0))) >= 0 )
550             Vec_BitWriteEntry( vMarksTop, iFadd, 1 );
551     // compress the remaining ones
552     Gia_ManIncrementTravId( p );
553     Dtc_ForEachFadd( vFadds, i )
554     {
555         if ( Vec_BitEntry(vMarksTop, i) )
556             continue;
557         Gia_ManCollectOneChain( p, vFadds, i, vMap, vChain );
558         if ( Vec_IntSize(vChain) < nFaddMin )
559             continue;
560         Vec_IntAppend( Vec_WecPushLevel(vChains), vChain );
561         Vec_IntForEachEntry( vChain, iFadd, j )
562         {
563             assert( !Gia_ObjIsTravIdCurrentId(p, Vec_IntEntry(vFadds, 5*iFadd+3)) );
564             assert( !Gia_ObjIsTravIdCurrentId(p, Vec_IntEntry(vFadds, 5*iFadd+4)) );
565             Gia_ManMarkWithTravId_rec( p, Vec_IntEntry(vFadds, 5*iFadd+3) );
566             Gia_ManMarkWithTravId_rec( p, Vec_IntEntry(vFadds, 5*iFadd+4) );
567         }
568     }
569     // cleanup
570     Vec_BitFree( vMarksTop );
571     Vec_IntFree( vChain );
572     return vChains;
573 }
574 // prints chains beginning in majority nodes contained in vTops
Gia_ManPrintChains(Gia_Man_t * p,Vec_Int_t * vFadds,Vec_Int_t * vMap,Vec_Wec_t * vChains)575 void Gia_ManPrintChains( Gia_Man_t * p, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Wec_t * vChains )
576 {
577     Vec_Int_t * vChain;
578     int i, k, iFadd, Count = 0;
579     Vec_WecForEachLevel( vChains, vChain, i )
580     {
581         Count += Vec_IntSize(vChain);
582         if ( i < 10 )
583         {
584             printf( "Chain %4d : %4d    ", i, Vec_IntSize(vChain) );
585             Vec_IntForEachEntry( vChain, iFadd, k )
586             {
587                 printf( "%d(%d) ", iFadd, Vec_IntEntry(vFadds, 5*iFadd+4) );
588                 if ( k != Vec_IntSize(vChain) - 1 )
589                     printf( "-> " );
590                 if ( k > 6 )
591                 {
592                     printf( "..." );
593                     break;
594                 }
595             }
596             printf( "\n" );
597         }
598         else if ( i == 10 )
599             printf( "...\n" );
600 
601     }
602     printf( "Total chains = %d. Total full-adders = %d.\n", Vec_WecSize(vChains), Count );
603 }
604 // map SUM bits and topmost MAJ into topmost FADD number
Gia_ManFindMapping(Gia_Man_t * p,Vec_Int_t * vFadds,Vec_Int_t * vMap,Vec_Wec_t * vChains)605 Vec_Int_t * Gia_ManFindMapping( Gia_Man_t * p, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Wec_t * vChains )
606 {
607     Vec_Int_t * vChain;
608     int i, k, iFadd = -1;
609     Vec_Int_t * vMap2Chain = Vec_IntStartFull( Gia_ManObjNum(p) );
610     Vec_WecForEachLevel( vChains, vChain, i )
611     {
612         assert( Vec_IntSize(vChain) > 0 );
613         Vec_IntForEachEntry( vChain, iFadd, k )
614         {
615             //printf( "Chain %d: setting SUM %d (obj %d)\n", i, k, Vec_IntEntry(vFadds, 5*iFadd+3) );
616             assert( Vec_IntEntry(vMap2Chain, Vec_IntEntry(vFadds, 5*iFadd+3)) == -1 );
617             Vec_IntWriteEntry( vMap2Chain, Vec_IntEntry(vFadds, 5*iFadd+3), i );
618         }
619         //printf( "Chain %d: setting CARRY (obj %d)\n", i, Vec_IntEntry(vFadds, 5*iFadd+4) );
620         assert( Vec_IntEntry(vMap2Chain, Vec_IntEntry(vFadds, 5*iFadd+4)) == -1 );
621         Vec_IntWriteEntry( vMap2Chain, Vec_IntEntry(vFadds, 5*iFadd+4), i );
622     }
623     return vMap2Chain;
624 }
625 
626 /**Function*************************************************************
627 
628   Synopsis    [Derive GIA with boxes containing adder-chains.]
629 
630   Description []
631 
632   SideEffects []
633 
634   SeeAlso     []
635 
636 ***********************************************************************/
Gia_ManCollectTruthTables(Gia_Man_t * p,Vec_Int_t * vFadds)637 Vec_Int_t * Gia_ManCollectTruthTables( Gia_Man_t * p, Vec_Int_t * vFadds )
638 {
639     int i, k, Type, Truth, pCut[4] = {3};
640     Vec_Int_t * vTruths = Vec_IntAlloc( 2*Vec_IntSize(vFadds)/5 );
641     Gia_ManCleanValue( p );
642     Dtc_ForEachFadd( vFadds, i )
643     {
644         for ( k = 0; k < 3; k++ )
645             pCut[k+1] = Vec_IntEntry( vFadds, 5*i+k );
646         Type = Dtc_ObjComputeTruth( p, Vec_IntEntry(vFadds, 5*i+3), pCut, &Truth );
647         assert( Type == 1 );
648         Vec_IntPush( vTruths, Truth );
649         Type = Dtc_ObjComputeTruth( p, Vec_IntEntry(vFadds, 5*i+4), pCut, &Truth );
650         assert( Type == 2 );
651         Vec_IntPush( vTruths, Truth );
652     }
653     return vTruths;
654 }
Gia_ManGenerateDelayTableFloat(int nIns,int nOuts)655 float * Gia_ManGenerateDelayTableFloat( int nIns, int nOuts )
656 {
657     int i, Total = nIns * nOuts;
658     float * pDelayTable = ABC_ALLOC( float, Total + 3 );
659     pDelayTable[0] = 0;
660     pDelayTable[1] = nIns;
661     pDelayTable[2] = nOuts;
662     for ( i = 0; i < Total; i++ )
663         pDelayTable[i+3] = 1;
664     pDelayTable[i+3 - nIns] = -ABC_INFINITY;
665     return pDelayTable;
666 }
Gia_ManGenerateTim(int nPis,int nPos,int nBoxes,int nIns,int nOuts)667 Tim_Man_t * Gia_ManGenerateTim( int nPis, int nPos, int nBoxes, int nIns, int nOuts )
668 {
669     Tim_Man_t * pMan;
670     int i, curPi, curPo;
671     Vec_Ptr_t * vDelayTables = Vec_PtrAlloc( 1 );
672     Vec_PtrPush( vDelayTables, Gia_ManGenerateDelayTableFloat(nIns, nOuts) );
673     pMan = Tim_ManStart( nPis + nOuts * nBoxes, nPos + nIns * nBoxes );
674     Tim_ManSetDelayTables( pMan, vDelayTables );
675     curPi = nPis;
676     curPo = 0;
677     for ( i = 0; i < nBoxes; i++ )
678     {
679         Tim_ManCreateBox( pMan, curPo, nIns, curPi, nOuts, 0, 0 );
680         curPi += nOuts;
681         curPo += nIns;
682     }
683     curPo += nPos;
684     assert( curPi == Tim_ManCiNum(pMan) );
685     assert( curPo == Tim_ManCoNum(pMan) );
686     //Tim_ManPrint( pMan );
687     return pMan;
688 }
Gia_ManGenerateExtraAig(int nBoxes,int nIns,int nOuts)689 Gia_Man_t * Gia_ManGenerateExtraAig( int nBoxes, int nIns, int nOuts )
690 {
691     Gia_Man_t * pNew = Gia_ManStart( nBoxes * 20 );
692     int i, k, pInLits[16], pOutLits[16];
693     assert( nIns < 16 && nOuts < 16 );
694     for ( i = 0; i < nIns; i++ )
695         pInLits[i] = Gia_ManAppendCi( pNew );
696     pOutLits[0] = Gia_ManAppendXor( pNew, Gia_ManAppendXor(pNew, pInLits[0], pInLits[1]), pInLits[2] );
697     pOutLits[1] = Gia_ManAppendMaj( pNew, pInLits[0], pInLits[1], pInLits[2] );
698     for ( i = 0; i < nBoxes; i++ )
699         for ( k = 0; k < nOuts; k++ )
700             Gia_ManAppendCo( pNew, pOutLits[k] );
701     return pNew;
702 }
Gia_ManDupFadd(Gia_Man_t * pNew,Gia_Man_t * p,Vec_Int_t * vChain,Vec_Int_t * vFadds,Vec_Int_t * vMap,Vec_Wec_t * vChains,Vec_Int_t * vMap2Chain,Vec_Int_t * vTruths)703 void Gia_ManDupFadd( Gia_Man_t * pNew, Gia_Man_t * p, Vec_Int_t * vChain, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Wec_t * vChains, Vec_Int_t * vMap2Chain, Vec_Int_t * vTruths )
704 {
705     extern void Gia_ManDupWithFaddBoxes_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Wec_t * vChains, Vec_Int_t * vMap2Chain, Vec_Int_t * vTruths );
706     int i, k, iFadd = -1, iCiLit, pLits[3];
707     Gia_Obj_t * pObj;
708     // construct FADD inputs
709     Vec_IntForEachEntry( vChain, iFadd, i )
710         for ( k = 0; k < 3; k++ )
711         {
712             if ( i && !k ) continue;
713             pObj = Gia_ManObj( p, Vec_IntEntry(vFadds, 5*iFadd+k) );
714             Gia_ManDupWithFaddBoxes_rec( pNew, p, pObj, vFadds, vMap, vChains, vMap2Chain, vTruths );
715         }
716     // construct boxes
717     iCiLit = 0;
718     Vec_IntForEachEntry( vChain, iFadd, i )
719     {
720         int iXorTruth = Vec_IntEntry( vTruths, 2*iFadd+0 );
721         int iMajTruth = Vec_IntEntry( vTruths, 2*iFadd+1 );
722         for ( k = 0; k < 3; k++ )
723         {
724             pObj = Gia_ManObj( p, Vec_IntEntry(vFadds, 5*iFadd+k) );
725             pLits[k] = (!k && iCiLit) ? iCiLit : pObj->Value;
726             assert( pLits[k] >= 0 );
727         }
728         // normalize truth table
729         //    if ( Truth == 0xE8 || Truth == 0xD4 || Truth == 0xB2 || Truth == 0x71 ||
730         //         Truth == 0x17 || Truth == 0x2B || Truth == 0x4D || Truth == 0x8E )
731         if ( iMajTruth == 0x4D )
732             pLits[0] = Abc_LitNot(pLits[0]), iMajTruth = 0x8E, iXorTruth = 0xFF & ~iXorTruth;
733         else if ( iMajTruth == 0xD4 )
734             pLits[0] = Abc_LitNot(pLits[0]), iMajTruth = 0xE8, iXorTruth = 0xFF & ~iXorTruth;
735         else if ( iMajTruth == 0x2B )
736             pLits[1] = Abc_LitNot(pLits[1]), iMajTruth = 0x8E, iXorTruth = 0xFF & ~iXorTruth;
737         else if ( iMajTruth == 0xB2 )
738             pLits[1] = Abc_LitNot(pLits[1]), iMajTruth = 0xE8, iXorTruth = 0xFF & ~iXorTruth;
739         if ( iMajTruth == 0x8E )
740             pLits[2] = Abc_LitNot(pLits[2]), iMajTruth = 0xE8, iXorTruth = 0xFF & ~iXorTruth;
741         else if ( iMajTruth == 0x71 )
742             pLits[2] = Abc_LitNot(pLits[2]), iMajTruth = 0x17, iXorTruth = 0xFF & ~iXorTruth;
743         else assert( iMajTruth == 0xE8 || iMajTruth == 0x17 );
744         // normalize carry-in
745         if ( Abc_LitIsCompl(pLits[0]) )
746         {
747             for ( k = 0; k < 3; k++ )
748                 pLits[k] = Abc_LitNot(pLits[k]);
749             iXorTruth = 0xFF & ~iXorTruth;
750             iMajTruth = 0xFF & ~iMajTruth;
751         }
752         // add COs
753         assert( !Abc_LitIsCompl(pLits[0]) );
754         for ( k = 0; k < 3; k++ )
755             Gia_ManAppendCo( pNew, pLits[k] );
756         // create CI
757         assert( iXorTruth == 0x96 || iXorTruth == 0x69 );
758         pObj = Gia_ManObj( p, Vec_IntEntry(vFadds, 5*iFadd+3) );
759         pObj->Value = Abc_LitNotCond( Gia_ManAppendCi(pNew), (int)(iXorTruth == 0x69) );
760         // create CI
761         assert( iMajTruth == 0xE8 || iMajTruth == 0x17 );
762         iCiLit = Abc_LitNotCond( Gia_ManAppendCi(pNew), (int)(iMajTruth == 0x17) );
763     }
764     // assign carry out
765     assert( iFadd == Vec_IntEntryLast(vChain) );
766     pObj = Gia_ManObj( p, Vec_IntEntry(vFadds, 5*iFadd+4) );
767     pObj->Value = iCiLit;
768 }
Gia_ManDupWithFaddBoxes_rec(Gia_Man_t * pNew,Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vFadds,Vec_Int_t * vMap,Vec_Wec_t * vChains,Vec_Int_t * vMap2Chain,Vec_Int_t * vTruths)769 void Gia_ManDupWithFaddBoxes_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vFadds, Vec_Int_t * vMap, Vec_Wec_t * vChains, Vec_Int_t * vMap2Chain, Vec_Int_t * vTruths )
770 {
771     int iChain;
772     if ( ~pObj->Value )
773         return;
774     assert( Gia_ObjIsAnd(pObj) );
775     iChain = Vec_IntEntry( vMap2Chain, Gia_ObjId(p, pObj) );
776 /*
777     assert( iChain == -1 );
778     if ( iChain >= 0 )
779     {
780         Gia_ManDupFadd( pNew, p, Vec_WecEntry(vChains, iChain), vFadds, vMap, vChains, vMap2Chain, vTruths );
781         assert( ~pObj->Value );
782         return;
783     }
784 */
785     Gia_ManDupWithFaddBoxes_rec( pNew, p, Gia_ObjFanin0(pObj), vFadds, vMap, vChains, vMap2Chain, vTruths );
786     Gia_ManDupWithFaddBoxes_rec( pNew, p, Gia_ObjFanin1(pObj), vFadds, vMap, vChains, vMap2Chain, vTruths );
787     pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
788 }
Gia_ManDupWithNaturalBoxes(Gia_Man_t * p,int nFaddMin,int fVerbose)789 Gia_Man_t * Gia_ManDupWithNaturalBoxes( Gia_Man_t * p, int nFaddMin, int fVerbose )
790 {
791     abctime clk = Abc_Clock();
792     Gia_Man_t * pNew;//, * pTemp;
793     Vec_Int_t * vFadds, * vMap, * vMap2Chain, * vTruths, * vChain;
794     Vec_Wec_t * vChains;
795     Gia_Obj_t * pObj;
796     int i, nBoxes;
797     if ( Gia_ManBoxNum(p) > 0 )
798     {
799         printf( "Currently natural carry-chains cannot be detected when boxes are present.\n" );
800         return NULL;
801     }
802     assert( Gia_ManBoxNum(p) == 0 );
803 
804     // detect FADDs
805     vFadds = Gia_ManDetectFullAdders( p, fVerbose, NULL );
806     assert( Vec_IntSize(vFadds) % 5 == 0 );
807     // map MAJ into its FADD
808     vMap = Gia_ManCreateMap( p, vFadds );
809     // for each FADD, find the longest chain and reorder its inputs
810     Gia_ManFindChains( p, vFadds, vMap );
811     // returns the set of topmost MAJ nodes
812     vChains = Gia_ManCollectTopmost( p, vFadds, vMap, nFaddMin );
813     if ( fVerbose )
814         Gia_ManPrintChains( p, vFadds, vMap, vChains );
815     if ( Vec_WecSize(vChains) == 0 )
816     {
817         Vec_IntFree( vFadds );
818         Vec_IntFree( vMap );
819         Vec_WecFree( vChains );
820         return Gia_ManDup( p );
821     }
822     // returns mapping of each MAJ into the topmost elements of its chain
823     vMap2Chain = Gia_ManFindMapping( p, vFadds, vMap, vChains );
824     // compute truth tables for FADDs
825     vTruths = Gia_ManCollectTruthTables( p, vFadds );
826     if ( fVerbose )
827         Abc_PrintTime( 1, "Carry-chain detection time", Abc_Clock() - clk );
828 
829     // duplicate
830     clk = Abc_Clock();
831     Gia_ManFillValue( p );
832     pNew = Gia_ManStart( Gia_ManObjNum(p) );
833     pNew->pName = Abc_UtilStrsav( p->pName );
834     pNew->pSpec = Abc_UtilStrsav( p->pSpec );
835     Gia_ManConst0(p)->Value = 0;
836     Gia_ManForEachCi( p, pObj, i )
837         pObj->Value = Gia_ManAppendCi( pNew );
838     Vec_WecForEachLevel( vChains, vChain, i )
839         Gia_ManDupFadd( pNew, p, vChain, vFadds, vMap, vChains, vMap2Chain, vTruths );
840     Gia_ManForEachCo( p, pObj, i )
841         Gia_ManDupWithFaddBoxes_rec( pNew, p, Gia_ObjFanin0(pObj), vFadds, vMap, vChains, vMap2Chain, vTruths );
842     Gia_ManForEachCo( p, pObj, i )
843         Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
844     Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
845     if ( Gia_ManRegNum(p) )
846     {
847         if ( fVerbose )
848             printf( "Warning: Sequential design is coverted into combinational one by adding white boxes.\n" );
849         pNew->nRegs = 0;
850     }
851     assert( !Gia_ManHasDangling(pNew) );
852 
853     // cleanup
854     Vec_IntFree( vFadds );
855     Vec_IntFree( vMap );
856     Vec_WecFree( vChains );
857     Vec_IntFree( vMap2Chain );
858     Vec_IntFree( vTruths );
859 
860     // other information
861     nBoxes = (Gia_ManCiNum(pNew) - Gia_ManCiNum(p)) / 2;
862     assert( nBoxes == (Gia_ManCoNum(pNew) - Gia_ManCoNum(p)) / 3 );
863     pNew->pManTime  = Gia_ManGenerateTim( Gia_ManCiNum(p), Gia_ManCoNum(p), nBoxes, 3, 2 );
864     pNew->pAigExtra = Gia_ManGenerateExtraAig( nBoxes, 3, 2 );
865 /*
866     // normalize
867     pNew = Gia_ManDupNormalize( pTemp = pNew, 0 );
868     pNew->pManTime  = pTemp->pManTime;  pTemp->pManTime  = NULL;
869     pNew->pAigExtra = pTemp->pAigExtra; pTemp->pAigExtra = NULL;
870     Gia_ManStop( pTemp );
871 */
872     //pNew = Gia_ManDupCollapse( pTemp = pNew, pNew->pAigExtra, NULL );
873     //Gia_ManStop( pTemp );
874 
875     //Gia_ManIllustrateBoxes( pNew );
876     if ( fVerbose )
877         Abc_PrintTime( 1, "AIG with boxes construction time", Abc_Clock() - clk );
878     return pNew;
879 }
880 
881 /**Function*************************************************************
882 
883   Synopsis    [Converting AIG with annotated carry-chains into AIG with boxes.]
884 
885   Description [Assumes that annotations are pObj->fMark0 or pObj->fMark1.
886   Only one of these can be set to 1.  If fMark0 (fMark1) is set to 1,
887   the first (second) input of an AND-gate is chained.]
888 
889   SideEffects []
890 
891   SeeAlso     []
892 
893 ***********************************************************************/
Gia_ObjFanin0CopyCarry(Vec_Int_t * vCarries,Gia_Obj_t * pObj,int Id)894 int Gia_ObjFanin0CopyCarry( Vec_Int_t * vCarries, Gia_Obj_t * pObj, int Id )
895 {
896     if ( vCarries == NULL || Vec_IntEntry(vCarries, Gia_ObjFaninId0(pObj, Id)) == -1 )
897         return Gia_ObjFanin0Copy(pObj);
898     return Abc_LitNotCond( Vec_IntEntry(vCarries, Gia_ObjFaninId0(pObj, Id)), Gia_ObjFaninC0(pObj) );
899 }
Gia_ObjFanin1CopyCarry(Vec_Int_t * vCarries,Gia_Obj_t * pObj,int Id)900 int Gia_ObjFanin1CopyCarry( Vec_Int_t * vCarries, Gia_Obj_t * pObj, int Id )
901 {
902     if ( vCarries == NULL || Vec_IntEntry(vCarries, Gia_ObjFaninId1(pObj, Id)) == -1 )
903         return Gia_ObjFanin1Copy(pObj);
904     return Abc_LitNotCond( Vec_IntEntry(vCarries, Gia_ObjFaninId1(pObj, Id)), Gia_ObjFaninC1(pObj) );
905 }
Gia_ManDupWithArtificalFaddBoxes(Gia_Man_t * p,int fUseFanout,int fXorTrick)906 Gia_Man_t * Gia_ManDupWithArtificalFaddBoxes( Gia_Man_t * p, int fUseFanout, int fXorTrick )
907 {
908     Gia_Man_t * pNew;
909     Gia_Obj_t * pObj;
910     int nBoxes = Gia_ManBoxNum(p);
911     int i, nRealPis, nRealPos;
912     Vec_Int_t * vCarries = NULL;
913     // make sure two chains do not overlap
914     Gia_ManCleanPhase( p );
915     Gia_ManForEachCi( p, pObj, i )
916         assert( !pObj->fMark0 && !pObj->fMark1 );
917     Gia_ManForEachCo( p, pObj, i )
918         assert( !pObj->fMark0 && !pObj->fMark1 );
919     Gia_ManForEachAnd( p, pObj, i )
920     {
921         assert( !pObj->fMark0 || !pObj->fMark1 );
922         if ( pObj->fMark0 )
923         {
924             assert( Gia_ObjFanin0(pObj)->fPhase == 0 );
925             Gia_ObjFanin0(pObj)->fPhase = 1;
926         }
927         if ( pObj->fMark1 )
928         {
929             assert( Gia_ObjFanin1(pObj)->fPhase == 0 );
930             Gia_ObjFanin1(pObj)->fPhase = 1;
931         }
932     }
933     // create mapping for carry-chains
934     if ( !fUseFanout )
935         vCarries = Vec_IntStartFull( Gia_ManObjNum(p) );
936     // create references and discount carries
937     if ( vCarries )
938     {
939         Gia_ManCreateRefs( p );
940         Gia_ManForEachAnd( p, pObj, i )
941             if ( pObj->fMark0 )
942                 Gia_ObjRefFanin0Dec( p, pObj );
943             else if ( pObj->fMark1 )
944                 Gia_ObjRefFanin1Dec( p, pObj );
945     }
946     // if AIG already has (natural) FADD boxes, it should not un-normalized
947     Gia_ManFillValue( p );
948     pNew = Gia_ManStart( Gia_ManObjNum(p) );
949     pNew->pName = Abc_UtilStrsav( p->pName );
950     pNew->pSpec = Abc_UtilStrsav( p->pSpec );
951     Gia_ManConst0(p)->Value = 0;
952     Gia_ManForEachObj1( p, pObj, i )
953     {
954         if ( Gia_ObjIsCi(pObj) )
955             pObj->Value = Gia_ManAppendCi( pNew );
956         else if ( Gia_ObjIsCo(pObj) )
957             pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
958         else if ( !pObj->fMark0 && !pObj->fMark1 ) // AND-gate
959             pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
960         else // AND-gate with chain
961         {
962             int iCiLit, iOtherLit, iLit0, iLit1, iLit2, iXorLit;
963             assert( pObj->fMark0 != pObj->fMark1 );
964             iCiLit    = pObj->fMark0 ? Gia_ObjFanin0CopyCarry(vCarries, pObj, i) : Gia_ObjFanin1CopyCarry(vCarries, pObj, i);
965             iOtherLit = pObj->fMark0 ? Gia_ObjFanin1Copy(pObj) : Gia_ObjFanin0Copy(pObj);
966             assert( iCiLit >= 0 && iOtherLit >= 0 );
967             iLit0 = Abc_LitNotCond( iCiLit,    Abc_LitIsCompl(iCiLit) );
968             iLit1 = Abc_LitNotCond( iOtherLit, Abc_LitIsCompl(iCiLit) );
969             iLit2 = Abc_LitNotCond( 0,         Abc_LitIsCompl(iCiLit) );
970             // add COs
971             assert( !Abc_LitIsCompl(iLit0) );
972             Gia_ManAppendCo( pNew, iLit0 );
973             Gia_ManAppendCo( pNew, iLit1 );
974             Gia_ManAppendCo( pNew, iLit2 );
975             // add CI (unused sum bit)
976             iXorLit = Gia_ManAppendCi(pNew);
977             // add CI (carry bit)
978             pObj->Value = Abc_LitNotCond( Gia_ManAppendCi(pNew), Abc_LitIsCompl(iCiLit) );
979             if ( vCarries && pObj->fPhase )
980             {
981                 Vec_IntWriteEntry( vCarries, i, pObj->Value );
982                 if ( Gia_ObjRefNum(p, pObj) > 0 )
983                 {
984                     if ( fXorTrick )
985                         pObj->Value = Gia_ManAppendAnd( pNew, Abc_LitNotCond(iXorLit, !Abc_LitIsCompl(iCiLit)), iOtherLit );
986                     else
987                         pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
988                 }
989             }
990             nBoxes++;
991         }
992     }
993     Gia_ManCleanPhase( p );
994     Vec_IntFreeP( &vCarries );
995     ABC_FREE( p->pRefs );
996     assert( !Gia_ManHasDangling(pNew) );
997     // other information
998 //    nBoxes += (Gia_ManCiNum(pNew) - Gia_ManCiNum(p)) / 2;
999 //    assert( nBoxes == Gia_ManBoxNum(p) + (Gia_ManCoNum(pNew) - Gia_ManCoNum(p)) / 3 );
1000     nRealPis = Gia_ManBoxNum(p) ? Tim_ManPiNum((Tim_Man_t *)p->pManTime) : Gia_ManCiNum(p);
1001     nRealPos = Gia_ManBoxNum(p) ? Tim_ManPoNum((Tim_Man_t *)p->pManTime) : Gia_ManCoNum(p);
1002     pNew->pManTime  = Gia_ManGenerateTim( nRealPis, nRealPos, nBoxes, 3, 2 );
1003     pNew->pAigExtra = Gia_ManGenerateExtraAig( nBoxes, 3, 2 );
1004     // optionally normalize the AIG
1005     return pNew;
1006 }
Gia_ManDupWithArtificalFaddBoxesTest(Gia_Man_t * p)1007 Gia_Man_t * Gia_ManDupWithArtificalFaddBoxesTest( Gia_Man_t * p )
1008 {
1009     Gia_Man_t * pNew;
1010     Gia_Obj_t * pObj;
1011     int i;
1012     // label some and-gates
1013     Gia_ManCleanMark01( p );
1014     Gia_ManForEachAnd( p, pObj, i )
1015     {
1016         pObj->fMark0 = i % 5;
1017         pObj->fMark1 = i % 7;
1018         if ( pObj->fMark0 && pObj->fMark1 )
1019             pObj->fMark0 = pObj->fMark1 = 0;
1020     }
1021 
1022     // output new AIG
1023     pNew = Gia_ManDupWithArtificalFaddBoxes( p, 0, 0 );
1024     Gia_ManCleanMark01( p );
1025     return pNew;
1026 }
1027 
1028 /**Function*************************************************************
1029 
1030   Synopsis    [Adds artificial carry chains to the manager.]
1031 
1032   Description []
1033 
1034   SideEffects []
1035 
1036   SeeAlso     []
1037 
1038 ***********************************************************************/
1039 // computes AIG delay information when boxes are used
Gia_ManFindAnnotatedDelay(Gia_Man_t * p,int DelayC,int * pnBoxes,int fIgnoreBoxDelays)1040 int Gia_ManFindAnnotatedDelay( Gia_Man_t * p, int DelayC, int * pnBoxes, int fIgnoreBoxDelays )
1041 {
1042     Gia_Obj_t * pObj;
1043     int nRealPis = Gia_ManBoxNum(p) ? Tim_ManPiNum((Tim_Man_t *)p->pManTime) : Gia_ManCiNum(p);
1044     int * pDelays = Vec_IntArray(p->vLevels);
1045     int i, k, iBox, iBoxOutId, Delay, Delay0, Delay1, DelayMax = 0, nBoxes = 0;
1046     Vec_IntFill( p->vLevels, Gia_ManObjNum(p), 0 );
1047     Gia_ManForEachObj1( p, pObj, i )
1048     {
1049         if ( Gia_ObjIsCi(pObj) )
1050         {
1051             if ( fIgnoreBoxDelays )
1052                 continue;
1053             // check if it is real PI
1054             iBoxOutId = Gia_ObjCioId(pObj) - nRealPis;
1055             if ( iBoxOutId < 0 )
1056                 continue;
1057             // if it is a box output, find box number
1058             iBox = iBoxOutId / 2;
1059             assert( iBox < Gia_ManBoxNum(p) );
1060             // check find the maximum delay of the box inputs
1061             Delay = 0;
1062             for ( k = 0; k < 3; k++ )
1063             {
1064                 int Id = Gia_ObjId( p, Gia_ManCo(p, iBox*3+k) );
1065                 assert( Id < i );
1066                 Delay = Abc_MaxInt( Delay, pDelays[Id] );
1067             }
1068             // consider outputs
1069             if ( iBoxOutId & 1 ) // carry output
1070                 Delay += DelayC;
1071             else // sum output
1072                 Delay += 100;
1073             pDelays[i] = Delay;
1074             continue;
1075         }
1076         if ( Gia_ObjIsCo(pObj) )
1077         {
1078             pDelays[i] = pDelays[Gia_ObjFaninId0(pObj, i)];
1079             DelayMax = Abc_MaxInt( DelayMax, pDelays[i] );
1080             continue;
1081         }
1082         assert( !pObj->fMark0 || !pObj->fMark1 );
1083         Delay0 = pDelays[Gia_ObjFaninId0(pObj, i)];
1084         Delay1 = pDelays[Gia_ObjFaninId1(pObj, i)];
1085         if ( pObj->fMark0 )
1086         {
1087             Delay = Abc_MaxInt( Delay0 + DelayC, Delay1 + 100 );
1088             nBoxes++;
1089         }
1090         else if ( pObj->fMark1 )
1091         {
1092             Delay = Abc_MaxInt( Delay1 + DelayC, Delay0 + 100 );
1093             nBoxes++;
1094         }
1095         else
1096             Delay = Abc_MaxInt( Delay0 + 100, Delay1 + 100 );
1097         pDelays[i] = Delay;
1098     }
1099     if ( pnBoxes )
1100         *pnBoxes = nBoxes;
1101     return DelayMax;
1102 }
1103 // check if the object is already used in some chain
Gia_ObjIsUsed(Gia_Obj_t * pObj)1104 static inline int Gia_ObjIsUsed( Gia_Obj_t * pObj )
1105 {
1106     return pObj->fMark0 || pObj->fMark1 || pObj->fPhase;
1107 }
1108 // finds internal node that can begin a new chain
Gia_ManFindChainStart(Gia_Man_t * p)1109 int Gia_ManFindChainStart( Gia_Man_t * p )
1110 {
1111     Gia_Obj_t * pObj;
1112     int * pDelays = Vec_IntArray(p->vLevels);
1113     int i, iMax = -1, DelayMax = 0;
1114     Gia_ManForEachAnd( p, pObj, i )
1115     {
1116         if ( Gia_ObjIsUsed(pObj) )
1117             continue;
1118         if ( DelayMax > pDelays[i] )
1119             continue;
1120         DelayMax = pDelays[i];
1121         iMax = i;
1122     }
1123     return iMax;
1124 }
1125 // finds a sequence of internal nodes that creates a new chain
Gia_ManFindPath(Gia_Man_t * p,int DelayC,int nPathMin,int nPathMax,Vec_Int_t * vPath)1126 int Gia_ManFindPath( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, Vec_Int_t * vPath )
1127 {
1128     Gia_Obj_t * pObj, * pFanin0, * pFanin1;
1129     int * pDelays = Vec_IntArray(p->vLevels);
1130     int i, iLit, iMax = Gia_ManFindChainStart( p );
1131     if ( iMax == -1 )
1132         return -1;
1133     Vec_IntClear( vPath );
1134     pObj = Gia_ManObj(p, iMax);
1135     assert( Gia_ObjIsAnd(pObj) );
1136     while ( Gia_ObjIsAnd(pObj) )
1137     {
1138         assert( !Gia_ObjIsUsed(pObj) );
1139         pFanin0 = Gia_ObjFanin0(pObj);
1140         pFanin1 = Gia_ObjFanin1(pObj);
1141         if ( Gia_ObjIsUsed(pFanin0) && Gia_ObjIsUsed(pFanin1) )
1142             break;
1143         if ( Gia_ObjIsUsed(pFanin0) )
1144         {
1145             Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 1) );
1146             pObj = pFanin1;
1147         }
1148         else if ( Gia_ObjIsUsed(pFanin1) )
1149         {
1150             Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 0) );
1151             pObj = pFanin0;
1152         }
1153         else
1154         {
1155             if ( pDelays[Gia_ObjId(p, pFanin1)] > pDelays[Gia_ObjId(p, pFanin0)] )
1156             {
1157                 Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 1) );
1158                 pObj = pFanin1;
1159             }
1160             else
1161             {
1162                 Vec_IntPush( vPath, Abc_Var2Lit(Gia_ObjId(p, pObj), 0) );
1163                 pObj = pFanin0;
1164             }
1165         }
1166     }
1167     if ( Vec_IntSize(vPath) < nPathMin )
1168     {
1169         Gia_ManObj(p, iMax)->fPhase = 1;
1170         return 0;
1171     }
1172     // label nodes
1173     if ( Vec_IntSize(vPath) > nPathMax )
1174         Vec_IntShrink( vPath, nPathMax );
1175     Vec_IntForEachEntry( vPath, iLit, i )
1176     {
1177         pObj = Gia_ManObj( p, Abc_Lit2Var(iLit) );
1178         if ( Abc_LitIsCompl(iLit) )
1179         {
1180             assert( pObj->fMark1 == 0 );
1181             pObj->fMark1 = 1;
1182             assert( Gia_ObjFanin1(pObj)->fPhase == 0 );
1183             Gia_ObjFanin1(pObj)->fPhase = 1;
1184         }
1185         else
1186         {
1187             assert( pObj->fMark0 == 0 );
1188             pObj->fMark0 = 1;
1189             assert( Gia_ObjFanin0(pObj)->fPhase == 0 );
1190             Gia_ObjFanin0(pObj)->fPhase = 1;
1191         }
1192     }
1193     return Vec_IntSize(vPath);
1194 }
1195 // iteratively create the given number of chains
Gia_ManIteratePaths(Gia_Man_t * p,int DelayC,int nPathMin,int nPathMax,int nPathLimit,int fIgnoreBoxDelays,int fVerbose)1196 int Gia_ManIteratePaths( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, int nPathLimit, int fIgnoreBoxDelays, int fVerbose )
1197 {
1198     Gia_Obj_t * pObj;
1199     Vec_Int_t * vPath = Vec_IntAlloc( 100 );
1200     int i, RetValue, nBoxes, MaxDelay, nPaths = 0;
1201     assert( p->vLevels == NULL );
1202     p->vLevels = Vec_IntStart( Gia_ManObjNum(p) );
1203     Gia_ManCleanMark01( p );
1204     Gia_ManCleanPhase( p );
1205     Gia_ManForEachCi( p, pObj, i )
1206         pObj->fPhase = 1;
1207     if ( fVerbose )
1208         printf( "Running path detection: BoxDelay = %d, PathMin = %d, PathMax = %d, PathLimit = %d.\n", DelayC, nPathMin, nPathMax, nPathLimit );
1209     for ( i = 0; i < nPathLimit; i++ )
1210     {
1211         MaxDelay = Gia_ManFindAnnotatedDelay( p, DelayC, &nBoxes, fIgnoreBoxDelays );
1212         RetValue = Gia_ManFindPath( p, DelayC, nPathMin, nPathMax, vPath );
1213         if ( RetValue == -1 )
1214             break;
1215         nPaths += (RetValue > 0);
1216         if ( fVerbose )
1217             printf( "Iter %5d : Paths = %2d. Boxes = %2d. Total boxes = %6d.  Max delay = %5d.\n", i, nPaths, RetValue, nBoxes, MaxDelay );
1218     }
1219     Vec_IntFree( vPath );
1220     Vec_IntFreeP( &p->vLevels );
1221     Gia_ManCleanPhase( p );
1222     return 1;
1223 }
1224 // annotate artificial chains and then put them into boxes
Gia_ManDupWithArtificialBoxes(Gia_Man_t * p,int DelayC,int nPathMin,int nPathMax,int nPathLimit,int fUseFanout,int fXorTrick,int fIgnoreBoxDelays,int fVerbose)1225 Gia_Man_t * Gia_ManDupWithArtificialBoxes( Gia_Man_t * p, int DelayC, int nPathMin, int nPathMax, int nPathLimit, int fUseFanout, int fXorTrick, int fIgnoreBoxDelays, int fVerbose )
1226 {
1227     Gia_Man_t * pNew;
1228 /*
1229     if ( Gia_ManBoxNum(p) > 0 )
1230     {
1231         printf( "Currently artifical carry-chains cannot be detected when natural ones are present.\n" );
1232         return NULL;
1233     }
1234 */
1235     Gia_ManIteratePaths( p, DelayC, nPathMin, nPathMax, nPathLimit, fIgnoreBoxDelays, fVerbose );
1236     pNew = Gia_ManDupWithArtificalFaddBoxes( p, fUseFanout, fXorTrick );
1237     Gia_ManCleanMark01( p );
1238     return pNew;
1239 }
1240 
1241 ////////////////////////////////////////////////////////////////////////
1242 ///                       END OF FILE                                ///
1243 ////////////////////////////////////////////////////////////////////////
1244 
1245 
1246 ABC_NAMESPACE_IMPL_END
1247 
1248