abc70930: src/opt/ret/retIncrem.c Source File

00001 
00021 #include "retInt.h"
00022 
00026 
00027 static int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose );
00028 
00032 
00044 int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int fForward, int fMinDelay, int fOneStep, int fVerbose )
00045 {
00046     Abc_Ntk_t * pNtkCopy = NULL;
00047     Vec_Ptr_t * vBoxes;
00048     st_table * tLatches;
00049     int nLatches = Abc_NtkLatchNum(pNtk);
00050     int nIdMaxStart = Abc_NtkObjNumMax(pNtk);
00051     int RetValue, nIterLimit;
00052     if ( Abc_NtkNodeNum(pNtk) == 0 )
00053         return 0;
00054     // reorder CI/CO/latch inputs
00055     Abc_NtkOrderCisCos( pNtk );
00056     if ( fMinDelay ) 
00057     {
00058         nIterLimit = fOneStep? 1 : 2 * Abc_NtkLevel(pNtk);
00059         pNtkCopy = Abc_NtkDup( pNtk );
00060         tLatches = Abc_NtkRetimePrepareLatches( pNtkCopy );
00061         st_free_table( tLatches );
00062     }
00063     // collect latches and remove CIs/COs
00064     tLatches = Abc_NtkRetimePrepareLatches( pNtk );
00065     // share the latches
00066     Abc_NtkRetimeShareLatches( pNtk, 0 );    
00067     // save boxes
00068     vBoxes = pNtk->vBoxes;  pNtk->vBoxes = NULL;
00069     // perform the retiming
00070     if ( fMinDelay )
00071         Abc_NtkRetimeMinDelay( pNtk, pNtkCopy, nIterLimit, fForward, fVerbose );
00072     else
00073         Abc_NtkRetimeOneWay( pNtk, fForward, fVerbose );
00074     if ( fMinDelay ) 
00075         Abc_NtkDelete( pNtkCopy );
00076     // share the latches
00077     Abc_NtkRetimeShareLatches( pNtk, 0 );    
00078     // restore boxes
00079     pNtk->vBoxes = vBoxes;
00080     // finalize the latches
00081     RetValue = Abc_NtkRetimeFinalizeLatches( pNtk, tLatches, nIdMaxStart );
00082     st_free_table( tLatches );
00083     if ( RetValue == 0 )
00084         return 0;
00085     // fix the COs
00086 //    Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
00087     // check for correctness
00088     if ( !Abc_NtkCheck( pNtk ) )
00089         fprintf( stdout, "Abc_NtkRetimeForward(): Network check has failed.\n" );
00090     // return the number of latches saved
00091     return nLatches - Abc_NtkLatchNum(pNtk);
00092 }
00093 
00105 st_table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk )
00106 {
00107     st_table * tLatches;
00108     Abc_Obj_t * pLatch, * pLatchIn, * pLatchOut, * pFanin;
00109     int i, nOffSet = Abc_NtkBoxNum(pNtk) - Abc_NtkLatchNum(pNtk);
00110     // collect latches and remove CIs/COs
00111     tLatches = st_init_table( st_ptrcmp, st_ptrhash );
00112     Abc_NtkForEachLatch( pNtk, pLatch, i )
00113     {
00114         // map latch into its true number
00115         st_insert( tLatches, (void *)pLatch, (void *)(i-nOffSet) );
00116         // disconnect LI     
00117         pLatchIn = Abc_ObjFanin0(pLatch);
00118         pFanin = Abc_ObjFanin0(pLatchIn);
00119         Abc_ObjTransferFanout( pLatchIn, pFanin );
00120         Abc_ObjDeleteFanin( pLatchIn, pFanin );
00121         // disconnect LO     
00122         pLatchOut = Abc_ObjFanout0(pLatch);
00123         pFanin = Abc_ObjFanin0(pLatchOut);
00124         if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
00125             Abc_ObjTransferFanout( pLatchOut, pFanin );
00126         Abc_ObjDeleteFanin( pLatchOut, pFanin );
00127     }
00128     return tLatches;
00129 }
00130 
00142 int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st_table * tLatches, int nIdMaxStart )
00143 {
00144     Vec_Ptr_t * vCisOld, * vCosOld, * vBoxesOld, * vCisNew, * vCosNew, * vBoxesNew;
00145     Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut;
00146     int i, Index;
00147     // create new arrays
00148     vCisOld   = pNtk->vCis;    pNtk->vCis   = NULL;  vCisNew   = Vec_PtrAlloc( 100 );
00149     vCosOld   = pNtk->vCos;    pNtk->vCos   = NULL;  vCosNew   = Vec_PtrAlloc( 100 );  
00150     vBoxesOld = pNtk->vBoxes;  pNtk->vBoxes = NULL;  vBoxesNew = Vec_PtrAlloc( 100 );
00151     // copy boxes and their CIs/COs
00152     Vec_PtrForEachEntryStop( vCisOld, pObj, i, Vec_PtrSize(vCisOld) - st_count(tLatches) )
00153         Vec_PtrPush( vCisNew, pObj );
00154     Vec_PtrForEachEntryStop( vCosOld, pObj, i, Vec_PtrSize(vCosOld) - st_count(tLatches) )
00155         Vec_PtrPush( vCosNew, pObj );
00156     Vec_PtrForEachEntryStop( vBoxesOld, pObj, i, Vec_PtrSize(vBoxesOld) - st_count(tLatches) )
00157         Vec_PtrPush( vBoxesNew, pObj );
00158     // go through the latches
00159     Abc_NtkForEachObj( pNtk, pLatch, i )
00160     {
00161         if ( !Abc_ObjIsLatch(pLatch) )
00162             continue;
00163         if ( Abc_ObjId(pLatch) >= (unsigned)nIdMaxStart )
00164         {
00165             // this is a new latch 
00166             pLatchIn  = Abc_NtkCreateBi(pNtk);
00167             pLatchOut = Abc_NtkCreateBo(pNtk);
00168             Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
00169             Abc_ObjAssignName( pLatchIn,  Abc_ObjName(pLatch), "_in" );
00170         }
00171         else
00172         {
00173             // this is an old latch 
00174             // get its number in the original order
00175             if ( !st_lookup( tLatches, (char *)pLatch, (char **)&Index ) )
00176             {
00177                 printf( "Abc_NtkRetimeFinalizeLatches(): Internal error.\n" );
00178                 return 0;
00179             }
00180             assert( pLatch == Vec_PtrEntry(vBoxesOld, Vec_PtrSize(vBoxesOld) - st_count(tLatches) + Index) );
00181             // reconnect with the old LIs/LOs
00182             pLatchIn  = Vec_PtrEntry( vCosOld, Vec_PtrSize(vCosOld) - st_count(tLatches) + Index );
00183             pLatchOut = Vec_PtrEntry( vCisOld, Vec_PtrSize(vCisOld) - st_count(tLatches) + Index );
00184         }
00185         // connect
00186         Abc_ObjAddFanin( pLatchIn, Abc_ObjFanin0(pLatch) );
00187         Abc_ObjPatchFanin( pLatch, Abc_ObjFanin0(pLatch), pLatchIn );
00188         if ( Abc_ObjFanoutNum(pLatch) > 0 )
00189             Abc_ObjTransferFanout( pLatch, pLatchOut );
00190         Abc_ObjAddFanin( pLatchOut, pLatch );
00191         // add to the arrays
00192         Vec_PtrPush( vCisNew, pLatchOut );
00193         Vec_PtrPush( vCosNew, pLatchIn );
00194         Vec_PtrPush( vBoxesNew, pLatch );
00195     }
00196     // free useless Cis/Cos
00197     Vec_PtrForEachEntry( vCisOld, pObj, i )
00198         if ( !Abc_ObjIsPi(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
00199             Abc_NtkDeleteObj(pObj);
00200     Vec_PtrForEachEntry( vCosOld, pObj, i )
00201         if ( !Abc_ObjIsPo(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
00202             Abc_NtkDeleteObj(pObj);
00203     // set the new arrays
00204     pNtk->vCis   = vCisNew;   Vec_PtrFree( vCisOld );
00205     pNtk->vCos   = vCosNew;   Vec_PtrFree( vCosOld );
00206     pNtk->vBoxes = vBoxesNew; Vec_PtrFree( vBoxesOld );
00207     return 1;
00208 }
00209 
00221 int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
00222 {
00223     Abc_Ntk_t * pNtkNew;
00224     Vec_Int_t * vValues;
00225     Abc_Obj_t * pObj;
00226     int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 10000;
00227     if ( fForward )
00228         Abc_NtkRetimeTranferToCopy( pNtk );
00229     else
00230     {
00231         // save initial values of the latches
00232         vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
00233         // start the network for initial value computation
00234         pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
00235     }
00236     // try to move latches forward whenever possible
00237     do {
00238         fChanges = 0;
00239         Abc_NtkForEachObj( pNtk, pObj, i )
00240         {
00241             if ( !Abc_ObjIsNode(pObj) )
00242                 continue;
00243             if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
00244             {
00245                 Abc_NtkRetimeNode( pObj, fForward, 1 );
00246                 fChanges = 1;
00247                 nTotalMoves++;
00248                 if ( nTotalMoves >= nTotalMovesLimit )
00249                 {
00250                     printf( "Stopped after %d latch moves.\n", nTotalMoves );
00251                     break;
00252                 }
00253             }
00254         }
00255     } while ( fChanges && nTotalMoves < nTotalMovesLimit );
00256     // transfer the initial state back to the latches
00257     if ( fForward )
00258         Abc_NtkRetimeTranferFromCopy( pNtk );
00259     else
00260     {
00261         Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
00262         Abc_NtkDelete( pNtkNew );
00263         Vec_IntFree( vValues );
00264     }
00265     return 0;
00266 }
00267 
00268 
00280 int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward )
00281 {
00282     Abc_Obj_t * pNext;
00283     int i;
00284     assert( Abc_ObjIsNode(pObj) );
00285     if ( fForward )
00286     {
00287         Abc_ObjForEachFanin( pObj, pNext, i )
00288             if ( !Abc_ObjIsLatch(pNext) )
00289                 return 0;
00290     }
00291     else
00292     {
00293         Abc_ObjForEachFanout( pObj, pNext, i )
00294             if ( !Abc_ObjIsLatch(pNext) )
00295                 return 0;
00296     }
00297     return 1;
00298 }
00299 
00311 void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial )
00312 {
00313     Abc_Ntk_t * pNtkNew = NULL;
00314     Vec_Ptr_t * vNodes;
00315     Abc_Obj_t * pNext, * pLatch;
00316     int i;
00317     vNodes = Vec_PtrAlloc( 10 );
00318     if ( fForward )
00319     {
00320         // compute the initial value
00321         if ( fInitial )
00322             pObj->pCopy = (void *)Abc_ObjSopSimulate( pObj );
00323         // collect fanins
00324         Abc_NodeCollectFanins( pObj, vNodes );
00325         // make the node point to the fanins fanins
00326         Vec_PtrForEachEntry( vNodes, pNext, i )
00327         {
00328             assert( Abc_ObjIsLatch(pNext) );
00329             Abc_ObjPatchFanin( pObj, pNext, Abc_ObjFanin0(pNext) );
00330             if ( Abc_ObjFanoutNum(pNext) == 0 )
00331                 Abc_NtkDeleteObj(pNext);            
00332         }
00333         // add a new latch on top
00334         pNext = Abc_NtkCreateLatch(pObj->pNtk);
00335         if ( Abc_ObjFanoutNum(pObj) > 0 )
00336             Abc_ObjTransferFanout( pObj, pNext );
00337         Abc_ObjAddFanin( pNext, pObj );
00338         // set the initial value
00339         if ( fInitial )
00340             pNext->pCopy = pObj->pCopy;
00341     }
00342     else
00343     {
00344         // compute the initial value
00345         if ( fInitial )
00346         {
00347             pNtkNew = Abc_ObjFanout0(pObj)->pCopy->pNtk;
00348             Abc_NtkDupObj( pNtkNew, pObj, 0 );
00349             Abc_ObjForEachFanout( pObj, pNext, i )
00350             {
00351                 assert( Abc_ObjFaninNum(pNext->pCopy) == 0 );
00352                 Abc_ObjAddFanin( pNext->pCopy, pObj->pCopy );
00353             }
00354         }
00355         // collect fanouts
00356         Abc_NodeCollectFanouts( pObj, vNodes );
00357         // make the fanouts fanouts point to the node
00358         Vec_PtrForEachEntry( vNodes, pNext, i )
00359         {
00360             assert( Abc_ObjIsLatch(pNext) );
00361             Abc_ObjTransferFanout( pNext, pObj );
00362             Abc_NtkDeleteObj( pNext );  
00363         }
00364         // add new latches to the fanins
00365         Abc_ObjForEachFanin( pObj, pNext, i )
00366         {
00367             pLatch = Abc_NtkCreateLatch(pObj->pNtk);
00368             Abc_ObjPatchFanin( pObj, pNext, pLatch );
00369             Abc_ObjAddFanin( pLatch, pNext );
00370             // create buffer isomorphic to this latch
00371             if ( fInitial )
00372             {
00373                 pLatch->pCopy = Abc_NtkCreateNodeBuf( pNtkNew, NULL );
00374                 Abc_ObjAddFanin( pObj->pCopy, pLatch->pCopy );
00375             }
00376         }
00377     }
00378     Vec_PtrFree( vNodes );
00379 }
00380 
00392 int Abc_NtkRetimeCheckCompatibleLatchFanouts( Abc_Obj_t * pObj )
00393 {
00394     Abc_Obj_t * pFanout;
00395     int i, nLatches = 0, Init = -1;
00396     Abc_ObjForEachFanout( pObj, pFanout, i )
00397     {
00398         if ( !Abc_ObjIsLatch(pFanout) )
00399             continue;
00400         if ( Init == -1 )
00401         {
00402             Init = (int)pObj->pData;
00403             nLatches++;
00404         }
00405         else if ( Init == (int)pObj->pData )
00406             nLatches++;
00407     }
00408     return nLatches;
00409 }
00410 
00422 void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial )
00423 {
00424     Vec_Ptr_t * vNodes;
00425     Abc_Obj_t * pFanin, * pLatchTop, * pLatchCur;
00426     int i, k;
00427     vNodes = Vec_PtrAlloc( 10 );
00428     // consider latch fanins
00429     Abc_NtkForEachObj( pNtk, pFanin, i )
00430     {
00431         if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 )
00432             continue;
00433         // get the first latch
00434         pLatchTop = NULL;
00435         Abc_ObjForEachFanout( pFanin, pLatchTop, k )
00436             if ( Abc_ObjIsLatch(pLatchTop) )
00437                 break;
00438         assert( pLatchTop && Abc_ObjIsLatch(pLatchTop) );
00439         // redirect compatible fanout latches to the first latch
00440         Abc_NodeCollectFanouts( pFanin, vNodes );
00441         Vec_PtrForEachEntry( vNodes, pLatchCur, k )
00442         {
00443             if ( !Abc_ObjIsLatch(pLatchCur) )
00444                 continue;
00445             if ( pLatchCur == pLatchTop )
00446                 continue;
00447             if ( pLatchCur->pData != pLatchTop->pData )
00448                 continue;
00449             // connect the initial state
00450             if ( fInitial )
00451                 Abc_ObjAddFanin( pLatchCur->pCopy, pLatchTop->pCopy );
00452             // redirect the fanouts
00453             Abc_ObjTransferFanout( pLatchCur, pLatchTop );
00454             Abc_NtkDeleteObj(pLatchCur);
00455         }
00456     }
00457     Vec_PtrFree( vNodes );
00458 }
00459 
00463 
00464