1 /**CFile****************************************************************
2
3 FileName [giaFrames.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Timeframe unrolling.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaFrames.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 typedef struct Gia_ManFra_t_ Gia_ManFra_t;
31 struct Gia_ManFra_t_
32 {
33 Gia_ParFra_t * pPars; // parameters
34 Gia_Man_t * pAig; // AIG to unroll
35 Vec_Ptr_t * vIns; // inputs of each timeframe
36 Vec_Ptr_t * vAnds; // nodes of each timeframe
37 Vec_Ptr_t * vOuts; // outputs of each timeframe
38 };
39
40
41 typedef struct Gia_ManUnr_t_ Gia_ManUnr_t;
42 struct Gia_ManUnr_t_
43 {
44 Gia_ParFra_t * pPars; // parameters
45 Gia_Man_t * pAig; // AIG to unroll (points to pOrder)
46 // internal data
47 Gia_Man_t * pOrder; // AIG reordered (points to pAig)
48 Vec_Int_t * vLimit; // limits of each timeframe
49 // data for each ordered node
50 Vec_Int_t * vRank; // rank of each node
51 Vec_Int_t * vDegree; // degree of each node
52 Vec_Int_t * vDegDiff; // degree of each node
53 Vec_Int_t * vFirst; // first entry in the store
54 Vec_Int_t * vStore; // store for saved data
55 // the resulting AIG
56 Gia_Man_t * pNew; // the resulting AIG
57 int LastLit; // the place to store the last literal
58 };
59
60 ////////////////////////////////////////////////////////////////////////
61 /// FUNCTION DEFINITIONS ///
62 ////////////////////////////////////////////////////////////////////////
63
64 /**Function*************************************************************
65
66 Synopsis [Duplicates AIG for unrolling.]
67
68 Description []
69
70 SideEffects []
71
72 SeeAlso []
73
74 ***********************************************************************/
Gia_ManUnrollDup_rec(Gia_Man_t * pNew,Gia_Obj_t * pObj,int Id)75 void Gia_ManUnrollDup_rec( Gia_Man_t * pNew, Gia_Obj_t * pObj, int Id )
76 {
77 if ( ~pObj->Value )
78 return;
79 if ( Gia_ObjIsCi(pObj) )
80 pObj->Value = Gia_ManAppendCi(pNew);
81 else if ( Gia_ObjIsCo(pObj) )
82 {
83 Gia_ManUnrollDup_rec( pNew, Gia_ObjFanin0(pObj), Gia_ObjFaninId0(pObj, Id) );
84 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
85 }
86 else if ( Gia_ObjIsAnd(pObj) )
87 {
88 Gia_ManUnrollDup_rec( pNew, Gia_ObjFanin0(pObj), Gia_ObjFaninId0(pObj, Id) );
89 Gia_ManUnrollDup_rec( pNew, Gia_ObjFanin1(pObj), Gia_ObjFaninId1(pObj, Id) );
90 pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
91 }
92 else assert( 0 );
93 Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value))->Value = Id;
94 }
95
96 /**Function*************************************************************
97
98 Synopsis [Duplicates AIG for unrolling.]
99
100 Description []
101
102 SideEffects []
103
104 SeeAlso []
105
106 ***********************************************************************/
Gia_ManUnrollDup(Gia_Man_t * p,Vec_Int_t * vLimit)107 Gia_Man_t * Gia_ManUnrollDup( Gia_Man_t * p, Vec_Int_t * vLimit )
108 {
109 Gia_Man_t * pNew;
110 Gia_Obj_t * pObj;
111 int i;
112 assert( Vec_IntSize(vLimit) == 0 );
113 pNew = Gia_ManStart( Gia_ManObjNum(p) );
114 pNew->pName = Abc_UtilStrsav( p->pName );
115 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
116
117 // save constant class
118 Gia_ManFillValue( p );
119 Gia_ManConst0(p)->Value = 0;
120 Vec_IntPush( vLimit, Gia_ManObjNum(pNew) );
121
122 // create first class
123 Gia_ManForEachPo( p, pObj, i )
124 Gia_ManUnrollDup_rec( pNew, pObj, Gia_ObjId(p, pObj) );
125 Vec_IntPush( vLimit, Gia_ManObjNum(pNew) );
126
127 // create next classes
128 for ( i = 1; i < Gia_ManObjNum(pNew); i++ )
129 {
130 if ( i == Vec_IntEntryLast(vLimit) )
131 Vec_IntPush( vLimit, Gia_ManObjNum(pNew) );
132 pObj = Gia_ManObj( p, Gia_ManObj(pNew, i)->Value );
133 if ( Gia_ObjIsRo(p, pObj) )
134 {
135 pObj = Gia_ObjRoToRi(p, pObj);
136 assert( !~pObj->Value );
137 Gia_ManUnrollDup_rec( pNew, pObj, Gia_ObjId(p, pObj) );
138 }
139 }
140 Gia_ManSetRegNum( pNew, 0 );
141 return pNew;
142 }
143
144 /**Function*************************************************************
145
146 Synopsis [Duplicates AIG for unrolling.]
147
148 Description []
149
150 SideEffects []
151
152 SeeAlso []
153
154 ***********************************************************************/
Gia_ManUnrollAbs(Gia_Man_t * p,int nFrames)155 Vec_Ptr_t * Gia_ManUnrollAbs( Gia_Man_t * p, int nFrames )
156 {
157 int fVerbose = 0;
158 Vec_Ptr_t * vFrames;
159 Vec_Int_t * vLimit, * vOne;
160 Gia_Man_t * pNew;
161 Gia_Obj_t * pObj;
162 int nObjBits, nObjMask;
163 int f, fMax, k, Entry, Prev, iStart, iStop, Size;
164 // get the bitmasks
165 nObjBits = Abc_Base2Log( Gia_ManObjNum(p) );
166 nObjMask = (1 << nObjBits) - 1;
167 assert( Gia_ManObjNum(p) <= nObjMask );
168 // derive the tents
169 vLimit = Vec_IntAlloc( 1000 );
170 pNew = Gia_ManUnrollDup( p, vLimit );
171 // debug printout
172 if ( fVerbose )
173 {
174 Prev = 1;
175 printf( "Tents: " );
176 Vec_IntForEachEntryStart( vLimit, Entry, k, 1 )
177 printf( "%d=%d ", k, Entry-Prev ), Prev = Entry;
178 printf( " Unused=%d", Gia_ManObjNum(p) - Gia_ManObjNum(pNew) );
179 printf( "\n" );
180 }
181 // create abstraction
182 vFrames = Vec_PtrAlloc( Vec_IntSize(vLimit) );
183 for ( fMax = 0; fMax < nFrames; fMax++ )
184 {
185 Size = (fMax+1 < Vec_IntSize(vLimit)) ? Vec_IntEntry(vLimit, fMax+1) : Gia_ManObjNum(pNew);
186 vOne = Vec_IntAlloc( Size );
187 for ( f = 0; f <= fMax; f++ )
188 {
189 iStart = (f < Vec_IntSize(vLimit)) ? Vec_IntEntry(vLimit, f ) : 0;
190 iStop = (f+1 < Vec_IntSize(vLimit)) ? Vec_IntEntry(vLimit, f+1) : 0;
191 for ( k = iStop - 1; k >= iStart; k-- )
192 {
193 assert( Gia_ManObj(pNew, k)->Value > 0 );
194 pObj = Gia_ManObj(p, Gia_ManObj(pNew, k)->Value);
195 if ( Gia_ObjIsCo(pObj) || Gia_ObjIsPi(p, pObj) )
196 continue;
197 assert( Gia_ObjIsRo(p, pObj) || Gia_ObjIsAnd(pObj) );
198 Entry = ((fMax-f) << nObjBits) | Gia_ObjId(p, pObj);
199 Vec_IntPush( vOne, Entry );
200 // printf( "%d ", Gia_ManObj(pNew, k)->Value );
201 }
202 // printf( "\n" );
203 }
204 // add in reverse topological order
205 Vec_IntSort( vOne, 1 );
206 Vec_PtrPush( vFrames, vOne );
207 assert( Vec_IntSize(vOne) <= Size - 1 );
208 }
209 Vec_IntFree( vLimit );
210 Gia_ManStop( pNew );
211 return vFrames;
212 }
213
214 /**Function*************************************************************
215
216 Synopsis [Creates manager.]
217
218 Description []
219
220 SideEffects []
221
222 SeeAlso []
223
224 ***********************************************************************/
Gia_ManUnrStart(Gia_Man_t * pAig,Gia_ParFra_t * pPars)225 Gia_ManUnr_t * Gia_ManUnrStart( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
226 {
227 Gia_ManUnr_t * p;
228 Gia_Obj_t * pObj;
229 int i, k, iRank, iFanin, Degree, Shift;
230 abctime clk = Abc_Clock();
231
232 p = ABC_CALLOC( Gia_ManUnr_t, 1 );
233 p->pAig = pAig;
234 p->pPars = pPars;
235 // create order
236 p->vLimit = Vec_IntAlloc( 0 );
237 p->pOrder = Gia_ManUnrollDup( pAig, p->vLimit );
238 /*
239 Vec_IntForEachEntryStart( p->vLimit, Shift, i, 1 )
240 printf( "%d=%d ", i, Shift-Vec_IntEntry(p->vLimit, i-1) );
241 printf( "\n" );
242 */
243 // assign rank
244 p->vRank = Vec_IntAlloc( Gia_ManObjNum(p->pOrder) );
245 for ( iRank = i = 0; i < Gia_ManObjNum(p->pOrder); Vec_IntPush(p->vRank, iRank), i++ )
246 if ( Vec_IntEntry(p->vLimit, iRank) == i )
247 iRank++;
248 assert( iRank == Vec_IntSize(p->vLimit)-1 );
249 assert( Vec_IntSize(p->vRank) == Gia_ManObjNum(p->pOrder) );
250 // assign degree
251 p->vDegree = Vec_IntStart( Gia_ManObjNum(p->pOrder) );
252 p->vDegDiff= Vec_IntStart( 2* Gia_ManObjNum(p->pOrder) );
253 Gia_ManForEachAnd( p->pOrder, pObj, i )
254 {
255 for ( k = 0; k < 2; k++ )
256 {
257 iFanin = k ? Gia_ObjFaninId1(pObj, i) : Gia_ObjFaninId0(pObj, i);
258 Degree = Vec_IntEntry(p->vRank, i) - Vec_IntEntry(p->vRank, iFanin);
259 Vec_IntWriteEntry( p->vDegDiff, 2*i + k, Degree );
260 if ( Vec_IntEntry(p->vDegree, iFanin) < Degree )
261 Vec_IntWriteEntry( p->vDegree, iFanin, Degree );
262 }
263 }
264 Gia_ManForEachCo( p->pOrder, pObj, k )
265 {
266 i = Gia_ObjId( p->pOrder, pObj );
267 iFanin = Gia_ObjFaninId0(pObj, i);
268 Degree = Vec_IntEntry(p->vRank, i) - Vec_IntEntry(p->vRank, iFanin);
269 Vec_IntWriteEntry( p->vDegDiff, 2*i, Degree );
270 if ( Vec_IntEntry(p->vDegree, iFanin) < Degree )
271 Vec_IntWriteEntry( p->vDegree, iFanin, Degree );
272 }
273 // assign first
274 p->vFirst = Vec_IntAlloc( Gia_ManObjNum(p->pOrder) );
275 p->vStore = Vec_IntStartFull( 2* Gia_ManObjNum(p->pOrder) + Vec_IntSum(p->vDegree) );
276 for ( Shift = i = 0; i < Gia_ManObjNum(p->pOrder); i++ )
277 {
278 Vec_IntPush( p->vFirst, Shift );
279 Vec_IntWriteEntry( p->vStore, Shift, 1 + Vec_IntEntry(p->vDegree, i) );
280 Shift += 2 + Vec_IntEntry(p->vDegree, i);
281 }
282 assert( Shift == Vec_IntSize(p->vStore) );
283 // cleanup
284 Vec_IntFreeP( &p->vRank );
285 Vec_IntFreeP( &p->vDegree );
286
287 // print verbose output
288 if ( pPars->fVerbose )
289 {
290 printf( "Convergence = %d. Dangling objects = %d. Average degree = %.3f ",
291 Vec_IntSize(p->vLimit) - 1,
292 Gia_ManObjNum(pAig) - Gia_ManObjNum(p->pOrder),
293 1.0*Vec_IntSize(p->vStore)/Gia_ManObjNum(p->pOrder) - 1.0 );
294 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
295 }
296 return p;
297 }
298
299 /**Function*************************************************************
300
301 Synopsis [Deletes manager.]
302
303 Description []
304
305 SideEffects []
306
307 SeeAlso []
308
309 ***********************************************************************/
Gia_ManUnrollStop(void * pMan)310 void Gia_ManUnrollStop( void * pMan )
311 {
312 Gia_ManUnr_t * p = (Gia_ManUnr_t *)pMan;
313 Gia_ManStopP( &p->pOrder );
314 Vec_IntFreeP( &p->vLimit );
315 Vec_IntFreeP( &p->vRank );
316 Vec_IntFreeP( &p->vDegree );
317 Vec_IntFreeP( &p->vDegDiff );
318 Vec_IntFreeP( &p->vFirst );
319 Vec_IntFreeP( &p->vStore );
320 ABC_FREE( p );
321 }
322
323
324 /**Function*************************************************************
325
326 Synopsis [Reading/writing entry from storage.]
327
328 Description []
329
330 SideEffects []
331
332 SeeAlso []
333
334 ***********************************************************************/
Gia_ObjUnrWrite(Gia_ManUnr_t * p,int Id,int Entry)335 static inline void Gia_ObjUnrWrite( Gia_ManUnr_t * p, int Id, int Entry )
336 {
337 int i, * pArray = Vec_IntEntryP( p->vStore, Vec_IntEntry(p->vFirst, Id) );
338 for ( i = pArray[0]; i > 1; i-- )
339 pArray[i] = pArray[i-1];
340 pArray[1] = Entry;
341 }
Gia_ObjUnrRead(Gia_ManUnr_t * p,int Id,int Degree)342 static inline int Gia_ObjUnrRead( Gia_ManUnr_t * p, int Id, int Degree )
343 {
344 int * pArray = Vec_IntEntryP( p->vStore, Vec_IntEntry(p->vFirst, Id) );
345 if ( Id == 0 )
346 return 0;
347 assert( Degree >= 0 && Degree < pArray[0] );
348 if ( Degree )
349 Degree--;
350 return pArray[Degree + 1];
351 }
Gia_ObjUnrReadCopy0(Gia_ManUnr_t * p,Gia_Obj_t * pObj,int Id)352 static inline int Gia_ObjUnrReadCopy0( Gia_ManUnr_t * p, Gia_Obj_t * pObj, int Id )
353 {
354 int Lit = Gia_ObjUnrRead(p, Gia_ObjFaninId0(pObj, Id), Vec_IntEntry(p->vDegDiff, 2*Id));
355 return Abc_LitNotCond( Lit, Gia_ObjFaninC0(pObj) );
356 }
Gia_ObjUnrReadCopy1(Gia_ManUnr_t * p,Gia_Obj_t * pObj,int Id)357 static inline int Gia_ObjUnrReadCopy1( Gia_ManUnr_t * p, Gia_Obj_t * pObj, int Id )
358 {
359 int Lit = Gia_ObjUnrRead(p, Gia_ObjFaninId1(pObj, Id), Vec_IntEntry(p->vDegDiff, 2*Id+1));
360 return Abc_LitNotCond( Lit, Gia_ObjFaninC1(pObj) );
361 }
Gia_ObjUnrReadCi(Gia_ManUnr_t * p,int Id,int f,Gia_Man_t * pNew)362 static inline int Gia_ObjUnrReadCi( Gia_ManUnr_t * p, int Id, int f, Gia_Man_t * pNew )
363 {
364 Gia_Obj_t * pObj = Gia_ManObj( p->pOrder, Id );
365 Gia_Obj_t * pObjReal = Gia_ManObj( p->pAig, pObj->Value );
366 assert( Gia_ObjIsCi(pObjReal) );
367 if ( Gia_ObjIsPi(p->pAig, pObjReal) )
368 {
369 if ( !p->pPars->fSaveLastLit )
370 pObj = Gia_ManPi( pNew, Gia_ManPiNum(p->pAig) * f + Gia_ObjCioId(pObjReal) );
371 else
372 pObj = Gia_ManPi( pNew, Gia_ManRegNum(p->pAig) + Gia_ManPiNum(p->pAig) * f + Gia_ObjCioId(pObjReal) );
373 return Abc_Var2Lit( Gia_ObjId(pNew, pObj), 0 );
374 }
375 if ( f == 0 ) // initialize!
376 {
377 if ( p->pPars->fInit )
378 return 0;
379 assert( Gia_ObjCioId(pObjReal) >= Gia_ManPiNum(p->pAig) );
380 if ( !p->pPars->fSaveLastLit )
381 pObj = Gia_ManPi( pNew, Gia_ManPiNum(p->pAig) * p->pPars->nFrames + Gia_ObjCioId(pObjReal)-Gia_ManPiNum(p->pAig) );
382 else
383 pObj = Gia_ManPi( pNew, Gia_ObjCioId(pObjReal)-Gia_ManPiNum(p->pAig) );
384 return Abc_Var2Lit( Gia_ObjId(pNew, pObj), 0 );
385 }
386 pObj = Gia_ManObj( p->pOrder, Abc_Lit2Var(Gia_ObjRoToRi(p->pAig, pObjReal)->Value) );
387 assert( Gia_ObjIsCo(pObj) );
388 return Gia_ObjUnrRead( p, Gia_ObjId(p->pOrder, pObj), 0 );
389 }
390
391 /**Function*************************************************************
392
393 Synopsis [Computes init/non-init unrolling without flops.]
394
395 Description []
396
397 SideEffects []
398
399 SeeAlso []
400
401 ***********************************************************************/
Gia_ManUnrollStart(Gia_Man_t * pAig,Gia_ParFra_t * pPars)402 void * Gia_ManUnrollStart( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
403 {
404 Gia_ManUnr_t * p;
405 int f, i;
406 // start
407 p = Gia_ManUnrStart( pAig, pPars );
408 // start timeframes
409 assert( p->pNew == NULL );
410 p->pNew = Gia_ManStart( 10000 );
411 p->pNew->pName = Abc_UtilStrsav( p->pAig->pName );
412 p->pNew->pSpec = Abc_UtilStrsav( p->pAig->pSpec );
413 Gia_ManHashAlloc( p->pNew );
414 // create combinational inputs
415 if ( !p->pPars->fSaveLastLit ) // only in the case when unrolling depth is known
416 for ( f = 0; f < p->pPars->nFrames; f++ )
417 for ( i = 0; i < Gia_ManPiNum(p->pAig); i++ )
418 Gia_ManAppendCi(p->pNew);
419 // create flop outputs
420 if ( !p->pPars->fInit ) // only in the case when initialization is not performed
421 for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
422 Gia_ManAppendCi(p->pNew);
423 return p;
424 }
425
426 /**Function*************************************************************
427
428 Synopsis [Computes init/non-init unrolling without flops.]
429
430 Description []
431
432 SideEffects []
433
434 SeeAlso []
435
436 ***********************************************************************/
Gia_ManUnrollAdd(void * pMan,int fMax)437 void * Gia_ManUnrollAdd( void * pMan, int fMax )
438 {
439 Gia_ManUnr_t * p = (Gia_ManUnr_t *)pMan;
440 Gia_Obj_t * pObj;
441 int f, i, Lit = 0, Beg, End;
442 // create PIs on demand
443 if ( p->pPars->fSaveLastLit )
444 for ( i = 0; i < Gia_ManPiNum(p->pAig); i++ )
445 Gia_ManAppendCi(p->pNew);
446 // unroll another timeframe
447 for ( f = 0; f < fMax; f++ )
448 {
449 if ( Vec_IntSize(p->vLimit) <= fMax-f )
450 continue;
451 Beg = Vec_IntEntry( p->vLimit, fMax-f-1 );
452 End = Vec_IntEntry( p->vLimit, fMax-f );
453 for ( i = Beg; i < End; i++ )
454 {
455 pObj = Gia_ManObj( p->pOrder, i );
456 if ( Gia_ObjIsAnd(pObj) )
457 Lit = Gia_ManHashAnd( p->pNew, Gia_ObjUnrReadCopy0(p, pObj, i), Gia_ObjUnrReadCopy1(p, pObj, i) );
458 else if ( Gia_ObjIsCo(pObj) )
459 {
460 Lit = Gia_ObjUnrReadCopy0(p, pObj, i);
461 if ( f == fMax-1 )
462 {
463 if ( p->pPars->fSaveLastLit )
464 p->LastLit = Lit;
465 else
466 Gia_ManAppendCo( p->pNew, Lit );
467 }
468 }
469 else if ( Gia_ObjIsCi(pObj) )
470 Lit = Gia_ObjUnrReadCi( p, i, f, p->pNew );
471 else assert( 0 );
472 assert( Lit >= 0 );
473 Gia_ObjUnrWrite( p, i, Lit ); // should be exactly one call for each obj!
474 }
475 }
476 return p->pNew;
477 }
478
479 /**Function*************************************************************
480
481 Synopsis [Read the last literal.]
482
483 Description []
484
485 SideEffects []
486
487 SeeAlso []
488
489 ***********************************************************************/
Gia_ManUnrollLastLit(void * pMan)490 int Gia_ManUnrollLastLit( void * pMan )
491 {
492 Gia_ManUnr_t * p = (Gia_ManUnr_t *)pMan;
493 return p->LastLit;
494 }
495
496 /**Function*************************************************************
497
498 Synopsis [Computes init/non-init unrolling without flops.]
499
500 Description []
501
502 SideEffects []
503
504 SeeAlso []
505
506 ***********************************************************************/
Gia_ManUnroll(Gia_Man_t * pAig,Gia_ParFra_t * pPars)507 Gia_Man_t * Gia_ManUnroll( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
508 {
509 Gia_ManUnr_t * p;
510 Gia_Man_t * pNew, * pTemp;
511 int fMax;
512 p = (Gia_ManUnr_t *)Gia_ManUnrollStart( pAig, pPars );
513 for ( fMax = 1; fMax <= p->pPars->nFrames; fMax++ )
514 Gia_ManUnrollAdd( p, fMax );
515 assert( Gia_ManPoNum(p->pNew) == p->pPars->nFrames * Gia_ManPoNum(p->pAig) );
516 Gia_ManHashStop( p->pNew );
517 Gia_ManSetRegNum( p->pNew, 0 );
518 // Gia_ManPrintStats( pNew, 0 );
519 // cleanup
520 p->pNew = Gia_ManCleanup( pTemp = p->pNew );
521 Gia_ManStop( pTemp );
522 // Gia_ManPrintStats( pNew, 0 );
523 pNew = p->pNew; p->pNew = NULL;
524 Gia_ManUnrollStop( p );
525 return pNew;
526 }
527
528
529 /**Function*************************************************************
530
531 Synopsis [Computes init/non-init unrolling without flops.]
532
533 Description []
534
535 SideEffects []
536
537 SeeAlso []
538
539 ***********************************************************************/
540 /*
541 Gia_Man_t * Gia_ManUnroll( Gia_ManUnr_t * p )
542 {
543 Gia_Man_t * pNew, * pTemp;
544 Gia_Obj_t * pObj;
545 int fMax, f, i, Lit, Beg, End;
546 // start timeframes
547 pNew = Gia_ManStart( 10000 );
548 pNew->pName = Abc_UtilStrsav( p->pAig->pName );
549 pNew->pSpec = Abc_UtilStrsav( p->pAig->pSpec );
550 Gia_ManHashAlloc( pNew );
551 // create combinational inputs
552 for ( f = 0; f < p->pPars->nFrames; f++ )
553 for ( i = 0; i < Gia_ManPiNum(p->pAig); i++ )
554 Gia_ManAppendCi(pNew);
555 if ( !p->pPars->fInit )
556 for ( i = 0; i < Gia_ManRegNum(p->pAig); i++ )
557 Gia_ManAppendCi(pNew);
558 // add nodes to each time-frame
559 // Gia_ObjUnrWrite( p, 0, 0 );
560 for ( fMax = 1; fMax <= p->pPars->nFrames; fMax++ )
561 for ( f = 0; f < fMax; f++ )
562 {
563 if ( Vec_IntSize(p->vLimit) <= fMax-f )
564 continue;
565 Beg = Vec_IntEntry( p->vLimit, fMax-f-1 );
566 End = Vec_IntEntry( p->vLimit, fMax-f );
567 for ( i = Beg; i < End; i++ )
568 {
569 pObj = Gia_ManObj( p->pOrder, i );
570 if ( Gia_ObjIsAnd(pObj) )
571 Lit = Gia_ManHashAnd( pNew, Gia_ObjUnrReadCopy0(p, pObj, i), Gia_ObjUnrReadCopy1(p, pObj, i) );
572 else if ( Gia_ObjIsCo(pObj) )
573 {
574 Lit = Gia_ObjUnrReadCopy0(p, pObj, i);
575 if ( f == fMax-1 )
576 Gia_ManAppendCo( pNew, Lit );
577 }
578 else if ( Gia_ObjIsCi(pObj) )
579 Lit = Gia_ObjUnrReadCi( p, i, f, pNew );
580 else assert( 0 );
581 assert( Lit >= 0 );
582 Gia_ObjUnrWrite( p, i, Lit ); // should be exactly one call for each obj!
583 }
584 }
585 assert( Gia_ManPoNum(pNew) == p->pPars->nFrames * Gia_ManPoNum(p->pAig) );
586 Gia_ManHashStop( pNew );
587 Gia_ManSetRegNum( pNew, 0 );
588 // Gia_ManPrintStats( pNew, 0 );
589 // cleanup
590 pNew = Gia_ManCleanup( pTemp = pNew );
591 Gia_ManStop( pTemp );
592 // Gia_ManPrintStats( pNew, 0 );
593 return pNew;
594 }
595 */
596
597 /**Function*************************************************************
598
599 Synopsis []
600
601 Description []
602
603 SideEffects []
604
605 SeeAlso []
606
607 ***********************************************************************/
Gia_ManFrames2(Gia_Man_t * pAig,Gia_ParFra_t * pPars)608 Gia_Man_t * Gia_ManFrames2( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
609 {
610 Gia_Man_t * pNew;
611 abctime clk = Abc_Clock();
612 pNew = Gia_ManUnroll( pAig, pPars );
613 if ( pPars->fVerbose )
614 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
615 return pNew;
616 }
617
618
619
620 /**Function*************************************************************
621
622 Synopsis [This procedure sets default parameters.]
623
624 Description []
625
626 SideEffects []
627
628 SeeAlso []
629
630 ***********************************************************************/
Gia_ManFraSetDefaultParams(Gia_ParFra_t * p)631 void Gia_ManFraSetDefaultParams( Gia_ParFra_t * p )
632 {
633 memset( p, 0, sizeof(Gia_ParFra_t) );
634 p->nFrames = 32; // the number of frames to unroll
635 p->fInit = 0; // initialize the timeframes
636 p->fVerbose = 0; // enables verbose output
637 }
638
639 /**Function*************************************************************
640
641 Synopsis [Creates manager.]
642
643 Description []
644
645 SideEffects []
646
647 SeeAlso []
648
649 ***********************************************************************/
Gia_ManFraStart(Gia_Man_t * pAig,Gia_ParFra_t * pPars)650 Gia_ManFra_t * Gia_ManFraStart( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
651 {
652 Gia_ManFra_t * p;
653 p = ABC_ALLOC( Gia_ManFra_t, 1 );
654 memset( p, 0, sizeof(Gia_ManFra_t) );
655 p->pAig = pAig;
656 p->pPars = pPars;
657 return p;
658 }
659
660 /**Function*************************************************************
661
662 Synopsis [Deletes manager.]
663
664 Description []
665
666 SideEffects []
667
668 SeeAlso []
669
670 ***********************************************************************/
Gia_ManFraStop(Gia_ManFra_t * p)671 void Gia_ManFraStop( Gia_ManFra_t * p )
672 {
673 Vec_VecFree( (Vec_Vec_t *)p->vIns );
674 Vec_VecFree( (Vec_Vec_t *)p->vAnds );
675 Vec_VecFree( (Vec_Vec_t *)p->vOuts );
676 ABC_FREE( p );
677 }
678
679 /**Function*************************************************************
680
681 Synopsis [Computes supports of all timeframes.]
682
683 Description []
684
685 SideEffects []
686
687 SeeAlso []
688
689 ***********************************************************************/
Gia_ManFraSupports(Gia_ManFra_t * p)690 void Gia_ManFraSupports( Gia_ManFra_t * p )
691 {
692 Vec_Int_t * vIns = NULL, * vAnds, * vOuts;
693 Gia_Obj_t * pObj;
694 int f, i;
695 p->vIns = Vec_PtrStart( p->pPars->nFrames );
696 p->vAnds = Vec_PtrStart( p->pPars->nFrames );
697 p->vOuts = Vec_PtrStart( p->pPars->nFrames );
698 Gia_ManIncrementTravId( p->pAig );
699 for ( f = p->pPars->nFrames - 1; f >= 0; f-- )
700 {
701 vOuts = Gia_ManCollectPoIds( p->pAig );
702 if ( vIns )
703 Gia_ManForEachObjVec( vIns, p->pAig, pObj, i )
704 if ( Gia_ObjIsRo(p->pAig, pObj) )
705 Vec_IntPush( vOuts, Gia_ObjId( p->pAig, Gia_ObjRoToRi(p->pAig, pObj) ) );
706 vIns = Vec_IntAlloc( 100 );
707 Gia_ManCollectCis( p->pAig, Vec_IntArray(vOuts), Vec_IntSize(vOuts), vIns );
708 vAnds = Vec_IntAlloc( 100 );
709 Gia_ManCollectAnds( p->pAig, Vec_IntArray(vOuts), Vec_IntSize(vOuts), vAnds, NULL );
710 Vec_PtrWriteEntry( p->vIns, f, vIns );
711 Vec_PtrWriteEntry( p->vAnds, f, vAnds );
712 Vec_PtrWriteEntry( p->vOuts, f, vOuts );
713 }
714 }
715
716 /**Function*************************************************************
717
718 Synopsis []
719
720 Description []
721
722 SideEffects []
723
724 SeeAlso []
725
726 ***********************************************************************/
Gia_ManFramesInit(Gia_Man_t * pAig,Gia_ParFra_t * pPars)727 Gia_Man_t * Gia_ManFramesInit( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
728 {
729 int fUseAllPis = 1;
730 Gia_Man_t * pFrames, * pTemp;
731 Gia_ManFra_t * p;
732 Gia_Obj_t * pObj;
733 Vec_Int_t * vIns, * vAnds, * vOuts;
734 int i, f;
735 p = Gia_ManFraStart( pAig, pPars );
736 Gia_ManFraSupports( p );
737 pFrames = Gia_ManStart( Vec_VecSizeSize((Vec_Vec_t*)p->vIns)+
738 Vec_VecSizeSize((Vec_Vec_t*)p->vAnds)+Vec_VecSizeSize((Vec_Vec_t*)p->vOuts) );
739 pFrames->pName = Abc_UtilStrsav( pAig->pName );
740 pFrames->pSpec = Abc_UtilStrsav( pAig->pSpec );
741 Gia_ManHashAlloc( pFrames );
742 Gia_ManConst0(pAig)->Value = 0;
743 for ( f = 0; f < pPars->nFrames; f++ )
744 {
745 vIns = (Vec_Int_t *)Vec_PtrEntry( p->vIns, f );
746 vAnds = (Vec_Int_t *)Vec_PtrEntry( p->vAnds, f );
747 vOuts = (Vec_Int_t *)Vec_PtrEntry( p->vOuts, f );
748 if ( pPars->fVerbose )
749 printf( "Frame %3d : CI = %6d. AND = %6d. CO = %6d.\n",
750 f, Vec_IntSize(vIns), Vec_IntSize(vAnds), Vec_IntSize(vOuts) );
751 if ( fUseAllPis )
752 {
753 Gia_ManForEachPi( pAig, pObj, i )
754 pObj->Value = Gia_ManAppendCi( pFrames );
755 if ( f == 0 )
756 {
757 Gia_ManForEachObjVec( vIns, pAig, pObj, i )
758 {
759 assert( Gia_ObjIsCi(pObj) );
760 if ( !Gia_ObjIsPi(pAig, pObj) )
761 pObj->Value = 0;
762 }
763 }
764 else
765 {
766 Gia_ManForEachObjVec( vIns, pAig, pObj, i )
767 {
768 assert( Gia_ObjIsCi(pObj) );
769 if ( !Gia_ObjIsPi(pAig, pObj) )
770 pObj->Value = Gia_ObjRoToRi(pAig, pObj)->Value;
771 }
772 }
773 }
774 else
775 {
776 if ( f == 0 )
777 {
778 Gia_ManForEachObjVec( vIns, pAig, pObj, i )
779 {
780 assert( Gia_ObjIsCi(pObj) );
781 if ( Gia_ObjIsPi(pAig, pObj) )
782 pObj->Value = Gia_ManAppendCi( pFrames );
783 else
784 pObj->Value = 0;
785 }
786 }
787 else
788 {
789 Gia_ManForEachObjVec( vIns, pAig, pObj, i )
790 {
791 assert( Gia_ObjIsCi(pObj) );
792 if ( Gia_ObjIsPi(pAig, pObj) )
793 pObj->Value = Gia_ManAppendCi( pFrames );
794 else
795 pObj->Value = Gia_ObjRoToRi(pAig, pObj)->Value;
796 }
797 }
798 }
799 Gia_ManForEachObjVec( vAnds, pAig, pObj, i )
800 {
801 assert( Gia_ObjIsAnd(pObj) );
802 pObj->Value = Gia_ManHashAnd( pFrames, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
803 }
804 Gia_ManForEachObjVec( vOuts, pAig, pObj, i )
805 {
806 assert( Gia_ObjIsCo(pObj) );
807 if ( Gia_ObjIsPo(pAig, pObj) )
808 pObj->Value = Gia_ManAppendCo( pFrames, Gia_ObjFanin0Copy(pObj) );
809 else
810 pObj->Value = Gia_ObjFanin0Copy(pObj);
811 }
812 }
813 Gia_ManFraStop( p );
814 Gia_ManHashStop( pFrames );
815 if ( Gia_ManCombMarkUsed(pFrames) < Gia_ManAndNum(pFrames) )
816 {
817 pFrames = Gia_ManDupMarked( pTemp = pFrames );
818 if ( pPars->fVerbose )
819 printf( "Before cleanup = %d nodes. After cleanup = %d nodes.\n",
820 Gia_ManAndNum(pTemp), Gia_ManAndNum(pFrames) );
821 Gia_ManStop( pTemp );
822 }
823 else if ( pPars->fVerbose )
824 printf( "Before cleanup = %d nodes. After cleanup = %d nodes.\n",
825 Gia_ManAndNum(pFrames), Gia_ManAndNum(pFrames) );
826 return pFrames;
827 }
828
829 /**Function*************************************************************
830
831 Synopsis []
832
833 Description []
834
835 SideEffects []
836
837 SeeAlso []
838
839 ***********************************************************************/
Gia_ManFrames(Gia_Man_t * pAig,Gia_ParFra_t * pPars)840 Gia_Man_t * Gia_ManFrames( Gia_Man_t * pAig, Gia_ParFra_t * pPars )
841 {
842 Gia_Man_t * pFrames, * pTemp;
843 Gia_Obj_t * pObj;
844 Vec_Int_t * vPoLits = NULL;
845 int i, f;
846 assert( Gia_ManRegNum(pAig) > 0 );
847 assert( pPars->nFrames > 0 );
848 if ( pPars->fInit )
849 return Gia_ManFramesInit( pAig, pPars );
850 if ( pPars->fOrPos )
851 vPoLits = Vec_IntStart( Gia_ManPoNum(pAig) );
852 pFrames = Gia_ManStart( pPars->nFrames * Gia_ManObjNum(pAig) );
853 pFrames->pName = Abc_UtilStrsav( pAig->pName );
854 pFrames->pSpec = Abc_UtilStrsav( pAig->pSpec );
855 if ( !pPars->fDisableSt )
856 Gia_ManHashAlloc( pFrames );
857 Gia_ManConst0(pAig)->Value = 0;
858 // create primary inputs
859 for ( f = 0; f < pPars->nFrames; f++ )
860 Gia_ManForEachPi( pAig, pObj, i )
861 pObj->Value = Gia_ManAppendCi( pFrames );
862 // add internal nodes for each timeframe
863 for ( f = 0; f < pPars->nFrames; f++ )
864 {
865 if ( f == 0 )
866 {
867 Gia_ManForEachRo( pAig, pObj, i )
868 pObj->Value = Gia_ManAppendCi( pFrames );
869 }
870 else
871 {
872 Gia_ManForEachRo( pAig, pObj, i )
873 pObj->Value = Gia_ObjRoToRi( pAig, pObj )->Value;
874 }
875 Gia_ManForEachPi( pAig, pObj, i )
876 pObj->Value = Gia_Obj2Lit( pFrames, Gia_ManPi(pFrames, f * Gia_ManPiNum(pAig) + i) );
877 if ( !pPars->fDisableSt )
878 Gia_ManForEachAnd( pAig, pObj, i )
879 pObj->Value = Gia_ManHashAnd( pFrames, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
880 else
881 Gia_ManForEachAnd( pAig, pObj, i )
882 pObj->Value = Gia_ManAppendAnd2( pFrames, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
883 if ( vPoLits )
884 {
885 if ( !pPars->fDisableSt )
886 Gia_ManForEachPo( pAig, pObj, i )
887 Vec_IntWriteEntry( vPoLits, i, Gia_ManHashOr(pFrames, Vec_IntEntry(vPoLits, i), Gia_ObjFanin0Copy(pObj)) );
888 else
889 Gia_ManForEachPo( pAig, pObj, i )
890 Vec_IntWriteEntry( vPoLits, i, Abc_LitNot(Gia_ManAppendAnd2(pFrames, Abc_LitNot(Vec_IntEntry(vPoLits, i)), Abc_LitNot(Gia_ObjFanin0Copy(pObj)))) );
891 }
892 else
893 {
894 Gia_ManForEachPo( pAig, pObj, i )
895 pObj->Value = Gia_ManAppendCo( pFrames, Gia_ObjFanin0Copy(pObj) );
896 }
897 if ( f == pPars->nFrames - 1 )
898 {
899 if ( vPoLits )
900 Gia_ManForEachPo( pAig, pObj, i )
901 pObj->Value = Gia_ManAppendCo( pFrames, Vec_IntEntry(vPoLits, i) );
902 Gia_ManForEachRi( pAig, pObj, i )
903 pObj->Value = Gia_ManAppendCo( pFrames, Gia_ObjFanin0Copy(pObj) );
904 }
905 else
906 {
907 Gia_ManForEachRi( pAig, pObj, i )
908 pObj->Value = Gia_ObjFanin0Copy(pObj);
909 }
910 }
911 Vec_IntFreeP( &vPoLits );
912 if ( !pPars->fDisableSt )
913 Gia_ManHashStop( pFrames );
914 Gia_ManSetRegNum( pFrames, Gia_ManRegNum(pAig) );
915 if ( Gia_ManCombMarkUsed(pFrames) < Gia_ManAndNum(pFrames) )
916 {
917 pFrames = Gia_ManDupMarked( pTemp = pFrames );
918 if ( pPars->fVerbose )
919 printf( "Before cleanup = %d nodes. After cleanup = %d nodes.\n",
920 Gia_ManAndNum(pTemp), Gia_ManAndNum(pFrames) );
921 Gia_ManStop( pTemp );
922 }
923 else if ( pPars->fVerbose )
924 printf( "Before cleanup = %d nodes. After cleanup = %d nodes.\n",
925 Gia_ManAndNum(pFrames), Gia_ManAndNum(pFrames) );
926 return pFrames;
927 }
928
929
930 /**Function*************************************************************
931
932 Synopsis [Perform init unrolling as long as PO(s) are constant 0.]
933
934 Description []
935
936 SideEffects []
937
938 SeeAlso []
939
940 ***********************************************************************/
Gia_ManFramesInitSpecial(Gia_Man_t * pAig,int nFrames,int fVerbose)941 Gia_Man_t * Gia_ManFramesInitSpecial( Gia_Man_t * pAig, int nFrames, int fVerbose )
942 {
943 Gia_Man_t * pFrames, * pTemp;
944 Gia_Obj_t * pObj;
945 int i, f;
946 assert( Gia_ManRegNum(pAig) > 0 );
947 if ( nFrames > 0 )
948 printf( "Computing specialized unrolling with %d frames...\n", nFrames );
949 pFrames = Gia_ManStart( Gia_ManObjNum(pAig) );
950 pFrames->pName = Abc_UtilStrsav( pAig->pName );
951 pFrames->pSpec = Abc_UtilStrsav( pAig->pSpec );
952 Gia_ManHashAlloc( pFrames );
953 Gia_ManConst0(pAig)->Value = 0;
954 for ( f = 0; nFrames == 0 || f < nFrames; f++ )
955 {
956 if ( fVerbose && (f % 100 == 0) )
957 {
958 printf( "%6d : ", f );
959 Gia_ManPrintStats( pFrames, NULL );
960 }
961 Gia_ManForEachRo( pAig, pObj, i )
962 pObj->Value = f ? Gia_ObjRoToRi( pAig, pObj )->Value : 0;
963 Gia_ManForEachPi( pAig, pObj, i )
964 pObj->Value = Gia_ManAppendCi( pFrames );
965 Gia_ManForEachAnd( pAig, pObj, i )
966 pObj->Value = Gia_ManHashAnd( pFrames, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
967 Gia_ManForEachPo( pAig, pObj, i )
968 if ( Gia_ObjFanin0Copy(pObj) != 0 )
969 break;
970 if ( i < Gia_ManPoNum(pAig) )
971 break;
972 Gia_ManForEachRi( pAig, pObj, i )
973 pObj->Value = Gia_ObjFanin0Copy(pObj);
974 }
975 if ( fVerbose )
976 printf( "Computed prefix of %d frames.\n", f );
977 Gia_ManForEachRi( pAig, pObj, i )
978 Gia_ManAppendCo( pFrames, pObj->Value );
979 Gia_ManHashStop( pFrames );
980 pFrames = Gia_ManCleanup( pTemp = pFrames );
981 if ( fVerbose )
982 printf( "Before cleanup = %d nodes. After cleanup = %d nodes.\n",
983 Gia_ManAndNum(pTemp), Gia_ManAndNum(pFrames) );
984 Gia_ManStop( pTemp );
985 return pFrames;
986 }
987
988
989
990 ////////////////////////////////////////////////////////////////////////
991 /// END OF FILE ///
992 ////////////////////////////////////////////////////////////////////////
993
994
995 ABC_NAMESPACE_IMPL_END
996
997