diff options
Diffstat (limited to 'abc70930/src/base/abci/abcMulti.c')
| -rw-r--r-- | abc70930/src/base/abci/abcMulti.c | 643 |
1 files changed, 643 insertions, 0 deletions
diff --git a/abc70930/src/base/abci/abcMulti.c b/abc70930/src/base/abci/abcMulti.c new file mode 100644 index 00000000..e93360a0 --- /dev/null +++ b/abc70930/src/base/abci/abcMulti.c @@ -0,0 +1,643 @@ +/**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 "abc.h" + +//////////////////////////////////////////////////////////////////////// +/// 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( pNtkNew->pManFunc ); Cudd_Ref( 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, vCone->pArray[i]) ); + + // derive the function of this node + pNodeNew->pData = Abc_NtkMultiDeriveBdd( pNtkNew->pManFunc, pNodeOld, vCone ); + Cudd_Ref( 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 = vFaninsOld->pArray[i]; + pFaninOld->pData = Cudd_bddIthVar( dd, i ); Cudd_Ref( 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 = vFaninsOld->pArray[i]; + Cudd_RecursiveDeref( dd, 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 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, Abc_ObjFaninC0(pNode) ); + bFunc1 = Cudd_NotCond( bFunc1, 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 /// +//////////////////////////////////////////////////////////////////////// + + |