ivyMulti8.c File Reference

#include "ivy.h"

Go to the source code of this file.

Data Structures
struct	Ivy_Eval_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Ivy_Eval_t_	Ivy_Eval_t
	DECLARATIONS ///. More...

Functions
static Ivy_Obj_t *	Ivy_MultiBuild_rec (Ivy_Eval_t *pEvals, int iNum, Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
static void	Ivy_MultiSort (Ivy_Obj_t **pArgs, int nArgs)
static int	Ivy_MultiPushUniqueOrderByLevel (Ivy_Obj_t **pArray, int nArgs, Ivy_Obj_t *pNode)
static Ivy_Obj_t *	Ivy_MultiEval (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
Ivy_Obj_t *	Ivy_Multi_rec (Ivy_Obj_t **ppObjs, int nObjs, Ivy_Type_t Type)
	FUNCTION DEFINITIONS ///. More...
Ivy_Obj_t *	Ivy_Multi (Ivy_Obj_t **pArgsInit, int nArgs, Ivy_Type_t Type)
Ivy_Obj_t *	Ivy_MultiBalance_rec (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
Ivy_Obj_t *	Ivy_Multi1 (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
Ivy_Obj_t *	Ivy_Multi2 (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Ivy_Eval_t_ Ivy_Eval_t

DECLARATIONS ///.

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

FileName [ivyMulti.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Constructing multi-input AND/EXOR gates.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]

Definition at line 30 of file ivyMulti8.c.

Function Documentation

Ivy_Obj_t* Ivy_Multi	(	Ivy_Obj_t **	pArgsInit,
		int	nArgs,
		Ivy_Type_t	Type
	)

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

Synopsis [Constructs a balanced tree while taking sharing into account.]

Description []

SideEffects []

SeeAlso []

Definition at line 83 of file ivyMulti8.c.

{
    static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5};
    static Ivy_Eval_t pEvals[15+15*14/2];
    static Ivy_Obj_t * pArgs[16];
    Ivy_Eval_t * pEva, * pEvaBest;
    int nArgsNew, nEvals, i, k;
    Ivy_Obj_t * pTemp;

    // consider the case of one argument
    assert( nArgs > 0 );
    if ( nArgs == 1 )
        return pArgsInit[0];
    // consider the case of two arguments
    if ( nArgs == 2 )
        return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type );

//Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" );

    // set the initial ones
    for ( i = 0; i < nArgs; i++ )
    {
        pArgs[i] = pArgsInit[i];
        pEva = pEvals + i;
        pEva->Mask   = (1 << i);
        pEva->Weight = 1;
        pEva->Cost   = 0; 
        pEva->Level  = Ivy_Regular(pArgs[i])->Level; 
        pEva->Fan0   = 0; 
        pEva->Fan1   = 0; 
    }

    // find the available nodes
    pEvaBest = pEvals;
    nArgsNew = nArgs;
    for ( i = 1; i < nArgsNew; i++ )
    for ( k = 0; k < i; k++ )
        if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) )
        {
            pEva = pEvals + nArgsNew;
            pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
            pEva->Weight = NumBits[pEva->Mask];
            pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
            pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
            pEva->Fan0   = k; 
            pEva->Fan1   = i; 
//            assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) );
            // compare
            if ( pEvaBest->Weight < pEva->Weight ||
                 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
                 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
                 pEvaBest = pEva;
            // save the argument
            pArgs[nArgsNew++] = pTemp;
            if ( nArgsNew == 15 )
                goto Outside;
        }
Outside:

//    printf( "Best = %d.\n", pEvaBest - pEvals );

    // the case of no common nodes
    if ( nArgsNew == nArgs )
    {
        Ivy_MultiSort( pArgs, nArgs );
        return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
    }
    // the case of one common node
    if ( nArgsNew == nArgs + 1 )
    {
        assert( pEvaBest - pEvals == nArgs );
        k = 0;
        for ( i = 0; i < nArgs; i++ )
            if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 )
                pArgs[k++] = pArgs[i];
        pArgs[k++] = pArgs[nArgs];
        assert( k == nArgs - 1 );
        nArgs = k;
        Ivy_MultiSort( pArgs, nArgs );
        return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
    }
    // the case when there is a node that covers everything
    if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) )
        return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); 

    // evaluate node pairs
    nEvals = nArgsNew;
    for ( i = 1; i < nArgsNew; i++ )
    for ( k = 0; k < i; k++ )
    {
        pEva = pEvals + nEvals;
        pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
        pEva->Weight = NumBits[pEva->Mask];
        pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
        pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
        pEva->Fan0   = k; 
        pEva->Fan1   = i; 
        // compare
        if ( pEvaBest->Weight < pEva->Weight ||
             pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
             pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
             pEvaBest = pEva;
        // save the argument
        nEvals++;
    }
    assert( pEvaBest - pEvals >= nArgsNew );

//    printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 );

    // get the best implementation
    pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type );

    // collect those not covered by EvaBest
    k = 0;
    for ( i = 0; i < nArgs; i++ )
        if ( (pEvaBest->Mask & (1 << i)) == 0 )
            pArgs[k++] = pArgs[i];
    pArgs[k++] = pTemp;
    assert( k == nArgs - (int)pEvaBest->Weight + 1 );
    nArgs = k;
    Ivy_MultiSort( pArgs, nArgs );
    return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
}

Ivy_Obj_t* Ivy_Multi1	(	Ivy_Obj_t **	pArgs,
		int	nArgs,
		Ivy_Type_t	Type
	)

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

Synopsis [Old code.]

Description []

SideEffects []

SeeAlso []

Definition at line 363 of file ivyMulti8.c.

{
    Ivy_Obj_t * pArgsRef[5], * pTemp;
    int i, k, m, nArgsNew, Counter = 0;
 
    
//Ivy_MultiEval( pArgs, nArgs, Type );  printf( "\n" );


    assert( Type == IVY_AND || Type == IVY_EXOR );
    assert( nArgs > 0 );
    if ( nArgs == 1 )
        return pArgs[0];

    // find the nodes with more than one fanout
    nArgsNew = 0;
    for ( i = 0; i < nArgs; i++ )
        if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 )
            pArgsRef[nArgsNew++] = pArgs[i];

    // go through pairs
    if ( nArgsNew >= 2 )
    for ( i = 0; i < nArgsNew; i++ )
    for ( k = i + 1; k < nArgsNew; k++ )
        if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
            Counter++;
//    printf( "%d", Counter );
            
    // go through pairs
    if ( nArgsNew >= 2 )
    for ( i = 0; i < nArgsNew; i++ )
    for ( k = i + 1; k < nArgsNew; k++ )
        if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
        {
            nArgsNew = 0;
            for ( m = 0; m < nArgs; m++ )
                if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] )
                    pArgs[nArgsNew++] = pArgs[m];
            pArgs[nArgsNew++] = pTemp;
            assert( nArgsNew == nArgs - 1 );
            return Ivy_Multi1( pArgs, nArgsNew, Type );
        }
    return Ivy_Multi_rec( pArgs, nArgs, Type );
}

Ivy_Obj_t* Ivy_Multi2	(	Ivy_Obj_t **	pArgs,
		int	nArgs,
		Ivy_Type_t	Type
	)

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

Synopsis [Old code.]

Description []

SideEffects []

SeeAlso []

Definition at line 419 of file ivyMulti8.c.

{
    assert( Type == IVY_AND || Type == IVY_EXOR );
    assert( nArgs > 0 );
    return Ivy_Multi_rec( pArgs, nArgs, Type );
}

Ivy_Obj_t* Ivy_Multi_rec	(	Ivy_Obj_t **	ppObjs,
		int	nObjs,
		Ivy_Type_t	Type
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Constructs the well-balanced tree of gates.]

Description [Disregards levels and possible logic sharing.]

SideEffects []

SeeAlso []

Definition at line 62 of file ivyMulti8.c.

{
    Ivy_Obj_t * pObj1, * pObj2;
    if ( nObjs == 1 )
        return ppObjs[0];
    pObj1 = Ivy_Multi_rec( ppObjs,           nObjs/2,         Type );
    pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type );
    return Ivy_Oper( pObj1, pObj2, Type );
}

Ivy_Obj_t* Ivy_MultiBalance_rec	(	Ivy_Obj_t **	pArgs,
		int	nArgs,
		Ivy_Type_t	Type
	)

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

Synopsis [Balances the array recursively.]

Description []

SideEffects []

SeeAlso []

Definition at line 301 of file ivyMulti8.c.

{
    Ivy_Obj_t * pNodeNew;
    // consider the case of one argument
    assert( nArgs > 0 );
    if ( nArgs == 1 )
        return pArgs[0];
    // consider the case of two arguments
    if ( nArgs == 2 )
        return Ivy_Oper( pArgs[0], pArgs[1], Type );
    // get the last two nodes
    pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type );
    // add the new node
    nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew );
    return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
}

Ivy_Obj_t * Ivy_MultiBuild_rec ( Ivy_Eval_t *  pEvals, int  iNum, Ivy_Obj_t **  pArgs, int  nArgs, Ivy_Type_t  Type  )

static

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

Synopsis [Implements multi-input AND/EXOR operation.]

Description []

SideEffects []

SeeAlso []

Definition at line 218 of file ivyMulti8.c.

{
    Ivy_Obj_t * pNode0, * pNode1;
    if ( iNum < nArgs )
        return pArgs[iNum];
    pNode0 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan0, pArgs, nArgs, Type );
    pNode1 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan1, pArgs, nArgs, Type );
    return Ivy_Oper( pNode0, pNode1, Type );
}

Ivy_Obj_t * Ivy_MultiEval ( Ivy_Obj_t **  pArgs, int  nArgs, Ivy_Type_t  Type  )

static

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

Synopsis [Implements multi-input AND/EXOR operation.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file ivyMulti8.c.

{
    Ivy_Obj_t * pTemp;
    int i, k;
    int nArgsOld = nArgs;
    for ( i = 0; i < nArgs; i++ )
        printf( "%d[%d] ", i, Ivy_Regular(pArgs[i])->Level );
    for ( i = 1; i < nArgs; i++ )
        for ( k = 0; k < i; k++ )
        {
            pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE));
            if ( pTemp != NULL )
            {
                printf( "%d[%d]=(%d,%d) ", nArgs, Ivy_Regular(pTemp)->Level, k, i );
                pArgs[nArgs++] = pTemp;
            }
        }
    printf( "     ((%d/%d))    ", nArgsOld, nArgs-nArgsOld );
    return NULL;
}

int Ivy_MultiPushUniqueOrderByLevel ( Ivy_Obj_t **  pArray, int  nArgs, Ivy_Obj_t *  pNode  )

static

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 267 of file ivyMulti8.c.

{
    Ivy_Obj_t * pNode1, * pNode2;
    int i;
    // try to find the node in the array
    for ( i = 0; i < nArgs; i++ )
        if ( pArray[i] == pNode )
            return nArgs;
    // put the node last
    pArray[nArgs++] = pNode;
    // find the place to put the new node
    for ( i = nArgs-1; i > 0; i-- )
    {
        pNode1 = pArray[i  ];
        pNode2 = pArray[i-1];
        if ( Ivy_Regular(pNode1)->Level <= Ivy_Regular(pNode2)->Level )
            break;
        pArray[i  ] = pNode2;
        pArray[i-1] = pNode1;
    }
    return nArgs;
}

void Ivy_MultiSort ( Ivy_Obj_t **  pArgs, int  nArgs  )

static

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

Synopsis [Selection-sorts the nodes in the decreasing over of level.]

Description []

SideEffects []

SeeAlso []

Definition at line 239 of file ivyMulti8.c.

{
    Ivy_Obj_t * pTemp;
    int i, j, iBest;

    for ( i = 0; i < nArgs-1; i++ )
    {
        iBest = i;
        for ( j = i+1; j < nArgs; j++ )
            if ( Ivy_Regular(pArgs[j])->Level > Ivy_Regular(pArgs[iBest])->Level )
                iBest = j;
        pTemp = pArgs[i]; 
        pArgs[i] = pArgs[iBest]; 
        pArgs[iBest] = pTemp;
    }
}