abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaResub.c File Reference
#include "gia.h"
#include "misc/vec/vecWec.h"
#include "misc/vec/vecQue.h"
#include "misc/vec/vecHsh.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START int Gia_ObjCheckMffc_rec (Gia_Man_t *p, Gia_Obj_t *pObj, int Limit, Vec_Int_t *vNodes)
 DECLARATIONS ///. More...
 
static int Gia_ObjCheckMffc (Gia_Man_t *p, Gia_Obj_t *pRoot, int Limit, Vec_Int_t *vNodes, Vec_Int_t *vLeaves, Vec_Int_t *vInners)
 
Vec_Wec_tGia_ManComputeMffcs (Gia_Man_t *p, int LimitMin, int LimitMax, int SuppMax, int RatioBest)
 
void Gia_ManPrintDivStats (Gia_Man_t *p, Vec_Wec_t *vMffcs, Vec_Wec_t *vPivots)
 
void Gia_ManAddDivisors (Gia_Man_t *p, Vec_Wec_t *vMffcs)
 
void Gia_ManResubTest (Gia_Man_t *p)
 

Function Documentation

void Gia_ManAddDivisors ( Gia_Man_t p,
Vec_Wec_t vMffcs 
)

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

Synopsis [Compute divisors and Boolean functions for the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 195 of file giaResub.c.

196 {
197  Vec_Wec_t * vPivots;
198  Vec_Int_t * vMffc, * vPivot, * vPivot0, * vPivot1;
199  Vec_Int_t * vCommon, * vCommon2, * vMap;
200  Gia_Obj_t * pObj;
201  int i, k, iObj, iPivot, iMffc;
202 //abctime clkStart = Abc_Clock();
203  // initialize pivots (mapping of nodes into MFFCs whose leaves they are)
204  vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
205  vPivots = Vec_WecStart( Gia_ManObjNum(p) );
206  Vec_WecForEachLevel( vMffcs, vMffc, i )
207  {
208  assert( Vec_IntSize(vMffc) == 3 + Vec_IntEntry(vMffc, 1) );
209  iPivot = Vec_IntEntry( vMffc, 0 );
210  Vec_IntWriteEntry( vMap, iPivot, i );
211  // iterate through the MFFC leaves
212  Vec_IntForEachEntryStart( vMffc, iObj, k, 3 )
213  {
214  vPivot = Vec_WecEntry( vPivots, iObj );
215  if ( Vec_IntSize(vPivot) == 0 )
216  Vec_IntGrow(vPivot, 4);
217  Vec_IntPush( vPivot, iPivot );
218  }
219  }
220  Vec_WecForEachLevel( vPivots, vPivot, i )
221  Vec_IntSort( vPivot, 0 );
222  // create pivots for internal nodes while growing MFFCs
223  vCommon = Vec_IntAlloc( 100 );
224  vCommon2 = Vec_IntAlloc( 100 );
225  Gia_ManForEachAnd( p, pObj, i )
226  {
227  // find commont pivots
228  // the slow down happens because some PIs have very large sets of pivots
229  vPivot0 = Vec_WecEntry( vPivots, Gia_ObjFaninId0(pObj, i) );
230  vPivot1 = Vec_WecEntry( vPivots, Gia_ObjFaninId1(pObj, i) );
231  Vec_IntTwoFindCommon( vPivot0, vPivot1, vCommon );
232  if ( Gia_ObjIsMuxId(p, i) )
233  {
234  vPivot = Vec_WecEntry( vPivots, Gia_ObjFaninId2(p, i) );
235  Vec_IntTwoFindCommon( vPivot, vCommon, vCommon2 );
236  ABC_SWAP( Vec_Int_t *, vCommon, vCommon2 );
237  }
238  if ( Vec_IntSize(vCommon) == 0 )
239  continue;
240  // add new pivots (this trick increased memory used in vPivots)
241  vPivot = Vec_WecEntry( vPivots, i );
242  Vec_IntTwoMerge2( vPivot, vCommon, vCommon2 );
243  ABC_SWAP( Vec_Int_t, *vPivot, *vCommon2 );
244  // grow MFFCs
245  Vec_IntForEachEntry( vCommon, iObj, k )
246  {
247  iMffc = Vec_IntEntry( vMap, iObj );
248  assert( iMffc != -1 );
249  vMffc = Vec_WecEntry( vMffcs, iMffc );
250  Vec_IntPush( vMffc, i );
251  }
252  }
253 //Abc_PrintTime( 1, "Time", Abc_Clock() - clkStart );
254  Vec_IntFree( vCommon );
255  Vec_IntFree( vCommon2 );
256  Vec_IntFree( vMap );
257  Gia_ManPrintDivStats( p, vMffcs, vPivots );
258  Vec_WecFree( vPivots );
259  // returns the modified array of MFFCs
260 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Wec_t_ Vec_Wec_t
INCLUDES ///.
Definition: vecWec.h:42
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
static void Vec_WecFree(Vec_Wec_t *p)
Definition: vecWec.h:345
static Vec_Wec_t * Vec_WecStart(int nSize)
Definition: vecWec.h:98
static void Vec_IntSort(Vec_Int_t *p, int fReverse)
Definition: vecInt.h:1293
static Vec_Int_t * Vec_IntStartFull(int nSize)
Definition: vecInt.h:119
Definition: gia.h:75
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
static void Vec_IntGrow(Vec_Int_t *p, int nCapMin)
Definition: bblif.c:336
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
static int Gia_ObjIsMuxId(Gia_Man_t *p, int iObj)
Definition: gia.h:424
#define Vec_WecForEachLevel(vGlob, vVec, i)
MACRO DEFINITIONS ///.
Definition: vecWec.h:55
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
static void Vec_IntTwoMerge2(Vec_Int_t *vArr1, Vec_Int_t *vArr2, Vec_Int_t *vArr)
Definition: vecInt.h:1690
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
#define Gia_ManForEachAnd(p, pObj, i)
Definition: gia.h:1002
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
#define Vec_IntForEachEntryStart(vVec, Entry, i, Start)
Definition: vecInt.h:56
static Vec_Int_t * Vec_WecEntry(Vec_Wec_t *p, int i)
Definition: vecWec.h:142
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static int Vec_IntTwoFindCommon(Vec_Int_t *vArr1, Vec_Int_t *vArr2, Vec_Int_t *vArr)
Definition: vecInt.h:1558
#define assert(ex)
Definition: util_old.h:213
static int Gia_ObjFaninId2(Gia_Man_t *p, int ObjId)
Definition: gia.h:462
void Gia_ManPrintDivStats(Gia_Man_t *p, Vec_Wec_t *vMffcs, Vec_Wec_t *vPivots)
Definition: giaResub.c:158
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
static int Gia_ObjFaninId1(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:461
static int Gia_ManObjNum(Gia_Man_t *p)
Definition: gia.h:388
static int Gia_ObjFaninId0(Gia_Obj_t *pObj, int ObjId)
Definition: gia.h:460
Vec_Wec_t* Gia_ManComputeMffcs ( Gia_Man_t p,
int  LimitMin,
int  LimitMax,
int  SuppMax,
int  RatioBest 
)

Definition at line 97 of file giaResub.c.

98 {
99  Gia_Obj_t * pObj;
100  Vec_Wec_t * vMffcs;
101  Vec_Int_t * vNodes, * vLeaves, * vInners, * vMffc;
102  int i, iPivot;
103  assert( p->pMuxes );
104  vNodes = Vec_IntAlloc( 2 * LimitMax );
105  vLeaves = Vec_IntAlloc( 2 * LimitMax );
106  vInners = Vec_IntAlloc( 2 * LimitMax );
107  vMffcs = Vec_WecAlloc( 1000 );
108  Gia_ManCreateRefs( p );
109  Gia_ManForEachAnd( p, pObj, i )
110  {
111  if ( !Gia_ObjRefNum(p, pObj) )
112  continue;
113  if ( !Gia_ObjCheckMffc(p, pObj, LimitMax, vNodes, vLeaves, vInners) )
114  continue;
115  if ( Vec_IntSize(vInners) < LimitMin )
116  continue;
117  if ( Vec_IntSize(vLeaves) > SuppMax )
118  continue;
119  // improve cut
120  // collect cut
121  vMffc = Vec_WecPushLevel( vMffcs );
122  Vec_IntGrow( vMffc, Vec_IntSize(vLeaves) + Vec_IntSize(vInners) + 20 );
123  Vec_IntPush( vMffc, i );
124  Vec_IntPush( vMffc, Vec_IntSize(vLeaves) );
125  Vec_IntPush( vMffc, Vec_IntSize(vInners) );
126  Vec_IntAppend( vMffc, vLeaves );
127 // Vec_IntAppend( vMffc, vInners );
128  // add last entry equal to the ratio
129  Vec_IntPush( vMffc, 1000 * Vec_IntSize(vInners) / Vec_IntSize(vLeaves) );
130  }
131  Vec_IntFree( vNodes );
132  Vec_IntFree( vLeaves );
133  Vec_IntFree( vInners );
134  // sort MFFCs by their inner/leaf ratio
135  Vec_WecSortByLastInt( vMffcs, 1 );
136  Vec_WecForEachLevel( vMffcs, vMffc, i )
137  Vec_IntPop( vMffc );
138  // remove those whose ratio is not good
139  iPivot = RatioBest * Vec_WecSize(vMffcs) / 100;
140  Vec_WecForEachLevelStart( vMffcs, vMffc, i, iPivot )
141  Vec_IntErase( vMffc );
142  assert( iPivot <= Vec_WecSize(vMffcs) );
143  Vec_WecShrink( vMffcs, iPivot );
144  return vMffcs;
145 }
static void Vec_WecShrink(Vec_Wec_t *p, int nSizeNew)
Definition: vecWec.h:238
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition: giaUtil.c:715
static Vec_Wec_t * Vec_WecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecWec.h:87
static void Vec_WecSortByLastInt(Vec_Wec_t *p, int fReverse)
Definition: vecWec.h:502
typedefABC_NAMESPACE_HEADER_START struct Vec_Wec_t_ Vec_Wec_t
INCLUDES ///.
Definition: vecWec.h:42
static int Gia_ObjCheckMffc(Gia_Man_t *p, Gia_Obj_t *pRoot, int Limit, Vec_Int_t *vNodes, Vec_Int_t *vLeaves, Vec_Int_t *vInners)
Definition: giaResub.c:70
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
static Vec_Int_t * Vec_WecPushLevel(Vec_Wec_t *p)
Definition: vecWec.h:284
unsigned * pMuxes
Definition: gia.h:104
static int Gia_ObjRefNum(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:521
static void Vec_IntErase(Vec_Int_t *p)
Definition: vecInt.h:266
Definition: gia.h:75
static int Vec_WecSize(Vec_Wec_t *p)
Definition: vecWec.h:193
static void Vec_IntGrow(Vec_Int_t *p, int nCapMin)
Definition: bblif.c:336
#define Vec_WecForEachLevel(vGlob, vVec, i)
MACRO DEFINITIONS ///.
Definition: vecWec.h:55
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
static int Vec_IntPop(Vec_Int_t *p)
#define Gia_ManForEachAnd(p, pObj, i)
Definition: gia.h:1002
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
static void Vec_IntAppend(Vec_Int_t *vVec1, Vec_Int_t *vVec2)
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
#define Vec_WecForEachLevelStart(vGlob, vVec, i, LevelStart)
Definition: vecWec.h:59
#define assert(ex)
Definition: util_old.h:213
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
void Gia_ManPrintDivStats ( Gia_Man_t p,
Vec_Wec_t vMffcs,
Vec_Wec_t vPivots 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 158 of file giaResub.c.

159 {
160  int fVerbose = 0;
161  Vec_Int_t * vMffc;
162  int i, nDivs, nDivsAll = 0, nDivs0 = 0;
163  Vec_WecForEachLevel( vMffcs, vMffc, i )
164  {
165  nDivs = Vec_IntSize(vMffc) - 3 - Vec_IntEntry(vMffc, 1) - Vec_IntEntry(vMffc, 2);
166  nDivs0 += (nDivs == 0);
167  nDivsAll += nDivs;
168  if ( !fVerbose )
169  continue;
170  printf( "%6d : ", Vec_IntEntry(vMffc, 0) );
171  printf( "Leaf =%3d ", Vec_IntEntry(vMffc, 1) );
172  printf( "Mffc =%4d ", Vec_IntEntry(vMffc, 2) );
173  printf( "Divs =%4d ", nDivs );
174  printf( "\n" );
175  }
176  printf( "Collected %d (%.1f %%) MFFCs and %d (%.1f %%) have no divisors (div ave for others is %.2f).\n",
177  Vec_WecSize(vMffcs), 100.0 * Vec_WecSize(vMffcs) / Gia_ManAndNum(p),
178  nDivs0, 100.0 * nDivs0 / Gia_ManAndNum(p),
179  1.0*nDivsAll/Abc_MaxInt(1, Vec_WecSize(vMffcs) - nDivs0) );
180  printf( "Using %.2f MB for MFFCs and %.2f MB for pivots. ",
181  Vec_WecMemory(vMffcs)/(1<<20), Vec_WecMemory(vPivots)/(1<<20) );
182 }
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
static double Vec_WecMemory(Vec_Wec_t *p)
Definition: vecWec.h:308
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
static int Vec_WecSize(Vec_Wec_t *p)
Definition: vecWec.h:193
static int Gia_ManAndNum(Gia_Man_t *p)
Definition: gia.h:389
#define Vec_WecForEachLevel(vGlob, vVec, i)
MACRO DEFINITIONS ///.
Definition: vecWec.h:55
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
void Gia_ManResubTest ( Gia_Man_t p)

Definition at line 261 of file giaResub.c.

262 {
263  Vec_Wec_t * vMffcs;
264  Gia_Man_t * pNew = Gia_ManDupMuxes( p, 2 );
265 abctime clkStart = Abc_Clock();
266  vMffcs = Gia_ManComputeMffcs( pNew, 4, 100, 8, 100 );
267  Gia_ManAddDivisors( pNew, vMffcs );
268  Vec_WecFree( vMffcs );
269 Abc_PrintTime( 1, "Time", Abc_Clock() - clkStart );
270  Gia_ManStop( pNew );
271 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Wec_t_ Vec_Wec_t
INCLUDES ///.
Definition: vecWec.h:42
void Gia_ManStop(Gia_Man_t *p)
Definition: giaMan.c:77
static void Vec_WecFree(Vec_Wec_t *p)
Definition: vecWec.h:345
Vec_Wec_t * Gia_ManComputeMffcs(Gia_Man_t *p, int LimitMin, int LimitMax, int SuppMax, int RatioBest)
Definition: giaResub.c:97
static abctime Abc_Clock()
Definition: abc_global.h:279
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Gia_Man_t * Gia_ManDupMuxes(Gia_Man_t *p, int Limit)
Definition: giaMuxes.c:96
void Gia_ManAddDivisors(Gia_Man_t *p, Vec_Wec_t *vMffcs)
Definition: giaResub.c:195
Definition: gia.h:95
ABC_INT64_T abctime
Definition: abc_global.h:278
static int Gia_ObjCheckMffc ( Gia_Man_t p,
Gia_Obj_t pRoot,
int  Limit,
Vec_Int_t vNodes,
Vec_Int_t vLeaves,
Vec_Int_t vInners 
)
inlinestatic

Definition at line 70 of file giaResub.c.

71 {
72  int RetValue, iObj, i;
73  Vec_IntClear( vNodes );
74  RetValue = Gia_ObjCheckMffc_rec( p, pRoot, Limit, vNodes );
75  if ( RetValue )
76  {
77  Vec_IntClear( vLeaves );
78  Vec_IntClear( vInners );
79  Vec_IntSort( vNodes, 0 );
80  Vec_IntForEachEntry( vNodes, iObj, i )
81  if ( Gia_ObjRefNumId(p, iObj) > 0 || Gia_ObjIsCi(Gia_ManObj(p, iObj)) )
82  {
83  if ( !Vec_IntSize(vLeaves) || Vec_IntEntryLast(vLeaves) != iObj )
84  Vec_IntPush( vLeaves, iObj );
85  }
86  else
87  {
88  if ( !Vec_IntSize(vInners) || Vec_IntEntryLast(vInners) != iObj )
89  Vec_IntPush( vInners, iObj );
90  }
91  Vec_IntPush( vInners, Gia_ObjId(p, pRoot) );
92  }
93  Vec_IntForEachEntry( vNodes, iObj, i )
94  Gia_ObjRefIncId( p, iObj );
95  return RetValue;
96 }
ABC_NAMESPACE_IMPL_START int Gia_ObjCheckMffc_rec(Gia_Man_t *p, Gia_Obj_t *pObj, int Limit, Vec_Int_t *vNodes)
DECLARATIONS ///.
Definition: giaResub.c:48
static int Gia_ObjRefNumId(Gia_Man_t *p, int Id)
Definition: gia.h:518
static void Vec_IntSort(Vec_Int_t *p, int fReverse)
Definition: vecInt.h:1293
static Gia_Obj_t * Gia_ManObj(Gia_Man_t *p, int v)
Definition: gia.h:402
if(last==0)
Definition: sparse_int.h:34
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
static int Gia_ObjId(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:410
static int Vec_IntEntryLast(Vec_Int_t *p)
Definition: bblif.c:319
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
static int Gia_ObjRefIncId(Gia_Man_t *p, int Id)
Definition: gia.h:519
ABC_NAMESPACE_IMPL_START int Gia_ObjCheckMffc_rec ( Gia_Man_t p,
Gia_Obj_t pObj,
int  Limit,
Vec_Int_t vNodes 
)

DECLARATIONS ///.

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

FileName [giaResub.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Scalable AIG package.]

Synopsis [Resubstitution.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Computes MFFCs of all qualifying nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 48 of file giaResub.c.

49 {
50  int iFanin;
51  if ( Gia_ObjIsCi(pObj) )
52  return 1;
53  assert( Gia_ObjIsAnd(pObj) );
54  iFanin = Gia_ObjFaninId0p(p, pObj);
55  Vec_IntPush( vNodes, iFanin );
56  if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin0(pObj), Limit, vNodes)) )
57  return 0;
58  iFanin = Gia_ObjFaninId1p(p, pObj);
59  Vec_IntPush( vNodes, iFanin );
60  if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin1(pObj), Limit, vNodes)) )
61  return 0;
62  if ( !Gia_ObjIsMux(p, pObj) )
63  return 1;
64  iFanin = Gia_ObjFaninId2p(p, pObj);
65  Vec_IntPush( vNodes, iFanin );
66  if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin2(p, pObj), Limit, vNodes)) )
67  return 0;
68  return 1;
69 }
ABC_NAMESPACE_IMPL_START int Gia_ObjCheckMffc_rec(Gia_Man_t *p, Gia_Obj_t *pObj, int Limit, Vec_Int_t *vNodes)
DECLARATIONS ///.
Definition: giaResub.c:48
static int Gia_ObjRefDecId(Gia_Man_t *p, int Id)
Definition: gia.h:520
static int Gia_ObjFaninId1p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:464
static Gia_Obj_t * Gia_ObjFanin0(Gia_Obj_t *pObj)
Definition: gia.h:454
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
static Gia_Obj_t * Gia_ObjFanin2(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:456
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
static int Gia_ObjIsAnd(Gia_Obj_t *pObj)
Definition: gia.h:422
static int Gia_ObjFaninId0p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:463
static int Gia_ObjFaninId2p(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:465
static Gia_Obj_t * Gia_ObjFanin1(Gia_Obj_t *pObj)
Definition: gia.h:455
#define assert(ex)
Definition: util_old.h:213
static int Gia_ObjIsCi(Gia_Obj_t *pObj)
Definition: gia.h:420
static int Gia_ObjIsMux(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition: gia.h:425