cswInt.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "aig/aig/aig.h"
#include "opt/dar/dar.h"
#include "bool/kit/kit.h"
#include "csw.h"

Go to the source code of this file.

Data Structures
struct	Csw_Cut_t_
struct	Csw_Man_t_

Macros
#define	Csw_ObjForEachCut(p, pObj, pCut, i)   for ( i = 0, pCut = Csw_ObjCuts(p, pObj); i < p->nCutsMax; i++, pCut = Csw_CutNext(pCut) )
	MACRO DEFINITIONS ///. More...
#define	Csw_CutForEachLeaf(p, pCut, pLeaf, i)   for ( i = 0; (i < (int)(pCut)->nFanins) && ((pLeaf) = Aig_ManObj(p, (pCut)->pFanins[i])); i++ )

Typedefs
typedef typedefABC_NAMESPACE_HEADER_START struct Csw_Man_t_	Csw_Man_t
	INCLUDES ///. More...
typedef struct Csw_Cut_t_	Csw_Cut_t

Functions
static int	Csw_CutLeaveNum (Csw_Cut_t *pCut)
static int *	Csw_CutLeaves (Csw_Cut_t *pCut)
static unsigned *	Csw_CutTruth (Csw_Cut_t *pCut)
static Csw_Cut_t *	Csw_CutNext (Csw_Cut_t *pCut)
static int	Csw_ObjRefs (Csw_Man_t *p, Aig_Obj_t *pObj)
static void	Csw_ObjAddRefs (Csw_Man_t *p, Aig_Obj_t *pObj, int nRefs)
static Csw_Cut_t *	Csw_ObjCuts (Csw_Man_t *p, Aig_Obj_t *pObj)
static void	Csw_ObjSetCuts (Csw_Man_t *p, Aig_Obj_t *pObj, Csw_Cut_t *pCuts)
static Aig_Obj_t *	Csw_ObjEquiv (Csw_Man_t *p, Aig_Obj_t *pObj)
static void	Csw_ObjSetEquiv (Csw_Man_t *p, Aig_Obj_t *pObj, Aig_Obj_t *pEquiv)
static Aig_Obj_t *	Csw_ObjChild0Equiv (Csw_Man_t *p, Aig_Obj_t *pObj)
static Aig_Obj_t *	Csw_ObjChild1Equiv (Csw_Man_t *p, Aig_Obj_t *pObj)
Csw_Cut_t *	Csw_ObjPrepareCuts (Csw_Man_t *p, Aig_Obj_t *pObj, int fTriv)
	FUNCTION DECLARATIONS ///. More...
Aig_Obj_t *	Csw_ObjSweep (Csw_Man_t *p, Aig_Obj_t *pObj, int fTriv)
Csw_Man_t *	Csw_ManStart (Aig_Man_t *pMan, int nCutsMax, int nLeafMax, int fVerbose)
	DECLARATIONS ///. More...
void	Csw_ManStop (Csw_Man_t *p)
int	Csw_TableCountCuts (Csw_Man_t *p)
void	Csw_TableCutInsert (Csw_Man_t *p, Csw_Cut_t *pCut)
Aig_Obj_t *	Csw_TableCutLookup (Csw_Man_t *p, Csw_Cut_t *pCut)

Macro Definition Documentation

#define Csw_CutForEachLeaf	(		p,
			pCut,
			pLeaf,
			i
	)		for ( i = 0; (i < (int)(pCut)->nFanins) && ((pLeaf) = Aig_ManObj(p, (pCut)->pFanins[i])); i++ )

Definition at line 131 of file cswInt.h.

#define Csw_ObjForEachCut	(		p,
			pObj,
			pCut,
			i
	)		for ( i = 0, pCut = Csw_ObjCuts(p, pObj); i < p->nCutsMax; i++, pCut = Csw_CutNext(pCut) )

MACRO DEFINITIONS ///.

ITERATORS ///

Definition at line 128 of file cswInt.h.

Typedef Documentation

typedef struct Csw_Cut_t_ Csw_Cut_t

Definition at line 53 of file cswInt.h.

typedef typedefABC_NAMESPACE_HEADER_START struct Csw_Man_t_ Csw_Man_t

INCLUDES ///.

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

FileName [cswInt.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Cut sweeping.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - July 11, 2007.]

Revision [

Id:

cswInt.h,v 1.00 2007/07/11 00:00:00 alanmi Exp

]PARAMETERS ///BASIC TYPES ///

Definition at line 52 of file cswInt.h.

Function Documentation

static int Csw_CutLeaveNum ( Csw_Cut_t *  pCut )

inlinestatic

Definition at line 102 of file cswInt.h.

{ return pCut->nFanins;                                   }

static int* Csw_CutLeaves ( Csw_Cut_t *  pCut )

inlinestatic

Definition at line 103 of file cswInt.h.

{ return pCut->pFanins;                                   }

static Csw_Cut_t* Csw_CutNext ( Csw_Cut_t *  pCut )

inlinestatic

Definition at line 105 of file cswInt.h.

{ return (Csw_Cut_t *)(((char *)pCut) + pCut->nCutSize);  }

static unsigned* Csw_CutTruth ( Csw_Cut_t *  pCut )

inlinestatic

Definition at line 104 of file cswInt.h.

{ return (unsigned *)(pCut->pFanins + pCut->nLeafMax);    }

Csw_Man_t* Csw_ManStart	(	Aig_Man_t *	pMan,
		int	nCutsMax,
		int	nLeafMax,
		int	fVerbose
	)

DECLARATIONS ///.

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

FileName [cswMan.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Cut sweeping.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - July 11, 2007.]

Revision [

Id:

cswMan.c,v 1.00 2007/07/11 00:00:00 alanmi Exp

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

Synopsis [Starts the cut sweeping manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file cswMan.c.

{
    Csw_Man_t * p;
    Aig_Obj_t * pObj;
    int i;
    assert( nCutsMax >= 2  );
    assert( nLeafMax <= 16 );
    // allocate the fraiging manager
    p = ABC_ALLOC( Csw_Man_t, 1 );
    memset( p, 0, sizeof(Csw_Man_t) );
    p->nCutsMax = nCutsMax;
    p->nLeafMax = nLeafMax;
    p->fVerbose = fVerbose;
    p->pManAig  = pMan;
    // create the new manager
    p->pManRes  = Aig_ManStartFrom( pMan );
    assert( Aig_ManCiNum(p->pManAig) == Aig_ManCiNum(p->pManRes) );
    // allocate room for cuts and equivalent nodes
    p->pnRefs   = ABC_ALLOC( int, Aig_ManObjNumMax(pMan) );
    p->pEquiv   = ABC_ALLOC( Aig_Obj_t *, Aig_ManObjNumMax(pMan) );
    p->pCuts    = ABC_ALLOC( Csw_Cut_t *, Aig_ManObjNumMax(pMan) );
    memset( p->pCuts, 0, sizeof(Aig_Obj_t *) * Aig_ManObjNumMax(pMan) );
    memset( p->pnRefs, 0, sizeof(int) * Aig_ManObjNumMax(pMan) );
    // allocate memory manager
    p->nTruthWords = Abc_TruthWordNum(nLeafMax);
    p->nCutSize = sizeof(Csw_Cut_t) + sizeof(int) * nLeafMax + sizeof(unsigned) * p->nTruthWords;
    p->pMemCuts = Aig_MmFixedStart( p->nCutSize * p->nCutsMax, 512 );
    // allocate hash table for cuts
    p->nTableSize = Abc_PrimeCudd( Aig_ManNodeNum(pMan) * p->nCutsMax / 2 );
    p->pTable = ABC_ALLOC( Csw_Cut_t *, p->nTableSize );
    memset( p->pTable, 0, sizeof(Aig_Obj_t *) * p->nTableSize );
    // set the pointers to the available fraig nodes
    Csw_ObjSetEquiv( p, Aig_ManConst1(p->pManAig), Aig_ManConst1(p->pManRes) );
    Aig_ManForEachCi( p->pManAig, pObj, i )
        Csw_ObjSetEquiv( p, pObj, Aig_ManCi(p->pManRes, i) );
    // room for temporary truth tables
    p->puTemp[0] = ABC_ALLOC( unsigned, 4 * p->nTruthWords );
    p->puTemp[1] = p->puTemp[0] + p->nTruthWords;
    p->puTemp[2] = p->puTemp[1] + p->nTruthWords;
    p->puTemp[3] = p->puTemp[2] + p->nTruthWords;
    return p;
}

void Csw_ManStop

(

Csw_Man_t *

p

)

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

Synopsis [Stops the fraiging manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 99 of file cswMan.c.

{
    if ( p->fVerbose )
    {
        int nNodesBeg = Aig_ManNodeNum(p->pManAig);
        int nNodesEnd = Aig_ManNodeNum(p->pManRes);
        printf( "Beg = %7d.  End = %7d.  (%6.2f %%)  Try = %7d.  Cuts = %8d.\n", 
            nNodesBeg, nNodesEnd, 100.0*(nNodesBeg-nNodesEnd)/nNodesBeg,
            p->nNodesTried, Csw_TableCountCuts( p ) );
        printf( "Triv0 = %6d.  Triv1 = %6d.  Triv2 = %6d.  Cut-replace = %6d.\n", 
            p->nNodesTriv0, p->nNodesTriv1, p->nNodesTriv2, p->nNodesCuts );
        ABC_PRTP( "Cuts    ", p->timeCuts,     p->timeTotal );
        ABC_PRTP( "Hashing ", p->timeHash,     p->timeTotal );
        ABC_PRTP( "Other   ", p->timeOther,    p->timeTotal );
        ABC_PRTP( "TOTAL   ", p->timeTotal,    p->timeTotal );
    }
    ABC_FREE( p->puTemp[0] );
    Aig_MmFixedStop( p->pMemCuts, 0 );
    ABC_FREE( p->pnRefs );
    ABC_FREE( p->pEquiv );
    ABC_FREE( p->pCuts );
    ABC_FREE( p->pTable );
    ABC_FREE( p );
}

static void Csw_ObjAddRefs ( Csw_Man_t *  p, Aig_Obj_t *  pObj, int  nRefs  )

inlinestatic

Definition at line 108 of file cswInt.h.

{ p->pnRefs[pObj->Id] += nRefs; }

static Aig_Obj_t* Csw_ObjChild0Equiv ( Csw_Man_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

Definition at line 116 of file cswInt.h.

{ assert( !Aig_IsComplement(pObj) ); return Aig_ObjFanin0(pObj)? Aig_NotCond(Csw_ObjEquiv(p, Aig_ObjFanin0(pObj)), Aig_ObjFaninC0(pObj)) : NULL;  }

static Aig_Obj_t* Csw_ObjChild1Equiv ( Csw_Man_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

Definition at line 117 of file cswInt.h.

{ assert( !Aig_IsComplement(pObj) ); return Aig_ObjFanin1(pObj)? Aig_NotCond(Csw_ObjEquiv(p, Aig_ObjFanin1(pObj)), Aig_ObjFaninC1(pObj)) : NULL;  }

static Csw_Cut_t* Csw_ObjCuts ( Csw_Man_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

Definition at line 110 of file cswInt.h.

{ return p->pCuts[pObj->Id];    }

static Aig_Obj_t* Csw_ObjEquiv ( Csw_Man_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

Definition at line 113 of file cswInt.h.

{ return p->pEquiv[pObj->Id];   }

Csw_Cut_t* Csw_ObjPrepareCuts	(	Csw_Man_t *	p,
		Aig_Obj_t *	pObj,
		int	fTriv
	)

FUNCTION DECLARATIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 453 of file cswCut.c.

{
    Csw_Cut_t * pCutSet, * pCut;
    int i;
    // create the cutset of the node
    pCutSet = (Csw_Cut_t *)Aig_MmFixedEntryFetch( p->pMemCuts );
    Csw_ObjSetCuts( p, pObj, pCutSet );
    Csw_ObjForEachCut( p, pObj, pCut, i )
    {
        pCut->nFanins = 0;
        pCut->iNode = pObj->Id;
        pCut->nCutSize = p->nCutSize;
        pCut->nLeafMax = p->nLeafMax;
    }
    // add unit cut if needed
    if ( fTriv )
    {
        pCut = pCutSet;
        pCut->Cost = 0;
        pCut->iNode = pObj->Id;
        pCut->nFanins = 1;
        pCut->pFanins[0] = pObj->Id;
        pCut->uSign = Aig_ObjCutSign( pObj->Id );
        memset( Csw_CutTruth(pCut), 0xAA, sizeof(unsigned) * p->nTruthWords );
    }
    return pCutSet;
}

static int Csw_ObjRefs ( Csw_Man_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

Definition at line 107 of file cswInt.h.

{ return p->pnRefs[pObj->Id];   }

static void Csw_ObjSetCuts ( Csw_Man_t *  p, Aig_Obj_t *  pObj, Csw_Cut_t *  pCuts  )

inlinestatic

Definition at line 111 of file cswInt.h.

{ p->pCuts[pObj->Id] = pCuts;   }

static void Csw_ObjSetEquiv ( Csw_Man_t *  p, Aig_Obj_t *  pObj, Aig_Obj_t *  pEquiv  )

inlinestatic

Definition at line 114 of file cswInt.h.

{ p->pEquiv[pObj->Id] = pEquiv; }

Aig_Obj_t* Csw_ObjSweep	(	Csw_Man_t *	p,
		Aig_Obj_t *	pObj,
		int	fTriv
	)

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

Synopsis [Derives cuts for one node and sweeps this node.]

Description []

SideEffects []

SeeAlso []

Definition at line 492 of file cswCut.c.

{
    int fUseResub = 1;
    Csw_Cut_t * pCut0, * pCut1, * pCut, * pCutSet;
    Aig_Obj_t * pFanin0 = Aig_ObjFanin0(pObj);
    Aig_Obj_t * pFanin1 = Aig_ObjFanin1(pObj);
    Aig_Obj_t * pObjNew;
    unsigned * pTruth;
    int i, k, nVars, nFanins, iVar;
    abctime clk;

    assert( !Aig_IsComplement(pObj) );
    if ( !Aig_ObjIsNode(pObj) )
        return pObj;
    if ( Csw_ObjCuts(p, pObj) )
        return pObj;
    // the node is not processed yet
    assert( Csw_ObjCuts(p, pObj) == NULL );
    assert( Aig_ObjIsNode(pObj) );

    // set up the first cut
    pCutSet = Csw_ObjPrepareCuts( p, pObj, fTriv );

    // compute pair-wise cut combinations while checking table
    Csw_ObjForEachCut( p, pFanin0, pCut0, i )
    if ( pCut0->nFanins > 0 )
    Csw_ObjForEachCut( p, pFanin1, pCut1, k )
    if ( pCut1->nFanins > 0 )
    {
        // make sure K-feasible cut exists
        if ( Kit_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->nLeafMax )
            continue;
        // get the next cut of this node
        pCut = Csw_CutFindFree( p, pObj );
clk = Abc_Clock();
        // assemble the new cut
        if ( !Csw_CutMerge( p, pCut0, pCut1, pCut ) )
        {
            assert( pCut->nFanins == 0 );
            continue;
        }
        // check containment
        if ( Csw_CutFilter( p, pObj, pCut ) )
        {
            assert( pCut->nFanins == 0 );
            continue;
        }
        // create its truth table
        pTruth = Csw_CutComputeTruth( p, pCut, pCut0, pCut1, Aig_ObjFaninC0(pObj), Aig_ObjFaninC1(pObj) );
        // support minimize the truth table
        nFanins = pCut->nFanins;
//        nVars = Csw_CutSupportMinimize( p, pCut ); // leads to quality degradation
        nVars = Kit_TruthSupportSize( pTruth, p->nLeafMax );
p->timeCuts += Abc_Clock() - clk;

        // check for trivial truth tables
        if ( nVars == 0 )
        {
            p->nNodesTriv0++;
            return Aig_NotCond( Aig_ManConst1(p->pManRes), !(pTruth[0] & 1) );
        }
        if ( nVars == 1 )
        {
            p->nNodesTriv1++;
            iVar = Kit_WordFindFirstBit( Kit_TruthSupport(pTruth, p->nLeafMax) );
            assert( iVar < pCut->nFanins );
            return Aig_NotCond( Aig_ManObj(p->pManRes, pCut->pFanins[iVar]), (pTruth[0] & 1) );
        }
        if ( nVars == 2 && nFanins > 2 && fUseResub )
        {
            if ( (pObjNew = Csw_ObjTwoVarCut( p, pCut )) )
            {
                p->nNodesTriv2++;
                return pObjNew;
            }
        }

        // check if an equivalent node with the same cut exists
clk = Abc_Clock();
        pObjNew = pCut->nFanins > 2 ? Csw_TableCutLookup( p, pCut ) : NULL;
p->timeHash += Abc_Clock() - clk;
        if ( pObjNew )
        {
            p->nNodesCuts++;
            return pObjNew;
        }

        // assign the cost
        pCut->Cost = Csw_CutFindCost( p, pCut );
        assert( pCut->nFanins > 0 );
        assert( pCut->Cost > 0 );
    }
    p->nNodesTried++;

    // load the resulting cuts into the table
clk = Abc_Clock();
    Csw_ObjForEachCut( p, pObj, pCut, i )
    {
        if ( pCut->nFanins > 2 )
        {
            assert( pCut->Cost > 0 );
            Csw_TableCutInsert( p, pCut );
        }
    }
p->timeHash += Abc_Clock() - clk;

    // return the node if could not replace it
    return pObj;
}

int Csw_TableCountCuts

(

Csw_Man_t *

p

)

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

Synopsis [Returns the total number of cuts in the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 82 of file cswTable.c.

{
    Csw_Cut_t * pEnt;
    int i, Counter = 0;
    for ( i = 0; i < p->nTableSize; i++ )
        for ( pEnt = p->pTable[i]; pEnt; pEnt = pEnt->pNext )
            Counter++;
    return Counter;
}

void Csw_TableCutInsert	(	Csw_Man_t *	p,
		Csw_Cut_t *	pCut
	)

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

Synopsis [Adds the cut to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 103 of file cswTable.c.

{
    int iEntry = Csw_CutHash(pCut) % p->nTableSize;
    pCut->pNext = p->pTable[iEntry];
    p->pTable[iEntry] = pCut;
}

Aig_Obj_t* Csw_TableCutLookup	(	Csw_Man_t *	p,
		Csw_Cut_t *	pCut
	)

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

Synopsis [Returns an equivalent node if it exists.]

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file cswTable.c.

{
    Aig_Obj_t * pRes = NULL;
    Csw_Cut_t * pEnt;
    unsigned * pTruthNew, * pTruthOld;
    int iEntry = Csw_CutHash(pCut) % p->nTableSize;
    for ( pEnt = p->pTable[iEntry]; pEnt; pEnt = pEnt->pNext )
    {
        if ( pEnt->nFanins != pCut->nFanins )
            continue;
        if ( pEnt->uSign != pCut->uSign )
            continue;
        if ( memcmp( pEnt->pFanins, pCut->pFanins, sizeof(int) * pCut->nFanins ) )
            continue;
        pTruthOld = Csw_CutTruth(pEnt);
        pTruthNew = Csw_CutTruth(pCut);
        if ( (pTruthOld[0] & 1) == (pTruthNew[0] & 1) )
        {
            if ( Kit_TruthIsEqual( pTruthOld, pTruthNew, pCut->nFanins ) )
            {
                pRes = Aig_ManObj( p->pManRes, pEnt->iNode );
                assert( pRes->fPhase == Aig_ManObj( p->pManRes, pCut->iNode )->fPhase );
                break;
            }
        }
        else
        {
            if ( Kit_TruthIsOpposite( pTruthOld, pTruthNew, pCut->nFanins ) )
            {
                pRes = Aig_Not( Aig_ManObj( p->pManRes, pEnt->iNode ) );
                assert( Aig_Regular(pRes)->fPhase != Aig_ManObj( p->pManRes, pCut->iNode )->fPhase );
                break;
            }
        }
    }
    return pRes;
}