ivyFastMap.c File Reference

#include "ivy.h"

Go to the source code of this file.

Data Structures
struct	Ivy_SuppMan_t_
struct	Ivy_Supp_t_

Macros
#define	IVY_INFINITY   10000
	DECLARATIONS ///. More...

Typedefs
typedef struct Ivy_SuppMan_t_	Ivy_SuppMan_t
typedef struct Ivy_Supp_t_	Ivy_Supp_t

Functions
static Ivy_Supp_t *	Ivy_ObjSupp (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static Ivy_Supp_t *	Ivy_ObjSuppStart (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static void	Ivy_FastMapPrint (Ivy_Man_t *pAig, int Delay, int Area, abctime Time, char *pStr)
static int	Ivy_FastMapDelay (Ivy_Man_t *pAig)
static int	Ivy_FastMapArea (Ivy_Man_t *pAig)
static void	Ivy_FastMapNode (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
static void	Ivy_FastMapNodeArea (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
static int	Ivy_FastMapMerge (Ivy_Supp_t *pSupp0, Ivy_Supp_t *pSupp1, Ivy_Supp_t *pSupp, int nLimit)
static void	Ivy_FastMapRequired (Ivy_Man_t *pAig, int Delay, int fSetInter)
static void	Ivy_FastMapRecover (Ivy_Man_t *pAig, int nLimit)
static int	Ivy_FastMapNodeDelay (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int	Ivy_FastMapNodeAreaRefed (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int	Ivy_FastMapNodeAreaDerefed (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static void	Ivy_FastMapNodeRecover (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
static int	Ivy_FastMapNodeRef (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
static int	Ivy_FastMapNodeDeref (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
void	Ivy_FastMapPerform (Ivy_Man_t *pAig, int nLimit, int fRecovery, int fVerbose)
	FUNCTION DEFINITIONS ///. More...
void	Ivy_FastMapStop (Ivy_Man_t *pAig)
int	Ivy_FastMapArea_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Vec_t *vLuts)
static int	Ivy_ObjIsNodeInt1 (Ivy_Obj_t *pObj)
static int	Ivy_ObjIsNodeInt2 (Ivy_Obj_t *pObj)
static int	Vec_IntRemoveDup (int *pArray, int nSize)
void	Ivy_FastMapNodeArea2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
void	Ivy_FastMapReadSupp (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Int_t *vLeaves)
void	Ivy_FastMapRequired_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Ivy_Obj_t *pRoot, int DelayR)
int	Ivy_FastMapCutCost (Ivy_Man_t *pAig, Vec_Ptr_t *vFront)
void	Ivy_FastMapMark_rec (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
int	Ivy_FastMapNodeWillGrow (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
int	Ivy_FastMapNodeFaninCost (Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
void	Ivy_FastMapNodeFaninUpdate (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
int	Ivy_FastMapNodeFaninCompact0 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int	Ivy_FastMapNodeFaninCompact1 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int	Ivy_FastMapNodeFaninCompact2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
int	Ivy_FastMapNodeFaninCompact_int (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
void	Ivy_FastMapNodeFaninCompact (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
void	Ivy_FastMapNodePrepare (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
void	Ivy_FastMapNodeUpdate (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
void	Ivy_FastMapNodeRecover2 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
void	Ivy_FastMapNodeRecover4 (Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)

Variables
abctime	s_MappingTime
	DECLARATIONS ///. More...
int	s_MappingMem

Macro Definition Documentation

#define IVY_INFINITY   10000

DECLARATIONS ///.

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

FileName [ivyFastMap.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Fast FPGA mapping.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006.]

Revision [

Id:

ivyFastMap.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

]

Definition at line 30 of file ivyFastMap.c.

Typedef Documentation

typedef struct Ivy_Supp_t_ Ivy_Supp_t

Definition at line 42 of file ivyFastMap.c.

typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t

Definition at line 32 of file ivyFastMap.c.

Function Documentation

int Ivy_FastMapArea ( Ivy_Man_t *  pAig )

static

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 288 of file ivyFastMap.c.

{
    Vec_Vec_t * vLuts;
    Ivy_Obj_t * pObj;
    int i, Counter = 0;
    // get the array to store the nodes
    vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
    Vec_VecClear( vLuts );
    // explore starting from each node
    Ivy_ManForEachPo( pAig, pObj, i )
        Counter += Ivy_FastMapArea_rec( pAig, Ivy_ObjFanin0(pObj), vLuts );
    // clean the marks
    Ivy_ManForEachNode( pAig, pObj, i )
        Ivy_ObjSupp( pAig, pObj )->fMark = 0;
    return Counter;
}

int Ivy_FastMapArea_rec	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		Vec_Vec_t *	vLuts
	)

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 259 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int i, Counter;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    // skip visited nodes and PIs
    if ( pSupp->fMark || pSupp->nSize == 1 )
        return 0;
    pSupp->fMark = 1;
    // compute the area of this node
    Counter = 0;
    for ( i = 0; i < pSupp->nSize; i++ )
        Counter += Ivy_FastMapArea_rec( pAig, Ivy_ManObj(pAig, pSupp->pArray[i]), vLuts );
    // add the node to the array of LUTs
    Vec_VecPush( vLuts, pSupp->Delay, pObj );
    return 1 + Counter;
}

int Ivy_FastMapCutCost	(	Ivy_Man_t *	pAig,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Counts the number of nodes with no external fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 1093 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSuppF;
    Ivy_Obj_t * pFanin;
    int i, Counter = 0;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
    {
        pSuppF = Ivy_ObjSupp( pAig, pFanin );
        if ( pSuppF->nRefs == 0 )
            Counter++;
    }
    return Counter;
}

int Ivy_FastMapDelay ( Ivy_Man_t *  pAig )

static

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

Synopsis [Computes delay after LUT mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 231 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    Ivy_Obj_t * pObj;
    int i, DelayMax = 0;
    Ivy_ManForEachPo( pAig, pObj, i )
    {
        pObj = Ivy_ObjFanin0(pObj);
        if ( !Ivy_ObjIsNode(pObj) )
            continue;
        pSupp = Ivy_ObjSupp( pAig, pObj );
        if ( DelayMax < pSupp->Delay )
            DelayMax = pSupp->Delay;
    }
    return DelayMax;
}

void Ivy_FastMapMark_rec	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj
	)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1118 of file ivyFastMap.c.

{
    if ( Ivy_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    assert( Ivy_ObjIsNode(pObj) );
    Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin0(pObj) );
    Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin1(pObj) );
    Ivy_ObjSetTravIdCurrent(pAig, pObj);
}

int Ivy_FastMapMerge ( Ivy_Supp_t *  pSupp0, Ivy_Supp_t *  pSupp1, Ivy_Supp_t *  pSupp, int  nLimit  )

static

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

Synopsis [Merges two supports]

Description []

SideEffects []

SeeAlso []

Definition at line 707 of file ivyFastMap.c.

{ 
    int i, k, c;
    assert( pSupp0->nSize >= pSupp1->nSize );
    // the case of the largest cut sizes
    if ( pSupp0->nSize == nLimit && pSupp1->nSize == nLimit )
    {
        for ( i = 0; i < pSupp0->nSize; i++ )
            if ( pSupp0->pArray[i] != pSupp1->pArray[i] )
                return 0;
        for ( i = 0; i < pSupp0->nSize; i++ )
            pSupp->pArray[i] = pSupp0->pArray[i];
        pSupp->nSize = pSupp0->nSize;
        return 1;
    }
    // the case when one of the cuts is the largest
    if ( pSupp0->nSize == nLimit )
    {
        for ( i = 0; i < pSupp1->nSize; i++ )
        {
            for ( k = pSupp0->nSize - 1; k >= 0; k-- )
                if ( pSupp0->pArray[k] == pSupp1->pArray[i] )
                    break;
            if ( k == -1 ) // did not find
                return 0;
        }
        for ( i = 0; i < pSupp0->nSize; i++ )
            pSupp->pArray[i] = pSupp0->pArray[i];
        pSupp->nSize = pSupp0->nSize;
        return 1;
    }

    // compare two cuts with different numbers
    i = k = 0;
    for ( c = 0; c < nLimit; c++ )
    {
        if ( k == pSupp1->nSize )
        {
            if ( i == pSupp0->nSize )
            {
                pSupp->nSize = c;
                return 1;
            }
            pSupp->pArray[c] = pSupp0->pArray[i++];
            continue;
        }
        if ( i == pSupp0->nSize )
        {
            if ( k == pSupp1->nSize )
            {
                pSupp->nSize = c;
                return 1;
            }
            pSupp->pArray[c] = pSupp1->pArray[k++];
            continue;
        }
        if ( pSupp0->pArray[i] < pSupp1->pArray[k] )
        {
            pSupp->pArray[c] = pSupp0->pArray[i++];
            continue;
        }
        if ( pSupp0->pArray[i] > pSupp1->pArray[k] )
        {
            pSupp->pArray[c] = pSupp1->pArray[k++];
            continue;
        }
        pSupp->pArray[c] = pSupp0->pArray[i++]; 
        k++;
    }
    if ( i < pSupp0->nSize || k < pSupp1->nSize )
        return 0;
    pSupp->nSize = c;
    return 1;
}

void Ivy_FastMapNode ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj, int  nLimit  )

static

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 541 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
    int fFaninParam = 2;
    int RetValue;
    assert( Ivy_ObjIsNode(pObj) );
    // get the supports
    pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
    pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
    pSupp  = Ivy_ObjSupp( pAig, pObj );
    pSupp->fMark = 0;
    // get the delays
    if ( pSupp0->Delay == pSupp1->Delay )
        pSupp->Delay = (pSupp0->Delay == 0) ? pSupp0->Delay + 1: pSupp0->Delay;
    else if ( pSupp0->Delay > pSupp1->Delay )
    {
        pSupp->Delay = pSupp0->Delay;
        pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
        pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
    }
    else // if ( pSupp0->Delay < pSupp1->Delay )
    {
        pSupp->Delay = pSupp1->Delay;
        pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
        pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
    }
    // merge the cuts
    if ( pSupp0->nSize < pSupp1->nSize )
        RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
    else
        RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
    if ( !RetValue )
    {
        pSupp->Delay++;
        if ( fFaninParam == 2 )
        {
            pSupp->nSize = 2;
            pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
            pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
        }
        else if ( fFaninParam == 3 )
        {
            Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
            pFanin0 = Ivy_ObjFanin0(pObj);
            pFanin1 = Ivy_ObjFanin1(pObj);
            pSupp->nSize = 0;
            // process the first fanin
            if ( Ivy_ObjIsNodeInt1(pFanin0) )
            {
                pFaninA = Ivy_ObjFanin0(pFanin0);
                pFaninB = Ivy_ObjFanin1(pFanin0);
                if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
                else
                {
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
                }
            }
            else
                pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
            // process the second fanin
            if ( Ivy_ObjIsNodeInt1(pFanin1) )
            {
                pFaninA = Ivy_ObjFanin0(pFanin1);
                pFaninB = Ivy_ObjFanin1(pFanin1);
                if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
                else
                {
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
                }
            }
            else
                pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
            // sort the fanins
            Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
            pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
            assert( pSupp->pArray[0] < pSupp->pArray[1] );
        }
        else if ( fFaninParam == 4 )
        {
            Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
            pFanin0 = Ivy_ObjFanin0(pObj);
            pFanin1 = Ivy_ObjFanin1(pObj);
            pSupp->nSize = 0;
            // consider the case when exactly one of them is internal
            if ( Ivy_ObjIsNodeInt1(pFanin0) ^ Ivy_ObjIsNodeInt1(pFanin1) )
            {
                pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
                pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
                if ( Ivy_ObjIsNodeInt1(pFanin0) && pSupp0->nSize < nLimit )
                {
                    pSupp->Delay = IVY_MAX( pSupp0->Delay, pSupp1->Delay + 1 );
                    pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
                    pSupp1->pArray[0] = Ivy_ObjId(pFanin1);
                    // merge the cuts
                    RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
                    assert( RetValue );
                    assert( pSupp->nSize > 1 );
                    return;
                }
                if ( Ivy_ObjIsNodeInt1(pFanin1) && pSupp1->nSize < nLimit )
                {
                    pSupp->Delay = IVY_MAX( pSupp1->Delay, pSupp0->Delay + 1 );
                    pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
                    pSupp0->pArray[0] = Ivy_ObjId(pFanin0);
                    // merge the cuts
                    RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
                    assert( RetValue );
                    assert( pSupp->nSize > 1 );
                    return;
                }
            }
            // process the first fanin
            if ( Ivy_ObjIsNodeInt1(pFanin0) )
            {
                pFaninA = Ivy_ObjFanin0(pFanin0);
                pFaninB = Ivy_ObjFanin1(pFanin0);
                if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
                else
                {
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
                }
            }
            else
                pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
            // process the second fanin
            if ( Ivy_ObjIsNodeInt1(pFanin1) )
            {
                pFaninA = Ivy_ObjFanin0(pFanin1);
                pFaninB = Ivy_ObjFanin1(pFanin1);
                if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
                else
                {
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
                    pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
                }
            }
            else
                pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
            // sort the fanins
            Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
            pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
            assert( pSupp->pArray[0] < pSupp->pArray[1] );
            assert( pSupp->nSize > 1 );
        }
    }
    assert( pSupp->Delay > 0 );
}

void Ivy_FastMapNodeArea ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj, int  nLimit  )

static

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 441 of file ivyFastMap.c.

{
    static int Store[32], StoreSize;
    static char Supp0[16], Supp1[16];
    static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
    static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
    Ivy_Obj_t * pFanin0, * pFanin1;
    Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
    int RetValue, DelayOld, RefsOld;
    int AreaBef, AreaAft;
    assert( nLimit <= 32 );
    assert( Ivy_ObjIsNode(pObj) );
    // get the fanins
    pFanin0 = Ivy_ObjFanin0(pObj);
    pFanin1 = Ivy_ObjFanin1(pObj);
    // get the supports
    pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
    pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
    pSupp  = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->fMark == 0 );

    // get the area
    if ( pSupp->nRefs == 0 )
        AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
    else
        AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
//    if ( AreaBef == 1 )
//        return;

    // deref the cut if the node is refed
    if ( pSupp->nRefs != 0 )
        Ivy_FastMapNodeDeref( pAig, pObj );

    // get the old delay of the node
    DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
    assert( DelayOld <= pSupp->DelayR );
    // copy the current cut
    memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
    StoreSize = pSupp->nSize;
    // get the fanin support
    if ( Ivy_ObjRefs(pFanin0) > 2 && pSupp0->Delay < pSupp->DelayR )
//    if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results
    {
        pSupp0 = pTemp0;
        pSupp0->nSize = 1;
        pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
    }
    // get the fanin support
    if ( Ivy_ObjRefs(pFanin1) > 2 && pSupp1->Delay < pSupp->DelayR )
//    if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR )
    {
        pSupp1 = pTemp1;
        pSupp1->nSize = 1;
        pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
    }
    // merge the cuts
    if ( pSupp0->nSize < pSupp1->nSize )
        RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
    else
        RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
    if ( !RetValue )
    {
        pSupp->nSize = 2;
        pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
        pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
    }

    // check the resulting delay
    pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);

    RefsOld = pSupp->nRefs; pSupp->nRefs = 0;
    AreaAft = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
    pSupp->nRefs = RefsOld;

    if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
//    if ( pSupp->Delay > pSupp->DelayR )
    {
        pSupp->nSize = StoreSize;
        memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
        pSupp->Delay = DelayOld;
//        printf( "-" );
    }
//    else
//        printf( "+" );

    if ( pSupp->nRefs != 0 )
        Ivy_FastMapNodeRef( pAig, pObj );
}

void Ivy_FastMapNodeArea2	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit
	)

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file ivyFastMap.c.

{
    static int Store[32], StoreSize;
    static char Supp0[16], Supp1[16];
    static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
    static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
    Ivy_Obj_t * pFanin0, * pFanin1;
    Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
    int RetValue, DelayOld;
    assert( nLimit <= 32 );
    assert( Ivy_ObjIsNode(pObj) );
    // get the fanins
    pFanin0 = Ivy_ObjFanin0(pObj);
    pFanin1 = Ivy_ObjFanin1(pObj);
    // get the supports
    pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
    pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
    pSupp  = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->fMark == 0 );
    // get the old delay of the node
    DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
    assert( DelayOld <= pSupp->DelayR );
    // copy the current cut
    memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
    StoreSize = pSupp->nSize;
    // get the fanin support
    if ( Ivy_ObjRefs(pFanin0) > 1 && pSupp0->Delay < pSupp->DelayR )
    {
        pSupp0 = pTemp0;
        pSupp0->nSize = 1;
        pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
    }
    // get the fanin support
    if ( Ivy_ObjRefs(pFanin1) > 1 && pSupp1->Delay < pSupp->DelayR )
    {
        pSupp1 = pTemp1;
        pSupp1->nSize = 1;
        pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
    }
    // merge the cuts
    if ( pSupp0->nSize < pSupp1->nSize )
        RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
    else
        RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
    if ( !RetValue )
    {
        pSupp->nSize = 2;
        pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
        pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
    }
    // check the resulting delay
    pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);
    if ( pSupp->Delay > pSupp->DelayR )
    {
        pSupp->nSize = StoreSize;
        memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
        pSupp->Delay = DelayOld;
    }
}

int Ivy_FastMapNodeAreaDerefed ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

static

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

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

description []

sideeffects []

seealso []

Definition at line 1064 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int aResult, aResult2;
    if ( Ivy_ObjIsCi(pObj) )
        return 0;
    assert( Ivy_ObjIsNode(pObj) );
    pSupp = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->nRefs == 0 );
    aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
    aResult  = Ivy_FastMapNodeDeref( pAig, pObj );
    assert( aResult == aResult2 );
    return aResult;
}

int Ivy_FastMapNodeAreaRefed ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

static

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

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

description []

sideeffects []

seealso []

Definition at line 1038 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int aResult, aResult2;
    if ( Ivy_ObjIsCi(pObj) )
        return 0;
    assert( Ivy_ObjIsNode(pObj) );
    pSupp = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->nRefs > 0 );
    aResult  = Ivy_FastMapNodeDeref( pAig, pObj );
    aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
    assert( aResult == aResult2 );
    return aResult;
}

int Ivy_FastMapNodeDelay ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

static

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

Synopsis [Computes the delay of the cut rooted at this node.]

Description []

SideEffects []

SeeAlso []

Definition at line 943 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp, * pSuppF;
    int c, Delay = 0;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    for ( c = 0; c < pSupp->nSize; c++ )
    {
        pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
        Delay = IVY_MAX( Delay, pSuppF->Delay );
    }
    return 1 + Delay;
}

int Ivy_FastMapNodeDeref ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

static

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

synopsis [Dereferences the cut.]

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

sideeffects []

seealso []

Definition at line 1003 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp, * pSuppF;
    Ivy_Obj_t * pNodeChild;
    int aArea, i;
    // start the area of this cut
    aArea = 1;
    // go through the children
    pSupp = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->nSize > 1 );
    for ( i = 0; i < pSupp->nSize; i++ )
    {
        pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
        pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
        assert( pSuppF->nRefs > 0 );
        if ( --pSuppF->nRefs > 0 )  
            continue;
        if ( pSuppF->nSize == 1 ) 
            continue;
        aArea += Ivy_FastMapNodeDeref( pAig, pNodeChild );
    }
    return aArea;
}

void Ivy_FastMapNodeFaninCompact	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1332 of file ivyFastMap.c.

{
    while ( Ivy_FastMapNodeFaninCompact_int( pAig, pObj, nLimit, vFront ) );
}

int Ivy_FastMapNodeFaninCompact0	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1223 of file ivyFastMap.c.

{
    Ivy_Obj_t * pFanin;
    int i;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
    {
        if ( Ivy_ObjIsCi(pFanin) )
            continue;
        if ( Ivy_FastMapNodeWillGrow(pAig, pFanin) )
            continue;
        if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
        {
            Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
            return 1;
        }
    }
    return 0;
}

int Ivy_FastMapNodeFaninCompact1	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1253 of file ivyFastMap.c.

{
    Ivy_Obj_t * pFanin;
    int i;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
    {
        if ( Ivy_ObjIsCi(pFanin) )
            continue;
        if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) < 0 )
        {
            Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
            return 1;
        }
    }
    return 0;
}

int Ivy_FastMapNodeFaninCompact2	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1281 of file ivyFastMap.c.

{
    Ivy_Obj_t * pFanin;
    int i;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
    {
        if ( Ivy_ObjIsCi(pFanin) )
            continue;
        if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
        {
            Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
            return 1;
        }
    }
    return 0;
}

int Ivy_FastMapNodeFaninCompact_int	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Compacts the number of external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1309 of file ivyFastMap.c.

{
    if ( Ivy_FastMapNodeFaninCompact0(pAig, pObj, nLimit, vFront) )
        return 1;
    if (  Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact1(pAig, pObj, nLimit, vFront) )
        return 1;
    if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact2(pAig, pObj, nLimit, vFront) )
        return 1;
    assert( Vec_PtrSize(vFront) <= nLimit );
    return 0;
}

int Ivy_FastMapNodeFaninCost	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj
	)

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

Synopsis [Returns the increase in the number of fanins with no external refs.]

Description []

SideEffects []

SeeAlso []

Definition at line 1159 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSuppF;
    Ivy_Obj_t * pFanin;
    int Counter = 0;
    assert( Ivy_ObjIsNode(pObj) );
    // check if the node has external refs
    pSuppF = Ivy_ObjSupp( pAig, pObj );
    if ( pSuppF->nRefs == 0 )
        Counter--;
    // increment the number of fanins without external refs
    pFanin = Ivy_ObjFanin0(pObj);
    pSuppF = Ivy_ObjSupp( pAig, pFanin );
    if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
        Counter++;
    // increment the number of fanins without external refs
    pFanin = Ivy_ObjFanin1(pObj);
    pSuppF = Ivy_ObjSupp( pAig, pFanin );
    if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
        Counter++;
    return Counter;
}

void Ivy_FastMapNodeFaninUpdate	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 1193 of file ivyFastMap.c.

{
    Ivy_Obj_t * pFanin;
    assert( Ivy_ObjIsNode(pObj) );
    Vec_PtrRemove( vFront, pObj );
    pFanin = Ivy_ObjFanin0(pObj);
    if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
    {
        Ivy_ObjSetTravIdCurrent(pAig, pFanin);
        Vec_PtrPush( vFront, pFanin );
    }
    pFanin = Ivy_ObjFanin1(pObj);
    if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
    {
        Ivy_ObjSetTravIdCurrent(pAig, pFanin);
        Vec_PtrPush( vFront, pFanin );
    }
}

void Ivy_FastMapNodePrepare	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vFrontOld
	)

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

Synopsis [Prepares node mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 1348 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    Ivy_Obj_t * pFanin;
    int i;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    // expand the cut downwards from the given place
    Vec_PtrClear( vFront );
    Vec_PtrClear( vFrontOld );
    Ivy_ManIncrementTravId( pAig );
    for ( i = 0; i < pSupp->nSize; i++ )
    {
        pFanin = Ivy_ManObj(pAig, pSupp->pArray[i]);
        Vec_PtrPush( vFront, pFanin );
        Vec_PtrPush( vFrontOld, pFanin );
        Ivy_ObjSetTravIdCurrent( pAig, pFanin );
    }
    // mark the nodes in the cone
    Ivy_FastMapMark_rec( pAig, pObj );
}

void Ivy_FastMapNodeRecover ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj, int  nLimit, Vec_Ptr_t *  vFront, Vec_Ptr_t *  vFrontOld  )

static

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1463 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int CostBef, CostAft;
    int AreaBef, AreaAft;
    int DelayOld;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
    assert( pSupp->Delay <= pSupp->DelayR );
    if ( pSupp->nRefs == 0 )
        return;
    // get the area
    AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
//    if ( AreaBef == 1 )
//        return;
    // the cut is non-trivial
    Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
    // iteratively modify the cut
    Ivy_FastMapNodeDeref( pAig, pObj );
    CostBef = Ivy_FastMapCutCost( pAig, vFront );
    Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
    CostAft = Ivy_FastMapCutCost( pAig, vFront );
    Ivy_FastMapNodeRef( pAig, pObj );
    assert( CostBef >= CostAft );
    // update the node
    Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
    pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
    // get the new area
    AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
    {
        Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
        AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
        assert( AreaAft == AreaBef );
        pSupp->Delay = DelayOld;
    }
}

void Ivy_FastMapNodeRecover2	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vFrontOld
	)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1407 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int CostBef, CostAft;
    int AreaBef, AreaAft;
    pSupp = Ivy_ObjSupp( pAig, pObj );
//    if ( pSupp->nRefs == 0 )
//        return;
    if ( pSupp->nRefs == 0 )
        AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
    else
        AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    // get the area
    if ( AreaBef == 1 )
        return;

    if ( pSupp->nRefs == 0 )
    {
        pSupp->nRefs = 1000000;
        Ivy_FastMapNodeRef( pAig, pObj );
    }
    // the cut is non-trivial
    Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
    // iteratively modify the cut
    CostBef = Ivy_FastMapCutCost( pAig, vFront );
    Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
    CostAft = Ivy_FastMapCutCost( pAig, vFront );
    assert( CostBef >= CostAft );
    // update the node
    Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
    // get the new area
    AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    if ( AreaAft > AreaBef )
    {
        Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
        AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
        assert( AreaAft == AreaBef );
    }
    if ( pSupp->nRefs == 1000000 )
    {
        pSupp->nRefs = 0;
        Ivy_FastMapNodeDeref( pAig, pObj );
    }
}

void Ivy_FastMapNodeRecover4	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		int	nLimit,
		Vec_Ptr_t *	vFront,
		Vec_Ptr_t *	vFrontOld
	)

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1512 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    int CostBef, CostAft;
    int AreaBef, AreaAft;
    int DelayOld;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
    assert( pSupp->Delay <= pSupp->DelayR );
//    if ( pSupp->nRefs == 0 )
//        return;
//    AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    // get the area
    if ( pSupp->nRefs == 0 )
        AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
    else
        AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    if ( AreaBef == 1 )
        return;

    if ( pSupp->nRefs == 0 )
    {
        pSupp->nRefs = 1000000;
        Ivy_FastMapNodeRef( pAig, pObj );
    }
    // the cut is non-trivial
    Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
    // iteratively modify the cut
    CostBef = Ivy_FastMapCutCost( pAig, vFront );
    Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
    CostAft = Ivy_FastMapCutCost( pAig, vFront );
    assert( CostBef >= CostAft );
    // update the node
    Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
    pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
    // get the new area
    AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
    if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
    {
        Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
        AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
        assert( AreaAft == AreaBef );
        pSupp->Delay = DelayOld;
    }
    if ( pSupp->nRefs == 1000000 )
    {
        pSupp->nRefs = 0;
        Ivy_FastMapNodeDeref( pAig, pObj );
    }
}

int Ivy_FastMapNodeRef ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

static

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

synopsis [References the cut.]

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

sideeffects []

seealso []

Definition at line 968 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp, * pSuppF;
    Ivy_Obj_t * pNodeChild;
    int aArea, i;
    // start the area of this cut
    aArea = 1;
    // go through the children
    pSupp = Ivy_ObjSupp( pAig, pObj );
    assert( pSupp->nSize > 1 );
    for ( i = 0; i < pSupp->nSize; i++ )
    {
        pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
        pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
        assert( pSuppF->nRefs >= 0 );
        if ( pSuppF->nRefs++ > 0 )  
            continue;
        if ( pSuppF->nSize == 1 ) 
            continue;
        aArea += Ivy_FastMapNodeRef( pAig, pNodeChild );
    }
    return aArea;
}

void Ivy_FastMapNodeUpdate	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		Vec_Ptr_t *	vFront
	)

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

Synopsis [Updates the frontier.]

Description []

SideEffects []

SeeAlso []

Definition at line 1380 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    Ivy_Obj_t * pFanin;
    int i;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    // deref node's cut
    Ivy_FastMapNodeDeref( pAig, pObj );
    // update the node's cut
    pSupp->nSize = Vec_PtrSize(vFront);
    Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
        pSupp->pArray[i] = pFanin->Id;
    // ref the new cut
    Ivy_FastMapNodeRef( pAig, pObj );
}

int Ivy_FastMapNodeWillGrow	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj
	)

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

Synopsis [Returns 1 if the number of fanins will grow.]

Description []

SideEffects []

SeeAlso []

Definition at line 1139 of file ivyFastMap.c.

{
    Ivy_Obj_t * pFanin0, * pFanin1;
    assert( Ivy_ObjIsNode(pObj) );
    pFanin0 = Ivy_ObjFanin0(pObj);
    pFanin1 = Ivy_ObjFanin1(pObj);
    return !Ivy_ObjIsTravIdCurrent(pAig, pFanin0) && !Ivy_ObjIsTravIdCurrent(pAig, pFanin1);
}

void Ivy_FastMapPerform	(	Ivy_Man_t *	pAig,
		int	nLimit,
		int	fRecovery,
		int	fVerbose
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Performs fast K-LUT mapping of the AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file ivyFastMap.c.

{
    Ivy_SuppMan_t * pMan;
    Ivy_Obj_t * pObj;
    int i, Delay, Area;
    abctime clk, clkTotal = Abc_Clock();
    // start the memory for supports
    pMan = ABC_ALLOC( Ivy_SuppMan_t, 1 );
    memset( pMan, 0, sizeof(Ivy_SuppMan_t) );
    pMan->nLimit = nLimit;
    pMan->nObjs  = Ivy_ManObjIdMax(pAig) + 1;
    pMan->nSize  = sizeof(Ivy_Supp_t) + nLimit * sizeof(int);
    pMan->pMem   = (char *)ABC_ALLOC( char, pMan->nObjs * pMan->nSize );
    memset( pMan->pMem, 0, pMan->nObjs * pMan->nSize );
    pMan->vLuts  = Vec_VecAlloc( 100 );
    pAig->pData  = pMan;
clk = Abc_Clock();
    // set the PI mapping
    Ivy_ObjSuppStart( pAig, Ivy_ManConst1(pAig) );
    Ivy_ManForEachPi( pAig, pObj, i )
        Ivy_ObjSuppStart( pAig, pObj );
    // iterate through all nodes in the topological order
    Ivy_ManForEachNode( pAig, pObj, i )
        Ivy_FastMapNode( pAig, pObj, nLimit );
    // find the best arrival time and area
    Delay = Ivy_FastMapDelay( pAig );
    Area = Ivy_FastMapArea(pAig);
    if ( fVerbose )
        Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Delay oriented mapping: " );

// 2-1-2 (doing 2-1-2-1-2 improves 0.5%)

    if ( fRecovery )
    {
clk = Abc_Clock();
    Ivy_FastMapRequired( pAig, Delay, 0 );
    // remap the nodes
    Ivy_FastMapRecover( pAig, nLimit );
    Delay = Ivy_FastMapDelay( pAig );
    Area = Ivy_FastMapArea(pAig);
    if ( fVerbose )
        Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2       : " );

clk = Abc_Clock();
    Ivy_FastMapRequired( pAig, Delay, 0 );
    // iterate through all nodes in the topological order
    Ivy_ManForEachNode( pAig, pObj, i )
        Ivy_FastMapNodeArea( pAig, pObj, nLimit );
    Delay = Ivy_FastMapDelay( pAig );
    Area = Ivy_FastMapArea(pAig);
    if ( fVerbose )
        Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 1       : " );

clk = Abc_Clock();
    Ivy_FastMapRequired( pAig, Delay, 0 );
    // remap the nodes
    Ivy_FastMapRecover( pAig, nLimit );
    Delay = Ivy_FastMapDelay( pAig );
    Area = Ivy_FastMapArea(pAig);
    if ( fVerbose )
        Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2       : " );
    }


    s_MappingTime = Abc_Clock() - clkTotal;
    s_MappingMem = pMan->nObjs * pMan->nSize;
/*
    {
        Vec_Ptr_t * vNodes;
        vNodes = Vec_PtrAlloc( 100 );
        Vec_VecForEachEntry( Ivy_Obj_t *, pMan->vLuts, pObj, i, k )
            Vec_PtrPush( vNodes, pObj );
        Ivy_ManShow( pAig, 0, vNodes );
        Vec_PtrFree( vNodes );
    }
*/
}

void Ivy_FastMapPrint ( Ivy_Man_t *  pAig, int  Delay, int  Area, abctime  Time, char *  pStr  )

static

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

Synopsis [Prints statistics.]

Description []

SideEffects []

SeeAlso []

Definition at line 214 of file ivyFastMap.c.

{
    printf( "%s : Delay = %3d. Area = %6d. ", pStr, Delay, Area );
    ABC_PRT( "Time", Time );
}

void Ivy_FastMapReadSupp	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		Vec_Int_t *	vLeaves
	)

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

Synopsis [Creates integer vector with the support of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 793 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    vLeaves->nCap   = 8;
    vLeaves->nSize  = pSupp->nSize;
    vLeaves->pArray = pSupp->pArray;
}

void Ivy_FastMapRecover ( Ivy_Man_t *  pAig, int  nLimit  )

static

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

Synopsis [Performs area recovery for each node.]

Description []

SideEffects []

SeeAlso []

Definition at line 917 of file ivyFastMap.c.

{
    Vec_Ptr_t * vFront, * vFrontOld;
    Ivy_Obj_t * pObj;
    int i;
    vFront = Vec_PtrAlloc( nLimit );
    vFrontOld = Vec_PtrAlloc( nLimit );
    Ivy_ManCleanTravId( pAig );
    // iterate through all nodes in the topological order
    Ivy_ManForEachNode( pAig, pObj, i )
        Ivy_FastMapNodeRecover( pAig, pObj, nLimit, vFront, vFrontOld );
    Vec_PtrFree( vFrontOld );
    Vec_PtrFree( vFront );
}

void Ivy_FastMapRequired ( Ivy_Man_t *  pAig, int  Delay, int  fSetInter  )

static

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

Synopsis [Computes the required times for each node.]

Description [Sets reference counters for each node.]

SideEffects []

SeeAlso []

Definition at line 836 of file ivyFastMap.c.

{
    Vec_Vec_t * vLuts;
    Vec_Ptr_t * vNodes;
    Ivy_Obj_t * pObj;
    Ivy_Supp_t * pSupp, * pSuppF;
    int i, k, c;
    // clean the required times
    Ivy_ManForEachPi( pAig, pObj, i )
    {
        pSupp = Ivy_ObjSupp( pAig, pObj );
        pSupp->DelayR = IVY_INFINITY;
        pSupp->nRefs = 0;
    }
    Ivy_ManForEachNode( pAig, pObj, i )
    {
        pSupp = Ivy_ObjSupp( pAig, pObj );
        pSupp->DelayR = IVY_INFINITY;
        pSupp->nRefs = 0;
    }
    // set the required times of the POs
    Ivy_ManForEachPo( pAig, pObj, i )
    {
        pSupp = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
        pSupp->DelayR = Delay;
        pSupp->nRefs++;
    }
    // get the levelized nodes used in the mapping
    vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
    // propagate the required times
    Vec_VecForEachLevelReverse( vLuts, vNodes, i )
    Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k )
    {
        pSupp = Ivy_ObjSupp( pAig, pObj );
        assert( pSupp->nRefs > 0 );
        for ( c = 0; c < pSupp->nSize; c++ )
        {
            pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
            pSuppF->DelayR = IVY_MIN( pSuppF->DelayR, pSupp->DelayR - 1 );
            pSuppF->nRefs++;
        }
    }
/*
    // print out some of the required times
    Ivy_ManForEachPi( pAig, pObj, i )
    {
        pSupp = Ivy_ObjSupp( pAig, pObj );
        printf( "%d ", pSupp->DelayR );
    }
    printf( "\n" );    
*/

    if ( fSetInter )
    {
        // set the required times of the intermediate nodes
        Vec_VecForEachLevelReverse( vLuts, vNodes, i )
        Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k )
        {
            pSupp = Ivy_ObjSupp( pAig, pObj );
            Ivy_FastMapRequired_rec( pAig, pObj, pObj, pSupp->DelayR ); 
        }
        // make sure that all required times are assigned
        Ivy_ManForEachNode( pAig, pObj, i )
        {
            pSupp = Ivy_ObjSupp( pAig, pObj );
            assert( pSupp->DelayR < IVY_INFINITY );
        }
    }
}

void Ivy_FastMapRequired_rec	(	Ivy_Man_t *	pAig,
		Ivy_Obj_t *	pObj,
		Ivy_Obj_t *	pRoot,
		int	DelayR
	)

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

Synopsis [Sets the required times of the intermediate nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 813 of file ivyFastMap.c.

{
    Ivy_Supp_t * pSupp;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    if ( pObj != pRoot && (pSupp->nRefs > 0 || Ivy_ObjIsCi(pObj)) )
        return;
    Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin0(pObj), pRoot, DelayR );
    Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin1(pObj), pRoot, DelayR );
//    assert( pObj == pRoot || pSupp->DelayR == IVY_INFINITY );
    pSupp->DelayR = DelayR;
}

void Ivy_FastMapStop

(

Ivy_Man_t *

pAig

)

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

Synopsis [Cleans memory used for decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 194 of file ivyFastMap.c.

{
    Ivy_SuppMan_t * p = (Ivy_SuppMan_t *)pAig->pData;
    Vec_VecFree( p->vLuts );
    ABC_FREE( p->pMem );
    ABC_FREE( p );
    pAig->pData = NULL;
}

static int Ivy_ObjIsNodeInt1 ( Ivy_Obj_t *  pObj )

inlinestatic

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 316 of file ivyFastMap.c.

{
    return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) == 1;
}

static int Ivy_ObjIsNodeInt2 ( Ivy_Obj_t *  pObj )

inlinestatic

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 332 of file ivyFastMap.c.

{
    return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) <= 2;
}

static Ivy_Supp_t* Ivy_ObjSupp ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

inlinestatic

Definition at line 55 of file ivyFastMap.c.

{ 
    return (Ivy_Supp_t *)(((Ivy_SuppMan_t*)pAig->pData)->pMem + pObj->Id * ((Ivy_SuppMan_t*)pAig->pData)->nSize); 
}

static Ivy_Supp_t* Ivy_ObjSuppStart ( Ivy_Man_t *  pAig, Ivy_Obj_t *  pObj  )

inlinestatic

Definition at line 59 of file ivyFastMap.c.

{ 
    Ivy_Supp_t * pSupp;
    pSupp = Ivy_ObjSupp( pAig, pObj );
    pSupp->fMark = 0;
    pSupp->Delay = 0;
    pSupp->nSize = 1;
    pSupp->pArray[0] = pObj->Id;
    return pSupp;
}

static int Vec_IntRemoveDup ( int *  pArray, int  nSize  )

inlinestatic

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

Synopsis [Performs fast mapping for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 348 of file ivyFastMap.c.

{
    int i, k;
    if ( nSize < 2 )
        return nSize;
    for ( i = k = 1; i < nSize; i++ )
        if ( pArray[i] != pArray[i-1] )
            pArray[k++] = pArray[i];
    return k;
}

Variable Documentation

int s_MappingMem

Definition at line 45 of file abcPrint.c.

abctime s_MappingTime

DECLARATIONS ///.

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

FileName [abcPrint.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Printing statistics.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

abcPrint.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 44 of file abcPrint.c.