1 /**CFile****************************************************************
2
3 FileName [giaDfs.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [DFS procedures.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis [Counts the support size of the node.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Gia_ManCollectCis_rec(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vSupp)45 void Gia_ManCollectCis_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
46 {
47 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
48 return;
49 Gia_ObjSetTravIdCurrent(p, pObj);
50 if ( Gia_ObjIsCi(pObj) )
51 {
52 Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
53 return;
54 }
55 assert( Gia_ObjIsAnd(pObj) );
56 Gia_ManCollectCis_rec( p, Gia_ObjFanin0(pObj), vSupp );
57 Gia_ManCollectCis_rec( p, Gia_ObjFanin1(pObj), vSupp );
58 }
59
60 /**Function*************************************************************
61
62 Synopsis [Collects support nodes.]
63
64 Description []
65
66 SideEffects []
67
68 SeeAlso []
69
70 ***********************************************************************/
Gia_ManCollectCis(Gia_Man_t * p,int * pNodes,int nNodes,Vec_Int_t * vSupp)71 void Gia_ManCollectCis( Gia_Man_t * p, int * pNodes, int nNodes, Vec_Int_t * vSupp )
72 {
73 Gia_Obj_t * pObj;
74 int i;
75 Vec_IntClear( vSupp );
76 Gia_ManIncrementTravId( p );
77 Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
78 for ( i = 0; i < nNodes; i++ )
79 {
80 pObj = Gia_ManObj( p, pNodes[i] );
81 if ( Gia_ObjIsCo(pObj) )
82 Gia_ManCollectCis_rec( p, Gia_ObjFanin0(pObj), vSupp );
83 else
84 Gia_ManCollectCis_rec( p, pObj, vSupp );
85 }
86 }
87
88 /**Function*************************************************************
89
90 Synopsis [Counts the support size of the node.]
91
92 Description []
93
94 SideEffects []
95
96 SeeAlso []
97
98 ***********************************************************************/
Gia_ManCollectAnds_rec(Gia_Man_t * p,int iObj,Vec_Int_t * vNodes)99 void Gia_ManCollectAnds_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vNodes )
100 {
101 Gia_Obj_t * pObj;
102 if ( Gia_ObjIsTravIdCurrentId(p, iObj) )
103 return;
104 Gia_ObjSetTravIdCurrentId(p, iObj);
105 pObj = Gia_ManObj( p, iObj );
106 if ( Gia_ObjIsCi(pObj) )
107 return;
108 assert( Gia_ObjIsAnd(pObj) );
109 Gia_ManCollectAnds_rec( p, Gia_ObjFaninId0(pObj, iObj), vNodes );
110 Gia_ManCollectAnds_rec( p, Gia_ObjFaninId1(pObj, iObj), vNodes );
111 Vec_IntPush( vNodes, iObj );
112 }
113
114 /**Function*************************************************************
115
116 Synopsis [Collects support nodes.]
117
118 Description []
119
120 SideEffects []
121
122 SeeAlso []
123
124 ***********************************************************************/
Gia_ManCollectAnds(Gia_Man_t * p,int * pNodes,int nNodes,Vec_Int_t * vNodes,Vec_Int_t * vLeaves)125 void Gia_ManCollectAnds( Gia_Man_t * p, int * pNodes, int nNodes, Vec_Int_t * vNodes, Vec_Int_t * vLeaves )
126 {
127 int i, iLeaf;
128 // Gia_ManIncrementTravId( p );
129 Gia_ObjSetTravIdCurrentId( p, 0 );
130 if ( vLeaves )
131 Vec_IntForEachEntry( vLeaves, iLeaf, i )
132 Gia_ObjSetTravIdCurrentId( p, iLeaf );
133 Vec_IntClear( vNodes );
134 for ( i = 0; i < nNodes; i++ )
135 {
136 Gia_Obj_t * pObj = Gia_ManObj( p, pNodes[i] );
137 if ( Gia_ObjIsCo(pObj) )
138 Gia_ManCollectAnds_rec( p, Gia_ObjFaninId0(pObj, pNodes[i]), vNodes );
139 else if ( Gia_ObjIsAnd(pObj) )
140 Gia_ManCollectAnds_rec( p, pNodes[i], vNodes );
141 }
142 }
143
144 /**Function*************************************************************
145
146 Synopsis [Collects support nodes.]
147
148 Description []
149
150 SideEffects []
151
152 SeeAlso []
153
154 ***********************************************************************/
Gia_ManCollectAndsAll(Gia_Man_t * p)155 Vec_Int_t * Gia_ManCollectAndsAll( Gia_Man_t * p )
156 {
157 Gia_Obj_t * pObj; int i;
158 Vec_Int_t * vNodes = Vec_IntAlloc( Gia_ManAndNum(p) );
159 Gia_ManForEachAnd( p, pObj, i )
160 Vec_IntPush( vNodes, i );
161 return vNodes;
162 }
163
164 /**Function*************************************************************
165
166 Synopsis [Counts the support size of the node.]
167
168 Description []
169
170 SideEffects []
171
172 SeeAlso []
173
174 ***********************************************************************/
Gia_ManCollectNodesCis_rec(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vNodes)175 void Gia_ManCollectNodesCis_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vNodes )
176 {
177 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
178 return;
179 Gia_ObjSetTravIdCurrent(p, pObj);
180 if ( Gia_ObjIsCi(pObj) )
181 {
182 Vec_IntPush( vNodes, Gia_ObjId(p, pObj) );
183 return;
184 }
185 assert( Gia_ObjIsAnd(pObj) );
186 Gia_ManCollectNodesCis_rec( p, Gia_ObjFanin0(pObj), vNodes );
187 Gia_ManCollectNodesCis_rec( p, Gia_ObjFanin1(pObj), vNodes );
188 Vec_IntPush( vNodes, Gia_ObjId(p, pObj) );
189 }
190
191 /**Function*************************************************************
192
193 Synopsis [Collects support nodes.]
194
195 Description []
196
197 SideEffects []
198
199 SeeAlso []
200
201 ***********************************************************************/
Gia_ManCollectNodesCis(Gia_Man_t * p,int * pNodes,int nNodes)202 Vec_Int_t * Gia_ManCollectNodesCis( Gia_Man_t * p, int * pNodes, int nNodes )
203 {
204 Vec_Int_t * vNodes;
205 Gia_Obj_t * pObj;
206 int i;
207 vNodes = Vec_IntAlloc( 10000 );
208 Gia_ManIncrementTravId( p );
209 Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
210 for ( i = 0; i < nNodes; i++ )
211 {
212 pObj = Gia_ManObj( p, pNodes[i] );
213 if ( Gia_ObjIsCo(pObj) )
214 Gia_ManCollectNodesCis_rec( p, Gia_ObjFanin0(pObj), vNodes );
215 else
216 Gia_ManCollectNodesCis_rec( p, pObj, vNodes );
217 }
218 return vNodes;
219 }
220
221 /**Function*************************************************************
222
223 Synopsis [Collects support nodes.]
224
225 Description []
226
227 SideEffects []
228
229 SeeAlso []
230
231 ***********************************************************************/
Gia_ManCollectTest(Gia_Man_t * p)232 void Gia_ManCollectTest( Gia_Man_t * p )
233 {
234 Vec_Int_t * vNodes;
235 Gia_Obj_t * pObj;
236 int i, iNode;
237 abctime clk = Abc_Clock();
238 vNodes = Vec_IntAlloc( 100 );
239 Gia_ManIncrementTravId( p );
240 Gia_ManForEachCo( p, pObj, i )
241 {
242 iNode = Gia_ObjId(p, pObj);
243 Gia_ManCollectAnds( p, &iNode, 1, vNodes, NULL );
244 }
245 Vec_IntFree( vNodes );
246 ABC_PRT( "DFS from each output", Abc_Clock() - clk );
247 }
248
249 /**Function*************************************************************
250
251 Synopsis [Collects support nodes.]
252
253 Description []
254
255 SideEffects []
256
257 SeeAlso []
258
259 ***********************************************************************/
Gia_ManSuppSize_rec(Gia_Man_t * p,Gia_Obj_t * pObj)260 int Gia_ManSuppSize_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
261 {
262 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
263 return 0;
264 Gia_ObjSetTravIdCurrent(p, pObj);
265 if ( Gia_ObjIsCi(pObj) )
266 return 1;
267 assert( Gia_ObjIsAnd(pObj) );
268 return Gia_ManSuppSize_rec( p, Gia_ObjFanin0(pObj) ) +
269 Gia_ManSuppSize_rec( p, Gia_ObjFanin1(pObj) );
270 }
271
272 /**Function*************************************************************
273
274 Synopsis [Computes support size of the node.]
275
276 Description []
277
278 SideEffects []
279
280 SeeAlso []
281
282 ***********************************************************************/
Gia_ManSuppSizeOne(Gia_Man_t * p,Gia_Obj_t * pObj)283 int Gia_ManSuppSizeOne( Gia_Man_t * p, Gia_Obj_t * pObj )
284 {
285 Gia_ManIncrementTravId( p );
286 return Gia_ManSuppSize_rec( p, pObj );
287 }
288
289 /**Function*************************************************************
290
291 Synopsis [Computes support size of the node.]
292
293 Description []
294
295 SideEffects []
296
297 SeeAlso []
298
299 ***********************************************************************/
Gia_ManSuppSizeTest(Gia_Man_t * p)300 int Gia_ManSuppSizeTest( Gia_Man_t * p )
301 {
302 Gia_Obj_t * pObj;
303 int i, Counter = 0;
304 abctime clk = Abc_Clock();
305 Gia_ManForEachObj( p, pObj, i )
306 if ( Gia_ObjIsAnd(pObj) )
307 Counter += (Gia_ManSuppSizeOne(p, pObj) <= 16);
308 printf( "Nodes with small support %d (out of %d)\n", Counter, Gia_ManAndNum(p) );
309 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
310 return Counter;
311 }
312
313 /**Function*************************************************************
314
315 Synopsis [Collects support nodes.]
316
317 Description []
318
319 SideEffects []
320
321 SeeAlso []
322
323 ***********************************************************************/
Gia_ManSuppSize(Gia_Man_t * p,int * pNodes,int nNodes)324 int Gia_ManSuppSize( Gia_Man_t * p, int * pNodes, int nNodes )
325 {
326 Gia_Obj_t * pObj;
327 int i, Counter = 0;
328 Gia_ManIncrementTravId( p );
329 Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
330 for ( i = 0; i < nNodes; i++ )
331 {
332 pObj = Gia_ManObj( p, pNodes[i] );
333 if ( Gia_ObjIsCo(pObj) )
334 Counter += Gia_ManSuppSize_rec( p, Gia_ObjFanin0(pObj) );
335 else
336 Counter += Gia_ManSuppSize_rec( p, pObj );
337 }
338 return Counter;
339 }
340
341 /**Function*************************************************************
342
343 Synopsis [Collects support nodes.]
344
345 Description []
346
347 SideEffects []
348
349 SeeAlso []
350
351 ***********************************************************************/
Gia_ManConeSize_rec(Gia_Man_t * p,Gia_Obj_t * pObj)352 int Gia_ManConeSize_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
353 {
354 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
355 return 0;
356 Gia_ObjSetTravIdCurrent(p, pObj);
357 if ( Gia_ObjIsCi(pObj) )
358 return 0;
359 assert( Gia_ObjIsAnd(pObj) );
360 return 1 + Gia_ManConeSize_rec( p, Gia_ObjFanin0(pObj) ) +
361 Gia_ManConeSize_rec( p, Gia_ObjFanin1(pObj) );
362 }
363
364 /**Function*************************************************************
365
366 Synopsis [Collects support nodes.]
367
368 Description []
369
370 SideEffects []
371
372 SeeAlso []
373
374 ***********************************************************************/
Gia_ManConeSize(Gia_Man_t * p,int * pNodes,int nNodes)375 int Gia_ManConeSize( Gia_Man_t * p, int * pNodes, int nNodes )
376 {
377 Gia_Obj_t * pObj;
378 int i, Counter = 0;
379 Gia_ManIncrementTravId( p );
380 Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
381 for ( i = 0; i < nNodes; i++ )
382 {
383 pObj = Gia_ManObj( p, pNodes[i] );
384 if ( Gia_ObjIsCo(pObj) )
385 Counter += Gia_ManConeSize_rec( p, Gia_ObjFanin0(pObj) );
386 else
387 Counter += Gia_ManConeSize_rec( p, pObj );
388 }
389 return Counter;
390 }
391
392 /**Function*************************************************************
393
394 Synopsis [Levelizes the nodes.]
395
396 Description []
397
398 SideEffects []
399
400 SeeAlso []
401
402 ***********************************************************************/
Gia_ManLevelize(Gia_Man_t * p)403 Vec_Vec_t * Gia_ManLevelize( Gia_Man_t * p )
404 {
405 Gia_Obj_t * pObj;
406 Vec_Vec_t * vLevels;
407 int nLevels, Level, i;
408 nLevels = Gia_ManLevelNum( p );
409 vLevels = Vec_VecStart( nLevels + 1 );
410 Gia_ManForEachAnd( p, pObj, i )
411 {
412 Level = Gia_ObjLevel( p, pObj );
413 assert( Level <= nLevels );
414 Vec_VecPush( vLevels, Level, pObj );
415 }
416 return vLevels;
417 }
418
419 /**Function*************************************************************
420
421 Synopsis [Computes reverse topological order.]
422
423 Description [Assumes that levels are already assigned.
424 The levels of CO nodes may not be assigned.]
425
426 SideEffects []
427
428 SeeAlso []
429
430 ***********************************************************************/
Gia_ManOrderReverse(Gia_Man_t * p)431 Vec_Int_t * Gia_ManOrderReverse( Gia_Man_t * p )
432 {
433 Gia_Obj_t * pObj;
434 Vec_Vec_t * vLevels;
435 Vec_Ptr_t * vLevel;
436 Vec_Int_t * vResult;
437 int i, k;
438 vLevels = Vec_VecStart( 100 );
439 // make sure levels are assigned
440 Gia_ManForEachAnd( p, pObj, i )
441 assert( Gia_ObjLevel(p, pObj) > 0 );
442 // add CO nodes based on the level of their fanin
443 Gia_ManForEachCo( p, pObj, i )
444 Vec_VecPush( vLevels, Gia_ObjLevel(p, Gia_ObjFanin0(pObj)), pObj );
445 // add other nodes based on their level
446 Gia_ManForEachObj( p, pObj, i )
447 if ( !Gia_ObjIsCo(pObj) )
448 Vec_VecPush( vLevels, Gia_ObjLevel(p, pObj), pObj );
449 // put the nodes in the reverse topological order
450 vResult = Vec_IntAlloc( Gia_ManObjNum(p) );
451 Vec_VecForEachLevelReverse( vLevels, vLevel, i )
452 Vec_PtrForEachEntry( Gia_Obj_t *, vLevel, pObj, k )
453 Vec_IntPush( vResult, Gia_ObjId(p, pObj) );
454 Vec_VecFree( vLevels );
455 return vResult;
456 }
457
458 /**Function*************************************************************
459
460 Synopsis []
461
462 Description []
463
464 SideEffects []
465
466 SeeAlso []
467
468 ***********************************************************************/
Gia_ManCollectSeq_rec(Gia_Man_t * p,int Id,Vec_Int_t * vRoots,Vec_Int_t * vObjs)469 void Gia_ManCollectSeq_rec( Gia_Man_t * p, int Id, Vec_Int_t * vRoots, Vec_Int_t * vObjs )
470 {
471 Gia_Obj_t * pObj;
472 if ( Gia_ObjIsTravIdCurrentId( p, Id ) )
473 return;
474 Gia_ObjSetTravIdCurrentId( p, Id );
475 pObj = Gia_ManObj( p, Id );
476 if ( Gia_ObjIsAnd(pObj) )
477 {
478 Gia_ManCollectSeq_rec( p, Gia_ObjFaninId0(pObj, Id), vRoots, vObjs );
479 Gia_ManCollectSeq_rec( p, Gia_ObjFaninId1(pObj, Id), vRoots, vObjs );
480 }
481 else if ( Gia_ObjIsCi(pObj) )
482 {
483 if ( Gia_ObjIsRo(p, pObj) )
484 Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ObjRoToRi(p, pObj)) );
485 }
486 else if ( Gia_ObjIsCo(pObj) )
487 Gia_ManCollectSeq_rec( p, Gia_ObjFaninId0(pObj, Id), vRoots, vObjs );
488 else assert( 0 );
489 Vec_IntPush( vObjs, Id );
490 }
Gia_ManCollectSeq(Gia_Man_t * p,int * pPos,int nPos)491 Vec_Int_t * Gia_ManCollectSeq( Gia_Man_t * p, int * pPos, int nPos )
492 {
493 Vec_Int_t * vObjs, * vRoots;
494 int i, iRoot;
495 // collect roots
496 vRoots = Vec_IntAlloc( 100 );
497 for ( i = 0; i < nPos; i++ )
498 Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ManPo(p, pPos[i])) );
499 // start trav IDs
500 Gia_ManIncrementTravId( p );
501 Gia_ObjSetTravIdCurrentId( p, 0 );
502 // collect objects
503 vObjs = Vec_IntAlloc( 1000 );
504 Vec_IntPush( vObjs, 0 );
505 Vec_IntForEachEntry( vRoots, iRoot, i )
506 Gia_ManCollectSeq_rec( p, iRoot, vRoots, vObjs );
507 Vec_IntFree( vRoots );
508 return vObjs;
509 }
Gia_ManCollectSeqTest(Gia_Man_t * p)510 void Gia_ManCollectSeqTest( Gia_Man_t * p )
511 {
512 Vec_Int_t * vObjs;
513 int i;
514 abctime clk = Abc_Clock();
515 for ( i = 0; i < Gia_ManPoNum(p); i++ )
516 {
517 if ( i % 10000 == 0 )
518 printf( "%8d finished...\r", i );
519
520 vObjs = Gia_ManCollectSeq( p, &i, 1 );
521 // printf( "%d ", Vec_IntSize(vObjs) );
522 Vec_IntFree( vObjs );
523 }
524 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
525
526 }
527
528 /**Function*************************************************************
529
530 Synopsis [Collect TFI nodes.]
531
532 Description []
533
534 SideEffects []
535
536 SeeAlso []
537
538 ***********************************************************************/
Gia_ManCollectTfi_rec(Gia_Man_t * p,int iObj,Vec_Int_t * vNodes)539 void Gia_ManCollectTfi_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vNodes )
540 {
541 Gia_Obj_t * pObj;
542 if ( Gia_ObjIsTravIdCurrentId(p, iObj) )
543 return;
544 Gia_ObjSetTravIdCurrentId(p, iObj);
545 pObj = Gia_ManObj( p, iObj );
546 if ( Gia_ObjIsCi(pObj) )
547 return;
548 assert( Gia_ObjIsAnd(pObj) );
549 Gia_ManCollectTfi_rec( p, Gia_ObjFaninId0(pObj, iObj), vNodes );
550 Gia_ManCollectTfi_rec( p, Gia_ObjFaninId1(pObj, iObj), vNodes );
551 Vec_IntPush( vNodes, iObj );
552 }
Gia_ManCollectTfi(Gia_Man_t * p,Vec_Int_t * vRoots,Vec_Int_t * vNodes)553 void Gia_ManCollectTfi( Gia_Man_t * p, Vec_Int_t * vRoots, Vec_Int_t * vNodes )
554 {
555 int i, iRoot;
556 Vec_IntClear( vNodes );
557 Gia_ManIncrementTravId( p );
558 Vec_IntForEachEntry( vRoots, iRoot, i )
559 Gia_ManCollectTfi_rec( p, iRoot, vNodes );
560 }
561
562 /**Function*************************************************************
563
564 Synopsis [Collect TFI nodes.]
565
566 Description []
567
568 SideEffects []
569
570 SeeAlso []
571
572 ***********************************************************************/
Gia_ManCollectTfo_rec(Gia_Man_t * p,int iObj,Vec_Int_t * vNodes)573 void Gia_ManCollectTfo_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vNodes )
574 {
575 Gia_Obj_t * pObj; int i, iFan;
576 if ( Gia_ObjIsTravIdCurrentId(p, iObj) )
577 return;
578 Gia_ObjSetTravIdCurrentId(p, iObj);
579 pObj = Gia_ManObj( p, iObj );
580 if ( Gia_ObjIsCo(pObj) )
581 return;
582 assert( Gia_ObjIsAnd(pObj) );
583 Gia_ObjForEachFanoutStaticId( p, iObj, iFan, i )
584 Gia_ManCollectTfo_rec( p, iFan, vNodes );
585 Vec_IntPush( vNodes, iObj );
586 }
Gia_ManCollectTfo(Gia_Man_t * p,Vec_Int_t * vRoots,Vec_Int_t * vNodes)587 void Gia_ManCollectTfo( Gia_Man_t * p, Vec_Int_t * vRoots, Vec_Int_t * vNodes )
588 {
589 int i, iRoot;
590 Vec_IntClear( vNodes );
591 Gia_ManIncrementTravId( p );
592 Vec_IntForEachEntry( vRoots, iRoot, i )
593 Gia_ManCollectTfo_rec( p, iRoot, vNodes );
594 }
595
596 ////////////////////////////////////////////////////////////////////////
597 /// END OF FILE ///
598 ////////////////////////////////////////////////////////////////////////
599
600
601 ABC_NAMESPACE_IMPL_END
602
603