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

00001 
00021 #include "abc.h"
00022 #include "cut.h"
00023 
00027 
00028 static void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq );
00029 static void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq );
00030 
00031 extern int nTotal, nGood, nEqual;
00032 
00033 static Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk );
00034 static int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p );
00035 
00039 
00051 Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams )
00052 {
00053     ProgressBar * pProgress;
00054     Cut_Man_t *  p;
00055     Abc_Obj_t * pObj, * pNode;
00056     Vec_Ptr_t * vNodes;
00057     Vec_Int_t * vChoices;
00058     int i;
00059     int clk = clock();
00060 
00061     extern void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk );
00062     extern void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk );
00063 
00064     nTotal = nGood = nEqual = 0;
00065 
00066     assert( Abc_NtkIsStrash(pNtk) );
00067     // start the manager
00068     pParams->nIdsMax = Abc_NtkObjNumMax( pNtk );
00069     p = Cut_ManStart( pParams );
00070     // compute node attributes if local or global cuts are requested
00071     if ( pParams->fGlobal || pParams->fLocal )
00072     {
00073         extern Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk );
00074         Cut_ManSetNodeAttrs( p, Abc_NtkGetNodeAttributes(pNtk) );
00075     }
00076     // prepare for cut dropping
00077     if ( pParams->fDrop )
00078         Cut_ManSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) );
00079     // set cuts for PIs
00080     Abc_NtkForEachCi( pNtk, pObj, i )
00081         if ( Abc_ObjFanoutNum(pObj) > 0 )
00082             Cut_NodeSetTriv( p, pObj->Id );
00083     // compute cuts for internal nodes
00084     vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs
00085     vChoices = Vec_IntAlloc( 100 );
00086     pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vNodes) );
00087     Vec_PtrForEachEntry( vNodes, pObj, i )
00088     {
00089         // when we reached a CO, it is time to deallocate the cuts
00090         if ( Abc_ObjIsCo(pObj) )
00091         {
00092             if ( pParams->fDrop )
00093                 Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) );
00094             continue;
00095         }
00096         // skip constant node, it has no cuts
00097 //        if ( Abc_NodeIsConst(pObj) )
00098 //            continue;
00099         Extra_ProgressBarUpdate( pProgress, i, NULL );
00100         // compute the cuts to the internal node
00101         Abc_NodeGetCuts( p, pObj, pParams->fDag, pParams->fTree );  
00102         // consider dropping the fanins cuts
00103         if ( pParams->fDrop )
00104         {
00105             Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) );
00106             Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId1(pObj) );
00107         }
00108         // add cuts due to choices
00109         if ( Abc_AigNodeIsChoice(pObj) )
00110         {
00111             Vec_IntClear( vChoices );
00112             for ( pNode = pObj; pNode; pNode = pNode->pData )
00113                 Vec_IntPush( vChoices, pNode->Id );
00114             Cut_NodeUnionCuts( p, vChoices );
00115         }
00116     }
00117     Extra_ProgressBarStop( pProgress );
00118     Vec_PtrFree( vNodes );
00119     Vec_IntFree( vChoices );
00120     Cut_ManPrintStats( p );
00121 PRT( "TOTAL ", clock() - clk );
00122     printf( "Area = %d.\n", Abc_NtkComputeArea( pNtk, p ) );
00123 //Abc_NtkPrintCuts( p, pNtk, 0 );
00124 //    Cut_ManPrintStatsToFile( p, pNtk->pSpec, clock() - clk );
00125 
00126     // temporary printout of stats
00127     if ( nTotal )
00128     printf( "Total cuts = %d. Good cuts = %d.  Ratio = %5.2f\n", nTotal, nGood, ((double)nGood)/nTotal );
00129     return p;
00130 }
00131 
00143 void Abc_NtkCutsOracle( Abc_Ntk_t * pNtk, Cut_Oracle_t * p )
00144 {
00145     Abc_Obj_t * pObj;
00146     Vec_Ptr_t * vNodes;
00147     int i, clk = clock();
00148     int fDrop = Cut_OracleReadDrop(p);
00149 
00150     assert( Abc_NtkIsStrash(pNtk) );
00151 
00152     // prepare cut droppping
00153     if ( fDrop )
00154         Cut_OracleSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) );
00155 
00156     // set cuts for PIs
00157     Abc_NtkForEachCi( pNtk, pObj, i )
00158         if ( Abc_ObjFanoutNum(pObj) > 0 )
00159             Cut_OracleNodeSetTriv( p, pObj->Id );
00160 
00161     // compute cuts for internal nodes
00162     vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs
00163     Vec_PtrForEachEntry( vNodes, pObj, i )
00164     {
00165         // when we reached a CO, it is time to deallocate the cuts
00166         if ( Abc_ObjIsCo(pObj) )
00167         {
00168             if ( fDrop )
00169                 Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) );
00170             continue;
00171         }
00172         // skip constant node, it has no cuts
00173 //        if ( Abc_NodeIsConst(pObj) )
00174 //            continue;
00175         // compute the cuts to the internal node
00176         Cut_OracleComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj),  
00177                 Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) );
00178         // consider dropping the fanins cuts
00179         if ( fDrop )
00180         {
00181             Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) );
00182             Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId1(pObj) );
00183         }
00184     }
00185     Vec_PtrFree( vNodes );
00186 //PRT( "Total", clock() - clk );
00187 //Abc_NtkPrintCuts_( p, pNtk, 0 );
00188 }
00189 
00190 
00202 Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams )
00203 {
00204 /*
00205     Cut_Man_t *  p;
00206     Abc_Obj_t * pObj, * pNode;
00207     int i, nIters, fStatus;
00208     Vec_Int_t * vChoices;
00209     int clk = clock();
00210 
00211     assert( Abc_NtkIsSeq(pNtk) );
00212     assert( pParams->fSeq );
00213 //    assert( Abc_NtkIsDfsOrdered(pNtk) );
00214 
00215     // start the manager
00216     pParams->nIdsMax = Abc_NtkObjNumMax( pNtk );
00217     pParams->nCutSet = Abc_NtkCutSetNodeNum( pNtk );
00218     p = Cut_ManStart( pParams );
00219 
00220     // set cuts for the constant node and the PIs
00221     pObj = Abc_AigConst1(pNtk);
00222     if ( Abc_ObjFanoutNum(pObj) > 0 )
00223         Cut_NodeSetTriv( p, pObj->Id );
00224     Abc_NtkForEachPi( pNtk, pObj, i )
00225     {
00226 //printf( "Setting trivial cut %d.\n", pObj->Id );
00227         Cut_NodeSetTriv( p, pObj->Id );
00228     }
00229     // label the cutset nodes and set their number in the array
00230     // assign the elementary cuts to the cutset nodes
00231     Abc_SeqForEachCutsetNode( pNtk, pObj, i )
00232     {
00233         assert( pObj->fMarkC == 0 );
00234         pObj->fMarkC = 1;
00235         pObj->pCopy = (Abc_Obj_t *)i;
00236         Cut_NodeSetTriv( p, pObj->Id );
00237 //printf( "Setting trivial cut %d.\n", pObj->Id );
00238     }
00239 
00240     // process the nodes
00241     vChoices = Vec_IntAlloc( 100 );
00242     for ( nIters = 0; nIters < 10; nIters++ )
00243     {
00244 //printf( "ITERATION %d:\n", nIters );
00245         // compute the cuts for the internal nodes
00246         Abc_AigForEachAnd( pNtk, pObj, i )
00247         {
00248             Abc_NodeGetCutsSeq( p, pObj, nIters==0 );
00249             // add cuts due to choices
00250             if ( Abc_AigNodeIsChoice(pObj) )
00251             {
00252                 Vec_IntClear( vChoices );
00253                 for ( pNode = pObj; pNode; pNode = pNode->pData )
00254                     Vec_IntPush( vChoices, pNode->Id );
00255                 Cut_NodeUnionCutsSeq( p, vChoices, (pObj->fMarkC ? (int)pObj->pCopy : -1), nIters==0 );
00256             }
00257         }
00258         // merge the new cuts with the old cuts
00259         Abc_NtkForEachPi( pNtk, pObj, i )
00260             Cut_NodeNewMergeWithOld( p, pObj->Id );
00261         Abc_AigForEachAnd( pNtk, pObj, i )
00262             Cut_NodeNewMergeWithOld( p, pObj->Id );
00263         // for the cutset, transfer temp cuts to new cuts
00264         fStatus = 0;
00265         Abc_SeqForEachCutsetNode( pNtk, pObj, i )
00266             fStatus |= Cut_NodeTempTransferToNew( p, pObj->Id, i );
00267         if ( fStatus == 0 )
00268             break;
00269     }
00270     Vec_IntFree( vChoices );
00271 
00272     // if the status is not finished, transfer new to old for the cutset
00273     Abc_SeqForEachCutsetNode( pNtk, pObj, i )
00274         Cut_NodeNewMergeWithOld( p, pObj->Id );
00275 
00276     // transfer the old cuts to the new positions
00277     Abc_NtkForEachObj( pNtk, pObj, i )
00278         Cut_NodeOldTransferToNew( p, pObj->Id );
00279 
00280     // unlabel the cutset nodes
00281     Abc_SeqForEachCutsetNode( pNtk, pObj, i )
00282         pObj->fMarkC = 0;
00283 if ( pParams->fVerbose )
00284 {
00285     Cut_ManPrintStats( p );
00286 PRT( "TOTAL ", clock() - clk );
00287 printf( "Converged after %d iterations.\n", nIters );
00288 }
00289 //Abc_NtkPrintCuts( p, pNtk, 1 );
00290     return p;
00291 */
00292     return NULL;
00293 }
00294 
00306 int Abc_NtkComputeArea( Abc_Ntk_t * pNtk, Cut_Man_t * p )
00307 {
00308     Abc_Obj_t * pObj;
00309     int Counter, i;
00310     Counter = 0;
00311     Abc_NtkForEachCo( pNtk, pObj, i )
00312         Counter += Cut_ManMappingArea_rec( p, Abc_ObjFaninId0(pObj) );
00313     return Counter;
00314 }
00315 
00327 void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj, int fDag, int fTree )
00328 {
00329     void * pList;
00330     if ( pList = Abc_NodeReadCuts( p, pObj ) )
00331         return pList;
00332     Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj), fDag, fTree );
00333     Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj), fDag, fTree );
00334     return Abc_NodeGetCuts( p, pObj, fDag, fTree );
00335 }
00336 
00348 void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj, int fDag, int fTree )
00349 {
00350     Abc_Obj_t * pFanin;
00351     int fDagNode, fTriv, TreeCode = 0;
00352 //    assert( Abc_NtkIsStrash(pObj->pNtk) );
00353     assert( Abc_ObjFaninNum(pObj) == 2 );
00354 
00355 
00356     // check if the node is a DAG node
00357     fDagNode = (Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj));
00358     // increment the counter of DAG nodes
00359     if ( fDagNode ) Cut_ManIncrementDagNodes( p );
00360     // add the trivial cut if the node is a DAG node, or if we compute all cuts
00361     fTriv = fDagNode || !fDag;
00362     // check if fanins are DAG nodes
00363     if ( fTree )
00364     {
00365         pFanin = Abc_ObjFanin0(pObj);
00366         TreeCode |=  (Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin));
00367         pFanin = Abc_ObjFanin1(pObj);
00368         TreeCode |= ((Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)) << 1);
00369     }
00370 
00371 
00372     // changes due to the global/local cut computation
00373     {
00374         Cut_Params_t * pParams = Cut_ManReadParams(p);
00375         if ( pParams->fLocal )
00376         {
00377             Vec_Int_t * vNodeAttrs = Cut_ManReadNodeAttrs(p);
00378             fDagNode = Vec_IntEntry( vNodeAttrs, pObj->Id );
00379             if ( fDagNode ) Cut_ManIncrementDagNodes( p );
00380 //            fTriv = fDagNode || !pParams->fGlobal;
00381             fTriv = !Vec_IntEntry( vNodeAttrs, pObj->Id );
00382             TreeCode = 0;
00383             pFanin = Abc_ObjFanin0(pObj);
00384             TreeCode |=  Vec_IntEntry( vNodeAttrs, pFanin->Id );
00385             pFanin = Abc_ObjFanin1(pObj);
00386             TreeCode |= (Vec_IntEntry( vNodeAttrs, pFanin->Id ) << 1);
00387         }
00388     }
00389     return Cut_NodeComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj),  
00390         Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), fTriv, TreeCode );  
00391 }
00392 
00404 void Abc_NodeGetCutsSeq( void * p, Abc_Obj_t * pObj, int fTriv )
00405 {
00406 /*
00407     int CutSetNum;
00408     assert( Abc_NtkIsSeq(pObj->pNtk) );
00409     assert( Abc_ObjFaninNum(pObj) == 2 );
00410     fTriv     = pObj->fMarkC ? 0 : fTriv;
00411     CutSetNum = pObj->fMarkC ? (int)pObj->pCopy : -1;
00412     Cut_NodeComputeCutsSeq( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj),  
00413         Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), Seq_ObjFaninL0(pObj), Seq_ObjFaninL1(pObj), fTriv, CutSetNum );  
00414 */
00415 }
00416 
00428 void * Abc_NodeReadCuts( void * p, Abc_Obj_t * pObj )
00429 {
00430     return Cut_NodeReadCutsNew( p, pObj->Id );  
00431 }
00432 
00444 void Abc_NodeFreeCuts( void * p, Abc_Obj_t * pObj )
00445 {
00446     Cut_NodeFreeCuts( p, pObj->Id );
00447 }
00448 
00460 void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq )
00461 {
00462     Cut_Man_t * pMan = p;
00463     Cut_Cut_t * pList;
00464     Abc_Obj_t * pObj;
00465     int i;
00466     printf( "Cuts of the network:\n" );
00467     Abc_NtkForEachObj( pNtk, pObj, i )
00468     {
00469         pList = Abc_NodeReadCuts( p, pObj );
00470         printf( "Node %s:\n", Abc_ObjName(pObj) );
00471         Cut_CutPrintList( pList, fSeq );
00472     }
00473 }
00474 
00486 void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq )
00487 {
00488     Cut_Man_t * pMan = p;
00489     Cut_Cut_t * pList;
00490     Abc_Obj_t * pObj;
00491     pObj = Abc_NtkObj( pNtk, 2 * Abc_NtkObjNum(pNtk) / 3 );
00492     pList = Abc_NodeReadCuts( p, pObj );
00493     printf( "Node %s:\n", Abc_ObjName(pObj) );
00494     Cut_CutPrintList( pList, fSeq );
00495 }
00496 
00497 
00498 
00499 
00511 Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ) 
00512 {
00513     Vec_Int_t * vAttrs;
00514 //    Vec_Ptr_t * vNodes;
00515     Abc_Obj_t * pObj;//, * pTemp;
00516     int i;//, k;
00517     int nNodesTotal = 0, nMffcsTotal = 0;
00518     extern Vec_Ptr_t * Abc_NodeMffsInsideCollect( Abc_Obj_t * pNode );
00519 
00520     vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
00521 //    Abc_NtkForEachCi( pNtk, pObj, i )
00522 //        Vec_IntWriteEntry( vAttrs, pObj->Id, 1 );
00523 
00524     Abc_NtkForEachObj( pNtk, pObj, i )
00525     {
00526         if ( Abc_ObjIsNode(pObj) )
00527             nNodesTotal++;
00528         if ( Abc_ObjIsCo(pObj) && Abc_ObjIsNode(Abc_ObjFanin0(pObj)) )
00529             nMffcsTotal += Abc_NodeMffcSize( Abc_ObjFanin0(pObj) );
00530 //        if ( Abc_ObjIsNode(pObj) && (rand() % 4 == 0) )
00531 //        if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) && (rand() % 3 == 0) )
00532         if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) )
00533         {
00534             int nMffc = Abc_NodeMffcSize(pObj);
00535             nMffcsTotal += Abc_NodeMffcSize(pObj);
00536 //            printf( "%d ", nMffc );
00537 
00538             if ( nMffc > 2 || Abc_ObjFanoutNum(pObj) > 8 )
00539                 Vec_IntWriteEntry( vAttrs, pObj->Id, 1 );
00540         }
00541     }
00542 /*
00543     Abc_NtkForEachObj( pNtk, pObj, i )
00544     {
00545         if ( Vec_IntEntry( vAttrs, pObj->Id ) )
00546         {
00547             vNodes = Abc_NodeMffsInsideCollect( pObj );
00548             Vec_PtrForEachEntry( vNodes, pTemp, k )
00549                 if ( pTemp != pObj )
00550                     Vec_IntWriteEntry( vAttrs, pTemp->Id, 0 );
00551             Vec_PtrFree( vNodes );
00552         }
00553     }
00554 */
00555     printf( "Total nodes = %d. Total MFFC nodes = %d.\n", nNodesTotal, nMffcsTotal );
00556     return vAttrs; 
00557 }
00558 
00570 int Abc_NtkSubDagSize_rec( Abc_Obj_t * pObj, Vec_Int_t * vAttrs ) 
00571 {
00572     if ( Abc_NodeIsTravIdCurrent(pObj) )
00573         return 0;
00574     Abc_NodeSetTravIdCurrent(pObj);
00575     if ( Vec_IntEntry( vAttrs, pObj->Id ) )
00576         return 0;
00577     if ( Abc_ObjIsCi(pObj) )
00578         return 1;
00579     assert( Abc_ObjFaninNum(pObj) == 2 );
00580     return 1 + Abc_NtkSubDagSize_rec(Abc_ObjFanin0(pObj), vAttrs) +
00581         Abc_NtkSubDagSize_rec(Abc_ObjFanin1(pObj), vAttrs);
00582 }
00583 
00595 Vec_Int_t * Abc_NtkGetNodeAttributes2( Abc_Ntk_t * pNtk ) 
00596 {
00597     Vec_Int_t * vAttrs;
00598     Abc_Obj_t * pObj;
00599     int i, nSize;
00600     assert( Abc_NtkIsDfsOrdered(pNtk) );
00601     vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 );
00602     Abc_NtkForEachObj( pNtk, pObj, i )
00603     {
00604         // skip no-nodes and nodes without fanouts
00605         if ( pObj->Id == 0 || !(Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)) )
00606             continue;
00607         // the node has more than one fanout - count its sub-DAG size
00608         Abc_NtkIncrementTravId( pNtk );
00609         nSize = Abc_NtkSubDagSize_rec( pObj, vAttrs );
00610         if ( nSize > 15 )
00611             Vec_IntWriteEntry( vAttrs, pObj->Id, 1 );
00612     }
00613     return vAttrs; 
00614 }
00615 
00619 
00620