sbdCut.c File Reference

#include "sbdInt.h"

Include dependency graph for sbdCut.c:

Go to the source code of this file.

Classes
struct	Sbd_Cut_t_
struct	Sbd_Sto_t_

Macros
#define	SBD_MAX_CUTSIZE   10
	DECLARATIONS ///.
#define	SBD_MAX_CUTNUM   501
#define	SBD_MAX_TT_WORDS   ((SBD_MAX_CUTSIZE > 6) ? 1 << (SBD_MAX_CUTSIZE-6) : 1)
#define	SBD_CUT_NO_LEAF   0xF
#define	Sbd_ForEachCut(pList, pCut, i)

Typedefs
typedef struct Sbd_Cut_t_	Sbd_Cut_t

Functions
void	Sbd_StoMergeCuts (Sbd_Sto_t *p, int iObj)
Sbd_Sto_t *	Sbd_StoAlloc (Gia_Man_t *pGia, Vec_Int_t *vMirrors, int nLutSize, int nCutSize, int nCutNum, int fCutMin, int fVerbose)
	MACRO DEFINITIONS ///.
void	Sbd_StoFree (Sbd_Sto_t *p)
void	Sbd_StoComputeCutsObj (Sbd_Sto_t *p, int iObj, int Delay, int Level)
void	Sbd_StoComputeCutsConst0 (Sbd_Sto_t *p, int iObj)
void	Sbd_StoComputeCutsCi (Sbd_Sto_t *p, int iObj, int Delay, int Level)
int	Sbd_StoComputeCutsNode (Sbd_Sto_t *p, int iObj)
void	Sbd_StoSaveBestDelayCut (Sbd_Sto_t *p, int iObj, int *pCut)
int	Sbd_StoObjRefs (Sbd_Sto_t *p, int iObj)
void	Sbd_StoRefObj (Sbd_Sto_t *p, int iObj, int iMirror)
void	Sbd_StoDerefObj (Sbd_Sto_t *p, int iObj)
int	Sbd_StoObjBestCut (Sbd_Sto_t *p, int iObj, int nSize, int *pLeaves)
void	Sbd_StoComputeCutsTest (Gia_Man_t *pGia)

Macro Definition Documentation

SBD_CUT_NO_LEAF

#define SBD_CUT_NO_LEAF   0xF

Definition at line 34 of file sbdCut.c.

Sbd_ForEachCut

#define Sbd_ForEachCut	(		pList,
			pCut,
			i )

Value:

for ( i = 0, pCut = pList + 1; i < pList[0]; i++, pCut += pCut[0] + 2 )

Definition at line 78 of file sbdCut.c.

SBD_MAX_CUTNUM

#define SBD_MAX_CUTNUM   501

Definition at line 31 of file sbdCut.c.

SBD_MAX_CUTSIZE

#define SBD_MAX_CUTSIZE   10

DECLARATIONS ///.

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

FileName [sbdCut.c]

SystemName [ABC: Logic synthesis and verification system.]

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

Synopsis [Cut computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

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

]

Definition at line 30 of file sbdCut.c.

SBD_MAX_TT_WORDS

#define SBD_MAX_TT_WORDS   ((SBD_MAX_CUTSIZE > 6) ? 1 << (SBD_MAX_CUTSIZE-6) : 1)

Definition at line 32 of file sbdCut.c.

Typedef Documentation

Sbd_Cut_t

typedef struct Sbd_Cut_t_ Sbd_Cut_t

Definition at line 36 of file sbdCut.c.

Function Documentation

Sbd_StoAlloc()

Sbd_Sto_t * Sbd_StoAlloc	(	Gia_Man_t *	pGia,
		Vec_Int_t *	vMirrors,
		int	nLutSize,
		int	nCutSize,
		int	nCutNum,
		int	fCutMin,
		int	fVerbose )

MACRO DEFINITIONS ///.

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

Synopsis [Incremental cut computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 667 of file sbdCut.c.

{
    Sbd_Sto_t * p;
    assert( nLutSize <= nCutSize );
    assert( nCutSize < SBD_CUT_NO_LEAF );
    assert( nCutSize > 1 && nCutSize <= SBD_MAX_CUTSIZE );
    assert( nCutNum > 1 && nCutNum < SBD_MAX_CUTNUM );
    p = ABC_CALLOC( Sbd_Sto_t, 1 );
    p->clkStart = Abc_Clock();
    p->nLutSize = nLutSize;
    p->nCutSize = nCutSize;
    p->nCutNum  = nCutNum;
    p->fCutMin  = fCutMin;
    p->fVerbose = fVerbose;
    p->pGia     = pGia;
    p->vMirrors = vMirrors;
    p->vDelays  = Vec_IntStart( Gia_ManObjNum(pGia) );
    p->vLevels  = Vec_IntStart( Gia_ManObjNum(pGia) );
    p->vRefs    = Vec_IntAlloc( Gia_ManObjNum(pGia) );
    p->vCuts    = Vec_WecStart( Gia_ManObjNum(pGia) );
    p->vTtMem   = fCutMin ? Vec_MemAllocForTT( nCutSize, 0 ) : NULL;
    return p;
}

Here is the caller graph for this function:

Sbd_StoComputeCutsCi()

void Sbd_StoComputeCutsCi	(	Sbd_Sto_t *	p,
		int	iObj,
		int	Delay,
		int	Level )

Definition at line 724 of file sbdCut.c.

{
    Sbd_StoComputeCutsObj( p, iObj, Delay, Level );
    Sbd_CutAddUnit( p, iObj );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Sbd_StoComputeCutsConst0()

void Sbd_StoComputeCutsConst0	(	Sbd_Sto_t *	p,
		int	iObj )

Definition at line 719 of file sbdCut.c.

{
    Sbd_StoComputeCutsObj( p, iObj, 0, 0 );
    Sbd_CutAddZero( p, iObj );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Sbd_StoComputeCutsNode()

int Sbd_StoComputeCutsNode	(	Sbd_Sto_t *	p,
		int	iObj )

Definition at line 729 of file sbdCut.c.

{
    Gia_Obj_t * pObj = Gia_ManObj(p->pGia, iObj);
    int Lev0 = Vec_IntEntry( p->vLevels, Gia_ObjFaninId0(pObj, iObj) );
    int Lev1 = Vec_IntEntry( p->vLevels, Gia_ObjFaninId1(pObj, iObj) );
    Sbd_StoComputeCutsObj( p, iObj, -1, 1 + Abc_MaxInt(Lev0, Lev1) );
    Sbd_StoMergeCuts( p, iObj );
    return Vec_IntEntry( p->vDelays, iObj );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Sbd_StoComputeCutsObj()

void Sbd_StoComputeCutsObj	(	Sbd_Sto_t *	p,
		int	iObj,
		int	Delay,
		int	Level )

Definition at line 702 of file sbdCut.c.

{
    if ( iObj < Vec_IntSize(p->vDelays) )
    {
        Vec_IntWriteEntry( p->vDelays, iObj, Delay );
        Vec_IntWriteEntry( p->vLevels, iObj, Level );
    }
    else
    {
        assert( iObj == Vec_IntSize(p->vDelays) );
        assert( iObj == Vec_IntSize(p->vLevels) );
        assert( iObj == Vec_WecSize(p->vCuts) );
        Vec_IntPush( p->vDelays, Delay );
        Vec_IntPush( p->vLevels, Level );
        Vec_WecPushLevel( p->vCuts );
    }
}

Here is the caller graph for this function:

Sbd_StoComputeCutsTest()

void Sbd_StoComputeCutsTest

(

Gia_Man_t *

pGia

)

Definition at line 833 of file sbdCut.c.

{
    Sbd_Sto_t * p = Sbd_StoAlloc( pGia, NULL, 4, 8, 100, 1, 1 );
    Gia_Obj_t * pObj;   
    int i, iObj;
    // prepare references
    Gia_ManForEachObj( p->pGia, pObj, iObj )
        Sbd_StoRefObj( p, iObj, -1 );
    // compute cuts
    Sbd_StoComputeCutsConst0( p, 0 );
    Gia_ManForEachCiId( p->pGia, iObj, i )
        Sbd_StoComputeCutsCi( p, iObj, 0, 0 );
    Gia_ManForEachAnd( p->pGia, pObj, iObj )
        Sbd_StoComputeCutsNode( p, iObj );
    if ( p->fVerbose )
    {
        printf( "Running cut computation with LutSize = %d  CutSize = %d  CutNum = %d:\n", p->nLutSize, p->nCutSize, p->nCutNum );
        printf( "CutPair = %.0f  ",         p->CutCount[0] );
        printf( "Merge = %.0f (%.2f %%)  ", p->CutCount[1], 100.0*p->CutCount[1]/p->CutCount[0] );
        printf( "Eval = %.0f (%.2f %%)  ",  p->CutCount[2], 100.0*p->CutCount[2]/p->CutCount[0] );
        printf( "Cut = %.0f (%.2f %%)  ",   p->CutCount[3], 100.0*p->CutCount[3]/p->CutCount[0] );
        printf( "Cut/Node = %.2f  ",        p->CutCount[3] / Gia_ManAndNum(p->pGia) );
        printf( "\n" );
        printf( "Spec = %4d  ",             p->nCutsSpec );
        printf( "Over = %4d  ",             p->nCutsOver );
        printf( "Lev = %4d  ",              p->DelayMin );
        Abc_PrintTime( 0, "Time", Abc_Clock() - p->clkStart );
    }
    Sbd_StoFree( p );
}

Here is the call graph for this function:

Sbd_StoDerefObj()

void Sbd_StoDerefObj	(	Sbd_Sto_t *	p,
		int	iObj )

Definition at line 778 of file sbdCut.c.

{
    Gia_Obj_t * pObj;
    int Lit0m, Lit1m, Fan0, Fan1;
    return;
 
    pObj = Gia_ManObj(p->pGia, iObj);
    if ( Vec_IntEntry(p->vRefs, iObj) == 0 )
        printf( "Ref count mismatch at node %d\n", iObj );
    assert( Vec_IntEntry(p->vRefs, iObj) > 0 );
    Vec_IntAddToEntry( p->vRefs, iObj, -1 );
    if ( Vec_IntEntry( p->vRefs, iObj ) > 0 )
        return;
    if ( Gia_ObjIsCi(pObj) )
        return;
//printf( "Deref %d\n", iObj );
    assert( Gia_ObjIsAnd(pObj) );
    Lit0m = Vec_IntEntry( p->vMirrors, Gia_ObjFaninId0(pObj, iObj) );
    Lit1m = Vec_IntEntry( p->vMirrors, Gia_ObjFaninId1(pObj, iObj) );
    Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, iObj);
    Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, iObj);
    if ( Fan0 ) Sbd_StoDerefObj( p, Fan0 );
    if ( Fan1 ) Sbd_StoDerefObj( p, Fan1 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Sbd_StoFree()

void Sbd_StoFree

(

Sbd_Sto_t *

p

)

Definition at line 690 of file sbdCut.c.

{
    Vec_IntFree( p->vDelays );
    Vec_IntFree( p->vLevels );
    Vec_IntFree( p->vRefs );
    Vec_WecFree( p->vCuts );
    if ( p->fCutMin )
        Vec_MemHashFree( p->vTtMem );
    if ( p->fCutMin )
        Vec_MemFree( p->vTtMem );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Sbd_StoMergeCuts()

void Sbd_StoMergeCuts	(	Sbd_Sto_t *	p,
		int	iObj )

Definition at line 594 of file sbdCut.c.

{
    Gia_Obj_t * pObj = Gia_ManObj(p->pGia, iObj);
    int fIsXor       = Gia_ObjIsXor(pObj);
    int nCutSize     = p->nCutSize;
    int nCutNum      = p->nCutNum;
    int Lit0m        = p->vMirrors ? Vec_IntEntry( p->vMirrors, Gia_ObjFaninId0(pObj, iObj) ) : -1;
    int Lit1m        = p->vMirrors ? Vec_IntEntry( p->vMirrors, Gia_ObjFaninId1(pObj, iObj) ) : -1;
    int fComp0       = Gia_ObjFaninC0(pObj) ^ (Lit0m >= 0 && Abc_LitIsCompl(Lit0m));
    int fComp1       = Gia_ObjFaninC1(pObj) ^ (Lit1m >= 0 && Abc_LitIsCompl(Lit1m));
    int Fan0         = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, iObj);
    int Fan1         = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, iObj);
    int nCuts0       = Sbd_StoPrepareSet( p, Fan0, 0 );
    int nCuts1       = Sbd_StoPrepareSet( p, Fan1, 1 );
    int i, k, nCutsR = 0;
    Sbd_Cut_t * pCut0, * pCut1, ** pCutsR = p->ppCuts;
    assert( !Gia_ObjIsBuf(pObj) );
    assert( !Gia_ObjIsMux(p->pGia, pObj) );
    Sbd_StoInitResult( p );
    p->CutCount[0] += nCuts0 * nCuts1;
    for ( i = 0, pCut0 = p->pCuts[0]; i < nCuts0; i++, pCut0++ )
    for ( k = 0, pCut1 = p->pCuts[1]; k < nCuts1; k++, pCut1++ )
    {
        if ( (int)(pCut0->nLeaves + pCut1->nLeaves) > nCutSize && Sbd_CutCountBits(pCut0->Sign | pCut1->Sign) > nCutSize )
            continue;
        p->CutCount[1]++; 
        if ( !Sbd_CutMergeOrder(pCut0, pCut1, pCutsR[nCutsR], nCutSize) )
            continue;
        if ( Sbd_CutSetLastCutIsContained(pCutsR, nCutsR) )
            continue;
        p->CutCount[2]++;
        if ( p->fCutMin && Sbd_CutComputeTruth(p, pCut0, pCut1, fComp0, fComp1, pCutsR[nCutsR], fIsXor) )
            pCutsR[nCutsR]->Sign = Sbd_CutGetSign(pCutsR[nCutsR]);
        pCutsR[nCutsR]->Cost = Sbd_CutCost( p, pCutsR[nCutsR] );
        pCutsR[nCutsR]->CostLev = Sbd_CutCostLev( p, pCutsR[nCutsR] );
        pCutsR[nCutsR]->nTreeLeaves = Sbd_CutTreeLeaves( p, pCutsR[nCutsR] );
        nCutsR = Sbd_CutSetAddCut( pCutsR, nCutsR, nCutNum );
    }
    Sbd_StoComputeDelay( p, iObj, pCutsR, nCutsR );
    Sbd_StoComputeSpec( p, iObj, pCutsR, nCutsR );
    p->CutCount[3] += nCutsR;
    p->nCutsOver += nCutsR == nCutNum-1;
    p->nCutsR = nCutsR;
    p->Pivot = iObj;
    // debug printout
    if ( 0 )
    {
        printf( "*** Obj = %4d  Delay = %4d  NumCuts = %4d\n", iObj, Vec_IntEntry(p->vDelays, iObj), nCutsR );
        for ( i = 0; i < nCutsR; i++ )
            if ( (int)pCutsR[i]->nLeaves <= p->nLutSize || pCutsR[i]->nSlowLeaves < 2 )
                Sbd_CutPrint( p, iObj, pCutsR[i] );
        printf( "\n" );
    }
    // verify
    assert( nCutsR > 0 && nCutsR < nCutNum );
    assert( Sbd_CutSetCheckArray(pCutsR, nCutsR) );
    // store the cutset
    Sbd_StoStoreResult( p, iObj, pCutsR, nCutsR );
    if ( nCutsR > 1 || pCutsR[0]->nLeaves > 1 )
        Sbd_CutAddUnit( p, iObj );
}

Here is the caller graph for this function:

Sbd_StoObjBestCut()

int Sbd_StoObjBestCut	(	Sbd_Sto_t *	p,
		int	iObj,
		int	nSize,
		int *	pLeaves )

Definition at line 802 of file sbdCut.c.

{
    int fVerbose = 0;
    Sbd_Cut_t * pCutBest = NULL;   int i;
    assert( p->Pivot == iObj );
    if ( fVerbose && iObj % 1000 == 0 )
        printf( "Node %6d : \n", iObj );
    for ( i = 0; i < p->nCutsR; i++ )
    {
        if ( fVerbose && iObj % 1000 == 0 )
            Sbd_CutPrint( p, iObj, p->ppCuts[i] );
        if ( nSize && (int)p->ppCuts[i]->nLeaves != nSize )
            continue;
        if ( (int)p->ppCuts[i]->nLeaves > p->nLutSize && 
             (int)p->ppCuts[i]->nSlowLeaves <= 1 &&
             (int)p->ppCuts[i]->nTopLeaves <= p->nLutSize-1 &&
             (pCutBest == NULL || Sbd_CutCompare2(pCutBest, p->ppCuts[i]) == 1) )
            pCutBest = p->ppCuts[i];
    }
    if ( fVerbose && iObj % 1000 == 0 )
    {
        printf( "Best cut of size %d:\n", nSize );
        Sbd_CutPrint( p, iObj, pCutBest );
    }
    if ( pCutBest == NULL )
        return -1;
    assert( pCutBest->nLeaves <= SBD_DIV_MAX );
    for ( i = 0; i < (int)pCutBest->nLeaves; i++ )
        pLeaves[i] = pCutBest->pLeaves[i];
    return pCutBest->nLeaves;
}

Here is the caller graph for this function:

Sbd_StoObjRefs()

int Sbd_StoObjRefs	(	Sbd_Sto_t *	p,
		int	iObj )

Definition at line 746 of file sbdCut.c.

{
    return Vec_IntEntry(p->vRefs, iObj);
}

Sbd_StoRefObj()

void Sbd_StoRefObj	(	Sbd_Sto_t *	p,
		int	iObj,
		int	iMirror )

Definition at line 750 of file sbdCut.c.

{
    Gia_Obj_t * pObj = Gia_ManObj(p->pGia, iObj);
    assert( iObj == Vec_IntSize(p->vRefs) );
    assert( iMirror < iObj );
    Vec_IntPush( p->vRefs, 0 );
//printf( "Ref %d\n", iObj );
    if ( iMirror > 0 )
    {
        Vec_IntWriteEntry( p->vRefs, iObj, Vec_IntEntry(p->vRefs, iMirror) );
        Vec_IntWriteEntry( p->vRefs, iMirror, 1 );
    }
    if ( Gia_ObjIsAnd(pObj) )
    {
        int Lit0m = Vec_IntEntry( p->vMirrors, Gia_ObjFaninId0(pObj, iObj) );
        int Lit1m = Vec_IntEntry( p->vMirrors, Gia_ObjFaninId1(pObj, iObj) );
        int Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, iObj);
        int Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, iObj);
        Vec_IntAddToEntry( p->vRefs, Fan0, 1 );
        Vec_IntAddToEntry( p->vRefs, Fan1, 1 );
    }
    else if ( Gia_ObjIsCo(pObj) )
    {
        int Lit0m = Vec_IntEntry( p->vMirrors, Gia_ObjFaninId0(pObj, iObj) );
        assert( Lit0m == -1 );
        Vec_IntAddToEntry( p->vRefs, Gia_ObjFaninId0(pObj, iObj), 1 );
    }
}

Here is the caller graph for this function:

Sbd_StoSaveBestDelayCut()

void Sbd_StoSaveBestDelayCut	(	Sbd_Sto_t *	p,
		int	iObj,
		int *	pCut )

Definition at line 738 of file sbdCut.c.

{
    Sbd_Cut_t * pCutBest = p->ppCuts[p->iCutBest]; int i;
    assert( iObj == p->Pivot );
    pCut[0] = pCutBest->nLeaves;
    for ( i = 0; i < (int)pCutBest->nLeaves; i++ )
        pCut[i+1] = pCutBest->pLeaves[i];
}

Here is the caller graph for this function: