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

00001 
00021 #include "retInt.h"
00022 
00026 
00027 static Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose );
00028 static void        Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward );
00029 static void        Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
00030 static Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
00031 static void        Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
00032 
00033 extern Abc_Ntk_t * Abc_NtkAttachBottom( Abc_Ntk_t * pNtkTop, Abc_Ntk_t * pNtkBottom );
00034 
00038 
00050 int Abc_NtkRetimeMinArea( Abc_Ntk_t * pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose )
00051 {
00052     Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom;
00053     Vec_Int_t * vValuesNew = NULL, * vValues;
00054     int nLatches = Abc_NtkLatchNum(pNtk);
00055     int fOneFrame = 0;
00056     assert( !fForwardOnly || !fBackwardOnly );
00057     // there should not be black boxes
00058     assert( Abc_NtkIsSopLogic(pNtk) );
00059     assert( Abc_NtkLatchNum(pNtk) == Vec_PtrSize(pNtk->vBoxes) );
00060     // reorder CI/CO/latch inputs
00061     Abc_NtkOrderCisCos( pNtk );
00062     // perform forward retiming
00063     if ( !fBackwardOnly )
00064     {
00065         if ( fOneFrame )
00066             Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose );
00067         else
00068             while ( Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose ) );
00069     }
00070     // remember initial values
00071     vValues = Abc_NtkCollectLatchValues( pNtk );
00072     // perform backward retiming
00073     if ( !fForwardOnly )
00074     {
00075         if ( fOneFrame )
00076             pNtkTotal = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose );
00077         else
00078             while ( pNtkBottom = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose ) )
00079                 pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom );  
00080     }
00081     // compute initial values
00082     vValuesNew = Abc_NtkRetimeInitialValues( pNtkTotal, vValues, fVerbose );
00083     if ( pNtkTotal ) Abc_NtkDelete( pNtkTotal );
00084     // insert new initial values
00085     Abc_NtkInsertLatchValues( pNtk, vValuesNew );
00086     if ( vValuesNew ) Vec_IntFree( vValuesNew );
00087     if ( vValues )    Vec_IntFree( vValues );
00088     // fix the COs (this changes the circuit structure)
00089 //    Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
00090     // check for correctness
00091     if ( !Abc_NtkCheck( pNtk ) )
00092         fprintf( stdout, "Abc_NtkRetimeMinArea(): Network check has failed.\n" );
00093     // return the number of latches saved
00094     return nLatches - Abc_NtkLatchNum(pNtk);
00095 }
00096 
00108 Abc_Ntk_t * Abc_NtkRetimeMinAreaOne( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
00109 { 
00110     Abc_Ntk_t * pNtkNew = NULL;
00111     Vec_Ptr_t * vMinCut;
00112     int nLatches = Abc_NtkLatchNum(pNtk);
00113     // mark current latches and TFI(POs)
00114     Abc_NtkRetimeMinAreaPrepare( pNtk, fForward );
00115     // run the maximum forward flow
00116     vMinCut = Abc_NtkMaxFlow( pNtk, fForward, fVerbose );
00117 //    assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) );
00118     // create new latch boundary if there is improvement
00119     if ( Vec_PtrSize(vMinCut) < Abc_NtkLatchNum(pNtk) )
00120     {
00121         pNtkNew = (Abc_Ntk_t *)1;
00122         if ( fForward )
00123             Abc_NtkRetimeMinAreaInitValues( pNtk, vMinCut );
00124         else
00125             pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut );
00126         Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, fForward );
00127     }
00128     // clean up
00129     Vec_PtrFree( vMinCut );
00130     Abc_NtkCleanMarkA( pNtk );
00131     return pNtkNew;
00132 }
00133 
00145 void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward )
00146 {
00147     Abc_Obj_t * pNext;
00148     int i;
00149     if ( pObj->fMarkA )
00150         return;
00151     pObj->fMarkA = 1;
00152     if ( fForward )
00153     {
00154         Abc_ObjForEachFanout( pObj, pNext, i )
00155             Abc_NtkMarkCone_rec( pNext, fForward );
00156     }
00157     else
00158     {
00159         Abc_ObjForEachFanin( pObj, pNext, i )
00160             Abc_NtkMarkCone_rec( pNext, fForward );
00161     }
00162 }
00163 
00175 void Abc_NtkUnmarkCone_rec( Abc_Obj_t * pObj, int fForward )
00176 {
00177     Abc_Obj_t * pNext;
00178     int i;
00179     if ( !pObj->fMarkA || Abc_ObjIsLatch(pObj) )
00180         return;
00181     pObj->fMarkA = 0;
00182     if ( fForward )
00183     {
00184         Abc_ObjForEachFanout( pObj, pNext, i )
00185             Abc_NtkUnmarkCone_rec( pNext, fForward );
00186     }
00187     else
00188     {
00189         Abc_ObjForEachFanin( pObj, pNext, i )
00190             Abc_NtkUnmarkCone_rec( pNext, fForward );
00191     }
00192 }
00193 
00205 void Abc_NtkRetimeMinAreaPrepare( Abc_Ntk_t * pNtk, int fForward )
00206 {
00207     Vec_Ptr_t * vNodes;
00208     Abc_Obj_t * pObj, * pFanin;
00209     int i, k;
00210     if ( fForward )
00211     {
00212         // mark the frontier
00213         Abc_NtkForEachPo( pNtk, pObj, i )
00214             pObj->fMarkA = 1;
00215         Abc_NtkForEachLatch( pNtk, pObj, i )
00216         {
00217             pObj->fMarkA = 1;
00218             Abc_ObjFanin0(pObj)->fMarkA = 1;
00219         }
00220         // mark the nodes reachable from the PIs
00221         Abc_NtkForEachPi( pNtk, pObj, i )
00222             Abc_NtkMarkCone_rec( pObj, fForward );
00223         // collect the unmarked fanins of the marked nodes
00224         vNodes = Vec_PtrAlloc( 100 );
00225         Abc_NtkForEachObj( pNtk, pObj, i )
00226             if ( pObj->fMarkA )
00227                 Abc_ObjForEachFanin( pObj, pFanin, k )
00228                     if ( !pFanin->fMarkA )
00229                         Vec_PtrPush( vNodes, pFanin );
00230         // mark these nodes
00231         Vec_PtrForEachEntry( vNodes, pObj, i )
00232             pObj->fMarkA = 1;
00233         Vec_PtrFree( vNodes );
00234     }
00235     else
00236     {
00237         // mark the frontier
00238         Abc_NtkForEachPi( pNtk, pObj, i )
00239             pObj->fMarkA = 1;
00240         Abc_NtkForEachLatch( pNtk, pObj, i )
00241         {
00242             pObj->fMarkA = 1;
00243             Abc_ObjFanout0(pObj)->fMarkA = 1;
00244         }
00245         // mark the nodes reachable from the POs
00246         Abc_NtkForEachPo( pNtk, pObj, i )
00247             Abc_NtkMarkCone_rec( pObj, fForward );
00248     }
00249 }
00250 
00262 int Abc_NtkRetimeMinAreaInitValues_rec( Abc_Obj_t * pObj )
00263 {
00264     Abc_Obj_t * pFanin;
00265     int i;
00266     // skip visited nodes
00267     if ( Abc_NodeIsTravIdCurrent(pObj) )
00268         return (int)pObj->pCopy;
00269     Abc_NodeSetTravIdCurrent(pObj);
00270     // consider the case of a latch output
00271     if ( Abc_ObjIsBo(pObj) )
00272     {
00273         assert( Abc_ObjIsLatch(Abc_ObjFanin0(pObj)) );
00274         pObj->pCopy = (void *)Abc_NtkRetimeMinAreaInitValues_rec( Abc_ObjFanin0(pObj) );
00275         return (int)pObj->pCopy;
00276     }
00277     assert( Abc_ObjIsNode(pObj) );
00278     // visit the fanins
00279     Abc_ObjForEachFanin( pObj, pFanin, i )
00280         Abc_NtkRetimeMinAreaInitValues_rec( pFanin );
00281     // compute the value of the node
00282     pObj->pCopy = (void *)Abc_ObjSopSimulate(pObj);
00283     return (int)pObj->pCopy;
00284 }
00285 
00297 void Abc_NtkRetimeMinAreaInitValues( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
00298 {
00299     Abc_Obj_t * pObj;
00300     int i;
00301     // transfer initial values to pCopy and mark the latches
00302     Abc_NtkIncrementTravId(pNtk);
00303     Abc_NtkForEachLatch( pNtk, pObj, i )
00304     {
00305         pObj->pCopy = (void *)Abc_LatchIsInit1(pObj);
00306         Abc_NodeSetTravIdCurrent( pObj );
00307     }
00308     // propagate initial values
00309     Vec_PtrForEachEntry( vMinCut, pObj, i )
00310         Abc_NtkRetimeMinAreaInitValues_rec( pObj );
00311     // unmark the latches
00312     Abc_NtkForEachLatch( pNtk, pObj, i )
00313         Abc_NodeSetTravIdPrevious( pObj );
00314 }
00315 
00327 Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pObj )
00328 {
00329     Abc_Obj_t * pFanin;
00330     int i;
00331     // skip visited nodes
00332     if ( Abc_NodeIsTravIdCurrent(pObj) )
00333         return pObj->pCopy;
00334     Abc_NodeSetTravIdCurrent(pObj);
00335     // consider the case of a latch output
00336     if ( Abc_ObjIsBi(pObj) )
00337     {
00338         pObj->pCopy = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
00339         return pObj->pCopy;
00340     }
00341     assert( Abc_ObjIsNode(pObj) );
00342     // visit the fanins
00343     Abc_ObjForEachFanin( pObj, pFanin, i )
00344         Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, pFanin );
00345     // compute the value of the node
00346     Abc_NtkDupObj( pNtkNew, pObj, 0 );
00347     Abc_ObjForEachFanin( pObj, pFanin, i )
00348         Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
00349     return pObj->pCopy;
00350 }
00351 
00363 Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
00364 {
00365     Abc_Ntk_t * pNtkNew;
00366     Abc_Obj_t * pObj, * pObjNew;
00367     int i;
00368     // create new network
00369     pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
00370     // map new latches into PIs of the new network
00371     Abc_NtkIncrementTravId(pNtk);
00372     Vec_PtrForEachEntry( vMinCut, pObj, i )
00373     {
00374         pObj->pCopy = Abc_NtkCreatePi(pNtkNew);
00375         Abc_NodeSetTravIdCurrent( pObj );
00376     }
00377     // construct the network recursively
00378     Abc_NtkForEachLatch( pNtk, pObj, i )
00379     {
00380         pObjNew = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
00381         Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObjNew );
00382     }
00383     // unmark the nodes in the cut
00384     Vec_PtrForEachEntry( vMinCut, pObj, i )
00385         Abc_NodeSetTravIdPrevious( pObj );
00386     // unmark the latches
00387     Abc_NtkForEachLatch( pNtk, pObj, i )
00388         Abc_NodeSetTravIdPrevious( pObj );
00389     // assign dummy node names
00390     Abc_NtkAddDummyPiNames( pNtkNew );
00391     Abc_NtkAddDummyPoNames( pNtkNew );
00392     if ( !Abc_NtkCheck( pNtkNew ) )
00393         fprintf( stdout, "Abc_NtkRetimeMinAreaConstructNtk(): Network check has failed.\n" );
00394     return pNtkNew;
00395 }
00396 
00409 void Abc_NtkRetimeMinAreaUpdateLatches( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
00410 {
00411     Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes, * vBuffers;
00412     Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext, * pBuffer;
00413     int i, k;
00414     // create new latches
00415     Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) );
00416     Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) );
00417     vCis   = pNtk->vCis;   pNtk->vCis   = NULL;  
00418     vCos   = pNtk->vCos;   pNtk->vCos   = NULL;  
00419     vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL; 
00420     // transfer boxes
00421     vBoxesNew = Vec_PtrAlloc(100);
00422     Vec_PtrForEachEntry( vBoxes, pObj, i )
00423         if ( !Abc_ObjIsLatch(pObj) )
00424             Vec_PtrPush( vBoxesNew, pObj );
00425     // create or reuse latches
00426     vNodes = Vec_PtrAlloc( 100 );
00427     vBuffers = Vec_PtrAlloc( 100 );
00428     Vec_PtrForEachEntry( vMinCut, pObj, i )
00429     {
00430         if ( Abc_ObjIsCi(pObj) && fForward )
00431         {
00432             pLatchOut = pObj;
00433             pLatch    = Abc_ObjFanin0(pLatchOut);
00434             pLatchIn  = Abc_ObjFanin0(pLatch);
00435             assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
00436             // mark the latch as reused
00437             Abc_NodeSetTravIdCurrent( pLatch );
00438 
00439             // check if there are marked fanouts
00440             // (these are fanouts to be connected to the latch input)
00441             Abc_ObjForEachFanout( pObj, pNext, k )
00442                 if ( pNext->fMarkA )
00443                     break;
00444             if ( k < Abc_ObjFanoutNum(pObj) )
00445             {
00446                 // add the buffer
00447                 pBuffer = Abc_NtkCreateNodeBuf( pNtk, Abc_ObjFanin0(pLatchIn) );
00448                 Abc_ObjPatchFanin( pLatchIn, Abc_ObjFanin0(pLatchIn), pBuffer );
00449                 Vec_PtrPush( vBuffers, pBuffer );
00450                 // redirect edges to the unvisited fanouts of the node
00451                 Abc_NodeCollectFanouts( pObj, vNodes );
00452                 Vec_PtrForEachEntry( vNodes, pNext, k )
00453                     if ( pNext->fMarkA )
00454                         Abc_ObjPatchFanin( pNext, pObj, pBuffer );
00455             }
00456             assert( Abc_ObjFanoutNum(pObj) > 0 );
00457 //            if ( Abc_ObjFanoutNum(pObj) == 0 )
00458 //                Abc_NtkDeleteObj_rec( pObj, 0 );
00459         }
00460         else if ( Abc_ObjIsCo(pObj) && !fForward )
00461         {
00462             pLatchIn  = pObj;
00463             pLatch    = Abc_ObjFanout0(pLatchIn);
00464             pLatchOut = Abc_ObjFanout0(pLatch);
00465             assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
00466             // mark the latch as reused
00467             Abc_NodeSetTravIdCurrent( pLatch );
00468             assert( !Abc_ObjFanin0(pLatchIn)->fMarkA );
00469         }
00470         else
00471         {
00472             pLatchOut = Abc_NtkCreateBo(pNtk);
00473             pLatch    = Abc_NtkCreateLatch(pNtk);
00474             pLatchIn  = Abc_NtkCreateBi(pNtk);
00475             Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
00476             Abc_ObjAssignName( pLatchIn,  Abc_ObjName(pLatch), "_in" );
00477             // connect
00478             Abc_ObjAddFanin( pLatchOut, pLatch );
00479             Abc_ObjAddFanin( pLatch, pLatchIn );
00480             if ( fForward )
00481             {
00482                 pLatch->pData = (void *)(pObj->pCopy? ABC_INIT_ONE : ABC_INIT_ZERO);
00483                 // redirect edges to the unvisited fanouts of the node
00484                 Abc_NodeCollectFanouts( pObj, vNodes );
00485                 Vec_PtrForEachEntry( vNodes, pNext, k )
00486                     if ( !pNext->fMarkA )
00487                         Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
00488             }
00489             else
00490             {
00491                 // redirect edges to the visited fanouts of the node
00492                 Abc_NodeCollectFanouts( pObj, vNodes );
00493                 Vec_PtrForEachEntry( vNodes, pNext, k )
00494                     if ( pNext->fMarkA )
00495                         Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
00496             }
00497             // connect latch to the node
00498             Abc_ObjAddFanin( pLatchIn, pObj );
00499         }
00500         Vec_PtrPush( vCis, pLatchOut );
00501         Vec_PtrPush( vBoxesNew, pLatch );
00502         Vec_PtrPush( vCos, pLatchIn );
00503     }
00504     Vec_PtrFree( vNodes );
00505     // remove buffers
00506     Vec_PtrForEachEntry( vBuffers, pObj, i )
00507     {
00508         Abc_ObjTransferFanout( pObj, Abc_ObjFanin0(pObj) );
00509         Abc_NtkDeleteObj( pObj );
00510     }
00511     Vec_PtrFree( vBuffers );
00512     // remove useless latches
00513     Vec_PtrForEachEntry( vBoxes, pObj, i )
00514     {
00515         if ( !Abc_ObjIsLatch(pObj) )
00516             continue;
00517         if ( Abc_NodeIsTravIdCurrent(pObj) )
00518             continue;
00519         pLatchOut = Abc_ObjFanout0(pObj);
00520         pLatch    = pObj;
00521         pLatchIn  = Abc_ObjFanin0(pObj);
00522         if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
00523             Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) );
00524         Abc_NtkDeleteObj( pLatchOut );
00525         Abc_NtkDeleteObj( pObj );
00526         Abc_NtkDeleteObj( pLatchIn );
00527     }
00528     // set the arrays
00529     pNtk->vCis = vCis;
00530     pNtk->vCos = vCos;
00531     pNtk->vBoxes = vBoxesNew;
00532     Vec_PtrFree( vBoxes );
00533 }
00534 
00535 
00539 
00540