1 /**CFile****************************************************************
2
3 FileName [darCore.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [DAG-aware AIG rewriting.]
8
9 Synopsis [Core of the rewriting package.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: darCore.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "darInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // iterator over the nodes in the topological order
31 #define Aig_ManForEachNodeInOrder( p, pObj ) \
32 for ( assert(p->pOrderData), p->iPrev = 0, p->iNext = p->pOrderData[1]; \
33 p->iNext && (((pObj) = Aig_ManObj(p, p->iNext)), 1); \
34 p->iNext = p->pOrderData[2*p->iPrev+1] )
35
36 ////////////////////////////////////////////////////////////////////////
37 /// FUNCTION DEFINITIONS ///
38 ////////////////////////////////////////////////////////////////////////
39
40 /**Function*************************************************************
41
42 Synopsis [Returns the structure with default assignment of parameters.]
43
44 Description []
45
46 SideEffects []
47
48 SeeAlso []
49
50 ***********************************************************************/
Dar_ManDefaultRwrParams(Dar_RwrPar_t * pPars)51 void Dar_ManDefaultRwrParams( Dar_RwrPar_t * pPars )
52 {
53 memset( pPars, 0, sizeof(Dar_RwrPar_t) );
54 pPars->nCutsMax = 8; // 8
55 pPars->nSubgMax = 5; // 5 is a "magic number"
56 pPars->fFanout = 1;
57 pPars->fUpdateLevel = 0;
58 pPars->fUseZeros = 0;
59 pPars->fPower = 0;
60 pPars->fRecycle = 1;
61 pPars->fVerbose = 0;
62 pPars->fVeryVerbose = 0;
63 }
64
65 #define MAX_VAL 10
66
67 /**Function*************************************************************
68
69 Synopsis []
70
71 Description []
72
73 SideEffects []
74
75 SeeAlso []
76
77 ***********************************************************************/
Dar_ManRewrite(Aig_Man_t * pAig,Dar_RwrPar_t * pPars)78 int Dar_ManRewrite( Aig_Man_t * pAig, Dar_RwrPar_t * pPars )
79 {
80 extern Vec_Int_t * Saig_ManComputeSwitchProbs( Aig_Man_t * p, int nFrames, int nPref, int fProbOne );
81 Dar_Man_t * p;
82 // Bar_Progress_t * pProgress;
83 Dar_Cut_t * pCut;
84 Aig_Obj_t * pObj, * pObjNew;
85 int i, k, nNodesOld, nNodeBefore, nNodeAfter, Required;
86 abctime clk = 0, clkStart;
87 int Counter = 0;
88 int nMffcSize;//, nMffcGains[MAX_VAL+1][MAX_VAL+1] = {{0}};
89 // prepare the library
90 Dar_LibPrepare( pPars->nSubgMax );
91 // create rewriting manager
92 p = Dar_ManStart( pAig, pPars );
93 if ( pPars->fPower )
94 pAig->vProbs = Saig_ManComputeSwitchProbs( pAig, 48, 16, 1 );
95 // remove dangling nodes
96 Aig_ManCleanup( pAig );
97 // if updating levels is requested, start fanout and timing
98 if ( p->pPars->fFanout )
99 Aig_ManFanoutStart( pAig );
100 if ( p->pPars->fUpdateLevel )
101 Aig_ManStartReverseLevels( pAig, 0 );
102 // set elementary cuts for the PIs
103 // Dar_ManCutsStart( p );
104 // resynthesize each node once
105 clkStart = Abc_Clock();
106 p->nNodesInit = Aig_ManNodeNum(pAig);
107 nNodesOld = Vec_PtrSize( pAig->vObjs );
108
109 // pProgress = Bar_ProgressStart( stdout, nNodesOld );
110 Aig_ManForEachObj( pAig, pObj, i )
111 // pProgress = Bar_ProgressStart( stdout, 100 );
112 // Aig_ManOrderStart( pAig );
113 // Aig_ManForEachNodeInOrder( pAig, pObj )
114 {
115 if ( pAig->Time2Quit && !(i & 256) && Abc_Clock() > pAig->Time2Quit )
116 break;
117 // Bar_ProgressUpdate( pProgress, 100*pAig->nAndPrev/pAig->nAndTotal, NULL );
118 // Bar_ProgressUpdate( pProgress, i, NULL );
119 if ( !Aig_ObjIsNode(pObj) )
120 continue;
121 if ( i > nNodesOld )
122 // if ( p->pPars->fUseZeros && i > nNodesOld )
123 break;
124 if ( pPars->fRecycle && ++Counter % 50000 == 0 && Aig_DagSize(pObj) < Vec_PtrSize(p->vCutNodes)/100 )
125 {
126 // printf( "Counter = %7d. Node = %7d. Dag = %5d. Vec = %5d.\n",
127 // Counter, i, Aig_DagSize(pObj), Vec_PtrSize(p->vCutNodes) );
128 // fflush( stdout );
129 Dar_ManCutsRestart( p, pObj );
130 }
131
132 // consider freeing the cuts
133 // if ( (i & 0xFFF) == 0 && Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) > 100 )
134 // Dar_ManCutsStart( p );
135
136 // compute cuts for the node
137 p->nNodesTried++;
138 clk = Abc_Clock();
139 Dar_ObjSetCuts( pObj, NULL );
140 Dar_ObjComputeCuts_rec( p, pObj );
141 p->timeCuts += Abc_Clock() - clk;
142
143 // check if there is a trivial cut
144 Dar_ObjForEachCut( pObj, pCut, k )
145 if ( pCut->nLeaves == 0 || (pCut->nLeaves == 1 && pCut->pLeaves[0] != pObj->Id && Aig_ManObj(p->pAig, pCut->pLeaves[0])) )
146 break;
147 if ( k < (int)pObj->nCuts )
148 {
149 assert( pCut->nLeaves < 2 );
150 if ( pCut->nLeaves == 0 ) // replace by constant
151 {
152 assert( pCut->uTruth == 0 || pCut->uTruth == 0xFFFF );
153 pObjNew = Aig_NotCond( Aig_ManConst1(p->pAig), pCut->uTruth==0 );
154 }
155 else
156 {
157 assert( pCut->uTruth == 0xAAAA || pCut->uTruth == 0x5555 );
158 pObjNew = Aig_NotCond( Aig_ManObj(p->pAig, pCut->pLeaves[0]), pCut->uTruth==0x5555 );
159 }
160 // remove the old cuts
161 Dar_ObjSetCuts( pObj, NULL );
162 // replace the node
163 Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
164 continue;
165 }
166
167 // evaluate the cuts
168 p->GainBest = -1;
169 nMffcSize = -1;
170 Required = pAig->vLevelR? Aig_ObjRequiredLevel(pAig, pObj) : ABC_INFINITY;
171 Dar_ObjForEachCut( pObj, pCut, k )
172 {
173 int nLeavesOld = pCut->nLeaves;
174 if ( pCut->nLeaves == 3 )
175 pCut->pLeaves[pCut->nLeaves++] = 0;
176 Dar_LibEval( p, pObj, pCut, Required, &nMffcSize );
177 pCut->nLeaves = nLeavesOld;
178 }
179 // check the best gain
180 if ( !(p->GainBest > 0 || (p->GainBest == 0 && p->pPars->fUseZeros)) )
181 {
182 // Aig_ObjOrderAdvance( pAig );
183 continue;
184 }
185 // nMffcGains[p->GainBest < MAX_VAL ? p->GainBest : MAX_VAL][nMffcSize < MAX_VAL ? nMffcSize : MAX_VAL]++;
186 // remove the old cuts
187 Dar_ObjSetCuts( pObj, NULL );
188 // if we end up here, a rewriting step is accepted
189 nNodeBefore = Aig_ManNodeNum( pAig );
190 pObjNew = Dar_LibBuildBest( p ); // pObjNew can be complemented!
191 pObjNew = Aig_NotCond( pObjNew, Aig_ObjPhaseReal(pObjNew) ^ pObj->fPhase );
192 assert( (int)Aig_Regular(pObjNew)->Level <= Required );
193 // replace the node
194 Aig_ObjReplace( pAig, pObj, pObjNew, p->pPars->fUpdateLevel );
195 // compare the gains
196 nNodeAfter = Aig_ManNodeNum( pAig );
197 assert( p->GainBest <= nNodeBefore - nNodeAfter );
198 // count gains of this class
199 p->ClassGains[p->ClassBest] += nNodeBefore - nNodeAfter;
200 }
201 // Aig_ManOrderStop( pAig );
202 /*
203 printf( "Distribution of gain (row) by MFFC size (column) %s 0-costs:\n", p->pPars->fUseZeros? "with":"without" );
204 for ( k = 0; k <= MAX_VAL; k++ )
205 printf( "<%4d> ", k );
206 printf( "\n" );
207 for ( i = 0; i <= MAX_VAL; i++ )
208 {
209 for ( k = 0; k <= MAX_VAL; k++ )
210 printf( "%6d ", nMffcGains[i][k] );
211 printf( "\n" );
212 }
213 */
214
215 p->timeTotal = Abc_Clock() - clkStart;
216 p->timeOther = p->timeTotal - p->timeCuts - p->timeEval;
217
218 // Bar_ProgressStop( pProgress );
219 Dar_ManCutsFree( p );
220 // put the nodes into the DFS order and reassign their IDs
221 // Aig_NtkReassignIds( p );
222 // fix the levels
223 // Aig_ManVerifyLevel( pAig );
224 if ( p->pPars->fFanout )
225 Aig_ManFanoutStop( pAig );
226 if ( p->pPars->fUpdateLevel )
227 {
228 // Aig_ManVerifyReverseLevel( pAig );
229 Aig_ManStopReverseLevels( pAig );
230 }
231 if ( pAig->vProbs )
232 {
233 Vec_IntFree( pAig->vProbs );
234 pAig->vProbs = NULL;
235 }
236 // stop the rewriting manager
237 Dar_ManStop( p );
238 Aig_ManCheckPhase( pAig );
239 // check
240 if ( !Aig_ManCheck( pAig ) )
241 {
242 printf( "Aig_ManRewrite: The network check has failed.\n" );
243 return 0;
244 }
245 return 1;
246 }
247
248 /**Function*************************************************************
249
250 Synopsis [Computes the total number of cuts.]
251
252 Description []
253
254 SideEffects []
255
256 SeeAlso []
257
258 ***********************************************************************/
Dar_ManCutCount(Aig_Man_t * pAig,int * pnCutsK)259 int Dar_ManCutCount( Aig_Man_t * pAig, int * pnCutsK )
260 {
261 Dar_Cut_t * pCut;
262 Aig_Obj_t * pObj;
263 int i, k, nCuts = 0, nCutsK = 0;
264 Aig_ManForEachNode( pAig, pObj, i )
265 Dar_ObjForEachCut( pObj, pCut, k )
266 {
267 nCuts++;
268 if ( pCut->nLeaves == 4 )
269 nCutsK++;
270 }
271 if ( pnCutsK )
272 *pnCutsK = nCutsK;
273 return nCuts;
274 }
275
276 /**Function*************************************************************
277
278 Synopsis []
279
280 Description []
281
282 SideEffects []
283
284 SeeAlso []
285
286 ***********************************************************************/
Dar_ManComputeCuts(Aig_Man_t * pAig,int nCutsMax,int fSkipTtMin,int fVerbose)287 Aig_MmFixed_t * Dar_ManComputeCuts( Aig_Man_t * pAig, int nCutsMax, int fSkipTtMin, int fVerbose )
288 {
289 Dar_Man_t * p;
290 Dar_RwrPar_t Pars, * pPars = &Pars;
291 Aig_Obj_t * pObj;
292 Aig_MmFixed_t * pMemCuts;
293 int i, nNodes;
294 abctime clk = Abc_Clock();
295 // remove dangling nodes
296 if ( (nNodes = Aig_ManCleanup( pAig )) )
297 {
298 // printf( "Removing %d nodes.\n", nNodes );
299 }
300 // create default parameters
301 Dar_ManDefaultRwrParams( pPars );
302 pPars->nCutsMax = nCutsMax;
303 // create rewriting manager
304 p = Dar_ManStart( pAig, pPars );
305 // set elementary cuts for the PIs
306 // Dar_ManCutsStart( p );
307 Aig_MmFixedRestart( p->pMemCuts );
308 Dar_ObjPrepareCuts( p, Aig_ManConst1(p->pAig) );
309 Aig_ManForEachCi( pAig, pObj, i )
310 Dar_ObjPrepareCuts( p, pObj );
311 // compute cuts for each nodes in the topological order
312 Aig_ManForEachNode( pAig, pObj, i )
313 Dar_ObjComputeCuts( p, pObj, fSkipTtMin );
314 // print verbose stats
315 if ( fVerbose )
316 {
317 // Aig_Obj_t * pObj;
318 int nCuts, nCutsK;//, i;
319 nCuts = Dar_ManCutCount( pAig, &nCutsK );
320 printf( "Nodes = %6d. Total cuts = %6d. 4-input cuts = %6d.\n",
321 Aig_ManObjNum(pAig), nCuts, nCutsK );
322 printf( "Cut size = %2d. Truth size = %2d. Total mem = %5.2f MB ",
323 (int)sizeof(Dar_Cut_t), (int)4, 1.0*Aig_MmFixedReadMemUsage(p->pMemCuts)/(1<<20) );
324 ABC_PRT( "Runtime", Abc_Clock() - clk );
325 /*
326 Aig_ManForEachNode( pAig, pObj, i )
327 if ( i % 300 == 0 )
328 Dar_ObjCutPrint( pAig, pObj );
329 */
330 }
331 // free the cuts
332 pMemCuts = p->pMemCuts;
333 p->pMemCuts = NULL;
334 // Dar_ManCutsFree( p );
335 // stop the rewriting manager
336 Dar_ManStop( p );
337 return pMemCuts;
338 }
339
340
341
342 ////////////////////////////////////////////////////////////////////////
343 /// END OF FILE ///
344 ////////////////////////////////////////////////////////////////////////
345
346
347 ABC_NAMESPACE_IMPL_END
348
349