1 /**CFile****************************************************************
2 Copyright (c) The Regents of the University of California. All rights reserved.
3
4 Permission is hereby granted, without written agreement and without license or
5 royalty fees, to use, copy, modify, and distribute this software and its
6 documentation for any purpose, provided that the above copyright notice and
7 the following two paragraphs appear in all copies of this software.
8
9 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
10 DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
11 THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
12 CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
13
14 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
15 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
16 A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS,
17 AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
18 SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
19
20
21 FileName [aigTiming.c]
22
23 SystemName [ABC: Logic synthesis and verification system.]
24
25 PackageName [AIG package.]
26
27 Synopsis [Incremental updating of direct/reverse AIG levels.]
28
29 Author [Alan Mishchenko]
30
31 Affiliation [UC Berkeley]
32
33 Date [Ver. 1.0. Started - April 28, 2007.]
34
35 Revision [$Id: aigTiming.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
36
37 ***********************************************************************/
38
39 #include "aig.h"
40
41 ////////////////////////////////////////////////////////////////////////
42 /// DECLARATIONS ///
43 ////////////////////////////////////////////////////////////////////////
44
45 ////////////////////////////////////////////////////////////////////////
46 /// FUNCTION DEFINITIONS ///
47 ////////////////////////////////////////////////////////////////////////
48
49 /**Function*************************************************************
50
51 Synopsis [Returns the reverse level of the node.]
52
53 Description [The reverse level is the level of the node in reverse
54 topological order, starting from the COs.]
55
56 SideEffects []
57
58 SeeAlso []
59
60 ***********************************************************************/
Aig_ObjReverseLevel(Aig_Man_t * p,Aig_Obj_t * pObj)61 static inline int Aig_ObjReverseLevel( Aig_Man_t * p, Aig_Obj_t * pObj )
62 {
63 assert( p->vLevelR );
64 Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
65 return Vec_IntEntry(p->vLevelR, pObj->Id);
66 }
67
68 /**Function*************************************************************
69
70 Synopsis [Sets the reverse level of the node.]
71
72 Description [The reverse level is the level of the node in reverse
73 topological order, starting from the COs.]
74
75 SideEffects []
76
77 SeeAlso []
78
79 ***********************************************************************/
Aig_ObjSetReverseLevel(Aig_Man_t * p,Aig_Obj_t * pObj,int LevelR)80 static inline void Aig_ObjSetReverseLevel( Aig_Man_t * p, Aig_Obj_t * pObj, int LevelR )
81 {
82 assert( p->vLevelR );
83 Vec_IntFillExtra( p->vLevelR, pObj->Id + 1, 0 );
84 Vec_IntWriteEntry( p->vLevelR, pObj->Id, LevelR );
85 }
86
87 /**Function*************************************************************
88
89 Synopsis [Resets reverse level of the node.]
90
91 Description []
92
93 SideEffects []
94
95 SeeAlso []
96
97 ***********************************************************************/
Aig_ObjClearReverseLevel(Aig_Man_t * p,Aig_Obj_t * pObj)98 void Aig_ObjClearReverseLevel( Aig_Man_t * p, Aig_Obj_t * pObj )
99 {
100 Aig_ObjSetReverseLevel( p, pObj, 0 );
101 }
102
103 /**Function*************************************************************
104
105 Synopsis [Returns required level of the node.]
106
107 Description [Converts the reverse levels of the node into its required
108 level as follows: ReqLevel(Node) = MaxLevels(Ntk) + 1 - LevelR(Node).]
109
110 SideEffects []
111
112 SeeAlso []
113
114 ***********************************************************************/
Aig_ObjRequiredLevel(Aig_Man_t * p,Aig_Obj_t * pObj)115 int Aig_ObjRequiredLevel( Aig_Man_t * p, Aig_Obj_t * pObj )
116 {
117 assert( p->vLevelR );
118 return p->nLevelMax + 1 - Aig_ObjReverseLevel(p, pObj);
119 }
120
121 /**Function*************************************************************
122
123 Synopsis [Computes the reverse level of the node using its fanout levels.]
124
125 Description []
126
127 SideEffects []
128
129 SeeAlso []
130
131 ***********************************************************************/
Aig_ObjReverseLevelNew(Aig_Man_t * p,Aig_Obj_t * pObj)132 int Aig_ObjReverseLevelNew( Aig_Man_t * p, Aig_Obj_t * pObj )
133 {
134 Aig_Obj_t * pFanout;
135 int i, iFanout = -1, LevelCur, Level = 0;
136 Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
137 {
138 LevelCur = Aig_ObjReverseLevel( p, pFanout );
139 Level = AIG_MAX( Level, LevelCur );
140 }
141 return Level + 1;
142 }
143
144 /**Function*************************************************************
145
146 Synopsis [Prepares for the computation of required levels.]
147
148 Description [This procedure should be called before the required times
149 are used. It starts internal data structures, which records the level
150 from the COs of the network nodes in reverse topologogical order.]
151
152 SideEffects []
153
154 SeeAlso []
155
156 ***********************************************************************/
Aig_ManStartReverseLevels(Aig_Man_t * p,int nMaxLevelIncrease)157 void Aig_ManStartReverseLevels( Aig_Man_t * p, int nMaxLevelIncrease )
158 {
159 Vec_Ptr_t * vNodes;
160 Aig_Obj_t * pObj;
161 int i;
162 assert( p->pFanData != NULL );
163 assert( p->vLevelR == NULL );
164 // remember the maximum number of direct levels
165 p->nLevelMax = Aig_ManLevels(p) + nMaxLevelIncrease;
166 // start the reverse levels
167 p->vLevelR = Vec_IntAlloc( 0 );
168 Vec_IntFill( p->vLevelR, Aig_ManObjNumMax(p), 0 );
169 // compute levels in reverse topological order
170 vNodes = Aig_ManDfsReverse( p );
171 Vec_PtrForEachEntry( vNodes, pObj, i )
172 {
173 assert( pObj->fMarkA == 0 );
174 Aig_ObjSetReverseLevel( p, pObj, Aig_ObjReverseLevelNew(p, pObj) );
175 }
176 Vec_PtrFree( vNodes );
177 }
178
179 /**Function*************************************************************
180
181 Synopsis [Cleans the data structures used to compute required levels.]
182
183 Description []
184
185 SideEffects []
186
187 SeeAlso []
188
189 ***********************************************************************/
Aig_ManStopReverseLevels(Aig_Man_t * p)190 void Aig_ManStopReverseLevels( Aig_Man_t * p )
191 {
192 assert( p->vLevelR != NULL );
193 Vec_IntFree( p->vLevelR );
194 p->vLevelR = NULL;
195 p->nLevelMax = 0;
196
197 }
198
199 /**Function*************************************************************
200
201 Synopsis [Incrementally updates level of the nodes.]
202
203 Description []
204
205 SideEffects []
206
207 SeeAlso []
208
209 ***********************************************************************/
Aig_ManUpdateLevel(Aig_Man_t * p,Aig_Obj_t * pObjNew)210 void Aig_ManUpdateLevel( Aig_Man_t * p, Aig_Obj_t * pObjNew )
211 {
212 Aig_Obj_t * pFanout, * pTemp;
213 int iFanout = -1, LevelOld, Lev, k, m;
214 assert( p->pFanData != NULL );
215 assert( Aig_ObjIsNode(pObjNew) );
216 // allocate level if needed
217 if ( p->vLevels == NULL )
218 p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
219 // check if level has changed
220 LevelOld = Aig_ObjLevel(pObjNew);
221 if ( LevelOld == Aig_ObjLevelNew(pObjNew) )
222 return;
223 // start the data structure for level update
224 // we cannot fail to visit a node when using this structure because the
225 // nodes are stored by their _old_ levels, which are assumed to be correct
226 Vec_VecClear( p->vLevels );
227 Vec_VecPush( p->vLevels, LevelOld, pObjNew );
228 pObjNew->fMarkA = 1;
229 // recursively update level
230 Vec_VecForEachEntryStart( p->vLevels, pTemp, Lev, k, LevelOld )
231 {
232 pTemp->fMarkA = 0;
233 assert( Aig_ObjLevel(pTemp) == Lev );
234 pTemp->Level = Aig_ObjLevelNew(pTemp);
235 // if the level did not change, no need to check the fanout levels
236 if ( Aig_ObjLevel(pTemp) == Lev )
237 continue;
238 // schedule fanout for level update
239 Aig_ObjForEachFanout( p, pTemp, pFanout, iFanout, m )
240 {
241 if ( Aig_ObjIsNode(pFanout) && !pFanout->fMarkA )
242 {
243 assert( Aig_ObjLevel(pFanout) >= Lev );
244 Vec_VecPush( p->vLevels, Aig_ObjLevel(pFanout), pFanout );
245 pFanout->fMarkA = 1;
246 }
247 }
248 }
249 }
250
251 /**Function*************************************************************
252
253 Synopsis [Incrementally updates level of the nodes.]
254
255 Description []
256
257 SideEffects []
258
259 SeeAlso []
260
261 ***********************************************************************/
Aig_ManUpdateReverseLevel(Aig_Man_t * p,Aig_Obj_t * pObjNew)262 void Aig_ManUpdateReverseLevel( Aig_Man_t * p, Aig_Obj_t * pObjNew )
263 {
264 Aig_Obj_t * pFanin, * pTemp;
265 int LevelOld, LevFanin, Lev, k;
266 assert( p->vLevelR != NULL );
267 assert( Aig_ObjIsNode(pObjNew) );
268 // allocate level if needed
269 if ( p->vLevels == NULL )
270 p->vLevels = Vec_VecAlloc( Aig_ManLevels(p) + 8 );
271 // check if level has changed
272 LevelOld = Aig_ObjReverseLevel(p, pObjNew);
273 if ( LevelOld == Aig_ObjReverseLevelNew(p, pObjNew) )
274 return;
275 // start the data structure for level update
276 // we cannot fail to visit a node when using this structure because the
277 // nodes are stored by their _old_ levels, which are assumed to be correct
278 Vec_VecClear( p->vLevels );
279 Vec_VecPush( p->vLevels, LevelOld, pObjNew );
280 pObjNew->fMarkA = 1;
281 // recursively update level
282 Vec_VecForEachEntryStart( p->vLevels, pTemp, Lev, k, LevelOld )
283 {
284 pTemp->fMarkA = 0;
285 LevelOld = Aig_ObjReverseLevel(p, pTemp);
286 assert( LevelOld == Lev );
287 Aig_ObjSetReverseLevel( p, pTemp, Aig_ObjReverseLevelNew(p, pTemp) );
288 // if the level did not change, to need to check the fanout levels
289 if ( Aig_ObjReverseLevel(p, pTemp) == Lev )
290 continue;
291 // schedule fanins for level update
292 pFanin = Aig_ObjFanin0(pTemp);
293 if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
294 {
295 LevFanin = Aig_ObjReverseLevel( p, pFanin );
296 assert( LevFanin >= Lev );
297 Vec_VecPush( p->vLevels, LevFanin, pFanin );
298 pFanin->fMarkA = 1;
299 }
300 pFanin = Aig_ObjFanin1(pTemp);
301 if ( Aig_ObjIsNode(pFanin) && !pFanin->fMarkA )
302 {
303 LevFanin = Aig_ObjReverseLevel( p, pFanin );
304 assert( LevFanin >= Lev );
305 Vec_VecPush( p->vLevels, LevFanin, pFanin );
306 pFanin->fMarkA = 1;
307 }
308 }
309 }
310
311 /**Function*************************************************************
312
313 Synopsis [Verifies direct level of the nodes.]
314
315 Description []
316
317 SideEffects []
318
319 SeeAlso []
320
321 ***********************************************************************/
Aig_ManVerifyLevel(Aig_Man_t * p)322 void Aig_ManVerifyLevel( Aig_Man_t * p )
323 {
324 Aig_Obj_t * pObj;
325 int i, Counter = 0;
326 assert( p->pFanData );
327 Aig_ManForEachNode( p, pObj, i )
328 if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
329 {
330 printf( "Level of node %6d should be %4d instead of %4d.\n",
331 pObj->Id, Aig_ObjLevelNew(pObj), Aig_ObjLevel(pObj) );
332 Counter++;
333 }
334 if ( Counter )
335 printf( "Levels of %d nodes are incorrect.\n", Counter );
336 }
337
338 /**Function*************************************************************
339
340 Synopsis [Verifies reverse level of the nodes.]
341
342 Description []
343
344 SideEffects []
345
346 SeeAlso []
347
348 ***********************************************************************/
Aig_ManVerifyReverseLevel(Aig_Man_t * p)349 void Aig_ManVerifyReverseLevel( Aig_Man_t * p )
350 {
351 Aig_Obj_t * pObj;
352 int i, Counter = 0;
353 assert( p->vLevelR );
354 Aig_ManForEachNode( p, pObj, i )
355 if ( Aig_ObjLevel(pObj) != Aig_ObjLevelNew(pObj) )
356 {
357 printf( "Reverse level of node %6d should be %4d instead of %4d.\n",
358 pObj->Id, Aig_ObjReverseLevelNew(p, pObj), Aig_ObjReverseLevel(p, pObj) );
359 Counter++;
360 }
361 if ( Counter )
362 printf( "Reverse levels of %d nodes are incorrect.\n", Counter );
363 }
364
365 ////////////////////////////////////////////////////////////////////////
366 /// END OF FILE ///
367 ////////////////////////////////////////////////////////////////////////
368
369
370