giaBalLut.c File Reference

#include "gia.h"
#include "misc/vec/vecHash.h"
#include "misc/vec/vecQue.h"
#include "opt/dau/dau.h"

Go to the source code of this file.

Data Structures
struct	Bal_Cut_t_
struct	Bal_Man_t_

Macros
#define	BAL_LEAF_MAX   6
	DECLARATIONS ///. More...
#define	BAL_CUT_MAX   8
#define	BAL_SUPER   50
#define	BAL_NO_LEAF   31
#define	BAL_NO_FUNC   134217727

Typedefs
typedef struct Bal_Cut_t_	Bal_Cut_t
typedef struct Bal_Man_t_	Bal_Man_t

Functions
static Bal_Man_t *	Bal_GiaMan (Gia_Man_t *p)
static int	Bal_ObjCost (Bal_Man_t *p, int i)
static int	Bal_LitCost (Bal_Man_t *p, int i)
static int	Bal_ObjDelay (Bal_Man_t *p, int i)
static int	Bal_LitDelay (Bal_Man_t *p, int i)
Bal_Man_t *	Bal_ManAlloc (Gia_Man_t *pGia, Gia_Man_t *pNew, int nLutSize, int nCutNum, int fVerbose)
	FUNCTION DEFINITIONS ///. More...
void	Bal_ManFree (Bal_Man_t *p)
static int	Bal_CutCountBits (word i)
static word	Bal_CutGetSign (int *pLeaves, int nLeaves)
static int	Bal_CutCreateUnit (Bal_Cut_t *p, int i, int Delay)
static int	Bal_ManPrepareSet (Bal_Man_t *p, int iObj, int Index, int fUnit, Bal_Cut_t **ppCutSet)
static int	Bal_CutCheck (Bal_Cut_t *pBase, Bal_Cut_t *pCut)
static int	Bal_SetCheckArray (Bal_Cut_t **ppCuts, int nCuts)
static int	Bal_CutMergeOrder (Bal_Cut_t *pCut0, Bal_Cut_t *pCut1, Bal_Cut_t *pCut, int nLutSize)
static int	Bal_CutMergeOrderMux (Bal_Cut_t *pCut0, Bal_Cut_t *pCut1, Bal_Cut_t *pCut2, Bal_Cut_t *pCut, int nLutSize)
static int	Bal_SetCutIsContainedOrder (Bal_Cut_t *pBase, Bal_Cut_t *pCut)
static int	Bal_SetLastCutIsContained (Bal_Cut_t **pCuts, int nCuts)
static int	Bal_SetLastCutContains (Bal_Cut_t **pCuts, int nCuts)
static int	Bal_CutCompareArea (Bal_Cut_t *pCut0, Bal_Cut_t *pCut1)
static void	Bal_SetSortByDelay (Bal_Cut_t **pCuts, int nCuts)
static int	Bal_SetAddCut (Bal_Cut_t **pCuts, int nCuts, int nCutNum)
int	Bal_ManDeriveCuts (Bal_Man_t *p, int iFan0, int iFan1, int iFan2, int fCompl0, int fCompl1, int fCompl2, int fUnit0, int fUnit1, int fUnit2, int fIsXor, int Target, int fSave)
int	Bal_ManSetGateLevel (Bal_Man_t *p, Gia_Obj_t *pObjOld, int iLitNew)
int	Bal_ManEvalTwo (Bal_Man_t *p, int iLitNew0, int iLitNew1, int iLitNew2, int fIsXor)
static void	Vec_IntSelectSortCostLit (Vec_Int_t *vSuper, Vec_Int_t *vCosts)
static void	Vec_IntPushOrderCost (Vec_Int_t *vSuper, Vec_Int_t *vCosts, int iLit)
static int	Vec_IntFindFirstSameDelayAsLast (Bal_Man_t *p, Vec_Int_t *vSuper)
static int	Bal_ManFindBestPair (Bal_Man_t *p, Vec_Int_t *vSuper, Gia_Obj_t *pObj)
static void	Gia_ManSimplifyXor (Vec_Int_t *vSuper)
static void	Gia_ManSimplifyAnd (Vec_Int_t *vSuper)
static void	Gia_ManSuperCollectXor_rec (Gia_Man_t *p, Gia_Obj_t *pObj)
static void	Gia_ManSuperCollectAnd_rec (Gia_Man_t *p, Gia_Obj_t *pObj)
static void	Gia_ManSuperCollect (Gia_Man_t *p, Gia_Obj_t *pObj)
static void	Gia_ManCreateGate (Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper)
static int	Gia_ManBalanceGate (Gia_Man_t *pNew, Gia_Obj_t *pObj, Vec_Int_t *vSuper, int *pLits, int nLits)
static void	Gia_ManBalance_rec (Gia_Man_t *pNew, Gia_Man_t *p, Gia_Obj_t *pObj)
static Gia_Man_t *	Gia_ManBalanceInt (Gia_Man_t *p, int nLutSize, int nCutNum, int fVerbose)
Gia_Man_t *	Gia_ManBalanceLut (Gia_Man_t *p, int nLutSize, int nCutNum, int fVerbose)

Macro Definition Documentation

#define BAL_CUT_MAX   8

Definition at line 34 of file giaBalLut.c.

#define BAL_LEAF_MAX   6

DECLARATIONS ///.

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

FileName [giaBalance.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Scalable AIG package.]

Synopsis [AIG balancing.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]

Definition at line 33 of file giaBalLut.c.

#define BAL_NO_FUNC   134217727

Definition at line 37 of file giaBalLut.c.

#define BAL_NO_LEAF   31

Definition at line 36 of file giaBalLut.c.

#define BAL_SUPER   50

Definition at line 35 of file giaBalLut.c.

Typedef Documentation

typedef struct Bal_Cut_t_ Bal_Cut_t

Definition at line 39 of file giaBalLut.c.

typedef struct Bal_Man_t_ Bal_Man_t

Definition at line 50 of file giaBalLut.c.

Function Documentation

static int Bal_CutCheck ( Bal_Cut_t *  pBase, Bal_Cut_t *  pCut  )

inlinestatic

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

Synopsis [Check correctness of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 168 of file giaBalLut.c.

{
    int nSizeB = pBase->nLeaves;
    int nSizeC = pCut->nLeaves;
    int i, * pB = pBase->pLeaves;
    int k, * pC = pCut->pLeaves;
    for ( i = 0; i < nSizeC; i++ )
    {
        for ( k = 0; k < nSizeB; k++ )
            if ( pC[i] == pB[k] )
                break;
        if ( k == nSizeB )
            return 0;
    }
    return 1;
}

static int Bal_CutCompareArea ( Bal_Cut_t *  pCut0, Bal_Cut_t *  pCut1  )

inlinestatic

Definition at line 364 of file giaBalLut.c.

{
    if ( pCut0->Delay   < pCut1->Delay   )  return -1;
    if ( pCut0->Delay   > pCut1->Delay   )  return  1;
    if ( pCut0->nLeaves < pCut1->nLeaves )  return -1;
    if ( pCut0->nLeaves > pCut1->nLeaves )  return  1;
    return 0;
}

static int Bal_CutCountBits ( word  i )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file giaBalLut.c.

{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
    return (i*(0x0101010101010101))>>56;
}

static int Bal_CutCreateUnit ( Bal_Cut_t *  p, int  i, int  Delay  )

inlinestatic

Definition at line 135 of file giaBalLut.c.

{
    p->iFunc = 2;
    p->Delay = Delay;
    p->nLeaves = 1;
    p->pLeaves[0] = i;
    p->Sign = ((word)1) << (i & 0x3F);
    return 1;
}

static word Bal_CutGetSign ( int *  pLeaves, int  nLeaves  )

inlinestatic

Definition at line 128 of file giaBalLut.c.

{
    word Sign = 0; int i; 
    for ( i = 0; i < nLeaves; i++ )
        Sign |= ((word)1) << (pLeaves[i] & 0x3F);
    return Sign;
}

static int Bal_CutMergeOrder ( Bal_Cut_t *  pCut0, Bal_Cut_t *  pCut1, Bal_Cut_t *  pCut, int  nLutSize  )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file giaBalLut.c.

{ 
    int nSize0   = pCut0->nLeaves;
    int nSize1   = pCut1->nLeaves;
    int i, * pC0 = pCut0->pLeaves;
    int k, * pC1 = pCut1->pLeaves;
    int c, * pC  = pCut->pLeaves;
    // the case of the largest cut sizes
    if ( nSize0 == nLutSize && nSize1 == nLutSize )
    {
        for ( i = 0; i < nSize0; i++ )
        {
            if ( pC0[i] != pC1[i] )  return 0;
            pC[i] = pC0[i];
        }
        pCut->nLeaves = nLutSize;
        pCut->iFunc = BAL_NO_FUNC;
        pCut->Sign = pCut0->Sign | pCut1->Sign;
        pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
        return 1;
    }
    // compare two cuts with different numbers
    i = k = c = 0;
    while ( 1 )
    {
        if ( c == nLutSize ) return 0;
        if ( pC0[i] < pC1[k] )
        {
            pC[c++] = pC0[i++];
            if ( i >= nSize0 ) goto FlushCut1;
        }
        else if ( pC0[i] > pC1[k] )
        {
            pC[c++] = pC1[k++];
            if ( k >= nSize1 ) goto FlushCut0;
        }
        else
        {
            pC[c++] = pC0[i++]; k++;
            if ( i >= nSize0 ) goto FlushCut1;
            if ( k >= nSize1 ) goto FlushCut0;
        }
    }

FlushCut0:
    if ( c + nSize0 > nLutSize + i ) return 0;
    while ( i < nSize0 )
        pC[c++] = pC0[i++];
    pCut->nLeaves = c;
    pCut->iFunc = BAL_NO_FUNC;
    pCut->Sign = pCut0->Sign | pCut1->Sign;
    pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
    return 1;

FlushCut1:
    if ( c + nSize1 > nLutSize + k ) return 0;
    while ( k < nSize1 )
        pC[c++] = pC1[k++];
    pCut->nLeaves = c;
    pCut->iFunc = BAL_NO_FUNC;
    pCut->Sign = pCut0->Sign | pCut1->Sign;
    pCut->Delay = Abc_MaxInt( pCut0->Delay, pCut1->Delay );
    return 1;
}

static int Bal_CutMergeOrderMux ( Bal_Cut_t *  pCut0, Bal_Cut_t *  pCut1, Bal_Cut_t *  pCut2, Bal_Cut_t *  pCut, int  nLutSize  )

inlinestatic

Definition at line 287 of file giaBalLut.c.

{ 
    int x0, i0 = 0, nSize0 = pCut0->nLeaves, * pC0 = pCut0->pLeaves;
    int x1, i1 = 0, nSize1 = pCut1->nLeaves, * pC1 = pCut1->pLeaves;
    int x2, i2 = 0, nSize2 = pCut2->nLeaves, * pC2 = pCut2->pLeaves;
    int xMin, c = 0, * pC  = pCut->pLeaves;
    while ( 1 )
    {
        x0 = (i0 == nSize0) ? ABC_INFINITY : pC0[i0];
        x1 = (i1 == nSize1) ? ABC_INFINITY : pC1[i1];
        x2 = (i2 == nSize2) ? ABC_INFINITY : pC2[i2];
        xMin = Abc_MinInt( Abc_MinInt(x0, x1), x2 );
        if ( xMin == ABC_INFINITY ) break;
        if ( c == nLutSize ) return 0;
        pC[c++] = xMin;
        if (x0 == xMin) i0++;
        if (x1 == xMin) i1++;
        if (x2 == xMin) i2++;
    }
    pCut->nLeaves = c;
    pCut->iFunc = BAL_NO_FUNC;
    pCut->Sign = pCut0->Sign | pCut1->Sign | pCut2->Sign;
    pCut->Delay = Abc_MaxInt( pCut0->Delay, Abc_MaxInt(pCut1->Delay, pCut2->Delay) );
    return 1;
}

static Bal_Man_t* Bal_GiaMan ( Gia_Man_t *  p )

inlinestatic

Definition at line 64 of file giaBalLut.c.

{ return (Bal_Man_t *)p->pData;           }

static int Bal_LitCost ( Bal_Man_t *  p, int  i  )

inlinestatic

Definition at line 67 of file giaBalLut.c.

{ return Bal_ObjCost(p, Abc_Lit2Var(i));  }

static int Bal_LitDelay ( Bal_Man_t *  p, int  i  )

inlinestatic

Definition at line 69 of file giaBalLut.c.

{ return Bal_ObjDelay(p, Abc_Lit2Var(i)); }

Bal_Man_t* Bal_ManAlloc	(	Gia_Man_t *	pGia,
		Gia_Man_t *	pNew,
		int	nLutSize,
		int	nCutNum,
		int	fVerbose
	)

FUNCTION DEFINITIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file giaBalLut.c.

{
    Bal_Man_t * p;
    p = ABC_CALLOC( Bal_Man_t, 1 );
    p->clkStart = Abc_Clock();
    p->pGia     = pGia;
    p->pNew     = pNew;
    p->nLutSize = nLutSize;
    p->nCutNum  = nCutNum;
    p->fVerbose = fVerbose;
    p->vCosts   = Vec_IntAlloc( 3 * Gia_ManObjNum(pGia) / 2 );
    p->vCutSets = Vec_PtrAlloc( 3 * Gia_ManObjNum(pGia) / 2 );
    Vec_IntFill( p->vCosts, Gia_ManObjNum(pNew), 0 );
    Vec_PtrFill( p->vCutSets, Gia_ManObjNum(pNew), NULL );
    pNew->pData = p;
    return p;
}

int Bal_ManDeriveCuts	(	Bal_Man_t *	p,
		int	iFan0,
		int	iFan1,
		int	iFan2,
		int	fCompl0,
		int	fCompl1,
		int	fCompl2,
		int	fUnit0,
		int	fUnit1,
		int	fUnit2,
		int	fIsXor,
		int	Target,
		int	fSave
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 402 of file giaBalLut.c.

{
    Bal_Cut_t pCutSet[BAL_CUT_MAX], * pCutsR[BAL_CUT_MAX];
    Bal_Cut_t * pCutSet0, * pCutSet1, * pCutSet2;
    int nCuts0 = Bal_ManPrepareSet( p, iFan0, 0, fUnit0, &pCutSet0 );
    int nCuts1 = Bal_ManPrepareSet( p, iFan1, 1, fUnit1, &pCutSet1 );
    Bal_Cut_t * pCut0, * pCut0Lim = pCutSet0 + nCuts0;
    Bal_Cut_t * pCut1, * pCut1Lim = pCutSet1 + nCuts1;
    int i, Cost, nCutsR = 0;
    memset( pCutSet, 0, sizeof(Bal_Cut_t) * p->nCutNum );
    for ( i = 0; i < p->nCutNum; i++ )
        pCutsR[i] = pCutSet + i;
    // enumerate cuts
    if ( iFan2 > 0 )
    {
        int nCuts2 = Bal_ManPrepareSet( p, iFan2, 2, fUnit2, &pCutSet2 );
        Bal_Cut_t * pCut2, * pCut2Lim = pCutSet2 + nCuts2;
        for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ )
        for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ )
        for ( pCut2 = pCutSet2; pCut2 < pCut2Lim; pCut2++ )
        {
            if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign | pCut2->Sign) > p->nLutSize )
                continue;
            if ( !Bal_CutMergeOrderMux(pCut0, pCut1, pCut2, pCutsR[nCutsR], p->nLutSize) )
                continue;
            assert( pCutsR[nCutsR]->Delay == Target );
            if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) )
                continue;
//            if ( p->fCutMin && Bal_CutComputeTruthMux(p, pCut0, pCut1, pCut2, fCompl0, fCompl1, fCompl2, pCutsR[nCutsR]) )
//                pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves);
            nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum );
        }
    }
    else
    {
        for ( pCut0 = pCutSet0; pCut0 < pCut0Lim; pCut0++ )
        for ( pCut1 = pCutSet1; pCut1 < pCut1Lim; pCut1++ )
        {
            if ( Bal_CutCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
                continue;
            if ( !Bal_CutMergeOrder(pCut0, pCut1, pCutsR[nCutsR], p->nLutSize) )
                continue;
            assert( pCutsR[nCutsR]->Delay == Target );
            if ( Bal_SetLastCutIsContained(pCutsR, nCutsR) )
                continue;
//            if ( p->fCutMin && Bal_CutComputeTruth(p, pCut0, pCut1, fCompl0, fCompl1, pCutsR[nCutsR], fIsXor) )
//                pCutsR[nCutsR]->Sign = Bal_CutGetSign(pCutsR[nCutsR]->pLeaves, pCutsR[nCutsR]->nLeaves);
            nCutsR = Bal_SetAddCut( pCutsR, nCutsR, p->nCutNum );
        }
    }
    if ( nCutsR == 0 )
        return -1;
//printf( "%d ", nCutsR );
    Cost = ((pCutsR[0]->Delay << 4) | pCutsR[0]->nLeaves);
    // verify
    assert( nCutsR > 0 && nCutsR < p->nCutNum );
    assert( Bal_SetCheckArray(pCutsR, nCutsR) );
    // save cuts
    if ( fSave && Cost >= 0 )
    {
        pCutSet0 = ABC_CALLOC( Bal_Cut_t, p->nCutNum );
        Vec_PtrPush( p->vCutSets, pCutSet0 );
        assert( Vec_PtrSize(p->vCutSets) == Gia_ManObjNum(p->pNew) );
        for ( i = 0; i < nCutsR; i++ )
            pCutSet0[i] = *pCutsR[i];        
        for ( ; i < p->nCutNum; i++ )
            pCutSet0[i].nLeaves = BAL_NO_LEAF;
        Vec_IntPush( p->vCosts, Cost );
        assert( Vec_IntSize(p->vCosts) == Gia_ManObjNum(p->pNew) );
    }
    return Cost;
}

int Bal_ManEvalTwo	(	Bal_Man_t *	p,
		int	iLitNew0,
		int	iLitNew1,
		int	iLitNew2,
		int	fIsXor
	)

Definition at line 526 of file giaBalLut.c.

{
    int iFan0    = Abc_Lit2Var( iLitNew0 );
    int iFan1    = Abc_Lit2Var( iLitNew1 );
    int iFan2    = Abc_Lit2Var( iLitNew2 );
    int fCompl0  = Abc_LitIsCompl( iLitNew0 );
    int fCompl1  = Abc_LitIsCompl( iLitNew1 );
    int fCompl2  = Abc_LitIsCompl( iLitNew2 );
    int Delay0   = Bal_ObjDelay( p, iFan0 );
    int Delay1   = Bal_ObjDelay( p, iFan1 );
    int Delay2   = Bal_ObjDelay( p, iFan2 );
    int DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) );
    int fUnit0   = (int)(Delay0 != DelayMax); 
    int fUnit1   = (int)(Delay1 != DelayMax); 
    int fUnit2   = (int)(Delay2 != DelayMax); 
    if ( DelayMax == 0 )
        return -1;
    return Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, fIsXor, DelayMax, 0 );
}

static int Bal_ManFindBestPair ( Bal_Man_t *  p, Vec_Int_t *  vSuper, Gia_Obj_t *  pObj  )

inlinestatic

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

Synopsis [Select the best pair to merge.]

Description []

SideEffects []

SeeAlso []

Definition at line 610 of file giaBalLut.c.

{
    int * pSuper = Vec_IntArray(vSuper);
    int iBeg = Vec_IntFindFirstSameDelayAsLast( p, vSuper );
    int iEnd = Vec_IntSize(vSuper)-1;
    int i, k, iBest = -1, kBest = -1, BestCost = ABC_INFINITY, Cost;
    assert( iBeg <= iEnd );
    // check if we can add to the higher levels without increasing cost
    for ( k = iBeg-1; k >= 0; k-- )
    for ( i = iEnd; i >= iBeg; i-- )
    {
        Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) );
        if ( Cost == -1 )
            continue;
        if ( Cost == Bal_LitCost(p, pSuper[k]) )
        {
//            printf( "A" );
            return (k << 16)|i;
        }
        if ( BestCost > Cost )
            BestCost = Cost, iBest = i, kBest = k;
    }
    if ( BestCost != ABC_INFINITY && (BestCost >> 4) == Bal_LitDelay(p, pSuper[kBest]) )
    {
//        printf( "B" );
        return (kBest << 16)|iBest;
    }
    // check if some can be added to lowest level without increasing cost
    BestCost = ABC_INFINITY;
    for ( i = iBeg; i <= iEnd; i++ )
    for ( k = i+1;  k <= iEnd; k++ )
    {
        Cost = Bal_ManEvalTwo( p, pSuper[i], pSuper[k], 0, Gia_ObjIsXor(pObj) );
        if ( Cost == -1 )
            continue;
        if ( Cost == Abc_MaxInt(Bal_LitCost(p, pSuper[i]), Bal_LitCost(p, pSuper[k])) )
        {
//            printf( "C" );
            return (k << 16)|i;
        }
        if ( BestCost > Cost )
            BestCost = Cost, iBest = i, kBest = k;
    }
    if ( BestCost != ABC_INFINITY )
    {
//        printf( "D" );
        return (kBest << 16)|iBest;
    }
//    printf( "E" );
    // group pairs from lowest level based on proximity
    return (iEnd << 16)|(iEnd-1);
}

void Bal_ManFree

(

Bal_Man_t *

p

)

Definition at line 103 of file giaBalLut.c.

{
    Vec_PtrFreeFree( p->vCutSets );
    Vec_IntFree( p->vCosts );
    ABC_FREE( p );
}

static int Bal_ManPrepareSet ( Bal_Man_t *  p, int  iObj, int  Index, int  fUnit, Bal_Cut_t **  ppCutSet  )

inlinestatic

Definition at line 144 of file giaBalLut.c.

{
    static Bal_Cut_t CutTemp[3]; int i;
    if ( Vec_PtrEntry(p->vCutSets, iObj) == NULL || fUnit )
        return Bal_CutCreateUnit( (*ppCutSet = CutTemp + Index), iObj, Bal_ObjDelay(p, iObj)+1 );
    *ppCutSet = (Bal_Cut_t *)Vec_PtrEntry(p->vCutSets, iObj);
    for ( i = 0; i < p->nCutNum; i++ ) 
        if ( (*ppCutSet)[i].nLeaves == BAL_NO_LEAF )
            return i;
    return i;
}

int Bal_ManSetGateLevel	(	Bal_Man_t *	p,
		Gia_Obj_t *	pObjOld,
		int	iLitNew
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 486 of file giaBalLut.c.

{
    int iFan0, iFan1, iFan2, Cost;
    int fCompl0, fCompl1, fCompl2;
    int fUnit0, fUnit1, fUnit2;
    int Delay0, Delay1, Delay2, DelayMax;
    int iObjNew = Abc_Lit2Var(iLitNew);
    Gia_Obj_t * pObjNew = Gia_ManObj( p->pNew, iObjNew );
    int fMux = Gia_ObjIsMux(p->pNew, pObjNew);
    if ( iObjNew < Vec_PtrSize(p->vCutSets) )
        return -1;
    iFan0    = Gia_ObjFaninId0( pObjNew, iObjNew );
    iFan1    = Gia_ObjFaninId1( pObjNew, iObjNew );
    iFan2    = fMux ? Gia_ObjFaninId2(p->pNew, iObjNew) : 0;
    fCompl0  = Gia_ObjFaninC0( pObjNew );
    fCompl1  = Gia_ObjFaninC1( pObjNew );
    fCompl2  = fMux ? Gia_ObjFaninC2(p->pNew, pObjNew) : 0;
    Delay0   = Bal_ObjDelay( p, iFan0 );
    Delay1   = Bal_ObjDelay( p, iFan1 );
    Delay2   = Bal_ObjDelay( p, iFan2 );
    DelayMax = Abc_MaxInt( Delay0, Abc_MaxInt(Delay1, Delay2) );
    fUnit0   = (int)(Delay0 != DelayMax); 
    fUnit1   = (int)(Delay1 != DelayMax); 
    fUnit2   = (int)(Delay2 != DelayMax); 
    if ( DelayMax > 0 )
    {
//printf( "A" );
        Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 );
//printf( "B" );
        if ( Cost >= 0 )
            return Cost;
    }
    DelayMax++;
    fUnit0 = fUnit1 = fUnit2 = 1;
//printf( "A" );
    Cost = Bal_ManDeriveCuts(p, iFan0, iFan1, iFan2, fCompl0, fCompl1, fCompl2, fUnit0, fUnit1, fUnit2, Gia_ObjIsXor(pObjNew), DelayMax, 1 );
//printf( "B" );
    assert( Cost >= 0 );
    return Cost;
}

static int Bal_ObjCost ( Bal_Man_t *  p, int  i  )

inlinestatic

Definition at line 66 of file giaBalLut.c.

{ return Vec_IntEntry(p->vCosts, i);      }

static int Bal_ObjDelay ( Bal_Man_t *  p, int  i  )

inlinestatic

Definition at line 68 of file giaBalLut.c.

{ return Bal_ObjCost(p, i) >> 4;          }

static int Bal_SetAddCut ( Bal_Cut_t **  pCuts, int  nCuts, int  nCutNum  )

inlinestatic

Definition at line 382 of file giaBalLut.c.

{
    if ( nCuts == 0 )
        return 1;
    nCuts = Bal_SetLastCutContains(pCuts, nCuts);
    Bal_SetSortByDelay( pCuts, nCuts );
    return Abc_MinInt( nCuts + 1, nCutNum - 1 );
}

static int Bal_SetCheckArray ( Bal_Cut_t **  ppCuts, int  nCuts  )

inlinestatic

Definition at line 184 of file giaBalLut.c.

{
    Bal_Cut_t * pCut0, * pCut1; 
    int i, k, m, n, Value;
    assert( nCuts > 0 );
    for ( i = 0; i < nCuts; i++ )
    {
        pCut0 = ppCuts[i];
        assert( pCut0->nLeaves <= BAL_LEAF_MAX );
        assert( pCut0->Sign == Bal_CutGetSign(pCut0->pLeaves, pCut0->nLeaves) );
        // check duplicates
        for ( m = 0; m < (int)pCut0->nLeaves; m++ )
        for ( n = m + 1; n < (int)pCut0->nLeaves; n++ )
            assert( pCut0->pLeaves[m] < pCut0->pLeaves[n] );
        // check pairs
        for ( k = 0; k < nCuts; k++ )
        {
            pCut1 = ppCuts[k];
            if ( pCut0 == pCut1 )
                continue;
            // check containments
            Value = Bal_CutCheck( pCut0, pCut1 );
            assert( Value == 0 );
        }
    }
    return 1;
}

static int Bal_SetCutIsContainedOrder ( Bal_Cut_t *  pBase, Bal_Cut_t *  pCut  )

inlinestatic

Definition at line 312 of file giaBalLut.c.

{
    int i, nSizeB = pBase->nLeaves;
    int k, nSizeC = pCut->nLeaves;
    if ( nSizeB == nSizeC )
    {
        for ( i = 0; i < nSizeB; i++ )
            if ( pBase->pLeaves[i] != pCut->pLeaves[i] )
                return 0;
        return 1;
    }
    assert( nSizeB > nSizeC ); 
    if ( nSizeC == 0 )
        return 1;
    for ( i = k = 0; i < nSizeB; i++ )
    {
        if ( pBase->pLeaves[i] > pCut->pLeaves[k] )
            return 0;
        if ( pBase->pLeaves[i] == pCut->pLeaves[k] )
        {
            if ( ++k == nSizeC )
                return 1;
        }
    }
    return 0;
}

static int Bal_SetLastCutContains ( Bal_Cut_t **  pCuts, int  nCuts  )

inlinestatic

Definition at line 346 of file giaBalLut.c.

{
    int i, k, fChanges = 0;
    for ( i = 0; i < nCuts; i++ )
        if ( pCuts[nCuts]->nLeaves < pCuts[i]->nLeaves && (pCuts[nCuts]->Sign & pCuts[i]->Sign) == pCuts[nCuts]->Sign && Bal_SetCutIsContainedOrder(pCuts[i], pCuts[nCuts]) )
            pCuts[i]->nLeaves = BAL_NO_LEAF, fChanges = 1;
    if ( !fChanges )
        return nCuts;
    for ( i = k = 0; i <= nCuts; i++ )
    {
        if ( pCuts[i]->nLeaves == BAL_NO_LEAF )
            continue;
        if ( k < i )
            ABC_SWAP( Bal_Cut_t *, pCuts[k], pCuts[i] );
        k++;
    }
    return k - 1;
}

static int Bal_SetLastCutIsContained ( Bal_Cut_t **  pCuts, int  nCuts  )

inlinestatic

Definition at line 338 of file giaBalLut.c.

{
    int i;
    for ( i = 0; i < nCuts; i++ )
        if ( pCuts[i]->nLeaves <= pCuts[nCuts]->nLeaves && (pCuts[i]->Sign & pCuts[nCuts]->Sign) == pCuts[i]->Sign && Bal_SetCutIsContainedOrder(pCuts[nCuts], pCuts[i]) )
            return 1;
    return 0;
}

static void Bal_SetSortByDelay ( Bal_Cut_t **  pCuts, int  nCuts  )

inlinestatic

= 1 )

Definition at line 372 of file giaBalLut.c.

{
    int i;
    for ( i = nCuts; i > 0; i-- )
    {
        if ( Bal_CutCompareArea(pCuts[i - 1], pCuts[i]) < 0 )//!= 1 )
            return;
        ABC_SWAP( Bal_Cut_t *, pCuts[i - 1], pCuts[i] );
    }
}

static void Gia_ManBalance_rec ( Gia_Man_t *  pNew, Gia_Man_t *  p, Gia_Obj_t *  pObj  )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 875 of file giaBalLut.c.

{
    int i, iLit, iBeg, iEnd;
    if ( ~pObj->Value )
        return;
    assert( Gia_ObjIsAnd(pObj) );
    // handle MUX
    if ( Gia_ObjIsMux(p, pObj) )
    {
        Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
        Gia_ManBalance_rec( pNew, p, Gia_ObjFanin1(pObj) );
        Gia_ManBalance_rec( pNew, p, Gia_ObjFanin2(p, pObj) );
        pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
        Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, pObj->Value );
//        Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(pObj->Value)) );
        return;
    }
    // find supergate
    Gia_ManSuperCollect( p, pObj );
    // save entries
    if ( p->vStore == NULL )
        p->vStore = Vec_IntAlloc( 1000 );
    iBeg = Vec_IntSize( p->vStore );
    Vec_IntAppend( p->vStore, p->vSuper );
    iEnd = Vec_IntSize( p->vStore );
    // call recursively
    Vec_IntForEachEntryStartStop( p->vStore, iLit, i, iBeg, iEnd )
    {
        Gia_Obj_t * pTemp = Gia_ManObj( p, Abc_Lit2Var(iLit) );
        Gia_ManBalance_rec( pNew, p, pTemp );
        Vec_IntWriteEntry( p->vStore, i, Abc_LitNotCond(pTemp->Value, Abc_LitIsCompl(iLit)) );
    }
    assert( Vec_IntSize(p->vStore) == iEnd );
    // consider general case
    pObj->Value = Gia_ManBalanceGate( pNew, pObj, p->vSuper, Vec_IntEntryP(p->vStore, iBeg), iEnd-iBeg );
    Vec_IntShrink( p->vStore, iBeg );
}

static int Gia_ManBalanceGate ( Gia_Man_t *  pNew, Gia_Obj_t *  pObj, Vec_Int_t *  vSuper, int *  pLits, int  nLits  )

inlinestatic

Definition at line 825 of file giaBalLut.c.

{
    Vec_IntClear( vSuper );
    if ( nLits == 1 )
        Vec_IntPush( vSuper, pLits[0] );
    else if ( nLits == 2 )
    {
        Vec_IntPush( vSuper, pLits[0] );
        Vec_IntPush( vSuper, pLits[1] );
        Gia_ManCreateGate( pNew, pObj, vSuper );
    }
    else if ( nLits > 2 )
    {
        Bal_Man_t * p = Bal_GiaMan(pNew); int i;
        for ( i = 0; i < nLits; i++ )
            Vec_IntPush( vSuper, pLits[i] );
        // sort by level/cut-size
        Vec_IntSelectSortCostLit( vSuper, p->vCosts );
        // iterate till everything is grouped
        while ( Vec_IntSize(vSuper) > 1 )
        {
            int iLit, Res = Bal_ManFindBestPair( p, vSuper, pObj );
            int iBest = Vec_IntEntry( vSuper, Res >> 16 );
            int kBest = Vec_IntEntry( vSuper, Res & 0xFFFF );
            Vec_IntRemove( vSuper, iBest );
            Vec_IntRemove( vSuper, kBest );
            if ( Gia_ObjIsXor(pObj) )
                iLit = Gia_ManHashXorReal( pNew, iBest, kBest );
            else 
                iLit = Gia_ManHashAnd( pNew, iBest, kBest );
            Bal_ManSetGateLevel( p, pObj, iLit );
            Vec_IntPushOrderCost( vSuper, p->vCosts, iLit );
        }
    }
    // consider trivial case
    assert( Vec_IntSize(vSuper) == 1 );
    return Vec_IntEntry(vSuper, 0);
}

static Gia_Man_t* Gia_ManBalanceInt ( Gia_Man_t *  p, int  nLutSize, int  nCutNum, int  fVerbose  )

inlinestatic

Definition at line 912 of file giaBalLut.c.

{
    Bal_Man_t * pMan;
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;
    int i;
    Gia_ManFillValue( p );
    Gia_ManCreateRefs( p ); 
    // start the new manager
    pNew = Gia_ManStart( 3*Gia_ManObjNum(p)/2 );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
    pNew->vLevels = Vec_IntStart( pNew->nObjsAlloc );
    // create constant and inputs
    Gia_ManConst0(p)->Value = 0;
    Gia_ManForEachCi( p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    // create balancing manager
    pMan = Bal_ManAlloc( p, pNew, nLutSize, nCutNum, fVerbose );
    // create internal nodes
    Gia_ManHashStart( pNew );
    Gia_ManForEachCo( p, pObj, i )
        Gia_ManBalance_rec( pNew, p, Gia_ObjFanin0(pObj) );
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
//    if ( fVerbose )
    {
        int nLevelMax = 0;
        Gia_ManForEachCo( pNew, pObj, i )
        {
            nLevelMax = Abc_MaxInt( nLevelMax, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) );
//            printf( "%d=%d ", i, Bal_ObjDelay(pMan, Gia_ObjFaninId0p(pNew, pObj)) );
        }
        printf( "Best delay = %d\n", nLevelMax );
    }

//    assert( Gia_ManObjNum(pNew) <= Gia_ManObjNum(p) );
    Gia_ManHashStop( pNew );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
    // delete manager
    Bal_ManFree( pMan );
    // perform cleanup
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

Gia_Man_t* Gia_ManBalanceLut	(	Gia_Man_t *	p,
		int	nLutSize,
		int	nCutNum,
		int	fVerbose
	)

Definition at line 959 of file giaBalLut.c.

{
    Gia_Man_t * pNew, * pNew1, * pNew2;
    if ( fVerbose )      Gia_ManPrintStats( p, NULL );
    pNew = Gia_ManDupMuxes( p, 2 );
    if ( fVerbose )      Gia_ManPrintStats( pNew, NULL );
    pNew1 = Gia_ManBalanceInt( pNew, nLutSize, nCutNum, fVerbose );
    if ( fVerbose )      Gia_ManPrintStats( pNew1, NULL );
    Gia_ManStop( pNew );
    pNew2 = Gia_ManDupNoMuxes( pNew1 );
    if ( fVerbose )      Gia_ManPrintStats( pNew2, NULL );
    Gia_ManStop( pNew1 );
    return pNew2;
}

static void Gia_ManCreateGate ( Gia_Man_t *  pNew, Gia_Obj_t *  pObj, Vec_Int_t *  vSuper  )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 800 of file giaBalLut.c.

{
    int iLit0 = Vec_IntPop(vSuper);
    int iLit1 = Vec_IntPop(vSuper);
    int iLit, i;
    if ( !Gia_ObjIsXor(pObj) )
        iLit = Gia_ManHashAnd( pNew, iLit0, iLit1 );
    else if ( pNew->pMuxes )
        iLit = Gia_ManHashXorReal( pNew, iLit0, iLit1 );
    else 
        iLit = Gia_ManHashXor( pNew, iLit0, iLit1 );
    Vec_IntPush( vSuper, iLit );
    Bal_ManSetGateLevel( Bal_GiaMan(pNew), pObj, iLit );
//    Gia_ObjSetGateLevel( pNew, Gia_ManObj(pNew, Abc_Lit2Var(iLit)) );
    // shift to the corrent location
    for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
    {
        int iLit1 = Vec_IntEntry(vSuper, i);
        int iLit2 = Vec_IntEntry(vSuper, i-1);
        if ( Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit1)) <= Gia_ObjLevelId(pNew, Abc_Lit2Var(iLit2)) )
            break;
        Vec_IntWriteEntry( vSuper, i,   iLit2 );
        Vec_IntWriteEntry( vSuper, i-1, iLit1 );
    }
}

static void Gia_ManSimplifyAnd ( Vec_Int_t *  vSuper )

inlinestatic

Definition at line 694 of file giaBalLut.c.

{
    int i, k = 0, Prev = -1, This;
    Vec_IntForEachEntry( vSuper, This, i )
    {
        if ( This == 0 )
            { Vec_IntFill(vSuper, 1, 0); return; }
        if ( This == 1 )
            continue;
        if ( Prev == -1 || Abc_Lit2Var(Prev) != Abc_Lit2Var(This) )
            Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
        else if ( Prev != This )
            { Vec_IntFill(vSuper, 1, 0); return; }
    }
    Vec_IntShrink( vSuper, k );
    if ( Vec_IntSize( vSuper ) == 0 )
        Vec_IntPush( vSuper, 1 );
}

static void Gia_ManSimplifyXor ( Vec_Int_t *  vSuper )

inlinestatic

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

Synopsis [Simplify multi-input AND/XOR.]

Description []

SideEffects []

SeeAlso []

Definition at line 674 of file giaBalLut.c.

{
    int i, k = 0, Prev = -1, This, fCompl = 0;
    Vec_IntForEachEntry( vSuper, This, i )
    {
        if ( This == 0 )
            continue;
        if ( This == 1 )
            fCompl ^= 1; 
        else if ( Prev != This )
            Vec_IntWriteEntry( vSuper, k++, This ), Prev = This;
        else
            Prev = -1, k--;
    }
    Vec_IntShrink( vSuper, k );
    if ( Vec_IntSize( vSuper ) == 0 )
        Vec_IntPush( vSuper, fCompl );
    else if ( fCompl )
        Vec_IntWriteEntry( vSuper, 0, Abc_LitNot(Vec_IntEntry(vSuper, 0)) );
}

static void Gia_ManSuperCollect ( Gia_Man_t *  p, Gia_Obj_t *  pObj  )

inlinestatic

Definition at line 755 of file giaBalLut.c.

{
//    int nSize;
    if ( p->vSuper == NULL )
        p->vSuper = Vec_IntAlloc( 1000 );
    else
        Vec_IntClear( p->vSuper );
    if ( Gia_ObjIsXor(pObj) )
    {
        assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
        Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) );
        Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) );
//        nSize = Vec_IntSize(vSuper);
        Vec_IntSort( p->vSuper, 0 );
        Gia_ManSimplifyXor( p->vSuper );
//        if ( nSize != Vec_IntSize(vSuper) )
//            printf( "X %d->%d  ", nSize, Vec_IntSize(vSuper) );
    }
    else if ( Gia_ObjIsAndReal(p, pObj) )
    {
        Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) );
        Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) );
//        nSize = Vec_IntSize(vSuper);
        Vec_IntSort( p->vSuper, 0 );
        Gia_ManSimplifyAnd( p->vSuper );
//        if ( nSize != Vec_IntSize(vSuper) )
//            printf( "A %d->%d  ", nSize, Vec_IntSize(vSuper) );
    }
    else assert( 0 );
//    if ( nSize > 10 )
//        printf( "%d ", nSize );
    assert( Vec_IntSize(p->vSuper) > 0 );
}

static void Gia_ManSuperCollectAnd_rec ( Gia_Man_t *  p, Gia_Obj_t *  pObj  )

inlinestatic

Definition at line 740 of file giaBalLut.c.

{
    if ( Gia_IsComplement(pObj) || 
        !Gia_ObjIsAndReal(p, pObj) || 
//        Gia_ObjRefNum(p, pObj) > 1 || 
        Gia_ObjRefNum(p, pObj) > 3 || 
//        (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || 
        Vec_IntSize(p->vSuper) > BAL_SUPER )
    {
        Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
        return;
    }
    Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild0(pObj) );
    Gia_ManSuperCollectAnd_rec( p, Gia_ObjChild1(pObj) );
}

static void Gia_ManSuperCollectXor_rec ( Gia_Man_t *  p, Gia_Obj_t *  pObj  )

inlinestatic

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

Synopsis [Collect multi-input AND/XOR.]

Description []

SideEffects []

SeeAlso []

Definition at line 724 of file giaBalLut.c.

{
    assert( !Gia_IsComplement(pObj) );
    if ( !Gia_ObjIsXor(pObj) || 
//        Gia_ObjRefNum(p, pObj) > 1 || 
        Gia_ObjRefNum(p, pObj) > 3 || 
//        (Gia_ObjRefNum(p, pObj) == 2 && (Gia_ObjRefNum(p, Gia_ObjFanin0(pObj)) == 1 || Gia_ObjRefNum(p, Gia_ObjFanin1(pObj)) == 1)) || 
        Vec_IntSize(p->vSuper) > BAL_SUPER )
    {
        Vec_IntPush( p->vSuper, Gia_ObjToLit(p, pObj) );
        return;
    }
    assert( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) );
    Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin0(pObj) );
    Gia_ManSuperCollectXor_rec( p, Gia_ObjFanin1(pObj) );
}

static int Vec_IntFindFirstSameDelayAsLast ( Bal_Man_t *  p, Vec_Int_t *  vSuper  )

inlinestatic

Definition at line 584 of file giaBalLut.c.

{
    int i, DelayCur, Delay = Bal_LitDelay( p, Vec_IntEntryLast(vSuper) );
    assert( Vec_IntSize(vSuper) > 1 );
    for ( i = Vec_IntSize(vSuper)-1; i > 0; i-- )
    {
        DelayCur = Bal_LitDelay( p, Vec_IntEntry(vSuper, i-1) );
        assert( DelayCur >= Delay );
        if ( DelayCur > Delay )
            return i;
    }
    return i;
}

static void Vec_IntPushOrderCost ( Vec_Int_t *  vSuper, Vec_Int_t *  vCosts, int  iLit  )

inlinestatic

Definition at line 571 of file giaBalLut.c.

{
    int i, nSize, * pArray;
    Vec_IntPush( vSuper, iLit );
    pArray = Vec_IntArray(vSuper);
    nSize = Vec_IntSize(vSuper);
    for ( i = nSize-1; i > 0; i-- )
    {
        if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i])) <= Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[i - 1])) )
            return;
        ABC_SWAP( int, pArray[i], pArray[i - 1] );
    }
}

static void Vec_IntSelectSortCostLit ( Vec_Int_t *  vSuper, Vec_Int_t *  vCosts  )

inlinestatic

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

Synopsis [Sort literals by their cost.]

Description []

SideEffects []

SeeAlso []

Definition at line 557 of file giaBalLut.c.

{
    int * pArray = Vec_IntArray(vSuper);
    int nSize = Vec_IntSize(vSuper);
    int i, j, best_i;
    for ( i = 0; i < nSize-1; i++ )
    {
        best_i = i;
        for ( j = i+1; j < nSize; j++ )
            if ( Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[j])) > Vec_IntEntry(vCosts, Abc_Lit2Var(pArray[best_i])) )
                best_i = j;
        ABC_SWAP( int, pArray[i], pArray[best_i] );
    }
}