/**CFile**************************************************************** FileName [abcMinBase.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Network and node package.] Synopsis [Makes nodes of the network minimum base.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: abcMinBase.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "abc.h" #include "misc/extra/extraBdd.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static int Abc_NodeSupport( DdNode * bFunc, Vec_Str_t * vSupport, int nVars ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Makes nodes minimum base.] Description [Returns the number of changed nodes.] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkMinimumBase( Abc_Ntk_t * pNtk ) { Abc_Obj_t * pNode; int i, Counter; assert( Abc_NtkIsBddLogic(pNtk) ); Counter = 0; Abc_NtkForEachNode( pNtk, pNode, i ) Counter += Abc_NodeMinimumBase( pNode ); return Counter; } /**Function************************************************************* Synopsis [Makes one node minimum base.] Description [Returns 1 if the node is changed.] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeMinimumBase( Abc_Obj_t * pNode ) { Vec_Str_t * vSupport; Vec_Ptr_t * vFanins; DdNode * bTemp; int i, nVars; assert( Abc_NtkIsBddLogic(pNode->pNtk) ); assert( Abc_ObjIsNode(pNode) ); // compute support vSupport = Vec_StrAlloc( 10 ); nVars = Abc_NodeSupport( Cudd_Regular(pNode->pData), vSupport, Abc_ObjFaninNum(pNode) ); if ( nVars == Abc_ObjFaninNum(pNode) ) { Vec_StrFree( vSupport ); return 0; } // remove unused fanins vFanins = Vec_PtrAlloc( Abc_ObjFaninNum(pNode) ); Abc_NodeCollectFanins( pNode, vFanins ); for ( i = 0; i < vFanins->nSize; i++ ) if ( vSupport->pArray[i] == 0 ) Abc_ObjDeleteFanin( pNode, (Abc_Obj_t *)vFanins->pArray[i] ); assert( nVars == Abc_ObjFaninNum(pNode) ); // update the function of the node pNode->pData = Extra_bddRemapUp( (DdManager *)pNode->pNtk->pManFunc, bTemp = (DdNode *)pNode->pData ); Cudd_Ref( (DdNode *)pNode->pData ); Cudd_RecursiveDeref( (DdManager *)pNode->pNtk->pManFunc, bTemp ); Vec_PtrFree( vFanins ); Vec_StrFree( vSupport ); return 1; } /**Function************************************************************* Synopsis [Makes nodes of the network fanin-dup-free.] Description [Returns the number of pairs of duplicated fanins.] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkRemoveDupFanins( Abc_Ntk_t * pNtk ) { Abc_Obj_t * pNode; int i, Counter; assert( Abc_NtkIsBddLogic(pNtk) ); Counter = 0; Abc_NtkForEachNode( pNtk, pNode, i ) Counter += Abc_NodeRemoveDupFanins( pNode ); return Counter; } /**Function************************************************************* Synopsis [Removes one pair of duplicated fanins if present.] Description [Returns 1 if the node is changed.] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeRemoveDupFanins_int( Abc_Obj_t * pNode ) { Abc_Obj_t * pFanin1, * pFanin2; int i, k; assert( Abc_NtkIsBddLogic(pNode->pNtk) ); assert( Abc_ObjIsNode(pNode) ); // make sure fanins are not duplicated Abc_ObjForEachFanin( pNode, pFanin2, i ) { Abc_ObjForEachFanin( pNode, pFanin1, k ) { if ( k >= i ) break; if ( pFanin1 == pFanin2 ) { DdManager * dd = (DdManager *)pNode->pNtk->pManFunc; DdNode * bVar1 = Cudd_bddIthVar( dd, i ); DdNode * bVar2 = Cudd_bddIthVar( dd, k ); DdNode * bTrans, * bTemp; bTrans = Cudd_bddXnor( dd, bVar1, bVar2 ); Cudd_Ref( bTrans ); pNode->pData = Cudd_bddAndAbstract( dd, bTemp = (DdNode *)pNode->pData, bTrans, bVar2 ); Cudd_Ref( (DdNode *)pNode->pData ); Cudd_RecursiveDeref( dd, bTemp ); Cudd_RecursiveDeref( dd, bTrans ); Abc_NodeMinimumBase( pNode ); return 1; } } } return 0; } /**Function************************************************************* Synopsis [Removes duplicated fanins if present.] Description [Returns the number of fanins removed.] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeRemoveDupFanins( Abc_Obj_t * pNode ) { int Counter = 0; while ( Abc_NodeRemoveDupFanins_int(pNode) ) Counter++; return Counter; } /**Function************************************************************* Synopsis [Computes support of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodeSupport_rec( DdNode * bFunc, Vec_Str_t * vSupport ) { if ( cuddIsConstant(bFunc) || Cudd_IsComplement(bFunc->next) ) return; vSupport->pArray[ bFunc->index ] = 1; Abc_NodeSupport_rec( cuddT(bFunc), vSupport ); Abc_NodeSupport_rec( Cudd_Regular(cuddE(bFunc)), vSupport ); bFunc->next = Cudd_Not(bFunc->next); } /**Function************************************************************* Synopsis [Computes support of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NodeSupportClear_rec( DdNode * bFunc ) { if ( !Cudd_IsComplement(bFunc->next) ) return; bFunc->next = Cudd_Regular(bFunc->next); if ( cuddIsConstant(bFunc) ) return; Abc_NodeSupportClear_rec( cuddT(bFunc) ); Abc_NodeSupportClear_rec( Cudd_Regular(cuddE(bFunc)) ); } /**Function************************************************************* Synopsis [Computes support of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeSupport( DdNode * bFunc, Vec_Str_t * vSupport, int nVars ) { int Counter, i; // compute the support by marking the BDD Vec_StrFill( vSupport, nVars, 0 ); Abc_NodeSupport_rec( bFunc, vSupport ); // clear the marak Abc_NodeSupportClear_rec( bFunc ); // get the number of support variables Counter = 0; for ( i = 0; i < nVars; i++ ) Counter += vSupport->pArray[i]; return Counter; } /**Function************************************************************* Synopsis [Find the number of unique variables after collapsing.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeCheckDupFanin( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, int * piFanin ) { Abc_Obj_t * pObj; int i, Counter = 0; Abc_ObjForEachFanin( pFanout, pObj, i ) if ( pObj == pFanin ) { if ( piFanin ) *piFanin = i; Counter++; } return Counter; } /**Function************************************************************* Synopsis [Find the number of unique variables after collapsing.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeCollapseSuppSize( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, Vec_Ptr_t * vFanins ) { Abc_Obj_t * pObj; int i; Vec_PtrClear( vFanins ); Abc_ObjForEachFanin( pFanout, pObj, i ) if ( pObj != pFanin ) Vec_PtrPushUnique( vFanins, pObj ); Abc_ObjForEachFanin( pFanin, pObj, i ) Vec_PtrPushUnique( vFanins, pObj ); return Vec_PtrSize( vFanins ); } /**Function************************************************************* Synopsis [Returns the index of the new fanin.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_ObjFaninNumberNew( Vec_Ptr_t * vFanins, Abc_Obj_t * pFanin ) { Abc_Obj_t * pObj; int i; Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i ) if ( pObj == pFanin ) return i; return -1; } /**Function************************************************************* Synopsis [Find the permutation map for the given node into the new order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeCollapsePermMap( Abc_Obj_t * pNode, Abc_Obj_t * pSkip, Vec_Ptr_t * vFanins, int * pPerm ) { Abc_Obj_t * pFanin; int i; for ( i = 0; i < Vec_PtrSize(vFanins); i++ ) pPerm[i] = i; Abc_ObjForEachFanin( pNode, pFanin, i ) { if ( pFanin == pSkip ) continue; pPerm[i] = Abc_ObjFaninNumberNew( vFanins, pFanin ); if ( pPerm[i] == -1 ) return 0; } return 1; } /**Function************************************************************* Synopsis [Eliminates the nodes into their fanouts if the node size does not exceed this number.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ DdNode * Abc_NodeCollapseFunc( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, Vec_Ptr_t * vFanins, int * pPermFanin, int * pPermFanout ) { DdManager * dd = (DdManager *)pFanin->pNtk->pManFunc; DdNode * bVar, * bFunc0, * bFunc1, * bTemp, * bFanin, * bFanout; int RetValue, nSize, iFanin; // can only eliminate if fanin occurs in the fanin list of the fanout exactly once if ( Abc_NodeCheckDupFanin( pFanin, pFanout, &iFanin ) != 1 ) return NULL; // find the new number of fanins after collapsing nSize = Abc_NodeCollapseSuppSize( pFanin, pFanout, vFanins ); bVar = Cudd_bddIthVar( dd, nSize - 1 ); assert( nSize <= dd->size ); // find the permutation after collapsing RetValue = Abc_NodeCollapsePermMap( pFanin, NULL, vFanins, pPermFanin ); assert( RetValue ); RetValue = Abc_NodeCollapsePermMap( pFanout, pFanin, vFanins, pPermFanout ); assert( RetValue ); // cofactor the local function of the node bVar = Cudd_bddIthVar( dd, iFanin ); bFunc0 = Cudd_Cofactor( dd, (DdNode *)pFanout->pData, Cudd_Not(bVar) ); Cudd_Ref( bFunc0 ); bFunc1 = Cudd_Cofactor( dd, (DdNode *)pFanout->pData, bVar ); Cudd_Ref( bFunc1 ); // find the permutation after collapsing bFunc0 = Cudd_bddPermute( dd, bTemp = bFunc0, pPermFanout ); Cudd_Ref( bFunc0 ); Cudd_RecursiveDeref( dd, bTemp ); bFunc1 = Cudd_bddPermute( dd, bTemp = bFunc1, pPermFanout ); Cudd_Ref( bFunc1 ); Cudd_RecursiveDeref( dd, bTemp ); bFanin = Cudd_bddPermute( dd, (DdNode *)pFanin->pData, pPermFanin ); Cudd_Ref( bFanin ); // create the new function bFanout = Cudd_bddIte( dd, bFanin, bFunc1, bFunc0 ); Cudd_Ref( bFanout ); Cudd_RecursiveDeref( dd, bFanin ); Cudd_RecursiveDeref( dd, bFunc1 ); Cudd_RecursiveDeref( dd, bFunc0 ); Cudd_Deref( bFanout ); return bFanout; } int Abc_NodeCollapse( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, Vec_Ptr_t * vFanins, int * pPermFanin, int * pPermFanout ) { Abc_Obj_t * pFanoutNew, * pObj; DdNode * bFanoutNew; int i; assert( Abc_NtkIsBddLogic(pFanin->pNtk) ); assert( Abc_ObjIsNode(pFanin) ); assert( Abc_ObjIsNode(pFanout) ); bFanoutNew = Abc_NodeCollapseFunc( pFanin, pFanout, vFanins, pPermFanin, pPermFanout ); if ( bFanoutNew == NULL ) return 0; Cudd_Ref( bFanoutNew ); // create the new node pFanoutNew = Abc_NtkCreateNode( pFanin->pNtk ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i ) Abc_ObjAddFanin( pFanoutNew, pObj ); pFanoutNew->pData = bFanoutNew; // minimize the node Abc_NodeMinimumBase( pFanoutNew ); // transfer the fanout Abc_ObjTransferFanout( pFanout, pFanoutNew ); assert( Abc_ObjFanoutNum( pFanout ) == 0 ); Abc_NtkDeleteObj_rec( pFanout, 1 ); return 1; } int Abc_NtkEliminate( Abc_Ntk_t * pNtk, int nMaxSize, int fReverse, int fVerbose ) { extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose ); Vec_Ptr_t * vFanouts, * vFanins, * vNodes; Abc_Obj_t * pNode, * pFanout; int * pPermFanin, * pPermFanout; int RetValue, i, k; assert( nMaxSize > 0 ); assert( Abc_NtkIsLogic(pNtk) ); // convert network to BDD representation if ( !Abc_NtkToBdd(pNtk) ) { fprintf( stdout, "Converting to BDD has failed.\n" ); return 0; } // prepare nodes for sweeping Abc_NtkRemoveDupFanins( pNtk ); Abc_NtkMinimumBase( pNtk ); Abc_NtkCleanup( pNtk, 0 ); // get the nodes in the given order vNodes = fReverse? Abc_NtkDfsReverse( pNtk ) : Abc_NtkDfs( pNtk, 0 ); // go through the nodes and decide is they can be eliminated pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 ); pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 ); vFanins = Vec_PtrAlloc( 1000 ); vFanouts = Vec_PtrAlloc( 1000 ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { if ( !Abc_ObjIsNode(pNode) ) // skip deleted nodes continue; if ( Abc_NodeFindCoFanout(pNode) != NULL ) continue; if ( Abc_ObjFaninNum(pNode) > nMaxSize ) continue; Abc_ObjForEachFanout( pNode, pFanout, k ) if ( Abc_NodeCollapseSuppSize(pNode, pFanout, vFanins) > nMaxSize ) break; if ( k < Abc_ObjFanoutNum(pNode) ) continue; // perform elimination Abc_NodeCollectFanouts( pNode, vFanouts ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k ) { if ( fVerbose ) printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ", Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) ); RetValue = Abc_NodeCollapse( pNode, pFanout, vFanins, pPermFanin, pPermFanout ); assert( RetValue ); if ( fVerbose ) { Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 ); if ( pNodeNew ) printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) ); } } } Abc_NtkBddReorder( pNtk, 0 ); Vec_PtrFree( vFanins ); Vec_PtrFree( vFanouts ); Vec_PtrFree( vNodes ); ABC_FREE( pPermFanin ); ABC_FREE( pPermFanout ); return 1; } /**Function************************************************************* Synopsis [Check how many times fanin appears in the FF of the fanout.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NodeCountAppearances( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout ) { Hop_Man_t * pMan = (Hop_Man_t *)pFanin->pNtk->pManFunc; int iFanin = Abc_NodeFindFanin( pFanout, pFanin ); assert( iFanin >= 0 && iFanin < Hop_ManPiNum(pMan) ); return Hop_ObjFanoutCount( (Hop_Obj_t *)pFanout->pData, Hop_IthVar(pMan, iFanin) ); } int Abc_NodeCountAppearancesAll( Abc_Obj_t * pNode ) { Abc_Obj_t * pFanout; int i, Count = 0; Abc_ObjForEachFanout( pNode, pFanout, i ) Count += Abc_NodeCountAppearances( pNode, pFanout ); return Count; } /**Function************************************************************* Synopsis [Performs traditional eliminate -1.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Hop_Obj_t * Abc_NodeCollapseFunc1( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, Vec_Ptr_t * vFanins, int * pPermFanin, int * pPermFanout ) { Hop_Man_t * pMan = (Hop_Man_t *)pFanin->pNtk->pManFunc; Hop_Obj_t * bFanin, * bFanout; int RetValue, nSize, iFanin; // can only eliminate if fanin occurs in the fanin list of the fanout exactly once if ( Abc_NodeCheckDupFanin( pFanin, pFanout, &iFanin ) != 1 ) return NULL; // find the new number of fanins after collapsing nSize = Abc_NodeCollapseSuppSize( pFanin, pFanout, vFanins ); Hop_IthVar( pMan, nSize ); // use additional var for fanin variable assert( nSize + 1 <= Hop_ManPiNum(pMan) ); // find the permutation after collapsing RetValue = Abc_NodeCollapsePermMap( pFanin, NULL, vFanins, pPermFanin ); assert( RetValue ); RetValue = Abc_NodeCollapsePermMap( pFanout, pFanin, vFanins, pPermFanout ); assert( RetValue ); // include fanin's variable pPermFanout[iFanin] = nSize; // create new function of fanin and fanout bFanin = Hop_Permute( pMan, (Hop_Obj_t *)pFanin->pData, Abc_ObjFaninNum(pFanin), pPermFanin ); bFanout = Hop_Permute( pMan, (Hop_Obj_t *)pFanout->pData, Abc_ObjFaninNum(pFanout), pPermFanout ); // compose fanin into fanout return Hop_Compose( pMan, bFanout, bFanin, nSize ); } int Abc_NodeCollapse1( Abc_Obj_t * pFanin, Abc_Obj_t * pFanout, Vec_Ptr_t * vFanins, int * pPermFanin, int * pPermFanout ) { Abc_Obj_t * pFanoutNew, * pObj; Hop_Obj_t * bFanoutNew; int i; assert( Abc_NtkIsAigLogic(pFanin->pNtk) ); assert( Abc_ObjIsNode(pFanin) ); assert( Abc_ObjIsNode(pFanout) ); bFanoutNew = Abc_NodeCollapseFunc1( pFanin, pFanout, vFanins, pPermFanin, pPermFanout ); if ( bFanoutNew == NULL ) return 0; // create the new node pFanoutNew = Abc_NtkCreateNode( pFanin->pNtk ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pObj, i ) Abc_ObjAddFanin( pFanoutNew, pObj ); pFanoutNew->pData = bFanoutNew; // transfer the fanout Abc_ObjTransferFanout( pFanout, pFanoutNew ); assert( Abc_ObjFanoutNum( pFanout ) == 0 ); Abc_NtkDeleteObj_rec( pFanout, 1 ); return 1; } int Abc_NodeIsExor( Abc_Obj_t * pNode ) { Hop_Man_t * pMan; word Truth; if ( Abc_ObjFaninNum(pNode) < 3 || Abc_ObjFaninNum(pNode) > 6 ) return 0; pMan = (Hop_Man_t *)pNode->pNtk->pManFunc; Truth = Hop_ManComputeTruth6( pMan, (Hop_Obj_t *)pNode->pData, Abc_ObjFaninNum(pNode) ); if ( Truth == 0x6666666666666666 || Truth == 0x9999999999999999 || Truth == 0x9696969696969696 || Truth == 0x6969696969696969 || Truth == 0x6996699669966996 || Truth == 0x9669966996699669 || Truth == 0x9669699696696996 || Truth == 0x6996966969969669 || Truth == 0x6996966996696996 || Truth == 0x9669699669969669 ) return 1; return 0; } int Abc_NtkEliminate1One( Abc_Ntk_t * pNtk, int ElimValue, int nMaxSize, int fReverse, int fVerbose ) { Vec_Ptr_t * vFanouts, * vFanins, * vNodes; Abc_Obj_t * pNode, * pFanout; int * pPermFanin, * pPermFanout; int RetValue, i, k; assert( nMaxSize > 0 ); assert( Abc_NtkIsLogic(pNtk) ); // convert network to BDD representation if ( !Abc_NtkToAig(pNtk) ) { fprintf( stdout, "Converting to AIG has failed.\n" ); return 0; } // get the nodes in the given order vNodes = fReverse? Abc_NtkDfsReverse( pNtk ) : Abc_NtkDfs( pNtk, 0 ); // go through the nodes and decide is they can be eliminated pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 ); pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 ); vFanins = Vec_PtrAlloc( 1000 ); vFanouts = Vec_PtrAlloc( 1000 ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { if ( !Abc_ObjIsNode(pNode) ) // skip deleted nodes continue; if ( Abc_NodeFindCoFanout(pNode) != NULL ) continue; if ( Abc_ObjFaninNum(pNode) > nMaxSize ) continue; if ( Abc_NodeIsExor(pNode) ) continue; // skip nodes with more than one fanout // if ( Abc_ObjFanoutNum(pNode) != 1 ) // continue; // skip nodes that appear in the FF of their fanout more than once if ( Abc_NodeCountAppearancesAll( pNode ) > ElimValue + 2 ) continue; Abc_ObjForEachFanout( pNode, pFanout, k ) if ( Abc_NodeCollapseSuppSize(pNode, pFanout, vFanins) > nMaxSize ) break; if ( k < Abc_ObjFanoutNum(pNode) ) continue; // perform elimination Abc_NodeCollectFanouts( pNode, vFanouts ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k ) { if ( fVerbose ) printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ", Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) ); RetValue = Abc_NodeCollapse1( pNode, pFanout, vFanins, pPermFanin, pPermFanout ); assert( RetValue ); if ( fVerbose ) { Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 ); if ( pNodeNew ) printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) ); } } } Vec_PtrFree( vFanins ); Vec_PtrFree( vFanouts ); Vec_PtrFree( vNodes ); ABC_FREE( pPermFanin ); ABC_FREE( pPermFanout ); return 1; } int Abc_NtkEliminate1( Abc_Ntk_t * pNtk, int ElimValue, int nMaxSize, int nIterMax, int fReverse, int fVerbose ) { int i; for ( i = 0; i < nIterMax; i++ ) { int nNodes = Abc_NtkNodeNum(pNtk); // printf( "%d ", nNodes ); if ( !Abc_NtkEliminate1One(pNtk, ElimValue, nMaxSize, fReverse, fVerbose) ) return 0; if ( nNodes == Abc_NtkNodeNum(pNtk) ) break; } return 1; } /**Function************************************************************* Synopsis [Sort nodes in the reverse topo order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_ObjCompareByNumber( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 ) { return Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp; } void Abc_ObjSortInReverseOrder( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes ) { Vec_Ptr_t * vOrder; Abc_Obj_t * pNode; int i; vOrder = Abc_NtkDfsReverse( pNtk ); Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i ) pNode->iTemp = i; Vec_PtrSort( vNodes, (int (*)())Abc_ObjCompareByNumber ); Vec_PtrForEachEntry( Abc_Obj_t *, vOrder, pNode, i ) pNode->iTemp = 0; Vec_PtrFree( vOrder ); } /**Function************************************************************* Synopsis [Performs traditional eliminate -1.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Abc_NtkEliminateSpecial( Abc_Ntk_t * pNtk, int nMaxSize, int fVerbose ) { extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose ); Vec_Ptr_t * vFanouts, * vFanins, * vNodes; Abc_Obj_t * pNode, * pFanout; int * pPermFanin, * pPermFanout; int RetValue, i, k; assert( nMaxSize > 0 ); assert( Abc_NtkIsLogic(pNtk) ); // convert network to BDD representation if ( !Abc_NtkToBdd(pNtk) ) { fprintf( stdout, "Converting to BDD has failed.\n" ); return 0; } // prepare nodes for sweeping Abc_NtkRemoveDupFanins( pNtk ); Abc_NtkMinimumBase( pNtk ); Abc_NtkCleanup( pNtk, 0 ); // convert network to SOPs if ( !Abc_NtkToSop(pNtk, 0) ) { fprintf( stdout, "Converting to SOP has failed.\n" ); return 0; } // collect info about the nodes to be eliminated vNodes = Vec_PtrAlloc( 1000 ); Abc_NtkForEachNode( pNtk, pNode, i ) { if ( Abc_ObjFanoutNum(pNode) != 1 ) continue; pFanout = Abc_ObjFanout0(pNode); if ( !Abc_ObjIsNode(pFanout) ) continue; if ( Abc_SopGetCubeNum((char *)pNode->pData) != 1 ) continue; if ( Abc_SopGetCubeNum((char *)pFanout->pData) != 1 ) continue; // find the fanout's fanin RetValue = Abc_NodeFindFanin( pFanout, pNode ); assert( RetValue >= 0 && RetValue < Abc_ObjFaninNum(pFanout) ); // both pNode and pFanout are AND/OR type nodes if ( Abc_SopIsComplement((char *)pNode->pData) == Abc_SopGetIthCareLit((char *)pFanout->pData, RetValue) ) continue; Vec_PtrPush( vNodes, pNode ); } if ( Vec_PtrSize(vNodes) == 0 ) { Vec_PtrFree( vNodes ); return 1; } Abc_ObjSortInReverseOrder( pNtk, vNodes ); // convert network to BDD representation if ( !Abc_NtkToBdd(pNtk) ) { fprintf( stdout, "Converting to BDD has failed.\n" ); return 0; } // go through the nodes and decide is they can be eliminated pPermFanin = ABC_ALLOC( int, nMaxSize + 1000 ); pPermFanout = ABC_ALLOC( int, nMaxSize + 1000 ); vFanins = Vec_PtrAlloc( 1000 ); vFanouts = Vec_PtrAlloc( 1000 ); Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i ) { assert( Abc_ObjIsNode(pNode) ); assert( Abc_NodeFindCoFanout(pNode) == NULL ); // perform elimination Abc_NodeCollectFanouts( pNode, vFanouts ); Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, k ) { if ( fVerbose ) printf( "Collapsing fanin %5d (supp =%2d) into fanout %5d (supp =%2d) ", Abc_ObjId(pNode), Abc_ObjFaninNum(pNode), Abc_ObjId(pFanout), Abc_ObjFaninNum(pFanout) ); RetValue = Abc_NodeCollapse( pNode, pFanout, vFanins, pPermFanin, pPermFanout ); assert( RetValue ); if ( fVerbose ) { Abc_Obj_t * pNodeNew = Abc_NtkObj( pNtk, Abc_NtkObjNumMax(pNtk) - 1 ); if ( pNodeNew ) printf( "resulting in node %5d (supp =%2d).\n", Abc_ObjId(pNodeNew), Abc_ObjFaninNum(pNodeNew) ); } } } Abc_NtkBddReorder( pNtk, 0 ); Vec_PtrFree( vFanins ); Vec_PtrFree( vFanouts ); Vec_PtrFree( vNodes ); ABC_FREE( pPermFanin ); ABC_FREE( pPermFanout ); return 1; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END