ivyMulti.c File Reference

#include "ivy.h"

Go to the source code of this file.

Data Structures
struct	Ivy_Eva_t_

Macros
#define	IVY_EVAL_LIMIT   128
	DECLARATIONS ///. More...

Typedefs
typedef struct Ivy_Eva_t_	Ivy_Eva_t

Functions
static void	Ivy_MultiPrint (Ivy_Man_t *p, Ivy_Eva_t *pEvals, int nLeaves, int nEvals)
static int	Ivy_MultiCover (Ivy_Man_t *p, Ivy_Eva_t *pEvals, int nLeaves, int nEvals, int nLimit, Vec_Ptr_t *vSols)
int	Ivy_MultiPlus (Ivy_Man_t *p, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vCone, Ivy_Type_t Type, int nLimit, Vec_Ptr_t *vSols)
	FUNCTION DEFINITIONS ///. More...
static int	Ivy_MultiWeight (unsigned uMask, int nMaskOnes, unsigned uFound)

Macro Definition Documentation

#define IVY_EVAL_LIMIT   128

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 ivyMulti.c.

Typedef Documentation

typedef struct Ivy_Eva_t_ Ivy_Eva_t

Definition at line 32 of file ivyMulti.c.

Function Documentation

int Ivy_MultiCover ( Ivy_Man_t *  p, Ivy_Eva_t *  pEvals, int  nLeaves, int  nEvals, int  nLimit, Vec_Ptr_t *  vSols  )

static

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

Synopsis [Finds the cover.]

Description [Returns 1 if the cover is found.]

SideEffects []

SeeAlso []

Definition at line 222 of file ivyMulti.c.

{
    int fVerbose = 0;
    Ivy_Eva_t * pEval;
    Ivy_Eva_t * pEvalBest = NULL; // Suppress "might be used uninitialized"
    unsigned uMaskAll, uFound, uTemp;
    int i, k, BestK;
    int WeightBest = -1; // Suppress "might be used uninitialized"
    int WeightCur;
    int LevelBest = -1; // Suppress "might be used uninitialized"
    int LevelCur;
    uMaskAll = (nLeaves == 32)? (~(unsigned)0) : ((1 << nLeaves) - 1);
    uFound = 0;
    // solve the covering problem
    if ( fVerbose )
    printf( "Solution:  " );
    Vec_PtrClear( vSols );
    for ( i = 0; i < nLimit; i++ )
    {
        BestK = -1;
        for ( k = nEvals - 1; k >= 0; k-- )
        {
            pEval = pEvals + k;
            if ( (pEval->Mask & ~uFound) == 0 )
                continue;
            if ( BestK == -1 )
            {
                BestK      = k;
                pEvalBest  = pEval;
                WeightBest = Ivy_MultiWeight( pEvalBest->Mask, pEvalBest->Weight, uFound );
                LevelBest  = Ivy_ObjLevel( Ivy_Regular(pEvalBest->pArg) );
                continue;
            }
            // compare BestK and the new one (k)
            WeightCur = Ivy_MultiWeight( pEval->Mask, pEval->Weight, uFound );
            LevelCur = Ivy_ObjLevel( Ivy_Regular(pEval->pArg) );
            if ( WeightBest < WeightCur || 
                (WeightBest == WeightCur && LevelBest > LevelCur) )
            {
                BestK      = k;
                pEvalBest  = pEval;
                WeightBest = WeightCur;
                LevelBest  = LevelCur;
            }
        }
        assert( BestK != -1 );
        // if the cost is only 1, take the leaf
        if ( WeightBest == 1 && BestK >= nLeaves )
        {
            uTemp = (pEvalBest->Mask & ~uFound);
            for ( k = 0; k < nLeaves; k++ )
                if ( uTemp & (1 << k) )
                    break;
            assert( k < nLeaves );
            BestK     = k;
            pEvalBest = pEvals + BestK;
        }
        if ( fVerbose )
        {
            if ( BestK < nLeaves )
                printf( "L(%d) ", BestK );
            else
                printf( "%d ", BestK - nLeaves );
        }
        // update the found set
        Vec_PtrPush( vSols, pEvalBest->pArg );
        uFound |= pEvalBest->Mask;
        if ( uFound == uMaskAll )
            break;
    }
    if ( uFound == uMaskAll )
    {
        if ( fVerbose )
            printf( "  Found \n\n" );
        return 1;
    }
    else
    {
        if ( fVerbose )
            printf( "  Not found \n\n" );
        return 0;
    }
}

int Ivy_MultiPlus	(	Ivy_Man_t *	p,
		Vec_Ptr_t *	vLeaves,
		Vec_Ptr_t *	vCone,
		Ivy_Type_t	Type,
		int	nLimit,
		Vec_Ptr_t *	vSols
	)

FUNCTION DEFINITIONS ///.

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

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

Description [Returns 1 if the implementation exists.]

SideEffects []

SeeAlso []

Definition at line 58 of file ivyMulti.c.

{
    static Ivy_Eva_t pEvals[IVY_EVAL_LIMIT];
    Ivy_Eva_t * pEval, * pFan0, * pFan1;
    Ivy_Obj_t * pObj = NULL; // Suppress "might be used uninitialized"
    Ivy_Obj_t * pTemp;
    int nEvals, nEvalsOld, i, k, x, nLeaves;
    unsigned uMaskAll;

    // consider special cases
    nLeaves = Vec_PtrSize(vLeaves);
    assert( nLeaves > 2 );
    if ( nLeaves > 32 || nLeaves + Vec_PtrSize(vCone) > IVY_EVAL_LIMIT )
        return 0;
//    if ( nLeaves == 1 )
//        return Vec_PtrEntry( vLeaves, 0 );
//    if ( nLeaves == 2 )
//        return Ivy_Oper( Vec_PtrEntry(vLeaves, 0), Vec_PtrEntry(vLeaves, 1), Type );

    // set the leaf entries
    uMaskAll = ((1 << nLeaves) - 1);
    nEvals = 0;
    Vec_PtrForEachEntry( Ivy_Obj_t *, vLeaves, pObj, i )
    {
        pEval = pEvals + nEvals;
        pEval->pArg   = pObj;
        pEval->Mask   = (1 << nEvals);
        pEval->Weight = 1;
        // mark the leaf
        Ivy_Regular(pObj)->TravId = nEvals;
        nEvals++;
    }

    // propagate masks through the cone
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pObj, i )
    {
        pObj->TravId = nEvals + i;
        if ( Ivy_ObjIsBuf(pObj) )
            pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask;
        else
            pEvals[pObj->TravId].Mask = pEvals[Ivy_ObjFanin0(pObj)->TravId].Mask | pEvals[Ivy_ObjFanin1(pObj)->TravId].Mask;
    }

    // set the internal entries
    Vec_PtrForEachEntry( Ivy_Obj_t *, vCone, pObj, i )
    {
        if ( i == Vec_PtrSize(vCone) - 1 )
            break;
        // skip buffers
        if ( Ivy_ObjIsBuf(pObj) )
            continue;
        // skip nodes without external fanout
        if ( Ivy_ObjRefs(pObj) == 0 )
            continue;
        assert( !Ivy_IsComplement(pObj) );
        pEval = pEvals + nEvals;
        pEval->pArg   = pObj;
        pEval->Mask   = pEvals[pObj->TravId].Mask;
        pEval->Weight = Extra_WordCountOnes(pEval->Mask);
        // mark the node
        pObj->TravId = nEvals;
        nEvals++;
    }

    // find the available nodes
    nEvalsOld = nEvals;
    for ( i = 1; i < nEvals; i++ )
    for ( k = 0; k < i; k++ )
    {
        pFan0 = pEvals + i;
        pFan1 = pEvals + k;
        pTemp = Ivy_TableLookup(p, Ivy_ObjCreateGhost(p, pFan0->pArg, pFan1->pArg, Type, IVY_INIT_NONE));
        // skip nodes in the cone
        if ( pTemp == NULL || pTemp->fMarkB )
            continue;
        // skip the leaves
        for ( x = 0; x < nLeaves; x++ )
            if ( pTemp == Ivy_Regular((Ivy_Obj_t *)vLeaves->pArray[x]) )
                break;
        if ( x < nLeaves )
            continue;
        pEval = pEvals + nEvals;
        pEval->pArg   = pTemp;
        pEval->Mask   = pFan0->Mask | pFan1->Mask;
        pEval->Weight = (pFan0->Mask & pFan1->Mask) ? Extra_WordCountOnes(pEval->Mask) : pFan0->Weight + pFan1->Weight;
        // save the argument
        pObj->TravId = nEvals;
        nEvals++;
        // quit if the number of entries exceeded the limit
        if ( nEvals == IVY_EVAL_LIMIT )
            goto Outside;
        // quit if we found an acceptable implementation
        if ( pEval->Mask == uMaskAll )
            goto Outside;
    }
Outside:

//    Ivy_MultiPrint( pEvals, nLeaves, nEvals );
    if ( !Ivy_MultiCover( p, pEvals, nLeaves, nEvals, nLimit, vSols ) )
        return 0;
    assert( Vec_PtrSize( vSols ) > 0 );
    return 1;
}

void Ivy_MultiPrint ( Ivy_Man_t *  p, Ivy_Eva_t *  pEvals, int  nLeaves, int  nEvals  )

static

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

Synopsis [Computes how many uncovered ones this one covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file ivyMulti.c.

{
    Ivy_Eva_t * pEval;
    int i, k;
    for ( i = nLeaves; i < nEvals; i++ )
    {
        pEval = pEvals + i;
        printf( "%2d  (id = %5d)  : |", i-nLeaves, Ivy_ObjId(pEval->pArg) );
        for ( k = 0; k < nLeaves; k++ )
        {
            if ( pEval->Mask & (1 << k) )
                printf( "+" );
            else
                printf( " " );
        }
        printf( "|  Lev = %d.\n", Ivy_ObjLevel(pEval->pArg) );
    }
}

static int Ivy_MultiWeight ( unsigned  uMask, int  nMaskOnes, unsigned  uFound  )

inlinestatic

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

Synopsis [Computes how many uncovered ones this one covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 203 of file ivyMulti.c.

{
    assert( uMask & ~uFound );
    if ( (uMask & uFound) == 0 )
        return nMaskOnes;
    return Extra_WordCountOnes( uMask & ~uFound );
}