1 /**CFile****************************************************************
2
3 FileName [lpkAbcDec.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Fast Boolean matching for LUT structures.]
8
9 Synopsis [The new core procedure.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "lpkInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis [Implements the function.]
37
38 Description [Returns the node implementing this function.]
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Lpk_ImplementFun(Lpk_Man_t * pMan,Abc_Ntk_t * pNtk,Vec_Ptr_t * vLeaves,Lpk_Fun_t * p)45 Abc_Obj_t * Lpk_ImplementFun( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * p )
46 {
47 extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory );
48 unsigned * pTruth;
49 Abc_Obj_t * pObjNew;
50 int i;
51 if ( p->fMark )
52 pMan->nMuxes++;
53 else
54 pMan->nDsds++;
55 // create the new node
56 pObjNew = Abc_NtkCreateNode( pNtk );
57 for ( i = 0; i < (int)p->nVars; i++ )
58 Abc_ObjAddFanin( pObjNew, Abc_ObjRegular((Abc_Obj_t *)Vec_PtrEntry(vLeaves, p->pFanins[i])) );
59 Abc_ObjSetLevel( pObjNew, Abc_ObjLevelNew(pObjNew) );
60 // assign the node's function
61 pTruth = Lpk_FunTruth(p, 0);
62 if ( p->nVars == 0 )
63 {
64 pObjNew->pData = Hop_NotCond( Hop_ManConst1((Hop_Man_t *)pNtk->pManFunc), !(pTruth[0] & 1) );
65 return pObjNew;
66 }
67 if ( p->nVars == 1 )
68 {
69 pObjNew->pData = Hop_NotCond( Hop_ManPi((Hop_Man_t *)pNtk->pManFunc, 0), (pTruth[0] & 1) );
70 return pObjNew;
71 }
72 // create the logic function
73 pObjNew->pData = Kit_TruthToHop( (Hop_Man_t *)pNtk->pManFunc, pTruth, p->nVars, NULL );
74 return pObjNew;
75 }
76
77 /**Function*************************************************************
78
79 Synopsis [Implements the function.]
80
81 Description [Returns the node implementing this function.]
82
83 SideEffects []
84
85 SeeAlso []
86
87 ***********************************************************************/
Lpk_Implement_rec(Lpk_Man_t * pMan,Abc_Ntk_t * pNtk,Vec_Ptr_t * vLeaves,Lpk_Fun_t * pFun)88 Abc_Obj_t * Lpk_Implement_rec( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * pFun )
89 {
90 Abc_Obj_t * pFanin, * pRes;
91 int i;
92 // prepare the leaves of the function
93 for ( i = 0; i < (int)pFun->nVars; i++ )
94 {
95 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
96 if ( !Abc_ObjIsComplement(pFanin) )
97 Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin );
98 pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
99 assert( Abc_ObjIsComplement(pFanin) );
100 }
101 // construct the function
102 pRes = Lpk_ImplementFun( pMan, pNtk, vLeaves, pFun );
103 // replace the function
104 Vec_PtrWriteEntry( vLeaves, pFun->Id, Abc_ObjNot(pRes) );
105 Lpk_FunFree( pFun );
106 return pRes;
107 }
108
109 /**Function*************************************************************
110
111 Synopsis [Implements the function.]
112
113 Description [Returns the node implementing this function.]
114
115 SideEffects []
116
117 SeeAlso []
118
119 ***********************************************************************/
Lpk_Implement(Lpk_Man_t * pMan,Abc_Ntk_t * pNtk,Vec_Ptr_t * vLeaves,int nLeavesOld)120 Abc_Obj_t * Lpk_Implement( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld )
121 {
122 Abc_Obj_t * pFanin, * pRes;
123 int i;
124 assert( nLeavesOld < Vec_PtrSize(vLeaves) );
125 // mark implemented nodes
126 Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pFanin, i, nLeavesOld )
127 Vec_PtrWriteEntry( vLeaves, i, Abc_ObjNot(pFanin) );
128 // recursively construct starting from the first entry
129 pRes = Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)Vec_PtrEntry( vLeaves, nLeavesOld ) );
130 Vec_PtrShrink( vLeaves, nLeavesOld );
131 return pRes;
132 }
133
134 /**Function*************************************************************
135
136 Synopsis [Decomposes the function using recursive MUX decomposition.]
137
138 Description [Returns the ID of the top-most decomposition node
139 implementing this function, or 0 if there is no decomposition satisfying
140 the constraints on area and delay.]
141
142 SideEffects []
143
144 SeeAlso []
145
146 ***********************************************************************/
Lpk_Decompose_rec(Lpk_Man_t * pMan,Lpk_Fun_t * p)147 int Lpk_Decompose_rec( Lpk_Man_t * pMan, Lpk_Fun_t * p )
148 {
149 Lpk_Res_t * pResMux, * pResDsd;
150 Lpk_Fun_t * p2;
151 abctime clk;
152
153 // is only called for non-trivial blocks
154 assert( p->nLutK >= 3 && p->nLutK <= 6 );
155 assert( p->nVars > p->nLutK );
156 // skip if area bound is exceeded
157 if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim )
158 return 0;
159 // skip if delay bound is exceeded
160 if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim )
161 return 0;
162
163 // compute supports if needed
164 if ( !p->fSupports )
165 Lpk_FunComputeCofSupps( p );
166
167 // check DSD decomposition
168 clk = Abc_Clock();
169 pResDsd = Lpk_DsdAnalize( pMan, p, pMan->pPars->nVarsShared );
170 pMan->timeEvalDsdAn += Abc_Clock() - clk;
171 if ( pResDsd && (pResDsd->nBSVars == (int)p->nLutK || pResDsd->nBSVars == (int)p->nLutK - 1) &&
172 pResDsd->AreaEst <= (int)p->nAreaLim && pResDsd->DelayEst <= (int)p->nDelayLim )
173 {
174 clk = Abc_Clock();
175 p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
176 pMan->timeEvalDsdSp += Abc_Clock() - clk;
177 assert( p2->nVars <= (int)p->nLutK );
178 if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
179 return 0;
180 return 1;
181 }
182
183 // check MUX decomposition
184 clk = Abc_Clock();
185 pResMux = Lpk_MuxAnalize( pMan, p );
186 pMan->timeEvalMuxAn += Abc_Clock() - clk;
187 // pResMux = NULL;
188 assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) );
189 // accept MUX decomposition if it is "good"
190 if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK )
191 pResDsd = NULL;
192 else if ( pResMux && pResDsd )
193 {
194 // compare two decompositions
195 if ( pResMux->AreaEst < pResDsd->AreaEst ||
196 (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) ||
197 (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) )
198 pResDsd = NULL;
199 else
200 pResMux = NULL;
201 }
202 assert( pResMux == NULL || pResDsd == NULL );
203 if ( pResMux )
204 {
205 clk = Abc_Clock();
206 p2 = Lpk_MuxSplit( pMan, p, pResMux->Variable, pResMux->Polarity );
207 pMan->timeEvalMuxSp += Abc_Clock() - clk;
208 if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p2 ) )
209 return 0;
210 if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
211 return 0;
212 return 1;
213 }
214 if ( pResDsd )
215 {
216 clk = Abc_Clock();
217 p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
218 pMan->timeEvalDsdSp += Abc_Clock() - clk;
219 assert( p2->nVars <= (int)p->nLutK );
220 if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
221 return 0;
222 return 1;
223 }
224 return 0;
225 }
226
227 /**Function*************************************************************
228
229 Synopsis [Removes decomposed nodes from the array of fanins.]
230
231 Description []
232
233 SideEffects []
234
235 SeeAlso []
236
237 ***********************************************************************/
Lpk_DecomposeClean(Vec_Ptr_t * vLeaves,int nLeavesOld)238 void Lpk_DecomposeClean( Vec_Ptr_t * vLeaves, int nLeavesOld )
239 {
240 Lpk_Fun_t * pFunc;
241 int i;
242 Vec_PtrForEachEntryStart( Lpk_Fun_t *, vLeaves, pFunc, i, nLeavesOld )
243 Lpk_FunFree( pFunc );
244 Vec_PtrShrink( vLeaves, nLeavesOld );
245 }
246
247 /**Function*************************************************************
248
249 Synopsis [Decomposes the function using recursive MUX decomposition.]
250
251 Description []
252
253 SideEffects []
254
255 SeeAlso []
256
257 ***********************************************************************/
Lpk_Decompose(Lpk_Man_t * p,Abc_Ntk_t * pNtk,Vec_Ptr_t * vLeaves,unsigned * pTruth,unsigned * puSupps,int nLutK,int AreaLim,int DelayLim)258 Abc_Obj_t * Lpk_Decompose( Lpk_Man_t * p, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim )
259 {
260 Lpk_Fun_t * pFun;
261 Abc_Obj_t * pObjNew = NULL;
262 int nLeaves = Vec_PtrSize( vLeaves );
263 pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
264 if ( puSupps[0] || puSupps[1] )
265 {
266 /*
267 int i;
268 Lpk_FunComputeCofSupps( pFun );
269 for ( i = 0; i < nLeaves; i++ )
270 {
271 assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] );
272 assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] );
273 }
274 */
275 memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves );
276 pFun->fSupports = 1;
277 }
278 Lpk_FunSuppMinimize( pFun );
279 if ( pFun->nVars <= pFun->nLutK )
280 pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun );
281 else if ( Lpk_Decompose_rec(p, pFun) )
282 pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves );
283 Lpk_DecomposeClean( vLeaves, nLeaves );
284 return pObjNew;
285 }
286
287
288 ////////////////////////////////////////////////////////////////////////
289 /// END OF FILE ///
290 ////////////////////////////////////////////////////////////////////////
291
292
293 ABC_NAMESPACE_IMPL_END
294
295