diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 08:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 08:01:00 -0800 |
commit | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (patch) | |
tree | 366355938a4af0a92f848841ac65374f338d691b /src/opt/lpk/lpkMux.c | |
parent | 6537f941887b06e588d3acfc97b5fdf48875cc4e (diff) | |
download | abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.gz abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.tar.bz2 abc-4d30a1e4f1edecff86d5066ce4653a370e59e5e1.zip |
Version abc80130
Diffstat (limited to 'src/opt/lpk/lpkMux.c')
-rw-r--r-- | src/opt/lpk/lpkMux.c | 247 |
1 files changed, 0 insertions, 247 deletions
diff --git a/src/opt/lpk/lpkMux.c b/src/opt/lpk/lpkMux.c deleted file mode 100644 index ed046ad7..00000000 --- a/src/opt/lpk/lpkMux.c +++ /dev/null @@ -1,247 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkMux.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkMux.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Find the best cofactoring variable.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_MapTreeBestCofVar( Lpk_Man_t * p, unsigned * pTruth, int nVars, unsigned * pCof0, unsigned * pCof1 ) -{ - int i, iBestVar, nSuppSizeCur0, nSuppSizeCur1, nSuppSizeCur, nSuppSizeMin; - // iterate through variables - iBestVar = -1; - nSuppSizeMin = KIT_INFINITY; - for ( i = 0; i < nVars; i++ ) - { - // cofactor the functiona and get support sizes - Kit_TruthCofactor0New( pCof0, pTruth, nVars, i ); - Kit_TruthCofactor1New( pCof1, pTruth, nVars, i ); - nSuppSizeCur0 = Kit_TruthSupportSize( pCof0, nVars ); - nSuppSizeCur1 = Kit_TruthSupportSize( pCof1, nVars ); - nSuppSizeCur = nSuppSizeCur0 + nSuppSizeCur1; - // skip cofactoring that goes above the limit - if ( nSuppSizeCur0 > p->pPars->nLutSize || nSuppSizeCur1 > p->pPars->nLutSize ) - continue; - // compare this variable with other variables - if ( nSuppSizeMin > nSuppSizeCur ) - { - nSuppSizeMin = nSuppSizeCur; - iBestVar = i; - } - } - // cofactor w.r.t. this variable - if ( iBestVar != -1 ) - { - Kit_TruthCofactor0New( pCof0, pTruth, nVars, iBestVar ); - Kit_TruthCofactor1New( pCof1, pTruth, nVars, iBestVar ); - } - return iBestVar; -} - -/**Function************************************************************* - - Synopsis [Maps the function by the best cofactoring.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapTreeMux_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) -{ - unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); - unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); - If_Obj_t * pObj0, * pObj1; - Kit_DsdNtk_t * ppNtks[2]; - int iBestVar; - assert( nVars > 3 ); - p->fCalledOnce = 1; - // cofactor w.r.t. the best variable - iBestVar = Lpk_MapTreeBestCofVar( p, pTruth, nVars, pCof0, pCof1 ); - if ( iBestVar == -1 ) - return NULL; - // decompose the functions - ppNtks[0] = Kit_DsdDecompose( pCof0, nVars ); - ppNtks[1] = Kit_DsdDecompose( pCof1, nVars ); - if ( p->pPars->fVeryVerbose ) - { - printf( "Cofactoring w.r.t. var %c (%d -> %d+%d supp vars):\n", - 'a'+iBestVar, nVars, Kit_TruthSupportSize(pCof0, nVars), Kit_TruthSupportSize(pCof1, nVars) ); - Kit_DsdPrintExpanded( ppNtks[0] ); - Kit_DsdPrintExpanded( ppNtks[1] ); - } - // map the DSD structures - pObj0 = Lpk_MapTree_rec( p, ppNtks[0], ppLeaves, ppNtks[0]->Root, NULL ); - pObj1 = Lpk_MapTree_rec( p, ppNtks[1], ppLeaves, ppNtks[1]->Root, NULL ); - Kit_DsdNtkFree( ppNtks[0] ); - Kit_DsdNtkFree( ppNtks[1] ); - return If_ManCreateMux( p->pIfMan, pObj0, pObj1, ppLeaves[iBestVar] ); -} - - - -/**Function************************************************************* - - Synopsis [Implements support-reducing decomposition.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapSuppRedDec_rec( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) -{ - Kit_DsdNtk_t * pNtkDec, * pNtkComp, * ppNtks[2], * pTemp; - If_Obj_t * pObjNew; - unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); - unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); - unsigned * pDec0 = Vec_PtrEntry( p->vTtNodes, 2 ); - unsigned * pDec1 = Vec_PtrEntry( p->vTtNodes, 3 ); - unsigned * pDec = Vec_PtrEntry( p->vTtNodes, 4 ); - unsigned * pCo00 = Vec_PtrEntry( p->vTtNodes, 5 ); - unsigned * pCo01 = Vec_PtrEntry( p->vTtNodes, 6 ); - unsigned * pCo10 = Vec_PtrEntry( p->vTtNodes, 7 ); - unsigned * pCo11 = Vec_PtrEntry( p->vTtNodes, 8 ); - unsigned * pCo0 = Vec_PtrEntry( p->vTtNodes, 9 ); - unsigned * pCo1 = Vec_PtrEntry( p->vTtNodes, 10 ); - unsigned * pCo = Vec_PtrEntry( p->vTtNodes, 11 ); - int TrueMint0, TrueMint1, FalseMint0, FalseMint1; - int uSubsets, uSubset0, uSubset1, iVar, iVarReused, i; - - // determine if supp-red decomposition exists - uSubsets = Lpk_MapSuppRedDecSelect( p, pTruth, nVars, &iVar, &iVarReused ); - if ( uSubsets == 0 ) - return NULL; - p->nCalledSRed++; - - // get the cofactors - Kit_TruthCofactor0New( pCof0, pTruth, nVars, iVar ); - Kit_TruthCofactor1New( pCof1, pTruth, nVars, iVar ); - - // get the bound sets - uSubset0 = uSubsets & 0xFFFF; - uSubset1 = uSubsets >> 16; - - // compute the decomposed functions - ppNtks[0] = Kit_DsdDecompose( pCof0, nVars ); - ppNtks[1] = Kit_DsdDecompose( pCof1, nVars ); - ppNtks[0] = Kit_DsdExpand( pTemp = ppNtks[0] ); Kit_DsdNtkFree( pTemp ); - ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] ); Kit_DsdNtkFree( pTemp ); - Kit_DsdTruthPartial( p->pDsdMan, ppNtks[0], pDec0, uSubset0 ); - Kit_DsdTruthPartial( p->pDsdMan, ppNtks[1], pDec1, uSubset1 ); -// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[0], uSubset0, iVarReused, pCo0, pDec0 ); -// Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[1], uSubset1, iVarReused, pCo1, pDec1 ); - Kit_DsdNtkFree( ppNtks[0] ); - Kit_DsdNtkFree( ppNtks[1] ); -//Kit_DsdPrintFromTruth( pDec0, nVars ); -//Kit_DsdPrintFromTruth( pDec1, nVars ); - // get the decomposed function - Kit_TruthMuxVar( pDec, pDec0, pDec1, nVars, iVar ); - - // find any true assignments of the decomposed functions - TrueMint0 = Kit_TruthFindFirstBit( pDec0, nVars ); - TrueMint1 = Kit_TruthFindFirstBit( pDec1, nVars ); - assert( TrueMint0 >= 0 && TrueMint1 >= 0 ); - // find any false assignments of the decomposed functions - FalseMint0 = Kit_TruthFindFirstZero( pDec0, nVars ); - FalseMint1 = Kit_TruthFindFirstZero( pDec1, nVars ); - assert( FalseMint0 >= 0 && FalseMint1 >= 0 ); - - // cofactor the cofactors according to these minterms - Kit_TruthCopy( pCo00, pCof0, nVars ); - Kit_TruthCopy( pCo01, pCof0, nVars ); - for ( i = 0; i < nVars; i++ ) - if ( uSubset0 & (1 << i) ) - { - if ( FalseMint0 & (1 << i) ) - Kit_TruthCofactor1( pCo00, nVars, i ); - else - Kit_TruthCofactor0( pCo00, nVars, i ); - if ( TrueMint0 & (1 << i) ) - Kit_TruthCofactor1( pCo01, nVars, i ); - else - Kit_TruthCofactor0( pCo01, nVars, i ); - } - Kit_TruthCopy( pCo10, pCof1, nVars ); - Kit_TruthCopy( pCo11, pCof1, nVars ); - for ( i = 0; i < nVars; i++ ) - if ( uSubset1 & (1 << i) ) - { - if ( FalseMint1 & (1 << i) ) - Kit_TruthCofactor1( pCo10, nVars, i ); - else - Kit_TruthCofactor0( pCo10, nVars, i ); - if ( TrueMint1 & (1 << i) ) - Kit_TruthCofactor1( pCo11, nVars, i ); - else - Kit_TruthCofactor0( pCo11, nVars, i ); - } - - // derive the functions by composing them with the new variable (iVarReused) - Kit_TruthMuxVar( pCo0, pCo00, pCo01, nVars, iVarReused ); - Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused ); -//Kit_DsdPrintFromTruth( pCo0, nVars ); -//Kit_DsdPrintFromTruth( pCo1, nVars ); - - // derive the composition function - Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar ); - - // process the decomposed function - pNtkDec = Kit_DsdDecompose( pDec, nVars ); - pNtkComp = Kit_DsdDecompose( pCo, nVars ); -//Kit_DsdPrint( stdout, pNtkDec ); -//Kit_DsdPrint( stdout, pNtkComp ); -//printf( "cofactored variable %c\n", 'a' + iVar ); -//printf( "reused variable %c\n", 'a' + iVarReused ); - - ppLeaves[iVarReused] = Lpk_MapTree_rec( p, pNtkDec, ppLeaves, pNtkDec->Root, NULL ); - pObjNew = Lpk_MapTree_rec( p, pNtkComp, ppLeaves, pNtkComp->Root, NULL ); - - Kit_DsdNtkFree( pNtkDec ); - Kit_DsdNtkFree( pNtkComp ); - return pObjNew; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |