diff options
Diffstat (limited to 'src/opt/lpk/lpkInt.h')
| -rw-r--r-- | src/opt/lpk/lpkInt.h | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h new file mode 100644 index 00000000..960599e4 --- /dev/null +++ b/src/opt/lpk/lpkInt.h @@ -0,0 +1,246 @@ +/**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 + Vec_Ptr_t * vLeaves; + // truth table representation + Vec_Ptr_t * vTtElems; // elementary truth tables + Vec_Ptr_t * vTtNodes; // storage for temporary truth tables of the nodes + Vec_Int_t * vMemory; + Vec_Int_t * vBddDir; + Vec_Int_t * vBddInv; + unsigned puSupps[32]; // the supports of the cofactors + unsigned * ppTruths[5][16]; + // 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 nMuxes; + int nDsds; + int nTotalNets; + int nTotalNets2; + int nTotalNodes; + int nTotalNodes2; + // counter of non-DSD blocks + int nBlocks[17]; + // runtime + int timeCuts; + int timeTruth; + int timeSupps; + int timeTruth2; + int timeTruth3; + int timeEval; + int timeMap; + int timeOther; + int timeTotal; + // runtime of eval + int timeEvalMuxAn; + int timeEvalMuxSp; + int timeEvalDsdAn; + int timeEvalDsdSp; + +}; + + +// internal representation of the function to be decomposed +typedef struct Lpk_Fun_t_ Lpk_Fun_t; +struct Lpk_Fun_t_ +{ + Vec_Ptr_t * vNodes; // the array of leaves and decomposition nodes + unsigned Id : 7; // the ID of this node + unsigned nVars : 5; // the number of variables + unsigned nLutK : 4; // the number of LUT inputs + unsigned nAreaLim : 5; // the area limit (the largest allowed) + unsigned nDelayLim : 9; // the delay limit (the largest allowed) + unsigned fSupports : 1; // supports of cofactors were precomputed + unsigned fMark : 1; // marks the MUX-based dec + unsigned uSupp; // the support of this component + unsigned puSupps[32]; // the supports of the cofactors + char pDelays[16]; // the delays of the inputs + char pFanins[16]; // the fanins of this function + unsigned pTruth[0]; // the truth table (contains room for three truth tables) +}; + +// preliminary decomposition result +typedef struct Lpk_Res_t_ Lpk_Res_t; +struct Lpk_Res_t_ +{ + int nBSVars; // the number of bound set variables + unsigned BSVars; // the bound set + int nCofVars; // the number of cofactoring variables + char pCofVars[4]; // the cofactoring variables + int nSuppSizeS; // support size of the smaller (decomposed) function + int nSuppSizeL; // support size of the larger (composition) function + int DelayEst; // estimated delay of the decomposition + int AreaEst; // estimated area of the decomposition + int Variable; // variable in MUX decomposition + int Polarity; // polarity in MUX decomposition +}; + +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-- ) +#define Lpk_SuppForEachVar( Supp, Var )\ + for ( Var = 0; Var < 16; Var++ )\ + if ( !(Supp & (1<<Var)) ) {} else + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== lpkAbcDec.c ============================================================*/ +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 ); +/*=== lpkAbcDsd.c ============================================================*/ +extern Lpk_Res_t * Lpk_DsdAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p, int nShared ); +extern Lpk_Fun_t * Lpk_DsdSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, char * pCofVars, int nCofVars, unsigned uBoundSet ); +/*=== lpkAbcMux.c ============================================================*/ +extern Lpk_Res_t * Lpk_MuxAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p ); +extern Lpk_Fun_t * Lpk_MuxSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, int Var, int Pol ); +/*=== lpkAbcUtil.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 int Lpk_FunSuppMinimize( Lpk_Fun_t * p ); +extern void Lpk_FunComputeCofSupps( Lpk_Fun_t * p ); +extern int Lpk_SuppDelay( unsigned uSupp, char * pDelays ); +extern int Lpk_SuppToVars( unsigned uBoundSet, char * pVars ); + + +/*=== lpkCut.c =========================================================*/ +extern unsigned * Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fInv ); +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 /// +//////////////////////////////////////////////////////////////////////// + |