fpgaInt.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc/extra/extra.h"
#include "fpga.h"

Go to the source code of this file.

Data Structures
struct	Fpga_ManStruct_t_
	STRUCTURE DEFINITIONS ///. More...
struct	Fpga_LutLibStruct_t_
struct	Fpga_NodeStruct_t_
struct	Fpga_CutStruct_t_
struct	Fpga_NodeVecStruct_t_

Macros
#define	FPGA_MAX_LEAVES   6
	INCLUDES ///. More...
#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)
#define	FPGA_MIN(a, b)   (((a) < (b))? (a) : (b))
#define	FPGA_MAX(a, b)   (((a) > (b))? (a) : (b))
#define	FPGA_FLOAT_LARGE   ((float)1.0e+20)
#define	FPGA_FLOAT_SMALL   ((float)1.0e-20)
#define	FPGA_INT_LARGE   (10000000)
#define	FPGA_SEQ_SIGN(p)   (1 << (((ABC_PTRUINT_T)p)%31));
#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)))
#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)))
#define	Fpga_NodeReadRef(p)   ((Fpga_Regular(p))->nRefs)
#define	Fpga_NodeRef(p)   ((Fpga_Regular(p))->nRefs++)
#define	Fpga_NodeIsSimComplement(p)   (Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv)
#define	FPGA_RANDOM_UNSIGNED   ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))
#define	Fpga_NodeReadNextFanout(pNode, pFanout)
#define	Fpga_NodeReadNextFanoutPlace(pNode, pFanout)
#define	Fpga_NodeForEachFanout(pNode, pFanout)
#define	Fpga_NodeForEachFanoutSafe(pNode, pFanout, pFanout2)

Functions
static int	Fpga_FloatMoreThan (Fpga_Man_t *p, float Arg1, float Arg2)
static int	Fpga_FloatLessThan (Fpga_Man_t *p, float Arg1, float Arg2)
static int	Fpga_FloatEqual (Fpga_Man_t *p, float Arg1, float Arg2)
void	Fpga_MappingCuts (Fpga_Man_t *p)
	GLOBAL VARIABLES ///. More...
void	Fpga_MappingCreatePiCuts (Fpga_Man_t *p)
int	Fpga_CutCountAll (Fpga_Man_t *pMan)
Fpga_Cut_t *	Fpga_CutAlloc (Fpga_Man_t *p)
	DECLARATIONS ///. More...
Fpga_Cut_t *	Fpga_CutDup (Fpga_Man_t *p, Fpga_Cut_t *pCutOld)
void	Fpga_CutFree (Fpga_Man_t *p, Fpga_Cut_t *pCut)
void	Fpga_CutPrint (Fpga_Man_t *p, Fpga_Node_t *pRoot, Fpga_Cut_t *pCut)
Fpga_Cut_t *	Fpga_CutCreateSimple (Fpga_Man_t *p, Fpga_Node_t *pNode)
float	Fpga_CutGetRootArea (Fpga_Man_t *p, Fpga_Cut_t *pCut)
Fpga_Cut_t *	Fpga_CutListAppend (Fpga_Cut_t *pSetAll, Fpga_Cut_t *pSets)
void	Fpga_CutListRecycle (Fpga_Man_t *p, Fpga_Cut_t *pSetList, Fpga_Cut_t *pSave)
int	Fpga_CutListCount (Fpga_Cut_t *pSets)
void	Fpga_CutRemoveFanouts (Fpga_Man_t *p, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
void	Fpga_CutInsertFanouts (Fpga_Man_t *p, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
float	Fpga_CutGetAreaRefed (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float	Fpga_CutGetAreaDerefed (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float	Fpga_CutRef (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float	Fpga_CutDeref (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float	Fpga_CutGetAreaFlow (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
void	Fpga_CutGetParameters (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
void	Fpga_NodeAddFaninFanout (Fpga_Node_t *pFanin, Fpga_Node_t *pFanout)
void	Fpga_NodeRemoveFaninFanout (Fpga_Node_t *pFanin, Fpga_Node_t *pFanoutToRemove)
int	Fpga_NodeGetFanoutNum (Fpga_Node_t *pNode)
Fpga_LutLib_t *	Fpga_LutLibRead (char *FileName, int fVerbose)
void	Fpga_LutLibFree (Fpga_LutLib_t *p)
void	Fpga_LutLibPrint (Fpga_LutLib_t *pLutLib)
int	Fpga_LutLibDelaysAreDiscrete (Fpga_LutLib_t *pLutLib)
int	Fpga_MappingMatches (Fpga_Man_t *p, int fDelayOriented)
	FUNCTION DEFINITIONS ///. More...
int	Fpga_MappingMatchesArea (Fpga_Man_t *p)
int	Fpga_MappingMatchesSwitch (Fpga_Man_t *p)
void	Fpga_MappingShow (Fpga_Man_t *pMan, char *pFileName)
void	Fpga_MappingShowNodes (Fpga_Man_t *pMan, Fpga_Node_t **ppRoots, int nRoots, char *pFileName)
float	Fpga_CutGetSwitchDerefed (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut)
	DECLARATIONS ///. More...
float	Fpga_CutRefSwitch (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float	Fpga_CutDerefSwitch (Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Cut_t *pCut, int fFanouts)
float	Fpga_MappingGetSwitching (Fpga_Man_t *pMan, Fpga_NodeVec_t *vMapping)
float	Fpga_TimeCutComputeArrival (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
	DECLARATIONS ///. More...
float	Fpga_TimeCutComputeArrival_rec (Fpga_Man_t *pMan, Fpga_Cut_t *pCut)
float	Fpga_TimeComputeArrivalMax (Fpga_Man_t *p)
void	Fpga_TimeComputeRequiredGlobal (Fpga_Man_t *p, int fFirstTime)
void	Fpga_TimeComputeRequired (Fpga_Man_t *p, float fRequired)
void	Fpga_TimePropagateRequired (Fpga_Man_t *p, Fpga_NodeVec_t *vNodes)
void	Fpga_TimePropagateArrival (Fpga_Man_t *p)
Fpga_NodeVec_t *	Fpga_NodeVecAlloc (int nCap)
	FUNCTION DEFINITIONS ///. More...
void	Fpga_NodeVecFree (Fpga_NodeVec_t *p)
Fpga_Node_t **	Fpga_NodeVecReadArray (Fpga_NodeVec_t *p)
int	Fpga_NodeVecReadSize (Fpga_NodeVec_t *p)
void	Fpga_NodeVecGrow (Fpga_NodeVec_t *p, int nCapMin)
void	Fpga_NodeVecShrink (Fpga_NodeVec_t *p, int nSizeNew)
void	Fpga_NodeVecClear (Fpga_NodeVec_t *p)
void	Fpga_NodeVecPush (Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
int	Fpga_NodeVecPushUnique (Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
Fpga_Node_t *	Fpga_NodeVecPop (Fpga_NodeVec_t *p)
void	Fpga_NodeVecWriteEntry (Fpga_NodeVec_t *p, int i, Fpga_Node_t *Entry)
Fpga_Node_t *	Fpga_NodeVecReadEntry (Fpga_NodeVec_t *p, int i)
void	Fpga_NodeVecSortByLevel (Fpga_NodeVec_t *p)
void	Fpga_SortNodesByArrivalTimes (Fpga_NodeVec_t *p)
void	Fpga_NodeVecUnion (Fpga_NodeVec_t *p, Fpga_NodeVec_t *p1, Fpga_NodeVec_t *p2)
void	Fpga_NodeVecPushOrder (Fpga_NodeVec_t *vNodes, Fpga_Node_t *pNode, int fIncreasing)
void	Fpga_NodeVecReverse (Fpga_NodeVec_t *vNodes)
Fpga_NodeVec_t *	Fpga_MappingDfs (Fpga_Man_t *pMan, int fCollectEquiv)
	FUNCTION DEFINITIONS ///. More...
Fpga_NodeVec_t *	Fpga_MappingDfsNodes (Fpga_Man_t *pMan, Fpga_Node_t **ppNodes, int nNodes, int fEquiv)
int	Fpga_CountLevels (Fpga_Man_t *pMan)
float	Fpga_MappingGetAreaFlow (Fpga_Man_t *p)
float	Fpga_MappingArea (Fpga_Man_t *pMan)
float	Fpga_MappingAreaTrav (Fpga_Man_t *pMan)
float	Fpga_MappingSetRefsAndArea (Fpga_Man_t *pMan)
void	Fpga_MappingPrintOutputArrivals (Fpga_Man_t *p)
void	Fpga_MappingSetupTruthTables (unsigned uTruths[][2])
void	Fpga_MappingSetupMask (unsigned uMask[], int nVarsMax)
void	Fpga_MappingSortByLevel (Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes, int fIncreasing)
Fpga_NodeVec_t *	Fpga_DfsLim (Fpga_Man_t *pMan, Fpga_Node_t *pNode, int nLevels)
Fpga_NodeVec_t *	Fpga_MappingLevelize (Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes)
int	Fpga_MappingMaxLevel (Fpga_Man_t *pMan)
void	Fpga_ManReportChoices (Fpga_Man_t *pMan)
void	Fpga_MappingSetChoiceLevels (Fpga_Man_t *pMan)

Macro Definition Documentation

#define Fpga_CutIsComplement

(

p

)

(((int)((ABC_PTRUINT_T)(p) & 01)))

Definition at line 73 of file fpgaInt.h.

#define Fpga_CutNot

(

p

)

((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ 01))

Definition at line 75 of file fpgaInt.h.

#define Fpga_CutNotCond	(		p,
			c
	)		((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) ^ (c)))

Definition at line 76 of file fpgaInt.h.

#define Fpga_CutRegular

(

p

)

((Fpga_Cut_t *)((ABC_PTRUINT_T)(p) & ~01))

Definition at line 74 of file fpgaInt.h.

#define FPGA_FLOAT_LARGE   ((float)1.0e+20)

Definition at line 65 of file fpgaInt.h.

#define FPGA_FLOAT_SMALL   ((float)1.0e-20)

Definition at line 66 of file fpgaInt.h.

#define FPGA_FULL   (~((unsigned)0))

Definition at line 56 of file fpgaInt.h.

#define FPGA_INT_LARGE   (10000000)

Definition at line 67 of file fpgaInt.h.

#define FPGA_MASK

(

n

)

((~((unsigned)0)) >> (32-(n)))

Definition at line 55 of file fpgaInt.h.

#define FPGA_MAX	(		a,
			b
	)		(((a) > (b))? (a) : (b))

Definition at line 62 of file fpgaInt.h.

#define FPGA_MAX_LEAVES   6

INCLUDES ///.

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

]PARAMETERS ///MACRO DEFINITIONS ///

Definition at line 52 of file fpgaInt.h.

#define FPGA_MIN	(		a,
			b
	)		(((a) < (b))? (a) : (b))

Definition at line 61 of file fpgaInt.h.

#define FPGA_NO_VAR   (-9999.0)

Definition at line 57 of file fpgaInt.h.

#define Fpga_NodeForEachFanout	(		pNode,
			pFanout
	)

Value:

for ( pFanout = (pNode)->pFanPivot; pFanout;                 \
          pFanout = Fpga_NodeReadNextFanout(pNode, pFanout) )

Definition at line 269 of file fpgaInt.h.

#define Fpga_NodeForEachFanoutSafe	(		pNode,
			pFanout,
			pFanout2
	)

Value:

for ( pFanout  = (pNode)->pFanPivot,                         \
          pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout);    \
          pFanout;                                               \
          pFanout  = pFanout2,                                   \
          pFanout2 = Fpga_NodeReadNextFanout(pNode, pFanout) )

Definition at line 274 of file fpgaInt.h.

#define Fpga_NodeIsSimComplement

(

p

)

(Fpga_IsComplement(p)? !(Fpga_Regular(p)->fInv) : (p)->fInv)

Definition at line 89 of file fpgaInt.h.

#define Fpga_NodeReadNextFanout	(		pNode,
			pFanout
	)

Value:

( ( pFanout == NULL )? NULL :                                \
        ((Fpga_Regular((pFanout)->p1) == (pNode))?               \
             (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) )

Definition at line 258 of file fpgaInt.h.

#define Fpga_NodeReadNextFanoutPlace	(		pNode,
			pFanout
	)

Value:

( (Fpga_Regular((pFanout)->p1) == (pNode))?                  \
         &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 )

Definition at line 264 of file fpgaInt.h.

#define Fpga_NodeReadRef

(

p

)

((Fpga_Regular(p))->nRefs)

Definition at line 85 of file fpgaInt.h.

#define Fpga_NodeRef

(

p

)

((Fpga_Regular(p))->nRefs++)

Definition at line 86 of file fpgaInt.h.

#define FPGA_NUM_BYTES

(

n

)

(((n)/16 + (((n)%16) > 0))*16)

Definition at line 58 of file fpgaInt.h.

#define FPGA_RANDOM_UNSIGNED   ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))

Definition at line 92 of file fpgaInt.h.

#define FPGA_SEQ_SIGN

(

p

)

(1 << (((ABC_PTRUINT_T)p)%31));

Definition at line 70 of file fpgaInt.h.

#define Fpga_SeqIndex

(

p

)

((((ABC_PTRUINT_T)(p)) >> 1) & 07)

Definition at line 81 of file fpgaInt.h.

#define Fpga_SeqIndexCreate	(		p,
			Ind
	)		(((ABC_PTRUINT_T)(p)) | (1 << (((ABC_PTRUINT_T)(Ind)) & 07)))

Definition at line 82 of file fpgaInt.h.

#define Fpga_SeqIsComplement

(

p

)

(((int)((ABC_PTRUINT_T) (p) & 01)))

Definition at line 79 of file fpgaInt.h.

#define Fpga_SeqRegular

(

p

)

((Fpga_Node_t *)((ABC_PTRUINT_T)(p) & ~015))

Definition at line 80 of file fpgaInt.h.

Function Documentation

int Fpga_CountLevels

(

Fpga_Man_t *

pMan

)

Fpga_Cut_t* Fpga_CutAlloc

(

Fpga_Man_t *

p

)

DECLARATIONS ///.

CFile****************************************************************

FileName [fpgaCutUtils.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - August 18, 2004.]

Revision [

Id:

fpgaCutUtils.h,v 1.0 2003/09/08 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Allocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pCut;
    pCut = (Fpga_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts );
    memset( pCut, 0, sizeof(Fpga_Cut_t) );
    return pCut;
}

int Fpga_CutCountAll

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Counts all the cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 767 of file fpgaCut.c.

{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i, nCuts;
    // go through all the nodes in the unique table of the manager
    nCuts = 0;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                if ( pCut->nLeaves > 1 ) // skip the elementary cuts
                {
//                    Fpga_CutVolume( pCut );
                    nCuts++;
                }
    return nCuts;
}

Fpga_Cut_t* Fpga_CutCreateSimple	(	Fpga_Man_t *	p,
		Fpga_Node_t *	pNode
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pCut;
    pCut = Fpga_CutAlloc( p );
    pCut->pRoot       = pNode;
    pCut->nLeaves     = 1;
    pCut->ppLeaves[0] = pNode;
    pCut->uSign = FPGA_SEQ_SIGN(pCut->ppLeaves[0]);
    return pCut;
}

float Fpga_CutDeref	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut,
		int	fFanouts
	)

function*************************************************************

synopsis [Dereferences the cut.]

description [This procedure is similar to the procedure NodeRecusiveDeref.]

sideeffects []

seealso []

Definition at line 421 of file fpgaCutUtils.c.

{
    Fpga_Node_t * pNodeChild;
    float aArea;
    int i;

    // deref the fanouts
//    if ( fFanouts ) 
//        Fpga_CutRemoveFanouts( pMan, pNode, pCut );

    // start the area of this cut
    aArea = pMan->pLutLib->pLutAreas[(int)pCut->nLeaves];
    // go through the children
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        pNodeChild = pCut->ppLeaves[i];
        assert( pNodeChild->nRefs > 0 );
        if ( --pNodeChild->nRefs > 0 )  
            continue;
        if ( !Fpga_NodeIsAnd(pNodeChild) ) 
            continue;
        aArea += Fpga_CutDeref( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
    }
    return aArea;
}

float Fpga_CutDerefSwitch	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut,
		int	fFanouts
	)

function*************************************************************

synopsis [Dereferences the cut.]

description [This procedure is similar to the procedure NodeRecusiveDeref.]

sideeffects []

seealso []

Definition at line 95 of file fpgaSwitch.c.

{
    Fpga_Node_t * pNodeChild;
    float aArea;
    int i;
    // start the area of this cut
    aArea = pNode->Switching;
    if ( pCut->nLeaves == 1 )
        return aArea;
    // go through the children
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        pNodeChild = pCut->ppLeaves[i];
        assert( pNodeChild->nRefs > 0 );
        if ( --pNodeChild->nRefs > 0 )  
            continue;
        aArea += Fpga_CutDerefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
    }
    return aArea;
}

Fpga_Cut_t* Fpga_CutDup	(	Fpga_Man_t *	p,
		Fpga_Cut_t *	pCutOld
	)

Function*************************************************************

Synopsis [Duplicates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 62 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pCutNew;
    int i;
    pCutNew = Fpga_CutAlloc( p );
    pCutNew->pRoot   = pCutOld->pRoot;
    pCutNew->nLeaves = pCutOld->nLeaves;
    for ( i = 0; i < pCutOld->nLeaves; i++ )
        pCutNew->ppLeaves[i] = pCutOld->ppLeaves[i];
    return pCutNew;
}

void Fpga_CutFree	(	Fpga_Man_t *	p,
		Fpga_Cut_t *	pCut
	)

Function*************************************************************

Synopsis [Deallocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 85 of file fpgaCutUtils.c.

{
    if ( pCut )
    Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pCut );
}

float Fpga_CutGetAreaDerefed	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 362 of file fpgaCutUtils.c.

{
    float aResult, aResult2;
    if ( pCut->nLeaves == 1 )
        return 0;
    aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 );
    aResult  = Fpga_CutDeref( pMan, NULL, pCut, 0 );
    assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) );
    return aResult;
}

float Fpga_CutGetAreaFlow	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

function*************************************************************

synopsis [Computes the area flow of the cut.]

description []

sideeffects []

seealso []

Definition at line 314 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pCutFanin;
    int i;
    pCut->aFlow = pMan->pLutLib->pLutAreas[(int)pCut->nLeaves];
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        // get the cut implementing this phase of the fanin
        pCutFanin  = pCut->ppLeaves[i]->pCutBest;   
        assert( pCutFanin );
        pCut->aFlow  += pCutFanin->aFlow / pCut->ppLeaves[i]->nRefs;
    }
    return pCut->aFlow;
}

float Fpga_CutGetAreaRefed	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 340 of file fpgaCutUtils.c.

{
    float aResult, aResult2;
    if ( pCut->nLeaves == 1 )
        return 0;
    aResult  = Fpga_CutDeref( pMan, NULL, pCut, 0 );
    aResult2 = Fpga_CutRef( pMan, NULL, pCut, 0 );
    assert( Fpga_FloatEqual( pMan, aResult, aResult2 ) );
    return aResult;
}

void Fpga_CutGetParameters	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

Function*************************************************************

Synopsis [Computes the arrival time and the area flow of the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 279 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pFaninCut;
    int i;
    pCut->tArrival = -FPGA_FLOAT_LARGE;
    pCut->aFlow    = pMan->pLutLib->pLutAreas[(int)pCut->nLeaves];
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        pFaninCut = pCut->ppLeaves[i]->pCutBest;
        if ( pCut->tArrival < pFaninCut->tArrival )
             pCut->tArrival = pFaninCut->tArrival;
        // if the fanout count is not set, assume it to be 1
        if ( pCut->ppLeaves[i]->nRefs == 0 )
            pCut->aFlow += pFaninCut->aFlow;
        else
//            pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->nRefs;
            pCut->aFlow += pFaninCut->aFlow / pCut->ppLeaves[i]->aEstFanouts;
    }
    // use the first pin to compute the delay of the LUT 
    // (this mapper does not support the variable pin delay model)
    pCut->tArrival += pMan->pLutLib->pLutDelays[(int)pCut->nLeaves][0];
}

float Fpga_CutGetRootArea	(	Fpga_Man_t *	p,
		Fpga_Cut_t *	pCut
	)

function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 146 of file fpgaCutUtils.c.

{
    return p->pLutLib->pLutAreas[(int)pCut->nLeaves];
}

float Fpga_CutGetSwitchDerefed	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut
	)

DECLARATIONS ///.

CFile****************************************************************

FileName [fpgaSwitch.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - September 8, 2003.]

Revision [

Id:

fpgaSwitch.h,v 1.0 2003/09/08 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// function*************************************************************

synopsis [Computes the exact area associated with the cut.]

description []

sideeffects []

seealso []

Definition at line 43 of file fpgaSwitch.c.

{
    float aResult, aResult2;
    aResult2 = Fpga_CutRefSwitch( pMan, pNode, pCut, 0 );
    aResult  = Fpga_CutDerefSwitch( pMan, pNode, pCut, 0 );
//    assert( aResult == aResult2 );
    return aResult;
}

void Fpga_CutInsertFanouts	(	Fpga_Man_t *	p,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut
	)

Fpga_Cut_t* Fpga_CutListAppend	(	Fpga_Cut_t *	pSetAll,
		Fpga_Cut_t *	pSets
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 162 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pPrev = NULL; // Suppress "might be used uninitialized"
    Fpga_Cut_t * pTemp;
    if ( pSetAll == NULL )
        return pSets;
    if ( pSets == NULL )
        return pSetAll;
    // find the last one
    for ( pTemp = pSets; pTemp; pTemp = pTemp->pNext )
        pPrev = pTemp;
    // append all the end of the current set
    assert( pPrev->pNext == NULL );
    pPrev->pNext = pSetAll;
    return pSets;
}

int Fpga_CutListCount

(

Fpga_Cut_t *

pSets

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 211 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pTemp;
    int i;
    for ( i = 0, pTemp = pSets; pTemp; pTemp = pTemp->pNext, i++ );
    return i;
}

void Fpga_CutListRecycle	(	Fpga_Man_t *	p,
		Fpga_Cut_t *	pSetList,
		Fpga_Cut_t *	pSave
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 190 of file fpgaCutUtils.c.

{
    Fpga_Cut_t * pNext, * pTemp;
    for ( pTemp = pSetList, pNext = pTemp? pTemp->pNext : NULL; 
          pTemp; 
          pTemp = pNext, pNext = pNext? pNext->pNext : NULL )
        if ( pTemp != pSave )
            Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pTemp );
}

void Fpga_CutPrint	(	Fpga_Man_t *	p,
		Fpga_Node_t *	pRoot,
		Fpga_Cut_t *	pCut
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 102 of file fpgaCutUtils.c.

{
    int i;
    printf( "CUT:  Delay = %4.2f. Area = %4.2f. Nodes = %d -> {", 
        pCut->tArrival, pCut->aFlow, pRoot->Num );
    for ( i = 0; i < pCut->nLeaves; i++ )
        printf( " %d", pCut->ppLeaves[i]->Num );
    printf( " } \n" );
}

float Fpga_CutRef	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut,
		int	fFanouts
	)

function*************************************************************

synopsis [References the cut.]

description [This procedure is similar to the procedure NodeReclaim.]

sideeffects []

seealso []

Definition at line 384 of file fpgaCutUtils.c.

{
    Fpga_Node_t * pNodeChild;
    float aArea;
    int i;

    // deref the fanouts
//    if ( fFanouts ) 
//        Fpga_CutInsertFanouts( pMan, pNode, pCut );

    // start the area of this cut
    aArea = pMan->pLutLib->pLutAreas[(int)pCut->nLeaves];
    // go through the children
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        pNodeChild = pCut->ppLeaves[i];
        assert( pNodeChild->nRefs >= 0 );
        if ( pNodeChild->nRefs++ > 0 )  
            continue;
        if ( !Fpga_NodeIsAnd(pNodeChild) ) 
            continue;
        aArea += Fpga_CutRef( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
    }
    return aArea;
}

float Fpga_CutRefSwitch	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut,
		int	fFanouts
	)

function*************************************************************

synopsis [References the cut.]

description [This procedure is similar to the procedure NodeReclaim.]

sideeffects []

seealso []

Definition at line 63 of file fpgaSwitch.c.

{
    Fpga_Node_t * pNodeChild;
    float aArea;
    int i;
    // start the area of this cut
    aArea = pNode->Switching;
    if ( pCut->nLeaves == 1 )
        return aArea;
    // go through the children
    for ( i = 0; i < pCut->nLeaves; i++ )
    {
        pNodeChild = pCut->ppLeaves[i];
        assert( pNodeChild->nRefs >= 0 );
        if ( pNodeChild->nRefs++ > 0 )  
            continue;
        aArea += Fpga_CutRefSwitch( pMan, pNodeChild, pNodeChild->pCutBest, fFanouts );
    }
    return aArea;
}

void Fpga_CutRemoveFanouts	(	Fpga_Man_t *	p,
		Fpga_Node_t *	pNode,
		Fpga_Cut_t *	pCut
	)

Fpga_NodeVec_t* Fpga_DfsLim	(	Fpga_Man_t *	pMan,
		Fpga_Node_t *	pNode,
		int	nLevels
	)

Function*************************************************************

Synopsis [Computes the limited DFS ordering for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 606 of file fpgaUtils.c.

{
    Fpga_NodeVec_t * vNodes;
    int i;
    // perform the traversal
    vNodes = Fpga_NodeVecAlloc( 100 );
    Fpga_DfsLim_rec( pNode, nLevels, vNodes );
    for ( i = 0; i < vNodes->nSize; i++ )
        vNodes->pArray[i]->fMark0 = 0;
    return vNodes;
}

static int Fpga_FloatEqual ( Fpga_Man_t *  p, float  Arg1, float  Arg2  )

inlinestatic

Definition at line 283 of file fpgaInt.h.

{ return Arg1 > Arg2 - p->fEpsilon && Arg1 < Arg2 + p->fEpsilon; }

static int Fpga_FloatLessThan ( Fpga_Man_t *  p, float  Arg1, float  Arg2  )

inlinestatic

Definition at line 282 of file fpgaInt.h.

{ return Arg1 < Arg2 - p->fEpsilon; }

static int Fpga_FloatMoreThan ( Fpga_Man_t *  p, float  Arg1, float  Arg2  )

inlinestatic

Definition at line 281 of file fpgaInt.h.

{ return Arg1 > Arg2 + p->fEpsilon; }

int Fpga_LutLibDelaysAreDiscrete

(

Fpga_LutLib_t *

pLutLib

)

Function*************************************************************

Synopsis [Returns 1 if the delays are discrete.]

Description []

SideEffects []

SeeAlso []

Definition at line 236 of file fpgaLib.c.

{
    float Delay;
    int i;
    for ( i = 1; i <= pLutLib->LutMax; i++ )
    {
        Delay = pLutLib->pLutDelays[i][0];
        if ( ((float)((int)Delay)) != Delay )
            return 0;
    }
    return 1;
}

void Fpga_LutLibFree

(

Fpga_LutLib_t *

pLutLib

)

Function*************************************************************

Synopsis [Frees the LUT library.]

Description []

SideEffects []

SeeAlso []

Definition at line 185 of file fpgaLib.c.

{
    if ( pLutLib == NULL )
        return;
    ABC_FREE( pLutLib->pName );
    ABC_FREE( pLutLib );
}

void Fpga_LutLibPrint

(

Fpga_LutLib_t *

pLutLib

)

Function*************************************************************

Synopsis [Prints the LUT library.]

Description []

SideEffects []

SeeAlso []

Definition at line 205 of file fpgaLib.c.

{
    int i, k;
    printf( "# The area/delay of k-variable LUTs:\n" );
    printf( "# k    area     delay\n" );
    if ( pLutLib->fVarPinDelays )
    {
        for ( i = 1; i <= pLutLib->LutMax; i++ )
        {
            printf( "%d   %7.2f  ", i, pLutLib->pLutAreas[i] );
            for ( k = 0; k < i; k++ )
                printf( " %7.2f", pLutLib->pLutDelays[i][k] );
            printf( "\n" );
        }
    }
    else
        for ( i = 1; i <= pLutLib->LutMax; i++ )
            printf( "%d   %7.2f   %7.2f\n", i, pLutLib->pLutAreas[i], pLutLib->pLutDelays[i][0] );
}

Fpga_LutLib_t* Fpga_LutLibRead	(	char *	FileName,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Reads the description of LUTs from the LUT library file.]

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file fpgaLib.c.

{
    char pBuffer[1000], * pToken;
    Fpga_LutLib_t * p;
    FILE * pFile;
    int i, k;

    pFile = fopen( FileName, "r" );
    if ( pFile == NULL )
    {
        printf( "Cannot open LUT library file \"%s\".\n", FileName );
        return NULL;
    }

    p = ABC_ALLOC( Fpga_LutLib_t, 1 );
    memset( p, 0, sizeof(Fpga_LutLib_t) );
    p->pName = Extra_UtilStrsav( FileName );

    i = 1;
    while ( fgets( pBuffer, 1000, pFile ) != NULL )
    {
        pToken = strtok( pBuffer, " \t\n" );
        if ( pToken == NULL )
            continue;
        if ( pToken[0] == '#' )
            continue;
        if ( i != atoi(pToken) )
        {
            printf( "Error in the LUT library file \"%s\".\n", FileName );
            ABC_FREE( p );
            return NULL;
        }

        // read area
        pToken = strtok( NULL, " \t\n" );
        p->pLutAreas[i] = (float)atof(pToken);

        // read delays
        k = 0;
        while ( (pToken = strtok( NULL, " \t\n" )) )
            p->pLutDelays[i][k++] = (float)atof(pToken);

        // check for out-of-bound
        if ( k > i )
        {
            printf( "LUT %d has too many pins (%d). Max allowed is %d.\n", i, k, i );
            return NULL;
        }

        // check if var delays are specifies
        if ( k > 1 )
            p->fVarPinDelays = 1;

        if ( i == FPGA_MAX_LUTSIZE )
        {
            printf( "Skipping LUTs of size more than %d.\n", i );
            return NULL;
        }
        i++;
    }
    p->LutMax = i-1;
/*
    if ( p->LutMax > FPGA_MAX_LEAVES )
    {
        p->LutMax = FPGA_MAX_LEAVES;
        printf( "Warning: LUTs with more than %d inputs will not be used.\n", FPGA_MAX_LEAVES );
    }
*/
    // check the library
    if ( p->fVarPinDelays )
    {
        for ( i = 1; i <= p->LutMax; i++ )
            for ( k = 0; k < i; k++ )
            {
                if ( p->pLutDelays[i][k] <= 0.0 )
                    printf( "Warning: Pin %d of LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", 
                        k, i, p->pLutDelays[i][k] );
                if ( k && p->pLutDelays[i][k-1] > p->pLutDelays[i][k] )
                    printf( "Warning: Pin %d of LUT %d has delay %f. Pin %d of LUT %d has delay %f. Pin delays should be in non-decreasing order. Technology mapping may not work correctly.\n", 
                        k-1, i, p->pLutDelays[i][k-1], 
                        k, i, p->pLutDelays[i][k] );
            }
    }
    else
    {
        for ( i = 1; i <= p->LutMax; i++ )
        {
            if ( p->pLutDelays[i][0] <= 0.0 )
                printf( "Warning: LUT %d has delay %f. Pin delays should be non-negative numbers. Technology mapping may not work correctly.\n", 
                    i, p->pLutDelays[i][0] );
        }
    }

    return p;
}

void Fpga_ManReportChoices

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Reports statistics on choice nodes.]

Description [The number of choice nodes is the number of primary nodes, which has pNextE set to a pointer. The number of choices is the number of entries in the equivalent-node lists of the primary nodes.]

SideEffects []

SeeAlso []

Definition at line 897 of file fpgaUtils.c.

{
    Fpga_Node_t * pNode, * pTemp;
    int nChoiceNodes, nChoices;
    int i, LevelMax1, LevelMax2;

    // report the number of levels
    LevelMax1 = Fpga_MappingMaxLevel( pMan );
    pMan->nTravIds++;
    for ( i = 0; i < pMan->nOutputs; i++ )
        Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 );
    LevelMax2 = Fpga_MappingMaxLevel( pMan );

    // report statistics about choices
    nChoiceNodes = nChoices = 0;
    for ( i = 0; i < pMan->vAnds->nSize; i++ )
    {
        pNode = pMan->vAnds->pArray[i];
        if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
        { // this is a choice node = the primary node that has equivalent nodes
            nChoiceNodes++;
            for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
                nChoices++;
        }
    }
    if ( pMan->fVerbose )
    {
    printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
    printf( "Choice stats:  Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
    }
/*
    {
        FILE * pTable;
        pTable = fopen( "stats_choice.txt", "a+" );
        fprintf( pTable, "%s ", pMan->pFileName );
        fprintf( pTable, "%4d ", LevelMax1 );
        fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs );
        fprintf( pTable, "%4d ", LevelMax2 );
        fprintf( pTable, "%7d ", nChoiceNodes );
        fprintf( pTable, "%7d ", nChoices + nChoiceNodes );
        fprintf( pTable, "\n" );
        fclose( pTable );
    }
*/
}

float Fpga_MappingArea

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Computes the area of the current mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 177 of file fpgaUtils.c.

{
    Fpga_Node_t * pNode;
    float aTotal;
    int i;
    // perform the traversal
    aTotal = 0;
    for ( i = 0; i < pMan->vMapping->nSize; i++ )
    {
        pNode = pMan->vMapping->pArray[i];
        aTotal += pMan->pLutLib->pLutAreas[(int)pNode->pCutBest->nLeaves];
    }
    return aTotal;
}

float Fpga_MappingAreaTrav

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Computes the area of the current mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 239 of file fpgaUtils.c.

{
    Fpga_NodeVec_t * vNodes;
    float aTotal;
    int i;
    // perform the traversal
    aTotal = 0;
    vNodes = Fpga_NodeVecAlloc( 100 );
    for ( i = 0; i < pMan->nOutputs; i++ )
        aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes );
    for ( i = 0; i < vNodes->nSize; i++ )
        vNodes->pArray[i]->fMark0 = 0;
    Fpga_NodeVecFree( vNodes );
    return aTotal;
}

void Fpga_MappingCreatePiCuts

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Performs technology mapping for variable-size-LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file fpgaCut.c.

{
    Fpga_Cut_t * pCut;
    int i;

    // set the elementary cuts for the PI variables
    for ( i = 0; i < p->nInputs; i++ )
    {
        pCut = Fpga_CutAlloc( p );
        pCut->nLeaves = 1;
        pCut->ppLeaves[0] = p->pInputs[i];
        pCut->uSign = (1 << (i%31));
        p->pInputs[i]->pCuts   = pCut;
        p->pInputs[i]->pCutBest = pCut;
        // set the input arrival times
//        p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
    }
}

void Fpga_MappingCuts

(

Fpga_Man_t *

p

)

GLOBAL VARIABLES ///.

FUNCTION DEFINITIONS ///

GLOBAL VARIABLES ///.

Function*************************************************************

Synopsis [Computes the cuts for each node in the object graph.]

Description [The cuts are computed in one sweep over the mapping graph. First, the elementary cuts, which include the node itself, are assigned to the PI nodes. The internal nodes are considered in the DFS order. Each node is two-input AND-gate. So to compute the cuts at a node, we need to merge the sets of cuts of its two predecessors. The merged set contains only unique cuts with the number of inputs equal to k or less. Finally, the elementary cut, composed of the node itself, is added to the set of cuts for the node.

This procedure is pretty fast for 5-feasible cuts, but it dramatically slows down on some "dense" networks when computing 6-feasible cuts. The problem is that there are too many cuts in this case. We should think how to heuristically trim the number of cuts in such cases, to have reasonable runtime.]

SideEffects []

SeeAlso []

Definition at line 130 of file fpgaCut.c.

{
    ProgressBar * pProgress;
    Fpga_CutTable_t * pTable;
    Fpga_Node_t * pNode;
    int nCuts, nNodes, i;
    clock_t clk = clock();

    // set the elementary cuts for the PI variables
    assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
    Fpga_MappingCreatePiCuts( p );

    // compute the cuts for the internal nodes
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    pTable = Fpga_CutTableStart( p );
    for ( i = 0; i < nNodes; i++ )
    {
        Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        Fpga_CutCompute( p, pTable, pNode );
    }
    Extra_ProgressBarStop( pProgress );
    Fpga_CutTableStop( pTable );

    // report the stats
    if ( p->fVerbose )
    {
        nCuts = Fpga_CutCountAll(p);
        printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", 
               p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
        ABC_PRT( "Time", clock() - clk );
    }

    // print the cuts for the first primary output
//    Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) );
}

Fpga_NodeVec_t* Fpga_MappingDfs	(	Fpga_Man_t *	pMan,
		int	fCollectEquiv
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 54 of file fpgaUtils.c.

{
    Fpga_NodeVec_t * vNodes;//, * vNodesCo;
    Fpga_Node_t * pNode;
    int i;
    // collect the CO nodes by level
//    vNodesCo = Fpga_MappingOrderCosByLevel( pMan );
    // start the array
    vNodes = Fpga_NodeVecAlloc( 100 );
    // collect the PIs
    for ( i = 0; i < pMan->nInputs; i++ )
    {
        pNode = pMan->pInputs[i];
        Fpga_NodeVecPush( vNodes, pNode );
        pNode->fMark0 = 1;
    }
    // perform the traversal
    for ( i = 0; i < pMan->nOutputs; i++ )
        Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
//    for ( i = vNodesCo->nSize - 1; i >= 0 ; i-- )
//        for ( pNode = vNodesCo->pArray[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
//            Fpga_MappingDfs_rec( pNode, vNodes, fCollectEquiv );
    // clean the node marks
    for ( i = 0; i < vNodes->nSize; i++ )
        vNodes->pArray[i]->fMark0 = 0;
//    for ( i = 0; i < pMan->nOutputs; i++ )
//        Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) );
//    Fpga_NodeVecFree( vNodesCo );
    return vNodes;
}

Fpga_NodeVec_t* Fpga_MappingDfsNodes	(	Fpga_Man_t *	pMan,
		Fpga_Node_t **	ppNodes,
		int	nNodes,
		int	fEquiv
	)

Function*************************************************************

Synopsis [Computes the DFS ordering of the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 129 of file fpgaUtils.c.

{
    Fpga_NodeVec_t * vNodes;
    int i;
    // perform the traversal
    vNodes = Fpga_NodeVecAlloc( 200 );
    for ( i = 0; i < nNodes; i++ )
        Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv );
    for ( i = 0; i < vNodes->nSize; i++ )
        vNodes->pArray[i]->fMark0 = 0;
    return vNodes;
}

float Fpga_MappingGetAreaFlow

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 153 of file fpgaUtils.c.

{
    float aFlowFlowTotal = 0;
    int i;
    for ( i = 0; i < p->nOutputs; i++ )
    {
        if ( Fpga_NodeIsConst(p->pOutputs[i]) )
            continue;
        aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
    }
    return aFlowFlowTotal;
}

float Fpga_MappingGetSwitching	(	Fpga_Man_t *	pMan,
		Fpga_NodeVec_t *	vMapping
	)

Function*************************************************************

Synopsis [Computes the array of mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 127 of file fpgaSwitch.c.

{
    Fpga_Node_t * pNode;
    float Switch;
    int i;
    Switch = 0.0;
    for ( i = 0; i < vMapping->nSize; i++ )
    {
        pNode = vMapping->pArray[i];
        // at least one phase has the best cut assigned
        assert( !Fpga_NodeIsAnd(pNode) || pNode->pCutBest != NULL );
        // at least one phase is used in the mapping
        assert( pNode->nRefs > 0 );
        // compute the array due to the supergate
        Switch += pNode->Switching;
    }
    // add buffer for each CO driven by a CI
    for ( i = 0; i < pMan->nOutputs; i++ )
        if ( Fpga_NodeIsVar(Fpga_Regular(pMan->pOutputs[i])) && !Fpga_IsComplement(pMan->pOutputs[i]) )
            Switch += Fpga_Regular(pMan->pOutputs[i])->Switching;
    return Switch;
}

Fpga_NodeVec_t* Fpga_MappingLevelize	(	Fpga_Man_t *	pMan,
		Fpga_NodeVec_t *	vNodes
	)

Function*************************************************************

Synopsis [Levelizes the nodes accessible from the POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 747 of file fpgaUtils.c.

{
    Fpga_NodeVec_t * vLevels;
    Fpga_Node_t ** ppNodes;
    Fpga_Node_t * pNode;
    int nNodes, nLevelsMax, i;

    // reassign the levels (this may be necessary for networks which choices)
    ppNodes = vNodes->pArray;
    nNodes  = vNodes->nSize;
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = ppNodes[i];
        if ( !Fpga_NodeIsAnd(pNode) )
        {
            pNode->Level = 0;
            continue;
        }
        pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level );
    }

    // get the max levels
    nLevelsMax = 0;
    for ( i = 0; i < pMan->nOutputs; i++ )
        nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level );
    nLevelsMax++;

    // allocate storage for levels
    vLevels = Fpga_NodeVecAlloc( nLevelsMax );
    for ( i = 0; i < nLevelsMax; i++ )
        Fpga_NodeVecPush( vLevels, NULL );

    // go through the nodes and add them to the levels
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = ppNodes[i];
        pNode->pLevel = NULL;
        if ( !Fpga_NodeIsAnd(pNode) )
            continue;
        // attach the node to this level
        pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level );
        Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode );
    }
    return vLevels;
}

int Fpga_MappingMatches	(	Fpga_Man_t *	p,
		int	fDelayOriented
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Finds the best delay assignment of LUTs.]

Description [This procedure iterates through all the nodes of the object graph reachable from the POs and assigns the best match to each of them. If the flag fDelayOriented is set to 1, it tries to minimize the arrival time and uses the area flow as a tie-breaker. If the flag is set to 0, it considers all the cuts, whose arrival times matches the required time at the node, and minimizes the area flow using the arrival time as a tie-breaker.

Before this procedure is called, the required times should be set and the fanout counts should be computed. In the first iteration, the required times are set to very large number (by NodeCreate) and the fanout counts are set to the number of fanouts in the AIG. In the following iterations, the required times are set by the backward traversal, while the fanouts are estimated approximately.

If the arrival times of the PI nodes are given, they should be assigned to the PIs after the cuts are computed and before this procedure is called for the first time.]

SideEffects []

SeeAlso []

Definition at line 67 of file fpgaMatch.c.

{
    ProgressBar * pProgress;
    Fpga_Node_t * pNode;
    int i, nNodes;
    
    // assign the arrival times of the PIs
    for ( i = 0; i < p->nInputs; i++ )
        p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];

    // match LUTs with nodes in the topological order
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        // skip a secondary node
        if ( pNode->pRepr )
            continue;
        // match the node
        Fpga_MatchNode( p, pNode, fDelayOriented );
        Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
    }
    Extra_ProgressBarStop( pProgress );
/*
    if ( !fDelayOriented )
    {
        float Area = 0.0;
        for ( i = 0; i < p->nOutputs; i++ )
        {
            printf( "%5.2f ", Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow );
            Area += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
        }
        printf( "\nTotal = %5.2f\n", Area );
    }
*/
    return 1;
}

int Fpga_MappingMatchesArea

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file fpgaMatch.c.

{
    ProgressBar * pProgress;
    Fpga_Node_t * pNode;
    int i, nNodes;
    
    // assign the arrival times of the PIs
    for ( i = 0; i < p->nInputs; i++ )
        p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];

    // match LUTs with nodes in the topological order
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        // skip a secondary node
        if ( pNode->pRepr )
            continue;
        // match the node
        Fpga_MatchNodeArea( p, pNode );
        Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
    }
    Extra_ProgressBarStop( pProgress );
    return 1;
}

int Fpga_MappingMatchesSwitch

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Finds the best area assignment of LUTs.]

Description []

SideEffects []

SeeAlso []

Definition at line 349 of file fpgaMatch.c.

{
    ProgressBar * pProgress;
    Fpga_Node_t * pNode;
    int i, nNodes;
    
    // assign the arrival times of the PIs
    for ( i = 0; i < p->nInputs; i++ )
        p->pInputs[i]->pCutBest->tArrival = p->pInputArrivals[i];

    // match LUTs with nodes in the topological order
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    for ( i = 0; i < nNodes; i++ )
    {
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        // skip a secondary node
        if ( pNode->pRepr )
            continue;
        // match the node
        Fpga_MatchNodeSwitch( p, pNode );
        Extra_ProgressBarUpdate( pProgress, i, "Matches ..." );
    }
    Extra_ProgressBarStop( pProgress );
    return 1;
}

int Fpga_MappingMaxLevel

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 804 of file fpgaUtils.c.

{
    int nLevelMax, i;
    nLevelMax = 0;
    for ( i = 0; i < pMan->nOutputs; i++ )
        nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level? 
                nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level;
    return nLevelMax;
}

void Fpga_MappingPrintOutputArrivals

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Prints a bunch of latest arriving outputs.]

Description []

SideEffects []

SeeAlso []

Definition at line 402 of file fpgaUtils.c.

{
    Fpga_Node_t * pNode;
    int pSorted[FPGA_CO_LIST_SIZE];
    int fCompl, Limit, MaxNameSize, i;

    // determine the number of nodes to print
    Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs;

    // determine the order
    Fpga_MappingFindLatest( p, pSorted, Limit );

    // determine max size of the node's name
    MaxNameSize = 0;
    for ( i = 0; i < Limit; i++ )
        if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
            MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);

    // print the latest outputs
    for ( i = 0; i < Limit; i++ )
    {
        // get the i-th latest output
        pNode  = Fpga_Regular(p->pOutputs[pSorted[i]]);
        fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]);
        // print out the best arrival time
        printf( "Output  %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
        printf( "Delay = %8.2f  ",     (double)pNode->pCutBest->tArrival );
        if ( fCompl )
            printf( "NEG" );
        else
            printf( "POS" );
        printf( "\n" );
    }
}

void Fpga_MappingSetChoiceLevels

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Resets the levels of the nodes in the choice graph.]

Description [Makes the level of the choice nodes to be equal to the maximum of the level of the nodes in the equivalence class. This way sorting by level leads to the reverse topological order, which is needed for the required time computation.]

SideEffects []

SeeAlso []

Definition at line 876 of file fpgaUtils.c.

{
    int i;
    pMan->nTravIds++;
    for ( i = 0; i < pMan->nOutputs; i++ )
        Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 );
}

float Fpga_MappingSetRefsAndArea

(

Fpga_Man_t *

pMan

)

Function*************************************************************

Synopsis [Sets the correct reference counts for the mapping.]

Description [Collects the nodes in reverse topological order and places in them in array pMan->vMapping.]

SideEffects []

SeeAlso []

Definition at line 299 of file fpgaUtils.c.

{
    Fpga_Node_t * pNode, ** ppStore;
    float aArea;
    int i, LevelMax;

    // clean all references
    for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
        pMan->vNodesAll->pArray[i]->nRefs = 0;

    // allocate place to store the nodes
    LevelMax = Fpga_MappingMaxLevel( pMan );
    ppStore = ABC_ALLOC( Fpga_Node_t *, LevelMax + 1 );
    memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) );

    // collect nodes reachable from POs in the DFS order through the best cuts
    aArea = 0;
    for ( i = 0; i < pMan->nOutputs; i++ )
    {
        pNode = Fpga_Regular(pMan->pOutputs[i]);
        if ( pNode == pMan->pConst1 )
            continue;
        aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore );
        pNode->nRefs++;
    }

    // reconnect the nodes in reverse topological order
    pMan->vMapping->nSize = 0;
    for ( i = LevelMax; i >= 0; i-- )
        for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
            Fpga_NodeVecPush( pMan->vMapping, pNode );
    ABC_FREE( ppStore );
    return aArea;
}

void Fpga_MappingSetupMask	(	unsigned	uMask[],
		int	nVarsMax
	)

Function*************************************************************

Synopsis [Sets up the mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 475 of file fpgaUtils.c.

{
    if ( nVarsMax == 6 )
        uMask[0] = uMask[1] = FPGA_FULL;
    else
    {
        uMask[0] = FPGA_MASK(1 << nVarsMax);
        uMask[1] = 0;
    }
}

void Fpga_MappingSetupTruthTables

(

unsigned

uTruths[][2]

)

Function*************************************************************

Synopsis [Sets up the truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 449 of file fpgaUtils.c.

{
    int m, v;
    // set up the truth tables
    for ( m = 0; m < 32; m++ )
        for ( v = 0; v < 5; v++ )
            if ( m & (1 << v) )
                uTruths[v][0] |= (1 << m);
    // make adjustments for the case of 6 variables
    for ( v = 0; v < 5; v++ )
        uTruths[v][1] = uTruths[v][0];
    uTruths[5][0] = 0;
    uTruths[5][1] = FPGA_FULL;
}

void Fpga_MappingShow	(	Fpga_Man_t *	pMan,
		char *	pFileName
	)

void Fpga_MappingShowNodes	(	Fpga_Man_t *	pMan,
		Fpga_Node_t **	ppRoots,
		int	nRoots,
		char *	pFileName
	)

void Fpga_MappingSortByLevel	(	Fpga_Man_t *	pMan,
		Fpga_NodeVec_t *	vNodes,
		int	fIncreasing
	)

Function*************************************************************

Synopsis [Orders the nodes in the decreasing order of levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 584 of file fpgaUtils.c.

{
    if ( fIncreasing )
        qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
                (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing );
    else
        qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *), 
                (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing );
//    assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
}

void Fpga_NodeAddFaninFanout	(	Fpga_Node_t *	pFanin,
		Fpga_Node_t *	pFanout
	)

int Fpga_NodeGetFanoutNum

(

Fpga_Node_t *

pNode

)

void Fpga_NodeRemoveFaninFanout	(	Fpga_Node_t *	pFanin,
		Fpga_Node_t *	pFanoutToRemove
	)

Fpga_NodeVec_t* Fpga_NodeVecAlloc

(

int

nCap

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Allocates a vector with the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file fpgaVec.c.

{
    Fpga_NodeVec_t * p;
    p = ABC_ALLOC( Fpga_NodeVec_t, 1 );
    if ( nCap > 0 && nCap < 16 )
        nCap = 16;
    p->nSize  = 0;
    p->nCap   = nCap;
    p->pArray = p->nCap? ABC_ALLOC( Fpga_Node_t *, p->nCap ) : NULL;
    return p;
}

void Fpga_NodeVecClear

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 153 of file fpgaVec.c.

{
    p->nSize = 0;
}

void Fpga_NodeVecFree

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 68 of file fpgaVec.c.

{
    ABC_FREE( p->pArray );
    ABC_FREE( p );
}

void Fpga_NodeVecGrow	(	Fpga_NodeVec_t *	p,
		int	nCapMin
	)

Function*************************************************************

Synopsis [Resizes the vector to the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 117 of file fpgaVec.c.

{
    if ( p->nCap >= nCapMin )
        return;
    p->pArray = ABC_REALLOC( Fpga_Node_t *, p->pArray, nCapMin ); 
    p->nCap   = nCapMin;
}

Fpga_Node_t* Fpga_NodeVecPop

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 213 of file fpgaVec.c.

{
    return p->pArray[--p->nSize];
}

void Fpga_NodeVecPush	(	Fpga_NodeVec_t *	p,
		Fpga_Node_t *	Entry
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file fpgaVec.c.

{
    if ( p->nSize == p->nCap )
    {
        if ( p->nCap < 16 )
            Fpga_NodeVecGrow( p, 16 );
        else
            Fpga_NodeVecGrow( p, 2 * p->nCap );
    }
    p->pArray[p->nSize++] = Entry;
}

void Fpga_NodeVecPushOrder	(	Fpga_NodeVec_t *	vNodes,
		Fpga_Node_t *	pNode,
		int	fIncreasing
	)

Function*************************************************************

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file fpgaVec.c.

{
    Fpga_Node_t * pNode1, * pNode2;
    int i;
    Fpga_NodeVecPush( vNodes, pNode );
    // find the place of the node
    for ( i = vNodes->nSize-1; i > 0; i-- )
    {
        pNode1 = vNodes->pArray[i  ];
        pNode2 = vNodes->pArray[i-1];
        if (( fIncreasing && pNode1->pCutBest->tArrival >= pNode2->pCutBest->tArrival) ||
            (!fIncreasing && pNode1->pCutBest->tArrival <= pNode2->pCutBest->tArrival) )
            break;
        vNodes->pArray[i  ] = pNode2;
        vNodes->pArray[i-1] = pNode1;
    }
}

int Fpga_NodeVecPushUnique	(	Fpga_NodeVec_t *	p,
		Fpga_Node_t *	Entry
	)

Function*************************************************************

Synopsis [Add the element while ensuring uniqueness.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 192 of file fpgaVec.c.

{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            return 1;
    Fpga_NodeVecPush( p, Entry );
    return 0;
}

Fpga_Node_t** Fpga_NodeVecReadArray

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 85 of file fpgaVec.c.

{
    return p->pArray;
}

Fpga_Node_t* Fpga_NodeVecReadEntry	(	Fpga_NodeVec_t *	p,
		int	i
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 246 of file fpgaVec.c.

{
    assert( i >= 0 && i < p->nSize );
    return p->pArray[i];
}

int Fpga_NodeVecReadSize

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 101 of file fpgaVec.c.

{
    return p->nSize;
}

void Fpga_NodeVecReverse

(

Fpga_NodeVec_t *

vNodes

)

Function*************************************************************

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 395 of file fpgaVec.c.

{
    Fpga_Node_t * pNode1, * pNode2;
    int i;
    for ( i = 0; i < vNodes->nSize/2; i++ )
    {
        pNode1 = vNodes->pArray[i];
        pNode2 = vNodes->pArray[vNodes->nSize-1-i];
        vNodes->pArray[i]                 = pNode2;
        vNodes->pArray[vNodes->nSize-1-i] = pNode1;
    }
}

void Fpga_NodeVecShrink	(	Fpga_NodeVec_t *	p,
		int	nSizeNew
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file fpgaVec.c.

{
    assert( p->nSize >= nSizeNew );
    p->nSize = nSizeNew;
}

void Fpga_NodeVecSortByLevel

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file fpgaVec.c.

{
    qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), 
            (int (*)(const void *, const void *)) Fpga_NodeVecCompareLevels );
}

void Fpga_NodeVecUnion	(	Fpga_NodeVec_t *	p,
		Fpga_NodeVec_t *	p1,
		Fpga_NodeVec_t *	p2
	)

Function*************************************************************

Synopsis [Computes the union of nodes in two arrays.]

Description []

SideEffects []

SeeAlso []

Definition at line 345 of file fpgaVec.c.

{
    int i;
    Fpga_NodeVecClear( p );
    for ( i = 0; i < p1->nSize; i++ )
        Fpga_NodeVecPush( p, p1->pArray[i] );
    for ( i = 0; i < p2->nSize; i++ )
        Fpga_NodeVecPush( p, p2->pArray[i] );
}

void Fpga_NodeVecWriteEntry	(	Fpga_NodeVec_t *	p,
		int	i,
		Fpga_Node_t *	Entry
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 229 of file fpgaVec.c.

{
    assert( i >= 0 && i < p->nSize );
    p->pArray[i] = Entry;
}

void Fpga_SortNodesByArrivalTimes

(

Fpga_NodeVec_t *

p

)

Function*************************************************************

Synopsis [Orders the nodes in the increasing order of the arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 326 of file fpgaVec.c.

{
    qsort( (void *)p->pArray, p->nSize, sizeof(Fpga_Node_t *), 
            (int (*)(const void *, const void *)) Fpga_NodeVecCompareArrivals );
//    assert( Fpga_CompareNodesByLevel( p->pArray, p->pArray + p->nSize - 1 ) <= 0 );
}

float Fpga_TimeComputeArrivalMax

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Computes the maximum arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 89 of file fpgaTime.c.

{
    float fRequired;
    int i;
    if ( p->fLatchPaths && p->nLatches == 0 )
    {
        printf( "Delay optimization of latch path is not performed because there is no latches.\n" );
        p->fLatchPaths = 0;
    }
    // get the critical PO arrival time
    fRequired = -FPGA_FLOAT_LARGE;
    if ( p->fLatchPaths )
    {
        for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ )
        {
            if ( Fpga_NodeIsConst(p->pOutputs[i]) )
                continue;
            fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
//            printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
        }
//        printf( "Required latches = %5.1f\n", fRequired );
    }
    else
    {
        for ( i = 0; i < p->nOutputs; i++ )
        {
            if ( Fpga_NodeIsConst(p->pOutputs[i]) )
                continue;
            fRequired = FPGA_MAX( fRequired, Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
//            printf( " %5.1f", Fpga_Regular(p->pOutputs[i])->pCutBest->tArrival );
        }
//        printf( "Required outputs = %5.1f\n", fRequired );
    }
    return fRequired;
}

void Fpga_TimeComputeRequired	(	Fpga_Man_t *	p,
		float	fRequired
	)

Function*************************************************************

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 168 of file fpgaTime.c.

{
    int i;
    // clean the required times and the fanout counts for all nodes
    for ( i = 0; i < p->vAnds->nSize; i++ )
        p->vAnds->pArray[i]->tRequired = FPGA_FLOAT_LARGE;
    // set the required times for the POs
    if ( p->fLatchPaths )
        for ( i = p->nOutputs - p->nLatches; i < p->nOutputs; i++ )
            Fpga_Regular(p->pOutputs[i])->tRequired = fRequired;
    else
        for ( i = 0; i < p->nOutputs; i++ )
            Fpga_Regular(p->pOutputs[i])->tRequired = fRequired;
    // collect nodes reachable from POs in the DFS order through the best cuts
    Fpga_TimePropagateRequired( p, p->vMapping );
/*
    {
        int Counter = 0;
        for ( i = 0; i < p->vAnds->nSize; i++ )
            if ( p->vAnds->pArray[i]->tRequired > FPGA_FLOAT_LARGE - 100 )
                Counter++;
        printf( "The number of nodes with large required times = %d.\n", Counter );
    }
*/
}

void Fpga_TimeComputeRequiredGlobal	(	Fpga_Man_t *	p,
		int	fFirstTime
	)

Function*************************************************************

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file fpgaTime.c.

{
    p->fRequiredGlo = Fpga_TimeComputeArrivalMax( p );
    // update the required times according to the target
    if ( p->DelayTarget != -1 )
    {
        if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon )
        {
            if ( fFirstTime )
                printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->DelayTarget );
        }
        else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon )
        {
            if ( fFirstTime )
                printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget );
            p->fRequiredGlo = p->DelayTarget;
        }
    }
    Fpga_TimeComputeRequired( p, p->fRequiredGlo );
}

float Fpga_TimeCutComputeArrival	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

DECLARATIONS ///.

CFile****************************************************************

FileName [fpgaTime.c]

PackageName [MVSIS 1.3: 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:

fpgaTime.c,v 1.1 2005/01/23 06:59:42 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Computes the arrival times of the cut.]

Description [Computes the maximum arrival time of the cut leaves and adds the delay of the LUT.]

SideEffects []

SeeAlso []

Definition at line 44 of file fpgaTime.c.

{
    int i;
    float tArrival;
    tArrival = -FPGA_FLOAT_LARGE;
    for ( i = 0; i < pCut->nLeaves; i++ )
        if ( tArrival < pCut->ppLeaves[i]->pCutBest->tArrival )
            tArrival = pCut->ppLeaves[i]->pCutBest->tArrival;
    tArrival += pMan->pLutLib->pLutDelays[(int)pCut->nLeaves][0];
    return tArrival;
}

float Fpga_TimeCutComputeArrival_rec	(	Fpga_Man_t *	pMan,
		Fpga_Cut_t *	pCut
	)

Function*************************************************************

Synopsis [Computes the arrival times of the cut recursively.]

Description [When computing the arrival time for the previously unused cuts, their arrival time may be incorrect because their fanins have incorrect arrival time. This procedure is called to fix this problem.]

SideEffects []

SeeAlso []

Definition at line 69 of file fpgaTime.c.

{
    int i;
    for ( i = 0; i < pCut->nLeaves; i++ )
        if ( pCut->ppLeaves[i]->nRefs == 0 )
            Fpga_TimeCutComputeArrival_rec( pMan, pCut->ppLeaves[i]->pCutBest );
    return Fpga_TimeCutComputeArrival( pMan, pCut );
}

void Fpga_TimePropagateArrival

(

Fpga_Man_t *

p

)

Function*************************************************************

Synopsis [Computes the required times of all nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 245 of file fpgaTime.c.

{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i;

    // clean the required times and the fanout counts for all nodes
    for ( i = 0; i < p->vAnds->nSize; i++ )
    {
        pNode = p->vAnds->pArray[i];
        for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
            pCut->tArrival = Fpga_TimeCutComputeArrival( p, pCut );
    }
}

void Fpga_TimePropagateRequired	(	Fpga_Man_t *	p,
		Fpga_NodeVec_t *	vNodes
	)

Function*************************************************************

Synopsis [Computes the required times of the given nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 205 of file fpgaTime.c.

{
    Fpga_Node_t * pNode, * pChild;
    float fRequired;
    int i, k;

    // sorts the nodes in the decreasing order of levels
//    Fpga_MappingSortByLevel( p, vNodes, 0 );
    // the nodes area already sorted in Fpga_MappingSetRefsAndArea()

    // go through the nodes in the reverse topological order
    for ( k = 0; k < vNodes->nSize; k++ )
    {
        pNode = vNodes->pArray[k];
        if ( !Fpga_NodeIsAnd(pNode) )
            continue;
        // get the required time for children
        fRequired = pNode->tRequired - p->pLutLib->pLutDelays[(int)pNode->pCutBest->nLeaves][0];
        // update the required time of the children
        for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
        {
            pChild = pNode->pCutBest->ppLeaves[i];
            pChild->tRequired = FPGA_MIN( pChild->tRequired, fRequired );
        }
    }
}