1 /**CFile****************************************************************
2
3 FileName [resDivs.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Resynthesis package.]
8
9 Synopsis [Collect divisors for the given window.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - January 15, 2007.]
16
17 Revision [$Id: resDivs.c,v 1.00 2007/01/15 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "base/abc/abc.h"
22 #include "resInt.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 static void Res_WinMarkTfi( Res_Win_t * p );
32
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36
37 /**Function*************************************************************
38
39 Synopsis [Adds candidate divisors of the node to its window.]
40
41 Description []
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
Res_WinDivisors(Res_Win_t * p,int nLevDivMax)48 void Res_WinDivisors( Res_Win_t * p, int nLevDivMax )
49 {
50 Abc_Obj_t * pObj, * pFanout, * pFanin;
51 int k, f, m;
52
53 // set the maximum level of the divisors
54 p->nLevDivMax = nLevDivMax;
55
56 // mark the TFI with the current trav ID
57 Abc_NtkIncrementTravId( p->pNode->pNtk );
58 Res_WinMarkTfi( p );
59
60 // mark with the current trav ID those nodes that should not be divisors:
61 // (1) the node and its TFO
62 // (2) the MFFC of the node
63 // (3) the node's fanins (these are treated as a special case)
64 Abc_NtkIncrementTravId( p->pNode->pNtk );
65 Res_WinSweepLeafTfo_rec( p->pNode, p->nLevDivMax );
66 Res_WinVisitMffc( p->pNode );
67 Abc_ObjForEachFanin( p->pNode, pObj, k )
68 Abc_NodeSetTravIdCurrent( pObj );
69
70 // at this point the nodes are marked with two trav IDs:
71 // nodes to be collected as divisors are marked with previous trav ID
72 // nodes to be avoided as divisors are marked with current trav ID
73
74 // start collecting the divisors
75 Vec_PtrClear( p->vDivs );
76 Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pObj, k )
77 {
78 assert( (int)pObj->Level >= p->nLevLeafMin );
79 if ( !Abc_NodeIsTravIdPrevious(pObj) )
80 continue;
81 if ( (int)pObj->Level > p->nLevDivMax )
82 continue;
83 Vec_PtrPush( p->vDivs, pObj );
84 }
85 // add the internal nodes to the data structure
86 Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodes, pObj, k )
87 {
88 if ( !Abc_NodeIsTravIdPrevious(pObj) )
89 continue;
90 if ( (int)pObj->Level > p->nLevDivMax )
91 continue;
92 Vec_PtrPush( p->vDivs, pObj );
93 }
94
95 // explore the fanouts of already collected divisors
96 p->nDivsPlus = 0;
97 Vec_PtrForEachEntry( Abc_Obj_t *, p->vDivs, pObj, k )
98 {
99 // consider fanouts of this node
100 Abc_ObjForEachFanout( pObj, pFanout, f )
101 {
102 // stop if there are too many fanouts
103 if ( f > 20 )
104 break;
105 // skip nodes that are already added
106 if ( Abc_NodeIsTravIdPrevious(pFanout) )
107 continue;
108 // skip nodes in the TFO or in the MFFC of node
109 if ( Abc_NodeIsTravIdCurrent(pFanout) )
110 continue;
111 // skip COs
112 if ( !Abc_ObjIsNode(pFanout) )
113 continue;
114 // skip nodes with large level
115 if ( (int)pFanout->Level > p->nLevDivMax )
116 continue;
117 // skip nodes whose fanins are not divisors
118 Abc_ObjForEachFanin( pFanout, pFanin, m )
119 if ( !Abc_NodeIsTravIdPrevious(pFanin) )
120 break;
121 if ( m < Abc_ObjFaninNum(pFanout) )
122 continue;
123 // add the node to the divisors
124 Vec_PtrPush( p->vDivs, pFanout );
125 Vec_PtrPush( p->vNodes, pFanout );
126 Abc_NodeSetTravIdPrevious( pFanout );
127 p->nDivsPlus++;
128 }
129 }
130 /*
131 printf( "Node level = %d. ", Abc_ObjLevel(p->pNode) );
132 Vec_PtrForEachEntryStart( Abc_Obj_t *, p->vDivs, pObj, k, Vec_PtrSize(p->vDivs)-p->nDivsPlus )
133 printf( "%d ", Abc_ObjLevel(pObj) );
134 printf( "\n" );
135 */
136 //printf( "%d ", p->nDivsPlus );
137 }
138
139 /**Function*************************************************************
140
141 Synopsis [Marks the TFI cone of the node.]
142
143 Description []
144
145 SideEffects []
146
147 SeeAlso []
148
149 ***********************************************************************/
Res_WinMarkTfi_rec(Res_Win_t * p,Abc_Obj_t * pObj)150 void Res_WinMarkTfi_rec( Res_Win_t * p, Abc_Obj_t * pObj )
151 {
152 Abc_Obj_t * pFanin;
153 int i;
154 if ( Abc_NodeIsTravIdCurrent(pObj) )
155 return;
156 Abc_NodeSetTravIdCurrent( pObj );
157 assert( Abc_ObjIsNode(pObj) );
158 // visit the fanins of the node
159 Abc_ObjForEachFanin( pObj, pFanin, i )
160 Res_WinMarkTfi_rec( p, pFanin );
161 }
162
163 /**Function*************************************************************
164
165 Synopsis [Marks the TFI cone of the node.]
166
167 Description []
168
169 SideEffects []
170
171 SeeAlso []
172
173 ***********************************************************************/
Res_WinMarkTfi(Res_Win_t * p)174 void Res_WinMarkTfi( Res_Win_t * p )
175 {
176 Abc_Obj_t * pObj;
177 int i;
178 // mark the leaves
179 Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pObj, i )
180 Abc_NodeSetTravIdCurrent( pObj );
181 // start from the node
182 Res_WinMarkTfi_rec( p, p->pNode );
183 }
184
185 /**Function*************************************************************
186
187 Synopsis [Marks the TFO of the collected nodes up to the given level.]
188
189 Description []
190
191 SideEffects []
192
193 SeeAlso []
194
195 ***********************************************************************/
Res_WinSweepLeafTfo_rec(Abc_Obj_t * pObj,int nLevelLimit)196 void Res_WinSweepLeafTfo_rec( Abc_Obj_t * pObj, int nLevelLimit )
197 {
198 Abc_Obj_t * pFanout;
199 int i;
200 if ( Abc_ObjIsCo(pObj) || (int)pObj->Level > nLevelLimit )
201 return;
202 if ( Abc_NodeIsTravIdCurrent(pObj) )
203 return;
204 Abc_NodeSetTravIdCurrent( pObj );
205 Abc_ObjForEachFanout( pObj, pFanout, i )
206 Res_WinSweepLeafTfo_rec( pFanout, nLevelLimit );
207 }
208
209 /**Function*************************************************************
210
211 Synopsis [Dereferences the node's MFFC.]
212
213 Description []
214
215 SideEffects []
216
217 SeeAlso []
218
219 ***********************************************************************/
Res_NodeDeref_rec(Abc_Obj_t * pNode)220 int Res_NodeDeref_rec( Abc_Obj_t * pNode )
221 {
222 Abc_Obj_t * pFanin;
223 int i, Counter = 1;
224 if ( Abc_ObjIsCi(pNode) )
225 return 0;
226 Abc_NodeSetTravIdCurrent( pNode );
227 Abc_ObjForEachFanin( pNode, pFanin, i )
228 {
229 assert( pFanin->vFanouts.nSize > 0 );
230 if ( --pFanin->vFanouts.nSize == 0 )
231 Counter += Res_NodeDeref_rec( pFanin );
232 }
233 return Counter;
234 }
235
236 /**Function*************************************************************
237
238 Synopsis [References the node's MFFC.]
239
240 Description []
241
242 SideEffects []
243
244 SeeAlso []
245
246 ***********************************************************************/
Res_NodeRef_rec(Abc_Obj_t * pNode)247 int Res_NodeRef_rec( Abc_Obj_t * pNode )
248 {
249 Abc_Obj_t * pFanin;
250 int i, Counter = 1;
251 if ( Abc_ObjIsCi(pNode) )
252 return 0;
253 Abc_ObjForEachFanin( pNode, pFanin, i )
254 {
255 if ( pFanin->vFanouts.nSize++ == 0 )
256 Counter += Res_NodeRef_rec( pFanin );
257 }
258 return Counter;
259 }
260
261 /**Function*************************************************************
262
263 Synopsis [Labels MFFC of the node with the current trav ID.]
264
265 Description []
266
267 SideEffects []
268
269 SeeAlso []
270
271 ***********************************************************************/
Res_WinVisitMffc(Abc_Obj_t * pNode)272 int Res_WinVisitMffc( Abc_Obj_t * pNode )
273 {
274 int Count1, Count2;
275 assert( Abc_ObjIsNode(pNode) );
276 // dereference the node (mark with the current trav ID)
277 Count1 = Res_NodeDeref_rec( pNode );
278 // reference it back
279 Count2 = Res_NodeRef_rec( pNode );
280 assert( Count1 == Count2 );
281 return Count1;
282 }
283
284 ////////////////////////////////////////////////////////////////////////
285 /// END OF FILE ///
286 ////////////////////////////////////////////////////////////////////////
287
288
289 ABC_NAMESPACE_IMPL_END
290
291