abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaSpeedup.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [gia.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Scalable AIG package.]
8 
9  Synopsis []
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "gia.h"
22 #include "map/if/if.h"
23 
25 
26 
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30 
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34 
35 /**Function*************************************************************
36 
37  Synopsis [Sorts the pins in the decreasing order of delays.]
38 
39  Description []
40 
41  SideEffects []
42 
43  SeeAlso []
44 
45 ***********************************************************************/
46 void Gia_LutDelayTraceSortPins( Gia_Man_t * p, int iObj, int * pPinPerm, float * pPinDelays )
47 {
48  int iFanin, i, j, best_i, temp;
49  assert( Gia_ObjIsLut(p, iObj) );
50  // start the trivial permutation and collect pin delays
51  Gia_LutForEachFanin( p, iObj, iFanin, i )
52  {
53  pPinPerm[i] = i;
54  pPinDelays[i] = Gia_ObjTimeArrival(p, iFanin);
55  }
56  // selection sort the pins in the decreasible order of delays
57  // this order will match the increasing order of LUT input pins
58  for ( i = 0; i < Gia_ObjLutSize(p, iObj)-1; i++ )
59  {
60  best_i = i;
61  for ( j = i+1; j < Gia_ObjLutSize(p, iObj); j++ )
62  if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
63  best_i = j;
64  if ( best_i == i )
65  continue;
66  temp = pPinPerm[i];
67  pPinPerm[i] = pPinPerm[best_i];
68  pPinPerm[best_i] = temp;
69  }
70  // verify
71  assert( Gia_ObjLutSize(p, iObj) == 0 || pPinPerm[0] < Gia_ObjLutSize(p, iObj) );
72  for ( i = 1; i < Gia_ObjLutSize(p, iObj); i++ )
73  {
74  assert( pPinPerm[i] < Gia_ObjLutSize(p, iObj) );
75  assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
76  }
77 }
78 
79 /**Function*************************************************************
80 
81  Synopsis [Sorts the pins in the decreasing order of delays.]
82 
83  Description []
84 
85  SideEffects []
86 
87  SeeAlso []
88 
89 ***********************************************************************/
90 int Gia_LutWhereIsPin( Gia_Man_t * p, int iFanout, int iFanin, int * pPinPerm )
91 {
92  int i;
93  for ( i = 0; i < Gia_ObjLutSize(p, iFanout); i++ )
94  if ( Gia_ObjLutFanin(p, iFanout, pPinPerm[i]) == iFanin )
95  return i;
96  return -1;
97 }
98 
99 /**Function*************************************************************
100 
101  Synopsis [Computes the arrival times for the given object.]
102 
103  Description []
104 
105  SideEffects []
106 
107  SeeAlso []
108 
109 ***********************************************************************/
110 float Gia_ObjComputeArrival( Gia_Man_t * p, int iObj, int fUseSorting )
111 {
112  If_LibLut_t * pLutLib = (If_LibLut_t *)p->pLutLib;
113  Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
114  int k, iFanin, pPinPerm[32];
115  float pPinDelays[32];
116  float tArrival, * pDelays;
117  if ( Gia_ObjIsCi(pObj) )
118  return Gia_ObjTimeArrival(p, iObj);
119  if ( Gia_ObjIsCo(pObj) )
120  return Gia_ObjTimeArrival(p, Gia_ObjFaninId0p(p, pObj) );
121  assert( Gia_ObjIsLut(p, iObj) );
122  tArrival = -TIM_ETERNITY;
123  if ( pLutLib == NULL )
124  {
125  Gia_LutForEachFanin( p, iObj, iFanin, k )
126  if ( tArrival < Gia_ObjTimeArrival(p, iFanin) + 1.0 )
127  tArrival = Gia_ObjTimeArrival(p, iFanin) + 1.0;
128  }
129  else if ( !pLutLib->fVarPinDelays )
130  {
131  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
132  Gia_LutForEachFanin( p, iObj, iFanin, k )
133  if ( tArrival < Gia_ObjTimeArrival(p, iFanin) + pDelays[0] )
134  tArrival = Gia_ObjTimeArrival(p, iFanin) + pDelays[0];
135  }
136  else
137  {
138  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
139  if ( fUseSorting )
140  {
141  Gia_LutDelayTraceSortPins( p, iObj, pPinPerm, pPinDelays );
142  Gia_LutForEachFanin( p, iObj, iFanin, k )
143  if ( tArrival < Gia_ObjTimeArrival( p, Gia_ObjLutFanin(p,iObj,pPinPerm[k])) + pDelays[k] )
144  tArrival = Gia_ObjTimeArrival( p, Gia_ObjLutFanin(p,iObj,pPinPerm[k])) + pDelays[k];
145  }
146  else
147  {
148  Gia_LutForEachFanin( p, iObj, iFanin, k )
149  if ( tArrival < Gia_ObjTimeArrival(p, iFanin) + pDelays[k] )
150  tArrival = Gia_ObjTimeArrival(p, iFanin) + pDelays[k];
151  }
152  }
153  if ( Gia_ObjLutSize(p, iObj) == 0 )
154  tArrival = 0.0;
155  return tArrival;
156 }
157 
158 
159 /**Function*************************************************************
160 
161  Synopsis [Propagates the required times through the given node.]
162 
163  Description []
164 
165  SideEffects []
166 
167  SeeAlso []
168 
169 ***********************************************************************/
170 float Gia_ObjPropagateRequired( Gia_Man_t * p, int iObj, int fUseSorting )
171 {
172  If_LibLut_t * pLutLib = (If_LibLut_t *)p->pLutLib;
173  int k, iFanin, pPinPerm[32];
174  float pPinDelays[32];
175  float tRequired = 0.0; // Suppress "might be used uninitialized"
176  float * pDelays;
177  assert( Gia_ObjIsLut(p, iObj) );
178  if ( pLutLib == NULL )
179  {
180  tRequired = Gia_ObjTimeRequired( p, iObj) - (float)1.0;
181  Gia_LutForEachFanin( p, iObj, iFanin, k )
182  if ( Gia_ObjTimeRequired(p, iFanin) > tRequired )
183  Gia_ObjSetTimeRequired( p, iFanin, tRequired );
184  }
185  else if ( !pLutLib->fVarPinDelays )
186  {
187  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
188  tRequired = Gia_ObjTimeRequired(p, iObj) - pDelays[0];
189  Gia_LutForEachFanin( p, iObj, iFanin, k )
190  if ( Gia_ObjTimeRequired(p, iFanin) > tRequired )
191  Gia_ObjSetTimeRequired( p, iFanin, tRequired );
192  }
193  else
194  {
195  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
196  if ( fUseSorting )
197  {
198  Gia_LutDelayTraceSortPins( p, iObj, pPinPerm, pPinDelays );
199  Gia_LutForEachFanin( p, iObj, iFanin, k )
200  {
201  tRequired = Gia_ObjTimeRequired( p, iObj) - pDelays[k];
202  if ( Gia_ObjTimeRequired( p, Gia_ObjLutFanin(p, iObj,pPinPerm[k])) > tRequired )
203  Gia_ObjSetTimeRequired( p, Gia_ObjLutFanin(p, iObj,pPinPerm[k]), tRequired );
204  }
205  }
206  else
207  {
208  Gia_LutForEachFanin( p, iObj, iFanin, k )
209  {
210  tRequired = Gia_ObjTimeRequired(p, iObj) - pDelays[k];
211  if ( Gia_ObjTimeRequired(p, iFanin) > tRequired )
212  Gia_ObjSetTimeRequired( p, iFanin, tRequired );
213  }
214  }
215  }
216  return tRequired;
217 }
218 
219 /**Function*************************************************************
220 
221  Synopsis [Computes the delay trace of the given network.]
222 
223  Description []
224 
225  SideEffects []
226 
227  SeeAlso []
228 
229 ***********************************************************************/
231 {
232  int fUseSorting = 1;
233  If_LibLut_t * pLutLib = (If_LibLut_t *)p->pLutLib;
234  Vec_Int_t * vObjs;
235  Gia_Obj_t * pObj;
236  float tArrival, tArrivalCur, tRequired, tSlack;
237  int i, iObj;
238 
239  // get the library
240  if ( pLutLib && pLutLib->LutMax < Gia_ManLutSizeMax(p) )
241  {
242  printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
243  pLutLib->LutMax, Gia_ManLutSizeMax(p) );
244  return -TIM_ETERNITY;
245  }
246 
247  // initialize the arrival times
248  Gia_ManTimeStart( p );
249 
250  // propagate arrival times
251  if ( p->pManTime )
253  Gia_ManForEachObj( p, pObj, i )
254  {
255  if ( !Gia_ObjIsCi(pObj) && !Gia_ObjIsCo(pObj) && !Gia_ObjIsLut(p, i) )
256  continue;
257  tArrival = Gia_ObjComputeArrival( p, i, fUseSorting );
258  if ( Gia_ObjIsCi(pObj) && p->pManTime )
259  {
260  tArrival = Tim_ManGetCiArrival( (Tim_Man_t *)p->pManTime, Gia_ObjCioId(pObj) );
261 //printf( "%.3f ", tArrival );
262  }
263  if ( Gia_ObjIsCo(pObj) && p->pManTime )
264  Tim_ManSetCoArrival( (Tim_Man_t *)p->pManTime, Gia_ObjCioId(pObj), tArrival );
265  Gia_ObjSetTimeArrival( p, i, tArrival );
266  }
267 
268  // get the latest arrival times
269  tArrival = -TIM_ETERNITY;
270  Gia_ManForEachCo( p, pObj, i )
271  {
272  tArrivalCur = Gia_ObjTimeArrivalObj( p, Gia_ObjFanin0(pObj) );
273  Gia_ObjSetTimeArrival( p, Gia_ObjId(p,pObj), tArrivalCur );
274  if ( tArrival < tArrivalCur )
275  tArrival = tArrivalCur;
276  }
277 
278  // initialize the required times
279  if ( p->pManTime )
280  {
282  Tim_ManInitPoRequiredAll( (Tim_Man_t *)p->pManTime, tArrival );
283  }
284  else
285  {
286  Gia_ManForEachCo( p, pObj, i )
287  Gia_ObjSetTimeRequiredObj( p, pObj, tArrival );
288  }
289 
290  // propagate the required times
291  vObjs = Gia_ManOrderReverse( p );
292  Vec_IntForEachEntry( vObjs, iObj, i )
293  {
294  pObj = Gia_ManObj(p, iObj);
295  if ( Gia_ObjIsLut(p, iObj) )
296  {
297  Gia_ObjPropagateRequired( p, iObj, fUseSorting );
298  }
299  else if ( Gia_ObjIsCi(pObj) )
300  {
301  if ( p->pManTime )
303  }
304  else if ( Gia_ObjIsCo(pObj) )
305  {
306  if ( p->pManTime )
307  {
308  tRequired = Tim_ManGetCoRequired( (Tim_Man_t *)p->pManTime, Gia_ObjCioId(pObj) );
309  Gia_ObjSetTimeRequired( p, iObj, tRequired );
310  }
311  if ( Gia_ObjTimeRequired(p, Gia_ObjFaninId0p(p, pObj)) > Gia_ObjTimeRequired(p, iObj) )
313  }
314 
315  // set slack for this object
316  tSlack = Gia_ObjTimeRequired(p, iObj) - Gia_ObjTimeArrival(p, iObj);
317  assert( tSlack + 0.01 > 0.0 );
318  Gia_ObjSetTimeSlack( p, iObj, tSlack < 0.0 ? 0.0 : tSlack );
319  }
320  Vec_IntFree( vObjs );
321  return tArrival;
322 }
323 
324 #if 0
325 
326 /**Function*************************************************************
327 
328  Synopsis [Computes the required times for the given node.]
329 
330  Description []
331 
332  SideEffects []
333 
334  SeeAlso []
335 
336 ***********************************************************************/
337 float Gia_ObjComputeRequired( Gia_Man_t * p, int iObj, int fUseSorting )
338 {
339  If_LibLut_t * pLutLib = p->pLutLib;
340  int pPinPerm[32];
341  float pPinDelays[32];
342  Gia_Obj_t * pFanout;
343  float tRequired, tDelay, * pDelays;
344  int k, iFanin;
345  if ( Gia_ObjIsCo(iObj) )
346  return Gia_ObjTimeRequired( p, iObj);
347  tRequired = TIM_ETERNITY;
348  if ( pLutLib == NULL )
349  {
350  Gia_ObjForEachFanout( iObj, pFanout, k )
351  {
352  tDelay = Gia_ObjIsCo(pFanout)? 0.0 : 1.0;
353  if ( tRequired > Gia_ObjTimeRequired( p, pFanout) - tDelay )
354  tRequired = Gia_ObjTimeRequired( p, pFanout) - tDelay;
355  }
356  }
357  else if ( !pLutLib->fVarPinDelays )
358  {
359  Gia_ObjForEachFanout( iObj, pFanout, k )
360  {
361  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, pFanout)];
362  tDelay = Gia_ObjIsCo(pFanout)? 0.0 : pDelays[0];
363  if ( tRequired > Gia_ObjTimeRequired( p, pFanout) - tDelay )
364  tRequired = Gia_ObjTimeRequired( p, pFanout) - tDelay;
365  }
366  }
367  else
368  {
369  if ( fUseSorting )
370  {
371  Gia_ObjForEachFanout( iObj, pFanout, k )
372  {
373  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, pFanout)];
374  Gia_LutDelayTraceSortPins( p, pFanout, pPinPerm, pPinDelays );
375  iFanin = Gia_LutWhereIsPin( p, pFanout, iObj, pPinPerm );
376  assert( Gia_ObjLutFanin( p, pFanout, pPinPerm[iFanin]) == iObj );
377  tDelay = Gia_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
378  if ( tRequired > Gia_ObjTimeRequired( p, pFanout) - tDelay )
379  tRequired = Gia_ObjTimeRequired( p, pFanout) - tDelay;
380  }
381  }
382  else
383  {
384  Gia_ObjForEachFanout( iObj, pFanout, k )
385  {
386  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, pFanout)];
387  iFanin = Gia_ObjFindFanin( p, pFanout, iObj );
388  assert( Gia_ObjLutFanin(p, pFanout, iFanin) == iObj );
389  tDelay = Gia_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin];
390  if ( tRequired > Gia_ObjTimeRequired( p, pFanout) - tDelay )
391  tRequired = Gia_ObjTimeRequired( p, pFanout) - tDelay;
392  }
393  }
394  }
395  return tRequired;
396 }
397 
398 /**Function*************************************************************
399 
400  Synopsis [Computes the arrival times for the given node.]
401 
402  Description []
403 
404  SideEffects []
405 
406  SeeAlso []
407 
408 ***********************************************************************/
409 int Gia_LutVerifyTiming( Gia_Man_t * p )
410 {
411  int iObj;
412  float tArrival, tRequired;
413  int i;
414  Gia_LutForEachObj( p, iObj, i )
415  {
416  if ( Gia_ObjIsCi(iObj) && Gia_ObjFanoutNum(iObj) == 0 )
417  continue;
418  tArrival = Gia_ObjComputeArrival( p, iObj, 1 );
419  tRequired = Gia_ObjComputeRequired( p, iObj, 1 );
420  if ( !Gia_LutTimeEqual( tArrival, Gia_ObjTimeArrival( p, iObj), (float)0.01 ) )
421  printf( "Gia_LutVerifyTiming(): Object %d has different arrival time (%.2f) from computed (%.2f).\n",
422  iObj->Id, Gia_ObjTimeArrival( p, iObj), tArrival );
423  if ( !Gia_LutTimeEqual( tRequired, Gia_ObjTimeRequired( p, iObj), (float)0.01 ) )
424  printf( "Gia_LutVerifyTiming(): Object %d has different required time (%.2f) from computed (%.2f).\n",
425  iObj->Id, Gia_ObjTimeRequired( p, iObj), tRequired );
426  }
427  return 1;
428 }
429 
430 #endif
431 
432 /**Function*************************************************************
433 
434  Synopsis [Prints the delay trace for the given network.]
435 
436  Description []
437 
438  SideEffects []
439 
440  SeeAlso []
441 
442 ***********************************************************************/
443 float Gia_ManDelayTraceLutPrint( Gia_Man_t * p, int fVerbose )
444 {
445  If_LibLut_t * pLutLib = (If_LibLut_t *)p->pLutLib;
446  int i, Nodes, * pCounters;
447  float tArrival, tDelta, nSteps, Num;
448  // get the library
449  if ( pLutLib && pLutLib->LutMax < Gia_ManLutSizeMax(p) )
450  {
451  printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
452  pLutLib->LutMax, Gia_ManLutSizeMax(p) );
453  return -ABC_INFINITY;
454  }
455  // decide how many steps
456  nSteps = pLutLib ? 20 : Gia_ManLutLevel(p);
457  pCounters = ABC_ALLOC( int, nSteps + 1 );
458  memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
459  // perform delay trace
460  tArrival = Gia_ManDelayTraceLut( p );
461  tDelta = tArrival / nSteps;
462  // count how many nodes have slack in the corresponding intervals
463  Gia_ManForEachLut( p, i )
464  {
465  if ( Gia_ObjLutSize(p, i) == 0 )
466  continue;
467  Num = Gia_ObjTimeSlack(p, i) / tDelta;
468  if ( Num > nSteps )
469  continue;
470  assert( Num >=0 && Num <= nSteps );
471  pCounters[(int)Num]++;
472  }
473  // print the results
474  if ( fVerbose )
475  {
476  printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, pLutLib? "LUT library" : "unit-delay" );
477  Nodes = 0;
478  for ( i = 0; i < nSteps; i++ )
479  {
480  Nodes += pCounters[i];
481  printf( "%3d %s : %5d (%6.2f %%)\n", pLutLib? 5*(i+1) : i+1,
482  pLutLib? "%":"lev", Nodes, 100.0*Nodes/Gia_ManLutNum(p) );
483  }
484  }
485  ABC_FREE( pCounters );
486  Gia_ManTimeStop( p );
487  return tArrival;
488 }
489 
490 /**Function*************************************************************
491 
492  Synopsis [Determines timing-critical edges of the node.]
493 
494  Description []
495 
496  SideEffects []
497 
498  SeeAlso []
499 
500 ***********************************************************************/
501 unsigned Gia_LutDelayTraceTCEdges( Gia_Man_t * p, int iObj, float tDelta )
502 {
503  If_LibLut_t * pLutLib = (If_LibLut_t *)p->pLutLib;
504  int pPinPerm[32];
505  float pPinDelays[32];
506  float tRequired, * pDelays;
507  unsigned uResult = 0;
508  int k, iFanin;
509  tRequired = Gia_ObjTimeRequired( p, iObj );
510  if ( pLutLib == NULL )
511  {
512  Gia_LutForEachFanin( p, iObj, iFanin, k )
513  if ( tRequired < Gia_ObjTimeArrival(p, iFanin) + 1.0 + tDelta )
514  uResult |= (1 << k);
515  }
516  else if ( !pLutLib->fVarPinDelays )
517  {
518  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
519  Gia_LutForEachFanin( p, iObj, iFanin, k )
520  if ( tRequired < Gia_ObjTimeArrival(p, iFanin) + pDelays[0] + tDelta )
521  uResult |= (1 << k);
522  }
523  else
524  {
525  pDelays = pLutLib->pLutDelays[Gia_ObjLutSize(p, iObj)];
526  Gia_LutDelayTraceSortPins( p, iObj, pPinPerm, pPinDelays );
527  Gia_LutForEachFanin( p, iObj, iFanin, k )
528  if ( tRequired < Gia_ObjTimeArrival( p, Gia_ObjLutFanin(p, iObj,pPinPerm[k])) + pDelays[k] + tDelta )
529  uResult |= (1 << pPinPerm[k]);
530  }
531  return uResult;
532 }
533 
534 /**Function*************************************************************
535 
536  Synopsis [Adds strashed nodes for one node.]
537 
538  Description []
539 
540  SideEffects []
541 
542  SeeAlso []
543 
544 ***********************************************************************/
546 {
547  if ( Gia_ObjIsTravIdCurrent(p, pObj) )
548  return 1;
549  Gia_ObjSetTravIdCurrent( p, pObj );
550  if ( Gia_ObjIsCi(pObj) )
551  return 0;
552  assert( Gia_ObjIsAnd(pObj) );
553  if ( !Gia_ManSpeedupObj_rec( p, Gia_ObjFanin0(pObj), vNodes ) )
554  return 0;
555  if ( !Gia_ManSpeedupObj_rec( p, Gia_ObjFanin1(pObj), vNodes ) )
556  return 0;
557  Vec_IntPush( vNodes, Gia_ObjId(p, pObj) );
558  return 1;
559 }
560 
561 /**Function*************************************************************
562 
563  Synopsis [Adds strashed nodes for one node.]
564 
565  Description []
566 
567  SideEffects []
568 
569  SeeAlso []
570 
571 ***********************************************************************/
572 void Gia_ManSpeedupObj( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vLeaves, Vec_Int_t * vTimes )
573 {
574  Vec_Int_t * vNodes;
575  Gia_Obj_t * pTemp = NULL;
576  int pCofs[32], nCofs, nSkip, i, k, iResult, iObj;
577  // mark the leaves
580  Gia_ManForEachObjVec( vLeaves, p, pTemp, i )
581  Gia_ObjSetTravIdCurrent( p, pTemp );
582  // collect the AIG nodes
583  vNodes = Vec_IntAlloc( 100 );
584  if ( !Gia_ManSpeedupObj_rec( p, pObj, vNodes ) )
585  {
586  printf( "Bad node!!!\n" );
587  Vec_IntFree( vNodes );
588  return;
589  }
590  // derive cofactors
591  nCofs = (1 << Vec_IntSize(vTimes));
592  for ( i = 0; i < nCofs; i++ )
593  {
594  Gia_ManForEachObjVec( vLeaves, p, pTemp, k )
595  pTemp->Value = Abc_Var2Lit( Gia_ObjId(p, pTemp), 0 );
596  Gia_ManForEachObjVec( vTimes, p, pTemp, k )
597  pTemp->Value = ((i & (1<<k)) != 0);
598  Gia_ManForEachObjVec( vNodes, p, pTemp, k )
599  pTemp->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pTemp), Gia_ObjFanin1Copy(pTemp) );
600  pCofs[i] = pTemp->Value;
601  }
602  Vec_IntFree( vNodes );
603  // collect the resulting tree
604  Gia_ManForEachObjVec( vTimes, p, pTemp, k )
605  for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
606  pCofs[i] = Gia_ManHashMux( pNew, Gia_ObjToLit(p,pTemp), pCofs[i+nSkip], pCofs[i] );
607  // create choice node (pObj is repr and ppCofs[0] is new)
608  iObj = Gia_ObjId( p, pObj );
609  iResult = Abc_Lit2Var( pCofs[0] );
610  if ( iResult <= iObj )
611  return;
612  Gia_ObjSetRepr( pNew, iResult, iObj );
613  Gia_ObjSetNext( pNew, iResult, Gia_ObjNext(pNew, iObj) );
614  Gia_ObjSetNext( pNew, iObj, iResult );
615 }
616 
617 /**Function*************************************************************
618 
619  Synopsis [Adds choices to speed up the network by the given percentage.]
620 
621  Description []
622 
623  SideEffects []
624 
625  SeeAlso []
626 
627 ***********************************************************************/
628 Gia_Man_t * Gia_ManSpeedup( Gia_Man_t * p, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
629 {
630  Gia_Man_t * pNew, * pTemp;
631  Vec_Int_t * vTimeCries, * vTimeFanins;
632  int iObj, iFanin, iFanin2, nNodesNew;
633  float tDelta, tArrival;
634  int i, k, k2, Counter, CounterRes, nTimeCris;
635  int fUseLutLib = (p->pLutLib != NULL);
636  void * pTempTim = NULL;
637  unsigned * puTCEdges;
639  if ( !fUseLutLib && p->pManTime )
640  {
641  pTempTim = p->pManTime;
642  p->pManTime = Tim_ManDup( (Tim_Man_t *)pTempTim, 1 );
643  }
644  // perform delay trace
645  tArrival = Gia_ManDelayTraceLut( p );
646  tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
647  if ( fVerbose )
648  {
649  printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
650  printf( "Using %s model. ", fUseLutLib ? "LUT library" : "unit-delay" );
651  if ( fUseLutLib )
652  printf( "Percentage = %d. ", Percentage );
653  printf( "\n" );
654  }
655  // mark the timing critical nodes and edges
656  puTCEdges = ABC_CALLOC( unsigned, Gia_ManObjNum(p) );
657  Gia_ManForEachLut( p, iObj )
658  {
659  if ( Gia_ObjTimeSlack(p, iObj) >= tDelta )
660  continue;
661  puTCEdges[iObj] = Gia_LutDelayTraceTCEdges( p, iObj, tDelta );
662  }
663  if ( fVerbose )
664  {
665  Counter = CounterRes = 0;
666  Gia_ManForEachLut( p, iObj )
667  {
668  Gia_LutForEachFanin( p, iObj, iFanin, k )
669  if ( !Gia_ObjIsCi(Gia_ManObj(p, iFanin)) && Gia_ObjTimeSlack(p, iFanin) < tDelta )
670  Counter++;
671  CounterRes += Gia_WordCountOnes( puTCEdges[iObj] );
672  }
673  printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n",
674  Gia_ManLutFaninCount(p), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
675  }
676 
677  // start the resulting network
678  pNew = Gia_ManDup( p );
679  Gia_ManHashStart( pNew );
680  nNodesNew = 1000 + 3 * Gia_ManObjNum(pNew);
681  pNew->pNexts = ABC_CALLOC( int, nNodesNew );
682  pNew->pReprs = ABC_CALLOC( Gia_Rpr_t, nNodesNew );
683  for ( i = 0; i < nNodesNew; i++ )
684  Gia_ObjSetRepr( pNew, i, GIA_VOID );
685 
686  // collect nodes to be used for resynthesis
687  Counter = CounterRes = 0;
688  vTimeCries = Vec_IntAlloc( 16 );
689  vTimeFanins = Vec_IntAlloc( 16 );
690  Gia_ManForEachLut( p, iObj )
691  {
692  if ( Gia_ObjTimeSlack(p, iObj) >= tDelta )
693  continue;
694  // count the number of non-PI timing-critical nodes
695  nTimeCris = 0;
696  Gia_LutForEachFanin( p, iObj, iFanin, k )
697  if ( !Gia_ObjIsCi(Gia_ManObj(p, iFanin)) && (puTCEdges[iObj] & (1<<k)) )
698  nTimeCris++;
699  if ( !fVeryVerbose && nTimeCris == 0 )
700  continue;
701  Counter++;
702  // count the total number of timing critical second-generation nodes
703  Vec_IntClear( vTimeCries );
704  if ( nTimeCris )
705  {
706  Gia_LutForEachFanin( p, iObj, iFanin, k )
707  if ( !Gia_ObjIsCi(Gia_ManObj(p, iFanin)) && (puTCEdges[iObj] & (1<<k)) )
708  Gia_LutForEachFanin( p, iFanin, iFanin2, k2 )
709  if ( puTCEdges[iFanin] & (1<<k2) )
710  Vec_IntPushUnique( vTimeCries, iFanin2 );
711  }
712 // if ( !fVeryVerbose && (Vec_IntSize(vTimeCries) == 0 || Vec_IntSize(vTimeCries) > Degree) )
713  if ( (Vec_IntSize(vTimeCries) == 0 || Vec_IntSize(vTimeCries) > Degree) )
714  continue;
715  CounterRes++;
716  // collect second generation nodes
717  Vec_IntClear( vTimeFanins );
718  Gia_LutForEachFanin( p, iObj, iFanin, k )
719  {
720  if ( Gia_ObjIsCi(Gia_ManObj(p, iFanin)) )
721  Vec_IntPushUnique( vTimeFanins, iFanin );
722  else
723  Gia_LutForEachFanin( p, iFanin, iFanin2, k2 )
724  Vec_IntPushUnique( vTimeFanins, iFanin2 );
725  }
726  // print the results
727  if ( fVeryVerbose )
728  {
729  printf( "%5d Node %5d : %d %2d %2d ", Counter, iObj,
730  nTimeCris, Vec_IntSize(vTimeCries), Vec_IntSize(vTimeFanins) );
731  Gia_LutForEachFanin( p, iObj, iFanin, k )
732  printf( "%d(%.2f)%s ", iFanin, Gia_ObjTimeSlack(p, iFanin), (puTCEdges[iObj] & (1<<k))? "*":"" );
733  printf( "\n" );
734  }
735  // add the node to choices
736  if ( Vec_IntSize(vTimeCries) == 0 || Vec_IntSize(vTimeCries) > Degree )
737  continue;
738  // order the fanins in the increasing order of criticalily
739  if ( Vec_IntSize(vTimeCries) > 1 )
740  {
741  iFanin = Vec_IntEntry( vTimeCries, 0 );
742  iFanin2 = Vec_IntEntry( vTimeCries, 1 );
743  if ( Gia_ObjTimeSlack(p, iFanin) < Gia_ObjTimeSlack(p, iFanin2) )
744  {
745  Vec_IntWriteEntry( vTimeCries, 0, iFanin2 );
746  Vec_IntWriteEntry( vTimeCries, 1, iFanin );
747  }
748  }
749  if ( Vec_IntSize(vTimeCries) > 2 )
750  {
751  iFanin = Vec_IntEntry( vTimeCries, 1 );
752  iFanin2 = Vec_IntEntry( vTimeCries, 2 );
753  if ( Gia_ObjTimeSlack(p, iFanin) < Gia_ObjTimeSlack(p, iFanin2) )
754  {
755  Vec_IntWriteEntry( vTimeCries, 1, iFanin2 );
756  Vec_IntWriteEntry( vTimeCries, 2, iFanin );
757  }
758  iFanin = Vec_IntEntry( vTimeCries, 0 );
759  iFanin2 = Vec_IntEntry( vTimeCries, 1 );
760  if ( Gia_ObjTimeSlack(p, iFanin) < Gia_ObjTimeSlack(p, iFanin2) )
761  {
762  Vec_IntWriteEntry( vTimeCries, 0, iFanin2 );
763  Vec_IntWriteEntry( vTimeCries, 1, iFanin );
764  }
765  }
766  // add choice
767  Gia_ManSpeedupObj( pNew, p, Gia_ManObj(p,iObj), vTimeFanins, vTimeCries );
768  // quit if the number of nodes is large
769  if ( Gia_ManObjNum(pNew) > nNodesNew - 100 )
770  {
771  printf( "Speedup stopped adding choices because there was too many to add.\n" );
772  break;
773  }
774  }
775  Gia_ManTimeStop( p );
776  Vec_IntFree( vTimeCries );
777  Vec_IntFree( vTimeFanins );
778  ABC_FREE( puTCEdges );
779  if ( fVerbose )
780  printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n",
781  Gia_ManLutNum(p), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 );
782  if ( pTempTim )
783  {
784  Tim_ManStop( (Tim_Man_t *)p->pManTime );
785  p->pManTime = pTempTim;
786  }
787  // derive AIG with choices
788 //Gia_ManPrintStats( pNew, 0 );
789  pTemp = Gia_ManEquivToChoices( pNew, 1 );
790  Gia_ManStop( pNew );
791 //Gia_ManPrintStats( pTemp, 0 );
792 // pNew = Gia_ManDupOrderDfsChoices( pTemp );
793 // Gia_ManStop( pTemp );
794 //Gia_ManPrintStats( pNew, 0 );
795 // return pNew;
796  return pTemp;
797 }
798 
799 ////////////////////////////////////////////////////////////////////////
800 /// END OF FILE ///
801 ////////////////////////////////////////////////////////////////////////
802 
803 
805 
char * memset()
static int Gia_ObjToLit(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:497
void * pLutLib
Definition: gia.h:166
ABC_NAMESPACE_IMPL_START void Gia_LutDelayTraceSortPins(Gia_Man_t *p, int iObj, int *pPinPerm, float *pPinDelays)
DECLARATIONS ///.
Definition: giaSpeedup.c:46
Gia_Man_t * Gia_ManDup(Gia_Man_t *p)
Definition: giaDup.c:552
void Gia_ManStop(Gia_Man_t *p)
Definition: giaMan.c:77
void Tim_ManIncrementTravId(Tim_Man_t *p)
DECLARATIONS ///.
Definition: timTrav.c:44
#define Gia_ManForEachCo(p, pObj, i)
Definition: gia.h:1022
int * pNexts
Definition: gia.h:122
int Gia_LutWhereIsPin(Gia_Man_t *p, int iFanout, int iFanin, int *pPinPerm)
Definition: giaSpeedup.c:90
float Gia_ObjPropagateRequired(Gia_Man_t *p, int iObj, int fUseSorting)
Definition: giaSpeedup.c:170
static Llb_Mgr_t * p
Definition: llb3Image.c:950
int Gia_ManLutLevel(Gia_Man_t *p)
Definition: giaIf.c:163
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
static int Gia_ObjIsTravIdCurrent(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:533
static int Abc_Var2Lit(int Var, int fCompl)
Definition: abc_global.h:263
void Tim_ManSetCoArrival(Tim_Man_t *p, int iCo, float Delay)
Definition: timTime.c:116
unsigned Gia_LutDelayTraceTCEdges(Gia_Man_t *p, int iObj, float tDelta)
Definition: giaSpeedup.c:501
int LutMax
Definition: if.h:173
float Gia_ManDelayTraceLut(Gia_Man_t *p)
Definition: giaSpeedup.c:230
float pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1]
Definition: if.h:176
static int Gia_WordCountOnes(unsigned uWord)
Definition: gia.h:313
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
int Gia_ManLutNum(Gia_Man_t *p)
Definition: giaIf.c:144
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
Definition: gia.h:75
#define Gia_ManForEachLut(p, i)
Definition: gia.h:968
Gia_Man_t * Gia_ManSpeedup(Gia_Man_t *p, int Percentage, int Degree, int fVerbose, int fVeryVerbose)
Definition: giaSpeedup.c:628
#define Gia_ObjForEachFanout(p, pObj, pFanout, iFan, i)
Definition: giaFanout.c:46
void Tim_ManSetCiRequired(Tim_Man_t *p, int iCi, float Delay)
Definition: timTime.c:135
Gia_Man_t * Gia_ManEquivToChoices(Gia_Man_t *p, int nSnapshots)
Definition: giaEquiv.c:1629
static void Gia_ObjSetRepr(Gia_Man_t *p, int Id, int Num)
Definition: gia.h:888
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
float Gia_ManDelayTraceLutPrint(Gia_Man_t *p, int fVerbose)
Definition: giaSpeedup.c:443
static void Gia_ObjSetTimeSlack(Gia_Man_t *p, int Id, float t)
Definition: gia.h:549
static Gia_Obj_t * Gia_ObjFanin0(Gia_Obj_t *pObj)
Definition: gia.h:454
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
static int Gia_ObjLutSize(Gia_Man_t *p, int Id)
Definition: gia.h:953
static float Gia_ObjTimeSlack(Gia_Man_t *p, int Id)
Definition: gia.h:543
int fVarPinDelays
Definition: if.h:174
int Gia_ManLutFaninCount(Gia_Man_t *p)
Definition: giaIf.c:106
static int Gia_ObjFanin1Copy(Gia_Obj_t *pObj)
Definition: gia.h:482
int Gia_ManSpeedupObj_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vNodes)
Definition: giaSpeedup.c:545
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
static void Gia_ObjSetTravIdCurrent(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:531
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
int Gia_ManHashMux(Gia_Man_t *p, int iCtrl, int iData1, int iData0)
Definition: giaHash.c:677
if(last==0)
Definition: sparse_int.h:34
void Gia_ManHashStart(Gia_Man_t *p)
Definition: giaHash.c:117
static int Gia_ObjFanoutNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:940
static float Gia_ObjTimeRequired(Gia_Man_t *p, int Id)
Definition: gia.h:542
Tim_Man_t * Tim_ManDup(Tim_Man_t *p, int fUnitDelay)
Definition: timMan.c:86
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
void * pManTime
Definition: gia.h:165
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
static int Counter
static void Gia_ManTimeStop(Gia_Man_t *p)
Definition: gia.h:540
void Tim_ManStop(Tim_Man_t *p)
Definition: timMan.c:375
int Gia_ManLutSizeMax(Gia_Man_t *p)
Definition: giaIf.c:125
static int Gia_ObjFanin0Copy(Gia_Obj_t *pObj)
Definition: gia.h:481
static int Gia_ObjIsCo(Gia_Obj_t *pObj)
Definition: gia.h:421
static int Gia_ObjNext(Gia_Man_t *p, int Id)
Definition: gia.h:912
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition: gia.h:988
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static void Gia_ObjSetNext(Gia_Man_t *p, int Id, int Num)
Definition: gia.h:913
static void Gia_ObjSetTimeArrival(Gia_Man_t *p, int Id, float t)
Definition: gia.h:547
static void Gia_ObjSetTimeRequiredObj(Gia_Man_t *p, Gia_Obj_t *pObj, float t)
Definition: gia.h:551
static int Gia_ObjLutFanin(Gia_Man_t *p, int Id, int i)
Definition: gia.h:955
#define GIA_VOID
Definition: gia.h:45
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static int Gia_ManHasMapping(Gia_Man_t *p)
Definition: gia.h:951
#define ABC_FREE(obj)
Definition: abc_global.h:232
Definition: gia.h:95
#define TIM_ETERNITY
MACRO DEFINITIONS ///.
Definition: tim.h:98
static int Gia_ObjIsAnd(Gia_Obj_t *pObj)
Definition: gia.h:422
static void Gia_ManTimeStart(Gia_Man_t *p)
Definition: gia.h:539
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition: gia.h:984
static Gia_Obj_t * Gia_ManConst0(Gia_Man_t *p)
Definition: gia.h:400
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
static int Abc_Lit2Var(int Lit)
Definition: abc_global.h:264
static int Gia_ObjFaninId0p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:463
static Gia_Obj_t * Gia_ObjFanin1(Gia_Obj_t *pObj)
Definition: gia.h:455
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
static float Gia_ObjTimeArrival(Gia_Man_t *p, int Id)
Definition: gia.h:541
Gia_Rpr_t * pReprs
Definition: gia.h:121
float Tim_ManGetCoRequired(Tim_Man_t *p, int iCo)
Definition: timTime.c:222
#define assert(ex)
Definition: util_old.h:213
unsigned Value
Definition: gia.h:87
typedefABC_NAMESPACE_HEADER_START struct Tim_Man_t_ Tim_Man_t
INCLUDES ///.
Definition: tim.h:92
static int Gia_ObjIsLut(Gia_Man_t *p, int Id)
Definition: gia.h:952
float Gia_ObjComputeArrival(Gia_Man_t *p, int iObj, int fUseSorting)
Definition: giaSpeedup.c:110
void Gia_ManIncrementTravId(Gia_Man_t *p)
Definition: giaUtil.c:149
Definition: gia.h:56
Vec_Int_t * Gia_ManOrderReverse(Gia_Man_t *p)
Definition: giaDfs.c:407
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
static int Vec_IntPushUnique(Vec_Int_t *p, int Entry)
Definition: vecInt.h:832
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
static void Gia_ObjSetTimeRequired(Gia_Man_t *p, int Id, float t)
Definition: gia.h:548
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
float Tim_ManGetCiArrival(Tim_Man_t *p, int iCi)
Definition: timTime.c:174
void Gia_ManSpeedupObj(Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vLeaves, Vec_Int_t *vTimes)
Definition: giaSpeedup.c:572
#define Gia_LutForEachFanin(p, i, iFan, k)
Definition: gia.h:970
int Gia_ManHashAnd(Gia_Man_t *p, int iLit0, int iLit1)
Definition: giaHash.c:572
static int Gia_ObjCioId(Gia_Obj_t *pObj)
Definition: gia.h:411
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
void Tim_ManInitPoRequiredAll(Tim_Man_t *p, float Delay)
Definition: timTime.c:97
static float Gia_ObjTimeArrivalObj(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:544