giaBalMap.c

Go to the documentation of this file.

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

  FileName    [giaSopb.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [SOP balancing for a window.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManHighlight_rec( Gia_Man_t * p, int iObj )
{
    Gia_Obj_t * pObj;
    if ( Gia_ObjIsTravIdCurrentId(p, iObj) )
        return;
    Gia_ObjSetTravIdCurrentId(p, iObj);
    pObj = Gia_ManObj( p, iObj );
    if ( Gia_ObjIsAnd(pObj) )
        Gia_ManHighlight_rec( p, Gia_ObjFaninId0(pObj, iObj) );
    if ( Gia_ObjIsAnd(pObj) )
        Gia_ManHighlight_rec( p, Gia_ObjFaninId1(pObj, iObj) );
}
void Gia_ManPrepareWin( Gia_Man_t * p, Vec_Int_t * vOuts, Vec_Int_t ** pvPis, Vec_Int_t ** pvPos, Vec_Int_t ** pvAnds, int fPoOnly )
{
    Gia_Obj_t * pObj;
    int i;
    // mark the section
    Gia_ManIncrementTravId( p );
    Gia_ManForEachCoVec( vOuts, p, pObj, i )
        Gia_ManHighlight_rec( p, Gia_ObjFaninId0p(p, pObj) );
    // mark fanins of the outside area
    Gia_ManCleanMark0( p );
    if ( fPoOnly )
    {
        Gia_ManForEachCoVec( vOuts, p, pObj, i )
            Gia_ObjFanin0(pObj)->fMark0 = 1;
    }
    else
    {
        Gia_ManForEachObj1( p, pObj, i )
        {
            if ( Gia_ObjIsCi(pObj) )
                continue;
            if ( Gia_ObjIsAnd(pObj) && !Gia_ObjIsTravIdCurrentId(p, i) )
                continue;
            Gia_ObjFanin0(pObj)->fMark0 = 1;
            if ( Gia_ObjIsAnd(pObj) )
                Gia_ObjFanin1(pObj)->fMark0 = 1;
        }
    }
    // collect pointed nodes
    *pvPis  = Vec_IntAlloc( 1000 );
    *pvPos  = Vec_IntAlloc( 1000 );
    *pvAnds = Vec_IntAlloc( 1000 );
    Gia_ManForEachObj1( p, pObj, i )
    {
        if ( !Gia_ObjIsTravIdCurrentId(p, i) )
            continue;
        if ( Gia_ObjIsCi(pObj) )
            Vec_IntPush( *pvPis, i );
        else if ( pObj->fMark0 )
            Vec_IntPush( *pvPos, i );
        if ( Gia_ObjIsAnd(pObj) )
            Vec_IntPush( *pvAnds, i );
    }
    Gia_ManCleanMark0( p );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManExtractWin( Gia_Man_t * p, Vec_Int_t * vOuts, int fPoOnly )
{
    Vec_Int_t * vPis, * vPos, * vAnds;
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    int i;
    Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, fPoOnly );
    // create AIG
    pNew = Gia_ManStart( Vec_IntSize(vPis) + Vec_IntSize(vPos) + Vec_IntSize(vAnds) + 1 );
    pNew->pName = Abc_UtilStrsav( p->pName );
    Gia_ManConst0(p)->Value = 0;
    Gia_ManForEachObjVec( vPis, p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    Gia_ManForEachObjVec( vAnds, p, pObj, i )
        pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachObjVec( vPos, p, pObj, i )
        Gia_ManAppendCo( pNew, pObj->Value );
    Vec_IntFree( vPis );
    Vec_IntFree( vPos );
    Vec_IntFree( vAnds );
    return pNew;
}
Gia_Man_t * Gia_ManInsertWin( Gia_Man_t * p, Vec_Int_t * vOuts, Gia_Man_t * pWin )
{
    Vec_Int_t * vPos, * vPis, * vAnds;
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;
    int i;
    Gia_ManPrepareWin( p, vOuts, &vPis, &vPos, &vAnds, 0 );
    // create AIG
    pNew = Gia_ManStart( Gia_ManObjNum(p) - Vec_IntSize(vAnds) + Gia_ManAndNum(pWin) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    // inputs
    Gia_ManConst0(p)->Value = 0;
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    Gia_ManConst0(pWin)->Value = 0;
    Gia_ManForEachCi( pWin, pObj, i )
        pObj->Value = Gia_ManObj(p, Vec_IntEntry(vPis, i))->Value;
    // internal nodes
    Gia_ManHashAlloc( pNew );
    Gia_ManForEachAnd( pWin, pObj, i )
        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( pWin, pObj, i )
        Gia_ManObj( p, Vec_IntEntry(vPos, i) )->Value = Gia_ObjFanin0Copy(pObj);
    Gia_ManForEachAnd( p, pObj, i )
        if ( !Gia_ObjIsTravIdCurrentId(p, i) )
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    Gia_ManForEachCo( p, pObj, i )
        Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManHashStop( pNew );
    // cleanup
    Vec_IntFree( vPis );
    Vec_IntFree( vPos );
    Vec_IntFree( vAnds );
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManFindLatest( Gia_Man_t * p, int LevelMax, int nTimeWindow )
{
    Gia_Obj_t * pObj;
    Vec_Int_t * vOuts;
    vOuts = Vec_IntAlloc( 1000 );
    if ( Gia_ManHasMapping(p) )
    {
        int i, k, iFan, nLevels = 0;
        int * pLevels = ABC_CALLOC( int, Gia_ManObjNum(p) );
        Gia_ManForEachLut( p, i )
        {
            Gia_LutForEachFanin( p, i, iFan, k )
                pLevels[i] = Abc_MaxInt( pLevels[i], pLevels[iFan] );
            pLevels[i]++;
            nLevels = Abc_MaxInt( nLevels, pLevels[i] );
        }
        if ( nTimeWindow )
            LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels);
        if ( nLevels < LevelMax )
            printf( "The maximum mapped level (%d) is less than the target level (%d).\n", nLevels, LevelMax );
        Gia_ManForEachCo( p, pObj, i )
            if ( pLevels[Gia_ObjFaninId0p(p, pObj)] >= LevelMax )
                Vec_IntPush( vOuts, i );
        ABC_FREE( pLevels );
    }
    else
    {
        int i, nLevels = Gia_ManLevelNum( p );
        if ( nTimeWindow )
            LevelMax = (int)((1.0 - 0.01 * nTimeWindow) * nLevels);
        if ( nLevels < LevelMax )
            printf( "The maximum AIG level (%d) is less than the target level (%d).\n", nLevels, LevelMax );
        Gia_ManForEachCo( p, pObj, i )
            if ( Gia_ObjLevel(p, pObj) >= LevelMax )
                Vec_IntPush( vOuts, i );
    }
    return vOuts;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManExtractWindow( Gia_Man_t * p, int LevelMax, int nTimeWindow, int fVerbose )
{
    Vec_Int_t * vOuts;
    Gia_Man_t * pWin;
    assert( !LevelMax != !nTimeWindow );
    vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow );
    if ( fVerbose )
        printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) );
    if ( Vec_IntSize(vOuts) == 0 )
    {
        Vec_IntFree( vOuts );
        return Gia_ManDup( p );
    }
    pWin = Gia_ManExtractWin( p, vOuts, 1 );
    Vec_IntFree( vOuts );
    return pWin;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManPerformSopBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nCutNum, int nRelaxRatio, int fVerbose )
{
    Vec_Int_t * vOuts;
    Gia_Man_t * pNew, * pWin, * pWinNew;
    assert( !LevelMax != !nTimeWindow );
    vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow );
    if ( fVerbose )
        printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) );
    if ( Vec_IntSize(vOuts) == 0 )
    {
        Vec_IntFree( vOuts );
        return Gia_ManDup( p );
    }
    pWin = Gia_ManExtractWin( p, vOuts, 0 );
    pWinNew = Gia_ManPerformSopBalance( pWin, nCutNum, nRelaxRatio, fVerbose );
    Gia_ManStop( pWin );
    pNew = Gia_ManInsertWin( p, vOuts, pWinNew );
    Gia_ManStop( pWinNew );
    Vec_IntFree( vOuts );
    return pNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManPerformDsdBalanceWin( Gia_Man_t * p, int LevelMax, int nTimeWindow, int nLutSize, int nCutNum, int nRelaxRatio, int fVerbose )
{
    Vec_Int_t * vOuts;
    Gia_Man_t * pNew, * pWin, * pWinNew;
    assert( !LevelMax != !nTimeWindow );
    vOuts = Gia_ManFindLatest( p, LevelMax, nTimeWindow );
    if ( fVerbose )
        printf( "Collected %d outputs to extract.\n", Vec_IntSize(vOuts) );
    if ( Vec_IntSize(vOuts) == 0 )
    {
        Vec_IntFree( vOuts );
        return Gia_ManDup( p );
    }
    pWin = Gia_ManExtractWin( p, vOuts, 0 );
    pWinNew = Gia_ManPerformDsdBalance( pWin, nLutSize, nCutNum, nRelaxRatio, fVerbose );
    Gia_ManStop( pWin );
    pNew = Gia_ManInsertWin( p, vOuts, pWinNew );
    Gia_ManStop( pWinNew );
    Vec_IntFree( vOuts );
    return pNew;
}

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


ABC_NAMESPACE_IMPL_END