/**CFile****************************************************************
FileName [fpgaInt.h]
PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
Synopsis [Technology mapping for variable-size-LUT FPGAs.]
Author [MVSIS Group]
Affiliation [UC Berkeley]
Date [Ver. 2.0. Started - August 18, 2004.]
Revision [$Id: fpgaInt.h,v 1.8 2004/09/30 21:18:10 satrajit Exp $]
***********************************************************************/
#ifndef ABC__map__fpga__fpgaInt_h
#define ABC__map__fpga__fpgaInt_h
////////////////////////////////////////////////////////////////////////
/// INCLUDES ///
////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc/extra/extra.h"
#include "fpga.h"
ABC_NAMESPACE_HEADER_START
////////////////////////////////////////////////////////////////////////
/// PARAMETERS ///
////////////////////////////////////////////////////////////////////////
// uncomment to have fanouts represented in the mapping graph
//#define FPGA_ALLOCATE_FANOUT 1
////////////////////////////////////////////////////////////////////////
/// MACRO DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
#ifdef _WIN32
#define inline __inline // compatible with MS VS 6.0
#endif
// the maximum number of cut leaves (currently does not work for 7)
#define FPGA_MAX_LEAVES 6
// the bit masks
#define FPGA_MASK(n) ((~((unsigned)0)) >> (32-(n)))
#define FPGA_FULL (~((unsigned)0))
#define FPGA_NO_VAR (-9999.0)
#define FPGA_NUM_BYTES(n) (((n)/16 + (((n)%16) > 0))*16)
// maximum/minimum operators
#define FPGA_MIN(a,b) (((a) < (b))? (a) : (b))
#define FPGA_MAX(a,b) (((a) > (b))? (a) : (b))
// the small and large numbers (min/max float are 1.17e-38/3.40e+38)
#define FPGA_FLOAT_LARGE ((float)1.0e+20)
#define FPGA_FLOAT_SMALL ((float)1.0e-20)
#define FPGA_INT_LARGE (10000000)
// the macro to compute the signature
#define FPGA_SEQ_SIGN(p) (1 << (((ABC_PTRUINT_T)p)%31));
// internal macros to work with cuts
#define Fpga_CutIsComplement(p) (((int)((ABC_PTRUINT_T)(p) & 01)))
#define Fpga_CutRegular(p) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) & ~01))
#define Fpga_CutNot(p) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ 01))
#define Fpga_CutNotCond(p,c) ((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ (c)))
// the cut nodes
#define Fpga_SeqIsComplement( p ) (((int)((ABC_PTRUINT_T) (p) & 01)))
#define Fpga_SeqRegular( p ) ((Fpga_Node_t *)((ABC_PTRUINT_T)(p) & ~015))
#define Fpga_SeqIndex( p ) ((((ABC_PTRUINT_T)(p)) >> 1) & 07)
#define Fpga_SeqIndexCreate( p, Ind ) (((ABC_PTRUINT_T)(p)) | (1 << (((ABC_PTRUINT_T)(Ind)) & 07)))
// internal macros for referencing of nodes
#define Fpga_NodeReadRef(p) ((Fpga_Regular(p))->nRefs)
#define Fpga_NodeRef(p) ((Fpga_Regular(p))->nRefs++)
// returns the complemented attribute of the node
#define Fpga_NodeIsSimComplement(p) (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv)
// generating random unsigned (#define RAND_MAX 0x7fff)
#define FPGA_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))
////////////////////////////////////////////////////////////////////////
/// STRUCTURE DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
// the mapping manager
struct Fpga_ManStruct_t_
{
// the mapping graph
Fpga_Node_t ** pBins; // the table of nodes hashed by their children
int nBins; // the size of the table
Fpga_Node_t ** pInputs; // the array of inputs
int nInputs; // the number of inputs
Fpga_Node_t ** pOutputs; // the array of outputs
int nOutputs; // the number of outputs
int nNodes; // the total number of nodes
int nLatches; // the number of latches in the circuit
Fpga_Node_t * pConst1; // the constant 1 node
Fpga_NodeVec_t * vNodesAll; // the nodes by number
Fpga_NodeVec_t * vAnds; // the nodes reachable from COs
Fpga_NodeVec_t * vMapping; // the nodes used in the current mapping
// info about the original circuit
char * pFileName; // the file name
char ** ppOutputNames; // the primary output names
float * pInputArrivals;// the PI arrival times
// mapping parameters
int nVarsMax; // the max number of variables
int fAreaRecovery; // the flag to use area flow as the first parameter
int fVerbose; // the verbosiness flag
int fSwitching; // minimize the switching activity (instead of area)
int fLatchPaths; // optimize latch paths for delay, other paths for area
int nTravIds; // the counter of traversal IDs
float DelayTarget; // the target required times
// support of choice nodes
int nChoiceNodes; // the number of choice nodes
int nChoices; // the number of all choices
int nCanons;
int nMatches;
// the supergate library
Fpga_LutLib_t * pLutLib; // the current LUT library
// the memory managers
Extra_MmFixed_t * mmNodes; // the memory manager for nodes
Extra_MmFixed_t * mmCuts; // the memory manager for cuts
// resynthesis parameters
int fResynthesis; // the resynthesis flag
float fRequiredGlo; // the global required times
float fRequiredShift;// the shift of the required times
float fRequiredStart;// the starting global required times
float fRequiredGain; // the reduction in delay
float fAreaGlo; // the total area
float fAreaGain; // the reduction in area
float fEpsilon; // the epsilon used to compare floats
float fDelayWindow; // the delay window for delay-oriented resynthesis
float DelayLimit; // for resynthesis
float AreaLimit; // for resynthesis
float TimeLimit; // for resynthesis
// runtime statistics
clock_t timeToMap; // time to transfer to the mapping structure
clock_t timeCuts; // time to compute k-feasible cuts
clock_t timeTruth; // time to compute the truth table for each cut
clock_t timeMatch; // time to perform matching for each node
clock_t timeRecover; // time to perform area recovery
clock_t timeToNet; // time to transfer back to the network
clock_t timeTotal; // the total mapping time
clock_t time1; // time to transfer to the mapping structure
clock_t time2; // time to transfer to the mapping structure
};
// the LUT library
struct Fpga_LutLibStruct_t_
{
char * pName; // the name of the LUT library
int LutMax; // the maximum LUT size
int fVarPinDelays; // set to 1 if variable pin delays are specified
float pLutAreas[FPGA_MAX_LUTSIZE+1]; // the areas of LUTs
float pLutDelays[FPGA_MAX_LUTSIZE+1][FPGA_MAX_LUTSIZE+1];// the delays of LUTs
};
// the mapping node
struct Fpga_NodeStruct_t_
{
// general information about the node
Fpga_Node_t * pNext; // the next node in the hash table
Fpga_Node_t * pLevel; // the next node in the linked list by level
int Num; // the unique number of this node
int NumA; // the unique number of this node
int Num2; // the temporary number of this node
int nRefs; // the number of references (fanouts) of the given node
unsigned fMark0 : 1; // the mark used for traversals
unsigned fMark1 : 1; // the mark used for traversals
unsigned fInv : 1; // the complemented attribute for the equivalent nodes
unsigned Value : 2; // the value of the nodes
unsigned fUsed : 1; // the flag indicating that the node is used in the mapping
unsigned fTemp : 1; // unused
unsigned Level :11; // the level of the given node
unsigned uData :14; // used to mark the fanins, for which resynthesis was tried
int TravId;
// the successors of this node
Fpga_Node_t * p1; // the first child
Fpga_Node_t * p2; // the second child
Fpga_Node_t * pNextE; // the next functionally equivalent node
Fpga_Node_t * pRepr; // the representative of the functionally equivalent class
#ifdef FPGA_ALLOCATE_FANOUT
// representation of node's fanouts
Fpga_Node_t * pFanPivot; // the first fanout of this node
Fpga_Node_t * pFanFanin1; // the next fanout of p1
Fpga_Node_t * pFanFanin2; // the next fanout of p2
// Fpga_NodeVec_t * vFanouts; // the array of fanouts of the gate
#endif
// the delay information
float tRequired; // the best area flow
float aEstFanouts; // the fanout estimation
float Switching; // the probability of switching
int LValue; // the l-value of the node
short nLatches1; // the number of latches on the first edge
short nLatches2; // the number of latches on the second edge
// cut information
Fpga_Cut_t * pCutBest; // the best mapping
Fpga_Cut_t * pCutOld; // the old mapping
Fpga_Cut_t * pCuts; // mapping choices for the node (elementary comes first)
Fpga_Cut_t * pCutsN; // mapping choices for the node (elementary comes first)
// misc information
char * pData0; // temporary storage for the corresponding network node
};
// the cuts used for matching
struct Fpga_CutStruct_t_
{
Fpga_Cut_t * pOne; // the father of this cut
Fpga_Cut_t * pTwo; // the mother of this cut
Fpga_Node_t * pRoot; // the root of the cut
Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]; // the leaves of this cut
float fLevel; // the average level of the fanins
unsigned uSign; // signature for quick comparison
char fMark; // the mark to denote visited cut
char Phase; // the mark to denote complemented cut
char nLeaves; // the number of leaves of this cut
char nVolume; // the volume of this cut
float tArrival; // the arrival time
float aFlow; // the area flow of the cut
Fpga_Cut_t * pNext; // the pointer to the next cut in the list
};
// the vector of nodes
struct Fpga_NodeVecStruct_t_
{
Fpga_Node_t ** pArray; // the array of nodes
int nSize; // the number of entries in the array
int nCap; // the number of allocated entries
};
// getting hold of the next fanout of the node
#define Fpga_NodeReadNextFanout( pNode, pFanout ) \
( ( pFanout == NULL )? NULL : \
((Fpga_Regular((pFanout)->p1) == (pNode))? \
(pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) )
// getting hold of the place where the next fanout will be attached
#define Fpga_NodeReadNextFanoutPlace( pNode, pFanout ) \
( (Fpga_Regular((pFanout)->p1) == (pNode))? \
&(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 )
// iterator through the fanouts of the node
#define Fpga_NodeForEachFanout( pNode, pFanout ) \
for ( pFanout = (pNode)->pFanPivot; pFanout; \
pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) )
// safe iterator through the fanouts of the node
#define Fpga_NodeForEachFanoutSafe( pNode, pFanout, pFanout2 ) \
for ( pFanout = (pNode)->pFanPivot, \
pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout); \
pFanout; \
pFanout = pFanout2, \
pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) )
static inline int Fpga_FloatMoreThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 + p->fEpsilon; }
static inline int Fpga_FloatLessThan( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 < Arg2 - p->fEpsilon; }
static inline int Fpga_FloatEqual( Fpga_Man_t * p, float Arg1, float Arg2 ) { return Arg1 > Arg2 - p->fEpsilon && Arg1 < Arg2 + p->fEpsilon; }
////////////////////////////////////////////////////////////////////////
/// GLOBAL VARIABLES ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/*=== fpgaCut.c ===============================================================*/
extern void Fpga_MappingCuts( Fpga_Man_t * p );
extern void Fpga_MappingCreatePiCuts( Fpga_Man_t * p );
extern int Fpga_CutCountAll( Fpga_Man_t * pMan );
/*=== fpgaCutUtils.c ===============================================================*/
extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p );
extern Fpga_Cut_t * Fpga_CutDup( Fpga_Man_t * p, Fpga_Cut_t * pCutOld );
extern void Fpga_CutFree( Fpga_Man_t * p, Fpga_Cut_t * pCut );
extern void Fpga_CutPrint( Fpga_Man_t * p, Fpga_Node_t * pRoot, Fpga_Cut_t * pCut );
extern Fpga_Cut_t * Fpga_CutCreateSimple( Fpga_Man_t * p, Fpga_Node_t * pNode );
extern float Fpga_CutGetRootArea( Fpga_Man_t * p, Fpga_Cut_t * pCut );
extern Fpga_Cut_t * Fpga_CutListAppend( Fpga_Cut_t * pSetAll, Fpga_Cut_t * pSets );
extern void Fpga_CutListRecycle( Fpga_Man_t * p, Fpga_Cut_t * pSetList, Fpga_Cut_t * pSave );
extern int Fpga_CutListCount( Fpga_Cut_t * pSets );
extern void Fpga_CutRemoveFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut );
extern void Fpga_CutInsertFanouts( Fpga_Man_t * p, Fpga_Node_t * pNode, Fpga_Cut_t * pCut );
extern float Fpga_CutGetAreaRefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
extern float Fpga_CutGetAreaDerefed( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
extern float Fpga_CutRef( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts );
extern float Fpga_CutDeref( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts );
extern float Fpga_CutGetAreaFlow( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
extern void Fpga_CutGetParameters( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
/*=== fraigFanout.c =============================================================*/
extern void Fpga_NodeAddFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanout );
extern void Fpga_NodeRemoveFaninFanout( Fpga_Node_t * pFanin, Fpga_Node_t * pFanoutToRemove );
extern int Fpga_NodeGetFanoutNum( Fpga_Node_t * pNode );
/*=== fpgaLib.c ============================================================*/
extern Fpga_LutLib_t * Fpga_LutLibRead( char * FileName, int fVerbose );
extern void Fpga_LutLibFree( Fpga_LutLib_t * p );
extern void Fpga_LutLibPrint( Fpga_LutLib_t * pLutLib );
extern int Fpga_LutLibDelaysAreDiscrete( Fpga_LutLib_t * pLutLib );
/*=== fpgaMatch.c ===============================================================*/
extern int Fpga_MappingMatches( Fpga_Man_t * p, int fDelayOriented );
extern int Fpga_MappingMatchesArea( Fpga_Man_t * p );
extern int Fpga_MappingMatchesSwitch( Fpga_Man_t * p );
/*=== fpgaShow.c =============================================================*/
extern void Fpga_MappingShow( Fpga_Man_t * pMan, char * pFileName );
extern void Fpga_MappingShowNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppRoots, int nRoots, char * pFileName );
/*=== fpgaSwitch.c =============================================================*/
extern float Fpga_CutGetSwitchDerefed( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut );
extern float Fpga_CutRefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts );
extern float Fpga_CutDerefSwitch( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Cut_t * pCut, int fFanouts );
extern float Fpga_MappingGetSwitching( Fpga_Man_t * pMan, Fpga_NodeVec_t * vMapping );
/*=== fpgaTime.c ===============================================================*/
extern float Fpga_TimeCutComputeArrival( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
extern float Fpga_TimeCutComputeArrival_rec( Fpga_Man_t * pMan, Fpga_Cut_t * pCut );
extern float Fpga_TimeComputeArrivalMax( Fpga_Man_t * p );
extern void Fpga_TimeComputeRequiredGlobal( Fpga_Man_t * p, int fFirstTime );
extern void Fpga_TimeComputeRequired( Fpga_Man_t * p, float fRequired );
extern void Fpga_TimePropagateRequired( Fpga_Man_t * p, Fpga_NodeVec_t * vNodes );
extern void Fpga_TimePropagateArrival( Fpga_Man_t * p );
/*=== fpgaVec.c =============================================================*/
extern Fpga_NodeVec_t * Fpga_NodeVecAlloc( int nCap );
extern void Fpga_NodeVecFree( Fpga_NodeVec_t * p );
extern Fpga_Node_t ** Fpga_NodeVecReadArray( Fpga_NodeVec_t * p );
extern int Fpga_NodeVecReadSize( Fpga_NodeVec_t * p );
extern void Fpga_NodeVecGrow( Fpga_NodeVec_t * p, int nCapMin );
extern void Fpga_NodeVecShrink( Fpga_NodeVec_t * p, int nSizeNew );
extern void Fpga_NodeVecClear( Fpga_NodeVec_t * p );
extern void Fpga_NodeVecPush( Fpga_NodeVec_t * p, Fpga_Node_t * Entry );
extern int Fpga_NodeVecPushUnique( Fpga_NodeVec_t * p, Fpga_Node_t * Entry );
extern Fpga_Node_t * Fpga_NodeVecPop( Fpga_NodeVec_t * p );
extern void Fpga_NodeVecWriteEntry( Fpga_NodeVec_t * p, int i, Fpga_Node_t * Entry );
extern Fpga_Node_t * Fpga_NodeVecReadEntry( Fpga_NodeVec_t * p, int i );
extern void Fpga_NodeVecSortByLevel( Fpga_NodeVec_t * p );
extern void Fpga_SortNodesByArrivalTimes( Fpga_NodeVec_t * p );
extern void Fpga_NodeVecUnion( Fpga_NodeVec_t * p, Fpga_NodeVec_t * p1, Fpga_NodeVec_t * p2 );
extern void Fpga_NodeVecPushOrder( Fpga_NodeVec_t * vNodes, Fpga_Node_t * pNode, int fIncreasing );
extern void Fpga_NodeVecReverse( Fpga_NodeVec_t * vNodes );
/*=== fpgaUtils.c ===============================================================*/
extern Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv );
extern Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv );
extern int Fpga_CountLevels( Fpga_Man_t * pMan );
extern float Fpga_MappingGetAreaFlow( Fpga_Man_t * p );
extern float Fpga_MappingArea( Fpga_Man_t * pMan );
extern float Fpga_MappingAreaTrav( Fpga_Man_t * pMan );
extern float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan );
extern void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p );
extern void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] );
extern void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax );
extern void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing );
extern Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels );
extern Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes );
extern int Fpga_MappingMaxLevel( Fpga_Man_t * pMan );
extern void Fpga_ManReportChoices( Fpga_Man_t * pMan );
extern void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan );
ABC_NAMESPACE_HEADER_END
#endif
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////