1 /**CFile****************************************************************
2
3 FileName [retIncrem.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Retiming package.]
8
9 Synopsis [Incremental retiming in one direction.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - Oct 31, 2006.]
16
17 Revision [$Id: retIncrem.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "retInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 static int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose );
31
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35
36 /**Function*************************************************************
37
38 Synopsis [Performs retiming in one direction.]
39
40 Description [Currently does not retime over black boxes.]
41
42 SideEffects []
43
44 SeeAlso []
45
46 ***********************************************************************/
Abc_NtkRetimeIncremental(Abc_Ntk_t * pNtk,int nDelayLim,int fForward,int fMinDelay,int fOneStep,int fUseOldNames,int fVerbose)47 int Abc_NtkRetimeIncremental( Abc_Ntk_t * pNtk, int nDelayLim, int fForward, int fMinDelay, int fOneStep, int fUseOldNames, int fVerbose )
48 {
49 Abc_Ntk_t * pNtkCopy = NULL;
50 Vec_Ptr_t * vBoxes;
51 st__table * tLatches;
52 int nLatches = Abc_NtkLatchNum(pNtk);
53 int nIdMaxStart = Abc_NtkObjNumMax(pNtk);
54 int RetValue;
55 int nIterLimit = -1; // Suppress "might be used uninitialized"
56 if ( Abc_NtkNodeNum(pNtk) == 0 )
57 return 0;
58 // reorder CI/CO/latch inputs
59 Abc_NtkOrderCisCos( pNtk );
60 if ( fMinDelay )
61 {
62 nIterLimit = fOneStep? 1 : 2 * Abc_NtkLevel(pNtk);
63 pNtkCopy = Abc_NtkDup( pNtk );
64 tLatches = Abc_NtkRetimePrepareLatches( pNtkCopy );
65 st__free_table( tLatches );
66 }
67 // collect latches and remove CIs/COs
68 tLatches = Abc_NtkRetimePrepareLatches( pNtk );
69 // share the latches
70 Abc_NtkRetimeShareLatches( pNtk, 0 );
71 // save boxes
72 vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL;
73 // perform the retiming
74 if ( fMinDelay )
75 Abc_NtkRetimeMinDelay( pNtk, pNtkCopy, nDelayLim, nIterLimit, fForward, fVerbose );
76 else
77 Abc_NtkRetimeOneWay( pNtk, fForward, fVerbose );
78 if ( fMinDelay )
79 Abc_NtkDelete( pNtkCopy );
80 // share the latches
81 Abc_NtkRetimeShareLatches( pNtk, 0 );
82 // restore boxes
83 pNtk->vBoxes = vBoxes;
84 // finalize the latches
85 RetValue = Abc_NtkRetimeFinalizeLatches( pNtk, tLatches, nIdMaxStart, fUseOldNames );
86 st__free_table( tLatches );
87 if ( RetValue == 0 )
88 return 0;
89 // fix the COs
90 // Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
91 // check for correctness
92 if ( !Abc_NtkCheck( pNtk ) )
93 fprintf( stdout, "Abc_NtkRetimeForward(): Network check has failed.\n" );
94 // return the number of latches saved
95 return nLatches - Abc_NtkLatchNum(pNtk);
96 }
97
98 /**Function*************************************************************
99
100 Synopsis [Prepares the network for retiming.]
101
102 Description [Hash latches into their number in the original network.]
103
104 SideEffects []
105
106 SeeAlso []
107
108 ***********************************************************************/
Abc_NtkRetimePrepareLatches(Abc_Ntk_t * pNtk)109 st__table * Abc_NtkRetimePrepareLatches( Abc_Ntk_t * pNtk )
110 {
111 st__table * tLatches;
112 Abc_Obj_t * pLatch, * pLatchIn, * pLatchOut, * pFanin;
113 int i, nOffSet = Abc_NtkBoxNum(pNtk) - Abc_NtkLatchNum(pNtk);
114 // collect latches and remove CIs/COs
115 tLatches = st__init_table( st__ptrcmp, st__ptrhash );
116 Abc_NtkForEachLatch( pNtk, pLatch, i )
117 {
118 // map latch into its true number
119 st__insert( tLatches, (char *)(ABC_PTRUINT_T)pLatch, (char *)(ABC_PTRUINT_T)(i-nOffSet) );
120 // disconnect LI
121 pLatchIn = Abc_ObjFanin0(pLatch);
122 pFanin = Abc_ObjFanin0(pLatchIn);
123 Abc_ObjTransferFanout( pLatchIn, pFanin );
124 Abc_ObjDeleteFanin( pLatchIn, pFanin );
125 // disconnect LO
126 pLatchOut = Abc_ObjFanout0(pLatch);
127 pFanin = Abc_ObjFanin0(pLatchOut);
128 if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
129 Abc_ObjTransferFanout( pLatchOut, pFanin );
130 Abc_ObjDeleteFanin( pLatchOut, pFanin );
131 }
132 return tLatches;
133 }
134
135 /**Function*************************************************************
136
137 Synopsis [Finalizes the latches after retiming.]
138
139 Description [Reuses the LIs/LOs for old latches.]
140
141 SideEffects []
142
143 SeeAlso []
144
145 ***********************************************************************/
Abc_NtkRetimeFinalizeLatches(Abc_Ntk_t * pNtk,st__table * tLatches,int nIdMaxStart,int fUseOldNames)146 int Abc_NtkRetimeFinalizeLatches( Abc_Ntk_t * pNtk, st__table * tLatches, int nIdMaxStart, int fUseOldNames )
147 {
148 Vec_Ptr_t * vCisOld, * vCosOld, * vBoxesOld, * vCisNew, * vCosNew, * vBoxesNew;
149 Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut;
150 int i, Index;
151 // create new arrays
152 vCisOld = pNtk->vCis; pNtk->vCis = NULL; vCisNew = Vec_PtrAlloc( 100 );
153 vCosOld = pNtk->vCos; pNtk->vCos = NULL; vCosNew = Vec_PtrAlloc( 100 );
154 vBoxesOld = pNtk->vBoxes; pNtk->vBoxes = NULL; vBoxesNew = Vec_PtrAlloc( 100 );
155 // copy boxes and their CIs/COs
156 Vec_PtrForEachEntryStop( Abc_Obj_t *, vCisOld, pObj, i, Vec_PtrSize(vCisOld) - st__count(tLatches) )
157 Vec_PtrPush( vCisNew, pObj );
158 Vec_PtrForEachEntryStop( Abc_Obj_t *, vCosOld, pObj, i, Vec_PtrSize(vCosOld) - st__count(tLatches) )
159 Vec_PtrPush( vCosNew, pObj );
160 Vec_PtrForEachEntryStop( Abc_Obj_t *, vBoxesOld, pObj, i, Vec_PtrSize(vBoxesOld) - st__count(tLatches) )
161 Vec_PtrPush( vBoxesNew, pObj );
162 // go through the latches
163 Abc_NtkForEachObj( pNtk, pLatch, i )
164 {
165 if ( !Abc_ObjIsLatch(pLatch) )
166 continue;
167 if ( Abc_ObjId(pLatch) >= (unsigned)nIdMaxStart )
168 {
169 // this is a new latch
170 pLatchIn = Abc_NtkCreateBi(pNtk);
171 pLatchOut = Abc_NtkCreateBo(pNtk);
172
173 if ( fUseOldNames )
174 {
175 Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
176 Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" );
177 }
178 else
179 {
180 Abc_ObjAssignName( pLatchOut, Abc_ObjName(Abc_ObjFanin0(pLatch)), "_o2" );
181 Abc_ObjAssignName( pLatchIn, Abc_ObjName(Abc_ObjFanin0(pLatch)), "_i2" );
182 }
183 }
184 else
185 {
186 // this is an old latch
187 // get its number in the original order
188 if ( ! st__lookup_int( tLatches, (char *)pLatch, &Index ) )
189 {
190 printf( "Abc_NtkRetimeFinalizeLatches(): Internal error.\n" );
191 return 0;
192 }
193 assert( pLatch == Vec_PtrEntry(vBoxesOld, Vec_PtrSize(vBoxesOld) - st__count(tLatches) + Index) );
194 // reconnect with the old LIs/LOs
195 pLatchIn = (Abc_Obj_t *)Vec_PtrEntry( vCosOld, Vec_PtrSize(vCosOld) - st__count(tLatches) + Index );
196 pLatchOut = (Abc_Obj_t *)Vec_PtrEntry( vCisOld, Vec_PtrSize(vCisOld) - st__count(tLatches) + Index );
197 }
198 // connect
199 Abc_ObjAddFanin( pLatchIn, Abc_ObjFanin0(pLatch) );
200 Abc_ObjPatchFanin( pLatch, Abc_ObjFanin0(pLatch), pLatchIn );
201 if ( Abc_ObjFanoutNum(pLatch) > 0 )
202 Abc_ObjTransferFanout( pLatch, pLatchOut );
203 Abc_ObjAddFanin( pLatchOut, pLatch );
204 // add to the arrays
205 Vec_PtrPush( vCisNew, pLatchOut );
206 Vec_PtrPush( vCosNew, pLatchIn );
207 Vec_PtrPush( vBoxesNew, pLatch );
208 }
209 // free useless Cis/Cos
210 Vec_PtrForEachEntry( Abc_Obj_t *, vCisOld, pObj, i )
211 if ( !Abc_ObjIsPi(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
212 Abc_NtkDeleteObj(pObj);
213 Vec_PtrForEachEntry( Abc_Obj_t *, vCosOld, pObj, i )
214 if ( !Abc_ObjIsPo(pObj) && Abc_ObjFaninNum(pObj) == 0 && Abc_ObjFanoutNum(pObj) == 0 )
215 Abc_NtkDeleteObj(pObj);
216 // set the new arrays
217 pNtk->vCis = vCisNew; Vec_PtrFree( vCisOld );
218 pNtk->vCos = vCosNew; Vec_PtrFree( vCosOld );
219 pNtk->vBoxes = vBoxesNew; Vec_PtrFree( vBoxesOld );
220 return 1;
221 }
222
223 /**Function*************************************************************
224
225 Synopsis [Performs retiming one way, forward or backward.]
226
227 Description []
228
229 SideEffects []
230
231 SeeAlso []
232
233 ***********************************************************************/
Abc_NtkRetimeOneWay(Abc_Ntk_t * pNtk,int fForward,int fVerbose)234 int Abc_NtkRetimeOneWay( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
235 {
236 Abc_Ntk_t * pNtkNew = NULL; // Suppress "might be used uninitialized"
237 Vec_Int_t * vValues = NULL; // Suppress "might be used uninitialized"
238 Abc_Obj_t * pObj;
239 int i, fChanges, nTotalMoves = 0, nTotalMovesLimit = 10000;
240 if ( fForward )
241 Abc_NtkRetimeTranferToCopy( pNtk );
242 else
243 {
244 // save initial values of the latches
245 vValues = Abc_NtkRetimeCollectLatchValues( pNtk );
246 // start the network for initial value computation
247 pNtkNew = Abc_NtkRetimeBackwardInitialStart( pNtk );
248 }
249 // try to move latches forward whenever possible
250 do {
251 fChanges = 0;
252 Abc_NtkForEachObj( pNtk, pObj, i )
253 {
254 if ( !Abc_ObjIsNode(pObj) )
255 continue;
256 if ( Abc_NtkRetimeNodeIsEnabled( pObj, fForward ) )
257 {
258 Abc_NtkRetimeNode( pObj, fForward, 1 );
259 fChanges = 1;
260 nTotalMoves++;
261 if ( nTotalMoves >= nTotalMovesLimit )
262 {
263 printf( "Stopped after %d latch moves.\n", nTotalMoves );
264 break;
265 }
266 }
267 }
268 } while ( fChanges && nTotalMoves < nTotalMovesLimit );
269 // transfer the initial state back to the latches
270 if ( fForward )
271 Abc_NtkRetimeTranferFromCopy( pNtk );
272 else
273 {
274 Abc_NtkRetimeBackwardInitialFinish( pNtk, pNtkNew, vValues, fVerbose );
275 Abc_NtkDelete( pNtkNew );
276 Vec_IntFree( vValues );
277 }
278 return 0;
279 }
280
281
282 /**Function*************************************************************
283
284 Synopsis [Returns 1 if retiming forward/backward is possible.]
285
286 Description []
287
288 SideEffects []
289
290 SeeAlso []
291
292 ***********************************************************************/
Abc_NtkRetimeNodeIsEnabled(Abc_Obj_t * pObj,int fForward)293 int Abc_NtkRetimeNodeIsEnabled( Abc_Obj_t * pObj, int fForward )
294 {
295 Abc_Obj_t * pNext;
296 int i;
297 assert( Abc_ObjIsNode(pObj) );
298 if ( fForward )
299 {
300 Abc_ObjForEachFanin( pObj, pNext, i )
301 if ( !Abc_ObjIsLatch(pNext) )
302 return 0;
303 }
304 else
305 {
306 Abc_ObjForEachFanout( pObj, pNext, i )
307 if ( !Abc_ObjIsLatch(pNext) )
308 return 0;
309 }
310 return 1;
311 }
312
313 /**Function*************************************************************
314
315 Synopsis [Retimes the node backward or forward.]
316
317 Description []
318
319 SideEffects []
320
321 SeeAlso []
322
323 ***********************************************************************/
Abc_NtkRetimeNode(Abc_Obj_t * pObj,int fForward,int fInitial)324 void Abc_NtkRetimeNode( Abc_Obj_t * pObj, int fForward, int fInitial )
325 {
326 Abc_Ntk_t * pNtkNew = NULL;
327 Vec_Ptr_t * vNodes;
328 Abc_Obj_t * pNext, * pLatch;
329 int i;
330 vNodes = Vec_PtrAlloc( 10 );
331 if ( fForward )
332 {
333 // compute the initial value
334 if ( fInitial )
335 pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_ObjSopSimulate( pObj );
336 // collect fanins
337 Abc_NodeCollectFanins( pObj, vNodes );
338 // make the node point to the fanins fanins
339 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, i )
340 {
341 assert( Abc_ObjIsLatch(pNext) );
342 Abc_ObjPatchFanin( pObj, pNext, Abc_ObjFanin0(pNext) );
343 if ( Abc_ObjFanoutNum(pNext) == 0 )
344 Abc_NtkDeleteObj(pNext);
345 }
346 // add a new latch on top
347 pNext = Abc_NtkCreateLatch(pObj->pNtk);
348 if ( Abc_ObjFanoutNum(pObj) > 0 )
349 Abc_ObjTransferFanout( pObj, pNext );
350 Abc_ObjAddFanin( pNext, pObj );
351 // set the initial value
352 if ( fInitial )
353 pNext->pCopy = pObj->pCopy;
354 }
355 else
356 {
357 // compute the initial value
358 if ( fInitial )
359 {
360 pNtkNew = Abc_ObjFanout0(pObj)->pCopy->pNtk;
361 Abc_NtkDupObj( pNtkNew, pObj, 0 );
362 Abc_ObjForEachFanout( pObj, pNext, i )
363 {
364 assert( Abc_ObjFaninNum(pNext->pCopy) == 0 );
365 Abc_ObjAddFanin( pNext->pCopy, pObj->pCopy );
366 }
367 }
368 // collect fanouts
369 Abc_NodeCollectFanouts( pObj, vNodes );
370 // make the fanouts fanouts point to the node
371 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, i )
372 {
373 assert( Abc_ObjIsLatch(pNext) );
374 Abc_ObjTransferFanout( pNext, pObj );
375 Abc_NtkDeleteObj( pNext );
376 }
377 // add new latches to the fanins
378 Abc_ObjForEachFanin( pObj, pNext, i )
379 {
380 pLatch = Abc_NtkCreateLatch(pObj->pNtk);
381 Abc_ObjPatchFanin( pObj, pNext, pLatch );
382 Abc_ObjAddFanin( pLatch, pNext );
383 // create buffer isomorphic to this latch
384 if ( fInitial )
385 {
386 pLatch->pCopy = Abc_NtkCreateNodeBuf( pNtkNew, NULL );
387 Abc_ObjAssignName( pLatch->pCopy, Abc_ObjName(pNext), "_buf" );
388 Abc_ObjAddFanin( pObj->pCopy, pLatch->pCopy );
389 }
390 }
391 }
392 Vec_PtrFree( vNodes );
393 }
394
395 /**Function*************************************************************
396
397 Synopsis [Returns the number of compatible fanout latches.]
398
399 Description []
400
401 SideEffects []
402
403 SeeAlso []
404
405 ***********************************************************************/
Abc_NtkRetimeCheckCompatibleLatchFanouts(Abc_Obj_t * pObj)406 int Abc_NtkRetimeCheckCompatibleLatchFanouts( Abc_Obj_t * pObj )
407 {
408 Abc_Obj_t * pFanout;
409 int i, nLatches = 0, Init = -1;
410 Abc_ObjForEachFanout( pObj, pFanout, i )
411 {
412 if ( !Abc_ObjIsLatch(pFanout) )
413 continue;
414 if ( Init == -1 )
415 {
416 Init = (int)(ABC_PTRUINT_T)pObj->pData;
417 nLatches++;
418 }
419 else if ( Init == (int)(ABC_PTRUINT_T)pObj->pData )
420 nLatches++;
421 }
422 return nLatches;
423 }
424
425 /**Function*************************************************************
426
427 Synopsis [Retimes the node backward or forward.]
428
429 Description []
430
431 SideEffects []
432
433 SeeAlso []
434
435 ***********************************************************************/
Abc_NtkRetimeShareLatches(Abc_Ntk_t * pNtk,int fInitial)436 void Abc_NtkRetimeShareLatches( Abc_Ntk_t * pNtk, int fInitial )
437 {
438 Vec_Ptr_t * vNodes;
439 Abc_Obj_t * pFanin, * pLatchTop, * pLatchCur;
440 int i, k;
441 vNodes = Vec_PtrAlloc( 10 );
442 // consider latch fanins
443 Abc_NtkForEachObj( pNtk, pFanin, i )
444 {
445 if ( Abc_NtkRetimeCheckCompatibleLatchFanouts(pFanin) <= 1 )
446 continue;
447 // get the first latch
448 pLatchTop = NULL;
449 Abc_ObjForEachFanout( pFanin, pLatchTop, k )
450 if ( Abc_ObjIsLatch(pLatchTop) )
451 break;
452 assert( pLatchTop && Abc_ObjIsLatch(pLatchTop) );
453 // redirect compatible fanout latches to the first latch
454 Abc_NodeCollectFanouts( pFanin, vNodes );
455 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pLatchCur, k )
456 {
457 if ( !Abc_ObjIsLatch(pLatchCur) )
458 continue;
459 if ( pLatchCur == pLatchTop )
460 continue;
461 if ( pLatchCur->pData != pLatchTop->pData )
462 continue;
463 // connect the initial state
464 if ( fInitial )
465 Abc_ObjAddFanin( pLatchCur->pCopy, pLatchTop->pCopy );
466 // redirect the fanouts
467 Abc_ObjTransferFanout( pLatchCur, pLatchTop );
468 Abc_NtkDeleteObj(pLatchCur);
469 }
470 }
471 Vec_PtrFree( vNodes );
472 }
473
474 ////////////////////////////////////////////////////////////////////////
475 /// END OF FILE ///
476 ////////////////////////////////////////////////////////////////////////
477
478
479 ABC_NAMESPACE_IMPL_END
480
481