hopBalance.c File Reference

#include "hop.h"

Include dependency graph for hopBalance.c:

Go to the source code of this file.

Functions
Hop_Man_t *	Hop_ManBalance (Hop_Man_t *p, int fUpdateLevel)
	FUNCTION DEFINITIONS ///.
int	Hop_NodeBalanceCone_rec (Hop_Obj_t *pRoot, Hop_Obj_t *pObj, Vec_Ptr_t *vSuper)
int	Hop_NodeCompareLevelsDecrease (Hop_Obj_t **pp1, Hop_Obj_t **pp2)
Hop_Obj_t *	Hop_NodeBalanceBuildSuper (Hop_Man_t *p, Vec_Ptr_t *vSuper, Hop_Type_t Type, int fUpdateLevel)

Function Documentation

Hop_ManBalance()

Hop_Man_t * Hop_ManBalance	(	Hop_Man_t *	p,
		int	fUpdateLevel )

FUNCTION DEFINITIONS ///.

FUNCTION DECLARATIONS ///.

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

Synopsis [Performs algebraic balancing of the AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 51 of file hopBalance.c.

{
    Hop_Man_t * pNew;
    Hop_Obj_t * pObj, * pObjNew;
    Vec_Vec_t * vStore;
    int i;
    // create the new manager 
    pNew = Hop_ManStart();
    pNew->fRefCount = 0;
    // map the PI nodes
    Hop_ManCleanData( p );
    Hop_ManConst1(p)->pData = Hop_ManConst1(pNew);
    Hop_ManForEachPi( p, pObj, i )
        pObj->pData = Hop_ObjCreatePi(pNew);
    // balance the AIG
    vStore = Vec_VecAlloc( 50 );
    Hop_ManForEachPo( p, pObj, i )
    {
        pObjNew = Hop_NodeBalance_rec( pNew, Hop_ObjFanin0(pObj), vStore, 0, fUpdateLevel );
        Hop_ObjCreatePo( pNew, Hop_NotCond( pObjNew, Hop_ObjFaninC0(pObj) ) );
    }
    Vec_VecFree( vStore );
    // remove dangling nodes
//    Hop_ManCreateRefs( pNew );
//    if ( i = Hop_ManCleanup( pNew ) )
//        printf( "Cleanup after balancing removed %d dangling nodes.\n", i );
    // check the resulting AIG
    if ( !Hop_ManCheck(pNew) )
        printf( "Hop_ManBalance(): The check has failed.\n" );
    return pNew;
}

Here is the call graph for this function:

Hop_NodeBalanceBuildSuper()

Hop_Obj_t * Hop_NodeBalanceBuildSuper	(	Hop_Man_t *	p,
		Vec_Ptr_t *	vSuper,
		Hop_Type_t	Type,
		int	fUpdateLevel )

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

Synopsis [Builds implication supergate.]

Description []

SideEffects []

SeeAlso []

Definition at line 243 of file hopBalance.c.

{
    Hop_Obj_t * pObj1, * pObj2;
    int LeftBound;
    assert( vSuper->nSize > 1 );
    // sort the new nodes by level in the decreasing order
    Vec_PtrSort( vSuper, (int (*)(const void *, const void *))Hop_NodeCompareLevelsDecrease );
    // balance the nodes
    while ( vSuper->nSize > 1 )
    {
        // find the left bound on the node to be paired
        LeftBound = (!fUpdateLevel)? 0 : Hop_NodeBalanceFindLeft( vSuper );
        // find the node that can be shared (if no such node, randomize choice)
        Hop_NodeBalancePermute( p, vSuper, LeftBound, Type == AIG_EXOR );
        // pull out the last two nodes
        pObj1 = (Hop_Obj_t *)Vec_PtrPop(vSuper);
        pObj2 = (Hop_Obj_t *)Vec_PtrPop(vSuper);
        Hop_NodeBalancePushUniqueOrderByLevel( vSuper, Hop_Oper(p, pObj1, pObj2, Type) );
    }
    return (Hop_Obj_t *)Vec_PtrEntry(vSuper, 0);
}

Here is the call graph for this function:

Hop_NodeBalanceCone_rec()

int Hop_NodeBalanceCone_rec	(	Hop_Obj_t *	pRoot,
		Hop_Obj_t *	pObj,
		Vec_Ptr_t *	vSuper )

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

Synopsis [Collects the nodes of the supergate.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file hopBalance.c.

{
    int RetValue1, RetValue2, i;
    // check if the node is visited
    if ( Hop_Regular(pObj)->fMarkB )
    {
        // check if the node occurs in the same polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == pObj )
                return 1;
        // check if the node is present in the opposite polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == Hop_Not(pObj) )
                return -1;
        assert( 0 );
        return 0;
    }
    // if the new node is complemented or a PI, another gate begins
    if ( pObj != pRoot && (Hop_IsComplement(pObj) || Hop_ObjType(pObj) != Hop_ObjType(pRoot) || Hop_ObjRefs(pObj) > 1 || Vec_PtrSize(vSuper) > 10000) )
    {
        Vec_PtrPush( vSuper, pObj );
        Hop_Regular(pObj)->fMarkB = 1;
        return 0;
    }
    assert( !Hop_IsComplement(pObj) );
    assert( Hop_ObjIsNode(pObj) );
    // go through the branches
    RetValue1 = Hop_NodeBalanceCone_rec( pRoot, Hop_ObjChild0(pObj), vSuper );
    RetValue2 = Hop_NodeBalanceCone_rec( pRoot, Hop_ObjChild1(pObj), vSuper );
    if ( RetValue1 == -1 || RetValue2 == -1 )
        return -1;
    // return 1 if at least one branch has a duplicate
    return RetValue1 || RetValue2;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Hop_NodeCompareLevelsDecrease()

int Hop_NodeCompareLevelsDecrease	(	Hop_Obj_t **	pp1,
		Hop_Obj_t **	pp2 )

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

Synopsis [Procedure used for sorting the nodes in decreasing order of levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file hopBalance.c.

{
    int Diff = Hop_ObjLevel(Hop_Regular(*pp1)) - Hop_ObjLevel(Hop_Regular(*pp2));
    if ( Diff > 0 )
        return -1;
    if ( Diff < 0 ) 
        return 1;
    Diff = Hop_Regular(*pp1)->Id - Hop_Regular(*pp2)->Id;
    if ( Diff > 0 )
        return -1;
    if ( Diff < 0 ) 
        return 1;
    return 0; 
}

Here is the caller graph for this function: