ivyBalance.c File Reference

#include "ivy.h"

Include dependency graph for ivyBalance.c:

Go to the source code of this file.

Functions
Ivy_Man_t *	Ivy_ManBalance (Ivy_Man_t *p, int fUpdateLevel)
	FUNCTION DEFINITIONS ///.
int	Ivy_NodeCompareLevelsDecrease (Ivy_Obj_t **pp1, Ivy_Obj_t **pp2)
Ivy_Obj_t *	Ivy_NodeBalanceBuildSuper (Ivy_Man_t *p, Vec_Ptr_t *vSuper, Ivy_Type_t Type, int fUpdateLevel)
int	Ivy_NodeBalanceCone_rec (Ivy_Obj_t *pRoot, Ivy_Obj_t *pObj, Vec_Ptr_t *vSuper)

Function Documentation

Ivy_ManBalance()

Ivy_Man_t * Ivy_ManBalance	(	Ivy_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 ivyBalance.c.

{
    Ivy_Man_t * pNew;
    Ivy_Obj_t * pObj, * pDriver;
    Vec_Vec_t * vStore;
    int i, NewNodeId;
    // clean the old manager
    Ivy_ManCleanTravId( p );
    // create the new manager 
    pNew = Ivy_ManStart();
    // map the nodes
    Ivy_ManConst1(p)->TravId = Ivy_EdgeFromNode( Ivy_ManConst1(pNew) );
    Ivy_ManForEachPi( p, pObj, i )
        pObj->TravId = Ivy_EdgeFromNode( Ivy_ObjCreatePi(pNew) );
    // if HAIG is defined, trasfer the pointers to the PIs/latches
//    if ( p->pHaig )
//        Ivy_ManHaigTrasfer( p, pNew );
    // balance the AIG
    vStore = Vec_VecAlloc( 50 );
    Ivy_ManForEachPo( p, pObj, i )
    {
        pDriver   = Ivy_ObjReal( Ivy_ObjChild0(pObj) );
        NewNodeId = Ivy_NodeBalance_rec( pNew, Ivy_Regular(pDriver), vStore, 0, fUpdateLevel );
        NewNodeId = Ivy_EdgeNotCond( NewNodeId, Ivy_IsComplement(pDriver) );
        Ivy_ObjCreatePo( pNew, Ivy_EdgeToNode(pNew, NewNodeId) );
    }
    Vec_VecFree( vStore );
    if ( (i = Ivy_ManCleanup( pNew )) )
    {
//        printf( "Cleanup after balancing removed %d dangling nodes.\n", i );
    }
    // check the resulting AIG
    if ( !Ivy_ManCheck(pNew) )
        printf( "Ivy_ManBalance(): The check has failed.\n" );
    return pNew;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Ivy_NodeBalanceBuildSuper()

Ivy_Obj_t * Ivy_NodeBalanceBuildSuper	(	Ivy_Man_t *	p,
		Vec_Ptr_t *	vSuper,
		Ivy_Type_t	Type,
		int	fUpdateLevel )

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

Synopsis [Builds implication supergate.]

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file ivyBalance.c.

{
    Ivy_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 *))Ivy_NodeCompareLevelsDecrease );
    // balance the nodes
    while ( vSuper->nSize > 1 )
    {
        // find the left bound on the node to be paired
        LeftBound = (!fUpdateLevel)? 0 : Ivy_NodeBalanceFindLeft( vSuper );
        // find the node that can be shared (if no such node, randomize choice)
        Ivy_NodeBalancePermute( p, vSuper, LeftBound, Type == IVY_EXOR );
        // pull out the last two nodes
        pObj1 = (Ivy_Obj_t *)Vec_PtrPop(vSuper);
        pObj2 = (Ivy_Obj_t *)Vec_PtrPop(vSuper);
        Ivy_NodeBalancePushUniqueOrderByLevel( vSuper, Ivy_Oper(p, pObj1, pObj2, Type) );
    }
    return (Ivy_Obj_t *)Vec_PtrEntry(vSuper, 0);
}

Here is the call graph for this function:

Ivy_NodeBalanceCone_rec()

int Ivy_NodeBalanceCone_rec	(	Ivy_Obj_t *	pRoot,
		Ivy_Obj_t *	pObj,
		Vec_Ptr_t *	vSuper )

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

Synopsis [Collects the nodes of the supergate.]

Description []

SideEffects []

SeeAlso []

Definition at line 208 of file ivyBalance.c.

{
    int RetValue1, RetValue2, i;
    // check if the node is visited
    if ( Ivy_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] == Ivy_Not(pObj) )
                return -1;
        assert( 0 );
        return 0;
    }
    // if the new node is complemented or a PI, another gate begins
    if ( pObj != pRoot && (Ivy_IsComplement(pObj) || Ivy_ObjType(pObj) != Ivy_ObjType(pRoot) || Ivy_ObjRefs(pObj) > 1 || Vec_PtrSize(vSuper) > 10000) )
    {
        Vec_PtrPush( vSuper, pObj );
        Ivy_Regular(pObj)->fMarkB = 1;
        return 0;
    }
    assert( !Ivy_IsComplement(pObj) );
    assert( Ivy_ObjIsNode(pObj) );
    // go through the branches
    RetValue1 = Ivy_NodeBalanceCone_rec( pRoot, Ivy_ObjReal( Ivy_ObjChild0(pObj) ), vSuper );
    RetValue2 = Ivy_NodeBalanceCone_rec( pRoot, Ivy_ObjReal( Ivy_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:

Ivy_NodeCompareLevelsDecrease()

int Ivy_NodeCompareLevelsDecrease	(	Ivy_Obj_t **	pp1,
		Ivy_Obj_t **	pp2 )

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 99 of file ivyBalance.c.

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

Here is the caller graph for this function: