ivyRwrAlg.c File Reference

#include "ivy.h"

Include dependency graph for ivyRwrAlg.c:

Go to the source code of this file.

Functions
int	Ivy_ManRewriteAlg (Ivy_Man_t *p, int fUpdateLevel, int fUseZeroCost)
	FUNCTION DEFINITIONS ///.
int	Ivy_NodeCountMffc_rec (Ivy_Obj_t *pNode)
int	Ivy_ManFindAlgCutCompare (Ivy_Obj_t **pp1, Ivy_Obj_t **pp2)
int	Ivy_ManFindAlgCut_rec (Ivy_Obj_t *pObj, Ivy_Type_t Type, Vec_Ptr_t *vFront, Vec_Ptr_t *vCone)

Function Documentation

Ivy_ManFindAlgCut_rec()

int Ivy_ManFindAlgCut_rec	(	Ivy_Obj_t *	pObj,
		Ivy_Type_t	Type,
		Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vCone )

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

Synopsis [Computing one algebraic cut.]

Description [Returns 1 if the tree-leaves of this node where traversed and found to have no external references (and have not been collected). Returns 0 if the tree-leaves have external references and are collected.]

SideEffects []

SeeAlso []

Definition at line 279 of file ivyRwrAlg.c.

{
    int RetValue0, RetValue1;
    Ivy_Obj_t * pObjR = Ivy_Regular(pObj);
    assert( !Ivy_ObjIsBuf(pObjR) );
    assert( Type != IVY_EXOR || !Ivy_IsComplement(pObj) );
 
    // make sure the node is not visited twice in different polarities
    if ( Ivy_IsComplement(pObj) )
    { // if complemented, mark B
        if ( pObjR->fMarkA )
            return -1;
        pObjR->fMarkB = 1;
    }
    else
    { // if non-complicated, mark A
        if ( pObjR->fMarkB )
            return -1;
        pObjR->fMarkA = 1;
    }
    Vec_PtrPush( vCone, pObjR );
 
    // if the node is the end of the tree, return
    if ( Ivy_IsComplement(pObj) || Ivy_ObjType(pObj) != Type )
    {
        if ( Ivy_ObjRefs(pObjR) == 1 )
            return 1;
        assert( Ivy_ObjRefs(pObjR) > 1 );
        Vec_PtrPush( vFront, pObj );
        return 0;
    }
 
    // branch on the node
    assert( !Ivy_IsComplement(pObj) );
    assert( Ivy_ObjIsNode(pObj) );
    // what if buffer has more than one fanout???
    RetValue0 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild0(pObj) ), Type, vFront, vCone );
    RetValue1 = Ivy_ManFindAlgCut_rec( Ivy_ObjReal( Ivy_ObjChild1(pObj) ), Type, vFront, vCone );
    if ( RetValue0 == -1 || RetValue1 == -1 )
        return -1;
 
    // the case when both have no external references
    if ( RetValue0 && RetValue1 )
    {
        if ( Ivy_ObjRefs(pObj) == 1 )
            return 1;
        assert( Ivy_ObjRefs(pObj) > 1 );
        Vec_PtrPush( vFront, pObj );
        return 0;
    }
    // the case when one of them has external references
    if ( RetValue0 )
        Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild0(pObj) ) );
    if ( RetValue1 )
        Vec_PtrPush( vFront, Ivy_ObjReal( Ivy_ObjChild1(pObj) ) );
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Ivy_ManFindAlgCutCompare()

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

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

Synopsis [Comparison for node pointers.]

Description []

SideEffects []

SeeAlso []

Definition at line 257 of file ivyRwrAlg.c.

{
    if ( *pp1 < *pp2 )
        return -1;
    if ( *pp1 > *pp2 )
        return 1;
    return 0;
}

Ivy_ManRewriteAlg()

int Ivy_ManRewriteAlg	(	Ivy_Man_t *	p,
		int	fUpdateLevel,
		int	fUseZeroCost )

FUNCTION DEFINITIONS ///.

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

Synopsis [Algebraic AIG rewriting.]

Description []

SideEffects []

SeeAlso []

Definition at line 49 of file ivyRwrAlg.c.

{
    Vec_Int_t * vRequired;
    Vec_Ptr_t * vFront, * vLeaves, * vCone, * vSol;
    Ivy_Obj_t * pObj, * pResult;
    int i, RetValue, LevelR, nNodesOld;
    int CountUsed, CountUndo;
    vRequired = fUpdateLevel? Ivy_ManRequiredLevels( p ) : NULL;
    vFront    = Vec_PtrAlloc( 100 );
    vLeaves   = Vec_PtrAlloc( 100 );
    vCone     = Vec_PtrAlloc( 100 );
    vSol      = Vec_PtrAlloc( 100 );
    // go through the nodes in the topological order
    CountUsed = CountUndo = 0;
    nNodesOld = Ivy_ManObjIdNext(p);
    Ivy_ManForEachObj( p, pObj, i )
    {
        assert( !Ivy_ObjIsBuf(pObj) );
        if ( i >= nNodesOld )
            break;
        // skip no-nodes and MUX roots
        if ( !Ivy_ObjIsNode(pObj) || Ivy_ObjIsExor(pObj) || Ivy_ObjIsMuxType(pObj) )
            continue;
//        if ( pObj->Id > 297 ) // 296 --- 297 
//            break;
        if ( pObj->Id == 297 )
        {
            int x = 0;
        }
        // get the largest algebraic cut
        RetValue = Ivy_ManFindAlgCut( pObj, vFront, vLeaves, vCone );
        // the case of a trivial tree cut
        if ( RetValue == 1 )
            continue;
        // the case of constant 0 cone
        if ( RetValue == -1 )
        {
            Ivy_ObjReplace( pObj, Ivy_ManConst0(p), 1, 0, 1 ); 
            continue;
        }
        assert( Vec_PtrSize(vLeaves) > 2 );
        // get the required level for this node
        LevelR = vRequired? Vec_IntEntry(vRequired, pObj->Id) : 1000000;
        // create a new cone
        pResult = Ivy_NodeRewriteAlg( pObj, vFront, vLeaves, vCone, vSol, LevelR, fUseZeroCost );
        if ( pResult == NULL || pResult == pObj )
            continue;
        assert( Vec_PtrSize(vSol) == 1 || !Ivy_IsComplement(pResult) );
        if ( Ivy_ObjLevel(Ivy_Regular(pResult)) > LevelR && Ivy_ObjRefs(Ivy_Regular(pResult)) == 0 )
            Ivy_ObjDelete_rec(Ivy_Regular(pResult), 1), CountUndo++;
        else
            Ivy_ObjReplace( pObj, pResult, 1, 0, 1 ), CountUsed++; 
    }
    printf( "Used = %d. Undo = %d.\n", CountUsed, CountUndo );
    Vec_PtrFree( vFront );
    Vec_PtrFree( vCone );
    Vec_PtrFree( vSol );
    if ( vRequired ) Vec_IntFree( vRequired );
    if ( i = Ivy_ManCleanup(p) )
        printf( "Cleanup after rewriting removed %d dangling nodes.\n", i );
    if ( !Ivy_ManCheck(p) )
        printf( "Ivy_ManRewriteAlg(): The check has failed.\n" );
    return 1;
}

Here is the call graph for this function:

Ivy_NodeCountMffc_rec()

int Ivy_NodeCountMffc_rec

(

Ivy_Obj_t *

pNode

)

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

Synopsis [Comparison for node pointers.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file ivyRwrAlg.c.

{
    if ( Ivy_ObjRefs(pNode) > 0 || Ivy_ObjIsCi(pNode) || pNode->fMarkA )
        return 0;
    assert( pNode->fMarkB );
    pNode->fMarkA = 1;
//    printf( "%d ", pNode->Id );
    if ( Ivy_ObjIsBuf(pNode) )
        return Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) );
    return 1 + Ivy_NodeCountMffc_rec( Ivy_ObjFanin0(pNode) ) + Ivy_NodeCountMffc_rec( Ivy_ObjFanin1(pNode) );
}

Here is the call graph for this function:

Here is the caller graph for this function: