1 /**CFile****************************************************************
2 
3   FileName    [fretMain.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [Flow-based retiming package.]
8 
9   Synopsis    [Main file for retiming package.]
10 
11   Author      [Aaron Hurst]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - January 1, 2008.]
16 
17   Revision    [$Id: fretMain.c,v 1.00 2008/01/01 00:00:00 ahurst Exp $]
18 
19 ***********************************************************************/
20 
21 #include "fretime.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 ///                        DECLARATIONS                              ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static void Abc_FlowRetime_AddDummyFanin( Abc_Obj_t * pObj );
31 
32 static Abc_Ntk_t* Abc_FlowRetime_MainLoop( );
33 
34 static void Abc_FlowRetime_MarkBlocks( Abc_Ntk_t * pNtk );
35 static void Abc_FlowRetime_MarkReachable_rec( Abc_Obj_t * pObj, char end );
36 static int  Abc_FlowRetime_ImplementCut( Abc_Ntk_t * pNtk );
37 static void  Abc_FlowRetime_RemoveLatchBubbles( Abc_Obj_t * pLatch );
38 
39 static Abc_Ntk_t* Abc_FlowRetime_NtkDup( Abc_Ntk_t * pNtk );
40 
41 static void Abc_FlowRetime_VerifyPathLatencies( Abc_Ntk_t * pNtk );
42 static int  Abc_FlowRetime_VerifyPathLatencies_rec( Abc_Obj_t * pObj, int markD );
43 
44 static void Abc_FlowRetime_UpdateLags_forw_rec( Abc_Obj_t *pObj );
45 static void Abc_FlowRetime_UpdateLags_back_rec( Abc_Obj_t *pObj );
46 
47 extern void Abc_NtkMarkCone_rec( Abc_Obj_t * pObj, int fForward );
48 
49 void
50 print_node3(Abc_Obj_t *pObj);
51 
52 MinRegMan_t *pManMR;
53 
54 int          fPathError = 0;
55 
56 ////////////////////////////////////////////////////////////////////////
57 ///                     FUNCTION DEFINITIONS                         ///
58 ////////////////////////////////////////////////////////////////////////
59 
60 /**Function*************************************************************
61 
62   Synopsis    [Performs minimum-register retiming.]
63 
64   Description []
65 
66   SideEffects []
67 
68   SeeAlso     []
69 
70 ***********************************************************************/
71 Abc_Ntk_t *
Abc_FlowRetime_MinReg(Abc_Ntk_t * pNtk,int fVerbose,int fComputeInitState,int fGuaranteeInitState,int fBlockConst,int fForwardOnly,int fBackwardOnly,int nMaxIters,int maxDelay,int fFastButConservative)72 Abc_FlowRetime_MinReg( Abc_Ntk_t * pNtk, int fVerbose,
73                        int fComputeInitState, int fGuaranteeInitState, int fBlockConst,
74                        int fForwardOnly, int fBackwardOnly, int nMaxIters,
75                        int maxDelay, int fFastButConservative ) {
76 
77   int i;
78   Abc_Obj_t   *pObj, *pNext;
79   InitConstraint_t *pData;
80 
81   // create manager
82   pManMR = ABC_ALLOC( MinRegMan_t, 1 );
83 
84   pManMR->pNtk = pNtk;
85   pManMR->fVerbose = fVerbose;
86   pManMR->fComputeInitState = fComputeInitState;
87   pManMR->fGuaranteeInitState = fGuaranteeInitState;
88   pManMR->fBlockConst = fBlockConst;
89   pManMR->fForwardOnly = fForwardOnly;
90   pManMR->fBackwardOnly = fBackwardOnly;
91   pManMR->nMaxIters = nMaxIters;
92   pManMR->maxDelay = maxDelay;
93   pManMR->fComputeInitState = fComputeInitState;
94   pManMR->fConservTimingOnly = fFastButConservative;
95   pManMR->vNodes = Vec_PtrAlloc(100);
96   pManMR->vInitConstraints = Vec_PtrAlloc(2);
97   pManMR->pInitNtk = NULL;
98   pManMR->pInitToOrig = NULL;
99   pManMR->sizeInitToOrig = 0;
100 
101   vprintf("Flow-based minimum-register retiming...\n");
102 
103   if (!Abc_NtkHasOnlyLatchBoxes(pNtk)) {
104     printf("\tERROR: Can not retime with black/white boxes\n");
105     return pNtk;
106   }
107 
108   if (maxDelay) {
109     vprintf("\tmax delay constraint = %d\n", maxDelay);
110     if (maxDelay < (i = Abc_NtkLevel(pNtk))) {
111       printf("ERROR: max delay constraint (%d) must be > current max delay (%d)\n", maxDelay, i);
112       return pNtk;
113     }
114   }
115 
116   // print info about type of network
117   vprintf("\tnetlist type = ");
118   if (Abc_NtkIsNetlist( pNtk )) { vprintf("netlist/"); }
119   else if (Abc_NtkIsLogic( pNtk )) { vprintf("logic/"); }
120   else if (Abc_NtkIsStrash( pNtk )) { vprintf("strash/"); }
121   else { vprintf("***unknown***/"); }
122   if (Abc_NtkHasSop( pNtk )) { vprintf("sop\n"); }
123   else if (Abc_NtkHasBdd( pNtk )) { vprintf("bdd\n"); }
124   else if (Abc_NtkHasAig( pNtk )) { vprintf("aig\n"); }
125   else if (Abc_NtkHasMapping( pNtk )) { vprintf("mapped\n"); }
126   else { vprintf("***unknown***\n"); }
127 
128   vprintf("\tinitial reg count = %d\n", Abc_NtkLatchNum(pNtk));
129   vprintf("\tinitial levels = %d\n", Abc_NtkLevel(pNtk));
130 
131   // remove bubbles from latch boxes
132   if (pManMR->fVerbose) Abc_FlowRetime_PrintInitStateInfo(pNtk);
133   vprintf("\tpushing bubbles out of latch boxes\n");
134   Abc_NtkForEachLatch( pNtk, pObj, i )
135     Abc_FlowRetime_RemoveLatchBubbles(pObj);
136   if (pManMR->fVerbose) Abc_FlowRetime_PrintInitStateInfo(pNtk);
137 
138   // check for box inputs/outputs
139   Abc_NtkForEachLatch( pNtk, pObj, i ) {
140     assert(Abc_ObjFaninNum(pObj) == 1);
141     assert(Abc_ObjFanoutNum(pObj) == 1);
142     assert(!Abc_ObjFaninC0(pObj));
143 
144     pNext = Abc_ObjFanin0(pObj);
145     assert(Abc_ObjIsBi(pNext));
146     assert(Abc_ObjFaninNum(pNext) <= 1);
147     if(Abc_ObjFaninNum(pNext) == 0) // every Bi should have a fanin
148       Abc_FlowRetime_AddDummyFanin( pNext );
149 
150     pNext = Abc_ObjFanout0(pObj);
151     assert(Abc_ObjIsBo(pNext));
152     assert(Abc_ObjFaninNum(pNext) == 1);
153     assert(!Abc_ObjFaninC0(pNext));
154   }
155 
156   pManMR->nLatches = Abc_NtkLatchNum( pNtk );
157   pManMR->nNodes = Abc_NtkObjNumMax( pNtk )+1;
158 
159   // build histogram
160   pManMR->vSinkDistHist = Vec_IntStart( pManMR->nNodes*2+10 );
161 
162   // initialize timing
163   if (maxDelay)
164     Abc_FlowRetime_InitTiming( pNtk );
165 
166   // create lag and Flow_Data structure
167   pManMR->vLags = Vec_IntStart(pManMR->nNodes);
168   memset(pManMR->vLags->pArray, 0, sizeof(int)*pManMR->nNodes);
169 
170   pManMR->pDataArray = ABC_ALLOC( Flow_Data_t, pManMR->nNodes );
171   Abc_FlowRetime_ClearFlows( 1 );
172 
173   // main loop!
174   pNtk = Abc_FlowRetime_MainLoop();
175 
176   // cleanup node fields
177   Abc_NtkForEachObj( pNtk, pObj, i ) {
178     // if not computing init state, set all latches to DC
179     if (!fComputeInitState && Abc_ObjIsLatch(pObj))
180       Abc_LatchSetInitDc(pObj);
181   }
182 
183   // deallocate space
184   ABC_FREE( pManMR->pDataArray );
185   if (pManMR->pInitToOrig) ABC_FREE( pManMR->pInitToOrig );
186   if (pManMR->vNodes) Vec_PtrFree(pManMR->vNodes);
187   if (pManMR->vLags) Vec_IntFree(pManMR->vLags);
188   if (pManMR->vSinkDistHist) Vec_IntFree(pManMR->vSinkDistHist);
189   if (pManMR->maxDelay) Abc_FlowRetime_FreeTiming( pNtk );
190   while( Vec_PtrSize( pManMR->vInitConstraints )) {
191     pData = (InitConstraint_t*)Vec_PtrPop( pManMR->vInitConstraints );
192     //assert( pData->pBiasNode );
193     //Abc_NtkDeleteObj( pData->pBiasNode );
194     ABC_FREE( pData->vNodes.pArray );
195     ABC_FREE( pData );
196   }
197   ABC_FREE( pManMR->vInitConstraints );
198 
199   // restrash if necessary
200   if (Abc_NtkIsStrash(pNtk)) {
201     Abc_NtkReassignIds( pNtk );
202     pNtk = Abc_FlowRetime_NtkSilentRestrash( pNtk, 1 );
203   }
204 
205   vprintf("\tfinal reg count = %d\n", Abc_NtkLatchNum(pNtk));
206   vprintf("\tfinal levels = %d\n", Abc_NtkLevel(pNtk));
207 
208 #if defined(DEBUG_CHECK)
209   Abc_NtkDoCheck( pNtk );
210 #endif
211 
212   // free manager
213   ABC_FREE( pManMR );
214 
215   return pNtk;
216 }
217 
218 /**Function*************************************************************
219 
220   Synopsis    [Main loop.]
221 
222   Description []
223 
224   SideEffects []
225 
226   SeeAlso     []
227 
228 ***********************************************************************/
229 Abc_Ntk_t *
Abc_FlowRetime_MainLoop()230 Abc_FlowRetime_MainLoop( ) {
231   Abc_Ntk_t *pNtk = pManMR->pNtk, *pNtkCopy = pNtk;
232   Abc_Obj_t *pObj; int i;
233   int last, flow = 0, cut;
234 
235   // (i) forward retiming loop
236   pManMR->fIsForward = 1;
237   pManMR->iteration = 0;
238 
239   if (!pManMR->fBackwardOnly) do {
240     if (pManMR->iteration == pManMR->nMaxIters) break;
241     pManMR->subIteration = 0;
242 
243     vprintf("\tforward iteration %d\n", pManMR->iteration);
244     last = Abc_NtkLatchNum( pNtk );
245 
246     Abc_FlowRetime_MarkBlocks( pNtk );
247 
248     if (pManMR->maxDelay) {
249       // timing-constrained loop
250       Abc_FlowRetime_ConstrainConserv( pNtk );
251       while(Abc_FlowRetime_RefineConstraints( )) {
252         pManMR->subIteration++;
253         Abc_FlowRetime_ClearFlows( 0 );
254       }
255     } else {
256       flow = Abc_FlowRetime_PushFlows( pNtk, 1 );
257     }
258 
259     cut = Abc_FlowRetime_ImplementCut( pNtk );
260 
261 #if defined (DEBUG_PRINT_LEVELS)
262     vprintf("\t\tlevels = %d\n", Abc_NtkLevel(pNtk));
263 #endif
264 
265     Abc_FlowRetime_ClearFlows( 1 );
266 
267     pManMR->iteration++;
268   } while( cut != last );
269 
270   // intermediate cleanup (for strashed networks)
271   if (Abc_NtkIsStrash(pNtk)) {
272     Abc_NtkReassignIds( pNtk );
273     pNtk = pManMR->pNtk = Abc_FlowRetime_NtkSilentRestrash( pNtk, 1 );
274   }
275 
276   // print info about initial states
277   if (pManMR->fComputeInitState && pManMR->fVerbose)
278     Abc_FlowRetime_PrintInitStateInfo( pNtk );
279 
280   // (ii) backward retiming loop
281   pManMR->fIsForward = 0;
282 
283   if (!pManMR->fForwardOnly) do {
284     // initializability loop
285     pManMR->iteration = 0;
286 
287     // copy/restore network
288     if (pManMR->fGuaranteeInitState) {
289       if ( pNtk != pNtkCopy )
290         Abc_NtkDelete( pNtk );
291       pNtk = pManMR->pNtk = Abc_FlowRetime_NtkDup( pNtkCopy );
292       vprintf("\trestoring network. regs = %d\n", Abc_NtkLatchNum( pNtk ));
293     }
294 
295     if (pManMR->fComputeInitState) {
296       Abc_FlowRetime_SetupBackwardInit( pNtk );
297     }
298 
299     do {
300       if (pManMR->iteration == pManMR->nMaxIters) break;
301       pManMR->subIteration = 0;
302 
303       vprintf("\tbackward iteration %d\n", pManMR->iteration);
304       last = Abc_NtkLatchNum( pNtk );
305 
306       Abc_FlowRetime_AddInitBias( );
307       Abc_FlowRetime_MarkBlocks( pNtk );
308 
309       if (pManMR->maxDelay) {
310         // timing-constrained loop
311         Abc_FlowRetime_ConstrainConserv( pNtk );
312         while(Abc_FlowRetime_RefineConstraints( )) {
313           pManMR->subIteration++;
314           Abc_FlowRetime_ClearFlows( 0 );
315         }
316       } else {
317         flow = Abc_FlowRetime_PushFlows( pNtk, 1 );
318       }
319 
320       Abc_FlowRetime_RemoveInitBias( );
321       cut = Abc_FlowRetime_ImplementCut( pNtk );
322 
323 #if defined(DEBUG_PRINT_LEVELS)
324       vprintf("\t\tlevels = %d\n", Abc_NtkLevelReverse(pNtk));
325 #endif
326 
327       Abc_FlowRetime_ClearFlows( 1 );
328 
329       pManMR->iteration++;
330     } while( cut != last );
331 
332     // compute initial states
333     if (!pManMR->fComputeInitState) break;
334 
335     if (Abc_FlowRetime_SolveBackwardInit( pNtk )) {
336       if (pManMR->fVerbose) Abc_FlowRetime_PrintInitStateInfo( pNtk );
337       break;
338     } else {
339       if (!pManMR->fGuaranteeInitState) {
340         printf("WARNING: no equivalent init state. setting all initial states to don't-cares\n");
341         Abc_NtkForEachLatch( pNtk, pObj, i ) Abc_LatchSetInitDc( pObj );
342         break;
343       }
344       Abc_FlowRetime_ConstrainInit( );
345     }
346 
347     Abc_NtkDelete(pManMR->pInitNtk);
348     pManMR->pInitNtk = NULL;
349   } while(1);
350 
351 //  assert(!pManMR->fComputeInitState || pManMR->pInitNtk);
352   if (pManMR->fComputeInitState)   Abc_NtkDelete(pManMR->pInitNtk);
353 //  if (pManMR->fGuaranteeInitState) ; /* Abc_NtkDelete(pNtkCopy); note: original ntk deleted later */
354 
355   return pNtk;
356 }
357 
358 
359 /**Function*************************************************************
360 
361   Synopsis    [Pushes latch bubbles outside of box.]
362 
363   Description [If network is an AIG, a fCompl0 is allowed to remain on
364                the BI node.]
365 
366   SideEffects []
367 
368   SeeAlso     []
369 
370 ***********************************************************************/
371 void
Abc_FlowRetime_RemoveLatchBubbles(Abc_Obj_t * pLatch)372 Abc_FlowRetime_RemoveLatchBubbles( Abc_Obj_t * pLatch ) {
373   int bubble = 0;
374   Abc_Ntk_t *pNtk = pManMR->pNtk;
375   Abc_Obj_t *pBi, *pBo, *pInv;
376 
377   pBi = Abc_ObjFanin0(pLatch);
378   pBo = Abc_ObjFanout0(pLatch);
379   assert(!Abc_ObjIsComplement(pBi));
380   assert(!Abc_ObjIsComplement(pBo));
381 
382   // push bubbles on BO into latch box
383   if (Abc_ObjFaninC0(pBo) && Abc_ObjFanoutNum(pBo) > 0) {
384     bubble = 1;
385     if (Abc_LatchIsInit0(pLatch)) Abc_LatchSetInit1(pLatch);
386     else if (Abc_LatchIsInit1(pLatch)) Abc_LatchSetInit0(pLatch);
387   }
388 
389   // absorb bubbles on BI
390   pBi->fCompl0 ^= bubble ^ Abc_ObjFaninC0(pLatch);
391 
392   // convert bubble to INV if not AIG
393   if (!Abc_NtkIsStrash( pNtk ) && Abc_ObjFaninC0(pBi)) {
394     pBi->fCompl0 = 0;
395     pInv = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanin0(pBi) );
396     Abc_ObjPatchFanin( pBi, Abc_ObjFanin0(pBi), pInv );
397   }
398 
399   pBo->fCompl0 = 0;
400   pLatch->fCompl0 = 0;
401 }
402 
403 
404 /**Function*************************************************************
405 
406   Synopsis    [Marks nodes in TFO/TFI of PI/PO.]
407 
408   Description [Sets flow data flag BLOCK appropriately.]
409 
410   SideEffects []
411 
412   SeeAlso     []
413 
414 ***********************************************************************/
415 void
Abc_FlowRetime_MarkBlocks(Abc_Ntk_t * pNtk)416 Abc_FlowRetime_MarkBlocks( Abc_Ntk_t * pNtk ) {
417   int i;
418   Abc_Obj_t *pObj;
419 
420   if (pManMR->fIsForward){
421     // --- forward retiming : block TFO of inputs
422 
423     // mark the frontier
424     Abc_NtkForEachPo( pNtk, pObj, i )
425       pObj->fMarkA = 1;
426     Abc_NtkForEachLatch( pNtk, pObj, i )
427       {
428         pObj->fMarkA = 1;
429       }
430     // mark the nodes reachable from the PIs
431     Abc_NtkForEachPi( pNtk, pObj, i )
432       Abc_NtkMarkCone_rec( pObj, pManMR->fIsForward );
433   } else {
434     // --- backward retiming : block TFI of outputs
435 
436     // mark the frontier
437     Abc_NtkForEachPi( pNtk, pObj, i )
438       pObj->fMarkA = 1;
439     Abc_NtkForEachLatch( pNtk, pObj, i )
440       {
441         pObj->fMarkA = 1;
442       }
443     // mark the nodes reachable from the POs
444     Abc_NtkForEachPo( pNtk, pObj, i )
445       Abc_NtkMarkCone_rec( pObj, pManMR->fIsForward );
446     // block constant nodes (if enabled)
447     if (pManMR->fBlockConst) {
448       Abc_NtkForEachObj( pNtk, pObj, i )
449         if ((Abc_NtkIsStrash(pNtk) && Abc_AigNodeIsConst(pObj)) ||
450             (!Abc_NtkIsStrash(pNtk) && Abc_NodeIsConst(pObj))) {
451           FSET(pObj, BLOCK);
452         }
453     }
454   }
455 
456   // copy marks
457   Abc_NtkForEachObj( pNtk, pObj, i ) {
458     if (pObj->fMarkA) {
459       pObj->fMarkA = 0;
460       if (!Abc_ObjIsLatch(pObj) /* && !Abc_ObjIsPi(pObj) */ )
461         FSET(pObj, BLOCK);
462     }
463   }
464 }
465 
466 
467 /**Function*************************************************************
468 
469   Synopsis    [Computes maximum flow.]
470 
471   Description []
472 
473   SideEffects [Leaves VISITED flags on source-reachable nodes.]
474 
475   SeeAlso     []
476 
477 ***********************************************************************/
478 int
Abc_FlowRetime_PushFlows(Abc_Ntk_t * pNtk,int fVerbose)479 Abc_FlowRetime_PushFlows( Abc_Ntk_t * pNtk, int fVerbose ) {
480   int i, j, flow = 0, last, srcDist = 0;
481   Abc_Obj_t   *pObj, *pObj2;
482 //  int clk = clock();
483 
484   pManMR->constraintMask |= BLOCK;
485 
486   pManMR->fSinkDistTerminate = 0;
487   dfsfast_preorder( pNtk );
488 
489   // (i) fast max-flow computation
490   while(!pManMR->fSinkDistTerminate && srcDist < MAX_DIST) {
491     srcDist = MAX_DIST;
492     Abc_NtkForEachLatch( pNtk, pObj, i )
493       if (FDATA(pObj)->e_dist)
494         srcDist = MIN(srcDist, (int)FDATA(pObj)->e_dist);
495 
496     Abc_NtkForEachLatch( pNtk, pObj, i ) {
497       if (srcDist == (int)FDATA(pObj)->e_dist &&
498           dfsfast_e( pObj, NULL )) {
499 #ifdef DEBUG_PRINT_FLOWS
500         printf("\n\n");
501 #endif
502         flow++;
503       }
504     }
505   }
506 
507   if (fVerbose) vprintf("\t\tmax-flow1 = %d \t", flow);
508 
509   // (ii) complete max-flow computation
510   // also, marks source-reachable nodes
511   do {
512     last = flow;
513     Abc_NtkForEachLatch( pNtk, pObj, i ) {
514       if (dfsplain_e( pObj, NULL )) {
515 #ifdef DEBUG_PRINT_FLOWS
516         printf("\n\n");
517 #endif
518         flow++;
519         Abc_NtkForEachObj( pNtk, pObj2, j )
520           FUNSET( pObj2, VISITED );
521       }
522     }
523   } while (flow > last);
524 
525   if (fVerbose) vprintf("max-flow2 = %d\n", flow);
526 
527 //  PRT( "time", clock() - clk );
528   return flow;
529 }
530 
531 
532 /**Function*************************************************************
533 
534   Synopsis    [Restores latch boxes.]
535 
536   Description [Latchless BI/BO nodes are removed.  Latch boxes are
537                restored around remaining latches.]
538 
539   SideEffects [Deletes nodes as appropriate.]
540 
541   SeeAlso     []
542 
543 ***********************************************************************/
544 void
Abc_FlowRetime_FixLatchBoxes(Abc_Ntk_t * pNtk,Vec_Ptr_t * vBoxIns)545 Abc_FlowRetime_FixLatchBoxes( Abc_Ntk_t *pNtk, Vec_Ptr_t *vBoxIns ) {
546   int i;
547   Abc_Obj_t *pObj, *pBo = NULL, *pBi = NULL;
548   Vec_Ptr_t *vFreeBi = Vec_PtrAlloc( 100 );
549   Vec_Ptr_t *vFreeBo = Vec_PtrAlloc( 100 );
550 
551   // 1. remove empty bi/bo pairs
552   while(Vec_PtrSize( vBoxIns )) {
553     pBi = (Abc_Obj_t *)Vec_PtrPop( vBoxIns );
554     assert(Abc_ObjIsBi(pBi));
555     assert(Abc_ObjFanoutNum(pBi) == 1);
556     // APH: broken by bias nodes assert(Abc_ObjFaninNum(pBi) == 1);
557     pBo = Abc_ObjFanout0(pBi);
558     assert(!Abc_ObjFaninC0(pBo));
559 
560     if (Abc_ObjIsBo(pBo)) {
561       // an empty bi/bo pair
562 
563       Abc_ObjRemoveFanins( pBo );
564       // transfer complement from BI, if present
565       assert(!Abc_ObjIsComplement(Abc_ObjFanin0(pBi)));
566       Abc_ObjBetterTransferFanout( pBo, Abc_ObjFanin0(pBi), Abc_ObjFaninC0(pBi) );
567 
568       Abc_ObjRemoveFanins( pBi );
569       pBi->fCompl0 = 0;
570       Vec_PtrPush( vFreeBi, pBi );
571       Vec_PtrPush( vFreeBo, pBo );
572 
573       // free names
574       if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pBi)))
575         Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pBi));
576       if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pBo)))
577         Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pBo));
578 
579       // check for complete detachment
580       assert(Abc_ObjFaninNum(pBi) == 0);
581       assert(Abc_ObjFanoutNum(pBi) == 0);
582       assert(Abc_ObjFaninNum(pBo) == 0);
583       assert(Abc_ObjFanoutNum(pBo) == 0);
584     } else if (Abc_ObjIsLatch(pBo)) {
585     } else {
586       Abc_ObjPrint(stdout, pBi);
587       Abc_ObjPrint(stdout, pBo);
588       assert(0);
589     }
590   }
591 
592   // 2. add bi/bos as necessary for latches
593   Abc_NtkForEachLatch( pNtk, pObj, i ) {
594     assert(Abc_ObjFaninNum(pObj) == 1);
595     if (Abc_ObjFanoutNum(pObj))
596       pBo = Abc_ObjFanout0(pObj);
597     else pBo = NULL;
598     pBi = Abc_ObjFanin0(pObj);
599 
600     // add BO
601     if (!pBo || !Abc_ObjIsBo(pBo)) {
602       pBo = (Abc_Obj_t *)Vec_PtrPop( vFreeBo );
603       if (Abc_ObjFanoutNum(pObj))  Abc_ObjTransferFanout( pObj, pBo );
604       Abc_ObjAddFanin( pBo, pObj );
605     }
606     // add BI
607     if (!Abc_ObjIsBi(pBi)) {
608       pBi = (Abc_Obj_t *)Vec_PtrPop( vFreeBi );
609       assert(Abc_ObjFaninNum(pBi) == 0);
610       Abc_ObjAddFanin( pBi, Abc_ObjFanin0(pObj) );
611       pBi->fCompl0 = pObj->fCompl0;
612       Abc_ObjRemoveFanins( pObj );
613       Abc_ObjAddFanin( pObj, pBi );
614     }
615   }
616 
617   // delete remaining BIs and BOs
618   while(Vec_PtrSize( vFreeBi )) {
619     pObj = (Abc_Obj_t *)Vec_PtrPop( vFreeBi );
620     Abc_NtkDeleteObj( pObj );
621   }
622   while(Vec_PtrSize( vFreeBo )) {
623     pObj = (Abc_Obj_t *)Vec_PtrPop( vFreeBo );
624     Abc_NtkDeleteObj( pObj );
625   }
626 
627 #if defined(DEBUG_CHECK)
628   Abc_NtkForEachObj( pNtk, pObj, i ) {
629     if (Abc_ObjIsBo(pObj)) {
630       assert(Abc_ObjFaninNum(pObj) == 1);
631       assert(Abc_ObjIsLatch(Abc_ObjFanin0(pObj)));
632     }
633     if (Abc_ObjIsBi(pObj)) {
634       assert(Abc_ObjFaninNum(pObj) == 1);
635       assert(Abc_ObjFanoutNum(pObj) == 1);
636       assert(Abc_ObjIsLatch(Abc_ObjFanout0(pObj)));
637     }
638     if (Abc_ObjIsLatch(pObj)) {
639       assert(Abc_ObjFanoutNum(pObj) == 1);
640       assert(Abc_ObjFaninNum(pObj) == 1);
641     }
642   }
643 #endif
644 
645   Vec_PtrFree( vFreeBi );
646   Vec_PtrFree( vFreeBo );
647 }
648 
649 
650 /**Function*************************************************************
651 
652   Synopsis    [Checks register count along all combinational paths.]
653 
654   Description []
655 
656   SideEffects []
657 
658   SeeAlso     []
659 
660 ***********************************************************************/
661 void
Abc_FlowRetime_VerifyPathLatencies(Abc_Ntk_t * pNtk)662 Abc_FlowRetime_VerifyPathLatencies( Abc_Ntk_t * pNtk ) {
663   int i;
664   Abc_Obj_t *pObj;
665   fPathError = 0;
666 
667   vprintf("\t\tVerifying latency along all paths...");
668 
669   Abc_NtkForEachObj( pNtk, pObj, i ) {
670     if (Abc_ObjIsBo(pObj)) {
671       Abc_FlowRetime_VerifyPathLatencies_rec( pObj, 0 );
672     } else if (!pManMR->fIsForward && Abc_ObjIsPi(pObj)) {
673       Abc_FlowRetime_VerifyPathLatencies_rec( pObj, 0 );
674     }
675 
676     if (fPathError) {
677       if (Abc_ObjFaninNum(pObj) > 0) {
678         printf("fanin ");
679         print_node(Abc_ObjFanin0(pObj));
680       }
681       printf("\n");
682       exit(0);
683     }
684   }
685 
686   vprintf(" ok\n");
687 
688   Abc_NtkForEachObj( pNtk, pObj, i ) {
689     pObj->fMarkA = 0;
690     pObj->fMarkB = 0;
691     pObj->fMarkC = 0;
692   }
693 }
694 
695 
696 int
Abc_FlowRetime_VerifyPathLatencies_rec(Abc_Obj_t * pObj,int markD)697 Abc_FlowRetime_VerifyPathLatencies_rec( Abc_Obj_t * pObj, int markD ) {
698   int i, j;
699   Abc_Obj_t *pNext;
700   int fCare = 0;
701   int markC = pObj->fMarkC;
702 
703   if (!pObj->fMarkB) {
704     pObj->fMarkB = 1; // visited
705 
706     if (Abc_ObjIsLatch(pObj))
707       markC = 1;      // latch in output
708 
709     if (!pManMR->fIsForward && !Abc_ObjIsPo(pObj) && !Abc_ObjFanoutNum(pObj))
710       return -1; // dangling non-PO outputs : don't care what happens
711 
712     Abc_ObjForEachFanout( pObj, pNext, i ) {
713       // reached end of cycle?
714       if ( Abc_ObjIsBo(pNext) ||
715            (pManMR->fIsForward && Abc_ObjIsPo(pNext)) ) {
716         if (!markD && !Abc_ObjIsLatch(pObj)) {
717           printf("\nERROR: no-latch path (end)\n");
718           print_node(pNext);
719           printf("\n");
720           fPathError = 1;
721         }
722       } else if (!pManMR->fIsForward && Abc_ObjIsPo(pNext)) {
723         if (markD || Abc_ObjIsLatch(pObj)) {
724           printf("\nERROR: extra-latch path to outputs\n");
725           print_node(pNext);
726           printf("\n");
727           fPathError = 1;
728         }
729       } else {
730         j = Abc_FlowRetime_VerifyPathLatencies_rec( pNext, markD || Abc_ObjIsLatch(pObj) );
731         if (j >= 0) {
732           markC |= j;
733           fCare = 1;
734         }
735       }
736 
737       if (fPathError) {
738         print_node(pObj);
739         printf("\n");
740         return 0;
741       }
742     }
743   }
744 
745   if (!fCare) return -1;
746 
747   if (markC && markD) {
748     printf("\nERROR: mult-latch path\n");
749     print_node(pObj);
750     printf("\n");
751     fPathError = 1;
752   }
753   if (!markC && !markD) {
754     printf("\nERROR: no-latch path (inter)\n");
755     print_node(pObj);
756     printf("\n");
757     fPathError = 1;
758   }
759 
760   return (pObj->fMarkC = markC);
761 }
762 
763 
764 /**Function*************************************************************
765 
766   Synopsis    [Copies initial state from latches to BO nodes.]
767 
768   Description [Initial states are marked on BO nodes with INIT_0 and
769                INIT_1 flags in their Flow_Data structures.]
770 
771   SideEffects []
772 
773   SeeAlso     []
774 
775 ***********************************************************************/
776 void
Abc_FlowRetime_CopyInitState(Abc_Obj_t * pSrc,Abc_Obj_t * pDest)777 Abc_FlowRetime_CopyInitState( Abc_Obj_t * pSrc, Abc_Obj_t * pDest ) {
778   Abc_Obj_t *pObj;
779 
780   if (!pManMR->fComputeInitState) return;
781 
782   assert(Abc_ObjIsLatch(pSrc));
783   assert(Abc_ObjFanin0(pDest) == pSrc);
784   assert(!Abc_ObjFaninC0(pDest));
785 
786   FUNSET(pDest, INIT_CARE);
787   if (Abc_LatchIsInit0(pSrc)) {
788     FSET(pDest, INIT_0);
789   } else if (Abc_LatchIsInit1(pSrc)) {
790     FSET(pDest, INIT_1);
791   }
792 
793   if (!pManMR->fIsForward) {
794     pObj = (Abc_Obj_t*)Abc_ObjData(pSrc);
795     assert(Abc_ObjIsPi(pObj));
796     FDATA(pDest)->pInitObj = pObj;
797   }
798 }
799 
800 
801 /**Function*************************************************************
802 
803   Synopsis    [Implements min-cut.]
804 
805   Description [Requires source-reachable nodes to be marked VISITED.]
806 
807   SideEffects []
808 
809   SeeAlso     []
810 
811 ***********************************************************************/
812 int
Abc_FlowRetime_ImplementCut(Abc_Ntk_t * pNtk)813 Abc_FlowRetime_ImplementCut( Abc_Ntk_t * pNtk ) {
814   int i, j, cut = 0, unmoved = 0;
815   Abc_Obj_t *pObj, *pReg, *pNext, *pBo = NULL, *pBi = NULL;
816   Vec_Ptr_t *vFreeRegs = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
817   Vec_Ptr_t *vBoxIns = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
818   Vec_Ptr_t *vMove = Vec_PtrAlloc( 100 );
819 
820   // remove latches from netlist
821   Abc_NtkForEachLatch( pNtk, pObj, i ) {
822     pBo = Abc_ObjFanout0(pObj);
823     pBi = Abc_ObjFanin0(pObj);
824     assert(Abc_ObjIsBo(pBo) && Abc_ObjIsBi(pBi));
825     Vec_PtrPush( vBoxIns, pBi );
826 
827     // copy initial state values to BO
828     Abc_FlowRetime_CopyInitState( pObj, pBo );
829 
830     // re-use latch elsewhere
831     Vec_PtrPush( vFreeRegs, pObj );
832     FSET(pBo, CROSS_BOUNDARY);
833 
834     // cut out of netlist
835     Abc_ObjPatchFanin( pBo, pObj, pBi );
836     Abc_ObjRemoveFanins( pObj );
837 
838     // free name
839     if (Nm_ManFindNameById(pNtk->pManName, Abc_ObjId(pObj)))
840       Nm_ManDeleteIdName( pNtk->pManName, Abc_ObjId(pObj));
841   }
842 
843   // insert latches into netlist
844   Abc_NtkForEachObj( pNtk, pObj, i ) {
845     if (Abc_ObjIsLatch( pObj )) continue;
846     if (FTEST(pObj, BIAS_NODE)) continue;
847 
848     // a latch is required on every node that lies across the min-cit
849     assert(!pManMR->fIsForward || !FTEST(pObj, VISITED_E) || FTEST(pObj, VISITED_R));
850     if (FTEST(pObj, VISITED_R) && !FTEST(pObj, VISITED_E)) {
851       assert(FTEST(pObj, FLOW));
852 
853       // count size of cut
854       cut++;
855       if ((pManMR->fIsForward && Abc_ObjIsBo(pObj)) ||
856           (!pManMR->fIsForward && Abc_ObjIsBi(pObj)))
857         unmoved++;
858 
859       // only insert latch between fanouts that lie across min-cut
860       // some fanout paths may be cut at deeper points
861       Abc_ObjForEachFanout( pObj, pNext, j )
862         if (Abc_FlowRetime_IsAcrossCut( pObj, pNext ))
863           Vec_PtrPush(vMove, pNext);
864 
865       // check that move-set is non-zero
866       if (Vec_PtrSize(vMove) == 0)
867         print_node(pObj);
868       assert(Vec_PtrSize(vMove) > 0);
869 
870       // insert one of re-useable registers
871       assert(Vec_PtrSize( vFreeRegs ));
872       pReg = (Abc_Obj_t *)Vec_PtrPop( vFreeRegs );
873 
874       Abc_ObjAddFanin(pReg, pObj);
875       while(Vec_PtrSize( vMove )) {
876         pNext = (Abc_Obj_t *)Vec_PtrPop( vMove );
877         Abc_ObjPatchFanin( pNext, pObj, pReg );
878         if (Abc_ObjIsBi(pNext)) assert(Abc_ObjFaninNum(pNext) == 1);
879 
880       }
881       // APH: broken by bias nodes  if (Abc_ObjIsBi(pObj)) assert(Abc_ObjFaninNum(pObj) == 1);
882     }
883   }
884 
885 #if defined(DEBUG_CHECK)
886   Abc_FlowRetime_VerifyPathLatencies( pNtk );
887 #endif
888 
889   // delete remaining latches
890   while(Vec_PtrSize( vFreeRegs )) {
891     pReg = (Abc_Obj_t *)Vec_PtrPop( vFreeRegs );
892     Abc_NtkDeleteObj( pReg );
893   }
894 
895   // update initial states
896   Abc_FlowRetime_UpdateLags( );
897   Abc_FlowRetime_InitState( pNtk );
898 
899   // restore latch boxes
900   Abc_FlowRetime_FixLatchBoxes( pNtk, vBoxIns );
901 
902   Vec_PtrFree( vFreeRegs );
903   Vec_PtrFree( vMove );
904   Vec_PtrFree( vBoxIns );
905 
906   vprintf("\t\tmin-cut = %d (unmoved = %d)\n", cut, unmoved);
907   return cut;
908 }
909 
910 
911 /**Function*************************************************************
912 
913   Synopsis    [Adds dummy fanin.]
914 
915   Description []
916 
917   SideEffects []
918 
919   SeeAlso     []
920 
921 ***********************************************************************/
922 void
Abc_FlowRetime_AddDummyFanin(Abc_Obj_t * pObj)923 Abc_FlowRetime_AddDummyFanin( Abc_Obj_t * pObj ) {
924   Abc_Ntk_t *pNtk = Abc_ObjNtk( pObj );
925 
926   if (Abc_NtkIsStrash(pNtk))
927     Abc_ObjAddFanin(pObj, Abc_AigConst1( pNtk ));
928   else
929     Abc_ObjAddFanin(pObj, Abc_NtkCreateNodeConst0( pNtk ));
930 }
931 
932 
933 /**Function*************************************************************
934 
935   Synopsis    [Prints information about a node.]
936 
937   Description [Debuging.]
938 
939   SideEffects []
940 
941   SeeAlso     []
942 
943 ***********************************************************************/
944 void
print_node(Abc_Obj_t * pObj)945 print_node(Abc_Obj_t *pObj) {
946   int i;
947   Abc_Obj_t * pNext;
948   char m[6];
949 
950   m[0] = 0;
951   if (pObj->fMarkA)
952     strcat(m, "A");
953   if (pObj->fMarkB)
954     strcat(m, "B");
955   if (pObj->fMarkC)
956     strcat(m, "C");
957 
958   printf("node %d type=%d lev=%d tedge=%d (%x%s) fanouts {", Abc_ObjId(pObj), Abc_ObjType(pObj),
959          pObj->Level, Vec_PtrSize(FTIMEEDGES(pObj)), FDATA(pObj)->mark, m);
960   Abc_ObjForEachFanout( pObj, pNext, i )
961     printf("%d[%d](%d),", Abc_ObjId(pNext), Abc_ObjType(pNext), FDATA(pNext)->mark);
962   printf("} fanins {");
963   Abc_ObjForEachFanin( pObj, pNext, i )
964     printf("%d[%d](%d),", Abc_ObjId(pNext), Abc_ObjType(pNext), FDATA(pNext)->mark);
965   printf("}\n");
966 }
967 
968 void
print_node2(Abc_Obj_t * pObj)969 print_node2(Abc_Obj_t *pObj) {
970   int i;
971   Abc_Obj_t * pNext;
972   char m[6];
973 
974   m[0] = 0;
975   if (pObj->fMarkA)
976     strcat(m, "A");
977   if (pObj->fMarkB)
978     strcat(m, "B");
979   if (pObj->fMarkC)
980     strcat(m, "C");
981 
982   printf("node %d type=%d %s fanouts {", Abc_ObjId(pObj), Abc_ObjType(pObj), m);
983   Abc_ObjForEachFanout( pObj, pNext, i )
984     printf("%d ,", Abc_ObjId(pNext));
985   printf("} fanins {");
986   Abc_ObjForEachFanin( pObj, pNext, i )
987     printf("%d ,", Abc_ObjId(pNext));
988   printf("} ");
989 }
990 
991 void
print_node3(Abc_Obj_t * pObj)992 print_node3(Abc_Obj_t *pObj) {
993   int i;
994   Abc_Obj_t * pNext;
995   char m[6];
996 
997   m[0] = 0;
998   if (pObj->fMarkA)
999     strcat(m, "A");
1000   if (pObj->fMarkB)
1001     strcat(m, "B");
1002   if (pObj->fMarkC)
1003     strcat(m, "C");
1004 
1005   printf("\nnode %d type=%d mark=%d %s\n", Abc_ObjId(pObj), Abc_ObjType(pObj), FDATA(pObj)->mark, m);
1006   printf("fanouts\n");
1007   Abc_ObjForEachFanout( pObj, pNext, i ) {
1008     print_node(pNext);
1009     printf("\n");
1010   }
1011   printf("fanins\n");
1012   Abc_ObjForEachFanin( pObj, pNext, i ) {
1013     print_node(pNext);
1014     printf("\n");
1015   }
1016 }
1017 
1018 
1019 /**Function*************************************************************
1020 
1021   Synopsis    [Transfers fanout.]
1022 
1023   Description [Does not produce an error if there is no fanout.
1024                Complements as necessary.]
1025 
1026   SideEffects []
1027 
1028   SeeAlso     []
1029 
1030 ***********************************************************************/
1031 void
Abc_ObjBetterTransferFanout(Abc_Obj_t * pFrom,Abc_Obj_t * pTo,int complement)1032 Abc_ObjBetterTransferFanout( Abc_Obj_t * pFrom, Abc_Obj_t * pTo, int complement ) {
1033   Abc_Obj_t *pNext;
1034 
1035   while(Abc_ObjFanoutNum(pFrom) > 0) {
1036     pNext = Abc_ObjFanout0(pFrom);
1037     Abc_ObjPatchFanin( pNext, pFrom, Abc_ObjNotCond(pTo, complement) );
1038   }
1039 }
1040 
1041 
1042 /**Function*************************************************************
1043 
1044   Synopsis    [Returns true is a connection spans the min-cut.]
1045 
1046   Description [pNext is a direct fanout of pObj.]
1047 
1048   SideEffects []
1049 
1050   SeeAlso     []
1051 
1052 ***********************************************************************/
1053 int
Abc_FlowRetime_IsAcrossCut(Abc_Obj_t * pObj,Abc_Obj_t * pNext)1054 Abc_FlowRetime_IsAcrossCut( Abc_Obj_t *pObj, Abc_Obj_t *pNext ) {
1055 
1056   if (FTEST(pObj, VISITED_R) && !FTEST(pObj, VISITED_E)) {
1057     if (pManMR->fIsForward) {
1058       if (!FTEST(pNext, VISITED_R) ||
1059           (FTEST(pNext, BLOCK_OR_CONS) & pManMR->constraintMask)||
1060           FTEST(pNext, CROSS_BOUNDARY) ||
1061           Abc_ObjIsLatch(pNext))
1062         return 1;
1063     } else {
1064       if (FTEST(pNext, VISITED_E) ||
1065           FTEST(pNext, CROSS_BOUNDARY))
1066         return 1;
1067     }
1068   }
1069 
1070   return 0;
1071 }
1072 
1073 
1074 /**Function*************************************************************
1075 
1076   Synopsis    [Resets flow problem]
1077 
1078   Description [If fClearAll is true, all marks will be cleared; this is
1079                typically appropriate after the circuit structure has
1080                been modified.]
1081 
1082   SideEffects []
1083 
1084   SeeAlso     []
1085 
1086 ***********************************************************************/
Abc_FlowRetime_ClearFlows(int fClearAll)1087 void Abc_FlowRetime_ClearFlows( int fClearAll ) {
1088   int i;
1089 
1090   if (fClearAll)
1091     memset(pManMR->pDataArray, 0, sizeof(Flow_Data_t)*pManMR->nNodes);
1092   else {
1093     // clear only data related to flow problem
1094     for(i=0; i<pManMR->nNodes; i++) {
1095       pManMR->pDataArray[i].mark &= ~(VISITED | FLOW );
1096       pManMR->pDataArray[i].e_dist = 0;
1097       pManMR->pDataArray[i].r_dist = 0;
1098       pManMR->pDataArray[i].pred = NULL;
1099     }
1100   }
1101 }
1102 
1103 
1104 /**Function*************************************************************
1105 
1106   Synopsis    [Duplicates network.]
1107 
1108   Description [Duplicates any type of network. Preserves copy data.]
1109 
1110   SideEffects []
1111 
1112   SeeAlso     []
1113 
1114 ***********************************************************************/
Abc_FlowRetime_NtkDup(Abc_Ntk_t * pNtk)1115 static Abc_Ntk_t* Abc_FlowRetime_NtkDup( Abc_Ntk_t * pNtk ) {
1116   Abc_Ntk_t *pNtkCopy;
1117   Abc_Obj_t *pObj, *pObjCopy, *pNext, *pNextCopy;
1118   int i, j;
1119 
1120   pNtkCopy = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 );
1121   pNtkCopy->pName = Extra_UtilStrsav(pNtk->pName);
1122   pNtkCopy->pSpec = Extra_UtilStrsav(pNtk->pSpec);
1123 
1124   // copy each object
1125   Abc_NtkForEachObj( pNtk, pObj, i) {
1126 
1127     if (Abc_NtkIsStrash( pNtk ) && Abc_AigNodeIsConst( pObj ))
1128       pObjCopy = Abc_AigConst1( pNtkCopy );
1129     else
1130       pObjCopy = Abc_NtkDupObj( pNtkCopy, pObj, 0 );
1131 
1132     FDATA( pObj )->pCopy = pObjCopy;
1133     FDATA( pObj )->mark = 0;
1134 
1135     // assert( pManMR->fIsForward || pObj->Id == pObjCopy->Id );
1136 
1137     // copy complementation
1138     pObjCopy->fCompl0 = pObj->fCompl0;
1139     pObjCopy->fCompl1 = pObj->fCompl1;
1140     pObjCopy->fPhase = pObj->fPhase;
1141   }
1142 
1143   // connect fanin
1144   Abc_NtkForEachObj( pNtk, pObj, i) {
1145     pObjCopy = FDATA(pObj)->pCopy;
1146     assert(pObjCopy);
1147     Abc_ObjForEachFanin( pObj, pNext, j ) {
1148       pNextCopy = FDATA(pNext)->pCopy;
1149       assert(pNextCopy);
1150       assert(pNext->Type == pNextCopy->Type);
1151 
1152       Abc_ObjAddFanin(pObjCopy, pNextCopy);
1153     }
1154   }
1155 
1156 #if defined(DEBUG_CHECK) || 1
1157   Abc_NtkForEachObj( pNtk, pObj, i) {
1158     pObjCopy = FDATA(pObj)->pCopy;
1159     assert( Abc_ObjFanoutNum( pObj ) ==  Abc_ObjFanoutNum( pObjCopy ) );
1160     assert( Abc_ObjFaninNum( pObj ) ==  Abc_ObjFaninNum( pObjCopy ) );
1161   }
1162 #endif
1163 
1164   assert(Abc_NtkObjNum( pNtk )   == Abc_NtkObjNum( pNtkCopy ) );
1165   assert(Abc_NtkLatchNum( pNtk ) == Abc_NtkLatchNum( pNtkCopy ) );
1166   assert(Abc_NtkPoNum( pNtk )    == Abc_NtkPoNum( pNtkCopy ) );
1167   assert(Abc_NtkPiNum( pNtk )    == Abc_NtkPiNum( pNtkCopy ) );
1168 
1169   return pNtkCopy;
1170 }
1171 
1172 
1173 /**Function*************************************************************
1174 
1175   Synopsis    [Silent restrash.]
1176 
1177   Description [Same functionality as Abc_NtkRestrash but w/o warnings.]
1178 
1179   SideEffects []
1180 
1181   SeeAlso     []
1182 
1183 ***********************************************************************/
Abc_FlowRetime_NtkSilentRestrash(Abc_Ntk_t * pNtk,int fCleanup)1184 Abc_Ntk_t * Abc_FlowRetime_NtkSilentRestrash( Abc_Ntk_t * pNtk, int fCleanup )
1185 {
1186     Abc_Ntk_t * pNtkAig;
1187     Abc_Obj_t * pObj;
1188     int i, nNodes;//, RetValue;
1189     assert( Abc_NtkIsStrash(pNtk) );
1190     // start the new network (constants and CIs of the old network will point to the their counterparts in the new network)
1191     pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
1192     // restrash the nodes (assuming a topological order of the old network)
1193     Abc_NtkForEachNode( pNtk, pObj, i )
1194         pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pNtkAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
1195     // finalize the network
1196     Abc_NtkFinalize( pNtk, pNtkAig );
1197     // perform cleanup if requested
1198     if ( fCleanup )
1199       nNodes = Abc_AigCleanup((Abc_Aig_t *)pNtkAig->pManFunc);
1200     // duplicate EXDC
1201     if ( pNtk->pExdc )
1202       pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
1203     // make sure everything is okay
1204     if ( !Abc_NtkCheck( pNtkAig ) )
1205       {
1206         printf( "Abc_NtkStrash: The network check has failed.\n" );
1207         Abc_NtkDelete( pNtkAig );
1208         return NULL;
1209       }
1210     return pNtkAig;
1211 }
1212 
1213 
1214 
1215 /**Function*************************************************************
1216 
1217   Synopsis    [Updates lag values.]
1218 
1219   Description [Recursive.  Forward retiming.]
1220 
1221   SideEffects []
1222 
1223   SeeAlso     []
1224 
1225 ***********************************************************************/
1226 void
Abc_FlowRetime_UpdateLags_forw_rec(Abc_Obj_t * pObj)1227 Abc_FlowRetime_UpdateLags_forw_rec( Abc_Obj_t *pObj ) {
1228   Abc_Obj_t *pNext;
1229   int i;
1230 
1231   assert(!Abc_ObjIsPi(pObj));
1232   assert(!Abc_ObjIsLatch(pObj));
1233 
1234   if (Abc_ObjIsBo(pObj)) return;
1235   if (Abc_NodeIsTravIdCurrent(pObj)) return;
1236 
1237   Abc_NodeSetTravIdCurrent(pObj);
1238 
1239   if (Abc_ObjIsNode(pObj)) {
1240     Abc_FlowRetime_SetLag( pObj, -1+Abc_FlowRetime_GetLag(pObj) );
1241   }
1242 
1243   Abc_ObjForEachFanin( pObj, pNext, i ) {
1244     Abc_FlowRetime_UpdateLags_forw_rec( pNext );
1245   }
1246 }
1247 
1248 
1249 /**Function*************************************************************
1250 
1251   Synopsis    [Updates lag values.]
1252 
1253   Description [Recursive.  Backward retiming.]
1254 
1255   SideEffects []
1256 
1257   SeeAlso     []
1258 
1259 ***********************************************************************/
1260 void
Abc_FlowRetime_UpdateLags_back_rec(Abc_Obj_t * pObj)1261 Abc_FlowRetime_UpdateLags_back_rec( Abc_Obj_t *pObj ) {
1262   Abc_Obj_t *pNext;
1263   int i;
1264 
1265   assert(!Abc_ObjIsPo(pObj));
1266   assert(!Abc_ObjIsLatch(pObj));
1267 
1268   if (Abc_ObjIsBo(pObj)) return;
1269   if (Abc_NodeIsTravIdCurrent(pObj)) return;
1270 
1271   Abc_NodeSetTravIdCurrent(pObj);
1272 
1273   if (Abc_ObjIsNode(pObj)) {
1274     Abc_FlowRetime_SetLag( pObj, 1+Abc_FlowRetime_GetLag(pObj) );
1275   }
1276 
1277   Abc_ObjForEachFanout( pObj, pNext, i ) {
1278     Abc_FlowRetime_UpdateLags_back_rec( pNext );
1279   }
1280 }
1281 
1282 /**Function*************************************************************
1283 
1284   Synopsis    [Updates lag values.]
1285 
1286   Description []
1287 
1288   SideEffects []
1289 
1290   SeeAlso     []
1291 
1292 ***********************************************************************/
1293 void
Abc_FlowRetime_UpdateLags()1294 Abc_FlowRetime_UpdateLags( ) {
1295   Abc_Obj_t *pObj, *pNext;
1296   int i, j;
1297 
1298   Abc_NtkIncrementTravId( pManMR->pNtk );
1299 
1300   Abc_NtkForEachLatch( pManMR->pNtk, pObj, i )
1301     if (pManMR->fIsForward) {
1302       Abc_ObjForEachFanin( pObj, pNext, j )
1303         Abc_FlowRetime_UpdateLags_forw_rec( pNext );
1304     } else {
1305       Abc_ObjForEachFanout( pObj, pNext, j )
1306         Abc_FlowRetime_UpdateLags_back_rec( pNext );
1307     }
1308 }
1309 
1310 
1311 /**Function*************************************************************
1312 
1313   Synopsis    [Gets lag value of a node.]
1314 
1315   Description []
1316 
1317   SideEffects []
1318 
1319   SeeAlso     []
1320 
1321 ***********************************************************************/
1322 int
Abc_FlowRetime_GetLag(Abc_Obj_t * pObj)1323 Abc_FlowRetime_GetLag( Abc_Obj_t *pObj ) {
1324   assert( !Abc_ObjIsLatch(pObj) );
1325   assert( (int)Abc_ObjId(pObj) < Vec_IntSize(pManMR->vLags) );
1326 
1327   return Vec_IntEntry(pManMR->vLags, Abc_ObjId(pObj));
1328 }
1329 
1330 /**Function*************************************************************
1331 
1332   Synopsis    [Sets lag value of a node.]
1333 
1334   Description []
1335 
1336   SideEffects []
1337 
1338   SeeAlso     []
1339 
1340 ***********************************************************************/
1341 void
Abc_FlowRetime_SetLag(Abc_Obj_t * pObj,int lag)1342 Abc_FlowRetime_SetLag( Abc_Obj_t *pObj, int lag ) {
1343   assert( Abc_ObjIsNode(pObj) );
1344   assert( (int)Abc_ObjId(pObj) < Vec_IntSize(pManMR->vLags) );
1345 
1346   Vec_IntWriteEntry(pManMR->vLags, Abc_ObjId(pObj), lag);
1347 }
1348 
1349 
Abc_ObjPrintNeighborhood_rec(Abc_Obj_t * pObj,Vec_Ptr_t * vNodes,int depth)1350 static void Abc_ObjPrintNeighborhood_rec( Abc_Obj_t *pObj, Vec_Ptr_t *vNodes, int depth ) {
1351   Abc_Obj_t *pObj2;
1352   int i;
1353 
1354   if (pObj->fMarkC || depth < 0) return;
1355 
1356   pObj->fMarkC = 1;
1357   Vec_PtrPush( vNodes, pObj );
1358 
1359   Abc_ObjPrint( stdout, pObj );
1360 
1361   Abc_ObjForEachFanout(pObj, pObj2, i) {
1362     Abc_ObjPrintNeighborhood_rec( pObj2, vNodes, depth-1 );
1363   }
1364   Abc_ObjForEachFanin(pObj, pObj2, i) {
1365     Abc_ObjPrintNeighborhood_rec( pObj2, vNodes, depth-1 );
1366   }
1367 }
1368 
Abc_ObjPrintNeighborhood(Abc_Obj_t * pObj,int depth)1369 void Abc_ObjPrintNeighborhood( Abc_Obj_t *pObj, int depth ) {
1370   Vec_Ptr_t *vNodes = Vec_PtrAlloc(100);
1371   Abc_Obj_t *pObj2;
1372 
1373   Abc_ObjPrintNeighborhood_rec( pObj, vNodes, depth );
1374 
1375   while(Vec_PtrSize(vNodes)) {
1376     pObj2 = (Abc_Obj_t*)Vec_PtrPop(vNodes);
1377     pObj2->fMarkC = 0;
1378   }
1379 
1380   Vec_PtrFree(vNodes);
1381 }
1382 ABC_NAMESPACE_IMPL_END
1383 
1384