aigCuts.c File Reference

#include "aig.h"
#include "bool/kit/kit.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Aig_ManCut_t *	Aig_ManCutStart (Aig_Man_t *pMan, int nCutsMax, int nLeafMax, int fTruth, int fVerbose)
	DECLARATIONS ///. More...
void	Aig_ManCutStop (Aig_ManCut_t *p)
void	Aig_CutPrint (Aig_Cut_t *pCut)
void	Aig_ObjCutPrint (Aig_ManCut_t *p, Aig_Obj_t *pObj)
int	Aig_ManCutCount (Aig_ManCut_t *p, int *pnCutsK)
static int	Aig_CutFindCost (Aig_ManCut_t *p, Aig_Cut_t *pCut)
static float	Aig_CutFindCost2 (Aig_ManCut_t *p, Aig_Cut_t *pCut)
static Aig_Cut_t *	Aig_CutFindFree (Aig_ManCut_t *p, Aig_Obj_t *pObj)
static unsigned	Aig_CutTruthPhase (Aig_Cut_t *pCut, Aig_Cut_t *pCut1)
unsigned *	Aig_CutComputeTruth (Aig_ManCut_t *p, Aig_Cut_t *pCut, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, int fCompl0, int fCompl1)
int	Aig_CutSupportMinimize (Aig_ManCut_t *p, Aig_Cut_t *pCut)
static int	Aig_CutCheckDominance (Aig_Cut_t *pDom, Aig_Cut_t *pCut)
int	Aig_CutFilter (Aig_ManCut_t *p, Aig_Obj_t *pObj, Aig_Cut_t *pCut)
static int	Aig_CutMergeOrdered (Aig_ManCut_t *p, Aig_Cut_t *pC0, Aig_Cut_t *pC1, Aig_Cut_t *pC)
int	Aig_CutMerge (Aig_ManCut_t *p, Aig_Cut_t *pCut0, Aig_Cut_t *pCut1, Aig_Cut_t *pCut)
Aig_Cut_t *	Aig_ObjPrepareCuts (Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
void	Aig_ObjComputeCuts (Aig_ManCut_t *p, Aig_Obj_t *pObj, int fTriv)
Aig_ManCut_t *	Aig_ComputeCuts (Aig_Man_t *pAig, int nCutsMax, int nLeafMax, int fTruth, int fVerbose)

Function Documentation

Aig_ManCut_t* Aig_ComputeCuts	(	Aig_Man_t *	pAig,
		int	nCutsMax,
		int	nLeafMax,
		int	fTruth,
		int	fVerbose
	)

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

Synopsis [Computes the cuts for all nodes in the static AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 631 of file aigCuts.c.

{
    Aig_ManCut_t * p;
    Aig_Obj_t * pObj;
    int i;
    abctime clk = Abc_Clock();
    assert( pAig->pManCuts == NULL );
    // start the manager
    p = Aig_ManCutStart( pAig, nCutsMax, nLeafMax, fTruth, fVerbose );
    // set elementary cuts at the PIs
    Aig_ManForEachCi( pAig, pObj, i )
        Aig_ObjPrepareCuts( p, pObj, 1 );
    // process the nodes
    Aig_ManForEachNode( pAig, pObj, i )
        Aig_ObjComputeCuts( p, pObj, 1 );
    // print stats
    if ( fVerbose )
    {
        int nCuts, nCutsK;
        nCuts = Aig_ManCutCount( p, &nCutsK );
        printf( "Nodes = %6d. Total cuts = %6d. %d-input cuts = %6d.\n",
            Aig_ManObjNum(pAig), nCuts, nLeafMax, nCutsK );
        printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f MB  ",
            p->nCutSize, 4*p->nTruthWords, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
        ABC_PRT( "Runtime", Abc_Clock() - clk );
/*
        Aig_ManForEachNode( pAig, pObj, i )
            if ( i % 300 == 0 )
                Aig_ObjCutPrint( p, pObj );
*/
    }
    // remember the cut manager
    pAig->pManCuts = p;
    return p;
}

static int Aig_CutCheckDominance ( Aig_Cut_t *  pDom, Aig_Cut_t *  pCut  )

inlinestatic

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

Synopsis [Returns 1 if pDom is contained in pCut.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file aigCuts.c.

{
    int i, k;
    for ( i = 0; i < (int)pDom->nFanins; i++ )
    {
        for ( k = 0; k < (int)pCut->nFanins; k++ )
            if ( pDom->pFanins[i] == pCut->pFanins[k] )
                break;
        if ( k == (int)pCut->nFanins ) // node i in pDom is not contained in pCut
            return 0;
    }
    // every node in pDom is contained in pCut
    return 1;
}

unsigned* Aig_CutComputeTruth	(	Aig_ManCut_t *	p,
		Aig_Cut_t *	pCut,
		Aig_Cut_t *	pCut0,
		Aig_Cut_t *	pCut1,
		int	fCompl0,
		int	fCompl1
	)

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

Synopsis [Performs truth table computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 276 of file aigCuts.c.

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

int Aig_CutFilter	(	Aig_ManCut_t *	p,
		Aig_Obj_t *	pObj,
		Aig_Cut_t *	pCut
	)

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

Synopsis [Returns 1 if the cut is contained.]

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file aigCuts.c.

{ 
    Aig_Cut_t * pTemp;
    int i;
    // go through the cuts of the node
    Aig_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 ( Aig_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 ( Aig_CutCheckDominance( pTemp, pCut ) )
            {
                // remove the given
                pCut->nFanins = 0;
                return 1;
            }
        }
    }
    return 0;
}

static int Aig_CutFindCost ( Aig_ManCut_t *  p, Aig_Cut_t *  pCut  )

inlinestatic

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

Synopsis [Compute the cost of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 177 of file aigCuts.c.

{
    Aig_Obj_t * pLeaf;
    int i, Cost = 0;
    assert( pCut->nFanins > 0 );
    Aig_CutForEachLeaf( p->pAig, pCut, pLeaf, i )
        Cost += pLeaf->nRefs;
    return Cost * 1000 / pCut->nFanins;
}

static float Aig_CutFindCost2 ( Aig_ManCut_t *  p, Aig_Cut_t *  pCut  )

inlinestatic

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

Synopsis [Compute the cost of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 198 of file aigCuts.c.

{
    Aig_Obj_t * pLeaf;
    float Cost = 0.0;
    int i;
    assert( pCut->nFanins > 0 );
    Aig_CutForEachLeaf( p->pAig, pCut, pLeaf, i )
        Cost += (float)1.0/pLeaf->nRefs;
    return 1/Cost;
}

static Aig_Cut_t* Aig_CutFindFree ( Aig_ManCut_t *  p, Aig_Obj_t *  pObj  )

inlinestatic

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

Synopsis [Returns the next free cut to use.]

Description []

SideEffects []

SeeAlso []

Definition at line 220 of file aigCuts.c.

{
    Aig_Cut_t * pCut, * pCutMax;
    int i;
    pCutMax = NULL;
    Aig_ObjForEachCut( p, pObj, pCut, i )
    {
        if ( pCut->nFanins == 0 )
            return pCut;
        if ( pCutMax == NULL || pCutMax->Cost < pCut->Cost )
            pCutMax = pCut;
    }
    assert( pCutMax != NULL );
    pCutMax->nFanins = 0;
    return pCutMax;
}

int Aig_CutMerge	(	Aig_ManCut_t *	p,
		Aig_Cut_t *	pCut0,
		Aig_Cut_t *	pCut1,
		Aig_Cut_t *	pCut
	)

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

Synopsis [Prepares the object for FPGA mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 507 of file aigCuts.c.

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

static int Aig_CutMergeOrdered ( Aig_ManCut_t *  p, Aig_Cut_t *  pC0, Aig_Cut_t *  pC1, Aig_Cut_t *  pC  )

inlinestatic

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

Synopsis [Merges two cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 421 of file aigCuts.c.

{ 
    int i, k, c;
    assert( pC0->nFanins >= pC1->nFanins );
    // the case of the largest cut sizes
    if ( pC0->nFanins == p->nLeafMax && pC1->nFanins == p->nLeafMax )
    {
        for ( i = 0; i < pC0->nFanins; i++ )
            if ( pC0->pFanins[i] != pC1->pFanins[i] )
                return 0;
        for ( i = 0; i < pC0->nFanins; i++ )
            pC->pFanins[i] = pC0->pFanins[i];
        pC->nFanins = pC0->nFanins;
        return 1;
    }
    // the case when one of the cuts is the largest
    if ( pC0->nFanins == p->nLeafMax )
    {
        for ( i = 0; i < pC1->nFanins; i++ )
        {
            for ( k = pC0->nFanins - 1; k >= 0; k-- )
                if ( pC0->pFanins[k] == pC1->pFanins[i] )
                    break;
            if ( k == -1 ) // did not find
                return 0;
        }
        for ( i = 0; i < pC0->nFanins; i++ )
            pC->pFanins[i] = pC0->pFanins[i];
        pC->nFanins = pC0->nFanins;
        return 1;
    }

    // compare two cuts with different numbers
    i = k = 0;
    for ( c = 0; c < p->nLeafMax; c++ )
    {
        if ( k == pC1->nFanins )
        {
            if ( i == pC0->nFanins )
            {
                pC->nFanins = c;
                return 1;
            }
            pC->pFanins[c] = pC0->pFanins[i++];
            continue;
        }
        if ( i == pC0->nFanins )
        {
            if ( k == pC1->nFanins )
            {
                pC->nFanins = c;
                return 1;
            }
            pC->pFanins[c] = pC1->pFanins[k++];
            continue;
        }
        if ( pC0->pFanins[i] < pC1->pFanins[k] )
        {
            pC->pFanins[c] = pC0->pFanins[i++];
            continue;
        }
        if ( pC0->pFanins[i] > pC1->pFanins[k] )
        {
            pC->pFanins[c] = pC1->pFanins[k++];
            continue;
        }
        pC->pFanins[c] = pC0->pFanins[i++]; 
        k++;
    }
    if ( i < pC0->nFanins || k < pC1->nFanins )
        return 0;
    pC->nFanins = c;
    return 1;
}

void Aig_CutPrint

(

Aig_Cut_t *

pCut

)

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

Synopsis [Prints one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file aigCuts.c.

{
    int i;
    printf( "{" );
    for ( i = 0; i < pCut->nFanins; i++ )
        printf( " %d", pCut->pFanins[i] );
    printf( " }\n" );
}

int Aig_CutSupportMinimize	(	Aig_ManCut_t *	p,
		Aig_Cut_t *	pCut
	)

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

Synopsis [Performs support minimization for the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 307 of file aigCuts.c.

{
    unsigned * pTruth;
    int uSupp, nFansNew, i, k;
    // get truth table
    pTruth = Aig_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;
}

static unsigned Aig_CutTruthPhase ( Aig_Cut_t *  pCut, Aig_Cut_t *  pCut1  )

inlinestatic

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

Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 248 of file aigCuts.c.

{
    unsigned uPhase = 0;
    int i, k;
    for ( i = k = 0; i < pCut->nFanins; i++ )
    {
        if ( k == pCut1->nFanins )
            break;
        if ( pCut->pFanins[i] < pCut1->pFanins[k] )
            continue;
        assert( pCut->pFanins[i] == pCut1->pFanins[k] );
        uPhase |= (1 << i);
        k++;
    }
    return uPhase;
}

int Aig_ManCutCount	(	Aig_ManCut_t *	p,
		int *	pnCutsK
	)

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

Synopsis [Computes the total number of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 147 of file aigCuts.c.

{
    Aig_Cut_t * pCut;
    Aig_Obj_t * pObj;
    int i, k, nCuts = 0, nCutsK = 0;
    Aig_ManForEachNode( p->pAig, pObj, i )
        Aig_ObjForEachCut( p, pObj, pCut, k )
        {
            if ( pCut->nFanins == 0 )
                continue;
            nCuts++;
            if ( pCut->nFanins == p->nLeafMax )
                nCutsK++;
        }
    if ( pnCutsK )
        *pnCutsK = nCutsK;
    return nCuts;
}

ABC_NAMESPACE_IMPL_START Aig_ManCut_t* Aig_ManCutStart	(	Aig_Man_t *	pMan,
		int	nCutsMax,
		int	nLeafMax,
		int	fTruth,
		int	fVerbose
	)

DECLARATIONS ///.

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

FileName [aigCuts.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Computation of K-feasible priority cuts.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

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

Synopsis [Starts the cut sweeping manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file aigCuts.c.

{
    Aig_ManCut_t * p;
    assert( nCutsMax >= 2  );
    assert( nLeafMax <= 16 );
    // allocate the fraiging manager
    p = ABC_ALLOC( Aig_ManCut_t, 1 );
    memset( p, 0, sizeof(Aig_ManCut_t) );
    p->nCutsMax = nCutsMax;
    p->nLeafMax = nLeafMax;
    p->fTruth   = fTruth;
    p->fVerbose = fVerbose;
    p->pAig     = pMan;
    p->pCuts    = ABC_CALLOC( Aig_Cut_t *, Aig_ManObjNumMax(pMan) );
    // allocate memory manager
    p->nTruthWords = Abc_TruthWordNum(nLeafMax);
    p->nCutSize = sizeof(Aig_Cut_t) + sizeof(int) * nLeafMax + fTruth * sizeof(unsigned) * p->nTruthWords;
    p->pMemCuts = Aig_MmFixedStart( p->nCutSize * p->nCutsMax, 512 );
    // room for temporary truth tables
    if ( fTruth )
    {
        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 Aig_ManCutStop

(

Aig_ManCut_t *

p

)

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

Synopsis [Stops the fraiging manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file aigCuts.c.

{
    Aig_MmFixedStop( p->pMemCuts, 0 );
    ABC_FREE( p->puTemp[0] );
    ABC_FREE( p->pCuts );
    ABC_FREE( p );
}

void Aig_ObjComputeCuts	(	Aig_ManCut_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 576 of file aigCuts.c.

{
    Aig_Cut_t * pCut0, * pCut1, * pCut, * pCutSet;
    Aig_Obj_t * pFanin0 = Aig_ObjFanin0(pObj);
    Aig_Obj_t * pFanin1 = Aig_ObjFanin1(pObj);
    int i, k;
    // the node is not processed yet
    assert( Aig_ObjIsNode(pObj) );
    assert( Aig_ObjCuts(p, pObj) == NULL );
    // set up the first cut
    pCutSet = Aig_ObjPrepareCuts( p, pObj, fTriv );
    // compute pair-wise cut combinations while checking table
    Aig_ObjForEachCut( p, pFanin0, pCut0, i )
    if ( pCut0->nFanins > 0 )
    Aig_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 = Aig_CutFindFree( p, pObj );
        // assemble the new cut
        if ( !Aig_CutMerge( p, pCut0, pCut1, pCut ) )
        {
            assert( pCut->nFanins == 0 );
            continue;
        }
        // check containment
        if ( Aig_CutFilter( p, pObj, pCut ) )
        {
            assert( pCut->nFanins == 0 );
            continue;
        }
        // create its truth table
        if ( p->fTruth )
            Aig_CutComputeTruth( p, pCut, pCut0, pCut1, Aig_ObjFaninC0(pObj), Aig_ObjFaninC1(pObj) );
        // assign the cost
        pCut->Cost = Aig_CutFindCost( p, pCut );
        assert( pCut->nFanins > 0 );
        assert( pCut->Cost > 0 );
    }
}

void Aig_ObjCutPrint	(	Aig_ManCut_t *	p,
		Aig_Obj_t *	pObj
	)

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

Synopsis [Prints one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file aigCuts.c.

{
    Aig_Cut_t * pCut;
    int i;
    printf( "Cuts for node %d:\n", pObj->Id );
    Aig_ObjForEachCut( p, pObj, pCut, i )
        if ( pCut->nFanins )
            Aig_CutPrint( pCut );
//    printf( "\n" );
}

Aig_Cut_t* Aig_ObjPrepareCuts	(	Aig_ManCut_t *	p,
		Aig_Obj_t *	pObj,
		int	fTriv
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 536 of file aigCuts.c.

{
    Aig_Cut_t * pCutSet, * pCut;
    int i;
    // create the cutset of the node
    pCutSet = (Aig_Cut_t *)Aig_MmFixedEntryFetch( p->pMemCuts );
    Aig_ObjSetCuts( p, pObj, pCutSet );
    Aig_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 );
        if ( p->fTruth )
        memset( Aig_CutTruth(pCut), 0xAA, sizeof(unsigned) * p->nTruthWords );
    }
    return pCutSet;
}