/**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 $] ***********************************************************************/ #include "base/abc/abc.h" #include "misc/extra/extraBdd.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static void Abc_NtkMultiInt( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ); 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 ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Transforms the AIG into nodes.] Description [Threhold is the max number of nodes duplicated at a node.] SideEffects [] SeeAlso [] ***********************************************************************/ Abc_Ntk_t * Abc_NtkMulti( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax, int fCnf, int fMulti, int fSimple, int fFactor ) { 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; } /**Function************************************************************* Synopsis [Transforms the AIG into nodes.] Description [Threhold is the max number of nodes duplicated at a node.] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiInt( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew ) { 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; } } /**Function************************************************************* Synopsis [Find the best multi-input node rooted at the given node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Abc_Obj_t * Abc_NtkMulti_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld ) { 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; } /**Function************************************************************* Synopsis [Derives the local BDD of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ DdNode * Abc_NtkMultiDeriveBdd( DdManager * dd, Abc_Obj_t * pNodeOld, Vec_Ptr_t * vFaninsOld ) { 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; } /**Function************************************************************* Synopsis [Derives the local BDD of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ DdNode * Abc_NtkMultiDeriveBdd_rec( DdManager * dd, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins ) { 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; } /**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 [] ***********************************************************************/ int Abc_NtkMultiLimit_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, int nFaninMax, int fCanStop, int fFirst ) { 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; } /**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 [] ***********************************************************************/ int Abc_NtkMultiLimit( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, int nFaninMax ) { vCone->nSize = 0; return Abc_NtkMultiLimit_rec( pNode, vCone, nFaninMax, 1, 1 ); } /**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 [] ***********************************************************************/ void Abc_NtkMultiSetBounds( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax ) { 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 ); } */ } /**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 [] ***********************************************************************/ void Abc_NtkMultiSetBoundsCnf( Abc_Ntk_t * pNtk ) { 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) ); } /**Function************************************************************* Synopsis [Sets the expansion boundary for conversion into multi-input AND graph.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiSetBoundsMulti( Abc_Ntk_t * pNtk, int nThresh ) { 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; } /**Function************************************************************* Synopsis [Sets a simple boundary.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiSetBoundsSimple( Abc_Ntk_t * pNtk ) { 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; } /**Function************************************************************* Synopsis [Sets a factor-cut boundary.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiSetBoundsFactor( Abc_Ntk_t * pNtk ) { 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; } /**Function************************************************************* Synopsis [Collects the fanins of a large node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone ) { 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 ); } /**Function************************************************************* Synopsis [Collects the fanins of a large node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Abc_NtkMultiCone( Abc_Obj_t * pNode, Vec_Ptr_t * vCone ) { 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 ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END