1 /**CFile****************************************************************
2
3 FileName [aigDoms.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [AIG package.]
8
9 Synopsis [Computing multi-output dominators.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: aigDoms.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "aig.h"
22 #include "aig/saig/saig.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 typedef struct Aig_Sto_t_ Aig_Sto_t;
31 typedef struct Aig_Dom_t_ Aig_Dom_t;
32
33 struct Aig_Dom_t_
34 {
35 int uSign; // signature
36 int nNodes; // the number of nodes
37 int pNodes[0]; // the nodes
38 };
39
40 struct Aig_Sto_t_
41 {
42 int Limit;
43 Aig_Man_t * pAig; // user's AIG
44 Aig_MmFixed_t * pMem; // memory manager for dominators
45 Vec_Ptr_t * vDoms; // dominators
46 Vec_Int_t * vFans; // temporary fanouts
47 Vec_Int_t * vTimes; // the number of times each appears
48 int nDomNodes; // nodes with dominators
49 int nDomsTotal; // total dominators
50 int nDomsFilter1; // filtered dominators
51 int nDomsFilter2; // filtered dominators
52 };
53
54 #define Aig_DomForEachNode( pAig, pDom, pNode, i ) \
55 for ( i = 0; (i < pDom->nNodes) && ((pNode) = Aig_ManObj(pAig, (pDom)->pNodes[i])); i++ )
56
57 ////////////////////////////////////////////////////////////////////////
58 /// FUNCTION DEFINITIONS ///
59 ////////////////////////////////////////////////////////////////////////
60
61 /**Function*************************************************************
62
63 Synopsis [Creates dominator manager.]
64
65 Description []
66
67 SideEffects []
68
69 SeeAlso []
70
71 ***********************************************************************/
Aig_ManDomStart(Aig_Man_t * pAig,int Limit)72 Aig_Sto_t * Aig_ManDomStart( Aig_Man_t * pAig, int Limit )
73 {
74 Aig_Sto_t * pSto;
75 pSto = ABC_CALLOC( Aig_Sto_t, 1 );
76 pSto->pAig = pAig;
77 pSto->Limit = Limit;
78 pSto->pMem = Aig_MmFixedStart( sizeof(Aig_Dom_t) + sizeof(int) * Limit, 10000 );
79 pSto->vDoms = Vec_PtrStart( Aig_ManObjNumMax(pAig) );
80 pSto->vFans = Vec_IntAlloc( 100 );
81 pSto->vTimes = Vec_IntStart( Aig_ManObjNumMax(pAig) );
82 return pSto;
83 }
84
85 /**Function*************************************************************
86
87 Synopsis [Adds trivial dominator.]
88
89 Description []
90
91 SideEffects []
92
93 SeeAlso []
94
95 ***********************************************************************/
Aig_ObjAddTriv(Aig_Sto_t * pSto,int Id,Vec_Ptr_t * vDoms)96 void Aig_ObjAddTriv( Aig_Sto_t * pSto, int Id, Vec_Ptr_t * vDoms )
97 {
98 Aig_Dom_t * pDom;
99 pDom = (Aig_Dom_t *)Aig_MmFixedEntryFetch( pSto->pMem );
100 pDom->uSign = (1 << (Id % 63));
101 pDom->nNodes = 1;
102 pDom->pNodes[0] = Id;
103 Vec_PtrPushFirst( vDoms, pDom );
104 assert( Vec_PtrEntry( pSto->vDoms, Id ) == NULL );
105 Vec_PtrWriteEntry( pSto->vDoms, Id, vDoms );
106 }
107
108 /**Function*************************************************************
109
110 Synopsis [Duplicates vector of doms.]
111
112 Description []
113
114 SideEffects []
115
116 SeeAlso []
117
118 ***********************************************************************/
Aig_ObjDomVecDup(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms,int fSkip1)119 Vec_Ptr_t * Aig_ObjDomVecDup( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms, int fSkip1 )
120 {
121 Vec_Ptr_t * vDoms2;
122 Aig_Dom_t * pDom, * pDom2;
123 int i;
124 vDoms2 = Vec_PtrAlloc( 0 );
125 Vec_PtrForEachEntryStart( Aig_Dom_t *, vDoms, pDom, i, fSkip1 )
126 {
127 pDom2 = (Aig_Dom_t *)Aig_MmFixedEntryFetch( pSto->pMem );
128 memcpy( pDom2, pDom, sizeof(Aig_Dom_t) + sizeof(int) * pSto->Limit );
129 Vec_PtrPush( vDoms2, pDom2 );
130 }
131 return vDoms2;
132 }
133
134 /**Function*************************************************************
135
136 Synopsis [Recycles vector of doms.]
137
138 Description []
139
140 SideEffects []
141
142 SeeAlso []
143
144 ***********************************************************************/
Aig_ObjDomVecRecycle(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms)145 void Aig_ObjDomVecRecycle( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms )
146 {
147 Aig_Dom_t * pDom;
148 int i;
149 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms, pDom, i )
150 Aig_MmFixedEntryRecycle( pSto->pMem, (char *)pDom );
151 Vec_PtrFree( vDoms );
152 }
153
154 /**Function*************************************************************
155
156 Synopsis [Duplicates the vector of doms.]
157
158 Description []
159
160 SideEffects []
161
162 SeeAlso []
163
164 ***********************************************************************/
Aig_ObjDomPrint(Aig_Sto_t * pSto,Aig_Dom_t * pDom,int Num)165 void Aig_ObjDomPrint( Aig_Sto_t * pSto, Aig_Dom_t * pDom, int Num )
166 {
167 int k;
168 printf( "%4d : {", Num );
169 for ( k = 0; k < pDom->nNodes; k++ )
170 printf( " %4d", pDom->pNodes[k] );
171 for ( ; k < pSto->Limit; k++ )
172 printf( " " );
173 printf( " }\n" );
174 }
175
176 /**Function*************************************************************
177
178 Synopsis [Duplicates the vector of doms.]
179
180 Description []
181
182 SideEffects []
183
184 SeeAlso []
185
186 ***********************************************************************/
Aig_ObjDomVecPrint(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms)187 void Aig_ObjDomVecPrint( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms )
188 {
189 Aig_Dom_t * pDom;
190 int i;
191 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms, pDom, i )
192 Aig_ObjDomPrint( pSto, pDom, i );
193 }
194
195 /**Function*************************************************************
196
197 Synopsis [Computes multi-node dominators.]
198
199 Description []
200
201 SideEffects []
202
203 SeeAlso []
204
205 ***********************************************************************/
Aig_ManDomPrint(Aig_Sto_t * pSto)206 void Aig_ManDomPrint( Aig_Sto_t * pSto )
207 {
208 Aig_Obj_t * pObj;
209 int i;
210 Saig_ManForEachPi( pSto->pAig, pObj, i )
211 {
212 printf( "*** PI %4d %4d :\n", i, pObj->Id );
213 Aig_ObjDomVecPrint( pSto, (Vec_Ptr_t *)Vec_PtrEntry(pSto->vDoms, pObj->Id) );
214 }
215 }
216
217 /**Function*************************************************************
218
219 Synopsis [Divides the circuit into well-balanced parts.]
220
221 Description []
222
223 SideEffects []
224
225 SeeAlso []
226
227 ***********************************************************************/
Aig_ManDomStop(Aig_Sto_t * pSto)228 void Aig_ManDomStop( Aig_Sto_t * pSto )
229 {
230 Vec_Ptr_t * vDoms;
231 int i;
232 Vec_PtrForEachEntry( Vec_Ptr_t *, pSto->vDoms, vDoms, i )
233 if ( vDoms )
234 Aig_ObjDomVecRecycle( pSto, vDoms );
235 Vec_PtrFree( pSto->vDoms );
236 Vec_IntFree( pSto->vFans );
237 Vec_IntFree( pSto->vTimes );
238 Aig_MmFixedStop( pSto->pMem, 0 );
239 ABC_FREE( pSto );
240 }
241
242
243 /**Function*************************************************************
244
245 Synopsis [Checks correctness of the cut.]
246
247 Description []
248
249 SideEffects []
250
251 SeeAlso []
252
253 ***********************************************************************/
Aig_ObjDomCheck(Aig_Dom_t * pDom)254 int Aig_ObjDomCheck( Aig_Dom_t * pDom )
255 {
256 int i;
257 for ( i = 1; i < pDom->nNodes; i++ )
258 {
259 if ( pDom->pNodes[i-1] >= pDom->pNodes[i] )
260 {
261 Abc_Print( -1, "Aig_ObjDomCheck(): Cut has wrong ordering of inputs.\n" );
262 return 0;
263 }
264 assert( pDom->pNodes[i-1] < pDom->pNodes[i] );
265 }
266 return 1;
267 }
268
269 /**Function*************************************************************
270
271 Synopsis [Returns 1 if pDom is contained in pCut.]
272
273 Description []
274
275 SideEffects []
276
277 SeeAlso []
278
279 ***********************************************************************/
Aig_ObjDomCheckDominance(Aig_Dom_t * pDom,Aig_Dom_t * pCut)280 static inline int Aig_ObjDomCheckDominance( Aig_Dom_t * pDom, Aig_Dom_t * pCut )
281 {
282 int i, k;
283 for ( i = 0; i < pDom->nNodes; i++ )
284 {
285 for ( k = 0; k < (int)pCut->nNodes; k++ )
286 if ( pDom->pNodes[i] == pCut->pNodes[k] )
287 break;
288 if ( k == (int)pCut->nNodes ) // node i in pDom is not contained in pCut
289 return 0;
290 }
291 // every node in pDom is contained in pCut
292 return 1;
293 }
294
295 /**Function*************************************************************
296
297 Synopsis [Returns 1 if the cut is contained.]
298
299 Description []
300
301 SideEffects []
302
303 SeeAlso []
304
305 ***********************************************************************/
Aig_ObjDomFilter(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms,Aig_Dom_t * pDom)306 int Aig_ObjDomFilter( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms, Aig_Dom_t * pDom )
307 {
308 Aig_Dom_t * pTemp;
309 int i;
310 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms, pTemp, i )
311 {
312 if ( pTemp->nNodes > pDom->nNodes )
313 {
314 // do not fiter the first cut
315 if ( i == 0 )
316 continue;
317 // skip the non-contained cuts
318 if ( (pTemp->uSign & pDom->uSign) != pDom->uSign )
319 continue;
320 // check containment seriously
321 if ( Aig_ObjDomCheckDominance( pDom, pTemp ) )
322 {
323 Vec_PtrRemove( vDoms, pTemp );
324 Aig_MmFixedEntryRecycle( pSto->pMem, (char *)pTemp );
325 i--;
326 pSto->nDomsFilter1++;
327 }
328 }
329 else
330 {
331 // skip the non-contained cuts
332 if ( (pTemp->uSign & pDom->uSign) != pTemp->uSign )
333 continue;
334 // check containment seriously
335 if ( Aig_ObjDomCheckDominance( pTemp, pDom ) )
336 {
337 pSto->nDomsFilter2++;
338 return 1;
339 }
340 }
341 }
342 return 0;
343 }
344
345 /**Function*************************************************************
346
347 Synopsis [Merges two cuts.]
348
349 Description []
350
351 SideEffects []
352
353 SeeAlso []
354
355 ***********************************************************************/
Aig_ObjDomMergeOrdered(Aig_Dom_t * pD0,Aig_Dom_t * pD1,Aig_Dom_t * pD,int Limit)356 static inline int Aig_ObjDomMergeOrdered( Aig_Dom_t * pD0, Aig_Dom_t * pD1, Aig_Dom_t * pD, int Limit )
357 {
358 int i, k, c;
359 assert( pD0->nNodes >= pD1->nNodes );
360 // the case of the largest cut sizes
361 if ( pD0->nNodes == Limit && pD1->nNodes == Limit )
362 {
363 for ( i = 0; i < pD0->nNodes; i++ )
364 if ( pD0->pNodes[i] != pD1->pNodes[i] )
365 return 0;
366 for ( i = 0; i < pD0->nNodes; i++ )
367 pD->pNodes[i] = pD0->pNodes[i];
368 pD->nNodes = pD0->nNodes;
369 return 1;
370 }
371 // the case when one of the cuts is the largest
372 if ( pD0->nNodes == Limit )
373 {
374 for ( i = 0; i < pD1->nNodes; i++ )
375 {
376 for ( k = pD0->nNodes - 1; k >= 0; k-- )
377 if ( pD0->pNodes[k] == pD1->pNodes[i] )
378 break;
379 if ( k == -1 ) // did not find
380 return 0;
381 }
382 for ( i = 0; i < pD0->nNodes; i++ )
383 pD->pNodes[i] = pD0->pNodes[i];
384 pD->nNodes = pD0->nNodes;
385 return 1;
386 }
387
388 // compare two cuts with different numbers
389 i = k = 0;
390 for ( c = 0; c < (int)Limit; c++ )
391 {
392 if ( k == pD1->nNodes )
393 {
394 if ( i == pD0->nNodes )
395 {
396 pD->nNodes = c;
397 return 1;
398 }
399 pD->pNodes[c] = pD0->pNodes[i++];
400 continue;
401 }
402 if ( i == pD0->nNodes )
403 {
404 if ( k == pD1->nNodes )
405 {
406 pD->nNodes = c;
407 return 1;
408 }
409 pD->pNodes[c] = pD1->pNodes[k++];
410 continue;
411 }
412 if ( pD0->pNodes[i] < pD1->pNodes[k] )
413 {
414 pD->pNodes[c] = pD0->pNodes[i++];
415 continue;
416 }
417 if ( pD0->pNodes[i] > pD1->pNodes[k] )
418 {
419 pD->pNodes[c] = pD1->pNodes[k++];
420 continue;
421 }
422 pD->pNodes[c] = pD0->pNodes[i++];
423 k++;
424 }
425 if ( i < pD0->nNodes || k < pD1->nNodes )
426 return 0;
427 pD->nNodes = c;
428 return 1;
429 }
430
431 /**Function*************************************************************
432
433 Synopsis [Prepares the object for FPGA mapping.]
434
435 Description []
436
437 SideEffects []
438
439 SeeAlso []
440
441 ***********************************************************************/
Aig_ObjDomMergeTwo(Aig_Dom_t * pDom0,Aig_Dom_t * pDom1,Aig_Dom_t * pDom,int Limit)442 int Aig_ObjDomMergeTwo( Aig_Dom_t * pDom0, Aig_Dom_t * pDom1, Aig_Dom_t * pDom, int Limit )
443 {
444 assert( Limit > 0 );
445 if ( pDom0->nNodes < pDom1->nNodes )
446 {
447 if ( !Aig_ObjDomMergeOrdered( pDom1, pDom0, pDom, Limit ) )
448 return 0;
449 }
450 else
451 {
452 if ( !Aig_ObjDomMergeOrdered( pDom0, pDom1, pDom, Limit ) )
453 return 0;
454 }
455 pDom->uSign = pDom0->uSign | pDom1->uSign;
456 assert( pDom->nNodes <= Limit );
457 assert( Aig_ObjDomCheck( pDom ) );
458 return 1;
459 }
460
461 /**Function*************************************************************
462
463 Synopsis [Merge two arrays of dominators.]
464
465 Description []
466
467 SideEffects []
468
469 SeeAlso []
470
471 ***********************************************************************/
Aig_ObjDomMerge(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms0,Vec_Ptr_t * vDoms1)472 Vec_Ptr_t * Aig_ObjDomMerge( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms0, Vec_Ptr_t * vDoms1 )
473 {
474 Vec_Ptr_t * vDoms;
475 Aig_Dom_t * pDom0, * pDom1, * pDom;
476 int i, k;
477 vDoms = Vec_PtrAlloc( 16 );
478 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms0, pDom0, i )
479 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms1, pDom1, k )
480 {
481 if ( Aig_WordCountOnes( pDom0->uSign | pDom1->uSign ) > pSto->Limit )
482 continue;
483 // check if the cut exists
484 pDom = (Aig_Dom_t *)Aig_MmFixedEntryFetch( pSto->pMem );
485 if ( !Aig_ObjDomMergeTwo( pDom0, pDom1, pDom, pSto->Limit ) )
486 {
487 Aig_MmFixedEntryRecycle( pSto->pMem, (char *)pDom );
488 continue;
489 }
490 // check if this cut is contained in any of the available cuts
491 if ( Aig_ObjDomFilter( pSto, vDoms, pDom ) )
492 {
493 Aig_MmFixedEntryRecycle( pSto->pMem, (char *)pDom );
494 continue;
495 }
496 Vec_PtrPush( vDoms, pDom );
497 }
498 return vDoms;
499 }
500
501 /**Function*************************************************************
502
503 Synopsis [Union two arrays of dominators.]
504
505 Description []
506
507 SideEffects []
508
509 SeeAlso []
510
511 ***********************************************************************/
Aig_ObjDomUnion(Aig_Sto_t * pSto,Vec_Ptr_t * vDoms2,Vec_Ptr_t * vDoms1)512 void Aig_ObjDomUnion( Aig_Sto_t * pSto, Vec_Ptr_t * vDoms2, Vec_Ptr_t * vDoms1 )
513 {
514 Aig_Dom_t * pDom1, * pDom2;
515 int i;
516 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms1, pDom1, i )
517 {
518 if ( i == 0 )
519 continue;
520 if ( Aig_ObjDomFilter( pSto, vDoms2, pDom1 ) )
521 continue;
522 pDom2 = (Aig_Dom_t *)Aig_MmFixedEntryFetch( pSto->pMem );
523 memcpy( pDom2, pDom1, sizeof(Aig_Dom_t) + sizeof(int) * pSto->Limit );
524 Vec_PtrPush( vDoms2, pDom2 );
525 }
526 }
527
528
529 /**Function*************************************************************
530
531 Synopsis [Computes multi-node dominators.]
532
533 Description []
534
535 SideEffects []
536
537 SeeAlso []
538
539 ***********************************************************************/
Aig_ObjDomCompute(Aig_Sto_t * pSto,Aig_Obj_t * pObj)540 void Aig_ObjDomCompute( Aig_Sto_t * pSto, Aig_Obj_t * pObj )
541 {
542 Vec_Ptr_t * vDoms0, * vDoms1, * vDoms2, * vDomsT;
543 Aig_Obj_t * pFanout;
544 int i, iFanout;
545 pSto->nDomNodes += Aig_ObjIsNode(pObj);
546 Vec_IntClear( pSto->vFans );
547 Aig_ObjForEachFanout( pSto->pAig, pObj, pFanout, iFanout, i )
548 if ( Aig_ObjIsTravIdCurrent(pSto->pAig, pFanout) )
549 Vec_IntPush( pSto->vFans, iFanout>>1 );
550 if ( Vec_IntSize(pSto->vFans) == 0 )
551 return;
552 vDoms0 = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, Vec_IntEntry(pSto->vFans, 0) );
553 vDoms2 = Aig_ObjDomVecDup( pSto, vDoms0, 0 );
554 Vec_IntForEachEntryStart( pSto->vFans, iFanout, i, 1 )
555 {
556 vDoms1 = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, iFanout );
557 vDoms2 = Aig_ObjDomMerge( pSto, vDomsT = vDoms2, vDoms1 );
558 Aig_ObjDomVecRecycle( pSto, vDomsT );
559 }
560 Aig_ObjAddTriv( pSto, pObj->Id, vDoms2 );
561 pSto->nDomsTotal += Vec_PtrSize(vDoms2);
562 }
563
564 /**Function*************************************************************
565
566 Synopsis [Marks the flop TFI with the current traversal ID.]
567
568 Description []
569
570 SideEffects []
571
572 SeeAlso []
573
574 ***********************************************************************/
Aig_ManMarkFlopTfi_rec(Aig_Man_t * p,Aig_Obj_t * pObj)575 int Aig_ManMarkFlopTfi_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
576 {
577 int Count;
578 assert( !Aig_IsComplement(pObj) );
579 if ( Aig_ObjIsTravIdCurrent(p, pObj) )
580 return 0;
581 Aig_ObjSetTravIdCurrent(p, pObj);
582 if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
583 return 1;
584 Count = Aig_ManMarkFlopTfi_rec( p, Aig_ObjFanin0(pObj) );
585 if ( Aig_ObjIsNode(pObj) )
586 Count += Aig_ManMarkFlopTfi_rec( p, Aig_ObjFanin1(pObj) );
587 return Count;
588 }
589
590 /**Function*************************************************************
591
592 Synopsis [Marks the flop TFI with the current traversal ID.]
593
594 Description []
595
596 SideEffects []
597
598 SeeAlso []
599
600 ***********************************************************************/
Aig_ManMarkFlopTfi(Aig_Man_t * p)601 void Aig_ManMarkFlopTfi( Aig_Man_t * p )
602 {
603 Aig_Obj_t * pObj;
604 int i;
605 Aig_ManIncrementTravId( p );
606 Saig_ManForEachLi( p, pObj, i )
607 Aig_ManMarkFlopTfi_rec( p, pObj );
608 }
609
610 /**Function*************************************************************
611
612 Synopsis [Computes multi-node dominators.]
613
614 Description []
615
616 SideEffects []
617
618 SeeAlso []
619
620 ***********************************************************************/
Aig_ManComputeDomsFlops(Aig_Man_t * pAig,int Limit)621 Aig_Sto_t * Aig_ManComputeDomsFlops( Aig_Man_t * pAig, int Limit )
622 {
623 Aig_Sto_t * pSto;
624 Vec_Ptr_t * vNodes;
625 Aig_Obj_t * pObj;
626 int i;
627 abctime clk = Abc_Clock();
628 pSto = Aig_ManDomStart( pAig, Limit );
629 // initialize flop inputs
630 Saig_ManForEachLi( pAig, pObj, i )
631 Aig_ObjAddTriv( pSto, pObj->Id, Vec_PtrAlloc(1) );
632 // compute internal nodes
633 vNodes = Aig_ManDfsReverse( pAig );
634 Aig_ManMarkFlopTfi( pAig );
635 Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
636 if ( Aig_ObjIsTravIdCurrent(pSto->pAig, pObj) )
637 Aig_ObjDomCompute( pSto, pObj );
638 Vec_PtrFree( vNodes );
639 // compute combinational inputs
640 Aig_ManForEachCi( pAig, pObj, i )
641 Aig_ObjDomCompute( pSto, pObj );
642 // print statistics
643 printf( "Nodes =%4d. Flops =%4d. Doms =%9d. Ave =%8.2f. ",
644 pSto->nDomNodes, Aig_ManRegNum(pSto->pAig), pSto->nDomsTotal,
645 // pSto->nDomsFilter1, pSto->nDomsFilter2,
646 1.0 * pSto->nDomsTotal / (pSto->nDomNodes + Aig_ManRegNum(pSto->pAig)) );
647 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
648 return pSto;
649 }
650
651 /**Function*************************************************************
652
653 Synopsis [Computes multi-node dominators.]
654
655 Description []
656
657 SideEffects []
658
659 SeeAlso []
660
661 ***********************************************************************/
Aig_ManComputeDomsPis(Aig_Man_t * pAig,int Limit)662 Aig_Sto_t * Aig_ManComputeDomsPis( Aig_Man_t * pAig, int Limit )
663 {
664 Aig_Sto_t * pSto;
665 Vec_Ptr_t * vNodes;
666 Aig_Obj_t * pObj;
667 int i;
668 abctime clk = Abc_Clock();
669 pSto = Aig_ManDomStart( pAig, Limit );
670 // initialize flop inputs
671 Aig_ManForEachCo( pAig, pObj, i )
672 Aig_ObjAddTriv( pSto, pObj->Id, Vec_PtrAlloc(1) );
673 // compute internal nodes
674 vNodes = Aig_ManDfsReverse( pAig );
675 Aig_ManMarkFlopTfi( pAig );
676 Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
677 if ( Aig_ObjIsTravIdCurrent(pSto->pAig, pObj) )
678 Aig_ObjDomCompute( pSto, pObj );
679 Vec_PtrFree( vNodes );
680 // compute combinational inputs
681 Saig_ManForEachPi( pAig, pObj, i )
682 Aig_ObjDomCompute( pSto, pObj );
683 // print statistics
684 printf( "Nodes =%4d. PIs =%4d. Doms =%9d. Ave =%8.2f. ",
685 pSto->nDomNodes, Saig_ManPiNum(pSto->pAig), pSto->nDomsTotal,
686 // pSto->nDomsFilter1, pSto->nDomsFilter2,
687 1.0 * pSto->nDomsTotal / (pSto->nDomNodes + Saig_ManPiNum(pSto->pAig)) );
688 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
689 return pSto;
690 }
691
692 /**Function*************************************************************
693
694 Synopsis [Computes multi-node dominators.]
695
696 Description []
697
698 SideEffects []
699
700 SeeAlso []
701
702 ***********************************************************************/
Aig_ManComputeDomsNodes(Aig_Man_t * pAig,int Limit)703 Aig_Sto_t * Aig_ManComputeDomsNodes( Aig_Man_t * pAig, int Limit )
704 {
705 Aig_Sto_t * pSto;
706 Vec_Ptr_t * vNodes;
707 Aig_Obj_t * pObj;
708 int i;
709 abctime clk = Abc_Clock();
710 pSto = Aig_ManDomStart( pAig, Limit );
711 // initialize flop inputs
712 Aig_ManForEachCo( pAig, pObj, i )
713 Aig_ObjAddTriv( pSto, pObj->Id, Vec_PtrAlloc(1) );
714 // compute internal nodes
715 vNodes = Aig_ManDfsReverse( pAig );
716 Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
717 Aig_ObjDomCompute( pSto, pObj );
718 Vec_PtrFree( vNodes );
719 // compute combinational inputs
720 Aig_ManForEachCi( pAig, pObj, i )
721 Aig_ObjDomCompute( pSto, pObj );
722 // print statistics
723 printf( "Nodes =%6d. Doms =%9d. Ave =%8.2f. ",
724 pSto->nDomNodes, pSto->nDomsTotal,
725 // pSto->nDomsFilter1, pSto->nDomsFilter2,
726 1.0 * pSto->nDomsTotal / pSto->nDomNodes );
727 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
728 return pSto;
729 }
730
731 /**Function*************************************************************
732
733 Synopsis [Collects dominators from the cut.]
734
735 Description []
736
737 SideEffects []
738
739 SeeAlso []
740
741 ***********************************************************************/
Aig_ObjDomCollect(Aig_Sto_t * pSto,Vec_Int_t * vCut)742 Vec_Ptr_t * Aig_ObjDomCollect( Aig_Sto_t * pSto, Vec_Int_t * vCut )
743 {
744 Vec_Ptr_t * vDoms0, * vDoms1, * vDoms2;
745 int i, ObjId;
746 vDoms0 = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, Vec_IntEntry(vCut, 0) );
747 vDoms2 = Aig_ObjDomVecDup( pSto, vDoms0, 1 );
748 Vec_IntForEachEntryStart( vCut, ObjId, i, 1 )
749 {
750 vDoms1 = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, ObjId );
751 if ( vDoms1 == NULL )
752 continue;
753 Aig_ObjDomUnion( pSto, vDoms2, vDoms1 );
754 }
755 return vDoms2;
756 }
757
758
759 /**Function*************************************************************
760
761 Synopsis [Marks the flop TFI with the current traversal ID.]
762
763 Description []
764
765 SideEffects []
766
767 SeeAlso []
768
769 ***********************************************************************/
Aig_ObjDomVolume_rec(Aig_Man_t * p,Aig_Obj_t * pObj)770 int Aig_ObjDomVolume_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
771 {
772 int Count;
773 assert( !Aig_IsComplement(pObj) );
774 if ( Aig_ObjIsTravIdCurrent(p, pObj) )
775 return 0;
776 Aig_ObjSetTravIdCurrent(p, pObj);
777 if ( pObj->fMarkA )
778 return 1;
779 // assert( !Aig_ObjIsCi(pObj) && !Aig_ObjIsConst1(pObj) );
780 if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
781 return 1;
782 Count = Aig_ObjDomVolume_rec( p, Aig_ObjFanin0(pObj) );
783 if ( Aig_ObjIsNode(pObj) )
784 Count += Aig_ObjDomVolume_rec( p, Aig_ObjFanin1(pObj) );
785 return Count;
786 }
787
788 /**Function*************************************************************
789
790 Synopsis [Count the number of nodes in the dominator.]
791
792 Description []
793
794 SideEffects []
795
796 SeeAlso []
797
798 ***********************************************************************/
Aig_ObjDomVolume(Aig_Sto_t * pSto,Aig_Dom_t * pDom)799 int Aig_ObjDomVolume( Aig_Sto_t * pSto, Aig_Dom_t * pDom )
800 {
801 Aig_Obj_t * pObj;
802 int i, Counter = 0;
803 Aig_ManIncrementTravId( pSto->pAig );
804 Aig_DomForEachNode( pSto->pAig, pDom, pObj, i )
805 Counter += Aig_ObjDomVolume_rec( pSto->pAig, pObj );
806 return Counter;
807 }
808
809
810
811
812 /**Function*************************************************************
813
814 Synopsis [Dereferences the node's MFFC.]
815
816 Description []
817
818 SideEffects []
819
820 SeeAlso []
821
822 ***********************************************************************/
Aig_ObjDomDeref_rec(Aig_Obj_t * pNode)823 int Aig_ObjDomDeref_rec( Aig_Obj_t * pNode )
824 {
825 int Counter = 0;
826 assert( pNode->nRefs > 0 );
827 if ( --pNode->nRefs > 0 )
828 return 0;
829 assert( pNode->nRefs == 0 );
830 if ( pNode->fMarkA )
831 return 1;
832 if ( Aig_ObjIsCi(pNode) )
833 return 0;
834 Counter += Aig_ObjDomDeref_rec( Aig_ObjFanin0(pNode) );
835 if ( Aig_ObjIsNode(pNode) )
836 Counter += Aig_ObjDomDeref_rec( Aig_ObjFanin1(pNode) );
837 return Counter;
838 }
839
840 /**Function*************************************************************
841
842 Synopsis [References the node's MFFC.]
843
844 Description []
845
846 SideEffects []
847
848 SeeAlso []
849
850 ***********************************************************************/
Aig_ObjDomRef_rec(Aig_Obj_t * pNode)851 int Aig_ObjDomRef_rec( Aig_Obj_t * pNode )
852 {
853 int Counter = 0;
854 assert( pNode->nRefs >= 0 );
855 if ( pNode->nRefs++ > 0 )
856 return 0;
857 assert( pNode->nRefs == 1 );
858 if ( pNode->fMarkA )
859 return 1;
860 if ( Aig_ObjIsCi(pNode) )
861 return 0;
862 Counter += Aig_ObjDomRef_rec( Aig_ObjFanin0(pNode) );
863 if ( Aig_ObjIsNode(pNode) )
864 Counter += Aig_ObjDomRef_rec( Aig_ObjFanin1(pNode) );
865 return Counter;
866 }
867
868 /**Function*************************************************************
869
870 Synopsis [Count the number of nodes in the dominator.]
871
872 Description []
873
874 SideEffects []
875
876 SeeAlso []
877
878 ***********************************************************************/
Aig_ObjDomDomed(Aig_Sto_t * pSto,Aig_Dom_t * pDom)879 int Aig_ObjDomDomed( Aig_Sto_t * pSto, Aig_Dom_t * pDom )
880 {
881 Aig_Obj_t * pObj;
882 int i, Counter0, Counter1;
883 Counter0 = 0;
884 Aig_DomForEachNode( pSto->pAig, pDom, pObj, i )
885 {
886 assert( !Aig_ObjIsCi(pObj) );
887 Counter0 += Aig_ObjDomDeref_rec( Aig_ObjFanin0(pObj) );
888 if ( Aig_ObjIsNode(pObj) )
889 Counter0 += Aig_ObjDomDeref_rec( Aig_ObjFanin1(pObj) );
890 }
891 Counter1 = 0;
892 Aig_DomForEachNode( pSto->pAig, pDom, pObj, i )
893 {
894 assert( !Aig_ObjIsCi(pObj) );
895 Counter1 += Aig_ObjDomRef_rec( Aig_ObjFanin0(pObj) );
896 if ( Aig_ObjIsNode(pObj) )
897 Counter1 += Aig_ObjDomRef_rec( Aig_ObjFanin1(pObj) );
898 }
899 assert( Counter0 == Counter1 );
900 return Counter0;
901 }
902
903
904 /**Function*************************************************************
905
906 Synopsis [Collects dominators from the cut.]
907
908 Description []
909
910 SideEffects []
911
912 SeeAlso []
913
914 ***********************************************************************/
Aig_ObjDomCollectLos(Aig_Sto_t * pSto)915 Vec_Int_t * Aig_ObjDomCollectLos( Aig_Sto_t * pSto )
916 {
917 Vec_Int_t * vCut;
918 Aig_Obj_t * pObj;
919 int i;
920 vCut = Vec_IntAlloc( Aig_ManRegNum(pSto->pAig) );
921 Saig_ManForEachLo( pSto->pAig, pObj, i )
922 {
923 Vec_IntPush( vCut, pObj->Id );
924 pObj->fMarkA = 1;
925 }
926 return vCut;
927 }
928
929 /**Function*************************************************************
930
931 Synopsis []
932
933 Description []
934
935 SideEffects []
936
937 SeeAlso []
938
939 ***********************************************************************/
Aig_ObjPoLogicDeref(Aig_Sto_t * pSto)940 void Aig_ObjPoLogicDeref( Aig_Sto_t * pSto )
941 {
942 Aig_Obj_t * pObj;
943 int i;
944 Saig_ManForEachPo( pSto->pAig, pObj, i )
945 Aig_ObjDomDeref_rec( Aig_ObjFanin0(pObj) );
946 }
947
948 /**Function*************************************************************
949
950 Synopsis []
951
952 Description []
953
954 SideEffects []
955
956 SeeAlso []
957
958 ***********************************************************************/
Aig_ObjPoLogicRef(Aig_Sto_t * pSto)959 void Aig_ObjPoLogicRef( Aig_Sto_t * pSto )
960 {
961 Aig_Obj_t * pObj;
962 int i;
963 Saig_ManForEachPo( pSto->pAig, pObj, i )
964 Aig_ObjDomRef_rec( Aig_ObjFanin0(pObj) );
965 }
966
967 /**Function*************************************************************
968
969 Synopsis [Collects dominators from the cut.]
970
971 Description []
972
973 SideEffects []
974
975 SeeAlso []
976
977 ***********************************************************************/
Aig_ObjDomFindGood(Aig_Sto_t * pSto)978 void Aig_ObjDomFindGood( Aig_Sto_t * pSto )
979 {
980 Aig_Dom_t * pDom;
981 Vec_Int_t * vCut;
982 Vec_Ptr_t * vDoms;
983 int i;
984 vCut = Aig_ObjDomCollectLos( pSto );
985 vDoms = Aig_ObjDomCollect( pSto, vCut );
986 Vec_IntFree( vCut );
987 printf( "The cut has %d non-trivial %d-dominators.\n", Vec_PtrSize(vDoms), pSto->Limit );
988
989 Aig_ObjPoLogicDeref( pSto );
990 Vec_PtrForEachEntry( Aig_Dom_t *, vDoms, pDom, i )
991 {
992 // if ( Aig_ObjDomDomed(pSto, pDom) <= 1 )
993 // continue;
994 printf( "Vol =%3d. ", Aig_ObjDomVolume(pSto, pDom) );
995 printf( "Dom =%3d. ", Aig_ObjDomDomed(pSto, pDom) );
996 Aig_ObjDomPrint( pSto, pDom, i );
997 }
998 Aig_ObjPoLogicRef( pSto );
999
1000 Aig_ObjDomVecRecycle( pSto, vDoms );
1001 Aig_ManCleanMarkA( pSto->pAig );
1002 }
1003
1004
1005 /**Function*************************************************************
1006
1007 Synopsis [Computes multi-node dominators.]
1008
1009 Description []
1010
1011 SideEffects []
1012
1013 SeeAlso []
1014
1015 ***********************************************************************/
Aig_ManComputeDomsTest2(Aig_Man_t * pAig,int Num)1016 void Aig_ManComputeDomsTest2( Aig_Man_t * pAig, int Num )
1017 {
1018 Aig_Sto_t * pSto;
1019 // int i;
1020 //Aig_ManShow( pAig, 0, NULL );
1021 Aig_ManFanoutStart( pAig );
1022 // for ( i = 1; i < 9; i++ )
1023 {
1024 printf( "ITERATION %d:\n", Num );
1025 pSto = Aig_ManComputeDomsFlops( pAig, Num );
1026 Aig_ObjDomFindGood( pSto );
1027 // Aig_ManDomPrint( pSto );
1028 Aig_ManDomStop( pSto );
1029 }
1030 Aig_ManFanoutStop( pAig );
1031 }
1032
1033 /**Function*************************************************************
1034
1035 Synopsis [Computes multi-node dominators.]
1036
1037 Description []
1038
1039 SideEffects []
1040
1041 SeeAlso []
1042
1043 ***********************************************************************/
Aig_ManComputeDomsTest(Aig_Man_t * pAig)1044 void Aig_ManComputeDomsTest( Aig_Man_t * pAig )
1045 {
1046 Aig_Sto_t * pSto;
1047 Aig_ManFanoutStart( pAig );
1048 pSto = Aig_ManComputeDomsPis( pAig, 1 );
1049 Aig_ManDomPrint( pSto );
1050 Aig_ManDomStop( pSto );
1051 Aig_ManFanoutStop( pAig );
1052 }
1053
1054
1055
1056
1057
1058 /**Function*************************************************************
1059
1060 Synopsis [Collects dominators from the cut.]
1061
1062 Description []
1063
1064 SideEffects []
1065
1066 SeeAlso []
1067
1068 ***********************************************************************/
Aig_ObjDomCount(Aig_Sto_t * pSto,Aig_Obj_t * pObj)1069 void Aig_ObjDomCount( Aig_Sto_t * pSto, Aig_Obj_t * pObj )
1070 {
1071 Aig_Dom_t * pDom;
1072 Aig_Obj_t * pFanout;
1073 Vec_Int_t * vSingles;
1074 Vec_Ptr_t * vDoms;
1075 int i, k, Entry, iFanout, fPrint = 0;
1076 vSingles = Vec_IntAlloc( 100 );
1077 // for each dominator of a fanout, count how many fanouts have it as a dominator
1078 Aig_ObjForEachFanout( pSto->pAig, pObj, pFanout, iFanout, i )
1079 {
1080 vDoms = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, Aig_ObjId(pFanout) );
1081 Vec_PtrForEachEntryStart( Aig_Dom_t *, vDoms, pDom, k, 1 )
1082 {
1083 // printf( "Fanout %d Dominator %d\n", Aig_ObjId(pFanout), pDom->pNodes[0] );
1084 Vec_IntAddToEntry( pSto->vTimes, pDom->pNodes[0], 1 );
1085 Vec_IntPushUnique( vSingles, pDom->pNodes[0] );
1086 }
1087 }
1088 // clear storage
1089 Vec_IntForEachEntry( vSingles, Entry, i )
1090 {
1091 if ( Vec_IntEntry(pSto->vTimes, Entry) > 5 )
1092 {
1093 if ( fPrint == 0 )
1094 {
1095 printf( "%6d : Level =%4d. Fanout =%6d.\n",
1096 Aig_ObjId(pObj), Aig_ObjLevel(pObj), Aig_ObjRefs(pObj) );
1097 }
1098 fPrint = 1;
1099 printf( "%d(%d) ", Entry, Vec_IntEntry(pSto->vTimes, Entry) );
1100 }
1101 Vec_IntWriteEntry( pSto->vTimes, Entry, 0);
1102 }
1103 if ( fPrint )
1104 printf( "\n" );
1105 Vec_IntFree( vSingles );
1106 }
1107
1108
1109 /**Function*************************************************************
1110
1111 Synopsis [Computes multi-node dominators.]
1112
1113 Description []
1114
1115 SideEffects []
1116
1117 SeeAlso []
1118
1119 ***********************************************************************/
Aig_ManComputeDomsForCofactoring(Aig_Man_t * pAig)1120 void Aig_ManComputeDomsForCofactoring( Aig_Man_t * pAig )
1121 {
1122 Vec_Ptr_t * vDoms;
1123 Aig_Sto_t * pSto;
1124 Aig_Obj_t * pObj;
1125 int i;
1126 Aig_ManFanoutStart( pAig );
1127 pSto = Aig_ManComputeDomsNodes( pAig, 1 );
1128 Aig_ManForEachObj( pAig, pObj, i )
1129 {
1130 if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) )
1131 continue;
1132 if ( Aig_ObjRefs(pObj) < 10 )
1133 continue;
1134 vDoms = (Vec_Ptr_t *)Vec_PtrEntry( pSto->vDoms, Aig_ObjId(pObj) );
1135 // printf( "%6d : Level =%4d. Fanout =%6d.\n",
1136 // Aig_ObjId(pObj), Aig_ObjLevel(pObj), Aig_ObjRefs(pObj) );
1137
1138 Aig_ObjDomCount( pSto, pObj );
1139 }
1140 Aig_ManDomStop( pSto );
1141 Aig_ManFanoutStop( pAig );
1142 }
1143
1144
1145
1146
1147
1148 ////////////////////////////////////////////////////////////////////////
1149 /// END OF FILE ///
1150 ////////////////////////////////////////////////////////////////////////
1151
1152
1153 ABC_NAMESPACE_IMPL_END
1154
1155