1 /**CFile****************************************************************
2
3 FileName [abcLutmin.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Minimization of the number of LUTs.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcLutmin.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "base/abc/abc.h"
22
23 #ifdef ABC_USE_CUDD
24 #include "bdd/extrab/extraBdd.h"
25 #endif
26
27 ABC_NAMESPACE_IMPL_START
28
29
30 /*
31 Implememented here is the algorithm for minimal-LUT decomposition
32 described in the paper: T. Sasao et al. "On the number of LUTs
33 to implement logic functions", To appear in Proc. IWLS'09.
34 */
35
36 ////////////////////////////////////////////////////////////////////////
37 /// DECLARATIONS ///
38 ////////////////////////////////////////////////////////////////////////
39
40 ////////////////////////////////////////////////////////////////////////
41 /// FUNCTION DEFINITIONS ///
42 ////////////////////////////////////////////////////////////////////////
43
44 #ifdef ABC_USE_CUDD
45
46 /**Function*************************************************************
47
48 Synopsis [Check if a LUT can absort a fanin.]
49
50 Description [The fanins are (c, d0, d1).]
51
52 SideEffects []
53
54 SeeAlso []
55
56 ***********************************************************************/
Abc_ObjCheckAbsorb(Abc_Obj_t * pObj,Abc_Obj_t * pPivot,int nLutSize,Vec_Ptr_t * vFanins)57 int Abc_ObjCheckAbsorb( Abc_Obj_t * pObj, Abc_Obj_t * pPivot, int nLutSize, Vec_Ptr_t * vFanins )
58 {
59 Abc_Obj_t * pFanin;
60 int i;
61 assert( Abc_ObjIsNode(pObj) && Abc_ObjIsNode(pPivot) );
62 // add fanins of the node
63 Vec_PtrClear( vFanins );
64 Abc_ObjForEachFanin( pObj, pFanin, i )
65 if ( pFanin != pPivot )
66 Vec_PtrPush( vFanins, pFanin );
67 // add fanins of the fanin
68 Abc_ObjForEachFanin( pPivot, pFanin, i )
69 {
70 Vec_PtrPushUnique( vFanins, pFanin );
71 if ( Vec_PtrSize(vFanins) > nLutSize )
72 return 0;
73 }
74 return 1;
75 }
76
77 /**Function*************************************************************
78
79 Synopsis [Check how many times a LUT can absorb a fanin.]
80
81 Description [The fanins are (c, d0, d1).]
82
83 SideEffects []
84
85 SeeAlso []
86
87 ***********************************************************************/
Abc_NtkCheckAbsorb(Abc_Ntk_t * pNtk,int nLutSize)88 void Abc_NtkCheckAbsorb( Abc_Ntk_t * pNtk, int nLutSize )
89 {
90 Vec_Int_t * vCounts;
91 Vec_Ptr_t * vFanins;
92 Abc_Obj_t * pObj, * pFanin;
93 int i, k, Counter = 0, Counter2 = 0;
94 abctime clk = Abc_Clock();
95 vCounts = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
96 vFanins = Vec_PtrAlloc( 100 );
97 Abc_NtkForEachNode( pNtk, pObj, i )
98 Abc_ObjForEachFanin( pObj, pFanin, k )
99 if ( Abc_ObjIsNode(pFanin) && Abc_ObjCheckAbsorb( pObj, pFanin, nLutSize, vFanins ) )
100 {
101 Vec_IntAddToEntry( vCounts, Abc_ObjId(pFanin), 1 );
102 Counter++;
103 }
104 Vec_PtrFree( vFanins );
105 Abc_NtkForEachNode( pNtk, pObj, i )
106 if ( Vec_IntEntry(vCounts, Abc_ObjId(pObj)) == Abc_ObjFanoutNum(pObj) )
107 {
108 // printf( "%d ", Abc_ObjId(pObj) );
109 Counter2++;
110 }
111 printf( "Absorted = %6d. (%6.2f %%) Fully = %6d. (%6.2f %%) ",
112 Counter, 100.0 * Counter / Abc_NtkNodeNum(pNtk),
113 Counter2, 100.0 * Counter2 / Abc_NtkNodeNum(pNtk) );
114 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
115 }
116
117 /**Function*************************************************************
118
119 Synopsis [Implements 2:1 MUX using one 3-LUT.]
120
121 Description [The fanins are (c, d0, d1).]
122
123 SideEffects []
124
125 SeeAlso []
126
127 ***********************************************************************/
Abc_NtkBddMux21(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pFanins[])128 Abc_Obj_t * Abc_NtkBddMux21( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pFanins[] )
129 {
130 DdManager * dd = (DdManager *)pNtkNew->pManFunc;
131 Abc_Obj_t * pNode;
132 DdNode * bSpin, * bCof0, * bCof1;
133 pNode = Abc_NtkCreateNode( pNtkNew );
134 Abc_ObjAddFanin( pNode, pFanins[0] );
135 Abc_ObjAddFanin( pNode, pFanins[1] );
136 Abc_ObjAddFanin( pNode, pFanins[2] );
137 bSpin = Cudd_bddIthVar(dd, 0);
138 bCof0 = Cudd_bddIthVar(dd, 1);
139 bCof1 = Cudd_bddIthVar(dd, 2);
140 pNode->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNode->pData );
141 return pNode;
142 }
143
144 /**Function*************************************************************
145
146 Synopsis [Implements 4:1 MUX using one 6-LUT.]
147
148 Description [The fanins are (c0, c1, d00, d01, d10, d11).]
149
150 SideEffects []
151
152 SeeAlso []
153
154 ***********************************************************************/
Abc_NtkBddMux411(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pFanins[])155 Abc_Obj_t * Abc_NtkBddMux411( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pFanins[] )
156 {
157 DdManager * dd = (DdManager *)pNtkNew->pManFunc;
158 Abc_Obj_t * pNode;
159 DdNode * bSpin, * bCof0, * bCof1;
160 pNode = Abc_NtkCreateNode( pNtkNew );
161 Abc_ObjAddFanin( pNode, pFanins[0] );
162 Abc_ObjAddFanin( pNode, pFanins[1] );
163 Abc_ObjAddFanin( pNode, pFanins[2] );
164 Abc_ObjAddFanin( pNode, pFanins[3] );
165 Abc_ObjAddFanin( pNode, pFanins[4] );
166 Abc_ObjAddFanin( pNode, pFanins[5] );
167 bSpin = Cudd_bddIthVar(dd, 1);
168 bCof0 = Cudd_bddIte( dd, bSpin, Cudd_bddIthVar(dd, 3), Cudd_bddIthVar(dd, 2) ); Cudd_Ref( bCof0 );
169 bCof1 = Cudd_bddIte( dd, bSpin, Cudd_bddIthVar(dd, 5), Cudd_bddIthVar(dd, 4) ); Cudd_Ref( bCof1 );
170 bSpin = Cudd_bddIthVar(dd, 0);
171 pNode->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNode->pData );
172 Cudd_RecursiveDeref( dd, bCof0 );
173 Cudd_RecursiveDeref( dd, bCof1 );
174 return pNode;
175 }
176
177 /**Function*************************************************************
178
179 Synopsis [Implementes 4:1 MUX using two 4-LUTs.]
180
181 Description [The fanins are (c0, c1, d00, d01, d10, d11).]
182
183 SideEffects []
184
185 SeeAlso []
186
187 ***********************************************************************/
Abc_NtkBddMux412(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pFanins[])188 Abc_Obj_t * Abc_NtkBddMux412( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pFanins[] )
189 {
190 DdManager * dd = (DdManager *)pNtkNew->pManFunc;
191 Abc_Obj_t * pNodeBot, * pNodeTop;
192 DdNode * bSpin, * bCof0, * bCof1;
193 // bottom node
194 pNodeBot = Abc_NtkCreateNode( pNtkNew );
195 Abc_ObjAddFanin( pNodeBot, pFanins[0] );
196 Abc_ObjAddFanin( pNodeBot, pFanins[1] );
197 Abc_ObjAddFanin( pNodeBot, pFanins[2] );
198 Abc_ObjAddFanin( pNodeBot, pFanins[3] );
199 bSpin = Cudd_bddIthVar(dd, 0);
200 bCof0 = Cudd_bddIte( dd, Cudd_bddIthVar(dd, 1), Cudd_bddIthVar(dd, 3), Cudd_bddIthVar(dd, 2) ); Cudd_Ref( bCof0 );
201 bCof1 = Cudd_bddIthVar(dd, 1);
202 pNodeBot->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNodeBot->pData );
203 Cudd_RecursiveDeref( dd, bCof0 );
204 // top node
205 pNodeTop = Abc_NtkCreateNode( pNtkNew );
206 Abc_ObjAddFanin( pNodeTop, pFanins[0] );
207 Abc_ObjAddFanin( pNodeTop, pNodeBot );
208 Abc_ObjAddFanin( pNodeTop, pFanins[4] );
209 Abc_ObjAddFanin( pNodeTop, pFanins[5] );
210 bSpin = Cudd_bddIthVar(dd, 0);
211 bCof0 = Cudd_bddIthVar(dd, 1);
212 bCof1 = Cudd_bddIte( dd, Cudd_bddIthVar(dd, 1), Cudd_bddIthVar(dd, 3), Cudd_bddIthVar(dd, 2) ); Cudd_Ref( bCof1 );
213 pNodeTop->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNodeTop->pData );
214 Cudd_RecursiveDeref( dd, bCof1 );
215 return pNodeTop;
216 }
217
218 /**Function*************************************************************
219
220 Synopsis [Implementes 4:1 MUX using two 4-LUTs.]
221
222 Description [The fanins are (c0, c1, d00, d01, d10, d11).]
223
224 SideEffects []
225
226 SeeAlso []
227
228 ***********************************************************************/
Abc_NtkBddMux412a(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pFanins[])229 Abc_Obj_t * Abc_NtkBddMux412a( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pFanins[] )
230 {
231 DdManager * dd = (DdManager *)pNtkNew->pManFunc;
232 Abc_Obj_t * pNodeBot, * pNodeTop;
233 DdNode * bSpin, * bCof0, * bCof1;
234 // bottom node
235 pNodeBot = Abc_NtkCreateNode( pNtkNew );
236 Abc_ObjAddFanin( pNodeBot, pFanins[1] );
237 Abc_ObjAddFanin( pNodeBot, pFanins[2] );
238 Abc_ObjAddFanin( pNodeBot, pFanins[3] );
239 bSpin = Cudd_bddIthVar(dd, 0);
240 bCof0 = Cudd_bddIthVar(dd, 1);
241 bCof1 = Cudd_bddIthVar(dd, 2);
242 pNodeBot->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNodeBot->pData );
243 // top node
244 pNodeTop = Abc_NtkCreateNode( pNtkNew );
245 Abc_ObjAddFanin( pNodeTop, pFanins[0] );
246 Abc_ObjAddFanin( pNodeTop, pFanins[1] );
247 Abc_ObjAddFanin( pNodeTop, pNodeBot );
248 Abc_ObjAddFanin( pNodeTop, pFanins[4] );
249 Abc_ObjAddFanin( pNodeTop, pFanins[5] );
250 bSpin = Cudd_bddIthVar(dd, 0);
251 bCof0 = Cudd_bddIthVar(dd, 2);
252 bCof1 = Cudd_bddIte( dd, Cudd_bddIthVar(dd, 1), Cudd_bddIthVar(dd, 4), Cudd_bddIthVar(dd, 3) ); Cudd_Ref( bCof1 );
253 pNodeTop->pData = Cudd_bddIte( dd, bSpin, bCof1, bCof0 ); Cudd_Ref( (DdNode *)pNodeTop->pData );
254 Cudd_RecursiveDeref( dd, bCof1 );
255 return pNodeTop;
256 }
257
258 /**Function*************************************************************
259
260 Synopsis [Implements 4:1 MUX using three 2:1 MUXes.]
261
262 Description [The fanins are (c0, c1, d00, d01, d10, d11).]
263
264 SideEffects []
265
266 SeeAlso []
267
268 ***********************************************************************/
Abc_NtkBddMux413(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pFanins[])269 Abc_Obj_t * Abc_NtkBddMux413( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pFanins[] )
270 {
271 Abc_Obj_t * pNodesBot[3], * pNodesTop[3];
272 // left bottom
273 pNodesBot[0] = pFanins[1];
274 pNodesBot[1] = pFanins[2];
275 pNodesBot[2] = pFanins[3];
276 pNodesTop[1] = Abc_NtkBddMux21( pNtkNew, pNodesBot );
277 // right bottom
278 pNodesBot[0] = pFanins[1];
279 pNodesBot[1] = pFanins[4];
280 pNodesBot[2] = pFanins[5];
281 pNodesTop[2] = Abc_NtkBddMux21( pNtkNew, pNodesBot );
282 // top node
283 pNodesTop[0] = pFanins[0];
284 return Abc_NtkBddMux21( pNtkNew, pNodesTop );
285 }
286
287 /**Function*************************************************************
288
289 Synopsis [Finds unique cofactors of the function on the given level.]
290
291 Description []
292
293 SideEffects []
294
295 SeeAlso []
296
297 ***********************************************************************/
Abc_NtkBddCofactors_rec(DdManager * dd,DdNode * bNode,int iCof,int iLevel,int nLevels)298 DdNode * Abc_NtkBddCofactors_rec( DdManager * dd, DdNode * bNode, int iCof, int iLevel, int nLevels )
299 {
300 DdNode * bNode0, * bNode1;
301 if ( Cudd_IsConstant(bNode) || iLevel == nLevels )
302 return bNode;
303 if ( Cudd_ReadPerm( dd, Cudd_NodeReadIndex(bNode) ) > iLevel )
304 {
305 bNode0 = bNode;
306 bNode1 = bNode;
307 }
308 else if ( Cudd_IsComplement(bNode) )
309 {
310 bNode0 = Cudd_Not(cuddE(Cudd_Regular(bNode)));
311 bNode1 = Cudd_Not(cuddT(Cudd_Regular(bNode)));
312 }
313 else
314 {
315 bNode0 = cuddE(bNode);
316 bNode1 = cuddT(bNode);
317 }
318 if ( (iCof >> (nLevels-1-iLevel)) & 1 )
319 return Abc_NtkBddCofactors_rec( dd, bNode1, iCof, iLevel + 1, nLevels );
320 return Abc_NtkBddCofactors_rec( dd, bNode0, iCof, iLevel + 1, nLevels );
321 }
322
323 /**Function*************************************************************
324
325 Synopsis [Finds unique cofactors of the function on the given level.]
326
327 Description []
328
329 SideEffects []
330
331 SeeAlso []
332
333 ***********************************************************************/
Abc_NtkBddCofactors(DdManager * dd,DdNode * bNode,int Level)334 Vec_Ptr_t * Abc_NtkBddCofactors( DdManager * dd, DdNode * bNode, int Level )
335 {
336 Vec_Ptr_t * vCofs;
337 int i, nCofs = (1<<Level);
338 assert( Level > 0 && Level < 10 );
339 vCofs = Vec_PtrAlloc( 8 );
340 for ( i = 0; i < nCofs; i++ )
341 Vec_PtrPush( vCofs, Abc_NtkBddCofactors_rec( dd, bNode, i, 0, Level ) );
342 return vCofs;
343 }
344
345 /**Function*************************************************************
346
347 Synopsis [Comparison procedure for two integers.]
348
349 Description []
350
351 SideEffects []
352
353 SeeAlso []
354
355 ***********************************************************************/
Vec_PtrSortCompare(void ** pp1,void ** pp2)356 static int Vec_PtrSortCompare( void ** pp1, void ** pp2 )
357 {
358 if ( *pp1 < *pp2 )
359 return -1;
360 if ( *pp1 > *pp2 )
361 return 1;
362 return 0;
363 }
364
365 /**Function*************************************************************
366
367 Synopsis [Converts the node to MUXes.]
368
369 Description []
370
371 SideEffects []
372
373 SeeAlso []
374
375 ***********************************************************************/
Abc_NtkCreateCofLut(Abc_Ntk_t * pNtkNew,DdManager * dd,DdNode * bCof,Abc_Obj_t * pNode,int Level)376 Abc_Obj_t * Abc_NtkCreateCofLut( Abc_Ntk_t * pNtkNew, DdManager * dd, DdNode * bCof, Abc_Obj_t * pNode, int Level )
377 {
378 int fVerbose = 0;
379 DdNode * bFuncNew;
380 Abc_Obj_t * pNodeNew;
381 int i;
382 assert( Abc_ObjFaninNum(pNode) > Level );
383 // create a new node
384 pNodeNew = Abc_NtkCreateNode( pNtkNew );
385 // add the fanins in the order, in which they appear in the reordered manager
386 for ( i = Level; i < Abc_ObjFaninNum(pNode); i++ )
387 Abc_ObjAddFanin( pNodeNew, Abc_ObjFanin(pNode, i)->pCopy );
388 if ( fVerbose )
389 {
390 Extra_bddPrint( dd, bCof );
391 printf( "\n" );
392 printf( "\n" );
393 }
394 // transfer the function
395 bFuncNew = Extra_bddMove( dd, bCof, -Level ); Cudd_Ref( bFuncNew );
396 if ( fVerbose )
397 {
398 Extra_bddPrint( dd, bFuncNew );
399 printf( "\n" );
400 printf( "\n" );
401 }
402 pNodeNew->pData = Extra_TransferLevelByLevel( dd, (DdManager *)pNtkNew->pManFunc, bFuncNew ); Cudd_Ref( (DdNode *)pNodeNew->pData );
403 //Extra_bddPrint( pNtkNew->pManFunc, pNodeNew->pData );
404 //printf( "\n" );
405 //printf( "\n" );
406 Cudd_RecursiveDeref( dd, bFuncNew );
407 return pNodeNew;
408 }
409
410 /**Function*************************************************************
411
412 Synopsis [Performs one step of Ashenhurst-Curtis decomposition.]
413
414 Description []
415
416 SideEffects []
417
418 SeeAlso []
419
420 ***********************************************************************/
Abc_NtkBddCurtis(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pNode,Vec_Ptr_t * vCofs,Vec_Ptr_t * vUniq)421 Abc_Obj_t * Abc_NtkBddCurtis( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Ptr_t * vCofs, Vec_Ptr_t * vUniq )
422 {
423 DdManager * ddOld = (DdManager *)pNode->pNtk->pManFunc;
424 DdManager * ddNew = (DdManager *)pNtkNew->pManFunc;
425 DdNode * bCof, * bUniq, * bMint, * bTemp, * bFunc, * bBits[10], ** pbCodeVars;
426 Abc_Obj_t * pNodeNew = NULL, * pNodeBS[10];
427 int nLutSize = Abc_Base2Log( Vec_PtrSize(vCofs) );
428 int nBits = Abc_Base2Log( Vec_PtrSize(vUniq) );
429 int b, c, u, i;
430 assert( nBits + 2 <= nLutSize );
431 assert( nLutSize < Abc_ObjFaninNum(pNode) );
432 // start BDDs for the decompoosed blocks
433 for ( b = 0; b < nBits; b++ )
434 bBits[b] = Cudd_ReadLogicZero(ddNew), Cudd_Ref( bBits[b] );
435 // add each bound set minterm to one of the blccks
436 Vec_PtrForEachEntry( DdNode *, vCofs, bCof, c )
437 {
438 Vec_PtrForEachEntry( DdNode *, vUniq, bUniq, u )
439 if ( bUniq == bCof )
440 break;
441 assert( u < Vec_PtrSize(vUniq) );
442 for ( b = 0; b < nBits; b++ )
443 {
444 if ( ((u >> b) & 1) == 0 )
445 continue;
446 bMint = Extra_bddBitsToCube( ddNew, c, nLutSize, ddNew->vars, 1 ); Cudd_Ref( bMint );
447 bBits[b] = Cudd_bddOr( ddNew, bTemp = bBits[b], bMint ); Cudd_Ref( bBits[b] );
448 Cudd_RecursiveDeref( ddNew, bTemp );
449 Cudd_RecursiveDeref( ddNew, bMint );
450 }
451 }
452 // create bound set nodes
453 for ( b = 0; b < nBits; b++ )
454 {
455 pNodeBS[b] = Abc_NtkCreateNode( pNtkNew );
456 for ( i = 0; i < nLutSize; i++ )
457 Abc_ObjAddFanin( pNodeBS[b], Abc_ObjFanin(pNode, i)->pCopy );
458 pNodeBS[b]->pData = bBits[b]; // takes ref
459 }
460 // create composition node
461 pNodeNew = Abc_NtkCreateNode( pNtkNew );
462 // add free set variables first
463 for ( i = nLutSize; i < Abc_ObjFaninNum(pNode); i++ )
464 Abc_ObjAddFanin( pNodeNew, Abc_ObjFanin(pNode, i)->pCopy );
465 // add code bit variables next
466 for ( b = 0; b < nBits; b++ )
467 Abc_ObjAddFanin( pNodeNew, pNodeBS[b] );
468 // derive function of the composition node
469 bFunc = Cudd_ReadLogicZero(ddNew); Cudd_Ref( bFunc );
470 pbCodeVars = ddNew->vars + Abc_ObjFaninNum(pNode) - nLutSize;
471 Vec_PtrForEachEntry( DdNode *, vUniq, bUniq, u )
472 {
473 bUniq = Extra_bddMove( ddOld, bUniq, -nLutSize ); Cudd_Ref( bUniq );
474 bUniq = Extra_TransferLevelByLevel( ddOld, ddNew, bTemp = bUniq ); Cudd_Ref( bUniq );
475 Cudd_RecursiveDeref( ddOld, bTemp );
476
477 bMint = Extra_bddBitsToCube( ddNew, u, nBits, pbCodeVars, 0 ); Cudd_Ref( bMint );
478 bMint = Cudd_bddAnd( ddNew, bTemp = bMint, bUniq ); Cudd_Ref( bMint );
479 Cudd_RecursiveDeref( ddNew, bTemp );
480 Cudd_RecursiveDeref( ddNew, bUniq );
481
482 bFunc = Cudd_bddOr( ddNew, bTemp = bFunc, bMint ); Cudd_Ref( bFunc );
483 Cudd_RecursiveDeref( ddNew, bTemp );
484 Cudd_RecursiveDeref( ddNew, bMint );
485 }
486 pNodeNew->pData = bFunc; // takes ref
487 return pNodeNew;
488 }
489
490 /**Function*************************************************************
491
492 Synopsis [Tries to decompose using cofactoring into two LUTs.]
493
494 Description []
495
496 SideEffects []
497
498 SeeAlso []
499
500 ***********************************************************************/
Abc_NtkBddFindCofactor(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pNode,int nLutSize)501 Abc_Obj_t * Abc_NtkBddFindCofactor( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, int nLutSize )
502 {
503 Abc_Obj_t * pNodeBot, * pNodeTop;
504 DdManager * ddOld = (DdManager *)pNode->pNtk->pManFunc;
505 DdManager * ddNew = (DdManager *)pNtkNew->pManFunc;
506 DdNode * bCof0 = NULL, * bCof1 = NULL, * bSupp, * bTemp, * bVar;
507 DdNode * bCof0n, * bCof1n;
508 int i, iCof, iFreeVar, fCof1Smaller = -1;
509 assert( Abc_ObjFaninNum(pNode) == nLutSize + 1 );
510 for ( iCof = 0; iCof < Abc_ObjFaninNum(pNode); iCof++ )
511 {
512 bVar = Cudd_bddIthVar( ddOld, iCof );
513 bCof0 = Cudd_Cofactor( ddOld, (DdNode *)pNode->pData, Cudd_Not(bVar) ); Cudd_Ref( bCof0 );
514 bCof1 = Cudd_Cofactor( ddOld, (DdNode *)pNode->pData, bVar ); Cudd_Ref( bCof1 );
515 if ( Cudd_SupportSize( ddOld, bCof0 ) <= nLutSize - 2 )
516 {
517 fCof1Smaller = 0;
518 break;
519 }
520 if ( Cudd_SupportSize( ddOld, bCof1 ) <= nLutSize - 2 )
521 {
522 fCof1Smaller = 1;
523 break;
524 }
525 Cudd_RecursiveDeref( ddOld, bCof0 );
526 Cudd_RecursiveDeref( ddOld, bCof1 );
527 }
528 if ( iCof == Abc_ObjFaninNum(pNode) )
529 return NULL;
530 // find unused variable
531 bSupp = Cudd_Support( ddOld, fCof1Smaller? bCof1 : bCof0 ); Cudd_Ref( bSupp );
532 iFreeVar = -1;
533 for ( i = 0; i < Abc_ObjFaninNum(pNode); i++ )
534 {
535 assert( i == Cudd_ReadPerm(ddOld, i) );
536 if ( i == iCof )
537 continue;
538 for ( bTemp = bSupp; !Cudd_IsConstant(bTemp); bTemp = cuddT(bTemp) )
539 if ( i == (int)Cudd_NodeReadIndex(bTemp) )
540 break;
541 if ( Cudd_IsConstant(bTemp) )
542 {
543 iFreeVar = i;
544 break;
545 }
546 }
547 assert( iFreeVar != iCof && iFreeVar < Abc_ObjFaninNum(pNode) );
548 Cudd_RecursiveDeref( ddOld, bSupp );
549 // transfer the cofactors
550 bCof0n = Extra_TransferLevelByLevel( ddOld, ddNew, bCof0 ); Cudd_Ref( bCof0n );
551 bCof1n = Extra_TransferLevelByLevel( ddOld, ddNew, bCof1 ); Cudd_Ref( bCof1n );
552 Cudd_RecursiveDeref( ddOld, bCof0 );
553 Cudd_RecursiveDeref( ddOld, bCof1 );
554 // create bottom node
555 pNodeBot = Abc_NtkCreateNode( pNtkNew );
556 for ( i = 0; i < Abc_ObjFaninNum(pNode); i++ )
557 Abc_ObjAddFanin( pNodeBot, Abc_ObjFanin(pNode, i)->pCopy );
558 pNodeBot->pData = fCof1Smaller? bCof0n : bCof1n;
559 // create top node
560 pNodeTop = Abc_NtkCreateNode( pNtkNew );
561 for ( i = 0; i < Abc_ObjFaninNum(pNode); i++ )
562 if ( i == iFreeVar )
563 Abc_ObjAddFanin( pNodeTop, pNodeBot );
564 else
565 Abc_ObjAddFanin( pNodeTop, Abc_ObjFanin(pNode, i)->pCopy );
566 // derive the new function
567 pNodeTop->pData = Cudd_bddIte( ddNew,
568 Cudd_bddIthVar(ddNew, iCof),
569 fCof1Smaller? bCof1n : Cudd_bddIthVar(ddNew, iFreeVar),
570 fCof1Smaller? Cudd_bddIthVar(ddNew, iFreeVar) : bCof0n );
571 Cudd_Ref( (DdNode *)pNodeTop->pData );
572 Cudd_RecursiveDeref( ddNew, fCof1Smaller? bCof1n : bCof0n );
573 return pNodeTop;
574 }
575
576 /**Function*************************************************************
577
578 Synopsis [Decompose the function once.]
579
580 Description []
581
582 SideEffects []
583
584 SeeAlso []
585
586 ***********************************************************************/
Abc_NtkBddDecompose(Abc_Ntk_t * pNtkNew,Abc_Obj_t * pNode,int nLutSize,int fVerbose)587 Abc_Obj_t * Abc_NtkBddDecompose( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, int nLutSize, int fVerbose )
588 {
589 Vec_Ptr_t * vCofs, * vUniq;
590 DdManager * dd = (DdManager *)pNode->pNtk->pManFunc;
591 DdNode * bCof;
592 Abc_Obj_t * pNodeNew = NULL;
593 Abc_Obj_t * pCofs[20];
594 int i;
595 assert( Abc_ObjFaninNum(pNode) > nLutSize );
596 // try to decompose with two LUTs (the best case for Supp = LutSize + 1)
597 if ( Abc_ObjFaninNum(pNode) == nLutSize + 1 )
598 {
599
600 pNodeNew = Abc_NtkBddFindCofactor( pNtkNew, pNode, nLutSize );
601 if ( pNodeNew != NULL )
602 {
603 if ( fVerbose )
604 printf( "Decomposing %d-input node %d using MUX.\n",
605 Abc_ObjFaninNum(pNode), Abc_ObjId(pNode) );
606 return pNodeNew;
607 }
608
609 }
610 // cofactor w.r.t. the bound set variables
611 vCofs = Abc_NtkBddCofactors( dd, (DdNode *)pNode->pData, nLutSize );
612 vUniq = Vec_PtrDup( vCofs );
613 Vec_PtrUniqify( vUniq, (int (*)())Vec_PtrSortCompare );
614 // only perform decomposition with it is support reduring with two less vars
615 if( Vec_PtrSize(vUniq) > (1 << (nLutSize-2)) )
616 {
617 Vec_PtrFree( vCofs );
618 vCofs = Abc_NtkBddCofactors( dd, (DdNode *)pNode->pData, 2 );
619 if ( fVerbose )
620 printf( "Decomposing %d-input node %d using cofactoring with %d cofactors.\n",
621 Abc_ObjFaninNum(pNode), Abc_ObjId(pNode), Vec_PtrSize(vCofs) );
622 // implement the cofactors
623 pCofs[0] = Abc_ObjFanin(pNode, 0)->pCopy;
624 pCofs[1] = Abc_ObjFanin(pNode, 1)->pCopy;
625 Vec_PtrForEachEntry( DdNode *, vCofs, bCof, i )
626 pCofs[2+i] = Abc_NtkCreateCofLut( pNtkNew, dd, bCof, pNode, 2 );
627 if ( nLutSize == 4 )
628 pNodeNew = Abc_NtkBddMux412( pNtkNew, pCofs );
629 else if ( nLutSize == 5 )
630 pNodeNew = Abc_NtkBddMux412a( pNtkNew, pCofs );
631 else if ( nLutSize == 6 )
632 pNodeNew = Abc_NtkBddMux411( pNtkNew, pCofs );
633 else assert( 0 );
634 }
635 // alternative decompose using MUX-decomposition
636 else
637 {
638 if ( fVerbose )
639 printf( "Decomposing %d-input node %d using Curtis with %d unique columns.\n",
640 Abc_ObjFaninNum(pNode), Abc_ObjId(pNode), Vec_PtrSize(vUniq) );
641 pNodeNew = Abc_NtkBddCurtis( pNtkNew, pNode, vCofs, vUniq );
642 }
643 Vec_PtrFree( vCofs );
644 Vec_PtrFree( vUniq );
645 return pNodeNew;
646 }
647
648 /**Function*************************************************************
649
650 Synopsis []
651
652 Description []
653
654 SideEffects []
655
656 SeeAlso []
657
658 ***********************************************************************/
Abc_NtkLutminConstruct(Abc_Ntk_t * pNtkClp,Abc_Ntk_t * pNtkDec,int nLutSize,int fVerbose)659 void Abc_NtkLutminConstruct( Abc_Ntk_t * pNtkClp, Abc_Ntk_t * pNtkDec, int nLutSize, int fVerbose )
660 {
661 Vec_Ptr_t * vNodes;
662 Abc_Obj_t * pNode, * pFanin;
663 int i, k;
664 vNodes = Abc_NtkDfs( pNtkClp, 0 );
665 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
666 {
667 if ( Abc_ObjFaninNum(pNode) <= nLutSize )
668 {
669 pNode->pCopy = Abc_NtkDupObj( pNtkDec, pNode, 0 );
670 Abc_ObjForEachFanin( pNode, pFanin, k )
671 Abc_ObjAddFanin( pNode->pCopy, pFanin->pCopy );
672 }
673 else
674 pNode->pCopy = Abc_NtkBddDecompose( pNtkDec, pNode, nLutSize, fVerbose );
675 }
676 Vec_PtrFree( vNodes );
677 }
678
679 /**Function*************************************************************
680
681 Synopsis []
682
683 Description []
684
685 SideEffects []
686
687 SeeAlso []
688
689 ***********************************************************************/
Abc_NtkLutminInt(Abc_Ntk_t * pNtk,int nLutSize,int fVerbose)690 Abc_Ntk_t * Abc_NtkLutminInt( Abc_Ntk_t * pNtk, int nLutSize, int fVerbose )
691 {
692 extern void Abc_NtkBddReorder( Abc_Ntk_t * pNtk, int fVerbose );
693 Abc_Ntk_t * pNtkDec;
694 // minimize BDDs
695 // Abc_NtkBddReorder( pNtk, fVerbose );
696 Abc_NtkBddReorder( pNtk, 0 );
697 // decompose one output at a time
698 pNtkDec = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_BDD );
699 // make sure the new manager has enough inputs
700 Cudd_bddIthVar( (DdManager *)pNtkDec->pManFunc, Abc_NtkGetFaninMax(pNtk) );
701 // put the results into the new network (save new CO drivers in old CO drivers)
702 Abc_NtkLutminConstruct( pNtk, pNtkDec, nLutSize, fVerbose );
703 // finalize the new network
704 Abc_NtkFinalize( pNtk, pNtkDec );
705 // make the network minimum base
706 Abc_NtkMinimumBase( pNtkDec );
707 return pNtkDec;
708 }
709
710 /**Function*************************************************************
711
712 Synopsis [Performs minimum-LUT decomposition of the network.]
713
714 Description []
715
716 SideEffects []
717
718 SeeAlso []
719
720 ***********************************************************************/
Abc_NtkLutmin(Abc_Ntk_t * pNtkInit,int nLutSize,int fVerbose)721 Abc_Ntk_t * Abc_NtkLutmin( Abc_Ntk_t * pNtkInit, int nLutSize, int fVerbose )
722 {
723 extern int Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose );
724 Abc_Ntk_t * pNtkNew, * pTemp;
725 int i;
726 if ( nLutSize < 4 )
727 {
728 printf( "The LUT count (%d) should be at least 4.\n", nLutSize );
729 return NULL;
730 }
731 if ( nLutSize > 6 )
732 {
733 printf( "The LUT count (%d) should not exceed 6.\n", nLutSize );
734 return NULL;
735 }
736 // create internal representation
737 if ( Abc_NtkIsStrash(pNtkInit) )
738 pNtkNew = Abc_NtkDup( pNtkInit );
739 else
740 pNtkNew = Abc_NtkStrash( pNtkInit, 0, 1, 0 );
741 // collapse the network
742 pNtkNew = Abc_NtkCollapse( pTemp = pNtkNew, 10000, 0, 1, 0, 0 );
743 Abc_NtkDelete( pTemp );
744 if ( pNtkNew == NULL )
745 return NULL;
746 // convert it to BDD
747 if ( !Abc_NtkIsBddLogic(pNtkNew) )
748 Abc_NtkToBdd( pNtkNew );
749 // iterate decomposition
750 for ( i = 0; Abc_NtkGetFaninMax(pNtkNew) > nLutSize; i++ )
751 {
752 if ( fVerbose )
753 printf( "*** Iteration %d:\n", i+1 );
754 if ( fVerbose )
755 printf( "Decomposing network with %d nodes and %d max fanin count for K = %d.\n",
756 Abc_NtkNodeNum(pNtkNew), Abc_NtkGetFaninMax(pNtkNew), nLutSize );
757 pNtkNew = Abc_NtkLutminInt( pTemp = pNtkNew, nLutSize, fVerbose );
758 Abc_NtkDelete( pTemp );
759 }
760 // fix the problem with complemented and duplicated CO edges
761 Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );
762 // merge functionally equivalent nodes
763 Abc_NtkFraigSweep( pNtkNew, 1, 0, 0, 0 );
764 // make sure everything is okay
765 if ( !Abc_NtkCheck( pNtkNew ) )
766 {
767 printf( "Abc_NtkLutmin: The network check has failed.\n" );
768 return 0;
769 }
770 return pNtkNew;
771 }
772
773 #else
774
775 Abc_Ntk_t * Abc_NtkLutmin( Abc_Ntk_t * pNtkInit, int nLutSize, int fVerbose ) { return NULL; }
776
777 #endif
778
779 ////////////////////////////////////////////////////////////////////////
780 /// END OF FILE ///
781 ////////////////////////////////////////////////////////////////////////
782
783
784 ABC_NAMESPACE_IMPL_END
785
786