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