diff options
Diffstat (limited to 'src/aig/ivy/ivyMulti.c')
| -rw-r--r-- | src/aig/ivy/ivyMulti.c | 301 |
1 files changed, 301 insertions, 0 deletions
diff --git a/src/aig/ivy/ivyMulti.c b/src/aig/ivy/ivyMulti.c new file mode 100644 index 00000000..a7970156 --- /dev/null +++ b/src/aig/ivy/ivyMulti.c @@ -0,0 +1,301 @@ +/**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" + +//////////////////////////////////////////////////////////////////////// +/// 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, * 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( 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( 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( 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(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, * pEvalBest; + unsigned uMaskAll, uFound, uTemp; + int i, k, BestK, WeightBest, WeightCur, LevelBest, 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 /// +//////////////////////////////////////////////////////////////////////// + + |