ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Macros | Functions
fretFlow.c File Reference
#include "fretime.h"
Include dependency graph for fretFlow.c:

Go to the source code of this file.

Macros

#define FDIST(xn, xe, yn, ye)
 

Functions

void dfsfast_preorder (Abc_Ntk_t *pNtk)
 FUNCTION DEFINITIONS ///.
 
int dfsfast_e (Abc_Obj_t *pObj, Abc_Obj_t *pPred)
 
int dfsfast_r (Abc_Obj_t *pObj, Abc_Obj_t *pPred)
 
int dfsplain_e (Abc_Obj_t *pObj, Abc_Obj_t *pPred)
 
int dfsplain_r (Abc_Obj_t *pObj, Abc_Obj_t *pPred)
 

Macro Definition Documentation

◆ FDIST

#define FDIST ( xn,
xe,
yn,
ye )
Value:
(FDATA(xn)->xe##_dist == (FDATA(yn)->ye##_dist + 1))
FDATA
#define FDATA(x)
Definition fretime.h:80

Definition at line 33 of file fretFlow.c.

Function Documentation

◆ dfsfast_e()

int dfsfast_e ( Abc_Obj_t * pObj,
Abc_Obj_t * pPred )

Definition at line 210 of file fretFlow.c.

210 {
211 int i;
212 Abc_Obj_t *pNext;
213
214 if (pManMR->fSinkDistTerminate) return 0;
215
216 // have we reached the sink?
217 if(FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask ||
218 Abc_ObjIsPi(pObj)) {
219 assert(pPred);
220 assert(!pManMR->fIsForward);
221 return 1;
222 }
223
224 FSET(pObj, VISITED_E);
225
226#ifdef DEBUG_VISITED
227 printf("(%de=%d) ", Abc_ObjId(pObj), FDATA(pObj)->e_dist);
228#endif
229
230 // 1. structural edges
231 if (pManMR->fIsForward)
232 Abc_ObjForEachFanout( pObj, pNext, i ) {
233 if (!FTEST(pNext, VISITED_R) &&
234 FDIST(pObj, e, pNext, r) &&
235 dfsfast_r(pNext, pPred)) {
236#ifdef DEBUG_PRINT_FLOWS
237 printf("o");
238#endif
239 goto found;
240 }
241 }
242 else
243 Abc_ObjForEachFanin( pObj, pNext, i ) {
244 if (!FTEST(pNext, VISITED_R) &&
245 FDIST(pObj, e, pNext, r) &&
246 dfsfast_r(pNext, pPred)) {
247#ifdef DEBUG_PRINT_FLOWS
248 printf("o");
249#endif
250 goto found;
251 }
252 }
253
254 if (Abc_ObjIsLatch(pObj))
255 goto not_found;
256
257 // 2. reverse edges (backward retiming only)
258 if (!pManMR->fIsForward) {
259 Abc_ObjForEachFanout( pObj, pNext, i ) {
260 if (!FTEST(pNext, VISITED_E) &&
261 FDIST(pObj, e, pNext, e) &&
262 dfsfast_e(pNext, pPred)) {
263#ifdef DEBUG_PRINT_FLOWS
264 printf("i");
265#endif
266 goto found;
267 }
268 }
269
270 // 3. timing edges (backward retiming only)
271#if !defined(IGNORE_TIMING)
272 if (pManMR->maxDelay)
273 Vec_PtrForEachEntry(Abc_Obj_t *, FTIMEEDGES(pObj), pNext, i) {
274 if (!FTEST(pNext, VISITED_E) &&
275 FDIST(pObj, e, pNext, e) &&
276 dfsfast_e(pNext, pPred)) {
277#ifdef DEBUG_PRINT_FLOWS
278 printf("o");
279#endif
280 goto found;
281 }
282 }
283#endif
284 }
285
286 // unwind
287 if (FTEST(pObj, FLOW) &&
288 !FTEST(pObj, VISITED_R) &&
289 FDIST(pObj, e, pObj, r) &&
290 dfsfast_r(pObj, FGETPRED(pObj))) {
291
292 FUNSET(pObj, FLOW);
293 FSETPRED(pObj, NULL);
294#ifdef DEBUG_PRINT_FLOWS
295 printf("u");
296#endif
297 goto found;
298 }
299
300 not_found:
301 FUNSET(pObj, VISITED_E);
302 dfsfast_e_retreat(pObj);
303 return 0;
304
305 found:
306#ifdef DEBUG_PRINT_FLOWS
307 printf("%d ", Abc_ObjId(pObj));
308#endif
309 FUNSET(pObj, VISITED_E);
310 return 1;
311}
Abc_Obj_t
struct Abc_Obj_t_ Abc_Obj_t
Definition abc.h:116
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition abc.h:527
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition abc.h:529
FDIST
#define FDIST(xn, xe, yn, ye)
Definition fretFlow.c:33
dfsfast_e
int dfsfast_e(Abc_Obj_t *pObj, Abc_Obj_t *pPred)
Definition fretFlow.c:210
dfsfast_r
int dfsfast_r(Abc_Obj_t *pObj, Abc_Obj_t *pPred)
Definition fretFlow.c:313
FSET
#define FSET(x, y)
Definition fretime.h:81
FLOW
#define FLOW
Definition fretime.h:49
VISITED_E
#define VISITED_E
Definition fretime.h:46
pManMR
MinRegMan_t * pManMR
Definition fretMain.c:52
VISITED_R
#define VISITED_R
Definition fretime.h:47
BLOCK_OR_CONS
#define BLOCK_OR_CONS
Definition fretime.h:56
FUNSET
#define FUNSET(x, y)
Definition fretime.h:82
FTIMEEDGES
#define FTIMEEDGES(x)
Definition fretime.h:84
FTEST
#define FTEST(x, y)
Definition fretime.h:83
assert
#define assert(ex)
Definition util_old.h:213
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition vecPtr.h:55
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfsfast_preorder()

void dfsfast_preorder ( Abc_Ntk_t * pNtk)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Fast DFS.]

Description [Uses sink-distance-histogram heuristic. May not find all flow paths: this occurs in a small number of cases where the flow predecessor points to a non-adjacent node and the distance ordering is perturbed.]

SideEffects []

SeeAlso []

Definition at line 54 of file fretFlow.c.

54 {
55 Abc_Obj_t *pObj, *pNext;
56 Vec_Ptr_t *vTimeIn, *qn = Vec_PtrAlloc(Abc_NtkObjNum(pNtk));
57 Vec_Int_t *qe = Vec_IntAlloc(Abc_NtkObjNum(pNtk));
58 int i, j, d = 0, end;
59 int qpos = 0;
60
61 // create reverse timing edges for backward traversal
62#if !defined(IGNORE_TIMING)
63 if (pManMR->maxDelay) {
64 Abc_NtkForEachObj( pNtk, pObj, i ) {
65 Vec_PtrForEachEntry( Abc_Obj_t *, FTIMEEDGES(pObj), pNext, j ) {
66 vTimeIn = FDATA(pNext)->vNodes;
67 if (!vTimeIn) {
68 vTimeIn = FDATA(pNext)->vNodes = Vec_PtrAlloc(2);
69 }
70 Vec_PtrPush(vTimeIn, pObj);
71 }
72 }
73 }
74#endif
75
76 // clear histogram
77 assert(pManMR->vSinkDistHist);
78 memset(Vec_IntArray(pManMR->vSinkDistHist), 0, sizeof(int)*Vec_IntSize(pManMR->vSinkDistHist));
79
80 // seed queue : latches, PIOs, and blocks
81 Abc_NtkForEachObj( pNtk, pObj, i )
82 if (Abc_ObjIsPo(pObj) ||
83 Abc_ObjIsLatch(pObj) ||
84 (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
85 Vec_PtrPush(qn, pObj);
86 Vec_IntPush(qe, 'r');
87 FDATA(pObj)->r_dist = 1;
88 } else if (Abc_ObjIsPi(pObj) ||
89 (!pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
90 Vec_PtrPush(qn, pObj);
91 Vec_IntPush(qe, 'e');
92 FDATA(pObj)->e_dist = 1;
93 }
94
95 // until queue is empty...
96 while(qpos < Vec_PtrSize(qn)) {
97 pObj = (Abc_Obj_t *)Vec_PtrEntry(qn, qpos);
98 assert(pObj);
99 end = Vec_IntEntry(qe, qpos);
100 qpos++;
101
102 if (end == 'r') {
103 d = FDATA(pObj)->r_dist;
104
105 // 1. structural edges
106 if (pManMR->fIsForward) {
107 Abc_ObjForEachFanin( pObj, pNext, i )
108 if (!FDATA(pNext)->e_dist) {
109 FDATA(pNext)->e_dist = d+1;
110 Vec_PtrPush(qn, pNext);
111 Vec_IntPush(qe, 'e');
112 }
113 } else
114 Abc_ObjForEachFanout( pObj, pNext, i )
115 if (!FDATA(pNext)->e_dist) {
116 FDATA(pNext)->e_dist = d+1;
117 Vec_PtrPush(qn, pNext);
118 Vec_IntPush(qe, 'e');
119 }
120
121 if (d == 1) continue;
122
123 // 2. reverse edges (forward retiming only)
124 if (pManMR->fIsForward) {
125 Abc_ObjForEachFanout( pObj, pNext, i )
126 if (!FDATA(pNext)->r_dist && !Abc_ObjIsLatch(pNext)) {
127 FDATA(pNext)->r_dist = d+1;
128 Vec_PtrPush(qn, pNext);
129 Vec_IntPush(qe, 'r');
130 }
131
132 // 3. timimg edges (forward retiming only)
133#if !defined(IGNORE_TIMING)
134 if (pManMR->maxDelay && FDATA(pObj)->vNodes)
135 Vec_PtrForEachEntry(Abc_Obj_t *, FDATA(pObj)->vNodes, pNext, i ) {
136 if (!FDATA(pNext)->r_dist) {
137 FDATA(pNext)->r_dist = d+1;
138 Vec_PtrPush(qn, pNext);
139 Vec_IntPush(qe, 'r');
140 }
141 }
142#endif
143 }
144
145 } else { // if 'e'
146 if (Abc_ObjIsLatch(pObj)) continue;
147
148 d = FDATA(pObj)->e_dist;
149
150 // 1. through node
151 if (!FDATA(pObj)->r_dist) {
152 FDATA(pObj)->r_dist = d+1;
153 Vec_PtrPush(qn, pObj);
154 Vec_IntPush(qe, 'r');
155 }
156
157 // 2. reverse edges (backward retiming only)
158 if (!pManMR->fIsForward) {
159 Abc_ObjForEachFanin( pObj, pNext, i )
160 if (!FDATA(pNext)->e_dist && !Abc_ObjIsLatch(pNext)) {
161 FDATA(pNext)->e_dist = d+1;
162 Vec_PtrPush(qn, pNext);
163 Vec_IntPush(qe, 'e');
164 }
165
166 // 3. timimg edges (backward retiming only)
167#if !defined(IGNORE_TIMING)
168 if (pManMR->maxDelay && FDATA(pObj)->vNodes)
169 Vec_PtrForEachEntry(Abc_Obj_t *, FDATA(pObj)->vNodes, pNext, i ) {
170 if (!FDATA(pNext)->e_dist) {
171 FDATA(pNext)->e_dist = d+1;
172 Vec_PtrPush(qn, pNext);
173 Vec_IntPush(qe, 'e');
174 }
175 }
176#endif
177 }
178 }
179 }
180
181 // free time edges
182#if !defined(IGNORE_TIMING)
183 if (pManMR->maxDelay) {
184 Abc_NtkForEachObj( pNtk, pObj, i ) {
185 vTimeIn = FDATA(pObj)->vNodes;
186 if (vTimeIn) {
187 Vec_PtrFree(vTimeIn);
188 FDATA(pObj)->vNodes = 0;
189 }
190 }
191 }
192#endif
193
194 Abc_NtkForEachObj( pNtk, pObj, i ) {
195 Vec_IntAddToEntry(pManMR->vSinkDistHist, FDATA(pObj)->r_dist, 1);
196 Vec_IntAddToEntry(pManMR->vSinkDistHist, FDATA(pObj)->e_dist, 1);
197
198#ifdef DEBUG_PREORDER
199 printf("node %d\t: r=%d\te=%d\n", Abc_ObjId(pObj), FDATA(pObj)->r_dist, FDATA(pObj)->e_dist);
200#endif
201 }
202
203 // printf("\t\tpre-ordered (max depth=%d)\n", d+1);
204
205 // deallocate
206 Vec_PtrFree( qn );
207 Vec_IntFree( qe );
208}
Abc_NtkForEachObj
#define Abc_NtkForEachObj(pNtk, pObj, i)
ITERATORS ///.
Definition abc.h:449
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
memset
char * memset()
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition vecPtr.h:42
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfsfast_r()

int dfsfast_r ( Abc_Obj_t * pObj,
Abc_Obj_t * pPred )

Definition at line 313 of file fretFlow.c.

313 {
314 int i;
315 Abc_Obj_t *pNext, *pOldPred;
316
317 if (pManMR->fSinkDistTerminate) return 0;
318
319#ifdef DEBUG_VISITED
320 printf("(%dr=%d) ", Abc_ObjId(pObj), FDATA(pObj)->r_dist);
321#endif
322
323 // have we reached the sink?
324 if (Abc_ObjIsLatch(pObj) ||
325 (pManMR->fIsForward && Abc_ObjIsPo(pObj)) ||
326 (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
327 assert(pPred);
328 return 1;
329 }
330
331 FSET(pObj, VISITED_R);
332
333 if (FTEST(pObj, FLOW)) {
334
335 pOldPred = FGETPRED(pObj);
336 if (pOldPred &&
337 !FTEST(pOldPred, VISITED_E) &&
338 FDIST(pObj, r, pOldPred, e) &&
339 dfsfast_e(pOldPred, pOldPred)) {
340
341 FSETPRED(pObj, pPred);
342
343#ifdef DEBUG_PRINT_FLOWS
344 printf("fr");
345#endif
346 goto found;
347 }
348
349 } else {
350
351 if (!FTEST(pObj, VISITED_E) &&
352 FDIST(pObj, r, pObj, e) &&
353 dfsfast_e(pObj, pObj)) {
354
355 FSET(pObj, FLOW);
356 FSETPRED(pObj, pPred);
357
358#ifdef DEBUG_PRINT_FLOWS
359 printf("f");
360#endif
361 goto found;
362 }
363 }
364
365 // 2. reverse edges (forward retiming only)
366 if (pManMR->fIsForward) {
367 Abc_ObjForEachFanin( pObj, pNext, i ) {
368 if (!FTEST(pNext, VISITED_R) &&
369 FDIST(pObj, r, pNext, r) &&
370 !Abc_ObjIsLatch(pNext) &&
371 dfsfast_r(pNext, pPred)) {
372#ifdef DEBUG_PRINT_FLOWS
373 printf("i");
374#endif
375 goto found;
376 }
377 }
378
379 // 3. timing edges (forward retiming only)
380#if !defined(IGNORE_TIMING)
381 if (pManMR->maxDelay)
382 Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
383 if (!FTEST(pNext, VISITED_R) &&
384 FDIST(pObj, r, pNext, r) &&
385 dfsfast_r(pNext, pPred)) {
386#ifdef DEBUG_PRINT_FLOWS
387 printf("o");
388#endif
389 goto found;
390 }
391 }
392#endif
393 }
394
395 FUNSET(pObj, VISITED_R);
396 dfsfast_r_retreat(pObj);
397 return 0;
398
399 found:
400#ifdef DEBUG_PRINT_FLOWS
401 printf("%d ", Abc_ObjId(pObj));
402#endif
403 FUNSET(pObj, VISITED_R);
404 return 1;
405}
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfsplain_e()

int dfsplain_e ( Abc_Obj_t * pObj,
Abc_Obj_t * pPred )

Function*************************************************************

Synopsis [Plain DFS.]

Description [Does not use sink-distance-histogram heuristic.]

SideEffects []

SeeAlso []

Definition at line 528 of file fretFlow.c.

528 {
529 int i;
530 Abc_Obj_t *pNext;
531
532 if (FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask ||
533 Abc_ObjIsPi(pObj)) {
534 assert(pPred);
535 assert(!pManMR->fIsForward);
536 return 1;
537 }
538
539 FSET(pObj, VISITED_E);
540
541 // printf(" %de\n", Abc_ObjId(pObj));
542
543 // 1. structural edges
544 if (pManMR->fIsForward)
545 Abc_ObjForEachFanout( pObj, pNext, i ) {
546 if (!FTEST(pNext, VISITED_R) &&
547 dfsplain_r(pNext, pPred)) {
548#ifdef DEBUG_PRINT_FLOWS
549 printf("o");
550#endif
551 goto found;
552 }
553 }
554 else
555 Abc_ObjForEachFanin( pObj, pNext, i ) {
556 if (!FTEST(pNext, VISITED_R) &&
557 dfsplain_r(pNext, pPred)) {
558#ifdef DEBUG_PRINT_FLOWS
559 printf("o");
560#endif
561 goto found;
562 }
563 }
564
565 if (Abc_ObjIsLatch(pObj))
566 return 0;
567
568 // 2. reverse edges (backward retiming only)
569 if (!pManMR->fIsForward) {
570 Abc_ObjForEachFanout( pObj, pNext, i ) {
571 if (!FTEST(pNext, VISITED_E) &&
572 dfsplain_e(pNext, pPred)) {
573#ifdef DEBUG_PRINT_FLOWS
574 printf("i");
575#endif
576 goto found;
577 }
578 }
579
580 // 3. timing edges (backward retiming only)
581#if !defined(IGNORE_TIMING)
582 if (pManMR->maxDelay)
583 Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
584 if (!FTEST(pNext, VISITED_E) &&
585 dfsplain_e(pNext, pPred)) {
586#ifdef DEBUG_PRINT_FLOWS
587 printf("o");
588#endif
589 goto found;
590 }
591 }
592#endif
593 }
594
595 // unwind
596 if (FTEST(pObj, FLOW) &&
597 !FTEST(pObj, VISITED_R) &&
598 dfsplain_r(pObj, FGETPRED(pObj))) {
599 FUNSET(pObj, FLOW);
600 FSETPRED(pObj, NULL);
601#ifdef DEBUG_PRINT_FLOWS
602 printf("u");
603#endif
604 goto found;
605 }
606
607 return 0;
608
609 found:
610#ifdef DEBUG_PRINT_FLOWS
611 printf("%d ", Abc_ObjId(pObj));
612#endif
613
614 return 1;
615}
dfsplain_e
int dfsplain_e(Abc_Obj_t *pObj, Abc_Obj_t *pPred)
Definition fretFlow.c:528
dfsplain_r
int dfsplain_r(Abc_Obj_t *pObj, Abc_Obj_t *pPred)
Definition fretFlow.c:617
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfsplain_r()

int dfsplain_r ( Abc_Obj_t * pObj,
Abc_Obj_t * pPred )

Definition at line 617 of file fretFlow.c.

617 {
618 int i;
619 Abc_Obj_t *pNext, *pOldPred;
620
621 // have we reached the sink?
622 if (Abc_ObjIsLatch(pObj) ||
623 (pManMR->fIsForward && Abc_ObjIsPo(pObj)) ||
624 (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
625 assert(pPred);
626 return 1;
627 }
628
629 FSET(pObj, VISITED_R);
630
631 // printf(" %dr\n", Abc_ObjId(pObj));
632
633 if (FTEST(pObj, FLOW)) {
634
635 pOldPred = FGETPRED(pObj);
636 if (pOldPred &&
637 !FTEST(pOldPred, VISITED_E) &&
638 dfsplain_e(pOldPred, pOldPred)) {
639
640 FSETPRED(pObj, pPred);
641
642#ifdef DEBUG_PRINT_FLOWS
643 printf("fr");
644#endif
645 goto found;
646 }
647
648 } else {
649
650 if (!FTEST(pObj, VISITED_E) &&
651 dfsplain_e(pObj, pObj)) {
652
653 FSET(pObj, FLOW);
654 FSETPRED(pObj, pPred);
655
656#ifdef DEBUG_PRINT_FLOWS
657 printf("f");
658#endif
659 goto found;
660 }
661 }
662
663 // 2. follow reverse edges
664 if (pManMR->fIsForward) { // forward retiming only
665 Abc_ObjForEachFanin( pObj, pNext, i ) {
666 if (!FTEST(pNext, VISITED_R) &&
667 !Abc_ObjIsLatch(pNext) &&
668 dfsplain_r(pNext, pPred)) {
669#ifdef DEBUG_PRINT_FLOWS
670 printf("i");
671#endif
672 goto found;
673 }
674 }
675
676 // 3. timing edges (forward only)
677#if !defined(IGNORE_TIMING)
678 if (pManMR->maxDelay)
679 Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
680 if (!FTEST(pNext, VISITED_R) &&
681 dfsplain_r(pNext, pPred)) {
682#ifdef DEBUG_PRINT_FLOWS
683 printf("o");
684#endif
685 goto found;
686 }
687 }
688#endif
689 }
690
691 return 0;
692
693 found:
694#ifdef DEBUG_PRINT_FLOWS
695 printf("%d ", Abc_ObjId(pObj));
696#endif
697 return 1;
698}
Here is the call graph for this function:
Here is the caller graph for this function: