/**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 /// //////////////////////////////////////////////////////////////////////// typedef struct Ivy_Eval_t_ Ivy_Eval_t; struct Ivy_Eval_t_ { unsigned Mask : 5; // the mask of covered nodes unsigned Weight : 3; // the number of covered nodes unsigned Cost : 4; // the number of overlapping nodes unsigned Level : 12; // the level of this node unsigned Fan0 : 4; // the first fanin unsigned Fan1 : 4; // the second fanin }; static Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ); static void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs ); static int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode ); static Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Constructs the well-balanced tree of gates.] Description [Disregards levels and possible logic sharing.] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_Multi_rec( Ivy_Obj_t ** ppObjs, int nObjs, Ivy_Type_t Type ) { Ivy_Obj_t * pObj1, * pObj2; if ( nObjs == 1 ) return ppObjs[0]; pObj1 = Ivy_Multi_rec( ppObjs, nObjs/2, Type ); pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type ); return Ivy_Oper( pObj1, pObj2, Type ); } /**Function************************************************************* Synopsis [Constructs a balanced tree while taking sharing into account.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_Multi( Ivy_Obj_t ** pArgsInit, int nArgs, Ivy_Type_t Type ) { static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5}; static Ivy_Eval_t pEvals[15+15*14/2]; static Ivy_Obj_t * pArgs[16]; Ivy_Eval_t * pEva, * pEvaBest; int nArgsNew, nEvals, i, k; Ivy_Obj_t * pTemp; // consider the case of one argument assert( nArgs > 0 ); if ( nArgs == 1 ) return pArgsInit[0]; // consider the case of two arguments if ( nArgs == 2 ) return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type ); //Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" ); // set the initial ones for ( i = 0; i < nArgs; i++ ) { pArgs[i] = pArgsInit[i]; pEva = pEvals + i; pEva->Mask = (1 << i); pEva->Weight = 1; pEva->Cost = 0; pEva->Level = Ivy_Regular(pArgs[i])->Level; pEva->Fan0 = 0; pEva->Fan1 = 0; } // find the available nodes pEvaBest = pEvals; nArgsNew = nArgs; for ( i = 1; i < nArgsNew; i++ ) for ( k = 0; k < i; k++ ) if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) ) { pEva = pEvals + nArgsNew; pEva->Mask = pEvals[k].Mask | pEvals[i].Mask; pEva->Weight = NumBits[pEva->Mask]; pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); pEva->Fan0 = k; pEva->Fan1 = i; // assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) ); // compare if ( pEvaBest->Weight < pEva->Weight || pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost || pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level ) pEvaBest = pEva; // save the argument pArgs[nArgsNew++] = pTemp; if ( nArgsNew == 15 ) goto Outside; } Outside: // printf( "Best = %d.\n", pEvaBest - pEvals ); // the case of no common nodes if ( nArgsNew == nArgs ) { Ivy_MultiSort( pArgs, nArgs ); return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); } // the case of one common node if ( nArgsNew == nArgs + 1 ) { assert( pEvaBest - pEvals == nArgs ); k = 0; for ( i = 0; i < nArgs; i++ ) if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 ) pArgs[k++] = pArgs[i]; pArgs[k++] = pArgs[nArgs]; assert( k == nArgs - 1 ); nArgs = k; Ivy_MultiSort( pArgs, nArgs ); return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); } // the case when there is a node that covers everything if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) ) return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); // evaluate node pairs nEvals = nArgsNew; for ( i = 1; i < nArgsNew; i++ ) for ( k = 0; k < i; k++ ) { pEva = pEvals + nEvals; pEva->Mask = pEvals[k].Mask | pEvals[i].Mask; pEva->Weight = NumBits[pEva->Mask]; pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); pEva->Fan0 = k; pEva->Fan1 = i; // compare if ( pEvaBest->Weight < pEva->Weight || pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost || pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level ) pEvaBest = pEva; // save the argument nEvals++; } assert( pEvaBest - pEvals >= nArgsNew ); // printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 ); // get the best implementation pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); // collect those not covered by EvaBest k = 0; for ( i = 0; i < nArgs; i++ ) if ( (pEvaBest->Mask & (1 << i)) == 0 ) pArgs[k++] = pArgs[i]; pArgs[k++] = pTemp; assert( k == nArgs - (int)pEvaBest->Weight + 1 ); nArgs = k; Ivy_MultiSort( pArgs, nArgs ); return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); } /**Function************************************************************* Synopsis [Implements multi-input AND/EXOR operation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) { Ivy_Obj_t * pNode0, * pNode1; if ( iNum < nArgs ) return pArgs[iNum]; pNode0 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan0, pArgs, nArgs, Type ); pNode1 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan1, pArgs, nArgs, Type ); return Ivy_Oper( pNode0, pNode1, Type ); } /**Function************************************************************* Synopsis [Selection-sorts the nodes in the decreasing over of level.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs ) { Ivy_Obj_t * pTemp; int i, j, iBest; for ( i = 0; i < nArgs-1; i++ ) { iBest = i; for ( j = i+1; j < nArgs; j++ ) if ( Ivy_Regular(pArgs[j])->Level > Ivy_Regular(pArgs[iBest])->Level ) iBest = j; pTemp = pArgs[i]; pArgs[i] = pArgs[iBest]; pArgs[iBest] = pTemp; } } /**Function************************************************************* Synopsis [Inserts a new node in the order by levels.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode ) { Ivy_Obj_t * pNode1, * pNode2; int i; // try to find the node in the array for ( i = 0; i < nArgs; i++ ) if ( pArray[i] == pNode ) return nArgs; // put the node last pArray[nArgs++] = pNode; // find the place to put the new node for ( i = nArgs-1; i > 0; i-- ) { pNode1 = pArray[i ]; pNode2 = pArray[i-1]; if ( Ivy_Regular(pNode1)->Level <= Ivy_Regular(pNode2)->Level ) break; pArray[i ] = pNode2; pArray[i-1] = pNode1; } return nArgs; } /**Function************************************************************* Synopsis [Balances the array recursively.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_MultiBalance_rec( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) { Ivy_Obj_t * pNodeNew; // consider the case of one argument assert( nArgs > 0 ); if ( nArgs == 1 ) return pArgs[0]; // consider the case of two arguments if ( nArgs == 2 ) return Ivy_Oper( pArgs[0], pArgs[1], Type ); // get the last two nodes pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type ); // add the new node nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew ); return Ivy_MultiBalance_rec( pArgs, nArgs, Type ); } /**Function************************************************************* Synopsis [Implements multi-input AND/EXOR operation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) { Ivy_Obj_t * pTemp; int i, k; int nArgsOld = nArgs; for ( i = 0; i < nArgs; i++ ) printf( "%d[%d] ", i, Ivy_Regular(pArgs[i])->Level ); for ( i = 1; i < nArgs; i++ ) for ( k = 0; k < i; k++ ) { pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)); if ( pTemp != NULL ) { printf( "%d[%d]=(%d,%d) ", nArgs, Ivy_Regular(pTemp)->Level, k, i ); pArgs[nArgs++] = pTemp; } } printf( " ((%d/%d)) ", nArgsOld, nArgs-nArgsOld ); return NULL; } /**Function************************************************************* Synopsis [Old code.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_Multi1( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) { Ivy_Obj_t * pArgsRef[5], * pTemp; int i, k, m, nArgsNew, Counter = 0; //Ivy_MultiEval( pArgs, nArgs, Type ); printf( "\n" ); assert( Type == IVY_AND || Type == IVY_EXOR ); assert( nArgs > 0 ); if ( nArgs == 1 ) return pArgs[0]; // find the nodes with more than one fanout nArgsNew = 0; for ( i = 0; i < nArgs; i++ ) if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 ) pArgsRef[nArgsNew++] = pArgs[i]; // go through pairs if ( nArgsNew >= 2 ) for ( i = 0; i < nArgsNew; i++ ) for ( k = i + 1; k < nArgsNew; k++ ) if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) ) Counter++; // printf( "%d", Counter ); // go through pairs if ( nArgsNew >= 2 ) for ( i = 0; i < nArgsNew; i++ ) for ( k = i + 1; k < nArgsNew; k++ ) if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) ) { nArgsNew = 0; for ( m = 0; m < nArgs; m++ ) if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] ) pArgs[nArgsNew++] = pArgs[m]; pArgs[nArgsNew++] = pTemp; assert( nArgsNew == nArgs - 1 ); return Ivy_Multi1( pArgs, nArgsNew, Type ); } return Ivy_Multi_rec( pArgs, nArgs, Type ); } /**Function************************************************************* Synopsis [Old code.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Ivy_Obj_t * Ivy_Multi2( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type ) { assert( Type == IVY_AND || Type == IVY_EXOR ); assert( nArgs > 0 ); return Ivy_Multi_rec( pArgs, nArgs, Type ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END