ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
sbdCut2.c File Reference
#include "sbdInt.h"
Include dependency graph for sbdCut2.c:

Go to the source code of this file.

Classes

struct  Sbd_Cut_t_
 
struct  Sbd_Srv_t_
 

Macros

#define SBD_MAX_CUTSIZE   10
 DECLARATIONS ///.
 
#define SBD_MAX_CUTNUM   501
 
#define SBD_CUT_NO_LEAF   0xF
 

Functions

Sbd_Srv_tSbd_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)
 FUNCTION DEFINITIONS ///.
 
void Sbd_ManCutServerStop (Sbd_Srv_t *p)
 
int Sbd_ManCutIsTopo_rec (Gia_Man_t *p, Vec_Int_t *vMirrors, int iObj)
 
int Sbd_ManCutIsTopo (Gia_Man_t *p, Vec_Int_t *vMirrors, Vec_Int_t *vCut, int iObj)
 
void Vec_IntOrdered (Vec_Int_t *vCut)
 
void Sbd_ManCutExpand (Gia_Man_t *p, Vec_Int_t *vMirrors, Vec_Int_t *vLutLevs, Vec_Int_t *vCut)
 
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)
 
int Sbd_ManCutCollect_rec (Gia_Man_t *p, Vec_Int_t *vMirrors, int iObj, int LevStop, Vec_Int_t *vLutLevs, Vec_Int_t *vCut)
 
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)
 
int Sbd_ManCutServerFirst (Sbd_Srv_t *p, int iObj, int *pLeaves)
 

Macro Definition Documentation

◆ SBD_CUT_NO_LEAF

#define SBD_CUT_NO_LEAF   0xF

Definition at line 33 of file sbdCut2.c.

◆ SBD_MAX_CUTNUM

#define SBD_MAX_CUTNUM   501

Definition at line 31 of file sbdCut2.c.

◆ SBD_MAX_CUTSIZE

#define SBD_MAX_CUTSIZE   10

DECLARATIONS ///.

CFile****************************************************************

FileName [sbdCut2.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [SAT-based optimization using internal don't-cares.]

Synopsis [Cut computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
sbdCut2.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 30 of file sbdCut2.c.

Function Documentation

◆ Sbd_ManCutCollect_rec()

int Sbd_ManCutCollect_rec ( Gia_Man_t * p,
Vec_Int_t * vMirrors,
int iObj,
int LevStop,
Vec_Int_t * vLutLevs,
Vec_Int_t * vCut )

Definition at line 234 of file sbdCut2.c.

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}
Cube * p
Definition exorList.c:222
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
int Sbd_ManCutCollect_rec(Gia_Man_t *p, Vec_Int_t *vMirrors, int iObj, int LevStop, Vec_Int_t *vLutLevs, Vec_Int_t *vCut)
Definition sbdCut2.c:234
#define assert(ex)
Definition util_old.h:213
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Sbd_ManCutExpand()

void Sbd_ManCutExpand ( Gia_Man_t * p,
Vec_Int_t * vMirrors,
Vec_Int_t * vLutLevs,
Vec_Int_t * vCut )

Definition at line 206 of file sbdCut2.c.

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}
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54
Here is the caller graph for this function:

◆ Sbd_ManCutIsTopo()

int Sbd_ManCutIsTopo ( Gia_Man_t * p,
Vec_Int_t * vMirrors,
Vec_Int_t * vCut,
int iObj )

Definition at line 147 of file sbdCut2.c.

148{
149 int i, Entry, RetValue;
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}
void Gia_ManIncrementTravId(Gia_Man_t *p)
Definition giaUtil.c:190
int Sbd_ManCutIsTopo_rec(Gia_Man_t *p, Vec_Int_t *vMirrors, int iObj)
Definition sbdCut2.c:130
Here is the call graph for this function:

◆ Sbd_ManCutIsTopo_rec()

int Sbd_ManCutIsTopo_rec ( Gia_Man_t * p,
Vec_Int_t * vMirrors,
int iObj )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 130 of file sbdCut2.c.

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}
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Sbd_ManCutReduceTop()

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 )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 266 of file sbdCut2.c.

267{
268 int i, Entry, Lit0m, Lit1m, Fan0, Fan1;
269 int LevStop = Vec_IntEntry(vLutLevs, iObj) - 2;
270 Vec_IntOrdered( 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}
void Vec_IntOrdered(Vec_Int_t *vCut)
Definition sbdCut2.c:196
#define Vec_IntForEachEntryReverse(vVec, pEntry, i)
Definition vecInt.h:62
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Sbd_ManCutReload()

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 )

Definition at line 217 of file sbdCut2.c.

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_IntOrdered( vCut );
233}
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Sbd_ManCutServerFirst()

int Sbd_ManCutServerFirst ( Sbd_Srv_t * p,
int iObj,
int * pLeaves )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 308 of file sbdCut2.c.

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}
void Sbd_ManCutExpand(Gia_Man_t *p, Vec_Int_t *vMirrors, Vec_Int_t *vLutLevs, Vec_Int_t *vCut)
Definition sbdCut2.c:206
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)
Definition sbdCut2.c:266
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)
Definition sbdCut2.c:217
char * memcpy()
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Sbd_ManCutServerStart()

Sbd_Srv_t * 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 )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 84 of file sbdCut2.c.

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}
#define ABC_CALLOC(type, num)
Definition abc_global.h:265
#define SBD_MAX_CUTSIZE
DECLARATIONS ///.
Definition sbdCut.c:30
#define SBD_CUT_NO_LEAF
Definition sbdCut.c:34
#define SBD_MAX_CUTNUM
Definition sbdCut.c:31
struct Sbd_Srv_t_ Sbd_Srv_t
Definition sbdInt.h:65
Here is the caller graph for this function:

◆ Sbd_ManCutServerStop()

void Sbd_ManCutServerStop ( Sbd_Srv_t * p)

Definition at line 110 of file sbdCut2.c.

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}
#define ABC_FREE(obj)
Definition abc_global.h:267
Here is the caller graph for this function:

◆ Vec_IntOrdered()

void Vec_IntOrdered ( Vec_Int_t * vCut)

Definition at line 196 of file sbdCut2.c.

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}
#define Vec_IntForEachEntryStart(vVec, Entry, i, Start)
Definition vecInt.h:56
Here is the caller graph for this function: