diff options
Diffstat (limited to 'src/aig/ivy/ivyMulti.c')
| -rw-r--r-- | src/aig/ivy/ivyMulti.c | 301 |
1 files changed, 0 insertions, 301 deletions
diff --git a/src/aig/ivy/ivyMulti.c b/src/aig/ivy/ivyMulti.c deleted file mode 100644 index a7970156..00000000 --- a/src/aig/ivy/ivyMulti.c +++ /dev/null @@ -1,301 +0,0 @@ -/**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 /// -//////////////////////////////////////////////////////////////////////// - - |