abcReconv.c

Go to the documentation of this file.

 
#include "base/abc/abc.h"
 
#ifdef ABC_USE_CUDD
#include "bdd/extrab/extraBdd.h"
#endif
 
ABC_NAMESPACE_IMPL_START
 

 
struct Abc_ManCut_t_
{
    // user specified parameters
    int              nNodeSizeMax;  // the limit on the size of the supernode
    int              nConeSizeMax;  // the limit on the size of the containing cone
    int              nNodeFanStop;  // the limit on the size of the supernode
    int              nConeFanStop;  // the limit on the size of the containing cone
    // internal parameters
    Vec_Ptr_t *      vNodeLeaves;   // fanins of the collapsed node (the cut)
    Vec_Ptr_t *      vConeLeaves;   // fanins of the containing cone
    Vec_Ptr_t *      vVisited;      // the visited nodes
    Vec_Vec_t *      vLevels;       // the data structure to compute TFO nodes
    Vec_Ptr_t *      vNodesTfo;     // the nodes in the TFO of the cut
};
 
static int   Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit );
static int   Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit );
static void  Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited );


static inline void Abc_NodesMark( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 1;
}

static inline void Abc_NodesUnmark( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 0;
}

static inline void Abc_NodesUnmarkB( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkB = 0;
}

static inline int Abc_NodeGetLeafCostOne( Abc_Obj_t * pNode, int nFaninLimit )
{
    int Cost;
    // make sure the node is in the construction zone
    assert( pNode->fMarkB == 1 );  
    // cannot expand over the PI node
    if ( Abc_ObjIsCi(pNode) )
        return 999;
    // get the cost of the cone
    Cost = (!Abc_ObjFanin0(pNode)->fMarkB) + (!Abc_ObjFanin1(pNode)->fMarkB);
    // always accept if the number of leaves does not increase
    if ( Cost < 2 )
        return Cost;
    // skip nodes with many fanouts
    if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
        return 999;
    // return the number of nodes that will be on the leaves if this node is removed
    return Cost;
}

static inline int Abc_NodeGetLeafCostTwo( Abc_Obj_t * pNode, int nFaninLimit, 
    Abc_Obj_t ** ppLeafToAdd, Abc_Obj_t ** pNodeToMark1, Abc_Obj_t ** pNodeToMark2 )
{
    Abc_Obj_t * pFanin0, * pFanin1, * pTemp;
    Abc_Obj_t * pGrand, * pGrandToAdd;
    // make sure the node is in the construction zone
    assert( pNode->fMarkB == 1 );  
    // cannot expand over the PI node
    if ( Abc_ObjIsCi(pNode) )
        return 999;
    // skip nodes with many fanouts
//    if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
//        return 999;
    // get the children
    pFanin0 = Abc_ObjFanin0(pNode);
    pFanin1 = Abc_ObjFanin1(pNode);
    assert( !pFanin0->fMarkB && !pFanin1->fMarkB );
    // count the number of unique grandchildren that will be included
    // return infinite cost if this number if more than 1
    if ( Abc_ObjIsCi(pFanin0) && Abc_ObjIsCi(pFanin1) )
        return 999;
    // consider the special case when a non-CI fanin can be dropped
    if ( !Abc_ObjIsCi(pFanin0) && Abc_ObjFanin0(pFanin0)->fMarkB && Abc_ObjFanin1(pFanin0)->fMarkB )
    {
        *ppLeafToAdd  = pFanin1;
        *pNodeToMark1 = pFanin0;
        *pNodeToMark2 = NULL;
        return 1;
    }
    if ( !Abc_ObjIsCi(pFanin1) && Abc_ObjFanin0(pFanin1)->fMarkB && Abc_ObjFanin1(pFanin1)->fMarkB )
    {
        *ppLeafToAdd  = pFanin0;
        *pNodeToMark1 = pFanin1;
        *pNodeToMark2 = NULL;
        return 1;
    }
 
    // make the first node CI if any
    if ( Abc_ObjIsCi(pFanin1) )
        pTemp = pFanin0, pFanin0 = pFanin1, pFanin1 = pTemp;
    // consider the first node
    pGrandToAdd = NULL;
    if ( Abc_ObjIsCi(pFanin0) )
    {
        *pNodeToMark1 = NULL;
        pGrandToAdd = pFanin0;
    }
    else
    {
        *pNodeToMark1 = pFanin0;
        pGrand = Abc_ObjFanin0(pFanin0);
        if ( !pGrand->fMarkB )
        {
            if ( pGrandToAdd && pGrandToAdd != pGrand )
                return 999;
            pGrandToAdd = pGrand;
        }
        pGrand = Abc_ObjFanin1(pFanin0);
        if ( !pGrand->fMarkB )
        {
            if ( pGrandToAdd && pGrandToAdd != pGrand )
                return 999;
            pGrandToAdd = pGrand;
        }
    }
    // consider the second node
    *pNodeToMark2 = pFanin1;
    pGrand = Abc_ObjFanin0(pFanin1);
    if ( !pGrand->fMarkB )
    {
        if ( pGrandToAdd && pGrandToAdd != pGrand )
            return 999;
        pGrandToAdd = pGrand;
    }
    pGrand = Abc_ObjFanin1(pFanin1);
    if ( !pGrand->fMarkB )
    {
        if ( pGrandToAdd && pGrandToAdd != pGrand )
            return 999;
        pGrandToAdd = pGrand;
    }
    assert( pGrandToAdd != NULL );
    *ppLeafToAdd = pGrandToAdd;
    return 1;
}
 

Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot, int fContain )
{
    Abc_Obj_t * pNode;
    int i;
 
    assert( !Abc_ObjIsComplement(pRoot) );
    assert( Abc_ObjIsNode(pRoot) );
 
    // start the visited nodes and mark them
    Vec_PtrClear( p->vVisited );
    Vec_PtrPush( p->vVisited, pRoot );
    Vec_PtrPush( p->vVisited, Abc_ObjFanin0(pRoot) );
    Vec_PtrPush( p->vVisited, Abc_ObjFanin1(pRoot) );
    pRoot->fMarkB = 1;
    Abc_ObjFanin0(pRoot)->fMarkB = 1;
    Abc_ObjFanin1(pRoot)->fMarkB = 1;
 
    // start the cut 
    Vec_PtrClear( p->vNodeLeaves );
    Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin0(pRoot) );
    Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin1(pRoot) );
 
    // compute the cut
    while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vNodeLeaves, p->nNodeSizeMax, p->nNodeFanStop ) );
    assert( Vec_PtrSize(p->vNodeLeaves) <= p->nNodeSizeMax );
 
    // return if containing cut is not requested
    if ( !fContain )
    {
        // unmark both fMarkA and fMarkB in tbe TFI
        Abc_NodesUnmarkB( p->vVisited );
        return p->vNodeLeaves;
    }
 
//printf( "\n\n\n" );
    // compute the containing cut
    assert( p->nNodeSizeMax < p->nConeSizeMax );
    // copy the current boundary
    Vec_PtrClear( p->vConeLeaves );
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodeLeaves, pNode, i )
        Vec_PtrPush( p->vConeLeaves, pNode );
    // compute the containing cut
    while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vConeLeaves, p->nConeSizeMax, p->nConeFanStop ) );
    assert( Vec_PtrSize(p->vConeLeaves) <= p->nConeSizeMax );
    // unmark TFI using fMarkA and fMarkB
    Abc_NodesUnmarkB( p->vVisited );
    return p->vNodeLeaves;
}

int Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit )
{
    Abc_Obj_t * pNode, * pFaninBest, * pNext;
    int CostBest, CostCur, i;
    // find the best fanin
    CostBest   = 100;
    pFaninBest = NULL;
//printf( "Evaluating fanins of the cut:\n" );
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
    {
        CostCur = Abc_NodeGetLeafCostOne( pNode, nFaninLimit );
//printf( "    Fanin %s has cost %d.\n", Abc_ObjName(pNode), CostCur );
//        if ( CostBest > CostCur ) // performance improvement: expand the variable with the smallest level
        if ( CostBest > CostCur ||
             (CostBest == CostCur && pNode->Level > pFaninBest->Level) )
        {
            CostBest   = CostCur;
            pFaninBest = pNode;
        }
        if ( CostBest == 0 )
            break;
    }
    if ( pFaninBest == NULL )
        return 0;
//        return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );
 
    assert( CostBest < 3 );
    if ( vLeaves->nSize - 1 + CostBest > nSizeLimit )
        return 0;
//        return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );
 
    assert( Abc_ObjIsNode(pFaninBest) );
    // remove the node from the array
    Vec_PtrRemove( vLeaves, pFaninBest );
//printf( "Removing fanin %s.\n", Abc_ObjName(pFaninBest) );
 
    // add the left child to the fanins
    pNext = Abc_ObjFanin0(pFaninBest);
    if ( !pNext->fMarkB )
    {
//printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
        pNext->fMarkB = 1;
        Vec_PtrPush( vLeaves, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    // add the right child to the fanins
    pNext = Abc_ObjFanin1(pFaninBest);
    if ( !pNext->fMarkB )
    {
//printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
        pNext->fMarkB = 1;
        Vec_PtrPush( vLeaves, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    assert( vLeaves->nSize <= nSizeLimit );
    // keep doing this
    return 1;
}

int Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit )
{
    Abc_Obj_t * pNode = NULL, * pLeafToAdd, * pNodeToMark1, * pNodeToMark2;
    int CostCur = 0, i;
    // find the best fanin
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
    {
        CostCur = Abc_NodeGetLeafCostTwo( pNode, nFaninLimit, &pLeafToAdd, &pNodeToMark1, &pNodeToMark2 );
        if ( CostCur < 2 )
            break;
    }
    if ( CostCur > 2 )
        return 0;
    // remove the node from the array
    Vec_PtrRemove( vLeaves, pNode );
    // add the node to the leaves
    if ( pLeafToAdd )
    {
        assert( !pLeafToAdd->fMarkB );
        pLeafToAdd->fMarkB = 1;
        Vec_PtrPush( vLeaves, pLeafToAdd );
        Vec_PtrPush( vVisited, pLeafToAdd );
    }
    // mark the other nodes
    if ( pNodeToMark1 )
    {
        assert( !pNodeToMark1->fMarkB );
        pNodeToMark1->fMarkB = 1;
        Vec_PtrPush( vVisited, pNodeToMark1 );
    }
    if ( pNodeToMark2 )
    {
        assert( !pNodeToMark2->fMarkB );
        pNodeToMark2->fMarkB = 1;
        Vec_PtrPush( vVisited, pNodeToMark2 );
    }
    // keep doing this
    return 1;
}
 

void Abc_NodeConeCollect( Abc_Obj_t ** ppRoots, int nRoots, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited, int fIncludeFanins )
{
    Abc_Obj_t * pTemp;
    int i;
    // mark the fanins of the cone
    Abc_NodesMark( vLeaves );
    // collect the nodes in the DFS order
    Vec_PtrClear( vVisited );
    // add the fanins
    if ( fIncludeFanins )
        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pTemp, i )
            Vec_PtrPush( vVisited, pTemp );
    // add other nodes
    for ( i = 0; i < nRoots; i++ )
        Abc_NodeConeMarkCollect_rec( ppRoots[i], vVisited );
    // unmark both sets
    Abc_NodesUnmark( vLeaves );
    Abc_NodesUnmark( vVisited );
}

void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited )
{
    if ( pNode->fMarkA == 1 )
        return;
    // visit transitive fanin 
    if ( Abc_ObjIsNode(pNode) )
    {
        Abc_NodeConeMarkCollect_rec( Abc_ObjFanin0(pNode), vVisited );
        Abc_NodeConeMarkCollect_rec( Abc_ObjFanin1(pNode), vVisited );
    }
    assert( pNode->fMarkA == 0 );
    pNode->fMarkA = 1;
    Vec_PtrPush( vVisited, pNode );
}
 
#ifdef ABC_USE_CUDD

DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    DdNode * bFunc0, * bFunc1, * bFunc = NULL;
    int i;
    // get the nodes in the cut without fanins in the DFS order
    Abc_NodeConeCollect( &pRoot, 1, vLeaves, vVisited, 0 );
    // set the elementary BDDs
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
        pNode->pCopy = (Abc_Obj_t *)pbVars[i];
    // compute the BDDs for the collected nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
    {
        assert( !Abc_ObjIsPi(pNode) );
        bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
        bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
        bFunc  = Cudd_bddAnd( dd, bFunc0, bFunc1 );    Cudd_Ref( bFunc );
        pNode->pCopy = (Abc_Obj_t *)bFunc;
    }
    assert(bFunc);
    Cudd_Ref( bFunc );
    // dereference the intermediate ones
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
    Cudd_Deref( bFunc );
    return bFunc;
}

DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited )
{
    DdNode * bFunc0, * bFunc1, * bFunc, * bTrans, * bTemp, * bCube, * bResult;
    Abc_Obj_t * pNode;
    int i;
    // get the nodes in the cut without fanins in the DFS order
    Abc_NodeConeCollect( (Abc_Obj_t **)vRoots->pArray, vRoots->nSize, vLeaves, vVisited, 0 );
    // set the elementary BDDs
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
        pNode->pCopy = (Abc_Obj_t *)pbVarsX[i];
    // compute the BDDs for the collected nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
    {
        bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
        bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
        bFunc  = Cudd_bddAnd( dd, bFunc0, bFunc1 );    Cudd_Ref( bFunc );
        pNode->pCopy = (Abc_Obj_t *)bFunc;
    }
    // compute the transition relation of the cone
    bTrans = b1;    Cudd_Ref( bTrans );
    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, i )
    {
        bFunc = Cudd_bddXnor( dd, (DdNode *)pNode->pCopy, pbVarsY[i] );  Cudd_Ref( bFunc );
        bTrans = Cudd_bddAnd( dd, bTemp = bTrans, bFunc );               Cudd_Ref( bTrans );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bFunc );
    }
    // dereference the intermediate ones
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
    // compute don't-cares
    bCube = Extra_bddComputeRangeCube( dd, vRoots->nSize, vRoots->nSize + vLeaves->nSize );  Cudd_Ref( bCube );
    bResult = Cudd_bddExistAbstract( dd, bTrans, bCube );                Cudd_Ref( bResult );
    bResult = Cudd_Not( bResult );
    Cudd_RecursiveDeref( dd, bCube );
    Cudd_RecursiveDeref( dd, bTrans );
    Cudd_Deref( bResult );
    return bResult;
}
 
#endif

Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax, int nNodeFanStop, int nConeFanStop )
{
    Abc_ManCut_t * p;
    p = ABC_ALLOC( Abc_ManCut_t, 1 );
    memset( p, 0, sizeof(Abc_ManCut_t) );
    p->vNodeLeaves  = Vec_PtrAlloc( 100 );
    p->vConeLeaves  = Vec_PtrAlloc( 100 );
    p->vVisited     = Vec_PtrAlloc( 100 );
    p->vLevels      = Vec_VecAlloc( 100 );
    p->vNodesTfo    = Vec_PtrAlloc( 100 );
    p->nNodeSizeMax = nNodeSizeMax;
    p->nConeSizeMax = nConeSizeMax;
    p->nNodeFanStop = nNodeFanStop;
    p->nConeFanStop = nConeFanStop;
    return p;
}

void Abc_NtkManCutStop( Abc_ManCut_t * p )
{
    Vec_PtrFree( p->vNodeLeaves );
    Vec_PtrFree( p->vConeLeaves );
    Vec_PtrFree( p->vVisited    );
    Vec_VecFree( p->vLevels );
    Vec_PtrFree( p->vNodesTfo );
    ABC_FREE( p );
}

Vec_Ptr_t * Abc_NtkManCutReadCutLarge( Abc_ManCut_t * p )
{
    return p->vConeLeaves;
}

Vec_Ptr_t * Abc_NtkManCutReadCutSmall( Abc_ManCut_t * p )
{
    return p->vNodeLeaves;
}

Vec_Ptr_t * Abc_NtkManCutReadVisited( Abc_ManCut_t * p )
{
    return p->vVisited;
}
 
 

Vec_Ptr_t * Abc_NodeCollectTfoCands( Abc_ManCut_t * p, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, int LevelMax )
{
    Abc_Ntk_t * pNtk = pRoot->pNtk;
    Vec_Ptr_t * vVec;
    Abc_Obj_t * pNode, * pFanout;
    int i, k, v, LevelMin;
    assert( Abc_NtkIsStrash(pNtk) );
 
    // assuming that the structure is clean
    Vec_VecForEachLevel( p->vLevels, vVec, i )
        assert( vVec->nSize == 0 );
 
    // put fanins into the structure while labeling them
    Abc_NtkIncrementTravId( pNtk );
    LevelMin = -1;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
    {
        if ( pNode->Level > (unsigned)LevelMax )
            continue;
        Abc_NodeSetTravIdCurrent( pNode );
        Vec_VecPush( p->vLevels, pNode->Level, pNode );
        if ( LevelMin < (int)pNode->Level )
            LevelMin = pNode->Level;
    }
    assert( LevelMin >= 0 );
 
    // mark MFFC 
    if ( pRoot )
        Abc_NodeMffcLabelAig( pRoot );
 
    // go through the levels up
    Vec_PtrClear( p->vNodesTfo );
    Vec_VecForEachEntryStart( Abc_Obj_t *, p->vLevels, pNode, i, k, LevelMin )
    {
        if ( i > LevelMax )
            break;
        // if the node is not marked, it is not a fanin
        if ( !Abc_NodeIsTravIdCurrent(pNode) )
        {
            // check if it belongs to the TFO
            if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pNode)) || 
                 !Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pNode)) )
                 continue;
            // save the node in the TFO and label it
            Vec_PtrPush( p->vNodesTfo, pNode );
            Abc_NodeSetTravIdCurrent( pNode );
        }
        // go through the fanouts and add them to the structure if they meet the conditions
        Abc_ObjForEachFanout( pNode, pFanout, v )
        {
            // skip if fanout is a CO or its level exceeds
            if ( Abc_ObjIsCo(pFanout) || pFanout->Level > (unsigned)LevelMax )
                continue;
            // skip if it is already added or if it is in MFFC
            if ( Abc_NodeIsTravIdCurrent(pFanout) )
                continue;
            // add it to the structure but do not mark it (until tested later)
            Vec_VecPushUnique( p->vLevels, pFanout->Level, pFanout );
        }
    }
 
    // clear the levelized structure
    Vec_VecForEachLevelStart( p->vLevels, vVec, i, LevelMin )
    {
        if ( i > LevelMax )
            break;
        Vec_PtrClear( vVec );
    }
    return p->vNodesTfo;
}

 
 
ABC_NAMESPACE_IMPL_END