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