abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcAuto.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcAuto.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [Computation of autosymmetries.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcAuto.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 #include "misc/extra/extraBdd.h"
23 
25 
26 
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30 
31 static void Abc_NtkAutoPrintAll( DdManager * dd, int nInputs, DdNode * pbOutputs[], int nOutputs, char * pInputNames[], char * pOutputNames[], int fNaive );
32 static void Abc_NtkAutoPrintOne( DdManager * dd, int nInputs, DdNode * pbOutputs[], int Output, char * pInputNames[], char * pOutputNames[], int fNaive );
33 
34 ////////////////////////////////////////////////////////////////////////
35 /// FUNCTION DEFINITIONS ///
36 ////////////////////////////////////////////////////////////////////////
37 
38 /**Function*************************************************************
39 
40  Synopsis []
41 
42  Description []
43 
44  SideEffects []
45 
46  SeeAlso []
47 
48 ***********************************************************************/
49 void Abc_NtkAutoPrint( Abc_Ntk_t * pNtk, int Output, int fNaive, int fVerbose )
50 {
51  DdManager * dd; // the BDD manager used to hold shared BDDs
52  DdNode ** pbGlobal; // temporary storage for global BDDs
53  char ** pInputNames; // pointers to the CI names
54  char ** pOutputNames; // pointers to the CO names
55  int nOutputs, nInputs, i;
56  Vec_Ptr_t * vFuncsGlob;
57  Abc_Obj_t * pObj;
58 
59  // compute the global BDDs
60  if ( Abc_NtkBuildGlobalBdds(pNtk, 10000000, 1, 1, fVerbose) == NULL )
61  return;
62 
63  // get information about the network
64  nInputs = Abc_NtkCiNum(pNtk);
65  nOutputs = Abc_NtkCoNum(pNtk);
66 // dd = pNtk->pManGlob;
67  dd = (DdManager *)Abc_NtkGlobalBddMan( pNtk );
68 
69  // complement the global functions
70  vFuncsGlob = Vec_PtrAlloc( Abc_NtkCoNum(pNtk) );
71  Abc_NtkForEachCo( pNtk, pObj, i )
72  Vec_PtrPush( vFuncsGlob, Abc_ObjGlobalBdd(pObj) );
73  pbGlobal = (DdNode **)Vec_PtrArray( vFuncsGlob );
74 
75  // get the network names
76  pInputNames = Abc_NtkCollectCioNames( pNtk, 0 );
77  pOutputNames = Abc_NtkCollectCioNames( pNtk, 1 );
78 
79  // print the size of the BDDs
80  if ( fVerbose )
81  printf( "Shared BDD size = %6d nodes.\n", Cudd_ReadKeys(dd) - Cudd_ReadDead(dd) );
82 
83  // allocate additional variables
84  for ( i = 0; i < nInputs; i++ )
85  Cudd_bddNewVar( dd );
86  assert( Cudd_ReadSize(dd) == 2 * nInputs );
87 
88  // create ZDD variables in the manager
89  Cudd_zddVarsFromBddVars( dd, 2 );
90 
91  // perform the analysis of the primary output functions for auto-symmetry
92  if ( Output == -1 )
93  Abc_NtkAutoPrintAll( dd, nInputs, pbGlobal, nOutputs, pInputNames, pOutputNames, fNaive );
94  else
95  Abc_NtkAutoPrintOne( dd, nInputs, pbGlobal, Output, pInputNames, pOutputNames, fNaive );
96 
97  // deref the PO functions
98 // Abc_NtkFreeGlobalBdds( pNtk );
99  // stop the global BDD manager
100 // Extra_StopManager( pNtk->pManGlob );
101 // pNtk->pManGlob = NULL;
102  Abc_NtkFreeGlobalBdds( pNtk, 1 );
103  ABC_FREE( pInputNames );
104  ABC_FREE( pOutputNames );
105  Vec_PtrFree( vFuncsGlob );
106 }
107 
108 /**Function*************************************************************
109 
110  Synopsis []
111 
112  Description []
113 
114  SideEffects []
115 
116  SeeAlso []
117 
118 ***********************************************************************/
119 void Abc_NtkAutoPrintAll( DdManager * dd, int nInputs, DdNode * pbOutputs[], int nOutputs, char * pInputNames[], char * pOutputNames[], int fNaive )
120 {
121  DdNode * bSpace1, * bSpace2, * bCanVars, * bReduced, * zEquations;
122  double nMints;
123  int nSupp, SigCounter, o;
124 
125  int nAutos;
126  int nAutoSyms;
127  int nAutoSymsMax;
128  int nAutoSymsMaxSupp;
129  int nAutoSymOuts;
130  int nSuppSizeMax;
131  abctime clk;
132 
133  nAutoSymOuts = 0;
134  nAutoSyms = 0;
135  nAutoSymsMax = 0;
136  nAutoSymsMaxSupp = 0;
137  nSuppSizeMax = 0;
138  clk = Abc_Clock();
139 
140  SigCounter = 0;
141  for ( o = 0; o < nOutputs; o++ )
142  {
143 // bSpace1 = Extra_bddSpaceFromFunctionFast( dd, pbOutputs[o] ); Cudd_Ref( bSpace1 );
144  bSpace1 = Extra_bddSpaceFromFunction( dd, pbOutputs[o], pbOutputs[o] ); Cudd_Ref( bSpace1 );
145  bCanVars = Extra_bddSpaceCanonVars( dd, bSpace1 ); Cudd_Ref( bCanVars );
146  bReduced = Extra_bddSpaceReduce( dd, pbOutputs[o], bCanVars ); Cudd_Ref( bReduced );
147  zEquations = Extra_bddSpaceEquations( dd, bSpace1 ); Cudd_Ref( zEquations );
148 
149  nSupp = Cudd_SupportSize( dd, bSpace1 );
150  nMints = Cudd_CountMinterm( dd, bSpace1, nSupp );
151  nAutos = Extra_Base2LogDouble(nMints);
152  printf( "Output #%3d: Inputs = %2d. AutoK = %2d.\n", o, nSupp, nAutos );
153 
154  if ( nAutos > 0 )
155  {
156  nAutoSymOuts++;
157  nAutoSyms += nAutos;
158  if ( nAutoSymsMax < nAutos )
159  {
160  nAutoSymsMax = nAutos;
161  nAutoSymsMaxSupp = nSupp;
162  }
163  }
164  if ( nSuppSizeMax < nSupp )
165  nSuppSizeMax = nSupp;
166 
167 
168 //ABC_PRB( dd, bCanVars );
169 //ABC_PRB( dd, bReduced );
170 //Cudd_PrintMinterm( dd, bReduced );
171 //printf( "The equations are:\n" );
172 //Cudd_zddPrintCover( dd, zEquations );
173 //printf( "\n" );
174 //fflush( stdout );
175 
176  bSpace2 = Extra_bddSpaceFromMatrixPos( dd, zEquations ); Cudd_Ref( bSpace2 );
177 //ABC_PRB( dd, bSpace1 );
178 //ABC_PRB( dd, bSpace2 );
179  if ( bSpace1 != bSpace2 )
180  printf( "Spaces are NOT EQUAL!\n" );
181 // else
182 // printf( "Spaces are equal.\n" );
183 
184  Cudd_RecursiveDeref( dd, bSpace1 );
185  Cudd_RecursiveDeref( dd, bSpace2 );
186  Cudd_RecursiveDeref( dd, bCanVars );
187  Cudd_RecursiveDeref( dd, bReduced );
188  Cudd_RecursiveDerefZdd( dd, zEquations );
189  }
190 
191  printf( "The cumulative statistics for all outputs:\n" );
192  printf( "Ins=%3d ", nInputs );
193  printf( "InMax=%3d ", nSuppSizeMax );
194  printf( "Outs=%3d ", nOutputs );
195  printf( "Auto=%3d ", nAutoSymOuts );
196  printf( "SumK=%3d ", nAutoSyms );
197  printf( "KMax=%2d ", nAutoSymsMax );
198  printf( "Supp=%3d ", nAutoSymsMaxSupp );
199  printf( "Time=%4.2f ", (float)(Abc_Clock() - clk)/(float)(CLOCKS_PER_SEC) );
200  printf( "\n" );
201 }
202 
203 /**Function*************************************************************
204 
205  Synopsis []
206 
207  Description []
208 
209  SideEffects []
210 
211  SeeAlso []
212 
213 ***********************************************************************/
214 void Abc_NtkAutoPrintOne( DdManager * dd, int nInputs, DdNode * pbOutputs[], int Output, char * pInputNames[], char * pOutputNames[], int fNaive )
215 {
216  DdNode * bSpace1, * bCanVars, * bReduced, * zEquations;
217  double nMints;
218  int nSupp, SigCounter;
219  int nAutos;
220 
221  SigCounter = 0;
222  bSpace1 = Extra_bddSpaceFromFunctionFast( dd, pbOutputs[Output] ); Cudd_Ref( bSpace1 );
223 // bSpace1 = Extra_bddSpaceFromFunction( dd, pbOutputs[Output], pbOutputs[Output] ); Cudd_Ref( bSpace1 );
224  bCanVars = Extra_bddSpaceCanonVars( dd, bSpace1 ); Cudd_Ref( bCanVars );
225  bReduced = Extra_bddSpaceReduce( dd, pbOutputs[Output], bCanVars ); Cudd_Ref( bReduced );
226  zEquations = Extra_bddSpaceEquations( dd, bSpace1 ); Cudd_Ref( zEquations );
227 
228  nSupp = Cudd_SupportSize( dd, bSpace1 );
229  nMints = Cudd_CountMinterm( dd, bSpace1, nSupp );
230  nAutos = Extra_Base2LogDouble(nMints);
231  printf( "Output #%3d: Inputs = %2d. AutoK = %2d.\n", Output, nSupp, nAutos );
232 
233  Cudd_RecursiveDeref( dd, bSpace1 );
234  Cudd_RecursiveDeref( dd, bCanVars );
235  Cudd_RecursiveDeref( dd, bReduced );
236  Cudd_RecursiveDerefZdd( dd, zEquations );
237 }
238 
239 ////////////////////////////////////////////////////////////////////////
240 /// END OF FILE ///
241 ////////////////////////////////////////////////////////////////////////
242 
243 
245 
DdNode * Extra_bddSpaceFromFunction(DdManager *dd, DdNode *bF, DdNode *bG)
Definition: extraBddAuto.c:253
void Cudd_RecursiveDerefZdd(DdManager *table, DdNode *n)
Definition: cuddRef.c:385
DdNode * Cudd_bddNewVar(DdManager *dd)
Definition: cuddAPI.c:323
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
double Cudd_CountMinterm(DdManager *manager, DdNode *node, int nvars)
Definition: cuddUtil.c:578
Definition: cudd.h:278
DdNode * Extra_bddSpaceFromMatrixPos(DdManager *dd, DdNode *zA)
Definition: extraBddAuto.c:431
ABC_DLL char ** Abc_NtkCollectCioNames(Abc_Ntk_t *pNtk, int fCollectCos)
Definition: abcNames.c:278
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Abc_NtkCiNum(Abc_Ntk_t *pNtk)
Definition: abc.h:287
#define Abc_NtkForEachCo(pNtk, pCo, i)
Definition: abc.h:519
static abctime Abc_Clock()
Definition: abc_global.h:279
DdNode * Extra_bddSpaceReduce(DdManager *dd, DdNode *bFunc, DdNode *bCanonVars)
Definition: extraBddAuto.c:337
DdNode * Extra_bddSpaceCanonVars(DdManager *dd, DdNode *bSpace)
Definition: extraBddAuto.c:316
static int Abc_NtkCoNum(Abc_Ntk_t *pNtk)
Definition: abc.h:288
int Cudd_ReadSize(DdManager *dd)
Definition: cuddAPI.c:1441
DdNode * Extra_bddSpaceEquations(DdManager *dd, DdNode *bSpace)
Definition: extraBddAuto.c:361
static void * Abc_ObjGlobalBdd(Abc_Obj_t *pObj)
Definition: abc.h:431
ABC_DLL void * Abc_NtkFreeGlobalBdds(Abc_Ntk_t *pNtk, int fFreeMan)
Definition: abcNtbdd.c:476
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
static ABC_NAMESPACE_IMPL_START void Abc_NtkAutoPrintAll(DdManager *dd, int nInputs, DdNode *pbOutputs[], int nOutputs, char *pInputNames[], char *pOutputNames[], int fNaive)
DECLARATIONS ///.
Definition: abcAuto.c:119
static void Abc_NtkAutoPrintOne(DdManager *dd, int nInputs, DdNode *pbOutputs[], int Output, char *pInputNames[], char *pOutputNames[], int fNaive)
Definition: abcAuto.c:214
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
static void * Abc_NtkGlobalBddMan(Abc_Ntk_t *pNtk)
Definition: abc.h:429
#define ABC_FREE(obj)
Definition: abc_global.h:232
unsigned int Cudd_ReadKeys(DdManager *dd)
Definition: cuddAPI.c:1626
void Abc_NtkAutoPrint(Abc_Ntk_t *pNtk, int Output, int fNaive, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition: abcAuto.c:49
int Cudd_zddVarsFromBddVars(DdManager *dd, int multiplicity)
Definition: cuddAPI.c:519
#define assert(ex)
Definition: util_old.h:213
DdNode * Extra_bddSpaceFromFunctionFast(DdManager *dd, DdNode *bFunc)
Definition: extraBddAuto.c:153
ABC_DLL void * Abc_NtkBuildGlobalBdds(Abc_Ntk_t *pNtk, int fBddSizeMax, int fDropInternal, int fReorder, int fVerbose)
Definition: abcNtbdd.c:251
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
unsigned int Cudd_ReadDead(DdManager *dd)
Definition: cuddAPI.c:1646
int Extra_Base2LogDouble(double Num)
Definition: extraUtilMisc.c:74
ABC_INT64_T abctime
Definition: abc_global.h:278
int Cudd_SupportSize(DdManager *dd, DdNode *f)
Definition: cuddUtil.c:857
static void ** Vec_PtrArray(Vec_Ptr_t *p)
Definition: vecPtr.h:279
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223