1 /**CFile****************************************************************
2
3 FileName [sbdCut2.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [SAT-based optimization using internal don't-cares.]
8
9 Synopsis [Cut computation.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: sbdCut2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "sbdInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 #define SBD_MAX_CUTSIZE 10
31 #define SBD_MAX_CUTNUM 501
32
33 #define SBD_CUT_NO_LEAF 0xF
34
35 typedef struct Sbd_Cut_t_ Sbd_Cut_t;
36 struct Sbd_Cut_t_
37 {
38 word Sign; // signature
39 int iFunc; // functionality
40 int Cost; // cut cost
41 int CostLev; // cut cost
42 unsigned nTreeLeaves : 9; // tree leaves
43 unsigned nSlowLeaves : 9; // slow leaves
44 unsigned nTopLeaves : 10; // top leaves
45 unsigned nLeaves : 4; // leaf count
46 int pLeaves[SBD_MAX_CUTSIZE]; // leaves
47 };
48
49 struct Sbd_Srv_t_
50 {
51 int nLutSize;
52 int nCutSize;
53 int nCutNum;
54 int fVerbose;
55 Gia_Man_t * pGia; // user's AIG manager (will be modified by adding nodes)
56 Vec_Int_t * vMirrors; // mirrors for each node
57 Vec_Int_t * vLutLevs; // delays for each node
58 Vec_Int_t * vLevs; // levels for each node
59 Vec_Int_t * vRefs; // refs for each node
60 Sbd_Cut_t pCuts[SBD_MAX_CUTNUM]; // temporary cuts
61 Sbd_Cut_t * ppCuts[SBD_MAX_CUTNUM]; // temporary cut pointers
62 abctime clkStart; // starting time
63 Vec_Int_t * vCut0; // current cut
64 Vec_Int_t * vCut; // current cut
65 Vec_Int_t * vCutTop; // current cut
66 Vec_Int_t * vCutBot; // current cut
67 };
68
69 ////////////////////////////////////////////////////////////////////////
70 /// FUNCTION DEFINITIONS ///
71 ////////////////////////////////////////////////////////////////////////
72
73 /**Function*************************************************************
74
75 Synopsis []
76
77 Description []
78
79 SideEffects []
80
81 SeeAlso []
82
83 ***********************************************************************/
Sbd_ManCutServerStart(Gia_Man_t * pGia,Vec_Int_t * vMirrors,Vec_Int_t * vLutLevs,Vec_Int_t * vLevs,Vec_Int_t * vRefs,int nLutSize,int nCutSize,int nCutNum,int fVerbose)84 Sbd_Srv_t * Sbd_ManCutServerStart( Gia_Man_t * pGia, Vec_Int_t * vMirrors,
85 Vec_Int_t * vLutLevs, Vec_Int_t * vLevs, Vec_Int_t * vRefs,
86 int nLutSize, int nCutSize, int nCutNum, int fVerbose )
87 {
88 Sbd_Srv_t * p;
89 assert( nLutSize <= nCutSize );
90 assert( nCutSize < SBD_CUT_NO_LEAF );
91 assert( nCutSize > 1 && nCutSize <= SBD_MAX_CUTSIZE );
92 assert( nCutNum > 1 && nCutNum < SBD_MAX_CUTNUM );
93 p = ABC_CALLOC( Sbd_Srv_t, 1 );
94 p->clkStart = Abc_Clock();
95 p->nLutSize = nLutSize;
96 p->nCutSize = nCutSize;
97 p->nCutNum = nCutNum;
98 p->fVerbose = fVerbose;
99 p->pGia = pGia;
100 p->vMirrors = vMirrors;
101 p->vLutLevs = vLutLevs;
102 p->vLevs = vLevs;
103 p->vRefs = vRefs;
104 p->vCut0 = Vec_IntAlloc( 100 );
105 p->vCut = Vec_IntAlloc( 100 );
106 p->vCutTop = Vec_IntAlloc( 100 );
107 p->vCutBot = Vec_IntAlloc( 100 );
108 return p;
109 }
Sbd_ManCutServerStop(Sbd_Srv_t * p)110 void Sbd_ManCutServerStop( Sbd_Srv_t * p )
111 {
112 Vec_IntFree( p->vCut0 );
113 Vec_IntFree( p->vCut );
114 Vec_IntFree( p->vCutTop );
115 Vec_IntFree( p->vCutBot );
116 ABC_FREE( p );
117 }
118
119 /**Function*************************************************************
120
121 Synopsis []
122
123 Description []
124
125 SideEffects []
126
127 SeeAlso []
128
129 ***********************************************************************/
Sbd_ManCutIsTopo_rec(Gia_Man_t * p,Vec_Int_t * vMirrors,int iObj)130 int Sbd_ManCutIsTopo_rec( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj )
131 {
132 Gia_Obj_t * pObj;
133 int Ret0, Ret1;
134 if ( Vec_IntEntry(vMirrors, iObj) >= 0 )
135 iObj = Abc_Lit2Var(Vec_IntEntry(vMirrors, iObj));
136 if ( !iObj || Gia_ObjIsTravIdCurrentId(p, iObj) )
137 return 1;
138 Gia_ObjSetTravIdCurrentId(p, iObj);
139 pObj = Gia_ManObj( p, iObj );
140 if ( Gia_ObjIsCi(pObj) )
141 return 0;
142 assert( Gia_ObjIsAnd(pObj) );
143 Ret0 = Sbd_ManCutIsTopo_rec( p, vMirrors, Gia_ObjFaninId0(pObj, iObj) );
144 Ret1 = Sbd_ManCutIsTopo_rec( p, vMirrors, Gia_ObjFaninId1(pObj, iObj) );
145 return Ret0 && Ret1;
146 }
Sbd_ManCutIsTopo(Gia_Man_t * p,Vec_Int_t * vMirrors,Vec_Int_t * vCut,int iObj)147 int Sbd_ManCutIsTopo( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vCut, int iObj )
148 {
149 int i, Entry, RetValue;
150 Gia_ManIncrementTravId( p );
151 Vec_IntForEachEntry( vCut, Entry, i )
152 Gia_ObjSetTravIdCurrentId( p, Entry );
153 RetValue = Sbd_ManCutIsTopo_rec( p, vMirrors, iObj );
154 if ( RetValue == 0 )
155 printf( "Cut of node %d is not tological\n", iObj );
156 assert( RetValue );
157 return RetValue;
158 }
159
160 /**Function*************************************************************
161
162 Synopsis []
163
164 Description []
165
166 SideEffects []
167
168 SeeAlso []
169
170 ***********************************************************************/
Sbd_ManCutExpandOne(Gia_Man_t * p,Vec_Int_t * vMirrors,Vec_Int_t * vLutLevs,Vec_Int_t * vCut,int iThis,int iObj)171 static inline int Sbd_ManCutExpandOne( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, Vec_Int_t * vCut, int iThis, int iObj )
172 {
173 int Lit0m, Lit1m, Fan0, Fan1, iPlace0, iPlace1;
174 int LutLev = Vec_IntEntry( vLutLevs, iObj );
175 Gia_Obj_t * pObj = Gia_ManObj(p, iObj);
176 if ( Gia_ObjIsCi(pObj) )
177 return 0;
178 assert( Gia_ObjIsAnd(pObj) );
179 Lit0m = Vec_IntEntry( vMirrors, Gia_ObjFaninId0(pObj, iObj) );
180 Lit1m = Vec_IntEntry( vMirrors, Gia_ObjFaninId1(pObj, iObj) );
181 Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, iObj);
182 Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, iObj);
183 iPlace0 = Vec_IntFind( vCut, Fan0 );
184 iPlace1 = Vec_IntFind( vCut, Fan1 );
185 if ( iPlace0 == -1 && iPlace1 == -1 )
186 return 0;
187 if ( Vec_IntEntry(vLutLevs, Fan0) > LutLev || Vec_IntEntry(vLutLevs, Fan1) > LutLev )
188 return 0;
189 Vec_IntDrop( vCut, iThis );
190 if ( iPlace0 == -1 && Fan0 )
191 Vec_IntPushOrder( vCut, Fan0 );
192 if ( iPlace1 == -1 && Fan1 )
193 Vec_IntPushOrder( vCut, Fan1 );
194 return 1;
195 }
Vec_IntIsOrdered(Vec_Int_t * vCut)196 void Vec_IntIsOrdered( Vec_Int_t * vCut )
197 {
198 int i, Prev, Entry;
199 Prev = Vec_IntEntry( vCut, 0 );
200 Vec_IntForEachEntryStart( vCut, Entry, i, 1 )
201 {
202 assert( Prev < Entry );
203 Prev = Entry;
204 }
205 }
Sbd_ManCutExpand(Gia_Man_t * p,Vec_Int_t * vMirrors,Vec_Int_t * vLutLevs,Vec_Int_t * vCut)206 void Sbd_ManCutExpand( Gia_Man_t * p, Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, Vec_Int_t * vCut )
207 {
208 int i, Entry;
209 do
210 {
211 Vec_IntForEachEntry( vCut, Entry, i )
212 if ( Sbd_ManCutExpandOne( p, vMirrors, vLutLevs, vCut, i, Entry ) )
213 break;
214 }
215 while ( i < Vec_IntSize(vCut) );
216 }
Sbd_ManCutReload(Vec_Int_t * vMirrors,Vec_Int_t * vLutLevs,int LevStop,Vec_Int_t * vCut,Vec_Int_t * vCutTop,Vec_Int_t * vCutBot)217 void Sbd_ManCutReload( Vec_Int_t * vMirrors, Vec_Int_t * vLutLevs, int LevStop, Vec_Int_t * vCut, Vec_Int_t * vCutTop, Vec_Int_t * vCutBot )
218 {
219 int i, Entry;
220 Vec_IntClear( vCutTop );
221 Vec_IntClear( vCutBot );
222 Vec_IntForEachEntry( vCut, Entry, i )
223 {
224 assert( Entry );
225 assert( Vec_IntEntry(vMirrors, Entry) == -1 );
226 assert( Vec_IntEntry(vLutLevs, Entry) <= LevStop );
227 if ( Vec_IntEntry(vLutLevs, Entry) == LevStop )
228 Vec_IntPush( vCutTop, Entry );
229 else
230 Vec_IntPush( vCutBot, Entry );
231 }
232 Vec_IntIsOrdered( vCut );
233 }
Sbd_ManCutCollect_rec(Gia_Man_t * p,Vec_Int_t * vMirrors,int iObj,int LevStop,Vec_Int_t * vLutLevs,Vec_Int_t * vCut)234 int Sbd_ManCutCollect_rec( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj, int LevStop, Vec_Int_t * vLutLevs, Vec_Int_t * vCut )
235 {
236 Gia_Obj_t * pObj;
237 int Ret0, Ret1;
238 if ( Vec_IntEntry(vMirrors, iObj) >= 0 )
239 iObj = Abc_Lit2Var(Vec_IntEntry(vMirrors, iObj));
240 if ( !iObj || Gia_ObjIsTravIdCurrentId(p, iObj) )
241 return 1;
242 Gia_ObjSetTravIdCurrentId(p, iObj);
243 pObj = Gia_ManObj( p, iObj );
244 if ( Gia_ObjIsCi(pObj) || Vec_IntEntry(vLutLevs, iObj) <= LevStop )
245 {
246 Vec_IntPush( vCut, iObj );
247 return Vec_IntEntry(vLutLevs, iObj) <= LevStop;
248 }
249 assert( Gia_ObjIsAnd(pObj) );
250 Ret0 = Sbd_ManCutCollect_rec( p, vMirrors, Gia_ObjFaninId0(pObj, iObj), LevStop, vLutLevs, vCut );
251 Ret1 = Sbd_ManCutCollect_rec( p, vMirrors, Gia_ObjFaninId1(pObj, iObj), LevStop, vLutLevs, vCut );
252 return Ret0 && Ret1;
253 }
254
255 /**Function*************************************************************
256
257 Synopsis []
258
259 Description []
260
261 SideEffects []
262
263 SeeAlso []
264
265 ***********************************************************************/
Sbd_ManCutReduceTop(Gia_Man_t * p,Vec_Int_t * vMirrors,int iObj,Vec_Int_t * vLutLevs,Vec_Int_t * vCut,Vec_Int_t * vCutTop,int nCutSize)266 int Sbd_ManCutReduceTop( Gia_Man_t * p, Vec_Int_t * vMirrors, int iObj, Vec_Int_t * vLutLevs, Vec_Int_t * vCut, Vec_Int_t * vCutTop, int nCutSize )
267 {
268 int i, Entry, Lit0m, Lit1m, Fan0, Fan1;
269 int LevStop = Vec_IntEntry(vLutLevs, iObj) - 2;
270 Vec_IntIsOrdered( vCut );
271 Vec_IntForEachEntryReverse( vCutTop, Entry, i )
272 {
273 Gia_Obj_t * pObj = Gia_ManObj( p, Entry );
274 if ( Gia_ObjIsCi(pObj) )
275 continue;
276 assert( Gia_ObjIsAnd(pObj) );
277 assert( Vec_IntEntry(vLutLevs, Entry) == LevStop );
278 Lit0m = Vec_IntEntry( vMirrors, Gia_ObjFaninId0(pObj, Entry) );
279 Lit1m = Vec_IntEntry( vMirrors, Gia_ObjFaninId1(pObj, Entry) );
280 Fan0 = Lit0m >= 0 ? Abc_Lit2Var(Lit0m) : Gia_ObjFaninId0(pObj, Entry);
281 Fan1 = Lit1m >= 0 ? Abc_Lit2Var(Lit1m) : Gia_ObjFaninId1(pObj, Entry);
282 if ( Vec_IntEntry(vLutLevs, Fan0) > LevStop || Vec_IntEntry(vLutLevs, Fan1) > LevStop )
283 continue;
284 assert( Vec_IntEntry(vLutLevs, Fan0) <= LevStop );
285 assert( Vec_IntEntry(vLutLevs, Fan1) <= LevStop );
286 if ( Vec_IntEntry(vLutLevs, Fan0) == LevStop && Vec_IntEntry(vLutLevs, Fan1) == LevStop )
287 continue;
288 Vec_IntRemove( vCut, Entry );
289 if ( Fan0 ) Vec_IntPushUniqueOrder( vCut, Fan0 );
290 if ( Fan1 ) Vec_IntPushUniqueOrder( vCut, Fan1 );
291 //Sbd_ManCutIsTopo( p, vMirrors, vCut, iObj );
292 return 1;
293 }
294 return 0;
295 }
296
297 /**Function*************************************************************
298
299 Synopsis []
300
301 Description []
302
303 SideEffects []
304
305 SeeAlso []
306
307 ***********************************************************************/
Sbd_ManCutServerFirst(Sbd_Srv_t * p,int iObj,int * pLeaves)308 int Sbd_ManCutServerFirst( Sbd_Srv_t * p, int iObj, int * pLeaves )
309 {
310 int RetValue, LevStop = Vec_IntEntry(p->vLutLevs, iObj) - 2;
311
312 Vec_IntClear( p->vCut );
313 Gia_ManIncrementTravId( p->pGia );
314 RetValue = Sbd_ManCutCollect_rec( p->pGia, p->vMirrors, iObj, LevStop, p->vLutLevs, p->vCut );
315 if ( RetValue == 0 ) // cannot build delay-improving cut
316 return -1;
317 // check if the current cut is good
318 Vec_IntSort( p->vCut, 0 );
319 /*
320 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
321 if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
322 {
323 //printf( "%d ", Vec_IntSize(p->vCut) );
324 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
325 return Vec_IntSize(p->vCut);
326 }
327 */
328 // try to expand the cut
329 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
330 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
331 if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
332 {
333 //printf( "1=(%d,%d) ", Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
334 //printf( "%d ", Vec_IntSize(p->vCut) );
335 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
336 return Vec_IntSize(p->vCut);
337 }
338
339 // try to reduce the topmost
340 Vec_IntClear( p->vCut0 );
341 Vec_IntAppend( p->vCut0, p->vCut );
342 if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) )
343 {
344 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
345 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
346 assert( Vec_IntSize(p->vCut) <= p->nCutSize );
347 if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
348 {
349 //printf( "%d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
350 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
351 return Vec_IntSize(p->vCut);
352 }
353 // try again
354 if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) )
355 {
356 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
357 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
358 assert( Vec_IntSize(p->vCut) <= p->nCutSize );
359 if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
360 {
361 //printf( "* %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
362 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
363 return Vec_IntSize(p->vCut);
364 }
365 // try again
366 if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) )
367 {
368 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
369 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
370 assert( Vec_IntSize(p->vCut) <= p->nCutSize );
371 if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
372 {
373 //printf( "** %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
374 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
375 return Vec_IntSize(p->vCut);
376 }
377 // try again
378 if ( Vec_IntSize(p->vCut) < p->nCutSize && Sbd_ManCutReduceTop( p->pGia, p->vMirrors, iObj, p->vLutLevs, p->vCut, p->vCutTop, p->nCutSize ) )
379 {
380 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
381 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
382 assert( Vec_IntSize(p->vCut) <= p->nCutSize );
383 if ( Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
384 {
385 //printf( "*** %d -> %d (%d + %d)\n", Vec_IntSize(p->vCut0), Vec_IntSize(p->vCut), Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
386 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
387 return Vec_IntSize(p->vCut);
388 }
389 }
390 }
391 }
392 }
393
394 // recompute the cut
395 Vec_IntClear( p->vCut );
396 Gia_ManIncrementTravId( p->pGia );
397 RetValue = Sbd_ManCutCollect_rec( p->pGia, p->vMirrors, iObj, LevStop-1, p->vLutLevs, p->vCut );
398 if ( RetValue == 0 ) // cannot build delay-improving cut
399 return -1;
400 // check if the current cut is good
401 Vec_IntSort( p->vCut, 0 );
402 /*
403 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
404 if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
405 {
406 //printf( "%d ", Vec_IntSize(p->vCut) );
407 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
408 return Vec_IntSize(p->vCut);
409 }
410 */
411 // try to expand the cut
412 Sbd_ManCutExpand( p->pGia, p->vMirrors, p->vLutLevs, p->vCut );
413 Sbd_ManCutReload( p->vMirrors, p->vLutLevs, LevStop, p->vCut, p->vCutTop, p->vCutBot );
414 if ( Vec_IntSize(p->vCut) <= p->nCutSize && Vec_IntSize(p->vCutTop) <= p->nLutSize-1 )
415 {
416 //printf( "2=(%d,%d) ", Vec_IntSize(p->vCutTop), Vec_IntSize(p->vCutBot) );
417 //printf( "%d ", Vec_IntSize(p->vCut) );
418 memcpy( pLeaves, Vec_IntArray(p->vCut), sizeof(int) * Vec_IntSize(p->vCut) );
419 return Vec_IntSize(p->vCut);
420 }
421
422 return -1;
423 }
424
425 ////////////////////////////////////////////////////////////////////////
426 /// END OF FILE ///
427 ////////////////////////////////////////////////////////////////////////
428
429
430 ABC_NAMESPACE_IMPL_END
431
432