1 /**CFile****************************************************************
2 
3   FileName    [abcTiming.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [Network and node package.]
8 
9   Synopsis    [Computation of timing info for mapped circuits.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - June 20, 2005.]
16 
17   Revision    [$Id: abcTiming.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include <math.h>
22 
23 #include "base/abc/abc.h"
24 #include "base/main/main.h"
25 #include "map/mio/mio.h"
26 
27 ABC_NAMESPACE_IMPL_START
28 
29 
30 ////////////////////////////////////////////////////////////////////////
31 ///                        DECLARATIONS                              ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 struct Abc_ManTime_t_
35 {
36     Abc_Time_t     tArrDef;
37     Abc_Time_t     tReqDef;
38     Vec_Ptr_t  *   vArrs;
39     Vec_Ptr_t  *   vReqs;
40     Abc_Time_t     tInDriveDef;
41     Abc_Time_t     tOutLoadDef;
42     Abc_Time_t *   tInDrive;
43     Abc_Time_t *   tOutLoad;
44 };
45 
46 #define TOLERANCE 0.001
47 
Abc_FloatEqual(float x,float y)48 static inline int          Abc_FloatEqual( float x, float y )     { return fabs(x-y) < TOLERANCE; }
49 
50 // static functions
51 static Abc_ManTime_t *     Abc_ManTimeStart( Abc_Ntk_t * pNtk );
52 static void                Abc_ManTimeExpand( Abc_ManTime_t * p, int nSize, int fProgressive );
53 
54 // accessing the arrival and required times of a node
Abc_NodeArrival(Abc_Obj_t * pNode)55 static inline Abc_Time_t * Abc_NodeArrival( Abc_Obj_t * pNode )  {  return (Abc_Time_t *)pNode->pNtk->pManTime->vArrs->pArray[pNode->Id];  }
Abc_NodeRequired(Abc_Obj_t * pNode)56 static inline Abc_Time_t * Abc_NodeRequired( Abc_Obj_t * pNode ) {  return (Abc_Time_t *)pNode->pNtk->pManTime->vReqs->pArray[pNode->Id];  }
57 
58 ////////////////////////////////////////////////////////////////////////
59 ///                     FUNCTION DEFINITIONS                         ///
60 ////////////////////////////////////////////////////////////////////////
61 
62 /**Function*************************************************************
63 
64   Synopsis    [Reads the arrival.required time of the node.]
65 
66   Description []
67 
68   SideEffects []
69 
70   SeeAlso     []
71 
72 ***********************************************************************/
Abc_NtkReadDefaultArrival(Abc_Ntk_t * pNtk)73 Abc_Time_t * Abc_NtkReadDefaultArrival( Abc_Ntk_t * pNtk )
74 {
75     assert( pNtk->pManTime );
76     return &pNtk->pManTime->tArrDef;
77 }
Abc_NtkReadDefaultRequired(Abc_Ntk_t * pNtk)78 Abc_Time_t * Abc_NtkReadDefaultRequired( Abc_Ntk_t * pNtk )
79 {
80     assert( pNtk->pManTime );
81     return &pNtk->pManTime->tReqDef;
82 }
Abc_NodeReadArrival(Abc_Obj_t * pNode)83 Abc_Time_t * Abc_NodeReadArrival( Abc_Obj_t * pNode )
84 {
85     assert( pNode->pNtk->pManTime );
86     return Abc_NodeArrival(pNode);
87 }
Abc_NodeReadRequired(Abc_Obj_t * pNode)88 Abc_Time_t * Abc_NodeReadRequired( Abc_Obj_t * pNode )
89 {
90     assert( pNode->pNtk->pManTime );
91     return Abc_NodeRequired(pNode);
92 }
Abc_NtkReadDefaultArrivalWorst(Abc_Ntk_t * pNtk)93 float Abc_NtkReadDefaultArrivalWorst( Abc_Ntk_t * pNtk )
94 {
95     return 0.5 * pNtk->pManTime->tArrDef.Rise + 0.5 * pNtk->pManTime->tArrDef.Fall;
96 }
Abc_NtkReadDefaultRequiredWorst(Abc_Ntk_t * pNtk)97 float Abc_NtkReadDefaultRequiredWorst( Abc_Ntk_t * pNtk )
98 {
99     return 0.5 * pNtk->pManTime->tReqDef.Rise + 0.5 * pNtk->pManTime->tReqDef.Fall;
100 }
Abc_NodeReadArrivalAve(Abc_Obj_t * pNode)101 float Abc_NodeReadArrivalAve( Abc_Obj_t * pNode )
102 {
103     return 0.5 * Abc_NodeArrival(pNode)->Rise + 0.5 * Abc_NodeArrival(pNode)->Fall;
104 }
Abc_NodeReadRequiredAve(Abc_Obj_t * pNode)105 float Abc_NodeReadRequiredAve( Abc_Obj_t * pNode )
106 {
107     return 0.5 * Abc_NodeReadRequired(pNode)->Rise + 0.5 * Abc_NodeReadRequired(pNode)->Fall;
108 }
Abc_NodeReadArrivalWorst(Abc_Obj_t * pNode)109 float Abc_NodeReadArrivalWorst( Abc_Obj_t * pNode )
110 {
111     return Abc_MaxFloat( Abc_NodeArrival(pNode)->Rise, Abc_NodeArrival(pNode)->Fall );
112 }
Abc_NodeReadRequiredWorst(Abc_Obj_t * pNode)113 float Abc_NodeReadRequiredWorst( Abc_Obj_t * pNode )
114 {
115     return Abc_MinFloat( Abc_NodeReadRequired(pNode)->Rise, Abc_NodeReadRequired(pNode)->Fall );
116 }
117 
118 /**Function*************************************************************
119 
120   Synopsis    [Reads the input drive / output load of the node.]
121 
122   Description []
123 
124   SideEffects []
125 
126   SeeAlso     []
127 
128 ***********************************************************************/
Abc_NtkReadDefaultInputDrive(Abc_Ntk_t * pNtk)129 Abc_Time_t * Abc_NtkReadDefaultInputDrive( Abc_Ntk_t * pNtk )
130 {
131     assert( pNtk->pManTime );
132     return &pNtk->pManTime->tInDriveDef;
133 }
Abc_NtkReadDefaultOutputLoad(Abc_Ntk_t * pNtk)134 Abc_Time_t * Abc_NtkReadDefaultOutputLoad( Abc_Ntk_t * pNtk )
135 {
136     assert( pNtk->pManTime );
137     return &pNtk->pManTime->tOutLoadDef;
138 }
Abc_NodeReadInputDrive(Abc_Ntk_t * pNtk,int iPi)139 Abc_Time_t * Abc_NodeReadInputDrive( Abc_Ntk_t * pNtk, int iPi )
140 {
141     assert( pNtk->pManTime );
142     return pNtk->pManTime->tInDrive ? pNtk->pManTime->tInDrive + iPi : NULL;
143 }
Abc_NodeReadOutputLoad(Abc_Ntk_t * pNtk,int iPo)144 Abc_Time_t * Abc_NodeReadOutputLoad( Abc_Ntk_t * pNtk, int iPo )
145 {
146     assert( pNtk->pManTime );
147     return pNtk->pManTime->tOutLoad ? pNtk->pManTime->tOutLoad + iPo : NULL;
148 }
Abc_NodeReadInputDriveWorst(Abc_Ntk_t * pNtk,int iPi)149 float Abc_NodeReadInputDriveWorst( Abc_Ntk_t * pNtk, int iPi )
150 {
151     return Abc_MaxFloat( Abc_NodeReadInputDrive(pNtk, iPi)->Rise, Abc_NodeReadInputDrive(pNtk, iPi)->Fall );
152 }
Abc_NodeReadOutputLoadWorst(Abc_Ntk_t * pNtk,int iPo)153 float Abc_NodeReadOutputLoadWorst( Abc_Ntk_t * pNtk, int iPo )
154 {
155     return Abc_MaxFloat( Abc_NodeReadOutputLoad(pNtk, iPo)->Rise, Abc_NodeReadOutputLoad(pNtk, iPo)->Fall );
156 }
157 
158 /**Function*************************************************************
159 
160   Synopsis    [Sets the default arrival time for the network.]
161 
162   Description [Please note that .default_input_arrival and
163   .default_output_required should precede .input_arrival and
164   .output required. Otherwise, an overwrite may happen.]
165 
166   SideEffects []
167 
168   SeeAlso     []
169 
170 ***********************************************************************/
Abc_NtkTimeSetDefaultArrival(Abc_Ntk_t * pNtk,float Rise,float Fall)171 void Abc_NtkTimeSetDefaultArrival( Abc_Ntk_t * pNtk, float Rise, float Fall )
172 {
173     Abc_Obj_t * pObj; int i;
174     if ( pNtk->pManTime == NULL )
175         pNtk->pManTime = Abc_ManTimeStart(pNtk);
176     pNtk->pManTime->tArrDef.Rise  = Rise;
177     pNtk->pManTime->tArrDef.Fall  = Fall;
178     // set the arrival times for each input
179     Abc_NtkForEachCi( pNtk, pObj, i )
180         Abc_NtkTimeSetArrival( pNtk, Abc_ObjId(pObj), Rise, Fall );
181 }
Abc_NtkTimeSetDefaultRequired(Abc_Ntk_t * pNtk,float Rise,float Fall)182 void Abc_NtkTimeSetDefaultRequired( Abc_Ntk_t * pNtk, float Rise, float Fall )
183 {
184     Abc_Obj_t * pObj; int i;
185     if ( pNtk->pManTime == NULL )
186         pNtk->pManTime = Abc_ManTimeStart(pNtk);
187     pNtk->pManTime->tReqDef.Rise  = Rise;
188     pNtk->pManTime->tReqDef.Fall  = Fall;
189     // set the required times for each output
190     Abc_NtkForEachCo( pNtk, pObj, i )
191         Abc_NtkTimeSetRequired( pNtk, Abc_ObjId(pObj), Rise, Fall );
192 }
193 
194 /**Function*************************************************************
195 
196   Synopsis    [Sets the arrival time for an object.]
197 
198   Description []
199 
200   SideEffects []
201 
202   SeeAlso     []
203 
204 ***********************************************************************/
Abc_NtkTimeSetArrival(Abc_Ntk_t * pNtk,int ObjId,float Rise,float Fall)205 void Abc_NtkTimeSetArrival( Abc_Ntk_t * pNtk, int ObjId, float Rise, float Fall )
206 {
207     Vec_Ptr_t * vTimes;
208     Abc_Time_t * pTime;
209     if ( pNtk->pManTime == NULL )
210         pNtk->pManTime = Abc_ManTimeStart(pNtk);
211     Abc_ManTimeExpand( pNtk->pManTime, ObjId + 1, 1 );
212     // set the arrival time
213     vTimes = pNtk->pManTime->vArrs;
214     pTime = (Abc_Time_t *)vTimes->pArray[ObjId];
215     pTime->Rise  = Rise;
216     pTime->Fall  = Fall;
217 }
Abc_NtkTimeSetRequired(Abc_Ntk_t * pNtk,int ObjId,float Rise,float Fall)218 void Abc_NtkTimeSetRequired( Abc_Ntk_t * pNtk, int ObjId, float Rise, float Fall )
219 {
220     Vec_Ptr_t * vTimes;
221     Abc_Time_t * pTime;
222     if ( pNtk->pManTime == NULL )
223         pNtk->pManTime = Abc_ManTimeStart(pNtk);
224     Abc_ManTimeExpand( pNtk->pManTime, ObjId + 1, 1 );
225     // set the required time
226     vTimes = pNtk->pManTime->vReqs;
227     pTime = (Abc_Time_t *)vTimes->pArray[ObjId];
228     pTime->Rise  = Rise;
229     pTime->Fall  = Fall;
230 }
231 
232 /**Function*************************************************************
233 
234   Synopsis    [Sets the default arrival time for the network.]
235 
236   Description []
237 
238   SideEffects []
239 
240   SeeAlso     []
241 
242 ***********************************************************************/
Abc_NtkTimeSetDefaultInputDrive(Abc_Ntk_t * pNtk,float Rise,float Fall)243 void Abc_NtkTimeSetDefaultInputDrive( Abc_Ntk_t * pNtk, float Rise, float Fall )
244 {
245 //    if ( Rise == 0.0 && Fall == 0.0 )
246 //        return;
247     if ( pNtk->pManTime == NULL )
248         pNtk->pManTime = Abc_ManTimeStart(pNtk);
249     pNtk->pManTime->tInDriveDef.Rise  = Rise;
250     pNtk->pManTime->tInDriveDef.Fall  = Fall;
251     if ( pNtk->pManTime->tInDrive != NULL )
252     {
253         int i;
254         for ( i = 0; i < Abc_NtkCiNum(pNtk); i++ )
255             if ( pNtk->pManTime->tInDrive[i].Rise == 0 && pNtk->pManTime->tInDrive[i].Fall == 0 )
256                 pNtk->pManTime->tInDrive[i] = pNtk->pManTime->tInDriveDef;
257     }
258 }
Abc_NtkTimeSetDefaultOutputLoad(Abc_Ntk_t * pNtk,float Rise,float Fall)259 void Abc_NtkTimeSetDefaultOutputLoad( Abc_Ntk_t * pNtk, float Rise, float Fall )
260 {
261 //    if ( Rise == 0.0 && Fall == 0.0 )
262 //        return;
263     if ( pNtk->pManTime == NULL )
264         pNtk->pManTime = Abc_ManTimeStart(pNtk);
265     pNtk->pManTime->tOutLoadDef.Rise  = Rise;
266     pNtk->pManTime->tOutLoadDef.Fall  = Fall;
267     if ( pNtk->pManTime->tOutLoad != NULL )
268     {
269         int i;
270         for ( i = 0; i < Abc_NtkCoNum(pNtk); i++ )
271             if ( pNtk->pManTime->tOutLoad[i].Rise == 0 && pNtk->pManTime->tOutLoad[i].Fall == 0 )
272                 pNtk->pManTime->tOutLoad[i] = pNtk->pManTime->tOutLoadDef;
273     }
274 }
275 
276 /**Function*************************************************************
277 
278   Synopsis    [Sets the arrival time for an object.]
279 
280   Description []
281 
282   SideEffects []
283 
284   SeeAlso     []
285 
286 ***********************************************************************/
Abc_NtkTimeSetInputDrive(Abc_Ntk_t * pNtk,int PiNum,float Rise,float Fall)287 void Abc_NtkTimeSetInputDrive( Abc_Ntk_t * pNtk, int PiNum, float Rise, float Fall )
288 {
289     Abc_Time_t * pTime;
290     assert( PiNum >= 0 && PiNum < Abc_NtkCiNum(pNtk) );
291     if ( pNtk->pManTime == NULL )
292         pNtk->pManTime = Abc_ManTimeStart(pNtk);
293     if ( pNtk->pManTime->tInDriveDef.Rise == Rise && pNtk->pManTime->tInDriveDef.Fall == Fall )
294         return;
295     if ( pNtk->pManTime->tInDrive == NULL )
296     {
297         int i;
298         pNtk->pManTime->tInDrive = ABC_CALLOC( Abc_Time_t, Abc_NtkCiNum(pNtk) );
299         for ( i = 0; i < Abc_NtkCiNum(pNtk); i++ )
300             pNtk->pManTime->tInDrive[i] = pNtk->pManTime->tInDriveDef;
301     }
302     pTime = pNtk->pManTime->tInDrive + PiNum;
303     pTime->Rise  = Rise;
304     pTime->Fall  = Fall;
305 }
Abc_NtkTimeSetOutputLoad(Abc_Ntk_t * pNtk,int PoNum,float Rise,float Fall)306 void Abc_NtkTimeSetOutputLoad( Abc_Ntk_t * pNtk, int PoNum, float Rise, float Fall )
307 {
308     Abc_Time_t * pTime;
309     assert( PoNum >= 0 && PoNum < Abc_NtkCoNum(pNtk) );
310     if ( pNtk->pManTime == NULL )
311         pNtk->pManTime = Abc_ManTimeStart(pNtk);
312     if ( pNtk->pManTime->tOutLoadDef.Rise == Rise && pNtk->pManTime->tOutLoadDef.Fall == Fall )
313         return;
314     if ( pNtk->pManTime->tOutLoad == NULL )
315     {
316         int i;
317         pNtk->pManTime->tOutLoad = ABC_CALLOC( Abc_Time_t, Abc_NtkCoNum(pNtk) );
318         for ( i = 0; i < Abc_NtkCoNum(pNtk); i++ )
319             pNtk->pManTime->tOutLoad[i] = pNtk->pManTime->tOutLoadDef;
320     }
321     pTime = pNtk->pManTime->tOutLoad + PoNum;
322     pTime->Rise  = Rise;
323     pTime->Fall  = Fall;
324 }
325 
326 /**Function*************************************************************
327 
328   Synopsis    [Finalizes the timing manager after setting arr/req times.]
329 
330   Description []
331 
332   SideEffects []
333 
334   SeeAlso     []
335 
336 ***********************************************************************/
Abc_NtkTimeInitialize(Abc_Ntk_t * pNtk,Abc_Ntk_t * pNtkOld)337 void Abc_NtkTimeInitialize( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkOld )
338 {
339     Abc_Obj_t * pObj;
340     Abc_Time_t ** ppTimes;
341     int i;
342     assert( pNtkOld == NULL || pNtkOld->pManTime != NULL );
343     assert( pNtkOld == NULL || Abc_NtkCiNum(pNtk) == Abc_NtkCiNum(pNtkOld) );
344     assert( pNtkOld == NULL || Abc_NtkCoNum(pNtk) == Abc_NtkCoNum(pNtkOld) );
345     if ( pNtk->pManTime == NULL )
346         return;
347     // create timing manager with default values
348     Abc_ManTimeExpand( pNtk->pManTime, Abc_NtkObjNumMax(pNtk), 0 );
349     // set global defaults from pNtkOld
350     if ( pNtkOld )
351     {
352         pNtk->pManTime->tArrDef = pNtkOld->pManTime->tArrDef;
353         pNtk->pManTime->tReqDef = pNtkOld->pManTime->tReqDef;
354         pNtk->AndGateDelay = pNtkOld->AndGateDelay;
355     }
356     // set the default timing for CI and COs
357     ppTimes = (Abc_Time_t **)pNtk->pManTime->vArrs->pArray;
358     Abc_NtkForEachCi( pNtk, pObj, i )
359         *ppTimes[pObj->Id] = pNtkOld ? *Abc_NodeReadArrival(Abc_NtkCi(pNtkOld, i)) : pNtk->pManTime->tArrDef;
360     ppTimes = (Abc_Time_t **)pNtk->pManTime->vReqs->pArray;
361     Abc_NtkForEachCo( pNtk, pObj, i )
362         *ppTimes[pObj->Id] = pNtkOld ? *Abc_NodeReadRequired(Abc_NtkCo(pNtkOld, i)) : pNtk->pManTime->tReqDef;
363 }
364 
365 /**Function*************************************************************
366 
367   Synopsis    [This procedure scales user timing by multiplicative factor.]
368 
369   Description []
370 
371   SideEffects []
372 
373   SeeAlso     []
374 
375 ***********************************************************************/
Abc_NtkTimeScale(Abc_Ntk_t * pNtk,float Scale)376 void Abc_NtkTimeScale( Abc_Ntk_t * pNtk, float Scale )
377 {
378     Abc_Obj_t * pObj;
379     Abc_Time_t ** ppTimes, * pTime;
380     int i;
381     if ( pNtk->pManTime == NULL )
382         return;
383     // arrival
384     pNtk->pManTime->tArrDef.Fall *= Scale;
385     pNtk->pManTime->tArrDef.Rise *= Scale;
386     // departure
387     pNtk->pManTime->tReqDef.Fall *= Scale;
388     pNtk->pManTime->tReqDef.Rise *= Scale;
389     // set the default timing
390     ppTimes = (Abc_Time_t **)pNtk->pManTime->vArrs->pArray;
391     Abc_NtkForEachCi( pNtk, pObj, i )
392     {
393         pTime = ppTimes[pObj->Id];
394         pTime->Fall *= Scale;
395         pTime->Rise *= Scale;
396     }
397     // set the default timing
398     ppTimes = (Abc_Time_t **)pNtk->pManTime->vReqs->pArray;
399     Abc_NtkForEachCo( pNtk, pObj, i )
400     {
401         pTime = ppTimes[pObj->Id];
402         pTime->Fall *= Scale;
403         pTime->Rise *= Scale;
404     }
405 }
406 
407 /**Function*************************************************************
408 
409   Synopsis    [Prepares the timing manager for delay trace.]
410 
411   Description []
412 
413   SideEffects []
414 
415   SeeAlso     []
416 
417 ***********************************************************************/
Abc_NtkTimePrepare(Abc_Ntk_t * pNtk)418 void Abc_NtkTimePrepare( Abc_Ntk_t * pNtk )
419 {
420     Abc_Obj_t * pObj;
421     Abc_Time_t ** ppTimes, * pTime;
422     int i;
423     // if there is no timing manager, allocate and initialize
424     if ( pNtk->pManTime == NULL )
425     {
426         pNtk->pManTime = Abc_ManTimeStart(pNtk);
427         Abc_NtkTimeInitialize( pNtk, NULL );
428         return;
429     }
430     // if timing manager is given, expand it if necessary
431     Abc_ManTimeExpand( pNtk->pManTime, Abc_NtkObjNumMax(pNtk), 0 );
432     // clean arrivals except for PIs
433     ppTimes = (Abc_Time_t **)pNtk->pManTime->vArrs->pArray;
434     Abc_NtkForEachNode( pNtk, pObj, i )
435     {
436         pTime = ppTimes[pObj->Id];
437         pTime->Fall = pTime->Rise = Abc_ObjFaninNum(pObj) ? -ABC_INFINITY : 0; // set contant node arrivals to zero
438     }
439     Abc_NtkForEachCo( pNtk, pObj, i )
440     {
441         pTime = ppTimes[pObj->Id];
442         pTime->Fall = pTime->Rise = -ABC_INFINITY;
443     }
444     // clean required except for POs
445     ppTimes = (Abc_Time_t **)pNtk->pManTime->vReqs->pArray;
446     Abc_NtkForEachNode( pNtk, pObj, i )
447     {
448         pTime = ppTimes[pObj->Id];
449         pTime->Fall = pTime->Rise = ABC_INFINITY;
450     }
451     Abc_NtkForEachCi( pNtk, pObj, i )
452     {
453         pTime = ppTimes[pObj->Id];
454         pTime->Fall = pTime->Rise = ABC_INFINITY;
455     }
456 }
457 
458 
459 
460 
461 /**Function*************************************************************
462 
463   Synopsis    []
464 
465   Description []
466 
467   SideEffects []
468 
469   SeeAlso     []
470 
471 ***********************************************************************/
Abc_ManTimeStart(Abc_Ntk_t * pNtk)472 Abc_ManTime_t * Abc_ManTimeStart( Abc_Ntk_t * pNtk )
473 {
474     int fUseZeroDefaultOutputRequired = 1;
475     Abc_ManTime_t * p;
476     Abc_Obj_t * pObj; int i;
477     p = pNtk->pManTime = ABC_ALLOC( Abc_ManTime_t, 1 );
478     memset( p, 0, sizeof(Abc_ManTime_t) );
479     p->vArrs = Vec_PtrAlloc( 0 );
480     p->vReqs = Vec_PtrAlloc( 0 );
481     // set default default input=arrivals (assumed to be 0)
482     // set default default output-requireds (can be either 0 or +infinity, based on the flag)
483     p->tReqDef.Rise = fUseZeroDefaultOutputRequired ? 0 : ABC_INFINITY;
484     p->tReqDef.Fall = fUseZeroDefaultOutputRequired ? 0 : ABC_INFINITY;
485     // extend manager
486     Abc_ManTimeExpand( p, Abc_NtkObjNumMax(pNtk) + 1, 0 );
487     // set the default timing for CIs
488     Abc_NtkForEachCi( pNtk, pObj, i )
489         Abc_NtkTimeSetArrival( pNtk, Abc_ObjId(pObj), p->tArrDef.Rise, p->tArrDef.Rise );
490     // set the default timing for COs
491     Abc_NtkForEachCo( pNtk, pObj, i )
492         Abc_NtkTimeSetRequired( pNtk, Abc_ObjId(pObj), p->tReqDef.Rise, p->tReqDef.Rise );
493     return p;
494 }
495 
496 /**Function*************************************************************
497 
498   Synopsis    []
499 
500   Description []
501 
502   SideEffects []
503 
504   SeeAlso     []
505 
506 ***********************************************************************/
Abc_ManTimeStop(Abc_ManTime_t * p)507 void Abc_ManTimeStop( Abc_ManTime_t * p )
508 {
509     if ( p->tInDrive )
510         ABC_FREE( p->tInDrive );
511     if ( p->tOutLoad )
512         ABC_FREE( p->tOutLoad );
513     if ( Vec_PtrSize(p->vArrs) > 0 )
514         ABC_FREE( p->vArrs->pArray[0] );
515     Vec_PtrFree( p->vArrs );
516     if ( Vec_PtrSize(p->vReqs) > 0 )
517         ABC_FREE( p->vReqs->pArray[0] );
518     Vec_PtrFree( p->vReqs );
519     ABC_FREE( p );
520 }
521 
522 /**Function*************************************************************
523 
524   Synopsis    [Duplicates the timing manager with the PI/PO timing info.]
525 
526   Description [The PIs/POs of the new network should be allocated.]
527 
528   SideEffects []
529 
530   SeeAlso     []
531 
532 ***********************************************************************/
Abc_ManTimeDup(Abc_Ntk_t * pNtkOld,Abc_Ntk_t * pNtkNew)533 void Abc_ManTimeDup( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew )
534 {
535     extern void Abc_NtkTimePrint( Abc_Ntk_t * pNtk );
536 
537     Abc_Obj_t * pObj;
538     Abc_Time_t ** ppTimesOld, ** ppTimesNew;
539     int i;
540     if ( pNtkOld->pManTime == NULL )
541         return;
542     assert( Abc_NtkCiNum(pNtkOld) == Abc_NtkCiNum(pNtkNew) );
543     assert( Abc_NtkCoNum(pNtkOld) == Abc_NtkCoNum(pNtkNew) );
544     assert( Abc_NtkLatchNum(pNtkOld) == Abc_NtkLatchNum(pNtkNew) );
545     // create the new timing manager
546     pNtkNew->pManTime = Abc_ManTimeStart(pNtkNew);
547     Abc_ManTimeExpand( pNtkNew->pManTime, Abc_NtkObjNumMax(pNtkNew), 0 );
548     // set the default timing
549     pNtkNew->pManTime->tArrDef = pNtkOld->pManTime->tArrDef;
550     pNtkNew->pManTime->tReqDef = pNtkOld->pManTime->tReqDef;
551     // set the CI timing
552     ppTimesOld = (Abc_Time_t **)pNtkOld->pManTime->vArrs->pArray;
553     ppTimesNew = (Abc_Time_t **)pNtkNew->pManTime->vArrs->pArray;
554     Abc_NtkForEachCi( pNtkOld, pObj, i )
555         *ppTimesNew[ Abc_NtkCi(pNtkNew,i)->Id ] = *ppTimesOld[ pObj->Id ];
556     // set the CO timing
557     ppTimesOld = (Abc_Time_t **)pNtkOld->pManTime->vReqs->pArray;
558     ppTimesNew = (Abc_Time_t **)pNtkNew->pManTime->vReqs->pArray;
559     Abc_NtkForEachCo( pNtkOld, pObj, i )
560         *ppTimesNew[ Abc_NtkCo(pNtkNew,i)->Id ] = *ppTimesOld[ pObj->Id ];
561     // duplicate input drive
562     pNtkNew->pManTime->tInDriveDef = pNtkOld->pManTime->tInDriveDef;
563     pNtkNew->pManTime->tOutLoadDef = pNtkOld->pManTime->tOutLoadDef;
564     if ( pNtkOld->pManTime->tInDrive )
565     {
566         pNtkNew->pManTime->tInDrive = ABC_ALLOC( Abc_Time_t, Abc_NtkCiNum(pNtkOld) );
567         memcpy( pNtkNew->pManTime->tInDrive, pNtkOld->pManTime->tInDrive, sizeof(Abc_Time_t) * Abc_NtkCiNum(pNtkOld) );
568     }
569     if ( pNtkOld->pManTime->tOutLoad )
570     {
571         pNtkNew->pManTime->tOutLoad = ABC_ALLOC( Abc_Time_t, Abc_NtkCiNum(pNtkOld) );
572         memcpy( pNtkNew->pManTime->tOutLoad, pNtkOld->pManTime->tOutLoad, sizeof(Abc_Time_t) * Abc_NtkCoNum(pNtkOld) );
573     }
574 }
575 
576 /**Function*************************************************************
577 
578   Synopsis    [Prints out the timing manager.]
579 
580   Description []
581 
582   SideEffects []
583 
584   SeeAlso     []
585 
586 ***********************************************************************/
Abc_NtkTimePrint(Abc_Ntk_t * pNtk)587 void Abc_NtkTimePrint( Abc_Ntk_t * pNtk )
588 {
589     if ( pNtk->pManTime == NULL )
590         printf( "There is no timing manager\n" );
591     else
592     {
593         Abc_Obj_t * pObj; int i;
594         printf( "Default arrival = %8f\n", pNtk->pManTime->tArrDef.Fall );
595         printf( "Default required = %8f\n", pNtk->pManTime->tReqDef.Fall );
596         printf( "Inputs (%d):\n", Abc_NtkCiNum(pNtk) );
597         Abc_NtkForEachCi( pNtk, pObj, i )
598             printf( "%20s   arrival = %8f   required = %8f\n",
599                 Abc_ObjName(pObj),
600                 Abc_NodeReadArrivalWorst(pObj),
601                 Abc_NodeReadRequiredWorst(pObj) );
602         printf( "Outputs (%d):\n", Abc_NtkCoNum(pNtk) );
603         Abc_NtkForEachCo( pNtk, pObj, i )
604             printf( "%20s   arrival = %8f   required = %8f\n",
605                 Abc_ObjName(pObj),
606                 Abc_NodeReadArrivalWorst(pObj),
607                 Abc_NodeReadRequiredWorst(pObj) );
608     }
609 }
610 
611 /**Function*************************************************************
612 
613   Synopsis    [Expends the storage for timing information.]
614 
615   Description []
616 
617   SideEffects []
618 
619   SeeAlso     []
620 
621 ***********************************************************************/
Abc_ManTimeExpand(Abc_ManTime_t * p,int nSize,int fProgressive)622 void Abc_ManTimeExpand( Abc_ManTime_t * p, int nSize, int fProgressive )
623 {
624     Vec_Ptr_t * vTimes;
625     Abc_Time_t * ppTimes, * ppTimesOld, * pTime;
626     int nSizeOld, nSizeNew, i;
627 
628     nSizeOld = p->vArrs->nSize;
629     if ( nSizeOld >= nSize )
630         return;
631     nSizeNew = fProgressive? 2 * nSize : nSize;
632     if ( nSizeNew < 100 )
633         nSizeNew = 100;
634 
635     vTimes = p->vArrs;
636     Vec_PtrGrow( vTimes, nSizeNew );
637     vTimes->nSize = nSizeNew;
638     ppTimesOld = ( nSizeOld == 0 )? NULL : (Abc_Time_t *)vTimes->pArray[0];
639     ppTimes = ABC_REALLOC( Abc_Time_t, ppTimesOld, nSizeNew );
640     for ( i = 0; i < nSizeNew; i++ )
641         vTimes->pArray[i] = ppTimes + i;
642     for ( i = nSizeOld; i < nSizeNew; i++ )
643     {
644         pTime = (Abc_Time_t *)vTimes->pArray[i];
645         pTime->Rise  = -ABC_INFINITY;
646         pTime->Fall  = -ABC_INFINITY;
647     }
648 
649     vTimes = p->vReqs;
650     Vec_PtrGrow( vTimes, nSizeNew );
651     vTimes->nSize = nSizeNew;
652     ppTimesOld = ( nSizeOld == 0 )? NULL : (Abc_Time_t *)vTimes->pArray[0];
653     ppTimes = ABC_REALLOC( Abc_Time_t, ppTimesOld, nSizeNew );
654     for ( i = 0; i < nSizeNew; i++ )
655         vTimes->pArray[i] = ppTimes + i;
656     for ( i = nSizeOld; i < nSizeNew; i++ )
657     {
658         pTime = (Abc_Time_t *)vTimes->pArray[i];
659         pTime->Rise  = ABC_INFINITY;
660         pTime->Fall  = ABC_INFINITY;
661     }
662 }
663 
664 
665 
666 
667 
668 
669 /**Function*************************************************************
670 
671   Synopsis    [Sets the CI node levels according to the arrival info.]
672 
673   Description []
674 
675   SideEffects []
676 
677   SeeAlso     []
678 
679 ***********************************************************************/
Abc_NtkSetNodeLevelsArrival(Abc_Ntk_t * pNtkOld)680 void Abc_NtkSetNodeLevelsArrival( Abc_Ntk_t * pNtkOld )
681 {
682     Abc_Obj_t * pNodeOld, * pNodeNew;
683     float tAndDelay;
684     int i;
685     if ( pNtkOld->pManTime == NULL )
686         return;
687     if ( Abc_FrameReadLibGen() == NULL || Mio_LibraryReadNand2((Mio_Library_t *)Abc_FrameReadLibGen()) == NULL )
688         return;
689     tAndDelay = Mio_LibraryReadDelayNand2Max((Mio_Library_t *)Abc_FrameReadLibGen());
690     Abc_NtkForEachCi( pNtkOld, pNodeOld, i )
691     {
692         pNodeNew = pNodeOld->pCopy;
693         pNodeNew->Level = (int)(Abc_NodeReadArrivalWorst(pNodeOld) / tAndDelay);
694     }
695 }
696 
697 /**Function*************************************************************
698 
699   Synopsis    [Sets the CI node levels according to the arrival info.]
700 
701   Description []
702 
703   SideEffects []
704 
705   SeeAlso     []
706 
707 ***********************************************************************/
Abc_NtkGetCiArrivalTimes(Abc_Ntk_t * pNtk)708 Abc_Time_t * Abc_NtkGetCiArrivalTimes( Abc_Ntk_t * pNtk )
709 {
710     Abc_Time_t * p;
711     Abc_Obj_t * pNode;
712     int i;
713     p = ABC_CALLOC( Abc_Time_t, Abc_NtkCiNum(pNtk) );
714     if ( pNtk->pManTime == NULL )
715         return p;
716     // set the PI arrival times
717     Abc_NtkForEachCi( pNtk, pNode, i )
718         p[i] = *Abc_NodeArrival(pNode);
719     return p;
720 }
Abc_NtkGetCoRequiredTimes(Abc_Ntk_t * pNtk)721 Abc_Time_t * Abc_NtkGetCoRequiredTimes( Abc_Ntk_t * pNtk )
722 {
723     Abc_Time_t * p;
724     Abc_Obj_t * pNode;
725     int i;
726     p = ABC_CALLOC( Abc_Time_t, Abc_NtkCoNum(pNtk) );
727     if ( pNtk->pManTime == NULL )
728         return p;
729     // set the PO required times
730     Abc_NtkForEachCo( pNtk, pNode, i )
731         p[i] = *Abc_NodeRequired(pNode);
732     return p;
733 }
734 
735 
736 /**Function*************************************************************
737 
738   Synopsis    [Sets the CI node levels according to the arrival info.]
739 
740   Description []
741 
742   SideEffects []
743 
744   SeeAlso     []
745 
746 ***********************************************************************/
Abc_NtkGetCiArrivalFloats(Abc_Ntk_t * pNtk)747 float * Abc_NtkGetCiArrivalFloats( Abc_Ntk_t * pNtk )
748 {
749     float * p;
750     Abc_Obj_t * pNode;
751     int i;
752     p = ABC_CALLOC( float, Abc_NtkCiNum(pNtk) );
753     if ( pNtk->pManTime == NULL )
754         return p;
755     // set the PI arrival times
756     Abc_NtkForEachCi( pNtk, pNode, i )
757         p[i] = Abc_NodeReadArrivalWorst(pNode);
758     return p;
759 }
Abc_NtkGetCoRequiredFloats(Abc_Ntk_t * pNtk)760 float * Abc_NtkGetCoRequiredFloats( Abc_Ntk_t * pNtk )
761 {
762     float * p;
763     Abc_Obj_t * pNode;
764     int i;
765     if ( pNtk->pManTime == NULL )
766         return NULL;
767     // set the PO required times
768     p = ABC_CALLOC( float, Abc_NtkCoNum(pNtk) );
769     Abc_NtkForEachCo( pNtk, pNode, i )
770         p[i] = Abc_NodeReadRequiredWorst(pNode);
771     return p;
772 }
773 
774 
775 /**Function*************************************************************
776 
777   Synopsis    []
778 
779   Description []
780 
781   SideEffects []
782 
783   SeeAlso     []
784 
785 ***********************************************************************/
Abc_NtkDelayTraceSlackStart(Abc_Ntk_t * pNtk)786 Vec_Int_t * Abc_NtkDelayTraceSlackStart( Abc_Ntk_t * pNtk )
787 {
788     Vec_Int_t * vSlacks;
789     Abc_Obj_t * pObj;
790     int i, k;
791     vSlacks = Vec_IntAlloc( Abc_NtkObjNumMax(pNtk) + Abc_NtkGetTotalFanins(pNtk) );
792     Vec_IntFill( vSlacks, Abc_NtkObjNumMax(pNtk), -1 );
793     Abc_NtkForEachNode( pNtk, pObj, i )
794     {
795         Vec_IntWriteEntry( vSlacks, i, Vec_IntSize(vSlacks) );
796         for ( k = 0; k < Abc_ObjFaninNum(pObj); k++ )
797             Vec_IntPush( vSlacks, -1 );
798     }
799 //    assert( Abc_MaxInt(16, Vec_IntSize(vSlacks)) == Vec_IntCap(vSlacks) );
800     return vSlacks;
801 }
802 
803 /**Function*************************************************************
804 
805   Synopsis    [Read/write edge slacks.]
806 
807   Description []
808 
809   SideEffects []
810 
811   SeeAlso     []
812 
813 ***********************************************************************/
Abc_NtkDelayTraceSlack(Vec_Int_t * vSlacks,Abc_Obj_t * pObj,int iFanin)814 static inline float Abc_NtkDelayTraceSlack( Vec_Int_t * vSlacks, Abc_Obj_t * pObj, int iFanin )
815 {
816     return Abc_Int2Float( Vec_IntEntry( vSlacks, Vec_IntEntry(vSlacks, Abc_ObjId(pObj)) + iFanin ) );
817 }
Abc_NtkDelayTraceSetSlack(Vec_Int_t * vSlacks,Abc_Obj_t * pObj,int iFanin,float Num)818 static inline void Abc_NtkDelayTraceSetSlack( Vec_Int_t * vSlacks, Abc_Obj_t * pObj, int iFanin, float Num )
819 {
820     Vec_IntWriteEntry( vSlacks, Vec_IntEntry(vSlacks, Abc_ObjId(pObj)) + iFanin, Abc_Float2Int(Num) );
821 }
822 
823 /**Function*************************************************************
824 
825   Synopsis    [Find most-critical path (the path with smallest slacks).]
826 
827   Description []
828 
829   SideEffects []
830 
831   SeeAlso     []
832 
833 ***********************************************************************/
Abc_NtkDelayTraceCritPath_rec(Vec_Int_t * vSlacks,Abc_Obj_t * pNode,Abc_Obj_t * pLeaf,Vec_Int_t * vBest)834 int Abc_NtkDelayTraceCritPath_rec( Vec_Int_t * vSlacks, Abc_Obj_t * pNode, Abc_Obj_t * pLeaf, Vec_Int_t * vBest )
835 {
836     Abc_Obj_t * pFanin, * pFaninBest = NULL;
837     float SlackMin = ABC_INFINITY;  int i;
838     // check primary inputs
839     if ( Abc_ObjIsCi(pNode) )
840         return (pLeaf == NULL || pLeaf == pNode);
841     assert( Abc_ObjIsNode(pNode) );
842     // check visited
843     if ( Abc_NodeIsTravIdCurrent( pNode ) )
844         return Vec_IntEntry(vBest, Abc_ObjId(pNode)) >= 0;
845     Abc_NodeSetTravIdCurrent( pNode );
846     // check the node
847     assert( Abc_ObjIsNode(pNode) );
848     Abc_ObjForEachFanin( pNode, pFanin, i )
849     {
850         if ( !Abc_NtkDelayTraceCritPath_rec( vSlacks, pFanin, pLeaf, vBest ) )
851             continue;
852         if ( pFaninBest == NULL || SlackMin > Abc_NtkDelayTraceSlack(vSlacks, pNode, i) )
853         {
854             pFaninBest = pFanin;
855             SlackMin = Abc_NtkDelayTraceSlack(vSlacks, pNode, i);
856         }
857     }
858     if ( pFaninBest != NULL )
859         Vec_IntWriteEntry( vBest, Abc_ObjId(pNode), Abc_NodeFindFanin(pNode, pFaninBest) );
860     return (pFaninBest != NULL);
861 }
862 
863 /**Function*************************************************************
864 
865   Synopsis    [Find most-critical path (the path with smallest slacks).]
866 
867   Description []
868 
869   SideEffects []
870 
871   SeeAlso     []
872 
873 ***********************************************************************/
Abc_NtkDelayTraceCritPathCollect_rec(Vec_Int_t * vSlacks,Abc_Obj_t * pNode,Vec_Int_t * vBest,Vec_Ptr_t * vPath)874 void Abc_NtkDelayTraceCritPathCollect_rec( Vec_Int_t * vSlacks, Abc_Obj_t * pNode, Vec_Int_t * vBest, Vec_Ptr_t * vPath )
875 {
876     assert( Abc_ObjIsCi(pNode) || Abc_ObjIsNode(pNode) );
877     if ( Abc_ObjIsNode(pNode) )
878     {
879         int iFanin = Vec_IntEntry( vBest, Abc_ObjId(pNode) );
880         assert( iFanin >= 0 );
881         Abc_NtkDelayTraceCritPathCollect_rec( vSlacks, Abc_ObjFanin(pNode, iFanin), vBest, vPath );
882     }
883     Vec_PtrPush( vPath, pNode );
884 }
885 
886 /**Function*************************************************************
887 
888   Synopsis    []
889 
890   Description []
891 
892   SideEffects []
893 
894   SeeAlso     []
895 
896 ***********************************************************************/
Abc_NodeDelayTraceArrival(Abc_Obj_t * pNode,Vec_Int_t * vSlacks)897 void Abc_NodeDelayTraceArrival( Abc_Obj_t * pNode, Vec_Int_t * vSlacks )
898 {
899     Abc_Obj_t * pFanin;
900     Abc_Time_t * pTimeIn, * pTimeOut;
901     float tDelayBlockRise, tDelayBlockFall;
902     Mio_PinPhase_t PinPhase;
903     Mio_Pin_t * pPin;
904     int i;
905 
906     // start the arrival time of the node
907     pTimeOut = Abc_NodeArrival(pNode);
908     pTimeOut->Rise = pTimeOut->Fall = -ABC_INFINITY;
909     // consider the buffer
910     if ( Abc_ObjIsBarBuf(pNode) )
911     {
912         pTimeIn = Abc_NodeArrival(Abc_ObjFanin0(pNode));
913         *pTimeOut = *pTimeIn;
914         return;
915     }
916     // go through the pins of the gate
917     pPin = Mio_GateReadPins((Mio_Gate_t *)pNode->pData);
918     Abc_ObjForEachFanin( pNode, pFanin, i )
919     {
920         pTimeIn = Abc_NodeArrival(pFanin);
921         // get the interesting parameters of this pin
922         PinPhase = Mio_PinReadPhase(pPin);
923         tDelayBlockRise = (float)Mio_PinReadDelayBlockRise( pPin );
924         tDelayBlockFall = (float)Mio_PinReadDelayBlockFall( pPin );
925         // compute the arrival times of the positive phase
926         if ( PinPhase != MIO_PHASE_INV )  // NONINV phase is present
927         {
928             if ( pTimeOut->Rise < pTimeIn->Rise + tDelayBlockRise )
929                 pTimeOut->Rise = pTimeIn->Rise + tDelayBlockRise;
930             if ( pTimeOut->Fall < pTimeIn->Fall + tDelayBlockFall )
931                 pTimeOut->Fall = pTimeIn->Fall + tDelayBlockFall;
932         }
933         if ( PinPhase != MIO_PHASE_NONINV )  // INV phase is present
934         {
935             if ( pTimeOut->Rise < pTimeIn->Fall + tDelayBlockRise )
936                 pTimeOut->Rise = pTimeIn->Fall + tDelayBlockRise;
937             if ( pTimeOut->Fall < pTimeIn->Rise + tDelayBlockFall )
938                 pTimeOut->Fall = pTimeIn->Rise + tDelayBlockFall;
939         }
940         pPin = Mio_PinReadNext(pPin);
941     }
942 
943     // compute edge slacks
944     if ( vSlacks )
945     {
946         float Slack;
947         // go through the pins of the gate
948         pPin = Mio_GateReadPins((Mio_Gate_t *)pNode->pData);
949         Abc_ObjForEachFanin( pNode, pFanin, i )
950         {
951             pTimeIn = Abc_NodeArrival(pFanin);
952             // get the interesting parameters of this pin
953             PinPhase = Mio_PinReadPhase(pPin);
954             tDelayBlockRise = (float)Mio_PinReadDelayBlockRise( pPin );
955             tDelayBlockFall = (float)Mio_PinReadDelayBlockFall( pPin );
956             // compute the arrival times of the positive phase
957             Slack = ABC_INFINITY;
958             if ( PinPhase != MIO_PHASE_INV )  // NONINV phase is present
959             {
960                 Slack = Abc_MinFloat( Slack, Abc_AbsFloat(pTimeIn->Rise + tDelayBlockRise - pTimeOut->Rise) );
961                 Slack = Abc_MinFloat( Slack, Abc_AbsFloat(pTimeIn->Fall + tDelayBlockFall - pTimeOut->Fall) );
962             }
963             if ( PinPhase != MIO_PHASE_NONINV )  // INV phase is present
964             {
965                 Slack = Abc_MinFloat( Slack, Abc_AbsFloat(pTimeIn->Fall + tDelayBlockRise - pTimeOut->Rise) );
966                 Slack = Abc_MinFloat( Slack, Abc_AbsFloat(pTimeIn->Rise + tDelayBlockFall - pTimeOut->Fall) );
967             }
968             pPin = Mio_PinReadNext(pPin);
969             Abc_NtkDelayTraceSetSlack( vSlacks, pNode, i, Slack );
970         }
971     }
972 }
973 
974 
975 /**Function*************************************************************
976 
977   Synopsis    [Performs delay-trace of the network. If input (pIn) or
978   output (pOut) are given, finds the most-timing-critical path between
979   them and prints it to the standard output. If input and/or output are
980   not given, finds the most-critical path in the network and prints it.]
981 
982   Description []
983 
984   SideEffects []
985 
986   SeeAlso     []
987 
988 ***********************************************************************/
Abc_NtkDelayTrace(Abc_Ntk_t * pNtk,Abc_Obj_t * pOut,Abc_Obj_t * pIn,int fPrint)989 float Abc_NtkDelayTrace( Abc_Ntk_t * pNtk, Abc_Obj_t * pOut, Abc_Obj_t * pIn, int fPrint )
990 {
991     Vec_Int_t * vSlacks = NULL;
992     Abc_Obj_t * pNode, * pDriver;
993     Vec_Ptr_t * vNodes;
994     Abc_Time_t * pTime;
995     float tArrivalMax;
996     int i;
997 
998     assert( Abc_NtkIsMappedLogic(pNtk) );
999     assert( pOut == NULL || Abc_ObjIsCo(pOut) );
1000     assert( pIn == NULL || Abc_ObjIsCi(pIn) );
1001 
1002     // create slacks (need slacks if printing is requested even if pIn/pOut are not given)
1003     if ( pOut || pIn || fPrint )
1004         vSlacks = Abc_NtkDelayTraceSlackStart( pNtk );
1005 
1006     // compute the timing
1007     Abc_NtkTimePrepare( pNtk );
1008     vNodes = Abc_NtkDfs( pNtk, 1 );
1009     Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
1010         Abc_NodeDelayTraceArrival( pNode, vSlacks );
1011     Vec_PtrFree( vNodes );
1012 
1013     // get the latest arrival times
1014     tArrivalMax = -ABC_INFINITY;
1015     Abc_NtkForEachCo( pNtk, pNode, i )
1016     {
1017         pDriver = Abc_ObjFanin0(pNode);
1018         pTime   = Abc_NodeArrival(pDriver);
1019         if ( tArrivalMax < Abc_MaxFloat(pTime->Fall, pTime->Rise) )
1020             tArrivalMax = Abc_MaxFloat(pTime->Fall, pTime->Rise);
1021     }
1022 
1023     // determine the output to print
1024     if ( fPrint && pOut == NULL )
1025     {
1026         Abc_NtkForEachCo( pNtk, pNode, i )
1027         {
1028             pDriver = Abc_ObjFanin0(pNode);
1029             pTime   = Abc_NodeArrival(pDriver);
1030             if ( tArrivalMax == Abc_MaxFloat(pTime->Fall, pTime->Rise) )
1031                 pOut = pNode;
1032         }
1033         assert( pOut != NULL );
1034     }
1035 
1036     if ( fPrint )
1037     {
1038         Vec_Ptr_t * vPath = Vec_PtrAlloc( 100 );
1039         Vec_Int_t * vBest = Vec_IntStartFull( Abc_NtkObjNumMax(pNtk) );
1040         // traverse to determine the critical path
1041         Abc_NtkIncrementTravId( pNtk );
1042         if ( !Abc_NtkDelayTraceCritPath_rec( vSlacks, Abc_ObjFanin0(pOut), pIn, vBest ) )
1043         {
1044             if ( pIn == NULL )
1045                 printf( "The logic cone of PO \"%s\" has no primary inputs.\n", Abc_ObjName(pOut) );
1046             else
1047                 printf( "There is no combinational path between PI \"%s\" and PO \"%s\".\n", Abc_ObjName(pIn), Abc_ObjName(pOut) );
1048         }
1049         else
1050         {
1051             float Slack = 0.0, SlackAdd;
1052             int k, iFanin, Length = 0;
1053             Abc_Obj_t * pFanin;
1054             // check the additional slack
1055             SlackAdd = Abc_NodeReadRequiredWorst(pOut) - Abc_NodeReadArrivalWorst(Abc_ObjFanin0(pOut));
1056             // collect the critical path
1057             Abc_NtkDelayTraceCritPathCollect_rec( vSlacks, Abc_ObjFanin0(pOut), vBest, vPath );
1058             if ( pIn == NULL )
1059                 pIn = (Abc_Obj_t *)Vec_PtrEntry( vPath, 0 );
1060             // find the longest gate name
1061             Vec_PtrForEachEntry( Abc_Obj_t *, vPath, pNode, i )
1062                 if ( Abc_ObjIsNode(pNode) )
1063                     Length = Abc_MaxInt( Length, strlen(Mio_GateReadName((Mio_Gate_t *)pNode->pData)) );
1064             // print critical path
1065             Abc_NtkLevel( pNtk );
1066             printf( "Critical path from PI \"%s\" to PO \"%s\":\n", Abc_ObjName(pIn), Abc_ObjName(pOut) );
1067             Vec_PtrForEachEntry( Abc_Obj_t *, vPath, pNode, i )
1068             {
1069                 printf( "Level %3d : ", Abc_ObjLevel(pNode) );
1070                 if ( Abc_ObjIsCi(pNode) )
1071                 {
1072                     printf( "Primary input \"%s\".   ", Abc_ObjName(pNode) );
1073                     printf( "Arrival time =%6.1f. ", Abc_NodeReadArrivalWorst(pNode) );
1074                     printf( "\n" );
1075                     continue;
1076                 }
1077                 if ( Abc_ObjIsCo(pNode) )
1078                 {
1079                     printf( "Primary output \"%s\".   ", Abc_ObjName(pNode) );
1080                     printf( "Arrival =%6.1f. ", Abc_NodeReadArrivalWorst(pNode) );
1081                 }
1082                 else
1083                 {
1084                     assert( Abc_ObjIsNode(pNode) );
1085                     iFanin = Abc_NodeFindFanin( pNode, (Abc_Obj_t *)Vec_PtrEntry(vPath,i-1) );
1086                     Slack = Abc_NtkDelayTraceSlack(vSlacks, pNode, iFanin);
1087                     printf( "%10s/", Abc_ObjName(pNode) );
1088                     printf( "%-4s", Mio_GateReadPinName((Mio_Gate_t *)pNode->pData, iFanin) );
1089                     printf( " (%s)", Mio_GateReadName((Mio_Gate_t *)pNode->pData) );
1090                     for ( k = strlen(Mio_GateReadName((Mio_Gate_t *)pNode->pData)); k < Length; k++ )
1091                         printf( " " );
1092                     printf( "   " );
1093                     printf( "Arrival =%6.1f.   ", Abc_NodeReadArrivalWorst(pNode) );
1094                     printf( "I/O times: (" );
1095                     Abc_ObjForEachFanin( pNode, pFanin, k )
1096                         printf( "%s%.1f", (k? ", ":""), Abc_NodeReadArrivalWorst(pFanin) );
1097 //                    printf( " -> %.1f)", Abc_NodeReadArrival(pNode)->Worst + Slack + SlackAdd );
1098                     printf( " -> %.1f)", Abc_NodeReadArrivalWorst(pNode) );
1099                 }
1100                 printf( "\n" );
1101             }
1102             printf( "Level %3d : ", Abc_ObjLevel(Abc_ObjFanin0(pOut)) + 1 );
1103             printf( "Primary output \"%s\".   ", Abc_ObjName(pOut) );
1104             printf( "Required time = %6.1f.  ", Abc_NodeReadRequiredWorst(pOut) );
1105             printf( "Path slack = %6.1f.\n", SlackAdd );
1106         }
1107         Vec_PtrFree( vPath );
1108         Vec_IntFree( vBest );
1109     }
1110 
1111     Vec_IntFreeP( &vSlacks );
1112     return tArrivalMax;
1113 }
1114 
1115 
1116 
1117 /**Function*************************************************************
1118 
1119   Synopsis    [Computes the level of the node using its fanin levels.]
1120 
1121   Description []
1122 
1123   SideEffects []
1124 
1125   SeeAlso     []
1126 
1127 ***********************************************************************/
Abc_ObjLevelNew(Abc_Obj_t * pObj)1128 int Abc_ObjLevelNew( Abc_Obj_t * pObj )
1129 {
1130     Abc_Obj_t * pFanin;
1131     int i, Level = 0;
1132     Abc_ObjForEachFanin( pObj, pFanin, i )
1133         Level = Abc_MaxFloat( Level, Abc_ObjLevel(pFanin) );
1134     return Level + (int)(Abc_ObjFaninNum(pObj) > 0);
1135 }
1136 
1137 /**Function*************************************************************
1138 
1139   Synopsis    [Computes the reverse level of the node using its fanout levels.]
1140 
1141   Description []
1142 
1143   SideEffects []
1144 
1145   SeeAlso     []
1146 
1147 ***********************************************************************/
Abc_ObjReverseLevelNew(Abc_Obj_t * pObj)1148 int Abc_ObjReverseLevelNew( Abc_Obj_t * pObj )
1149 {
1150     Abc_Obj_t * pFanout;
1151     int i, LevelCur, Level = 0;
1152     Abc_ObjForEachFanout( pObj, pFanout, i )
1153     {
1154         LevelCur = Abc_ObjReverseLevel( pFanout );
1155         Level = Abc_MaxFloat( Level, LevelCur );
1156     }
1157     return Level + 1;
1158 }
1159 
1160 /**Function*************************************************************
1161 
1162   Synopsis    [Returns required level of the node.]
1163 
1164   Description [Converts the reverse levels of the node into its required
1165   level as follows: ReqLevel(Node) = MaxLevels(Ntk) + 1 - LevelR(Node).]
1166 
1167   SideEffects []
1168 
1169   SeeAlso     []
1170 
1171 ***********************************************************************/
Abc_ObjRequiredLevel(Abc_Obj_t * pObj)1172 int Abc_ObjRequiredLevel( Abc_Obj_t * pObj )
1173 {
1174     Abc_Ntk_t * pNtk = pObj->pNtk;
1175     assert( pNtk->vLevelsR );
1176     return pNtk->LevelMax + 1 - Abc_ObjReverseLevel(pObj);
1177 }
1178 
1179 /**Function*************************************************************
1180 
1181   Synopsis    [Returns the reverse level of the node.]
1182 
1183   Description [The reverse level is the level of the node in reverse
1184   topological order, starting from the COs.]
1185 
1186   SideEffects []
1187 
1188   SeeAlso     []
1189 
1190 ***********************************************************************/
Abc_ObjReverseLevel(Abc_Obj_t * pObj)1191 int Abc_ObjReverseLevel( Abc_Obj_t * pObj )
1192 {
1193     Abc_Ntk_t * pNtk = pObj->pNtk;
1194     assert( pNtk->vLevelsR );
1195     Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
1196     return Vec_IntEntry(pNtk->vLevelsR, pObj->Id);
1197 }
1198 
1199 /**Function*************************************************************
1200 
1201   Synopsis    [Sets the reverse level of the node.]
1202 
1203   Description [The reverse level is the level of the node in reverse
1204   topological order, starting from the COs.]
1205 
1206   SideEffects []
1207 
1208   SeeAlso     []
1209 
1210 ***********************************************************************/
Abc_ObjSetReverseLevel(Abc_Obj_t * pObj,int LevelR)1211 void Abc_ObjSetReverseLevel( Abc_Obj_t * pObj, int LevelR )
1212 {
1213     Abc_Ntk_t * pNtk = pObj->pNtk;
1214     assert( pNtk->vLevelsR );
1215     Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
1216     Vec_IntWriteEntry( pNtk->vLevelsR, pObj->Id, LevelR );
1217 }
1218 
1219 /**Function*************************************************************
1220 
1221   Synopsis    [Prepares for the computation of required levels.]
1222 
1223   Description [This procedure should be called before the required times
1224   are used. It starts internal data structures, which records the level
1225   from the COs of the network nodes in reverse topologogical order.]
1226 
1227   SideEffects []
1228 
1229   SeeAlso     []
1230 
1231 ***********************************************************************/
Abc_NtkStartReverseLevels(Abc_Ntk_t * pNtk,int nMaxLevelIncrease)1232 void Abc_NtkStartReverseLevels( Abc_Ntk_t * pNtk, int nMaxLevelIncrease )
1233 {
1234     Vec_Ptr_t * vNodes;
1235     Abc_Obj_t * pObj;
1236     int i;
1237     // remember the maximum number of direct levels
1238     pNtk->LevelMax = Abc_NtkLevel(pNtk) + nMaxLevelIncrease;
1239     // start the reverse levels
1240     pNtk->vLevelsR = Vec_IntAlloc( 0 );
1241     Vec_IntFill( pNtk->vLevelsR, 1 + Abc_NtkObjNumMax(pNtk), 0 );
1242     // compute levels in reverse topological order
1243     vNodes = Abc_NtkDfsReverse( pNtk );
1244     Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
1245         Abc_ObjSetReverseLevel( pObj, Abc_ObjReverseLevelNew(pObj) );
1246     Vec_PtrFree( vNodes );
1247 }
1248 
1249 /**Function*************************************************************
1250 
1251   Synopsis    [Cleans the data structures used to compute required levels.]
1252 
1253   Description []
1254 
1255   SideEffects []
1256 
1257   SeeAlso     []
1258 
1259 ***********************************************************************/
Abc_NtkStopReverseLevels(Abc_Ntk_t * pNtk)1260 void Abc_NtkStopReverseLevels( Abc_Ntk_t * pNtk )
1261 {
1262     assert( pNtk->vLevelsR );
1263     Vec_IntFree( pNtk->vLevelsR );
1264     pNtk->vLevelsR = NULL;
1265     pNtk->LevelMax = 0;
1266 
1267 }
1268 
1269 /**Function*************************************************************
1270 
1271   Synopsis    [Incrementally updates level of the nodes.]
1272 
1273   Description []
1274 
1275   SideEffects []
1276 
1277   SeeAlso     []
1278 
1279 ***********************************************************************/
Abc_NtkUpdateLevel(Abc_Obj_t * pObjNew,Vec_Vec_t * vLevels)1280 void Abc_NtkUpdateLevel( Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
1281 {
1282     Abc_Obj_t * pFanout, * pTemp;
1283     int LevelOld, Lev, k, m;
1284 //    int Counter = 0, CounterMax = 0;
1285     // check if level has changed
1286     LevelOld = Abc_ObjLevel(pObjNew);
1287     if ( LevelOld == Abc_ObjLevelNew(pObjNew) )
1288         return;
1289     // start the data structure for level update
1290     // we cannot fail to visit a node when using this structure because the
1291     // nodes are stored by their _old_ levels, which are assumed to be correct
1292     Vec_VecClear( vLevels );
1293     Vec_VecPush( vLevels, LevelOld, pObjNew );
1294     pObjNew->fMarkA = 1;
1295     // recursively update level
1296     Vec_VecForEachEntryStart( Abc_Obj_t *, vLevels, pTemp, Lev, k, LevelOld )
1297     {
1298 //        Counter--;
1299         pTemp->fMarkA = 0;
1300         assert( Abc_ObjLevel(pTemp) == Lev );
1301         Abc_ObjSetLevel( pTemp, Abc_ObjLevelNew(pTemp) );
1302         // if the level did not change, no need to check the fanout levels
1303         if ( Abc_ObjLevel(pTemp) == Lev )
1304             continue;
1305         // schedule fanout for level update
1306         Abc_ObjForEachFanout( pTemp, pFanout, m )
1307         {
1308             if ( !Abc_ObjIsCo(pFanout) && !pFanout->fMarkA )
1309             {
1310                 assert( Abc_ObjLevel(pFanout) >= Lev );
1311                 Vec_VecPush( vLevels, Abc_ObjLevel(pFanout), pFanout );
1312 //                Counter++;
1313 //                CounterMax = Abc_MaxFloat( CounterMax, Counter );
1314                 pFanout->fMarkA = 1;
1315             }
1316         }
1317     }
1318 //    printf( "%d ", CounterMax );
1319 }
1320 
1321 /**Function*************************************************************
1322 
1323   Synopsis    [Incrementally updates level of the nodes.]
1324 
1325   Description []
1326 
1327   SideEffects []
1328 
1329   SeeAlso     []
1330 
1331 ***********************************************************************/
Abc_NtkUpdateReverseLevel(Abc_Obj_t * pObjNew,Vec_Vec_t * vLevels)1332 void Abc_NtkUpdateReverseLevel( Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
1333 {
1334     Abc_Obj_t * pFanin, * pTemp;
1335     int LevelOld, LevFanin, Lev, k, m;
1336     // check if level has changed
1337     LevelOld = Abc_ObjReverseLevel(pObjNew);
1338     if ( LevelOld == Abc_ObjReverseLevelNew(pObjNew) )
1339         return;
1340     // start the data structure for level update
1341     // we cannot fail to visit a node when using this structure because the
1342     // nodes are stored by their _old_ levels, which are assumed to be correct
1343     Vec_VecClear( vLevels );
1344     Vec_VecPush( vLevels, LevelOld, pObjNew );
1345     pObjNew->fMarkA = 1;
1346     // recursively update level
1347     Vec_VecForEachEntryStart( Abc_Obj_t *, vLevels, pTemp, Lev, k, LevelOld )
1348     {
1349         pTemp->fMarkA = 0;
1350         LevelOld = Abc_ObjReverseLevel(pTemp);
1351         assert( LevelOld == Lev );
1352         Abc_ObjSetReverseLevel( pTemp, Abc_ObjReverseLevelNew(pTemp) );
1353         // if the level did not change, no need to check the fanout levels
1354         if ( Abc_ObjReverseLevel(pTemp) == Lev )
1355             continue;
1356         // schedule fanins for level update
1357         Abc_ObjForEachFanin( pTemp, pFanin, m )
1358         {
1359             if ( !Abc_ObjIsCi(pFanin) && !pFanin->fMarkA )
1360             {
1361                 LevFanin = Abc_ObjReverseLevel( pFanin );
1362                 assert( LevFanin >= Lev );
1363                 Vec_VecPush( vLevels, LevFanin, pFanin );
1364                 pFanin->fMarkA = 1;
1365             }
1366         }
1367     }
1368 }
1369 
1370 /**Function*************************************************************
1371 
1372   Synopsis    [Replaces the node and incrementally updates levels.]
1373 
1374   Description []
1375 
1376   SideEffects []
1377 
1378   SeeAlso     []
1379 
1380 ***********************************************************************/
Abc_NtkUpdate(Abc_Obj_t * pObj,Abc_Obj_t * pObjNew,Vec_Vec_t * vLevels)1381 void Abc_NtkUpdate( Abc_Obj_t * pObj, Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
1382 {
1383     // replace the old node by the new node
1384     pObjNew->Level = pObj->Level;
1385     Abc_ObjReplace( pObj, pObjNew );
1386     // update the level of the node
1387     Abc_NtkUpdateLevel( pObjNew, vLevels );
1388     Abc_ObjSetReverseLevel( pObjNew, 0 );
1389     Abc_NtkUpdateReverseLevel( pObjNew, vLevels );
1390 }
1391 
1392 ////////////////////////////////////////////////////////////////////////
1393 ///                       END OF FILE                                ///
1394 ////////////////////////////////////////////////////////////////////////
1395 
1396 
1397 ABC_NAMESPACE_IMPL_END
1398 
1399