cswCut.c File Reference

#include "cswInt.h"

Include dependency graph for cswCut.c:

Go to the source code of this file.

Functions
unsigned *	Csw_CutComputeTruth (Csw_Man_t *p, Csw_Cut_t *pCut, Csw_Cut_t *pCut0, Csw_Cut_t *pCut1, int fCompl0, int fCompl1)
int	Csw_CutSupportMinimize (Csw_Man_t *p, Csw_Cut_t *pCut)
int	Csw_CutFilter (Csw_Man_t *p, Aig_Obj_t *pObj, Csw_Cut_t *pCut)
int	Csw_CutMerge (Csw_Man_t *p, Csw_Cut_t *pCut0, Csw_Cut_t *pCut1, Csw_Cut_t *pCut)
Aig_Obj_t *	Csw_ObjTwoVarCut (Csw_Man_t *p, Csw_Cut_t *pCut)
Csw_Cut_t *	Csw_ObjPrepareCuts (Csw_Man_t *p, Aig_Obj_t *pObj, int fTriv)
	FUNCTION DECLARATIONS ///.
Aig_Obj_t *	Csw_ObjSweep (Csw_Man_t *p, Aig_Obj_t *pObj, int fTriv)

Function Documentation

Csw_CutComputeTruth()

unsigned * Csw_CutComputeTruth	(	Csw_Man_t *	p,
		Csw_Cut_t *	pCut,
		Csw_Cut_t *	pCut0,
		Csw_Cut_t *	pCut1,
		int	fCompl0,
		int	fCompl1 )

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

Synopsis [Performs truth table computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 149 of file cswCut.c.

{
    // permute the first table
    if ( fCompl0 ) 
        Kit_TruthNot( p->puTemp[0], Csw_CutTruth(pCut0), p->nLeafMax );
    else
        Kit_TruthCopy( p->puTemp[0], Csw_CutTruth(pCut0), p->nLeafMax );
    Kit_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nFanins, p->nLeafMax, Cut_TruthPhase(pCut, pCut0), 0 );
    // permute the second table
    if ( fCompl1 ) 
        Kit_TruthNot( p->puTemp[1], Csw_CutTruth(pCut1), p->nLeafMax );
    else
        Kit_TruthCopy( p->puTemp[1], Csw_CutTruth(pCut1), p->nLeafMax );
    Kit_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nFanins, p->nLeafMax, Cut_TruthPhase(pCut, pCut1), 0 );
    // produce the resulting table
    Kit_TruthAnd( Csw_CutTruth(pCut), p->puTemp[2], p->puTemp[3], p->nLeafMax );
//    assert( pCut->nFanins >= Kit_TruthSupportSize( Csw_CutTruth(pCut), p->nLeafMax ) );
    return Csw_CutTruth(pCut);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Csw_CutFilter()

int Csw_CutFilter	(	Csw_Man_t *	p,
		Aig_Obj_t *	pObj,
		Csw_Cut_t *	pCut )

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

Synopsis [Returns 1 if the cut is contained.]

Description []

SideEffects []

SeeAlso []

Definition at line 243 of file cswCut.c.

{ 
    Csw_Cut_t * pTemp;
    int i;
    // go through the cuts of the node
    Csw_ObjForEachCut( p, pObj, pTemp, i )
    {
        if ( pTemp->nFanins < 2 )
            continue;
        if ( pTemp == pCut )
            continue;
        if ( pTemp->nFanins > pCut->nFanins )
        {
            // skip the non-contained cuts
            if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
                continue;
            // check containment seriously
            if ( Csw_CutCheckDominance( pCut, pTemp ) )
            {
                // remove contained cut
                pTemp->nFanins = 0;
            }
         }
        else
        {
            // skip the non-contained cuts
            if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
                continue;
            // check containment seriously
            if ( Csw_CutCheckDominance( pTemp, pCut ) )
            {
                // remove the given
                pCut->nFanins = 0;
                return 1;
            }
        }
    }
    return 0;
}

Here is the caller graph for this function:

Csw_CutMerge()

int Csw_CutMerge	(	Csw_Man_t *	p,
		Csw_Cut_t *	pCut0,
		Csw_Cut_t *	pCut1,
		Csw_Cut_t *	pCut )

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

Synopsis [Prepares the object for FPGA mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 380 of file cswCut.c.

{ 
    assert( p->nLeafMax > 0 );
    // merge the nodes
    if ( pCut0->nFanins < pCut1->nFanins )
    {
        if ( !Csw_CutMergeOrdered( p, pCut1, pCut0, pCut ) )
            return 0;
    }
    else
    {
        if ( !Csw_CutMergeOrdered( p, pCut0, pCut1, pCut ) )
            return 0;
    }
    pCut->uSign = pCut0->uSign | pCut1->uSign;
    return 1;
}

Here is the caller graph for this function:

Csw_CutSupportMinimize()

int Csw_CutSupportMinimize	(	Csw_Man_t *	p,
		Csw_Cut_t *	pCut )

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

Synopsis [Performs support minimization for the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 180 of file cswCut.c.

{
    unsigned * pTruth;
    int uSupp, nFansNew, i, k;
    // get truth table
    pTruth = Csw_CutTruth( pCut );
    // get support 
    uSupp = Kit_TruthSupport( pTruth, p->nLeafMax );
    // get the new support size
    nFansNew = Kit_WordCountOnes( uSupp );
    // check if there are redundant variables
    if ( nFansNew == pCut->nFanins )
        return nFansNew;
    assert( nFansNew < pCut->nFanins );
    // minimize support
    Kit_TruthShrink( p->puTemp[0], pTruth, nFansNew, p->nLeafMax, uSupp, 1 );
    for ( i = k = 0; i < pCut->nFanins; i++ )
        if ( uSupp & (1 << i) )
            pCut->pFanins[k++] = pCut->pFanins[i];
    assert( k == nFansNew );
    pCut->nFanins = nFansNew;
//    assert( nFansNew == Kit_TruthSupportSize( pTruth, p->nLeafMax ) );
//Extra_PrintBinary( stdout, pTruth, (1<<p->nLeafMax) ); printf( "\n" );
    return nFansNew;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Csw_ObjPrepareCuts()

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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Csw_ObjSweep()

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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Csw_ObjTwoVarCut()

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

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

Synopsis [Consider cut with more than 2 fanins having 2 true variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 409 of file cswCut.c.

{
    Aig_Obj_t * pRes, * pIn0, * pIn1;
    int nVars, uTruth, fCompl = 0;
    assert( pCut->nFanins > 2 );
    // minimize support of this cut
    nVars = Csw_CutSupportMinimize( p, pCut );
    assert( nVars == 2 );
    // get the fanins
    pIn0 = Aig_ManObj( p->pManRes, pCut->pFanins[0] );
    pIn1 = Aig_ManObj( p->pManRes, pCut->pFanins[1] );
    // derive the truth table
    uTruth = 0xF & *Csw_CutTruth(pCut);
    if ( uTruth == 14 || uTruth == 13 || uTruth == 11 || uTruth == 7 )
    {
        uTruth = 0xF & ~uTruth;
        fCompl = 1;
    }
    // compute the result
    pRes = NULL;
    if ( uTruth == 1  )  // 0001  // 1110  14
        pRes = Aig_And( p->pManRes, Aig_Not(pIn0), Aig_Not(pIn1) );
    if ( uTruth == 2  )  // 0010  // 1101  13 
        pRes = Aig_And( p->pManRes,         pIn0 , Aig_Not(pIn1) );
    if ( uTruth == 4  )  // 0100  // 1011  11
        pRes = Aig_And( p->pManRes, Aig_Not(pIn0),         pIn1  );
    if ( uTruth == 8  )  // 1000  // 0111   7
        pRes = Aig_And( p->pManRes,         pIn0 ,         pIn1  );
    if ( pRes )
        pRes = Aig_NotCond( pRes, fCompl );
    return pRes;
}

Here is the call graph for this function:

Here is the caller graph for this function: