1 /**CFile****************************************************************
2
3 FileName [cutOracle.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [K-feasible cut computation package.]
8
9 Synopsis [Procedures to compute cuts for a node using the oracle.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: cutOracle.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "cutInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 struct Cut_OracleStruct_t_
31 {
32 // cut comptupatation parameters
33 Cut_Params_t * pParams;
34 Vec_Int_t * vFanCounts;
35 int fSimul;
36 // storage for cuts
37 Vec_Ptr_t * vCutsNew;
38 Vec_Ptr_t * vCuts0;
39 Vec_Ptr_t * vCuts1;
40 // oracle info
41 Vec_Int_t * vNodeCuts;
42 Vec_Int_t * vNodeStarts;
43 Vec_Int_t * vCutPairs;
44 // memory management
45 Extra_MmFixed_t * pMmCuts;
46 int EntrySize;
47 int nTruthWords;
48 // stats
49 abctime timeTotal;
50 int nCuts;
51 int nCutsTriv;
52 };
53
54 static Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p );
55 static Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node );
56 static Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 );
57
58 ////////////////////////////////////////////////////////////////////////
59 /// FUNCTION DEFINITIONS ///
60 ////////////////////////////////////////////////////////////////////////
61
62 /**Function*************************************************************
63
64 Synopsis [Starts the cut oracle.]
65
66 Description []
67
68 SideEffects []
69
70 SeeAlso []
71
72 ***********************************************************************/
Cut_OracleStart(Cut_Man_t * pMan)73 Cut_Oracle_t * Cut_OracleStart( Cut_Man_t * pMan )
74 {
75 Cut_Oracle_t * p;
76
77 assert( pMan->pParams->nVarsMax >= 3 && pMan->pParams->nVarsMax <= CUT_SIZE_MAX );
78 assert( pMan->pParams->fRecord );
79
80 p = ABC_ALLOC( Cut_Oracle_t, 1 );
81 memset( p, 0, sizeof(Cut_Oracle_t) );
82
83 // set and correct parameters
84 p->pParams = pMan->pParams;
85
86 // transfer the recording info
87 p->vNodeCuts = pMan->vNodeCuts; pMan->vNodeCuts = NULL;
88 p->vNodeStarts = pMan->vNodeStarts; pMan->vNodeStarts = NULL;
89 p->vCutPairs = pMan->vCutPairs; pMan->vCutPairs = NULL;
90
91 // prepare storage for cuts
92 p->vCutsNew = Vec_PtrAlloc( p->pParams->nIdsMax );
93 Vec_PtrFill( p->vCutsNew, p->pParams->nIdsMax, NULL );
94 p->vCuts0 = Vec_PtrAlloc( 100 );
95 p->vCuts1 = Vec_PtrAlloc( 100 );
96
97 // entry size
98 p->EntrySize = sizeof(Cut_Cut_t) + p->pParams->nVarsMax * sizeof(int);
99 if ( p->pParams->fTruth )
100 {
101 if ( p->pParams->nVarsMax > 8 )
102 {
103 p->pParams->fTruth = 0;
104 printf( "Skipping computation of truth table for more than 8 inputs.\n" );
105 }
106 else
107 {
108 p->nTruthWords = Cut_TruthWords( p->pParams->nVarsMax );
109 p->EntrySize += p->nTruthWords * sizeof(unsigned);
110 }
111 }
112 // memory for cuts
113 p->pMmCuts = Extra_MmFixedStart( p->EntrySize );
114 return p;
115 }
116 /**Function*************************************************************
117
118 Synopsis [Stop the cut oracle.]
119
120 Description []
121
122 SideEffects []
123
124 SeeAlso []
125
126 ***********************************************************************/
Cut_OracleStop(Cut_Oracle_t * p)127 void Cut_OracleStop( Cut_Oracle_t * p )
128 {
129 // if ( p->pParams->fVerbose )
130 {
131 printf( "Cut computation statistics with oracle:\n" );
132 printf( "Current cuts = %8d. (Trivial = %d.)\n", p->nCuts-p->nCutsTriv, p->nCutsTriv );
133 ABC_PRT( "Total time ", p->timeTotal );
134 }
135
136 if ( p->vCuts0 ) Vec_PtrFree( p->vCuts0 );
137 if ( p->vCuts1 ) Vec_PtrFree( p->vCuts1 );
138 if ( p->vCutsNew ) Vec_PtrFree( p->vCutsNew );
139 if ( p->vFanCounts ) Vec_IntFree( p->vFanCounts );
140
141 if ( p->vNodeCuts ) Vec_IntFree( p->vNodeCuts );
142 if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts );
143 if ( p->vCutPairs ) Vec_IntFree( p->vCutPairs );
144
145 Extra_MmFixedStop( p->pMmCuts );
146 ABC_FREE( p );
147 }
148
149 /**Function*************************************************************
150
151 Synopsis []
152
153 Description []
154
155 SideEffects []
156
157 SeeAlso []
158
159 ***********************************************************************/
Cut_OracleSetFanoutCounts(Cut_Oracle_t * p,Vec_Int_t * vFanCounts)160 void Cut_OracleSetFanoutCounts( Cut_Oracle_t * p, Vec_Int_t * vFanCounts )
161 {
162 p->vFanCounts = vFanCounts;
163 }
164
165 /**Function*************************************************************
166
167 Synopsis []
168
169 Description []
170
171 SideEffects []
172
173 SeeAlso []
174
175 ***********************************************************************/
Cut_OracleReadDrop(Cut_Oracle_t * p)176 int Cut_OracleReadDrop( Cut_Oracle_t * p )
177 {
178 return p->pParams->fDrop;
179 }
180
181 /**Function*************************************************************
182
183 Synopsis [Sets the trivial cut for the node.]
184
185 Description []
186
187 SideEffects []
188
189 SeeAlso []
190
191 ***********************************************************************/
Cut_OracleNodeSetTriv(Cut_Oracle_t * p,int Node)192 void Cut_OracleNodeSetTriv( Cut_Oracle_t * p, int Node )
193 {
194 assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
195 Vec_PtrWriteEntry( p->vCutsNew, Node, Cut_CutTriv(p, Node) );
196 }
197
198
199
200 /**Function*************************************************************
201
202 Synopsis [Allocates the cut.]
203
204 Description []
205
206 SideEffects []
207
208 SeeAlso []
209
210 ***********************************************************************/
Cut_CutStart(Cut_Oracle_t * p)211 Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p )
212 {
213 Cut_Cut_t * pCut;
214 // cut allocation
215 pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts );
216 memset( pCut, 0, sizeof(Cut_Cut_t) );
217 pCut->nVarsMax = p->pParams->nVarsMax;
218 pCut->fSimul = p->fSimul;
219 p->nCuts++;
220 return pCut;
221 }
222
223 /**Function*************************************************************
224
225 Synopsis [Creates the trivial cut.]
226
227 Description []
228
229 SideEffects []
230
231 SeeAlso []
232
233 ***********************************************************************/
Cut_CutTriv(Cut_Oracle_t * p,int Node)234 Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node )
235 {
236 Cut_Cut_t * pCut;
237 pCut = Cut_CutStart( p );
238 pCut->nLeaves = 1;
239 pCut->pLeaves[0] = Node;
240 if ( p->pParams->fTruth )
241 {
242 unsigned * pTruth = Cut_CutReadTruth(pCut);
243 int i;
244 for ( i = 0; i < p->nTruthWords; i++ )
245 pTruth[i] = 0xAAAAAAAA;
246 }
247 p->nCutsTriv++;
248 return pCut;
249 }
250
251 /**Function*************************************************************
252
253 Synopsis [Merges two cuts.]
254
255 Description []
256
257 SideEffects []
258
259 SeeAlso []
260
261 ***********************************************************************/
Cut_CutMerge(Cut_Oracle_t * p,Cut_Cut_t * pCut0,Cut_Cut_t * pCut1)262 Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
263 {
264 Cut_Cut_t * pCut;
265 int Limit, i, k, c;
266 // create the leaves of the new cut
267 pCut = Cut_CutStart( p );
268 Limit = p->pParams->nVarsMax;
269 for ( i = k = c = 0; c < Limit; c++ )
270 {
271 if ( k == (int)pCut1->nLeaves )
272 {
273 if ( i == (int)pCut0->nLeaves )
274 {
275 pCut->nLeaves = c;
276 return pCut;
277 }
278 pCut->pLeaves[c] = pCut0->pLeaves[i++];
279 continue;
280 }
281 if ( i == (int)pCut0->nLeaves )
282 {
283 if ( k == (int)pCut1->nLeaves )
284 {
285 pCut->nLeaves = c;
286 return pCut;
287 }
288 pCut->pLeaves[c] = pCut1->pLeaves[k++];
289 continue;
290 }
291 if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
292 {
293 pCut->pLeaves[c] = pCut0->pLeaves[i++];
294 continue;
295 }
296 if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
297 {
298 pCut->pLeaves[c] = pCut1->pLeaves[k++];
299 continue;
300 }
301 pCut->pLeaves[c] = pCut0->pLeaves[i++];
302 k++;
303 }
304 assert( i == (int)pCut0->nLeaves && k == (int)pCut1->nLeaves );
305 pCut->nLeaves = c;
306 return pCut;
307 }
308
309 /**Function*************************************************************
310
311 Synopsis [Reconstruct the cuts of the node.]
312
313 Description []
314
315 SideEffects []
316
317 SeeAlso []
318
319 ***********************************************************************/
Cut_OracleComputeCuts(Cut_Oracle_t * p,int Node,int Node0,int Node1,int fCompl0,int fCompl1)320 Cut_Cut_t * Cut_OracleComputeCuts( Cut_Oracle_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 )
321 {
322 Cut_Cut_t * pList = NULL, ** ppTail = &pList;
323 Cut_Cut_t * pCut, * pCut0, * pCut1, * pList0, * pList1;
324 int iCutStart, nCuts, i, Entry;
325 abctime clk = Abc_Clock();
326
327 // get the cuts of the children
328 pList0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 );
329 pList1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 );
330 assert( pList0 && pList1 );
331
332 // get the complemented attribute of the cut
333 p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);
334
335 // collect the cuts
336 Vec_PtrClear( p->vCuts0 );
337 Cut_ListForEachCut( pList0, pCut )
338 Vec_PtrPush( p->vCuts0, pCut );
339 Vec_PtrClear( p->vCuts1 );
340 Cut_ListForEachCut( pList1, pCut )
341 Vec_PtrPush( p->vCuts1, pCut );
342
343 // get the first and last cuts of this node
344 nCuts = Vec_IntEntry(p->vNodeCuts, Node);
345 iCutStart = Vec_IntEntry(p->vNodeStarts, Node);
346
347 // create trivial cut
348 assert( Vec_IntEntry(p->vCutPairs, iCutStart) == 0 );
349 pCut = Cut_CutTriv( p, Node );
350 *ppTail = pCut;
351 ppTail = &pCut->pNext;
352 // create other cuts
353 for ( i = 1; i < nCuts; i++ )
354 {
355 Entry = Vec_IntEntry( p->vCutPairs, iCutStart + i );
356 pCut0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts0, Entry & 0xFFFF );
357 pCut1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts1, Entry >> 16 );
358 pCut = Cut_CutMerge( p, pCut0, pCut1 );
359 *ppTail = pCut;
360 ppTail = &pCut->pNext;
361 // compute the truth table
362 if ( p->pParams->fTruth )
363 Cut_TruthComputeOld( pCut, pCut0, pCut1, fCompl0, fCompl1 );
364 }
365 *ppTail = NULL;
366
367 // write the new cut
368 assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
369 Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
370 p->timeTotal += Abc_Clock() - clk;
371 return pList;
372 }
373
374 /**Function*************************************************************
375
376 Synopsis [Deallocates the cuts at the node.]
377
378 Description []
379
380 SideEffects []
381
382 SeeAlso []
383
384 ***********************************************************************/
Cut_OracleFreeCuts(Cut_Oracle_t * p,int Node)385 void Cut_OracleFreeCuts( Cut_Oracle_t * p, int Node )
386 {
387 Cut_Cut_t * pList, * pCut, * pCut2;
388 pList = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node );
389 if ( pList == NULL )
390 return;
391 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
392 Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut );
393 Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
394 }
395
396 /**Function*************************************************************
397
398 Synopsis [Consider dropping cuts if they are useless by now.]
399
400 Description []
401
402 SideEffects []
403
404 SeeAlso []
405
406 ***********************************************************************/
Cut_OracleTryDroppingCuts(Cut_Oracle_t * p,int Node)407 void Cut_OracleTryDroppingCuts( Cut_Oracle_t * p, int Node )
408 {
409 int nFanouts;
410 assert( p->vFanCounts );
411 nFanouts = Vec_IntEntry( p->vFanCounts, Node );
412 assert( nFanouts > 0 );
413 if ( --nFanouts == 0 )
414 Cut_OracleFreeCuts( p, Node );
415 Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts );
416 }
417
418 ////////////////////////////////////////////////////////////////////////
419 /// END OF FILE ///
420 ////////////////////////////////////////////////////////////////////////
421
422
423 ABC_NAMESPACE_IMPL_END
424
425