1 /**CFile****************************************************************
2
3 FileName [giaEdge.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Edge-related 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: giaEdge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22 #include "misc/tim/tim.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
Gia_ObjEdgeCount(int iObj,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2)30 static inline int Gia_ObjEdgeCount( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
31 {
32 return (Vec_IntEntry(vEdge1, iObj) > 0) + (Vec_IntEntry(vEdge2, iObj) > 0);
33 }
Gia_ObjEdgeAdd(int iObj,int iNext,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2)34 static inline int Gia_ObjEdgeAdd( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
35 {
36 int RetValue = 0;
37 if ( Vec_IntEntry(vEdge1, iObj) == 0 )
38 Vec_IntWriteEntry(vEdge1, iObj, iNext);
39 else if ( Vec_IntEntry(vEdge2, iObj) == 0 )
40 Vec_IntWriteEntry(vEdge2, iObj, iNext);
41 else RetValue = 1;
42 return RetValue;
43 }
Gia_ObjEdgeRemove(int iObj,int iNext,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2)44 static inline void Gia_ObjEdgeRemove( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
45 {
46 assert( Vec_IntEntry(vEdge1, iObj) == iNext || Vec_IntEntry(vEdge2, iObj) == iNext );
47 if ( Vec_IntEntry(vEdge1, iObj) == iNext )
48 Vec_IntWriteEntry( vEdge1, iObj, Vec_IntEntry(vEdge2, iObj) );
49 Vec_IntWriteEntry( vEdge2, iObj, 0 );
50 }
Gia_ObjEdgeClean(int iObj,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2)51 static inline void Gia_ObjEdgeClean( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
52 {
53 Vec_IntWriteEntry( vEdge1, iObj, 0 );
54 Vec_IntWriteEntry( vEdge2, iObj, 0 );
55 }
56
57 ////////////////////////////////////////////////////////////////////////
58 /// FUNCTION DEFINITIONS ///
59 ////////////////////////////////////////////////////////////////////////
60
61 /**Function*************************************************************
62
63 Synopsis [Transforms edge assignment.]
64
65 Description []
66
67 SideEffects []
68
69 SeeAlso []
70
71 ***********************************************************************/
Gia_ManEdgeFromArray(Gia_Man_t * p,Vec_Int_t * vArray)72 void Gia_ManEdgeFromArray( Gia_Man_t * p, Vec_Int_t * vArray )
73 {
74 int i, iObj1, iObj2, Count = 0;
75 Vec_IntFreeP( &p->vEdge1 );
76 Vec_IntFreeP( &p->vEdge2 );
77 p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
78 p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
79 Vec_IntForEachEntryDouble( vArray, iObj1, iObj2, i )
80 {
81 assert( iObj1 < iObj2 );
82 Count += Gia_ObjEdgeAdd( iObj1, iObj2, p->vEdge1, p->vEdge2 );
83 Count += Gia_ObjEdgeAdd( iObj2, iObj1, p->vEdge1, p->vEdge2 );
84 }
85 if ( Count )
86 printf( "Found %d violations during edge conversion.\n", Count );
87 }
Gia_ManEdgeToArray(Gia_Man_t * p)88 Vec_Int_t * Gia_ManEdgeToArray( Gia_Man_t * p )
89 {
90 int iObj, iFanin;
91 Vec_Int_t * vArray = Vec_IntAlloc( 1000 );
92 assert( p->vEdge1 && p->vEdge2 );
93 assert( Vec_IntSize(p->vEdge1) == Gia_ManObjNum(p) );
94 assert( Vec_IntSize(p->vEdge2) == Gia_ManObjNum(p) );
95 for ( iObj = 0; iObj < Gia_ManObjNum(p); iObj++ )
96 {
97 iFanin = Vec_IntEntry( p->vEdge1, iObj );
98 if ( iFanin && iFanin < iObj )
99 Vec_IntPushTwo( vArray, iFanin, iObj );
100 iFanin = Vec_IntEntry( p->vEdge2, iObj );
101 if ( iFanin && iFanin < iObj )
102 Vec_IntPushTwo( vArray, iFanin, iObj );
103 }
104 return vArray;
105 }
106
107 /**Function*************************************************************
108
109 Synopsis [Prints mapping statistics.]
110
111 Description []
112
113 SideEffects []
114
115 SeeAlso []
116
117 ***********************************************************************/
Gia_ManConvertPackingToEdges(Gia_Man_t * p)118 void Gia_ManConvertPackingToEdges( Gia_Man_t * p )
119 {
120 int i, k, Entry, nEntries, nEntries2, nNodes[4], Count = 0;
121 if ( p->vPacking == NULL )
122 return;
123 Vec_IntFreeP( &p->vEdge1 );
124 Vec_IntFreeP( &p->vEdge2 );
125 p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
126 p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
127 // iterate through structures
128 nEntries = Vec_IntEntry( p->vPacking, 0 );
129 nEntries2 = 0;
130 Vec_IntForEachEntryStart( p->vPacking, Entry, i, 1 )
131 {
132 assert( Entry > 0 && Entry < 4 );
133 i++;
134 for ( k = 0; k < Entry; k++, i++ )
135 nNodes[k] = Vec_IntEntry(p->vPacking, i);
136 i--;
137 nEntries2++;
138 // create edges
139 if ( Entry == 2 )
140 {
141 Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[1], p->vEdge1, p->vEdge2 );
142 Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[0], p->vEdge1, p->vEdge2 );
143 }
144 else if ( Entry == 3 )
145 {
146 Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[2], p->vEdge1, p->vEdge2 );
147 Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[0], p->vEdge1, p->vEdge2 );
148 Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[2], p->vEdge1, p->vEdge2 );
149 Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[1], p->vEdge1, p->vEdge2 );
150 }
151 }
152 assert( nEntries == nEntries2 );
153 if ( Count )
154 printf( "Skipped %d illegal edges.\n", Count );
155 }
156
157 /**Function*************************************************************
158
159 Synopsis [Evaluates given edge assignment.]
160
161 Description []
162
163 SideEffects []
164
165 SeeAlso []
166
167 ***********************************************************************/
Gia_ObjHaveEdge(Gia_Man_t * p,int iObj,int iNext)168 static inline int Gia_ObjHaveEdge( Gia_Man_t * p, int iObj, int iNext )
169 {
170 return Vec_IntEntry(p->vEdge1, iObj) == iNext || Vec_IntEntry(p->vEdge2, iObj) == iNext;
171 }
Gia_ObjCheckEdge(Gia_Man_t * p,int iObj,int iNext)172 int Gia_ObjCheckEdge( Gia_Man_t * p, int iObj, int iNext )
173 {
174 return Gia_ObjHaveEdge( p, iObj, iNext );
175 }
Gia_ObjEvalEdgeDelay(Gia_Man_t * p,int iObj,Vec_Int_t * vDelay)176 static inline int Gia_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
177 {
178 int nEdgeDelay = 2;
179 int i, iFan, Delay, DelayMax = 0;
180 if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
181 {
182 assert( Gia_ObjLutSize(p, iObj) <= 4 );
183 Gia_LutForEachFanin( p, iObj, iFan, i )
184 {
185 Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
186 DelayMax = Abc_MaxInt( DelayMax, Delay );
187 }
188 }
189 else if ( Gia_ObjIsLut2(p, iObj) )
190 {
191 assert( Gia_ObjLutSize2(p, iObj) <= 4 );
192 Gia_LutForEachFanin2( p, iObj, iFan, i )
193 {
194 Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
195 DelayMax = Abc_MaxInt( DelayMax, Delay );
196 }
197 }
198 else assert( 0 );
199 return DelayMax;
200 }
Gia_ManEvalEdgeDelay(Gia_Man_t * p)201 int Gia_ManEvalEdgeDelay( Gia_Man_t * p )
202 {
203 int k, iLut, DelayMax = 0;
204 assert( p->vEdge1 && p->vEdge2 );
205 Vec_IntFreeP( &p->vEdgeDelay );
206 p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
207 if ( Gia_ManHasMapping(p) )
208 {
209 if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
210 {
211 Gia_Obj_t * pObj;
212 Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
213 Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
214 Gia_ManForEachObjVec( vNodes, p, pObj, k )
215 {
216 iLut = Gia_ObjId( p, pObj );
217 if ( Gia_ObjIsAnd(pObj) )
218 {
219 if ( Gia_ObjIsLut(p, iLut) )
220 Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
221 }
222 else if ( Gia_ObjIsCi(pObj) )
223 {
224 int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
225 Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
226 }
227 else if ( Gia_ObjIsCo(pObj) )
228 {
229 int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
230 Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
231 }
232 else if ( !Gia_ObjIsConst0(pObj) )
233 assert( 0 );
234 }
235 Vec_IntFree( vNodes );
236 }
237 else
238 {
239 Gia_ManForEachLut( p, iLut )
240 Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
241 }
242 }
243 else if ( Gia_ManHasMapping2(p) )
244 {
245 if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
246 {
247 Gia_Obj_t * pObj;
248 Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
249 Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
250 Gia_ManForEachObjVec( vNodes, p, pObj, k )
251 {
252 iLut = Gia_ObjId( p, pObj );
253 if ( Gia_ObjIsAnd(pObj) )
254 {
255 if ( Gia_ObjIsLut2(p, iLut) )
256 Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
257 }
258 else if ( Gia_ObjIsCi(pObj) )
259 {
260 int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
261 Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
262 }
263 else if ( Gia_ObjIsCo(pObj) )
264 {
265 int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
266 Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
267 }
268 else if ( !Gia_ObjIsConst0(pObj) )
269 assert( 0 );
270 }
271 Vec_IntFree( vNodes );
272 }
273 else
274 {
275 Gia_ManForEachLut2( p, iLut )
276 Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
277 }
278 }
279 else assert( 0 );
280 Gia_ManForEachCoDriverId( p, iLut, k )
281 DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
282 return DelayMax;
283 }
Gia_ManEvalEdgeCount(Gia_Man_t * p)284 int Gia_ManEvalEdgeCount( Gia_Man_t * p )
285 {
286 return (Vec_IntCountPositive(p->vEdge1) + Vec_IntCountPositive(p->vEdge2))/2;
287 }
288
289
290 /**Function*************************************************************
291
292 Synopsis [Finds edge assignment.]
293
294 Description []
295
296 SideEffects []
297
298 SeeAlso []
299
300 ***********************************************************************/
Gia_ObjComputeEdgeDelay(Gia_Man_t * p,int iObj,Vec_Int_t * vDelay,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2,int fUseTwo)301 int Gia_ObjComputeEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, int fUseTwo )
302 {
303 int i, iFan, Delay, Status1, Status2;
304 int DelayMax = 0, DelayMax2 = 0, nCountMax = 0;
305 int iFanMax1 = -1, iFanMax2 = -1;
306 Vec_IntWriteEntry(vEdge1, iObj, 0);
307 Vec_IntWriteEntry(vEdge2, iObj, 0);
308 if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
309 {
310 assert( Gia_ObjLutSize(p, iObj) <= 4 );
311 Gia_LutForEachFanin( p, iObj, iFan, i )
312 {
313 Delay = Vec_IntEntry( vDelay, iFan ) + 10;
314 if ( DelayMax < Delay )
315 {
316 DelayMax2 = DelayMax;
317 DelayMax = Delay;
318 iFanMax1 = iFan;
319 nCountMax = 1;
320 }
321 else if ( DelayMax == Delay )
322 {
323 iFanMax2 = iFan;
324 nCountMax++;
325 if ( !fUseTwo )
326 DelayMax2 = DelayMax;
327 }
328 else
329 DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
330 }
331 }
332 else if ( Gia_ObjIsLut2(p, iObj) )
333 {
334 assert( Gia_ObjLutSize2(p, iObj) <= 4 );
335 Gia_LutForEachFanin2( p, iObj, iFan, i )
336 {
337 Delay = Vec_IntEntry( vDelay, iFan ) + 10;
338 if ( DelayMax < Delay )
339 {
340 DelayMax2 = DelayMax;
341 DelayMax = Delay;
342 iFanMax1 = iFan;
343 nCountMax = 1;
344 }
345 else if ( DelayMax == Delay )
346 {
347 iFanMax2 = iFan;
348 nCountMax++;
349 if ( !fUseTwo )
350 DelayMax2 = DelayMax;
351 }
352 else
353 DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
354 }
355 }
356 else assert( 0 );
357 assert( nCountMax > 0 );
358 if ( DelayMax <= 10 )
359 {} // skip first level
360 else if ( nCountMax == 1 )
361 {
362 Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
363 if ( Status1 <= 1 )
364 {
365 Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
366 Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
367 DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
368 Vec_IntWriteEntry( vDelay, iObj, DelayMax );
369 return DelayMax;
370 }
371 }
372 else if ( fUseTwo && nCountMax == 2 )
373 {
374 Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
375 Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
376 if ( Status1 <= 1 && Status2 <= 1 )
377 {
378 Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
379 Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
380 Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
381 Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
382 DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
383 Vec_IntWriteEntry( vDelay, iObj, DelayMax );
384 return DelayMax;
385 }
386 }
387 Vec_IntWriteEntry( vDelay, iObj, DelayMax );
388 return DelayMax;
389 }
Gia_ManComputeEdgeDelay(Gia_Man_t * p,int fUseTwo)390 int Gia_ManComputeEdgeDelay( Gia_Man_t * p, int fUseTwo )
391 {
392 int k, iLut, DelayMax = 0;
393 Vec_IntFreeP( &p->vEdgeDelay );
394 Vec_IntFreeP( &p->vEdge1 );
395 Vec_IntFreeP( &p->vEdge2 );
396 p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
397 p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
398 p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
399 if ( Gia_ManHasMapping(p) )
400 {
401 if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
402 {
403 Gia_Obj_t * pObj;
404 Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
405 Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
406 Gia_ManForEachObjVec( vNodes, p, pObj, k )
407 {
408 iLut = Gia_ObjId( p, pObj );
409 if ( Gia_ObjIsAnd(pObj) )
410 {
411 if ( Gia_ObjIsLut(p, iLut) )
412 Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
413 }
414 else if ( Gia_ObjIsCi(pObj) )
415 {
416 int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
417 Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
418 }
419 else if ( Gia_ObjIsCo(pObj) )
420 {
421 int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
422 Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
423 }
424 else if ( !Gia_ObjIsConst0(pObj) )
425 assert( 0 );
426 }
427 Vec_IntFree( vNodes );
428 }
429 else
430 {
431 Gia_ManForEachLut( p, iLut )
432 Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
433 }
434 }
435 else if ( Gia_ManHasMapping2(p) )
436 {
437 if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
438 {
439 Gia_Obj_t * pObj;
440 Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
441 Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
442 Gia_ManForEachObjVec( vNodes, p, pObj, k )
443 {
444 iLut = Gia_ObjId( p, pObj );
445 if ( Gia_ObjIsAnd(pObj) )
446 {
447 if ( Gia_ObjIsLut2(p, iLut) )
448 Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
449 }
450 else if ( Gia_ObjIsCi(pObj) )
451 {
452 int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
453 Vec_IntWriteEntry( p->vEdgeDelay, iLut, arrTime );
454 }
455 else if ( Gia_ObjIsCo(pObj) )
456 {
457 int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
458 Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
459 }
460 else if ( !Gia_ObjIsConst0(pObj) )
461 assert( 0 );
462 }
463 Vec_IntFree( vNodes );
464 }
465 else
466 {
467 Gia_ManForEachLut2( p, iLut )
468 Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
469 }
470 }
471 else assert( 0 );
472 Gia_ManForEachCoDriverId( p, iLut, k )
473 DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
474 //printf( "The number of edges = %d. Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
475 return DelayMax;
476 }
477
478 /**Function*************************************************************
479
480 Synopsis [Finds edge assignment.]
481
482 Description []
483
484 SideEffects []
485
486 SeeAlso []
487
488 ***********************************************************************/
Gia_ObjComputeEdgeDelay2(Gia_Man_t * p,int iObj,Vec_Int_t * vDelay,Vec_Int_t * vEdge1,Vec_Int_t * vEdge2,Vec_Int_t * vFanMax1,Vec_Int_t * vFanMax2,Vec_Int_t * vCountMax)489 int Gia_ObjComputeEdgeDelay2( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, Vec_Int_t * vFanMax1, Vec_Int_t * vFanMax2, Vec_Int_t * vCountMax )
490 {
491 int i, iFan, DelayFanin, Status1, Status2;
492 int DelayMax = 0, nCountMax = 0;
493 int iFanMax1 = -1, iFanMax2 = -1;
494 Vec_IntWriteEntry(vEdge1, iObj, 0);
495 Vec_IntWriteEntry(vEdge2, iObj, 0);
496 // analyze this node
497 DelayMax = Vec_IntEntry( vDelay, iObj );
498 nCountMax = Vec_IntEntry( vCountMax, iObj );
499 if ( DelayMax == 0 )
500 {}
501 else if ( nCountMax == 1 )
502 {
503 iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
504 Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
505 if ( Status1 <= 1 )
506 {
507 Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
508 Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
509 DelayMax--;
510 }
511 }
512 else if ( nCountMax == 2 )
513 {
514 iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
515 iFanMax2 = Vec_IntEntry( vFanMax2, iObj );
516 Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
517 Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
518 if ( Status1 <= 1 && Status2 <= 1 )
519 {
520 Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
521 Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
522 Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
523 Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
524 DelayMax--;
525 }
526 }
527 Vec_IntWriteEntry( vDelay, iObj, DelayMax );
528 // computed DelayMax at this point
529 if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
530 {
531 Gia_LutForEachFanin( p, iObj, iFan, i )
532 {
533 DelayFanin = Vec_IntEntry( vDelay, iFan );
534 if ( DelayFanin < DelayMax + 1 )
535 {
536 Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
537 Vec_IntWriteEntry( vFanMax1, iFan, iObj );
538 Vec_IntWriteEntry( vCountMax, iFan, 1 );
539 }
540 else if ( DelayFanin == DelayMax + 1 )
541 {
542 Vec_IntWriteEntry( vFanMax2, iFan, iObj );
543 Vec_IntAddToEntry( vCountMax, iFan, 1 );
544 }
545 }
546 }
547 else if ( Gia_ObjIsLut2(p, iObj) )
548 {
549 Gia_LutForEachFanin2( p, iObj, iFan, i )
550 {
551 DelayFanin = Vec_IntEntry( vDelay, iFan );
552 if ( DelayFanin < DelayMax + 1 )
553 {
554 Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
555 Vec_IntWriteEntry( vFanMax1, iFan, iObj );
556 Vec_IntWriteEntry( vCountMax, iFan, 1 );
557 }
558 else if ( DelayFanin == DelayMax + 1 )
559 {
560 Vec_IntWriteEntry( vFanMax2, iFan, iObj );
561 Vec_IntAddToEntry( vCountMax, iFan, 1 );
562 }
563 }
564 }
565 else assert( 0 );
566 return DelayMax;
567 }
Gia_ManComputeEdgeDelay2(Gia_Man_t * p)568 int Gia_ManComputeEdgeDelay2( Gia_Man_t * p )
569 {
570 int k, iLut, DelayMax = 0;
571 Vec_Int_t * vFanMax1 = Vec_IntStart( Gia_ManObjNum(p) );
572 Vec_Int_t * vFanMax2 = Vec_IntStart( Gia_ManObjNum(p) );
573 Vec_Int_t * vCountMax = Vec_IntStart( Gia_ManObjNum(p) );
574 assert( p->pManTime == NULL );
575 Vec_IntFreeP( &p->vEdgeDelay );
576 Vec_IntFreeP( &p->vEdge1 );
577 Vec_IntFreeP( &p->vEdge2 );
578 p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
579 p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
580 p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
581 // Gia_ManForEachCoDriverId( p, iLut, k )
582 // Vec_IntWriteEntry( p->vEdgeDelay, iLut, 1 );
583 if ( Gia_ManHasMapping(p) )
584 Gia_ManForEachLutReverse( p, iLut )
585 Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
586 else if ( Gia_ManHasMapping2(p) )
587 Gia_ManForEachLut2Reverse( p, iLut )
588 Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
589 else assert( 0 );
590 Gia_ManForEachCiId( p, iLut, k )
591 DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
592 Vec_IntFree( vFanMax1 );
593 Vec_IntFree( vFanMax2 );
594 Vec_IntFree( vCountMax );
595 //printf( "The number of edges = %d. Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
596 return DelayMax;
597 }
598
599 /**Function*************************************************************
600
601 Synopsis [Finds edge assignment.]
602
603 Description []
604
605 SideEffects []
606
607 SeeAlso []
608
609 ***********************************************************************/
Gia_ManUpdateMapping(Gia_Man_t * p,Vec_Int_t * vNodes,Vec_Wec_t * vWin)610 void Gia_ManUpdateMapping( Gia_Man_t * p, Vec_Int_t * vNodes, Vec_Wec_t * vWin )
611 {
612 int i, iNode;
613 Vec_IntForEachEntry( vNodes, iNode, i )
614 ABC_SWAP( Vec_Int_t, *Vec_WecEntry(p->vMapping2, iNode), *Vec_WecEntry(vWin, i) );
615 }
Gia_ManEvalWindowInc(Gia_Man_t * p,Vec_Int_t * vLeaves,Vec_Int_t * vNodes,Vec_Wec_t * vWin,Vec_Int_t * vTemp,int fUseTwo)616 int Gia_ManEvalWindowInc( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
617 {
618 int i, iLut, Delay, DelayMax = 0;
619 assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
620 Gia_ManUpdateMapping( p, vNodes, vWin );
621 Gia_ManCollectTfo( p, vLeaves, vTemp );
622 Vec_IntReverseOrder( vTemp );
623 Vec_IntForEachEntry( vTemp, iLut, i )
624 {
625 if ( !Gia_ObjIsLut(p, iLut) )
626 continue;
627 Delay = Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
628 DelayMax = Abc_MaxInt( DelayMax, Delay );
629 }
630 Gia_ManUpdateMapping( p, vNodes, vWin );
631 return DelayMax;
632 }
Gia_ManEvalWindow(Gia_Man_t * p,Vec_Int_t * vLeaves,Vec_Int_t * vNodes,Vec_Wec_t * vWin,Vec_Int_t * vTemp,int fUseTwo)633 int Gia_ManEvalWindow( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
634 {
635 int DelayMax;
636 assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
637 Gia_ManUpdateMapping( p, vNodes, vWin );
638 DelayMax = Gia_ManComputeEdgeDelay( p, fUseTwo );
639 Gia_ManUpdateMapping( p, vNodes, vWin );
640 return DelayMax;
641 }
642
643
644
645
646 /**Function*************************************************************
647
648 Synopsis []
649
650 Description []
651
652 SideEffects []
653
654 SeeAlso []
655
656 ***********************************************************************/
Edg_ManToMapping(Gia_Man_t * p)657 void Edg_ManToMapping( Gia_Man_t * p )
658 {
659 int iObj, iFanin, k;
660 assert( Gia_ManHasMapping(p) );
661 Vec_WecFreeP( &p->vMapping2 );
662 Vec_WecFreeP( &p->vFanouts2 );
663 p->vMapping2 = Vec_WecStart( Gia_ManObjNum(p) );
664 p->vFanouts2 = Vec_WecStart( Gia_ManObjNum(p) );
665 Gia_ManForEachLut( p, iObj )
666 {
667 assert( Gia_ObjLutSize(p, iObj) <= 4 );
668 Gia_LutForEachFanin( p, iObj, iFanin, k )
669 {
670 Vec_WecPush( p->vMapping2, iObj, iFanin );
671 Vec_WecPush( p->vFanouts2, iFanin, iObj );
672 }
673 }
674 }
675
676 /**Function*************************************************************
677
678 Synopsis [Computes delay for the given edge assignment.]
679
680 Description []
681
682 SideEffects []
683
684 SeeAlso []
685
686 ***********************************************************************/
Edg_ObjEvalEdgeDelay(Gia_Man_t * p,int iObj,Vec_Int_t * vDelay)687 static inline int Edg_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
688 {
689 int DelayEdge = 0; // 2;
690 int DelayNoEdge = 1;
691 int i, iFan, Delay, DelayMax = 0;
692 assert( Gia_ObjIsLut2(p, iObj) );
693 Gia_LutForEachFanin2( p, iObj, iFan, i )
694 {
695 Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
696 DelayMax = Abc_MaxInt( DelayMax, Delay );
697 }
698 //printf( "Obj %d - Level %d\n", iObj, DelayMax );
699 return DelayMax;
700 }
Edg_ManEvalEdgeDelay(Gia_Man_t * p)701 int Edg_ManEvalEdgeDelay( Gia_Man_t * p )
702 {
703 int iLut, Delay, DelayMax = 0;
704 assert( p->vEdge1 && p->vEdge2 );
705 if ( p->vEdgeDelay == NULL )
706 p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
707 else
708 Vec_IntFill( p->vEdgeDelay, Gia_ManObjNum(p), 0 );
709 Gia_ManForEachLut2( p, iLut )
710 {
711 Delay = Edg_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay);
712 Vec_IntWriteEntry( p->vEdgeDelay, iLut, Delay );
713 DelayMax = Abc_MaxInt( DelayMax, Delay );
714 }
715 return DelayMax;
716 }
717
Edg_ObjEvalEdgeDelayR(Gia_Man_t * p,int iObj,Vec_Int_t * vDelay)718 static inline int Edg_ObjEvalEdgeDelayR( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
719 {
720 int DelayEdge = 0; // 2;
721 int DelayNoEdge = 1;
722 int i, iFan, Delay, DelayMax = 0;
723 assert( Gia_ObjIsLut2(p, iObj) );
724 Gia_LutForEachFanout2( p, iObj, iFan, i )
725 {
726 Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
727 DelayMax = Abc_MaxInt( DelayMax, Delay );
728 }
729 //printf( "Obj %d - LevelR %d\n", iObj, DelayMax );
730 return DelayMax;
731 }
Edg_ManEvalEdgeDelayR(Gia_Man_t * p)732 int Edg_ManEvalEdgeDelayR( Gia_Man_t * p )
733 {
734 // int k, DelayNoEdge = 1;
735 int iLut, Delay, DelayMax = 0;
736 assert( p->vEdge1 && p->vEdge2 );
737 if ( p->vEdgeDelayR == NULL )
738 p->vEdgeDelayR = Vec_IntStart( Gia_ManObjNum(p) );
739 else
740 Vec_IntFill( p->vEdgeDelayR, Gia_ManObjNum(p), 0 );
741 // Gia_ManForEachCoDriverId( p, iLut, k )
742 // Vec_IntWriteEntry( p->vEdgeDelayR, iLut, DelayNoEdge );
743 Gia_ManForEachLut2Reverse( p, iLut )
744 {
745 Delay = Edg_ObjEvalEdgeDelayR(p, iLut, p->vEdgeDelayR);
746 Vec_IntWriteEntry( p->vEdgeDelayR, iLut, Delay );
747 DelayMax = Abc_MaxInt( DelayMax, Delay );
748 }
749 return DelayMax;
750 }
751
Edg_ManCollectCritEdges(Gia_Man_t * p,Vec_Wec_t * vEdges,int DelayMax)752 void Edg_ManCollectCritEdges( Gia_Man_t * p, Vec_Wec_t * vEdges, int DelayMax )
753 {
754 Vec_Int_t * vLevel;
755 int k, iLut, Delay1, Delay2;
756 assert( p->vEdge1 && p->vEdge2 );
757 Vec_WecClear( vEdges );
758 Vec_WecInit( vEdges, DelayMax + 1 );
759 Gia_ManForEachLut2( p, iLut )
760 {
761 Delay1 = Vec_IntEntry( p->vEdgeDelay, iLut );
762 Delay2 = Vec_IntEntry( p->vEdgeDelayR, iLut );
763 assert( Delay1 + Delay2 <= DelayMax );
764 if ( Delay1 + Delay2 == DelayMax )
765 Vec_WecPush( vEdges, Delay1, iLut );
766 }
767 // every level should have critical nodes, except the first one
768 //Vec_WecPrint( vEdges, 0 );
769 Vec_WecForEachLevelStart( vEdges, vLevel, k, 1 )
770 assert( Vec_IntSize(vLevel) > 0 );
771 }
772
773
774 /**Function*************************************************************
775
776 Synopsis [Update one node.]
777
778 Description []
779
780 SideEffects []
781
782 SeeAlso []
783
784 ***********************************************************************/
Edg_ObjImprove(Gia_Man_t * p,int iObj,int nEdgeLimit,int DelayMax,int fVerbose)785 int Edg_ObjImprove( Gia_Man_t * p, int iObj, int nEdgeLimit, int DelayMax, int fVerbose )
786 {
787 int nFaninsC = 0, nFanoutsC = 0; // critical
788 int nFaninsEC = 0, nFanoutsEC = 0; // edge-critical
789 int nFaninsENC = 0, nFanoutsENC = 0; // edge-non-critial
790 int pFanins[4], pFanouts[4];
791 int nEdgeDiff, nEdges = 0, Count = 0;
792 int i, iNext, Delay1, Delay2;
793 // count how many fanins have critical edge
794 Delay1 = Vec_IntEntry( p->vEdgeDelayR, iObj );
795 //if ( Delay1 > 1 )
796 Gia_LutForEachFanin2( p, iObj, iNext, i )
797 {
798 if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
799 continue;
800 Delay2 = Vec_IntEntry( p->vEdgeDelay, iNext );
801 if ( Gia_ObjHaveEdge(p, iObj, iNext) )
802 {
803 nEdges++;
804 assert( Delay1 + Delay2 <= DelayMax );
805 if ( Delay1 + Delay2 == DelayMax )
806 nFaninsEC++;
807 else
808 nFaninsENC++;
809 }
810 else
811 {
812 assert( Delay1 + Delay2 + 1 <= DelayMax );
813 if ( Delay1 + Delay2 + 1 == DelayMax )
814 pFanins[nFaninsC++] = iNext;
815 }
816 }
817 // count how many fanouts have critical edge
818 Delay1 = Vec_IntEntry( p->vEdgeDelay, iObj );
819 //if ( Delay2 < DelayMax - 1 )
820 Gia_LutForEachFanout2( p, iObj, iNext, i )
821 {
822 //if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
823 // continue;
824 assert( Gia_ObjIsAnd(Gia_ManObj(p, iNext)) );
825 Delay2 = Vec_IntEntry( p->vEdgeDelayR, iNext );
826 if ( Gia_ObjHaveEdge(p, iObj, iNext) )
827 {
828 nEdges++;
829 assert( Delay1 + Delay2 <= DelayMax );
830 if ( Delay1 + Delay2 == DelayMax )
831 nFanoutsEC++;
832 else
833 nFanoutsENC++;
834 }
835 else
836 {
837 assert( Delay1 + Delay2 + 1 <= DelayMax );
838 if ( Delay1 + Delay2 + 1 == DelayMax )
839 {
840 if ( nFanoutsC < nEdgeLimit )
841 pFanouts[nFanoutsC] = iNext;
842 nFanoutsC++;
843 }
844 }
845 }
846 if ( fVerbose )
847 {
848 printf( "%8d : ", iObj );
849 printf( "Edges = %d ", nEdges );
850 printf( "Fanins (all %d EC %d ENC %d C %d) ",
851 Gia_ObjLutSize2(p, iObj), nFaninsEC, nFaninsENC, nFaninsC );
852 printf( "Fanouts (all %d EC %d ENC %d C %d) ",
853 Gia_ObjLutFanoutNum2(p, iObj), nFanoutsEC, nFanoutsENC, nFanoutsC );
854 }
855 // consider simple cases
856 assert( nEdges <= nEdgeLimit );
857 if ( nEdges == nEdgeLimit )
858 {
859 if ( fVerbose )
860 printf( "Full\n" );
861 return 0;
862 }
863 nEdgeDiff = nEdgeLimit - nEdges;
864 // check if fanins or fanouts could be improved
865 if ( nFaninsEC == 0 && nFaninsC && nFaninsC <= nEdgeDiff )
866 {
867 for ( i = 0; i < nFaninsC; i++ )
868 if ( Gia_ObjEdgeCount(pFanins[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
869 break;
870 if ( i == nFaninsC )
871 {
872 for ( i = 0; i < nFaninsC; i++ )
873 {
874 Count += Gia_ObjEdgeAdd( iObj, pFanins[i], p->vEdge1, p->vEdge2 );
875 Count += Gia_ObjEdgeAdd( pFanins[i], iObj, p->vEdge1, p->vEdge2 );
876 }
877 if ( Count )
878 printf( "Wrong number of edges.\n" );
879 if ( fVerbose )
880 printf( "Fixed %d critical fanins\n", nFaninsC );
881 return 1;
882 }
883 }
884 if ( nFanoutsEC == 0 && nFanoutsC && nFanoutsC <= nEdgeDiff )
885 {
886 for ( i = 0; i < nFanoutsC; i++ )
887 if ( Gia_ObjEdgeCount(pFanouts[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
888 break;
889 if ( i == nFanoutsC )
890 {
891 for ( i = 0; i < nFanoutsC; i++ )
892 {
893 Count += Gia_ObjEdgeAdd( iObj, pFanouts[i], p->vEdge1, p->vEdge2 );
894 Count += Gia_ObjEdgeAdd( pFanouts[i], iObj, p->vEdge1, p->vEdge2 );
895 }
896 if ( Count )
897 printf( "Wrong number of edges.\n" );
898 if ( fVerbose )
899 printf( "Fixed %d critical fanouts\n", nFanoutsC );
900 return 1;
901 }
902 }
903 if ( fVerbose )
904 printf( "Cannot fix\n" );
905 return 0;
906 }
907
908 /**Function*************************************************************
909
910 Synopsis [Finds edge assignment.]
911
912 Description []
913
914 SideEffects []
915
916 SeeAlso []
917
918 ***********************************************************************/
Edg_ManAssignEdgeNew(Gia_Man_t * p,int nEdges,int fVerbose)919 int Edg_ManAssignEdgeNew( Gia_Man_t * p, int nEdges, int fVerbose )
920 {
921 int DelayNoEdge = 1;
922 int fLevelVerbose = 0;
923 Vec_Int_t * vLevel;
924 Vec_Wec_t * vEdges = Vec_WecStart(0);
925 Vec_Int_t * vEdge1 = NULL, * vEdge2 = NULL;
926 int DelayD = 0, DelayR = 0, DelayPrev = ABC_INFINITY;
927 int k, j, i, iLast = -1, iObj;
928 if ( fVerbose )
929 printf( "Running edge assignment with E = %d.\n", nEdges );
930 // create fanouts
931 Edg_ManToMapping( p );
932 // create empty assignment
933 Vec_IntFreeP( &p->vEdge1 );
934 Vec_IntFreeP( &p->vEdge2 );
935 p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
936 p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
937 // perform optimization
938 for ( i = 0; i < 10000; i++ )
939 {
940 // if there is no improvement after 10 iterations, quit
941 if ( i > iLast + 50 )
942 break;
943 // create delay information
944 DelayD = Edg_ManEvalEdgeDelay( p );
945 DelayR = Edg_ManEvalEdgeDelayR( p );
946 assert( DelayD == DelayR + DelayNoEdge );
947 if ( DelayPrev > DelayD )
948 {
949 //printf( "Saving backup point at %d levels.\n", DelayD );
950 Vec_IntFreeP( &vEdge1 ); vEdge1 = Vec_IntDup( p->vEdge1 );
951 Vec_IntFreeP( &vEdge2 ); vEdge2 = Vec_IntDup( p->vEdge2 );
952 DelayPrev = DelayD;
953 iLast = i;
954 }
955 if ( fVerbose )
956 printf( "\nIter %4d : Delay = %4d\n", i, DelayD );
957 // collect critical nodes (nodes with critical edges)
958 Edg_ManCollectCritEdges( p, vEdges, DelayD );
959 // sort levels according to the number of critical edges
960 if ( fLevelVerbose )
961 {
962 Vec_WecForEachLevel( vEdges, vLevel, k )
963 Vec_IntPush( vLevel, k );
964 }
965 Vec_WecSort( vEdges, 0 );
966 if ( fLevelVerbose )
967 {
968 Vec_WecForEachLevel( vEdges, vLevel, k )
969 {
970 int Level = Vec_IntPop( vLevel );
971 printf( "%d: Level %2d : ", k, Level );
972 Vec_IntPrint( vLevel );
973 }
974 }
975 Vec_WecForEachLevel( vEdges, vLevel, k )
976 {
977 Vec_IntForEachEntry( vLevel, iObj, j )
978 if ( Edg_ObjImprove(p, iObj, nEdges, DelayD, fVerbose) ) // improved
979 break;
980 if ( j < Vec_IntSize(vLevel) )
981 break;
982 }
983 if ( k == Vec_WecSize(vEdges) ) // if we could not improve anything, quit
984 break;
985 }
986 Vec_WecFree( vEdges );
987 // update to the saved version
988 Vec_IntFreeP( &p->vEdge1 ); p->vEdge1 = vEdge1;
989 Vec_IntFreeP( &p->vEdge2 ); p->vEdge2 = vEdge2;
990 return DelayD;
991 }
992
993
994 ////////////////////////////////////////////////////////////////////////
995 /// END OF FILE ///
996 ////////////////////////////////////////////////////////////////////////
997
998
999 ABC_NAMESPACE_IMPL_END
1000
1001