retIncrem.c

Go to the documentation of this file.

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

  FileName    [retIncrem.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Retiming package.]

  Synopsis    [Incremental retiming in one direction.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "retInt.h"

ABC_NAMESPACE_IMPL_START


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

static int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose );

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

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

  Synopsis    [Performs retiming in one direction.]

  Description [Currently does not retime over black boxes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fMinDelay, int fOneStep, int fVerbose )
{
    Abc_Ntk_t * pNtkCopy = NULL;
    Vec_Ptr_t * vBoxes;
    st__table * tLatches;
    int nLatches = Abc_NtkLatchNum(pNtk);
    int nIdMaxStart = Abc_NtkObjNumMax(pNtk);
    int RetValue;
    int nIterLimit = -1; // Suppress "might be used uninitialized"
    if ( Abc_NtkNodeNum(pNtk) == 0 )
        return 0;
    // reorder CI/CO/latch inputs
    Abc_NtkOrderCisCos( pNtk );
    if ( fMinDelay ) 
    {
        nIterLimit = fOneStep? 1 : 2 * Abc_NtkLevel(pNtk);
        pNtkCopy = Abc_NtkDup( pNtk );
        tLatches = Abc_NtkRetimePrepareLatches( pNtkCopy );
        st__free_table( tLatches );
    }
    // collect latches and remove CIs/COs
    tLatches = Abc_NtkRetimePrepareLatches( pNtk );
    // share the latches
    Abc_NtkRetimeShareLatches( pNtk, 0 );    
    // save boxes
    vBoxes = pNtk->vBoxes;  pNtk->vBoxes = NULL;
    // perform the retiming
    if ( fMinDelay )
        Abc_NtkRetimeMinDelay( pNtk, pNtkCopy, nDelayLim, nIterLimit, fForward, fVerbose );
    else
        Abc_NtkRetimeOneWay( pNtk, fForward, fVerbose );
    if ( fMinDelay ) 
        Abc_NtkDelete( pNtkCopy );
    // share the latches
    Abc_NtkRetimeShareLatches( pNtk, 0 );    
    // restore boxes
    pNtk->vBoxes = vBoxes;
    // finalize the latches
    RetValue = Abc_NtkRetimeFinalizeLatches( pNtk, tLatches, nIdMaxStart );
    st__free_table( tLatches );
    if ( RetValue == 0 )
        return 0;
    // fix the COs
//    Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
    // check for correctness
    if ( !Abc_NtkCheck( pNtk ) )
        fprintf( stdout, "Abc_NtkRetimeForward(): Network check has failed.\n" );
    // return the number of latches saved
    return nLatches - Abc_NtkLatchNum(pNtk);
}

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

  Synopsis    [Prepares the network for retiming.]

  Description [Hash latches into their number in the original network.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
 st__table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk )
{
    st__table * tLatches;
    Abc_Obj_t * pLatch, * pLatchIn, * pLatchOut, * pFanin;
    int i, nOffSet = Abc_NtkBoxNum(pNtk) - Abc_NtkLatchNum(pNtk);
    // collect latches and remove CIs/COs
    tLatches = st__init_table( st__ptrcmp, st__ptrhash );
    Abc_NtkForEachLatch( pNtk, pLatch, i )
    {
        // map latch into its true number
        st__insert( tLatches, (char *)(ABC_PTRUINT_T)pLatch, (char *)(ABC_PTRUINT_T)(i-nOffSet) );
        // disconnect LI     
        pLatchIn = Abc_ObjFanin0(pLatch);
        pFanin = Abc_ObjFanin0(pLatchIn);
        Abc_ObjTransferFanout( pLatchIn, pFanin );
        Abc_ObjDeleteFanin( pLatchIn, pFanin );
        // disconnect LO     
        pLatchOut = Abc_ObjFanout0(pLatch);
        pFanin = Abc_ObjFanin0(pLatchOut);
        if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
            Abc_ObjTransferFanout( pLatchOut, pFanin );
        Abc_ObjDeleteFanin( pLatchOut, pFanin );
    }
    return tLatches;
}

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

  Synopsis    [Finalizes the latches after retiming.]

  Description [Reuses the LIs/LOs for old latches.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st__table * tLatches, int nIdMaxStart )
{
    Vec_Ptr_t * vCisOld, * vCosOld, * vBoxesOld, * vCisNew, * vCosNew, * vBoxesNew;
    Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut;
    int i, Index;
    // create new arrays
    vCisOld   = pNtk->vCis;    pNtk->vCis   = NULL;  vCisNew   = Vec_PtrAlloc( 100 );
    vCosOld   = pNtk->vCos;    pNtk->vCos   = NULL;  vCosNew   = Vec_PtrAlloc( 100 );  
    vBoxesOld = pNtk->vBoxes;  pNtk->vBoxes = NULL;  vBoxesNew = Vec_PtrAlloc( 100 );
    // copy boxes and their CIs/COs
    Vec_PtrForEachEntryStop( Abc_Obj_t *, vCisOld, pObj, i, Vec_PtrSize(vCisOld) - st__count(tLatches) )
        Vec_PtrPush( vCisNew, pObj );
    Vec_PtrForEachEntryStop( Abc_Obj_t *, vCosOld, pObj, i, Vec_PtrSize(vCosOld) - st__count(tLatches) )
        Vec_PtrPush( vCosNew, pObj );
    Vec_PtrForEachEntryStop( Abc_Obj_t *, vBoxesOld, pObj, i, Vec_PtrSize(vBoxesOld) - st__count(tLatches) )
        Vec_PtrPush( vBoxesNew, pObj );
    // go through the latches
    Abc_NtkForEachObj( pNtk, pLatch, i )
    {
        if ( !Abc_ObjIsLatch(pLatch) )
            continue;
        if ( Abc_ObjId(pLatch) >= (unsigned)nIdMaxStart )
        {
            // this is a new latch 
            pLatchIn  = Abc_NtkCreateBi(pNtk);
            pLatchOut = Abc_NtkCreateBo(pNtk);
            Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
            Abc_ObjAssignName( pLatchIn,  Abc_ObjName(pLatch), "_in" );
        }
        else
        {
            // this is an old latch 
            // get its number in the original order
            if ( ! st__lookup( tLatches, (char *)pLatch, (char **)&Index ) )
            {
                printf( "Abc_NtkRetimeFinalizeLatches(): Internal error.\n" );
                return 0;
            }
            assert( pLatch == Vec_PtrEntry(vBoxesOld, Vec_PtrSize(vBoxesOld) - st__count(tLatches) + Index) );
            // reconnect with the old LIs/LOs
            pLatchIn  = (Abc_Obj_t *)Vec_PtrEntry( vCosOld, Vec_PtrSize(vCosOld) - st__count(tLatches) + Index );
            pLatchOut = (Abc_Obj_t *)Vec_PtrEntry( vCisOld, Vec_PtrSize(vCisOld) - st__count(tLatches) + Index );
        }
        // connect
        Abc_ObjAddFanin( pLatchIn, Abc_ObjFanin0(pLatch) );
        Abc_ObjPatchFanin( pLatch, Abc_ObjFanin0(pLatch), pLatchIn );
        if ( Abc_ObjFanoutNum(pLatch) > 0 )
            Abc_ObjTransferFanout( pLatch, pLatchOut );
        Abc_ObjAddFanin( pLatchOut, pLatch );
        // add to the arrays
        Vec_PtrPush( vCisNew, pLatchOut );
        Vec_PtrPush( vCosNew, pLatchIn );
        Vec_PtrPush( vBoxesNew, pLatch );
    }
    // free useless Cis/Cos
    Vec_PtrForEachEntry( Abc_Obj_t *, vCisOld, pObj, i )
        if ( !Abc_ObjIsPi(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
            Abc_NtkDeleteObj(pObj);
    Vec_PtrForEachEntry( Abc_Obj_t *, vCosOld, pObj, i )
        if ( !Abc_ObjIsPo(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
            Abc_NtkDeleteObj(pObj);
    // set the new arrays
    pNtk->vCis   = vCisNew;   Vec_PtrFree( vCisOld );
    pNtk->vCos   = vCosNew;   Vec_PtrFree( vCosOld );
    pNtk->vBoxes = vBoxesNew; Vec_PtrFree( vBoxesOld );
    return 1;
}

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

  Synopsis    [Performs retiming one way, forward or backward.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
{
    Abc_Ntk_t * pNtkNew = NULL; // Suppress "might be used uninitialized"
    Vec_Int_t * vValues = NULL; // Suppress "might be used uninitialized"
    Abc_Obj_t * pObj;
    int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 10000;
    if ( fForward )
        Abc_NtkRetimeTranferToCopy( pNtk );
    else
    {
        // save initial values of the latches
        vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
        // start the network for initial value computation
        pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
    }
    // try to move latches forward whenever possible
    do {
        fChanges = 0;
        Abc_NtkForEachObj( pNtk, pObj, i )
        {
            if ( !Abc_ObjIsNode(pObj) )
                continue;
            if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
            {
                Abc_NtkRetimeNode( pObj, fForward, 1 );
                fChanges = 1;
                nTotalMoves++;
                if ( nTotalMoves >= nTotalMovesLimit )
                {
                    printf( "Stopped after %d latch moves.\n", nTotalMoves );
                    break;
                }
            }
        }
    } while ( fChanges && nTotalMoves < nTotalMovesLimit );
    // transfer the initial state back to the latches
    if ( fForward )
        Abc_NtkRetimeTranferFromCopy( pNtk );
    else
    {
        Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
        Abc_NtkDelete( pNtkNew );
        Vec_IntFree( vValues );
    }
    return 0;
}


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

  Synopsis    [Returns 1 if retiming forward/backward is possible.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward )
{
    Abc_Obj_t * pNext;
    int i;
    assert( Abc_ObjIsNode(pObj) );
    if ( fForward )
    {
        Abc_ObjForEachFanin( pObj, pNext, i )
            if ( !Abc_ObjIsLatch(pNext) )
                return 0;
    }
    else
    {
        Abc_ObjForEachFanout( pObj, pNext, i )
            if ( !Abc_ObjIsLatch(pNext) )
                return 0;
    }
    return 1;
}

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

  Synopsis    [Retimes the node backward or forward.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial )
{
    Abc_Ntk_t * pNtkNew = NULL;
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pNext, * pLatch;
    int i;
    vNodes = Vec_PtrAlloc( 10 );
    if ( fForward ) 
    {
        // compute the initial value
        if ( fInitial )
            pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_ObjSopSimulate( pObj );
        // collect fanins
        Abc_NodeCollectFanins( pObj, vNodes );
        // make the node point to the fanins fanins
        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, i )
        {
            assert( Abc_ObjIsLatch(pNext) );
            Abc_ObjPatchFanin( pObj, pNext, Abc_ObjFanin0(pNext) );
            if ( Abc_ObjFanoutNum(pNext) == 0 )
                Abc_NtkDeleteObj(pNext);            
        }
        // add a new latch on top
        pNext = Abc_NtkCreateLatch(pObj->pNtk);
        if ( Abc_ObjFanoutNum(pObj) > 0 )
            Abc_ObjTransferFanout( pObj, pNext );
        Abc_ObjAddFanin( pNext, pObj );
        // set the initial value
        if ( fInitial )
            pNext->pCopy = pObj->pCopy;
    }
    else
    {
        // compute the initial value
        if ( fInitial )
        {
            pNtkNew = Abc_ObjFanout0(pObj)->pCopy->pNtk;
            Abc_NtkDupObj( pNtkNew, pObj, 0 );
            Abc_ObjForEachFanout( pObj, pNext, i )
            {
                assert( Abc_ObjFaninNum(pNext->pCopy) == 0 );
                Abc_ObjAddFanin( pNext->pCopy, pObj->pCopy );
            }
        }
        // collect fanouts
        Abc_NodeCollectFanouts( pObj, vNodes );
        // make the fanouts fanouts point to the node
        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, i )
        {
            assert( Abc_ObjIsLatch(pNext) );
            Abc_ObjTransferFanout( pNext, pObj );
            Abc_NtkDeleteObj( pNext );  
        }
        // add new latches to the fanins
        Abc_ObjForEachFanin( pObj, pNext, i )
        {
            pLatch = Abc_NtkCreateLatch(pObj->pNtk);
            Abc_ObjPatchFanin( pObj, pNext, pLatch );
            Abc_ObjAddFanin( pLatch, pNext );
            // create buffer isomorphic to this latch
            if ( fInitial )
            {
                pLatch->pCopy = Abc_NtkCreateNodeBuf( pNtkNew, NULL );
                Abc_ObjAddFanin( pObj->pCopy, pLatch->pCopy );
            }
        }
    }
    Vec_PtrFree( vNodes );
}

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

  Synopsis    [Returns the number of compatible fanout latches.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRetimeCheckCompatibleLatchFanouts( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pFanout;
    int i, nLatches = 0, Init = -1;
    Abc_ObjForEachFanout( pObj, pFanout, i )
    {
        if ( !Abc_ObjIsLatch(pFanout) )
            continue;
        if ( Init == -1 )
        {
            Init = (int)(ABC_PTRUINT_T)pObj->pData;
            nLatches++;
        }
        else if ( Init == (int)(ABC_PTRUINT_T)pObj->pData )
            nLatches++;
    }
    return nLatches;
}

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

  Synopsis    [Retimes the node backward or forward.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial )
{
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pFanin, * pLatchTop, * pLatchCur;
    int i, k;
    vNodes = Vec_PtrAlloc( 10 );
    // consider latch fanins
    Abc_NtkForEachObj( pNtk, pFanin, i )
    {
        if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 )
            continue;
        // get the first latch
        pLatchTop = NULL;
        Abc_ObjForEachFanout( pFanin, pLatchTop, k )
            if ( Abc_ObjIsLatch(pLatchTop) )
                break;
        assert( pLatchTop && Abc_ObjIsLatch(pLatchTop) );
        // redirect compatible fanout latches to the first latch
        Abc_NodeCollectFanouts( pFanin, vNodes );
        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pLatchCur, k )
        {
            if ( !Abc_ObjIsLatch(pLatchCur) )
                continue;
            if ( pLatchCur == pLatchTop )
                continue;
            if ( pLatchCur->pData != pLatchTop->pData )
                continue;
            // connect the initial state
            if ( fInitial )
                Abc_ObjAddFanin( pLatchCur->pCopy, pLatchTop->pCopy );
            // redirect the fanouts
            Abc_ObjTransferFanout( pLatchCur, pLatchTop );
            Abc_NtkDeleteObj(pLatchCur);
        }
    }
    Vec_PtrFree( vNodes );
}

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


ABC_NAMESPACE_IMPL_END