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

00001 
00021 #include "abc.h"
00022 #include "extra.h"
00023 #include "dec.h"
00024 
00028 
00029 static void Abc_NtkStrashPerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkNew, int fAllNodes, int fRecord );
00030 
00034 
00047 Abc_Ntk_t * Abc_NtkRestrash( Abc_Ntk_t * pNtk, bool fCleanup )
00048 {
00049     extern int timeRetime;
00050     Abc_Ntk_t * pNtkAig;
00051     Abc_Obj_t * pObj;
00052     int i, nNodes;//, RetValue;
00053     assert( Abc_NtkIsStrash(pNtk) );
00054 //timeRetime = clock();
00055     // print warning about choice nodes
00056     if ( Abc_NtkGetChoiceNum( pNtk ) )
00057         printf( "Warning: The choice nodes in the original AIG are removed by strashing.\n" );
00058     // start the new network (constants and CIs of the old network will point to the their counterparts in the new network)
00059     pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
00060     // restrash the nodes (assuming a topological order of the old network)
00061     Abc_NtkForEachNode( pNtk, pObj, i )
00062         pObj->pCopy = Abc_AigAnd( pNtkAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
00063     // finalize the network
00064     Abc_NtkFinalize( pNtk, pNtkAig );
00065     // print warning about self-feed latches
00066 //    if ( Abc_NtkCountSelfFeedLatches(pNtkAig) )
00067 //        printf( "Warning: The network has %d self-feeding latches.\n", Abc_NtkCountSelfFeedLatches(pNtkAig) );
00068     // perform cleanup if requested
00069     if ( fCleanup && (nNodes = Abc_AigCleanup(pNtkAig->pManFunc)) ) 
00070         printf( "Abc_NtkRestrash(): AIG cleanup removed %d nodes (this is a bug).\n", nNodes );
00071     // duplicate EXDC 
00072     if ( pNtk->pExdc )
00073         pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
00074     // make sure everything is okay
00075     if ( !Abc_NtkCheck( pNtkAig ) )
00076     {
00077         printf( "Abc_NtkStrash: The network check has failed.\n" );
00078         Abc_NtkDelete( pNtkAig );
00079         return NULL;
00080     }
00081 //timeRetime = clock() - timeRetime;
00082 //    if ( RetValue = Abc_NtkRemoveSelfFeedLatches(pNtkAig) )
00083 //        printf( "Modified %d self-feeding latches. The result may not verify.\n", RetValue );
00084     return pNtkAig;
00085 
00086 }
00087 
00100 Abc_Ntk_t * Abc_NtkRestrashZero( Abc_Ntk_t * pNtk, bool fCleanup )
00101 {
00102     extern int timeRetime;
00103     Abc_Ntk_t * pNtkAig;
00104     Abc_Obj_t * pObj;
00105     int i, nNodes;//, RetValue;
00106     assert( Abc_NtkIsStrash(pNtk) );
00107 //timeRetime = clock();
00108     // print warning about choice nodes
00109     if ( Abc_NtkGetChoiceNum( pNtk ) )
00110         printf( "Warning: The choice nodes in the original AIG are removed by strashing.\n" );
00111     // start the new network (constants and CIs of the old network will point to the their counterparts in the new network)
00112     pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
00113     // complement the 1-values registers
00114     Abc_NtkForEachLatch( pNtk, pObj, i )
00115         if ( Abc_LatchIsInit1(pObj) )
00116             Abc_ObjFanout0(pObj)->pCopy = Abc_ObjNot(Abc_ObjFanout0(pObj)->pCopy);
00117     // restrash the nodes (assuming a topological order of the old network)
00118     Abc_NtkForEachNode( pNtk, pObj, i )
00119         pObj->pCopy = Abc_AigAnd( pNtkAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
00120     // finalize the network
00121     Abc_NtkFinalize( pNtk, pNtkAig );
00122     // complement the 1-valued registers
00123     Abc_NtkForEachLatch( pNtkAig, pObj, i )
00124         if ( Abc_LatchIsInit1(pObj) )
00125             Abc_ObjXorFaninC( Abc_ObjFanin0(pObj), 0 );
00126     // set all constant-0 values
00127     Abc_NtkForEachLatch( pNtkAig, pObj, i )
00128         Abc_LatchSetInit0( pObj );
00129 
00130     // print warning about self-feed latches
00131 //    if ( Abc_NtkCountSelfFeedLatches(pNtkAig) )
00132 //        printf( "Warning: The network has %d self-feeding latches.\n", Abc_NtkCountSelfFeedLatches(pNtkAig) );
00133     // perform cleanup if requested
00134     if ( fCleanup && (nNodes = Abc_AigCleanup(pNtkAig->pManFunc)) ) 
00135         printf( "Abc_NtkRestrash(): AIG cleanup removed %d nodes (this is a bug).\n", nNodes );
00136     // duplicate EXDC 
00137     if ( pNtk->pExdc )
00138         pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
00139     // make sure everything is okay
00140     if ( !Abc_NtkCheck( pNtkAig ) )
00141     {
00142         printf( "Abc_NtkStrash: The network check has failed.\n" );
00143         Abc_NtkDelete( pNtkAig );
00144         return NULL;
00145     }
00146 //timeRetime = clock() - timeRetime;
00147 //    if ( RetValue = Abc_NtkRemoveSelfFeedLatches(pNtkAig) )
00148 //        printf( "Modified %d self-feeding latches. The result may not verify.\n", RetValue );
00149     return pNtkAig;
00150 
00151 }
00152 
00164 Abc_Ntk_t * Abc_NtkStrash( Abc_Ntk_t * pNtk, int fAllNodes, int fCleanup, int fRecord )
00165 {
00166     Abc_Ntk_t * pNtkAig;
00167     int nNodes;
00168     assert( Abc_NtkIsLogic(pNtk) || Abc_NtkIsStrash(pNtk) );
00169     // consider the special case when the network is already structurally hashed
00170     if ( Abc_NtkIsStrash(pNtk) )
00171         return Abc_NtkRestrash( pNtk, fCleanup );
00172     // convert the node representation in the logic network to the AIG form
00173     if ( !Abc_NtkToAig(pNtk) )
00174     {
00175         printf( "Converting to AIGs has failed.\n" );
00176         return NULL;
00177     }
00178     // perform strashing
00179 //    Abc_NtkCleanCopy( pNtk );
00180     pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
00181     Abc_NtkStrashPerform( pNtk, pNtkAig, fAllNodes, fRecord );
00182     Abc_NtkFinalize( pNtk, pNtkAig );
00183     // print warning about self-feed latches
00184 //    if ( Abc_NtkCountSelfFeedLatches(pNtkAig) )
00185 //        printf( "Warning: The network has %d self-feeding latches.\n", Abc_NtkCountSelfFeedLatches(pNtkAig) );
00186     // perform cleanup if requested
00187     nNodes = fCleanup? Abc_AigCleanup(pNtkAig->pManFunc) : 0;
00188 //    if ( nNodes )
00189 //        printf( "Warning: AIG cleanup removed %d nodes (this is not a bug).\n", nNodes );
00190     // duplicate EXDC 
00191     if ( pNtk->pExdc )
00192         pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
00193     // make sure everything is okay
00194     if ( !Abc_NtkCheck( pNtkAig ) )
00195     {
00196         printf( "Abc_NtkStrash: The network check has failed.\n" );
00197         Abc_NtkDelete( pNtkAig );
00198         return NULL;
00199     }
00200     return pNtkAig;
00201 }
00202 
00216 int Abc_NtkAppend( Abc_Ntk_t * pNtk1, Abc_Ntk_t * pNtk2, int fAddPos )
00217 {
00218     Abc_Obj_t * pObj;
00219     char * pName;
00220     int i, nNewCis;
00221     // the first network should be an AIG
00222     assert( Abc_NtkIsStrash(pNtk1) );
00223     assert( Abc_NtkIsLogic(pNtk2) || Abc_NtkIsStrash(pNtk2) ); 
00224     if ( Abc_NtkIsLogic(pNtk2) && !Abc_NtkToAig(pNtk2) )
00225     {
00226         printf( "Converting to AIGs has failed.\n" );
00227         return 0;
00228     }
00229     // check that the networks have the same PIs
00230     // reorder PIs of pNtk2 according to pNtk1
00231     if ( !Abc_NtkCompareSignals( pNtk1, pNtk2, 1, 1 ) )
00232         printf( "Abc_NtkAppend(): The union of the network PIs is computed (warning).\n" );
00233     // perform strashing
00234     nNewCis = 0;
00235     Abc_NtkCleanCopy( pNtk2 );
00236     if ( Abc_NtkIsStrash(pNtk2) )
00237         Abc_AigConst1(pNtk2)->pCopy = Abc_AigConst1(pNtk1);
00238     Abc_NtkForEachCi( pNtk2, pObj, i )
00239     {
00240         pName = Abc_ObjName(pObj);
00241         pObj->pCopy = Abc_NtkFindCi(pNtk1, Abc_ObjName(pObj));
00242         if ( pObj->pCopy == NULL )
00243         {
00244             pObj->pCopy = Abc_NtkDupObj(pNtk1, pObj, 1);
00245             nNewCis++;
00246         }
00247     }
00248     if ( nNewCis )
00249         printf( "Warning: Procedure Abc_NtkAppend() added %d new CIs.\n", nNewCis );
00250     // add pNtk2 to pNtk1 while strashing
00251     if ( Abc_NtkIsLogic(pNtk2) )
00252         Abc_NtkStrashPerform( pNtk2, pNtk1, 1, 0 );
00253     else
00254         Abc_NtkForEachNode( pNtk2, pObj, i )
00255             pObj->pCopy = Abc_AigAnd( pNtk1->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
00256     // add the COs of the second network
00257     if ( fAddPos )
00258     {
00259         Abc_NtkForEachPo( pNtk2, pObj, i )
00260         {
00261             Abc_NtkDupObj( pNtk1, pObj, 0 );
00262             Abc_ObjAddFanin( pObj->pCopy, Abc_ObjChild0Copy(pObj) );
00263             Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj->pCopy), NULL );
00264         }
00265     }
00266     else
00267     {
00268         Abc_Obj_t * pObjOld, * pDriverOld, * pDriverNew;
00269         int fCompl, iNodeId;
00270         // OR the choices
00271         Abc_NtkForEachCo( pNtk2, pObj, i )
00272         {
00273             iNodeId = Nm_ManFindIdByNameTwoTypes( pNtk1->pManName, Abc_ObjName(pObj), ABC_OBJ_PO, ABC_OBJ_BI );
00274             assert( iNodeId >= 0 );
00275             pObjOld = Abc_NtkObj( pNtk1, iNodeId );
00276             // derive the new driver
00277             pDriverOld = Abc_ObjChild0( pObjOld );
00278             pDriverNew = Abc_ObjChild0Copy( pObj );
00279             pDriverNew = Abc_AigOr( pNtk1->pManFunc, pDriverOld, pDriverNew );
00280             if ( Abc_ObjRegular(pDriverOld) == Abc_ObjRegular(pDriverNew) )
00281                 continue;
00282             // replace the old driver by the new driver
00283             fCompl = Abc_ObjRegular(pDriverOld)->fPhase ^ Abc_ObjRegular(pDriverNew)->fPhase;
00284             Abc_ObjPatchFanin( pObjOld, Abc_ObjRegular(pDriverOld), Abc_ObjNotCond(Abc_ObjRegular(pDriverNew), fCompl) );
00285         }
00286     }
00287     // make sure that everything is okay
00288     if ( !Abc_NtkCheck( pNtk1 ) )
00289     {
00290         printf( "Abc_NtkAppend: The network check has failed.\n" );
00291         return 0;
00292     }
00293     return 1;
00294 }
00295 
00307 void Abc_NtkStrashPerform( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew, int fAllNodes, int fRecord )
00308 {
00309     ProgressBar * pProgress;
00310     Vec_Ptr_t * vNodes;
00311     Abc_Obj_t * pNodeOld;
00312     int i, clk = clock();
00313     assert( Abc_NtkIsLogic(pNtkOld) );
00314     assert( Abc_NtkIsStrash(pNtkNew) );
00315 //    vNodes = Abc_NtkDfs( pNtkOld, fAllNodes );
00316     vNodes = Abc_NtkDfsIter( pNtkOld, fAllNodes );
00317 //printf( "Nodes = %d. ", Vec_PtrSize(vNodes) );
00318 //PRT( "Time", clock() - clk );
00319     pProgress = Extra_ProgressBarStart( stdout, vNodes->nSize );
00320     Vec_PtrForEachEntry( vNodes, pNodeOld, i )
00321     {
00322         Extra_ProgressBarUpdate( pProgress, i, NULL );
00323         pNodeOld->pCopy = Abc_NodeStrash( pNtkNew, pNodeOld, fRecord );
00324     }
00325     Extra_ProgressBarStop( pProgress );
00326     Vec_PtrFree( vNodes );
00327 }
00328 
00340 void Abc_NodeStrash_rec( Abc_Aig_t * pMan, Hop_Obj_t * pObj )
00341 {
00342     assert( !Hop_IsComplement(pObj) );
00343     if ( !Hop_ObjIsNode(pObj) || Hop_ObjIsMarkA(pObj) )
00344         return;
00345     Abc_NodeStrash_rec( pMan, Hop_ObjFanin0(pObj) ); 
00346     Abc_NodeStrash_rec( pMan, Hop_ObjFanin1(pObj) );
00347     pObj->pData = Abc_AigAnd( pMan, (Abc_Obj_t *)Hop_ObjChild0Copy(pObj), (Abc_Obj_t *)Hop_ObjChild1Copy(pObj) );
00348     assert( !Hop_ObjIsMarkA(pObj) ); // loop detection
00349     Hop_ObjSetMarkA( pObj );
00350 }
00351 
00363 Abc_Obj_t * Abc_NodeStrash( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, int fRecord )
00364 {
00365     Hop_Man_t * pMan;
00366     Hop_Obj_t * pRoot;
00367     Abc_Obj_t * pFanin;
00368     int i;
00369     assert( Abc_ObjIsNode(pNodeOld) );
00370     assert( Abc_NtkHasAig(pNodeOld->pNtk) && !Abc_NtkIsStrash(pNodeOld->pNtk) );
00371     // get the local AIG manager and the local root node
00372     pMan = pNodeOld->pNtk->pManFunc;
00373     pRoot = pNodeOld->pData;
00374     // check the constant case
00375     if ( Abc_NodeIsConst(pNodeOld) || Hop_Regular(pRoot) == Hop_ManConst1(pMan) )
00376         return Abc_ObjNotCond( Abc_AigConst1(pNtkNew), Hop_IsComplement(pRoot) );
00377     // perform special case-strashing using the record of AIG subgraphs
00378     if ( fRecord && Abc_NtkRecIsRunning() && Abc_ObjFaninNum(pNodeOld) > 2 && Abc_ObjFaninNum(pNodeOld) <= Abc_NtkRecVarNum() )
00379     {
00380         extern Vec_Int_t * Abc_NtkRecMemory();
00381         extern int Abc_NtkRecStrashNode( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj, unsigned * pTruth, int nVars );
00382         int nVars = Abc_NtkRecVarNum();
00383         Vec_Int_t * vMemory = Abc_NtkRecMemory();
00384         unsigned * pTruth = Abc_ConvertAigToTruth( pMan, Hop_Regular(pRoot), nVars, vMemory, 0 );
00385         assert( Extra_TruthSupportSize(pTruth, nVars) == Abc_ObjFaninNum(pNodeOld) ); // should be swept
00386         if ( Hop_IsComplement(pRoot) )
00387             Extra_TruthNot( pTruth, pTruth, nVars );
00388         if ( Abc_NtkRecStrashNode( pNtkNew, pNodeOld, pTruth, nVars ) )
00389             return pNodeOld->pCopy;
00390     }
00391     // set elementary variables
00392     Abc_ObjForEachFanin( pNodeOld, pFanin, i )
00393         Hop_IthVar(pMan, i)->pData = pFanin->pCopy;
00394     // strash the AIG of this node
00395     Abc_NodeStrash_rec( pNtkNew->pManFunc, Hop_Regular(pRoot) );
00396     Hop_ConeUnmark_rec( Hop_Regular(pRoot) );
00397     // return the final node
00398     return Abc_ObjNotCond( Hop_Regular(pRoot)->pData, Hop_IsComplement(pRoot) );
00399 }
00400 
00401 
00402 
00403 
00404 
00405 
00406 
00418 Abc_Obj_t * Abc_NtkTopmost_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, int LevelCut )
00419 {
00420     assert( !Abc_ObjIsComplement(pNode) );
00421     if ( pNode->pCopy )
00422         return pNode->pCopy;
00423     if ( pNode->Level <= (unsigned)LevelCut )
00424         return pNode->pCopy = Abc_NtkCreatePi( pNtkNew );
00425     Abc_NtkTopmost_rec( pNtkNew, Abc_ObjFanin0(pNode), LevelCut );
00426     Abc_NtkTopmost_rec( pNtkNew, Abc_ObjFanin1(pNode), LevelCut );
00427     return pNode->pCopy = Abc_AigAnd( pNtkNew->pManFunc, Abc_ObjChild0Copy(pNode), Abc_ObjChild1Copy(pNode) );
00428 }
00429 
00441 Abc_Ntk_t * Abc_NtkTopmost( Abc_Ntk_t * pNtk, int nLevels )
00442 {
00443     Abc_Ntk_t * pNtkNew;
00444     Abc_Obj_t * pObjNew, * pPoNew;
00445     int LevelCut;
00446     assert( Abc_NtkIsStrash(pNtk) );
00447     assert( Abc_NtkCoNum(pNtk) == 1 );
00448     // get the cutoff level
00449     LevelCut = ABC_MAX( 0, Abc_AigLevel(pNtk) - nLevels );
00450     // start the network
00451     pNtkNew = Abc_NtkAlloc( ABC_NTK_STRASH, ABC_FUNC_AIG, 1 );
00452     pNtkNew->pName = Extra_UtilStrsav(pNtk->pName);
00453     Abc_AigConst1(pNtk)->pCopy = Abc_AigConst1(pNtkNew);
00454     // create PIs below the cut and nodes above the cut
00455     Abc_NtkCleanCopy( pNtk );
00456     pObjNew = Abc_NtkTopmost_rec( pNtkNew, Abc_ObjFanin0(Abc_NtkPo(pNtk, 0)), LevelCut );
00457     pObjNew = Abc_ObjNotCond( pObjNew, Abc_ObjFaninC0(Abc_NtkPo(pNtk, 0)) );
00458     // add the PO node and name
00459     pPoNew = Abc_NtkCreatePo(pNtkNew);
00460     Abc_ObjAddFanin( pPoNew, pObjNew );
00461     Abc_NtkAddDummyPiNames( pNtkNew );
00462     Abc_ObjAssignName( pPoNew, Abc_ObjName(Abc_NtkPo(pNtk, 0)), NULL );
00463     // make sure everything is okay
00464     if ( !Abc_NtkCheck( pNtkNew ) )
00465     {
00466         printf( "Abc_NtkTopmost: The network check has failed.\n" );
00467         Abc_NtkDelete( pNtkNew );
00468         return NULL;
00469     }
00470     return pNtkNew;
00471 }
00472 
00473 
00477 
00478