1 /**CFile****************************************************************
2
3 FileName [giaBidec.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Application of bi-decomposition to AIG minimization.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaBidec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22 #include "bool/bdc/bdc.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Computes truth table of the cut.]
38
39 Description []
40
41 SideEffects []
42
43 SeeAlso []
44
45 ***********************************************************************/
Gia_ManConvertAigToTruth_rec(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Int_t * vTruth,int nWords,Vec_Int_t * vVisited)46 unsigned * Gia_ManConvertAigToTruth_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vTruth, int nWords, Vec_Int_t * vVisited )
47 {
48 unsigned * pTruth, * pTruth0, * pTruth1;
49 int i;
50 assert( !Gia_IsComplement(pObj) );
51 if ( Vec_IntGetEntry(p->vTruths, Gia_ObjId(p, pObj)) != -1 )
52 return (unsigned *)Vec_IntEntryP( vTruth, nWords * Vec_IntGetEntry(p->vTruths, Gia_ObjId(p, pObj)) );
53 // compute the truth tables of the fanins
54 pTruth0 = Gia_ManConvertAigToTruth_rec( p, Gia_ObjFanin0(pObj), vTruth, nWords, vVisited );
55 pTruth1 = Gia_ManConvertAigToTruth_rec( p, Gia_ObjFanin1(pObj), vTruth, nWords, vVisited );
56 // get room for the truth table
57 pTruth = Vec_IntFetch( vTruth, nWords );
58 // create the truth table of the node
59 if ( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
60 for ( i = 0; i < nWords; i++ )
61 pTruth[i] = pTruth0[i] & pTruth1[i];
62 else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
63 for ( i = 0; i < nWords; i++ )
64 pTruth[i] = pTruth0[i] & ~pTruth1[i];
65 else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
66 for ( i = 0; i < nWords; i++ )
67 pTruth[i] = ~pTruth0[i] & pTruth1[i];
68 else // if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
69 for ( i = 0; i < nWords; i++ )
70 pTruth[i] = ~pTruth0[i] & ~pTruth1[i];
71 // save the visited node
72 Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), Vec_IntSize(vVisited) );
73 Vec_IntPush( vVisited, Gia_ObjId(p, pObj) );
74 return pTruth;
75 }
76
77 /**Function*************************************************************
78
79 Synopsis [Computes truth table of the node.]
80
81 Description [Assumes that the structural support is no more than 8 inputs.
82 Uses array vTruth to store temporary truth tables. The returned pointer should
83 be used immediately.]
84
85 SideEffects []
86
87 SeeAlso []
88
89 ***********************************************************************/
Gia_ManConvertAigToTruth(Gia_Man_t * p,Gia_Obj_t * pRoot,Vec_Int_t * vLeaves,Vec_Int_t * vTruth,Vec_Int_t * vVisited)90 unsigned * Gia_ManConvertAigToTruth( Gia_Man_t * p, Gia_Obj_t * pRoot, Vec_Int_t * vLeaves, Vec_Int_t * vTruth, Vec_Int_t * vVisited )
91 {
92 static unsigned uTruths[8][8] = { // elementary truth tables
93 { 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
94 { 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
95 { 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
96 { 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
97 { 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 },
98 { 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF },
99 { 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF },
100 { 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF }
101 };
102 Gia_Obj_t * pObj;
103 Vec_Ptr_t * vTtElems = NULL;
104 unsigned * pTruth;//, * pTruth2;
105 int i, nWords, nVars;
106 // get the number of variables and words
107 nVars = Vec_IntSize( vLeaves );
108 nWords = Abc_TruthWordNum( nVars );
109 // check the case of a constant
110 if ( Gia_ObjIsConst0( Gia_Regular(pRoot) ) )
111 {
112 Vec_IntClear( vTruth );
113 // get room for the truth table
114 pTruth = Vec_IntFetch( vTruth, nWords );
115 if ( !Gia_IsComplement(pRoot) )
116 Gia_ManTruthClear( pTruth, nVars );
117 else
118 Gia_ManTruthFill( pTruth, nVars );
119 return pTruth;
120 }
121 // if the number of variables is more than 8, allocate truth tables
122 if ( nVars > 8 )
123 vTtElems = Vec_PtrAllocTruthTables( nVars );
124 // assign elementary truth tables
125 Vec_IntClear( vTruth );
126 Vec_IntClear( vVisited );
127 Gia_ManForEachObjVec( vLeaves, p, pObj, i )
128 {
129 // get room for the truth table
130 pTruth = Vec_IntFetch( vTruth, nWords );
131 // assign elementary variable
132 if ( vTtElems )
133 Gia_ManTruthCopy( pTruth, (unsigned *)Vec_PtrEntry(vTtElems, i), nVars );
134 else
135 Gia_ManTruthCopy( pTruth, uTruths[i], nVars );
136 // save the visited node
137 Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), Vec_IntSize(vVisited) );
138 Vec_IntPush( vVisited, Gia_ObjId(p, pObj) );
139 }
140 if ( vTtElems )
141 Vec_PtrFree( vTtElems );
142 // clear the marks and compute the truth table
143 // pTruth2 = Gia_ManConvertAigToTruth_rec( p, Gia_Regular(pRoot), vTruth, nWords, vVisited );
144 pTruth = Gia_ManConvertAigToTruth_rec( p, Gia_Regular(pRoot), vTruth, nWords, vVisited );
145 // copy the result
146 // Gia_ManTruthCopy( pTruth, pTruth2, nVars );
147 if ( Gia_IsComplement(pRoot) )
148 Gia_ManTruthNot( pTruth, pTruth, nVars );
149 // clean truth tables
150 Gia_ManForEachObjVec( vVisited, p, pObj, i )
151 Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), -1 );
152 return pTruth;
153 }
154
155 /**Function*************************************************************
156
157 Synopsis [Resynthesizes nodes using bi-decomposition.]
158
159 Description []
160
161 SideEffects []
162
163 SeeAlso []
164
165 ***********************************************************************/
Gia_ObjPerformBidec(Bdc_Man_t * pManDec,Gia_Man_t * pNew,Gia_Man_t * p,Gia_Obj_t * pRoot,Vec_Int_t * vLeaves,Vec_Int_t * vTruth,Vec_Int_t * vVisited)166 int Gia_ObjPerformBidec( Bdc_Man_t * pManDec,
167 Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pRoot,
168 Vec_Int_t * vLeaves, Vec_Int_t * vTruth, Vec_Int_t * vVisited )
169 {
170 unsigned * pTruth;
171 Bdc_Fun_t * pFunc;
172 Gia_Obj_t * pFanin;
173 int i, iFan, nVars, nNodes;
174 // collect leaves of this gate
175 Vec_IntClear( vLeaves );
176 Gia_LutForEachFanin( p, Gia_ObjId(p, pRoot), iFan, i )
177 Vec_IntPush( vLeaves, iFan );
178 nVars = Vec_IntSize( vLeaves );
179 assert( nVars < 16 );
180 // derive truth table
181 pTruth = Gia_ManConvertAigToTruth( p, pRoot, vLeaves, vTruth, vVisited );
182 //Extra_PrintBinary( stdout, pTruth, (1<<nVars) ); printf( "\n" );
183 if ( Gia_ManTruthIsConst0(pTruth, nVars) )
184 {
185 //printf( "Node %d is const0\n", Gia_ObjId(p, pRoot) );
186 return 0;
187 }
188 if ( Gia_ManTruthIsConst1(pTruth, nVars) )
189 {
190 //printf( "Node %d is const1\n", Gia_ObjId(p, pRoot) );
191 return 1;
192 }
193 // decompose truth table
194 Bdc_ManDecompose( pManDec, pTruth, NULL, nVars, NULL, 1000 );
195 /*
196 if ( Bdc_ManNodeNum(pManDec) == 0 )
197 printf( "Node %d has 0 bidec nodes\n", Gia_ObjId(p, pRoot) );
198 if ( Kit_TruthSupportSize(pTruth, nVars) != nVars )
199 {
200 printf( "Node %d has %d fanins and %d supp size\n", Gia_ObjId(p, pRoot), nVars, Kit_TruthSupportSize(pTruth, nVars) );
201 Gia_LutForEachFanin( p, Gia_ObjId(p, pRoot), iFan, i )
202 {
203 printf( "%d ", Kit_TruthVarInSupport(pTruth, nVars, i) );
204 Gia_ObjPrint( p, Gia_ManObj(p, iFan) );
205 }
206 // Gia_ManPrintStats( p, 0 );
207 }
208 */
209 // convert back into HOP
210 Bdc_FuncSetCopy( Bdc_ManFunc( pManDec, 0 ), Gia_ManConst1(pNew) );
211 Gia_ManForEachObjVec( vLeaves, p, pFanin, i )
212 Bdc_FuncSetCopyInt( Bdc_ManFunc( pManDec, i+1 ), Gia_ObjValue(pFanin) );
213 nNodes = Bdc_ManNodeNum( pManDec );
214 for ( i = nVars + 1; i < nNodes; i++ )
215 {
216 pFunc = Bdc_ManFunc( pManDec, i );
217 Bdc_FuncSetCopyInt( pFunc, Gia_ManHashAnd( pNew, Bdc_FunFanin0Copy(pFunc), Bdc_FunFanin1Copy(pFunc) ) );
218 }
219 return Bdc_FunObjCopy( Bdc_ManRoot(pManDec) );
220 }
221
222 /**Function*************************************************************
223
224 Synopsis []
225
226 Description []
227
228 SideEffects []
229
230 SeeAlso []
231
232 ***********************************************************************/
Gia_ManPerformBidec(Gia_Man_t * p,int fVerbose)233 Gia_Man_t * Gia_ManPerformBidec( Gia_Man_t * p, int fVerbose )
234 {
235 Bdc_Man_t * pManDec;
236 Bdc_Par_t Pars = {0}, * pPars = &Pars;
237 Vec_Int_t * vLeaves, * vTruth, * vVisited;
238 Gia_Man_t * pNew, * pTemp;
239 Gia_Obj_t * pObj;
240 int i;//, clk = Abc_Clock();
241 pPars->nVarsMax = Gia_ManLutSizeMax( p );
242 pPars->fVerbose = fVerbose;
243 if ( pPars->nVarsMax < 2 )
244 {
245 printf( "Resynthesis is not performed when nodes have less than 2 inputs.\n" );
246 return NULL;
247 }
248 if ( pPars->nVarsMax > 15 )
249 {
250 printf( "Resynthesis is not performed when nodes have more than 15 inputs.\n" );
251 return NULL;
252 }
253 vLeaves = Vec_IntAlloc( 0 );
254 vTruth = Vec_IntAlloc( (1<<16) );
255 vVisited = Vec_IntAlloc( 0 );
256 // clean the old manager
257 Gia_ManCleanTruth( p );
258 Gia_ManFillValue( p );
259 Gia_ManConst0(p)->Value = 0;
260 // start the new manager
261 pNew = Gia_ManStart( Gia_ManObjNum(p) );
262 pNew->pName = Abc_UtilStrsav( p->pName );
263 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
264 Gia_ManHashAlloc( pNew );
265 // Gia_ManCleanLevels( pNew, Gia_ManObjNum(p) );
266 pManDec = Bdc_ManAlloc( pPars );
267 Gia_ManForEachObj1( p, pObj, i )
268 {
269 if ( Gia_ObjIsCi(pObj) ) // transfer the CI level (is it needed?)
270 pObj->Value = Gia_ManAppendCi( pNew );
271 else if ( Gia_ObjIsCo(pObj) )
272 pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
273 else if ( Gia_ObjIsLut(p, i) )
274 pObj->Value = Gia_ObjPerformBidec( pManDec, pNew, p, pObj, vLeaves, vTruth, vVisited );
275 }
276 Bdc_ManFree( pManDec );
277 // cleanup the AIG
278 Gia_ManHashStop( pNew );
279 // check the presence of dangling nodes
280 if ( Gia_ManHasDangling(pNew) )
281 {
282 pNew = Gia_ManCleanup( pTemp = pNew );
283 if ( Gia_ManAndNum(pNew) != Gia_ManAndNum(pTemp) )
284 printf( "Gia_ManPerformBidec() node count before and after: %6d and %6d.\n", Gia_ManAndNum(pNew), Gia_ManAndNum(pTemp) );
285 Gia_ManStop( pTemp );
286 }
287 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
288 Vec_IntFree( vLeaves );
289 Vec_IntFree( vTruth );
290 Vec_IntFree( vVisited );
291 if ( fVerbose )
292 {
293 // printf( "Total gain in AIG nodes = %d. ", Gia_ManObjNum(p)-Gia_ManObjNum(pNew) );
294 // ABC_PRT( "Total runtime", Abc_Clock() - clk );
295 }
296 return pNew;
297 }
298
299 ////////////////////////////////////////////////////////////////////////
300 /// END OF FILE ///
301 ////////////////////////////////////////////////////////////////////////
302
303
304 ABC_NAMESPACE_IMPL_END
305
306