abcMulti.c File Reference

#include "base/abc/abc.h"
#include "misc/extra/extraBdd.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START void	Abc_NtkMultiInt (Abc_Ntk_t *pNtk, Abc_Ntk_t *pNtkNew)
	DECLARATIONS ///. More...
static Abc_Obj_t *	Abc_NtkMulti_rec (Abc_Ntk_t *pNtkNew, Abc_Obj_t *pNodeOld)
static DdNode *	Abc_NtkMultiDeriveBdd_rec (DdManager *dd, Abc_Obj_t *pNodeOld, Vec_Ptr_t *vFanins)
static DdNode *	Abc_NtkMultiDeriveBdd (DdManager *dd, Abc_Obj_t *pNodeOld, Vec_Ptr_t *vFaninsOld)
static void	Abc_NtkMultiSetBounds (Abc_Ntk_t *pNtk, int nThresh, int nFaninMax)
static void	Abc_NtkMultiSetBoundsCnf (Abc_Ntk_t *pNtk)
static void	Abc_NtkMultiSetBoundsMulti (Abc_Ntk_t *pNtk, int nThresh)
static void	Abc_NtkMultiSetBoundsSimple (Abc_Ntk_t *pNtk)
static void	Abc_NtkMultiSetBoundsFactor (Abc_Ntk_t *pNtk)
static void	Abc_NtkMultiCone (Abc_Obj_t *pNode, Vec_Ptr_t *vCone)
Abc_Ntk_t *	Abc_NtkMulti (Abc_Ntk_t *pNtk, int nThresh, int nFaninMax, int fCnf, int fMulti, int fSimple, int fFactor)
	FUNCTION DEFINITIONS ///. More...
int	Abc_NtkMultiLimit_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vCone, int nFaninMax, int fCanStop, int fFirst)
int	Abc_NtkMultiLimit (Abc_Obj_t *pNode, Vec_Ptr_t *vCone, int nFaninMax)
void	Abc_NtkMultiCone_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vCone)

Function Documentation

Abc_Ntk_t* Abc_NtkMulti	(	Abc_Ntk_t *	pNtk,
		int	nThresh,
		int	nFaninMax,
		int	fCnf,
		int	fMulti,
		int	fSimple,
		int	fFactor
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Transforms the AIG into nodes.]

Description [Threhold is the max number of nodes duplicated at a node.]

SideEffects []

SeeAlso []

Definition at line 59 of file abcMulti.c.

{
    Abc_Ntk_t * pNtkNew;

    assert( Abc_NtkIsStrash(pNtk) );
    assert( nThresh >= 0 );
    assert( nFaninMax > 1 );

    // print a warning about choice nodes
    if ( Abc_NtkGetChoiceNum( pNtk ) )
        printf( "Warning: The choice nodes in the AIG are removed by renoding.\n" );

    // define the boundary
    if ( fCnf )
        Abc_NtkMultiSetBoundsCnf( pNtk );
    else if ( fMulti )
        Abc_NtkMultiSetBoundsMulti( pNtk, nThresh );
    else if ( fSimple )
        Abc_NtkMultiSetBoundsSimple( pNtk );
    else if ( fFactor )
        Abc_NtkMultiSetBoundsFactor( pNtk );
    else
        Abc_NtkMultiSetBounds( pNtk, nThresh, nFaninMax );

    // perform renoding for this boundary
    pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_BDD );
    Abc_NtkMultiInt( pNtk, pNtkNew );
    Abc_NtkFinalize( pNtk, pNtkNew );

    // make the network minimum base
    Abc_NtkMinimumBase( pNtkNew );

    // fix the problem with complemented and duplicated CO edges
    Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );

    // report the number of CNF objects
    if ( fCnf )
    {
//        int nClauses = Abc_NtkGetClauseNum(pNtkNew) + 2*Abc_NtkPoNum(pNtkNew) + 2*Abc_NtkLatchNum(pNtkNew);
//        printf( "CNF variables = %d. CNF clauses = %d.\n",  Abc_NtkNodeNum(pNtkNew), nClauses );
    }
//printf( "Maximum fanin = %d.\n", Abc_NtkGetFaninMax(pNtkNew) );

    if ( pNtk->pExdc )
        pNtkNew->pExdc = Abc_NtkDup( pNtk->pExdc );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkNew ) )
    {
        printf( "Abc_NtkMulti: The network check has failed.\n" );
        Abc_NtkDelete( pNtkNew );
        return NULL;
    }
    return pNtkNew;
}

Abc_Obj_t * Abc_NtkMulti_rec ( Abc_Ntk_t *  pNtkNew, Abc_Obj_t *  pNodeOld  )

static

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

Synopsis [Find the best multi-input node rooted at the given node.]

Description []

SideEffects []

SeeAlso []

Definition at line 170 of file abcMulti.c.

{
    Vec_Ptr_t * vCone;
    Abc_Obj_t * pNodeNew;
    int i;

    assert( !Abc_ObjIsComplement(pNodeOld) );
    // return if the result if known
    if ( pNodeOld->pCopy )
        return pNodeOld->pCopy;
    assert( Abc_ObjIsNode(pNodeOld) );
    assert( !Abc_AigNodeIsConst(pNodeOld) );
    assert( pNodeOld->fMarkA );

//printf( "%d ", Abc_NodeMffcSizeSupp(pNodeOld) );

    // collect the renoding cone
    vCone = Vec_PtrAlloc( 10 );
    Abc_NtkMultiCone( pNodeOld, vCone );

    // create a new node 
    pNodeNew = Abc_NtkCreateNode( pNtkNew ); 
    for ( i = 0; i < vCone->nSize; i++ )
        Abc_ObjAddFanin( pNodeNew, Abc_NtkMulti_rec(pNtkNew, (Abc_Obj_t *)vCone->pArray[i]) );

    // derive the function of this node
    pNodeNew->pData = Abc_NtkMultiDeriveBdd( (DdManager *)pNtkNew->pManFunc, pNodeOld, vCone );    
    Cudd_Ref( (DdNode *)pNodeNew->pData );
    Vec_PtrFree( vCone );

    // remember the node
    pNodeOld->pCopy = pNodeNew;
    return pNodeOld->pCopy;
}

void Abc_NtkMultiCone ( Abc_Obj_t *  pNode, Vec_Ptr_t *  vCone  )

static

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

Synopsis [Collects the fanins of a large node.]

Description []

SideEffects []

SeeAlso []

Definition at line 634 of file abcMulti.c.

{
    assert( !Abc_ObjIsComplement(pNode) );
    assert( Abc_ObjIsNode(pNode) );
    vCone->nSize = 0;
    Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,0), vCone );
    Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,1), vCone );
}

void Abc_NtkMultiCone_rec	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vCone
	)

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

Synopsis [Collects the fanins of a large node.]

Description []

SideEffects []

SeeAlso []

Definition at line 611 of file abcMulti.c.

{
    assert( !Abc_ObjIsComplement(pNode) );
    if ( pNode->fMarkA || !Abc_ObjIsNode(pNode) )
    {
        Vec_PtrPushUnique( vCone, pNode );
        return;
    }
    Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,0), vCone );
    Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,1), vCone );
}

DdNode * Abc_NtkMultiDeriveBdd ( DdManager *  dd, Abc_Obj_t *  pNodeOld, Vec_Ptr_t *  vFaninsOld  )

static

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

Synopsis [Derives the local BDD of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file abcMulti.c.

{
    Abc_Obj_t * pFaninOld;
    DdNode * bFunc;
    int i;
    assert( !Abc_AigNodeIsConst(pNodeOld) );
    assert( Abc_ObjIsNode(pNodeOld) );
    // set the elementary BDD variables for the input nodes
    for ( i = 0; i < vFaninsOld->nSize; i++ )
    {
        pFaninOld = (Abc_Obj_t *)vFaninsOld->pArray[i];
        pFaninOld->pData = Cudd_bddIthVar( dd, i );    Cudd_Ref( (DdNode *)pFaninOld->pData );
        pFaninOld->fMarkC = 1;
    }
    // call the recursive BDD computation
    bFunc = Abc_NtkMultiDeriveBdd_rec( dd, pNodeOld, vFaninsOld );  Cudd_Ref( bFunc );
    // dereference the intermediate nodes
    for ( i = 0; i < vFaninsOld->nSize; i++ )
    {
        pFaninOld = (Abc_Obj_t *)vFaninsOld->pArray[i];
        Cudd_RecursiveDeref( dd, (DdNode *)pFaninOld->pData );
        pFaninOld->fMarkC = 0;
    }
    Cudd_Deref( bFunc );
    return bFunc;
}

DdNode * Abc_NtkMultiDeriveBdd_rec ( DdManager *  dd, Abc_Obj_t *  pNode, Vec_Ptr_t *  vFanins  )

static

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

Synopsis [Derives the local BDD of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 255 of file abcMulti.c.

{
    DdNode * bFunc, * bFunc0, * bFunc1;
    assert( !Abc_ObjIsComplement(pNode) );
    // if the result is available return
    if ( pNode->fMarkC )
    {
        assert( pNode->pData ); // network has a cycle
        return (DdNode *)pNode->pData;
    }
    // mark the node as visited
    pNode->fMarkC = 1;
    Vec_PtrPush( vFanins, pNode );
    // compute the result for both branches
    bFunc0 = Abc_NtkMultiDeriveBdd_rec( dd, Abc_ObjFanin(pNode,0), vFanins ); Cudd_Ref( bFunc0 );
    bFunc1 = Abc_NtkMultiDeriveBdd_rec( dd, Abc_ObjFanin(pNode,1), vFanins ); Cudd_Ref( bFunc1 );
    bFunc0 = Cudd_NotCond( bFunc0, (long)Abc_ObjFaninC0(pNode) );
    bFunc1 = Cudd_NotCond( bFunc1, (long)Abc_ObjFaninC1(pNode) );
    // get the final result
    bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 );   Cudd_Ref( bFunc );
    Cudd_RecursiveDeref( dd, bFunc0 );
    Cudd_RecursiveDeref( dd, bFunc1 );
    // set the result
    pNode->pData = bFunc;
    assert( pNode->pData );
    return bFunc;
}

void Abc_NtkMultiInt ( Abc_Ntk_t *  pNtk, Abc_Ntk_t *  pNtkNew  )

static

DECLARATIONS ///.

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

FileName [abcMulti.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Procedures which transform an AIG into multi-input AND-graph.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]

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

Synopsis [Transforms the AIG into nodes.]

Description [Threhold is the max number of nodes duplicated at a node.]

SideEffects []

SeeAlso []

Definition at line 125 of file abcMulti.c.

{
    ProgressBar * pProgress;
    Abc_Obj_t * pNode, * pConst1, * pNodeNew;
    int i;

    // set the constant node
    pConst1 = Abc_AigConst1(pNtk);
    if ( Abc_ObjFanoutNum(pConst1) > 0 )
    {
        pNodeNew = Abc_NtkCreateNode( pNtkNew );  
        pNodeNew->pData = Cudd_ReadOne( (DdManager *)pNtkNew->pManFunc );   Cudd_Ref( (DdNode *)pNodeNew->pData );
        pConst1->pCopy = pNodeNew;
    }

    // perform renoding for POs
    pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
    Abc_NtkForEachCo( pNtk, pNode, i )
    {
        Extra_ProgressBarUpdate( pProgress, i, NULL );
        if ( Abc_ObjIsCi(Abc_ObjFanin0(pNode)) )
            continue;
        Abc_NtkMulti_rec( pNtkNew, Abc_ObjFanin0(pNode) );
    }
    Extra_ProgressBarStop( pProgress );

    // clean the boundaries and data field in the old network
    Abc_NtkForEachObj( pNtk, pNode, i )
    {
        pNode->fMarkA = 0;
        pNode->pData = NULL;
    }
}

int Abc_NtkMultiLimit	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vCone,
		int	nFaninMax
	)

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

Synopsis [Limits the cones to be no more than the given size.]

Description [Returns 1 if the last cone was limited. Returns 0 if no changes.]

SideEffects []

SeeAlso []

Definition at line 365 of file abcMulti.c.

{
    vCone->nSize = 0;
    return Abc_NtkMultiLimit_rec( pNode, vCone, nFaninMax, 1, 1 );
}

int Abc_NtkMultiLimit_rec	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vCone,
		int	nFaninMax,
		int	fCanStop,
		int	fFirst
	)

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

Synopsis [Limits the cones to be no more than the given size.]

Description [Returns 1 if the last cone was limited. Returns 0 if no changes.]

SideEffects []

SeeAlso []

Definition at line 296 of file abcMulti.c.

{
    int nNodes0, nNodes1;
    assert( !Abc_ObjIsComplement(pNode) );
    // check if the node should be added to the fanins
    if ( !fFirst && (pNode->fMarkA || !Abc_ObjIsNode(pNode)) )
    {
        Vec_PtrPushUnique( vCone, pNode );
        return 0;
    }
    // if we cannot stop in this branch, collect all nodes
    if ( !fCanStop )
    {
        Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,0), vCone, nFaninMax, 0, 0 );
        Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
        return 0;
    }
    // if we can stop, try the left branch first, and return if we stopped
    assert( vCone->nSize == 0 );
    if ( Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,0), vCone, nFaninMax, 1, 0 ) )
        return 1;
    // save the number of nodes in the left branch and call for the right branch
    nNodes0 = vCone->nSize;
    assert( nNodes0 <= nFaninMax );
    Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
    // check the number of nodes
    if ( vCone->nSize <= nFaninMax )
        return 0;
    // the number of nodes exceeds the limit

    // get the number of nodes in the right branch
    vCone->nSize = 0;
    Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
    // if this number exceeds the limit, solve the problem for this branch
    if ( vCone->nSize > nFaninMax )
    {
        int RetValue;
        vCone->nSize = 0;
        RetValue = Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 1, 0 );
        assert( RetValue == 1 );
        return 1;
    }

    nNodes1 = vCone->nSize; 
    assert( nNodes1 <= nFaninMax );
    if ( nNodes0 >= nNodes1 )
    { // the left branch is larger - cut it
        assert( Abc_ObjFanin(pNode,0)->fMarkA == 0 );
        Abc_ObjFanin(pNode,0)->fMarkA = 1;
    }
    else
    { // the right branch is larger - cut it
        assert( Abc_ObjFanin(pNode,1)->fMarkA == 0 );
        Abc_ObjFanin(pNode,1)->fMarkA = 1;
    }
    return 1;
}

void Abc_NtkMultiSetBounds ( Abc_Ntk_t *  pNtk, int  nThresh, int  nFaninMax  )

static

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

Synopsis [Sets the expansion boundary for multi-input nodes.]

Description [The boundary includes the set of PIs and all nodes such that when expanding over the node we duplicate no more than nThresh nodes.]

SideEffects []

SeeAlso []

Definition at line 383 of file abcMulti.c.

{
    Vec_Ptr_t * vCone = Vec_PtrAlloc(10);
    Abc_Obj_t * pNode;
    int i, nFanouts, nConeSize;

    // make sure the mark is not set
    Abc_NtkForEachObj( pNtk, pNode, i )
        assert( pNode->fMarkA == 0 );

    // mark the nodes where expansion stops using pNode->fMarkA
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // mark the nodes with multiple fanouts
        nFanouts = Abc_ObjFanoutNum(pNode);
        nConeSize = Abc_NodeMffcSize(pNode);
        if ( (nFanouts - 1) * nConeSize > nThresh )
            pNode->fMarkA = 1;
    }

    // mark the PO drivers
    Abc_NtkForEachCo( pNtk, pNode, i )
        Abc_ObjFanin0(pNode)->fMarkA = 1;

    // make sure the fanin limit is met
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        if ( pNode->fMarkA == 0 )
            continue;
        // continue cutting branches until it meets the fanin limit
        while ( Abc_NtkMultiLimit(pNode, vCone, nFaninMax) );
        assert( vCone->nSize <= nFaninMax );  
    }
    Vec_PtrFree(vCone);
/*
    // make sure the fanin limit is met
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        if ( pNode->fMarkA == 0 )
            continue;
        Abc_NtkMultiCone( pNode, vCone );
        assert( vCone->nSize <= nFaninMax );    
    }
*/
}

void Abc_NtkMultiSetBoundsCnf ( Abc_Ntk_t *  pNtk )

static

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

Synopsis [Sets the expansion boundary for conversion into CNF.]

Description [The boundary includes the set of PIs, the roots of MUXes, the nodes with multiple fanouts and the nodes with complemented outputs.]

SideEffects []

SeeAlso []

Definition at line 450 of file abcMulti.c.

{
    Abc_Obj_t * pNode;
    int i, nMuxes;

    // make sure the mark is not set
    Abc_NtkForEachObj( pNtk, pNode, i )
        assert( pNode->fMarkA == 0 );

    // mark the nodes where expansion stops using pNode->fMarkA
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // mark the nodes with multiple fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1 )
            pNode->fMarkA = 1;
        // mark the nodes that are roots of MUXes
        if ( Abc_NodeIsMuxType( pNode ) )
        {
            pNode->fMarkA = 1;
            Abc_ObjFanin0( Abc_ObjFanin0(pNode) )->fMarkA = 1;
            Abc_ObjFanin0( Abc_ObjFanin1(pNode) )->fMarkA = 1;
            Abc_ObjFanin1( Abc_ObjFanin0(pNode) )->fMarkA = 1;
            Abc_ObjFanin1( Abc_ObjFanin1(pNode) )->fMarkA = 1;
        }
        else  // mark the complemented edges
        {
            if ( Abc_ObjFaninC0(pNode) )
                Abc_ObjFanin0(pNode)->fMarkA = 1;
            if ( Abc_ObjFaninC1(pNode) )
                Abc_ObjFanin1(pNode)->fMarkA = 1;
        }
    }

    // mark the PO drivers
    Abc_NtkForEachCo( pNtk, pNode, i )
        Abc_ObjFanin0(pNode)->fMarkA = 1;

    // count the number of MUXes
    nMuxes = 0;
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        if ( Abc_NodeIsMuxType(pNode) && 
            Abc_ObjFanin0(pNode)->fMarkA == 0 &&
            Abc_ObjFanin1(pNode)->fMarkA == 0 )
            nMuxes++;
    }
//    printf( "The number of MUXes detected = %d (%5.2f %% of logic).\n", nMuxes, 300.0*nMuxes/Abc_NtkNodeNum(pNtk) );
} 

void Abc_NtkMultiSetBoundsFactor ( Abc_Ntk_t *  pNtk )

static

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

Synopsis [Sets a factor-cut boundary.]

Description []

SideEffects []

SeeAlso []

Definition at line 585 of file abcMulti.c.

{
    Abc_Obj_t * pNode;
    int i;
    // make sure the mark is not set
    Abc_NtkForEachObj( pNtk, pNode, i )
        assert( pNode->fMarkA == 0 );
    // mark the nodes where expansion stops using pNode->fMarkA
    Abc_NtkForEachNode( pNtk, pNode, i )
        pNode->fMarkA = (pNode->vFanouts.nSize > 1 && !Abc_NodeIsMuxControlType(pNode));
    // mark the PO drivers
    Abc_NtkForEachCo( pNtk, pNode, i )
        Abc_ObjFanin0(pNode)->fMarkA = 1;
}

void Abc_NtkMultiSetBoundsMulti ( Abc_Ntk_t *  pNtk, int  nThresh  )

static

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

Synopsis [Sets the expansion boundary for conversion into multi-input AND graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 516 of file abcMulti.c.

{
    Abc_Obj_t * pNode;
    int i, nFanouts, nConeSize;

    // make sure the mark is not set
    Abc_NtkForEachObj( pNtk, pNode, i )
        assert( pNode->fMarkA == 0 );

    // mark the nodes where expansion stops using pNode->fMarkA
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip PI/PO nodes
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // mark the nodes with multiple fanouts
//        if ( Abc_ObjFanoutNum(pNode) > 1 )
//            pNode->fMarkA = 1;
        // mark the nodes with multiple fanouts
        nFanouts = Abc_ObjFanoutNum(pNode);
        nConeSize = Abc_NodeMffcSizeStop(pNode);
        if ( (nFanouts - 1) * nConeSize > nThresh )
            pNode->fMarkA = 1;
        // mark the children if they are pointed by the complemented edges
        if ( Abc_ObjFaninC0(pNode) )
            Abc_ObjFanin0(pNode)->fMarkA = 1;
        if ( Abc_ObjFaninC1(pNode) )
            Abc_ObjFanin1(pNode)->fMarkA = 1;
    }

    // mark the PO drivers
    Abc_NtkForEachCo( pNtk, pNode, i )
        Abc_ObjFanin0(pNode)->fMarkA = 1;
}

void Abc_NtkMultiSetBoundsSimple ( Abc_Ntk_t *  pNtk )

static

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

Synopsis [Sets a simple boundary.]

Description []

SideEffects []

SeeAlso []

Definition at line 562 of file abcMulti.c.

{
    Abc_Obj_t * pNode;
    int i;
    // make sure the mark is not set
    Abc_NtkForEachObj( pNtk, pNode, i )
        assert( pNode->fMarkA == 0 );
    // mark the nodes where expansion stops using pNode->fMarkA
    Abc_NtkForEachNode( pNtk, pNode, i )
        pNode->fMarkA = 1;
}