lpkInt.h

/**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 ABC__opt__lpk__lpkInt_h
#define ABC__opt__lpk__lpkInt_h


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

#include "base/abc/abc.h"
#include "bool/kit/kit.h"
#include "map/if/if.h"
#include "lpk.h"

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



ABC_NAMESPACE_HEADER_START
 

////////////////////////////////////////////////////////////////////////
///                         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
    clock_t      timeCuts;
    clock_t      timeTruth;
    clock_t      timeSupps;
    clock_t      timeTruth2;
    clock_t      timeTruth3;
    clock_t      timeEval;
    clock_t      timeMap;
    clock_t      timeOther;
    clock_t      timeTotal;
    // runtime of eval
    clock_t      timeEvalMuxAn;
    clock_t      timeEvalMuxSp;
    clock_t      timeEvalDsdAn;
    clock_t      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 );



ABC_NAMESPACE_HEADER_END



#endif

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