ivyMulti.c File Reference

#include "ivy.h"

Include dependency graph for ivyMulti.c:

Go to the source code of this file.

Classes
struct	Ivy_Eva_t_

Macros
#define	IVY_EVAL_LIMIT   128
	DECLARATIONS ///.

Typedefs
typedef struct Ivy_Eva_t_	Ivy_Eva_t

Functions
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 ///.

Macro Definition Documentation

IVY_EVAL_LIMIT

#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

Ivy_Eva_t

typedef struct Ivy_Eva_t_ Ivy_Eva_t

Definition at line 32 of file ivyMulti.c.

Function Documentation

Ivy_MultiPlus()

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;
}

Here is the call graph for this function: