giaMffc.c File Reference

#include "gia.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START int	Gia_ObjDom (Gia_Man_t *p, Gia_Obj_t *pObj)
	DECLARATIONS ///. More...
static void	Gia_ObjSetDom (Gia_Man_t *p, Gia_Obj_t *pObj, int d)
static void	Gia_ManAddDom (Gia_Man_t *p, Gia_Obj_t *pObj, int iDom0)
	FUNCTION DEFINITIONS ///. More...
static void	Gia_ManComputeDoms (Gia_Man_t *p)
static int	Gia_NodeDeref_rec (Gia_Man_t *p, Gia_Obj_t *pNode)
static int	Gia_NodeRef_rec (Gia_Man_t *p, Gia_Obj_t *pNode)
static void	Gia_NodeCollect_rec (Gia_Man_t *p, Gia_Obj_t *pNode, Vec_Int_t *vSupp, Vec_Int_t *vSuppRefs)
static int	Gia_NodeMffcSizeSupp (Gia_Man_t *p, Gia_Obj_t *pNode, Vec_Int_t *vSupp, Vec_Int_t *vSuppRefs)
int	Gia_ManDomDerive_rec (Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pNode)
Gia_Man_t *	Gia_ManDomDerive (Gia_Man_t *p, Gia_Obj_t *pRoot, Vec_Int_t *vSupp, int nVars)
void	Gia_ManComputeDomsTry (Gia_Man_t *p)

Function Documentation

static void Gia_ManAddDom ( Gia_Man_t *  p, Gia_Obj_t *  pObj, int  iDom0  )

inlinestatic

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Computes one-node dominators.]

Description [For each node, computes the closest one-node dominator, which can be the node itself if the node has no other dominators.]

SideEffects []

SeeAlso []

Definition at line 49 of file giaMffc.c.

{
    int iDom1, iDomNext;
    if ( Gia_ObjDom(p, pObj) == -1 )
    {
        Gia_ObjSetDom( p, pObj, iDom0 );
        return;
    }
    iDom1 = Gia_ObjDom( p, pObj );
    while ( 1 )
    {
        if ( iDom0 > iDom1 )
        {
            iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom1) );
            if ( iDomNext == iDom1 )
                break;
            iDom1 = iDomNext;
            continue;
        }
        if ( iDom1 > iDom0 )
        {
            iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom0) );
            if ( iDomNext == iDom0 )
                break;
            iDom0 = iDomNext;
            continue;
        }
        assert( iDom0 == iDom1 );
        Gia_ObjSetDom( p, pObj, iDom0 );
        return;
    }
    Gia_ObjSetDom( p, pObj, Gia_ObjId(p, pObj) );
}

static void Gia_ManComputeDoms ( Gia_Man_t *  p )

inlinestatic

Definition at line 82 of file giaMffc.c.

{
    Gia_Obj_t * pObj;
    int i;
    if ( p->vDoms == NULL )
        p->vDoms = Vec_IntAlloc( 0 );
    Vec_IntFill( p->vDoms, Gia_ManObjNum(p), -1 );
    Gia_ManForEachObjReverse( p, pObj, i )
    {
        if ( i == 0 || Gia_ObjIsCi(pObj) )
            continue;
        if ( Gia_ObjIsCo(pObj) )
        {
            Gia_ObjSetDom( p, pObj, i );
            Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
            continue;
        }
        assert( Gia_ObjIsAnd(pObj) );
        Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
        Gia_ManAddDom( p, Gia_ObjFanin1(pObj), i );
    }
}

void Gia_ManComputeDomsTry

(

Gia_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 250 of file giaMffc.c.

{
    extern void Gia_ManCollapseTestTest( Gia_Man_t * p );

    Vec_Int_t * vSupp, * vSuppRefs;
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    int i, nSize, Entry, k;
    abctime clk = Abc_Clock();
    ABC_FREE( p->pRefs );
    Gia_ManLevelNum( p );
    Gia_ManCreateRefs( p );
    Gia_ManComputeDoms( p );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    vSupp = Vec_IntAlloc( 1000 );
    vSuppRefs = Vec_IntAlloc( 1000 );
    Gia_ManForEachObj( p, pObj, i )
    {
        if ( !Gia_ObjIsAnd(pObj) && !Gia_ObjIsCo(pObj) )
            continue;
        if ( Gia_ObjDom(p, pObj) != i )
            continue;
        if ( Gia_ObjIsCo(pObj) )
            pObj = Gia_ObjFanin0(pObj);
        if ( !Gia_ObjIsAnd(pObj) )
            continue;
        nSize = Gia_NodeMffcSizeSupp( p, pObj, vSupp, vSuppRefs );
        if ( nSize < 10 )//|| nSize > 100 )
            continue;
        // sort by cost
        Vec_IntSelectSortCost2( Vec_IntArray(vSupp), Vec_IntSize(vSupp), Vec_IntArray(vSuppRefs) );

        printf( "Obj %6d : ", i );
        printf( "Cone = %4d  ", nSize );
        printf( "Supp = %4d  ", Vec_IntSize(vSupp) );
//        Vec_IntForEachEntry( vSuppRefs, Entry, k )
//            printf( "%d(%d) ", -Entry, Gia_ObjLevelId(p, Vec_IntEntry(vSupp, k)) );
        printf( "\n" );

        // selected k
        for ( k = 0; k < Vec_IntSize(vSupp); k++ )
            if ( Vec_IntEntry(vSuppRefs, k) == 1 )
                break;
        k = Abc_MinInt( k, 3 );
        k = 0;

        // dump
        pNew = Gia_ManDomDerive( p, pObj, vSupp, k );
        Gia_DumpAiger( pNew, "mffc", i, 6 );
        Gia_ManCollapseTestTest( pNew );

        Gia_ManStop( pNew );
    }
    Vec_IntFree( vSuppRefs );
    Vec_IntFree( vSupp );
}

Gia_Man_t* Gia_ManDomDerive	(	Gia_Man_t *	p,
		Gia_Obj_t *	pRoot,
		Vec_Int_t *	vSupp,
		int	nVars
	)

Definition at line 205 of file giaMffc.c.

{
    Gia_Man_t * pNew, * pTemp;
    int nMints = 1 << nVars;
    int i, m, iResLit;
    assert( nVars >= 0 && nVars <= 5 );
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    Gia_ManConst0(p)->Value = 0;
    Gia_ManHashAlloc( pNew );
    for ( i = 0; i < Vec_IntSize(vSupp); i++ )
        Gia_ManAppendCi(pNew);
    for ( m = 0; m < nMints; m++ )
    {
        Gia_Obj_t * pObj;
        Gia_ManIncrementTravId( p );
        Gia_ManForEachObjVec( vSupp, p, pObj, i )
        {
            if ( i < nVars )
                pObj->Value = (m >> i) & 1;
            else
                pObj->Value = Gia_ObjToLit(pNew, Gia_ManCi(pNew, i));
            Gia_ObjSetTravIdCurrent( p, pObj );
        }
        iResLit = Gia_ManDomDerive_rec( pNew, p, pRoot );
        Gia_ManAppendCo( pNew, iResLit );
    }
    Gia_ManHashStop( pNew );
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

int Gia_ManDomDerive_rec	(	Gia_Man_t *	pNew,
		Gia_Man_t *	p,
		Gia_Obj_t *	pNode
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 195 of file giaMffc.c.

{
    if ( Gia_ObjIsTravIdCurrent(p, pNode) )
        return pNode->Value;
    Gia_ObjSetTravIdCurrent(p, pNode);
    assert( Gia_ObjIsAnd(pNode) );
    Gia_ManDomDerive_rec( pNew, p, Gia_ObjFanin0(pNode) );
    Gia_ManDomDerive_rec( pNew, p, Gia_ObjFanin1(pNode) );
    return pNode->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pNode), Gia_ObjFanin1Copy(pNode) );
}

static void Gia_NodeCollect_rec ( Gia_Man_t *  p, Gia_Obj_t *  pNode, Vec_Int_t *  vSupp, Vec_Int_t *  vSuppRefs  )

inlinestatic

Definition at line 149 of file giaMffc.c.

{
    if ( Gia_ObjIsTravIdCurrent(p, pNode) )
        return;
    Gia_ObjSetTravIdCurrent(p, pNode);
    if ( Gia_ObjRefNum(p, pNode) || Gia_ObjIsCi(pNode) )
    {
        Vec_IntPush( vSupp, Gia_ObjId(p, pNode) );
        Vec_IntPush( vSuppRefs, Gia_ObjRefNum(p, pNode) );
        return;
    }
    assert( Gia_ObjIsAnd(pNode) );
    Gia_NodeCollect_rec( p, Gia_ObjFanin0(pNode), vSupp, vSuppRefs );
    Gia_NodeCollect_rec( p, Gia_ObjFanin1(pNode), vSupp, vSuppRefs );
}

static int Gia_NodeDeref_rec ( Gia_Man_t *  p, Gia_Obj_t *  pNode  )

inlinestatic

Function*************************************************************

Synopsis [Returns the number of internal nodes in the MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 117 of file giaMffc.c.

{
    Gia_Obj_t * pFanin;
    int Counter = 0;
    if ( Gia_ObjIsCi(pNode) )
        return 0;
    assert( Gia_ObjIsAnd(pNode) );
    pFanin = Gia_ObjFanin0(pNode);
    assert( Gia_ObjRefNum(p, pFanin) > 0 );
    if ( Gia_ObjRefDec(p, pFanin) == 0 )
        Counter += Gia_NodeDeref_rec( p, pFanin );
    pFanin = Gia_ObjFanin1(pNode);
    assert( Gia_ObjRefNum(p, pFanin) > 0 );
    if ( Gia_ObjRefDec(p, pFanin) == 0 )
        Counter += Gia_NodeDeref_rec( p, pFanin );
    return Counter + 1;
}

static int Gia_NodeMffcSizeSupp ( Gia_Man_t *  p, Gia_Obj_t *  pNode, Vec_Int_t *  vSupp, Vec_Int_t *  vSuppRefs  )

inlinestatic

Definition at line 164 of file giaMffc.c.

{
    int ConeSize1, ConeSize2, i, iObj;
    assert( !Gia_IsComplement(pNode) );
    assert( Gia_ObjIsAnd(pNode) );
    Vec_IntClear( vSupp );
    Vec_IntClear( vSuppRefs );
    Gia_ManIncrementTravId( p );
    ConeSize1 = Gia_NodeDeref_rec( p, pNode );
    Gia_NodeCollect_rec( p, Gia_ObjFanin0(pNode), vSupp, vSuppRefs );
    Gia_NodeCollect_rec( p, Gia_ObjFanin1(pNode), vSupp, vSuppRefs );
    ConeSize2 = Gia_NodeRef_rec( p, pNode );
    assert( ConeSize1 == ConeSize2 );
    assert( ConeSize1 >= 0 );
    // record supp refs    
    Vec_IntForEachEntry( vSupp, iObj, i )
        Vec_IntAddToEntry( vSuppRefs, i, -Gia_ObjRefNumId(p, iObj) );
    return ConeSize1;
}

static int Gia_NodeRef_rec ( Gia_Man_t *  p, Gia_Obj_t *  pNode  )

inlinestatic

Definition at line 134 of file giaMffc.c.

{
    Gia_Obj_t * pFanin;
    int Counter = 0;
    if ( Gia_ObjIsCi(pNode) )
        return 0;
    assert( Gia_ObjIsAnd(pNode) );
    pFanin = Gia_ObjFanin0(pNode);
    if ( Gia_ObjRefInc(p, pFanin) == 0 )
        Counter += Gia_NodeRef_rec( p, pFanin );
    pFanin = Gia_ObjFanin1(pNode);
    if ( Gia_ObjRefInc(p, pFanin) == 0 )
        Counter += Gia_NodeRef_rec( p, pFanin );
    return Counter + 1;
}

static ABC_NAMESPACE_IMPL_START int Gia_ObjDom ( Gia_Man_t *  p, Gia_Obj_t *  pObj  )

inlinestatic

DECLARATIONS ///.

CFile****************************************************************

FileName [gia.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Scalable AIG package.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 30 of file giaMffc.c.

{ return Vec_IntEntry(p->vDoms, Gia_ObjId(p, pObj));   }

static void Gia_ObjSetDom ( Gia_Man_t *  p, Gia_Obj_t *  pObj, int  d  )

inlinestatic

Definition at line 31 of file giaMffc.c.

{ Vec_IntWriteEntry(p->vDoms, Gia_ObjId(p, pObj), d);  }