sfmWin.c File Reference

#include "sfmInt.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START int	Sfm_ObjRef_rec (Sfm_Ntk_t *p, int iObj)
	DECLARATIONS ///. More...
int	Sfm_ObjRef (Sfm_Ntk_t *p, int iObj)
int	Sfm_ObjDeref_rec (Sfm_Ntk_t *p, int iObj)
int	Sfm_ObjDeref (Sfm_Ntk_t *p, int iObj)
int	Sfm_ObjMffcSize (Sfm_Ntk_t *p, int iObj)
static void	Sfm_NtkIncrementTravId (Sfm_Ntk_t *p)
static void	Sfm_ObjSetTravIdCurrent (Sfm_Ntk_t *p, int Id)
static int	Sfm_ObjIsTravIdCurrent (Sfm_Ntk_t *p, int Id)
static int	Sfm_ObjIsTravIdPrevious (Sfm_Ntk_t *p, int Id)
static void	Sfm_NtkIncrementTravId2 (Sfm_Ntk_t *p)
static void	Sfm_ObjSetTravIdCurrent2 (Sfm_Ntk_t *p, int Id)
static int	Sfm_ObjIsTravIdCurrent2 (Sfm_Ntk_t *p, int Id)
void	Sfm_NtkDfs_rec (Sfm_Ntk_t *p, int iNode, Vec_Int_t *vNodes, Vec_Wec_t *vGroups, Vec_Int_t *vGroupMap, Vec_Int_t *vBoxesLeft)
Vec_Int_t *	Sfm_NtkDfs (Sfm_Ntk_t *p, Vec_Wec_t *vGroups, Vec_Int_t *vGroupMap, Vec_Int_t *vBoxesLeft)
int	Sfm_NtkCheckOverlap_rec (Sfm_Ntk_t *p, int iThis, int iNode)
int	Sfm_NtkCheckOverlap (Sfm_Ntk_t *p, int iFan, int iNode)
static int	Sfm_NtkCheckRoot (Sfm_Ntk_t *p, int iNode, int nLevelMax)
void	Sfm_NtkComputeRoots_rec (Sfm_Ntk_t *p, int iNode, int nLevelMax, Vec_Int_t *vRoots, Vec_Int_t *vTfo)
void	Sfm_NtkAddDivisors (Sfm_Ntk_t *p, int iNode, int nLevelMax)
static int	Sfm_ObjIsUseful (Sfm_Ntk_t *p, int iNode)
int	Sfm_NtkCollectTfi_rec (Sfm_Ntk_t *p, int iNode, Vec_Int_t *vNodes)
int	Sfm_NtkCreateWindow (Sfm_Ntk_t *p, int iNode, int fVerbose)
void	Sfm_NtkWindowTest (Sfm_Ntk_t *p, int iNode)

Function Documentation

void Sfm_NtkAddDivisors	(	Sfm_Ntk_t *	p,
		int	iNode,
		int	nLevelMax
	)

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

Synopsis [Collects divisors of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 262 of file sfmWin.c.

{
    int i, iFanout;
    Sfm_ObjForEachFanout( p, iNode, iFanout, i )
    {
        // skip some of the fanouts if the number is large
        if ( p->pPars->nFanoutMax && i > p->pPars->nFanoutMax )
            return;
        // skip TFI nodes, PO nodes, or nodes with high logic level
        if ( Sfm_ObjIsTravIdCurrent(p, iFanout) || Sfm_ObjIsPo(p, iFanout) || Sfm_ObjLevel(p, iFanout) > nLevelMax )
            continue;
        // handle single-input nodes
        if ( Sfm_ObjFaninNum(p, iFanout) == 1 )
            Vec_IntPush( p->vDivs, iFanout );
        // visit node for the first time
        else if ( !Sfm_ObjIsTravIdCurrent2(p, iFanout) )
        {
            assert( Sfm_ObjFaninNum(p, iFanout) > 1 );
            Sfm_ObjSetTravIdCurrent2( p, iFanout );
            Sfm_ObjResetFaninCount( p, iFanout );
        }
        // visit node again
        else if ( Sfm_ObjUpdateFaninCount(p, iFanout) == 0 )
            Vec_IntPush( p->vDivs, iFanout );
    }
}

int Sfm_NtkCheckOverlap	(	Sfm_Ntk_t *	p,
		int	iFan,
		int	iNode
	)

Definition at line 203 of file sfmWin.c.

{
    Sfm_NtkIncrementTravId2( p );
    return Sfm_NtkCheckOverlap_rec( p, iFan, iNode );
}

int Sfm_NtkCheckOverlap_rec	(	Sfm_Ntk_t *	p,
		int	iThis,
		int	iNode
	)

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

Synopsis [Check if this fanout overlaps with TFI cone of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 189 of file sfmWin.c.

{
    int i, iFanin;
    if ( Sfm_ObjIsTravIdCurrent2(p, iThis) || iThis == iNode )
        return 0;
//    if ( Sfm_ObjIsTravIdCurrent(p, iThis) )
    if ( Sfm_ObjIsTravIdPrevious(p, iThis) )
        return 1;
    Sfm_ObjSetTravIdCurrent2(p, iThis);
    Sfm_ObjForEachFanin( p, iThis, iFanin, i )
        if ( Sfm_NtkCheckOverlap_rec(p, iFanin, iNode) )
            return 1;
    return 0;
}

static int Sfm_NtkCheckRoot ( Sfm_Ntk_t *  p, int  iNode, int  nLevelMax  )

inlinestatic

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

Synopsis [Recursively collects roots of the window.]

Description []

SideEffects []

SeeAlso []

Definition at line 220 of file sfmWin.c.

{
    int i, iFanout;
    // the node is the root if one of the following is true:
    // (1) the node has more than fanouts than the limit or has no fanouts (should not happen in general)
    if ( Sfm_ObjFanoutNum(p, iNode) == 0 || Sfm_ObjFanoutNum(p, iNode) > p->pPars->nFanoutMax )
        return 1;
    // (2) the node has CO fanouts
    // (3) the node has fanouts above the cutoff level
    Sfm_ObjForEachFanout( p, iNode, iFanout, i )
        if ( Sfm_ObjIsPo(p, iFanout) || Sfm_ObjLevel(p, iFanout) > nLevelMax )//|| !Sfm_NtkCheckOverlap(p, iFanout, iNode) )
            return 1;
    return 0;
}

int Sfm_NtkCollectTfi_rec	(	Sfm_Ntk_t *	p,
		int	iNode,
		Vec_Int_t *	vNodes
	)

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

Synopsis [Computes structural window.]

Description []

SideEffects []

SeeAlso []

Definition at line 322 of file sfmWin.c.

{
    int i, iFanin;
    if ( Sfm_ObjIsTravIdCurrent( p, iNode ) )
        return 0;
    Sfm_ObjSetTravIdCurrent( p, iNode );
    Sfm_ObjForEachFanin( p, iNode, iFanin, i )
        if ( Sfm_NtkCollectTfi_rec( p, iFanin, vNodes ) )
            return 1;
    Vec_IntPush( vNodes, iNode );
    return p->pPars->nWinSizeMax && (Vec_IntSize(vNodes) > p->pPars->nWinSizeMax);
}

void Sfm_NtkComputeRoots_rec	(	Sfm_Ntk_t *	p,
		int	iNode,
		int	nLevelMax,
		Vec_Int_t *	vRoots,
		Vec_Int_t *	vTfo
	)

Definition at line 234 of file sfmWin.c.

{
    int i, iFanout;
    assert( Sfm_ObjIsNode(p, iNode) );
    if ( Sfm_ObjIsTravIdCurrent(p, iNode) )
        return;
    Sfm_ObjSetTravIdCurrent(p, iNode);
    if ( iNode != p->iPivotNode )
        Vec_IntPush( vTfo, iNode );
    // check if the node should be the root
    if ( Sfm_NtkCheckRoot( p, iNode, nLevelMax ) )
        Vec_IntPush( vRoots, iNode );
    else // if not, explore its fanouts
        Sfm_ObjForEachFanout( p, iNode, iFanout, i )
            Sfm_NtkComputeRoots_rec( p, iFanout, nLevelMax, vRoots, vTfo );
}

int Sfm_NtkCreateWindow	(	Sfm_Ntk_t *	p,
		int	iNode,
		int	fVerbose
	)

Definition at line 334 of file sfmWin.c.

{
    int i, k, iTemp;
    abctime clkDiv, clkWin = Abc_Clock();

    assert( Sfm_ObjIsNode( p, iNode ) );
    p->iPivotNode = iNode;
    Vec_IntClear( p->vNodes );  // internal
    Vec_IntClear( p->vDivs );   // divisors
    Vec_IntClear( p->vRoots );  // roots
    Vec_IntClear( p->vTfo );    // roots
    Vec_IntClear( p->vOrder );  // variable order

    // collect transitive fanin
    Sfm_NtkIncrementTravId( p );
    if ( Sfm_NtkCollectTfi_rec( p, iNode, p->vNodes ) )
    {
        p->nMaxDivs++;
        p->timeWin += Abc_Clock() - clkWin;
        return 0;
    }

    // create divisors
    clkDiv = Abc_Clock();
    Vec_IntClear( p->vDivs );
    Vec_IntAppend( p->vDivs, p->vNodes );
    Vec_IntPop( p->vDivs );
    // add non-topological divisors
    if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax + 0 )
    {
        Sfm_NtkIncrementTravId2( p );
        Vec_IntForEachEntry( p->vDivs, iTemp, i )
            if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax + 0 )
//                Sfm_NtkAddDivisors( p, iTemp, Sfm_ObjLevel(p, iNode) - 1 );
                Sfm_NtkAddDivisors( p, iTemp, p->nLevelMax - Sfm_ObjLevelR(p, iNode) ); 
    }
    if ( Vec_IntSize(p->vDivs) > p->pPars->nWinSizeMax )
    {
/*
        k = 0;
        Vec_IntForEachEntryStart( p->vDivs, iTemp, i, Vec_IntSize(p->vDivs) - p->pPars->nWinSizeMax )
            Vec_IntWriteEntry( p->vDivs, k++, iTemp );
        assert( k == p->pPars->nWinSizeMax );
*/
        Vec_IntShrink( p->vDivs, p->pPars->nWinSizeMax );
    }
    assert( Vec_IntSize(p->vDivs) <= p->pPars->nWinSizeMax );
    p->nMaxDivs += (int)(Vec_IntSize(p->vDivs) == p->pPars->nWinSizeMax);
    // remove node/fanins from divisors
    // mark fanins
    Sfm_NtkIncrementTravId2( p );
    Sfm_ObjSetTravIdCurrent2( p, iNode );
    Sfm_ObjForEachFanin( p, iNode, iTemp, i )
        Sfm_ObjSetTravIdCurrent2( p, iTemp );
    // compact divisors
    k = 0;
    Vec_IntForEachEntry( p->vDivs, iTemp, i )
        if ( !Sfm_ObjIsTravIdCurrent2(p, iTemp) && Sfm_ObjIsUseful(p, iTemp) )
            Vec_IntWriteEntry( p->vDivs, k++, iTemp );
    Vec_IntShrink( p->vDivs, k );
    assert( Vec_IntSize(p->vDivs) <= p->pPars->nWinSizeMax );
    clkDiv = Abc_Clock() - clkDiv;
    p->timeDiv += clkDiv;
    p->nTotalDivs += Vec_IntSize(p->vDivs);
 
    // collect TFO and window roots
    if ( p->pPars->nTfoLevMax > 0 && !Sfm_NtkCheckRoot(p, iNode, Sfm_ObjLevel(p, iNode) + p->pPars->nTfoLevMax) )
    {
        // explore transitive fanout
        Sfm_NtkIncrementTravId( p );
        Sfm_NtkComputeRoots_rec( p, iNode, Sfm_ObjLevel(p, iNode) + p->pPars->nTfoLevMax, p->vRoots, p->vTfo );
        assert( Vec_IntSize(p->vRoots) > 0 );
        assert( Vec_IntSize(p->vTfo) > 0 );
        // compute new leaves and nodes
        Sfm_NtkIncrementTravId( p );
        Vec_IntForEachEntry( p->vRoots, iTemp, i )
            if ( Sfm_NtkCollectTfi_rec( p, iTemp, p->vOrder ) )
            {
                Vec_IntClear( p->vRoots );
                Vec_IntClear( p->vTfo );
                Vec_IntClear( p->vOrder );
                break;
            }
        if ( Vec_IntSize(p->vRoots) > 0 )
        Vec_IntForEachEntry( p->vTfo, iTemp, i )
            if ( Sfm_NtkCollectTfi_rec( p, iTemp, p->vOrder ) )
            {
                Vec_IntClear( p->vRoots );
                Vec_IntClear( p->vTfo );
                Vec_IntClear( p->vOrder );
                break;
            }
        if ( Vec_IntSize(p->vRoots) > 0 )
        Vec_IntForEachEntry( p->vDivs, iTemp, i )
            if ( Sfm_NtkCollectTfi_rec( p, iTemp, p->vOrder ) )
            {
                Vec_IntClear( p->vRoots );
                Vec_IntClear( p->vTfo );
                Vec_IntClear( p->vOrder );
                break;
            }
    }

    if ( Vec_IntSize(p->vOrder) == 0 )
    {
        int Temp = p->pPars->nWinSizeMax;
        p->pPars->nWinSizeMax = 0;
        Sfm_NtkIncrementTravId( p );
        Sfm_NtkCollectTfi_rec( p, iNode, p->vOrder );
        Vec_IntForEachEntry( p->vDivs, iTemp, i )
            Sfm_NtkCollectTfi_rec( p, iTemp, p->vOrder );
        p->pPars->nWinSizeMax = Temp;
    }

    // statistics
    p->timeWin += Abc_Clock() - clkWin - clkDiv;
    if ( !fVerbose )
        return 1;

    // print stats about the window
    printf( "%6d : ", iNode );
    printf( "Leaves = %5d. ", 0 );
    printf( "Nodes = %5d. ",  Vec_IntSize(p->vNodes) );
    printf( "Roots = %5d. ",  Vec_IntSize(p->vRoots) );
    printf( "Divs = %5d. ",   Vec_IntSize(p->vDivs) );
    printf( "\n" );
    return 1;
}

Vec_Int_t* Sfm_NtkDfs	(	Sfm_Ntk_t *	p,
		Vec_Wec_t *	vGroups,
		Vec_Int_t *	vGroupMap,
		Vec_Int_t *	vBoxesLeft
	)

Definition at line 166 of file sfmWin.c.

{
    Vec_Int_t * vNodes;
    int i;
    Vec_IntClear( vBoxesLeft );
    vNodes = Vec_IntAlloc( p->nObjs );
    Sfm_NtkIncrementTravId( p );
    Sfm_NtkForEachPo( p, i )
        Sfm_NtkDfs_rec( p, Sfm_ObjFanin(p, i, 0), vNodes, vGroups, vGroupMap, vBoxesLeft );
    return vNodes;
}

void Sfm_NtkDfs_rec	(	Sfm_Ntk_t *	p,
		int	iNode,
		Vec_Int_t *	vNodes,
		Vec_Wec_t *	vGroups,
		Vec_Int_t *	vGroupMap,
		Vec_Int_t *	vBoxesLeft
	)

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

Synopsis [Collects used internal nodes in a topological order.]

Description [Additionally considers objects in groups as a single object and collects them in a topological order together as single entity.]

SideEffects []

SeeAlso []

Definition at line 136 of file sfmWin.c.

{
    int i, iFanin;
    if ( Sfm_ObjIsPi(p, iNode) )
        return;
    if ( Sfm_ObjIsTravIdCurrent(p, iNode) )
        return;
    if ( Vec_IntEntry(vGroupMap, iNode) >= 0 )
    {
        int k, iGroup = Abc_Lit2Var( Vec_IntEntry(vGroupMap, iNode) );
        Vec_Int_t * vGroup = Vec_WecEntry( vGroups, iGroup );
        Vec_IntForEachEntry( vGroup, iNode, i )
            assert( Sfm_ObjIsNode(p, iNode) );
        Vec_IntForEachEntry( vGroup, iNode, i )
            Sfm_ObjSetTravIdCurrent( p, iNode );
        Vec_IntForEachEntry( vGroup, iNode, i )
            Sfm_ObjForEachFanin( p, iNode, iFanin, k )
                Sfm_NtkDfs_rec( p, iFanin, vNodes, vGroups, vGroupMap, vBoxesLeft );
        Vec_IntForEachEntry( vGroup, iNode, i )
            Vec_IntPush( vNodes, iNode );
        Vec_IntPush( vBoxesLeft, iGroup );
    }
    else
    {
        Sfm_ObjSetTravIdCurrent(p, iNode);
        Sfm_ObjForEachFanin( p, iNode, iFanin, i )
            Sfm_NtkDfs_rec( p, iFanin, vNodes, vGroups, vGroupMap, vBoxesLeft );
        Vec_IntPush( vNodes, iNode );
    }
}

static void Sfm_NtkIncrementTravId ( Sfm_Ntk_t *  p )

inlinestatic

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

Synopsis [Working with traversal IDs.]

Description []

SideEffects []

SeeAlso []

Definition at line 114 of file sfmWin.c.

{ p->nTravIds++;                                            }       

static void Sfm_NtkIncrementTravId2 ( Sfm_Ntk_t *  p )

inlinestatic

Definition at line 119 of file sfmWin.c.

{ p->nTravIds2++;                                           }       

void Sfm_NtkWindowTest	(	Sfm_Ntk_t *	p,
		int	iNode
	)

Definition at line 462 of file sfmWin.c.

{
    int i;
    Sfm_NtkForEachNode( p, i )
        Sfm_NtkCreateWindow( p, i, 1 );
}

int Sfm_ObjDeref	(	Sfm_Ntk_t *	p,
		int	iObj
	)

Definition at line 82 of file sfmWin.c.

{
    int i, iFanin, Count = 1;
    Sfm_ObjForEachFanin( p, iObj, iFanin, i )
        Count += Sfm_ObjDeref_rec( p, iFanin );
    return Count;
}

int Sfm_ObjDeref_rec	(	Sfm_Ntk_t *	p,
		int	iObj
	)

Definition at line 67 of file sfmWin.c.

{
    int i, iFanin, Value, Count;
    if ( Sfm_ObjIsPi(p, iObj) )
        return 0;
    assert( Sfm_ObjIsNode(p, iObj) );
    Value = Sfm_ObjRefDecrement(p, iObj);
    if ( Value > 0 )
        return 0;
    assert( Value == 0 );
    Count = 1;
    Sfm_ObjForEachFanin( p, iObj, iFanin, i )
        Count += Sfm_ObjDeref_rec( p, iFanin );
    return Count;
}

static int Sfm_ObjIsTravIdCurrent ( Sfm_Ntk_t *  p, int  Id  )

inlinestatic

Definition at line 116 of file sfmWin.c.

{ return (Vec_IntEntry(&p->vTravIds, Id) == p->nTravIds);   }   

static int Sfm_ObjIsTravIdCurrent2 ( Sfm_Ntk_t *  p, int  Id  )

inlinestatic

Definition at line 121 of file sfmWin.c.

{ return (Vec_IntEntry(&p->vTravIds2, Id) == p->nTravIds2); }   

static int Sfm_ObjIsTravIdPrevious ( Sfm_Ntk_t *  p, int  Id  )

inlinestatic

Definition at line 117 of file sfmWin.c.

{ return (Vec_IntEntry(&p->vTravIds, Id) == p->nTravIds-1); }   

static int Sfm_ObjIsUseful ( Sfm_Ntk_t *  p, int  iNode  )

inlinestatic

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

Synopsis [Fixed object is useful when it has a non-fixed fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 300 of file sfmWin.c.

{
    int i, iFanout;
    if ( !Sfm_ObjIsFixed(p, iNode) )
        return 1;
    Sfm_ObjForEachFanout( p, iNode, iFanout, i )
        if ( !Sfm_ObjIsFixed(p, iFanout) )
            return 1;
    return 0;
}

int Sfm_ObjMffcSize	(	Sfm_Ntk_t *	p,
		int	iObj
	)

Definition at line 89 of file sfmWin.c.

{
    int Count1, Count2;
    if ( Sfm_ObjIsPi(p, iObj) )
        return 0;
    if ( Sfm_ObjFanoutNum(p, iObj) != 1 )
        return 0;
    assert( Sfm_ObjIsNode( p, iObj ) );
    Count1 = Sfm_ObjDeref( p, iObj );
    Count2 = Sfm_ObjRef( p, iObj );
    assert( Count1 == Count2 );
    return Count1;
}

int Sfm_ObjRef	(	Sfm_Ntk_t *	p,
		int	iObj
	)

Definition at line 60 of file sfmWin.c.

{
    int i, iFanin, Count = 1;
    Sfm_ObjForEachFanin( p, iObj, iFanin, i )
        Count += Sfm_ObjRef_rec( p, iFanin );
    return Count;
}

ABC_NAMESPACE_IMPL_START int Sfm_ObjRef_rec	(	Sfm_Ntk_t *	p,
		int	iObj
	)

DECLARATIONS ///.

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

FileName [sfmWin.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [SAT-based optimization using internal don't-cares.]

Synopsis [Structural window computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

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

Synopsis [Returns the MFFC size.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file sfmWin.c.

{
    int i, iFanin, Value, Count;
    if ( Sfm_ObjIsPi(p, iObj) )
        return 0;
    assert( Sfm_ObjIsNode(p, iObj) );
    Value = Sfm_ObjRefIncrement(p, iObj);
    if ( Value > 1 )
        return 0;
    assert( Value == 1 );
    Count = 1;
    Sfm_ObjForEachFanin( p, iObj, iFanin, i )
        Count += Sfm_ObjRef_rec( p, iFanin );
    return Count;
}

static void Sfm_ObjSetTravIdCurrent ( Sfm_Ntk_t *  p, int  Id  )

inlinestatic

Definition at line 115 of file sfmWin.c.

{ Vec_IntWriteEntry( &p->vTravIds, Id, p->nTravIds );       }

static void Sfm_ObjSetTravIdCurrent2 ( Sfm_Ntk_t *  p, int  Id  )

inlinestatic

Definition at line 120 of file sfmWin.c.

{ Vec_IntWriteEntry( &p->vTravIds2, Id, p->nTravIds2 );     }