1 /**CFile****************************************************************
2
3 FileName [ifDelay.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [FPGA mapping based on priority cuts.]
8
9 Synopsis [Delay balancing for cut functions.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - November 21, 2006.]
16
17 Revision [$Id: ifDelay.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "if.h"
22 #include "ifCount.h"
23 #include "bool/kit/kit.h"
24
25 ABC_NAMESPACE_IMPL_START
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 #define IF_MAX_CUBES 70
32
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36
37 /**Function*************************************************************
38
39 Synopsis [Computes the SOP delay using balanced AND decomposition.]
40
41 Description []
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
If_CutMaxCubeSize(Vec_Int_t * vCover,int nVars)48 static inline int If_CutMaxCubeSize( Vec_Int_t * vCover, int nVars )
49 {
50 int i, k, Entry, Literal, Count, CountMax = 0;
51 Vec_IntForEachEntry( vCover, Entry, i )
52 {
53 Count = 0;
54 for ( k = 0; k < nVars; k++ )
55 {
56 Literal = (3 & (Entry >> (k << 1)));
57 if ( Literal == 1 || Literal == 2 )
58 Count++;
59 }
60 CountMax = Abc_MaxInt( CountMax, Count );
61 }
62 return CountMax;
63 }
If_CutDelaySop(If_Man_t * p,If_Cut_t * pCut)64 int If_CutDelaySop( If_Man_t * p, If_Cut_t * pCut )
65 {
66 char * pPerm = If_CutPerm( pCut );
67 // delay is calculated using 1+log2(NumFanins)
68 static double GateDelays[20] = { 1.00, 1.00, 2.00, 2.58, 3.00, 3.32, 3.58, 3.81, 4.00, 4.17, 4.32, 4.46, 4.58, 4.70, 4.81, 4.91, 5.00, 5.09, 5.17, 5.25 };
69 Vec_Int_t * vCover;
70 If_Obj_t * pLeaf;
71 int i, nLitMax, Delay, DelayMax;
72 // mark cut as a user cut
73 pCut->fUser = 1;
74 if ( pCut->nLeaves == 0 )
75 return 0;
76 if ( pCut->nLeaves == 1 )
77 return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
78 vCover = Vec_WecEntry( p->vTtIsops[pCut->nLeaves], Abc_Lit2Var(If_CutTruthLit(pCut)) );
79 if ( Vec_IntSize(vCover) == 0 )
80 return -1;
81 // mark the output as complemented
82 // vAnds = If_CutDelaySopAnds( p, pCut, vCover, RetValue ^ pCut->fCompl );
83 if ( Vec_IntSize(vCover) > p->pPars->nGateSize )
84 return -1;
85 // set the area cost
86 assert( If_CutLeaveNum(pCut) >= 0 && If_CutLeaveNum(pCut) <= 16 );
87 // compute the gate delay
88 nLitMax = If_CutMaxCubeSize( vCover, If_CutLeaveNum(pCut) );
89 if ( Vec_IntSize(vCover) < 2 )
90 {
91 pCut->Cost = Vec_IntSize(vCover);
92 Delay = (int)(GateDelays[If_CutLeaveNum(pCut)] + 0.5);
93 DelayMax = 0;
94 If_CutForEachLeaf( p, pCut, pLeaf, i )
95 DelayMax = Abc_MaxInt( DelayMax, If_ObjCutBest(pLeaf)->Delay + (pPerm[i] = (char)Delay) );
96 }
97 else
98 {
99 pCut->Cost = Vec_IntSize(vCover) + 1;
100 Delay = (int)(GateDelays[If_CutLeaveNum(pCut)] + GateDelays[nLitMax] + 0.5);
101 DelayMax = 0;
102 If_CutForEachLeaf( p, pCut, pLeaf, i )
103 DelayMax = Abc_MaxInt( DelayMax, If_ObjCutBest(pLeaf)->Delay + (pPerm[i] = (char)Delay) );
104 }
105 return DelayMax;
106 }
107
108
109 /**Function*************************************************************
110
111 Synopsis [Compute pin delays.]
112
113 Description []
114
115 SideEffects []
116
117 SeeAlso []
118
119 ***********************************************************************/
If_CutSopBalancePinDelaysInt(Vec_Int_t * vCover,int * pTimes,word * pFaninRes,int nSuppAll,word * pRes)120 int If_CutSopBalancePinDelaysInt( Vec_Int_t * vCover, int * pTimes, word * pFaninRes, int nSuppAll, word * pRes )
121 {
122 word pPinDelsAnd[IF_MAX_FUNC_LUTSIZE], pPinDelsOr[IF_MAX_CUBES];
123 int nCounterAnd, pCounterAnd[IF_MAX_FUNC_LUTSIZE];
124 int nCounterOr, pCounterOr[IF_MAX_CUBES];
125 int i, k, Entry, Literal, Delay = 0;
126 word ResAnd;
127 if ( Vec_IntSize(vCover) > IF_MAX_CUBES )
128 return -1;
129 nCounterOr = 0;
130 Vec_IntForEachEntry( vCover, Entry, i )
131 {
132 nCounterAnd = 0;
133 for ( k = 0; k < nSuppAll; k++ )
134 {
135 Literal = 3 & (Entry >> (k << 1));
136 if ( Literal == 1 || Literal == 2 ) // neg or pos literal
137 Delay = If_LogCounterPinDelays( pCounterAnd, &nCounterAnd, pPinDelsAnd, pTimes[k], pFaninRes[k], nSuppAll, 0 );
138 else if ( Literal != 0 )
139 assert( 0 );
140 }
141 assert( nCounterAnd > 0 );
142 ResAnd = If_LogPinDelaysMulti( pPinDelsAnd, nCounterAnd, nSuppAll, 0 );
143 Delay = If_LogCounterPinDelays( pCounterOr, &nCounterOr, pPinDelsOr, Delay, ResAnd, nSuppAll, 0 );
144 }
145 assert( nCounterOr > 0 );
146 *pRes = If_LogPinDelaysMulti( pPinDelsOr, nCounterOr, nSuppAll, 0 );
147 return Delay;
148 }
If_CutSopBalancePinDelaysIntInt(Vec_Int_t * vCover,int * pTimes,int nSuppAll,char * pPerm)149 int If_CutSopBalancePinDelaysIntInt( Vec_Int_t * vCover, int * pTimes, int nSuppAll, char * pPerm )
150 {
151 int i, Delay;
152 word Res, FaninRes[IF_MAX_FUNC_LUTSIZE];
153 for ( i = 0; i < nSuppAll; i++ )
154 FaninRes[i] = If_CutPinDelayInit(i);
155 Delay = If_CutSopBalancePinDelaysInt( vCover, pTimes, FaninRes, nSuppAll, &Res );
156 If_CutPinDelayTranslate( Res, nSuppAll, pPerm );
157 return Delay;
158 }
If_CutSopBalancePinDelays(If_Man_t * p,If_Cut_t * pCut,char * pPerm)159 int If_CutSopBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm )
160 {
161 if ( pCut->nLeaves == 0 ) // const
162 return 0;
163 if ( pCut->nLeaves == 1 ) // variable
164 {
165 pPerm[0] = 0;
166 return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
167 }
168 else
169 {
170 Vec_Int_t * vCover;
171 int i, pTimes[IF_MAX_FUNC_LUTSIZE];
172 vCover = Vec_WecEntry( p->vTtIsops[pCut->nLeaves], Abc_Lit2Var(If_CutTruthLit(pCut)) );
173 if ( Vec_IntSize(vCover) == 0 )
174 return -1;
175 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
176 pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay;
177 return If_CutSopBalancePinDelaysIntInt( vCover, pTimes, If_CutLeaveNum(pCut), pPerm );
178 }
179 }
180
181 /**Function*************************************************************
182
183 Synopsis [Evaluate delay using SOP balancing.]
184
185 Description []
186
187 SideEffects []
188
189 SeeAlso []
190
191 ***********************************************************************/
If_CutSopBalanceEvalInt(Vec_Int_t * vCover,int * pTimes,int * pFaninLits,Vec_Int_t * vAig,int * piRes,int nSuppAll,int * pArea)192 int If_CutSopBalanceEvalInt( Vec_Int_t * vCover, int * pTimes, int * pFaninLits, Vec_Int_t * vAig, int * piRes, int nSuppAll, int * pArea )
193 {
194 int nCounterAnd, pCounterAnd[IF_MAX_FUNC_LUTSIZE], pFaninLitsAnd[IF_MAX_FUNC_LUTSIZE];
195 int nCounterOr, pCounterOr[IF_MAX_CUBES], pFaninLitsOr[IF_MAX_CUBES];
196 int i, k, Entry, Literal, nLits, Delay = 0, iRes = 0;
197 if ( Vec_IntSize(vCover) > IF_MAX_CUBES )
198 return -1;
199 nCounterOr = 0;
200 Vec_IntForEachEntry( vCover, Entry, i )
201 {
202 nCounterAnd = nLits = 0;
203 for ( k = 0; k < nSuppAll; k++ )
204 {
205 Literal = 3 & (Entry >> (k << 1));
206 if ( Literal == 1 ) // neg literal
207 nLits++, Delay = If_LogCounterAddAig( pCounterAnd, &nCounterAnd, pFaninLitsAnd, pTimes[k], vAig ? Abc_LitNot(pFaninLits[k]) : -1, vAig, nSuppAll, 0, 0 );
208 else if ( Literal == 2 ) // pos literal
209 nLits++, Delay = If_LogCounterAddAig( pCounterAnd, &nCounterAnd, pFaninLitsAnd, pTimes[k], vAig ? pFaninLits[k] : -1, vAig, nSuppAll, 0, 0 );
210 else if ( Literal != 0 )
211 assert( 0 );
212 }
213 assert( nCounterAnd > 0 );
214 assert( nLits > 0 );
215 if ( vAig )
216 iRes = If_LogCreateAndXorMulti( vAig, pFaninLitsAnd, nCounterAnd, nSuppAll, 0 );
217 else
218 *pArea += nLits == 1 ? 0 : nLits - 1;
219 Delay = If_LogCounterAddAig( pCounterOr, &nCounterOr, pFaninLitsOr, Delay, vAig ? Abc_LitNot(iRes) : -1, vAig, nSuppAll, 0, 0 );
220 }
221 assert( nCounterOr > 0 );
222 if ( vAig )
223 {
224 *piRes = Abc_LitNot( If_LogCreateAndXorMulti( vAig, pFaninLitsOr, nCounterOr, nSuppAll, 0 ) );
225 if ( ((vCover->nCap >> 16) & 1) ) // hack to remember complemented attribute
226 *piRes = Abc_LitNot( *piRes );
227 }
228 else
229 *pArea += Vec_IntSize(vCover) == 1 ? 0 : Vec_IntSize(vCover) - 1;
230 return Delay;
231 }
If_CutSopBalanceEvalIntInt(Vec_Int_t * vCover,int nLeaves,int * pTimes,Vec_Int_t * vAig,int fCompl,int * pArea)232 int If_CutSopBalanceEvalIntInt( Vec_Int_t * vCover, int nLeaves, int * pTimes, Vec_Int_t * vAig, int fCompl, int * pArea )
233 {
234 int pFaninLits[IF_MAX_FUNC_LUTSIZE];
235 int iRes = 0, Res, k;
236 if ( vAig )
237 for ( k = 0; k < nLeaves; k++ )
238 pFaninLits[k] = Abc_Var2Lit(k, 0);
239 Res = If_CutSopBalanceEvalInt( vCover, pTimes, pFaninLits, vAig, &iRes, nLeaves, pArea );
240 if ( Res == -1 )
241 return -1;
242 assert( vAig == NULL || Abc_Lit2Var(iRes) == nLeaves + Abc_Lit2Var(Vec_IntSize(vAig)) - 1 );
243 if ( vAig )
244 Vec_IntPush( vAig, Abc_LitIsCompl(iRes) ^ fCompl );
245 assert( vAig == NULL || (Vec_IntSize(vAig) & 1) );
246 return Res;
247 }
If_CutSopBalanceEval(If_Man_t * p,If_Cut_t * pCut,Vec_Int_t * vAig)248 int If_CutSopBalanceEval( If_Man_t * p, If_Cut_t * pCut, Vec_Int_t * vAig )
249 {
250 pCut->fUser = 1;
251 if ( vAig )
252 Vec_IntClear( vAig );
253 if ( pCut->nLeaves == 0 ) // const
254 {
255 assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 );
256 if ( vAig )
257 Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) );
258 pCut->Cost = 0;
259 return 0;
260 }
261 if ( pCut->nLeaves == 1 ) // variable
262 {
263 assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 1 );
264 if ( vAig )
265 Vec_IntPush( vAig, 0 );
266 if ( vAig )
267 Vec_IntPush( vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) );
268 pCut->Cost = 0;
269 return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
270 }
271 else
272 {
273 int fVerbose = 0;
274 Vec_Int_t * vCover = Vec_WecEntry( p->vTtIsops[pCut->nLeaves], Abc_Lit2Var(If_CutTruthLit(pCut)) );
275 int Delay, Area = 0;
276 int i, pTimes[IF_MAX_FUNC_LUTSIZE];
277 if ( vCover == NULL )
278 return -1;
279 assert( Vec_IntSize(vCover) > 0 );
280 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
281 pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay;
282 Delay = If_CutSopBalanceEvalIntInt( vCover, If_CutLeaveNum(pCut), pTimes, vAig, Abc_LitIsCompl(If_CutTruthLit(pCut)) ^ pCut->fCompl, &Area );
283 pCut->Cost = Area;
284 if ( fVerbose )
285 {
286 int Max = 0, Two = 0;
287 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
288 Max = Abc_MaxInt( Max, pTimes[i] );
289 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
290 if ( pTimes[i] != Max )
291 Two = Abc_MaxInt( Two, pTimes[i] );
292 if ( Two + 2 < Max && Max + 3 < Delay )
293 {
294 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
295 printf( "%3d ", pTimes[i] );
296 for ( ; i < p->pPars->nLutSize; i++ )
297 printf( " " );
298 printf( "-> %3d ", Delay );
299 Dau_DsdPrintFromTruth( If_CutTruthW(p, pCut), If_CutLeaveNum(pCut) );
300 Kit_TruthIsopPrintCover( vCover, If_CutLeaveNum(pCut), Abc_LitIsCompl(If_CutTruthLit(pCut)) ^ pCut->fCompl );
301 {
302 Vec_Int_t vIsop;
303 int pIsop[64];
304 vIsop.nCap = vIsop.nSize = Abc_Tt6Esop( *If_CutTruthW(p, pCut), pCut->nLeaves, pIsop );
305 vIsop.pArray = pIsop;
306 printf( "ESOP (%d -> %d)\n", Vec_IntSize(vCover), vIsop.nSize );
307 Kit_TruthIsopPrintCover( &vIsop, If_CutLeaveNum(pCut), 0 );
308 }
309 printf( "\n" );
310 }
311 }
312 return Delay;
313 }
314 }
315
316 /**Function*************************************************************
317
318 Synopsis [Evaluate delay using SOP balancing.]
319
320 Description []
321
322 SideEffects []
323
324 SeeAlso []
325
326 ***********************************************************************/
If_CutLutBalancePinDelays(If_Man_t * p,If_Cut_t * pCut,char * pPerm)327 int If_CutLutBalancePinDelays( If_Man_t * p, If_Cut_t * pCut, char * pPerm )
328 {
329 if ( pCut->nLeaves == 0 ) // const
330 return 0;
331 if ( pCut->nLeaves == 1 ) // variable
332 {
333 pPerm[0] = 0;
334 return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
335 }
336 else
337 {
338 char * pCutPerm = If_CutDsdPerm( p, pCut );
339 int LutSize = p->pPars->pLutStruct[0] - '0';
340 int i, Delay, DelayMax = -1;
341 assert( (If_CutLeaveNum(pCut) > LutSize) == (pCut->uMaskFunc > 0) );
342 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
343 {
344 if ( If_CutLeaveNum(pCut) > LutSize && ((pCut->uMaskFunc >> (i << 1)) & 1) )
345 pPerm[Abc_Lit2Var((int)pCutPerm[i])] = 2;
346 else
347 pPerm[Abc_Lit2Var((int)pCutPerm[i])] = 1;
348 }
349 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
350 {
351 Delay = (int)If_ObjCutBest(If_CutLeaf(p, pCut, i))->Delay;
352 DelayMax = Abc_MaxInt( DelayMax, Delay + (int)pPerm[i] );
353 }
354 return DelayMax;
355 }
356 }
357
358 /**Function*************************************************************
359
360 Synopsis [Evaluate delay using SOP balancing.]
361
362 Description []
363
364 SideEffects []
365
366 SeeAlso []
367
368 ***********************************************************************/
If_CutLutBalanceEval(If_Man_t * p,If_Cut_t * pCut)369 int If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut )
370 {
371 pCut->fUser = 1;
372 pCut->Cost = pCut->nLeaves > 1 ? 1 : 0;
373 pCut->uMaskFunc = 0;
374 if ( pCut->nLeaves == 0 ) // const
375 {
376 assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 0 );
377 return 0;
378 }
379 if ( pCut->nLeaves == 1 ) // variable
380 {
381 assert( Abc_Lit2Var(If_CutTruthLit(pCut)) == 1 );
382 return (int)If_ObjCutBest(If_CutLeaf(p, pCut, 0))->Delay;
383 }
384 else
385 {
386 char * pCutPerm = If_CutDsdPerm( p, pCut );
387 int LutSize = p->pPars->pLutStruct[0] - '0';
388 int i, pTimes[IF_MAX_FUNC_LUTSIZE];
389 int DelayMax = -1, nLeafMax = 0;
390 unsigned uLeafMask = 0;
391 for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
392 {
393 pTimes[i] = (int)If_ObjCutBest(If_CutLeaf(p, pCut, Abc_Lit2Var((int)pCutPerm[i])))->Delay;
394 if ( DelayMax < pTimes[i] )
395 DelayMax = pTimes[i], nLeafMax = 1, uLeafMask = (1 << (i << 1));
396 else if ( DelayMax == pTimes[i] )
397 nLeafMax++, uLeafMask |= (1 << (i << 1));
398 }
399 if ( If_CutLeaveNum(pCut) <= LutSize )
400 return DelayMax + 1;
401 pCut->Cost = 2;
402 if ( nLeafMax <= LutSize - 1 )
403 {
404 pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, uLeafMask, 0, 0 );
405 if ( pCut->uMaskFunc > 0 )
406 return DelayMax + 1;
407 }
408 pCut->uMaskFunc = If_DsdManCheckXY( p->pIfDsdMan, If_CutDsdLit(p, pCut), LutSize, 1, 0, 0, 0 );
409 if ( pCut->uMaskFunc == 0 )
410 return -1;
411 return DelayMax + 2;
412 }
413 }
414 /*
415 int If_CutLutBalanceEval( If_Man_t * p, If_Cut_t * pCut )
416 {
417 char pPerm[16];
418 int Delay2, Delay = If_CutLutBalanceEvalInt( p, pCut );
419 if ( Delay == -1 )
420 return -1;
421 Delay2 = If_CutLutBalancePinDelays( p, pCut, pPerm );
422 if ( Delay2 != Delay )
423 {
424 int s = 0;
425 char * pCutPerm = If_CutDsdPerm( p, pCut );
426 If_DsdManPrintNode( p->pIfDsdMan, If_CutDsdLit(p, pCut) ); Dau_DecPrintSet( pCut->uMaskFunc, pCut->nLeaves, 1 );
427 Kit_DsdPrintFromTruth( If_CutTruthUR(p, pCut), pCut->nLeaves ); printf( "\n" );
428 for ( s = 0; s < pCut->nLeaves; s++ )
429 // printf( "%d ", (int)If_ObjCutBest(If_CutLeaf(p, pCut, Abc_Lit2Var((int)pCutPerm[s])))->Delay );
430 printf( "%d ", (int)If_ObjCutBest(If_CutLeaf(p, pCut, s))->Delay );
431 printf( "\n" );
432
433 Delay = If_CutLutBalanceEvalInt( p, pCut );
434 Delay2 = If_CutLutBalancePinDelays( p, pCut, pPerm );
435 }
436
437 return Delay;
438 }
439 */
440
441 ////////////////////////////////////////////////////////////////////////
442 /// END OF FILE ///
443 ////////////////////////////////////////////////////////////////////////
444
445
446 ABC_NAMESPACE_IMPL_END
447
448