1 /**CFile****************************************************************
2
3 FileName [aigRet.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [AIG package.]
8
9 Synopsis [Retiming of AIGs.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: aigRet.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "aig.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // init values
31 typedef enum {
32 RTM_VAL_NONE, // 0: non-existent value
33 RTM_VAL_ZERO, // 1: initial value 0
34 RTM_VAL_ONE, // 2: initial value 1
35 RTM_VAL_VOID // 3: unused value
36 } Rtm_Init_t;
37
38 typedef struct Rtm_Man_t_ Rtm_Man_t;
39 struct Rtm_Man_t_
40 {
41 // network representation
42 Vec_Ptr_t * vObjs; // retiming objects
43 Vec_Ptr_t * vPis; // PIs only
44 Vec_Ptr_t * vPos; // POs only
45 Aig_MmFlex_t * pMem; // the memory manager
46 // autonomous components after cutting off
47 // storage for overflow latches
48 unsigned * pExtra;
49 int nExtraCur;
50 int nExtraAlloc;
51 };
52
53 typedef struct Rtm_Edg_t_ Rtm_Edg_t;
54 struct Rtm_Edg_t_
55 {
56 unsigned long nLats : 12; // the number of latches
57 unsigned long LData : 20; // the latches themselves
58 };
59
60 typedef struct Rtm_Obj_t_ Rtm_Obj_t;
61 struct Rtm_Obj_t_
62 {
63 void * pCopy; // the copy of this object
64 unsigned long Type : 3; // object type
65 unsigned long fMark : 1; // multipurpose mark
66 unsigned long fAuto : 1; // this object belongs to an autonomous component
67 unsigned long fCompl0 : 1; // complemented attribute of the first edge
68 unsigned long fCompl1 : 1; // complemented attribute of the second edge
69 unsigned long nFanins : 8; // the number of fanins
70 unsigned Num : 17; // the retiming number of this node
71 int Id; // ID of this object
72 int Temp; // temporary usage
73 int nFanouts; // the number of fanouts
74 void * pFanio[0]; // fanins and their edges (followed by fanouts and pointers to their edges)
75 };
76
Rtm_ObjFanin(Rtm_Obj_t * pObj,int i)77 static inline Rtm_Obj_t * Rtm_ObjFanin( Rtm_Obj_t * pObj, int i ) { return (Rtm_Obj_t *)pObj->pFanio[2*i]; }
Rtm_ObjFanout(Rtm_Obj_t * pObj,int i)78 static inline Rtm_Obj_t * Rtm_ObjFanout( Rtm_Obj_t * pObj, int i ) { return (Rtm_Obj_t *)pObj->pFanio[2*(pObj->nFanins+i)]; }
Rtm_ObjEdge(Rtm_Obj_t * pObj,int i)79 static inline Rtm_Edg_t * Rtm_ObjEdge( Rtm_Obj_t * pObj, int i ) { return (Rtm_Edg_t *)(pObj->pFanio + 2*i + 1); }
Rtm_ObjFanoutEdge(Rtm_Obj_t * pObj,int i)80 static inline Rtm_Edg_t * Rtm_ObjFanoutEdge( Rtm_Obj_t * pObj, int i ) { return (Rtm_Edg_t *)pObj->pFanio[2*(pObj->nFanins+i) + 1]; }
81
Rtm_InitNot(Rtm_Init_t Val)82 static inline Rtm_Init_t Rtm_InitNot( Rtm_Init_t Val ) { if ( Val == RTM_VAL_ZERO ) return (Rtm_Init_t)RTM_VAL_ONE; if ( Val == RTM_VAL_ONE ) return (Rtm_Init_t)RTM_VAL_ZERO; assert( 0 ); return (Rtm_Init_t)-1; }
Rtm_InitNotCond(Rtm_Init_t Val,int c)83 static inline Rtm_Init_t Rtm_InitNotCond( Rtm_Init_t Val, int c ) { return c ? Rtm_InitNot(Val) : Val; }
Rtm_InitAnd(Rtm_Init_t ValA,Rtm_Init_t ValB)84 static inline Rtm_Init_t Rtm_InitAnd(Rtm_Init_t ValA, Rtm_Init_t ValB ) { if ( ValA == RTM_VAL_ONE && ValB == RTM_VAL_ONE ) return (Rtm_Init_t)RTM_VAL_ONE; if ( ValA == RTM_VAL_ZERO || ValB == RTM_VAL_ZERO ) return (Rtm_Init_t)RTM_VAL_ZERO; assert( 0 ); return (Rtm_Init_t)-1; }
85
Rtm_InitWordsNum(int nLats)86 static inline int Rtm_InitWordsNum( int nLats ) { return (nLats >> 4) + ((nLats & 15) > 0); }
Rtm_InitGetTwo(unsigned * p,int i)87 static inline int Rtm_InitGetTwo( unsigned * p, int i ) { return (p[i>>4] >> ((i & 15)<<1)) & 3; }
Rtm_InitSetTwo(unsigned * p,int i,int val)88 static inline void Rtm_InitSetTwo( unsigned * p, int i, int val ) { p[i>>4] |= (val << ((i & 15)<<1)); }
Rtm_InitXorTwo(unsigned * p,int i,int val)89 static inline void Rtm_InitXorTwo( unsigned * p, int i, int val ) { p[i>>4] ^= (val << ((i & 15)<<1)); }
90
Rtm_ObjGetFirst1(Rtm_Edg_t * pEdge)91 static inline Rtm_Init_t Rtm_ObjGetFirst1( Rtm_Edg_t * pEdge ) { return (Rtm_Init_t)(pEdge->LData & 3); }
Rtm_ObjGetLast1(Rtm_Edg_t * pEdge)92 static inline Rtm_Init_t Rtm_ObjGetLast1( Rtm_Edg_t * pEdge ) { return (Rtm_Init_t)((pEdge->LData >> ((pEdge->nLats-1)<<1)) & 3); }
Rtm_ObjGetOne1(Rtm_Edg_t * pEdge,int i)93 static inline Rtm_Init_t Rtm_ObjGetOne1( Rtm_Edg_t * pEdge, int i ) { assert( i < (int)pEdge->nLats ); return (Rtm_Init_t)((pEdge->LData >> (i << 1)) & 3); }
Rtm_ObjRemFirst1(Rtm_Edg_t * pEdge)94 static inline Rtm_Init_t Rtm_ObjRemFirst1( Rtm_Edg_t * pEdge ) { int Val = pEdge->LData & 3; pEdge->LData >>= 2; assert(pEdge->nLats > 0); pEdge->nLats--; return (Rtm_Init_t)Val; }
Rtm_ObjRemLast1(Rtm_Edg_t * pEdge)95 static inline Rtm_Init_t Rtm_ObjRemLast1( Rtm_Edg_t * pEdge ) { int Val = (pEdge->LData >> ((pEdge->nLats-1)<<1)) & 3; pEdge->LData ^= Val << ((pEdge->nLats-1)<<1); assert(pEdge->nLats > 0); pEdge->nLats--; return (Rtm_Init_t)Val; }
Rtm_ObjAddFirst1(Rtm_Edg_t * pEdge,Rtm_Init_t Val)96 static inline void Rtm_ObjAddFirst1( Rtm_Edg_t * pEdge, Rtm_Init_t Val ) { assert( Val > 0 ); pEdge->LData = (pEdge->LData << 2) | Val; pEdge->nLats++; }
Rtm_ObjAddLast1(Rtm_Edg_t * pEdge,Rtm_Init_t Val)97 static inline void Rtm_ObjAddLast1( Rtm_Edg_t * pEdge, Rtm_Init_t Val ) { assert( Val > 0 ); pEdge->LData |= Val << (pEdge->nLats<<1); pEdge->nLats++; }
98
Rtm_ObjGetFirst2(Rtm_Man_t * p,Rtm_Edg_t * pEdge)99 static inline Rtm_Init_t Rtm_ObjGetFirst2( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { return (Rtm_Init_t)Rtm_InitGetTwo( p->pExtra + pEdge->LData, 0 ); }
Rtm_ObjGetLast2(Rtm_Man_t * p,Rtm_Edg_t * pEdge)100 static inline Rtm_Init_t Rtm_ObjGetLast2( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { return (Rtm_Init_t)Rtm_InitGetTwo( p->pExtra + pEdge->LData, pEdge->nLats - 1 ); }
Rtm_ObjGetOne2(Rtm_Man_t * p,Rtm_Edg_t * pEdge,int i)101 static inline Rtm_Init_t Rtm_ObjGetOne2( Rtm_Man_t * p, Rtm_Edg_t * pEdge, int i ) { return (Rtm_Init_t)Rtm_InitGetTwo( p->pExtra + pEdge->LData, i ); }
102 static Rtm_Init_t Rtm_ObjRemFirst2( Rtm_Man_t * p, Rtm_Edg_t * pEdge );
Rtm_ObjRemLast2(Rtm_Man_t * p,Rtm_Edg_t * pEdge)103 static inline Rtm_Init_t Rtm_ObjRemLast2( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { Rtm_Init_t Val = Rtm_ObjGetLast2( p, pEdge ); Rtm_InitXorTwo( p->pExtra + pEdge->LData, pEdge->nLats - 1, Val ); pEdge->nLats--; return (Rtm_Init_t)Val; }
104 static void Rtm_ObjAddFirst2( Rtm_Man_t * p, Rtm_Edg_t * pEdge, Rtm_Init_t Val );
Rtm_ObjAddLast2(Rtm_Man_t * p,Rtm_Edg_t * pEdge,Rtm_Init_t Val)105 static inline void Rtm_ObjAddLast2( Rtm_Man_t * p, Rtm_Edg_t * pEdge, Rtm_Init_t Val ) { Rtm_InitSetTwo( p->pExtra + pEdge->LData, pEdge->nLats, Val ); pEdge->nLats++; }
106
107 static void Rtm_ObjTransferToSmall( Rtm_Man_t * p, Rtm_Edg_t * pEdge );
108 static void Rtm_ObjTransferToBig( Rtm_Man_t * p, Rtm_Edg_t * pEdge );
109 static void Rtm_ObjTransferToBigger( Rtm_Man_t * p, Rtm_Edg_t * pEdge );
110
Rtm_ObjGetFirst(Rtm_Man_t * p,Rtm_Edg_t * pEdge)111 static inline Rtm_Init_t Rtm_ObjGetFirst( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { return pEdge->nLats > 10? Rtm_ObjGetFirst2(p, pEdge) : Rtm_ObjGetFirst1(pEdge); }
Rtm_ObjGetLast(Rtm_Man_t * p,Rtm_Edg_t * pEdge)112 static inline Rtm_Init_t Rtm_ObjGetLast( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { return pEdge->nLats > 10? Rtm_ObjGetLast2(p, pEdge) : Rtm_ObjGetLast1(pEdge); }
Rtm_ObjGetOne(Rtm_Man_t * p,Rtm_Edg_t * pEdge,int i)113 static inline Rtm_Init_t Rtm_ObjGetOne( Rtm_Man_t * p, Rtm_Edg_t * pEdge, int i ) { return pEdge->nLats > 10? Rtm_ObjGetOne2(p, pEdge, i) : Rtm_ObjGetOne1(pEdge, i); }
Rtm_ObjRemFirst(Rtm_Man_t * p,Rtm_Edg_t * pEdge)114 static Rtm_Init_t Rtm_ObjRemFirst( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { Rtm_Init_t Res = pEdge->nLats > 10 ? Rtm_ObjRemFirst2(p, pEdge) : Rtm_ObjRemFirst1(pEdge); if ( pEdge->nLats == 10 ) Rtm_ObjTransferToSmall(p, pEdge); return Res; }
Rtm_ObjRemLast(Rtm_Man_t * p,Rtm_Edg_t * pEdge)115 static Rtm_Init_t Rtm_ObjRemLast( Rtm_Man_t * p, Rtm_Edg_t * pEdge ) { Rtm_Init_t Res = pEdge->nLats > 10 ? Rtm_ObjRemLast2(p, pEdge) : Rtm_ObjRemLast1(pEdge); if ( pEdge->nLats == 10 ) Rtm_ObjTransferToSmall(p, pEdge); return Res; }
Rtm_ObjAddFirst(Rtm_Man_t * p,Rtm_Edg_t * pEdge,Rtm_Init_t Val)116 static void Rtm_ObjAddFirst( Rtm_Man_t * p, Rtm_Edg_t * pEdge, Rtm_Init_t Val ) { if ( pEdge->nLats == 10 ) Rtm_ObjTransferToBig(p, pEdge); else if ( (pEdge->nLats & 15) == 15 ) Rtm_ObjTransferToBigger(p, pEdge); if ( pEdge->nLats >= 10 ) Rtm_ObjAddFirst2(p, pEdge, Val); else Rtm_ObjAddFirst1(pEdge, Val); }
Rtm_ObjAddLast(Rtm_Man_t * p,Rtm_Edg_t * pEdge,Rtm_Init_t Val)117 static void Rtm_ObjAddLast( Rtm_Man_t * p, Rtm_Edg_t * pEdge, Rtm_Init_t Val ) { if ( pEdge->nLats == 10 ) Rtm_ObjTransferToBig(p, pEdge); else if ( (pEdge->nLats & 15) == 15 ) Rtm_ObjTransferToBigger(p, pEdge); if ( pEdge->nLats >= 10 ) Rtm_ObjAddLast2(p, pEdge, Val); else Rtm_ObjAddLast1(pEdge, Val); }
118
119
120 // iterator over the primary inputs
121 #define Rtm_ManForEachPi( p, pObj, i ) \
122 Vec_PtrForEachEntry( Rtm_Obj_t *, p->vPis, pObj, i )
123 // iterator over the primary outputs
124 #define Rtm_ManForEachPo( p, pObj, i ) \
125 Vec_PtrForEachEntry( Rtm_Obj_t *, p->vPos, pObj, i )
126 // iterator over all objects, including those currently not used
127 #define Rtm_ManForEachObj( p, pObj, i ) \
128 Vec_PtrForEachEntry( Rtm_Obj_t *, p->vObjs, pObj, i )
129 // iterate through the fanins
130 #define Rtm_ObjForEachFanin( pObj, pFanin, i ) \
131 for ( i = 0; i < (int)(pObj)->nFanins && ((pFanin = Rtm_ObjFanin(pObj, i)), 1); i++ )
132 // iterate through the fanouts
133 #define Rtm_ObjForEachFanout( pObj, pFanout, i ) \
134 for ( i = 0; i < (int)(pObj)->nFanouts && ((pFanout = Rtm_ObjFanout(pObj, i)), 1); i++ )
135 // iterate through the fanin edges
136 #define Rtm_ObjForEachFaninEdge( pObj, pEdge, i ) \
137 for ( i = 0; i < (int)(pObj)->nFanins && ((pEdge = Rtm_ObjEdge(pObj, i)), 1); i++ )
138 // iterate through the fanout edges
139 #define Rtm_ObjForEachFanoutEdge( pObj, pEdge, i ) \
140 for ( i = 0; i < (int)(pObj)->nFanouts && ((pEdge = Rtm_ObjFanoutEdge(pObj, i)), 1); i++ )
141
142 ////////////////////////////////////////////////////////////////////////
143 /// FUNCTION DEFINITIONS ///
144 ////////////////////////////////////////////////////////////////////////
145
146 /**Function*************************************************************
147
148 Synopsis [Transfers from big to small storage.]
149
150 Description []
151
152 SideEffects []
153
154 SeeAlso []
155
156 ***********************************************************************/
Rtm_ObjTransferToSmall(Rtm_Man_t * p,Rtm_Edg_t * pEdge)157 void Rtm_ObjTransferToSmall( Rtm_Man_t * p, Rtm_Edg_t * pEdge )
158 {
159 assert( pEdge->nLats == 10 );
160 pEdge->LData = p->pExtra[pEdge->LData];
161 }
162
163 /**Function*************************************************************
164
165 Synopsis [Transfers from small to big storage.]
166
167 Description []
168
169 SideEffects []
170
171 SeeAlso []
172
173 ***********************************************************************/
Rtm_ObjTransferToBig(Rtm_Man_t * p,Rtm_Edg_t * pEdge)174 void Rtm_ObjTransferToBig( Rtm_Man_t * p, Rtm_Edg_t * pEdge )
175 {
176 assert( pEdge->nLats == 10 );
177 if ( p->nExtraCur + 1 > p->nExtraAlloc )
178 {
179 int nExtraAllocNew = Abc_MaxInt( 2 * p->nExtraAlloc, 1024 );
180 p->pExtra = ABC_REALLOC( unsigned, p->pExtra, nExtraAllocNew );
181 p->nExtraAlloc = nExtraAllocNew;
182 }
183 p->pExtra[p->nExtraCur] = pEdge->LData;
184 pEdge->LData = p->nExtraCur++;
185 }
186
187 /**Function*************************************************************
188
189 Synopsis [Transfers to bigger storage.]
190
191 Description []
192
193 SideEffects []
194
195 SeeAlso []
196
197 ***********************************************************************/
Rtm_ObjTransferToBigger(Rtm_Man_t * p,Rtm_Edg_t * pEdge)198 void Rtm_ObjTransferToBigger( Rtm_Man_t * p, Rtm_Edg_t * pEdge )
199 {
200 int nWords;
201 assert( (pEdge->nLats & 15) == 15 );
202 nWords = (pEdge->nLats + 1) >> 4;
203 if ( p->nExtraCur + nWords + 1 > p->nExtraAlloc )
204 {
205 int nExtraAllocNew = Abc_MaxInt( 2 * p->nExtraAlloc, 1024 );
206 p->pExtra = ABC_REALLOC( unsigned, p->pExtra, nExtraAllocNew );
207 p->nExtraAlloc = nExtraAllocNew;
208 }
209 memcpy( p->pExtra + p->nExtraCur, p->pExtra + pEdge->LData, sizeof(unsigned) * nWords );
210 p->pExtra[p->nExtraCur + nWords] = 0;
211 pEdge->LData = p->nExtraCur;
212 p->nExtraCur += nWords + 1;
213 }
214
215 /**Function*************************************************************
216
217 Synopsis []
218
219 Description []
220
221 SideEffects []
222
223 SeeAlso []
224
225 ***********************************************************************/
Rtm_ObjRemFirst2(Rtm_Man_t * p,Rtm_Edg_t * pEdge)226 Rtm_Init_t Rtm_ObjRemFirst2( Rtm_Man_t * p, Rtm_Edg_t * pEdge )
227 {
228 Rtm_Init_t Val = (Rtm_Init_t)0, Temp;
229 unsigned * pB = p->pExtra + pEdge->LData, * pE = pB + Rtm_InitWordsNum( pEdge->nLats-- ) - 1;
230 while ( pE >= pB )
231 {
232 Temp = (Rtm_Init_t)(*pE & 3);
233 *pE = (*pE >> 2) | (Val << 30);
234 Val = Temp;
235 pE--;
236 }
237 assert( Val != 0 );
238 return Val;
239 }
240
241 /**Function*************************************************************
242
243 Synopsis []
244
245 Description []
246
247 SideEffects []
248
249 SeeAlso []
250
251 ***********************************************************************/
Rtm_ObjAddFirst2(Rtm_Man_t * p,Rtm_Edg_t * pEdge,Rtm_Init_t Val)252 void Rtm_ObjAddFirst2( Rtm_Man_t * p, Rtm_Edg_t * pEdge, Rtm_Init_t Val )
253 {
254 unsigned * pB = p->pExtra + pEdge->LData, * pE = pB + Rtm_InitWordsNum( ++pEdge->nLats );
255 Rtm_Init_t Temp;
256 assert( Val != 0 );
257 while ( pB < pE )
258 {
259 Temp = (Rtm_Init_t)(*pB >> 30);
260 *pB = (*pB << 2) | Val;
261 Val = Temp;
262 pB++;
263 }
264 }
265
266 /**Function*************************************************************
267
268 Synopsis []
269
270 Description []
271
272 SideEffects []
273
274 SeeAlso []
275
276 ***********************************************************************/
Rtm_PrintEdge(Rtm_Man_t * p,Rtm_Edg_t * pEdge)277 void Rtm_PrintEdge( Rtm_Man_t * p, Rtm_Edg_t * pEdge )
278 {
279 // unsigned LData = pEdge->LData;
280 printf( "%d : ", (int)pEdge->nLats );
281 /*
282 if ( pEdge->nLats > 10 )
283 Extra_PrintBinary( stdout, p->pExtra + pEdge->LData, 2*(pEdge->nLats+1) );
284 else
285 Extra_PrintBinary( stdout, &LData, 2*(pEdge->nLats+1) );
286 */
287 printf( "\n" );
288 }
289
290
291 /**Function*************************************************************
292
293 Synopsis [Allocates the retiming manager.]
294
295 Description []
296
297 SideEffects []
298
299 SeeAlso []
300
301 ***********************************************************************/
Rtm_ManAlloc(Aig_Man_t * p)302 Rtm_Man_t * Rtm_ManAlloc( Aig_Man_t * p )
303 {
304 Rtm_Man_t * pRtm;
305 // start the manager
306 pRtm = ABC_ALLOC( Rtm_Man_t, 1 );
307 memset( pRtm, 0, sizeof(Rtm_Man_t) );
308 // perform initializations
309 pRtm->vObjs = Vec_PtrAlloc( Aig_ManObjNum(p) );
310 pRtm->vPis = Vec_PtrAlloc( Aig_ManCiNum(p) );
311 pRtm->vPos = Vec_PtrAlloc( Aig_ManCoNum(p) );
312 pRtm->pMem = Aig_MmFlexStart();
313 return pRtm;
314 }
315
316 /**Function*************************************************************
317
318 Synopsis [Allocates the retiming manager.]
319
320 Description []
321
322 SideEffects []
323
324 SeeAlso []
325
326 ***********************************************************************/
Rtm_ManFree(Rtm_Man_t * p)327 void Rtm_ManFree( Rtm_Man_t * p )
328 {
329 Vec_PtrFree( p->vObjs );
330 Vec_PtrFree( p->vPis );
331 Vec_PtrFree( p->vPos );
332 Aig_MmFlexStop( p->pMem, 0 );
333 ABC_FREE( p->pExtra );
334 ABC_FREE( p );
335 }
336
337 /**Function*************************************************************
338
339 Synopsis [Counts the maximum number of latches on an edge.]
340
341 Description []
342
343 SideEffects []
344
345 SeeAlso []
346
347 ***********************************************************************/
Rtm_ManLatchMax(Rtm_Man_t * p)348 int Rtm_ManLatchMax( Rtm_Man_t * p )
349 {
350 Rtm_Obj_t * pObj;
351 Rtm_Edg_t * pEdge;
352 int nLatchMax = 0, i, k;//, c, Val;
353 Rtm_ManForEachObj( p, pObj, i )
354 Rtm_ObjForEachFaninEdge( pObj, pEdge, k )
355 {
356 /*
357 for ( c = 0; c < (int)pEdge->nLats; c++ )
358 {
359 Val = Rtm_ObjGetOne( p, pEdge, c );
360 assert( Val == 1 || Val == 2 );
361 }
362 */
363 nLatchMax = Abc_MaxInt( nLatchMax, (int)pEdge->nLats );
364 }
365 return nLatchMax;
366 }
367
368 /**Function*************************************************************
369
370 Synopsis [Allocates the retiming object.]
371
372 Description []
373
374 SideEffects []
375
376 SeeAlso []
377
378 ***********************************************************************/
Rtm_ObjAlloc(Rtm_Man_t * pRtm,int nFanins,int nFanouts)379 Rtm_Obj_t * Rtm_ObjAlloc( Rtm_Man_t * pRtm, int nFanins, int nFanouts )
380 {
381 Rtm_Obj_t * pObj;
382 int Size = sizeof(Rtm_Obj_t) + sizeof(Rtm_Obj_t *) * (nFanins + nFanouts) * 2;
383 pObj = (Rtm_Obj_t *)Aig_MmFlexEntryFetch( pRtm->pMem, Size );
384 memset( pObj, 0, sizeof(Rtm_Obj_t) );
385 pObj->Type = (int)(nFanins == 1 && nFanouts == 0); // mark PO
386 pObj->Num = nFanins; // temporary
387 pObj->Temp = nFanouts;
388 pObj->Id = Vec_PtrSize(pRtm->vObjs);
389 Vec_PtrPush( pRtm->vObjs, pObj );
390 return pObj;
391 }
392
393 /**Function*************************************************************
394
395 Synopsis [Allocates the retiming object.]
396
397 Description []
398
399 SideEffects []
400
401 SeeAlso []
402
403 ***********************************************************************/
Rtm_ObjAddFanin(Rtm_Obj_t * pObj,Rtm_Obj_t * pFanin,int fCompl)404 void Rtm_ObjAddFanin( Rtm_Obj_t * pObj, Rtm_Obj_t * pFanin, int fCompl )
405 {
406 pObj->pFanio[ 2*pObj->nFanins ] = pFanin;
407 pObj->pFanio[ 2*pObj->nFanins + 1 ] = NULL;
408 pFanin->pFanio[ 2*(pFanin->Num + pFanin->nFanouts) ] = pObj;
409 pFanin->pFanio[ 2*(pFanin->Num + pFanin->nFanouts) + 1 ] = pObj->pFanio + 2*pObj->nFanins + 1;
410 if ( pObj->nFanins == 0 )
411 pObj->fCompl0 = fCompl;
412 else if ( pObj->nFanins == 1 )
413 pObj->fCompl1 = fCompl;
414 else
415 assert( 0 );
416 pObj->nFanins++;
417 pFanin->nFanouts++;
418 assert( pObj->nFanins <= pObj->Num );
419 assert( pFanin->nFanouts <= pFanin->Temp );
420 }
421
422 /**Function*************************************************************
423
424 Synopsis [Check the possibility of forward retiming.]
425
426 Description []
427
428 SideEffects []
429
430 SeeAlso []
431
432 ***********************************************************************/
Rtm_ObjCheckRetimeFwd(Rtm_Obj_t * pObj)433 int Rtm_ObjCheckRetimeFwd( Rtm_Obj_t * pObj )
434 {
435 Rtm_Edg_t * pEdge;
436 int i;
437 Rtm_ObjForEachFaninEdge( pObj, pEdge, i )
438 if ( pEdge->nLats == 0 )
439 return 0;
440 return 1;
441 }
442
443 /**Function*************************************************************
444
445 Synopsis [Check the possibility of forward retiming.]
446
447 Description []
448
449 SideEffects []
450
451 SeeAlso []
452
453 ***********************************************************************/
Rtm_ObjCheckRetimeBwd(Rtm_Obj_t * pObj)454 int Rtm_ObjCheckRetimeBwd( Rtm_Obj_t * pObj )
455 {
456 Rtm_Edg_t * pEdge;
457 int i;
458 Rtm_ObjForEachFanoutEdge( pObj, pEdge, i )
459 if ( pEdge->nLats == 0 )
460 return 0;
461 return 1;
462 }
463
464 /**Function*************************************************************
465
466 Synopsis [Check the possibility of forward retiming.]
467
468 Description []
469
470 SideEffects []
471
472 SeeAlso []
473
474 ***********************************************************************/
Rtm_ObjGetDegreeFwd(Rtm_Obj_t * pObj)475 int Rtm_ObjGetDegreeFwd( Rtm_Obj_t * pObj )
476 {
477 Rtm_Obj_t * pFanin;
478 int i, Degree = 0;
479 Rtm_ObjForEachFanin( pObj, pFanin, i )
480 Degree = Abc_MaxInt( Degree, (int)pFanin->Num );
481 return Degree + 1;
482 }
483
484 /**Function*************************************************************
485
486 Synopsis [Check the possibility of forward retiming.]
487
488 Description []
489
490 SideEffects []
491
492 SeeAlso []
493
494 ***********************************************************************/
Rtm_ObjGetDegreeBwd(Rtm_Obj_t * pObj)495 int Rtm_ObjGetDegreeBwd( Rtm_Obj_t * pObj )
496 {
497 Rtm_Obj_t * pFanout;
498 int i, Degree = 0;
499 Rtm_ObjForEachFanout( pObj, pFanout, i )
500 Degree = Abc_MaxInt( Degree, (int)pFanout->Num );
501 return Degree + 1;
502 }
503
504 /**Function*************************************************************
505
506 Synopsis [Performs forward retiming.]
507
508 Description []
509
510 SideEffects []
511
512 SeeAlso []
513
514 ***********************************************************************/
Rtm_ObjRetimeFwd(Rtm_Man_t * pRtm,Rtm_Obj_t * pObj)515 void Rtm_ObjRetimeFwd( Rtm_Man_t * pRtm, Rtm_Obj_t * pObj )
516 {
517 Rtm_Init_t ValTotal, ValCur;
518 Rtm_Edg_t * pEdge;
519 int i;
520 assert( Rtm_ObjCheckRetimeFwd(pObj) );
521 // extract values and compute the result
522 ValTotal = RTM_VAL_ONE;
523 Rtm_ObjForEachFaninEdge( pObj, pEdge, i )
524 {
525 ValCur = Rtm_ObjRemFirst( pRtm, pEdge );
526 ValCur = Rtm_InitNotCond( ValCur, i? pObj->fCompl1 : pObj->fCompl0 );
527 ValTotal = Rtm_InitAnd( ValTotal, ValCur );
528 }
529 // insert the result in the fanout values
530 Rtm_ObjForEachFanoutEdge( pObj, pEdge, i )
531 Rtm_ObjAddLast( pRtm, pEdge, ValTotal );
532 }
533
534 /**Function*************************************************************
535
536 Synopsis [Performs forward retiming.]
537
538 Description []
539
540 SideEffects []
541
542 SeeAlso []
543
544 ***********************************************************************/
Rtm_ObjRetimeBwd(Rtm_Man_t * pRtm,Rtm_Obj_t * pObj)545 void Rtm_ObjRetimeBwd( Rtm_Man_t * pRtm, Rtm_Obj_t * pObj )
546 {
547 Rtm_Edg_t * pEdge;
548 int i;
549 assert( Rtm_ObjCheckRetimeBwd(pObj) );
550 // extract values and compute the result
551 Rtm_ObjForEachFanoutEdge( pObj, pEdge, i )
552 Rtm_ObjRemLast( pRtm, pEdge );
553 // insert the result in the fanout values
554 Rtm_ObjForEachFaninEdge( pObj, pEdge, i )
555 Rtm_ObjAddFirst( pRtm, pEdge, RTM_VAL_VOID );
556 }
557
558 /**Function*************************************************************
559
560 Synopsis []
561
562 Description []
563
564 SideEffects []
565
566 SeeAlso []
567
568 ***********************************************************************/
Rtm_ObjMarkAutoFwd_rec(Rtm_Obj_t * pObj)569 void Rtm_ObjMarkAutoFwd_rec( Rtm_Obj_t * pObj )
570 {
571 Rtm_Obj_t * pFanout;
572 int i;
573 if ( pObj->fAuto )
574 return;
575 pObj->fAuto = 1;
576 Rtm_ObjForEachFanout( pObj, pFanout, i )
577 Rtm_ObjMarkAutoFwd_rec( pFanout );
578 }
579
580 /**Function*************************************************************
581
582 Synopsis [Marks the nodes unreachable from the PIs.]
583
584 Description []
585
586 SideEffects []
587
588 SeeAlso []
589
590 ***********************************************************************/
Rtm_ManMarkAutoFwd(Rtm_Man_t * pRtm)591 int Rtm_ManMarkAutoFwd( Rtm_Man_t * pRtm )
592 {
593 Rtm_Obj_t * pObjRtm;
594 int i, Counter = 0;
595 // mark nodes reachable from the PIs
596 pObjRtm = (Rtm_Obj_t *)Vec_PtrEntry( pRtm->vObjs, 0 );
597 Rtm_ObjMarkAutoFwd_rec( pObjRtm );
598 Rtm_ManForEachPi( pRtm, pObjRtm, i )
599 Rtm_ObjMarkAutoFwd_rec( pObjRtm );
600 // count the number of autonomous nodes
601 Rtm_ManForEachObj( pRtm, pObjRtm, i )
602 {
603 pObjRtm->fAuto = !pObjRtm->fAuto;
604 Counter += pObjRtm->fAuto;
605 }
606 // mark the fanins of the autonomous nodes
607 return Counter;
608 }
609
610 /**Function*************************************************************
611
612 Synopsis []
613
614 Description []
615
616 SideEffects []
617
618 SeeAlso []
619
620 ***********************************************************************/
Rtm_ObjMarkAutoBwd_rec(Rtm_Obj_t * pObj)621 void Rtm_ObjMarkAutoBwd_rec( Rtm_Obj_t * pObj )
622 {
623 Rtm_Obj_t * pFanin;
624 int i;
625 if ( pObj->fAuto )
626 return;
627 pObj->fAuto = 1;
628 Rtm_ObjForEachFanin( pObj, pFanin, i )
629 Rtm_ObjMarkAutoBwd_rec( pFanin );
630 }
631
632 /**Function*************************************************************
633
634 Synopsis [Marks the nodes unreachable from the POs.]
635
636 Description []
637
638 SideEffects []
639
640 SeeAlso []
641
642 ***********************************************************************/
Rtm_ManMarkAutoBwd(Rtm_Man_t * pRtm)643 int Rtm_ManMarkAutoBwd( Rtm_Man_t * pRtm )
644 {
645 Rtm_Obj_t * pObjRtm;
646 int i, Counter = 0;
647 // mark nodes reachable from the PIs
648 pObjRtm = (Rtm_Obj_t *)Vec_PtrEntry( pRtm->vObjs, 0 );
649 pObjRtm->fAuto = 1;
650 Rtm_ManForEachPi( pRtm, pObjRtm, i )
651 pObjRtm->fAuto = 1;
652 Rtm_ManForEachPo( pRtm, pObjRtm, i )
653 Rtm_ObjMarkAutoBwd_rec( pObjRtm );
654 // count the number of autonomous nodes
655 Rtm_ManForEachObj( pRtm, pObjRtm, i )
656 {
657 pObjRtm->fAuto = !pObjRtm->fAuto;
658 Counter += pObjRtm->fAuto;
659 }
660 // mark the fanins of the autonomous nodes
661 return Counter;
662 }
663
664 /**Function*************************************************************
665
666 Synopsis [Derive retiming manager from the given AIG manager.]
667
668 Description []
669
670 SideEffects []
671
672 SeeAlso []
673
674 ***********************************************************************/
Rtm_ManFromAig(Aig_Man_t * p)675 Rtm_Man_t * Rtm_ManFromAig( Aig_Man_t * p )
676 {
677 Rtm_Man_t * pRtm;
678 Aig_Obj_t * pObj, * pObjLi, * pObjLo;
679 int i;
680 assert( Aig_ManRegNum(p) > 0 );
681 assert( Aig_ManBufNum(p) == 0 );
682 // allocate the manager
683 pRtm = Rtm_ManAlloc( p );
684 // allocate objects
685 pObj = Aig_ManConst1(p);
686 pObj->pData = Rtm_ObjAlloc( pRtm, 0, pObj->nRefs );
687 Aig_ManForEachPiSeq( p, pObj, i )
688 {
689 pObj->pData = Rtm_ObjAlloc( pRtm, 0, pObj->nRefs );
690 Vec_PtrPush( pRtm->vPis, pObj->pData );
691 }
692 Aig_ManForEachPoSeq( p, pObj, i )
693 {
694 pObj->pData = Rtm_ObjAlloc( pRtm, 1, 0 );
695 Vec_PtrPush( pRtm->vPos, pObj->pData );
696 }
697 Aig_ManForEachLoSeq( p, pObj, i )
698 pObj->pData = Rtm_ObjAlloc( pRtm, 1, pObj->nRefs );
699 Aig_ManForEachLiSeq( p, pObj, i )
700 pObj->pData = Rtm_ObjAlloc( pRtm, 1, 1 );
701 Aig_ManForEachNode( p, pObj, i )
702 pObj->pData = Rtm_ObjAlloc( pRtm, 2, pObj->nRefs );
703 // connect objects
704 Aig_ManForEachPoSeq( p, pObj, i )
705 Rtm_ObjAddFanin( (Rtm_Obj_t *)pObj->pData, (Rtm_Obj_t *)Aig_ObjFanin0(pObj)->pData, Aig_ObjFaninC0(pObj) );
706 Aig_ManForEachLiSeq( p, pObj, i )
707 Rtm_ObjAddFanin( (Rtm_Obj_t *)pObj->pData, (Rtm_Obj_t *)Aig_ObjFanin0(pObj)->pData, Aig_ObjFaninC0(pObj) );
708 Aig_ManForEachLiLoSeq( p, pObjLi, pObjLo, i )
709 Rtm_ObjAddFanin( (Rtm_Obj_t *)pObjLo->pData, (Rtm_Obj_t *)pObjLi->pData, 0 );
710 Aig_ManForEachNode( p, pObj, i )
711 {
712 Rtm_ObjAddFanin( (Rtm_Obj_t *)pObj->pData, (Rtm_Obj_t *)Aig_ObjFanin0(pObj)->pData, Aig_ObjFaninC0(pObj) );
713 Rtm_ObjAddFanin( (Rtm_Obj_t *)pObj->pData, (Rtm_Obj_t *)Aig_ObjFanin1(pObj)->pData, Aig_ObjFaninC1(pObj) );
714 }
715 return pRtm;
716 }
717
718 /**Function*************************************************************
719
720 Synopsis [Derive AIG manager after retiming.]
721
722 Description []
723
724 SideEffects []
725
726 SeeAlso []
727
728 ***********************************************************************/
Rtm_ManToAig_rec(Aig_Man_t * pNew,Rtm_Man_t * pRtm,Rtm_Obj_t * pObjRtm,int * pLatches)729 Aig_Obj_t * Rtm_ManToAig_rec( Aig_Man_t * pNew, Rtm_Man_t * pRtm, Rtm_Obj_t * pObjRtm, int * pLatches )
730 {
731 Rtm_Edg_t * pEdge;
732 Aig_Obj_t * pRes, * pFanin;
733 int k, Val;
734 if ( pObjRtm->pCopy )
735 return (Aig_Obj_t *)pObjRtm->pCopy;
736 // get the inputs
737 pRes = Aig_ManConst1( pNew );
738 Rtm_ObjForEachFaninEdge( pObjRtm, pEdge, k )
739 {
740 if ( pEdge->nLats == 0 )
741 pFanin = Rtm_ManToAig_rec( pNew, pRtm, Rtm_ObjFanin(pObjRtm, k), pLatches );
742 else
743 {
744 Val = Rtm_ObjGetFirst( pRtm, pEdge );
745 pFanin = Aig_ManCi( pNew, pLatches[2*pObjRtm->Id + k] + pEdge->nLats - 1 );
746 pFanin = Aig_NotCond( pFanin, Val == RTM_VAL_ONE );
747 }
748 pFanin = Aig_NotCond( pFanin, k ? pObjRtm->fCompl1 : pObjRtm->fCompl0 );
749 pRes = Aig_And( pNew, pRes, pFanin );
750 }
751 return (Aig_Obj_t *)(pObjRtm->pCopy = pRes);
752 }
753
754 /**Function*************************************************************
755
756 Synopsis [Derive AIG manager after retiming.]
757
758 Description []
759
760 SideEffects []
761
762 SeeAlso []
763
764 ***********************************************************************/
Rtm_ManToAig(Rtm_Man_t * pRtm)765 Aig_Man_t * Rtm_ManToAig( Rtm_Man_t * pRtm )
766 {
767 Aig_Man_t * pNew;
768 Aig_Obj_t * pObjNew;
769 Rtm_Obj_t * pObjRtm;
770 Rtm_Edg_t * pEdge;
771 int i, k, m, Val, nLatches, * pLatches;
772 // count latches and mark the first latch on each edge
773 pLatches = ABC_ALLOC( int, 2 * Vec_PtrSize(pRtm->vObjs) );
774 nLatches = 0;
775 Rtm_ManForEachObj( pRtm, pObjRtm, i )
776 Rtm_ObjForEachFaninEdge( pObjRtm, pEdge, k )
777 {
778 pLatches[2*pObjRtm->Id + k] = Vec_PtrSize(pRtm->vPis) + nLatches;
779 nLatches += pEdge->nLats;
780 }
781 // create the new manager
782 pNew = Aig_ManStart( Vec_PtrSize(pRtm->vObjs) + nLatches );
783 // create PIs/POs and latches
784 pObjRtm = (Rtm_Obj_t *)Vec_PtrEntry( pRtm->vObjs, 0 );
785 pObjRtm->pCopy = Aig_ManConst1(pNew);
786 Rtm_ManForEachPi( pRtm, pObjRtm, i )
787 pObjRtm->pCopy = Aig_ObjCreateCi(pNew);
788 for ( i = 0; i < nLatches; i++ )
789 Aig_ObjCreateCi(pNew);
790 // create internal nodes
791 Rtm_ManForEachObj( pRtm, pObjRtm, i )
792 Rtm_ManToAig_rec( pNew, pRtm, pObjRtm, pLatches );
793 // create POs
794 Rtm_ManForEachPo( pRtm, pObjRtm, i )
795 Aig_ObjCreateCo( pNew, (Aig_Obj_t *)pObjRtm->pCopy );
796 // connect latches
797 Rtm_ManForEachObj( pRtm, pObjRtm, i )
798 Rtm_ObjForEachFaninEdge( pObjRtm, pEdge, k )
799 {
800 if ( pEdge->nLats == 0 )
801 continue;
802 pObjNew = (Aig_Obj_t *)Rtm_ObjFanin( pObjRtm, k )->pCopy;
803 for ( m = 0; m < (int)pEdge->nLats; m++ )
804 {
805 Val = Rtm_ObjGetOne( pRtm, pEdge, pEdge->nLats - 1 - m );
806 assert( Val == RTM_VAL_ZERO || Val == RTM_VAL_ONE || Val == RTM_VAL_VOID );
807 pObjNew = Aig_NotCond( pObjNew, Val == RTM_VAL_ONE );
808 Aig_ObjCreateCo( pNew, pObjNew );
809 pObjNew = Aig_ManCi( pNew, pLatches[2*pObjRtm->Id + k] + m );
810 pObjNew = Aig_NotCond( pObjNew, Val == RTM_VAL_ONE );
811 }
812 // assert( Aig_Regular(pObjNew)->nRefs > 0 );
813 }
814 ABC_FREE( pLatches );
815 Aig_ManSetRegNum( pNew, nLatches );
816 // remove useless nodes
817 Aig_ManCleanup( pNew );
818 if ( !Aig_ManCheck( pNew ) )
819 printf( "Rtm_ManToAig: The network check has failed.\n" );
820 return pNew;
821 }
822
823 /**Function*************************************************************
824
825 Synopsis [Performs forward retiming with the given limit on depth.]
826
827 Description []
828
829 SideEffects []
830
831 SeeAlso []
832
833 ***********************************************************************/
Rtm_ManRetime(Aig_Man_t * p,int fForward,int nStepsMax,int fVerbose)834 Aig_Man_t * Rtm_ManRetime( Aig_Man_t * p, int fForward, int nStepsMax, int fVerbose )
835 {
836 Vec_Ptr_t * vQueue;
837 Aig_Man_t * pNew;
838 Rtm_Man_t * pRtm;
839 Rtm_Obj_t * pObj, * pNext;
840 Aig_Obj_t * pObjAig;
841 int i, k, nAutos, Degree, DegreeMax = 0;
842 abctime clk;
843
844 // create the retiming manager
845 clk = Abc_Clock();
846 pRtm = Rtm_ManFromAig( p );
847 // set registers
848 Aig_ManForEachLoSeq( p, pObjAig, i )
849 Rtm_ObjAddFirst( pRtm, Rtm_ObjEdge((Rtm_Obj_t *)pObjAig->pData, 0), fForward? RTM_VAL_ZERO : RTM_VAL_VOID );
850 // detect and mark the autonomous components
851 if ( fForward )
852 nAutos = Rtm_ManMarkAutoFwd( pRtm );
853 else
854 nAutos = Rtm_ManMarkAutoBwd( pRtm );
855 if ( fVerbose )
856 {
857 printf( "Detected %d autonomous objects. ", nAutos );
858 ABC_PRT( "Time", Abc_Clock() - clk );
859 }
860
861 // set the current retiming number
862 Rtm_ManForEachObj( pRtm, pObj, i )
863 {
864 assert( pObj->nFanins == pObj->Num );
865 assert( pObj->nFanouts == pObj->Temp );
866 pObj->Num = 0;
867 }
868
869 clk = Abc_Clock();
870 // put the LOs on the queue
871 vQueue = Vec_PtrAlloc( 1000 );
872 if ( fForward )
873 {
874 Aig_ManForEachLoSeq( p, pObjAig, i )
875 {
876 pObj = (Rtm_Obj_t *)pObjAig->pData;
877 if ( pObj->fAuto )
878 continue;
879 pObj->fMark = 1;
880 Vec_PtrPush( vQueue, pObj );
881 }
882 }
883 else
884 {
885 Aig_ManForEachLiSeq( p, pObjAig, i )
886 {
887 pObj = (Rtm_Obj_t *)pObjAig->pData;
888 if ( pObj->fAuto )
889 continue;
890 pObj->fMark = 1;
891 Vec_PtrPush( vQueue, pObj );
892 }
893 }
894 // perform retiming
895 DegreeMax = 0;
896 Vec_PtrForEachEntry( Rtm_Obj_t *, vQueue, pObj, i )
897 {
898 pObj->fMark = 0;
899 // retime the node
900 if ( fForward )
901 {
902 Rtm_ObjRetimeFwd( pRtm, pObj );
903 // check if its fanouts should be retimed
904 Rtm_ObjForEachFanout( pObj, pNext, k )
905 {
906 if ( pNext->fMark ) // skip aleady scheduled
907 continue;
908 if ( pNext->Type ) // skip POs
909 continue;
910 if ( !Rtm_ObjCheckRetimeFwd( pNext ) ) // skip non-retimable
911 continue;
912 Degree = Rtm_ObjGetDegreeFwd( pNext );
913 DegreeMax = Abc_MaxInt( DegreeMax, Degree );
914 if ( Degree > nStepsMax ) // skip nodes with high degree
915 continue;
916 pNext->fMark = 1;
917 pNext->Num = Degree;
918 Vec_PtrPush( vQueue, pNext );
919 }
920 }
921 else
922 {
923 Rtm_ObjRetimeBwd( pRtm, pObj );
924 // check if its fanouts should be retimed
925 Rtm_ObjForEachFanin( pObj, pNext, k )
926 {
927 if ( pNext->fMark ) // skip aleady scheduled
928 continue;
929 if ( pNext->nFanins == 0 ) // skip PIs
930 continue;
931 if ( !Rtm_ObjCheckRetimeBwd( pNext ) ) // skip non-retimable
932 continue;
933 Degree = Rtm_ObjGetDegreeBwd( pNext );
934 DegreeMax = Abc_MaxInt( DegreeMax, Degree );
935 if ( Degree > nStepsMax ) // skip nodes with high degree
936 continue;
937 pNext->fMark = 1;
938 pNext->Num = Degree;
939 Vec_PtrPush( vQueue, pNext );
940 }
941 }
942 }
943
944 if ( fVerbose )
945 {
946 printf( "Performed %d %s latch moves of max depth %d and max latch count %d.\n",
947 Vec_PtrSize(vQueue), fForward? "fwd":"bwd", DegreeMax, Rtm_ManLatchMax(pRtm) );
948 printf( "Memory usage = %d. ", pRtm->nExtraCur );
949 ABC_PRT( "Time", Abc_Clock() - clk );
950 }
951 Vec_PtrFree( vQueue );
952
953 // get the new manager
954 pNew = Rtm_ManToAig( pRtm );
955 pNew->pName = Abc_UtilStrsav( p->pName );
956 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
957 Rtm_ManFree( pRtm );
958 // group the registers
959 clk = Abc_Clock();
960 pNew = Aig_ManReduceLaches( pNew, fVerbose );
961 if ( fVerbose )
962 {
963 ABC_PRT( "Register sharing time", Abc_Clock() - clk );
964 }
965 return pNew;
966 }
967
968
969 ////////////////////////////////////////////////////////////////////////
970 /// END OF FILE ///
971 ////////////////////////////////////////////////////////////////////////
972
973
974 ABC_NAMESPACE_IMPL_END
975
976