aigWin.c File Reference

#include "aig.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START int	Aig_NodeGetLeafCostOne (Aig_Obj_t *pNode, int nFanoutLimit)
	DECLARATIONS ///. More...
int	Aig_ManFindCut_int (Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited, int nSizeLimit, int nFanoutLimit)
void	Aig_ManFindCut (Aig_Obj_t *pRoot, Vec_Ptr_t *vFront, Vec_Ptr_t *vVisited, int nSizeLimit, int nFanoutLimit)

Function Documentation

void Aig_ManFindCut	(	Aig_Obj_t *	pRoot,
		Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vVisited,
		int	nSizeLimit,
		int	nFanoutLimit
	)

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

Synopsis [Computes one sequential cut of the given size.]

Description []

SideEffects []

SeeAlso []

Definition at line 145 of file aigWin.c.

{
    Aig_Obj_t * pNode;
    int i;

    assert( !Aig_IsComplement(pRoot) );
    assert( Aig_ObjIsNode(pRoot) );
    assert( Aig_ObjChild0(pRoot) );
    assert( Aig_ObjChild1(pRoot) );

    // start the cut 
    Vec_PtrClear( vFront );
    Vec_PtrPush( vFront, Aig_ObjFanin0(pRoot) );
    Vec_PtrPush( vFront, Aig_ObjFanin1(pRoot) );

    // start the visited nodes
    Vec_PtrClear( vVisited );
    Vec_PtrPush( vVisited, pRoot );
    Vec_PtrPush( vVisited, Aig_ObjFanin0(pRoot) );
    Vec_PtrPush( vVisited, Aig_ObjFanin1(pRoot) );

    // mark these nodes
    assert( !pRoot->fMarkA );
    assert( !Aig_ObjFanin0(pRoot)->fMarkA );
    assert( !Aig_ObjFanin1(pRoot)->fMarkA );
    pRoot->fMarkA = 1;
    Aig_ObjFanin0(pRoot)->fMarkA = 1;
    Aig_ObjFanin1(pRoot)->fMarkA = 1;

    // compute the cut
    while ( Aig_ManFindCut_int( vFront, vVisited, nSizeLimit, nFanoutLimit ) );
    assert( Vec_PtrSize(vFront) <= nSizeLimit );

    // clean the visit markings
    Vec_PtrForEachEntry( Aig_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 0;
}

int Aig_ManFindCut_int	(	Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vVisited,
		int	nSizeLimit,
		int	nFanoutLimit
	)

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

Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.]

Description [This procedure looks at the current leaves and tries to change one leaf at a time in such a way that the cut grows as little as possible. In evaluating the fanins, this procedure looks only at their immediate predecessors (this is why it is called a one-level construction procedure).]

SideEffects []

SeeAlso []

Definition at line 80 of file aigWin.c.

{
    Aig_Obj_t * pNode, * pFaninBest, * pNext;
    int CostBest, CostCur, i;
    // find the best fanin
    CostBest   = 100;
    pFaninBest = NULL;
//printf( "Evaluating fanins of the cut:\n" );
    Vec_PtrForEachEntry( Aig_Obj_t *, vFront, pNode, i )
    {
        CostCur = Aig_NodeGetLeafCostOne( pNode, nFanoutLimit );
//printf( "    Fanin %s has cost %d.\n", Aig_ObjName(pNode), CostCur );
        if ( CostBest > CostCur ||
            (CostBest == CostCur && pNode->Level > pFaninBest->Level) )
        {
            CostBest   = CostCur;
            pFaninBest = pNode;
        }
        if ( CostBest == 0 )
            break;
    }
    if ( pFaninBest == NULL )
        return 0;
    assert( CostBest < 3 );
    if ( Vec_PtrSize(vFront) - 1 + CostBest > nSizeLimit )
        return 0;
    assert( Aig_ObjIsNode(pFaninBest) );
    // remove the node from the array
    Vec_PtrRemove( vFront, pFaninBest );
//printf( "Removing fanin %s.\n", Aig_ObjName(pFaninBest) );

    // add the left child to the fanins
    pNext = Aig_ObjFanin0(pFaninBest);
    if ( !pNext->fMarkA )
    {
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
        pNext->fMarkA = 1;
        Vec_PtrPush( vFront, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    // add the right child to the fanins
    pNext = Aig_ObjFanin1(pFaninBest);
    if ( !pNext->fMarkA )
    {
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
        pNext->fMarkA = 1;
        Vec_PtrPush( vFront, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    assert( Vec_PtrSize(vFront) <= nSizeLimit );
    // keep doing this
    return 1;
}

static ABC_NAMESPACE_IMPL_START int Aig_NodeGetLeafCostOne ( Aig_Obj_t *  pNode, int  nFanoutLimit  )

inlinestatic

DECLARATIONS ///.

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

FileName [aigWin.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Window computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id:

aigWin.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Evaluate the cost of removing the node from the set of leaves.]

Description [Returns the number of new leaves that will be brought in. Returns large number if the node cannot be removed from the set of leaves.]

SideEffects []

SeeAlso []

Definition at line 46 of file aigWin.c.

{
    int Cost;
    // make sure the node is in the construction zone
    assert( pNode->fMarkA );  
    // cannot expand over the PI node
    if ( Aig_ObjIsCi(pNode) )
        return 999;
    // get the cost of the cone
    Cost = (!Aig_ObjFanin0(pNode)->fMarkA) + (!Aig_ObjFanin1(pNode)->fMarkA);
    // always accept if the number of leaves does not increase
    if ( Cost < 2 )
        return Cost;
    // skip nodes with many fanouts
    if ( (int)pNode->nRefs > nFanoutLimit )
        return 999;
    // return the number of nodes that will be on the leaves if this node is removed
    return Cost;
}