retDelay.c

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

  FileName    [retDelay.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Retiming package.]

  Synopsis    [Incremental retiming for optimum delay.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - Oct 31, 2006.]

  Revision    [$Id: retDelay.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $]

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

#include "retInt.h"

ABC_NAMESPACE_IMPL_START


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

static int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose );
static int Abc_NtkRetimeTiming( Abc_Ntk_t * pNtk, int fForward, Vec_Ptr_t * vCritical );
static int Abc_NtkRetimeTiming_rec( Abc_Obj_t * pObj, int fForward );

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

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

  Synopsis    [Retimes incrementally for minimum delay.]

  Description [This procedure cannot be called in the application code
  because it assumes that the network is preprocessed by removing LIs/LOs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeMinDelay( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkCopy, int nDelayLim, int nIterLimit, int fForward, int fVerbose )
{
    int IterBest, DelayBest;
    int IterBest2, DelayBest2;
    // try to find the best delay iteration on a copy
    DelayBest = Abc_NtkRetimeMinDelayTry( pNtkCopy, nDelayLim, fForward, 0, nIterLimit, &IterBest, fVerbose );
    if ( IterBest == 0 )
        return 1;
    // perform the given number of iterations on the original network
    DelayBest2 = Abc_NtkRetimeMinDelayTry( pNtk, nDelayLim, fForward, 1, IterBest, &IterBest2, fVerbose );
    assert( DelayBest == DelayBest2 );
    assert( IterBest == IterBest2 );
    return 1;
}

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

  Synopsis    [Returns the best delay and the number of best iteration.]

  Description [] 
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeMinDelayTry( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fInitial, int nIterLimit, int * pIterBest, int fVerbose )
{
    Abc_Ntk_t * pNtkNew = NULL;
    Vec_Ptr_t * vCritical;
    Vec_Int_t * vValues = NULL; // Suppress "might be used uninitialized"
    Abc_Obj_t * pObj;
    int i, k, IterBest, DelayCur, DelayBest;
    int DelayStart = -1; // Suppress "might be used uninitialized"
    int LatchesBest;
    // transfer intitial values
    if ( fInitial )
    {
        if ( fForward )
            Abc_NtkRetimeTranferToCopy( pNtk );
        else
        {
            // save initial value of the latches
            vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
            // start the network for initial value computation
            pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
        }
    }

if ( fVerbose && !fInitial )
    printf( "Performing analysis:\n" );
    // find the best iteration
    DelayBest = ABC_INFINITY; IterBest = 0; LatchesBest = Abc_NtkLatchNum(pNtk);
    vCritical = Vec_PtrAlloc( 100 );
    for ( i = 0; ; i++ )
    {
        // perform moves for the timing-critical nodes
        DelayCur = Abc_NtkRetimeTiming( pNtk, fForward, vCritical );
        if ( i == 0 )
            DelayStart = DelayCur;
        // record this position if it has the best delay
        if ( DelayBest > DelayCur )
        {
if ( fVerbose && !fInitial )
    printf( "%s Iter = %3d. Delay = %3d. Latches = %5d. Delta = %6.2f. Ratio = %4.2f %%\n", 
        fForward ? "Fwd": "Bwd", i, DelayCur, Abc_NtkLatchNum(pNtk), 
        1.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/(DelayBest-DelayCur), 
        100.0*(Abc_NtkLatchNum(pNtk)-LatchesBest)/Abc_NtkLatchNum(pNtk)/(DelayBest-DelayCur) );

            DelayBest = DelayCur;
            IterBest = i;
            LatchesBest = Abc_NtkLatchNum(pNtk);
        }
        // quit after timing analysis
        if ( i == nIterLimit )
            break;
        // skip if 10 interations did not give improvement
        if ( i - IterBest > 20 )
            break;
        // skip if delay limit is reached
        if ( nDelayLim > 0 && DelayCur <= nDelayLim )
            break;
        // try retiming to improve the delay
        Vec_PtrForEachEntry( Abc_Obj_t *, vCritical, pObj, k )
            if ( Abc_NtkRetimeNodeIsEnabled(pObj, fForward) )
                Abc_NtkRetimeNode( pObj, fForward, fInitial );
        // share latches
        if ( !fForward )
            Abc_NtkRetimeShareLatches( pNtk, fInitial );    
    }
    Vec_PtrFree( vCritical );
    // transfer the initial state back to the latches
    if ( fInitial )
    {
        if ( fForward )
            Abc_NtkRetimeTranferFromCopy( pNtk );
        else
        {
            Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
            Abc_NtkDelete( pNtkNew );
            Vec_IntFree( vValues );
        }
    }
if ( fVerbose && !fInitial )
    printf( "%s : Starting delay = %3d.  Final delay = %3d.  IterBest = %2d (out of %2d).\n", 
        fForward? "Forward " : "Backward", DelayStart, DelayBest, IterBest, nIterLimit );
    *pIterBest = (nIterLimit == 1) ? 1 : IterBest;
    return DelayBest;
}

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

  Synopsis    [Returns the set of timing-critical nodes.]

  Description [Performs static timing analysis on the network. Uses 
  unit-delay model.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeTiming( Abc_Ntk_t * pNtk, int fForward, Vec_Ptr_t * vCritical )
{
    Vec_Ptr_t * vLatches;
    Abc_Obj_t * pObj, * pNext;
    int i, k, LevelCur, LevelMax = 0;
    // mark all objects except nodes
    Abc_NtkIncrementTravId(pNtk);
    vLatches = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
    Abc_NtkForEachObj( pNtk, pObj, i )
    {
        if ( Abc_ObjIsLatch(pObj) )
            Vec_PtrPush( vLatches, pObj );
        if ( Abc_ObjIsNode(pObj) )
            continue;
        pObj->Level = 0;
        Abc_NodeSetTravIdCurrent( pObj );
    }
    // perform analysis from CIs/COs
    if ( fForward )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
                if ( LevelMax < LevelCur )
                    LevelMax = LevelCur;
            }
        }
        Abc_NtkForEachPi( pNtk, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
                if ( LevelMax < LevelCur )
                    LevelMax = LevelCur;
            }
        }
    }
    else
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
        Abc_NtkForEachPo( pNtk, pObj, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( Abc_ObjFanin0(pObj), fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
    // collect timing critical nodes, which should be retimed forward/backward
    Vec_PtrClear( vCritical );
    Abc_NtkIncrementTravId(pNtk);
    if ( fForward )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                if ( Abc_NodeIsTravIdCurrent(pNext) )
                    continue;
                if ( LevelMax != (int)pNext->Level )
                    continue;
                // new critical node
                Vec_PtrPush( vCritical, pNext );
                Abc_NodeSetTravIdCurrent( pNext );
            }
        }
    }
    else
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vLatches, pObj, i )
        {
            Abc_ObjForEachFanin( pObj, pNext, k )
            {
                if ( Abc_NodeIsTravIdCurrent(pNext) )
                    continue;
                if ( LevelMax != (int)pNext->Level )
                    continue;
                // new critical node
                Vec_PtrPush( vCritical, pNext );
                Abc_NodeSetTravIdCurrent( pNext );
            }
        }
    }
    Vec_PtrFree( vLatches );
    return LevelMax;
}

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

  Synopsis    [Recursively performs timing analysis.]

  Description [Performs static timing analysis on the network. Uses 
  unit-delay model.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeTiming_rec( Abc_Obj_t * pObj, int fForward )
{
    Abc_Obj_t * pNext;
    int i, LevelCur, LevelMax = 0;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return pObj->Level;
    Abc_NodeSetTravIdCurrent(pObj);
    // visit the next nodes
    if ( fForward )
    {
        Abc_ObjForEachFanout( pObj, pNext, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
    else
    {
        Abc_ObjForEachFanin( pObj, pNext, i )
        {
            LevelCur = Abc_NtkRetimeTiming_rec( pNext, fForward );
            if ( LevelMax < LevelCur )
                LevelMax = LevelCur;
        }
    }
//    printf( "Node %3d -> Level %3d.\n", pObj->Id, LevelMax + 1 );
    pObj->Level = LevelMax + 1;
    return pObj->Level;
}

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


ABC_NAMESPACE_IMPL_END