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