1 /**CFile****************************************************************
2
3 FileName [lpkInt.h]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Fast Boolean matching for LUT structures.]
8
9 Synopsis [Internal declarations.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: lpkInt.h,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #ifndef ABC__opt__lpk__lpkInt_h
22 #define ABC__opt__lpk__lpkInt_h
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// INCLUDES ///
27 ////////////////////////////////////////////////////////////////////////
28
29 #include "base/abc/abc.h"
30 #include "bool/kit/kit.h"
31 #include "map/if/if.h"
32 #include "lpk.h"
33
34 ////////////////////////////////////////////////////////////////////////
35 /// PARAMETERS ///
36 ////////////////////////////////////////////////////////////////////////
37
38
39
40 ABC_NAMESPACE_HEADER_START
41
42
43 ////////////////////////////////////////////////////////////////////////
44 /// BASIC TYPES ///
45 ////////////////////////////////////////////////////////////////////////
46
47 #define LPK_SIZE_MAX 100 // the largest size of the function
48 #define LPK_CUTS_MAX 10000 // the largest number of cuts considered
49
50 typedef struct Lpk_Man_t_ Lpk_Man_t;
51 typedef struct Lpk_Cut_t_ Lpk_Cut_t;
52
53 struct Lpk_Cut_t_
54 {
55 unsigned nLeaves : 6; // (L) the number of leaves
56 unsigned nNodes : 6; // (M) the number of nodes
57 unsigned nNodesDup : 6; // (Q) nodes outside of MFFC
58 unsigned nLuts : 6; // (N) the number of LUTs to try
59 unsigned unused : 6; // unused
60 unsigned fHasDsd : 1; // set to 1 if the cut has structural DSD (and so cannot be used)
61 unsigned fMark : 1; // multipurpose mark
62 unsigned uSign[2]; // the signature
63 float Weight; // the weight of the cut: (M - Q)/N(V) (the larger the better)
64 int Gain; // the gain achieved using this cut
65 int pLeaves[LPK_SIZE_MAX]; // the leaves of the cut
66 int pNodes[LPK_SIZE_MAX]; // the nodes of the cut
67 };
68
69 struct Lpk_Man_t_
70 {
71 // parameters
72 Lpk_Par_t * pPars; // the set of parameters
73 // current representation
74 Abc_Ntk_t * pNtk; // the network
75 Abc_Obj_t * pObj; // the node to resynthesize
76 // cut representation
77 int nMffc; // the size of MFFC of the node
78 int nCuts; // the total number of cuts
79 int nCutsMax; // the largest possible number of cuts
80 int nEvals; // the number of good cuts
81 Lpk_Cut_t pCuts[LPK_CUTS_MAX]; // the storage for cuts
82 int pEvals[LPK_CUTS_MAX]; // the good cuts
83 // visited nodes
84 Vec_Vec_t * vVisited;
85 // mapping manager
86 If_Man_t * pIfMan;
87 Vec_Int_t * vCover;
88 Vec_Vec_t * vLevels;
89 // temporary variables
90 int fCofactoring; // working in the cofactoring mode
91 int fCalledOnce; // limits the depth of MUX cofactoring
92 int nCalledSRed; // the number of called to SRed
93 int pRefs[LPK_SIZE_MAX]; // fanin reference counters
94 int pCands[LPK_SIZE_MAX]; // internal nodes pointing only to the leaves
95 Vec_Ptr_t * vLeaves;
96 Vec_Ptr_t * vTemp;
97 // truth table representation
98 Vec_Ptr_t * vTtElems; // elementary truth tables
99 Vec_Ptr_t * vTtNodes; // storage for temporary truth tables of the nodes
100 Vec_Int_t * vMemory;
101 Vec_Int_t * vBddDir;
102 Vec_Int_t * vBddInv;
103 unsigned puSupps[32]; // the supports of the cofactors
104 unsigned * ppTruths[5][16];
105 // variable sets
106 Vec_Int_t * vSets[8];
107 Kit_DsdMan_t* pDsdMan;
108 // statistics
109 int nNodesTotal; // total number of nodes
110 int nNodesOver; // nodes with cuts over the limit
111 int nCutsTotal; // total number of cuts
112 int nCutsUseful; // useful cuts
113 int nGainTotal; // the gain in LUTs
114 int nChanges; // the number of changed nodes
115 int nBenefited; // the number of gainful that benefited from decomposition
116 int nMuxes;
117 int nDsds;
118 int nTotalNets;
119 int nTotalNets2;
120 int nTotalNodes;
121 int nTotalNodes2;
122 // counter of non-DSD blocks
123 int nBlocks[17];
124 // runtime
125 abctime timeCuts;
126 abctime timeTruth;
127 abctime timeSupps;
128 abctime timeTruth2;
129 abctime timeTruth3;
130 abctime timeEval;
131 abctime timeMap;
132 abctime timeOther;
133 abctime timeTotal;
134 // runtime of eval
135 abctime timeEvalMuxAn;
136 abctime timeEvalMuxSp;
137 abctime timeEvalDsdAn;
138 abctime timeEvalDsdSp;
139
140 };
141
142
143 // internal representation of the function to be decomposed
144 typedef struct Lpk_Fun_t_ Lpk_Fun_t;
145 struct Lpk_Fun_t_
146 {
147 Vec_Ptr_t * vNodes; // the array of leaves and decomposition nodes
148 unsigned Id : 7; // the ID of this node
149 unsigned nVars : 5; // the number of variables
150 unsigned nLutK : 4; // the number of LUT inputs
151 unsigned nAreaLim : 14; // the area limit (the largest allowed)
152 unsigned fSupports : 1; // supports of cofactors were precomputed
153 unsigned fMark : 1; // marks the MUX-based dec
154 unsigned uSupp; // the support of this component
155 unsigned puSupps[32]; // the supports of the cofactors
156 unsigned nDelayLim; // the delay limit (the largest allowed)
157 int pDelays[16]; // the delays of the inputs
158 char pFanins[16]; // the fanins of this function
159 unsigned pTruth[0]; // the truth table (contains room for three truth tables)
160 };
161
162 // preliminary decomposition result
163 typedef struct Lpk_Res_t_ Lpk_Res_t;
164 struct Lpk_Res_t_
165 {
166 int nBSVars; // the number of bound set variables
167 unsigned BSVars; // the bound set
168 int nCofVars; // the number of cofactoring variables
169 char pCofVars[4]; // the cofactoring variables
170 int nSuppSizeS; // support size of the smaller (decomposed) function
171 int nSuppSizeL; // support size of the larger (composition) function
172 int DelayEst; // estimated delay of the decomposition
173 int AreaEst; // estimated area of the decomposition
174 int Variable; // variable in MUX decomposition
175 int Polarity; // polarity in MUX decomposition
176 };
177
Lpk_LutNumVars(int nLutsLim,int nLutK)178 static inline int Lpk_LutNumVars( int nLutsLim, int nLutK ) { return nLutsLim * (nLutK - 1) + 1; }
Lpk_LutNumLuts(int nVarsMax,int nLutK)179 static inline int Lpk_LutNumLuts( int nVarsMax, int nLutK ) { return (nVarsMax - 1) / (nLutK - 1) + (int)((nVarsMax - 1) % (nLutK - 1) > 0); }
Lpk_FunTruth(Lpk_Fun_t * p,int Num)180 static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num ) { assert( Num < 3 ); return p->pTruth + Kit_TruthWordNum(p->nVars) * Num; }
181
182 ////////////////////////////////////////////////////////////////////////
183 /// MACRO DEFINITIONS ///
184 ////////////////////////////////////////////////////////////////////////
185
186 ////////////////////////////////////////////////////////////////////////
187 /// ITERATORS ///
188 ////////////////////////////////////////////////////////////////////////
189
190 #define Lpk_CutForEachLeaf( pNtk, pCut, pObj, i ) \
191 for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ )
192 #define Lpk_CutForEachNode( pNtk, pCut, pObj, i ) \
193 for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ )
194 #define Lpk_CutForEachNodeReverse( pNtk, pCut, pObj, i ) \
195 for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- )
196 #define Lpk_SuppForEachVar( Supp, Var )\
197 for ( Var = 0; Var < 16; Var++ )\
198 if ( !(Supp & (1<<Var)) ) {} else
199
200 ////////////////////////////////////////////////////////////////////////
201 /// FUNCTION DECLARATIONS ///
202 ////////////////////////////////////////////////////////////////////////
203
204 /*=== lpkAbcDec.c ============================================================*/
205 extern Abc_Obj_t * Lpk_Decompose( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim );
206 /*=== lpkAbcDsd.c ============================================================*/
207 extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p, int nShared );
208 extern Lpk_Fun_t * Lpk_DsdSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet );
209 /*=== lpkAbcMux.c ============================================================*/
210 extern Lpk_Res_t * Lpk_MuxAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p );
211 extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, int Var, int Pol );
212 /*=== lpkAbcUtil.c ============================================================*/
213 extern Lpk_Fun_t * Lpk_FunAlloc( int nVars );
214 extern void Lpk_FunFree( Lpk_Fun_t * p );
215 extern Lpk_Fun_t * Lpk_FunCreate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim );
216 extern Lpk_Fun_t * Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth );
217 extern int Lpk_FunSuppMinimize( Lpk_Fun_t * p );
218 extern void Lpk_FunComputeCofSupps( Lpk_Fun_t * p );
219 extern int Lpk_SuppDelay( unsigned uSupp, int * pDelays );
220 extern int Lpk_SuppToVars( unsigned uBoundSet, char * pVars );
221
222
223 /*=== lpkCut.c =========================================================*/
224 extern unsigned * Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fInv );
225 extern int Lpk_NodeCuts( Lpk_Man_t * p );
226 /*=== lpkMap.c =========================================================*/
227 extern Lpk_Man_t * Lpk_ManStart( Lpk_Par_t * pPars );
228 extern void Lpk_ManStop( Lpk_Man_t * p );
229 /*=== lpkMap.c =========================================================*/
230 extern If_Obj_t * Lpk_MapPrime( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
231 extern If_Obj_t * Lpk_MapTree_rec( Lpk_Man_t * p, Kit_DsdNtk_t * pNtk, If_Obj_t ** ppLeaves, int iLit, If_Obj_t * pResult );
232 /*=== lpkMulti.c =======================================================*/
233 extern If_Obj_t * Lpk_MapTreeMulti( Lpk_Man_t * p, unsigned * pTruth, int nLeaves, If_Obj_t ** ppLeaves );
234 /*=== lpkMux.c =========================================================*/
235 extern If_Obj_t * Lpk_MapTreeMux_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
236 extern If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
237 /*=== lpkSets.c =========================================================*/
238 extern unsigned Lpk_MapSuppRedDecSelect( Lpk_Man_t * p, unsigned * pTruth, int nVars, int * piVar, int * piVarReused );
239
240
241
242 ABC_NAMESPACE_HEADER_END
243
244
245
246 #endif
247
248 ////////////////////////////////////////////////////////////////////////
249 /// END OF FILE ///
250 ////////////////////////////////////////////////////////////////////////
251
252