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