abc/src/opt/sfm/sfmTim.c - third_party/vtr-verilog-to-routing - Git at Google


            
            /**CFile****************************************************************


              FileName    [sfmTim.c]


              SystemName  [ABC: Logic synthesis and verification system.]


              PackageName [SAT-based optimization using internal don't-cares.]


              Synopsis    [Timing manager.]


              Author      [Alan Mishchenko]


              Affiliation [UC Berkeley]


              Date        [Ver. 1.0. Started - June 20, 2005.]


              Revision    [$Id: sfmTim.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]


            ***********************************************************************/


            #include "sfmInt.h"


            ABC_NAMESPACE_IMPL_START


            ////////////////////////////////////////////////////////////////////////

            
            ///                        DECLARATIONS                              ///

            
            ////////////////////////////////////////////////////////////////////////


            struct Sfm_Tim_t_

            
            {

            
                // external

            
                Mio_Library_t *   pLib;        // library

            
                Scl_Con_t *       pExt;        // external timing

            
                Abc_Ntk_t *       pNtk;        // mapped network

            
                int               Delay;       // the largest delay

            
                int               DeltaCrit;   // critical delay delta

            
                // timing info

            
                Vec_Int_t         vTimArrs;    // arrivals (rise/fall)

            
                Vec_Int_t         vTimReqs;    // required (rise/fall)

            
                // incremental timing

            
                Vec_Wec_t         vLevels;     // levels

            
                // critical path

            
                Vec_Int_t         vPath;       // critical path

            
                Vec_Wrd_t         vSortData;   // node priority order

            
            };


            static inline int * Sfm_TimArrId( Sfm_Tim_t * p, int Id )                    { return Vec_IntEntryP( &p->vTimArrs,  Abc_Var2Lit(Id, 0) );               }

            
            static inline int * Sfm_TimReqId( Sfm_Tim_t * p, int Id )                    { return Vec_IntEntryP( &p->vTimReqs,  Abc_Var2Lit(Id, 0) );               }


            static inline int * Sfm_TimArr( Sfm_Tim_t * p, Abc_Obj_t * pNode )           { return Vec_IntEntryP( &p->vTimArrs,  Abc_Var2Lit(Abc_ObjId(pNode), 0) ); }

            
            static inline int * Sfm_TimReq( Sfm_Tim_t * p, Abc_Obj_t * pNode )           { return Vec_IntEntryP( &p->vTimReqs,  Abc_Var2Lit(Abc_ObjId(pNode), 0) ); }


            static inline int   Sfm_TimArrMaxId( Sfm_Tim_t * p, int Id )                 { int * a = Sfm_TimArrId(p, Id); return Abc_MaxInt(a[0], a[1]);            }


            static inline int   Sfm_TimArrMax( Sfm_Tim_t * p, Abc_Obj_t * pNode )        { int * a = Sfm_TimArr(p, pNode); return Abc_MaxInt(a[0], a[1]);           }

            
            static inline void  Sfm_TimSetReq( Sfm_Tim_t * p, Abc_Obj_t * pNode, int t ) { int * r = Sfm_TimReq(p, pNode); r[0] = r[1] = t;                         }

            
            static inline int   Sfm_TimSlack( Sfm_Tim_t * p, Abc_Obj_t * pNode )         { int * r = Sfm_TimReq(p, pNode), * a = Sfm_TimArr(p, pNode); return Abc_MinInt(r[0]-a[0], r[1]-a[1]); }


            ////////////////////////////////////////////////////////////////////////

            
            ///                     FUNCTION DEFINITIONS                         ///

            
            ////////////////////////////////////////////////////////////////////////


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            static inline void Sfm_TimEdgeArrival( Sfm_Tim_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut )

            
            {

            
                Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin);

            
                int tDelayBlockRise = Scl_Flt2Int(Mio_PinReadDelayBlockRise(pPin));

            
                int tDelayBlockFall = Scl_Flt2Int(Mio_PinReadDelayBlockFall(pPin));

            
                if ( PinPhase != MIO_PHASE_INV )  // NONINV phase is present

            
                {

            
                    pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[0] + tDelayBlockRise );

            
                    pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[1] + tDelayBlockFall );

            
                }

            
                if ( PinPhase != MIO_PHASE_NONINV )  // INV phase is present

            
                {

            
                    pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[1] + tDelayBlockRise );

            
                    pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[0] + tDelayBlockFall );

            
                }

            
            }

            
            static inline void Sfm_TimGateArrival( Sfm_Tim_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut )

            
            {

            
                Mio_Pin_t * pPin;  int i = 0;

            
                pTimeOut[0] = pTimeOut[1] = 0;

            
                Mio_GateForEachPin( pGate, pPin )

            
                    Sfm_TimEdgeArrival( p, pPin, pTimesIn[i++], pTimeOut );

            
                assert( i == Mio_GateReadPinNum(pGate) );

            
            }

            
            static inline void Sfm_TimNodeArrival( Sfm_Tim_t * p, Abc_Obj_t * pNode )

            
            {

            
                int i, iFanin, * pTimesIn[6];

            
                int * pTimeOut = Sfm_TimArr(p, pNode);

            
                assert( Abc_ObjFaninNum(pNode) <= 6 );

            
                Abc_ObjForEachFaninId( pNode, iFanin, i )

            
                    pTimesIn[i] = Sfm_TimArrId( p, iFanin );

            
                Sfm_TimGateArrival( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut );

            
            }


            static inline void Sfm_TimEdgeRequired( Sfm_Tim_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut )

            
            {

            
                Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin);

            
                int tDelayBlockRise = Scl_Flt2Int(Mio_PinReadDelayBlockRise(pPin));

            
                int tDelayBlockFall = Scl_Flt2Int(Mio_PinReadDelayBlockFall(pPin));

            
                if ( PinPhase != MIO_PHASE_INV )  // NONINV phase is present

            
                {

            
                    pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[0] - tDelayBlockRise );

            
                    pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[1] - tDelayBlockFall );

            
                }

            
                if ( PinPhase != MIO_PHASE_NONINV )  // INV phase is present

            
                {

            
                    pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[1] - tDelayBlockRise );

            
                    pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[0] - tDelayBlockFall );

            
                }

            
            }

            
            static inline void Sfm_TimGateRequired( Sfm_Tim_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut )

            
            {

            
                Mio_Pin_t * pPin;  int i = 0;

            
                Mio_GateForEachPin( pGate, pPin )

            
                    Sfm_TimEdgeRequired( p, pPin, pTimesIn[i++], pTimeOut );

            
                assert( i == Mio_GateReadPinNum(pGate) );

            
            }

            
            void Sfm_TimNodeRequired( Sfm_Tim_t * p, Abc_Obj_t * pNode )

            
            {

            
                int i, iFanin, * pTimesIn[6];

            
                int * pTimeOut = Sfm_TimReq(p, pNode);

            
                assert( Abc_ObjFaninNum(pNode) <= 6 );

            
                Abc_ObjForEachFaninId( pNode, iFanin, i )

            
                    pTimesIn[i] = Sfm_TimReqId( p, iFanin );

            
                Sfm_TimGateRequired( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut );

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            void Sfm_TimCriticalPath_int( Sfm_Tim_t * p, Abc_Obj_t * pObj, Vec_Int_t * vPath, int SlackMax )

            
            {

            
                Abc_Obj_t * pNext; int i;

            
                if ( Abc_NodeIsTravIdCurrent( pObj ) )

            
                    return;

            
                Abc_NodeSetTravIdCurrent( pObj );

            
                assert( Abc_ObjIsNode(pObj) );

            
                Abc_ObjForEachFanin( pObj, pNext, i )

            
                {

            
                    if ( Abc_ObjIsCi(pNext) || Abc_ObjFaninNum(pNext) == 0 )

            
                        continue;

            
                    assert( Abc_ObjIsNode(pNext) );

            
                    if ( Sfm_TimSlack(p, pNext) <= SlackMax )

            
                        Sfm_TimCriticalPath_int( p, pNext, vPath, SlackMax );

            
                }

            
                if ( Abc_ObjFaninNum(pObj) > 0 )

            
                    Vec_IntPush( vPath, Abc_ObjId(pObj) );

            
            }

            
            int Sfm_TimCriticalPath( Sfm_Tim_t * p, int Window )

            
            {

            
                int i, SlackMax = p->Delay * Window / 100;

            
                Abc_Obj_t * pObj, * pNext;

            
                Vec_IntClear( &p->vPath );

            
                Abc_NtkIncrementTravId( p->pNtk );

            
                Abc_NtkForEachCo( p->pNtk, pObj, i )

            
                {

            
                    pNext = Abc_ObjFanin0(pObj);

            
                    if ( Abc_ObjIsCi(pNext) || Abc_ObjFaninNum(pNext) == 0 )

            
                        continue;

            
                    assert( Abc_ObjIsNode(pNext) );

            
                    if ( Sfm_TimSlack(p, pNext) <= SlackMax )

            
                        Sfm_TimCriticalPath_int( p, pNext, &p->vPath, SlackMax );

            
                }

            
                return Vec_IntSize(&p->vPath);

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            int Sfm_TimTrace( Sfm_Tim_t * p )

            
            {

            
                Abc_Obj_t * pObj; int i, Delay = 0;

            
                Vec_Ptr_t * vNodes = Abc_NtkDfs( p->pNtk, 1 );

            
                Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )

            
                    Sfm_TimNodeArrival( p, pObj );

            
                Abc_NtkForEachCo( p->pNtk, pObj, i )

            
                    Delay = Abc_MaxInt( Delay, Sfm_TimArrMax(p, Abc_ObjFanin0(pObj)) );

            
                Vec_IntFill( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), ABC_INFINITY );

            
                Abc_NtkForEachCo( p->pNtk, pObj, i )

            
                    Sfm_TimSetReq( p, Abc_ObjFanin0(pObj), Delay );

            
                Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i )

            
                    Sfm_TimNodeRequired( p, pObj );

            
                Vec_PtrFree( vNodes );

            
                return Delay;

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            Sfm_Tim_t * Sfm_TimStart( Mio_Library_t * pLib, Scl_Con_t * pExt, Abc_Ntk_t * pNtk, int DeltaCrit )

            
            {

            
                Sfm_Tim_t * p = ABC_CALLOC( Sfm_Tim_t, 1 );

            
                p->pLib = pLib;

            
                p->pExt = pExt;

            
                p->pNtk = pNtk;

            
                Vec_IntFill( &p->vTimArrs,  3*Abc_NtkObjNumMax(pNtk), 0 );

            
                Vec_IntFill( &p->vTimReqs,  3*Abc_NtkObjNumMax(pNtk), 0 );

            
                p->Delay = Sfm_TimTrace( p );

            
                assert( DeltaCrit > 0 && DeltaCrit < Scl_Flt2Int(1000.0) );

            
                p->DeltaCrit = DeltaCrit;

            
                return p;

            
            }

            
            void Sfm_TimStop( Sfm_Tim_t * p )

            
            {

            
                Vec_IntErase( &p->vTimArrs );

            
                Vec_IntErase( &p->vTimReqs );

            
                Vec_WecErase( &p->vLevels );

            
                Vec_IntErase( &p->vPath );

            
                Vec_WrdErase( &p->vSortData );

            
                ABC_FREE( p );

            
            }

            
            int Sfm_TimReadNtkDelay( Sfm_Tim_t * p )

            
            {

            
                return p->Delay;

            
            }

            
            int Sfm_TimReadObjDelay( Sfm_Tim_t * p, int iObj )

            
            {

            
                return Sfm_TimArrMaxId(p, iObj);

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            void Sfm_TimTest( Abc_Ntk_t * pNtk )

            
            {

            
                Mio_Library_t * pLib = (Mio_Library_t *)pNtk->pManFunc;

            
                Sfm_Tim_t * p = Sfm_TimStart( pLib, NULL, pNtk, 100 );

            
                printf( "Max delay = %.2f.  Path = %d (%d).\n", Scl_Int2Flt(p->Delay), Sfm_TimCriticalPath(p, 1), Abc_NtkNodeNum(p->pNtk) );

            
                Sfm_TimStop( p );

            
            }


            /**Function*************************************************************


              Synopsis    [Levelized structure.]


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            static inline void Sfm_TimUpdateClean( Sfm_Tim_t * p )

            
            {

            
                Vec_Int_t * vLevel;

            
                Abc_Obj_t * pObj;

            
                int i, k;

            
                Vec_WecForEachLevel( &p->vLevels, vLevel, i )

            
                {

            
                    Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k )

            
                    {

            
                        assert( pObj->fMarkC == 1 );

            
                        pObj->fMarkC = 0;

            
                    }

            
                    Vec_IntClear( vLevel );

            
                }

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            void Sfm_TimUpdateTiming( Sfm_Tim_t * p, Vec_Int_t * vTimeNodes )

            
            {

            
                assert( Vec_IntSize(vTimeNodes) > 0 && Vec_IntSize(vTimeNodes) <= 2 );

            
                Vec_IntFillExtra( &p->vTimArrs, 2*Abc_NtkObjNumMax(p->pNtk), 0 );

            
                Vec_IntFillExtra( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), 0 );

            
                p->Delay = Sfm_TimTrace( p );

            
            }


            /**Function*************************************************************


              Synopsis    [Sort an array of nodes using their max arrival times.]


              Description [Returns the number of new divisor nodes.]


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            int Sfm_TimSortArrayByArrival( Sfm_Tim_t * p, Vec_Int_t * vNodes, int iPivot )

            
            {

            
                word Entry;

            
                int i, Id, Time, nDivNew = -1;

            
                int MaxDelay = ABC_INFINITY/2+Sfm_TimArrMaxId(p, iPivot);

            
                assert( p->DeltaCrit > 0 );

            
                // collect nodes

            
                Vec_WrdClear( &p->vSortData );

            
                Vec_IntForEachEntry( vNodes, Id, i )

            
                {

            
                    Time = Sfm_TimArrMaxId( p, Id );

            
                    assert( -ABC_INFINITY/2 < Time && Time < ABC_INFINITY/2 );

            
                    Vec_WrdPush( &p->vSortData, ((word)Id << 32) | (ABC_INFINITY/2+Time) );

            
                }

            
                // sort nodes by delay

            
                Abc_QuickSort3( Vec_WrdArray(&p->vSortData), Vec_WrdSize(&p->vSortData), 0 );

            
                // collect sorted nodes and find place where divisors end

            
                Vec_IntClear( vNodes );

            
                Vec_WrdForEachEntry( &p->vSortData, Entry, i )

            
                {

            
                    Vec_IntPush( vNodes, (int)(Entry >> 32) );

            
                    if ( nDivNew == -1 && ((int)Entry) + p->DeltaCrit > MaxDelay )

            
                        nDivNew = i;

            
                }

            
                return nDivNew;

            
            }


            /**Function*************************************************************


              Synopsis    [Priority of nodes to try remapping for delay.]


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            int Sfm_TimPriorityNodes( Sfm_Tim_t * p, Vec_Int_t * vCands, int Window )

            
            {

            
                Vec_Int_t * vLevel;

            
                Abc_Obj_t * pObj;

            
                int i, k;

            
                assert( Window >= 0 && Window <= 100 );

            
                // collect critical path

            
                Sfm_TimCriticalPath( p, Window );

            
                // add nodes to the levelized structure

            
                Sfm_TimUpdateClean( p );

            
                Abc_NtkForEachObjVec( &p->vPath, p->pNtk, pObj, i )

            
                {

            
                    assert( pObj->fMarkC == 0 );

            
                    pObj->fMarkC = 1;

            
                    Vec_WecPush( &p->vLevels, Abc_ObjLevel(pObj), Abc_ObjId(pObj) );

            
                }

            
                // prioritize nodes by expected gain

            
                Vec_WecSort( &p->vLevels, 0 );

            
                Vec_IntClear( vCands );

            
                Vec_WecForEachLevel( &p->vLevels, vLevel, i )

            
                    Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k )

            
                        if ( !pObj->fMarkA )

            
                            Vec_IntPush( vCands, Abc_ObjId(pObj) );

            
            //    printf( "Path = %5d   Cand = %5d\n", Vec_IntSize(&p->vPath) );

            
                return Vec_IntSize(vCands) > 0;

            
            }


            /**Function*************************************************************


              Synopsis    [Returns 1 if node is relatively non-critical compared to the pivot.]


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            int Sfm_TimNodeIsNonCritical( Sfm_Tim_t * p, Abc_Obj_t * pPivot, Abc_Obj_t * pNode )

            
            {

            
                return Sfm_TimArrMax(p, pNode) + p->DeltaCrit <= Sfm_TimArrMax(p, pPivot);

            
            }


            /**Function*************************************************************


              Synopsis    []


              Description []


              SideEffects []


              SeeAlso     []


            ***********************************************************************/

            
            int Sfm_TimEvalRemapping( Sfm_Tim_t * p, Vec_Int_t * vFanins, Vec_Int_t * vMap, Mio_Gate_t * pGate1, char * pFans1, Mio_Gate_t * pGate2, char * pFans2 )

            
            {

            
                int TimeOut[2][2];

            
                int * pTimesIn1[6], * pTimesIn2[6];

            
                int i, nFanins1, nFanins2;

            
                // process the first gate

            
                nFanins1 = Mio_GateReadPinNum( pGate1 );

            
                for ( i = 0; i < nFanins1; i++ )

            
                    pTimesIn1[i] = Sfm_TimArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans1[i])) );

            
                Sfm_TimGateArrival( p, pGate1, pTimesIn1, TimeOut[0] );

            
                if ( pGate2 == NULL )

            
                    return Abc_MaxInt(TimeOut[0][0], TimeOut[0][1]);

            
                // process the second gate

            
                nFanins2 = Mio_GateReadPinNum( pGate2 );

            
                for ( i = 0; i < nFanins2; i++ )

            
                    if ( (int)pFans2[i] == 16 )

            
                        pTimesIn2[i] = TimeOut[0];

            
                    else

            
                        pTimesIn2[i] = Sfm_TimArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans2[i])) );

            
                Sfm_TimGateArrival( p, pGate2, pTimesIn2, TimeOut[1] );

            
                return Abc_MaxInt(TimeOut[1][0], TimeOut[1][1]);

            
            }


            ////////////////////////////////////////////////////////////////////////

            
            ///                       END OF FILE                                ///

            
            ////////////////////////////////////////////////////////////////////////


            ABC_NAMESPACE_IMPL_END
	/CFile**************************************************************

	FileName [sfmTim.c]

	SystemName [ABC: Logic synthesis and verification system.]

	PackageName [SAT-based optimization using internal don't-cares.]

	Synopsis [Timing manager.]

	Author [Alan Mishchenko]

	Affiliation [UC Berkeley]

	Date [Ver. 1.0. Started - June 20, 2005.]

	Revision [$Id: sfmTim.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

	***********************************************************************/

	#include "sfmInt.h"

	ABC_NAMESPACE_IMPL_START


	////////////////////////////////////////////////////////////////////////
	/// DECLARATIONS ///
	////////////////////////////////////////////////////////////////////////

	struct Sfm_Tim_t_
	{
	// external
	Mio_Library_t * pLib; // library
	Scl_Con_t * pExt; // external timing
	Abc_Ntk_t * pNtk; // mapped network
	int Delay; // the largest delay
	int DeltaCrit; // critical delay delta
	// timing info
	Vec_Int_t vTimArrs; // arrivals (rise/fall)
	Vec_Int_t vTimReqs; // required (rise/fall)
	// incremental timing
	Vec_Wec_t vLevels; // levels
	// critical path
	Vec_Int_t vPath; // critical path
	Vec_Wrd_t vSortData; // node priority order
	};

	static inline int * Sfm_TimArrId( Sfm_Tim_t * p, int Id ) { return Vec_IntEntryP( &p->vTimArrs, Abc_Var2Lit(Id, 0) ); }
	static inline int * Sfm_TimReqId( Sfm_Tim_t * p, int Id ) { return Vec_IntEntryP( &p->vTimReqs, Abc_Var2Lit(Id, 0) ); }

	static inline int * Sfm_TimArr( Sfm_Tim_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimArrs, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); }
	static inline int * Sfm_TimReq( Sfm_Tim_t * p, Abc_Obj_t * pNode ) { return Vec_IntEntryP( &p->vTimReqs, Abc_Var2Lit(Abc_ObjId(pNode), 0) ); }

	static inline int Sfm_TimArrMaxId( Sfm_Tim_t * p, int Id ) { int * a = Sfm_TimArrId(p, Id); return Abc_MaxInt(a[0], a[1]); }

	static inline int Sfm_TimArrMax( Sfm_Tim_t * p, Abc_Obj_t * pNode ) { int * a = Sfm_TimArr(p, pNode); return Abc_MaxInt(a[0], a[1]); }
	static inline void Sfm_TimSetReq( Sfm_Tim_t * p, Abc_Obj_t * pNode, int t ) { int * r = Sfm_TimReq(p, pNode); r[0] = r[1] = t; }
	static inline int Sfm_TimSlack( Sfm_Tim_t * p, Abc_Obj_t * pNode ) { int * r = Sfm_TimReq(p, pNode), * a = Sfm_TimArr(p, pNode); return Abc_MinInt(r[0]-a[0], r[1]-a[1]); }

	////////////////////////////////////////////////////////////////////////
	/// FUNCTION DEFINITIONS ///
	////////////////////////////////////////////////////////////////////////

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	static inline void Sfm_TimEdgeArrival( Sfm_Tim_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut )
	{
	Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin);
	int tDelayBlockRise = Scl_Flt2Int(Mio_PinReadDelayBlockRise(pPin));
	int tDelayBlockFall = Scl_Flt2Int(Mio_PinReadDelayBlockFall(pPin));
	if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present
	{
	pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[0] + tDelayBlockRise );
	pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[1] + tDelayBlockFall );
	}
	if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present
	{
	pTimeOut[0] = Abc_MaxInt( pTimeOut[0], pTimeIn[1] + tDelayBlockRise );
	pTimeOut[1] = Abc_MaxInt( pTimeOut[1], pTimeIn[0] + tDelayBlockFall );
	}
	}
	static inline void Sfm_TimGateArrival( Sfm_Tim_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut )
	{
	Mio_Pin_t * pPin; int i = 0;
	pTimeOut[0] = pTimeOut[1] = 0;
	Mio_GateForEachPin( pGate, pPin )
	Sfm_TimEdgeArrival( p, pPin, pTimesIn[i++], pTimeOut );
	assert( i == Mio_GateReadPinNum(pGate) );
	}
	static inline void Sfm_TimNodeArrival( Sfm_Tim_t * p, Abc_Obj_t * pNode )
	{
	int i, iFanin, * pTimesIn[6];
	int * pTimeOut = Sfm_TimArr(p, pNode);
	assert( Abc_ObjFaninNum(pNode) <= 6 );
	Abc_ObjForEachFaninId( pNode, iFanin, i )
	pTimesIn[i] = Sfm_TimArrId( p, iFanin );
	Sfm_TimGateArrival( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut );
	}

	static inline void Sfm_TimEdgeRequired( Sfm_Tim_t * p, Mio_Pin_t * pPin, int * pTimeIn, int * pTimeOut )
	{
	Mio_PinPhase_t PinPhase = Mio_PinReadPhase(pPin);
	int tDelayBlockRise = Scl_Flt2Int(Mio_PinReadDelayBlockRise(pPin));
	int tDelayBlockFall = Scl_Flt2Int(Mio_PinReadDelayBlockFall(pPin));
	if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present
	{
	pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[0] - tDelayBlockRise );
	pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[1] - tDelayBlockFall );
	}
	if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present
	{
	pTimeIn[0] = Abc_MinInt( pTimeIn[0], pTimeOut[1] - tDelayBlockRise );
	pTimeIn[1] = Abc_MinInt( pTimeIn[1], pTimeOut[0] - tDelayBlockFall );
	}
	}
	static inline void Sfm_TimGateRequired( Sfm_Tim_t * p, Mio_Gate_t * pGate, int ** pTimesIn, int * pTimeOut )
	{
	Mio_Pin_t * pPin; int i = 0;
	Mio_GateForEachPin( pGate, pPin )
	Sfm_TimEdgeRequired( p, pPin, pTimesIn[i++], pTimeOut );
	assert( i == Mio_GateReadPinNum(pGate) );
	}
	void Sfm_TimNodeRequired( Sfm_Tim_t * p, Abc_Obj_t * pNode )
	{
	int i, iFanin, * pTimesIn[6];
	int * pTimeOut = Sfm_TimReq(p, pNode);
	assert( Abc_ObjFaninNum(pNode) <= 6 );
	Abc_ObjForEachFaninId( pNode, iFanin, i )
	pTimesIn[i] = Sfm_TimReqId( p, iFanin );
	Sfm_TimGateRequired( p, (Mio_Gate_t *)pNode->pData, pTimesIn, pTimeOut );
	}


	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	void Sfm_TimCriticalPath_int( Sfm_Tim_t * p, Abc_Obj_t * pObj, Vec_Int_t * vPath, int SlackMax )
	{
	Abc_Obj_t * pNext; int i;
	if ( Abc_NodeIsTravIdCurrent( pObj ) )
	return;
	Abc_NodeSetTravIdCurrent( pObj );
	assert( Abc_ObjIsNode(pObj) );
	Abc_ObjForEachFanin( pObj, pNext, i )
	{
	if ( Abc_ObjIsCi(pNext) \|\| Abc_ObjFaninNum(pNext) == 0 )
	continue;
	assert( Abc_ObjIsNode(pNext) );
	if ( Sfm_TimSlack(p, pNext) <= SlackMax )
	Sfm_TimCriticalPath_int( p, pNext, vPath, SlackMax );
	}
	if ( Abc_ObjFaninNum(pObj) > 0 )
	Vec_IntPush( vPath, Abc_ObjId(pObj) );
	}
	int Sfm_TimCriticalPath( Sfm_Tim_t * p, int Window )
	{
	int i, SlackMax = p->Delay * Window / 100;
	Abc_Obj_t * pObj, * pNext;
	Vec_IntClear( &p->vPath );
	Abc_NtkIncrementTravId( p->pNtk );
	Abc_NtkForEachCo( p->pNtk, pObj, i )
	{
	pNext = Abc_ObjFanin0(pObj);
	if ( Abc_ObjIsCi(pNext) \|\| Abc_ObjFaninNum(pNext) == 0 )
	continue;
	assert( Abc_ObjIsNode(pNext) );
	if ( Sfm_TimSlack(p, pNext) <= SlackMax )
	Sfm_TimCriticalPath_int( p, pNext, &p->vPath, SlackMax );
	}
	return Vec_IntSize(&p->vPath);
	}

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	int Sfm_TimTrace( Sfm_Tim_t * p )
	{
	Abc_Obj_t * pObj; int i, Delay = 0;
	Vec_Ptr_t * vNodes = Abc_NtkDfs( p->pNtk, 1 );
	Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
	Sfm_TimNodeArrival( p, pObj );
	Abc_NtkForEachCo( p->pNtk, pObj, i )
	Delay = Abc_MaxInt( Delay, Sfm_TimArrMax(p, Abc_ObjFanin0(pObj)) );
	Vec_IntFill( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), ABC_INFINITY );
	Abc_NtkForEachCo( p->pNtk, pObj, i )
	Sfm_TimSetReq( p, Abc_ObjFanin0(pObj), Delay );
	Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i )
	Sfm_TimNodeRequired( p, pObj );
	Vec_PtrFree( vNodes );
	return Delay;
	}

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	Sfm_Tim_t * Sfm_TimStart( Mio_Library_t * pLib, Scl_Con_t * pExt, Abc_Ntk_t * pNtk, int DeltaCrit )
	{
	Sfm_Tim_t * p = ABC_CALLOC( Sfm_Tim_t, 1 );
	p->pLib = pLib;
	p->pExt = pExt;
	p->pNtk = pNtk;
	Vec_IntFill( &p->vTimArrs, 3*Abc_NtkObjNumMax(pNtk), 0 );
	Vec_IntFill( &p->vTimReqs, 3*Abc_NtkObjNumMax(pNtk), 0 );
	p->Delay = Sfm_TimTrace( p );
	assert( DeltaCrit > 0 && DeltaCrit < Scl_Flt2Int(1000.0) );
	p->DeltaCrit = DeltaCrit;
	return p;
	}
	void Sfm_TimStop( Sfm_Tim_t * p )
	{
	Vec_IntErase( &p->vTimArrs );
	Vec_IntErase( &p->vTimReqs );
	Vec_WecErase( &p->vLevels );
	Vec_IntErase( &p->vPath );
	Vec_WrdErase( &p->vSortData );
	ABC_FREE( p );
	}
	int Sfm_TimReadNtkDelay( Sfm_Tim_t * p )
	{
	return p->Delay;
	}
	int Sfm_TimReadObjDelay( Sfm_Tim_t * p, int iObj )
	{
	return Sfm_TimArrMaxId(p, iObj);
	}

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	void Sfm_TimTest( Abc_Ntk_t * pNtk )
	{
	Mio_Library_t * pLib = (Mio_Library_t *)pNtk->pManFunc;
	Sfm_Tim_t * p = Sfm_TimStart( pLib, NULL, pNtk, 100 );
	printf( "Max delay = %.2f. Path = %d (%d).\n", Scl_Int2Flt(p->Delay), Sfm_TimCriticalPath(p, 1), Abc_NtkNodeNum(p->pNtk) );
	Sfm_TimStop( p );
	}

	/Function***********************************************************

	Synopsis [Levelized structure.]

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	static inline void Sfm_TimUpdateClean( Sfm_Tim_t * p )
	{
	Vec_Int_t * vLevel;
	Abc_Obj_t * pObj;
	int i, k;
	Vec_WecForEachLevel( &p->vLevels, vLevel, i )
	{
	Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k )
	{
	assert( pObj->fMarkC == 1 );
	pObj->fMarkC = 0;
	}
	Vec_IntClear( vLevel );
	}
	}

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	void Sfm_TimUpdateTiming( Sfm_Tim_t * p, Vec_Int_t * vTimeNodes )
	{
	assert( Vec_IntSize(vTimeNodes) > 0 && Vec_IntSize(vTimeNodes) <= 2 );
	Vec_IntFillExtra( &p->vTimArrs, 2*Abc_NtkObjNumMax(p->pNtk), 0 );
	Vec_IntFillExtra( &p->vTimReqs, 2*Abc_NtkObjNumMax(p->pNtk), 0 );
	p->Delay = Sfm_TimTrace( p );
	}

	/Function***********************************************************

	Synopsis [Sort an array of nodes using their max arrival times.]

	Description [Returns the number of new divisor nodes.]

	SideEffects []

	SeeAlso []

	***********************************************************************/
	int Sfm_TimSortArrayByArrival( Sfm_Tim_t * p, Vec_Int_t * vNodes, int iPivot )
	{
	word Entry;
	int i, Id, Time, nDivNew = -1;
	int MaxDelay = ABC_INFINITY/2+Sfm_TimArrMaxId(p, iPivot);
	assert( p->DeltaCrit > 0 );
	// collect nodes
	Vec_WrdClear( &p->vSortData );
	Vec_IntForEachEntry( vNodes, Id, i )
	{
	Time = Sfm_TimArrMaxId( p, Id );
	assert( -ABC_INFINITY/2 < Time && Time < ABC_INFINITY/2 );
	Vec_WrdPush( &p->vSortData, ((word)Id << 32) \| (ABC_INFINITY/2+Time) );
	}
	// sort nodes by delay
	Abc_QuickSort3( Vec_WrdArray(&p->vSortData), Vec_WrdSize(&p->vSortData), 0 );
	// collect sorted nodes and find place where divisors end
	Vec_IntClear( vNodes );
	Vec_WrdForEachEntry( &p->vSortData, Entry, i )
	{
	Vec_IntPush( vNodes, (int)(Entry >> 32) );
	if ( nDivNew == -1 && ((int)Entry) + p->DeltaCrit > MaxDelay )
	nDivNew = i;
	}
	return nDivNew;
	}

	/Function***********************************************************

	Synopsis [Priority of nodes to try remapping for delay.]

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	int Sfm_TimPriorityNodes( Sfm_Tim_t * p, Vec_Int_t * vCands, int Window )
	{
	Vec_Int_t * vLevel;
	Abc_Obj_t * pObj;
	int i, k;
	assert( Window >= 0 && Window <= 100 );
	// collect critical path
	Sfm_TimCriticalPath( p, Window );
	// add nodes to the levelized structure
	Sfm_TimUpdateClean( p );
	Abc_NtkForEachObjVec( &p->vPath, p->pNtk, pObj, i )
	{
	assert( pObj->fMarkC == 0 );
	pObj->fMarkC = 1;
	Vec_WecPush( &p->vLevels, Abc_ObjLevel(pObj), Abc_ObjId(pObj) );
	}
	// prioritize nodes by expected gain
	Vec_WecSort( &p->vLevels, 0 );
	Vec_IntClear( vCands );
	Vec_WecForEachLevel( &p->vLevels, vLevel, i )
	Abc_NtkForEachObjVec( vLevel, p->pNtk, pObj, k )
	if ( !pObj->fMarkA )
	Vec_IntPush( vCands, Abc_ObjId(pObj) );
	// printf( "Path = %5d Cand = %5d\n", Vec_IntSize(&p->vPath) );
	return Vec_IntSize(vCands) > 0;
	}

	/Function***********************************************************

	Synopsis [Returns 1 if node is relatively non-critical compared to the pivot.]

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	int Sfm_TimNodeIsNonCritical( Sfm_Tim_t * p, Abc_Obj_t * pPivot, Abc_Obj_t * pNode )
	{
	return Sfm_TimArrMax(p, pNode) + p->DeltaCrit <= Sfm_TimArrMax(p, pPivot);
	}

	/Function***********************************************************

	Synopsis []

	Description []

	SideEffects []

	SeeAlso []

	***********************************************************************/
	int Sfm_TimEvalRemapping( Sfm_Tim_t * p, Vec_Int_t * vFanins, Vec_Int_t * vMap, Mio_Gate_t * pGate1, char * pFans1, Mio_Gate_t * pGate2, char * pFans2 )
	{
	int TimeOut[2][2];
	int * pTimesIn1[6], * pTimesIn2[6];
	int i, nFanins1, nFanins2;
	// process the first gate
	nFanins1 = Mio_GateReadPinNum( pGate1 );
	for ( i = 0; i < nFanins1; i++ )
	pTimesIn1[i] = Sfm_TimArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans1[i])) );
	Sfm_TimGateArrival( p, pGate1, pTimesIn1, TimeOut[0] );
	if ( pGate2 == NULL )
	return Abc_MaxInt(TimeOut[0][0], TimeOut[0][1]);
	// process the second gate
	nFanins2 = Mio_GateReadPinNum( pGate2 );
	for ( i = 0; i < nFanins2; i++ )
	if ( (int)pFans2[i] == 16 )
	pTimesIn2[i] = TimeOut[0];
	else
	pTimesIn2[i] = Sfm_TimArrId( p, Vec_IntEntry(vMap, Vec_IntEntry(vFanins, (int)pFans2[i])) );
	Sfm_TimGateArrival( p, pGate2, pTimesIn2, TimeOut[1] );
	return Abc_MaxInt(TimeOut[1][0], TimeOut[1][1]);
	}


	////////////////////////////////////////////////////////////////////////
	/// END OF FILE ///
	////////////////////////////////////////////////////////////////////////


	ABC_NAMESPACE_IMPL_END