abc70930: src/base/abci/abcMulti.c Source File

00001 
00021 #include "abc.h"
00022 
00026 
00027 static void        Abc_NtkMultiInt( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew );
00028 static Abc_Obj_t * Abc_NtkMulti_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld );
00029 
00030 static DdNode *    Abc_NtkMultiDeriveBdd_rec( DdManager * dd, Abc_Obj_t * pNodeOld, Vec_Ptr_t * vFanins );
00031 static DdNode *    Abc_NtkMultiDeriveBdd( DdManager * dd, Abc_Obj_t * pNodeOld, Vec_Ptr_t * vFaninsOld );
00032 
00033 static void        Abc_NtkMultiSetBounds( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax );
00034 static void        Abc_NtkMultiSetBoundsCnf( Abc_Ntk_t * pNtk );
00035 static void        Abc_NtkMultiSetBoundsMulti( Abc_Ntk_t * pNtk, int nThresh );
00036 static void        Abc_NtkMultiSetBoundsSimple( Abc_Ntk_t * pNtk );
00037 static void        Abc_NtkMultiSetBoundsFactor( Abc_Ntk_t * pNtk );
00038 static void        Abc_NtkMultiCone( Abc_Obj_t * pNode, Vec_Ptr_t * vCone );
00039 
00043 
00055 Abc_Ntk_t * Abc_NtkMulti( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax, int fCnf, int fMulti, int fSimple, int fFactor )
00056 {
00057     Abc_Ntk_t * pNtkNew;
00058 
00059     assert( Abc_NtkIsStrash(pNtk) );
00060     assert( nThresh >= 0 );
00061     assert( nFaninMax > 1 );
00062 
00063     // print a warning about choice nodes
00064     if ( Abc_NtkGetChoiceNum( pNtk ) )
00065         printf( "Warning: The choice nodes in the AIG are removed by renoding.\n" );
00066 
00067     // define the boundary
00068     if ( fCnf )
00069         Abc_NtkMultiSetBoundsCnf( pNtk );
00070     else if ( fMulti )
00071         Abc_NtkMultiSetBoundsMulti( pNtk, nThresh );
00072     else if ( fSimple )
00073         Abc_NtkMultiSetBoundsSimple( pNtk );
00074     else if ( fFactor )
00075         Abc_NtkMultiSetBoundsFactor( pNtk );
00076     else
00077         Abc_NtkMultiSetBounds( pNtk, nThresh, nFaninMax );
00078 
00079     // perform renoding for this boundary
00080     pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_BDD );
00081     Abc_NtkMultiInt( pNtk, pNtkNew );
00082     Abc_NtkFinalize( pNtk, pNtkNew );
00083 
00084     // make the network minimum base
00085     Abc_NtkMinimumBase( pNtkNew );
00086 
00087     // fix the problem with complemented and duplicated CO edges
00088     Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );
00089 
00090     // report the number of CNF objects
00091     if ( fCnf )
00092     {
00093 //        int nClauses = Abc_NtkGetClauseNum(pNtkNew) + 2*Abc_NtkPoNum(pNtkNew) + 2*Abc_NtkLatchNum(pNtkNew);
00094 //        printf( "CNF variables = %d. CNF clauses = %d.\n",  Abc_NtkNodeNum(pNtkNew), nClauses );
00095     }
00096 //printf( "Maximum fanin = %d.\n", Abc_NtkGetFaninMax(pNtkNew) );
00097 
00098     if ( pNtk->pExdc )
00099         pNtkNew->pExdc = Abc_NtkDup( pNtk->pExdc );
00100     // make sure everything is okay
00101     if ( !Abc_NtkCheck( pNtkNew ) )
00102     {
00103         printf( "Abc_NtkMulti: The network check has failed.\n" );
00104         Abc_NtkDelete( pNtkNew );
00105         return NULL;
00106     }
00107     return pNtkNew;
00108 }
00109 
00121 void Abc_NtkMultiInt( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew )
00122 {
00123     ProgressBar * pProgress;
00124     Abc_Obj_t * pNode, * pConst1, * pNodeNew;
00125     int i;
00126 
00127     // set the constant node
00128     pConst1 = Abc_AigConst1(pNtk);
00129     if ( Abc_ObjFanoutNum(pConst1) > 0 )
00130     {
00131         pNodeNew = Abc_NtkCreateNode( pNtkNew );  
00132         pNodeNew->pData = Cudd_ReadOne( pNtkNew->pManFunc );   Cudd_Ref( pNodeNew->pData );
00133         pConst1->pCopy = pNodeNew;
00134     }
00135 
00136     // perform renoding for POs
00137     pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
00138     Abc_NtkForEachCo( pNtk, pNode, i )
00139     {
00140         Extra_ProgressBarUpdate( pProgress, i, NULL );
00141         if ( Abc_ObjIsCi(Abc_ObjFanin0(pNode)) )
00142             continue;
00143         Abc_NtkMulti_rec( pNtkNew, Abc_ObjFanin0(pNode) );
00144     }
00145     Extra_ProgressBarStop( pProgress );
00146 
00147     // clean the boundaries and data field in the old network
00148     Abc_NtkForEachObj( pNtk, pNode, i )
00149     {
00150         pNode->fMarkA = 0;
00151         pNode->pData = NULL;
00152     }
00153 }
00154 
00166 Abc_Obj_t * Abc_NtkMulti_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld )
00167 {
00168     Vec_Ptr_t * vCone;
00169     Abc_Obj_t * pNodeNew;
00170     int i;
00171 
00172     assert( !Abc_ObjIsComplement(pNodeOld) );
00173     // return if the result if known
00174     if ( pNodeOld->pCopy )
00175         return pNodeOld->pCopy;
00176     assert( Abc_ObjIsNode(pNodeOld) );
00177     assert( !Abc_AigNodeIsConst(pNodeOld) );
00178     assert( pNodeOld->fMarkA );
00179 
00180 //printf( "%d ", Abc_NodeMffcSizeSupp(pNodeOld) );
00181 
00182     // collect the renoding cone
00183     vCone = Vec_PtrAlloc( 10 );
00184     Abc_NtkMultiCone( pNodeOld, vCone );
00185 
00186     // create a new node 
00187     pNodeNew = Abc_NtkCreateNode( pNtkNew ); 
00188     for ( i = 0; i < vCone->nSize; i++ )
00189         Abc_ObjAddFanin( pNodeNew, Abc_NtkMulti_rec(pNtkNew, vCone->pArray[i]) );
00190 
00191     // derive the function of this node
00192     pNodeNew->pData = Abc_NtkMultiDeriveBdd( pNtkNew->pManFunc, pNodeOld, vCone );    
00193     Cudd_Ref( pNodeNew->pData );
00194     Vec_PtrFree( vCone );
00195 
00196     // remember the node
00197     pNodeOld->pCopy = pNodeNew;
00198     return pNodeOld->pCopy;
00199 }
00200 
00201 
00213 DdNode * Abc_NtkMultiDeriveBdd( DdManager * dd, Abc_Obj_t * pNodeOld, Vec_Ptr_t * vFaninsOld )
00214 {
00215     Abc_Obj_t * pFaninOld;
00216     DdNode * bFunc;
00217     int i;
00218     assert( !Abc_AigNodeIsConst(pNodeOld) );
00219     assert( Abc_ObjIsNode(pNodeOld) );
00220     // set the elementary BDD variables for the input nodes
00221     for ( i = 0; i < vFaninsOld->nSize; i++ )
00222     {
00223         pFaninOld = vFaninsOld->pArray[i];
00224         pFaninOld->pData = Cudd_bddIthVar( dd, i );    Cudd_Ref( pFaninOld->pData );
00225         pFaninOld->fMarkC = 1;
00226     }
00227     // call the recursive BDD computation
00228     bFunc = Abc_NtkMultiDeriveBdd_rec( dd, pNodeOld, vFaninsOld );  Cudd_Ref( bFunc );
00229     // dereference the intermediate nodes
00230     for ( i = 0; i < vFaninsOld->nSize; i++ )
00231     {
00232         pFaninOld = vFaninsOld->pArray[i];
00233         Cudd_RecursiveDeref( dd, pFaninOld->pData );
00234         pFaninOld->fMarkC = 0;
00235     }
00236     Cudd_Deref( bFunc );
00237     return bFunc;
00238 }
00239 
00251 DdNode * Abc_NtkMultiDeriveBdd_rec( DdManager * dd, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins )
00252 {
00253     DdNode * bFunc, * bFunc0, * bFunc1;
00254     assert( !Abc_ObjIsComplement(pNode) );
00255     // if the result is available return
00256     if ( pNode->fMarkC )
00257     {
00258         assert( pNode->pData ); // network has a cycle
00259         return pNode->pData;
00260     }
00261     // mark the node as visited
00262     pNode->fMarkC = 1;
00263     Vec_PtrPush( vFanins, pNode );
00264     // compute the result for both branches
00265     bFunc0 = Abc_NtkMultiDeriveBdd_rec( dd, Abc_ObjFanin(pNode,0), vFanins ); Cudd_Ref( bFunc0 );
00266     bFunc1 = Abc_NtkMultiDeriveBdd_rec( dd, Abc_ObjFanin(pNode,1), vFanins ); Cudd_Ref( bFunc1 );
00267     bFunc0 = Cudd_NotCond( bFunc0, Abc_ObjFaninC0(pNode) );
00268     bFunc1 = Cudd_NotCond( bFunc1, Abc_ObjFaninC1(pNode) );
00269     // get the final result
00270     bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 );   Cudd_Ref( bFunc );
00271     Cudd_RecursiveDeref( dd, bFunc0 );
00272     Cudd_RecursiveDeref( dd, bFunc1 );
00273     // set the result
00274     pNode->pData = bFunc;
00275     assert( pNode->pData );
00276     return bFunc;
00277 }
00278 
00279 
00280 
00292 int Abc_NtkMultiLimit_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, int nFaninMax, int fCanStop, int fFirst )
00293 {
00294     int nNodes0, nNodes1;
00295     assert( !Abc_ObjIsComplement(pNode) );
00296     // check if the node should be added to the fanins
00297     if ( !fFirst && (pNode->fMarkA || !Abc_ObjIsNode(pNode)) )
00298     {
00299         Vec_PtrPushUnique( vCone, pNode );
00300         return 0;
00301     }
00302     // if we cannot stop in this branch, collect all nodes
00303     if ( !fCanStop )
00304     {
00305         Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,0), vCone, nFaninMax, 0, 0 );
00306         Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
00307         return 0;
00308     }
00309     // if we can stop, try the left branch first, and return if we stopped
00310     assert( vCone->nSize == 0 );
00311     if ( Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,0), vCone, nFaninMax, 1, 0 ) )
00312         return 1;
00313     // save the number of nodes in the left branch and call for the right branch
00314     nNodes0 = vCone->nSize;
00315     assert( nNodes0 <= nFaninMax );
00316     Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
00317     // check the number of nodes
00318     if ( vCone->nSize <= nFaninMax )
00319         return 0;
00320     // the number of nodes exceeds the limit
00321 
00322     // get the number of nodes in the right branch
00323     vCone->nSize = 0;
00324     Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 0, 0 );
00325     // if this number exceeds the limit, solve the problem for this branch
00326     if ( vCone->nSize > nFaninMax )
00327     {
00328         int RetValue;
00329         vCone->nSize = 0;
00330         RetValue = Abc_NtkMultiLimit_rec( Abc_ObjFanin(pNode,1), vCone, nFaninMax, 1, 0 );
00331         assert( RetValue == 1 );
00332         return 1;
00333     }
00334 
00335     nNodes1 = vCone->nSize; 
00336     assert( nNodes1 <= nFaninMax );
00337     if ( nNodes0 >= nNodes1 )
00338     { // the left branch is larger - cut it
00339         assert( Abc_ObjFanin(pNode,0)->fMarkA == 0 );
00340         Abc_ObjFanin(pNode,0)->fMarkA = 1;
00341     }
00342     else
00343     { // the right branch is larger - cut it
00344         assert( Abc_ObjFanin(pNode,1)->fMarkA == 0 );
00345         Abc_ObjFanin(pNode,1)->fMarkA = 1;
00346     }
00347     return 1;
00348 }
00349 
00361 int Abc_NtkMultiLimit( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, int nFaninMax )
00362 {
00363     vCone->nSize = 0;
00364     return Abc_NtkMultiLimit_rec( pNode, vCone, nFaninMax, 1, 1 );
00365 }
00366 
00379 void Abc_NtkMultiSetBounds( Abc_Ntk_t * pNtk, int nThresh, int nFaninMax )
00380 {
00381     Vec_Ptr_t * vCone = Vec_PtrAlloc(10);
00382     Abc_Obj_t * pNode;
00383     int i, nFanouts, nConeSize;
00384 
00385     // make sure the mark is not set
00386     Abc_NtkForEachObj( pNtk, pNode, i )
00387         assert( pNode->fMarkA == 0 );
00388 
00389     // mark the nodes where expansion stops using pNode->fMarkA
00390     Abc_NtkForEachNode( pNtk, pNode, i )
00391     {
00392         // skip PI/PO nodes
00393 //        if ( Abc_NodeIsConst(pNode) )
00394 //            continue;
00395         // mark the nodes with multiple fanouts
00396         nFanouts = Abc_ObjFanoutNum(pNode);
00397         nConeSize = Abc_NodeMffcSize(pNode);
00398         if ( (nFanouts - 1) * nConeSize > nThresh )
00399             pNode->fMarkA = 1;
00400     }
00401 
00402     // mark the PO drivers
00403     Abc_NtkForEachCo( pNtk, pNode, i )
00404         Abc_ObjFanin0(pNode)->fMarkA = 1;
00405 
00406     // make sure the fanin limit is met
00407     Abc_NtkForEachNode( pNtk, pNode, i )
00408     {
00409         // skip PI/PO nodes
00410 //        if ( Abc_NodeIsConst(pNode) )
00411 //            continue;
00412         if ( pNode->fMarkA == 0 )
00413             continue;
00414         // continue cutting branches until it meets the fanin limit
00415         while ( Abc_NtkMultiLimit(pNode, vCone, nFaninMax) );
00416         assert( vCone->nSize <= nFaninMax );  
00417     }
00418     Vec_PtrFree(vCone);
00419 /*
00420     // make sure the fanin limit is met
00421     Abc_NtkForEachNode( pNtk, pNode, i )
00422     {
00423         // skip PI/PO nodes
00424 //        if ( Abc_NodeIsConst(pNode) )
00425 //            continue;
00426         if ( pNode->fMarkA == 0 )
00427             continue;
00428         Abc_NtkMultiCone( pNode, vCone );
00429         assert( vCone->nSize <= nFaninMax );    
00430     }
00431 */
00432 }
00433 
00446 void Abc_NtkMultiSetBoundsCnf( Abc_Ntk_t * pNtk )
00447 {
00448     Abc_Obj_t * pNode;
00449     int i, nMuxes;
00450 
00451     // make sure the mark is not set
00452     Abc_NtkForEachObj( pNtk, pNode, i )
00453         assert( pNode->fMarkA == 0 );
00454 
00455     // mark the nodes where expansion stops using pNode->fMarkA
00456     Abc_NtkForEachNode( pNtk, pNode, i )
00457     {
00458         // skip PI/PO nodes
00459 //        if ( Abc_NodeIsConst(pNode) )
00460 //            continue;
00461         // mark the nodes with multiple fanouts
00462         if ( Abc_ObjFanoutNum(pNode) > 1 )
00463             pNode->fMarkA = 1;
00464         // mark the nodes that are roots of MUXes
00465         if ( Abc_NodeIsMuxType( pNode ) )
00466         {
00467             pNode->fMarkA = 1;
00468             Abc_ObjFanin0( Abc_ObjFanin0(pNode) )->fMarkA = 1;
00469             Abc_ObjFanin0( Abc_ObjFanin1(pNode) )->fMarkA = 1;
00470             Abc_ObjFanin1( Abc_ObjFanin0(pNode) )->fMarkA = 1;
00471             Abc_ObjFanin1( Abc_ObjFanin1(pNode) )->fMarkA = 1;
00472         }
00473         else  // mark the complemented edges
00474         {
00475             if ( Abc_ObjFaninC0(pNode) )
00476                 Abc_ObjFanin0(pNode)->fMarkA = 1;
00477             if ( Abc_ObjFaninC1(pNode) )
00478                 Abc_ObjFanin1(pNode)->fMarkA = 1;
00479         }
00480     }
00481 
00482     // mark the PO drivers
00483     Abc_NtkForEachCo( pNtk, pNode, i )
00484         Abc_ObjFanin0(pNode)->fMarkA = 1;
00485 
00486     // count the number of MUXes
00487     nMuxes = 0;
00488     Abc_NtkForEachNode( pNtk, pNode, i )
00489     {
00490         // skip PI/PO nodes
00491 //        if ( Abc_NodeIsConst(pNode) )
00492 //            continue;
00493         if ( Abc_NodeIsMuxType(pNode) && 
00494             Abc_ObjFanin0(pNode)->fMarkA == 0 &&
00495             Abc_ObjFanin1(pNode)->fMarkA == 0 )
00496             nMuxes++;
00497     }
00498 //    printf( "The number of MUXes detected = %d (%5.2f %% of logic).\n", nMuxes, 300.0*nMuxes/Abc_NtkNodeNum(pNtk) );
00499 } 
00500  
00512 void Abc_NtkMultiSetBoundsMulti( Abc_Ntk_t * pNtk, int nThresh )
00513 {
00514     Abc_Obj_t * pNode;
00515     int i, nFanouts, nConeSize;
00516 
00517     // make sure the mark is not set
00518     Abc_NtkForEachObj( pNtk, pNode, i )
00519         assert( pNode->fMarkA == 0 );
00520 
00521     // mark the nodes where expansion stops using pNode->fMarkA
00522     Abc_NtkForEachNode( pNtk, pNode, i )
00523     {
00524         // skip PI/PO nodes
00525 //        if ( Abc_NodeIsConst(pNode) )
00526 //            continue;
00527         // mark the nodes with multiple fanouts
00528 //        if ( Abc_ObjFanoutNum(pNode) > 1 )
00529 //            pNode->fMarkA = 1;
00530         // mark the nodes with multiple fanouts
00531         nFanouts = Abc_ObjFanoutNum(pNode);
00532         nConeSize = Abc_NodeMffcSizeStop(pNode);
00533         if ( (nFanouts - 1) * nConeSize > nThresh )
00534             pNode->fMarkA = 1;
00535         // mark the children if they are pointed by the complemented edges
00536         if ( Abc_ObjFaninC0(pNode) )
00537             Abc_ObjFanin0(pNode)->fMarkA = 1;
00538         if ( Abc_ObjFaninC1(pNode) )
00539             Abc_ObjFanin1(pNode)->fMarkA = 1;
00540     }
00541 
00542     // mark the PO drivers
00543     Abc_NtkForEachCo( pNtk, pNode, i )
00544         Abc_ObjFanin0(pNode)->fMarkA = 1;
00545 }
00546 
00558 void Abc_NtkMultiSetBoundsSimple( Abc_Ntk_t * pNtk )
00559 {
00560     Abc_Obj_t * pNode;
00561     int i;
00562     // make sure the mark is not set
00563     Abc_NtkForEachObj( pNtk, pNode, i )
00564         assert( pNode->fMarkA == 0 );
00565     // mark the nodes where expansion stops using pNode->fMarkA
00566     Abc_NtkForEachNode( pNtk, pNode, i )
00567         pNode->fMarkA = 1;
00568 }
00569 
00581 void Abc_NtkMultiSetBoundsFactor( Abc_Ntk_t * pNtk )
00582 {
00583     Abc_Obj_t * pNode;
00584     int i;
00585     // make sure the mark is not set
00586     Abc_NtkForEachObj( pNtk, pNode, i )
00587         assert( pNode->fMarkA == 0 );
00588     // mark the nodes where expansion stops using pNode->fMarkA
00589     Abc_NtkForEachNode( pNtk, pNode, i )
00590         pNode->fMarkA = (pNode->vFanouts.nSize > 1 && !Abc_NodeIsMuxControlType(pNode));
00591     // mark the PO drivers
00592     Abc_NtkForEachCo( pNtk, pNode, i )
00593         Abc_ObjFanin0(pNode)->fMarkA = 1;
00594 }
00595 
00607 void Abc_NtkMultiCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone )
00608 {
00609     assert( !Abc_ObjIsComplement(pNode) );
00610     if ( pNode->fMarkA || !Abc_ObjIsNode(pNode) )
00611     {
00612         Vec_PtrPushUnique( vCone, pNode );
00613         return;
00614     }
00615     Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,0), vCone );
00616     Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,1), vCone );
00617 }
00618 
00630 void Abc_NtkMultiCone( Abc_Obj_t * pNode, Vec_Ptr_t * vCone )
00631 {
00632     assert( !Abc_ObjIsComplement(pNode) );
00633     assert( Abc_ObjIsNode(pNode) );
00634     vCone->nSize = 0;
00635     Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,0), vCone );
00636     Abc_NtkMultiCone_rec( Abc_ObjFanin(pNode,1), vCone );
00637 }
00638 
00642 
00643