summaryrefslogtreecommitdiffstats
path: root/src/opt/lpk/lpkInt.h
blob: d04032efb8074194f4e3d7b31d6bee52b2e86441 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
/**CFile****************************************************************

  FileName    [lpkInt.h]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Fast Boolean matching for LUT structures.]

  Synopsis    [Internal declarations.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - April 28, 2007.]

  Revision    [$Id: lpkInt.h,v 1.00 2007/04/28 00:00:00 alanmi Exp $]

***********************************************************************/
 
#ifndef __LPK_INT_H__
#define __LPK_INT_H__

#ifdef __cplusplus
extern "C" {
#endif 

////////////////////////////////////////////////////////////////////////
///                          INCLUDES                                ///
////////////////////////////////////////////////////////////////////////

#include "abc.h"
#include "kit.h"
#include "if.h"
#include "lpk.h"

////////////////////////////////////////////////////////////////////////
///                         PARAMETERS                               ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                         BASIC TYPES                              ///
////////////////////////////////////////////////////////////////////////

#define LPK_SIZE_MAX             24     // the largest size of the function
#define LPK_CUTS_MAX            512     // the largest number of cuts considered

typedef struct Lpk_Man_t_ Lpk_Man_t;
typedef struct Lpk_Cut_t_ Lpk_Cut_t;

struct Lpk_Cut_t_
{
    unsigned     nLeaves       : 6;     // (L) the number of leaves
    unsigned     nNodes        : 6;     // (M) the number of nodes
    unsigned     nNodesDup     : 6;     // (Q) nodes outside of MFFC
    unsigned     nLuts         : 6;     // (N) the number of LUTs to try
    unsigned     unused        : 6;     // unused
    unsigned     fHasDsd       : 1;     // set to 1 if the cut has structural DSD (and so cannot be used)
    unsigned     fMark         : 1;     // multipurpose mark
    unsigned     uSign[2];              // the signature
    float        Weight;                // the weight of the cut: (M - Q)/N(V)   (the larger the better)
    int          Gain;                  // the gain achieved using this cut
    int          pLeaves[LPK_SIZE_MAX]; // the leaves of the cut
    int          pNodes[LPK_SIZE_MAX];  // the nodes of the cut
};

struct Lpk_Man_t_
{
    // parameters
    Lpk_Par_t *  pPars;                 // the set of parameters
    // current representation
    Abc_Ntk_t *  pNtk;                  // the network
    Abc_Obj_t *  pObj;                  // the node to resynthesize 
    // cut representation
    int          nMffc;                 // the size of MFFC of the node
    int          nCuts;                 // the total number of cuts    
    int          nCutsMax;              // the largest possible number of cuts
    int          nEvals;                // the number of good cuts
    Lpk_Cut_t    pCuts[LPK_CUTS_MAX];   // the storage for cuts
    int          pEvals[LPK_CUTS_MAX];  // the good cuts
    // visited nodes 
    Vec_Vec_t *  vVisited;
    // mapping manager
    If_Man_t *   pIfMan;
    Vec_Int_t *  vCover; 
    Vec_Vec_t *  vLevels;
    // temporary variables
    int          fCofactoring;          // working in the cofactoring mode
    int          fCalledOnce;           // limits the depth of MUX cofactoring
    int          nCalledSRed;           // the number of called to SRed
    int          pRefs[LPK_SIZE_MAX];   // fanin reference counters 
    int          pCands[LPK_SIZE_MAX];  // internal nodes pointing only to the leaves
    // truth table representation
    Vec_Ptr_t *  vTtElems;              // elementary truth tables
    Vec_Ptr_t *  vTtNodes;              // storage for temporary truth tables of the nodes 
    // variable sets
    Vec_Int_t *  vSets[8];
    Kit_DsdMan_t * pDsdMan;
    // statistics
    int          nNodesTotal;           // total number of nodes
    int          nNodesOver;            // nodes with cuts over the limit 
    int          nCutsTotal;            // total number of cuts
    int          nCutsUseful;           // useful cuts 
    int          nGainTotal;            // the gain in LUTs
    int          nChanges;              // the number of changed nodes
    int          nBenefited;            // the number of gainful that benefited from decomposition
    int          nTotalNets;
    int          nTotalNets2;
    // counter of non-DSD blocks
    int          nBlocks[17];
    // rutime
    int          timeCuts;
    int          timeTruth;
    int          timeEval;
    int          timeMap;
    int          timeOther;
    int          timeTotal;
};


// preliminary decomposition result
typedef struct Lpk_Res_t_ Lpk_Res_t;
struct Lpk_Res_t_
{
    int           nBSVars;
    unsigned      BSVars;
    int           nCofVars;
    char          pCofVars[4];
    int           nSuppSizeS;
    int           nSuppSizeL;
    int           DelayEst;
    int           AreaEst;
};

// function to be decomposed
typedef struct Lpk_Fun_t_ Lpk_Fun_t;
struct Lpk_Fun_t_
{
    Vec_Ptr_t *   vNodes;           // the array of all functions
    unsigned int  Id         :  5;  // the ID of this node
    unsigned int  nVars      :  5;  // the number of variables
    unsigned int  nLutK      :  4;  // the number of LUT inputs
    unsigned int  nAreaLim   :  8;  // the area limit (the largest allowed)
    unsigned int  nDelayLim  : 10;  // the delay limit (the largest allowed)
    char          pFanins[16];      // the fanins of this function
    char          pDelays[16];      // the delays of the inputs
    unsigned      uSupp;            // the support of this component
    unsigned      pTruth[0];        // the truth table (contains room for three truth tables)    
};

#define Lpk_SuppForEachVar( Supp, Var )\
    for ( Var = 0; Var < 16; Var++ )\
        if ( !(Supp & (1<<Var)) ) {} else

static inline int Lpk_LutNumVars( int nLutsLim, int nLutK )  { return  nLutsLim * (nLutK - 1) + 1;                                            }
static inline int Lpk_LutNumLuts( int nVarsMax, int nLutK )  { return (nVarsMax - 1) / (nLutK - 1) + (int)((nVarsMax - 1) % (nLutK - 1) > 0); }
    
static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num )  { assert( Num < 3 ); return p->pTruth + Kit_TruthWordNum(p->nVars) * Num; }


////////////////////////////////////////////////////////////////////////
///                      MACRO DEFINITIONS                           ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                           ITERATORS                              ///
////////////////////////////////////////////////////////////////////////

#define Lpk_CutForEachLeaf( pNtk, pCut, pObj, i )                                        \
    for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ )
#define Lpk_CutForEachNode( pNtk, pCut, pObj, i )                                        \
    for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ )
#define Lpk_CutForEachNodeReverse( pNtk, pCut, pObj, i )                                 \
    for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- )

////////////////////////////////////////////////////////////////////////
///                    FUNCTION DECLARATIONS                         ///
////////////////////////////////////////////////////////////////////////

/*=== lpkAbcCore.c ============================================================*/
extern Abc_Obj_t *    Lpk_LpkDecompose( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim );
/*=== lpkAbcFun.c ============================================================*/
extern Lpk_Fun_t *    Lpk_FunAlloc( int nVars );
extern void           Lpk_FunFree( Lpk_Fun_t * p );
extern Lpk_Fun_t *    Lpk_FunCreate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim );
extern Lpk_Fun_t *    Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth );
extern void           Lpk_FunSuppMinimize( Lpk_Fun_t * p );
extern int            Lpk_SuppDelay( unsigned uSupp, char * pDelays );
extern int            Lpk_SuppToVars( unsigned uBoundSet, char * pVars );
/*=== lpkAbcDsd.c ============================================================*/
extern Lpk_Res_t *    Lpk_FunAnalizeDsd( Lpk_Fun_t * p, int nCofDepth );
extern Lpk_Fun_t *    Lpk_FunSplitDsd( Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet );
/*=== lpkAbcMux.c ============================================================*/
extern int            Lpk_FunAnalizeMux( Lpk_Fun_t * p );
extern Lpk_Fun_t *    Lpk_FunSplitMux( Lpk_Fun_t * p, int VarPol );


/*=== lpkCut.c =========================================================*/
extern unsigned *     Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut );
extern int            Lpk_NodeCuts( Lpk_Man_t * p );
/*=== lpkMap.c =========================================================*/
extern Lpk_Man_t *    Lpk_ManStart( Lpk_Par_t * pPars );
extern void           Lpk_ManStop( Lpk_Man_t * p );
/*=== lpkMap.c =========================================================*/
extern If_Obj_t *     Lpk_MapPrime( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
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 );
/*=== lpkMulti.c =======================================================*/
extern If_Obj_t *     Lpk_MapTreeMulti( Lpk_Man_t * p, unsigned * pTruth, int nLeaves, If_Obj_t ** ppLeaves );
/*=== lpkMux.c =========================================================*/
extern If_Obj_t *     Lpk_MapTreeMux_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
extern If_Obj_t *     Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves );
/*=== lpkSets.c =========================================================*/
extern unsigned       Lpk_MapSuppRedDecSelect( Lpk_Man_t * p, unsigned * pTruth, int nVars, int * piVar, int * piVarReused );

#ifdef __cplusplus
}
#endif

#endif

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////