ivyMulti.c

Go to the documentation of this file.

/**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 $]

***********************************************************************/

#include "ivy.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

#define IVY_EVAL_LIMIT    128

typedef struct Ivy_Eva_t_ Ivy_Eva_t;
struct Ivy_Eva_t_
{
    Ivy_Obj_t * pArg;     // the argument node
    unsigned    Mask;     // the mask of covered nodes
    int         Weight;   // the number of covered nodes
};

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

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

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

  Description [Returns 1 if the implementation exists.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
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 )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ivy_MultiPrint( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals )
{
    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) );
    }
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Ivy_MultiWeight( unsigned uMask, int nMaskOnes, unsigned uFound )
{
    assert( uMask & ~uFound );
    if ( (uMask & uFound) == 0 )
        return nMaskOnes;
    return Extra_WordCountOnes( uMask & ~uFound );
}

/**Function*************************************************************

  Synopsis    [Finds the cover.]

  Description [Returns 1 if the cover is found.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ivy_MultiCover( Ivy_Man_t * p, Ivy_Eva_t * pEvals, int nLeaves, int nEvals, int nLimit, Vec_Ptr_t * vSols )
{
    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;
    }
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END