saigRetFwd.c

Go to the documentation of this file.

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

  FileName    [saigRetFwd.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Sequential AIG package.]

  Synopsis    [Most-forward retiming.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "saig.h"

ABC_NAMESPACE_IMPL_START


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

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++ )

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

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

  Synopsis    [Allocate static fanout for all nodes in the AIG manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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;
}

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

  Synopsis    [Marks the objects reachable from the given object.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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 );
}

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

  Synopsis    [Marks with current trav ID nodes reachable from Const1 and PIs.]

  Description [Returns the number of unreachable registers.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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;
    }
}

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

  Synopsis    [Derives the cut for forward retiming.]

  Description [Assumes topological ordering of the nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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;
}

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

  Synopsis    [Derives the cut for forward retiming.]

  Description [Assumes topological ordering of the nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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;
}


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


ABC_NAMESPACE_IMPL_END