1 /**CFile****************************************************************
2 
3   FileName    [abcSpeedup.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [Network and node package.]
8 
9   Synopsis    [Delay trace and speedup.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - June 20, 2005.]
16 
17   Revision    [$Id: abcSpeedup.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 #include "base/main/main.h"
23 #include "map/if/if.h"
24 #include "aig/aig/aig.h"
25 
26 ABC_NAMESPACE_IMPL_START
27 
28 
29 ////////////////////////////////////////////////////////////////////////
30 ///                        DECLARATIONS                              ///
31 ////////////////////////////////////////////////////////////////////////
32 
Abc_ObjArrival(Abc_Obj_t * pNode)33 static inline float Abc_ObjArrival( Abc_Obj_t * pNode )                 { return pNode->pNtk->pLutTimes[3*pNode->Id+0]; }
Abc_ObjRequired(Abc_Obj_t * pNode)34 static inline float Abc_ObjRequired( Abc_Obj_t * pNode )                { return pNode->pNtk->pLutTimes[3*pNode->Id+1]; }
Abc_ObjSlack(Abc_Obj_t * pNode)35 static inline float Abc_ObjSlack( Abc_Obj_t * pNode )                   { return pNode->pNtk->pLutTimes[3*pNode->Id+2]; }
36 
Abc_ObjSetArrival(Abc_Obj_t * pNode,float Time)37 static inline void  Abc_ObjSetArrival( Abc_Obj_t * pNode, float Time )  { pNode->pNtk->pLutTimes[3*pNode->Id+0] = Time; }
Abc_ObjSetRequired(Abc_Obj_t * pNode,float Time)38 static inline void  Abc_ObjSetRequired( Abc_Obj_t * pNode, float Time ) { pNode->pNtk->pLutTimes[3*pNode->Id+1] = Time; }
Abc_ObjSetSlack(Abc_Obj_t * pNode,float Time)39 static inline void  Abc_ObjSetSlack( Abc_Obj_t * pNode, float Time )    { pNode->pNtk->pLutTimes[3*pNode->Id+2] = Time; }
40 
41 ////////////////////////////////////////////////////////////////////////
42 ///                     FUNCTION DEFINITIONS                         ///
43 ////////////////////////////////////////////////////////////////////////
44 
45 /**Function*************************************************************
46 
47   Synopsis    [Sorts the pins in the decreasing order of delays.]
48 
49   Description []
50 
51   SideEffects []
52 
53   SeeAlso     []
54 
55 ***********************************************************************/
Abc_NtkDelayTraceSortPins(Abc_Obj_t * pNode,int * pPinPerm,float * pPinDelays)56 void Abc_NtkDelayTraceSortPins( Abc_Obj_t * pNode, int * pPinPerm, float * pPinDelays )
57 {
58     Abc_Obj_t * pFanin;
59     int i, j, best_i, temp;
60     // start the trivial permutation and collect pin delays
61     Abc_ObjForEachFanin( pNode, pFanin, i )
62     {
63         pPinPerm[i] = i;
64         pPinDelays[i] = Abc_ObjArrival(pFanin);
65     }
66     // selection sort the pins in the decreasible order of delays
67     // this order will match the increasing order of LUT input pins
68     for ( i = 0; i < Abc_ObjFaninNum(pNode)-1; i++ )
69     {
70         best_i = i;
71         for ( j = i+1; j < Abc_ObjFaninNum(pNode); j++ )
72             if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
73                 best_i = j;
74         if ( best_i == i )
75             continue;
76         temp = pPinPerm[i];
77         pPinPerm[i] = pPinPerm[best_i];
78         pPinPerm[best_i] = temp;
79     }
80     // verify
81     assert( Abc_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Abc_ObjFaninNum(pNode) );
82     for ( i = 1; i < Abc_ObjFaninNum(pNode); i++ )
83     {
84         assert( pPinPerm[i] < Abc_ObjFaninNum(pNode) );
85         assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
86     }
87 }
88 
89 /**Function*************************************************************
90 
91   Synopsis    []
92 
93   Description []
94 
95   SideEffects []
96 
97   SeeAlso     []
98 
99 ***********************************************************************/
Abc_NtkDelayTraceLut(Abc_Ntk_t * pNtk,int fUseLutLib)100 float Abc_NtkDelayTraceLut( Abc_Ntk_t * pNtk, int fUseLutLib )
101 {
102     int fUseSorting = 1;
103     int pPinPerm[32];
104     float pPinDelays[32];
105     If_LibLut_t * pLutLib;
106     Abc_Obj_t * pNode, * pFanin;
107     Vec_Ptr_t * vNodes;
108     float tArrival, tRequired, tSlack, * pDelays;
109     int i, k;
110 
111     assert( Abc_NtkIsLogic(pNtk) );
112     // get the library
113     pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
114     if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
115     {
116         printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
117             pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
118         return -ABC_INFINITY;
119     }
120 
121     // initialize the arrival times
122     ABC_FREE( pNtk->pLutTimes );
123     pNtk->pLutTimes = ABC_ALLOC( float, 3 * Abc_NtkObjNumMax(pNtk) );
124     for ( i = 0; i < Abc_NtkObjNumMax(pNtk); i++ )
125     {
126         pNtk->pLutTimes[3*i+0] = pNtk->pLutTimes[3*i+2] = 0;
127         pNtk->pLutTimes[3*i+1] = ABC_INFINITY;
128     }
129 
130     // propagate arrival times
131     vNodes = Abc_NtkDfs( pNtk, 1 );
132     Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
133     {
134         tArrival = -ABC_INFINITY;
135         if ( pLutLib == NULL )
136         {
137             Abc_ObjForEachFanin( pNode, pFanin, k )
138                 if ( tArrival < Abc_ObjArrival(pFanin) + 1.0 )
139                     tArrival = Abc_ObjArrival(pFanin) + 1.0;
140         }
141         else if ( !pLutLib->fVarPinDelays )
142         {
143             pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
144             Abc_ObjForEachFanin( pNode, pFanin, k )
145                 if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[0] )
146                     tArrival = Abc_ObjArrival(pFanin) + pDelays[0];
147         }
148         else
149         {
150             pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
151             if ( fUseSorting )
152             {
153                 Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
154                 Abc_ObjForEachFanin( pNode, pFanin, k )
155                     if ( tArrival < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] )
156                         tArrival = Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k];
157             }
158             else
159             {
160                 Abc_ObjForEachFanin( pNode, pFanin, k )
161                     if ( tArrival < Abc_ObjArrival(pFanin) + pDelays[k] )
162                         tArrival = Abc_ObjArrival(pFanin) + pDelays[k];
163             }
164         }
165         if ( Abc_ObjFaninNum(pNode) == 0 )
166             tArrival = 0.0;
167         Abc_ObjSetArrival( pNode, tArrival );
168     }
169     Vec_PtrFree( vNodes );
170 
171     // get the latest arrival times
172     tArrival = -ABC_INFINITY;
173     Abc_NtkForEachCo( pNtk, pNode, i )
174         if ( tArrival < Abc_ObjArrival(Abc_ObjFanin0(pNode)) )
175             tArrival = Abc_ObjArrival(Abc_ObjFanin0(pNode));
176 
177     // initialize the required times
178     Abc_NtkForEachCo( pNtk, pNode, i )
179         if ( Abc_ObjRequired(Abc_ObjFanin0(pNode)) > tArrival )
180             Abc_ObjSetRequired( Abc_ObjFanin0(pNode), tArrival );
181 
182     // propagate the required times
183     vNodes = Abc_NtkDfsReverse( pNtk );
184     Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
185     {
186         if ( pLutLib == NULL )
187         {
188             tRequired = Abc_ObjRequired(pNode) - (float)1.0;
189             Abc_ObjForEachFanin( pNode, pFanin, k )
190                 if ( Abc_ObjRequired(pFanin) > tRequired )
191                     Abc_ObjSetRequired( pFanin, tRequired );
192         }
193         else if ( !pLutLib->fVarPinDelays )
194         {
195             pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
196             tRequired = Abc_ObjRequired(pNode) - pDelays[0];
197             Abc_ObjForEachFanin( pNode, pFanin, k )
198                 if ( Abc_ObjRequired(pFanin) > tRequired )
199                     Abc_ObjSetRequired( pFanin, tRequired );
200         }
201         else
202         {
203             pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
204             if ( fUseSorting )
205             {
206                 Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
207                 Abc_ObjForEachFanin( pNode, pFanin, k )
208                 {
209                     tRequired = Abc_ObjRequired(pNode) - pDelays[k];
210                     if ( Abc_ObjRequired(Abc_ObjFanin(pNode,pPinPerm[k])) > tRequired )
211                         Abc_ObjSetRequired( Abc_ObjFanin(pNode,pPinPerm[k]), tRequired );
212                 }
213             }
214             else
215             {
216                 Abc_ObjForEachFanin( pNode, pFanin, k )
217                 {
218                     tRequired = Abc_ObjRequired(pNode) - pDelays[k];
219                     if ( Abc_ObjRequired(pFanin) > tRequired )
220                         Abc_ObjSetRequired( pFanin, tRequired );
221                 }
222             }
223         }
224         // set slack for this object
225         tSlack = Abc_ObjRequired(pNode) - Abc_ObjArrival(pNode);
226         assert( tSlack + 0.001 > 0.0 );
227         Abc_ObjSetSlack( pNode, tSlack < 0.0 ? 0.0 : tSlack );
228     }
229     Vec_PtrFree( vNodes );
230     return tArrival;
231 }
232 
233 /**Function*************************************************************
234 
235   Synopsis    [Delay tracing of the LUT mapped network.]
236 
237   Description []
238 
239   SideEffects []
240 
241   SeeAlso     []
242 
243 ***********************************************************************/
Abc_NtkDelayTracePrint(Abc_Ntk_t * pNtk,int fUseLutLib,int fVerbose)244 void Abc_NtkDelayTracePrint( Abc_Ntk_t * pNtk, int fUseLutLib, int fVerbose )
245 {
246     Abc_Obj_t * pNode;
247     If_LibLut_t * pLutLib;
248     int i, Nodes, * pCounters;
249     float tArrival, tDelta, nSteps, Num;
250     // get the library
251     pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
252     if ( pLutLib && pLutLib->LutMax < Abc_NtkGetFaninMax(pNtk) )
253     {
254         printf( "The max LUT size (%d) is less than the max fanin count (%d).\n",
255             pLutLib->LutMax, Abc_NtkGetFaninMax(pNtk) );
256         return;
257     }
258     // decide how many steps
259     nSteps = fUseLutLib ? 20 : Abc_NtkLevel(pNtk);
260     pCounters = ABC_ALLOC( int, nSteps + 1 );
261     memset( pCounters, 0, sizeof(int)*(nSteps + 1) );
262     // perform delay trace
263     tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
264     tDelta = tArrival / nSteps;
265     // count how many nodes have slack in the corresponding intervals
266     Abc_NtkForEachNode( pNtk, pNode, i )
267     {
268         if ( Abc_ObjFaninNum(pNode) == 0 )
269             continue;
270         Num = Abc_ObjSlack(pNode) / tDelta;
271         assert( Num >=0 && Num <= nSteps );
272         pCounters[(int)Num]++;
273     }
274     // print the results
275     printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, fUseLutLib? "LUT library" : "unit-delay" );
276     Nodes = 0;
277     for ( i = 0; i < nSteps; i++ )
278     {
279         Nodes += pCounters[i];
280         printf( "%3d %s : %5d  (%6.2f %%)\n", fUseLutLib? 5*(i+1) : i+1,
281             fUseLutLib? "%":"lev", Nodes, 100.0*Nodes/Abc_NtkNodeNum(pNtk) );
282     }
283     ABC_FREE( pCounters );
284 }
285 
286 /**Function*************************************************************
287 
288   Synopsis    [Returns 1 if pOld is in the TFI of pNew.]
289 
290   Description []
291 
292   SideEffects []
293 
294   SeeAlso     []
295 
296 ***********************************************************************/
Abc_AigCheckTfi_rec(Abc_Obj_t * pNode,Abc_Obj_t * pOld)297 int Abc_AigCheckTfi_rec( Abc_Obj_t * pNode, Abc_Obj_t * pOld )
298 {
299     // check the trivial cases
300     if ( pNode == NULL )
301         return 0;
302     if ( Abc_ObjIsCi(pNode) )
303         return 0;
304     if ( pNode == pOld )
305         return 1;
306     // skip the visited node
307     if ( Abc_NodeIsTravIdCurrent( pNode ) )
308         return 0;
309     Abc_NodeSetTravIdCurrent( pNode );
310     // check the children
311     if ( Abc_AigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) )
312         return 1;
313     if ( Abc_AigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) )
314         return 1;
315     // check equivalent nodes
316     return Abc_AigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld );
317 }
318 
319 /**Function*************************************************************
320 
321   Synopsis    [Returns 1 if pOld is in the TFI of pNew.]
322 
323   Description []
324 
325   SideEffects []
326 
327   SeeAlso     []
328 
329 ***********************************************************************/
Abc_AigCheckTfi(Abc_Obj_t * pNew,Abc_Obj_t * pOld)330 int Abc_AigCheckTfi( Abc_Obj_t * pNew, Abc_Obj_t * pOld )
331 {
332     assert( !Abc_ObjIsComplement(pNew) );
333     assert( !Abc_ObjIsComplement(pOld) );
334     Abc_NtkIncrementTravId( pNew->pNtk );
335     return Abc_AigCheckTfi_rec( pNew, pOld );
336 }
337 
338 /**Function*************************************************************
339 
340   Synopsis    [Adds strashed nodes for one node.]
341 
342   Description []
343 
344   SideEffects []
345 
346   SeeAlso     []
347 
348 ***********************************************************************/
Abc_NtkSpeedupNode_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)349 int Abc_NtkSpeedupNode_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
350 {
351     if ( Abc_NodeIsTravIdCurrent(pNode) )
352         return 1;
353     if ( Abc_ObjIsCi(pNode) )
354         return 0;
355     assert( Abc_ObjIsNode(pNode) );
356     Abc_NodeSetTravIdCurrent( pNode );
357     if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin0(pNode), vNodes ) )
358         return 0;
359     if ( !Abc_NtkSpeedupNode_rec( Abc_ObjFanin1(pNode), vNodes ) )
360         return 0;
361     Vec_PtrPush( vNodes, pNode );
362     return 1;
363 }
364 
365 /**Function*************************************************************
366 
367   Synopsis    [Adds strashed nodes for one node.]
368 
369   Description []
370 
371   SideEffects []
372 
373   SeeAlso     []
374 
375 ***********************************************************************/
Abc_NtkSpeedupNode(Abc_Ntk_t * pNtk,Abc_Ntk_t * pAig,Abc_Obj_t * pNode,Vec_Ptr_t * vLeaves,Vec_Ptr_t * vTimes)376 void Abc_NtkSpeedupNode( Abc_Ntk_t * pNtk, Abc_Ntk_t * pAig, Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes )
377 {
378     Vec_Ptr_t * vNodes;
379     Abc_Obj_t * pObj, * pObj2, * pAnd;
380     Abc_Obj_t * ppCofs[32];
381     int nCofs, i, k, nSkip;
382 
383     // quit of regulars are the same
384     Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
385     Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj2, k )
386         if ( i != k && Abc_ObjRegular(pObj->pCopy) == Abc_ObjRegular(pObj2->pCopy) )
387         {
388 //            printf( "Identical after structural hashing!!!\n" );
389             return;
390         }
391 
392     // collect the AIG nodes
393     vNodes = Vec_PtrAlloc( 100 );
394     Abc_NtkIncrementTravId( pAig );
395     Abc_NodeSetTravIdCurrent( Abc_AigConst1(pAig) );
396     Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
397     {
398         pAnd = pObj->pCopy;
399         Abc_NodeSetTravIdCurrent( Abc_ObjRegular(pAnd) );
400     }
401     // traverse from the root node
402     pAnd = pNode->pCopy;
403     if ( !Abc_NtkSpeedupNode_rec( Abc_ObjRegular(pAnd), vNodes ) )
404     {
405 //        printf( "Bad node!!!\n" );
406         Vec_PtrFree( vNodes );
407         return;
408     }
409 
410     // derive cofactors
411     nCofs = (1 << Vec_PtrSize(vTimes));
412     for ( i = 0; i < nCofs; i++ )
413     {
414         Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, k )
415         {
416             pAnd = pObj->pCopy;
417             Abc_ObjRegular(pAnd)->pCopy = Abc_ObjRegular(pAnd);
418         }
419         Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
420         {
421             pAnd = pObj->pCopy;
422             Abc_ObjRegular(pAnd)->pCopy = Abc_ObjNotCond( Abc_AigConst1(pAig), ((i & (1<<k)) == 0) );
423         }
424         Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, k )
425             pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
426         // save the result
427         pAnd = pNode->pCopy;
428         ppCofs[i] = Abc_ObjNotCond( Abc_ObjRegular(pAnd)->pCopy, Abc_ObjIsComplement(pAnd) );
429     }
430     Vec_PtrFree( vNodes );
431 
432 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );
433 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[1] );
434 
435     // collect the resulting tree
436     Vec_PtrForEachEntry( Abc_Obj_t *, vTimes, pObj, k )
437         for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip )
438         {
439             pAnd = pObj->pCopy;
440             ppCofs[i] = Abc_AigMux( (Abc_Aig_t *)pAig->pManFunc, Abc_ObjRegular(pAnd), ppCofs[i+nSkip], ppCofs[i] );
441         }
442 //Abc_ObjAddFanin( Abc_NtkCreatePo(pAig), ppCofs[0] );
443 
444     // create choice node
445     pAnd = Abc_ObjRegular(pNode->pCopy); // repr
446     pObj = Abc_ObjRegular(ppCofs[0]);    // new
447     if ( pAnd->pData == NULL && pObj->pData == NULL && !Abc_AigNodeIsConst(pObj) && !Abc_AigCheckTfi(pObj, pAnd) )
448     {
449         pObj->pData = pAnd->pData;
450         pAnd->pData = pObj;
451     }
452 
453 }
454 
455 /**Function*************************************************************
456 
457   Synopsis    [Determines timing-critical edges of the node.]
458 
459   Description []
460 
461   SideEffects []
462 
463   SeeAlso     []
464 
465 ***********************************************************************/
Abc_NtkDelayTraceTCEdges(Abc_Ntk_t * pNtk,Abc_Obj_t * pNode,float tDelta,int fUseLutLib)466 unsigned Abc_NtkDelayTraceTCEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float tDelta, int fUseLutLib )
467 {
468     int pPinPerm[32];
469     float pPinDelays[32];
470     If_LibLut_t * pLutLib;
471     Abc_Obj_t * pFanin;
472     unsigned uResult = 0;
473     float tRequired, * pDelays;
474     int k;
475     pLutLib = fUseLutLib?  (If_LibLut_t *)Abc_FrameReadLibLut() : NULL;
476     tRequired = Abc_ObjRequired(pNode);
477     if ( pLutLib == NULL )
478     {
479         Abc_ObjForEachFanin( pNode, pFanin, k )
480             if ( tRequired < Abc_ObjArrival(pFanin) + 1.0 + tDelta )
481                 uResult |= (1 << k);
482     }
483     else if ( !pLutLib->fVarPinDelays )
484     {
485         pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
486         Abc_ObjForEachFanin( pNode, pFanin, k )
487             if ( tRequired < Abc_ObjArrival(pFanin) + pDelays[0] + tDelta )
488                 uResult |= (1 << k);
489     }
490     else
491     {
492         pDelays = pLutLib->pLutDelays[Abc_ObjFaninNum(pNode)];
493         Abc_NtkDelayTraceSortPins( pNode, pPinPerm, pPinDelays );
494         Abc_ObjForEachFanin( pNode, pFanin, k )
495             if ( tRequired < Abc_ObjArrival(Abc_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta )
496                 uResult |= (1 << pPinPerm[k]);
497     }
498     return uResult;
499 }
500 
501 /**Function*************************************************************
502 
503   Synopsis    [Adds choices to speed up the network by the given percentage.]
504 
505   Description []
506 
507   SideEffects []
508 
509   SeeAlso     []
510 
511 ***********************************************************************/
Abc_NtkSpeedup(Abc_Ntk_t * pNtk,int fUseLutLib,int Percentage,int Degree,int fVerbose,int fVeryVerbose)512 Abc_Ntk_t * Abc_NtkSpeedup( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
513 {
514     Abc_Ntk_t * pNtkNew;
515     Vec_Ptr_t * vTimeCries, * vTimeFanins;
516     Abc_Obj_t * pNode, * pFanin, * pFanin2;
517     float tDelta, tArrival;
518     int i, k, k2, Counter, CounterRes, nTimeCris;
519     unsigned * puTCEdges;
520     // perform delay trace
521     tArrival = Abc_NtkDelayTraceLut( pNtk, fUseLutLib );
522     tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0;
523     if ( fVerbose )
524     {
525         printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta );
526         printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" );
527         if ( fUseLutLib )
528             printf( "Percentage = %d. ", Percentage );
529         printf( "\n" );
530     }
531     // mark the timing critical nodes and edges
532     puTCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
533     memset( puTCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
534     Abc_NtkForEachNode( pNtk, pNode, i )
535     {
536         if ( Abc_ObjSlack(pNode) >= tDelta )
537             continue;
538         puTCEdges[pNode->Id] = Abc_NtkDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib );
539     }
540     if ( fVerbose )
541     {
542         Counter = CounterRes = 0;
543         Abc_NtkForEachNode( pNtk, pNode, i )
544         {
545             Abc_ObjForEachFanin( pNode, pFanin, k )
546                 if ( !Abc_ObjIsCi(pFanin) && Abc_ObjSlack(pFanin) < tDelta )
547                     Counter++;
548             CounterRes += Extra_WordCountOnes( puTCEdges[pNode->Id] );
549         }
550         printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n",
551             Abc_NtkGetTotalFanins(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
552     }
553     // start the resulting network
554     pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );
555 
556     // collect nodes to be used for resynthesis
557     Counter = CounterRes = 0;
558     vTimeCries = Vec_PtrAlloc( 16 );
559     vTimeFanins = Vec_PtrAlloc( 16 );
560     Abc_NtkForEachNode( pNtk, pNode, i )
561     {
562         if ( Abc_ObjSlack(pNode) >= tDelta )
563             continue;
564         // count the number of non-PI timing-critical nodes
565         nTimeCris = 0;
566         Abc_ObjForEachFanin( pNode, pFanin, k )
567             if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
568                 nTimeCris++;
569         if ( !fVeryVerbose && nTimeCris == 0 )
570             continue;
571         Counter++;
572         // count the total number of timing critical second-generation nodes
573         Vec_PtrClear( vTimeCries );
574         if ( nTimeCris )
575         {
576             Abc_ObjForEachFanin( pNode, pFanin, k )
577                 if ( !Abc_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) )
578                     Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
579                         if ( puTCEdges[pFanin->Id] & (1<<k2) )
580                             Vec_PtrPushUnique( vTimeCries, pFanin2 );
581         }
582 //        if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
583         if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
584             continue;
585         CounterRes++;
586         // collect second generation nodes
587         Vec_PtrClear( vTimeFanins );
588         Abc_ObjForEachFanin( pNode, pFanin, k )
589         {
590             if ( Abc_ObjIsCi(pFanin) )
591                 Vec_PtrPushUnique( vTimeFanins, pFanin );
592             else
593                 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
594                     Vec_PtrPushUnique( vTimeFanins, pFanin2 );
595         }
596         // print the results
597         if ( fVeryVerbose )
598         {
599         printf( "%5d Node %5d : %d %2d %2d  ", Counter, pNode->Id,
600             nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
601         Abc_ObjForEachFanin( pNode, pFanin, k )
602             printf( "%d(%.2f)%s ", pFanin->Id, Abc_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" );
603         printf( "\n" );
604         }
605         // add the node to choices
606         if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
607             continue;
608         // order the fanins in the increasing order of criticalily
609         if ( Vec_PtrSize(vTimeCries) > 1 )
610         {
611             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
612             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
613             if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
614             {
615                 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
616                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
617             }
618         }
619         if ( Vec_PtrSize(vTimeCries) > 2 )
620         {
621             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
622             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
623             if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
624             {
625                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
626                 Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
627             }
628             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
629             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
630             if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
631             {
632                 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
633                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
634             }
635         }
636         // add choice
637         Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
638     }
639     Vec_PtrFree( vTimeCries );
640     Vec_PtrFree( vTimeFanins );
641     ABC_FREE( puTCEdges );
642     if ( fVerbose )
643         printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n",
644             Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
645 
646     // remove invalid choice nodes
647     Abc_AigForEachAnd( pNtkNew, pNode, i )
648         if ( pNode->pData )
649         {
650             if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
651                 pNode->pData = NULL;
652         }
653 
654     // return the result
655     return pNtkNew;
656 }
657 
658 /**Function*************************************************************
659 
660   Synopsis    [Marks nodes for power-optimization.]
661 
662   Description []
663 
664   SideEffects []
665 
666   SeeAlso     []
667 
668 ***********************************************************************/
Abc_NtkPowerEstimate(Abc_Ntk_t * pNtk,int fProbOne)669 Vec_Int_t * Abc_NtkPowerEstimate( Abc_Ntk_t * pNtk, int fProbOne )
670 {
671     extern Aig_Man_t * Abc_NtkToDar( Abc_Ntk_t * pNtk, int fExors, int fRegisters );
672     extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
673     Vec_Int_t * vProbs;
674     Vec_Int_t * vSwitching;
675     float * pProbability;
676     float * pSwitching;
677     Abc_Ntk_t * pNtkStr;
678     Aig_Man_t * pAig;
679     Aig_Obj_t * pObjAig;
680     Abc_Obj_t * pObjAbc, * pObjAbc2;
681     int i;
682     // start the resulting array
683     vProbs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
684     pProbability = (float *)vProbs->pArray;
685     // strash the network
686     pNtkStr = Abc_NtkStrash( pNtk, 0, 1, 0 );
687     Abc_NtkForEachObj( pNtk, pObjAbc, i )
688         if ( Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)->Type == ABC_FUNC_NONE )
689             pObjAbc->pTemp = NULL;
690     // map network into an AIG
691     pAig = Abc_NtkToDar( pNtkStr, 0, (int)(Abc_NtkLatchNum(pNtk) > 0) );
692     vSwitching = Saig_ManComputeSwitchProbs( pAig, 48, 16, fProbOne );
693     pSwitching = (float *)vSwitching->pArray;
694     Abc_NtkForEachObj( pNtk, pObjAbc, i )
695     {
696         if ( (pObjAbc2 = Abc_ObjRegular((Abc_Obj_t *)pObjAbc->pTemp)) && (pObjAig = Aig_Regular((Aig_Obj_t *)pObjAbc2->pTemp)) )
697             pProbability[pObjAbc->Id] = pSwitching[pObjAig->Id];
698     }
699     Vec_IntFree( vSwitching );
700     Aig_ManStop( pAig );
701     Abc_NtkDelete( pNtkStr );
702     return vProbs;
703 }
704 
705 /**Function*************************************************************
706 
707   Synopsis    [Marks nodes for power-optimization.]
708 
709   Description []
710 
711   SideEffects []
712 
713   SeeAlso     []
714 
715 ***********************************************************************/
Abc_NtkPowerPrint(Abc_Ntk_t * pNtk,Vec_Int_t * vProbs)716 void Abc_NtkPowerPrint( Abc_Ntk_t * pNtk, Vec_Int_t * vProbs )
717 {
718     Abc_Obj_t * pObj;
719     float * pProb, TotalProb = 0.0, ProbThis, Probs[6] = {0.0};
720     int i, nNodes = 0, nEdges = 0, Counter[6] = {0};
721     pProb = (float *)vProbs->pArray;
722     assert( Vec_IntSize(vProbs) >= Abc_NtkObjNumMax(pNtk) );
723     Abc_NtkForEachObj( pNtk, pObj, i )
724     {
725         if ( !Abc_ObjIsNode(pObj) && !Abc_ObjIsPi(pObj) )
726             continue;
727         nNodes++;
728         nEdges += Abc_ObjFanoutNum(pObj);
729         ProbThis = pProb[i] * Abc_ObjFanoutNum(pObj);
730         TotalProb += ProbThis;
731         assert( pProb[i] >= 0.0 && pProb[i] <= 1.0 );
732         if ( pProb[i] >= 0.5 )
733         {
734             Counter[5]++;
735             Probs[5] += ProbThis;
736         }
737         else if ( pProb[i] >= 0.4 )
738         {
739             Counter[4]++;
740             Probs[4] += ProbThis;
741         }
742         else if ( pProb[i] >= 0.3 )
743         {
744             Counter[3]++;
745             Probs[3] += ProbThis;
746         }
747         else if ( pProb[i] >= 0.2 )
748         {
749             Counter[2]++;
750             Probs[2] += ProbThis;
751         }
752         else if ( pProb[i] >= 0.1 )
753         {
754             Counter[1]++;
755             Probs[1] += ProbThis;
756         }
757         else
758         {
759             Counter[0]++;
760             Probs[0] += ProbThis;
761         }
762     }
763     printf( "Node  distribution: " );
764     for ( i = 0; i < 6; i++ )
765         printf( "n%d%d = %6.2f%%  ", i, i+1, 100.0 * Counter[i]/nNodes );
766     printf( "\n" );
767     printf( "Power distribution: " );
768     for ( i = 0; i < 6; i++ )
769         printf( "p%d%d = %6.2f%%  ", i, i+1, 100.0 * Probs[i]/TotalProb );
770     printf( "\n" );
771     printf( "Total probs = %7.2f. ", TotalProb );
772     printf( "Total edges = %d. ", nEdges );
773     printf( "Average = %7.2f. ", TotalProb / nEdges );
774     printf( "\n" );
775 }
776 
777 /**Function*************************************************************
778 
779   Synopsis    [Determines timing-critical edges of the node.]
780 
781   Description []
782 
783   SideEffects []
784 
785   SeeAlso     []
786 
787 ***********************************************************************/
Abc_NtkPowerCriticalEdges(Abc_Ntk_t * pNtk,Abc_Obj_t * pNode,float Limit,Vec_Int_t * vProbs)788 unsigned Abc_NtkPowerCriticalEdges( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, float Limit, Vec_Int_t * vProbs )
789 {
790     Abc_Obj_t * pFanin;
791     float * pProb = (float *)vProbs->pArray;
792     unsigned uResult = 0;
793     int k;
794     Abc_ObjForEachFanin( pNode, pFanin, k )
795         if ( pProb[pFanin->Id] >= Limit )
796             uResult |= (1 << k);
797     return uResult;
798 }
799 
800 /**Function*************************************************************
801 
802   Synopsis    [Adds choices to speed up the network by the given percentage.]
803 
804   Description []
805 
806   SideEffects []
807 
808   SeeAlso     []
809 
810 ***********************************************************************/
Abc_NtkPowerdown(Abc_Ntk_t * pNtk,int fUseLutLib,int Percentage,int Degree,int fVerbose,int fVeryVerbose)811 Abc_Ntk_t * Abc_NtkPowerdown( Abc_Ntk_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose )
812 {
813     Abc_Ntk_t * pNtkNew;
814     Vec_Int_t * vProbs;
815     Vec_Ptr_t * vTimeCries, * vTimeFanins;
816     Abc_Obj_t * pNode, * pFanin, * pFanin2;
817     float * pProb, Limit;
818     int i, k, k2, Counter, CounterRes, nTimeCris;
819     unsigned * puPCEdges;
820     // compute the limit
821     Limit = 0.5 - (1.0 * Percentage / 100);
822     // perform computation of switching probability
823     vProbs = Abc_NtkPowerEstimate( pNtk, 0 );
824     pProb = (float *)vProbs->pArray;
825     // compute percentage of wires of each type
826     if ( fVerbose )
827         Abc_NtkPowerPrint( pNtk, vProbs );
828     // mark the power critical nodes and edges
829     puPCEdges = ABC_ALLOC( unsigned, Abc_NtkObjNumMax(pNtk) );
830     memset( puPCEdges, 0, sizeof(unsigned) * Abc_NtkObjNumMax(pNtk) );
831     Abc_NtkForEachNode( pNtk, pNode, i )
832     {
833         if ( pProb[pNode->Id] < Limit )
834             continue;
835         puPCEdges[pNode->Id] = Abc_NtkPowerCriticalEdges( pNtk, pNode, Limit, vProbs );
836     }
837 /*
838     if ( fVerbose )
839     {
840         Counter = CounterRes = 0;
841         Abc_NtkForEachNode( pNtk, pNode, i )
842         {
843             Counter += Abc_ObjFaninNum(pNode);
844             CounterRes += Extra_WordCountOnes( puPCEdges[pNode->Id] );
845         }
846         printf( "Edges: Total = %7d. Critical = %7d. Ratio = %4.2f\n",
847             Counter, CounterRes, 1.0*CounterRes/Counter );
848     }
849 */
850     // start the resulting network
851     pNtkNew = Abc_NtkStrash( pNtk, 0, 1, 0 );
852 
853     // collect nodes to be used for resynthesis
854     Counter = CounterRes = 0;
855     vTimeCries = Vec_PtrAlloc( 16 );
856     vTimeFanins = Vec_PtrAlloc( 16 );
857     Abc_NtkForEachNode( pNtk, pNode, i )
858     {
859 //        if ( pProb[pNode->Id] < Limit )
860 //            continue;
861         // count the number of non-PI power-critical nodes
862         nTimeCris = 0;
863         Abc_ObjForEachFanin( pNode, pFanin, k )
864             if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
865                 nTimeCris++;
866         if ( !fVeryVerbose && nTimeCris == 0 )
867             continue;
868         Counter++;
869         // count the total number of power-critical second-generation nodes
870         Vec_PtrClear( vTimeCries );
871         if ( nTimeCris )
872         {
873             Abc_ObjForEachFanin( pNode, pFanin, k )
874                 if ( !Abc_ObjIsCi(pFanin) && (puPCEdges[pNode->Id] & (1<<k)) )
875                     Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
876                         if ( puPCEdges[pFanin->Id] & (1<<k2) )
877                             Vec_PtrPushUnique( vTimeCries, pFanin2 );
878         }
879 //        if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
880         if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) )
881             continue;
882         CounterRes++;
883         // collect second generation nodes
884         Vec_PtrClear( vTimeFanins );
885         Abc_ObjForEachFanin( pNode, pFanin, k )
886         {
887             if ( Abc_ObjIsCi(pFanin) )
888                 Vec_PtrPushUnique( vTimeFanins, pFanin );
889             else
890                 Abc_ObjForEachFanin( pFanin, pFanin2, k2 )
891                     Vec_PtrPushUnique( vTimeFanins, pFanin2 );
892         }
893         // print the results
894         if ( fVeryVerbose )
895         {
896         printf( "%5d Node %5d : %d %2d %2d  ", Counter, pNode->Id,
897             nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) );
898         Abc_ObjForEachFanin( pNode, pFanin, k )
899             printf( "%d(%.2f)%s ", pFanin->Id, pProb[pFanin->Id], (puPCEdges[pNode->Id] & (1<<k))? "*":"" );
900         printf( "\n" );
901         }
902         // add the node to choices
903         if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree )
904             continue;
905         // order the fanins in the increasing order of criticalily
906         if ( Vec_PtrSize(vTimeCries) > 1 )
907         {
908             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
909             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
910 //            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
911             if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
912             {
913                 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
914                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
915             }
916         }
917         if ( Vec_PtrSize(vTimeCries) > 2 )
918         {
919             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
920             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 2 );
921 //            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
922             if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
923             {
924                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 );
925                 Vec_PtrWriteEntry( vTimeCries, 2, pFanin );
926             }
927             pFanin = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 0 );
928             pFanin2 = (Abc_Obj_t *)Vec_PtrEntry( vTimeCries, 1 );
929 //            if ( Abc_ObjSlack(pFanin) < Abc_ObjSlack(pFanin2) )
930             if ( pProb[pFanin->Id] > pProb[pFanin2->Id] )
931             {
932                 Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 );
933                 Vec_PtrWriteEntry( vTimeCries, 1, pFanin );
934             }
935         }
936         // add choice
937         Abc_NtkSpeedupNode( pNtk, pNtkNew, pNode, vTimeFanins, vTimeCries );
938     }
939     Vec_PtrFree( vTimeCries );
940     Vec_PtrFree( vTimeFanins );
941     ABC_FREE( puPCEdges );
942     if ( fVerbose )
943         printf( "Nodes: Total = %7d. Power-critical = %7d. Workable = %7d. Ratio = %4.2f\n",
944             Abc_NtkNodeNum(pNtk), Counter, CounterRes, 1.0*CounterRes/Counter );
945 
946     // remove invalid choice nodes
947     Abc_AigForEachAnd( pNtkNew, pNode, i )
948         if ( pNode->pData )
949         {
950             if ( Abc_ObjFanoutNum((Abc_Obj_t *)pNode->pData) > 0 )
951                 pNode->pData = NULL;
952         }
953 
954     // return the result
955     Vec_IntFree( vProbs );
956     return pNtkNew;
957 }
958 
959 ////////////////////////////////////////////////////////////////////////
960 ///                       END OF FILE                                ///
961 ////////////////////////////////////////////////////////////////////////
962 
963 
964 ABC_NAMESPACE_IMPL_END
965 
966