saigRetFwd.c

Go to the documentation of this file.

 
#include "saig.h"
 
ABC_NAMESPACE_IMPL_START
 

 
static inline Aig_Obj_t * Aig_ObjFanoutStatic( Aig_Obj_t * pObj, int i )               { return ((Aig_Obj_t **)pObj->pData)[i];             }
static inline void        Aig_ObjSetFanoutStatic( Aig_Obj_t * pObj, Aig_Obj_t * pFan ) { ((Aig_Obj_t **)pObj->pData)[pObj->nRefs++] = pFan; }
 
#define Aig_ObjForEachFanoutStatic( pObj, pFan, i )                        \
    for ( i = 0; (i < (int)(pObj)->nRefs) && ((pFan) = Aig_ObjFanoutStatic(pObj, i)); i++ )


Aig_Obj_t ** Aig_ManStaticFanoutStart( Aig_Man_t * p )
{
    Aig_Obj_t ** ppFanouts, * pObj;
    int i, nFanouts, nFanoutsAlloc;
    // allocate fanouts
    nFanoutsAlloc = 2 * Aig_ManObjNumMax(p) - Aig_ManCiNum(p) - Aig_ManCoNum(p);
    ppFanouts = ABC_ALLOC( Aig_Obj_t *, nFanoutsAlloc );
    // mark up storage
    nFanouts = 0;
    Aig_ManForEachObj( p, pObj, i )
    {
        pObj->pData = ppFanouts + nFanouts;
        nFanouts += pObj->nRefs;  
        pObj->nRefs = 0;
    }
    assert( nFanouts < nFanoutsAlloc ); 
    // add fanouts
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( Aig_ObjChild0(pObj) )
            Aig_ObjSetFanoutStatic( Aig_ObjFanin0(pObj), pObj );
        if ( Aig_ObjChild1(pObj) )
            Aig_ObjSetFanoutStatic( Aig_ObjFanin1(pObj), pObj );
    }
    return ppFanouts;
}

void Aig_ManMarkAutonomous_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
{
    Aig_Obj_t * pFanout;
    int i;
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(p, pObj);
    Aig_ObjForEachFanoutStatic( pObj, pFanout, i )
        Aig_ManMarkAutonomous_rec( p, pFanout );
}

void Saig_ManMarkAutonomous( Aig_Man_t * p )
{
    Aig_Obj_t ** ppFanouts;
    Aig_Obj_t * pObj, * pObjLi, * pObjLo;
    int i;
    // temporarily connect register outputs to register inputs
    Saig_ManForEachLiLo( p, pObjLi, pObjLo, i )
    {
        pObjLo->pFanin0 = pObjLi;
        pObjLi->nRefs = 1;
    }
    // mark nodes reachable from Const1 and PIs
    Aig_ManIncrementTravId( p );
    ppFanouts = Aig_ManStaticFanoutStart( p );
    Aig_ManMarkAutonomous_rec( p, Aig_ManConst1(p) );
    Saig_ManForEachPi( p, pObj, i )
        Aig_ManMarkAutonomous_rec( p, pObj );
    ABC_FREE( ppFanouts );
    // disconnect LIs/LOs and label unreachable registers
    Saig_ManForEachLiLo( p, pObjLi, pObjLo, i )
    {
        assert( pObjLo->pFanin0 && pObjLi->nRefs == 1 );
        pObjLo->pFanin0 = NULL;
        pObjLi->nRefs = 0;
    }
}

Aig_Man_t * Saig_ManRetimeForwardOne( Aig_Man_t * p, int * pnRegFixed, int * pnRegMoves )
{
    Aig_Man_t * pNew;
    Vec_Ptr_t * vCut;
    Aig_Obj_t * pObj, * pFanin;
    int i;
    // mark the retimable nodes
    Saig_ManMarkAutonomous( p );
    // mark the retimable registers with the fresh trav ID
    Aig_ManIncrementTravId( p );
    *pnRegFixed = 0;
    Saig_ManForEachLo( p, pObj, i )
        if ( Aig_ObjIsTravIdPrevious(p, pObj) )
            Aig_ObjSetTravIdCurrent(p, pObj);
        else
            (*pnRegFixed)++;
    // mark all the nodes that can be retimed forward
    *pnRegMoves = 0;
    Aig_ManForEachNode( p, pObj, i )
        if ( Aig_ObjIsTravIdCurrent(p, Aig_ObjFanin0(pObj)) && Aig_ObjIsTravIdCurrent(p, Aig_ObjFanin1(pObj)) )
        {
            Aig_ObjSetTravIdCurrent(p, pObj);
            (*pnRegMoves)++;
        }
    // mark the remaining registers
    Saig_ManForEachLo( p, pObj, i )
        Aig_ObjSetTravIdCurrent(p, pObj);
    // find the cut (all such marked objects that fanout into unmarked nodes)
    vCut = Vec_PtrAlloc( 1000 );
    Aig_ManIncrementTravId( p );
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( Aig_ObjIsTravIdPrevious(p, pObj) )
            continue;
        pFanin = Aig_ObjFanin0(pObj);
        if ( pFanin && Aig_ObjIsTravIdPrevious(p, pFanin) )
        {
            Vec_PtrPush( vCut, pFanin );
            Aig_ObjSetTravIdCurrent( p, pFanin );
        }
        pFanin = Aig_ObjFanin1(pObj);
        if ( pFanin && Aig_ObjIsTravIdPrevious(p, pFanin) )
        {
            Vec_PtrPush( vCut, pFanin );
            Aig_ObjSetTravIdCurrent( p, pFanin );
        }
    }
    // finally derive the new manager
    pNew = Saig_ManRetimeDupForward( p, vCut );
    Vec_PtrFree( vCut );
    return pNew;
}

Aig_Man_t * Saig_ManRetimeForward( Aig_Man_t * p, int nMaxIters, int fVerbose )
{
    Aig_Man_t * pNew, * pTemp;
    int i, nRegFixed, nRegMoves = 1;
    abctime clk;
    pNew = p;
    for ( i = 0; i < nMaxIters && nRegMoves > 0; i++ )
    {
        clk = Abc_Clock();
        pNew = Saig_ManRetimeForwardOne( pTemp = pNew, &nRegFixed, &nRegMoves );
        if ( fVerbose )
        {
            printf( "%2d : And = %6d. Reg = %5d. Unret = %5d. Move = %6d. ", 
                i + 1, Aig_ManNodeNum(pTemp), Aig_ManRegNum(pTemp), nRegFixed, nRegMoves );
            ABC_PRT( "Time", Abc_Clock() - clk );
        }
        if ( pTemp != p )
            Aig_ManStop( pTemp );
    }
    clk = Abc_Clock();
    pNew = Aig_ManReduceLaches( pNew, fVerbose );
    if ( fVerbose )
    {
        ABC_PRT( "Register sharing time", Abc_Clock() - clk );
    }
    return pNew;
}
 

 
 
ABC_NAMESPACE_IMPL_END